优化初始聚类中心的K-means聚类算法

针对传统K-means算法对初始中心十分敏感,聚类结果不稳定问题,提出了一种改进K-means聚类算法。该算法首先计算样本间的距离,根据样本距离找出距离最近的两点形成集合,根据点与集合的计算公式找出其他所有离集合最近的点,直到集合内数据数目大于或等于[α]（[α]为样本集数据点数目与聚类的簇类数目的比值）,再把该集合从样本集中删除,重复以上步骤得到K（K为簇类数目）个集合,计算每个集合的均值作为初始中心,并根据K-means算法得到最终的聚类结果。在Wine、Hayes-Roth、Iris、Tae、Heart-stalog、Ionosphere、Haberman数据集中,改进算法比传统K-means、K-means++算法的聚类结果更稳定;在Wine、Iris、Tae数据集中,比最小方差优化初始聚类中心的K-means算法聚类准确率更高,且在7组数据集中改进算法得到的轮廓系数和F1值最大。对于密度差异较大数据集,聚类结果比传统K-means、K-means++算法更稳定,更准确,且比最小方差优化初始聚类中心的K-means算法更高效。     

基于密度和中心指标的Canopy二分K-均值算法优化

针对二分K-均值算法由于随机选取初始中心及人为定义聚类数而造成的聚类结果不稳定问题,提出了基于密度和中心指标的Canopy二分K-均值算法SDC_Bisecting K-Means。首先计算样本中数据密度及其邻域半径;然后选出密度最小的数据并结合Canopy算法的思想进行聚类,将得到的簇的个数及其中心作为二分K-均值算法的输入参数;最后在二分K-均值算法的基础上引入指数函数和中心指标对原始样本进行聚类。利用UCI数据集和自建数据集进行模拟实验对比,结果表明SDC_Bisecting K-Means不仅使得聚类结果更精确,同时算法的运行速度更快、稳定性更好。     

基于距离和权重改进的K-means算法

K-means聚类算法简单高效,应用广泛。针对传统K-means算法初始聚类中心点的选择随机性导致算法易陷入局部最优以及K值需要人工确定的问题,为了得到最合适的初始聚类中心,提出一种基于距离和样本权重改进的K-means算法。该聚类算法采用维度加权的欧氏距离来度量样本点之间的远近,计算出所有样本的密度和权重后,令密度最大的点作为第一个初始聚类中心,并剔除该簇内所有样本,然后依次根据上一个聚类中心和数据集中剩下样本点的权重并通过引入的参数[τi]找出下一个初始聚类中心,不断重复此过程直至数据集为空,最后自动得到[k]个初始聚类中心。在UCI数据集上进行测试,对比经典K-means算法、WK-means算法、ZK-means算法和DCK-means算法,基于距离和权重改进的K-means算法的聚类效果更好。     

结合mean-shift与MST的K-means聚类算法

针对初始点选择不当导致K—means陷入局部最小值问题,提出一种结合自适应mean-shift与最小生成树（MST）的K—means聚类算法。将数据对象投影到主成分分析（PCA）子空间,给出自适应mean．shift算法,并在PCA子空间内将数据向密度大的区域聚集,再利用MST与图连通分量算法,找出数据的类别数和类标签,据此计算原始空间的密度峰值,并将其作为K．means聚类的初始中心点。对K—means的目标函数、聚类精度和运行时间进行比较,结果表明,该算法在较短的运行时间内能给出较优的全局解。     

基于新聚类有效性函数的改进K-means算法

在K-means算法中,聚类数k是影响聚类质量的关键因素之一。目前,已经提出了许多确定最佳k值的聚类有效性方法,但这些方法都不能很好地处理两种数据集:类（簇）密度不同的数据集和类间距比较小的数据集(含有合并簇的数据集)。为此,提出了一种新的聚类有效性函数,该函数定义为数据特征轴总长度的平方与最小类间距的比值,最佳聚类数为这个比值达到最小时对应的k值。同时,为减小K-means算法对噪声和孤立点数据的敏感性,使用了基于加权的改进K-平均的方法计算类中心。实验证明,与其他算法相比,基于新聚类有效性函数的K-wmeans算法不仅降低了噪声和孤立点数据对聚类结果的影响,而且能有效地处理上面提到的两种数据集,明显提高了数据聚类质量。     

