东莞理工学院学报 第１ ７卷第３期 Ｖ０Ｉ．１７ ＮＯ．３ ２０１０年６月 ＪＯＵＲＮＡＬ ＯＦ ＤＯＮＧＧＵＡＮ ＵＮＩＶＥＲＳＩＴＹ ＯＦ ＴＥＣＨＮＯＬＯＧＹ Ｊｕｎ． ２ＯｌＯ 一个基于ｋ—ｍ ｅ ａ ｎ ｓ算法的聚类 陈勇 陈健 （东莞理工学院计算机学院，广东东莞５２３８０８） 摘要：用七．ｍｅａｎｓ算法对二维数据进行聚类分析，并用ｃ 语言实现了该算法。先按照样本点的距离 进行初始划分，然后再按照各样本点和初始中点的距离远近进行聚类。结果表明，ｋ－ｍｅａｎｓ算法对二维数 据的聚类是有效的，实现该算法的程序对二维数据的聚类具有通用性。 关键词：足．ｍｅａｎｓ算法；聚类；迭代；数据挖掘 中图分类号：０２１１．４ 文献标识码：Ａ 文章编号ｔ ｌ００９—０３１２（２０１０）０３一ｏ０２７—０５ 随着数据库技术的迅速发展以及数据库管理系统广泛的应用，人们利用信息技术和搜集数据的 能力大幅度提高，数据库被广泛应用于商业管理、办公、科学研究和工程开发等领域。数据挖 掘技术是人们长期对数据库技术进行研究而产生的一种技术。它是一门交叉学科，汇聚了数据库、 人工智能、统计学、可视化等不同学科和领域，因此近年来受到各界的广泛关注” 。聚类是数据挖 掘中的一类重要技术，是分析数据并从中发现有用信息的一种有效手段 。数据聚类是发现事物自 然分类的一种方法，也是机器学习和模式识别的一个重要研究领域。为了得到分类，人们提出了许 多种聚类算法，如庀．ｍｅａｎｓ算法、高斯最大期望算法、七．ｈａｒｍｏｎｉｃ算法等” 。这些算法形成的聚类会 使一个客观划分标准（如最小方差）最优化，从而使得一个聚类中的对象是相似的，而不同聚类中 的对象是不相似的。本文用ｋ．ｍｅａｎｓ算法对一个二维数据集进行聚类。 １ 问题和算法 １．１ 要解决的问题 以坐标表示的７个点（ ・， ， ，，Ｘ４， ｓ， ， ）作为一个聚类分析的二维样本： ．＝（１。２）， ：＝ （３，２）， ，＝（１，１），Ｘ４＝（６，５）， ｓ＝（８，５）， ＝（５，６）， ＝（３，１），要求划分的簇的数量ｋ ＝２。 １．２ ｋ—ｍｅａｎｓ算法 １．２．１ 庀一ｍｅａｎｓ算法的基本思想 ｋ－ｍｅａｎｓ算法采用迭代更新的方法，在每一次迭代中，依据 个聚类中心将周围的点分别组成ｋ 个簇，而重新计算的每个簇的质 ｔｌ，（即簇中所有点的平均值，也就是几何中心）将被作为下一次迭 ⑩ 图１ ｋ—ｍｏａｎｓ算法聚类示意图 收稿日期：２０１ ０—０１—１ ８ 基金项目：广东省科技计划项目（２００９Ｂ０１０８０００５４）。 作者简介：陈勇（１ ９６４一）。男。广东阳江人，【程师，硕士。主要从事人 ＿【智能及数据挖掘研究。 ２８ 东 莞理工学院学报 ２Ｏｌ 代的参照点。迭代使得选取的参照点越来越接近真实的簇的质心，所以目标函数越来越小，聚类效 果也就越来越好” 。图１是聚类示意图。 １．２－２ 一ｍｅａｎｓ算法的基本步骤 步骤一：由样本的随机分布形成下面两个簇开始迭代：Ｃ－＝（ ，， ：， ，， ， ｓ， ）和ｃ：＝（ｘ３， ・， ７）。 步骤二：计算两个簇的中点。 步骤三：计算每个点到两个簇的 中点的距离。 点距离的大小，对二维样本点进行重新分类，形成新簇。 步骤四：按照样本点和两个簇中 步骤五：新簇和旧簇是否一样。 是，则聚类到此结束；否，则按顺序重新执行步骤二、步骤三 和步骤四。 ２算法的实现 ２．１ 编程 编程语言：ｃ 算法实现代码 ／／样本点类 ｐｕｂｌｉｃ ｃｌａｓｓ Ｐｏｓｉｔｉｏｎ｛ ｐｒｉｖａｔｅ ｆｌｏａｔ ｘ，ｙ： ｐｒｉｖａｔｅ ｉｎｔ ｋｌ，ｋ２； ｐｕｂｌｉｃ Ｐｏｓｉｔｉｏｎ（）｛ｊ ｐｕｂｌｉｃ Ｐｏｓｉｔｉｏｎ（ｌｆｏａｔ ｘ，ｆｌｏａｔ Ｙ，ｉｎｔ ｋｌ，ｉｎｔ ｋ２）｛ ｔｈｉｓ．ｘ＝ｘ；ｔｈｉｓ．Ｙ＝ｙ；ｔｈｉｓ．ｋｌ＝ｋｌ；ｔｈｉｓ．ｋ２ ｋ２； ） ｐｕｂｌｉｃ ｌｆｏａｔ Ｘ｛ｇｅｔ｛ｒｅｔｕｒｎ ｘ；｝ｓｅｔ｛ｘ ｖａｌｕｅ；｝｝ ｐｕｂｌｉｃ ｌｆｏａｔ Ｙ｛ｇｅｔ｛ｒｅｔｕｒｎ ｙ；｝ｓｅｔ｛ｙ ｖａｌｕｅ；）） ｐｕｂｌｉｃ ｉｎｔ Ｋ１｛ｇｅｔ｛ｒｅｔｕｒｎ ｋｌ；）ｓｅｔ｛ｋｌ ｖａｌｕｅ；）｝ ｐｕｂｌｉｃ ｉｎｔ Ｋ２｛ｇｅｔ｛ｒｅｔｕｒｎ ｋ２；）ｓｅｔ｛ｋ２ ｖａｌｕｅ；）） ） ｓｔｒｕｃｔ ＭｉｄＸＹ｛ ｐｕｂｌｉｃ ｌｆｏａｔ ｘ：／／簇中点ｘ坐标 ｐｕｂｌｉｃ ｌｆｏａｔ ｙ；／／簇中点Ｙ坐标 ） ｃｌａｓｓ Ｐｒｏｇｒａｍ｛ ／／计算二维样本点到簇巾点的距离 ｓｔａｔｉｃ ｌｆｏａｔ Ｄｉｓｔａｎｔ（ＭｉｄＸＹ ｍｉｄ，Ｐｏｓｉｔｉｏｎ Ｐ）｛ ｌｆｏａｔ ｄｉｓｔａｎｔ； ｄｉｓｔａｎｔ＝（ｌｆｏａｔ）Ｓｙｓｔｅｍ．Ｍａｔｈ．Ｓｑｒｔ（（ｍｉｄ．ｘ－ｐ．Ｘ） （ｍｉｄ．ｘ—ｐ．Ｘ）＋（ｍｉｄ．ｙ。ｐ．Ｙ）‘ （ｍｉｄ．Ｙ—ｐ．Ｙ））； ｒｅｔｕｒｎ ｄｉｓｔａｎｔ； ｝ ／／对样本进行聚类 ｓｔａｔｉｃ ｖｏｉｄ ＤｉｅＤａｉ（ｐａｒａｍｓ Ｐｏｓｉｔｉｏｎ［】Ｐ）｛ ｉｎｔ［】ｃｏｕｎｔ＝ｎｅｗ ｉｎｔ［２】｛Ｏ，０）； ＭｉｄＸＹ［】ｍｉｄ＝ｎｅｗ ＭｉｄＸＹ［２］； ｆｏｒｅａｃｈ（Ｐｏｓｉｔｉｏｎ Ｐ ｉｎ Ｐ）｛ ｉｆ（ｐ．Ｋｌ＝：１）｛ ｃｏｕｎｔ［０】＝ｃｏｕｎｔ［０】＋ｌ； 第３期 陈勇等：一个越于ｋ—ｍｅａｎｓ算法的聚类 ｍｉｄ［Ｏ】．ｘ ｍｉｄ［Ｏ］．ｘ＋ｐ．ｘ； ｍｉｄ［０】．Ｙ ｍｉｄ［０】．Ｙ＋‘Ｐ．Ｙ； ） ｉｆ（Ｐ．Ｋ１＝：２）｛ ｃｏｕｎｔ【１】 ｃｏｕｎｔ［１】＋１； ｍｉｄ［１】．Ｘ ｍｉｄ【１】．ｘ ｐ．ｘ； ｍｉｄ［１】．Ｙ ｍｉｄ【１】．Ｙ ｐ．Ｙ； ｝ ｝ ／／输出簇中点坐标 ｆｏｒ（ｉｎｔ ｉ＝０；ｉ＜２；ｉ＋＋）｛ ｍｉｄ［ｉ］．ｘ／＝ｃｏｕｎｔ［ｉ］；ｍｉｄ［ｉ］．Ｙ／ ｃｏｕｎｔ［ｉ］； ｉｆ（ｉ＝＝０）Ｃｏｎｓｏｌｅ．Ｗｒｉｔｅ（”Ｃｌ簇的中点为：”）； ｉｆ（ｉ＝＝１）Ｃｏｎｓｏｌｅ．Ｗｒｉｔｅ（”Ｃ２簇的巾点为：”）； Ｃｏｎｓｏｌｅ．ＷｒｉｔｅＬｉｎｅ（”（｛０｝，｛１））”，ｍｉｄ［ｉ】－ｘ＿ＴｏＳｔｒｉｎｇ（”Ｆ２”）， ｍｉｄ［ｉ］．Ｙ．ＴｏＳｔｒｉｎｇ（”Ｆ２”））； ｝ ｌｆｏａｔ ｄｉｓｔａｎｔ ｌ，ｄｉｓｔａｎｔ２； ｉｎｔ ｋ：１； ／／输出各二维样本点到簇巾点距离 ｆｏｒｅａｃｈ（Ｐｏｓｉｔｉｏｎ Ｐ ｉｎ Ｐ）｛ ｄｉｓｔａｎｔ １ Ｄｉｓｔａｎｔ（ｍｉｄ［０］，ｐ）；ｄｉｓｔａｎｔ２＝Ｄｉｓｔａｎｔ（ｍｉｄ［１】，ｐ）； Ｃｏｎｓｏｌｅ．ＷｒｉｔｅＬｉｎｅ（”ｘ｛ｏ｝到ｃｌ的距离｛１），￣ｌＪＣ２的距离｛２ ｋ，ｄｉｓｔａｎｔ１．ＴｏＳｔｒｉｎｇ（”Ｆ２”），ｄｉｓｔａｎｔ２．ＴｏＳｔｒｉｎｇ（”Ｆ２”））；ｋ＋＋； ｉｆ（ｄｉｓｔａｎｔｌ＞ｄｉｓｔａｎｔ２）ｐ．Ｋ２＝２； ｅｌｓｅ Ｐ．Ｋ２：ｌ： ｝ Ｃｏｎｓｏｌｅ．Ｗｒｉｔｅ（”产生的新簇ＣＩ：”）； ｆ０ｒ（ｉｎｔｊ ０ｉ＿ｊ＜７；ｊ＋＋）｛ ｉｆ（Ｐ【ｊ】．Ｋ２＝＝１） Ｃｏｎｓｏｌｅ．Ｗｒｉｔｅ（”Ｘ｛０｝”，ｊ十１）； ） Ｃｏｎｓｏｌｅ．Ｗｒｉｔｅ（”＼ｎ”）；Ｃｏｎｓｏｌｅ．Ｗｒｉｔｅ（”产生的新簇Ｃ２：”）； ｆｏｒ（ｉｎｔｊ Ｏ；ｊ＜７；ｊ＋＋）｛ ｉｆ（Ｐ［ｊ】．Ｋ２＝；２） Ｃｏｎｓｏｌｅ．Ｗｒｉｔｅ（”Ｘ｛０）”，ｊ＋１）； ｝ Ｃｏｎｓｏｌｅ．Ｗｒｉｔｅ（”＼ｎ”）； ｝ ｓｔａｔｉｃ ｖｏｉｄ Ｍａｉｎ（ｓｔｒｉｎｇ［】ａｒｇｓ）｛ ｂｏｏｌ ｓｉｇｎ＝ｔｒｕｅ； Ｐｏｓｉｔｉｏｎ［】ｐｏｓｉｔｉｏｎ＝ｎｅｗ Ｐｏｓｉｔｉｏｎ［７］； ｐｏｓｉｔｉｏｎ［Ｏ】＝ｎｅｗ Ｐｏｓｉｔｉｏｎ（１，２，１，０）； ／／Ｘｌ ｐｏｓｉｔｉｏｎ【Ｉ】＝ｎｅｗ Ｐｏｓｉｔｉｏｎ（３，２，１，０）； ／／Ｘ２ ｐｏｓｉｔｉｏｎ［２】＝ｎｅｗ Ｐｏｓｉｔｉｏｎ（１，１，２，ｏ）； ／／Ｘ３ ｐｏｓｉｔｉｏｎ［３】＝ｎｅｗ Ｐｏｓｉｔｉｏｎ（６，５，２，０）； ｜｜Ｘ４ ｐｏｓｉｔｉｏｎ［４】＝ｎｅｗ Ｐｏｓｉｔｉｏｎ（８，５，１，Ｏ）； ｜ ５ ｐｏｓｉｔｉｏｎ［５】＝ｎｅｗ Ｐｏｓｉｔｉｏｎ（５，６，１，０）； ／／Ｘ６ ｐｏｓｉｔｉｏｎ［６】＝ｎｅｗ Ｐｏｓｉｔｉｏｎ（３，１，２，ｏ）； ／／Ｘ７ ｗｈｉｌｅ（ｓｉｇｎ）｛ Ｑ ＤｌｅＤａｌ（ｐｏｓｉｔＩｏｎ）； ｉｎｔ ｃｏｕｎｔ＝Ｏ： 查苤 茎堕学报 ２０１ ｆｏｒ（ｉｎｔｊ＝０；ｊ＜７；ｊ＋＋）｛ ｉｆ（ｐｏｓｉｔｉｏｎ［ｊ］．Ｋ１＝＝ｐｏｓｉｔｉｏｎ［ｊ］．Ｋ２）ｃｏｕｎｔ＋＋； ｉｆ（ｃｏｕｎｔ＝ ７）｛ｓｉｇｎ＝ｆａｌｓｅ；｝ ） ｉｆ（！ｓｉｇｎ）ｂｒｅａｋ； ｆｏｒｅａｃｈ（Ｐｏｓｉｔｉｏｎ Ｐ ｉｎ ｐｏｓｉｔｉｏｎ）｛ ｐ．ＫＩｐ．Ｋ２； ｝ ） Ｃｏｎｓｏｌｅ．ＲｅａｄＫｅｙ（）； ｝ ） ２．２ 结果 结果精确到小数点后两位。 第一次迭代： Ｃ・簇的中点为：（４．２５，３．７５）。 Ｃ：簇的中点为：（３．３３，２．３３）。 一到Ｃ・的距离３．６９，到Ｃ：的距离２．３６。 到Ｃ－的距离２．１５，到 的距离０．４７。 到Ｃ，的距离４．２６，到 的距离２．６９。 到Ｃｔ的距离２．１５，到Ｃ：的距离３．７７。 ：，Ｘｓ到Ｃ・的距离３．９５，到Ｃ：的距离５－３７。 到Ｃｔ的距离２．３７，到Ｃ２的距离４．０３。 ，到Ｃ－的距离３．Ｏ２，到 的距离１．３７。 产生的新簇Ｃｔ：｛ ， ｓ， ）。 产生的新簇Ｃ：：｛ 一， ：， ，，Ｘ７）。 第二次迭代： Ｃ・簇的中点为：（６．３３，５．３３）。 Ｃ：簇的中点为：（２．Ｏ０，１．５０）。 ｔ一 到Ｃ－的距离６．２９，到Ｃ：的距离１．１２。 到Ｃ・的距离４．７１，到Ｃ２的距离１．１２。 ｚ，到Ｃ．的距离６．８７，到Ｃ：的距离１．１２。 到Ｃ．的距离０．４７，到Ｃ：的距离５．３２。 Ｘｓ到Ｃ，的距离１．７０，到Ｃ：的距离６．９５。 到Ｃ。的距离１．４９，到Ｃ：的距离５．４１。 ，到Ｃｔ的距离５．４７，到Ｃ：的距离１．１２。 产生的新簇Ｃ・：｛ ，Ｘ５， ｏ）。 产生的新簇Ｃ２：｛ －， ， ３， ｝。 相邻两次聚类结果一样，ｋ－＇ｍｅａｎｓ算法结束。 ２．３ 结果分析 从７个二维数据样本集｛Ｘｌ，Ｘ２，Ｘｓ，Ｘ４，Ｘｓ，Ｘ６， ，｝，可以很容易看出（ －， ：， ， ，）应该聚为一个 簇，｛ ， ｓ，Ｘ６）应该为另一个簇，实验结果也表明了这一点，从而表明了七－ｍｅａｎｓ算法的有效性。 第３期 陈¨ 勇等：一个 于庀一ｍｅａｎｓ算法的聚类 口 ３ｌ ３ 结语 本文简要介绍足．ｍｅａｎｓ算法的基本思想及具体步骤，针对要解决的问题，使用ｋ－ｍｅａｎｓ算法思想 （按照样本点与簇的中点距离大小，对样本点进行聚类），用ＣｊＩｊ｝语言实现了该算法，并解决了二维 数据集聚类问题。算例表明，使用ｋ．ｍｅａｎｓ算法可以对二维数据有效地实现聚类。编制的程序对二维 数据的聚类具有通用性。 参考文献 朱明．数据挖掘［Ｍ】．合肥：中国科学技术大学出版社，２００８． 张一Ｋ芳，毛熹莉，熊忠阳．一种改进的ｋ—ｍｅａｎｓ算法［Ｊ】ｌ计算机应用，２００３，８（８）：３１－３３． 袁方，孟增辉，于戈．对ｋ—ｍｅａｎｓ算法的改进【Ｊ】＿计算机工程与应用，２００４，３６（１）：１ ７７－ｌ ８０ 王燕．一种改进的ｋ－ｍｅａｎｓ聚类算法［Ｊ】．计算机应用与软件，２００４，ｌ０（３）：１２２－１２３． Ａ Ｃｌｕｓｔｅｒｉｎｇ Ｂａｓｅｄ ｏｎ ｋ－Ｍｅａｎｓ Ａｌｇｏｒｉｔｈｍ ＣＨＥＮ Ｙｏｎｇ ＣＨＥＮ Ｊｌａｎ （Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ，Ｄｏｎｇｇｕａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｄｏｎｇｇｕａｎ ５２３８０８，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ Ｔｈｉｓ ｐａｐｅｒ ｕｓｅｓ七一ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｔｏ ａｎａｌｙｓｅ ｃｌｕｓｔｅｒｅｄｌｙ ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ，ａｎｄ ｉｍｐｌｅｍｅｎｔｓ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｎ Ｃ ｌａｎｇｕａｇｅ．Ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｍａｋｅｓ ｉｎｉｔｉａｌ ｄｉｖｉｓｉｏｎ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｓａｍｐｌｅ ｐｏｉｎｔｓ．ａｎｄ ｔｈｅｎ ｃｌｕｓｔｅｒｓ ｔｈｅｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｅａｃｈ ｓａｍｐｌｅ ｐｏｉｎｔ ａｎｄ ｉｎｉｔｉａｌ ｍｉｄｐｏｉｎｔ．Ｔｈｅ ｒｅｓｕｌｔ ｓｈｏｗｓ ｔｈａｔ庀－ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｉｓ ｖａｌｉｄ ｔｏ ｃｌｕｓｔｅｒ ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ ｄａｔａ，ａｎｄ ｔｈｅ ｐｒｏｃｅｄｕｒｅ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ａｐｐｌｉｃａｂｌｅ ｆｏｒ ｃｌｕｓｔｅｒｉｎｇ ｔｗｏ－ｄｉｍｅｎｓｉｏｎａＩ ｄａｔａ． Ｋｅｙ ｗｏｒｄｓ七一ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ；ｃｌｕｓｔｅｒｉｎｇ；ｉｔｅｒａｔｉｖｅ；ｄａｔａ ｍｉｎｉｎｇ
