（通信与信息系统专业论文）kmeans聚类优化算法的研究.pdf

：二 i l t r e s e a r c ho nk - m e a n s o 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 s h ix i u l i n g b e ( h u n a nu n i v e r s i t yo f t e c h n o l o g y ) 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 r t h ed e g r e eo f m a s t e ro f e n g i n e e r i n g c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m s 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 r m a r c h ，2 0 1 1 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名：史奄盼 日期：力7 ，年s 月“日 学位论文版权使用授权书 本学位论文作者完令了解学校有关保留、使用学位论文的规定，同意 学校保留并向困家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密同。 ( 请在以上相应方框内打“4 ) 作者签名：丧奄玲 f l , 甘a ：7 、, 17 年岁月确 导师签名： 日期：驯移旃 ； 摘要 聚类是数据挖掘中颇为藿要的技术，其功能是按照某种准则将数据划分成组。 k - m e a n s 算法是一种被广泛使用的聚类算法，本文主要对该算法做深入的分析和研究。 k - m e a n s 算法具有简单易行、高效性等优点。但是，该算法具有对初值选择的依赖性和 敏感性、易受孤立点影响、易陷入局部最优等缺点。为此，本文提出并设计了两类改进 算法，主要工作内容如下： 1 针对初值选择依赖性的不足，采用初值优化方法完成聚类。首先采用了一种基于 密度、距离和邻域的初始化中心点的方法；然后，将其用于改进标准的k - m e a n s 算法； 接着，进一步结合动态聚类和粗糙聚类的思想，设计了一种k - m e a n s 粗糙聚类算法。实 验结果表明，改进算法在较大程度上弥补了k - m e a n s 算法的不足，提高了聚类结果的稳 定性和有效性。 2 针对易陷入局部最优的不足，设计混合算法实现聚类。在分析和研究k - m e a n s 算 法与差分进化算法的特点的基础上，提出了一种基于差分进化算法的k - m e a n s 聚类算法。 该方法将二者有机的结合，充分发挥k - m e a n s 算法的局部搜索能力和差分进化算法的全 局寻优能力。实验结果表明，可以更有效的提高聚类质鼍。 关键词：聚类算法；初值优化；k - m e a n s 算法：k - m e a n s 粗糙聚类算法；差分进化算法 a bs t r a c t c l u s t e r i n gi sav e r yi m p o r t a n tt e c h n o l o g yo ft h ed a t am i n i n g a c c o r d i n gt oc e r t a i n r u l e s ，t h ef u n c t i o no fc l u s t e r i n gi st od e v i d et h el a r g ed a t as e t si n t og r o u p s k - m e a n s a l g o r i t h mi sw i d e l yu s e df o rc l u s t e r i n ga l g o r i t h m t h i sp a p e rd e e p l ya n a l y s i sa n ds t u d i e so f k - m e a n s a l g o r i t h m k - m e a n sa l g o r i t h mi se a s y t ob ea c h i e v e da n dh i g he f f i c i e n - t h o w e v e r , k - m e a n sh a ss o m ed e 拇畿船i t i v et oi n i t i a lv a l u e ，e a s yt ob ei m p a c t e db y o u t l i e r , e a s yt og e ti n t oal o c a lo p t i m u m f o rt h i sr e a s o n , t h i sp a p e rd e s i g n e dt w ok i n d so f i m p r o v e da l g o r i t h m m a i nw o r kh a sb e e nd o n ea sf o l l o w s ： 1 i l 培a ts e n s i t i v et oi n i t i a lv a l u e ，i n i t i a lv a l u eo p t i m i z a t i o nm e t h o di su s e df o r c l u s t e r i n g f i r s to fa l l ，am e t h o di sd e s i g n e dt h a ti su s e dt oi n i t i a l i z ac e n t e rb a s e do nd e n s i t y , d i s t a n c ea n dn e i g h b o r h o o d t h e n , k - m e a n sa l g o r i t h mi si m p r o v e db yt h em e t h o d t h e n , f u r t h e rc o m b i n e dt h e t h o u g h t so fd y n a m i cc l u s t e r i n ga n dr o u g hc l u s t e r i n g ，ak i n d o f k - m e a n sr o u g h c l u s t e r i n ga l g o r i t h mi sd e s i g n e d f i n a l l y , e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e i m p r o v e da l g o r i t h mc o m p e n s a t e sf o rs h o r t a g eo fk - m e a n sa l g o r i t h mi nm o r ed e g r e e ， i m p r o v i n gs t a b i l i t ya n de f f e c t i v e n e s so fc l u s t e r i n gr e s u l t s 2 a i m i n ga te a s yt og e ti n t oal o c a lo p t i m u m ，h y b r i da l g o r i t h mh a v e b e e nd e s i g n e dt o r e a l i z ec l u s t e r i n g t h ep a p e rp r o v i d e das y s t e m a t i ca n a l y s i sa n d s t u d yo f t h ec h a r a c t e r i s t i c s o fd i f f e r e n t i a le v o l u t i o na l g o r i t h ma n dk - m e a n s o nt h i s b a s i s ，k m e a n sc l u s t e r i n g a l g o r i t h mb a s e do nd i f f e r e n t i a le v o l u t i o na l g o r i t h mh a v eb e e nd e s i g n e d t h em e t h o di s d e s i g n e do nt h eb a s eo ft h eo r g a n i cc o m b i n a t i o no ft h et w o t h em e t h o dg i v e sf u l lp l a yt o l o c a ls e a r c ha b i l i t yo fk - m e a n sa l g o r i t h ma n dg l o b a lo p t i m i z a t i o na b i l i t yo fd i f f e r e n t i a l e v o l u t i o na l g o r i t h m e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ec l u s t e rq u a l i t yc a nb em o r e e f f e c t i v e l yi m p r o v e d k e yw o r d s ：c l u s t e r i n ga l g o r i t h m s ；i n i t i a lv a l u eo p t i m i z a t i o n ；k - m e a n sa l g o r i t h m ； k - m e a n sr o u g hc l u s t e r i n ga l g o r i t h m ；d i f f e r e n t i a le v o l u t i o n a l g o r i t h m 目录 摘要i a b s t r a c t i i 第一章绪论 1 1 研究背景和意义l 1 2 国内外研究概况3 1 2 1 数据挖掘现状3 1 2 2 聚类研究现状4 1 3 本文工作5 1 4 本文结构6 第二章聚类概述 2 1 聚类7 2 1 1 聚类概念7 2 1 2 聚类过程8 2 2 聚类相似性度量8 2 2 1 数据结构8 2 2 2 相似性度量方法9 2 3 聚类准则1 1 2 4 聚类评价13 2 5 聚类方法15 2 5 1 聚类方法l 5 2 5 2 常用算法1 5 2 6k - m e a n s 算法16 2 6 1 算法思想l7 2 6 2 算法流程17 2 6 3 算法特点l7 2 7 聚类应用2 0 2 8 本章小结2 1 第三章基于初始中心点优化的k - m e a n s 粗糙聚类算法 3 1 k - m e a n s 算法对初值的依赖性2 2 3 2 粗糙k m e a n s 聚类算法2 4 3 2 1 粗糙集理论2 4 3 3 3 4 3 5 3 6 3 7 3 8 3 9 第四章 4 1 4 2 3 2 2 粗糙k - m e a n s 聚类算法2 5 基本定义2 6 高密度区域选取方法2 7 初始中心点优化算法2 8 3 5 1 算法思想2 8 3 5 2 算法流程2 8 3 5 3 算法分析2 9 基f 初始中心点优化的k - m e a n s 算法2 9 基于初始中心点优化的k m e a n s 粗糙聚类算法2 9 3 7 1 基本定义3 0 3 7 2 算法描述3 0 3 7 3 算法分析3 l 仿真实验3 l 3 8 1 实验设计3 2 3 8 2 实验结果与分析3 2 本章小结3 7 基于差分进化算法的k - m e a n s 聚类算法 差分进化算法3 8 4 1 1 研究背景3 8 4 1 2 基本思想3 9 4 1 3 算法特点4 0 4 1 4 算法研究及应用4 1 基于差分进化算法的k - m e a n s 聚类算法4 2 4 2 1 基本思想4 2 4 2 2 算法流程4 4 4 2 3 复杂度分析4 5 4 3 实验结果及分析4 6 4 4 本章小结4 7 第五章结论与展望 5 1 结论4 8 5 2 展望4 8 参考文献5 0 蜀谢5 4 附录a ( 攻读硕士学位期间发表录用论文) 5 5 第一章绪论 本章首先阐明了本文选题的研究背景和意义，介绍了数据挖掘的相关概念、 功能、发展和应用，以及它的一种重要的技术一一聚类。然后，着重阐述了数据 挖掘以及聚类的国内外研究现状。接着，综述了本文的创新点和所作的主要工 作。最后，概述了本文的组织结构。 1 1 研究背景和意义 近年来，随着计算机技术、网络技术的飞速发展和普及，以及数据库技术、 数据库管理系统的迅猛发展和广泛的应用，同时数据采集j 【具的日益先进，获取 数据信息的手段越来越广阔，积累的数据知识也随之急剧增加【1 l 。人们希望更好 的利用数据，从中获得有用的信息、价值以及知识。然而，在获得了大量的数据 的同时，也增加了提炼有用信息的难度。目前的数据库技术对海量的数据进行录 入、统计以及查询等功能具有高效性，但是对于隐藏在数据背后的潜在的价值信 息，却略显无能为力。因此，数据的日趋涌入但缺乏强有力的分析工具，从而产 生了数据爆炸知识缺乏的窘境。面对这一挑战，为了能够对已有的数据有效的分 析处理，进行科学研究、企业管理和商业决策，在这种背景下，数据挖掘( d a t a m i n i n g ，d m ) 应运而生【2 】。 数据挖掘【1 1 ，又被称作数据库中的知识发现，是指从很多的、随机的、不确 定的、有噪声的、不完备的数据中，提取隐含在里面的有潜在意义的信息或知识 的过程。数据挖掘的功能主要有聚类、分类、关联分析、概念描述、孤立点分 析、时序模式、预测和偏差分析。简单而言，它就是一种深度分析数据的工具。 一般情况下，数据挖掘能够处理任意类型的信息，包括了关系数据库、事务数据 库、面向对象数据库、时间序列数据库、数据仓库、空间数据库、多媒体数据库 以及文本数据库等等。数据类型可以是结构化、半结构化以及异构璎。 数据挖掘是一门新兴的交叉的学科，融合了模式识别与人工智能、数据库技 术、机器学习、神经网络模型、数据的町视化、信息检索、统计学、图像与信号 处理等多学科的理论知识【l l 。目前国内外已经进入了数据挖掘的应用阶段，已应 用于市场营销、生物科学、保险行业、网络管理、金融投资等领域。数据挖掘可 以智能的将数据转化为有价值的信息，不仅可以描述数据过去的发展，还可以预 测以后的发展趋势1 1 】。所以，数据挖掘技术正在蓬勃发展，已成为一个崭新的、 藿要的和热点的研究领域。 聚类分析3 】作为数据挖掘中诸多技术中的一个重要的方法，倍受关注。它可 以用f 分析数据并发现有价值信息，基于的思想是物以类聚，按照一定的标准将 样本数据划分为若干个分组，并尽可能的满足同一类中的样本最相似，而不同类 中的尽可能的相异。聚类分析已涉足到很多领域，例如数据挖掘、人工智能、统 计学等等，应用也相当的广泛，例如市场销售、地理学、天文学、生物学、信息 检索、文本挖掘、图像分割等。数据的日益增多，也促使了聚类技术的发展，聚 类分析已成为一个非常有挑战的研究方向。 k - m e a n s 算法【4 】是用于聚类分析的一个典型的方法。当用该算法在聚类时， 优点是简单、快速、高效等等，但适用的范围有一定的局限性，还存在着种种的 不足之处。由于聚类应用的范围广，没有一种通用的算法适用于各种各样的领域 要求，所以，对于聚类算法中的不完善，有必要对它做进一步的研究，以完善理 论，推广算法，扩大应用。 差分进化算法【5 j 是一种启发式优化算法，与其他启发式优化算法的不同之处 是，差分进化算法是以种群差异为基础的启发式的随机搜索方式。差分进化算法 具有原理相对简单、比较容易实现、控制参数少、鲁棒性好、全局搜索能力强等 特点，是一种有效的、智能的、全局收敛的优化技术。近年来，该算法在国外是 一个研究热点，在国内的研究还相对薄弱，但是i f 受到国内学者的e 1 益关注，其 应用领域也不断扩大【6 】。 针对传统的k - m e a n s 算法存在的缺点，首先从算法自身着手，对其改进。其 次，由于差分进化算法的优点以及它的一个霞要的研究方向是与其他算法进行融 合，为此，将差分进化算法应用到k - m e a n s 算法。改进后的k - m e a n s 算法的有效 性以及聚类质量在很大程度上得到了提高。所以，本课题的研究具有理论意义和 使用价值。 2 数据挖掘是一种用于处理数据的蓬勃发展的技术，涉及到神经网络、机器学 习、数据库技术、人： 智能等多学科。聚类作为数据挖掘的莺要技术，其功能主 要是对数据进行分析并从中发现有价值的信息。本节介绍将数据挖掘以及聚类的 国内研究现状。 1 2 1 数据挖掘现状 科学技术特别是人工智能学科的发展和数据库技术的应用，为数据挖掘的产 生和发展创造了良好的条件。数据挖掘的最初思想可以追溯到上个世纪的七十年 代，是一个逐渐演变的发展过程。随着计算机的存储和运算速度的提高，以及数 据库中的存储技术的发展，研究者开辟了用机器学习作为数据分析的方式。在机 器学习中，首先将一些范例问题输送给计算机，这些问题是已知的并且已经成功 解决了的，然后让机器学习这些成功的例子，最后总结并且产生相应的规则。生 成的规则有一定的通用性，可以用于解决具有某些共同特征的问题。之后，神经 网络产生并逐步发展，知识工程又成为研究者的注意点。知识工程的过程是直接 把已经代码化的规则输送给计算机，然后让计算机使用它们来解决问题。专家系 统是它的一个典氆的应用，但不足之处是投资较大且效果不好。 到了八十年代，新的神经网络技术促使人们又回到了机器学习中，八十年代 末，在美国举行的第十一届国际人工智能联合会议上首次提出术语k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) ，并用它对数据挖掘过程的实质进行描述， 因此数据挖掘( d a t am i n i n g ，也称为数据开采) 常被简称为d m 或者k d d 。在此 之后的国际学术会议的重点慢慢的从理论转到应用。一九九三年，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 的技术专刊，此后在其他领域的 学术期刊中也专题专刊讨论知识发现和数据挖掘，比较权威的有i e e e 知识与数 据工程汇刊以及a c m 数据库系统汇刊等等著名杂志期刊。数据挖掘的概念 是于一九九五年在美国召开的计算机年会上提出的，此后数据挖掘便逐渐被人们 所熟知。 一九九八年，第四届知识发现与数据挖掘国际学术会议在纽约隆藿召开，有 很多多家软件公司相继开发了数据挖掘应用的系统。在北美和欧洲的很多国家引 3 入了这些软件。很多公司开发了数据挖掘工具，其中有i b m 公司开发的i b m d b 2 、 q u e s t 和i n t e l l i g e n tm i n e r ；s p s s 和s a s 作为两大统计软件公司，开发了 c l e m e n ti n e 和e n t e r p r is em i n e r ；w a r e h o u s es t d i o 是由s y b a s e 公司研制；s g i 开 发了s e t m i n e r 软件等等。 此外，国外的一些学者也在数据挖掘领域硕果累累，比如h a nj i a w e i ，他是 加拿大大学的从事国际知识发现的权威学者，组织了数据挖掘研究的课题小组； 以及以学者r a g g r a w a l 为首的i b ma l m a d e n 实验窀。 数据挖掘的研究在国内起步较晚，国内的研究力量主要集中在学校、研究所 和企业，研究领域也较广，主要是算法的研究与改进等理论上的研究以及实际的 应用。直到一九九三年，国家自然科学基金才开始大力关注数据挖掘的项目研 究。目前大部分研究项目是由国家自然科学基金和8 6 3 计划等政府资助的。学术 界、商业界等不断的重视数据挖掘的研究和应用。九十年代中后期在一些核心期 刊刊物如计算机学报和软件学报等刊出了一些理论成果。目前还主要集 中在理论研究上，应用研究在逐渐深入，应用的成功范例也较少，研发产品也更 是甚少，还未达到整体力量。 从1 9 9 5 年数据挖掘概念被提出到现在，数据挖掘已经取得了相对较大的进 展。近年，g a r m e rg r o u p 进行的一次高级技术调查中发现，在即将到来的5 年 内，数据挖掘和人工智能会跻身为5 大高新技术的首要位置并对工业带来重大效 益；在未来的五年内，成为投资焦点的十大新兴技术排名中，数据挖掘位二f 第二 位。 1 2 2 聚类研究现状 目前很多领域都需要用到聚类分析，针对信息时代的数据海量的特点，研究 有效的和适用的算法是聚类分析的重要方向。一般，算法的研究方向主要有，不 断改进现有算法和创造出新的算法。聚类分析在发展的初期，是统计学的分支， 主要的方法是基于距离的。随着人们把注意力转到机器学习时，聚类就成了无监 督学习的一个范例。因此，传统的聚类算法一般都局限于这两个学科中，已不满 足于当今数据量大、数据复杂性高等特点，致使算法显现出了效率低和开销大等 不足【1 。但是面对各种领域的各式各样的数据，要寻找到一个万能的聚类算法又 4 是极具困难。通常情况f ，一个算法可以解决一个或者两个方面，可以解决多个 方面的算法少之甚少，而目前最大的难题是处理含有噪卢的高维数据。 传统的聚类算法实质上是爬山算法，存在着两个主要的缺陷，一是常会陷入 局部最优；二是在面临数据量较大时，表现出不合适和花费大量时间的不足。于 是，如何高效的处理大规模高维度数据分布的规律及其模式，在聚类分析中有极 其重要的意义。为了提高算法性能和效率，以满足对聚类算法越来越高的要求， 达到更好的为数据挖掘的功能服务的目的，所以，不断的改进传统的算法，而且 引入其他学科的研究成果，例如图论、模糊数学、神经网络、粗糙集理论和人工 智能等，特别是近年新兴的混沌理论，由于该理论的优点，在无线通信系统和多 载波调制技术的应用中取得了良好的效果1 8 - - 9 1 ，在聚类分析中也卓有成效1 1 1 1 。 同时结合其他领域的优化方法，例如模拟退火算法、遗传算法、粒子群算法、蚁 群算法以及近几年兴起的人工免疫系统等等，取长补短。目前众多学者们探索的 一个焦点是使用的比较多的聚类方法中的划分的方法、层次算法等等，其中有 k m e a n s 算法、模糊c 一均值算法等等。 聚类分析目f j i 研究的方向主要表现在算法的町伸缩性、海量高维数据的分析 处理、聚类算法对于数据分布的形状的复杂性和数据类型多样性的有效性、存在 障碍约束条件的方法的性能等等。聚类分析富有挑战性，随着它的应用领域的飞 速扩大和理论应用研究的逐步深入，将会取得更加丰硕的研究和应用成果。 1 3 本攻腓 聚类足数据挖掘中的一个基本问题和一项重要的分析技术，本文主要研究用 于聚类分析的方法，重点探讨了k - m e a n s 聚类算法。主要内容如下： 1 基础知识概况。阐述数据挖掘以及聚类的基本概念、原理等，对聚类的相 关知识做了归纳和总结。然后，详细介绍聚类分析的一个经典算法一k - m e a n s 算 法，阐述基本思想，分析和归纳优缺点及其改进方法。 2 从k m e a n s 算法自身角度改进。针对k - m e a n s 算法的缺点，首先基于高密 度区域的思想，设计了一种初始中心点优化的算法；其次，将该算法用f 改进 k m e a n s 算法，设计了基于初始中心点优化的k m e a n s 算法，克服了标准 k m e a n s 算法随机选取初始聚类中心的缺陷；最后，基f 初始中心点优化的算法 5 和粗糙聚类的思想，又进一步的设计了基于初始中心优化的k - m e a n s 粗糙聚类算 法。克服了k - m e a n s 算法对初值的依赖性、易受孤立点影响等不足，改善了聚类 结果不稳定的不良后果。 3 引入差分进化算法到k - m e a n s 算法中形成混合算法。在k - m e a n s 算法的基 础七，将差分进化算引入到其中，形成一种混合算法。由于差分进化算法全局搜 索能力强，k - m e a n s 算易陷入局部最优，为此，将二者结合，以使得混合算法具 有优良的性能。 4 改进聚类算法的实现。选用国际通用的专门用于测试的数据集，将改进后 的算法用m a t l a b 编程实现，得出实验结果，与其他文献的算法结果进行对比，分 析实验结果。最后，对本文所做的工作进行评价。 1 4 本文结构 本文的主要工作是针对k m e a n s 算法的不足，对其做了改进，本文内容的组 织结构如下： 第一章：绪论，主要概述了论文的研究背景、意义以及目前的研究进展，本 文所作的工作以及文章的组织结构。 第二章：聚类概述，主要介绍了聚类的相关知识，为后面章节做理论基础。 详细介绍了k - m e a n s 算法的基本思想和算法流程，主要分析了算法的优缺点以及 改进方法。 第三章：基于初始中心点优化的k - m e a n s 粗糙聚类算法，首先介绍k m e a n s 算法对初值选择的依赖性及目前主要的选择方法。接着详细介绍改进算法，该算 法首先采用高密度区域的思想，然后再从高密度区域中基于密度、距离和邻域选 择初始聚类中心。然后，将该算法用于优化k - m e a n s 算法，并进一步设计了一种 k - m e a n s 粗糙聚类算法，最后，用实验结果表明改进后的算法性能得到了提高。 第四章：基于差分进化算法的k - m e a n s 算法，算法首先采用高密度区域的思 想预处理数据，然后引入差分进化算法到k - m e a n s 算法中，用该混合算法从高密 度区域中选择初始聚类中心并进行聚类，最后分析实验结果。 第五章：总结和展望，总结全文内容，客观评价在本课题中所作的：i = 作，并 在本文的基础七探讨下一步的研究工作。 6 第二章聚类概述 聚类分析是数据挖掘中的重要的技术之一，用来发现数据源中未知的信息。 在现实生活中，聚类问题是普遍存在的。比如，人类叮以区分动植物，是通过不 断的积累和加工思想意识中的聚类模型的一个过程。聚类的应用也不断的深化， 聚类的研究也不断的深入。本章主要介绍聚类的基础知识。 2 1 聚类 聚类是获取有价值的信息的重要方法，在本小节中主要介绍聚类的基本概念 和对聚类算法的要求，在进行数据处理时所遵循的聚类的过程。 2 1 1 聚类概念 聚类是数据挖掘的一个特别蘑要的方法。所谓聚类就是按照事物的某些属 性，把一个数据集合聚集成多个簇，使得簇中的对象相似度大，而与其他簇中对 象的相异度大【1 2 】。相异与相似度是根据样本集中对象的属性值来获得的，通常 采用距离作为衡量的方法。 聚类通常被认为是一种无监督的学习过程，因为无需通过预先指出分类信息 或者训练数据的案例，来指明样本之间本身应具有什么样的联系。数据挖掘中的 聚类与分类既相联系又相区别【1 3 1 。二者都是把未知模式的数据分成多个类；二 者的区别是，分类是一种有监督学习过程，需要预先给出样本集的特征信息，而 聚类的目的是要找出数据信息。所以，一般情况下，聚类分析用于样本集的预处 理，以实现对数据的进一步分析与处理。 一个有效的聚类算法需要满足下面的条件：( 1 ) 簇内的对象相异度弱； ( 2 ) 簇之间相异度强。聚类质量的好坏，一般与采用的相异度度量方法以及如 何实现有密切关系，与该聚类算法能否发现潜在的模式有关也有一定的关系。 7 2 1 2 聚类过程 聚类任务遵循一定的过程，图2 1 给出了聚类过程的步骤。 首先是数据特征选择，需要适当的选择特征，尽可能多的提取对任务有用的 信息，该步骤的主要目的是信息冗余的减少和最小化。相似性度量是定量两个特 征向量之间是否相似的条件，一般采用欧式距离作为一个简单的度量方式。然后 选择合适的聚类算法进行聚类。接下来需要结果验证，因为只要使用了聚类算法 且得出了聚类结果，就需要对其正确性进行验证。在结果判定时，一般情况下， 相关领域的专家需要用其他的实验数据及分析，作为判定聚类结果的先验知识， 最后得到i f 确的结论。 图2 1 聚类的过程 样本之间的相似性是聚类的重要内容， 象的区分是建立在相似性的度量的基础上。 结构以及常用的度量方法。 2 2 1 数据结构 是衡量聚类质量的重要依据。样本对 本节将介绍在聚类分析中常用的数据 在本小节中介绍了聚类分析应用中的两种常用的数据结构，为介绍聚类算法 的类与类之间以及对象与对象之间相异度度量的方法做准备。 1 数据矩阵 如果一个样本集合有t 个对象，用而，而，而表示，每个对象有，个属 性，则用j 个属性表示t 个对象的数据结构，这种数据结构可以看成是关系表形 8 式，也可以看作t x l 矩阵的形式。比如说，采集学生的成绩数据时，可以使用姓 名、学号、班级、性别以及各门学科来体现。数据矩阵表示的足一个样本集中的 所有对象及其属性，表示方法如下所示： 西1 五。 而， 毛l 五l ( 2 1) 2 相异度矩阵 一个样本集合中的f 个对象，两两对象之间具有一定程度的相似性，样本而 和样本_之间的相似性用d ( x , x ，) 表示，则，个对象的相似性可以用一个f f 的矩阵表示。 0 d ( x 2 x 1 ) 0 d ( x s x a ) d ( x 3 x 2 ) 0 d ( 薯西) d ( x ，x 2 ) 0 ( 2 2 ) d ( x 。x ，) 之值一般是一个非负数，其数值越小，表示两个样本对象越相似；值 越大，表示样本对象间越不一样。在通常情况下，聚类算法的相似度度量方法是 建立在相异度矩阵的基础之上。 2 2 2 相似性度量方法 当用聚类去解决某一问题时，聚类的结果是由不同的簇组成的，这些簇集之 间要满足聚类的最重要的一个条件，即较低的簇内相异度和较高的簇间相异度。 相似度度最的方法也是多种多样，针对特定的聚类问题，相似度度量方法的选择 至关藿要。下面介绍常用的簇间相异度和簇内相似度的度量方法。 1 簇与簇之间的相似度度量方法 很多的聚类算法在聚类过程中会计算簇与簇之间的距离。因为两个簇的距离 有多种定义方式，没有一个统一的标准，所以造成了计算的难度。假设有两个簇 尺。和r ，下面介绍几种常见的计算方式。 9 ( 1 ) 质心之间的距离。质心，也就是簇的中心。若可以获得用以代表每个 类的质心，并用这些质心来表示相应类的中心时，质心距离就是两个类中心的距 离。 ( 2 ) 平均值。即某一个簇内的所有对象与另外一个簇内的所有对象的两两 之间的距离的平均值。 ( 3 ) 中心点之间的距离。如果使用一个簇的中心点来表示聚类中心，聚类 中心之间的距离是两个类别的中心点间的距离。 ( 4 ) 单连接距离。即某一个簇内的所有对象与另外一个簇内的所有对象两 两间的距离的最小值。 ( 5 ) 全连接距离。即某，一个簇内的所有对象与另外一个簇内的所有对象两 两间的距离的最大值。 2 对象与对象之间的相似度度量方法 相似度计算是聚类分析算法的基本组成部分，如何来衡量对象与对象的相似 性，对聚类的结果有着直接影响。相似度的度量方法的选择对于聚类问题而占至 关重要。通常，在应用中通过距离的计算来衡量样本与样本的相似性。对于数值 类型的数据而言，大多数聚类算法都是直接或者间接的使用欧几里得距离公式， 比如基于划分方法的k m e a n s 算法、基于层次方法的b i r c h 算法和c u r e 算法、基 于密度的d b s c a n 算法等等。 如果一个样本集合中有f 个对象，两个对象分别为样本和样本，每个对 象有，个属性，则两个对象之间的距离d ( ，0 )，下面介绍几种常见的距离的计 算方法。 ( 1 ) 欧几咀得距离，也就是欧氏距离，定义如下： d ( ，- ) = ( ( ，m 一) 2 ) j ( n = l ，2 ，z ) ( 2 3 ) ( 2 ) 曼哈顿距离 ( 3 ) 马氏距离 ， d ( ，o ) = l - 5 1 ( n = l ，2 ，) ( 2 4 ) n = l d ( ，0 ) 2 = ( 一0 ) rv 。1 ( 一0 ) 其中v _ 1 为样本协方差的逆矩阵，t 表示的是求矩阵的转置。 1 0 ( 2 5 ) ( 4 ) 切氏距离 d ( ，0 ) = 1 l d l 乞一i ( 5 ) 斜交距离 d c ，= ； 喜妻c ，m 一。，c ，肼一，欠。 在数据标准化处理后，r n ，为和，之间的相关系数。 ( 6 ) 兰氏距离 毗，= 喜剖 ( 7 ) 明考斯基距离 ， d ( ，o ) = ( ( 厂肼一) 9 ) 叮 n = l ( 2 6 ) ( 2 7 ) ( 2 8 ) ( 2 9 ) 从公式( 2 9 ) 我们可以看出，当g = l时，它表示的是曼哈顿距离；当 g = 2 时，它就变成了欧几罩得距离。 通常距离函数的结果满足一定的数学要求，所以距离d ( ，)也依此满足下 面的要求： ( 1 ) 距离是非负值，即d ( ，) 0 。 ( 2 ) 一个样本与它本身的距离为零，即d ( ，r j ) = 0 。 ( 3 ) 距离函数是对称的，即d ( ，) = d ( r j ，) 。 ( 4 ) 满足- - 9 0 不等式，即d ( ，r j ) d ( ，r h ) + d ( r h ，r j ) 。 2 3 聚糊0 上一节中介绍了在聚类过程中如何划分数据集归类的方法，那么，又是如何 确定聚类完成或者聚类过程结束呢? 因此还需要一定的聚类准则函数作为判定的 标准1 1 4 1 。准则函数的作用是尽叮能的把属于同一个簇的对象聚到一起，把属于 不同簇的对象分离。准则函数评价一个聚类结果的质量，因为在聚类过程中，若 聚类的结果不满足准则的要求，就需进一步执行聚类过程，以使聚类结果最优， 所以准则函数的选择对聚类质量非常重要。一般情况下，有两种方式来确定准则 函数： 1 试探法 这种方式依赖丁二经验和主观判断，针对具体问题，首先在样本分配给某一个 簇时，规定对象间相似性测度的范围，即一个阈值：然后依照某一种最邻近测度 规则将样本分配给某一个簇。比如，使用反映样本间的邻近程度的欧氏距离，将 一个样本分配给两个簇之一时，需要定义一个阈值作为聚类的判定规则。 2 目标函数法 聚类的目的是按照不同的簇相异度最大的原则将样本进行聚合分类，所以聚 类准则是体现各个簇之间分离程度的函数。由丁二簇是由具有相似性对象所组成， 所以簇的相异性与对象具有直接关系。因此，定义一种目标函数，它足样本和簇 之问关系的函数，这样，就将聚类问题转化为求目标函数最优的值的优化问题。 常见的指标函数有下面三种： ( 1 ) 误差平方和准则函数 这种准则函数在聚类分析时最常用。假设样本集合为尺= ，吒， ， ) ，通过聚类过程被聚类为七个簇，分别为置，马，墨，每个簇分别包含 的样本的个数为：，定义误差平方和准则函数为： ( 2 1 0 ) 式中，巳 表示第歹个簇的中心，即该簇中所有样本的均值，表示为： 巳= 去霎。一啦，七 可以发现，样本被聚类为七个簇时，t ，函数描述的是总误差平方和。显而易 见，当函数值越大，误差就越大，聚类的效果越差。所以，聚类过程就是寻找 使得，函数值最小的结果，即目标函数的最优值。这种方式的聚类过程一般被叫 做最小方差划分。，函数一般适用于聚类结果表现为簇内样本较密集且各个簇内 样本对象数目相差不大的情况。如果各个簇内的样本数悬殊较大，为了达到函数 值最小的效果，可能会出现将大簇分割的现象。 ( 2 ) 加权平均平方和准则函数 该函数定义如下： j = p ，f ( 2 1 2 ) 其中岛表示先验概率，可以用各个簇内样本数坍，和样本集合总数目聊 1 2 2 巳 一 o 乙脚 七一 = ， 来估计，即： ：生，l i ：1 ，2 ， k (213p-j 221 3 ) ，= 一，j = ， () 。 m f 表示簇内对象之间平方距离的平均值，即： f = m j ( m l j - 莓驴们2 ( 2 簇q中样本的个数为m 1 ，该簇内对象的两两组合的种类数总共为： 竺坐孚竺，”一厂o ：表示为簇哆 中样本之间的平方距离之和。 r e r ，e r ， ( 3 ) 类间距离和准则 为了对聚类结果中各个簇间的距离的情况进行描述，用类间距离和准则函数 以及对其的加权来表示，即： 以= ( c 厂c 棚) r ( c 厂c 棚) j = l k 以= p ， 厂c 棚) r o 厂c 口，) ( 2 1 5 ) ( 2 1 6 ) 式中，c j为第_ ，个簇中所有样本的均值，c u h 表示全体对象均值，即： = 去善 ，p ，表示先验概率。以和以 表示的是簇之间的分离程度， 函数值越大，则各簇之间的相异性越大，聚类质量也就越好。 目前已有很多种聚类算法，但是每种聚类算法基本上只是对数据特征的某一 方面进行优化。例如，簇间距的最大化、簇内距的最小化。随着聚类技术的不断 推广，不同的应用范围对聚类的要求不同，所以就产生了很多种不一致的聚类评 价标准，同时聚类算法的标准自身也值得研究。目前从某几个方面来衡量一些通 用的聚类算法，而没有一个客观的标准。对于聚类的评价标准差要有以下方面： ( 1 ) 良好的可扩展性。聚类算法不仅可以处理小数据集，而且在面临一个 大数据库时，也需要具有处理大的、复杂的数据集的能力。 1 3 ( 2 ) 可用性和可解释性。因为聚类分析是用来解释特定的应用问题的，所 以得到的聚