第２９卷第２期 ２０１４年４月 平顶山学院学报 Ｊｏｕｒｎａｌ ｏｆ Ｐｉｎｇｄｉｎｇｓｈａｎ Ｕｎｉｖｅｒｓｉｔｙ Ｖｏ１．２９ Ｎｏ．２ Ａｐｒ．２０１４ 基于Ｋ均值算法的数据聚类和图像分割研究 王军敏，李艳 （平顶山学院电气信息工程学院，河南平顸山４６７０９９） 摘 要：Ｋ均值算法利用Ｋ个聚类的均值作为聚类中心，通过对比样本到各聚类中心的距离，将样本划 分到距离最近的聚类中，从而实现样本的聚类．分析了Ｋ均值算法的基本原理和实现步骤，并将其应用于数据聚 类和图像分割，取得了较好的聚类效果．最后，针对Ｋ均值算法的不足之处，提出了改进措施，提高了Ｋ均值算 法的聚类性能． 关键词：Ｋ均值算法；数据聚类；图像分割 文献标识码：Ａ 文章编号：１６７３—１６７０（２０１４）０２—００４３—０３ 中图分类号：ＴＰ３９１ ０引言 表明聚类效果越好，类间区分度越大，类内数据相 似度越高，所以，当代价函数＇，最小时，Ｋ均值算法 收敛，实现了对数据集的Ｋ个聚类划分． 聚类是将数据集按照数据的相似性分成多个 类的过程，相似度较高的样本归为一类，相似度较 低或不相似的样本则划归到不同的类．聚类分析作 为一种非监督学习方法，可用于数据挖掘、模式识 Ｋ均值算法实现聚类的具体步骤 为： １）输入待分类的数据集Ｘ＝ 和分类数Ｋ． ， ，…， ｝ 别、机器视觉等领域，而Ｋ均值算法就是一种简单 高效，被广泛使用的聚类算法，在数据聚类、图像分 割中具有重要应用． １ Ｋ均值算法的基本原理 …２）初始化：从数据集 中选取 个元素，作为 类｛ｃ。，ｃ ，…， ｝的初始聚类中心｛ 。‘们， ：‘们， ， Ｋ‘。’｝，其中， 表示第 类ｃｉ在第１１，次迭代 后新的聚类中心． ３）将数据归类：根据欧式距离，依次计算每个 数据到各类中心的距离，并比较这些距离的大小， 按最小距离准则将各数据划分到离它最近的那个 聚类中心所在的类．例如，数据 到各类中心的欧 １９６７年ＭａｃＱｕｅｅｎ首次提出了Ｋ均值算法（Ｋ —ｍｅａｎｓ算法）…，很多聚类任务都选择该聚类算 法，它常采用误差平方和函数作为聚类准则函数， 即代价函数．设数据集Ｘ＝｛ ， ：，…， ｝，划分为 氏距离为ｄ（ｘ ， ）＝ＩＩｘ 一 ＝ｌ，２，…， ，其 Ｋ类，则代价函数为．，＝ 【∑ 一 々 Ｇｉ ，其中， 中ｌＩ．１Ｊ表示范数运算．对Ｅ匕这Ｋ个距离，若ｄ（ ， ）最小，表明数据 距离Ｃ 类的中心 最近，则 是第ｉ类ｃｉ的聚类中心，数据 属于第 类ｃｉ，即 ∈Ｃ ．聚类过程就是寻找最佳聚类中心 ， ＝１， 将数据 划归到聚类ｃ 中． ４）更新聚类中心：重新计算Ｋ个聚类的中心 ‘ １２，…，Ｋ，使代价函数 为最小值的过程 ］．要计算 代价函数－，，可先分别计算每一类中各数据到该类 ‘ ， ２，…， Ｋ‘ ｝，其中， ‘ ＝ ｙ ｘｍ表示 ｎ－－ １中心的距离平方和，例如∑ 一 ｌＪ 表示第ｉ类 Ｅｑ 各数据到该类中心Ｉ．ｔ 的距离平方和．然后，将Ｋ类 第 次划分后聚类Ｃ 的中心，／７， 为当前Ｃ 中数据的 个数．在这一步中，因为要计算Ｋ类的均值作为聚 类中心，所以称为Ｋ均值算法． ５）判断分类是否结束：若第 ＋１次划分后的 的距离平方和相加，即可得到代价函数 ．，越小， 收稿日期：２０１４一Ｏ１—０４ 作者简介：王军敏（１９８２一），男，河南省叶县人，硕士，平顶山学院电气信息工程学院讲师，主要研究方向：信号检测与处理 第２期 王军敏，李艳：基于Ｋ均值算法的数据聚类和图像分割研究 ・４５・ 心在几个分布密集区域的中心，其周围的点越容易 分到最近的中心点，聚类收敛越快，所需迭代次数 布密度高的局部区域中心点作为初始聚类中心． 通过对聚类数目Ｋ和初始聚类中心选择的改 越少．以二维数据为例，图４为某数据集的分布情 况，数据主要分布在Ａ， 点周围，若要分为两类， 则选取Ａ，Ｂ两点为初始聚类中心时，其周围的点 到该初始中心的距离区分越明显，越容易收敛．相 反，若选择Ｃ，Ｄ两点为初始中心，则收敛速度慢． 进，可进一步提高Ｋ均值算法的自适应性，更好地 发挥Ｋ均值算法在数据聚类和图像分割中的应 用． 参考文献： ［１］赵丽．全局Ｋ一均值聚类算法研究与改进［Ｄ］．西安： 西安电子科技大学，２０１３． ［２］粱烨炜．Ｋ一均值聚类算法的改进及其应用［Ｄ］．长沙： 湖南大学，２０１２． ［３］周俊，刘丽川，杨继平．基于Ｋ一均值聚类与小波分 析的声发射信号去噪［Ｊ］．石油化工高等学校学报， ２０１３，２６（３）：６９—７３． 图４二维数据的聚类中心选择 ［４］陈坤，马燕，李顺宝．融合直方图阈值和Ｋ一均值 根据随机信号的统计特性，聚类数据应主要分 布在所有数据的均值附近，标准差表明数据分布偏 的彩色图像分割方法［Ｊ］．计算机工程与应用，２０１３，４９ （４）：１７０—１７３． 离均值的程度．设所有数据的均值为 ，标准差为 ｏｒ，则数据应主要分布在（ 一ｏｒ， ＋ ）之间．所以， 可利用数据的均值和标准差统计特性，选择样本分 ［５］张文君．基于均值一标准差的Ｋ均值初始聚类中心选 取算法［Ｊ］．遥感学报，２００６，１０（５）：７１５－７２１． Ｓｔｕｄｙ ｏｆ Ｄａｔａ Ｃｌｕｓｔｅｒｉｎｇ ａｎｄ Ｉｍａｇｅ Ｓｅｇｍｅｎｔａｔｉｏｎ Ｂａｓｅｄ ｏｎ Ｋ——ｍｅａｎｓ Ａｌｇｏｒｉｔｈｍ ＷＡＮＧ Ｊｕｎｍｉｎ，ＬＩ Ｙａｎ （Ｓｃｈｏｏｌ ｏｆ Ｅｌｅｃｔｉｒｃａｌ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｐｉｎｇｄｉｎｇｓｈａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｐｉｎｇｄｉｎｇｓｈａｎ，Ｈｅｎａｎ ４６７０９９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｋ—ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｕｓｅｓ ｔｈｅ ｍｅａｎｓ ｏｆ Ｋ ｃｌｕｓｔｅｒ ａｓ ｔｈｅ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ．Ｂｙ ｃｏｍｐａｒｉｎｇ ｔｈｅ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｔｈｅ ｓａｍｐｌｅ ｔｏ ａｌｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ，ｔｈｅ ｓａｍｐｌｅ ｉｓ ｄｉｖｉｄｅｄ ｉｎｔｏ ｔｈｅ ｎｅａｒｅｓｔ ｃｌｕｓｔｅｒ ＳＯ ａｓ ｔｏ ｒｅａｌｉｚｅ ｔｈｅ ｓａｍｐｌｅ ｃｌｕｓｔｅｒｉｎｇ．Ｔｈｅ ｂａｓｉｃ ｐｒｉｎｃｉｐｌｅｓ ａｎｄ ｓｔｅｐｓ ｏｆ Ｋ—ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ａｒｅ ａｎａｌｙｚｅｄ，ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｉｎ ｄａｔａ ｃｌｕｓｔｅ－ ｒｉｎｇ ａｎｄ ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｉｓ ｇｉｖｅｎ，ｗｈｉｃｈ ａｃｈｉｅｖｅｄ ｇｏｏｄ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ．Ｆｉｎａｌｌｙ，ａｉｍｉｎｇ ａｔ ｔｈｅ ｓｈｏｒｔｃｏｍｉｎｇｓ ｏｆ Ｋ—ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ，ｔｈｅ ｉｍｐｒｏｖｅｍｅｎｔ ｍｅａｓｕｒｅｓ ａｒｅ ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ Ｋ—ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：Ｋ—ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ；ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ；ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ
