第 31 卷第 2 期 2011 年 2 月 计算机应用 Journal of Computer Applications Vol． 31 No． 2 Feb． 2011 文章编号:1001 － 9081(2011)02 － 0432 － 03 doi:10． 3724 / SP． J． 1087． 2011． 00432 基于密度的改进 K 均值算法及实现 傅德胜，周 辰 ( 南京信息工程大学 计算机与软件学院，南京 210044) ( 000501@ nuist． edu． cn) 摘 要:传统的 K 均值算法的初始聚类中心从数据集中随机产生，聚类结果很不稳定。提出一种基于密度算法 优化初始聚类中心的改进 K-means 算法，该算法选择相互距离最远的 k 个处于高密度区域的点作为初始聚类中心。 实验证明，改进的 K-means 算法能够消除对初始聚类中心的依赖，聚类结果有了较大的改进。 关键词:聚类; K-均值算法;初始聚类中心;高密度区域 中图分类号: TP301 文献标志码:A Improved K-means algorithm and its implementation based on density ( Computer and Software College， Nanjing University of Information Science and Technology， Nanjing Jiangsu 210044， China) FU De-sheng， ZHOU Chen Abstract: The initial clustering center of the traditional K-means algorithm was generated randomly from the data set， and the clustering result was unstable． An improved K-means algorithm based on density algorithm optimizing initial clustering center was proposed， which selected the furthest mutual distance k points in high-density region as the initial centers． The experimental results demonstrate that the improved K- means algorithm can eliminate the dependence on the initial cluster center， and the clustering result has been greatly improved． Key words: clustering; K-means algorithm; initial clustering center; high-density area 0 引言 “聚类”是人类的一项最基本的认识活动。聚类分析是 数据挖掘领域的一个重要分支，通过聚类可以把数据对象分 成若干个类或簇，使得不同类中的数据对象相似度低，同一个 类中的数据对象相似度高。聚类操作要划分的类是事先未知 的，类的形成完全是数据驱动的，是一种无监督的学习方法。 聚类分析在数据挖掘领域中，既可以作为数据挖掘其他算法 的预处理步骤，又可以作为一个独立的工具来获得数据的分 布情况。聚类分析的用途非常广泛，在图像处理、模式识别、 市场分析、目标客户定位、生物种群划分等方面具有广泛的应 用前景。 K-means ［1］算法是一种得到最广泛使用的基于划分的聚 类算法，该算法简单、快速，对处理大数据集，该算法是相对可 伸缩和高效的，但是聚类结果的好坏取决于对初始聚类中心 的选择。传统的 K-means 算法的初始聚类中心是随机从数据 集中产生的，容易陷入最小局部最优解，且聚类结果不稳定。 针对传统 K-means 算法的缺点，很多研究人员提出了一 系列改进的 K-means 算法。文献［2］提出用 k-d 树结构改进 K-means 算法;文献［3］用遗传算法优化 K-means 算法，将遗 传算法的全局搜索能力和 K-means 算法的局部搜索能力结合 起来;文献［4］提出了一种新的基于数据样本分布选取初始 聚类中心的 K-means 算法。 本文提出一种基于密度算法的改进 K-means 算法，该算 法产生的初始聚类中心处于数据集的高密度区域，能很好地 体现数据的分布情况，消除了传统 K-means 算法对初始聚类 中心的依赖。 1 K-means 算法 K-means 算法的基本思想是:随机地选择 k 个对象，每个 对象初始代表了一个簇的平均值或中心;对剩余的每个对象 根据其与各个簇中心的距离，将它赋给最近的簇;然后重新计 算每个簇的平均值。不断重复该过程，直到准则函数收敛。 准则函数 E 定义为: k E = ∑ i = 1 ∑ x∈Ci | x － xi | 2 (1) 其中:E 是数据集所有对象与它所在簇的中心点的平方误差 的总和，E 越大说明对象与聚类中心的距离越大，簇内的相似 性越低;反之 E 越小说明簇内的相似性越高。x 为簇内的一 个数据对象;xi 是 k 个 簇中的第 i 个簇。 的聚类中心;k 是簇的个数;Ci 是簇 Ci K-means 算法描述如下: 输入:包含 n 个对象的数据集和簇的数目 k。 输出:k 个簇，满足准则函数收敛。 1) 随机选择 k 个数据对象，每个对象作为初始聚类中心; 2) 根据每个聚类对象的均值，计算每个数据对象与聚类 中心的距离，根据距离将对象划分到距离最近的簇; 3) 重新计算每个簇中对象的平均值，更新簇的聚类 中 心; 4) 重复 2) ～ 3) ，直到准则函数 E 不再变化。 收稿日期:2010 － 06 － 23;修回日期:2010 － 09 － 07。 作者简介:傅德胜(1950 － ) ，男，江苏靖江人，教授，博士生导师，主要研究方向:信息安全; 周辰(1986 － ) ，男，山东临沂人，硕士研究生， 主要研究方向:信息安全。 

