改进的K-means聚类算法及应用.doc
改进的K-means聚类算法及应用摘 要：传统的k-means算法需要事先确定初始聚类中心，聚类精确程度不高。针对以上问题，本文结合熵值法和动态规划算法来对传统的k-means算法进行改进，提出了基于熵值法及动态规划的改进k-means算法。熵值法用来修订算法的距离计算公式，以提高算法的聚类精确程度, 动态规划算法用来确定算法的初始聚类中心。将改进算法应用于矿井监测传感器聚类中，结果显示较传统的k-means算法，改进算法效率有了明显提高，聚类精确程度有较大增强。关键词：k-means；动态规划；熵值法；聚类精确度；矿井监测传感器【abstract】the traditional k-means has sensitivity to the initial clustering centers, and its clustering accuracy is low. to against these short comings, an improved k-means algorithm based on the combination of dynamic programming algorithm and entropy method is proposed. the entropy method is used to amend the distance calculating formula to improve the clustering accuracy, and dynamic programming algorithm is used to define the initial cluster centers. the result of the simulation on the clustering in the mine monitoring sensors shows that the proposed algorithm has better performance than the traditional k-means algorithm in terms of efficiency and clustering accuracy .【key words】k-means; dynamic programming; entropy; clustering accuracy; mine monitoring sensors 0 引 言k-means算法是数据挖掘技术中基于分裂法的一个经典的聚类算法，因为该算法的理论可靠、算法简单、收敛迅速而被广泛应用1-2。但是，k-means算法的聚类结果对初始聚类中心的依赖性导致聚类结果不稳定，并且仅依据对象间的欧式距离而忽略数据对象不同属性对对象间差异程度的影响也使得k-means算法的聚类精确度降低。在实际应用中，如果可以同时从初始聚类中心的选取和对象间欧式距离计算公式的修订两个方面对算法进行改进，将对降低传统k-means算法聚类结果的波动性以及获得一个较好的聚类效果具有重要意义。文献3基于每个数据对象的密度参数选取处于高密度分布的点作为k-means算法的初始聚类中心，提高了聚类的准确率和稳定性。文献4利用贪心算法参照数据样本的分布特征将数据划分为k个集合，选取各集合中数据的平均值作为初始聚类中心。文献5 提出了基于kruskal算法的改进kmeans算法，该算法利用最小生成树的构造原理依次向聚类中心集合中加入当前数据对象中距离最远的两个对象，如此迭代直至集合中包含k个聚类中心为止，取得了良好效果。文献6利用主成分分析方法对原始数据进行预处理，将处理后的数据作为k-means的输入样本，解决了因样本间分类指标信息重叠导致k-means算法效率降低的问题。文献7基于因子分析为复杂参数变量下的数据挖掘有效地减少了冗余字段，提高了k-means分群算法的效率。文献8利用信息熵对数据对象的属性进行赋权，并利用权值来修改距离计算公式，在一定程度上提高了k-means聚类的精度和稳定性。在借鉴以上研究成果的基础上，现提出一种利用熵值法和动态规划算法改进的k-means聚类算法，该算法利用熵值法9-10确定数据属性的权值并进一步得到数据对象和其邻居间的权重系数，采用赋权的欧式距离作为相似性度量的依据，在确定初始聚类中心时，利用动态规划算法求得距离累加和最大的k个数据对象作为初始聚类中心。该算法在矿井监测传感器聚类的应用结果表明该算法提高了聚类的精度和稳定性。 1 相关定义 5 结束语本文结合熵值法和动态规划提出了一种改进的k-means算法，动态规划算法用来对数据进行分析，实现确定对象集的初始聚类中心，熵值法用来计算数据对象的各个属性的权值，用改进的权值修正距离计算公式，以提高聚类的精确度。在矿井监测传感器聚类的应用结果表明，改进的算法较之于传统的k-means算法在算法的计算效率上有所提高，聚类的精确度明显增强。本文利用聚类的数据对象之间存在某种关系的特点，利用动态规划的算法和统计分析的算法对k-means聚类算法进行了改进，得到了良好的效果，而这种改进的思想将会是聚类算法研究的一个新方向。参考文献1 施培蓓.数据挖掘技术中聚类算法的研究d.江南大学，2008.2 苏锦旗，薛惠锋，詹海亮.基于划分的k-均值初始聚类中心优化算法j.微电子学与计算机,2009,26(1):8-11.3 韩凌波，王强，蒋正锋，郝志强.一种改进的k-means初始聚类中心选取算法j.计算机工程与应用,2010,46(17):150-152.4 仝雪姣, 孟凡荣, 王志晓.对k-means初始聚类中心的优化j.计算机工程与设计,2011,08:2721-2723.5 李卫平.对k-means聚类算法的改进研究j.中国西部科技，2010，08:49-50.6 曹国.基于k-means和pca的商业银行客户价值细分模型研究j.财会科技，2010,09:27-29.7 彭凯，秦永彬，许道云.应用因子分析和k-means聚类的客户分群建模j.计算机科学，2011,38(5):154-198.8 原福永，张晓彩，罗思标.基于信息熵的精确属性赋权k-means聚类算法j.计算机应用，2011,31(6):1675-1677.9 陈雷，王延章.熵权法对融合网络服务质量效率保障研究j.计算机工程与应用，2005，41(23):13.10 高孝伟.熵权法在教学评优中的应用研究j.中国地质教育，2008，17(4):100104.11 ahmad a,dey l. a k-mean clustering algorithm for mixed numeric and categorical dataj. dataknowledge engineering,2007,63(2):503-527.12 席景科.时空孤立点检测算法研究d.徐州：中国矿业大学计算机科学与技术学院，2010：48-51.13 he z y, xu x f, deng s c. an optimization model for outlier detection in categorical datac. proceedings, part i. lecture notes in computer science of advances in intelligent computing, international conference on intelligent computing, 2005: 23-26.14 王晓东.计算机算法设计与分析m.北京:电子工业出版社，2008,4:102-127.15 费蓉.动态规划研究及其在电力市场动态分区定价问题上的应用d.西安: 西安理工大学电力电子与电力传动学院，2009：6-9.16 杨世兴. 煤矿监测监控系统的现状与发展j.安防科技，2004，(05):13-19.17 王军号，孟祥瑞.物联网感知技术在煤矿瓦斯监测系统中的应用j.煤炭科学技术，2011，39(7),64-69
