（计算机软件与理论专业论文）结合蚁群算法的调和k均值聚类算法研究.pdf

学位论文使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许 论文被查阅和借阅。本人授权东北师范大学可以采用影印、缩印或其它复制手段保存、 汇编本学位论文。同意将本学位论文收录到中国优秀博硕士学位论文全文数据库 ( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论文全文数据库( 中国科学技 术信息研究所) 等数据库中，并以电子出版物形式出版发行和提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：趣 日 期：卫2 垒! ! h 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 日 期：一，。六二! 电话： 邮编： 摘要 数据挖掘是从大量的、不完全的、有噪音的、随机的数据中获取潜在的、有用的信 息和知识的过程。聚类分析是数据挖掘重要的组成部分，它是一种无监督的学习方法， 不需要关于数据集的先验知识。聚类算法就是根据事物之间的某些属性，把事物聚集成 类，使得不同类中的事物尽可能的相异，而同一类中的事物尽可能的相似。聚类分析已 经被广泛地应用于生活中的各个领域。 k 均值聚类是典型的划分聚类，它因为实现简单，效率高而被广泛的应用，但该算 法存在着需要事先给定簇个数、对初始中心点选择的依赖性和容易陷入局部最优解等问 题。调和k 均值算法( k 删) 虽然有效减小了对初始中心点选择的依赖性，但它仍需要 事先给定簇个数且容易陷入局部最优结果。针对以上问题，本文提出新算法结合蚁群算 法的调和k 均值算法( a c a k h m ) ，引入了蚁群算法，蚁群算法的特点是可自主聚类，不 需要给定簇个数，且它是全局寻优的启发式随机搜索算法，有较强的鲁棒性，易于与其 他算法相结合。 ， 。 新算法充分利用了蚁群算法和调和k 均值聚类算法的优点，先通过蚁群算法对数据 集进行初步聚类，得到簇个数及初始聚类结果，再将蚁群算法得到的初始聚类簇中心点 作为调和k 均值聚类的初始中心点，选择较优的初始值，以达到获得较优聚类结果的目 的。实验证明新算法有效解决了调和k 均值算法中簇个数需事先给定及聚类算法容易陷 入局部最优的问题。 关键字：数据挖掘；聚类分析；k 均值聚类；调和k 均值聚类；蚁群算法 a b s t r a c t d a t am i n i n gi st h ep r o c e s st h a to b t a i n i n gi n f o r m a t i o na n dk n o w l e d g ef r o mal o to f i m p e r f e c tn o i s yr a n d o md a t a c l u s t e r i n ga n a l y s i si si m p o r t a n tp a r to fd a t am i n i n g i ti s a n u n s u p e r v i s e dl e a r n i n gp r o c e s sa n di t d o e s n tn e e dp r i o rk n o w l e d g ea b o u td a t as e t c l u s t e r i n g a l g o r i t h mi st h ep r o c e s st h a tp u to b j e c t si n t od i f f e r e n tc l u s t e r sa c c o r d i n gt ot h ea t t r i b u t eo f o b j e c t sa n dm a k e so b j e c t si no n ec l u s t e rh a v eh i g h e rs i m i l a r i t ya n do b j e c t si nd i f f e r e n t c l u s t e r sh a v es l o w e rs i m i l a r i t y c l u s t e r i n ga n a l y s i sh a sb e e nu s e di nm a n yf i e l do fl i f e k m e a n sc l u s t e ri sc l a s s i cp a r t i t i o n i n gc l u s t e r i n g i ti sw i d e l yu s e db e c a u s ei tc a nb e i m p l e m e n t e de a s i l ya n dh a sh i 曲e f f i c i e n c y b u tt h ea l g o r i t h mh a ss o m ep r o b l e m s o n e p r o b l e mi st h a tt h ec o u n to fc l u s t e r sm u s tb ed e c i d e dp r i o r t h eo t h e rp r o b l e m i st h a ti t d e p e n d e n ti n i t i a lc l u s t e rc e n t r ep o i n t sa n di tc a nr e a c hl o c a lm i n i m a lr e s u l te a s i l y a l t h o u g h k h m a l g o r i t h mr e s o l v e st h ep r o b l e mt h a td e p e n d e n to ni n i t i a lc l u s t e rc e n t r ep o i n ti ts t i l lh a s t h ep r o b l e mt h a ti tn e e dt od e c i d et h ec o u n to fc l u s t e ra n dw i l lr e a c hl o c a lm i n i m a lv a l u e e a s i l y t or e s o l v et h e s ep r o b l e m sw ep r e s e n t a na l g o r i t h mc a l l e da c a k h mi nt h i sp a p e r w e a d da n tc o l o n ya l g o r i t h mt ot h ec l u s t e r i n ga l g o r i t h m a n tc o l o n ya l g o r i t h mh a sm a n yf e a t u r e s i td o e s n tn e e dt h ec o u n to fc l u s t e r sa n di ti st h eh e u r i s t i cr a n d o ms e a r c ha l g o r i t h mt h a tc a l l s e a r c hg l o b a lo p t i m u mr e s u l t i ti sr o b u s ta n dc a l la d dt oo t h e ra l g o r i t h me a s i l y t h en e wa l g o r i t h mt a k e sf u l la d v a n t a g eo fa n tc o l o n ya l g o r i t h ma n dk - h a r m o n i cm e a n s c l u s t e r i n ga l g o r i t h m f i r s t ，t h ea l g o r i t h mi n i t i a l l yc l u s t e r st h ed a t as e tb yc o l o n ya l g o r i t h mt o o b t a i nt h ec o u n to fc l u s t e r sa n di n i t i a lc l u s t e r i n gr e s u l t t h e nt h ec l u s t e rc e n t r ep o i n t sd e r i v e d f r o ma n tc o l o n ya l g o r i t h ma r eu s e da sc l u s t e rc e n t r ep o i n t so fk - m e a n sa l g o r i t h ma n dc h o o s e t h eb e t t e ri n i t i a lv a l u et og a i nt h ep u r p o s eo fo b t a i n i n gt h eo p t i m u mr e s u l t t h er e s u l to f e x p e r i m e n ti n d i c a t et h a t t h en e wa l g o r i t h me f f i c i e n t l yr e s o l v e s t h ep r o b l e m so fk h m a l g o r i t h mt h a tt h ec o u n to fc l u s t e r sn e e dd e c i d ep r i o ra n di tw e l lr e a c h1 0 c a lo p t i m u mr e s u l t k e yw 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 ；k m e a n sc l u s t e r i n g ；k h ma l g o r i t h m ；a n t c o l o n ya l g o r i t h m i i 目录 中文摘要i 英文摘要。- i i 目录：i i i 第一章绪论一1 1 1 研究目的及意义1 1 2 国内外的研究现状2 1 3 本文的主要内容3 第二章数据挖掘及聚类分析概述4 2 1 数据挖掘概述4 2 2 数据挖掘任务4 2 3 聚类分析j 5 2 4 聚类分析的主要算法8 第三章蚁群算法的基本原理。：1 2 3 1 蚁群算法概述1 2 3 2 基于蚁群觅食原理的蚁群算法一1 2 3 3 基于蚁堆形成原理的蚁群算法一1 3 第四章结合a c a 算法和k h m 算法的新算法1 6 4 1 调和k 均值聚类16 4 2 结合蚁群方法和调和k 均值聚类算法的新算法18 4 3 实验结果及分析一2 1 第五章结束语- 2 7 参考文献：2 8 j 2 疋谢31 在学期间公开发表著作和论文情况3 2 i 东北师范大学硕士毕业论文 第一章绪论 1 1 研究目的及意义 随着科技的发展带动社会和经济取得巨大进步，社会生活的各个领域都有着越来越 多的数据信息，人类拥有的数据量与日俱增，而且数据类型越来越复杂、结构越来越多 种多样，信息爆炸给人们带来庞大信息资源的同时，也使人们陷入在海量的数据中获取 有用信息难的困境中。如何在海量的数据中快速、有效地发现有用的信息或知识是人们 迫切需要解决的问题，数据挖掘技术因此被提出来，它汇集了统计学( s t a t i s t i c s ) 、机器 学习( m 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 ) 、人工 智能( a r t i f i c i a li n t e l l i g e n c e ) 等学科的内容，它在庞大的数据资源中能有效地提炼有用 的信息和知识。 数据挖掘的定义是从大量的、不完全的、有噪音的、随机的数据中，获取隐藏在其 中的、人们事先不知道的，但又潜在的、有用的信息和知识的过程【l 】【2 】【3 1 。聚类分析是 数据挖掘重要的组成部分，它可以从数据集中发现数据间的相似性，并根据相似性对数 据进行分类，使得不同类中的数据尽可能的相异，而同一类中的数据尽可能的相似 【1 】 2 】【4 】【5 1 。聚类分析是一种不需要先验知识的无监督的学习方法，被广泛的应用于生活中 的各个领域，如市场客户分析、模式识别、空间数据分析、w e b 文档信息检索0 图像处 理、生物学研究等。聚类分析发展至今，主要分为划分聚类法、层次聚类法、基于密度 的聚类法、基于模型的聚类法和基于网格的聚类法等等。不同算法适用的数据集不同， 有的算法复杂适用于大数据集，有的算法简单适用于小数据集，有的算法可以发现球形 簇，有的算法可以发现任意形状的簇等。 k 均值聚类是典型的划分聚类，它因为实现简单，效率高而被广泛的应用，但该算 法存在着需要事先给定簇个数、对初始中心点选择的依赖性和容易陷入局部最优解的问 题，本文提出新算法结合蚁群算法的调和k 均值聚类算法( a c a k h m ) ，将蚁群算法和 调和k 均值聚类相结合，其中，调和k 均值改善了k 均值聚类算法对初始中心点的依 赖性，蚁群算法可自主聚类，不需要给定簇个数，且它是全局寻优的启发式随机搜索算 法，有较强的鲁棒性，易于与其他算法相结合，实验证明新算法在聚类结果准确性上效 果明显。 本文提出利用蚁群算法对数据集进行初步聚类，得到簇个数及初始聚类结果，并将 蚁群算法得到的初始聚类结果作为调和k 均值聚类的初始值，以达到得到较优聚类结果 的目的。该算法有效解决了簇个数需事先给定，及聚类算法容易陷入局部最优的问题。 东北师范大学硕士毕业论文 1 2 国内外的研究现状 随着信息时代的到来，在海量的数据库中快速、有效地获得有用的信息变得尤其重 要，数据挖掘技术应运而生，并迅速引起了国内外学者的极大关注，越来越多的学者投 身到数据挖掘技术的研究和探讨中。下面主要介绍一下数据挖掘的国内外现状，并详尽 阐述其中的主要方法，聚类分析的现状和未来发展趋势。 1 9 8 9 年8 月，k d d ( k a o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 在第十一届国际联合人工智 能学术会议( u c a i ) 上首次被提出，在随后的1 9 9 1 年、1 9 9 3 年、1 9 9 4 年都曾举办过k d d 专题讨论会，来自各个领域的学者集中参加、讨论数据统计、海量数据分析和知识表示 等问题，随着关注k d d 的学者越来越多，k d d 国际会议渐渐发展成为年会。 除了k d d 年会外，还有许多的数据挖掘年会，其中有p a k d d 、p k d d 、s i a m d a t a m i n i n g 等。p a k d d ( p a c i f i c - a s i ac o n f e r e n c eo nk n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ) 是亚太平洋地区的数据挖掘年会。0 7 年的p a k d d 在5 月份的中国南京举行。s i a m d a t a m i n i n g 是0 1 年召开的数据挖掘讨论会。 数据挖掘在国外被广大学者探讨和研究，已成立专门的工作组。比较著名的有 r a g r a w a l 领导的i b ma l m a d e n 实验室的数据挖掘工作组；s t a n f o r d 大学的关联规则研 究小组；j h a n 的s f u 工作组等。这些研究学者提出了很多新的数据挖掘算法，并实 现了数据挖掘工具，为数据挖掘领域的发展做出很大的贡献，其中0 5 年的a c a s i g i d 国际会议，新西兰怀卡托大学的w e k a 工作组荣获了数据挖掘和知识探索的最 高服务奖，w e k a 也被誉为数据挖掘和机器学习历史上的里程碑。 国内相对国外研究数据挖掘稍晚，没有形成整体力量，不过近几年数据挖掘在国内 已迅速引起广泛关注，在理论和应用技术方面得到了长足的发展。目前，国内的许多 科研单位和高等院校竞相开展知识发现的基础理论及应用研究，1 9 9 3 年国家自然科学 基金首次支持对数据挖掘方面的研究项目，其中，北京大学智能科学院的唐世渭和杨 冬青教授研究开发了基于空间数据挖掘的客户分析模型c a s d m 系统。复旦大学施伯 乐教授研究实习了数据挖掘的工具集a m i n e r 等。南京大学、四川联合大学和上海交 通科技大学等高校经过探讨、专研，在非结构化数据的知识发现及w e b 数据挖掘上有 较好成果。越来越多的国内学者投入到数据挖掘技术的研究和学习中，并在近些年有 较大的成果。 数据挖掘的前景很好，目前正在探索中日益发展，很多专家学者提出了数据挖掘未 来的发展趋势，随着数据挖掘引起越来越多人的关注，这一技术更加完善、强大。 可视化数据挖掘能从大量的可视化数据( 影像、图片) 中发现、提取有用的信息。 可视化信息已是现实生活信息的主要组成部分，研究和分析可视化数据挖掘有着越来 越重要的意义。 w e b 挖掘是随着互联网的日益壮大发展起来的，w e b 上存在海量的数据信息，有关 w e b 内容挖掘、w e b 日志挖掘等技术，将成为数据挖掘技术的重要的研究方向。 复杂数据类型挖掘是数据挖掘中一项重要的前沿课题，包括地理空间挖掘、多媒体 2 东北师范大学硕士毕业论文 挖掘、时序挖掘、离散挖掘、文本挖掘等技术，目前还在起步阶段，未来有很大的发 展空间。 随着数据挖掘技术的日益发展，人们已认识到数据挖掘技术可以从大量的数据中， 获取潜在有用的信息，可以从中挖掘巨大的商业价值和潜在的科学知识，数据挖掘技 术正不断的被应用到新的领域，各种算法被不断改进应用到数据挖掘技术中，这将更 大激发数据挖掘技术的潜力，进一步推动数据挖掘技术的发展和应用。 1 3 本文的主要内容 k 均值聚类是经典的划分聚类，由于它的简单、容易实现而被广泛应用，但k 均值 聚类仍存在它的不足，首先，只有在聚类结果簇的个数k 事先确定的情况下，聚类结果 才是唯一确定的；其次，簇中心点的选择对最终聚类的结果有着很大的影响，选择较优 的初始中心点，可得到较优的聚类结果；最后，k 均值的聚类结果容易陷入局部最优值， 最终得到局部最优解。调和k 均值聚类算法引入了调和平均值的思想，虽可减小算法对 初始中心点选择的依赖性，但仍存在着容易陷入局部最优和需事先给定簇个数的问题。 基于以上不足，本文提出了将蚁群算法和调和k 均值聚类相结合的新算法a c a k h m ， 蚁群算法是全局寻优的启发式搜索算法，且它不需要事先给定簇的个数。本文的实验部 分采用了2 组人工数据集和3 组经典数据集来验证新算法的性能，实验表明新算法在聚 类效果上有很好的改进。 本文的章节安排如下： 第一章绪论主要介绍本课题的研究目的及意义，数据挖掘技术中聚类算法的国内外 的研究现状和未来的发展趋势。 第二章介绍了数据挖掘的基础知识，详尽介绍了有关聚类分析的相关理论及基本概 念。讨论了聚类分析的各种算法，包括：划分聚类法、层次聚类法、模型聚类法、密度 聚类法等等，本文主要研究其中的划分聚类方法的典型算法调和k 均值聚类算法。 第三章是关于蚁群算法的介绍和分析。讨论了蚁群算法的基本原理，分析了蚁群算 法的特点，本节内容为深入理解、利用蚁群算法改进聚类方法的研究提供了扎实的基础。 第四章提出了新算法，利用蚁群算法不需要事先给定簇个数，且全局寻优的特点， 将它和调和k 均值聚类相结合，改善调和k 均值聚类对初始中心点的依赖性和容易陷 入局部最优的问题。首先利用蚁群算法对数据集进行预处理，得到初始聚类结果，将此 聚类结果作为调和k 均值聚类算法的初始值，选择较优的初始中心点，使得聚类算法最 终得到较优的聚类结果。同时采用人工数据集和经典数据集验证新算法的性能，实验证 明新算法有效地改进了原调和k 均值聚类算法的不足。 第五章对本文的主要工作进行了简单的总结，并提出了本文的工作需要进一步完善 和提高的地方。 东北师范大学硕士毕业论文 2 1 数据挖掘概述 第二章数据挖掘及聚类分析概述 随着科技发展带动社会和经济取得巨大进步，社会生活的各个领域都有着越来越多 的数据信息，人类拥有的数据量与日俱增，信息爆炸给人们带来庞大信息资源的同时， 也使人们陷入在海量的数据中获取有用信息难的困境中。如何在海量的数据中快速、有 效地发现有用的信息或知识是人们迫切需要解决的问题，数据挖掘技术应运而生。数据 挖掘( d a t am i n i n g ，d m ) 能在庞大的数据资源中能有效地提炼有用的信息和知识，它是 一门交叉学科，汇集了数据库、人工智能、统计学、机器学习、模式识别等不同学科和 领域，在这个信息爆炸的时代越来越广泛地被人们关注。 数据挖掘是从大量数据中挖掘出隐含的、未知的、潜在有用的知识或信息的过程。 数据挖掘可以从大型的数据库或数据仓库中的相关数据中提取人们感兴趣的知识、规律 等信息，且可以在不同程度上对数据进行分析，从而可以更加有效地利用数据。数据挖 掘从提出至今，已经被广泛地应用于生活中的各个领域，包括金融业、零售业、电信业、 生物医学类等行业，与我们的生活息息相关，越来越多的学者对数据挖掘进行深入研究 和探讨 1 】【3 】 4 5 1 。 2 2 数据挖掘任务 数据挖掘的分析方法主要包括：分类分析、聚类分析、关联分析、序列模式分析、 。 偏差分析、粗糙集和模糊集方法等【4 】【5 】【6 】【丌。 分类分析( c l a s s i f i c a t i o na n a l y s i s ) 是有指导、监督的学习过程，首先分析一组数据 集的数据对象，分配不同特征的类别不同的标记，这样的数据集就是训练集。分类分析 通过分析训练集中的数据，为每个类别进行准确描述或建立相应模型或提取出分类的规 则，然后利用该分类规则对其他的数据集进行分类。 聚类分析( c l u s t e r i n g a n a l y s i s ) 与分类分析不同，它是无监督的学习过程，它没有 数据集的先验知识，即事先对数据集的分布没有任何的了解，通过分析数据集的数据， 根据某种相似性度量将数据对象划分成簇，使得每个簇中的数据无限的相似，簇之间的 数据尽可能的不同。聚类分析方法适用于分析那些缺乏描述信息的数据集，或是无法进 4 东北师范大学硕士毕业论文 行预先分类的数据集，它可以通过聚类分析自动得到簇。 关联分析( a s s o c i a t i o n a n a l y s i s ) 是为了发现数据集中潜在的数据之间的关联信息。 关联分析定义了支持度和可信度两个阈值来确定关联规则。如超市记录了交易时的商品 清单，通过对顾客购物行为进行关联分析，可以获得商品之间的关联程度，9 0 购买了 面包的顾客还会购买牛奶，这就是一条有用的关联规则，超市将面包和牛奶放在一起销 售，就会提高销量。 序列模式分析( s e q u e n c ep a t t e r na n a l y s i s ) 同关联分析相似，它的主要思想是通过 分析数据间的先后次序关系，挖掘数据之间的关联，即它是用来分析数据之间和时间有 关的内在联系。序列模式分析适用于发现事物的发展趋势或发现重复性模式。 偏差分析( d e v i a t i o na n a l y s i s ) 是用来发现差异或偏差的数据，即与正常情况不同 的变化或异常，并通过分析判断是否是极端行为。如异常，则提示预防并处理；如正常 变化，更新数据记录。实际生活中的数据经常会出现异常情况，通过偏差分析方法处理 异常，有着重大的现实意义。 粗糙集( r o u g hs e t ) 和模糊集( f u z z ys e t ) 方法都是用来描述知识的不确定性和不 完全性。其中，粗糙集适用于类的数据对象的不可分辨性，而模糊集适用于类边界数据 的不确定性；且模糊集研究属于同一个类的不同数据对象的隶属关系，强调隶属程度， 而粗糙集研究不同分类中的数据对象组成的集合之间的关系，强调分类。 2 3 聚类分析 聚类分析( c l u s t e r i n g ) 是数据挖掘的重要组成部分，近些年备受关注，发展迅速。 聚类分析即“物以类聚”是一种无监督的学习过程，它不需要数据集的先验知识，根据 某种方法对数据进行分组，使得每组内部的数据尽可能的相似，而不同组之间的数据尽 可能的不同 2 】 3 】【4 】【5 】【6 】啊。聚类和分类的主要区别在于，分类方法中我们需事先知道训练 数据集的分类属性，而聚类方法则根据数据的特征按照数据之间的某种相似性进行自行 分类，找到这个分类属性值，最终得到簇结果。数据聚类算法多用于模式识别、图像处 理和数据分析研究等。 聚类分析也可作为独立的数据挖掘工具，根据获得数据分布的情况，观察簇的特点， 集中对某些簇做进一步的分析和研究；或作为其他数据挖掘算法( 关联规则和分类等) 的预处理，在此基础上对簇进行再处理。 在数据挖掘领域，不断有新的聚类分析算法被提出和改进，大量的研究工作都集中 在寻找更加适当的、高效的聚类分析算法。聚类的潜在应用对算法提出了很多要求，主 要包括【3 】【4 】 5 】【8 】： ( 1 ) 算法的可伸缩性和高维性。由于数据规模的与日俱增、数据类型的日益复杂，聚 类分析算法在处理小数据集的同时必须能有效的处理大规模的数据。 ( 2 ) 处理不同数据类型。由于聚类算法在实际生活中的应用要求算法能够处理不同类 气 东北师范大学硕士毕业论文 型的数据。 ( 3 ) 发现任意形状的簇。基于距离的聚类算法适用于发现类球形簇，基于密度的聚类 算法可以发现任意形状的簇，数据特征的未知性要求聚类算法能发现球形簇、长条形簇 和任意形状的簇。 ( 4 ) 参数设置对领域知识的最小依赖。很多聚类算法都需要事先给定某些参数：参数 多是根据经验预先给定，参数设定的好坏直接影响着最后的聚类结果。 ( 5 ) 有效的处理噪音数据。现实生活中的数据大多存在孤立点、异常点、未知或错误 的数据。 ( 6 ) 对数据输入顺序不敏感。有些聚类算法存在着当输入数据顺序不同时，得到不同 的聚类效果的问题。 。 ( 7 ) 可解释和可用性。聚类算法是用来处理数据信息的工具，最终得到有用的知识或 规律的过程，所以聚类结果是可以解释的、可以理解的并在实际生活中可以应用的。 2 3 1 聚类分析的定义 聚类分析是无监督的学习过程，它不需要数据集的先验知识，根据数据对象自身的 特征属性对数据进行划分成簇，使得每个簇中的数据尽可能的相似，而不同簇之间的数 据尽可能的不同。聚类的定义描述如下【3 】 4 】 8 】 9 】： 给定包括n 个对象的数据集x ： x 。，x 29 1 9 以) ，根据数据之间的相似程度将数据集 划分成k 个簇： c 1 ，c 2 ，c t ) ，且c i ，c 2 ，c i 需满足( 1 ) c 1uc 2u uc t = x ；( 2 ) cr 、c j = ，i 手- ，。其中，数据集中第f 个数据对象表示为x i = ( x i lx j 2 ，x 甜) ，d 为 数据的维数即数据对象有d 个属性值。由以上定义可知，数据集x 中的每个数据对象x ， 必定属于某一个类且唯一属于某一个类。通常数据集可以表示为n x d ( n 个样本，d 个 属性) 的数据矩阵： 鼍ix 1 2 x 2 lx 2 2 工n lx 目2 聚类分析的过程主要包括数据准各、特征选择和特征提取、相似度计算、聚类( 分 组) 、对聚类效果进行有效性评估等 4 【6 】 8 】。 数据准备的主要内容是对数据对象进行预处理，包括特征规范化和降维，其中，降 维的主要作用是为了减少高维数据分析时的复杂性，采用维度归约技术得到的数据集表 示保持了数据的完整性，可以更有效的分析数据对象。常用的维度归约技术有小波变换 和主成分分析方法；对数据对象进行特征规范化处理是因为不同的数据对象有着不同的 d j d 嘞； 东北师范大学硕士毕业论文 属性变量，不同的特征属性有着不可共度性。通过对数据对象的准备处理，可以使得聚 类算法更加高效、容易实现。 特征选择和特征提取是指从数据对象的特征中选择最有效的特征，并存储于向量 中，再对选择的特征进行处理转换成新的突出特征。 聚类( 分组) 需首先选择某种相似性度量函数计算数据对象之间的相似性，然后再 选择合适的聚类算法进行分组，得到簇。 聚类的结果评估主要采用三种评估准则，分别是：外部有效性评估、内部有效性评 估和相关性测试评估等。 2 3 2 数据的相似性度量 聚类算法的思想是事先定义某种相似性度量，根据数据对象的相似性程度，将相似 的数据划分成簇，每个簇中的数据尽可能的相似，而簇之间的数据尽可能的不同。所以 定义衡量相似性的度量变得尤其重要，最常用的相似性度量方法是计算数据对象的数值 属性的距离。数据之间距离越小，表示数据之间的相似性越大，反之，差异越大【3 】 7 】【9 1 。 对于，维样本空间中的7 个数据对象，任意两个数据对象x ；和x ，之间相似性度量 方法一般包括：e u c l i d e a n 距离、m i n k o w s k i 距离和m a h a l a n o b i s 距离等 1 】 2 】 5 1 。 m i n k o w s k i 距离：表示高维空间中数据z ，和x ，之间的距离度量。 。d ( x ，) = ( k 一砾q ) 石( f ，j = l ，2 刀) ( 2 一1 ) 七= l 当g = l 时，m i n k o w s k i 距离即绝对值距离： d c z p 一，= ( 喜i 一靠| ) 当g = 2 时，m i n k o w s k i 距离即e u c l i d e a n 距离： d ( x ，x ，) = ( 窆k 一砾1 2 ) ( f ，_ ，= 1 ，2 行) ( 2 3 ) 七篁1 m a h a l a n o b i s 距离：根据数据属性之间的协方差矩阵设置权值定义距离。 d ( x ，x ，) = ( x f x j ) 7 ( x 一x j ) ( f ，j = l ，2 ，1 ) ( 2 4 ) 其中，表示数据对象的协方差矩阵。m a h a l a n o b i s 距离的计算量较大，不适于 计算大规模数据集。 余弦距离：多用来度量文本类型的数据对象相似度。 7 东北师范大学硕士毕业论文 d ( x f ，x ) = 1 一s i m ( x f ，x ) ( 2 5 ) 其中，豇m ( x i , x j ) = 丙鬲瓦。余弦距离和余弦相似度刚好相反，余 弦相似度越大，余弦距离越小；反之，余弦相似度越小，余弦距离越大。 2 3 3 聚类的准则函数 聚类的准则函数是用来评价和衡量聚类结果质量的函数，一般也称为目标函数。聚 类分析算法的最终目的是对数据集进行分簇，使得同一个簇中的数据尽可能的相似，不 同簇之间的数据尽可能的不同。选择合适的聚类准则，可以得到较好的聚类效果，且聚 类准则可以评价聚类分析算法结果的好坏。聚类分析的准则函数一般是反映簇之间相似 性或差异的函数。将含有 1 个数据对象的数据集x = 瓴，而，x 。) 划分为七个子集即簇， 为衡量聚类的质量，定义目标函数，反复执行聚类算法的过程就是不断的优化目标函数 的过程【4 儿引。最常用的目标函数是误差平方和函数s s e ( s u mo f s q u a r e de r r o r ) ： 鼻 = 妇= 卜m 川2 j 越z t c i ( 2 6 ) 其中， c ，表示第个簇，m ，( ，= 1 , 2 ，尼) 是第_ ，个簇的中心点，七是聚类结果簇 的数目，聊，= 南x ，( = 1 ，2 ，尼) ，l q i 表示第个簇中数据对象的个数。 i 乙卜睢q 由上式可知，目标函数，是所有的数据对象和与其最近中心点之间的误差平方和， ，值的大小取决于c 个聚类簇中心点，值越大，说明误差越大，聚类结果不理想；值 越小，说明误差越小，聚类结果越好。通常该类型的聚类又称最小方差划分，多适用于 各类数据对象分布密集且类别之间数目差别不大的数据集。 2 4 聚类分析的主要算法 聚类算法从发展至今，主要分为以下几种：划分方法( p a r t i 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 dm e t h o d ) 、基于网 格的方法( g r i d b a s e dm e t h o d ) 和基于模型的方法( m o d e l b a s e dm e t h o d ) 等【3 】 4 】 5 】 6 8 1 。 所有聚类方法都有着各自的特点，有的算法简单，容易理解、执行效率高( 如k - m e a n s ) ； 有的算法能有效的过滤噪音数据( 如d b s c a n 算法) ；有的算法能发现任意形状的簇( 如 c u b n ) ，有的算法适用于高维的数据集( c l q u e ) ；对于不同的数据类型，不同的数据规 东北师范大学硕士毕业论文 模，不同的簇形状等数据集分别有相应的聚类算法。 2 4 1 划分方法( p a r t i t i o n i n gm e t h o d ) 划分方法( p a r t i t i o n i n gm e t h o d ) 的基本思想是给定一个包含n 个数据对象的数 据集，通过目标函数最小化的策略把数据划分成k ( k n ) 个簇，即每个簇是一个类。划 分方法首先选择初始中心点，确定初始簇划分，然后采用迭代重定位技术，通过中心点 的不断变化重新进行分组聚类。划分方法的评判标准是：在同一个簇中的数据对象无限 的相似或相近，而不同簇中的数据对象之间无限的远离或相异。k 一均值算法( k m e a n s ) 1 0 】和k 一中心点算法( k m e d o i d s ) 1 1 是两个典型的划分聚类算法，由于它们的实现简单、 执行效率高，被广泛的应用于生活的各个领域，在此基础上发展起来的算法还有c l a r a ( c l u s t e r i n gl a r g ea p p l i c a t i o n s ) 和c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o nb a s e d u p o nr a n d o m i z e ds e a r c h ) 1 6 等。 1 9 6 7 年学者m a c q u e e n 最先提出了k - m e a n s 算法，该算法从提出到不断完善发展至 今在数据挖掘领域得到了广泛的关注【l o 】【1 2 】 1 3 1 。 k 一均值算法是把n 个数据对象分成k 个 簇的过程，其中满足簇内的数据对象无限的相似，而簇之间的数据对象的相似性尽可能 的小。其中，相似度是根据数据对象与每个簇中心点的距离来计算的。k 一均值聚类算法 一七 的目标函数为脚( x ，0 = 恢一c 川2 ，其中，葺表示数据对象，- 而 c j 是簇中心点 f - i ，= 1 ( 即簇，中所有数据对象的平均值) 。目标函数值越小，最终得到的聚类结果越好。 k - 均值聚类算法的一般过程为： 在待处理的数据对象中随机选取k 个数据对象作为初始簇的中心点； 计算数据对象与各个簇中心点的距离，并将其分配到离它最近的簇中心点所在 簇中； 重新计算每个簇的中心点； 重复，直至目标函数达到最小值，或中心点不再变化，得到划分结果。 i ( m 算法( k - 均值聚类算法) 由于它的实现简单、效率高等特点被广泛地应用于生活 中的各个领域，且该算法对大规模数据集具有可扩展性。当数据样本显示球形簇分布， 且各个簇的数据量差别不大时，i ( m 算法的聚类效果较好。然而k 一均值算法也存在很多 不足，其一，需事先给定簇个数k ，不同的k 值可能得到完全不同的聚类结果；其二， 该算法对事先选择的初始中心点具有依赖性，初始中心点选择的好坏决定着最终聚类结 果的好坏；其三，k 一均值算法多用于球形簇聚类，它不能发现凹形的簇，而且对噪音和 孤立点十分敏感；其四，l ( m 算法容易得到局部最优解 1 3 】【1 4 】 1 5 】。 9 东北师范大学硕士毕业论文 2 4 2 层次方法( h i e r a r c h i c a lm e t h o d ) 层次方法可以分为凝聚( a g g l o m e r a t i r e ) 层次聚类和分裂( d i v i s i v e ) 层次聚类 两种。凝聚层次聚类是自底向上的方法，最初将每个数据对象单独分组，然后陆续连续 地合并相近的簇，直到所有的数据对象最终合并为一个簇，或达到一个终止条件。分裂 层次聚类是自顶向下的方法，最初将所有的数据对象都放在同一个簇中，在其后的迭代 过程中，大的簇不断被分裂成更小的簇，直到每个簇最终只包含一个数据对象，或达到 一个终止条件。层次聚类方法的原则是一旦一个合并或分裂的动作完成，它将不能被撤 消。典型的层次聚类算法包括：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 g u s i n gh i e r a r c h i e s ) 、c 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 h a m e l e o n 、r o c k 等算法 1 5 】【1 7 1 。 2 4 3 基于密度的方法( d e n s i t y - b a s e dm e t h o d ) 基于密度的方法的主要思想是：对于数据集中的每一个数据对象，当其邻近区域的 密度( 或数据点的数目) 超过了某个闽值，就继续聚类。基于密度聚类方法的提出解决 了基于距离聚类算法只能发现球形簇聚类的缺点，它可以发现任意形状的簇，且可以过 滤噪音数据。基于密度聚类方法的代表算法有：d b s c a n 算法、o p t i c s 算法、d e n c l u e 算法等 2 0 1 。 d b s c a n 算法( d e n s i t y b a s e ds p a t i a lc l u s t e r i n go fa p p l i c a t i o nw i t hn o i s e ) 是由e s t e r 等最早提出的，该算法将密度足够大的区域划分成簇，并可以在具有噪音的 空间数据中发现任意形状的簇，它是密度相连的点的最大集合【2 0 1 。d b s c a n 算法需事先 根据经验给定两个全局参数占和m i n p t s ，参数的设置对聚类算法的执行效率有着较大的 影响，且当数据对象分布不均匀时，聚类的效果不理想。基于以上问题，近年来提出很 多算法对d b s c a n 算法进行改进和优化，o p t i c s 算法( o r d e r i n gp o i n t st oi n d e n t i f yt h e c l u s t e r i n gs t r u c t u r e ) 是一种顺序聚类的方法，首先对数据对象进行排序，再得到簇 的排序，它包含的信息是一个从更广的参数设置范围获得的基于密度的簇。d e n c l u e ( d e n s i t y b a s e dc l u s t e r i n g ) 算法是基于一组密度分布函数的聚类算法，该算法定义 了一个影响函数用来描述数据点在其邻域内的影响程度。与其他聚类算法相比较， d e n c l u e 可以发现任意形状的簇，可以较好的过滤噪音数据，聚类效率比较高。 2 4 4 基于网格的方法( g r i d b a s e dm e t h o d ) 基于网格的方法首先将数据空间量化为有限数目的网格单元，对数据对象的所有操 作都是以网格单元为单位的。该类方法的特点是处理数据对象的速度快，其处理速度与 1 0 东北师范大学硕士毕业论文 数据空间被分成的单元个数有关，而与数据对象的数目无关。典型的基于网格的方法包 括：s t i n g 算法、w a v e c l u s t e r 算