一种基于初始点密度最大的改进型ISODATA聚类算法

李润青+谢明鸿+黄冰晶

摘要：针对ISODATA对初始聚类点选取较为敏感，不能处理噪声点的缺陷，提出一种基于结合密度最大的改进型ISODATA的划分聚类方法D-ISODATA。基于高局部密度点距离和局部密度最大原则，优化聚类初始点并去除噪声点。根据考察对象所处空间区域的密度分布情况划分基本簇，结合ISODATA聚类算法良好的自适应性，有效地对数据集进行分类。实验表明，这种基于密度聚类的改进型ISODATA算法能有效去除噪声点，改善初始中心点选择对最后聚类算法的影响，并且具有良好的自适应性，对于数据集处理的准确性优于传统K-means算法和ISODATA算法。

关键词：高局部密度点距离；初始点选择；噪声点；ISODATA；D-ISODATA 算法

DOIDOI：10.11907/rjdk.172074

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2017）012-0094-05

Abstract：Aiming at the defect that ISODATA is sensitive to the initial clustering points and can not deal with the noise points， this paper proposes an improved ISODATA clustering method based on the combination of maximum density D-ISODATA. Based on the principle of “high local density point distance” and local density maximum principle， the initial points and the noise points are optimized. Through the investigation of the basic object to divide the cluster density distribution area， combined with the ISODATA clustering algorithm is a good “adaptive”， classify the data set， experiments show that the improved ISODATA algorithm can effectively remove the noise density clustering based on improved effect on the final selection of the initial center point clustering algorithm， and have good adaptability. The accuracy of data processing is better than the traditional partition based clustering algorithms such as K-means algorithm and IOSDATA algorithm and the clustering algorithm based on density division such as DBSCAN algorithm.

Key Words：high local density point distance； optimal initial point selection； noise point； ISODATA； D-ISODATA algorithm

0 引言

聚類是一种流行的数据挖掘技术，聚类算法被广泛应用于诸多领域，包括模式识别、机器学习、图像处理、信息检索等[1]，在数据挖掘中起到重要作用。

现有聚类算法可以分为划分法[2]、层次法[3]、密度法[4]、网格法[5]和模型法[6-7]。划分法首先创建k个划分，然后利用循环定位技术将对象从一个划分移到另一个更合适的划分，以此改善划分质量。层次法创建一个层次以分解给定的数据集，该方法可分为自上而下（分解）和自下而上（合并）两种操作方式。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。密度法根据元素密度完成对象聚类。它根据对象周围的密度（如DBSCAN）不断增长聚类。网格法首先将对象空间划分为有限个单元以构成网格结构，然后利用网格结构完成聚类。模型法则假设每个聚类的模型并发现适合相应模型的数据。

以上聚类算法具有各自的特点，在不同领域也有着各自的优缺点。基于划分的聚类，如K-means算法[8]，具有算法简单、速度快等优点，因此在实践中使用最为广泛。但此方法只能对简单的数据进行分类，并且存在分类结果受初始点选择影响较大的缺点。基于密度的聚类方法，如DBSCAN[9]，由于不需要输入聚类个数，能发现任意形状簇，但是对于密度变化不明显或密度变化过于复杂的数据，却存在着处理效果不理想的问题，同时该算法还存在处理结果对噪声点比较敏感的缺陷[10]。

相对于K-means算法，基于划分的ISODATA算法[11]更加灵活，能自动调整类别中心和类别个数。其自组织性也能减小一些初始点选择所带来的影响，使得该算法得到了广泛应用。但初始点选择对ISODATA算法的影响却始终存在，当数据中存在较多噪声点时，初始点选择对分类效果的影响会更加明显。

本文针对上述传统ISODATA聚类算法的缺点，提出一种改进算法（D-ISODATA）。该算法能够有效处理噪声点，并且通过高局部密度点距离和局部密度最大原则自动选择初始点（而非经典ISODATA的随机选取初始点方法），可以极大改善最终聚类效果。

1 相关研究

迭代自组织的数据分析算法也称ISODATA聚类算法，此算法与K-means算法有相似之处，即聚类中心由样本均值的迭代决定。但ISODATA算法加入了一些试探性的步骤，即能吸取中间结果所得到的经验，在迭代过程中可以将类一分为二，也可以将两类合并，即“自组织”。ISODATA算法通过设置初始参数而引入人机对话环节，并使用合并和分裂等机制，当两类聚类中心小于某个阈值时，将它们合并为一类。当某类的标准差大于某一阈值或其样本数目超过某一阈值时，将其分裂为两类。在某类样本数目小于某一阈值时，将其取消。这样根据初始类聚中心和设定的类别数目等参数迭代，最终得到一个比较理想的聚类结果。ISODATA算法是一种常用的聚类分析方法，也是一种非监督学习方法。

