基于K-center和信息增益的Web搜索结果聚类方法

基于K-center和信息增益的概念,将改进后的FPF(furthest-point-first)算法用于Web搜索结果聚类,提出了聚类标志方法,使得聚类呈现出的结果更易于用户理解,给出了评价聚类质量的模型。将该算法与Lingo,K-means算法进行比较,其结果表明,本算法能够较好地平衡聚类质量和速度,更加适用于Web检索聚类。

K-centers聚类算法在教学评估中的应用

考虑不同出现频率的可分类属性值对聚类中心的影响,通过重新定义聚类中心和距离,提出了一种新的聚类算法K-centers,这种算法能够有效处理可分类和混合类型数据。在此基础上,将K-centers应用于课程教学评估,分析不同类型课程的特点,为评估教学提供了参考。

一种面向SNP选择的K-Center算法

单核苷酸多态性(Single Nucleotide Polymorphism,SNP)数据是一种关于遗传病理学研究的重要数据,其高维少样本,存在大量噪声和冗余,并且SNP位点之间存在连锁不平衡性,因此需要对SNP数据进行降维。提出一种改进的K-Center算法——K-MSU算法。使用K-Center进行数据降维,在K-Center算法的距离度量中引入对称不确定性,解决SNP数据之间的连锁不平衡性;针对K-Center算法的随机选择初始聚类中心的方法容易对聚类结果产生较大的影响,使用基于信息增益的密度方法去选择初始聚类中心。在医院提供的临床实验数据的实验结果表明,K-MSU算法在SNP选择中具有更高的分类准确率和较好的效果。

Fair k-Center Problem with Outliers on Massive Data

The clustering problem of big data in the era of artificial intelligence has been widely studied.Because of the huge amount of data,distributed algorithms are often used to deal with big data problems.The distributed computing model has an attractive feature:it can handle massive datasets that cannot be put into the main memory.On the other hand,since many decisions are made automatically by machines in today’s society,algorithm fairness is also an important research area of machine learning.In this paper,we study two fair clustering problems:the centralized fair k-center problem with outliers and the distributed fair k-center problem with outliers.For these two problems,we have designed corresponding constant approximation ratio algorithms.The theoretical proof and analysis of the approximation ratio,and the running space of the algorithm are given.

满足参数不等式的k-Center问题的近似算法

考虑了无向完全图中满足参数不等式的k-Center问题,确切来讲,假定有一参数τ满足τ≥12,对于任意3个点x,y和z,都有dist(x,y)≤τ(dist(x,z)+dist(z,y)).利用罚参数中技术得到了1个2τ近似的算法,并且证明了对任意的ε>0,不存在2τ-ε近似,除非P=NP.用同样的技术得到了对于有权重限制的k-Center问题的1个2τ2+τ近似算法.

基于蚁群算法的三支k-means聚类算法

在聚类分析中,三支k-means聚类算法较具有较强的处理边界不确定数据的能力,但仍然存在对初始聚类中心敏感的问题.通过将蚁群算法和三支k-means聚类算法相结合,给出了一种基于蚁群算法的三支k-means聚类算法来解决这一问题.利用蚁群算法中随机概率选择策略和信息素的正负反馈机制,动态调整权重的方法,对三支k-means聚类算法进行优化.在UCI数据集上实验证明,该方法对聚类结果的性能指标有所提高.

基于改进K-means算法的物流配送中心选址研究

针对传统K-means算法需要主观设定K值及无法处理类别型数据问题,文章运用肘部法及轮廓系数法确定合理K值,对类别型数据采取独热编码(One-Hot Encoding)转换为可以处理的连续型数据,并将其运用到在物流配送中心选址中;并综合考虑多种类别的影响因素,构建了相应的影响因素指标体系,提出的模型能够识别输入数据的数值型及类别型数据,实现样本的有效聚类。相关的案例分析结果表明,相比传统K-means聚类,文章的改进K-means算法选址结果可使物流总成本降低8.76%,运营成本降低14.85%,固定成本降低8.09%,效果显著。

