（计算机应用技术专业论文）基于变异粒子群的聚类算法研究.pdf

r e s e a r c ho nc l u s t e r i n ga l g o r i t h mb a s e do nm u t a t i o np a r t i c l e s w a r mo p t i m i z a t i o n b y w a n gd o n g b e ( a n q i n gt e a c h e r sc o l l e g e ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g m c o m p u t e ra p p l i c a t i o n s m c h a n g s h au n i v e r s i t yo fs c i e n c e t e c h n o l o g y s u p e r v i s o r p r o f e s s o rl u ok e m a r c h ，2 0 1 1 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名： 丑砻、 日期：山年岁月“日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密圈。 ( 请在以上相应方框内打“”) 作者签名：王、考、 导师签名：、多可 日期：勘i1 年j 月铂 日期：工口1 1 年f 月d 日 摘要 在数据挖掘中，很多工作都集中在发现能够高效地对大数据库进行聚类分析的方法 上。在现有的大量聚类算法中，尤其以k - m e a n s 算法应用比较广泛。k m e a n s 算法以点 为原型，能够实现球形数据的聚类。该算法思想简单，易于实现，而且运行速度快，内 存消耗小，能有效地处理大数据集，但是k - m e a n s 聚类算法存在一些缺点：只有在初始 值确定的情况下，聚类结果才是唯一确定的；算法都是局部寻优算法，容易追寻目标函 数而陷入局部最优解，而且算法在一定程度上依赖于初始分类的确定，如果初始分类严 重地偏离全局最优分类时，算法很容易陷入局部极小值，得到一个局部最优解。另一方 面由于p s o 算法结构简单，运行速度快，所以也被大量地用于聚类算法中。因此本文 在前人的基础上对算法进行了改进，把两种算法进行了有机的结合。所做的工作如下： 1 用变异粒子群聚类挖掘完成聚类。首先分析了粒子群算法的缺点，将粒子变异引 入粒子群算法，通过增加种群的多样性来克服早熟收敛现象；其次通过对惯性权重的调 整提高了算法的精度和收敛速度；最后，将k m e a n s 算法和粒子群算法结合起来形成一 种混合聚类算法。该算法有效地平衡了粒子群寻优过程中的探索和开发，从而保证了粒 子群算法稳定且收敛到全局最优。 2 用基于种群多样性的p s o 聚类挖掘算法实现聚类。首先分析现有的描述种群多样 性指标的缺点；其次将基于粒子群算法的变异操作和k - m e a n s 算法结合到粒子群算法 中；最后，通过内部空间特性对粒子进行适当的扰动。该算法既改善了粒子群算法的局 部搜索能力，又通过增加种群的多样性，避免了算法出现早熟收敛现象。 3 计算机仿真。使用v c 6 0 工具对提出的算法进行模拟实现，并对提出的算法与现 有的成果进行比较，分析算法的优劣性。 关键词：数据挖掘；粒子群；k - 均值聚类算法；变异；聚类 a b s t r a c t m o s tw o r ko fd a t am i n i n gh a sf o c u s e do nt h ed i s c o v e r yo ft h em e t h o d sw h i c hc o u l d e f f e c t i v ec l u s t e rt ol a r g ed a t a b a s e a tp r e s e n t ，t h e r ei sal a r g en u m b e ro fc l u s t e r i n ga l g o r i t h m s i nw h i c hk m e a n sa l g o r i t h mw a sa p p l i e dw i d e l y k - m e a n sc l u s t e r i n ga l g o r i t h mr e g a r dp o i n ta s t h ep r o t o t y p ef o rc l u s t e r i n go fs p h e r i c a ld a t a t h o u g h t so ft h ea l g o r i t h mi ss i m p l e ，e a s yt o i m p l e m e n t ，f a s tr u n n i n gs p e e d ，s m a l lm e m o r yc o n s u m p t i o na n dh a n d l i n gl a r g ed a t as e t s ，b u t t h e r ea r es o m em a j o rd i s a d v a n t a g e s ：o n l yt h e ni nt h es i t u a t i o no fd e f i n i t et h es t a r t i n gv a l u e ，t h e c l u s t e rr e s u l ti st h eo n l ya s c e r t a i n e d ；t h ea l g o r i t h mi st h ep a r t i a ls e a r c h i n go p t i m i z a t i o n a l g o r i t h m ，e a s y t of a l li n t o t h e p a r t i a l m i n i m u mf o r t r a c k i n g d o w nt h e o b j e c t i v e f u n c t i o n m o r e o v e r , t h ea l g o r i t h mr e l i e so nt h ei n i t i a lc l a s s i f i e dc h o i c eo nag r e a te x t e n t i ft h e c l a s s i f i c a t i o ns e r i o u s l yd e v i a t e st h eo v e r a l ls u p e r i o rc a l s s i f i c a t i o n ，t h ea l g o r i t h mv e r yp o s s i b l y f a l l si n t ot h ep a r t i a lm i n i m u ma n do b t a i n sap a r t i a lo p t i m a ls o l u t i o n o nt h eo t h e rh a n d ，t h e s t r u c t u r eo ft h ep s oi ss i m p l ea n dt h ev e r yq u i c kr u n n i n gr a t e ，s ot h ep s oa l g o r i t h mi su s e dt o t h ec l u s t e ra l g o r i t h m o nt h e b a s i so fp r e v i o u st h e o r y , t h ea l g o r i t h mw a si m p r o v e do nt h i s p a p e ra n dt h et w oa l g o r i t h mw e r e c o m b i n e do r g a n i c l y w o r ka sf o l l o w s ： 1 t h ec l u s t e r i n gw a sc o m p l e t e dw i t ht h ev a r i a t i o np s o f i r s t ，a n a l y z i n g t h e s h o r t c o m i n g so f t h ep a r t i c l es w a r ma l g o r i t h ma n dv a r i a t i o no ft h ep a r t i c l ei si n t r o d u c t i o nt o p s o ，t h ep r e m a t u r ec o n v e r g e n c ep h e n o m e n o nw a so v e r c o m e db yi n c r e a s i n gt h ed i v e r s i t yo f t h ep o p u l a t i o n s e c o n d l y , i m p r o v i n gt h ea l g o r i t h m sa c c u r a c ya n dc o n v e r g e n c es p e e dt h r o u g h t h ea d j u s t r n e n to ft h ei n e r t i aw e i g h t f i n a l l y , t h ek - m e a n sa l g o r i t h ma n dp s ow a sc o m b i n e dt oa h y b r i dc l u s t e r i n ga l g o r i t h m t h ea l g o r i t h me f f e c t i v e l yb a l a n c et h ee x p l o r a t i o na n dd e v e l o p m e n t o ft h ep s oi nt h ep r o c e s so fo p t i m i z a t i o n , t h u se n s u r i n gt h es t a b i l i t ya n dc o n v e r g e n c i n gt ot h e g l o b a lo p t i m u mo f t h ep s o 2 t h ec l u s t e r i n gw a sr e a l i z e db yt h ep s oc l u s t e r i n ga l g o r i t h mb a s e do np o p u l a t i o n d i v e r s i t y i n t h ef i r s t p l a c e ，a n a l y z i n gt h es h o r t c o m i n g so ft h e i n d i c a t o r s o fp o p u l a t i o n d i v e r s i t y i nt h es e c o n dp l a c e ，t h em u t a t i o no f t h ep s oa n dk m e a n sa l g o r i t h mw e r ei n t r o d u c e d t ot h ep s o ；f i n a l l y , t h ep a r t i c l e sw a sa p p r o p r i a t ed i s t u r b a n c eb yt h es p a t i a lc h a r a c t e r i s t i c s n o t o n l yi st h ep s ol o c a ls e a r c ha b i l i t yi m p r o v e d ，a v o i d i n gt h ep r e m a t u r ec o n v e r g e n c eo ft h e i i a l g o r i t h mb yi n c r e a s i n gt h ep o p u l a t i o nd i v e r s i t y 3 c o m p u t e rs i m u l a t i o n s i m u l a t i n go ft h ep r o p o s e da l g o r i t h mw a si m p l e m e n t e db yu s i n gt h e v c 6 0t o o l ，a n dc o m p a r e dt h ep r o p o s e da l g o r i t h mw i t ht h ee x i s t i n gr e s u l t s ，a n da n a l y s i s i n g p e r f o r m a n c eo ft h ea l g o r i t h m k e yw o r d s ：d a t am i n i n g ；p a r t i c l es w a r mo p t i m i z a t i o n ；k - m e a n s ；c l u s t e r i n ga l g o r i t h m m u t a t i o n ；c l u s t e r i n g i i i 目录 摘要。i a b s t r a c t i i 第一章绪论 1 1 研究背景和意义1 1 2 国内外研究现状2 1 2 1 数据挖掘的研究现状2 1 2 2 聚类的研究现状3 1 3 本文工作4 1 4 论文结构5 第二章聚类 2 1 聚类概述6 2 1 1 聚类的概念6 2 1 2 聚类算法性能评价7 2 2 距离和相似系数一9 2 2 1 距离9 2 2 2 相似系数1 0 2 3 聚类分析的过程1 2 2 3 1 数据准备1 3 2 3 2 特征生成1 3 2 3 3 聚类分析1 3 2 4 聚类分析算法的分类1 4 2 4 1 戈0 分法1 4 2 4 2 层次方法1 4 2 4 3 基于网格的方法l5 2 4 4 基于密度的方法1 5 2 4 5 基于变换的聚类算法1 5 2 4 6 基于模型的方法1 6 2 5k m e a n s 算法。1 6 2 6 聚类分析的应用17 2 7 本章小结18 第三章基于变异粒子的聚类挖掘 3 1p s o 研究背景19 3 2 基本粒子群算法介绍2 0 3 2 1 算法原理2 1 3 2 2 基本粒子群算法描述2 2 3 2 3 社会行为分析2 2 3 3 与其它进化算法的比较。2 3 3 4 具有惯性权重的粒子群算法2 4 3 5 基于粒子群的k m e a n s 算法2 5 3 5 1p s o 算法的参数选择2 5 3 5 2p s o 聚类算法的编码与适应度选择2 6 3 5 3 基于p s o 的k - m e a n s 算法的描述2 6 3 6 变异粒子群算法( m k - p s o ) 2 8 3 7 种群多样性描述2 8 3 8 参数调整2 9 3 8 1 惯性权重的调整2 9 3 8 2 学习因子的调整。2 9 3 9 变异操作3 0 3 10 算法描述3 0 3 1 1 变异粒子群聚类算法的编码设计3 1 3 1 1 1m k p s o 聚类的编码表示与适应度选择3 1 3 1 1 2 算法设计。3l 3 1 2 算法复杂度分析。3 2 3 1 2 1 空间复杂度3 2 3 1 2 2 时间复杂度3 2 3 1 3 仿真实验3 2 3 1 4 本章小结3 4 第四章基于种群多样性的p s 0 聚类挖掘算法 4 1 种群多样性描述3 5 4 1 1 种群平均粒距：3 5 4 1 2 种群分布熵3 5 4 1 3 均值偏差3 6 4 2 调整策略3 6 4 2 1 最大位置3 6 4 2 2 惯性权重自适应调节3 7 4 - 3 变异操作3 7 4 4 改进后的基于种群多样性的p s o 算法3 7 4 5 基于种群多样性的p s o 聚类算法( m p s o ) 3 8 4 5 1m p s o 算法的编码表示与适应度选择3 8 4 5 2 内部空间特性3 8 4 5 3m p s o 聚类算法的实现步骤3 9 4 6 算法复杂度分析3 9 4 6 1 空间复杂度3 9 4 6 2 时间复杂度4 0 4 7 收敛性分析4 0 4 8 仿真实验4 0 4 9 本章小结4 1 第五章结论与展望 5 1 结论。4 2 5 2 展望。4 2 参考文献4 4 致谢4 7 附录( 攻读硕士学位期间发表录用论文) 4 8 1 1 研究背景和意义 第一章绪论 随着计算机软件和硬件的快速发展，特别是数据库技术的广泛使用，人们面临着快 速增长的海量数据，如何有效地从这一海量数据中发现有用的知识为人类服务，也已成 为许多研究人员所重点关注的一个研究课题。与逐步完善的软件和数据存储技术相比， 人们所采用的数据分析工具，却很难有效地为决策者提供决策所需要的数据、信息，因 此面临着尴尬的境地一“丰富的数据，匮乏的信息 。为了有效地解决这一实际问题， 从二十世纪8 0 年代开始，数据挖掘技术慢慢地发展起来。数据挖掘又常被称为数据库 中知识发现，它是一个从大量的、有噪声的、模糊的、不完全的、随机的数据集中抽取 挖掘出新颖的、有价值的规律或可理解的模式等知识的复杂过程。通过数据挖掘，有价 值的知识、规则或高层次的信息就能从数据库的相关数据集合中抽取出来，为决策提供 依据，从而使数据库作为一个丰富可靠的资源为知识归纳服务【l j 。 聚类是数据挖掘研究中的一个重要的研究方向。聚类分析的研究已有较长的历史， 几十年来，其重要程度及与其他学科的交叉特性得到人们的充分肯定。聚类也是模式识 别、图像处理等研究方向的重要内容之一，在分辨数据的内在关系方面具有非常重要的 作用。聚类分析在模式识别中的主要运用有字符识别、语音识别等。在机器学习中，聚 类算法主要应用于机器视觉和图像分割。图像处理中聚类用于数据压缩和信息检索，聚 类的另一个主要应用是数据挖掘( 多关系数据挖掘) 、时空数据库应用( g i s 等) 、序列和异 类数据分析等。另外，聚类在统计科学中还有应用。值得一提的是，聚类对地理学、地 质学、考古学、心理学、生物学以及市场营销等方面的研究也都有非常重要作用【2 羽。 在电子商务网站的建设中，聚类分析也发挥着很重要的作用。通过聚类分析获得浏 览行为相似的客户，并通过对客户的行为规律分析，可以更好地理解自己的客户，向客 户提供更实用的服务。此外在其他数据挖掘算法中( 如关联规则，分类) ，聚类分析还 可以作为预处理步骤。 聚类分析的应用十分的广泛，其中包括：市场营销、顾客分类、模式识别、生物研 究、空间分析、w e b 文档分类等。目前，聚类分析逐渐受到人们的重视，已经成为数据 挖掘研究领域中的一个十分活跃的研究课题。 1 - 2 国内外研究现状 1 2 1 数据挖掘的研究现状 数据挖掘( d a t am i n i n g ) 就是从大量的、有噪声的、不完全的、模糊的、随机的数 据中，获取有效的、新颖的、可理解的、但又是潜在有用的知识和信息的过程。还存在 很多和这一术语相近的术语，如决策支持、数据融合( d a t af u s i o n ) 、数据分析以及数 据库中的知识发现( k d d ) 等。在第1 1 届国际人工智能学术会议上第一次出现k d d 一词。到目前为止，美国人工智能协会已经召开了8 次国际k d d 研讨会，规模也发生 了很大的变化，由专题研讨会发展成国际学术大会，人数由原先的二三十人增加到七八 百人，论文收录比例也逐年提高，研究重点也从算法的发现逐渐转变为系统应用，并且 注重多种技术和方法的集成，以及多学科间的相互交叉。在其他专题会议上也把数据挖 掘列为议题之一，成为当前计算机科学与技术研究领域的一大热门。 1 9 9 7 年，亚太地区在新加坡组织了第一次有较大的p a k d d 学术研讨会。在澳大利 亚墨尔本召开的p a k d d 9 8 会议上收到了1 5 0 多篇学术论文，会议空前热烈【6 1 。 此外，在人工智能、模式识别、数据库、图像处理等研究方面的国际学术刊物上也 开辟了d m 的专刊或专题。在1 9 9 3 年，i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率 先出版了k d d 技术专刊，所刊出的论文代表了当时数据挖掘研究领域的最新动态和成 果，比较全面地阐述了k d d 系统理论方法、评价方法、k d d 应用系统设计方法，全面 讨论了数据库的动态冗余、不确定性和高噪声、空值等一些问题，k d d 系统与其它传 统的分析方法的区别与联系，如：数量统计、专家系统、神经网络、机器学习。其中的 六篇论文摘要也说明了数据挖掘在不同领域的具体应用。 不仅如此，在因特网上还有很多数据挖掘的电子刊物，其中最为权威的刊物为 k n o w l e d g ed i s c o v e r yn u g g e t s 。另一份在线周刊为1 9 9 7 年1 0 月开始出版的决策支持 ( d s ) 。在i n t e m e t 上，还有一个名为d me m a i lc l u b 的自由论坛，在论坛上人们可以 通过邮件讨论有关d m l 的热点话题。 在国外数据挖掘技术发展的比较迅猛，出现了许多从事相关工作的个人和研究小 组。1 9 8 6 年，q u i n l a n 在机器学习杂志上发表文章介绍了i d 3 算法。1 9 9 3 年，q u i n l a n 在机器学习规划专著中详细介绍了非常流行的决策树算法c 4 5 。同年a g r a w a l 等人 首先提出了一个重要的k d d 研究课题一关联规则。为了改善a p r i o r 算法的运算性能， 包括a g r a w a l 在内许多学者又提出了改进算法，p a r k 等人与1 9 9 5 年在s i g m o d 9 5 上提 2 出了一种基于散列( h a s h ) 技术来增强a p r i o r 算法的有效性。2 0 0 0 年，h a nj i a w e i 等人 提出了一种基于f p t r e e 的关联规则挖掘算法。另外h a r tj i a w e i 在信息网络分析、序列 和结构模式发现等方面作出了杰出的贡献。他们为数据挖掘的发展奠定了极其深厚的理 论基础。 与国外相比，国内对数据挖掘的研究较晚，没有形成整体科研力量。1 9 9 3 年国家自 然科学基金第一次支持该研究领域的研究课题。目前，国内的多家高校和科研单位对数 据挖掘进行了理论和实际应用的研究，这些单位包括清华大学、中科院计算技术研究所、 空军第三研究所、海军装备论证中心等。其中，北京系统工程研究所较深入地研究了模 糊方法在数据挖掘中的应用，北京大学进行了对数据立方体代数的研究，中科院、中国 科技大学、浙江大学、复旦大学、华中理工大学等单位开展了对关联规则算法理论的研 究；上海交通大学和南京大学等单位研究、探讨了w e b 数据挖掘以及非结构化数据的 知识发现。 最近，在g a r t n e rg r o u p 的高级技术调查中将人工智能和数据挖掘列为“未来三到 五年内将对工业产生深远影响的五大关键技术”之首，并且在未来五年内数据挖掘和并 行处理体系投资排在十大新兴技术前两位。根据最近这一组织的研究表明，“随着数据 传输、捕获和存储技术的不断发展，大型系统用户将更加地需要应用新技术来发现市场 以外的价值，采用更加广阔的并行处理技术来建立新的商业增长点。 1 2 2 聚类的研究现状 聚类算法可以分为：基于模型的方法、基于网格的方法、基于密度的方法、层次法、 分裂法。许多方法需要设定聚类数目和一些限制条件，而且初始状态的选择及参数的设 定能够影响到聚类结果。k - m e a n s 算法就是其中具有代表性的聚类算法。k - m e a n s 算法 是m a c q u e e n 提出的一种迭代下降聚类方法，在最小化目标函数的基础上将数据划分到 不同的簇中。该算法原理简单、能够处理大量数据，内存占用小，运行速度快，是目前 应用比较广泛的聚类算法之一。目前k - m e a n s 算法的研究主要体现在如下几个方面：算 法极值点的检测及收敛性的研究、抑制噪声能力的提高、聚类有效性研究、距离定义的 扩展、聚类准则的发展、数据类型与聚类空间的扩展、初始化方法的发展、寻优能力的 提高、与先验知识或其它算法相结合1 7 】等等。 但是k - m e a n s 算法存在如下不足：算法对初始值比较敏感，对不同的初始值，可能 导致不同的聚类结果；该算法是基于梯度下降的方法，由于目标函数局部极小值点的存 在以及算法的“贪心性”，算法容易陷入局部极小值从而得到一个局部最优解。 为了解决上述问题，有学者把群体智能算法引入到k 均值算法中【8 。1 1 ，如基于遗传 算法的聚类。通过交叉、变异等策略来提高算法的自适应能力，解决算法容易陷入局部 最优解问题，提高算法收敛速度。基于蚁群算法的聚类【l 厶1 3 l ，这些聚类算法利用蚁群算 法的并行计算，全局搜索等特点来避免算法陷入局部最优解，从而提高聚类质量。 以上研究表明，把人工智能方法运用于k m e a n s 算法中是一种发展趋势。粒子群算 法( p s o ) 是近年来才提出的仿生算法，其改进算法在聚类问题中得到了广泛运用，这 为解决聚类问题提供了新的思路【l 6 】。有的将p s o 算法运用到k m e a n s 聚类算法中， 提出p s o k - m e a n s 混合算法和g b e s tp s o 算法，克服k m e a n s 算法容易陷入局部最优解 的问题，提高k m e a n s 算法的收敛速度；或者把k - m e a n s 的聚类算法结果作为粒子群中 的一个粒子和利用新的聚类中心调整粒子位置；或者把p s o 算法引入到传统的聚类算 法中，提高算法的收敛速度，克服传统聚类算法存在的缺点。目前，利用遗传算法，粒 子群算法，蚁群算法来进行聚类挖掘，取得一系列较好的成果，而能否达到一个稳定的 且可以收敛到全局最优的算法一直是研究的关键点。 1 3 本文工作 本论文从两个方面，对p s o 算法进行了改进，并把改进的算法运用到k - m e a n s 聚 类算法中。第一种算法通过调整调节因子来改变粒子的认知性和社会性，通过惯性权重 来调整种群的多样性，同时在粒子趋同时引入粒子变异来提高粒子群的探索能力，克服 算法陷入到局部最优解，从而使算法能够稳定地收敛于全局最优。在聚类过程中，该算 法以总类内离散度和的倒数为策略，找出对聚类有较大影响的样本，将它重新划分到其 它类中，以这种思想来寻找全局最优值，使种群能够向全局最优进化，实验表明，该算 法具有很好的稳定性。第二种算法是采用计算量小的平均偏差作为描述种群多样性的指 标，在种群早熟收敛时通过粒子变异改变种群的多样性。然后再采用内部空间特性对粒 子进行扰动，这些措施的实施克服了粒子群的早熟收敛现象，提高了算法搜索的准确性。 本文主要工作体现在以下几个方面： ( 1 ) 本文采用粒子变异、惯性权重自适应调节等技术，较好地平衡了p s o 搜索过 程中的开发和探索，从而保证了粒子群算法稳定且收敛到全局最优。 ( 2 ) 引入新的种群多样性测度指标和内部空间特性来提高聚类效果。 ( 3 ) 计算机仿真，使用v c 一6 0 工具对提出的算法进行模拟实现，对给出算法并结 4 合已有的成果进行比较，分析算法的优劣性。 1 4 论文结构 本文包括五章内容，其组织结构如下： 第一章介绍了数据挖掘和聚类算法的研究背景和意义，交待了论文的组织结构， 便于读者把握各章节之间的内容及其相互关系。 第二章介绍了聚类的相关概念、聚类分析的过程、分类、应用以及本论文采用的 基本聚类方法k - m e a n s 算法，为后续章节奠定理论基础。 第三章为了研究带变异粒子群的k m e a n s 聚类，本章首先介绍了粒子群算法的研 究背景、粒子群算法原理，然后给出了算法个参数的调整策略，最后讲述了算法的实现 过程和对比实验。 第四章阐述本文提出的基于种群多样性的p s o 聚类算法。该算法通过引入惯性权 重自适应调整、粒子变异以及内部空间特性对粒子进行的扰动策略克服粒子收敛于局部 最优解，从而提高聚类效果。 第五章主要总结本文所做的工作，并且指出了算法还有很多要改进的地方和可以 展开的下一步的深入研究。 5 2 1 聚类概述 2 1 1 聚类的概念 第二章聚类 聚类分析也称为无监督学习，或无指导学习，或无教师学习，与分类学习相比，聚 类分析不依靠标有类别的学习训练样本集合，样本类别由聚类学习算法自动确定。聚类 分析是研究如何在没有训练样本情况下把样本集划分为若干类。 聚类( c l u s t e r i n g ) 是把一组数据按照差异性和相似性归为若干类别过程。聚类分 析存在多个目标，但都涉及把一个样本集合分割或分成为簇( c l u s t e r ) 或子集。簇是 被划分到同一类别的数据样本集合。与其他簇中样本之间的相关性相比，每个簇内部的 样本之间的相关性更强，即属于同一个簇的任意两个样本之间具有较大的相似性，而属 于不同簇的两个样本间的差异性较大n 刀。相似性可以由样本的属性值计算得出，样本间 的距离是经常采用的一种测度。在实际的运用中，一般是把一个簇中的数据对象作为一 个整体。由于用聚类生成的簇来表示数据集，这样必定会丢失一些信息，但是这样可以 使问题得到一定地简化。从统计学角度来看，聚类分析可以看作是一种通过数据建模简 化数据的方法。 了解聚类与分类分析之间的区别有十分重要的意义。通常，为分类提供一些已标记 的类别的样本，待解决的问题是为一个新的无标记的样本进行标记类别。在很多情况下， 先从训练样本的属性中发现样本的一般分类规则，反过来再根据这些规则对非训练样本 标记一个新模式。在分类学习中，事先知道数据库中存在哪些类别，要解决的问题就是 将每一个样本属于哪一类别给标记出来。聚类分析的问题是将数据库中无标记的模式划 分为或干聚类，聚类是预先不知道数据库中样本可以划分的类别数，希望将所有的样本 划分到不同的类别中，并且使得同一个聚类内的数据对象具有较高的相似度，而不同聚 类中的数据对象则是不相似的。 聚类主要处理的数据类型包括以下几种：二值变量、比例标度型变量、区间标度变 量、序数型变量、标称变量、以及由这些类型构成的复合类型。 作为统计学的研究领域之一，聚类分析已经经历了多年，研究成果主要体现在基于 相似系数和基于距离的聚类算法。传统的基于统计学的聚类分析方法包括模糊聚类、有 6 重叠聚类、有序样本聚类、动态聚类法、加入法、分解法和系统聚类法；采用k - m e a n s 、 k - m e d o i d s 等算法。在神经网络算法中，聚类方法包括竞争学习网络、有组织神经网络 方法等。 从计算智能的角度讲，簇可以看作隐藏模式。聚类是搜索簇的无指导学习过程。与 分类学习不同，无指导学习不依赖预先给定的带有类别标记的训练样本，而是由聚类学 习算法自动确定类别标记，而分类学习的训练样本给出了类别标记。聚类是无指导学习， 而不是示例式的学习。 2 1 2 聚类算法性能评价 随着聚类分析的广泛应用和研究工作的不断深化，基于各种方法的聚类算法不断出 现。但是，到目前为止还没有发现一种算法可以适用于所有类型的数据。所以，对于具 体的应用场合，了解并选择合适的聚类算法是十分重要的。在思考具体的聚类算法时， 一般依据以下的评价标准来衡量一种聚类算法的适应性及优劣性n 7 1 。 1 输入顺序的敏感程度 有些聚类算法对样本数据的输入顺序敏感，对同一样本集按不同的输入顺序提交， 聚类算法会产生明显不同的聚类结果。即，对同一个数据库中样本，把它们以不同的顺 序输入到聚类算法，得到不同的结果，这种情况是不希望发生的。为了得到一个稳定的 聚类结果，应该研究输入数据顺序不会影响聚类结果的算法。 2 异常数据的处理 来自应用领域的数据集难免包含噪声数据，例如，空值、错误数据、孤立点或未知 数据等。如果聚类算法不能有效地处理这些数据，就有可能导致聚类结果不正确。因此， 在处理孤立点时，要求尽量降低或排除孤立点对聚类的影响。在解决一些实际问题上， 聚类算法应该能够自动过滤噪声数据并产生正确的聚类结果。 但是，从另一个方面上看，某些实际问题又要求聚类算法在运行的过程中，能够正 确地发现孤立点，如欺诈检测。 3 可伸缩性 数据挖掘领域的研究主要面向海量数据库，因此可伸缩性是一项基本要求。可伸缩 性是指算法对数据集规模的适应能力。比如在处理上百万记录的数据库时，算法的时间 复杂度不能太大，最好是多项式时间复杂度。很多的聚类算法在解决小规模的数据库问 题上有效。但随着数据仓库、大型数据库的广泛使用，对处理大数据量的数据库对象时 7 许多原有的聚类算法将因为产生偏差或出现错误结果而无法使用。因此可以这么说，实 践要求聚类算法具有可伸缩性。 4 发现任意形状聚类的能力 许多聚类算法是采用距离来度量样本之间的相似性。例如，采用欧式距离来刻画数 据对象间的相似度。这一类算法通常只能发现球状的、密度和大小很相近的聚类。但是， 数据库中实际存在的簇的形状可能是不同的。簇的密度差异较大，大小也不尽相同。因 此，实践要求算法不仅能发现球形聚类，还能对任意形状的聚类加以定义并发现。 5 处理不同类型属性的能力 算法在处理数值型数据的同时，还要有处理其他类型数据的能力。目前，虽然有许 多处理数值型数据的聚类算法，但现实中还存在需要对其他类型的数据进行聚类，如： 序数型、分类型、布尔型和混合型等。 6 对输入参数的依赖性 许多算法依赖于一组事先给定的阈值或参数，如密度阈值、相似性阈值、聚类的数 目等。聚类结果对输入的这些参数十分敏感，如果输入的参数稍微改变可能导致聚类结 果发生很大变化。在处理高维数据时，这些参数又是很难确定的。此外，参数设置增加 了用户的负担，也难以保证聚类的效果。针对这个问题，一个好的聚类算法应该给出一 个好的解决方案。 7 处理高维数据的能力 大型数据仓库或数据库一般会含有若干个属性或维。一个数据仓库或数据库都有很 多的字段，即数据为高维数据。较早提出的聚类算法主要针对低维数据，这些聚类算法 在处理低维数据集时效果不错，例如，二三维的数据，但是在处理高维数据时准确率就 没有那么高了。所以对于研究高维数据的聚类算法难度较大，特别是在考虑到高维空间 的数据分布特点。高维数据的分布特点包括：稀疏性、高度倾斜、并且形状极其不规则 等。目前，许多学者已经提出了解决高维数据问题的聚类算法。 8 处理限制条件的能力 在实践中，限制条件可能会有很多，一个优秀的聚类算法，在考虑到这些限制条件 时，仍然表现较好。 9 结果的可解释性 由于聚类结果最后都要提交给用户，因此，聚类的结果需要是可用的、可解释的、 可理解的。这就需要聚类算法要与一定的语义解释及语义环境相关联。相关领域知识对 8 于聚类算法的设计影响很大，并且是一个重要研究方面。 2 2 足巨离禾口相似系数 为了对数据集进行聚类分析，就需要分析样本之间的相似度，一般情况下，相似度 的测度方法有两种。一种方法是使用相似系数。彼此相近的样本之间，它们间相似系数 的越接近1 ，而彼此无关的样本之间，它们间相似系数越接近于0 。比较相似的样本被 划分为一类，不怎么相似的样本划分到不同的类中；另一种方法是将一个样本看作d 维 空间中的一个点，并且在空间中定义数据对象间的距离，距离越近的点划分到同一个类 中，距离较远的点划分到不同的类中。 设有甩个样本，每个样本有p 维属性，则胛个样本对象所有的p 个属性的观测值可 用如下矩阵来表示： x = 一般称上式为样本数据矩阵，其中而( 江1 ，2 ，n ；j = l ，2 ，p ) 为第f 个样本的第，维 的观测值。矩阵x 的第f 行给出了第f 个样本数据薯，所以任意两个样本间以与而之间 的相似度，可以通过样本数据矩阵x 中的第k 行与第，行的相似程度来表示， 1 k r l ，1 ，1 1 ，k ，。 2 2 1 距离 距离是表示样本间相似度的一种测度，显然，样本间的距离确定后，二者之间的距 离越大，其相似度越小，否则相似度越大。 假设要考虑的刀个样本为五，恐，吒，令吃表示样本_ 与之间的距离。如果把任 意两个样本之间的距离计算出来，可排成如下所示的距离阵d ： 9 d = 碣。盔：4 。 以。以：丸 其中磊，= 如= 吒= 0 。由于以是一个实对称矩阵，所以只须计算下三角或上三角 部分