一种K-means算法的k值优化方案

2007年第9卷第6期 总第87期 巢湖学院学报 Joumal0fC}laohuCoUege N0．6。V01．9．20口7 Gene甩lSe—alNo．87 一种K—means算法的k值优化 吴艳文胡学钢 (合肥工业大学计算机与信息学院．安徽合肥230000) 摘要：聚类算法是数据挖掘中核心技术之一，而k_means算法在经典聚类算法中占有重要 地位。针对k_means聚类算法的最佳聚类个数k不易获得，因而使得该聚类算法的应用受到 限制，为此提出一种k值优化方法：通过给出大于最佳聚类数的可能聚类数．而得到优化的 聚类个数。通过实例给予验证，其结果该方法合理有效。 关键词：聚类；k均值算法；聚类教优化；数据挖掘 中图分类号：’IPl8l文献标识码：A 文章编号：1672-2868(2007)06-0021—04 引言 聚类(dustering)是数据挖掘中发现知识常 用到的方法之一，它是将数据集划分为若干个类 (cluster)的过程。聚类目的使得同一个类中数据 对象(样本点)具有较高的相似度，而不同类中的 数据对象则是不相似的。聚类方法主要有：划分 方法、分层类方法、基于密度方法、基于网格方法 和基于模型方法。旧 在众多的聚类方法中。基于划分方法的k— mearIs[1】算法因其算法复杂度较低0“kn)(n为数 据对象总数，k为聚类个数，t为循环次数)，效率 高、应用领域广、具有一定的可扩展性等优点．在 聚类算法中占有重要的地位。但由于其自身的缺 点，如：聚类个数k必须事先给定、不适用于非凸 形状的聚类或以及具有各种大小不同的聚类、对 噪声和异常数据也很敏感等缺点。限制了其广泛 地应用。在大多数情形下，我们所研究、挖掘知识 的领域往往是我们未知的领域，其最优聚类数k 往往是不得而知。为此本文提出一方案以实现k 值的优化。 本文的结构是：第一节介绍k—rmarIs算法实 现的过程，第二节讨论目前k值优化方案．第三 节提出一种k值优化方案，第四节通过实例证实 所提出方案的合理性，第五节结束语。 1 k—meam算法 k—mens算法工作过程如下：首先从n个数 据对象任意选择k个对象作为初始聚类中心．而 对于所剩下的其它对象，则根据它们与这些聚类 中心的相似度(距离)，分别将它们要配与其最相 似的(聚类中心所代表)聚类，然后再计算每个所 获新聚类中心(该聚类中所在对象的均值)。不断 重复这一过程，直到测度函数(1．1)开始收敛 为止。 相似度通过距离进行计算，常用的距离算法 有Minkoski距离、Euclid距离、Chebyshev距离、 Mahalanoi8距离等，在此以欧式距离作为距离计 算公式如下(1．2) E=∑∑0p哪0z (1．1) ‘=I‘=1 厂i——————一 D(％耳)=＼／∑』ⅥIIz (1．2) T r=】 P为数据对象(样本点)，盹为岛类的均值 收稿日期：2007一10埘 作者简介：吴艳文(1967一)，男．安徽巢湖人。合肥工业大学硕士研究生，研究方向：人工智能与数据挖掘。 21 万方数据 D“，劫为点置和耳的距离，m为数据对象的 维数 k—means算法步骤如下：嗍 (1)从n个数据对象任意选择k个对象作为 初始聚类中心： (2)循环下述流程(3)蓟(4)，直到每个聚类不再 发生变化为止； (3)根据每个聚类对象的均值，计算每个对 象与这此中心的距离，并根据最小距离重新对相 应对象进行划分； (4)重新计算每个(有变化)聚类的均值。 2目前k优化方案 最佳聚类个数如何确定．很多文献提出了评 价函数．通过函数极值以确定聚类个数在局部或 整体最优。 (1)BezdekJC基于样本隶属度提出划分概念日 F(U；c)=上∑∑u≯，具有直观的几何解释和 ，‘●=lJ=1。 良好数学性质。最优聚类数通过满足minf只u； c)l获得。 (2)K—me∞s算法中，将两个类之间距离以 相应类的半径(标准方差)归一化并用各类权值 进行加权平均，所得数据表示类分离系数。 (3)通过轮廓系数来测量不同类的分离度。日 类中某点i与该类中其它点的平均距离为d(i)； 该点与最近邻类各点平均距离为6(i)，则f点轮 廓系数为(b(i)一a(i))，m“{a(i)山(i))。此值越接 近l则聚类越好。所有样本点轮廓系数均值反映 类之间分离度，聚类数通过对分离度优化来实现。 (4)[7】【13】等通过类问和类际相对距离来作 为评价函数，文献㈣中定义I，—A卢胁m僻p血抛r fj}肺2，俺m吐其中≈m∞是可聚类的最大数目。 其中 I 、÷乞0口(地)0 1咖(‘)2土诂酾厂(2r1) ；m。蜘车圭c圭 ％”‘“‘ D恤=Ⅱt础ll研一虬|l 2l也=m抚iIq一坼8 11巩一q0 2)_1(2．2) (2．3) (2．4) 以上方案均通过分离度函数或评价函数优 化来实现。但由于面临聚类的情况复杂，可能各 聚类在空间的位置不同、可能各类的样本点数大 小不同、可能各类的空间大小不同、可能各类的 样本点密度不同等众多因素，所以单一通过一函 数来解决多种聚类状况实属NP问。这些方案 大多在解决各聚类样本数相差甚远时．效果较 差。 3一种k值优化方案 3．1基本概念 ^一，w一是通过判断样本点到各聚类中心 的距离大小进行分配的，设数据对象合理聚类个 数为k，当设置的聚类个数超过k时，采用^一 一ms算法后，本应是一个的聚类就会被分成若 干个小的聚类，但这些小的聚类其边界距离即间 隙距离相对较近。通过判断边界距离来确定二个 小的聚类是否应是同一个聚类。 定义1称两聚类c．和c：中心点之间的距离 为两聚类中心距离，记cd(c。，c：)。 定义2称一聚类c。所有数据对象到另一聚 类c：中心距离的最小值为一类到另一类中心的 最近距离，记，以(c。砌)。 定义3称两聚类c，c2在中心连线上两边界 之间的距离为两聚类间隙距离，记intval(c。，c2) 容易看出这三个距离满足如下关系 intvaI(cl，c2)md0I，c2)+md(c2，c1)—cd(cl’c2) (3．1) 定义4称类中各样本点平均相邻距离为类 中各样本点平均相邻距离，记aver。 3，2算法实现 本节中详细介绍该k值优化算法。算法实现。 (1)输入k初值和数据集dat8： (2)运行k—means算法得k个聚类； (3)计算md、cd、intval； (4)判断两两聚类是否应是同一类； (5)输出优化的聚类数。 3．2．1寻找初值％一 ^初值取大于^。的任意值，显然，如果k值 太大．会对以后t值优化带来时间上的代价。如 果k初值不易找到．可以取聚类个数上限作为 ^。值。对一个样本点数为n的数据对象可能有 的聚类个数上隈．很多研究者使用经验规则为： L、厂ij或L2hnJ下取整。虽然此结论无明显的 理论指导，但很多专家已在使用。也有间接傍证 文献㈣和实例应用。 万方数据 3．2．2类中各样本．董平均相邻距离aver 对于研究领域．如果各类样本密度均匀．可 以求其中一个类的各样本点平均相邻距离．此距 离适用于每个类。一个类中各样本点平均相邻距 离可以通过以下两种方法求得。 (1)如果类的样本数样本空间足够大．可以 认为该类的样本点均匀分布在类中．通过求得该 类各维上的距离求出超体积．再求出每个样本应 占有的超体积。。 (2)如果类的样本数不够大．可以通过最小 生成树方法．每个边的权重为两样本之间距离。 求得整个最小生成树边和．进而得”er。 3．2．3t值优化算法 输入初值^初值、数据集，运行k—means算 法．得々个聚类 for(i=0；i分析

定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析