（计算机应用技术专业论文）聚类算法的研究及应用基于群智能技术的聚类算法研究.pdf

摘要 摘要 数据挖掘是在海量的数据中寻找模式或规则的过程。数据聚类则是数据挖掘中的一 项重要技术，是人们认识和探索事物之间内在联系的有效手段，它既可以作为独立的数 据挖掘工具，从知识库中获取数据分布的一些深入信息，也可以作为其它数据挖掘算法 的预处理步骤，且广泛应用于商务管理、市场分析、工程设计和科学探索等领域。聚类 就是将数据对象划分到不同的类或者簇中，使得属于同簇的数据对象相似性尽量小，而 不同簇的数据对象相异性尽量大。 蚁群算法和粒子群优化算法是群智能理论研究领域的两种主要算法。蚁群算法源于 蚂蚁堆积他们的尸体和分类它们的幼体的研究，粒子群算法源于鸟群群体运动行为的研 究。作为新兴的演化计算技术，群智能算法已成为越来越多研究者的关注焦点，并被引 进到数据聚类领域里且发挥了巨大的作用。但由于蚁群算法和粒子群算法还不够完善， 在数据聚类的处理过程中存在智能算法自身的缺陷，导致聚类效果的差强人意，因而如 何设计出行之有效的聚类算法将成为群智能理论在聚类领域发展的一个重要课题。 针对基本蚁群聚类算法较长时间开销和易产生冗余聚类数目的缺陷，提出了一种聚 类邻域自适应调整的多载蚁群算法。算法通过邻域动态自适应调整寻找纯净的邻域，增 强蚂蚁记忆体记忆纯净邻域的大小，蚂蚁之间协同交流进行多载整合相似邻域形成最终 聚类结果。实验结果表明新算法能有效提高算法效率且取得较好的聚类效果。 针对k 调和均值和混沌粒子群聚类算法的优缺点，本文提出了种融合k - 调和均 值的混沌粒子群聚类算法。首先通过k 调和均值方法把粒子群分成若干个子群体，每 个粒子根据其个体极值和所在子种群的全局极值来更新位置。其次，算法中引入变尺度 混沌变异，抑制了早熟收敛，提高了计算精度。实验证明，该算法可以有效避免算法陷 入局部最优，在保证收敛速度的同时增强了算法全局搜索能力，明显改善了聚类效果。 关键词：数据挖掘，聚类，蚁群算法，粒子群算法，k - 调和均值，混沌优化 a b s t r a c t d a t am i n i n gi sap r o c e s st h a ti nt h ev a s ta m o u n t so fd a t al o o k i n gf o rp a t t e r n so r r u l e s d a t ac l u s t e r i n gi sa l li m p o r t a n td a t am i n i n gt e c h n o l o g yf o rp e o p l et ou n d e r s t a n da n d e x p l o r et h ei n h e r e n tr e l a t i o n s h i pb e t w e e nt h i n g s i tc a nb eu s e d 嬲i n d e p e n d e n td a t am i n i n g t o o l st og e ts o m ei n - d e p t hi n f o r m a t i o nf r o mt h ek n o w l e d g eb a s e ，b u ta l s oc a nb eu s e d 鹤t h e p r e t r e a t m e n ts t e pf o ro t h e rd a t am i n i n ga l g o r i t h m s i ti sw i d e l yu s e di nb u s i n e s sm a n a g e m e n t ， m a r k e ta n a l y s i s ，e n g i n e e r i n gd e s i g na n ds c i e n t i f i ce x p l o r a t i o na n do t h e rf i e l d s c l u s t e r i n gi st o p a r t i t i o nd a t ao b j e c t si n t od i f f e r e n tc a t e g o r i e s ，o rc l u s t e r s ，m a k i n gt h es i m i l a r i t y 、) r i t l lt h e c l u s t e r so fd a t a 部s m a l l 勰p o s s i b l e ，w h i l et h ed i s s i m i l a r i t yo fd i f f e r e n tc l u s t e r so fd a t a 嬲 l a r g e 嬲p o s s i b l e a n tc o l o n ya l g o r i t h ma n dp a r t i c l es w a r mo p t i m i z a t i o na r et h et w om a i na l g o r i t h m si nt h e f i e l do fs w a r mi n t e l l i g e n c e a n t c o l o n ya l g o r i t h mo r i g i n a t e s f r o mt h e s t u d yo nt h e a c c u m u l a t i o no ft h e i rb o d i e sa n dc l a s s i f i c a t i o no ft h e i rl a r v a e p a r t i c l es w a r mo p t i m i z a t i o n o r i g i n a t e sf r o mt h es t u d yo nt h eg r o u pm o v e m e n tb e h a v i o ro fb i r d s a san e we v o l u t i o n a r y c o m p u t a t i o nt e c h n i q u e ，s w a r mi n t e l l i g e n c ea l g o r i t h mh a sb e c o m em o r ea n dm o r er e s e a r c h e r s f o c u so fa t t e n t i o n , a n dw a si n t r o d u c e dt ot h ef i e l do fd a t ac l u s t e r i n ga n dp l a y sah u g e r o l e h o w e v e r , a n tc o l o n ya l g o r i t h ma n dp a r t i c l es w a r mo p t i m i z a t i o ni ss t i l ln o tp e r f e c t , t h e r e e x i s t st h e i ro w ni n t e l l i g e n c ed e f i c i e n c i e si nt h ep r o c e s so fd a t ac l u s t e r i n g ，r e s u l t i n gi n u n s a t i s f a c t o r y , c l u s t e r i n ge f f e c t t h u sh o w t od e s i g ne f f e c t i v ec l u s t e r i n ga l g o r i t h mw i l lb ea n i m p o r t a n tt o p i ci nt h ef i e l do fs w a r mi n t e l l i g e n c et h e o r yi nt h ed e v e l o p m e n to fc l u s t e r i n g a i m e dt os o l v et h ep r o b l e mt h a tt h ea n t - b a s e dc l u s t e r i n ga l g o r i t h me x p e n s e sal o n gt i m e a n de a s i l yp r o d u c e sr e d u n d a n tn u m b e ro fc l u s t e r s ，an e wm u l t i l o a d i n ga n tc o l o n yc l u s t e r i n g a l g o r i t h mb a s e do nd y n a m i cn e i g h b o r h o o di sp r o v i d e d t h ea l g o r i t h ms e e k sf o rt h ep u r e n e i g h b o r h o o dt h r o u g ht h en e i g h b o r h o o dd y n a m i ca u t o - a d a p t e da d j u s t m e n t ，e n h a n c e sa n t s m e m o r yt os t o r et h es i z eo ft h ep u r en e i g h b o r h o o d ，e x c h a n g e st h ei n f o r m a t i o nb e t w e e na n t s ， m u l t i l o a d sa n dm e r g e st h es i m i l a rr e g i o n st of o r mt h ef i n a lc l u s t e rr e s u l t e x p e r i m e n ts h o w s t h a tt h en e wa l g o r i t h me f f e c t i v e l ya d v a n c e st h ee f f i c i e n c yo fa l g o r i t h ma n dt h er e s u l to f c l u s t e r i n g i nv i e wo ft h ea d v a n t a g e sa n dd i s a d v a n t a g e so fk - h a r m o n i cm e a n sa n dc h a o sp a r t i c l e s w a r mo p t i m i z a t i o nc l u s t e r i n ga l g o r i t h m ，ac h a o sp a r t i c l es w a r mo p t i m i z a t i o nc l u s t e r i n g a l g o r i t h mm e r g e d 、航mk - h a r m o n i cm e a n s i sp r o v i d e d p a r t i c l es w a r mw a sf i r s t l yd i v i d e di n t o s u b - g r o u p s ，r e s u l t i n gi na ni t e r a t i v ep r o c e s sf o re a c hp a r t i c l eb a s e do ni t se x t r e m ev a l u ea n d l o c a t i o no ft h ei n d i v i d u a ls u b - p o p u l a t i o n si nt h eg l o b a le x t r e m u mt ou p d a t et h e i rp o s i t i o n s e c o n d l y , t h ei n t r o d u c t i o n o fv a r i a b l e - s c a l ec h a o t i cm u t a t i o n , i n h i b i tt h e p r e m a t u r e c o n v e r g e n c ea n di m p r o v et h e c a l c u l a t i o na c c u r a c y t h en e wa l g o r i t h mc a na v o i dt h e a l g o r i t h mi n t o al o c a lo p t i m u m ，g u a r a n t e et h e c o n v e r g e n c es p e e dw h i l ee n h a n c i n gt h e c a p a c i t yo fg l o b a ls e a r c ha l g o r i t h m s ，i m p r o v et h ec l u s t e r i n ge f f i c i e n c y k e y w o r d s ：d a t am i n i n g ，c l u s t e r , a n tc o l o n ya l g o r i t h m ，p s o ，k h a r m o n i cm e a n s ，c h a o s o p t i m i z a t i o n l i 目录 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 论文的研究背景及选题意义1 1 2 国内外研究现状及发展趋势2 1 2 1 国内外研究现状2 1 2 2 未来发展趋势2 1 3 本文的研究内容和结构安排3 1 3 1 研究内容3 1 3 2 结构安排3 第二章群智能聚类算法5 2 1 数据挖掘5 2 1 1 数据挖掘的定义5 2 1 2 数据挖掘常用的方法5 2 2 聚类分析7 2 2 1 聚类分析的定义7 2 2 2 传统聚类分析方法7 2 2 3 聚类分析的度量标准9 2 3 群智能算法1 1 2 3 1 群智能概念和特点1 1 2 3 2 蚁群算法1 2 2 3 3 粒子群算法1 6 第三章聚类邻域自适应调整的多载蚁群算法1 9 3 1 算法思想：1 9 3 2 相关概念2 0 3 3 算法改进2 l 3 3 1p i c k d r o p 策略改进2 l 3 3 2 蚂蚁多载2 1 3 3 3 增强蚂蚁记忆体2 1 3 3 4 协同交流2 2 3 4 算法实现过程2 2 3 5 仿真实验2 3 3 5 1 测试数据2 3 3 5 2 评价标准2 3 3 5 3 仿真结果2 3 目录 3 5 4 本章结论2 5 第四章融合k - 调和均值的混沌粒子群聚类算法2 7 4 1 算法思想2 7 4 2 粒子群聚类算法2 8 4 3k 一调和均值算法2 9 4 4 混沌优化3 1 4 5 算法改进3 2 4 5 1 简化粒子群优化算法3 2 4 5 2 惯性权重动态调整3 3 4 5 3 早熟判断3 4 4 5 4 变尺度混沌搜索3 5 4 6 粒子编码及算法进程描述3 5 4 7 仿真实验3 6 4 7 1 评价标准3 6 4 7 2 仿真结果3 7 4 7 3 本章结论3 8 第五章总结与展望3 9 5 1 总结3 9 5 2 展望3 9 致谢4 0 参考文献4 1 附录：作者在攻读硕士学位期间发表的论文4 5 i i 第一章绪论 第一章绪论 1 1 论文的研究背景及选题意义 近年来，伴随计算机与信息技术的高速发展和广泛使用，数据库应用的规模、范围 和深度逐步扩大，进而积累了海量的、以多种形式存储的数据资料。在这些海量数据中 往往隐含着各种各样的凭人们直觉与经验难以发现的重要信息。如何有效利用这一丰富 数据海洋的宝藏并从中获取有价值的信息为人类服务，单凭传统的数据库技术已不能满 足这种需求了，业已成为广大信息技术工作者的所重点关注的热点之一。来自数据的迅 速增加和数据分析处理方法的滞后之间矛盾越来越大，人们面临的主要困境将不再是缺 乏足够的信息可以利用，而是如何有效地利用浩瀚数据海洋里的这些复杂数据，希望能 够在对已有的大量数据分析的基础上进行科学探索、医学研究或企业管理等等，从而达 到为决策服务的目的。 于是，人们汲取统计学、数据库、机器学习等技术，提出了信息技术发展过程中的 关键技术：数据挖掘。数据挖掘应运而生，并显示出前所未有的强大生命力，它是一个 利用各种分析工具在海量数据中发现模型和数据间关系的过程，这些模型和关系可以用 来预测和决策；它也是一种发现知识的应用，是一个提取有用信息的过程。数据挖掘技 术逐渐成为研究的热点，吸引了大量研究工作人员来进行探索，引起了国内外学术界的 广泛关注，许多研究机构都在该领域开展了多种形式的研究工作。 聚类分析是数据挖掘研究中一个富有挑战且相当活跃的研究课题，可以用于从大量 数据中寻找隐含其中的数据分布和模式1 1 1 。聚类是当前数据挖掘领域中的一个重要分支， 是人们认识和探索事物之间内在联系的有效手段，它既可以作为一种独立的数据挖掘工 具从大量数据集中智能、自动地提取出有价值的分类知识，获得数据分布的状况，观察 每个簇之间的区别点，并对某些特定的聚簇集合作进一步分析；也可以作为数据挖掘算 法中其他分析算法( 如分类和定性归纳算法) 的一个预处理步骤，这些算法可以在聚类 生成的簇上进行进一步处理。 对于聚类的研究始于2 0 世纪6 0 年代初，从统计学的观点看，聚类分析是通过数据 建模技术来简化海量数据的一种方法。从机器学习的观点来看，聚类是一种无人监督的 学习过程，因为它没有关于分类的先验知识，由聚类算法自动确定标记簇，是观察式学 习。从实际应用的观点来看，聚类在科学探索、医学诊断、信息检索、商业决策、客户 关系管理( c 砌旧、人力资源管理、生物学等等领域都起着非常重要的作用1 2 j 。 聚类分析在研究发展过程中已经取得了丰硕的成果，尤其随着数据挖掘技术的广泛 应用，聚类的研究对象也随之更加丰富，不断涌现出新的聚类算法。但不同的算法的诞 生来自不同的应用背景，有的适用于大数据集，可以发现任意形状的聚类，可以发现噪 声点；有的算法思想简单，适用于小数据集，它们都试图从不同的角度、不同的途径实现 对数据集进行高效、可靠的聚类。这就要求对现有的聚类算法进行改进，尤其结合目前 流行的群智能技术不断提出新的聚类理论和方法以适应新的应用。 江南大学硕士学位论文 群智能可被描述为一些相互作用相邻个体的集合体的信息交互过程，鱼群、蜂群、 蚁群、鸟群等都是人工智能的典型例子。信息的交互过程表现在群体信息的沟通、群体 内部的个体根据所获得的环境信息以及附近其它个体的信息来改变自身的信息，因而就 使得群体涌现出单独个体所不具备的能力和群智能的性质，为在没有集中控制并且不提 供全局模型的前提下寻找复杂问题的求解方案( 无监督聚类) 提供了开阔的思路。 目前，日益发展壮大的群智能理论和应用研究足以显示出群智能方法是一种能够有 效解决大多数优化问题的新途径，尤其是群智能潜在的并行性和分布式特色为处理海量 繁杂的数据提供了技术保证( 数学建模和计算仿真) 。不论是从理论研究还是实际应用 的角度分析，数据挖掘中的聚类分析适用群智能技术都具有非常重要学术意义和现实价 值的。 1 2 国内外研究现状及发展趋势 1 2 1 国内外研究现状 聚类分析作为数据挖掘的一个重要分支，已被广泛地研究和使用了多年，运用于各 行各业，例如图像识别、物种筛选等等，逐步成为许多领域的有用工具。含有k m e a n s 算法、k m e d o i d s 算法以及其他一些成熟方法的聚类分析工具已经被融入到许多统计分 析软件包或系统中。 在机器学习领域，聚类是无监督学习的。与分类不同，聚类等无监督学习不依赖于 预先准备好的类或带类标号的训练实例，正是如此，聚类不是示例式学习，而是观察式 学习。为了使聚类方法的适应性更强、性能更高，得到更广泛的使用，可以将其他领域 中的技术融入聚类方法中，弥补基础聚类方法的某些缺陷，更加充分的发挥聚类方法的 最优性能。常引进的一些著名方法有：遗传算法、蚂蚁算法、粒子群算法、免疫算法等。 近年来，群智能技术与聚类分析的结合越来越多，不断有新的模型、新的理念产生， 足见群智能技术在聚类领域的发展前景和广阔空f 日q t 3 1 。尤其较成熟的群智能算法：蚁群 算法和粒子群算法，它们的介入聚类领域对聚类技术的提升和自身的发展都带来了可见 的益处。因为相当一部分基础聚类算法都要求用户提供一定的聚类先验知识，如希望产 生的类别数目，从而导致聚类结果对输入的参数十分敏感，这在很大程度上局限了算法 的适应性，特别是包含高维数据的数据集更是如此。而基于蚁群或粒子群的聚类算法最 大的优点就是无需先验信息的设置，从而减轻了用户的负担，并改善了聚类结果。蚁群 或粒子群聚类方法是一种非常有效的随机搜索机制，尽量避免陷入局部最优，足以保证 算法运行的准确性和一致性，在可行性、运行效率、求解精度或实现简单性方面都做得 非常出色。 1 2 2 未来发展趋势 聚类技术是一个充满希望而富有挑战的研究领域，许多科研专家的看法使人们坚信 聚类技术将是信息化一个应用点的价值所在，而且它将会不停地向前发展，每年诞生出 2 第一章绪论 新的聚类理论和模型，人们对它的研究利用正日益广泛和深入。相信实际应用需求的广 阔前景会使聚类分析技术有一个辉煌灿烂的明天。 群智能是近年来人工智能研究和应用的一个热门话题，尤其在数据挖掘聚类分析方 面的理论研究和实际应用，因为群智能聚类对算法使用者的经验要求较低。设计基于群 智能技术的聚类算法必须简单有效，因为这样的算法才具备推广性和实用价值，许多群 智能聚类算法不成功的原因就在于他们对于自然、社会生活现象过于复杂的模拟。由于 群智能聚类技术是模拟生物的群落社会性，因而其相关数学理论基础还比较薄弱，导致 了现有研究存在的一些问题。未来的群智能聚类算法将更加注重数学理论基础的夯实， 使之具备普遍意义上的理论性分析，依据确切的理论依据来设置算法中涉及的各种参 数，而不再按照经验型方法来确定，降低对具体问题和应用环境的依赖性；群智能聚类 与其它各种先进技术( 如：模糊逻辑、神经网络、禁忌搜索和支持向量机等) 的融合将更 加紧密1 4 】。聚类分析与群智能的结合将提出很多新概念、新理论、新方法和新技术，开 辟出一个全新的领域，开辟出更多新的研究路径，在以后的发展中取得重大成就。 1 3 本文的研究内容和结构安排 1 3 1 研究内容 本文致力于研究基于蚁群和粒子群算法的聚类算法。 一、蚁群聚类算法一般对要处理的聚类分析问题没有依赖性，聚类的数目能够自动 生成，对噪声数据和异常值的处理也能满足一定的要求。但在追求聚类准确度和精度的 同时，同时也造成了算法运行效率较低、聚类数目冗余的现象，且算法的环境参数的配 置仍需经验知识。本文对该算法进行改进并提出了一种聚类邻域自适应调整的多载蚁群 算法。算法充分利用蚂蚁所携带的信息进行数据的搬运和合并，在算法运行过程中增强 蚂蚁的记忆并适时进行沟通、协调，实现了相似对象越聚越多，不相似对象互不交叉， 体现了算法的良好的聚类效果。 二、粒子群算法原理简单、易于实现，且精度较好、容易理解，在聚类分析方面有 独到的优势，但粒子群算法高收敛性的同时携带了局部收敛早熟的问题。借用混沌优化 算法的高效全局搜索能力和k - 调和均值算法的高收敛速度的优点，本文提出一种融合 k 调和均值的混沌粒子群聚类算法。算法首先随机初始化每一个样本的类别并生成初始 粒子群的位置编码，然后交替进行k 调和均值算法和粒子群算法迭代，并且对陷入早 熟收敛的粒子个体产生变尺度混沌扰动，跳出局部最优。新算法具有很好的全局收敛性， 能够较快地收敛到最优解。 1 3 2 结构安排 本文首先对数据挖掘及聚类算法的研究现状进行了概述，接着在提出数据挖掘、聚 类分析基本概念的基础上，对数据挖掘的过程、对象、任务等问题及常用聚类算法进行 了详细的论述，然后重点介绍了数据挖掘中的聚类分析技术和各种改进思想及智能聚类 江南大学硕士学位论文 算法的原理，在前两章综述的基础上，将蚁群、粒子群算法应用于聚类分析技术，并进 行了相关的实验，最后进行了总结及展望。 本文的组织结构如下： 第一章首先简要分析了本文的研究背景及意义，接着介绍了数据挖掘及聚类算法的 国内外研究现状以及今后的发展趋势，同时给出了本文的主要内容安排。 第二章首先介绍了数据挖掘和聚类分析的定义，以及数据挖掘的常用方法和常用聚 类分析算法，接着详细讨论了群智能理论以及其在聚类算法中的应用，并着重介绍了群 智能聚类算法中的蚁群、粒子群聚类算法。 第三章对基于蚁群算法的聚类技术进行了研究探讨，给出了聚类邻域自适应调整的 多载蚁群算法，并通过实验结果数据对比分析，新算法既提高了聚类的效率，也降低了 冗余聚类数目的形成，显著改善了聚类的效果。 第四章对基于粒子群算法的聚类技术进行了研究探讨，给出了融合k 调和均值的 混沌粒子群聚类算法，并通过实验结果数据对比分析，新算法相对于其它算法，不仅能 更快地达到收敛，而且在收敛精度上也有所提高。 第五章主要是对研究工作的总结，并指出还需解决的问题和进一步的研究方向。 4 第二章群智能聚类算法 第二章群智能聚类算法 2 1 数据挖掘 2 1 1 数据挖掘的定义 数据挖掘，也叫做在数据中的知识发现或知识发现和数据挖掘，实质上是知识发现 技术在数据库领域中的应用，它是指从大量的、不完全的、有噪声的、模糊的、随机的 数据中，高度自动化提取隐含在其中的、人们事先不知道的、但又是潜在非常有用的信 息和知识的过程，提取的知识表示为概念( c o n c e p t s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、 模式( p a t t e r n s ) 等形式【5 。 这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的，这些数据可 以是结构化的，如关系数据库中的数据，也可以是半结构化的，如文本、图形、图像数 据，甚至是分布在网络上的异构型数据；发现的是用户感兴趣的知识，发现知识的方法 可以是数学的，也可以是非数学的，可以是演绎的，也可以是归纳的；发现的知识要可 接受、可理解、可运用，并不要求发现放之四海皆准，实际上，所有发现的知识都是是 有特定前提和约束条件的、相对的、面向特定研究问题的。发现了的知识可以被用于信 息管理、医学研究、工程设计、决策支持等，还可以进行数据自身的维护。因此，数据 挖掘是- - f 7 交叉学科，它把人们从低层次的简单的数据查询应用要求，提升到从数据中 挖掘知识，提供决策支持。 数据挖掘系统的输入是数据库的数据、信息分析员的指导以及存储在挖掘系统知识 库中的知识和规则。选择的数据在各种挖掘模块中处理，生成辅助模式和关系。然后进 行评价，通过与分析员交互以期发现令人感兴趣的模式。有的还要加入知识库中，以便 后继的抽取和评价( 见图2 1 ) 。 图2 - 1 数据挖掘的逻辑模型 f i g 2 - 1l o g i c a lm o d e lo f d a t am i n i n g 2 1 2 数据挖掘常用的方法 进行数据分析时，分类、回归分析、聚类、关联规则、特征、变化和偏差分析、 w e b 页挖掘等是数据挖掘常用的方法，它们从不同的角度分别对数据进行挖掘1 6 】。 分类。分类就是根据数据库中数据对象的某些属性值找出它们之间的共同特点并 按照分类模式将它们划分为不同的类，其目的是通过分类模型将数据库中的数据项映射 到给定类别的中的某一个类别。在实际使用上，既可以通过此模型分析现有的数据，也 江南大学硕士学位论文 可以用它来预测未来的数据。典型的用于预测数据的分类器就能够把数据库中的数据记 录通过某个函数或模型映射到某个预定义的类。数据挖掘分类算法的工作途径就是通过 分析己知分类信息的历史数据从而归纳出一个预测模型，这里用于建立模型的数据称为 训练集，通常是以往的一些经验数据。 回归分析。回归分析方法是在分析事务数据库中属性值在时间上的特征的基础上 建立一个将数据项映射到一个实值预测变量的函数，并将此函数作为预测模型，发现变 量或属性间的依赖关系，其主要研究方面包括数据序列的趋势、数据序列的预测以及数 据间的相关影响因素等。它可以应用到市场营销的各个方面，如客户拓展、保持和预防 客户流失活动、增长销售额、解释市场占有率、发现品牌偏好及提高市场营销效果等。 聚类。聚类分析就是在相似的基础上收集数据来分类，把一组数据按照相似性和 差异性分为多个类别，其目的是使得属于同一类别的数据间有很大相似性，不同类别中 的数据间有很大相异性。与分类不同的是，在开始聚集之前，人们不知道如何分开数据， 也不知道要把数据分成几组。聚类和分类的区别是聚类不依赖预先定义的类或带类标记 的训练实例，不需要先验知识，它可以应用到客户群体的分类、动植物基因分类、网络 文档归类、保险市场的细分等。 关联规则。关联规则是描述数据库中数据项之间的密切程度或关系，即通过对数 据库集的分析得出项目集中的项目之间的相关性，即隐藏在数据间的关联或相互关系。 一条关联规则可解释为：满足x 的数据集元组很有可能同时也满足y 。目前，关联技术 的主要应用于商业领域，通过分析交易数据库来知道销售、设计优惠券及其他市场决策 的制定。例如，分析美国加州某连锁店的销售记录可以发现男性顾客下班以后购买婴儿 尿布的同时往往也会购买啤酒。关联性规则是数据挖掘中相比较成熟的技术。关联技术 不但在商业领域中得到广泛的应用，也不断拓展到其它领域，比如工程设计、医疗保健、 金融证券分析等。 特征。从数据库中的某一组数据集中提取出关于这些数据内部之间共同的特征式 的行为就叫特征分析，当中这些特征式概括了该数据集的总体特征。如教学实践中，教 师可以把不同学习者的学习特征存入数据库，这样可以动态的掌握学习者的不同需求、 个性差异等信息，并以此为依据为不同学习者提供不同的学习内容及推荐个性化的学习 材料等服务项目，真正的实现教学方式个性化。 变化和偏差分析。数据库中的数据不时有一些异常记录，偏差分析就是从数据库 中检测出这些偏差的数据。偏差包括很大一类潜在有用的知识，如观测结果与期望的偏 离、分类中的反常实例，不满足规则的特例等，其目的是寻找观测结果与标准之间有意 义的变化偏差。工程项目实施中经常会用到偏差分析手段来对项目进度和费用进行综合 控制。偏差分析往往还应用到各种异常信息的发现、分析、评价和预警等方面。 w r e b 页挖掘。随着i n t e m e t w e b 技术的全球推广及迅速发展，w e b 上的信息量无 比丰富，人们已经无法从表面上看出它们所蕴涵的内在信息。如通过对w e b 挖掘统计 分析用户自建的r s s 、b l o g 等群体信息，能够帮助网络开发商以较低的成本准确的获得 客户兴趣倾向、个性化需求等信息以及将来作出如何开发新业务的规划。 6 第二章群智能聚类算法 2 2 聚类分析 2 2 1 聚类分析的定义 聚类分析又称群分析，是知识发现中一项重要研究内容。所谓类，通俗地说，就是 指相似元素的集合。所谓聚类，就是将一个数据单位的集合分割成几个称为簇的子集， 每个簇中的数据之间有较大的相似性 7 1 。聚类主要用于在潜在的数据中发现有价值的数 据分布和数据模式，是数据挖掘中一个重要的组成部分。聚类过程可以定义如下：给定 d 维空间的n 个数据点，根据数据点问的相似程度把这n 个点分成k 个簇，即满足相似 样本在同一簇中，相异样本在不同簇中，使得同一簇中的对象具有尽可能大相似性，而 不同簇中的对象具有尽可能大相异性。如果将含有n 个样本9o - - 9 h 的数据集x 聚成c 个子类a l ，a c ，则要求a 1 ，以c 满足： i x l u x 2 u ”c = x l 五n y ，= f ( 1 f j c )， ，、 数据聚类分析是根据事物各自的特性，根据“物以类聚”的道理，研究被聚类的对 象并进行类别划分的方法【8 】o 它是一种无监督学习方式，没有任何模式可供参考或依循， 主要解决如何在没有先验知识的情况下实现满足这种要求的聚簇的聚合的问题。聚类分 析起源于分类学，目前聚类分析在商务智能化中有着举足轻重的地位；哲学领域，聚类 可以完美的实现人格分类；在生物领域，利用生物的特点，可以一瞬间把成千上万种类 中的同一纲动物分为一类；在商业管理领域，面对数以万记的客户和商业事件资料，没 有一个智能聚类软件是很困难的。生活中到处都有聚类的影子，它离我们从不遥远。 聚类分析方法的选择取决于数据的类型、聚类的目的及应用，近年来涌现出了许多 聚类分析方法。由于各种聚类分析方法之间并不是完全独立的，互相之间彼此交叉，所 以很难对聚类分析方法进行严格意义上的划分，现就聚类分析方法的发展进程分为两 类：传统的聚类分析方法和新发展的聚类分析方法。这些方法涉及的领域遍布人工智能 科学的方方面面，而且在某些特定的领域中取得了较为理想的效果，现在聚类分析的理 论正在发展，内容不断得到丰富，研究的范围也在不断得到扩大。目前，聚类分析研究 己深入到数据库、数据分析、统计等领域并取得了很大的成就，聚类算法在金融投资、 卫星图像和信息检索等领域也有着广泛的应用。 2 2 2 传统聚类分析方法 1 划分法( p a r t i t i o n i n gm e t h o d s ) 给定一个包含n 个对象或数据行，划分法将构建数据的k 个子集( 划分) ，其中每 一个子集就代表一个聚类，k n 。而且这k 个分组满足以下条件：( a ) 每一个分组至少 包含一个数据对象；( b ) 每一个数据对象属于且仅属于一个分组。对于给定要构建的划分 的数目k ，算法首先创建一个初始的划分方法，以后通过反复迭代的方法改变分组，即 通过移动不同划分( 组) 中的对象来改变划分内容，使得每一次改进之后的分组方案都 7 江南大学硕士学位论文 较前一次好。一个好的划分衡量标准通常就是同一分组中的对象之间尽可能“接近”或 相关，而不同分组中的对象之间尽可能“远离”或不同。 划分法是应用范围最广的聚类方法。为获得全局最优结果，基于划分的聚类要求穷 举所有可能的对象划分。基于划分的方法，其代表算法有k - m e a n s 、k m e d o i d s 、 大型数据库划分方法( c l a r a n s ) 等。划分法收敛速度快，在分析中小规模数据集时， 发现圆形或球状聚类工作得很好。缺点是它要求聚类数目k 必须合理地估计，初始中心 的选择和噪声对最终聚类结果会产生很大影响，且它适合于识别凸形分布、大小相近、 密度相近的聚类，此时需要对其进行扩展，否则难以发现分布形状比较复杂的聚类。 2 层次法( h i e r a r c h i c a lm e t h o d s ) 这种方法通过层次似的分解给定的数据集直到某种条件满足为止。根据层次分解形 成的方式，可以将层次方法分为凝聚聚类和分裂聚类两种类型。凝聚的方法，也称为自 底向上的方法，开始将每个对象作为一个单独的类，然后逐步合并相近的类，直到所有 的类合并为一个( 层次顶端) 或满足一个终止条件为止。分裂的方法，也称为自顶向下 的方法，开始所有对象均属于一个类中，在每一次循环将类分裂为更小的类，直到每个 类只包含一个对象或满足一个终止条件为止。在凝聚或者分裂聚类方法中，通常以用户 定义的希望得到的类的数目作为终止条件。层次方法代表算法有c u r e 、c h a m e l e o n 、 r o c k 和b r i c h 等。 层次聚类算法能得到不同粒度上的多层次聚类结构，缺点是没有全局待优化的目标 函数；合并或分裂点的选择困难，好的局部合并选择往往不能保证高质量的全局聚类结 果；且对噪声、孤立点敏感，不适用于非凸型分布数据集；一旦一个步骤( 合并或分裂) 完成之后，无法回溯。 3 基于密度的聚类方法 基于密度的方法与其它大多数基于对象间距离进行聚类方法的一个根本区别是：它 而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类而较难发现 具有任何形状的聚类的缺点。根据空间密度的差别，基于密度的聚类方法把具有相似密 度的点作为聚类，且随着密度的变化延伸向任意方向。其指导思想是：只要临近区域的 数据对象或点的数目超过一定阈值，就继续聚类。也就是说，对给定类中的每个数据点， 在一个给定半径内必须至少包含某个数目的点数。这样的方法可以消除“噪声”数据， 以及帮助发现任意形状的聚类。但算法计算复杂度较高，一般为o ( n 2 ) ，对于密度分布 不均的数据集，聚类结果往往并不令人满意。 基于密度的聚类方法主要分为两种方式，一种是基于密度分布函数的聚类，其典型 代表算法是d e n c l u e 等；另一种是基于高密度连接区域的密度聚类，其典型代表算法 有d b s c a n ，o p t i c 等。 4 基于网格的聚类方法 基于网格的聚类方法采用一个多分辨率的网格数据结构，将对点的处理转化成对空 间的处理，再通过对空间的划分以达到数据聚类的目的。它将对象空间划分成为有限个 单元( c e l l ) 的网格结构，并且所有聚类操作均是以单个的单元为对象的。但量化尺度是所 8 第二章群智能聚类算法 有的网格聚类算法都存在的问题。一般来说，划分太粗糙则会将不同聚类的对象划分到 同一个单元( 量化不足) 。相反，划分太细致则会得到许多冗余的聚类( 量化过度) 。通常 办法先从小单元开始聚类，然后逐渐增大单元的体积，重复这个过程直至形成满意的聚 类为止。基于网格的聚类方法的主要优点是处理时间由于与数据对象的数目无关而仅与 划量化空间中每一维的单元数目相关，从而显得相对较快。但这种算法效率的提高是以 降低聚类结果的精确性为代价的。 常用的基于网格的聚类算法有统计信息网格法s t i n g ，聚类高维空间法c i q u e 以 及基于小波变换的聚类法w a v ec l u s t e r 等等。 5 基于模型的聚类方法 基于模型的方法事先为每个类假定了一个模型，算法主要寻找数据对给定模型的最 佳拟合。这种方法假设数据是根据潜在的概率分布生成的。基于模型的方法主要包括两 类：统计学方法和神经网络方法。 概念聚类是统计学方法中的一类重要聚类方法，它生成数据对象的一个分类模式， 并描述出每个类的模式特征，即每个类代表了一个概念。它使用概率度量概念，且描述 导出的概念。典型的概念聚类算法是c o b w e b 算法。它是一种针对分类属性数据相对 简单的增量式概念聚类方法。该算法采用一个分类树的形式创建一个层次聚类。算法假 定在每个属性上的概率是独立分布的，实际上这个假设并不总是成立。此外，聚类的概 率分布表示使得更新和存储有相当大的代价。 神经网络方法描述每个聚类为一个原型，根据度量标准将新的对象分配到与其最相 似的原型所代表的类中，被分配到一个类的对象的属性可根据该类原型的属性来预测。 代表性的方法有竞争学习神经网络和自组织特征映射神经网络。 6 基于约束的方法 基于约束的方法又称条件系统聚类法，它基于系统聚类的思想，在聚类过程中按类 与类之间相聚的约束条件进行聚类，不满足条件者不得相聚。但现实生活中的聚类问题 往往拥有多种约束条件，然而在聚类过程中不能准确表达相应的约束条件，使得这一方法 难以广泛的推广和应用。这里的约束条件可以对个体对象进行约束，也可以约束聚类参数， 它们均来自相关领域的经验知识。对存在障碍数据的二维空间数据聚类是该方法的一个 重要应用。c o d 就是其中的代表算法，其主要是用两点之间的障碍距离代替了一般的欧 氏距离来计算数据间的最小距离。 2 2 3 聚类分析的度量标准 数据聚类是一