A hybrid approach for data clustering based on modified cohort intelligence and K-means

Clustering is an important and popular technique in data mining. It partitions a set of objects in such a manner that objects in the same clusters are more similar to each another than objects in the different cluster according to certain predefined criteria. K-means is simple yet an efficient method used in data clustering. However, K-means has a tendency to converge to local optima and depends on initial value of cluster centers. In the past, many heuristic algorithms have been introduced to overcome this local optima problem. Nevertheless, these algorithms too suffer several short-comings. In this paper, we present an efficient hybrid evolutionary data clustering algorithm referred to as K-MCI, whereby, we combine K-means with modified cohort intelligence. Our proposed algorithm is tested on several standard data sets from UCI Machine Learning Repository and its performance is compared with other well-known algorithms such as K-means, K-means++, cohort intelligence (CI), modified cohort intelligence (MCI), genetic algorithm (GA), simulated annealing (SA), tabu search (TS), ant colony optimization (ACO), honey bee mating optimization (HBMO) and particle swarm optimization (PSO). The simulation results are very promising in the terms of quality of solution and convergence speed of algorithm.     

量子行为粒子群算法在基因聚类中的应用

在PSO算法的基础上提出的基于量子行为的QPSO算法,并将其应用到基因表达数据集上。QPSO基因聚类算法是将N条基因根据使TWCV（Total Within-Cluster Variation）函数值达到最小分到由用户指定的K个聚类中。根据K-means算法的优点,利用K-means聚类的结果重新初始化粒子群,结合QPSO和PSO的聚类算法提出了KQPSO和KPSO算法。通过在4个实验数据集上利用K-means、PSO、QPSO、KPSO、KQPSO 5个聚类算法得出的结果比较显示QPSO算法在基因表达数据分析上具有良好的性能。     

基于改进的K均值聚类彩色图像分割方法

提出了一种改进的K均值聚类图像分割方法。针对彩色图像的像素特征,利用Ohta等人的研究成果,选取能有效表示彩色像素特征的彩色特征集中的第一个分量作为图像像素的一维特征向量,用来替代经典K均值聚类图像分割中的灰度．大大降低了运算量。基于粗糙集理论的算法,求出初始聚类个数与均值。选用对特征空间结构没有特殊要求的特征距离代替欧氏距离,应用改进的K均值聚类算法对样本数据进行聚类,从而实现对彩色图像的快速自动分割。实验表明,该图像分割算法可有效提高图像分类的精度和准确度,并且运算代价小．收敛速度快。     

基于K-means算法的轨迹数据热点挖掘算法

针对渔船轨迹数据具有时间序列性、数量大的特点,提出一种轨迹热点挖掘算法。该算法克服了K-means算法在渔船轨迹数据上无法捕捉热点分布的缺点。其主要的思想是：首先使用时间维度来处理数据,以置信度和KL散度作为衡量所选取数据的可靠性、正确性依据,从大量的轨迹数据中选取信息含量较高的数据,然后使用K-means聚类算法进行数据的聚类。本文所提出的算法只需要设定显著水平参数a和时间间隔T,算法本身就可通过时间维度处理数据的方法自主完成数据的选择以及置信度、KL散度的计算,并引入聚类有效性度量的方法,使K-means通过自我寻找K值来实现热点挖掘的整个过程。在渔船轨迹数据上进行本文算法与K-means算法的对比实验和数据热力图的参照实验,结果显示本文所提的算法在寻找轨迹数据热点上有优越性和正确性。     

基于MapReduce框架下K-means的改进算法

