（计算机应用技术专业论文）一种新的分层聚类算法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 数据挖掘是近年研究比较热门的信息技术之一，该技术广泛应用于各个 行业。聚类分析是数据挖掘的个重要部分。聚类算法都需要面对输入参 数的问题：k - m e a n s 等划分方法需要输入聚类的数量；d b s c a n 等密度算法 需要输入密度阀值参数。这些参数大多不容易获取。 为解决参数问题，本文提出了一种新的分层聚类算法，该算法的思想是： 首先利用单位距离对数据对象聚类，以产生数量比较多的原子聚类，再利用 比较容易获取的参数对这个聚类结果优化，以取得最终的聚类效果。本文还 分析了用代表点描述聚类的几种方法，提出了用边界代表点描述聚类的算法， 该算法可用于大量数据的聚类。 本文的工作如下：。 ( 1 ) 提出单位距离的概念：对于空间的数据对象，在均匀分布的情况下， 用对象之间的最短距离来聚类，聚类的结果是一个类，把这个平均分布情况 下的对缘之间的最短距离称为单位距离。对数据对象用单位距离聚类可以得 到初始的低层的聚类( 原子聚类) 。 ( 2 ) 提出孤立点优化的思想：聚类结果中的孤立点可以认为是数据对象 中的非正常数据，现实世界中，对于每一类数据对象，假设非正常数据出现 的概率是致的，则可以根据数据量和非正常数据出现的概率来估算聚类结 果中孤立点的数量，并利用该参数对聚类结果优化。 ( 3 ) 结合单位距离和孤立点优化的思想提出基于单位距离的聚类算法， 并对算法的实现步骤作了详细分析，并且用实验来比较该算法与 c h a m e l o n 算法聚类的结果。 ( 4 ) 给出把普通算法得到的聚类结果转化到边界代表点的方法并用实例 说明该算法特点：用比较少的代表点教准确代表任意复杂图形的聚类，为大 量数据的聚类提供了_ 个可行的解决方法。 关键字：聚类分析；单位距离；孤立点分析；多代表点；边界代表点 西南交通大学硕士研究生学位论文第i i 页 d a t am i n i n gi sac u r r e n t l yd e v e l o p e dt e c h n o l o g yw h i c ha t l r a c t sl o t so f r e s e a r c h e r s c l u s t e r i n gi sa l li m p o r m tp a r to fd a t am i n i n g m o s ta l g o r i t h m so f c l u s t e r i n gh a v et od e a lw i t ht h ep a r a m e t e r s ：k - m n sa l g o r i t h md e m a n d su s e rt o i n p u tt h ec l u s t e r i n gn u m b e r d b s c a na n do t h e rd e 卿a l g o r i t h m sn e e du s e rt o p r o v i d et h ed e n s i t yp a r a m e t e r h o w e v e rm o s to ft h ep a r a m e t e r sa r eh a r dt ob e a c q u i r e d 砀et h e s i sp r e s e n t san e wl a y e r e dc l u s t e r i n ga l g o r i t h mt od e a lw i t ht h i s p r o b l e m t b em a i ni d e ai s ：f i r s t l y , c l u s t e rt h ed a t aw i t hu n i td i s t a n c e , i tw i l l g e n e r a t em a n ya t o mc l u s t e r s t h e nd u s t e rt h ea t o mc l u s t e r sw i t ho u t l i e rp o i n t s n u m b e rw h i c hm a yb ea c q u i r e de a s i l y a f t e rt h e 缸岍so fc l u s t e rd e s c r i b i n gw i t h r e p r e s e n t s , t h et h e s i ss i v e san e wc l u s t e rd e s c r i b i n ga l g o r i f l m a s ：b o r d e rr e p r e s e n t s a l g o r i t h mw h i c hc a nb eu s e di nc l u s t e r i n gl a r g ed a t a s e t r 1 1 1 em a i nw o r ko f t h et h e s i si n c l u d e s ： ( 1 ) n 坞t h e s i sp r e s e n t st h ec o n c e p to f u n i td i s t a n c e ：i nt h ed a t as p a c e , i f t h e d a t a 蛳e c t si se q u a b l yd i s t r i b u t i n g , c l u s t e rt h e mw i t ht h es h o r t e s td i s t a n c eo f 删e c t s , t h e r ew i ub co n l yo n ec l u s t e r ，1 1 舱s h o r t e s td i s t a t l c ei sc a l l e du n i td i s t a n c e c l u s t e r i n gd a t aw i t hu n i td i s t a n c e , w ew i l lg e tt h ea t o mc l u s t e r s ( 2 ) ，1 1 硷t h e s i sp r e s e n t st h ei d e ao f o u t l i e rp o i n to p t i m i z i n g ：o u t l i e rp o i n t so f c l u s t e r i n g 扣弓d e e m e dt ob es p e c i a ld a t a w ea s s u m et l m , t h ep r o b a b i l i t yo fs p e c i a l d a t ai s 五x e d t h u st h eo u t l i e rp o i n t so fd a t ac a nb ee s t i m a t e db yt h ed a t as i z ea n d s p e c i a ld a t a sp r o b a b i l i t y g e n e r a l l yt h i sp a r a m e t e ri s e a s i e rt ob ea c q u i r e dt h a n o t h e rp m a m e t e r s 抡o u t l i e rp o i n t se x p e c t a t i o nc a nb eu s e dt oo p t i m i z et h ea t o m c l u s t e r s ( 3 ) i n t e r g r a f i n gt h ei d e a so f u n i td i s t a n c ea n do u t l i e rp o i n to p 。t m a i m 舀t h e t h e s i sp r e s e n t st h eu d b a ( u n i td i s t ；啪c eb a s e da l g o r i t h m ) t h et h e i sl i s t st h e d e t a i ls t e p so ft h eu d b aa l g o r i t h m , a n di ta n a l y s e sa n dc o m p a r e st h ec l u s t e r i n g r e s u l to f u d b a a l g o r i t h mw i t hc h a m e l o na l g o r i t h m ( 4 ) mt h e s i s 胛啪at r a n s l a t i o nm e t h o dw h i c h 锄t r a n s l a t ec l u s t e r so f u a d i f i o n a la l g o r i t h mi n t ob o r d e rr c p r e s e n t a t i n e s ，1 1 1 ee x p e r i m e n te x p l a i n st h e c h a r a c t e r i s t i co f b o r d e rr e p r e s e n t a t i n e s ：e a t r r e p r e s e n tac o m p l e xc l u s t e rs h a p ew i t h af e wr e p r e s e n t a t i n e s - 1 1 1 i sa l g o r i t h mm a yh e l pi tt od e a l 讹t h ec l u s t e r i n go f 西南交通大学硕士研究生学位论文 第i 页 l a r g ed a t as e t s k e yw o r d s ：c l u s t e r i n ga n a l y s i s , u n i td i s t a n c e , o u t l i e rp o i n ta n a l y s i s ， 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密d 使用本授权书。 ( 请在以上方框内打“ ) 学位论文作者签名：l 虱幻失 日期：加暑6 ，2 0 指导老 日期： 西南交通大学学位论文创新性声明 i本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作 所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 提出了基于单位距离的分层聚类算法，该算法利用单位距离完成分层聚 类的低层聚类，在孤立点数量可以估计的情况下，文章提出孤立点优化算法 来完成高层的聚类。文章分析了聚类的描述问题，提出了边界代表点的概念， 并提出了把普通聚类转化为边界代表点的转化算法。所有算法都进行了试验 对比。 西南交通大学硕士研究生学位论文第l 页 1 1 数据挖掘概述 第1 章绪论 近年来，计算机技术和信息技术的高速发展给人类社会带来了巨大的变 化，数据成为最重要的战略资源。由于技术的进步，人们能以更快速、更容 易、更廉价的方式获取和储存数据，数据库应用的规模、范围和深度不断扩 大，大量的数据库被用于商业管理、政府办公、科学研究和工程开发等，并 且这一势头仍将持续发展下去，使得数据及其信息量以指数形式增长 。由 于海量数据的复杂性和数据处理的时效性妨碍了人们对数据的使用，人们陷 入了缴据丰富，但知识缺乏”的困境。如何才能不被信息的汪洋大海所淹没， 提高信息利用率呢? 面对这一严峻挑战，数据挖掘( d a t am i n i n g ) 技术应运 而生，并得以蓬勃发展，越来越显示出其强大的生命力 2 1 1 3 1 。 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中， 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过 程。还有很多和这一术语相近似的术语，如从数据库中发现知识( k d d ) 、数 据分析( d a t aa n a l y s i s ) 、数据融合( d a t af u s i o n ) 以及决策支持( d e c i s i o n s u p p o r t i n g ) 等。原始数据可以是结构化的，如关系数据库中的数据，也可以 是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构数据。 发现知识的方法可以是数学的，也可以是非数学的：可以是演绎的，也可以 是归纳的。发现的知识可以被用于信息管理、查询优化、决策支持、过程控 制等，还可以用于数据自身的维护。因此，数据挖掘是一门很广义的交叉学 科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可 视化、并行计算等方面的学者和工程技术人员。 从数据仓库观点来看，数据挖掘可以看作联机分析处理( o l a p ) 的高 级阶段。然而，通过结合更高级的数据理解技术，数据挖掘比数据仓库的汇 总型分析处理走得更远。f 4 j s 西南交通大学硕士研究生学位论文第2 页 1 2 聚类分析研究的方法 聚类分析是数据挖掘中的核心部分，所谓聚类，就是将物理或抽象对象 的集合组成为由类似的对象组成的多个类或簇的过程。由聚类所生成的簇是 一组数据对象的集合，同一簇中的对象尽可能相似，而不同簇中的对象尽可 能相异。聚类与数据挖掘中的分类不同。在分类模块中，目标数据库中存在 哪些类我们是知道的，我们要做的就是将每一条记录分别属于哪一类标记出 来；与此相似但又不同的是，聚类是在预先不知道目标数据库到底有多少类 的情况下，希望将所有的记录组成不同的类或者说“聚类 ( c l u s t e r ) ，并且 使得在这种分类情况下，以某种度量为标准的相似性在同一聚类之间最小化， 而在不同聚类之间最大化。在很多应用中，由聚类分析得到的每一个聚类中 的成员都可以被统一看待。聚类分析的算法可以分为以下几大类：划分法、 层次法、基于密度的方法、基于网格的方法和基于模型的方法等。 在聚类分析研究的方法主要分以下几个方面： 1 划分方法 划分方法的定义给定一个包含厅个对象或数据行，划分方法将数据集划 分为k 个子集。其中每个子集均代表一个聚类( 解邗) 。也就是说将数据分 为k 组，这些组满足以下要求：( a ) 每组至少应包含一个对象：且( b ) 每个 对象必须只能属于某一组。( c ) 每组的数据对象到该组中心的距离比他到其 他组的中心的距离都短。 划分方法的经典算法是：( a ) k - m e a n s 算法，该算法中的每一个聚类均 用相应聚类中对象的均值来表示【2 1 1 ；( b ) k - m e d o i d s 算法，该算法中的每一 个聚类均用相应聚类中离聚类中心最近的对象来表示。k - m e d o i d s 聚类算法比 k - m e a m 聚类算法在处理异常数据和噪声数据方面更为鲁棒；因为与聚类均 值相比，一个聚类中心的代表对象要较少受到异常数据或极端数据的影响。 但是前者的处理时间要比后者更大【2 2 1 。两个算法都需要用户事先指定所需聚 类个数k 。( c ) 基于采样的聚类方法，称为c l a r a ( c l u s t e r i n gl a r g e a p p l i c a t i o n ) ，来有效处理大规模数据 4 7 1 。 2 层次方法 层次方法就是通过分解所给定的数据对象集来创建一个层次。根据层次 分解形成的方式，可以将层次方法分为自下而上和自上而下两种类型。自下 而上的层次方法从每个对象均为个( 单独的) 组开始；逐步将这些( 对象) 西南交通大学硕士研究生学位论文第3 页 组进行合并，直到组合并在层次顶端或满足终止条件为止。自上而下层次方 法从所有均属于一个组开始；每一次循环将其( 组) 分解为更小的组：直到 每个对象构成一组或满足终止条件为止。 多代表聚类( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e s ，c u r e ) 每个类的所有样本 点不再由单个类中心代表，而是由多个散布于类中、能够表现类几何形状的 样本点代表：同时为了消除外围噪声带来的影响，这些散布的样本点向类中 心“收缩”一个比例因子，力求在表现类形状的同时减小噪声的扰动郴1 。 r o c k 也是一个聚合层次聚类算法。与c u r e 算法不同，r o c k 算法适 合处理符号属性四】。 c h a m e l e o n 是一个探索层次聚类中动态模型的聚类算法。在其聚类 过程中，如果两个聚类问的连接度和相似度与聚类内部的连接度和相似度密 切相关，那么就合并这两个聚类。基于动态模型的合并过程将有助于发现自 然和同质的聚类；并在定义了有关相似函数的情况下，适用于任何的数据类 型【2 4 】。 3 密度方法 大多数划分方法是基于对象间距离进行聚类的。这类方法仅能发现圆形 或球状的聚类而在较难发现具有任何形状的聚类。而基于密度概念的聚类方 法实际上就是不断增长所获得的聚类直到“邻近 ( 数据对象或点) 密度超 过一定阈值( 如：一个聚类中的点数，或一个给定半径内必须包含至少的点 数) 为止。这种方法可以用于消除数据中的噪声( 异常数据) ，以及帮助发现 任意形状的聚类。 d b s q 心蹴是一个典型的基于密度方法，该方法根据密度阈值不断增长 聚类。o p t i c s 也是一个基于密度方法，该方法提供聚类增长顺序以便进行自 动或交互式数据分析瞄j 。 4 网格化方法 基于网格方法将对象空间划分为有限数目的单元以形成网格结构。所有 聚类操作均是在这一网格结构上进行的。这种方法主要优点就是处理时间由 于与数据对象个数无关而仅与划分对象空间的网格数相关，从而显得相对较 快。 s t i n g 就是一个典型的基于网格的方法【2 6 1 。c l i q u e 和w a v e c l u s t e r 是两 个基于网格和基于密度的聚类方法。 实验分析表明w a v e l e tc l u s t e r 能处理多达2 0 维的数据刚。文献 4 1 】提出 了小波包模糊聚类网络。该网络能够处理平稳和非平稳信号的不确定性问题， 西南交通大学硕士研究生学位论文第4 页 并且具有自适应及自组织聚类分析功能， 单纯的只用用一种方法对数据进行聚类的模式不再多见。多数新的聚类 算法是综合几种聚类方法而成的。如文献 3 】提出的云概念空间模型。小波变 换方法也是网格方法和密度方法的结合算法。 1 3 本文研究的内容 对于普通的聚类方法，总是需要输入聚类的参数，比如划分方法都需要 输入聚类的数量。但是很多时候聚类的参数不容易获取。然而，很多时候， 聚类的结果中的孤立点的数量是在一定范围内。本文研究内容之是寻找一 种简单的聚类方法对数据聚类，并用聚类结果中的孤立点的数量对聚类结果 进行优化，使之达到满意的聚类结果。该方法不需要输入任何聚类数量等预 值，动态的增加类的数量，聚类效果稳定，运算复杂度低，实现比较容易， 还可以利用孤立点对聚类效果优化，能够完成同c h a m e l e o n 算法相同的 聚类效果。 7 对大量数据的聚类，多代表点的处理方法是可行的策略。用多代表点完整 准确的代表一个聚类有两种方法：区域覆盖代表点方法和边界代表点方法， 区域覆盖代表点用到的代表点太多。边界代表点方法用到的代表点的数量跟 聚类的数量和形状有关，既：聚类数量越多，聚类形状越复杂边界代表点的 数量越多。边界代表点可以准确的用较少的数量的代表点代表一个聚类，可 以处理大量数据的聚类。问题在于：边界代表点方法中的代表点的产生办法? 本文提出通过普通聚类向边界代表点的转换方案解决了这个难题，为大量数 据的聚类提供了一个有效的途径。 本文的具体结构组织如下： 第l 章，绪论：介绍数据挖掘的由来，聚类分析研究的方法，本文的研究 内容。 、 第2 章聚类分析：对现有的典型的聚类研究方法做了说明、分析、比较， 并指出了各自的优缺点。 第3 章单位距离的分层聚类方法：提出分层聚类方法：u d b a 方法( 基 于单位距离的聚类算法) 。对该方法详细描述并实现。 第4 章改进和应用：阐述对u d b a 算法时间复杂度改进的方法及在孤 立点搜索过程中的应用。 西南交通大学硕士研究生学位论文第5 页 第5 章分析了聚类描述方法，提出边界代表点聚类方法 结论和展望：总结本文的研究成果，并对今后的研究方向做了展望。 西南交通大学硕士研究生学位论文第6 页 2 1 引言 第2 章聚类分析 聚类分析作为统计学习的一个分支和一种无指导的机器学习方法已有几 十年的研究历史。近十多年来随数据挖掘的兴起而成为数据分析领域的一个 研究热点。聚类分析在电子商务、图像处理、模式识别、文本学习、数据库 等领域有广泛的应用背景。聚类与分类的根本不同在于：分类问题中我们知 道训练集的分类属性，而聚类问题则需要我们从数据集中找这个分类属性。 所谓聚类，就是对数据集中的数据应用某种方法进行分组，使得每组内部的 数据尽可能相似而不同组之间的数据尽可能不同，从而发现数据集内在的结 构。其中数据集可以是结构数据、半结构数据、非结构化数据、多媒体数据、 有序数据集等，对于不同的数据集要采用不同的方法。 2 2 聚类算法的标准 统计学习中的聚类方法主要是基于距离的聚类分析。如k - m e a n s 方法、 k - m e d o i d s 方法以及其他一些方法已被加入到s a s ，s p s s ，s p l u s 等统计分 析软件中。数据挖掘的聚类一般是针对大数据集而言的，因此在数据挖掘中 聚类方法的比较应该满足以下7 个标准【4 l 】： 1 可伸缩性。算法在满足小数据集的同时能否满足大数据集、高复杂性、 高增量的要求。 2 处理不同类型属性的能力。算法在处理数值类型数据的同时能否处理 其他的数据类型，如二元类型，分类标称型，序数型及混合数据类型。 3 发现任意形状的类。许多基于距离的算法只能发现具有相近尺度的球 状簇。而算法能否发现任意形状的簇很重要，如螺旋型。 4 决定输入参数的领域知识最小化。许多算法要求用户输入一定的参数 ( 如希望产生的簇数) 。聚类结果对输入的参数十分敏感，因此要尽量避免。 5 处理噪声数据的能力。实际数据集都包含孤立点、空缺、未知数据或 西南交通大学硕士研究生学位论文第7 页 错误等。算法能否降低这些噪声数据的影响。 6 对输入数据顺序的敏感性。算法结果能否与顺序无关。 7 处理高维数据的能力。算法在应付低维数据的同时能否处理高维空间 的非常稀疏、高度偏斜的数据。 2 3 层次聚类方法比较 层次方法就是通过分解所给定的数据对象集来创建一个层次。根据层次 分解形成的方式，可以将层次方法分为自下而上和自上而下两种类型。自下 而上的层次方法从每个对象均为一个( 单独的) 组开始；逐步将这些( 对象) 组进行合并，直到组合并在层次顶端或满足终止条件为止。自上而下层次方 法从所有均属于一个组开始；每一次循环将其( 组) 分解为更小的组；直到 每个对象构成一组或满足终止条件为止。 层次方法存在缺陷就是在进行( 组) 分解或合并之后，无法回溯。这一 特点也是有用的，因为在进行分解或合并时无须考虑不同选择所造成的组合 爆炸问题。但这一特点也使得这种方法无法纠正自己的错误决策。 将循环再定位与层次方法结合起来使用常常是有效的，即首先通过利用 自下而上层次方法；然后再利用循环再定位技术对结果进行调整。一些具有 可扩展性的聚类算法，如：b i r c h 和c u r e ，就是基于这种组合方法设计的。 2 3 1b 口r t c h 算法 b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s ) 方法 是一个集成的层次聚类方法。它包含两个重要概念：聚类特征( 简称c f ) 和 聚类特征树( c ft r e e ) 。这两个概念用于对聚类描述进行概要总结。相应的有 关数据结构将帮助聚类方法获得较好的聚类速度和可对大数据库进行处理的 可扩展性。此外：b i r c h 方法在进行增量和动态聚类时也是很有效的。 b i r c h 方法努力在现有资源条件下产生最好的聚类。面对有限的内存， 一个重要考虑就是如何使得i o 时间最小。b i r c h 方法利用多阶段处理方式： 先扫描一遍数据获得一个基本理想的聚类；再次扫描一遍数据以帮助改善( 所 获) 聚类的质量。b i r c h 的计算复杂度为o ( n ) ，其中n 为待聚类的对象数。 有关的实验结果表明：基于对象数目和聚类的质量，b i r c h 算法表现出 西南交通大学硕士研究生学位论文第8 页 线性可扩展性；然而由于大小的限制，c f 树中的每个结点仅能容纳有限的入 口，因此一个c f 树结点并不总能对应用户所认为的一个自然聚类；此外如果 聚类不是圆状的，则会由于b i r c h 算法是利用半径来控制一个聚类半径的， 从而导致算法的性能变差【4 】。 2 3 2c u r e 算法 多代表聚类( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e s ，c u r e ) 在一般的分割聚类和分层聚类方法中，各类往往只由类中心来代表，即 主观假设类形状为超球：而且优化目标函数往往以最小化方差为目标。这样 当类的形状和大小相差很大或存在噪声时往往导致误分类，例如著名的“锁 链效应 。g u h a 等提出的多代表分层聚类( c u r e ) 具有非常简洁的思想：每个 类的所有样本点不再由单个类中心代表，而是由多个散布于类中、能够表现 类几何形状的样本点代表，同时为了消除外围噪声带来的影响，这些散布的 样本点向类中心“收缩”一个比例因子，力求在表现类形状的同时减小噪声 的扰动。正是这样的特点使得a 珉e 能够较好地分辨任意形状的类，同时对 噪声具有很好的鲁棒性。 r o c k 也是一个聚合层次聚类算法。与a 瓜e 算法不同，r o c k 算法适 合处理符号属性。它通过将两个聚类间连接的累计与用户所指定的静态连接 模型相比较，计算出两个聚类间的相似性。而所谓两个聚类( c 1 和c 2 ) 间连 接就是指两个聚类间的连接数目。而l i n k ( p 1 ，p 2 ) 就是指两个点p 1 和p 2 之 间共同邻居的数目。也就是聚类间的相似程度是利用不同聚类中点所具有的 共同邻居数来确定的【2 引。 r o c k 算法首先根据所给数据的相似矩阵和相似阈值，构造出一个松散 图；然后在这一松散图上应用一个层次聚类算法。 c h a m e l e o n 是一个探索层次聚类中动态模型的聚类算法。在其聚类 过程中，如果两个聚类间的连接度和相似度与聚类内部的连接度和相似度密 切相关，那么就合并这两个聚类。基于动态模型的合并过程将有助于发现自 然和同质的聚类；并在定义了有关相似函数的情况下j 适用于任何的数据类 西南交通大学硕士研究生学位论文第9 页 型。 c h a m e l e o n 是针对c u r e 和r 燃两个层次聚类算法所存在的不足 而提出的。c u r e 忽略了两个不同聚类间的连接累计信息；而r o c k 则在强调 聚类间连接信息却忽略了有关两个聚类间相接近的信息。 c h a m e l e o n 首先利用一个图划分算法将数据对象聚合成许多相对较 小的子聚类；然后再利用聚合层次聚类方法，并通过不断合并这些子聚类来 发现真正的聚类。为确定哪两个子聚类最相似，该算法不仅考虑了聚类间的 连接度，而且也考虑了聚类间的接近度，特别是聚类本身的内部特征。由于 算法并不依赖一个静态用户指定的模型，因此它能够自动适应要合并的聚类 内部特征。 图2 1c h a m e l e o n 算法主要处理步骤示意描述 c h a m e l e o n 算法利用常用妊最近邻图方法来表示相应的对象。k 最近 邻图中的每个顶点代表一个数据对象；若一个对象为另一个对象k - 最近邻 ( 对象) 之一，则这两个对象之间就存在一条边。k - 最近邻图c k 动态描述了 相邻的概念。一个对象近邻半径是由该对象所处区域的密度来决定的。在一 个密集区域中，其近邻就很狭小：而在稀疏区域中，其近邻就较广。这样就 可能得到比较自然的聚类。此外一个区域密度就定义为其中的边数。这样一 个密集的区域所含的边数显然要多于一个稀疏区域所含的。 有关研究表明，与c u r e 和r d b s c a n 方法相比，c h a m e l e o n 算法在 发现具有高质量任意形状聚类方面能力更强：但在最坏情况下，它处理高维 数据还可能需要o ( n 2 ) 时间1 4 j 。 毒 棼伊 西南交通大学硕士研究生学位论文第1 0 页 第3 章新的层次聚类算法 3 1 现有层次方法普遍存在的问题 现有的分层方法普遍存在一些问题： 1 输入聚类参数：比如聚类数量，多数聚类算法都存在这个问题，需 要输入聚类的数量比如划分方法的k - m e a n s 和k - m e d o i d 。c h a m e l e o n 算法也是一样。问题在于：基于最短距离的算法总是把距离最短的对象聚 合成一个聚类，如果没有限制终结条件的话，该过程会持续进行，直到所 有的数据都聚类成一类。d b s c a n 等密度算法需要设置密度系数e 等参数。 这些参数的获取本身相当困难。 2 发现的形状：a 瓜e 算法和c h a m e l e o n 都可以发现任意形状， 但是c u r e 算法的形状局限于k - m e a n s 算法的结果，c h a m e l e o n 算法 所能发现的形状受输入聚类数量参数k 的影响，使的所发现的最终结果并 不一定是理想的聚类结果和形状。很明显，密度的聚类算法总是可以形成 任意形状的聚类，但是划分算法总是很难达到这个目的。原因他们是基于 最短距离的思想，该距离不断增长，其结果总是球( 圆) 形的范围。 为了克服以上问题，本文有针对性的提出了基于单位距离的聚类方法。 3 2 新的分层聚类算法 3 2 1 单位距离的思想 针对上面提出的任意形状的问题，可以提出个思想就是：数据对象 可以按照某个规则先聚类成比较小的球形聚类，然后再按照类似的规则进 一步形成任意形状的聚类，反复这个过程，最终形成终极聚类。 对于空间的n 个对象，假设这n 个对象在这个空问上是平均散布的， 我们把邻近的两个对象之间的距离的称为单位距离( u 1 1 i td i s t a n c e u d ) ， 利用该距离对数据对象聚类，只可能把他聚成一个类，再假设有一个对象 西南交通大学硕士研究生学位论文第1 1 页 ( 或者几个对象) 的位置产生偏移，我们还是用这个单位距离( u d ) 对n 个对象聚类，结果是占用空间多的这个对象自己是一个类，其他就可能分 为一个或者几个类。如果所有的对象的位置都产生了偏移。仍然可以用这 个距离对他们进行聚类。 图3 一l 空间平均散布的对象( 1 个聚类结果) 图3 - 2 单个对象空间扩展后的聚类( 3 个聚类结果) 要对这些对象聚类，更希望聚类的结果是任意形状的，可以用小的聚 类连结成大的聚类的层次办法，即尽可能的产生细小的聚类，然后通过一 定的策略将这些聚类连接起来，形成最终的任意形状的聚类。 显然可以利用单位距离的思想完成底层的聚类，同时这种方法面临一 个重要问题：初始聚类利用标准的单位距离会产生底层的原子聚类，原子 聚类合并成最终的聚类需要有个标准，即在什么条件下可以结束合并过程。 产生原子聚类的过程能够产生比较多的数据原子类，同时也会产生比 较多的孤立点。虽然我们不太清楚最终期望的聚类数量，但是聚类的结果 中的孤立点的数量可以有个期望。利用对聚类结果的孤立点的期望对数据 聚类的结果作为约束条件是可行的。针对这个问题，本文引入孤立点优化 的思想。 3 2 2 孤立点优化的思想 孤立点优化：只有1 个对象的聚类称为孤立点。聚类结果中的孤立点 可以看作是特殊数据或者非正常数据，在现实世界中，非正常数据产生的 概率是固定。 我国新生儿童死亡率：城市为干分之七，农村新生儿童死亡率为千分 之十二。新生儿童死亡率跟很多方面有关系：经济能力、医疗水平，但是 纵然经济能力再提升，医疗水平再提升，新生儿童死亡率也不可能为零。 可以理解该数据为特殊事件，特殊事件的概率永远存在，能力的提高能够 西南交通大学硕士研究生学位论文第1 2 页 降低这个概率，但是概率是存在的，可以根据这个概率推算我国新生儿童 大概死亡数量1 0 0 ，0 0 0 。 美国警察自杀率高有其自身的特殊性。据统计，美国每1 0 万警察中 有2 0 几人自杀，其自杀率居各职业之首。 为什么在一个经济如此发达的社会中出现这样的现象，其原因主要 有：美国警察面临的压力普遍较高，工作时间过长、工作负担过重，使一 些警察感到难以承受；警察经常面临死亡的威胁，对死亡会产生一种司空 见惯的感觉：警察经常遭受来自新闻媒体的批评，感到自己费力不讨好； 法庭审判否认了警察的工作成果，警察可能认为这是对其最大的打击；警 察的职业以男性为主，而通常男性自杀的成功率特别高：警察配有致命的 武器，一旦发生自杀行为就无法抢救；长期的无规律的生活使家庭关系紧 张，导致家庭成员的不满意 警察自杀可以看作特殊事件，该特殊事件永远存在，只可能降低或者 提高，可以推算，2 0 5 0 年美国警察自杀数量大概为5 0 0 人。 根据特殊事件出现的概率和数据集的大小，可以估算聚类结果中孤立 点的数量。可以根据孤立点的数量对已经存在的聚类进行优化： 假设当前存在的孤立点的数量为：m 指定的孤立点的数量为：m 。如 果胗硼则可以优化优化的过程是：寻找一个优化系数使的用u d x a , 进行聚类的时候，刚好可以产生饥个孤立点。 方法如下：为m 个孤立点p i 寻找到其他点最近的距离d ，找到第( m - m ) 个最近距离d ，计算入： d u i ) = x d - u d 用新的u d 对已经存在的聚类重新聚类，就可以得到期望的聚类结果。 对孤立点的期望值取得：通常情况下，孤立点数量有一个大概的范围， 可以根据特殊数据产生的概率来推算。如果没有这个期望值，或者该数值 浮动比较大，可以先用简便的算法( 采样分析) 分析孤立点的数量然后再 优化该算法。 如果确实无法取得孤立点的期望值，本文还引入了u d 优化方法。 ；2 3u d 优化的思想 在孤立点期望无法取的情况下，可以利用u d 优化方法：u d - - u d x x 入 西南交通大学硕士研究生学位论文 第1 3 页 为优化系数。利用u d 聚类结束后，产生数量比较多的原子聚类和孤立点。 u d 优化的策略是对这些孤立点再聚类的思想，即：假设孤立点在所占用的 空间中均匀分布，在该空间中用单位距离来聚类，所有数据是一个聚类，实 际上这些数据不是均匀分布的，对该数据利用该空间的单位距离来聚类，可 以获得更准确的孤立点范围，反复这个过程直到所求孤立点的数量无显著变 化。为了降低噪音，第一次对孤立点聚类的时候要排除显著孤立点及其所占 有的空间( 去掉距离最大的孤立点和它所占的空间) 。 算法步骤： 1 用u d 对所有数据聚类 2 排除显著孤立点及其所占空间 3 计算剩余孤立点在所在空间的单位距离u d 4 利用u d 对1 所求的聚类以及剩余孤立点聚类 5 重复3 - 4 步骤直到孤立点( i p ) 数量相当小，根据不同情况可以设置为 i p k 。 3 3u d b a 算法实现的步骤 结合单位距离和孤立点优化的思想，本文提出了基于单位距离的分层聚 类算法：u d b a 算法( u m td i s t a n c eb a s e da l g o r i t h m ) ，对该算法的实现步骤描 述如下： ，1 计算单位距离l i d ，u d 是单位空间( t o t a l s p a e e n ，总空间除以对象 的总个数) 的直径的长度。 2 建立一个双向链表。如图3 3 西南交通大学硕士研究生学位论文 第1 4 页 图3 3 带一个孩子的双向链表 链表结点的结构如下： 指针p r i o r 指向前一个结点 指针q l i l d ：指向第一个孩子结点 变量s i z e ：是聚类中对象的个数 指针e n d c h i l d ：指向最后一个孩子 指针n e x t ：指向下一个结点 选择双向链表的原因是聚类的数量的动态的，存在插入和删除聚类 的情况，相比之下，双向链表对删除对象的操作比单向链表的操作要方 便。 孩子结点的数据结构如下： 变量p i ，是第i 元素( 可以在原始数组b a s e a r r a y i 找到它的坐标： b a s e a r r a y i x ，b a s e a r r a y i y ，) 指针n e x t ：指向下一个孩子 3 对于一个新的对象p ，要么它自己是一个聚类，要么他邻接其他聚类。 如果p 是单独聚类，则创建一个新的聚类。如果他跟其他的聚类邻接，则把 这些聚类合并为一个聚类，持续这一操作，直到最后一个对象。 邻接的条件是：d ( c ，p ) 列) d d ( c ，p ) 是聚类c 中的孩子与p 之间的最小距离 4 孤立点优化：计算聚类中s i z e 为1 个聚类的个数，并找到这些孤立点 的最短距离。如果孤立点个数大于给定的孤立点的个数，找到第m - m 个最 西南交通大学硕士研究生学位论文第1 5 页 短距离d ，利用x = d ( u d ) ，重新计算u d = d 。 7 5 利用新的u d ，对聚类进行合并，形成最终聚类。 3 4u d b a 算法的特点 3 4 1u d b a 算法的优点 1 无须输入聚类数量k ，但是可以提供其他的参数，比如孤立点的数量， 而且此参数在某些情况下比较容易获得，比如采样。 2 可以完成任意形状的聚类。 3 4 2u d b a 算法的局限性 只能完成能计算出单位距离的一些数值类型对象的聚类，不能针对其他 的比如二值型、多维空间等。针对大量数据的处理能力也是一般。容易受噪 音的影响。 3 5u d b a 算法的复杂度 3 5 1 空间复杂度 对于空间来说，一个长度为刀的双向链表加上一个长度为刀的坐标数组 就可以满足空间的需要。空间复杂度为：o ( n ) 3 5 2 时间复杂度 时间复杂度可以通过计算每个步骤使用的时间来计算 1 计算u d ：复杂度为n 2 形成双向链表：复杂度为i 1 3 用l i d 聚类： 西南交通大学硕士研究生学位论文第1 6 页 最坏情况为：n x ( n - 1 ) 2 最好情况下：n - l 4 平均复杂度为：n x ( n - 1 ) 2 5 孤立点优化中，l i d 的重新计算：复杂度为m x n ( m 为孤立点的数量) 6 ，孤立点优化是重复第3 步：复杂度为n 2 。 所以时间复杂度为：w ( n ) = o ( n b 3 6 算法性能分析 1 可伸缩性。一般：大量数据处理方法从理论讲应该是多种思想和方法 的的结合体。单独的j 种算法处理大量数据总是很困难。 2 处理不同类型属性的能力。一般。 3 发现任意形状的类。良好：可以实现任意形状。 4 决定输入参数的领域知识最小化。良好，特殊数据产生的概率相对固 定，因此产生的聚类结果中的孤立点的数量也可以推算。 5 处理噪声数据的能力。一般，该层次化的方法由低层聚类向高层聚类 合并来产生最终聚类，该过程受噪音的影响比较小，但是最终聚类的结果对 因为孤立点优化的问题，受噪音影响比较大。 6 对输入数据顺序的敏感性。良好：该算法对数据顺序不敏感 7 处理高维数据的能力。一般。 3 7 实验比较和结果分析 1 、实验选择 本文选择的比较算法是c h a m e l e o n 算法，因为此算法具有以下特点： 1 算法的确定性，该算法聚类效果是唯一的，跟元素输入的次序 没有关系。 2 该算法可以聚类任意图形。 3 正确性，该算法根据最近距离计算聚类，其正确性不容置疑。 4 输入聚类的数量决定了聚类的结果便于比较观察。 所以，选择c h a m e l e o n 算法可以验证本文算法的正确性。 西南交通大学硕士研究生学位论文第1 7 页 实验的环境：x p 编译环境为t u r b o c 2 实验数据的选择： 实验( 一) 选用的数据集合是i r i s 给出的一个生物数据集。碾i s 是一 种鸢尾属植物) 在数据记录中，每组数据包含i r i s 花的四种属性：萼片长度， 萼片宽度，花瓣长度和花瓣宽度，三种不同的u s 花各有5 0 组数据这样 总共有1 5 0 组数据或模式。 实验( 二) 由于实验一中得到的孤点数量比较少，无法进行孤立点优化 的实验，实验( 二) 只选用萼片长度，萼片宽度作为实验数据，使数据聚类 过程中能够产生教多孤立点以便进行优化实验。 实验( 三) 选用d e l v e 提供的c e n s u sh o u s e 数据集，为美国1 9 9 0 的房屋 普查数据，总数据量为2 2 8 7 4 条，实验过程中选用的数据内容为区域人口数 量和家庭数量，分别采集5 0 0 条和1 0 0 0 条数据观察。 2 、实验( 一) 对于高维数据的聚类，图象化的显示聚类结果是比较困难的，通常情况 下，都需要把聚类结果投影