ISODATA算法基本步骤如下：①选择某些初始值，可选不同的参数指标，也可在迭代过程中人为修改，以将N个模式样本按指标分配到各聚类中心；②计算各类诸样本的距离指标函数；③按给定要求将前一次获得的聚类集进行分裂与合并处理从而获得新的聚类中心；④重新进行迭代运算，计算各项指标判断聚类结果是否符合要求。经过多次迭代后若聚类结果收敛则运算结束。

可以发现，ISODATA聚类算法相比K-means算法在灵活性上提高了很多，其“自组织”性也使得能够更准确地找到各类。但同时，该算法也存在着很大缺陷：ISODATA有很多需要选择的参数，其中初始聚类数目难指定，而数据集中初始中心点选取的不同往往导致最后聚类效果的不同。文献[12]基于密度思想，通过设定Eps 邻域及Eps邻域内至少包含的对象数minpts排除孤立点，并将不重复的核心点作为初始聚类中心用于改进K-means的初始聚类中心，此方法对ISODATA算法同样有改进效果。文献[13]通过对DBSCAN的初始点进行优化以改进算法。该优化算法先确定全局密度最大点，结合该点和数据集自身特征，自适应得到DBSCAN算法所聚类出的当前簇所需参数。优先对高密度簇聚类，即能对变化密度的数据集进行聚类。文献[14]提出黄金分割法度量用ISODATA算法聚类的有效性。该方法可动态计算聚类度量参数，能够反映聚类数据的内在结构。总体而言，以上算法主要通过优化初始点，增加评判标准判断类内、类间参数改进算法，但这些算法依旧存在不足，如不能解决噪声问题等。

2 密度最大中心点ISODATA聚类算法

2.1 设计思想

ISODATA虽然对原有K-means算法有所改进，但该聚类算法在合并、分裂过程中没有考虑到噪声点（异常点），而噪声点对数据集聚类影响较大。由于ISODATA所选的中心点具有随机性，最后的聚类结果受初始中心点的选取影响很大。ISODATA聚类算法有很好的自适应性，本文提出的改进算法是通过高局部密度点距离[15]和局部密度最大原则选取初始中心点得到初始聚类簇，再结合ISODATA的良好自适应性完成进一步聚类。此方法能解决ISODATA受初始点选取影响，每次选取中心点不同所带来的随机性而造成最终结果不同的问题。同时由于引入高局部密度点距离，该算法能够在划分初始聚类簇时去除数据集中的异常点（噪声点）。

2.2 D-ISODATA算法

D-ISODATA（密度最大中心点ISODATA聚类算法）通过引入局部密度和高局部密度点距离这两个概念优化ISODATA存在的问题。

3 实验分析

通过实验对D-ISODATA算法进行评估，分别采用人工数据集、IRIS数据集进行测试。通过与ISODATA算法、K-means算法比较，检测其对初始点选取的优化能力和去噪声能力，提高聚类准确性。对于两个数据集都采用欧几里德距離（Euclidian Distance）。

D-ISODATA算法对于数据集的处理是先计算高局部密度点距离δi及局部密度ρi确定密度最大点，即最优初始聚类中心。其中，由于全局密度最大点的高局部密度点距离δi无穷大，因此给定一个较大值19.9作为其δi，再以该点为中心通过中心点密度曲线的波峰波谷得到数据集的初始聚类簇，实验结果如图1、图2所示。将得到的初始聚类簇通过ISODATA的分裂、合并迭代进一步优化聚类结果。

本文实验环境为Windows 7操作系统，实验平台为Matlab 2014a。

（1）人工数据集检测。分别以均值为0、5、10，方差为1的正态分布的300个随机点作为待处理数据值，并在该数据值中加入加性高斯白噪声如图3所示，每个数据包含X与Y两个坐标值。分别采用K-means算法、ISODATA算法及D-ISODATA算法进行实验对比。其中，K-means算法和ISODATA算法的初始类手工设定为3类。由于K-means算法和ISODATA算法的初始点选取具有随机性，取100次实验求平均值。

D-ISODATA算法由于具有良好的去噪性且对初始聚类中心点有良好判断，最终对数据集的处理效果准确度及准确率明显好于ISODATA聚类算法和K-means聚类算法。实验结果如图4所示。

由实验结果可以看出，由于ISODATA算法的初始中心点选择不当加上噪声点的影响，聚类结果与预期偏差较大。而D-ISODATA聚类结果显示，噪声点明显减少，聚类结果很好。表1给出了3种实验方法在发现簇数量、准确率上的对比，其中K-means算法和ISODATA算法以100次实验结果平均值作为对比结果。