基于MapReduce的大规模网络社区发现算法

社区发现是社会网络挖掘领域的基本问题。随着海量数据的迅速产生,传统社区发现算法愈发难以处理大规模社会网络。因此,针对大规模网络设计高效的社区发现算法意义重大。文中提出了一种基于MapReduce和k中心聚类的新型分布式算法。首先,该算法提出“朋友圈系数”技术,该技术可更加准确地度量结点间的距离。其次,该算法提出“两阶段k中心聚类”技术,该技术在选取中心点过程中融入结点中心度启发式信息,可显著优化输出结果的模块度。最后,该算法提出“以模块度为优化目标的社区融合”技术,该技术能够在无先验知识的前提下自动确定网络中的社区数目。实验结果表明,所提算法的社区发现结果模块度明显优于最先进的社区发现算法。例如,相比LPA算法,其将模块度平均提升9.19倍。

基于3D激光雷达的鸡舍通道中心线检测方法

针对笼养鸡舍环境下光照强度弱、作业通道内狭小导致机器人巡检时通道中心线检测困难的问题,该研究利用3D激光雷达对鸡舍通道中心线进行获取。首先通过机器人搭载的3D激光雷达对鸡舍作业通道信息进行采集,利用直通滤波、地面点滤波、体素滤波、统计滤波和平面投影对获取的3D激光雷达点云数据进行预处理,获取XOY平面上的点云数据。通过改变K-means聚类初始点选择方式和聚类函数对预处理后的点云数据进行数据分类。利用改进RANSAC算法对分类后的数据进行处理,提取通道中心线。试验结果表明该研究提出的改进K-means聚类算法平均耗时6.98 ms,相较于传统的K-means聚类算法平均耗时减少了29.40 ms,准确率提高了82.41%。该研究提出的改进RANSAC算法中心线提取准确率为93.66%、平均误差角为0.89°、平均耗时为3.97 ms,比LSM算法得到的平均绝对误差角高0.14°,平均耗时减少6.15 ms。表明该研究提出的鸡舍通道中心线检测方法基本满足笼养鸡舍环境实时自主导航的需求,为巡检机器人在鸡舍作业通道内进行激光雷达导航提供了技术支撑。

自适应引力密度峰值聚类优化算法

针对密度峰值聚类(Density Peak Clustering,DPC)算法对截断距离的取值较为敏感,密度度量标准不统一且人为选取聚类中心存在主观性的问题,提出了一种自适应引力密度峰值聚类优化(Optimized Adaptive Gravitational Density Peak Clustering Algorithm,OAGDPC)算法。首先采用模糊加权K-近邻技术(Fuzzy Weighted KNearest Neighbors Density Peak Clustering,FKNN-DPC)重新定义了局部密度,统一了密度度量的标准;然后提出一种自适应选择聚类中心的策略,结合基于引力的密度峰值(Gravitational Density Peak Clustering,GDPC)算法中牛顿万有引力定律与DPC算法的参数映射,使用引力类比距离,并设置综合考虑局部密度和引力的决策参数,依据决策参数降序折线图的顶角变化自适应确定聚类中心;最后聚集非中心点并识别异常点。实验选取DPC、GDPC、FKNN-DPC和OAGDPC在人工和UCI数据集上进行测试,结果表明,OAGDPC算法在各数据集上都有良好的表现,特别在聚类结果准确性、自适应能力、鲁棒性方面相对于对比算法具有明显优势。

基于改进K-means聚类定心算法的曲轴轴颈圆度误差评定