第 2 期 傅德胜等:基于密度的改进 K 均值算法及实现 334 2 基于密度算法的改进 K 均值算法 3 实验结果和分析 由于传统的 K 均值算法对初始聚类中心敏感，聚类中心 的不同往往会导致聚类结果有很大的波动性。针对这一缺点， 找到一组能反映数据分布特征的数据对象作为初始聚类中 心，即可优化初始聚类中心，进而提高传统 K 均值算法的计算 稳定性。 传统 K 均值算法用欧氏距离作为相似性度量的标准，随 机初始化聚类中心不能很好地体现数据的分布情况，而相互 距离最远的 k 个对象更具有代表性。但是只考虑距离最远往 往会取到噪声点，对聚类结果不利，所以在选取初始聚类中心 时，还要考虑数据对象的密度。通常在一个数据集合里，高密 度区域的数据对象被低密度区域的对象所分割，一般情况下， 处于低密度区域的数据对象通常被认为是噪声点［5］ 。为了避 免噪声数据的干扰，本文取相距最远的 k 个处于高密度区域 的点作为初始聚类中心。 定义 1 对象的 ε-邻域。给定的数据对象在半径 ε 内的 区域，ε 越大，说明数据对象所处区域的数据密度越低;反之， ε 越小，说明数据对象所处区域的数据密度越高。 Ptsmin 定义 2 核心对象。如果一个对象的 ε- 邻域至少包含 个对象，则称该对象为核心对象。 定义 3 两个 n 维数据对象的距离公式为: d( i，j) = ) 2 + … + ( xin － yjn ) 2 + ( xi2 － yj2 ( xi1 － yj1 ) 2 槡 (2) 和 分别表示对象 i 和对象 j 在第 1，2，…，n 维的数 其中: d( i，j) 是 n 维数据对象 i 和 j 的距离;xi1 ，yj2 yj1 据。 ，…，xin ，…，yjn ，xi2 基于密度算法的改进 K 均值算法描述如下。 输入:包含 n 个对象的数据集、簇的数目、邻域半径 ε 以 及邻域包含对象的最小数目 Ptsmin ; 满足最小数目 Ptsmin 输出:满足准则函数收敛的 k 个簇。 算法步骤: 1) 计算数据集中所有对象间的距离 d( i，j) 。 2) 计算每个数据对象的 ε-邻域包含的数据对象的个数， ，就将该对象加入高密度区域集合 D 中。 ，即 该对象的 ε-邻域包含的对象个数最多，然后从集合 D 中删除 该对象，将 k1 4) 计算 k1 加入到初始聚类中心集合。 和集合 D 中所有数据对象的距离，找出离 k1 ，从集合 D 中删除该对象，然后将 k2 3) 从集合 D 中找出处于最高密度区域的数据对象 k1 加入初始 最 远的数据对象 k2 聚类中心集合。 和 k2 的 k3 将 k3 最远的数据对象 k3 ，即得到 的距离之和最大，从集合 D 中删除该对象，然后 5) 从集合 D 中找出离 k1 与 k1 、k2 加入到初始聚类中心集合。 6) 继续从集合 D 中找出离初始聚类中心集合最远的对 象，即得到的对象与初始聚类中心集合中所有的对象的距离 之和最大，直到找到第 k 个初始聚类中心。 7) 从得到的这 k 个初始聚类中心出发，运用 K 均值算法 进行聚类。 本文将传统的 K 均值算法和优化初始聚类中心的改进 K ［6］数据 均值算法进行了对比实验。采用的测试数据集是 UCI 库的 Iris、Glass Identification、Wine 和 Hayes-Roth 4 组 数 据。 UCI 数据库是一个专门用于测试机器学习、数据挖掘算法的 公共数据库，库中的数据都有确定的分类，因此可以用准确率 来直观地表示聚类的质量。为了验证算法的准确率，测试数 据集的数据分布保持原有状态，不做任何的人工处理。 根 据 实 验 经 验，改 进 算 法 测 试 时 对 Iris 和 Glass Identifications 数据集指定邻域半径 ε 为 1，最小数目 Ptsmin 为 为 40; 对 于 40;对于 Wine 数 据 集，指 定 ε 为 10 000，Ptsmin Hayes-Roth 数据集，指定 ε 为 500，Ptsmin 为 40。由于运用改进 K 均值算法得到的初始聚类中心是确定的，所以用改进后的 算法只进行一次实验，得到的最高、最低和平均聚类精度以及 最大、最小和平均准则函数 E 是相同的。运用传统的 K 均值 算法进行 20 次实验，本文算法进行 1 次实验，实验结果如表 1、2 所示。 表 1 K-means 算法与本文算法聚类精度比较 算法 数据集 K-means 本文算法 Iris Glass Wine Hayes-Roth Iris Glass Wine Hayes-Roth 最高 89． 33 74． 77 74． 16 80． 30 89． 33 55． 61 70． 22 80． 30 聚类精度 / % 最低 82． 00 47． 20 70． 22 77． 27 89． 33 55． 61 70． 22 80． 30 平均 87． 30 64． 74 71． 01 78． 41 89． 33 55． 61 70． 22 80． 30 表 2 K-means 算法与本文算法准则函数 E 比较 % 算法 数据集 Emax Emin Eavg K-means 本文算法 Iris Glass Wine 145． 279 32 78． 940 84 98． 510 58 585． 457 03 336． 268 65 409． 979 66 2． 646 97E6 2． 370 69E6 2． 423 93E6 Hayes-Roth 2． 174 1E4 2． 171 8E4 2． 174 0E4 Iris Glass Wine 78． 940 84 78． 940 84 78． 940 840 378． 909 80 378． 909 80 378． 909 80 2． 370 69E6 2． 370 69E6 2． 370 69E6 Hayes-Roth 2． 174 10E4 2． 174 1E4 2． 174 1E4 运用传统 K-means 算法和本文算法各进行一次实验，算 法执行时间如表 3 所示。 表 3 K-means 算法与本文算法执行时间比较 算法 数据集 执行时间 / ms K-means 本文算法 Iris Glass Wine Hayes-Roth Iris Glass Wine Hayes-Roth 16 16 15 16 110 187 125 63 由表 1、2 可见，本文算法对 Iris 和 Hayes-Roth 数据集的 

