一种 K-均值聚类的改进算法及其应用.pdf

第 24卷第 5期 测 绘 工 程 Vo1．24。NO．5 2015年 5月 EngineeringofSurveyingandM apping M ay．2015 一 种 K一均值聚类的改进算法及其应用 江京亚 ，郭庆胜 ，陈 旺 ，周贺杰 ，陈 勇 (1．武汉大学 资源与环境科学学院，湖北 武汉 430079；2．湖北省鄂东地质大队，湖北 孝感 432000) 摘 要：由于传统的K一均值聚类算法固有的特性，如对初始聚类中心的依赖性和对噪声点的敏感性，导致了其聚类 结果的不稳定。文中基于k-dist图提出一种改进算法，算法首先去除数据集中的噪声点，然后从数据集中选取靠近 点聚集区域、相距最远的 个数据点作为初始簇中心。实验结果证明，文中算法能够很好地消除K一均值聚类算法对 初始簇中心的依赖性，并能有效去除噪声点。 关键词：数据挖掘 ；K一均值聚类；第4邻近距离图；初始簇中心；噪声点 中图分类号：TP301．6 文献标识码 ：A 文章编号：1006—7949(2015)05—0042—05 A K—meansalgorithm basedon densityand itsapplication JIANGJing—ya，GUOQing—sheng，CHENWang，ZHOU He-jie，CHENYong (1．SchoolofResourceandEnvironmentScience，W uhanUniversity，W uhan430079，China；2．NortheasternHubeiGeological Brigade，Xiaogan432000，China) Abstract：Because ofthe inherent characteristics ofthe traditionalK-means algorithm ，such as the dependenceoftheinitialclusteringcenterandthesensitivitytonoisepoints，itiseasytogeneratethe instableclusteringresults．An improvedalgorithm isproposedbasedonthe志一distgraph．Thealgorithm firstremovesthenoisepointsofthedataset。andthenselectsk initialcenter，which iSclosetothepoint gatheringareaandfarawayfrom eachother．Theexperimentalresultsshow thatthealgorithm can eliminateitsdependenceoftheinitialcenteraswellasremovingthenoisepointseffectively． Keywords：datamining；K-meansalgorithm ；4一distGraph；initialclusteringcenter；noisepoints 聚类分析是人类理性认识 自然，科学分析世界 由于其简单、高效，已被广泛应用于诸如图像处理、 的主要手段之一。自1994年，李德仁院士在国际上 模式识别、人工智能和市场销售等领域。然而K一均 首次提出空间数据挖掘与知识发现 (Knowledge 值聚类其本身却存在很多缺陷，如对初始聚类中心 DiscoveringandDataMining)这一概念以来 ，聚类 的依赖性和对少量噪声点的敏感性。本文正是为 分析在信息领域得到空前发展，至今已成为空间数 了较好克服这两方面的缺陷，基于k-dist图(又称第 据挖掘与知识发现的主要技术手段之一_1]。近十年 k邻近距离图)提出了一种改进 K一均值聚类算法。 来，聚类分析 已经成为数据挖掘 中的一个热点，得 通过数据集的第 k邻近距离图，获得噪声范围去除 到广大学者的关注。综合 国内外多年的研究成