针对海量数据背景下K-means聚类结果不稳定和收敛速度较慢的问题,提出了基于MapReduce框架下的K-means改进算法。首先,为了能获得K-means聚类的初始簇数,利用凝聚层次聚类法对数据集进行聚类,并用轮廓系数对聚类结果进行初步评价,将获得数据集的簇数作为K-means算法的初始簇中心进行聚类;其次,为了能适应于海量数据的聚类挖掘,将改进的K-means算法部署在MapReduce框架上进行运算。实验结果表明,在单机性能上,该方法具有较高的准确率和召回率,同时也具有较强的聚类稳定性;在集群性能上,也具有较好的加速比和运行速度。     

一种改进的K—means算法在入侵检测中的应用

传统的聚类算法存在很多缺点,因此需要做进一步的研究。通过对传统的K-means算法和加权熵措施的K—means算法的研究,提出了一种改进的加权熵措施的K—means算法,且该算法采用了一种新的计算对象间距离的方法,不仅能使在同一个簇中任意对象之间的距离尽可能的小,更能使得不同簇中的任意对象之间的距离尽可能的大。通过在KDD Cup99数据集上实验仿真,表明该算法具有较强的实用性和自适应功能。     

基于加权距离计算的自适应粗糙K均值算法*

针对粗糙K均值算法的执行效率较低和对数据对象的处理不准确,本文提出了基于加权距离计算的自适应粗糙K均值算法。该算法首先在粗糙集理论应用的基础上修正数据集合的隶属度函数,其次结合属性约简方法,根据数据属性对聚类效果的影响因子设置权值,在欧氏距离中引入权值系数来初始化簇的中心点,最后通过K值递增的改进算法对数据集进行正态检验来验证每个簇的数据是否符合高斯分布模型,从而能够自适应地确定K值。实验结果表明,改进后的算法相比原算法在能保证一定执行效率的同时,能获得较高的聚类精确度,且对高维数据集也有较强的适应性,从而表明该算法是有效可行的。     

PCA-AKM算法及其在入侵检测中的应用

初始聚类中心是指在聚类的过程中首次被选为中心的点或对象。针对传统的K-means算法由于随机选择初始聚类中心而造成的聚类结果不稳定的问题,提出PCA-AKM算法。该算法利用主成分分析方法提取数据集中的主要成分,实现数据降维,使用自定义指标密权值选择初始聚类中心,避免聚类中心局部最优问题。将该算法与K-means算法在UCI数据集上进行聚类对比,其聚类稳定性高于传统K-means算法。 在KDD CUP99数据集上,对所提算法进行入侵检测仿真,实验结果证明该算法检测率高,误检率低,能够有效提高入侵检测的准确率。     

基于差分隐私保护的Stacking集成聚类算法研究

针对差分隐私保护下单一聚类算法准确性和安全性不足的问题,提出了一种基于差分隐私保护的Stacking集成聚类算法。使用Stacking集成多种异质聚类算法,将K-means聚类、Birch层次聚类、谱聚类和混合高斯聚类作为初级聚类算法,结合轮廓系数对初级聚类算法产生的聚类结果加权并入原始数据,将K-means算法作为次级聚类算法对扩展后的数据集进行聚类分析。其中,针对原始数据和初级聚类算法的聚类结果分别提出自适应的ε函数确定隐私预算,为不同敏感度的数据分配不同程度的Laplace噪声。理论分析和实验结果均表明,与单一聚类算法相比,该算法满足ε-差分隐私保护的同时有效提高了聚类准确性,实现了隐私保护与数据可用性的高度平衡。     

基于犹豫模糊Canopy-K均值聚类算法的研究与应用

针对传统K均值聚类算法对初始值敏感、易陷入局部极值点,导致数据分类结果不理想的问题,本文提出一种基于犹豫模糊Canopy-K均值聚类算法。首先利用Canopy算法对原始数据进行初步分类,形成多个数据重合的Canopy中心集合,即得到K均值算法的初始聚类中心。然后再利用K均值聚类算法进行聚类,得到最终的聚类结果。最后结合疫情后复工复产企业评价信息数据进行实例分析,从6个方面对复工复产的5个企业发展情况进行评估。将新提出的算法和基于层次分析的K均值聚类算法进行对比分析。结果表明,新提出的方法较大地减少了迭代次数,聚类结果更加合理、稳定和有效。     