434 计算机应用 第 31 卷 聚类精度达到了传统 K-means 的最高聚类精度，而且 E 的值 等于传统算法的 E 的最小值，这说明改进后的算法对于 Iris 和 Hayes-Roth 数 据 集 有 非 常 好 的 聚 类 效 果。 对 于 Glass Identification 数据集，改进的算法的聚类精度低于传统算法的 平均聚类精度，但是 E 的值小于传统算法 E 的平均值，这说明 改进后的算法对于 Glass Identification 数据集有较好的聚类效 果。而对于 Wine 数据集，虽然改进的算法的聚类精度等于传 统算法的最小精度，但是 E 的值是传统算法的最小值，这说明 改进的算法对于 Wine 数据集的聚类效果也有一定的改进。 由表 3 可以可知，本文算法较传统的 K-means 算法在执 行时间上要长，分别是传统算法执行时间的 6． 9 倍、11． 7 倍、 8． 3 倍和 3． 9 倍。虽然本文算法在聚类精度和准则函数都有 了一定的改进，但是本文算法的执行时间延长了。对于较小 数据量的数据集，本文算法延长的执行时间是可以接受的。 但是也看到，对于 Wine 数据集本文算法的聚类精度较传 统的 K-means 算法的平均聚类精度低，只能达到传统算法的 最低聚类精度。Wine 数据集的每个数据项有 14 个属性，各 个数据项的取值范围差距较大，尤其是 Proline 属性，它的取 值范围是 278 ～ 1 680，在计算数据对象间距离时该属性的影 响很大，致使处于高密度区域的相互距离最远的 k 个对象并 不能很好地体现数据的实际分布情况［4］ 。这说明本文算法 有一定的局限性。 4 结语 K-means 算法是一种应用广泛的聚类算法，其初始聚类 中心随机选择，聚类结果随初始聚类中心的不同而波动，从而 导致聚类结果不稳定。本文从优化初始聚类中心出发，提出 了一种基于密度算法的初始聚类中心的改进 K-means 算法， 实验表明，本文算法能够消除对初始聚类中心的依赖，有较好 的聚类效果。 本文算法对于属性取值范围很大的数据集有一定的局限 性，这将在今后的工作中去完善。 参考文献: ［1］ McQUEEN J． Some methods for classification and analysis of multi- variate observations［C］ / / Proceedings of the 5th Berkeley Symposi- um on Mathematical Statistics and Probability． Berkeley: University of California Press， 1967: 281 － 297． ［2］ ALSABTI K， RANKA S， SINGH V． An efficient K-means cluste- ring algorithm ［C ］ / / IPPS / SPDP Workshop on High Performance Data Mining． Orlando，Florida: ［s． n． ］， 1998: 9 － 15． ［3］ 陆林华，王波． 一种改进的遗传聚类算法［J］． 计算机工程与应 用，2007，43( 21) : 170 － 172． ［4］ 曹志宇，张忠林，李元韬． 快速查找初始聚类中心的 K-means 算 法［J］． 兰州交通大学学报，2009，28( 6) : 15 － 18． ［5］ ESTER M， KRIEGEL H P， SANDER J， et al． A density-based al- gorithm for discovering clusters in large spatial databases with noise ［C］ / / Proceedings of the 2nd International Conference on Knowl- edge Discovery and Data Mining． Portland: AAAI， 1996: 226 － 231． ［6 ］ David aha and fellow graduate students at UC irvine ［ EB / OL ］． ［2010 － 06 － 01］． http: / / archive． ics． uci． edu / ml / datasets． html． ( 上接第 427 页) 其中:K0 、K1 、K2 部二分之一处的特征值，i = 2，3，…，128。 分别表示质心处、上半部二分之一处和下半 珔K = K0 + K1 + K2 3 (7) 式(6) 将一颗开心果的 3 个特征值结合在一起，开壳果 的 珔K 值要大于闭壳果的 珔K，因此可设定一个阈值，珔K 值大于设 定阈值的开心果为开壳果，而小于阈值的为闭壳果。 4 实验及分析 实验中选取 珔K = 410 为阈值，对 152 幅样本图像进行了 实验，其中开壳果图像 120 幅，闭壳果图像 32 幅。结果如表 1 所示，120 颗开壳果能正确识别 112 颗，识别率为 93． 3% ;而 对于 32 颗闭壳果，正确识别率达 100% 。因此本算法能从开 心果中剔除闭壳果，而且开壳果的识别率效高。 表 1 类型 颗数 正确识别数 错误识别数 正确识别率 / % 开壳果 120 闭壳果 32 112 32 8 0 93． 3 100． 0 5 结语 本文研究了利用图像处理技术从开心果中选出闭壳果以 提高开心果产品品质。提出的闭壳果和开壳果图像特征处理 方法能较好地区分出开壳果与闭壳果，选取 3 条像素行灰度 值曲线能有效提高开壳开心果部分果肉与果壳颜色相近时的 识别率。实验结果表明，开壳果的正确识别率为 93． 3% ，闭 壳果的正确识别率达 100． 0% ，为开心果自动分级提供了基 础研究。 参考文献: ［1］ 梁理． 开心果生产工艺及安全卫生规范［J］． 农业与技术， 2006， 26( 3) : 167 － 168． ［2］ 李疆． 美国加州的阿月浑子产业概况 ［J］． 经济林研究，2003，21 ( 4) : 102 － 103． ［3］ 王树清，尚新业，石玉琴，等． 新疆阿月浑子资源情况［J］． 经济林 研究，1996，14( 4) : 54 － 55． ［4］ California pistachio production history ［ EB / OL ］． ［2010 － 10 － 08］． http: / / acpistachios． org / pdf /2009Statistics． pdf． ［5］ OMID M， MAHMOUDI A， OMID M H． An intelligent system for sorting pistachio nut varieties［J］． Expert Systems with Applications， 2009， 36( 9) : 11528 － 11535． ［6］ PEARSON T， TOYOFUKU N． Automated sorting of pistachio nuts with closed shells［J］． American Society of Agricultural Engineers， 2000，16( 1) : 91 － 94． ［7］ 杨恒，魏安智，杨途熙，等． 开心果的生物学特性及主要品种简 述［J］． 陕西林业科技， 2002( 4) : 54 － 56． ［8］ 蒋建国． 美国的开心果产业［J］． 柑桔与亚热带果树信息， 1999 ( 1) : 16 － 18． ［9］ 谢凤英， 赵丹培． Visual C + + 图像处理［M］． 北京: 电子工业出 版社，2008． ［10］ 张宏林． 精通 Visual C + + 数字图像处理典型算法及实现［M］． 北京: 人民邮电出版社，2008．