发布时间 : 星期一 文章基于划分的聚类算法更新完毕开始阅读470d1ce32e60ddccda38376baf1ffc4fff47e24c
.
2.5.1关于聚类中心初始化的改进
1）Forgy 最早提出任选k个数据对象，将其作为初始聚类的中心（也有人把随机的选择初始聚类中心的方法称之为FA（ForgyApproach））；2）根据最大距离和最小距离的聚类方法来寻找聚类的中心，以此来确定初始的聚类中心， 如BKMishra 等人于2012 年提出的Far Efficient K-Means 聚类算法；3）直观的用将预理数据集内的混合样本分成k类的方法，计算出各个类的均值，将其作为初始的聚类中心；4）最具有代表性的基于数据采样的方法就是Bradley 等人提出的RA 算法；5）通过“密度法”选择数据样本，将该样本作为初始的聚类中心.2008 年的时候，Park 等人对密度提出了一种全新的定义[9]，计算的数据集中了所有数据对象的密度，且选密度最小的k个数据对象，将它们作为初始的聚类中心；6）用全局的思想来初始化聚类中心。Likas 等学者发明了全局K均值聚类的算法，该算法是根据递增的思想提出的，把k 个簇的聚类问题转变成一系列的子聚类的问题，先从一个簇的聚类问题开始，每增加一个簇，就用迭代的方法求出k 个簇的聚类问题.后来，许多学者对该算法进行研究，并在它的基础上做了一些改进；7）多次对初始值进行选择和聚类，将最优的聚类结果找出。
2.5.2 关于聚类数目k值的确定
G.W.Milligan[10]在1985 年时就最先提出了通过测试的方法来得到最佳的聚类数目k 值的思想.其思想就是:对一定范围内的所有的聚类数目进行测试， 观察它们的收敛速度，得出最优的k 值。紧接着，Xu 使用一种被称之为次胜者受罚的竞争的学习规则来自动的决定类的适当数目。其思想就是:对每个输入， 竞争获胜的单元的权值将被修正以适应输入值，次胜的单元将采用惩罚的方式使其远离输入值。后期，S.Ray等人研究出了一种新的确定最优k 值的方法， 它是基于Milligan 而提出的.其思想为:主要考虑类内和类间的距离，认定类内足够紧凑且类间足够分离时，此时的k 值是最优的.他们还引入了v（validity）值，v 值表示类内的距离与类间的距离的比值，在迭代时计算出k 值最小的时候，其对应的k 值，此k 值就是最优的k 值。根据方差分析的理论，孙才志等人提出了应用混合F 统计量来确定最佳的分类数， 不仅如此，他还应用模糊划分嫡来验证最佳的分类数正确与否。
2.6其他对于K-均值聚类算法的改进
针对K-均值聚类算法极易陷入局部最优解的问题，刘伟民等研究人员将K-均值算法和模拟退火算法进行结合，得出一种新的算法，以模拟退火算法的全局寻找最优解的能力来解决此问题。为防止算法陷入到局部极小值，加快收敛的速度， 刘韬将一种免疫的计算方法与K-均值聚类算法结合起来， 为每一个抗体的亲和度及浓度进行了重新定义，对繁殖率的计算及复制和变异的方法进行了重新的设计。面对K-均值聚类算法对其它形状的类簇不敏感或不识别的问题，于是，易云飞又一次对K-均值聚类算法进行了改进，它用复合形粒子群的算法对聚类的初始中心点进行选取，再通过执行K-均值聚类算法，最终得到聚类的结果。郑超等人对粗糙集进行了改进，将其与K-均值聚类算法结合起来，提出了一种全新的算法.该算法对每个样本点所在的区域的密度值进行了考虑，在求均值点过程中加入了权重的计算，规避了噪音点数据对聚类结果产生的影响。
3 基于划分的聚类分析技术具体应用
多数学者对基于划分的聚类算法的研究大都在对算法的改进方面，而将算法应用于具体领域的很少。现在该算法的应用方向集中在图像的分割与识别、文本的聚类、基于聚类的入侵检测、空间
Word 资料
.
的约束聚类等方面.Cui Xiao-hui[11]将PSO、K-means 和混合PSO 算法应用于四种不同的文本文件，并对其数据集进行聚类，聚类后，经比较分析，混合PSO算法得到的聚簇结果非常紧致，而且用时非常短。文献中，学者们把PSO 与K-means方法结合起来，新发明了一种PSO-KM 的聚类算法，并将该算法应用于无监督的异常的入侵检测当中。其优点是与输入样本和初始的权值的选择无直接的联系，全局搜索能力比K-means 强。将该算法在KDD Cup 1999 数据集上做实验，结果显示:误报率2.8%时，检测率则为86%；此方法对Probe、Dos、U2R 攻击类型的检测最为有效，正确度可达到78%（U2R）到94%（Dos）。X 光图像中的鱼骨检测技术就是用基于质心划分的PSO 聚类做的。面对X光图像的灰度值分布的问题，是用高斯分布的工具与形态学的方法相结合，结合后将其应用于图像的预处理，以此来消减图像数据的规模，从而得到一个有效的区域。PSO 聚类方法的作用则是将有效的区域分割成为不同的簇。与传统的图像分割技术Mean Shift比较，改良后的方法更为有效。
3．结语
本文在查阅大量文献、资料、书籍的基础上，对基于划分的聚类算法进行了系统的学习和总结，主要对聚类的定义及聚类算法的种类进行了介绍， 并对K 均值聚类算法和K 中心点聚类算法的基本原理进行了详细阐述，还对它们的性能进行了分析，梳理了基于划分的聚类算法的研究现状，最后，对其应用做了简要介绍.经过归纳与总结，基于划分的聚类算法主要有以下几方面研究方向:1）如何解决基于划分的聚类算法所不能解决的凸型聚类以外的子样集合问题；2）怎样选择值，使基于划分的聚类算法得以优化，性能更佳；3）如何选取初始的中心点，更大程度的增强基于划分的聚类算法的聚类效果；4）怎样对算法做出改进，使其能从各种聚类的结果中，筛选出或确定出最佳的聚类的分布。
参考文献：
[1] QIAN Wei-ning , ZHOU Ao-ying. Analyzing Popular Clustering Algorithms from DifferentViewpoints[J].软件学报，
Vol.13,No.8:1382-1394.
[2]
孙吉贵，刘杰，赵连宇.聚类算法研究[J]. Journal of Software, Vol.19, No.1, January 2008, pp.48?61.
[3] BARRETT D J, CLARKE L A, TARR P L, et a l. A f ramew ork for event-based softw are in tegration[ J] . ACM
Transactions on SoftwareEng ineering andMethodo logy, 1996, 5(4):378 -421.
[4] [5]
丁丽，孙高峰.基于划分的k-means聚类算法[J].宜春学院学报，2013年6月，第35卷第6期：28-30.
李洪升.K-Medoids算法在人脸识别系统中的应用[J].图形图像，2009,04:59-62.
Word 资料
.
[6][7]
陈志强，刘钊，张建辉.聚类分析中PAM算法的分析与实现[J].计算机与现代化，2003年第9期：1-3. 梁吉业，白亮，曹付元.基于新的距离度量的K-Modes聚类算法[J].计算机研究与发展，2010:1749-1755.
余文利，余建军，方建文.混合属性数据k-prototypes聚类算法[J].计算机系统应用，2015年第24卷第6
[8]
期:168-172.
[9] Park H S，Jun C H. A simple and fast algorithm for K -medoids clustering [J]. Expert Systems with Applications，2009，
36（2）:3336-3341.
[10] Milligan G W，Cooper M C. Methodology Review: ClusteringMethods [J]. Applied Psychological Measurement，
1987，11（4）:329-354.
[11] CUI Xiao-hui，POTOK T E. Document clustering analysisbased on hybrid PSO +K -means algorithm [J]. Journal
ofComputer Sciences:Special Issue，2006（4）:27-33.
Word 资料