最小局部方差优化初始聚类中心的K-means算法

来源:用户上传      作者:

　　摘要：针对传统K-means算法随机选取初始聚类中心导致聚类结果随机性大、优劣不定的缺点，通过定义局部方差，利用方差反映数据密集程度的特性，提出一种基于最小局部方差优化初始聚类中心的K-means算法。该算法选取数据集中局部方差最小的点作为一个初始聚类中心，并利用数据信息更新数据集，直到选到k个初始聚类中心，实现初始聚类中心优化。基于UCI数据集与人工数据集进行实验，与传统K-means算法及最小方差优化初始聚类中心的K-means算法进行性能比较。实验结果表明，基于最小局部方差优化初始聚类中心的K-means算法具有良好的聚类效果和很好的鲁棒性，且聚类时间较短，验证了算法有效性和优越性。
　　关键词：聚类;K-means算法;初始化聚类中心;局部方差;密集程度
　　DOI：10.11907/rjdk.192061 开放科学（资源服务）标识码（OSID）：
　　中图分类号：TP312文献标识码：A 文章编号：1672-7800（2020）006-0196-05
　　0 引言
　　针对K-means算法随机选取初始聚类中心容易得到局部最优解的缺点，众多学者提出优化初始聚类中心的方法改进传统K-means算法，这些方法主要可分为3类：①基于样本空间密度的初始聚类中心优化，有时有较好的聚类结果，但该法依赖于参数选择，可能会因选取到噪声点或参数选取不当造成聚类效果差;②全局K均值聚类算法，虽有良好的聚类结果，但因算法复杂，聚类时间过长;③基于最小方差选择初始聚类中心，该方法不依赖参数选取，且多数情况聚类效果良好，在聚类效果和时间上优于前面两种方法，但在某些情况下聚類效果较差，因此在聚类效果和时耗上还有提升空间。
　　仅基于方差选择初始聚类中心的算法不依赖参数类型且复杂度较低，但该类方法以全局方差作为衡量数据密集度的指标值。全局方差计算采用来自于不同类的全部数据计算，因此，不同数据点全局方差大小比较意义并不明显。本文定义局部方差，选择某数据点附近的局部数据计算方差，基于局部方差最小优化初始聚类中心，提出最小局部方差优化初始聚类中心的K-means算法，以期缩短时耗、提升聚类效果。
　　1 算法改进
　　1.1 算法原理
　　选取初始聚类中心时需保证两点：①K个初始聚类中心距离尽量远;②每个初始中心附近数据点尽量密集。基于这些前提，文献利用方差反映数据密集程度的特性，提出基于最小方差初始化聚类中心的K-means算法。全局方差定义为用所有数据信息反映某一数据点附近数据的密集程度，但由于这些数据属于不同的类，因此该定义有不合理之处;文献通过去掉每个选取到的聚类中心周围平均距离内的点，实现数据集更新，即认为数据集中每个点的地位等同，但该观点并不客观，当中心选取到离群点时，以该方式更新数据集会产生很大问题。
　　为更确切地反映数据点附近的数据密集程度，本文重新定义数据点局部方差，并改变数据集更新方式，利用每个数据点附近的局部数据信息衡量该点数据密集度，提出最小局部方差优化初始聚类中心的K-means算法。首先，计算所有数据点局部方差，选取局部方差最小的点作为第一个初始聚类中心，并计算距该点最远的点与该点之间的距离dismax，半径取dismax/K，删除以该点为圆心的圆域内的点，再计算每个数据点局部方差，选择第二个初始聚类中心，第二次更新数据集时，选取的半径为dismax/（K-1），循序往后，直到选择到K个初始聚类中心。
　　1.2 基本概念
　　假设待聚类的含n个数据点的s维数据集W={x1，x2，…，xn}，其中xi=（xi1，xi2，…，xis）T，将其划分为K个类簇W1，W2，…，WK，K个类簇中心分别记为C1，C2，…，Ck，进行以下定义。
　　定义1 样本数据xi，xj之间的欧氏距离为：
　　1.3 算法步骤
　　1.3.1 初始聚类中心选择
　　（1）选取首个初始聚类中心时，k=l，根据定义1～4计算数据集中每一个样本局部方差，在数据集w中选择局部方差最小样本x1将其作为第一个类簇初始聚类中心C1。令：
　　否则，得到K个初始聚类中心C1，C2，…，Ck，转至初始划分构造流程。
　　（3）转步骤（2）。
　　1.3.2 初始划分构造
　　（1）遍历数据，按照定义1定义的距离，将每个数据划分到最近中心点所在的类中。
　　（2）计算每个类簇的坐标均值并作为新的中心点。
　　（3）根据定义4，计算误差平方和E。
　　1.3.3 数据点再分配与聚类中心更新
　　（1）遍历数据，按照定义1，将每个数据划分到最近中心点所在的类中。
　　（2）计算每个类簇的坐标均值，作为新的中心点。
　　（3）根据定义4，计算误差平方和E'。如果|E'-E|<10-10，即聚类中心不再变化，则结束算法，输出聚类结果;否则，令E=E’，并转至初始聚类中的选择流程。
　　综上所述，相较于传统K-means算法，本文算法改变了选取初始聚类中心的方式，后续聚类过程相同。
　　2 聚类算法性能指标
　　（1）聚类误差平方和。它是所有数据点到所属类中心的距离平方和，通常作为迭代停止的准则。一般来说，聚类误差平方和越小，聚类效果越好，聚类准确率越高。 　　（2）聚类时间。聚类算法运行时间越短，算法越好。
　　（3）聚类准确率。计算聚类准确率需知道数据点真实类型，聚类准确率越高，聚类效果越好。
　　（4）兰德系数。兰德系数定义式为：
　　其中n是数据集的数据点个数，a表示在真实类中同类且在聚类结果中同类的数据对数，b表示在真实类中异类、且在聚类结果中异类的数据对数。兰德系数取值范围为[0，1]，越接近于l，聚类效果越好。
　　（5）调整兰德系数。为在随机产生聚类结果时使指标接近零，提出调整兰德系数（Adjusted Rand Index）。设ui是聚类得到的类型，vj是真实类型，则对n个数据点的K类待聚类数据集如表l所示。
　　其中nij表示属于ui且属于vj的数据点个数，则调整兰德系数定义式为：
　　RI值通常较大，即便聚类效果较差，RI值也不会很小，ARI是RI的调整值，比RI更直观，取值范围为[-1，1]，ARI越接近于1，聚类效果越好;反之ARI越小，聚类效果越差。
　　3 数据仿真实验
　　为检验算法有效性，本文利用Matlab编程实现算法，与其它算法进行比较。目前3类改进方法只有第3类基于最小方差选择初始聚类中心的算法不依赖参数选取且计算复杂度不高、聚类效果良好。该类算法特点基本一致，因此本文仅与传统K-mean算法及文献算法比较聚类结果。其中，文献的算法与本文算法消除了K-means算法随机性，每次聚类结果固定;传统K-means聚类过程是随机的，同一数据集确定的分类数K的每次聚类结果不尽相同。
　　若以聚类误差平方和大小为衡量聚类优劣标准，对同一组数据集确定的分类数K多次执行傳统K-means算法，基本上均可得到一组最好的聚类结果和一组最差的聚类结果，大多数改进方法得到的聚类结果介于这两组聚类结果之间。因此利用这两组结果比较本文算法和文献算法的聚类效果。本文对每个数据集执行100次传统K-means算法，得到一组最好的结果和一组最差的结果，与执行100次传统K-means算法结果的平均值进行对比。
　　3.1 UCI数据集实验及结果比较
　　本文选取10组不同的UCI数据集进行仿真实验，相关数据集信息如表2所示。
　　分别用文献的算法、本文算法与传统K-means算法计算得到聚类误差平方和，如表3所示，聚类时间如表4所示。
　　由表3、表4可以看出在10个UCI数据集中，本文算法有9组聚类误差平方和小于K-means算法平均值，接近于传统K-means算法的最好情形，其中l组Soybean-small优于传统算法最优情形，只有l组Wine数据集聚类结果较差;而文献的算法有3组数据集Haberman、New thyroid和Balance-scale聚类结果较差，其余均接近于传统算法最好情形;传统K-means算法聚类时间最短，文献的算法聚类时间最长，本文算法聚类时间介于两者之间，与文献的算法聚类时间基本相差一个数量级。
　　计算聚类准确率如图1所示。
　　计算RI与ARI，结果如图2和图3所示。
　　首先通过聚类准确率比较，可以看到本文算法聚类准确率大多与传统算法最好情形一致，其中Soybean-small聚类准确率甚至略高于传统算法最好情形，New-thyroid和Balance-sacle聚类准确率介于传统算法最好、最差之间，与较好情形相差不大，只有1组Wine数据集聚类准确率较低;文献算法聚类准确率较低的数据集较多，包括New-thyroid、Balance-scale等。数据集Haberman聚类误差平方和较小时聚类准确率反而较低，这可能是因为该数据集分类不适用本文采用的相似性准则，因此该组数据不作参考。
　　其次是RI值和ARI值的比较，这两个值相对大小基本一致，综合来看本文算法对数据集Wine、New thyroid聚类的RI和ARI值较小;文献算法对数据集New-thy.roid、Balance-scale的RI和ARI值较小，其余数据集两个算法聚类得到的RI和ARI值较大，接近于传统算法最好情形。
　　3.2 人工数据集实验及结果比较
　　分别用文献的算法、本文算法、传统K-means算法对各组数据进行聚类，其聚类误差平方和与聚类时间如表6、表7所示。
　　由表6比较3种算法的误差平方和，本文算法只有两组较差，即噪声比率10%和噪声比率25%的数据集，其余组误差平方和小于100次传统算法平均值，且基本与传统算法最好情形相同;而文献算法对噪声比率5%、20%、25%的数据集聚类结果较差。两种算法均对噪声有很强的免疫性，高噪声比率不影响聚类效果。
　　聚类时间与UCI数据集结果一致，本文算法聚类时间介于文献算法与传统K-means算法之间，且聚类时间小于文献算法的1/10。进一步计算3种算法聚类准确率、兰德系数RI、调整兰德系数ARI，如图4-图6所示。
　　聚类准确率、RI值、ARI值相对大小基本一致，11组数据中，本文算法聚类结果多数较好，有9组数据聚类准确率达到90%以上，有两组较差，分别是10%噪声组和25%噪声组，其聚类准确率只有50%左右;文献算法聚类结果有3组较差，分别是5%噪声组、20%噪声组、25%噪声组，其余组数据聚类结果良好。
　　同时实验发现，聚类准确率、RI值与ARI值均随噪声比率的增大而减小，但基本保持很高的水平，说明本文算法对数据噪声有很强的免疫性。
　　综上所述，本文算法较文献算法的聚类效果有一定提高，大部分数据集的聚类结果接近传统K-means算法的最好情形，绝大部分数据集聚类效果好于传统K-means算法平均效果，且对噪声数据有很强的免疫性。同时，在聚类时间方面，本文算法虽不及传统K-means算法，但与文献算法相比有大幅改善。
　　4 结语
　　针对传统K-means算法随机性引起聚类效果不稳定的缺陷，本文提出了一种基于最小局部方差初始化聚类中心的K-means改进算法。UCI数据集和人工数据集实验表明，本文算法较文献算法更快、更有效，与传统K-means算法相比，不仅提高了算法稳定性和平均聚类准确率，而且对噪声数据有很强的免疫性、鲁棒性及较快的聚类速度，是一种高效、稳定、准确的K-means改进算法。但同时本文算法对个别数据集聚类效果不理想，下一步将考虑结合样本空间密度进一步扩大算法适用范围。
转载注明来源:https://www.xzbu.com/8/view-15278000.htm