基于面向对象思想KMeans算法实现.pdfVIP

第lO卷第3期 滁州学院学报 V01．10No．3 200旧年5月 oFCH唧0UUNn咂RSrrY May．2008 JOUIINAL 基于面向对象思想KMeans算法实现 陈寿文，，： 李明东- (1．西华师范大学计算机学院，四川南充637000；2．滁州学院数学系，安徽滁州239000) 摘要：KMe咖算法是聚类算法中的一种常用算法。在模式识别和聚类中经常被使用，属于无监督武分类的 一个分支。其主要目的是对具有相同数据类型的样本数据按距离最短规则进行集合的划分。最终获取各等价 类。在采用面向对象程序设计方法时，利用Y蛐幽n类实现各样本的相关运算，并采用IJiIll【U8t类对象来存储 各等价类中的元素，从而简化了实现的复杂度。并试图从初始化聚类中心点角度对Ⅺ吼：咖算法提出了改进。 关键词：对象；类；KMe咖算法实现 中图分类号：0121-4 文献标识码：A 文章编号：1673—1794(2008)03—0042咱3 作者简介：陈寿文(1979_)，男，安徽怀宁人，西华师范大学计算机学院2007级硕士研究生潞州学院数学系． 1 KMe舭8算法简介 1．1KMea璐算法算术描述 KHeans算法是一种聚类算法，经常运用于数据挖掘和模式识别中，是一种无监督式的学习算法，其使 用的目的是对集合进行等价类的划分，即对一组具有相同数据结构的纪录按某种分类准则进行分类，以获取 若干个同类记录集田，相应的数学语言描述为： ×1-(×11，X12，…，X1n1． 【 ， 结论A—fA1．A2．…，AKl中A1 为集合A，中记录的 1-1。…．K的获取，其畸哇。nA膨．UA一，∑IA；I=^‘lA；I I l I i=1 个数． 1．2l【I慨算法实现步骤描述目 Sb叩2：以cb％…，cx为参考对所有的记录)【i嘶．谭进行归类，其中归类的标准为： If ID(剖Il酬b．K肄．K砖．僵，一then置划分到A，中； step3：重新计算各划分记录集合A，产1，…，k的参考中心，通常按照加权平均的方式处理，即：。 五 c≥由∑)(jEA轴 s姊)4：计算平方误差髓∑∑五EA0．≯毛‘I； St印5：E不再改变或各A孙．‘中的成员不再改变时算法终止，否则转Step2继续． 1．3KMea璐算法改进 一42— 由于在KMeaIls算法中初始化聚类中心的时候，习惯性采用随机抽取样本数据集合中的K个样本来近似， 所以样本点抽取的不同将很大程度地影响聚类结果的获取，为此，本文采用了预处理初始聚类中心点的方法来 改进该算法．其中点】【P到集合A的最短距离定义为：】【p与集合A中任一点】【q的距离的最小值钿dn{I节气Il，∥ ．最长距离则反之．具体处理过程如下： stepl：从样本总体集合A中选择距离最长的两点】【p，】【q，构造中间集合船¨，Al_㈥，脯～．埘。； ste母随机生成一随机数同-龃dO吲嫉类教耳)，分别对～，A-进行添加r个样本，添加的策略为：从D集合 1…r； Step3：分别计算～，A。的加权平均中心Co和C。作为聚类的初始中心； D=D一{0，仿step2向札中添加r个样本，计算Ak的加权中心c。； Step5：重复Step4直到k_l(．-2； Step6：对所有样本集合A，分别以氏庐c-．《为聚类初始中心执行KMealls算法； 2算法实现 2．1l(fⅥea璐算法实现 通过观察，该算法中处理的对象分为两种，即其中之一均为同一数据类型的向量鼯Ⅸ函X西…，Xd计帕涉及到 的操作有“