（计算机软件与理论专业论文）数据挖掘技术中聚类算法的研究.pdf

摘要 摘要 随着信息技术的迅速发展，需要分析和管理的数据日益增多。为了从数据中发现有 价值的知识和规律，人们提出用数据挖掘来解决这一难题。数据挖掘及其应用已经渗透 到多个学科，并在人工智能与机器学习、数据库、模式识别、生物信息学、神经计算等 领域取得了丰硕的成果。作为数据挖掘的重要工具之一，聚类技术得到越来越多的关注， 至今已提出了大量的理论和方法。随着数据挖掘技术的广泛应用，数据挖掘所面对的数 据对象日趋复杂，聚类研究也面临更多新的内容和挑战。本文对数据挖掘技术，尤其是 对聚类分析进行了较为系统的分析和研究，介绍了一些改进的算法，主要内容如下： ( 1 ) 介绍了数据挖掘的产生与发展以及数据挖掘中聚类分析的发展方向，总结了划 分方法、层次方法、基于网格和密度聚类方法以及其他聚类方法的国内外发展现状，最 后介绍了本文的主要研究内容和章节安排。 ( 2 ) 简要介绍了聚类算法的定义、相似性度量，聚类算法的分类和聚类方法的评价。 详细讨论了数据挖掘中常用的聚类算法及其基本原理，最后对聚类算法的评价进行了讨 论。 ( 3 ) 详细讨论传统k - m e a n s 算法的基本思想、算法流程和算法性能。传统的k - m e a n s 算法要求用户事先给定k 值，限制了很多应用，初始中心点随机选择，容易导致局部极 值点，常用的评价函数对于求解最优的聚类数目也不是很理想。针对这些问题，研究了 一种新的评价函数均衡化函数，同时采用基于密度的初始化中心点选择算法，自动生 成聚类数目，实验结果表明了改进算法的有效性。 ( 4 ) 详细讨论了常用的几个划分判据，介绍谱聚类算法的基本框架和代表性算法， 同时给出谱聚类算法的理论解释。通过分析谱聚类初始化敏感的特点，引入对初值不敏 感的k h m 算法克服这一缺点，在此基础上研究了初始化独立的谱聚类算法。实验结果 表明该算法的有效性和可行性。 最后，对论文的工作进行回顾和总结，就进一步有待研究的问题进行讨论和展望。 关键词：聚类分析；评价函数；谱聚类；初始化敏感 a b s t r a c t w i t ht h ef a s td e v e l o p m e n ti ni t , t b en e e do fa n a l y s i sa n dm a n a g eat r e m e n d o u sa m o u n t o fd a t ab e c o m e sm o r ea n dm o r ei n s t a n t , d a t am i n i n gt e c h n o l o g yi su t i l i z e dt of i n dt h e v a l u a b l ek n o w l e d g ea n dr u l e sf r o mt h e s ed a t a d a t am i n i n ga n di t sa p p l i c a t i o n sh a v ea l r e a d y c o m ei n t om a n yd i s c i p l i n e sa n da c h i e v e dp l e n t i f u lf r u i t si nd i v e r s i f i e df i e l d s ，i n c l u d i n g a r i t i f i c a li n t e l l i g e n c ea n dm a c h i n el e a r n i n g ，d a t a b a s e ，p a t t e r nr e c o g n i t i o n , b i o i n f o r m a t i c s ，n e u r a l c o m p u t i n g ，a n ds oo n a so n eo ft h ei m p o r t a n td a t am i n i n gt o o l s ，c l u s t e r i n gt e c h n o l o g yg e t s m o r ea n dm o r ea r e n t i o n s ，am a s so ft h e o r i e sa n dm e t h o d sh a v eb e e na c h i e v e d w i t hd a t a l 证i l i n gt e c h n o l o g yu s e di nv a r i o u si n d u s t r i e sa n dt h ed a t ab e c o m i n gm o r ea n dm o r e c o m p l i c a t e d ，al o to fn e wc h a g l l e n g e sl i e si nt h er e s e a r c ho nd a t ac l u s t e r i n g t l l i sd i s s e r t a t i o n s y s t e m a t i c a l l y , d e e p l y , r o u n d l y a n dd e t a i l e d l ys t u d i e sa n d a n a l y s e s t h ed a t a m i n i n g t e c h n i q u e ，e s p e c i a l l yc l u s t e r i n ga n a l y s i s n em a i nc o n t e n t sa r eo u t l i n e da sf o l l o w i n g ： ( 1 ) a ni n t r o d u c t i o no ft h ed e v e l o p m e n to fd a t am i n i n ga n dt h ed e v e l o p m e n td i r e c t i o no f c l u s t e r i n ga n a l y s i si nd a t am i n i n ga r ee x ) n c e r n e d ，t h e ns u m m a r i z e dt h es t a t u sq u ob o t hi n c h i n aa n da b r o a do ft h ep o r t i o n i n gm e t h o d ，h i e r a r c h i c a lm e t h o d ，d e n s i t y - b a s e da n d g r i d b a s e d m e t h o da n dt h eo t h e rc l u s t e r i n gm e t h o d s f i n a l l y , t h em a i na c h i e v e m e n t sa n da r r a n g e m e n t so f t h et h e s i sa r ep r e s e n t e d ( 2 ) ab r i e fi n t r o d u c t i o no ft h e d e f i n i t i o no fc l u s t e r i n g a l g o r i t h m , c o m p a r a b i l i 够 m e a s u r e m e n t , t h ec l a s s i f i c a t i o na n de v a l u a t i o no ft h ec l u s t e r i n ga l g o r i t h m sa r ec o n c e m e d n em a i nc l u s t e r i n ga l g o r i t h m sa n di t sb a s i cp r i n c i p l eu s e di nd a t am i n i n ga r ei n t r o d u c e di n d e t a i l f i n a l l y , t h em e t h o d sf o re v a l u a t i n gt h ec l u s t e r i n gr e s u l t sa r ee x p l a i n e d ( 3 ) t h eb a s i ci d e a s ，a l g o r i t h mp r o c e s s e sa n da l g o r i t h mp e r f o r m a n c eo ft r a d i t i o n a l k - m e a n s a l g o r i t h ma l ei n t r o d u c e di nd e t a i l e d i nt r a d i t i o n a lk m e a n sa l g o r i t h m ，v a l u ekm u s t b ec o n f i r m e di na d v a n c e ，a n dt h i sd e m a n dr e s t r i c t sa l a r g en u m b e ro fp r a c t i c a la p p l i c a t i o n s i n i t i a lc e n t e r sa r es e l e c t e dr a n d o m l ya n df o rt h i sr e a s o nl o c a le x t r e m u m sw i l lb ei n t r o d u c e d n l ec o m m o ne v a l u a t ef u n c t i o n st ot h eo p t i m u mn u m b e ro fc l u s t e r i n gc a nn o tb ev e r y s a t i s f a c t o r i l yc a l c u l a t e d t oc o n q u e rt h e s ep r o b l e m s ，an e we v a l u a t i o nf u n c t i o n e q u a l i z a t i o n f u n c t i o ni si n t r o d u c e d , m e a n w h i l eb a s e do nt h ed e n s i t yo ft h ec e n t e ri n i t i a l i z a t i o na l g o r i t h m , t h en u m b e ro fg e n e r a t i o nc l u s t e r i n ga r ea u t o m a t i c a l l yc a l c u l a t e d ，r e s u l t so ft h ee x p e r i m e n t p r o v et h ee f f i c i e n c yo ft h ei m p r o v e dk - m e a n sa l g o r i t h m ( 4 ) mc o m m o np a r t i t i o nc r i t e r i o nu s e di ns p e c t r a lc l u s t e r i n g ，t h eb a s i cf r a m e w o r ka n d r e p r e s e n t a t i v ea l g o r i t h m sa r ei n t r o d u c e di nd e t a i l e d ，m e a n w h i l ep r e s e n tt h et h e o r ye x p l a i no f s p e c t r a lc l u s t e r i n ga l g o r i t h m t h r o u g ha n a l y z i n gt h ee s s e n t i a lo fs p e c t r a lc l u s t e r i n gi n i t a l i z e s e n s i t i v e ，t h i sp a p e ri n t r o d u c e dt h ek - h a r m o n i cm e a n sa l g o r i t h mt oc o n q u e rt h es h o r t c o m i n g ， as p e c t r a lc l u s t e r i n ga l g o r i t h mb a s e do nk - h a r m o n i cm e a n si ss t u d i e d e x p e r i m e n t ss h o wt h a t i ti sa ne f f e c t i v ea n df e a s i b l ew a yf o ri m p r o v i n gt h ep e r f o r m a n c eo fs p e c t r a lc l u s t e r i n g a l g o r i t h m i nl a s t , i tm a k e sac o n c l u s i o no ft h er e s e a r c ha n dp u t sf o r w a r dt h ef u t u r er e s e a r c hi nt h i s f i e l d k e y w o r d s ：c l u s t e r i n ga n a l y s i s ；e v a l u a t i o nf u n c t i o n ；s p e c t r a lc l u s e r i n g ；i n i t a l i z es e n s i t i v e i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我- - - n 工作的同志 对本研究所做的任何贡_ 献均已在论文中作了明确的说明并表示谢意。 签 名： 适必垄 日 期： 盈! 昼：2 f ! 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留，使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定 签名： 施饬覆 导师签名： 逝鱼 日 期： 丝叟：z 二 第一章绪论 第一章绪论 1 1 研究背景及研究意义 1 1 1 数据挖掘的产生和发展 随着信息技术的发展，特别是互联网的发展和信息量的爆炸性增长，信息的重要性 与日俱增。数据分析和理解已经成为新的目标，人们期待着从数据中发现有价值的信息 和知识，发现事物发展的趋势，期待自动分析工具的出现【1 】1 2 。所以，利用大型数据库 技术、并行计算机、高级算法进行主动传输已成为数据库系统的一个关键性的研究课题 【3 】【4 】。但是，数据库技术它仍然以联机事务处理( o n l i n et r a n s a c t i o np r o c e s s i n g ，o l t p ) 为核心应用，缺少对决策、分析、预测等高级功能的支持机制。随着数据库容量的膨胀， 特别是数据仓库( d a t aw a r e h o u s e ) 以及w e b 等新型数据源的日益普及，联机分析处理 ( o n - l i n e a n a l y t i cp r o c e s s i n g ，o l a p ) 、决策支持以及分类、聚类等复杂应用成为必然。 面对这一挑战，数据挖掘( d a t am i n i n g ) 和知识发现( k n o w l e d g ed i s c o v e r y ，k d ) 技术应 运而生，并显示出强大的生命力。 从数据中的发现知识( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 一词首先出现在 1 9 8 9 年举行的第十一届国际联合人工智能学术会议( i j c 趟) 上，从1 9 8 9 年到1 9 9 4 年 举行了四次k d d 的国际研讨会。此后，1 9 9 5 年召开了第一届知识发现和数据挖掘的国 际学术会议。1 9 9 8 年建立新的学术组织a c m s i g k d d ，即a c m 下的数据库中的知识 发现专业组。近几年，从事数据挖掘研发的人员遍布世界8 0 多个国家，数据挖掘的重 点也已从算法研究向具体应用过渡，从实验室原型走向商品化阶段。目前比较有影响的 数据挖掘系统有：s a s 公司的e n t e r p r i s em i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、s g i 公司 的s e t m i n e r 、s p s s 公司的c l e m e n t i n e 、s y b a s e 公司w a r e h o u s es t u d i o 、r u l e q u e s tr e s e a r c h 公司的s e e 5 等。与国外相比，国内数据挖掘的研究稍晚。国内许多科研单位和高等院 校竞相开展知识发现的理论基础及其应用研究，如北京系统工程研究所对模糊方法在知 识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究，中 国科技大学、复旦大学等开展了对关联规则开采算法的优化和构造，南京大学、上海交 通大学等探讨研究了非结构化数据的知识发现以及w e b 数据挖掘。 简单地说，数据挖掘就是在数据中发现模式、知识，或数据间的关系。从统计学角 度，数据挖掘指分析所观察的数据集以发现可信的数据间的未知关系并提供数据拥有者 可理解的、新颖的和有用的归纳数据【5 1 。从数据库的观点来看，数据挖掘是指在存储数 据库、数据仓库或其它信息仓库中的大量数据中发现有趣的知识的过程1 6 j 。从机器学习 的角度，数据挖掘定义为从数据中抽取隐含的、明显未知的和潜在的有用的信息【_ 7 1 。因 此，数据挖掘是一个基于统计学、模式识别、人工智能、机器学习、数据库技术以及高 性能并行计算等领域的交叉性学科，已在经济、商业、金融、天文等行业得到了成功应 用。 江南大学硕士学位论文 1 1 2 数据挖掘中的聚类分析 作为数据挖掘中的重要分支和有效工具，聚类分析并非一个新领域，它早已被应用 在其他学科中。d u b e s 和j a i n 8 】关于聚类分析的综述包括了从7 7 份杂志和4 0 本书中摘 取出来的2 5 0 条引文，如此巨大的文献量说明了聚类分析的重要性和学科交叉性，也足 以说明它的发展及应用前景的概括性。 聚类就是按照一定的要求和规律对事物进行区分和分类的过程，在这一过程中没有 任何关于类别的先验知识，也没有教师的指导，仅靠事物间的相似性作为类属划分的准 则，因此属于无监督分类的范畴。聚类分析则是指用数学的方法研究和处理给定对象的 分类。聚类分析是多元统计分析的一种，也是非监督模式识别的一个分支。基于“物以 聚类 的思想，它将数据对象分组为若干个类或簇，使得在同一个簇中的对象之间具有 较高的相似度，而不同簇中的对象差别较大，通过聚类，人们发现全局的分布模式以及 数据属性之间的相互关系。 数据挖掘技术的一个突出特点是处理巨大的、复杂的数据集，这对聚类分析提出了 特殊的挑战。根据潜在的各项应用，数据挖掘对聚类分析方法提出了不同的要求，具体 如下1 9 】： 可伸缩性：很多聚类算法在小于2 0 0 个数据对象的小数据集上鲁棒性很好，而对 包含上万个数据对象的大规模数据库进行聚类时，将会导致不同的偏差结果。 具有处理不同类型属性的能力：既可处理数值型数据，又可处理非数值型数据， 既可处理离散数据，又可处理连续域内的数据，如布尔型、序数型、枚举型或这些数据 的混合。 能够发现任意形状聚类：一般聚类的算法采用欧几里得距离或者曼哈坦距离来衡 量数据的相似度，但基于这样的距离度量的算法趋向于发现具有相近密度和尺寸的球状 簇。因此，好的算法必须能有效地并且正确地发现任意形状的聚类。 输入参数对领域知识的弱依赖性：在聚类分析中，许多聚类算法要求用户输入参 数，聚类结果对于输入参数十分敏感，通常参数较难确定，尤其在处理高维对象数据集 更是如此。 对于输入记录顺序不敏感：一些聚类算法对于输入数据的顺序是敏感的，对于同 一个数据集合，以不同的顺序提交给同一个算法时，聚类结果也将不同。 处理噪声和高维数据的能力：现实应用中绝大多数的数据都包含了孤立点、空缺、 未知数据或者错误的数据，如果算法对于这样的数据敏感，就会导致聚类结果质量较低。 很多聚类算法只能处理低维数据，数据对象在高维空间的聚类非常具有挑战性。 基于约束的聚类：在实际应用中可能需要在各种约束条件下聚类，既要找到满足 特定的约束，又要具有良好的聚类特性的数据分组是一项具有挑战性的任务。 聚类分析既可以作为其他算法的预处理步骤，又可以作为一个独立的工具来获得数 据的分布情况。它主要应用于模式识别中的语音识别、字符识别等，机器学习中的聚类 算法应用于图像分割和机器视觉，图像处理中的聚类用于数据压缩、信息检索。聚类的 另一主要应用是多关系数据挖掘、时空数据库应用( g i s 等) 、序列和异类数据分析等。 2 第一苹绪论 此外，聚类还应用于统计科学，对生物学、心理学、考古学、地理学以及市场营销等研 究都有重要作用【lo 】【1 1 1 。 1 2 国内外研究现状 根据数据在聚类中的积聚规则以及应用这些规则的方法，有多种聚类算法。聚类算 法有多种分类方法，大致可以分为基于划分的聚类方法、基于层次的聚类方法、基于密 度和网格的聚类方法以及其他聚类方法。下面我们将根据目前发展情况，仍以这几类为 基准简要阐述一些比较有代表性的方法。 1 2 1 基于划分的聚类方法 1 9 6 7 年，m a c q u e e n 首次提出k 均值算法【1 2 】( k - m e a n s 算法) ，但是它只有在簇平 均值被事先预先定义好的情况下才能使用，加之对噪声数据的敏感性等，使得对数据挖 掘的适应性较差。因此，出现一些改进算法，主要有k a u f m a n 等提出的k 中心点算法 p a m i 玎1 和c l a r a 1 3 1 算法，其他有代表性算法有e m f l 4 1 算法、c l a r a n s 15 】算法等。19 9 8 年，h u a n g 等【1 6 】提出一种适合于分类属性数据聚类的k m o d e s 算法，并且证明了经过有 限次迭代收敛于局部最小值。2 0 0 1 年，c h a t u r v e d i 等【1 刀提出一种面向分类属性数据的非 参数聚类方法，h u a n g 证明了它与k m o d e s 算法是等价的。2 0 0 2 年，s u n 等人【l3 】将b r a d l e y 等迭代初始点集求精算法应用于k m o d e s 算法。2 0 0 4 年，d i n g 等【2 0 1 提出了一致性保 留k m e a l l s 算法。1 9 6 9 年，r u s p i n i t 2 1 】首次将模糊集理论应用到聚类分析中，提出模糊 聚类算法( f c m ) 。2 0 0 6 年，李洁等1 2 2 】提出基于特征加权的模糊聚类新算法n f w f c a 。 2 0 0 7 年，c a i 等【2 3 】结合局部空间和灰度信息，提出快速通用f c m 聚类算法f g f c m ，成 功应用在合成和真实世界图像中。1 9 9 9 年，j a i n l 2 4 l 指出著名的图论分裂聚类算法，基于 图论的聚类算法主要包括：r a n d o mw a l k l 2 5 1 ，c h a m e l e o n l 2 6 1 ，a u t o c l u s t l 2 7 】等。2 0 0 7 年，l i l 2 8 】提出一种基于最大0 距离子树的聚类算法m d sc l u s t e r 。基于划分的聚类 方法得到了广泛应用和研究，但是，对于大规模数据集的聚类仍需要进一步研究。 1 2 2 基于层次的聚类方法 层次聚类方法又称为树聚类算法，通过对源数据库中的数据进行层次分解( 分裂和 聚合) ，达到目标簇的逐步生成。代表性的方法有：k a u f m a n 等【1 3 】详细介绍了分裂和聚 合的基本方法；z h a n g 等1 2 9 1 提出利用c f 树进行层次聚类的b i r t h 算法；g u h a 等提出的 c u r e p 0 1 算法、r o c k t 3 1 1 算法；k a r y p i s & h a n 等【3 2 1 提出c h a m e l e o n 算法；2 0 0 7 年，o e l b a r d 等1 3 3 】提出一种新的基于正二进制的层次聚合算法，实验结果表明新算法的正确率和鲁棒 性较好；2 0 0 7 年，k u m a r 等f 3 4 1 面向连续数据提出一种新的基于不可分辨粗聚合的层次 聚类算法r c o s d 。基于层次的聚类方法计算相对简单，但是操作后不易撤销，因而对 于迭代中心中的重定义问题仍需进一步研究。 江南大学硕士学位论文 1 2 3 基于网格扣密度的聚类方法 基于密度的聚类方法是通过度量区域所包含的对象数目来形成最终目标的，基于网 格的聚类方法是将对象空间离散化成有限的网格单元。基于网格的聚类方法通常与其他 方法相结合，特别是与基于密度的聚类方法相结合。比较有代表性的工作有1 9 9 6 年e s t e r 等【3 5 】提出的d b s c a n 方法、1 9 9 8 年h i n n e b u r g 等【3 6 】提出的基于密度分布函数的d e n c l u e 算法、1 9 9 9 年a n k e r s t 等【3 7 】提出的o p t i c s 聚类排序方法、1 9 9 7 年w a n g 等【3 8 】 提出的s t r i n g 方法是一个多层聚类技术。另外一些代表性的研究包括s h i e k h o l e s l a m i 等 1 3 9 】提出的通过小波变换进行多分辨率聚类方法w a v ec l u s t e r ，a g r a w a l 等【柏】提出的将基 于网格和密度结合的高维数据聚类算法c l i q u e 。2 0 0 1 年，z h a o 和s o n g 【4 1 】给出网格密 度等值线聚类算法g d i l ，具有消除奇异值和发现各种形状类簇的能力。2 0 0 4 年，m a 4 2 】 提出一个新的基于移位网格概念的基于密度和网格的聚类算法s g c ，适合任意形状类 簇，且计算时间与数据集规模无关；2 0 0 5 年p i l e v a 等【4 3 】提出一种用于大型、高维空间 数据库的网格聚类算法g c h l ，对噪声数据不敏感且聚类快速、伸缩性极好；2 0 0 6 年， m i c r o 等l 4 4 j 结合时态信息和空间信息，提出了一个基于密度的自适应聚类方法t f c t - m o ；2 0 0 7 年，d e r y a 等【4 5 】对d b s c a n 进行了与辨识核对象、噪音对象和邻近类簇相关 的三个边缘扩展，进而提出一种新的基于密度的聚类方法s t - d b s c a n 。基于网格和密 度的聚类方法最终结果由参数决定，而且对参数设定的敏感性高，这是有待进一步解决 的问题。 1 2 4 其他聚类算法 谱聚类算法作为一种有效的聚类方法受到广泛关注，其中代表性的工作有h a g e n 和 k a h n g 4 6 】将r a t i o c u t 的目标函数图划分算法用于v l s i 设计中；2 0 0 0 年s l l i 和m a l i k l 4 7 根据谱图理论建立二路划分的n c u t 目标函数，设计了用于图像分割的算法；n g 等【4 8 1 人提出一种简单有效的n j w 算法；z h a 等【4 9 】分析了核k m e a n s 的方法，首次用谱松散 的方法获得全局最优解；d h i l l o n 5 0 】在此基础上又研究了加权核k - m e a n s 的目标函数，成 功的应用到文本聚类中；m e i l a & s h i l 5 1 】给出了谱聚类算法的一些简单概率解释；z e l n i k - m a n o r l 5 2 】最近提出一种自调整的谱聚类算法，同时，i o g o rf i s c h e r l 5 3 】提出依赖于背景的 相似性矩阵度量方法和尺度确定方法；2 0 0 5 年，r o b e r tj 和0 c a l l a g h a n 等【5 4 】提出将分 水岭与谱聚类相结合的两个阶段的图像分割方法；2 0 0 7 年，f o w 墩e s 【5 5 】提出使用n y s t r o m 逼近方法减小求解特征问题的计算复杂度；2 0 0 7 年，钱线等【5 6 】提出一种初始化k - m e a n s 的谱方法；王玲等【5 7 】提出一种密度敏感的相似性度量，将其引入谱聚类得到密度敏感 的谱聚类算法和密度敏感的半监督谱聚类；田铮等【5 8 j 给出谱聚类的扰动分析，设计一个 基于权矩阵的无监督谱聚类算法。谱聚类的研究正在起步，还没有完整的理论来描述谱 聚类方法的性能和分析其局限性，目前存在一些问题如相似度矩阵的构造、怎么解决模 糊聚类问题和海量数据的处理问题等。 4 第一章绪论 1 3 本文的研究内容和结构安排 通过分析聚类的研究方向和发展趋势，针对聚类算法存在的问题，本文的研究内容 主要包括k m e a n s 算法研究和谱聚类算法研究，具体如下： ( 1 ) 针对传统k - m e a n s 算法对初值敏感、聚类个数难以确定以及评价函数选取困难 等缺点进行研究，研究了一种新的评价函数均衡化函数，同时采用基于密度的初始中 心点选取算法，自动生成聚类个数。通过在人工数据和真实数据进行实验，证明了改进 算法不仅可以获得稳定的初始中心，同时提高了聚类性能。 ( 2 ) 对现有的谱聚类算法的差异进行分析，针对传统谱聚类算法对初值敏感的特点 进行改造，研究了一种基于k - h a r m o n i cm e a n s 的谱聚类算法( s c k h m ) ，在人工数据 和真实数据上进行实验，并与传统谱聚类算法以及k - m e a n s 、e m 及f c m 算法进行分析 比较，证明了s c k h m 算法的优越性和有效性。 本文分为五章，各章节安排如下： 第1 章，绪论。介绍课题的研究背景与意义，介绍了数据挖掘的产生与发展以及数据 挖掘中聚类分析的发展方向；总结了基于划分的聚类方法、基于层次的聚类方法、基于 网格和密度的聚类方法、其他聚类方法的国内外发展现状；最后介绍了本文的主要研究 内容和章节安排。 第2 章，数据挖掘中聚类算法。简要介绍了聚类算法的定义、相似性度量，聚类算法 的分类和聚类方法的评价。详细讨论了数据挖掘中常用的聚类算法及其基本原理，最后 对聚类算法的评价进行了讨论。 第3 章，基于均衡化函数的k - m e a n s 优化算法。详细讨论传统k - m e a n s 算法的基本思 想、算法流程和算法性能。介绍划分系数、划分熵及紧致度和分离度等几个常用的评价 函数，在此基础上研究一种新的评价函数。借鉴基于密度的初始中心点选取算法，研究 了基于均衡化函数的k m e a n s 优化算法，仿真实验通过人工数据和真实数据证明了算法 的有效性。 第4 章，初始化独立的谱聚类算法。详细讨论了常用的几个划分判据，介绍谱聚类算 法的基本框架和代表性算法，同时给出谱聚类算法的理论解释。介绍对初值不敏感的 k h m 算法的基本思想，在此基础上研究了初始化独立的谱聚类算法。仿真实验通过人 工数据和真实数据验证了改进算法不仅可以成功识别有挑战性的人工数据，并且得到稳 定性的结果，同时减低了聚类的误分率。 第5 章，总结与展望。对论文的工作进行回顾和总结，就进一步有待研究的问题进行 讨论和展望。 5 江南大学硕士学位论文 第二章聚类算法 2 1 聚类算法的基本概念 2 1 1 聚类定义 聚类就是将数据对象分组为多个类或簇，划分的原则是在同一个簇中的对象之间具 有较好的相似度，而不同簇中的对象差别较大。一个聚类分析系统的输入是一组样本和 一个度量两个样本相似度的标准，输出是数据集的几个类，描述如下： 聚类分析的输入可以用一组有序对( x ，s ) 或( x ，d ) 表示，这里x 表示一组样 本，s 和d 分别是度量样本相似度或相异度的标准。聚类系统的输出是一个分区，若 c = c ；，c 2 , , 0 0 9 q ，其中c i ( i = 1 ，2 ，k ) 是x 的子集，如下表示： guc ：u uc：=x(21) c n c ，= 9 ，i ， ( 2 2 ) c 中的成员c ；，c 2 ，g 叫做类，每一个类都是通过一些特征描述的，通常有如下集中表 一- i 不力瓦： 一通过类的中心或类的边界点表示一个类。 使用聚类树中的结点图形化地表示一个类。 使用样本属性的逻辑表达式表示类。 从上可以得知，样本集中每个样本至少属于一个类，并且每个样本只属于一个类。 2 1 2 距离和相似性度量 一个聚类分析过程的质量取决于对相似性度量标准的选择，通常情况下，聚类算法 不是计算两个样本间的相似度，而是用特征空间中的距离作为度量标准来计算两个样本 间的相异度，相异度的度量用d ( 五力来表示，通常称相异度为距离。当x 和y 相似时， 距离d ( x , y ) 取值很小，当x 和y 不相似时，d ( 五力就很大。其中距离测度要满足距离 公理的四个条件：自相似性、最小性、对称性以及三角不等性。 常用的距离函数有如下几种： ( 1 ) 明可夫斯基距离( m i n k o w s k i ) 假设x ，y 是相应的特征，n 是特征的维数。x 和y 的明可夫斯基距离度量的形式如 下： d c x ，y ，= 善i ，一巧l r u ， c 2 3 ， 当r = l 时为绝对值距离d ( 五少) = 善i t y i l 。 6 第- - 2 聚类舁法 当f 2 时为欧氏距离 d c 五y ，= 善k 一以1 2 1 彪。 当，_ 时为切比雪夫距离d ( 而j ，) = k m 毽a x ，z i i x l 一以i 。 以上几种距离中，通常最常用的是欧氏距离，其特点是对坐标系进行平移和旋转变 换之后，保持欧氏距离不变，因此对象仍然保持原来的相似结构。 ( 2 ) 二次型距离( q u a d r a t i c ) 二次型距离测度的形似如下： d ( 五y ) = f ( 工一y ) r a ( x - y ) ) 1 7 2 ( 2 4 ) 其中a 是非负定矩阵。 当a 为单位矩阵时为欧式距离。 当a 为对角阵时为加权欧式距离d c 五y ，= 蓦气，i t 一兄1 2 1 彪。 当a 为协方差矩阵时为马氏距离。 ( 3 )余弦距离 余弦距离的度量形式如下： d ( x ，y ) = 刀 f - e l x i y i ( 2 5 ) ( 4 ) 二元特征样本的距离度量 上面三种距离度量对于包含连续特征的样本很有效，但对于包含些或者全部不连 续特征的样本，计算样本间的距离是比较困难的。下面介绍几种二元类型数据的距离度 量标准。假定x 和y 分别是n 维特征，再和y ，分别表示每维特征，且墨和乃的取值为二 元类型数值 0 ，l 。则x 和y 的距离定义是先求如下几个参数，然后采用s m c 、j a c c a r d 系数或r a o 系数。 a 是样本x 和y 中满足毛= 乃= 1 的二元类型的数量。 b 是样本x 和y 中满足而= l ，3 , i = 0 的二元类型属性的数量。 c 是样本x 和y 中满足毛= o ，咒= 1 的二元类型属性的数量。 d 是样本x 和y 中满足薯= 乃= o 的二元类型的数量。 简单匹配系数( s i m p l em a t c hc o e 伍c i e n t ，s m c ) c k 力= 百瓦a + b 而 ( 2 6 ) 江南大学硕士学位论文 j a c c a r d 系数 ( 五y ) = 磊a 爵 ( 2 7 ) r a o 系数 ( x ，y ) = 百再a 鬲 ( 2 8 ) 2 1 3 类间的测度距离 设有两个类e 和g ，它们分别有m 和h 个元素，它们的中心分别为乞和r b 。设 x c 4 ，y c 6 ，这两个元素间的距离记为d ( x , y ) ，类间距离e y od ( c o ，g ) 。 ( 1 ) 最短距离法 定义两个类中最靠近的两个元素间的距离为类间距离： b ( 巳，c 6 ) = m i n d ( x , y ) i x c a ，y ec 6 ( 2 9 ) ( 2 ) 最长距离法 定义两个类中最远的两个元素间的距离为类间距离： 气( 巴，c 6 ) = m a x d ( x , y ) l x c ，y e 巳 ( 2 1 0 ) ( 3 ) 中心法 定义两类的两个中心间的距离为类间距离。中心法涉及到类的中心概念，首先定义 类中心，然后给出类间距离。 假如q 是一个类，xec ，即x 是c 的一个数据点，则类中心薅定义如下： z 一工c x ，e = _ l ( 2 1 1 ) l 刀 其中，吩是第i 个类中的点数。则c 口和g 的类间距离为： ( c 口，勺) = d ( 乞，名) ( 2 1 2 ) ( 4 ) 类平均法 两个类中任意两个元素间的距离定义为类间距离： d g 乞，勺= 磊1x 三y 乏。d 力 ( 2 1 3 ) ( 5 ) 离差平方和 离差平方和用到了类直径的概念，类直径反映了类中各元素的差异，可定义为类中 各元素至类中心的欧式距离之和，其量纲为距离的平方。 乞= 兰，( _ 一秽( _ 一- ) 乞= f 三l _ 一屹1 _ 一 8 ( 2 1 4 ) 第二章聚类算法 根据上式得到两类c 和g 的直径分布为r o 和r b ，类c o + 。= c 口ug 的直径为o 。，则 可以定义类间距离的平方为： d 参( c i 口，c 6 ) 2 乞+ 6 一乞一名 ( 2 1 5 ) 2 2 主要的聚类方法 聚类是一个活跃的研究领域，目前已经有大量的、经典的和流行的算法涌现。采用 不同的聚类算法，对于相同的数据集可能有不同的划分结果，很多文献从不同角度对聚 类分析方法进行了分类，有如下几种分类方法。 按照聚类的标准进行分类，聚类方法如下两种： ( 1 ) 统计聚类方法 统计聚类方法基于对象之间的几何距离。统计聚类分析包括系统聚类法、分解法、 加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。这种聚类方法是一种 基于全局比较的聚类，它需要考察所有的个体才能决定类的划分。因此，它要求所有的 数据需预先给定，而不能动态的增加新的数据对象。 ( 2 ) 概念聚类方法 概念聚类方法基于对象具有的概念进行聚类，这里的距离不再是传统方法中的几何 距离，而是根据概念的描述来确定的。典型的概念聚类或形成方法有：c o b w e b 、o l o c 和基于列联表的方法。 按照聚类所处理的数据类型进行分类，聚类方法可以分为三种： ( 1 ) 数值型数据聚类方法 数值型数据聚类方法所分析的数据的属性为数值数据，因此可对所处理的数据直接 比较大小。目前，大多数的聚类算法都是基于数值型数据的。 ( 2 ) 离散型数据聚类方法 由于数据挖掘的内容经常含有非数值型数据，近年来人们在离散型数据聚类方法方 面做了许多研究，提出了一些基于此类数据的聚类算法，如k - m o d e 、r o c k 、c a t u s 和s t i i 汛。 ( 3 ) 混合型数据聚类方法 混合型数据聚类方法是能同时处理数值型数据和离散型数据的聚类方法，这类聚类 方法通常功能强大，但性能往往不尽人意。混合型数据聚类方法的典型算法有：k 原型 算法。 按照聚类的尺度，聚类方法可被分为以下三种： ( 1 ) 基于距离的聚类算法 距离是聚类分析的常用的分类统计量。常用的距离定义有欧式距离和马氏距离，许 多算法都是用各式各样的距离来衡量数据对象之间的相似度。算法通常需要给定聚类数 目k 或区分两个类的最小距离。基于距离的算法聚类标准易于确定、容易理解，对数据 维度具有可伸缩性，但只适用于欧几里得空间和曼哈坦空间，对独立点敏感，只能发现 类圆形类。 9 江南大学硕士学位论文 ( 2 ) 基于密度的聚类算法 从广义上说，基于密度和基于网格的算法都可算作是基于密度的算法，此类算法通 常需要规定最小密度门限值。算法同样适用于欧几里得和曼哈坦空间，对噪声数据不敏 感，可以发现不规则的类，但当类或子类的粒度小于密度计算单位时，会被遗漏。 ( 3 ) 基于互连性的聚类算法 基于互连性的聚类算法通常是基于图或超图模型，它们通常将数据集映射为图或超 图，满足连接条件的数据对象之间画一条边，高度连通的数据聚为一类。此类算法可适 用于任意形状的度量空间，聚类的质量取决于链或边的定义，不适合处理太大的数据集。 当数据集大时，通常忽略权重小的边，使图变稀疏，以提高效率，但会影响聚类质量。 按照聚类的原理进行分类，聚类分为划分聚类方法、层次聚类方法、密度聚类方法、 网格聚类方法和模型聚类方法等。 2 2 1 划分聚类方