由表1可知，在人工数据集中，3种方法的实验准确率分别为87.22%、89.93%和96.41%，在发现簇的数量及准确率上，D-ISODATA算法实验效果比ISODATA算法更优。

（2）IRIS数据集检测。IRIS数据集是由3种不同种类鸢尾花的各50个样本组成，每个样本共4种属性，分别代表花萼长度、花萼宽度、花瓣长度和花瓣宽度，共有150个数据。该实验中，ISODATA算法仍采用100次实验求平均值，每次选取初始聚类点个数为3。实验结果如图5所示。

IRIS数据集是4维数据，本实验图像采用该数据集的前3维数据进行画图比较，从图像中发现，D-ISODATA相对于ISODATA在实验准确率上优化效果不明显。

由表2可知，在IRIS数据集中，ISODATA算法比D-ISODATA算法的准确率略低，在发现簇的数量上都很准确，但由于随机取中心点的不稳定性，在测试ISODATA算法时有几次实验的结果与真实情况严重不符，导致准确率大为降低。而D-ISODATA算法由于其良好的稳定性在相同数据集下的多次实验结果都相同。

4 结语

为了解决ISODATA聚类算法不能处理噪声点，且在初始点的选择上具有较大随机性，并带来实验结果的不确定性和巨大差异性问题，本文提出了基于局部密度最大中心点选取的改进型ISODATA聚类算法。由于这种改进型算法引用了高局部密度点距离和局部密度原则，在初始点选取和噪声处理过程中有着非常好的实验结果，解决了ISODATA算法由于中心点选取带来的实验结果不稳定性问题。相比于ISODATA算法，改进型ISODATA聚类算法具有实验准确率高、发现簇的数量更加准确等优点。但同时，其在IRIS数据集中改进算法的准确率比ISODATA算法的平均准确率提升不够明显，说明在处理高维数据时的实验效果还有待提高。后续研究中，需重点解决高维数据处理问题，如加入SVM的核函数，将数据投影到高维再进行分类等。

参考文献：

[1] 王光宏，蒋平.数据挖掘综述[J].同济大学学报：自然科学版，2004，32（2）：246-252.

[2] 董琦璠.基于划分聚类算法的研究及其应用[D].哈尔滨：哈尔滨工程大学，2015.

[3] 陈黎飞，姜青山，王声瑞.基于层次划分的最佳聚类数确定方法[J].软件学报，2008，19（1）：62-72.

[4] 张业嘉诚.划分聚类与基于密度聚类算法的改进方法研究[D].大连：大连理工大学，2007.

[5] 赵慧，刘希玉，崔海青.网格聚类算法[J].计算机技术与发展，2010，20（9）：83-85.

[6] 贺玲，吴玲达，蔡益朝.数据挖掘中的聚类算法综述[J].计算机应用研究，2007，24（1）：10-13.

[7] 朱红灿，陈星星.一种消除变量间相关性的模型聚类方法[J].统计与决策，2016（21）：26-28.

[8] MACQUEEN J.Some methods for classification and analysis of multivariateobservations[C].Proc. of Berkeley Symposium on Mathematical Statistics and Probability，1967：281-297.

[9] BI F M，WANG W K，CHEN L.DBSCAN：density-based spatial clustering of applications with noise[J].Journal of Nanjing University，2012，48（4）：491-498.

[10] SARWAR B，KARYPIS G，KONSTAN J，et al.Item-based collaborative filtering recommendation algorithms[C].International Conference on World Wide Web. ACM，2001：285-295.

[11] VELASCO F R D.Thresholding using the ISODATA clustering algorithm[J].IEEE Transactions on Systems Man & Cybernetics，2007，10（11）：771-774.

[12] 張琳，陈燕，汲业，等.一种基于密度的K-means算法研究[J].计算机应用研究，2011（11）：4071-4073.

[13] 戴阳阳，李朝锋，徐华.初始点优化与参数自适应的密度聚类算法[J].计算机工程，2016，42（1）：203-209.

[14] 张丽娜，姜新华，那日苏.基于改进的ISODATA算法的大样本数据聚类方法研究[J].内蒙古农业大学学报：自然科学版，2013，34（1）：133-137.

[15] RODRIGUZE A，LAIO A.Clustering by fast search and find of density peaks[J].Science，2014，344（6191）：1492-1498.

[16] 王晶，夏鲁宁，荆继武.一种基于密度最大值的聚类算法[J].中国科学院大学学报，2009，26（4）：539-548.

（责任编辑：孙 娟）