曲轴轴颈的圆度误差作为曲轴必检的核心尺寸,直接影响曲轴的寿命和性能。针对圆度误差求解数据量多和计算复杂的问题,提出一种基于改进K-means聚类定心算法的圆度误差评定方法。该算法通过对轴颈采样通道的样本点进行环形聚类获得集合UK,同时以设计的目标控制器剔除UK的噪声点,以UK的最小二乘法圆度评定误差fm来估计整个环形样本的误差。聚类值从K=5循环迭代增加,直至fm符合预设统计质量控制规划。评定结果表明,聚类定心算法的圆度误差评定方法能实现曲轴圆度误差的高效、精确评定。

动态粒度结合中心点算法在电力设备缺陷管控中的应用研究

针对电力设备缺陷管控问题,文章研究提出了一种基于改进k-中心点聚类算法与动态粒度的电力设备缺陷管控模型。首先,利用改进的k-中心点聚类算法对设备缺陷数据进行聚类处理;然后,将动态粒度与改进算法进行结合,用于构建缺陷管控模型。结果表明,缺陷管控模型的数据聚类正确率为93.07%,聚类效率能够达到90.07%,同时数据识别准确率、召回率和F1值分别为93.27%、93.52%和0.951,均优于对比方法。这说明研究构建的电力设备缺陷管控模型显著可以提高设备的可靠性和稳定性。

k度匿名社交网络隐私保护方法

随着社交网络的迅速发展,社交网络积累了大量的数据,它们在一定程度上反映了社会规律。社交网络分析人员研究这些数据可得到有用的信息,但在该过程中,往往伴随着用户隐私泄露。针对如何在挖掘有效知识的问题中保证隐私安全,提出了k度匿名社交网络隐私保护方法(k degree anonymity social network privacy protection method,KDSNP)。首先,将社交网络转化为度序列,采用聚类的方法生成超点,再对超点进行划分得出至少包含k个节点的超点,以满足k度匿名的要求保证用户隐私,最后通过邻域中心概念和结构相似度相结合,对节点的边进行删除和增加,能有效减少信息损失和提高数据的效用性。在不同的数据集上的试验结果表明,与其他类似技术相比,该方法在匿名图和原始图间的平均相对性能较好。

基于参数优化VMD和改进K聚类判据融合的配电网故障选线方法

针对现有暂态量选线方法易受到故障相角、过渡电阻、噪声、谐波及判据阈值的影响,提出基于参数优化变分模态分解(variational mode decomposition,VMD)和改进K聚类判据融合的选线方法。首先对分解过程的3个关键性参数进行动态优化,利用信号频谱及分量特性确定VMD分解层数,并以算术优化算法求取最佳惩罚因子,剔除了工频、噪声及谐波干扰,再根据分解层数与各模态频谱确定模态中心频率以提高分解效率。其次,以优化后的VMD获取余弦相似度、高频幅值和直流能量作为互补的故障选线判据值。最后以改进K聚类算法实现多判据融合,弥补了单一判据的局限性。理论分析、仿真与实测结果表明,所提方法适用于分布式电源接入的电网,不受故障位置、故障相角及过渡电阻的影响,具有优异的抗谐波与噪声干扰性能。

优先级k-中心问题的FPT近似算法

优先级k-中心问题是聚类领域中1个经典的NP-难问题。给定度量空间中的1个集合X和参数k∈N+,其中,集合X中每个点v都被赋予1个优先级参数r(v)∈R+,求解1个大小为k的子集S■X,考虑集合X中任意数据点到集合S的距离与r(v)之间比值,找到最大比值,目标是最小化该比值。对于优先级k-中心问题,目前最好的结近似算法是多项式时间内的2-近似算法,该问题不存在1个(2-ε)-近似算法,(其中,ε为用于控制算法近似比的参数)。本文研究优先级k-中心问题的固定参数可解(fixed-parameter tractability,FPT)时间内的近似算法。基于k-中心问题的贪心策略,提出新的中心点选取方法。研究结果表明:该方法通过贪心策略选取一定规模的候选中心点集,利用加倍度量维度的性质去限制该集合的大小,实现了FPT时间内的(1+ε)-近似算法,降低了目前该问题的近似比。