结合自然和共享最近邻的密度峰值聚类算法

基于快速搜索和寻找密度峰值聚类算法(DPC)具有无需迭代且需要较少参数的优点,但其仍然存在一些缺点:需要人为选取截断距离参数;在流形数据集上的处理效果不佳。针对这些问题,提出一种密度峰值聚类改进算法。该算法结合了自然和共享最近邻算法,重新定义了截断距离和局部密度的计算方法,并且算法融合了候选聚类中心计算概念,通过算法选出不同的候选聚类中心,然后以这些候选中心为新的数据集,再次开始密度峰值聚类,最后将剩余的点分配到所对应的候选中心点所在类簇中。改进的算法在合成数据集和UCI数据集上进行验证,并与K-means、DBSCAN和DPC算法进行比较。实验结果表明,提出的算法在性能方面有明显提升。     

基于样本空间分布密度的初始聚类中心优化K-均值算法*

针对传统K-均值聚类算法对初始聚类中心敏感、现有初始聚类中心优化算法缺乏客观性,提出一种基于样本空间分布密度的初始聚类中心优化K-均值算法。该算法利用数据集样本的空间分布信息定义数据对象的密度,并根据整个数据集的空间信息定义了数据对象的邻域;在此基础上选择位于数据集样本密集区且相距较远的数据对象作为初始聚类中心,实现K-均值聚类。UCI机器学习数据库数据集以及随机生成的带有噪声点的人工模拟数据集的实验测试证明,本算法不仅具有很好的聚类效果,而且运行时间短,对噪声数据有很强的抗干扰性能。基于样本空间分布密度的初始聚类中心优化K-均值算法优于传统K-均值聚类算法和已有的相关K-均值初始中心优化算法。     

基于密度的改进K均值算法及实现

传统的K均值算法的初始聚类中心从数据集中随机产生,聚类结果很不稳定。提出一种基于密度算法优化初始聚类中心的改进K-means算法,该算法选择相互距离最远的k个处于高密度区域的点作为初始聚类中心。实验证明,改进的K-means算法能够消除对初始聚类中心的依赖,聚类结果有了较大的改进。     

PHD: an efficient data clustering scheme using partition space technique for knowledge discovery in large databases

Rapid technological advances imply that the amount of data stored in databases is rising very fast. However, data mining can discover helpful implicit information in large databases. How to detect the implicit and useful information with lower time cost, high correctness, high noise filtering rate and fit for large databases is of priority concern in data mining, specifying why considerable clustering schemes have been proposed in recent decades. This investigation presents a new data clustering approach called PHD, which is an enhanced version of KIDBSCAN. PHD is a hybrid density-based algorithm, which partitions the data set by K-means, and then clusters the resulting partitions with IDBSCAN. Finally, the closest pairs of clusters are merged until the natural number of clusters of data set is reached. Experimental results reveal that the proposed algorithm can perform the entire clustering, and efficiently reduce the run-time cost. They also indicate that the proposed new clustering algorithm conducts better than several existing well-known schemes such as the K-means, DBSCAN, IDBSCAN and KIDBSCAN algorithms. Consequently, the proposed PHD algorithm is efficient and effective for data clustering in large databases.     

快速混合Web文档聚类

提出了一种使用后缀树聚类算法优化K-means文档聚类初始值的快速混合聚类方法STK-means。该方法首先构建文档集的后缀树模型,使用后缀树聚类算法识别初始聚类、提取K-means聚类算法初始值中心值。然后,把后缀树模型的节点映射到M维向量空间模型中的特征项,利用TF-IDF方案计算基于短语的文档向量特征值。最后,使用K-means算法产生聚类结果。实验结果表明该方法优于传统K-means聚类算法和后缀树聚类算法,并具备了这些算法聚类速度快的优点。