具有全局优化能力的K均值聚类算法.pdf

《具有全局优化能力的K均值聚类算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第39卷第7期西南师范大学学报(自然科学版)2014年7月Vo1．39No．7JournalofSouthwestChinaNormalUniversity(NaturalScienceEdition)Ju1．2014具有全局优化能力的K均值聚类算法①李彬乐山师范学院智能信息处理及应用实验室，四JIl乐山614004摘要：传统的K均值聚类算法是确定性的迭代算法，具有探索能力弱、容易陷入局部最优的缺点．在聚类中心的更新过程中加入系数因子线性递减的随机项，使改进的迭代算法在前期具有强的探索能力，而在后期保持良好的

2、局部搜索能力，同时保持了传统K均值聚类算法结构简单的特点．实例说明，增加了随机项的K均值聚类算法具有良好的全局优化能力．关键词：K均值聚类；确定性的；随机项；全局最优中图分类号：TP301文献标志码：A文章编号：1000—5471(2014)7—0036—05对事物进行分类是人们在日常生活、工业生产和科学研究中经常遇到的问题．随着研究的不断深入，仅仅依靠经验进行分类已经很难达到要求．将数理统计中的多元分析方法应用到分类问题中，形成了聚类分析这样一个统计研究领域．聚类分析不仅是数理统计、多元分析的重要内容，它在

3、计算机领域的数据挖掘、图像识别等方面都有重要应用．曾接贤等将聚类算法用于图像检索中，黄月等l_2]在传感器网络的多目标定位中用到了聚类分析方法．聚类分析方法的研究内容十分丰富，主要有系统聚类法和动态聚类法，如粒子群优化算法[3]、蚁群聚类算法]、K均值聚类法等等．K均值聚类法是一种重要的动态聚类算法，因其算法结构简单、迭代步骤少等优点，使得它成为人们在做聚类分析时首先考虑的算法之一．但是K均值聚类算法的探索性能较差，在搜索过程中很容易得到局部最优解，算法解的质量很大程度上受初始解的影响，因此很多学者对K均值聚

4、类算法的改进做了大量研究．胡伟结合空间中的层次结构，提出了改进的层次K均值聚类算法．将基于生物群体行为机理的群智能算法应用到K均值聚类算法中，是K均值聚类算法的一个改进方向．如刘靖明等将粒子群算法引入K均值聚类算法中，提高了聚类算法的全局优化能力；陶新民等]进一步将改进的粒子群算法与K均值聚类算法相结合，给出了一种混合聚类算法．根据具体问题提出算法的改进措施也是K均值聚类的一个改进方向，如：王红睿等根据连续隐马尔可夫模型进行语音识别时初值提取中训练矢量分类不均匀的问题，提出了均衡化的改进K均值聚类算法；Ale

5、xandraPi—ryatinskaE等将K均值算法应用于睡眠模式的研究中；余心杰noj研究了结合K均值的遗传算法聚类分析．虽然以上改进措施在一定程度上提高了K均值聚类算法的全局优化能力，但同时也增加了算法结构的复杂性，为得到全局最优解，往往要付出较大的时间成本．一个好的优化算法应平衡其开发能力和探索能力．群智能算法是一种很好的优化算法，它在迭代过程中通过保留一部分当前的劣解，在保证开发能力的同时，增强了算法的探索能力，使算法能够跳出局部最优解，具有良好的全局寻优能力．基于上述想法，本文在传统的确定性的K均值

6、聚类算法中，在聚类中心的迭代中增加了一个随机项，使算法能跳出局部最优位置，减小对初值的依赖．为了使更新的聚类中心不至于偏离原数据集太远，增加的随机项与原聚类中心和整个数据集的几何中心的距离有关．同时，随机项的系数线性地减小，使算法在初期的探索能力强，在后期的开发能力强．改进算法同时吸收了粒子群算法等群智能算法中使用的最优保留策略的优点，如果当前的聚类中心差于前一步的聚类中心，就不对聚类中心进行替换，以保证迭代过程①收稿日期：2O14—01—11基金项目：四川省教育厅科研项目(12ZB238)；乐山市科技计划项

7、目(13GZD051)．作者简介：李彬(1979一)，女，四川眉山人，讲师，硕士，主要从事数据挖掘、网络安全方面的研究第7期李彬：具有全局优化能力的K均值聚类算法37指向更优的方向．另外改进措施还保持了传统K均值聚类算法结构简单的特点，有利于算法的推广应用．1传统的K均值聚类算法设X=：=(，z，⋯，,27}是D维空间R。中含有个数据的数据集，其中．78ER。．假设根据问题，需要把数据集X分成k个类别C，C。，⋯，，其中要求X—CUc。U⋯U，而且C，C一，C两两之间互不相交，每个类别ci(J一1，2，⋯，走

8、)不是空集．令类别C，的几何中心为1⋯J一而厶tlIJI∈Cj其中：iC，f表示类别C，中样本的个数．设数据集x中的每个样本与其所在类别的中心，的距离为(z，m，)，通常D维空间R。中两个元素之间的距离可以取为欧氏距离d(x，174．j)：定义总类间离散度为F(1，2，⋯，)一鬲>—>d。(z，)(3)xiECjF(m，m，⋯，m)的值度量了分别用k个聚类中心去代表k个类别C，C“，所付出的代价，F