（概率论与数理统计专业论文）传统聚类方法的分析及改进.pdf

摘要 聚类问题一直是数据挖掘领域的一个重要研究方向。本文首先介绍 了聚类问题的广泛应用。随后，在聚类方法分类的基础上，重点介绍了 层次聚类方法和划分聚类法一k 一平均方法，k 一中心方法以及它们的改进 方法。综合分析和比较了层次聚类方法和k 一平均方法的优点和缺点。 在聚类分析中，k 一均值算法可以说是应用较为广泛的一种算法，虽 然传统的k 一均值聚类算法方法简单、执行速度快且效率高，但同时它的 一个致命弱点是它对初始值敏感而且容易陷入局部最小值。而且算法需 要人为地预先指定类别的个数，而实际中类别的个数不能简单明确的确 定。 本文的主要工作可以概括为两个方面。 1 本文提出了一种比上述两种聚类方法更有效的聚类方法。改进算 法由层次凝聚算法得到的初始分区，这就避免了出现随机地选取k 个初 始分区的现象。在某种程度上，大大降低了准则函数收敛为一个局部最 小值的可能性。 2 本文分析经典的k 一均值算法的一个重要缺点：需要用户事先给出 要生成的分类数目，提出了一种寻找最优k 值的方法。引入了一个简单 函数来描述聚类质量，通过遍历所以可能取到的k 值即可确定最优的聚 类个数。 关键字层次聚类方法，划分法，k 一均值聚类方法，最优聚类数目 a bs t r a c t t h ec l u s t e r i n gh a sa l w a y sb e e na ni m p o r t a n tr e s e a r c ha r e ai nd a t a m i n i n g a t f i r s t ，t h i s p a p e r i n t r o d u c e s c l u s t e r i n g s e x t e n s i v e a p p l i c a t i o n s t h e n ，o nt h eb a s eo fc l a s s i f yi nc l u s t e r i n gm e t h o d s ，t h i sp a p e r e m p h a s i z e sh i e r a r c h i c a lc l u s t e r i n gm e t h o d ，t r a d i t i o n a lp a r t i t i o n i n gc l u s t e r i n g k - m e a n sa l g o r i t h m ，k c e n t e r a l g o r i t h ma n d t h e i rm u t a t i o n s t h e a d v a n t a g e sa n dd i s a d v a n t a g e so ft h ea b o v et w om e n t i o n e da l g o r i t h m sw e r e s y n t h e t i c a l l ya n a l y z e da n dc o m p a r e d k m e a n sa l g o r i t h mi st h em o s tw i d e s p r e a dm e t h o di nc l u s t e ra n a l y s i s ， w h i c hi s s i m p l e ，f a s ta n de f f e c t i v e b u t a tt h es a m et i m ei t sv i t a l s h o r t c o m i n gi st h es e n s i b i l i t yt oi n i t i a lv a l u e ；i ti se a s yt or u ni n t oal o c a l o p t i m u m a l s ot h en u m b e ro f t h ec l u s t e r sn e e d st ob es p e c i f i e di na d v a n c e ， a n di tc a n n o tb ec l e a r l ya n de a s i l yc o n f i r m e di nf a c t m a i nw o r k si nt h ep a p e rc a nb es u m m e du pi nt w oa s p e c t s 1 a ni m p r o v e da l g o r i t h m ，w h i c hn o to n l yw a sm o r ee f f e c t i v e ，b u ta l s o h a da ni d e a lr e s u l t ，w a sp r o p o s e di nt h i sp a p e r a tf i r s t ，i tg e ti n i t i a lc e n t e r s f r o mh i e r a r c h i c a lc l u s t e ra n a l y s i s ，w h i c ha v o i dar a n d o ms e l e c t i o no fk i n i t i a lc e n t e r s t oac e r t a i ne x t e n t ，t h ep o s s i b i l i t yo fr u n n i n gi n t oal o c a l m i n i m u mh a sb e e ng r e a t l yr e d u c e d 2 a l s o ，t h i sp a p e rd e s i g n san e wa l g o r i t h mt ol o o kf o ro p t i m u mkv a l u e s i n c et h ec l a s s i c a lk m e a n sa l g o r i t h mh a sa n o t h e ri m p o r t a n ts h o r t c o m i n g t h a tt h en u m b e ro ft h ec l u s t e r sn e e d st ob es p e c if i e di na d v a n c e t h e i n t r o d u c t i o no fas i m p l ef u n c t i o nt od e s c r i b ec l u s t e r i n gq u a l i t yc a ni d e n t i f y o p t i m a ln u m b e r k e yw o r d sh i e r a r c h i c a lc l u s t e ra n a l y s i s ，p a r t i t i o n i n gc l u s t e ra n a l y s i s ， k - m e a n sm e t h o d s ，o p t i m u mn u m b e ro fc l u s t e r s u 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果尽我所知，除了论文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得中南大学或其他单位的学位或证书而使用过的材料与我共同工作的 同志对本研究所作的贡献均已在在论文中作了明确的说明 作者签名：呈薹 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的 全部或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校 可根据国家或湖南省有关部门规定送交学位论文 作者签名：至茎导师签名日期：1 年! 月翔 硕士学位论文绪论 1 1 聚类的应用 第一章绪论 聚类是一种重要的数据分析技术，它将一个对象的集合分成不同的类，从而 描述数据。聚类分析作为统计学的一个分支，己经被广泛研究了许多年。而且， 聚类分析也已经广泛地应用到诸多领域中，包括模式识别、数据分析、图像处理 以及市场研究u 1 。通过聚类，人们能够识别密集的和稀疏的区域，从而发现全局 的分布模式，以及数据属性之间的有趣的相互关系。在商务上，聚类能帮助市场 分析人员从客户基本信息库中发现不同的客户群，并且用购买模式来刻画不同的 客户群的特征。在生物学上，聚类能用于推导植物和动物的分类，对基因进行分 类，获得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定， 汽车保险单持有者的分组，及根据房屋的类型、价值和地理位置对一个城市中房 屋的分组上也可以发挥作用脚。 聚类分析可以作为其他算法的预处理步骤，利用聚类进行数据预处理，可以 获得数据的基本概况，在此基础上进行特征抽取或分类可以提高精确度和挖掘效 率，也可以将聚类结果用于进一步关联分析，以进步获得有用的信息。 聚类分析也可以作为一个独立的工具来获得数据的分布情况。例如，在商业 上，聚类分析可以帮助市场分析人员从客户基本库中发现不同的客户群，并且用 购买模式来刻画不同客户群的特征。通过观察聚类得到的每个类的特点，可以集 中对特定的某些类做进一步分析。这在诸如市场细分、目标顾客定位、业绩评估、 生物种群划分等方面具有广阔的应用前景。 聚类分析可以完成孤立点的挖掘。许多数据挖掘算法试图使孤立点影响最小 化，或者排除它们。然而孤立点本身可能是非常有用的。如在欺诈探测中，孤立 点可能预示着欺诈行为的存在口1 。因此聚类分析己经成为数据挖掘领域中一个非 常活跃的研究课题。 1 2 聚类问题的研究历史 人们对聚类问题的研究已有相当长的历史h 1 。传统的统计方法主要基于统计 学和模式识别。早在多年前，聚类分析就成为统计学的一个分支，主要的研究方 硕+ 学位论文绪论 法是基于距离的聚类。在模式识别中，聚类分析常被称作非监督的学习或者聚类， 它不仅考虑对象间的距离，还要求同类的对象具有某种共同内涵。从这个意义上 看，聚类分析可以这样定义：将一组数据分组，使其具有最大的组内相似性和最 小的组间相似性，也就是说，最后的结果要达到不同的聚类中的数据尽可能的不 同，而同一组聚类中的数据尽可能的相似。 今天，聚类分析也是数据挖掘和知识发现领域中的重要课题，迄今为止，人 们已经提出了许多数据聚类的算法，试图解决各种领域的聚类问题。 1 3 现存聚类方法存在的主要问题 尽管聚类问题的研究已有相当长的历史，但是绝大多数聚类方法是在最近十 年内提出的。随着各种聚类算法的提出，每种新算法都声称至少比以前的一种算 法优越，这使得各种聚类算法之间的比较越来越困难。但是就聚类分析而言，没 有单一的最好方法。不同的聚类方法将产生不同的结果，而且某些方法不能发现 明显的聚类。所以总结数据挖掘对聚类分析方法的典型要求和现存各种聚类方法 存在的问题就变得非常必要。当前实际应用对聚类算法的典型要求包括以下几个 方面晦7 1 。 1 可伸缩性 可伸缩性是指聚类算法不论对小数据集还是对于大数据集都应是有效的。许 多聚类算法在较小的数据集合上工作很好，但是，一旦在大数据集合样本上进行 聚类可能会导致偏差的结果。一个可伸缩性好的算法应该能在大数据集合样本也 能运行良好。 2 处理不同类型数据的能力 实际应用中可能要求算法既可处理数值型数据，又可处理非数值型数据，既 可以处理离散数据，又可以处理连续的数据。但是现存大部分算法被设计用来处 理数值类型的数据。 3 发现任意形状的聚类 许多聚类算法基于欧几里得距离来作为相似性度量方法，但基于这样的距离 度量的算法趋向于发现具有相近尺度和密度的球状类。但是一个类可能是任意形 状的，如何发现任意形状的类显得非常重要。 4 输入参数对领域知识的弱依赖性 很多聚类算法在聚类分析中要求用户输入用户难以确定的参数，而聚类的结 果对于输入参数十分敏感，要求用户输入参数不仅加重了用户的负担，而且使得 聚类的质量难以控制。 2 硕士学位论文 绪论 5 处理噪声数据的能力 现实世界中的数据都包含了孤立点、空缺、未知数据或错误的数据，一些聚 类算法对于这样的数据相当敏感，有时可能导致低质量的聚类结果。个好的算 法应该具有能处理噪声数据的能力。 6 对于输入记录的顺序不敏感 一些性能较差的聚类算法对于输入数据的顺序是敏感的，当不同的顺序提交 给同一个算法时，可能生成差别很大的聚类结果。 7 高维性 许多聚类算法擅长处理低维数据，一般只涉及二到三维，其实人类对二三维 数据的聚类很容易直观的判断。但是，在高维空间中对数据对象聚类是非常具有 挑战性的。 8 可解释性和可用性 用户希望聚类结果是可解释的、可理解的和可用的，也就是说聚类可能需要 和特定的语义解释和应用相联系。这一点很容易理解，但在很多情况下做不到。 1 4 本文的主要工作 本文主要的研究工作包括以下几个方面的内容。 1 简要阐述了聚类问题的研究历史和应用领域，并且分析了数据挖掘对聚类 算法的典型要求及现存算法的主要不足之处。 2 简要介绍了各种聚类方法，重点分析了常用的层次聚类方法、划分聚类方 法及它们的改进方法。 3 在分析层次聚类方法和划分聚类方法的过程中，找出它们的不足之处， 提出了一种简单的无需编程的处理方法以弥补这两种方法的不足。改进算法由层 次凝聚算法得到的初始分区，这就避免了出现随机地选取k 个初始分区的现象。 在某种程度上，大大降低了准则函数收敛为一个局部最小值的可能性。 4 本文分析经典的k 一均值算法的一个重要缺点：需要用户事先给出要生成 的分类数目，提出了一个简单函数来描述聚类质量，通过遍历所以可能取到的k 值即可确定最优的聚类个数。 硕士学位论文 基础知识 第二章基础知识 聚类分析是研究数据间逻辑上或物理上的相互关系的技术，它通过一定的规 则将数据集划分为在性质上相似的数据点构成的若干个类。聚类分析的结果不仅 可以揭示数据间的内在联系与区别，同时也为进一步的数据分析与知识发现提供 了重要的依据，如数据间的关联规则，分类模式以及数据的变化趋势等。作为统 计学的重要研究内容之一，聚类分析具有坚实的理论基础并形成了系统的方法学 体系。 2 1 聚类概念 聚类的严格数学描述如下刊： 假设被研究的样本集为e ，类c 定义为e 的一个非空子集，即cce 且c g ， 聚类就是满足下列两个条件的类q ，g ，g 的集合，其中 1 guc ：u u e = e 2 gn c ，= 0 ( 对任意的f - ，) 由第一个条件可知，样本集e 中的每个样本必定属于某一个类，由第二个条 件可知，样本集e 中的每个样本最多只属于一个类。 从应用上来说，聚类就是将数据分组成为多个类。在同一个类内对象之间具 有较高的相似度，不同类之间的对象差别较大。聚类所说的类不是事先给定的， 而是根据数据的相似性和距离来划分，聚类的数目和结构都没有事先假定，这也 是聚类分析和判别分析的不同之处。 2 2 变量类型 在实际问题中，遇到的指标存在着多种多样性，有的是定量的( 如长度、重 量等) ，有的是定性的( 如性别、职业等) ，因此将变量类型划分为间隔变量、名 义变量和有序变量陋1 。对不同类型的对象，对象间的相异度有不同的度量方法。 1 间隔变量 4 硕士学位论文基础知识 间隔变量是一种连续的变量。如重量、长度、压力、速度等等。为避免度量 单位选择对聚类结果的影响，数据应当先标准化。 2 名义变量 变量度量时既没有数量表示，也没有次序关系，如某物体有红、黄、白三种 颜色，又如医学化验中的阴性和阳性，市场供求中的“产”和“销”。 3 有序变量 序数型变量度量上没有明确的数量表示，而是划分一些等级，等级之间有次 序关系，如产品分上、中、下三等，此三等有次序关系，但没有数量关系。 2 3 数据的变换方法 设有刀个样品，每个样品测得m 项指标。通常将原始资料阵用，z m 的矩阵 来表示引。 x = ix 1 2 m 乇j艺2 屯。 x lx n 2 吒。 ( 2 - 1 ) 其中而( f = 1 ，n ；j = l ，聊) 为第f 个样品的第歹个指标的观测数据。第f 个 样品置为矩阵工的第f 行所描述，所以任何两个样品五和五之间的相似性，可 以通过矩阵x 的第k 行和第行的相似程度来刻画；任何两个变量以和而之间 的相似性，可以通过第尺列和第列的相似程度来刻画h 1 。 我们所考察的m 个不同变量，一般有不同的量纲，不同的数量级单位，不同 的取值范围，为了使不同的量纲，不同取值范围的数据能够放在一起进行比较， 通常需要对数据进行变换处理。常用的变换方法有以下几种。 1 中心化变换 称变换 葛= 黾- x j ( i = l ，2 ，刀；= l ，2 ，聊)( 2 - 2 ) 为中心化变换。变换后数据的均值为0 ，而协方差阵不便，即协方差阵为 s = s = ( s o ) ，。 ( 2 - 3 ) 其中西5 志荟( 而蟊) ( 而一i ，) 2 者善x o x # 。中心化变换是一种方便地计 算样本协方差阵的变换。 2 标准化变换 称变换 硕士学位论文基础知识 巧= ( 而一毛) 邑o = l ，2 ，力；= ，2 ，所) s j = ( = 1 ，2 ，聊) ( 2 - 4 ) 为标准化变换。变换后的数据，每个变量的样本均值为0 ，标准差为1 ，而 且标准化后的数据 巧) 与变量的量纲无关。 3 极差标准化变换 称变换 弓2 l 而一i j 7 巧( f = 1 ，2 ，l ；歹= 1 ，2 ，聊) ( 2 5 ) q 2 州m ，a x x 一一h m ，i l ”l 吻( = i 2 堋) 为极差标准化变换。变换后的数据，每个变量的样本均值为0 ，标准差为i ， 且k i 一旦一组对象合并时，下一步将在新生成的类上进行。已做的处理不能被撤 消，类之间不能交换对象。如果在某一步没有很好地选择合并的话，将会造 成低质量的聚类结果。 因为合并或分裂的决定需要检查和估算大量的对象或类。需计算大量的距 离，需要花费大量的时间，所以算法不具有很好的可伸缩性。 上述的每种聚类方法都有其缺陷。例如，最短距离法容易受链式结构的影响， 从而导致蔓延较长的类( 如图3 - 6 所示) 。类平均连接方法、最长距离法则 倾向子集中在内部集合上形成同种的紧密类( 通常为球形) 。重心聚类和中 间距离聚类方法有可能导致逆增( 当聚类规模增大时，对象与聚类之间的相 异度反而减小) ，这就使得谱系图难以解释n 9 1 。 1 2 硕士学位论文聚类方法的综合分析 3 2 2 改进的层次聚类方法 图3 - 6 最短距离法链式影响 c l u s t e rn u m b e r o fc a s e 女1 o2 大规模的数据库要求快速、高效的聚类算法，改进层次方法的聚类质量的一 个有希望的方向是将层次聚类和其他聚类技术进行集成，形成多阶段聚类。有代 表性的两个改进的层次聚类方法是b i r c h 算法和c u r e 算法一。 1 b i r c h 算法 b i r c h 算法是一个综合的层次聚类方法，它用聚类特征和聚类特征树来概括 聚类描述。该算法通过聚类特征可以方便的进行中心、半径、直径及类内、类间 距离的运算。介绍b i r c h 算法之前，首先要了解下面两个重要概念。 ( 1 ) 聚类特征( c f ) 聚类特征是一个三元组，它给出子聚类的信息的汇总描述，假设某个子聚类 有n 个对象，则该子聚类的聚类特征定义如下： c f = ( ，l s ，s s )( 3 1 ) 其中是子聚类中点的个数，l s 是个点的线性和，s s 是个点的平方和。 ( 2 ) 聚类特征树( c f 树) c f 树是高度平衡的树，它存储了层次聚类的聚类特征。树中的非叶节点有后 代，它们存储了其后代的c f 的总和，即汇总了关于其后代的聚类信息。一个c f 树有两个参数：分支因子b 和阈值t 。分支因子b 定义了每个非叶节点后代的最大 数目，而阈值参数给出了存储在树的叶子节点中的子聚类的最大直径这两个参 数影响了结果树的大小。 b i r c h 算法的步骤： 1 ) 扫描数据库，建立一个初始存放于内存的聚类特征树，它可以看作数据 的多层压缩，试图保留数据内在的聚类结构。 2 ) 采用某种聚类算法对聚类特征树的叶节点进行聚类。在这个阶段可以执 行任何算法，如典型的划分方法。 b i r c h 方法是一种综合的层次聚类方法，它首先利用树的结构对对象进行层 次划分，然后采用其它聚类算法对聚类结果进行改进。由于它引入了两个概念 硕士学位论文聚类方法的综合分析 ( 聚类特征和聚类特征树) 来概括聚类描述，使得聚类方法在大型数据库中取得较 高的速度和可伸缩性，该算法还可以动态地分析增量聚类。 b i r c h 的计算复杂性是p ( 以1 ，其中力是样本个数它具有对样本数目的线性伸 缩性，而且聚类质量较好。 b i r c h 算法的缺点有：因为c f 树的每个节点由于大小限制只能包含有限数目 的后代节点，所以一个c f 树节点并不总是对应于用户所认为的一个自然聚类。如 果类不是球形的，b i r c h 不能很好地工作，因为它用了半径或直径的概念来控制 聚类的边界。此外它需要提供正确的聚类数和类直径两个参数。 2 c u r e 算法 传统的层次聚类算法虽然很简单，但通常缺乏鲁棒性，也就是说对噪音和孤 立点很敏感，而且一旦一个对象被分配到一个类中，它将不会再被考虑，这意味 着层次算法不能纠正之前可能发生的错误分类。另外，很多聚类方法只擅长处理 球形或相似大小的聚类。c u r e 算法解决了上述问题，选择基于质心和基于代表对 象之间的中间策略，即选择空间中固定数目的点，而不是用单个中心或对象来代 表一个类。该算法首先把每个数据点看成一类，然后再以一个特定的收缩因子向 类中心收缩它们，即合并两个距离最近的点代表点的类。 c u r e 算法是随机取样和划分两种方法的组合，具体步骤如下： 1 ) 从源数据集中抽取一个随机样本。 2 ) 将样本分割划分为p 份，每份大小相等。 3 ) 对每个划分局部地聚类。 4 ) 通过随机取样剔除孤立点，如果一个类增长太慢，就去掉它。 5 ) 对局部的类进行聚类。落在每个新形成的类中的代表点根据用户定义的 一个收缩因子收缩或向类中心移动。这些点代表和捕捉到了类的形状。 6 ) 用相应的类标签来标记数据。 c u r e 算法采用的是合并层次聚类，在最开始的时候，每一个对象就是一个独 立的类，然后从最相似的对象开始进行合并，传统的算法常常采用一个对象来代 表一个类，而c u r e 选择基于质心和基于代表对象方法之间的中间策略，它不同 于单个质心或对象来代表一个类，而是选择数据空间中固定数目的具有代表性的 点。一个类的代表点通过如下方式产生：首先选择类中分散的对象，然后根据一 个特定的分数或收缩因子“收缩 或移动它们。在算法的每一步，有最近距离的 代表点对( 每个点来白于一个不同的类) 的两个类被合并。 为了处理大型数据库，c u r e 算法采用随机取样和划分两种方法组合：一个随 机样本首先被划分，每个划分被部分聚类。采用抽样的方法可以降低数据量，提 高算法的效率在样本大小选择合适的情况下，一般能够得到比较好的聚类结果 1 4 硕士学位论文 聚类方法的综合分析 而引入了分割手段，即将样本分割为几个部分，然后针对各个部分中的对象分别 进行局部聚类，形成子类再针对子类进行聚类，形成新的类。 c u r e 算法的优点是基于多代表点的类间相似性度量既可以降低噪声点对类 合并的影响，因为噪声点不易被选为类的代表点，又可以使相似性度量反映出类 的形状、分布等信息，因此得到的类的质量更好。基于这些优点，c u r e 算法能 够处理非球形的对象分布。具体说来，它是通过两个阶段来消除异常值的影响的， 由于异常值同其它对象的距离更大，所以其所在的类中对象数目的增大就会非常 缓慢，甚至不增长。第一个阶段是将聚类过程中增长非常缓慢的类作为异常值除 去的。第二个阶段是将数目明显少的类作为异常值除去在计算基于代表点的类 间相似度时，只须计算代表点之间的距离，而传统的类间相似度是建立在类内所 有数据点之间的距离的基础上的，因此其计算的时间代价更小。通过合理的选择 机制得到的代表点可以最大程度地反映出类的形状、位置、分布及密度等重要信 息。从知识发现的角度讲，类的多代表点是对类所反映的知识的浓缩。即代表点 既可以描述类本身的信息、又比原有的类占有更少的存储空间。 c u r e 算法的缺点是在类的形状、分布、密度不一致时，c u r e 使用的代表点 选取方法将可能选取不合理的代表点；在小类合并时，计算两个小类的相似度时 仅考虑了这两个小类的代表点之间的最小距离，这种策略使得类的个别代表点可 能较严重的影响类间的相似度。而且这种相似性度量忽略了类本身的部分信息。 这种问题在类的形状更复杂，数据集维数较高的时候体现得更加明显。此外，如 果在运行聚类算法之前对数据集进行了分块，或数据集具有不断增量的特性，要 合并的小类将产生互相重叠的现象，在这种情况下，类的代表点之间的最小距离 将无法度量类之间的真实距离。 3 3 划分聚类法 划分聚类方法是最基本的聚类方法，像k 一均值、k 一模、k 一原型、k 一中心点、 c l a r a 以及c l a r a n s 等都属于划分聚类方法耻删。 3 3 1 传统的划分法 1 划分聚类方法的主要思想 给定一个包含刀个数据对象的数据集，以及要生成的类的数目k ，划分聚类 算法将构造k 个划分，其中每个划分代表一个类，k 玎。对于给定的k ，算法首 先给出一个初始的划分方法，以后通过反复迭代的方法改变划分，使得每一次改 硕十学位论文聚类方法的综合分析 迸后的划分方案比前一次更好( 见图3 2 ) 。所谓好的标准是：类内具有较高的相 似度，而类间的相似度较低。通常会采取一个划分准则函数，以便使同一个类中 的对象是相似的，而不同类中的对象是相异的口1 。 2 k 一均值算法 k 一均值算法，是一种使用最广泛的聚类算法。k 一均值算法以k 为参数，把刀 个对象分为k 个类，使类内具有较高的相似度，而类问的相似度较低。算法首先 随机的选择k 个对象，每个对象初始地代表一个类的平均值或中心。对剩余的每 个对象根据其与各个类中心的距离，将它赋给最近的类。然后重新计算每个类的 平均值。这个过程不断重复，直到准则函数收敛。准则函数如下： 七lj 2 e = 卜i i ( 3 2 ) f = i 艇c i 这里的e 是数据库所有对象的平方误差的总和，工是空间中的点，表示给定 的数据对象，是类e 的平均值。这个准则试图使生成的结果类尽可能的紧凑 和独立。 图3 - 2k 一均值方法的图示 k 一均值算法描述及算法过程 输入：包含刀个数据对象的数据集及要生成类的数目k 。 输出：k 个类，使平方误差准则为最小。 算法过程： ( 1 ) 任意( 或人为) 地选择k 个对象作为初始的类中心； ( 2 ) 根据类中对象的平均值，将每个对象赋给最近的类； ( 3 ) 更新类的平均值，即计算每个类中对象的平均值： ( 4 ) 计算准则函数e ； ( 5 ) 如果e 与上一个循环相比不再发生明显变化，结束；如果e 与上一个循环 相比差别明显，返回到第( 2 ) 步。 具体过程见图3 - 3 。 1 6 硕士学位论文 聚类方法的综合分析 图3 - 3 基于k - m e a n s 方法的一组对象的聚类过程 k 均值算法的优点： 这种方法是相对高效的，它的复杂度是o ( 1 a n ) ，其中，z 是数据对象的 个数，k 是类的数目，t 是迭代的次数，通常，k n ，且t 要求用户必须事先给定要生成的类的数目。 对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。 对噪声和异常数据敏感，少量的该类数据能够对平均值产生极大的影 响。 只有当平均值有意义的情况下才能使用，对于类别字段不适用。 3 k 一均值算法的变体 k 一均值算法有很多变体，这些变体相对于k 一均值算法，主要是在以下几个方 面有所不同：初始k 个平均值的选择、评价准则的计算和计算类的平均值的策略 3 】 5 】 o 1 k 一模算法：为了实现对离散数据的聚类提出t k - 模算法。它用模代替类的 平均值，采用基于频率的方法来修改聚类的模，采用新的评价函数来处理分类对 象。它在保留了k 一均值算法的效率同时将k 一均值算法的应用范围扩大到离散数 据。 2 k 一原型算法：综合k 一均值和k 一模算法，可以对离散和数值两中混合的数据 进行聚类，在k 一原型算法中定义了一个对数值与离散属性都计算的相异性度量标 准。 3 k 一中心点方法：为了解决k 一均值算法对于孤立点敏感的问题，k 一中心点方 法不是将类中对象的平均值作为参照点，而是选用类中位置最靠近中心的对象， 即中心点作为参照点。k 一中心点聚类算法的基本策略是：首先为每个类随机选择 一个代表对象，剩余的对象根据其与代表对象的距离分配一个最近的类。然后反 复地用非代表对象来代替代表对象，以改进聚类的质量。这样的划分方法仍然是 基于最小化准则函数的原则执行的。 1 7 硕士学位论文 聚类方法的综合分析 p a m ( p a r t i t i o n i n ga r o u n dm e d o i d s ) 是最早提出的k 一中心点算法的算法之 一。它试图对拧个对象给出k 个划分。最初随机选择七个中心点，然后反复地用 非中心点对象来替代中心点对象，以改进聚类的质量。 3 3 2 改进的划分法 1 c l a r a 方法b 吲 典型的k 一中心点划分方法，如p a m ，对小的数据集合非常有效，但对大的数 据集合没有良好的可伸缩性。为了处理较大的数据集合，可以采用一个基于选择 的方法c l a r a ( c l u s t e r i n gl a r g ea p p l i c a t i o n s ) 。c l a r a 的主要思想是不考虑整 个数据集合，选择实际数据的一小部分作为数据的样本。然后用p a m 方法从样本 中选择中心点。 c l a r a 方法优点是能够处理大数据集。 c l a r a 方法缺点是效率依赖于采样的大小，如果样本发生偏斜，基于样本的 一个好的聚类不一定能代表整个数据集合的一个好的聚类。 2 c l a r a n s 方法 为了改进c l a r a 聚类质量和可伸缩性，c l a r a n s 算法将采样技术和p a m 结合起 来。与c l a r a 不同在于：c l a r a 在搜索的每个阶段有一个固定的样本，而c l a r a n s 在搜索的每一步带一定随机性地抽取一个样本。c l a r a n s 聚类过程可以被描述为 对一个图的搜索，图中的每个节点是一个潜在的解，即k 个中心点的集合。在替 换了一个中心点后得到的聚类结果被称为当前结果的邻居。随机尝试的邻居的数 目被用户定义的一个参数加以限制。如果一个更好的邻居被发现，也就是说它有 更小的误差值，c l a r a n s 移到该邻居点，处理过程重新开始。否则当前的聚类达 到了一个局部最优。如果找到了一个局部最优，c l a r a n s 随机选择的节点开始寻 找新的局部最优。 c l a r a n s 方法优点是比p a m 和c l a r a 更有效和有更好的伸缩性。 c l a r a n s 方法缺点是计算复杂，复杂度大约是o ( n 2 ) 。 划分法及其变形方法的性质总结于表3 一l 。 表3 - 1划分法及其变种方法的性质 算法名称算法复杂度 需要的参数 k - m e a n s d ( 砌) 聚类数k p a m o ( k ( n - k ) 2 ) 聚类数k c l a i r a o ( k s 2 + 七( ，z 一七) ) 聚类数k c l a r a n s o ( n 2 ) 聚类数七、最大邻居数、局部最小值 硕十学位论文 聚类方法的综合分析 3 4 小结 本章主要介绍了基于距离的层次聚类方法和划分聚类方法及其改进算法。 传统的层次聚类方法的缺点是已做的合并或分裂不能撤销，类之间不能交换 对象，如果某一步没有选择好合并或分裂点，可能会降低聚类的质量。而且，层 次聚类方法不具有很好的可伸缩性，因为合并或分裂的决定需要检查和估算大量 的对象或类。接着介绍了两种改进的层次聚类方法b i r t h 算法和c u r e 算法。b i r t h 算法用聚类特征和聚类特征树来概括聚类描述，通过一次扫描就可以进行较好的 聚类，在大型数据库中取得了较高的速度。c u r e 对孤立点的处理更加健壮，而且 能够识别非球型的类。 划分聚类方法通过准则函数把数据集分割成k 个部分，本章主要介绍了k 一均 值算法，它处理大数据集方面非常有效，特别是对于数值性数据。p a m 是最早提 出k 一中心点算法的算法之一，它消除了k 一均值算法对于孤立点的敏感性。p a m 算 法对小数据集非常有效，但对于大数据集合没有良好的可伸缩性。c l a r a 能处理 更大的数据集合。c l a s n s 采用随机搜索对c l a r a 算法的聚类质量和伸缩性进行了 改进。 1 9 硕士学位论文聚类分析的几个问题的解决办法 第四章聚类分析的几个问题的解决办法 随着各种聚类算法的提出，每种新算法都声称至少比以前的一种算法优越， 这使得各种聚类算法之间的比较越来越困难。实际上，任何算法都不能够证明自 己比其他所有的算法在各方面都优越。而且，许多算法是为特定的领域设计的， 虽然对某类特殊数据的性能较好，但对其他类型的数据则不具有优势。另外，不 同的用户对好的算法的要求不同，评价最优的标准也名目繁多，适用于各种情况 的算法似乎是不存在的。即使对每一个特定的数据集，也很难选择一个最适合的 聚类算法进行分析。了解各种聚类算法的性质、缺点有助于决策者根据实际情况 选择恰当的聚类方法。 上一章中介绍的传统方法的改进方法由于其使用不广，还没有收录到几大统 计软件中。我们需要精通- - i 计算机语言才能设计出成熟的改进方法，网上流传 着这些方法的源代码，我们要么不能轻易得到，要么不具有权威性。s p s s 或s a s 软件已实现的算法是层次聚类算法和k 一均值算法，但是由上章知这两种方法各有 其缺点，下面我们将这两种方法结合在一起以消除它们的缺点。新算法只需要对 这两种统计软件有初步学习就能对大量数据进行聚类。 4 1 改进算法介绍 4 1 1 改进算法的思想 层次聚类方法的主要缺点是已做的处理不能被撤消，类之间不能交换对象。 如果在某一步没有很好地选择合并的话，将会造成低质量聚类结果，而且层次聚 类方法时间和空间复杂度大。k 一均值算法的致命缺点是对初值敏感，对于不同的 初始值，可能会导致不同的聚类结果。改进的算法是将两种方法结合起来。 改进算法的基本思想分两个步骤完成： 1 ) 应用层次聚类方法进行聚类得到初始类( 如数据超过1 0 0 个，则从中抽样 1 0 0 个数据进行层次聚类) ； 2 ) 对从层次聚类方法中得到的初始类作为初值，运行k 一均值算法进行求精。 4 1 2 改进算法与原算法的实例对比 下面是世界4 3 个国家和地区的人均食物成分图( 见2 0 0 5 年国际统计年鉴) ， 硕士学位论文 聚类分析的几个问题的解决办法 对这些国家和地区进行聚成3 类。首先任选3 个聚类中心，得到聚类结果见表4 2 表4 - 3 。聚类结果可以在图4 一l 直观的表示出来。 表4 - 1 世界4 3 个国家和地区的人均食物成分图 淀粉蛋向质脂肪淀粉蛋白质 脂肪淀粉蛋白质脂肪 2 9 5 18 1 - 59 0 32 4 6 7 35 75 1 13 6 5 3 91 1 9 21 7 0 8 2 2 0 54 8 12 3 53 3 5 79 5 49 1 63 4 9 5 61 0 0 11 4 6 4 2 4 5 95 7 34 9 62 5 6 6 26 2 34 5 53 6 7 0 ，61 1 3 11 5 8 1 2 9 0 3 96 4 25 9 43 3 3 89 5 45 9 83 3 6 2 3 1 0 7 51 4 4 3 3 0 8 4 98 3 45 7 22 7 2 5 56 1 16 2 3 3 7 4 5 9 9 41 1 2 ，8 3 6 6 6 11 2 8 61 3 92 9 5 6 17 6 2 7 7 53 4 5 4 61 0 7 49 6 1 2 7 6 0 99 1 88 4 63 5 8 9 3 1 0 51 4 6 23 0 7 1 89 1 48 3 2 6 7 6 68 4 ，77 63 1 4 4 79 0 88 7 5 3 3 7 0 61 l l - 71 5 0 ，9 3 0 5 88 9 67 7 1 3 7 7 4 11 1 41 5 6 53 0 5 3 68 4 18 1 7 2 8 8 1 17 6 38 1 82 9 9 2 1 9 61 0 6 13 4 1 2 21 0 2 41 3 8 9 2 2 4 9 17 9 8 7 53 0 4 9 58 2 。89 3 73 0 5 3 61 0 3 51 3 1 2 2 9 3 7 17 9 94 8 3 2 3 3 6 36 3 86 3 63 2 1 9 29 9 91 1 5 3 2 4 1 8 86 1 96 5 1 3 0 0 0 38 6 19 7 81 0 0 0 ，01 9 9 01 9 9 0 2 3 7 9 35 6 1 4 8 4 2 8 4 7 ，98 8 49 6 2 3 8 5 35 4 94 3 93 1 7 1 39 4 11 1 8 表4 2 任选初始值得到的最终聚类中心 初始聚类中心 最终聚类中心 1 23i23 淀粉3 0 5 43 0 5 02 4 5 93 4 4 12 7 4 91 0 0 0 蛋白质 1 0 3 58 2 8 5 7 31 0 5 37 5 42 0 0 0 脂肪 1 3 1 29 3 74 9 61 2 7 07 2 4 2 0 0 0 表4 - 3 任选初始聚类中心时每类样本个数 c l u s t e r1 1 3 0 0 0 22 0 0 0 0 31 0 0 0 0 然后我们用层次聚类法聚类得到3 个聚类中心( 见表4 - 4 ) ，得到聚类结果 见表4 4 和表4 5 。此时的聚类结果可以在图4 - 2 中直观的表示出来。由图4 - 1 和4 2 很明显看出任选初始聚类中心得到了局部最优解，而改进后的方法得到了 正确的分类。 2 1 硕士学位论文 聚类分析的几个问题的解决办法 图4 - 1 任选聚类中心得到的聚类图 表4 - 4 改进算法得到的聚类结果1 初始聚类中心最终聚类中心 123123 淀粉 l o o o 02 2 0 53 7 7 4 3 4 4 12 7 4 91 0 0 0 蛋白质 1 9 9 04 8 11 1 4 o1 0 5 37 5 42 0 0 0 脂肪1 9 9 02 3 51 5 6 51 2 7 07 2 42 0 0 ，0 表4 5 用改进算法得到的聚类结果2 c l u s t e rl1 6 0 0 0 22 6 0 0 0 31 0 0 0 图4 - 2 改进算法得到的聚类图 硕十学位论文 聚类分析的几个问题的解决办法 4 1 3 改进算法与层次聚类算法和k 一均值算法的性能比较 层次聚类算法在小数据集上工作很好，一旦在大数据集合样本上进行聚类可 能需要相当多的时间，它的可伸缩性较差。而且已做的处理不能被撤消，类之间 不能交换对象。如果在某一步没有很好地选择合并的话，将会造成低质量聚类结 果。k 平均分区算法对初始分区选择相当敏感，如果初始分区选择不好，将完全 有可能成为一个局部最小准则函数，降低聚类质量。 改进的方法从大量数据中抽取1 0 0 个( 如果数据数量大于1 0 0 ) ，得到初始聚 类中心。这就克服了层次聚类算法伸缩性较差的缺陷。改进算法由改进的层次凝 聚算法得到的初始分区，这就避免了出现随机地选取k 个初始分区的现象。在某 种程度上，大大降低了出现收敛为一个局部最小准则函数的可能性。 改进的算法由于先运行层次聚类算法，再应用k 平均分区算法对已生成的初 始类进行求精。若发现某个数据点分配得不合理、则允许类之间重新分配数据点。 这在一定程度上，提高了聚类的质量。 4 2 类个数的确定 聚类分析中，类的个数如何确定是一个十分困难的问题，人们至今仍未找到 另人满意的方法，但这又是一个不可回避的问题。 k 一均值聚类方法是最常用的聚类方法，它以平方误差准则较好地实现了聚 类。但是k 一均值聚类方法及其变种方法有一个致命的缺点：需要用户事先给出 要生成的分类数目k 。但大多数情况下，聚类数目k 事先无法确定，用户无法知 道采用什么样的k 值对自己更有利，这在一定程度上影响和限制了其应用合理 性。因此，确定的k 虽然对算法本身更方便、高效，但对一些实际问题并不有效。 下面给出一种确定最优聚类数目吃。的方法。 4 2 1 算法提出 由准则函数e 难以直接找到最佳聚类数，多数学者认为为丸p ts i 蚋。 并且这个结论已经被证明呻1 。下面我们勾画出一个描写聚类质量的函数。一个好 的聚类应该使不同聚类中心的间距尽可能地大，而样本与其所属类中心间距尽可 能地小，所以我们构造函数s 。 硕士学位论文 聚类分析的几个问题的解决办法 s ( 七) = 圭i = lx e c , i b112 卜i l 小m 舢l n 弦弓 2 ( 4 1 ) 其中i 和是第j 类和第类的中心。s 的分子是所有类样本与其中心间距 的平方和，而分母是两不同类中心间距平方的最小值，所以s 越小，说明聚类结 果越好。 4 2 2 算法