（应用数学专业论文）基于蚁群算法的混合属性数据集聚类方法的研究.pdf

东北大学顾士学位论文 摘要 基于蚁群算法的混合属性数据集聚类方法的研究 摘要 数据挖掘的目的是从海量的数据中提取人们感兴趣的，有价值的知识和重要的 信息，聚类分析则是数据挖掘的一个重要研究领域。它在商业、生物、医学、地质、 w e b 文档等方面都有重要的应用，是当前的研究热点问题之一。 本文对混合属性数据集聚类方法进行了研究，主要傲了以下工作： 1 将基于蚁群的聚类算法用于混合属性数据集的聚类问题。在基本蚁群聚类算 法( l f 算法) 的基础上，提出了一种改进的基本蚁群聚类算法( i l f 算法) ，在该 算法中，引入了公式改进、半径递增、短期记忆、空间分割等策略，大大提高了算 法的效率，并且使聚类性能得到较好的改善。同时，该算法利用了自适应原理，在 一定程度上，可以加快进化过程，而且是一种本质上分布并列的算法，因此具有很 高的效率，适合数据集聚类分析。同时采用了一种新的距离测度函数将数值特征与 类属特征相结合，从而实现了具有混合属性特征数据的聚类分析。通过对u c i 数据 库进行测试，仿真实验结果表明，改进后的算法具有较强的鲁棒性，对于处理具有 混合特征的数据集聚类问题是相当有效的，最后的聚类质量也达到了令人满意的效 果。 2 对基于信息熵的蚁群聚类算法( e a c 算法) 进行改进，提出了i e a c 算法， 通过信息熵的计算与比较，改变了拾起和放下数据的规则，减少了参数设置，并通 过半径递增、短期记忆、强行放下等策略，提高了聚类性能。这种方法对于处理混 合属性数据集尤其是类属性数据集聚类问题是相当有效的。 关键词：数据挖掘；聚类分析；数值属性；类属性；蚁群算法；信息熵 东北大学硕士学位论文 a b s t r a c t t h er e s e a r c ho fa n t - b a s e dc l u s t e r i n g a l g o r i t h mf o rd a t a s e t sw i t hm i x e da t t r i b u t e a b s t r a c t t h ep u r p o s eo fd a t am i n i n gi st oa b s t r a c tp o t e n t i a l ，v a l u a b l ek n o w l e d g ea n du s e f u l i n f o r m a t i o nf r o mp l e n t i f u ld a t a ，c l u s t e ra n a l y s i si so n eo ft h er e s e a r c hd o m a i n so fd a t a m i n i n g i th a si m p o r t a n ta p p l i a n c e si nm a n yd o m a i n ss u c ha si nb u s i n e s s ，b i o l o g y , m e d i c i n e ，g e o g r a p h y , w e ba r c h i v e ，a n di ti so n eo f t h eh o tr e s e a r c hp r o b l e m s t h i sp a p e rh a ss t u d i e dc l u s t e ra n a l y s i sm e t h o d sc l e a r l y , a n dd o n et h ef o l l o ww o r k ： 1 w ea p p l ya n t b a s e dc l u s t e r i n ga l g o r i t h mt od a t as e t sw i t hm i x e da t t r i b u t e ，p u t f o r w a r da ni m p r o v e da n tc l u s t e r i n ga l g o r i t h m ( i l fa l g o r i t h m ) b a s e do ns t a n d a r da n t c l u s t e r i n ga l g o r i t h m ( i fa l g o r i t h m ) i nt h i sa l g o r i t h m ，b yi n t r o d u c i n gm a n ys t r a t e g i e s s u c ha sf o r m u l ai m p r o v e m e n t ，r a d i u si n c r e a s e ，s h o r t - t e r r am e m o r y ，s p a c ep a r t i t i o ne t c 。， t h ee f f i c i e n c ya n dt h ec l u s t e r i n gp e r f o r m a n c ea r eb o t hi m p r o v e di nac e r t a i nd e g r e e t h e a n t - b a s e dc l u s t e r i n ga l g o r i t h mi nt h i sp a p e ra v a i la d a p t i v et h e o r y ，i nad e g r e e ，c o u l d e x p e d i t ee v o l u t i o n a r yp r o c e s s ，w h a ti sb e t t e ras o r to fe s s e n t i a l l yd i s t r i b u t i o nc o o r d i n a t e a l g o r i t h m ，h e n c ei t i sm o r ee f f i c i e n ta n di sq u i t ef e a s i b l ef o rd a t as e t sw i t hm i x e d a t t r i b u t e a tt h es a m et i m e ，an e wd i s t a n c em e a s u r ef u n c t i o ni sa d o p t e dt oc o m b i n e n u m e r i ca n dc a t e g o r i c a lv a l u e st o g e t h e r ，a n dc l u s t e ra n a l y s i so f r a i x e dd a t as e t si sc a r r i e d o u t t h r o u g ht h eu c id a t a b a s et e s t ，t h es i m u l a t i o ne x p e r i m e n tr e s u l ti l l u s t r a t e st h a tt h e a n t b a s e df l e wa l g o r i t h m sf u nf a s t e ra n dh a v es t r o n g e rr o b u s t n e s s t h e ya r eq u i t ef e a s i b l e f o rd a t as e t sw i t hm i x e dn u m e r i ca n dc a t e g o r i c a lv a l u e sa n dt h er e s u l t sa r es a t i s l y i n g 2 w ea l s oi m p r o v et h ea n tc l u s t e r i n ga l g o r i t h mb a s e do ni n f o r m a t i o ne n t r o p y ( e a c a l g o r i t h m ) a n ds e tf o r w a r di e a ca l g o r i t h m i ta m e n d sp i c k i n ga n dd r o p p i n gr u l e si nl f a l g o r i t h mt h r o u g hc o m p u t i n ga n dc o m p a r i n gi n f o r m a t i o ne n t r o p yt or e d u c et h en u m b e r o fp a r a m e t e r s b yi n t r o d u c i n gm a n ys t r a t e g i e ss u c ha sr a d i u si n c r e a s e ，s h o r t t e r m m e m o r y ，f o r c e dd r o p ，e t c ，t h ep e r f o r m a n c eh a sb e e ni m p r o v e d t h i sa l g o r i t h mi sq u i t e f e a s i b l ef o rd a t as e t sw i t hm i x e da t t r i b u t ee s p e c i a l l yf o rc a t e g o r i c a lv a l u e s k e y w o r d s ：d a t am i n i n g ；c l u s t e r i n ga n a l y s i s ；n u m e r i cd a t a ；c a t e g o r i c a ld a t a ；a n tc o l o n y a l g o r i t h m ；i n f o r m a t i o ne n t r o p y m 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写 过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示谢意。 学位论文作者签名：趣伟丽 日 期：2 0 口6 年3 日f 日 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位 论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文 的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 东北大学硕士学位论文 第一章引言 1 1 论文研究背景 第一章引言 近年来，数据挖掘的研究是信息产业界的一个热点问题，引起人们的很大关注 ”，2 ，3 j 。其主要原因在于最近的一、二十年，我们生产、获取各种数据的能力提高得 很快。大量的数据被广泛使用，迫切需要将这些数据转换成有用的信息和知识。数 据收集工具和技术的多元化，以及互联网的发展，为我们带来了海量的数据和信息。 但在缺乏强有力的工具的情况下，这些海量数据已经远远的超出了人的理解和概括 的能力，存在“胖数据，瘦信息”的现象。许多的数据库也就成了“数据坟墓”，这 些数据很少被再访问，而与此同时，拥有这些数据的决策者们，在做决策时不是基 于数据库中蕴涵的大量信息，而是基于决策者的直觉。所以迫切需要一种新的技术 来解决以上的问题，数据挖掘技术由此而产生。 现在我们面临的问题是：需要新的技术来“智能地”和“自动地”分析这些原 始的大量数据，以使消耗大量财力与物力所收集与整理的宝贵资源数据得以利 用，这就是数据挖掘( d a t a m i n i n g ) 产生的背景。它的产生使我们可以对数据进行 分析，可以发现重要的数据模式，为商务决策、知识库、科学和医药学研究做出了 巨大贡献。填平了数据和信息之间的鸿沟，将“数据坟墓”转换成知识“金块” 4 1 。 1 2 数据挖掘技术 1 2 1 数据挖掘的概念 数据挖掘是指从大型数据库或数据仓库中提取隐含的、未知的、非平凡的、极 有潜在应用价值的信息或模式，它是数据库研究中很有价值的新领域，融合了数据 库、人工智能、机器学习、统计学等多个领域的理论和技术。可以看出数据挖掘是 一门很广泛的交叉学科，它汇集了不同领域的研究者。特别要指出的是，数据挖掘 技术从一开始就是面向应用的。它不仅是面向特定数据库的简单检索查询调用，而 且要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推理，以指导实际 问题的求解，企图发现事件间的相互关联，甚至利用已有的数据对未来的活动进行 预测。 东北大学硕士学位论文第一章引言 1 2 2 数据挖掘的过程和分类 所有的数据挖掘系统都有数据准备、执行挖掘算法和表达结果等几个阶段，数 据挖掘过程细分为以下几个步骤：( 1 ) 解释和定义问题；( 2 ) 数据的搜集和抽取； ( 3 ) 数据引擎；( 4 ) 算法引擎；( 5 ) 运行数据挖掘算法；( 6 ) 评估结果；( 7 ) 重新 净化数据和问题；( 8 ) 使用结果【5 】。 最常用的数据挖掘技术有：( 1 ) 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) ；( 2 ) 决策树( d e c i s i o nt r e e ) ；( 3 ) 遗传算法( g e n e t i c a l g o r i t h m ) ；( 4 ) 最近邻技术( n e a r e s t n e i g h b o r ) ；( 5 ) 规则归纳( r u l ei n d u c t i o n ) ：( 6 ) 可视化( v i s u a l i z a t i o n ) 。 1 。2 3 数据挖掘的现状和发展趋势 1 数据挖掘的研究现状 数据挖掘是数据库领域中最重要的课题之一。目前，国外数据挖掘的发展趋势 其研究方面主要有：对知识发现方法的研究进一步发展，如近年来注重对b a y e s ( 贝 叶斯) 方法及b o o s t i n g 方法的研究和提高；传统的统计学回归法在数据挖掘中的 应用；数据挖掘与数据库的紧密结合。在应用方面包括：数据挖掘商业软件工具不 断产生和完善，注重建立解决问题的整体系统，而不是孤立的过程。用户主要集中 在大型银行、保险公司、电信公司和销售业。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉及 的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据 挖掘理论方面的研究。目前进行的大多数研究项目是由政府资助进行的，如国家自 然科学基金、8 6 3 计划、“九五”计划等。南京大学的徐洁磐、陈栋等人开发了一个 原型系统：k n i g h t ，这是一个通用的数据挖掘工具【6 1 ，可用于处理不同领域的知识发 现任务，主要有聚类分析、特征知识发现、分类规则发现、关联规则发现、函数依 赖发现及基于查询的知识发现等。中科院软件所史忠植研究员领导的课题组在d m 技术的研究上也有大量成果，发表若干论文【7 1 。李德毅院士【8 】、焦李成【9 1 等人发表多 篇论文。 2 数据挖掘的发展趋势 ( 1 ) 应用方面 早期的数据挖掘应用主要集中在帮助企业提升竞争能力。随着数据挖掘的日益 普及，数据挖掘也曰益探索其他应用范围，如生物医学、金融分析和电信等领域。 2 东北大学硕士学位论文第一章引言 此外，随着电子商务和电子市场逐渐成为零售业的主流因素，数据挖掘也在不断扩 展其在商业领域的应用面，通用数据挖掘系统在通行处理特定应用问题时有其局限 性，因此目前的一种趋势是开发针对特定应用的数据挖掘系统。 ( 2 ) 可伸缩的数据挖掘方法 由于数据量是在不断地激增，针对单独的和集成的数据挖掘功能的可伸缩算法 显得十分重要。一个重要的方向是所谓基于约束的挖掘。它致力于在增加用户交互 的同时如何改进挖掘处理的总体效率。它提供了额外的控制方法，允许用户说明和 使用约束，引导数据挖掘系统对感兴趣模式的搜索。 ( 3 ) 数据挖掘与数据库系统、数据仓库系统和w e b 数据库系统的集成数据库系 统、数据仓库系统和w w w 已经成为信息处理环境中十分重要的方面。 ( 4 ) 数据挖掘语言的标准化 标准的数据挖掘语言或其他方法的标准化工作将有助于数据挖掘的系统化丌 发，改进多个数据挖掘系统和功能间的互操作，促进数据挖掘系统在企业和社会中 的教育和使用。 ( 5 ) 可视化数据挖掘 可视化数据挖掘是从大量数据中发现知识的有效途径。系统研究和开发可视化 数据挖掘技术将有助于推进数据挖掘作为数据分析的基本工具。 ( 6 ) 复杂数据类型挖掘的新方法 复杂数据类型挖掘是数据挖掘中一项重要的前沿研究课题。虽然在地理空间挖 掘、多媒体挖掘、时序挖掘、离散挖掘以及文本挖掘方面取得一些进展，但它们与 实际应用的需要仍存在很大的距离。对此需要进一步的研究，尤其是针对上述数据 类型的现存数据分析技术与数据挖掘方法集成起来的研究。 ( 7 ) w e b 挖掘 由于w e b a z 存在大量信息，并w e b 在当今社会扮演越来越重要的角色，有关 w 曲内容挖掘、w e b 日志挖掘和因特网上的数据挖掘服务，将成为数据挖掘中一个最 为重要和繁荣的子领域。 ( 8 ) 数据挖掘中的隐私保护与信息安全 随着数据挖掘工具和电信与计算机网络的日益普及，数据挖掘要面对的一个重 要问题是隐私保护和信息安全。需要进一步开发有关方法，以便在适当的信息访问 和挖掘过程中确保隐私保护与信息安全。 3 。 东北大学硕士学位论文 第一章引言 1 3 本文主要工作与内容安排 聚类分析是数据挖掘中的个重要领域，也是当前研究的热点问题之一。它源 于许多研究领域，包括数据挖掘、统计学、生物学、机器学习等，主要目的是对数 据对象的集合进行分类，具有较高的应用价值。现在存在的算法较多，但各种算法 都有自己的优缺点，有待于进一步成熟和完善。 本文主要研究了群体智能有代表性的蚁群算法，目的就是将蚁群算法用于聚类 分析，在前人的基础上对蚁群聚类算法进行改进，并将它用于处理混合类型的数据， 最终得到较满意的聚类效果，具有较强的鲁棒性。我们对大量具有混合属性特征和 类属混合特征的数据进行聚类分析时，发现改进后的算法收敛速度快，且能够自动 确定聚类的个数，不需要人为的设定，这些特性在数据挖掘中是十分重要的。 另外我们还运用信息熵理论的思想，同蚁群聚类算法相结合，减少了参数设置， 大大提高了计算速度。既可以利用蚁群算法的随机性，使算法避免陷入局部最优， 又可以充分利用已有信息且有效进行两区域的合并操作。仿真实验结果表明新算法 能得到比原算法更好的结果，并且能缩短运行时间，对处理混合属性的数据集尤其 对类属性数据集是十分有效的。 本文内容安排如下： 第一章详细介绍课题的背景和意义； 第二章系统详细的介绍了聚类分析的概念，聚类分析中的数据类型和目前较典 型的聚类算法： 第三章主要介绍蚁群算法原理及其在聚类分析中的应用，在基本蚁群算法的基 础上提出了改进的蚁群聚类算法，并给出了该算法对混合属性数据集的仿真结果， 表明算法的优越性，是本文的重点： 第四章运用信息熵理论的思想，同蚂蚁聚类算法相结合，提出了改进的基于信 息熵的蚁群聚类算法，实验结果表明该算法运算速度提高，具有较强的鲁棒性； 第五章总结本文的主要工作并做出对未来的展望。 4 。 东北大学硕士学位论文 第二章数据挖掘中的聚类技术 第二章数据挖掘中的聚类技术 2 1 聚类分析概述 2 1 1 聚类的概念及描述 聚类分析是数据挖掘中的一个重要领域，也是当前研究的热点问题之一 1 0 , 1 1 。 所谓聚类，就是把给定对象集合分组成为由类似对象组成的多个类的过程，每个类 内的对象之间是相似的，但与其他类的对象是不相似的。聚类是数据挖掘中一种重 要的挖掘任务和挖掘方法。它从数据库中寻找数据间的相似性，并依此对数据进行 分类，使得不同类中的数据尽可能相异，而同一类中的数据尽可能相似，即“物以 类聚”，从而优化大规模数据库的查询和发现数据中隐含的有用信息或知识。 聚类问题可描述为：给定m 维空间r ”中的力个向量( 数据集) ，把每个向量归 属到孟个聚类中的某一个，使得每个向量与其聚类中心的“距离”最小。 2 1 2 聚类分析的用途 聚类的用途是很广泛的。比较典型的有 1 0 , 1 1 , 1 2 , 1 3 , 1 4 1 ：模式识别；空间数据分析， 在g i s 中，通过聚类发现特征空间来建立主题索引；在空间数据挖掘中，检测并解 释空间中的簇；图像处理；经济学；w w w 方面：文档分类，分析w e b 目志数据来 发现相似的访问模式等。 例如，在市场销售方面，帮助市场人员发现客户中的不同群体，并且概括出每 一类消费者的消费模式或者说习惯，然后用这些知识来制定出目标明确的销售方案； 在保险业中，对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；在 城市规划中，根据类型、价格、地理位置等来划分不同类型的住宅；在地震研究中， 根据地质断层的特点把已观察到的地震中心分成不同的类；在生物学中，辅助研究 动、植物的分类。可以用来分类具有相似功能的基因，还可以用来发现人群中的一 些潜在的结构等等：在地理方面，从数据库中识别出具有相似土地用途的区域，从 一个城市的房地产信息数据库中，根据房型、房价及地理位置分成不同的类；等等。 聚类分析作为数据挖掘中的一个模块，它既可以作为单独的工具以发现数据库 中数据分布的一些深入的信息，并且概括出每一类的特点，或者把注意力放在某一 个特定的类上以做进一步的分析；聚类分析也可以作为数据挖掘算法中其他分析算 。5 东北大学硕士学位论文第二章数据挖掘中的聚类技术 法的一个预处理步骤 4 1 。 2 1 3 对聚类算法的要求 数据挖掘中对聚类算法的典型要求包括以下几点f 4 】： ( 1 ) 可伸缩性：许多算法对于较小的数据集能够很好地进行聚类，但是，大型 数据集中可能包含有几百万、几千万乃至更多的对象。虽然通过抽样可以减少要处 理的数据量，但是抽样会对聚类的结果带来影响甚至会产生错误的结果。因此，可 伸缩性好的聚类算法是很有必要的。 ( 2 ) 能够处理混合型数据：许多算法是设计来对数值型( n u m e d c a l ) 数据进行 聚类的。然而，在许多应用中待聚类的数据可能是二值型( b i n a r y ) 、枚举型 ( c a t e g o r i c a l n o m i n a l ) 、序数型( o r d i n a l ) ，也可能是上述各种类型数据的混合。 ( 3 ) 识别任意形状的聚类：很多聚类算法中采用了欧氏距离或曼哈坦距离度量 来确定聚类，而这些距离度量倾向于识别大小与密度都相差不大的球形聚类。然而， 聚类可能是各种形状的，如线形、环形、凹形、及其他各种复杂不规则形状。这就 要求聚类算法要能够识别任意形状的聚类。 ( 4 ) 在确定输入参数时需要的相关领域内的知识最少：许多聚类算法要求用户 输入一定的参数( 如类别数或一定的度量闭值等) ，而聚类结果对输入的参数非常 敏感。而这些参数往往很难确定，尤其对于高维数据集更是如此。这不仅对用户带 来了难题，而且还使聚类的结果难以控制。 ( 5 ) 能够处理噪声：现实世界的很多数据中都包含一些异常数据或错误数据， 有些聚类算法对这些数据非常敏感，并可能会产生错误的聚类结果。 ( 6 ) 对输入顺序不敏感：有些聚类算法对数据的输入顺序非常敏感，例如，对 于同一个数据集，用不同的顺序输入到某个算法中，就可能会产生完全不同的聚类 结果。 ( 7 ) 对高维数据的处理：数据库或数据仓库中的数据可以有几十乃至成百上千 个维度或属性。许多聚类算法只擅长处理低维数据，如二维或三维数据。在高维数 据空间中，数据可能非常稀疏并且高度扭曲，因此，高维空间中数据的聚类是一个 很大的挑战。 ( 8 ) 带有约束条件的聚类：在现实世界中的一些应用中，可能需要在一些约束 条件下来进行聚类分析。例如一个城市中自动提款机位置的选择，就需要在对家庭 分布进行聚类时，考虑城市中河流、公路网、每个地区消费者的需求等约束条件。 6 东北大学硕士学位论文 第二章数据挖掘中的聚类技术 ( 9 ) 可理解性和可用性：用户期望聚类的结果是可以解释、易于理解并具有可 用性。也就是说，聚类可能需要与具体的语义解释和具体应用结合在一起，具体应 用的特定目标可能会影响到聚类算法的选择。 2 ，2 聚类分析中的相似度度量方法 在数据挖掘中，聚类分析的对象是实例( i n s t a n c e ) ，每个实例由不同的属性构 成，这些属性主要分为数值属性( n u m e d c a la t t r i b u t e s ) 和类属性( c a t e g o r i c a l a t t r i b u t e s ) ( 也可称为符号属性，类别属性等) 。例如，考试分数( 取值范围为o 1 0 0 的整数) 属性就是数值属性，而颜色属性( 取值为红、橙、黄、绿、青、蓝、 紫中的一个) 和姓名属性( 字符串型) 则是类属性。关于相似性度量方法的详细介 绍，可参见文献【1 5 。 由于要处理的往往是非常大量而复杂的数据集。因此，传统的聚类方法必须尽 量满足如下要求： ( 1 ) 能同时处理数值属性和类属性。 ( 2 ) 面对数量繁多且仍在迅猛增长的数据集，算法要满足效率及增量性方面的 要求。 2 2 1 数值属性的相似性测量方法 数值属性的相似性测量方法大多直接或间接依赖欧几里德距离。对于p 维样本 空间s 中的任意两个数据对象工，y ，如果属于数值属性对象，我们很容易测量出对 象之间的距离，主要方法有： ( 1 ) 欧氏距离： d q , j ) = 瓜i 阿i 了i 丽 ( 2 ，) ( 2 ) 曼哈坦距离： d ( i ，i ，) = i 一，一x ) l i + 1 x , ：- - x j ：l + - + 1 一b i ( 2 2 ) ( 3 ) 明考斯基距离： d ( i ，力= 拈1 - - o 。h 2 - - 埘+ - + k b 9 ( 2 ，3 ) 其中f - ( - ，薯：，) 和j = ( 一，x j ：，b ) 是两个p 维的数据对象，q 是一个正整数。 欧氏距离是最常用的方法，我们平时测量几何距离就是用的这种方法。曼哈坦距离 是另外一种常用的方法，而明考斯基距离将两种距离统一到一种形式中。 7 东北大学硕士学位论文第二章数据挖掘中的聚类技术 有时为了突出一些数据的关键属性对聚类分析的重要作用，常采用加权形式的 距离，以避免某些属性的值过大而屏蔽其它取值较小的属性对数据相似性测量的影 响。 2 2 2 类属性的相似性测量方法 针对欧氏距离不能直接应用于类属性数据的特点，r a l a m b o n d r a m y 提出一种将 类属性转换成二进制属性的方法，用0 或l 表示一个类属性值存在或不存在，并在 算法里把这些二进制属性当成数值来处理，这些方法需要一个转换过程来处理类属 性，如果类属性值很多的话，转换后的空间会很大。 通过这种方法容易得出描述类属性的海明距离公式：其中盖，y 为具有几个类属 性的实例对象，x ，m 是对应的属性： 鼽眠班 ：鬻。 d ( i ，j ) ：妻万( 葺，m )( 2 4 ) i = l 2 2 3 混合属性的相似性测量方法 我们称同时包含数值属性和类属性的对象为混合属性对象。对于混合属性的聚 类有一种将欧氏距离和海明距离组合在一起的相似性公式： d ( i ，- ，) = d ( t ，m ) + 万( t ，咒) ( 2 ，5 ) i = 1 j = p + l 式中实例对象x ，y 属性为掣，掣，。，犀c 。，其中掣，掣，4 为数值属 性，彳知，一暑：，为类属性，显然这是一种折中的算法。 2 3k - m e a n s 聚类分析算法 目前，在聚类分析领域，根据具体不同的应用已经研究出了大量的算法。算法 的选择取决于数据的类型、聚类的目的和应用。如果聚类分析被用作描述或探查的 工具，可以对同样的数据尝试多种算法，以发现数据可能揭示的结果。许多算法为 了提高效率和聚类结果的质量，往往继承了许多其他聚类方法的思想，很难将它们 单独划归为哪一类。因此，对于算法的分类也是仁者见仁、智者见智。 8 。 东北大学硕士学位论文第二章数据挖掘中的聚类技术 大体上，主要的聚类算法可以划分为如下几类【4 】：划分聚类、层次聚类、密度 型聚类、网格型聚类和模型聚类。为了方便下文进行算法比较，这里仅将划分聚类 中的一种代表算法k m e a n s 算法介绍如下： k - m e a n s 算法首先m a e q u e n 提出f 1 6 a 7 1 ，在数据挖掘领域中得到了广泛的应用。 k m e a l l s 算法以k 为参数，把一个对象分为k 个簇，使簇内具有较高的相似度，而簇 间的相似度较低。相似度的计算根据簇中对象的平均值( 被看作簇的重心) 来进行。 k m e a l l s 算法首先随机选取k 个数据对象，每个对象代表一个簇的平均值或中心 点。其余的对象按照它们与这些平均值之间的距离，被赋予与之最相近的簇。然后， 算法对每个新簇重新计算其平均值。这个过程一直迭代直到一个准则函数收敛为止。 典型的准则函数是方差准则函数，定义为： e - - x x l x - - m , 1 2 ( 2 6 ) i = l j e 巴 其中e 是数据库中所有对象的平方误差的总和，算代表数据空间中给定的对象，卅是 簇c i 的平均值( x 和m 。可以是任意维的向量) 。该准则函数试图使结果簇内部尽可 能地紧凑并相互分离。k m e a l l $ 算法的过程如图2 1 所示假设有一个二维的数据集 位于一个矩形区域中。令k = 3 ，即用户想将该数据集聚类成三个簇。按照上述的算 法，首先任意的三个数据点被选作初始簇的平均值点( 图中用“+ ”标示) 。于是其 余的每个点被分配到距离最近的平均值点所代表的簇中，如图2 1 ( a ) 所示，每个簇的 轮廓用点虚线环绕表示。 每次划分后，簇中的元素只要发生了变化，都有可能改变簇的平均值。而数据 对象将随着新的簇的平均值重新分布，其结果如图2 1 ( b ) 所示，每个新簇的轮廓用线 段虚线环绕表示。 这一过程迭代的最终结果如图2 1 ( c ) 所示( 每个簇的轮廓用实线环绕) ，此时每 个簇中的数据对象不再重新分布，即使得上述的方差准则函数收敛。该结果即为 k m e a n s 算法的聚类结果。 图2 1k m e a n s 算法的聚类过程 f i g 2 1c l u s t e r i n gp r o c e s so f k - m e a r l sa l g o r i t h m 9 东北大学硕士学位论文第二章数据挖掘中的聚类技术 k m e a n s 算法是解决聚类问题的一种经典算法。它的主要优点是算法简单、快速 而且能有效地处理大数据库。然而这种算法对不同的初始值可能会导致不同的聚类 结果；在线( o nl i n e ) k m e a n s 算法的执行结果对输入顺序有关。其次，这种算法采 用了所谓的爬山式( h i l l c l i m b i n g ) 技术来寻找最优解，因此易陷入局部极小值。由 于这两大缺陷较大限制了它的应用范围。k m e a n s 算法只有在簇的平均值被定义的情 况下才能使用，而且要求事先给出要生成簇的数目k 。此外，它不适合发现非凸面 形状或大小差别很大的簇，并对“噪音”和孤立点数据敏感，少量这样的数据会对 平均值产生极大的影响。 k - m e a n s 算法有不少变种，变化可能在于初始k 个平均值的选择、相异度的计算 和计算聚类平均值的策略上有所不同。为了得到好的聚类结果，常用的策略是首先 采用层次的聚类算法决定结果簇的数目，并找到一个初始的聚类，然后用迭代重定 位来改进聚类的结果。 2 4 目前聚类算法存在的一些问题 目前的聚类算法都有自己的优点和不足之处，聚类方法中主要存在的问题如下： ( 1 ) 符号属性的问题：大部分聚类方法因为是基于欧氏距离的，所以只能处理 数值属性，新出现的一些聚类算法，例如：k - p r o t o t y p e s 方法不但可以处理数值属性 也可以处理符号属性，这样就可以大大扩展聚类方法的应用范围。 ( 2 ) 算法的效率：通过对现有的聚类算法进行改进，使之具有伸缩性，具有增 量聚类的能力，在处理大数据集时，对数据库只需扫描一次。这些是当前数据挖掘 领域研究的一个重要问题。 ( 3 ) 初值的选择：初值的选择对聚类的最终结果有很大的影响。在数据挖掘的 领域中可以实现的方法是采用多组不同的初值并进行多次迭代，最后选择其中的最 佳者作为运算的结果，但不能保证一定能够达到全局最小值。 ( 4 ) 输入顺序：许多算法对数据的输入顺序非常敏感，如c l a r a n a s 。 ( 5 ) 最优解问题：聚类问题本质是一个优化问题的，这就是通过一种迭代运算 使得系统的目标函数达到一个极小值。但是这个目标函数在状态空间这不是一个非 凸函数，它有许多极小值，其中只有一个是全局最小者，而其它的都是局部最小者。 我们的目标是得到全局最小值，而不是其它的局部极小值。目前一些聚类算法，常 常会在求解过程中陷入局部最优，而得不到全局最优；即使求得了最优解，往往也 需要耗费大量的时间。在数据挖掘领域中，遇到大数据集时，使得求最优解问题变 1 0 东北大学硕士学位论文 第二章数据挖掘中的聚类技术 得困难，现在常采用初值的选择来求得近似最优解。 综上所述，我们可以看出现有的聚类算法在算法效率、算法质量等问题上都有 一些缺点，不是很成熟，正有待我们去完善、提高。许多学者针对现有算法的不足， 在聚类数据的预处理、聚类算法的效果、聚类算法的速度等方面不断的改进，提出 许多新的算法。同时结合一些前沿的知识来改进聚类算法，如遗传算法，蚁群算法， 模拟退火算法等 1 8 , 1 9 , 2 0 】。 本课题研究的目的和意义就是将蚁群算法用于聚类分析，在前人的基础上对蚁 群聚类算法进行改进，最后得到较满意的聚类效果；同时运用信息熵理论的思想， 同蚂蚁聚类算法相结合，减少了参数设置，大大提高了计算速度。既可以利用蚁群 算法的随机性，使算法避免陷入局部最优，又可以充分利用已有信息且有效进行两 区域的合并操作。仿真结果表明改进后的算法具有较强的鲁棒性，对处理混合属性 的数据集尤其对类属性数据集是十分有效的。 东北大学硕士学位论文 第三章基于蚁群的聚类算法 第三章基于蚁群的聚类算法 3 1 蚁群算法简介 3 1 1 蚁群算法的原理 2 0 世纪5 0 年代中期创立了仿生学，人们从生物进化的机理中受到启发，提出了 许多用以解决复杂优化问题的新方法【2 l 】，如遗传算法、进化规划、进化策略等。蚁 群算法是最近几年才提出的一种新型模拟进化算法，它首先由意大利学者m d o r i g o 等人提出来，称之为蚁群系统2 2 1 ，利用该方法求解旅行商问题( t s p ) 1 2 3 1 、指派问 题( j o b s h o p ) 【2 ”、调度问题1 2 5 等，取得了一系列较好的效果，受其影响，蚁群系 统模型逐渐引起了其他研究者的注意，并用该算法来解决一些实际问题。虽然对此 方法的研究刚刚起步，但是这些初步研究己显示出蚁群算法在求解复杂优化问题( 特 别是离散优化问题) 方面的一些优越性，证明它是一种很有发展前途的方法。 人工蚁群算法是受到人们对自然界中真实的蚁群集体行为的研究成果的启发丽 提出的一种基于种群的模拟进化算法，是继模拟退火算法、遗传算法、禁忌搜索( t a b u s e a r c h ) 算法、人工神经网络算法等启发式搜索算法以后的又一种应用于组合优化 问题的启发式搜索算法。m d o d g o 等人提出该方法时，充分利用了蚁群搜索食物的 过程与著名的旅行商问题之间的相似性，通过人工模拟蚂蚁搜索食物的过程( 通过 个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径) 来求解t s p ， 为了区别于真实的蚂蚁群体系统，这里称之为人工蚁群算法。 像蚂蚁这类群居动物，虽然单个蚂蚁的行为比较简单，但由这样简单的个体所 组成的群体却表现出极其复杂的行为特征，能够完成复杂的任务 不仅如此，蚂蚁 还能够适应环境的变化，如在蚁群运动路线上突然出现障碍物时蚂蚁能够很快重新 找到最优路径。蚁群是如何完成这些复杂任务的呢? 人们通过研究发现，蚂蚁个体 之间是通过一种称之为外激素( p h e r o m o n e ) 的物质进行信息传递，从而能相互协作， 完成复杂的任务。蚁群之所以表现出复杂有序的行为，个体之间的信息交流与相互 协作起着重要的作用。蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质， 而且能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁群倾向 于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现 出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率 1 2 东北大学硕士学位论文 第三章基于蚁群的聚类算法 就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。 可以用图3 1 中的实验解释蚁群是如何发现最优路径的。 ( a ) 蚂蚁开始选路( b ) 蚂蚁完成选路 ( a ) a n tb e g i nt os e l e c tw a y( b ) a n tc o m p l e t es e l e c tw a y 图3 1 蚁群算法的原理 f i g 3 1p r i n c i p l eo fa n ta l g o r i t h m 图3 1 ( a ) 所示，在网络的某两个节点a 与节点b 之间有两个支路a c b 和a d b ，其 中a c b 支路的长度大于a d b 支路的长度：假设在节点a 、b 各有两只蚂蚁，蚂蚁i 、2 由节点a 向节点b 行进，而同时蚂蚁3 、4 由节点b 向节点a 行进。在初始情况下，由 于各个支路上没有任何信息素的痕迹存在，所以在节点a 和节点b 处蚂蚁选择两条支 路的概率是均等的；于是蚂蚁1 和2 将分别沿着支路a c b 和a d b 向着节点b 行进，同 样蚂蚁3 和4 也将分别沿着支路b c a 和b d a 向着节点a 行进，由于蚂蚁行进的速度相 同，在一段时间之后，蚂蚁2 和蚂蚁4 经过支路a d b 分别到达节点b 和a ，而蚂蚁1 和3 却还在支路a c b 的途中，见图3 1 ( b ) 。在蚂蚁行进的过程中每个蚂蚁均留下了同样数 量的信息素的痕迹。这时可以看出，支路a d b 上留下的信息素的痕迹浓度要高于支 路a c b 上的信息素浓度；此后若再有蚂蚁到达节点a 和b 时，由于受到信息素痕迹的 诱导它们选择支路a d b 的概率就会较大，反过来它们又不断地增加支路a d b 上的信 息素痕迹的浓度，形成正反馈作用；与此同时，遗留在支路a c b 上信息素的痕迹还 会因不断的挥发而进一步的减弱。这样一来，选择走支路a d b 的蚂蚁就会越来越多， 选择走支路a c b 的蚂蚁就会越来越少，最后呈现有较强的信息素痕迹的那些支路便 会形成一条从蚁穴到食物源的最短路径。 3 1 2 蚁群算法的特征 作为一种模拟进化算法，蚁群算法有如下的特征： 1 蚁群算法是一种自组织的算法。在系统论中，如果系统在获得空间的、时间 的或者功能结构的过程中，没有外界的特定干预，我们便说系统是自组织的。在抽 象意义上讲，自组织就是在没有外界作用下使得系统熵增加的过程( 即是系统从无 t1 3 东北大学硕士学位论文第三章基于蚁群的聚类算法 序到有序的变化过程) 。蚁群算法充分体现了这个过程，以蚁群群体优化为例子说 明。当算法开始的初期，单个的人工蚂蚁无序的寻找解，算法经过一段时间的演化， 人工蚂蚁间通过信息素的作用，自发的越来越趋向于寻找到接近最优解的一些解， 这就是一个无序到有序的过程。 2 蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立，仅通过 信息素进行通信。所以蚁群算法则可以看作是一个分布式的多a g e n t 系统，它在问题 空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具 有较强的全局搜索能力。 3 蚁群算法是一种正反馈的算法。从真实蚂蚁的觅食过程中我们不难看出，蚂 蚁能够最终找到最短路径，直接依赖于最短路径上信息素的堆积，而信息素的堆积 却是一个正反馈的过程。对蚁群算法来说，初始时刻在环境中存在完全相同的信息 素，给予系统一个微小扰动，使得各个边上的轨迹浓度不相同，蚂蚁构造的解就存 在了优劣，算法采用的反馈方式是在较优的解经过的路径留下更多的信息素，而更 多的信息素又吸引了更多的蚂蚁，这个正反馈的过程使得初始的不同得到不断的扩 大，同时又引导整个系统向最优解的方向进化。因此，正反馈是蚂蚁算法的重要特 征，它使得算法演化过程得以进行。 4 蚁群算法具有较强的鲁棒性。相对于其它算法，蚁群算法对初始路线要求不 高，即蚁群算法的求解结果不依赖于初始路线的选择，而且在搜索过程中不需要进 行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其 它组合优化问题的求解。 以上是蚁群算法的优点，但蚁群算法也存在如下一些缺陷： 1 算法需要较长的搜索时间。蚁群中各个体的运动是随机的，虽然通过信息素 交换能够向着最优路径进化，但是当群体规模较大时，很难在较短的时间内从大量 杂乱无章的路径中找出一条较好的路径。这是因为在进化的初期，各个路径上的信 息素差别不大，通过信息正反馈，使得较好路径上的信息素逐渐增大，经过较长一 段时间，才能使得较好路径上的信息素明显高于其它路径，随着这一过程的进行， 差别越来越明显，从而最终收敛，这一过程一般需要较长的时间。 2 蚁群算法易于出现早熟停滞现象。在蚁群算法中，蚁群的转移是由各路径上 留下的信息素浓度和城市间距离来引导的，蚁群运动的路径总是趋向于信