（计算机科学与技术专业论文）基于蚁群算法的混合聚类算法研究.pdf

摘要 在聚类分析问题中，实际应用的复杂性以及数据的多样性往往使得某个算法仅适用 于某一类特定数据，且存在一定缺陷。因此，许多新的聚类算法不断被提出。基于蚂蚁 化学识别系统的聚类算法( a n t c l u s t ) 是一种新型的生物模拟进化算法，它能自动形成聚 类数目、能发现任意形状的簇、能处理任意类型的数据，有较强鲁棒性和适应性。然而， a n t c l u s t 算法是基于随机选择的，且使用较多统计的随机性参数作为判定依据，导致算 法计算误差较大。同时，它删除小巢的方法也过于呆板，不够灵活。本文从对a n t c l u s t 算法进行改进和将改进的a n t c l u s t 与k m e a n s 算法进行组合两方面着手，构建一种新 的混合聚类算法，来提高聚类结果的质量。 针对蚂蚁初始化、行为规则、相似度计算和小巢删除等方面存在的问题，提出了新 的随机碰面规则、相似度计算方法、复杂聚类中心定义和小巢删除规则等改进措施。改 进过程中，将“均值 的思想用于行为规则中，降低了随机性带来的误差，提高了运算 的精确度；新的复杂聚类中心，使算法能够计算类别属性的“平均值”，提高了算法的 处理能力，为与k m e a n s 算法的组合奠定基础。改进的a n t c l u s t 算法降低了迭代次数， 提高了聚类结果的质量。 结合改进的a n t c l u s t 特点，对k - m e a n s 算法进行适当的修改：通过设定最大迭代 次数控制k m e a n s 算法的停止；迭代过程中能更新蚂蚁的接受阈值。按照以改进型 a n t c l u s t 算法为总体框架，将k - m e a n s 算法融入其中的思路组合这两个算法，通过二者 反复调用来处理数据。混合算法在提高计算精度方面比原a n t c l u s t 算法有更优秀的表 现。 在u c i 数据集上的实验结果表明了对a n t c l u s t 的改进和与k m e a n s 算法的组合是 有效的，在获得有效聚类的同时，提高了聚类结果的质量。 关键词：蚁群算法，混合聚类，a n t c l u s t ，复杂聚类中心，k m e a n s r e s e a r c ho fh y b r i dc l u s t e r i n ga l g o r i t h m b a s e do na n tc o l o n ya l g o r i t h m l ic h a n g j i n ( c o m p u t e rs c i e n c e & t e c h n o l o g y ) d i r e c t e db yp r o f e s s o rd u a ny o u x i a n g a n da s s o c i a t ep r o f e s s o rg o n ga n a b s t r a c t i nt h ec l u s t e ra n a l y s i s ，t h ec o m p l e x i t yo fp r a c t i c a la p p l i c a t i o na n dm u l t i f o r m i t yo fd a m a l w a y sm a k ea na l g o r i t h mo n l yc a nb ea p p l i e dt oas p e c i f i ct y p eo fd a t a , a n dt h ea l g o r i t h m a l w a y sh a ss o m ed e f e c t s s o ，m a n yn e wc l u s t e r i n ga l g o r i t h ma r ei n t r o d u c e dc o n t i n u a l l y t h e c l u s t e r i n ga l g o r i t h mb a s e do nt h ec h e m i c a lr e c o g n i t i o ns y s t e mo fa n t s ( a n t c l u s t ) i san e w s i m u l a t i n gb i o l o g i c a le v o l u t i o na l g o r i t h m i tc a np r o d u c et h en u m b e ro fc l u s t e r i n g a u t o m a t i c a l l y , f i n dc l u s t e r so fa r b i t r a r ys h a p e ，a n dp r o c e s sd a t ao fa r b i t r a r yt y p e i ta l s oh a s s t r o n gr o b u s t n e s sa n ds u i t a b i l i t y h o w e v e r , a n t c l u s ti sb a s e do nr a n d o ms e l e c t i o n ，a n du s e s m a n ys t a t i s t i cr a n d o mp a r a m e t e r sa sj u d g e m e n ts t a n d a r d t h e s et o wm e t h o d sm a k ea n t c l u s t h a v em o r ec o m p u t a t i o n a lm i s t a k e s i m u l t a n e o u s l y , i t sm e t h o do fd e l e t i n gs m a l ln e t si st o o r i g i d t h i sp a p e ri n t r o d u c e an e wh y b r i dc l u s t e r i n ga l g o r i t h mb ym e a n so fi m p r o v i n g a n t c l u s ta n dc o m b i n i n ga n t c l u s ta n dk - m e a n sa l g o r i t h m t h i sn e wa l g o r i t h mc a nr a i s et h e q u a l i t yo fc l u s t e r i n gr e s u l t a c c o r d i n gt ot h ed e f e c t so fa n t c l u s ti n t h ei n i t i a l i z a t i o no fa n t s ，b e h a v i o r a lr u l e s ， c o m p u t a t i o no fs i m i l a r i t ya n dd e l e t i n gs m a l ln e t s ，t h i sp a p e ri n t r o d u c en e w r u l e so fr a n d o m m e e t i n g ，n e wm e t h o do fc o m p u t i n gs i m i l a r i t y , n e wd e f i n i t i o no fc o m p l e xc l u s t e r i n gc e n t e r a n dn e wr u l e so fd e l e t i n gs m a l ln e t s i nt h ei m p r o v e m e n tp r o c e s s ，t h i sp a p e ru s e st h et h o u g h t o fm e a n si nb e h a v i o r a lr u l e s t h i sm e t h o dr e d u c e st h ee r r o rc a u s e db yr a n d o ma n di n c r e a s e s t h ep r e c i s i o no fc o m p u t a t i o n n e wc o m p l e xc l u s t e r i n gc e n t e rm a k et h ea l g o r i t h mc a n c o m p u t et h em e a nv a l u eo fc a t e g o r ya t t r i b u t e ，r a i s e st h eh a n d l i n gc a p a c i t yo ft h ea l g o r i t h m a n dl a y st h ef o u n d a t i o nf o rc o m b i n i n gw i t hk - m e a n s t h ei m p r o v e da n t c l u s tr e d u c e st h e n u m b e ro fi t e r a t i o n s ，a n dr a i s e st h eq u a l i t yo fc l u s t e r i n gr e s u l t 。 a c c o r d i n gt ot h et r a i to fi m p r o v e da n t c l u s t ，t h i sa l t e r sk m e a n sa l g o r i t h mp r o p e r l y ：s e t t h em a x i m u mn u m b e ro fi t e r a t i o n s ，w h i c hc a l ls t o pt h ea l g o r i t h me a s i l y ；i nt h ep r o c e s so f i t e r a t i o n s ，a l g o r i t h mc a nu p d a t et h ea c c e p t a n c et h r e s h o l do fa n t s t h i sp a p e r u s e si m p r o v e d a n t c l u s ta so v e r a l lf r a m e ，p u tk - m e a n sa l g o r i t h mi n t ot h i sf r a m e ，a n dp r o c e s s i n gd a t ab y i n v o k i n gt h et w oa l g o r i t h m sr e p e a t e d l y t h eh y b r i da l g o r i t h mh a sh i g h e rc o m p u t a t i o n a l a c c u r a c yt h a na n t c l u s t e x p e r i m e n t a lr e s u l t sn ou c id a t as e t sp r o v et h a tt h ei m p r o v e m e n to fa n t c l u s ta n dt h e c o m b i n a t i o no fi m p r o v e da n t c l u s ta n dk - m e a n sa l ee f f e c t i v e t h eh y b r i dc a nf i n de f f e c t i v e c l u s t e r s a tt h es a m et i m e ，i tc a nr a i s e st h eq u 2 l l 毋o fc l u s t e r i n gr e s u l t k e yw o r d s ：a n tc o l o n ya l g o r i t h m ，h y b r i dc l u s t e r i n g ，a n t c l u s t ，c o m p l e xc l u s t e r i n gc e n t e r , k - m e a n s 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名： 鸯长盘 日期：勿加年厂月研日 ， 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门 ( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被 查阅、借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用 影印、缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：查丞丝 指导教师签名： 日期： 日期： 日 日 1卵， 月 月 r r 年 年 勿 p 加 圳 中国石油大学( 华东) 硕士学位论文 1 1 课题的提出及意义 第一章绪论 如今，计算机技术、网络技术、通讯技术及数据库技术的飞速发展使得各行各业积 累了大量的数据，而且数量也在急剧增加。同时，激烈的市场竞争也要求决策者必须能 够从现有的数据中获取有价值的信息，来指导决策，从而获得最大的竞争优势和效益。 但是由于没有有效的提取方法，使得蕴含在巨大的信息海洋中的极有价值的大量信息和 知识没有得到充分的开发和利用。这就迫切要求人们开发出有效的技术手段来提取知 识、获得有用的信息，知识发现【1 捌和数据挖掘【3 ，4 】技术也就应运而生了。 其中，聚类分析t s , 6 1 ，又称聚类，是一种广泛应用于数据挖掘的分析方法。聚类分 析有着广泛的应用，它既能作为一个独立的工具，进行数据分析处理；又能用来进行数 据预处理，作为其他算法的先行步骤。聚类是一种无监督学习方法，无需事先训练，只 依据数据间的相似度，就可将数据分成几个事先未知的簇，因此它是一种有效的知识发 现与未知模式识别的方法。聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究 课题。 聚类研究有很长的历史，几十年来，其重要性及与其他领域的交叉特性得到学者们 的积极肯定【5 1 。聚类也是一个非常活跃的研究领域，产生了很多重要的、具有代表性的 经典聚类算法，如基于划分的k 均值聚类张m e a n s ) 算法【7 8 】、基于层次的层次聚合算法 【9 】、基于网格的c l i q u e ( c l u s t e r i n gi nq u e s t ) g 法t l o 等。这些算法有其各自的优缺点。 例如，层次聚合算法【9 】计算方法简单，结果是个谱系图，可以根据实际需要选择最佳聚 类结果，但其计算复杂性为d 伽乡，因而仅适合于对小数据集进行聚类，对大数据集的 处理能力有限。而且，当某一数据对象划归到某一类后，其类别不能再改变，若分类方 法选择不当，对聚类结果精度的影响很大。另外，很多聚类算法对输入参数十分敏感， 而且参数很难确定，需要很多专业知识和经验，加重了用户的负担。这些都是需要改进 的地方。 蚁群算法1 1 1 】是受到蚂蚁群体行为的启发而提出的一种生物模拟进化算法，是一种新 型优化算法。该算法不依赖于具体的数学模型，基本原理简单易懂，具有全局优化能力。 将蚁群优化算法应用于聚类问题产生了很多优秀的算法【1 2 , 1 3 】，这些算法不需要事先指定 聚类数目，并且此类算法最大的优点就是能获取全局最优解。此外，它们还具有灵活性、 第一章绪论 健壮性、分布性、自组织性等，使其非常适合于本质上是分布、动态、交错的问题的求 解。但蚁群算法的严格理论基础还没有确立，以及算法的收敛性等问题也有待解决。另 外，在具体的蚁群聚类算法中还有许多需要解决的问题，如，在基于蚂蚁觅食的聚类算 法中，有两个调节因子系数、簇半径和循环次数需要预先指定，这需要大量的经验和专 业知识，这些参数的选取是否得当将直接影响聚类的质量。 混合聚类是指将两种或多种聚类方法组合起来以改善其聚类性能的组合方法，这也 是一种比较新的思路。混合聚类的特点是组合在一起的各个算法能“以己之长，补它之 短”，通过有效的组合能屏蔽掉各算法原来的缺点和不足，将各自原有的优点集于一身。 这种方法获得的聚类结果往往比单一的算法要好得多。对于混合聚类，在哪些聚类算法 适合组合在一起以及组合方式的问题上还有研究和提高的空间。 尽管聚类分析有着几十年的研究历史，众多聚类算法相继被提出、相关的应用也被 广泛展开，但聚类问题仍然存在着巨大的挑战。 综上所述，本课题提出在改进蚁群算法的基础上，在众多聚类算法中寻求能与改进 的蚁群算法以较高效率组合的算法，各算法之间相互取长补短，从而形成一种具有较高 性能的基于蚁群算法的混合聚类新算法。新的算法能保留蚁群算法的全局寻优、能构造 任意形状簇以及简单易实现的特性，保留传统聚类算法的描述相对精确的特性，从而能 够得到质量相对较高的聚类结果。新算法能为聚类分析研究提供一种更便利的方法。 1 2 国内外研究现状 聚类分析有着几十年的发展历史，积累了大量优秀的算法。从发展历程的角度可以 将聚类算法分为传统聚类算法和新兴聚类算法。传统的聚类算法可分为基于划分的方 法、基于层次的方法、基于网格的方法、基于密度的方法以及基于模型的方法 9 , 1 4 , 1 5 】。 这些方法一般是较早出现的、较为经典的聚类算法。新兴聚类算法主要是基于模拟生物 进化、模糊数学、量子理论等理论的研究而形成的，主要有基于生物种群的聚类、基于 粒度的聚类、基于模糊的聚类、量子聚类、核聚类、普聚类等【1 4 】。 下面围绕本课题的研究重点，着重介绍蚁群聚类算法和混合聚类算法的国内外研究 现状。 1 2 1 蚁群聚类算法研究现状 1 9 9 1 年意大利学者m d o r i g o 等提出蚁群算法【1 1 1 ，该算法模拟蚂蚁搜索食物的过程 2 中国石油大学( 华东) 硕士学位论文 以及蚂蚁个体之间是通过一种称之为外激素的化学物质( 2 z 称为信恩素) 进行信息传递 的行为，来实现对问题解的寻优。随后，他们又提出了多种类似的蚁群算法【m 羽，并将 这些算法用于求解组合优化问题，如旅行商问题( t s p ) 、任务调度问题等，获得了很好 的效果。 2 0 0 3 年，国内学者杨欣斌等将这种基于信息素的蚂蚁算法应用于聚类问题，提出 了一种基于蚁群的聚类学习新方法【l9 】。该方法可以最终获得全局最优解，并且具有本质 并行性、计算效率高、聚类学习能力强等优点。 除了基于信息素的蚂蚁算法外，其他一些学者通过模拟蚂蚁的其他行为提出了其他 不同类型的蚁群聚类算法。 2 0 0 3 年，h a z z a g 等学者通过模拟蚂蚁的自我聚集行为，建立了一个蚂蚁树模型 ( a n t t r e e ) ，来实现对数据集的聚类【2 0 1 。开始时，蚂蚁都处在一个相当于树根的点上，蚂 蚁在这棵树上及已经固定在树上的蚂蚁身上移动，来寻找最适合它的位置。受到其他蚂 蚁的作用，蚂蚁更趋于固定在树枝的末端，即树叶上。树的结构和蚂蚁之间的相似性引 导它的移动，当所有蚂蚁都在树上固定后，就获得了对数据集的划分。 1 9 9 1 年d e n e u b o u r g 等学者提出了一种智能体1 2 1 1 ( 人工蚂蚁) 模型，通过智能体来模 仿蚂蚁的行为，从而对数据进行聚类。它模拟蚂蚁堆形成的原理：在工蚁堆积蚂蚁尸体 过程中，小蚁堆不断吸引工蚁向上面堆积更多的死蚂蚁，通过正反馈使得蚁堆逐渐增大。 让数据分布在一个网格上，每个单元格只含一个数据对象，而人工蚂蚁沿着网格移动。 没有搬运数据对象的蚂蚁碰到对象时就会以一定概率拾起它，携带对象的蚂蚁遇到空单 元格或者被搬运的对象与邻近对象相似时就会以一定概率放下它，最终相同类型的数据 都被聚集到了一起。 2 0 0 3 年，j h a n d l 等人提出基于蚂蚁的聚类算法【2 2 】也是受蚁卵分类的启发，实际上 是对上述算法的改进，修改了几个重要的特性，主要过程与前述算法相似。 2 0 0 6 年，受蚂蚁分巢而居的启发，徐晓华等学者提出了一种人工蚂蚁运动模型( a n t m o v e m e n t ，a m ) 和以此模型为基础的自适应蚂蚁聚类算法( a d a p t i v ea n tc l u s t e r i n g ， a a c ) 2 3 1 。将入工蚂蚁看成一个行为简单的a g e n t ，代表个数据对象，人工蚂蚁有睡 眠和活跃两种状态。算法中定义了一个适应度函数，用来计算蚂蚁与其邻居的相似度。 人工蚂蚁通过其适应度和激活概率来决定是处于活跃状态还是睡眠状态。整个蚂蚁群在 移动中动态地、自适应地、自组织地形成多个独立的子群体，使不同类别的蚂蚁相互分 离，而同类的蚂蚁则高度紧密地聚集在一起，从而形成聚类。 3 第一章绪论 2 0 0 2 年，l a b r o c h e 等学者以化学识别系统原理为基础，提出了一种叫做蚂蚁簇 ( a m c l u s t ) 的聚类方法【2 4 1 。它通过模拟蚂蚁间通过各自的气味来分辨敌友的行为，实现 对数据集的聚类。 1 2 2 混合聚类研究现状 混合聚类是将多种聚类方法组合在一起，优势互补，以获得更优的聚类效果。 2 0 0 1 年，z h a o 和s o n g 给出网格密度等值线聚类算法g d i l c t 2 5 1 。密度等值线图能 够很好地描述数据样本的分布。算法g d i l c 的核心思想是用密度等值线图描述数据样 本分布，使用基于网格方法计算每一个数据样本的密度，发现相对的密集区域- 类。 g d i l c 具有消除奇异值和发现各种形状的类的能力，它是一种无监督聚类算法。这是 一种将基于网格和基于密度的方法结合起来的混合聚类算法。 2 0 0 4 年，m a 提出一种新的基于移位网格的、基于密度和网格的聚类算法s g c t 2 6 1 。 s g c 是一种无参数类型的算法，它不需要用户输入参数。它把数据空间的每一维分成 某些间隔，以形成一个数据空间的网格结构。基于滑动窗口概念，引入了整个网格结构 的移位概念，从而获得一个被更多描述的密度剖面，因而能够提高聚类结果的精度。其 主要优点为：计算时间与数据集样本数无关；在处理任意形状簇时展现了极好的性能； 不需要用户输入参数；当处理大型数据集时，很少遇到内存受限问题。 国内的一些学者也提出了自己的混合聚类算法。 吴文丽等通过分析基于蚂蚁堆形成原理的蚁群聚类算法和k - m e a n s 算法两种不同 算法的基本思想，将两种算法相结合得到混合聚类算法【2 7 1 。首先使用蚁群聚类算法得到 一个初始聚类结果，将这个结果作为k - m e a n s 算法的输入，由k - m e a n s 算法得到最终 结果。仿真实验证明混合聚类算法的性能优于蚂蚁算法和k m e a n s 算法。 周新华等将基于蚂蚁觅食的聚类算法与模糊c 均值聚类算法( f c m ) 相结合阎，利用 蚁群算法产生f c m 算法所需的聚类个数和初始聚类中心，再利用f c m 算法对初始结 果进行精细聚类。利用蚁群算法的全局搜索性、并行性等特点避免了f c m 算法容易陷 入局部最优解的问题。 杨燕、张昭涛等为了改善聚类的质量，提出了一种基于阈值和蚁群算法相结合的聚 类方法【2 9 1 。按此方法，首先由基于阂值的聚类算法进行聚类，生成聚类中心，聚类个数 也随之初步确定；然后将蚁群算法的转移概率引入k m e a n s 算法，对上述聚类结果进行 二次优化。实验表明，与k - m e a n s 算法等相比，该聚类方法的f 测度值( f m e a s u r e ) 更 4 中国石油大学( 华东) 硕士学位论文 高。 1 3 研究目标和主要研究内容 本文在研究和分析各种类型的蚁群聚类算法基础上，确定以蚂蚁簇( a n t c l u s t ) 聚类 算法为主要研究对象，通过对它进行改进形成改进型a n t c l u s t 算法( i m p r o v e da n t c l u s t ， i a n t c l u s t ) 。通过对传统聚类算法以及现有混合聚类算法的研究，在传统聚类算法中找 到一种能与改进型a n t c l u s t 算法较好结合的算法，通过有效方式将二者进行组合，形成 一种基于蚁群算法的混合聚类算法。该混合算法能获得高质量的聚类结果。 本文的主要研究内容包括以下几个方面： ( 1 ) 研究各个类型的蚁群聚类算法，比较它们的优缺点，确定以a n t c l u s t 聚类算法 为主要研究对象。分析a n t c l u s t 算法的不足，并对其进行改进，形成改进型a n t c l u s t 算法。 ( 2 ) 深入研究现有的混合聚类算法。分析、研究它们对各个算法进行组合的方式和 方法，为寻找能与改进型a n t c l u s t 算法组合的算法和制定有效的组合方式做准备。 ( 3 ) 分析改进型a n t c l u s t 算法的特点，研究传统的经典聚类算法，确定要与改进型 a n t c l u s t 算法组合的算法为k m e a n s 算法。 ( 4 ) 以改进型a n t c l u s t 算法为总体框架，将k m e a n s 算法融入其中。通过二者反复 调用来实现它们的组合。 ( 5 ) 在u c i 数据集上进行实验，验证算法改进的有效性。通过实验结果的反馈，进 一步优化新的算法。 1 4 论文的组织结构 本文围绕a n t c l u s t 算法的改进和将它与k m e a n s 算法进行组合展开研究和论述， 组织结构如下： 第一章绪论 主要介绍本课题的提出背景及研究意义，对蚁群聚类算法和混合聚类算法的国内外 研究现状进行了必要的介绍。提出本课题研究的思路和主要研究内容，阐明本文的研究 意义和学术价值。 第二章蚁群聚类和混合聚类 本章首先给出了聚类分析的数学定义，然后重点对蚁群算法和混合聚类算法进行研 s 第一章绪论 究，确定以a n t c l u s t 算法为本文主要研究算法，同时确定将k - m e a n s 算法与经过改进 的a n t c l u s t 算法进行组合，得到混合算法。最后着重介绍了聚类有效性的评价方法，确 定了以f m e a s u r e 方法作为本课题进行数据实验时的评价方法。 第三章a n t c l u s t 算法 本章对a n t c l u s t 算法的原理、思想、人工蚂蚁模型、接受规则和行为规则等进行了 详细的研究和介绍，最后给出了算法的总体描述。 第四章改进型a n t c l u s t 算法 本章详细分析了a n t c l u s t 算法存在的缺点。提出了新的随机碰面规则、相似度计算 方法、聚类中心定义和小巢删除规则等，对蚂蚁初始化、行为规则、相似度计算和小巢 删除等方面存在的问题进行了改进。通过在u c i 数据集上的实验验证了算法改进的有 效性。 第五章基于改进型a n t c l u s t 和k m e a n s 的混合聚类算法 在分析了改进型a n t c l u s t 算法和k - m e a n s 算法优缺点的基础上，论证了二者的可 结合性。以a n t c l u s t 算法为主体，将k m e a n s 算法作为增强计算精度的工具融入其中， 通过二者反复调用处理数据的方式将二者结合起来，形成混合算法。通过在u c i 数据 集上的实验验证了混合算法的有效性。 总结 总结本文的主要工作和创新点，分析归纳本文提出的混合算法的优缺点，并对本课 题中未完成的问题做出总结和下一步规划。 6 中国石油大学( 华东) 硕士学位论文 第二章蚁群聚类和混合聚类 聚类分析( c l u s t e r i n ga n a l y s i s ) s , 6 1 ，又称聚类( c l u s t e r i n g ) ，是数据挖掘技术中重要的 组成部分，它能够在潜在的数据中发现令人感兴趣的数据分布模式【3 0 】。 所谓聚类就是将一组数据对象分成若干个类或簇，在同一个簇中，对象之间的相似 度较高，而不同簇之间的对象相似性较低。 聚类的严格数学定义1 5 , 6 1 可描述为： 在数据空间r 中，数据集是由许多数据对象组成的一个数据集合，对象研= 向f j ，x i 2 ，二 圳e r ，每个x ，都有n 个属性值，砌可以是数值类型的，也可以是类别类型的。设数据 集x 中有个对象x 1 ，x 2 ，x n ，聚类就是要把x 分成k 个分割c j ，c 2 ，c 七，可能有 些对象不属于任何一个分割，这些对象称为噪声数据o ，所有分割与噪声的并集就是 数据集工并且这些分割的交集为空集，即：炸c ，u u q u q ，且a a ，且簖八 c = 乃夕p 呦幻= j ，z ：j ；) 。肛c ) 称为一个聚类空间，c f 称为聚类空间的第f 类( 簇) 。 聚类产生的结果簇是一组数据对象的集合，同一个簇中的对象之间有较高的相似 度，而不同的簇之间的对象则差别较大。在许多实际应用中，可以将同一簇中的所有数 据对象当作一个对象来使用。 聚类分析是人类认识现实世界的重要方法之一。虽然人们可以凭借已有的经验和专 业知识对众多事物进行有效的分类，但聚类作为一种自动的、定量的、无监督的知识发 现方法，能从数据分析的角度给出了一个更为准确、简便、快捷的分类工具【5 ，6 1 ，能使 分类工作更快、更有效的完成。目前，聚类分析己在各数值分析领域得到广泛应用，例 如文本挖掘、空间数据处理、医学图像的自动检测、模式识别及市场分析等。 2 1 蚁群聚类 蚁群算法是一种模拟生物种群的优化算法。最早的蚁群算法【l l 】由意大利学者 a d o r i g o 等提出，并应用于旅行商问题、调度问题等复杂的组合优化问题的求解中，取 得良好的效果。该蚁群算法是模拟蚂蚁觅食及蚂蚁间通过信息素传递信息的行为来实现 优化的。 最早应用于聚类问题的蚁群算法是由d e n e u b o u r g 等学者在1 9 9 1 年提出的基于人工 蚂蚁模型的聚类算法f 2 1 1 。该算法通过人工蚂蚁来模拟现实中的工蚁堆积蚂蚁尸体的行为 7 第二章蚁群聚类和混合聚类 原理的蚁群聚类算法。总体来说，蚁群聚类算法从原理上可以分为五种【1 2 1 3 】：( 1 ) 基于蚂 彳= xx = ( x i l ，t 2 ，) ，f = 1 ，2 ， ， 径的信息素为0 ，即研( o ) = o 。计算所有数据对象蜀、玛间的距离西，根据距离，由公 式i 2 1 ) 计算每条路径的信息素f f ，( f ) ： 妒艨j ： ， 丽v箩(t)rliflj(t)pij(t)= 了丽 s s 哪 码 其中，s = - x , l d , j t e m p l a t ef ) ( 2 - l2 ) 该算法反复地随机选择两只蚂蚁，模仿它们相遇过程【2 4 】： ( 1 ) 两只无巢蚂蚁相遇并彼此接受时，将创建一个新的巢，完成新巢的创建，新巢 会吸引其他相似蚂蚁加入进来； ( 2 ) 有巢蚂蚁与无巢蚂蚁相遇，并且能彼此接受时，将无巢蚂蚁加入该巢，壮大现 有的蚁巢； ( 3 ) 同巢蚂蚁相遇并彼此接受的情况下增加两个统计量，使巢变得更健壮： ( 4 ) 当两个同巢蚂蚁相遇但不能彼此接受，则将整体最差的蚂蚁从巢中删除。通过 除去不理想的蚂蚁，使巢变得更完美； ( 5 ) 不同巢的蚂蚁相遇且彼此接受时，将小巢中的蚂蚁归入到大巢中。通过多次完 成这个行为，可以合并相似的簇，小簇被大簇吸收。 算法最后要将巢内蚂蚁小于一定数量的小巢删除，其中蚂蚁归入最相似的大巢中。 算法结束后就能得到最终想要的划分。该算法能处理任意类型的数据，具有较强的鲁棒 性和适应性。但是，算法迭代次数需要事先指定，如何确定它并保证算法收敛还需进一 1 3 第二章蚁群聚类和混合聚类 步研究。另外，巢的删除参数直接影响到聚类结果的稳定性，此参数的设定还没有有效 的方法。 分析以上五种类型的蚁群聚类算法，从算法设计思想的简易程度、数据参数计算的 简易程度以及算法的可改进性等方面考虑，本文确定选取a n t c l u s t 算法为主要研究对 象，通过对它的进一步研究对其进行改进。 2 2 混合聚类算法 实际应用的复杂性以及数据的多样性使得单一的聚类方法往往得不到有效的结果。 因此，学者们对多种聚类方法的组合进行了广泛研究，取得了一系列成果，形成了混合 聚类方法。混合聚类是指将两种或多种聚类方法组合起来，各算法间优势互补，以获得 更优的聚类效果的一种方法。 将多种聚类算法组合在一起的方式有多种，大体上可分为算法思想上的组合和算法 本身的组合两类。 算法思想组合方式一般是将某种算法的思想应用于另外一种算法，总体上还是一种 算法，但具备了两种聚类思想的优点。c l i q u e 算法就是这样一种综合了基于密度和 网格思想的聚类方法。它先将数据空间划分为网格单元：然后识别其中密度大于输入参 数的密集单元，类则定义为相连密集单元的最大集合。此方法明显提高了算法的执行效 率，只是由于方法大大简化，聚类的精确性较低。 算法本身组合方式一般是先用一种算法对数据进行聚类，得到一个初始聚类结果， 然后再用另外一个算法处理初始结果，最后得到最终的聚类结果。 吴文丽等学者将基于蚂蚁堆形成原理的蚁群聚类算法和k - m e a n s 算法结合得到混 合聚类算法【2 刀。首先使用蚁群聚类算法得到一个初始聚类结果，包括初始聚类个数和聚 类中心。然后，将这个结果作为k m e a n s 算法的输入，由k m e a n s 算法得到最终结果。 周新华、黄道等学者将基于蚂蚁觅食的聚类算法与f c m 聚类算法相结合【2 8 1 ，先利 用蚁群算法产生f c m 算法的聚类个数和初始聚类中心，再利用f c m 算法对初始结果 进行精细聚类。利用蚊群算法的全局搜索性、并行性等特点避免了f c m 聚类算法容易 陷入局部最优解的问题。 当然，上述两种混合算法的组合方式比较简单，都是各个算法按顺序使用一次。也 有学者采用了多次使用各个算法的方式。 针对基于蚁堆聚类算法最终聚类的数目太高，而且收敛很慢的问题，m o n m a r c h e 1 4 中国石油大学( 华东) 硕士学位论文 建议一个网格可以放置多个对象，每个放置了多个对象的单元相当于一个簇。每只蚂蚁 具有承载或放下多个数据的能力。同时，m o n m a r c h e 建议结合k m e a n s 方法进行聚类【3 3 1 ， 主要步骤如下： 先用蚁群算法形成初始的簇，此时蚂蚁还是只拾起或放下一个数据对象，且在算法 收敛前就停止蚂蚁算法。然后使用k m e a n s 算法排除初始聚类中的小错误，分配被蚂蚁 搬运着的或仍单独存在于单元格上的对象。由于k m e a n s 算法只是局部优化算法，此时 得到的聚类结果质量还不够高，需要再使用蚁群算法处理这个中间结果。这次蚁群算法 处理的对象是数据堆，可以像单个对象那样拾起或放下这些堆。蚁群算法执行完后，再 次使用k - m e a n s 算法进行处理，从而得到最后的聚类结果。这样得到的聚类结果质量 比较高。 通过文献调研发现，诸如k m e a n s 算法、模糊c 均值算法等具有“均值 思想的 算法在与蚁群算法的组合中使用得较多，原因是此类算法有坚实数学依据，计算精确， 能较好地处理大数集。因此，本文选择k ，m e a n s 算法与改进的a n t c l u s t 算法进行组合。 与此同时，在改进a n t c l u s t 算法时，力求将k m e a n s 算法的某些思想运用到其中；再 次，结合两种算法的特点，设计出一种多层次的组合方式，而不是各个算法按顺序使用 一次的简单方式，从而能够提高算法的性能和聚类质量。 2 3 聚类有效性评价方法 聚类过程实际上是一个寻找最优划分的过程，即根据聚类质量的评价准则或方法对 划分进行不断地优化，直到得到最优划分【3 4 1 。由于聚类是无指导的学习，而且事先并不 知道数据集的结构，因此，最终的聚类结果都需要进行有效性和质量的评价。如何能用 一种客观公正的评价方法来评判聚类结果的有效性是一个非常重要的问题。它关系到判 定某个聚类算法是否可以对数据进行有效聚类，也就是该聚类算法的存在和使用是否有 意义。 广义上讲，聚类有效性评价包含对聚类结果质量、聚类算法适合某种特殊数据集的 程度、某种划分的最佳聚类数目等方面的评估【3 5 1 。 常用的聚类有效性评价方法有相对评价法、内部评价法和外部评价法 3 4 - 3 8 】。 相对评价法寻求聚类算法在一定假设和参数下能获得的一个最好聚类结果。它根据 预定义的评价标准，针对聚类算法的不同参数