数据中心流量调度的分簇聚类算法仿真

为了避免数据中心出现信道拥塞问题,需要对数据中心中的流量展开调度处理,为此提出面向数据中心流量调度的分簇聚类算法。分析数据中心的拓扑结构,检测网络中存在的流量数据,通过梯度下降方法对多层感知机的参数展开调节,利用调节后的多层感知机对检测到的流量数据展开去噪处理,提升流量数据分簇精度。采用K-means算法分簇聚类处理去噪后的流量数据,通过网络带宽分配,在相关约束条件的基础上分簇调度流量数据,实现数据中心流量的调度。实验结果表明,所提方法的分簇精度较高,流量包的速率基本相同,表明所提方法具有较高的稳定性,调度效果较好。

基于Tukey规则与初始中心点优化的K⁃means聚类改进算法

针对K⁃means聚类算法存在的初始中心点选择及异常点、离群点极易影响聚类结果等待改进问题,提出了一个基于Tukey规则与优化初始中心点选择的K⁃means改进算法。该算法利用Tukey规则构造核心与非核心子集,将聚类过程划分成2个阶段。同时,在核心子集上执行中心点逐个递增优化选择策略,选出初始中心点。在来自UCI的20个数据集上聚类结果表明,本文提出的算法优于K⁃means++聚类算法,有效地提升了聚类性能。

基于预测需求量的物流仓储中心选址研究

为了解决目前物流仓储中心选址模型存在的脱离实际、需求不合理、成本模型不完备等问题。以长三角地区为例,采用二次指数平滑法预测出该地区27个中心城市未来3年的货物需求量,构建长三角地区物流仓储中心选址模型,利用K-means聚类算法和遗传算法进行仿真实验,并与多种算法进行对比分析。仿真实验表明,K-means聚类算法在求解备选仓储中心问题上有很好的效果,可以使仓储中心到需求点的总距离和最小,遗传算法相比于其他算法在求解仓储中心选址问题上求解速度更快、迭代次数更少、最终结果更精确。结果证明,使用K-means聚类算法和遗传算法求解长三角地区物流仓储中心可以大大提高该地区物流效率并降低物流成本。

基于k近邻中心偏移因子的欠采样方法

针对不平衡数据集在实际应用中分类效果较差的问题,文章提出一种基于k近邻中心偏移因子对多数类样本欠采样的数据处理方法。k近邻中心是样本的k个最近邻覆盖区域的中心点,所在位置随着k值的增加而发生偏移,偏移变化的波动程度用中心偏移因子来表示。中心偏移因子的值反映了样本周围的局部密度,数值较小的因子代表样本及其近邻处于密集区域,或近邻在样本的同一侧密集分布,样本可能为冗余样本。为了在不改变原始数据分布的前提下尽可能地删除冗余度较高的多数类样本,首先,移除多数类样本中的噪声点,计算多数类样本的中心偏移因子;然后,将多数类样本按照偏移因子的数值从低到高排序;最后,通过比较样本与k近邻的中心偏移因子来删除部分多数类样本,使数据集趋于平衡。实验使用支持向量机对多种欠采样方法平衡后的14个数据集进行了分类,实验结果表明,所提方法在大多数数据集上表现较优,有效提高了少数类的分类精度。

基于加权二分图的K均值最佳聚类数确定算法

针对传统K均值算法无法精确预设初始聚类中心数目的问题,提出基于加权二分图的K均值最佳聚类数确定算法。设计等比例随机采样的方式,从原始大数据集中产生小数据集集合并从中产生聚类中心点点集,提高应对大规模数据集的能力;用聚类中心点点集形成二分图,针对聚类算法特性改进其赋权函数;设计评价数,改进Kuhn-Munkres算法,将其用于求取二分图的最大权完美匹配,确定最佳聚类数。实验结果表明,相较其它6种对比算法,所提算法有更高的准确性,更好的稳定性,以及更强的处理大规模数据集能力。