（计算机软件与理论专业论文）数据挖掘中聚类算法的研究.pdf

摘要 随着信息技术的迅速发展，人们积累了大量的数据。如何从这些冗余数据中提 出对人们有用的信息就成了如今亟需要解决的问题。数据挖掘技术就在这种背景下 应运而生，并且发展了几年就已经成为目前数据库和信息决策领域最为热门的课题 和方向之一。作为数据挖掘中的一个重要分支，聚类分析是通过分析数据的相似性 把大型数据集合分类，使得在同一个类里面的数据最为相似，而不同类中的数据又 彼此相异，得到很好的分类效果。 本文主要研究了聚类算法，所做的主要工作如下： 1 利用密度聚类算法收敛速度快，层次聚类算法可以在不同粒度水平上对数据进 行探测，而且容易实现相似度量或距离度量的优点，发现了一种新的基于密度的层 次聚类算法，克服了层次聚类算法时间复杂度的问题，得到比较好的聚类结果。 2 将免疫算法引入模糊聚类算法，克服了模糊聚类算法对初始值敏感容易陷入局 部最优的问题。新的聚类算法能够在不给定初始簇数目的条件下得到准确的聚类结 果。 3 结合传统聚类算法与模糊聚类算法。利用密度算法对中心点不敏感的优点， 将密度算法应用于模糊聚类，得到新的聚类算法应用于数据量大的数据集时，它的 准确率要明显高于模糊聚类算法和免疫算法。 关键词：聚类算法；c 均值算法；密度聚类算法；层次聚类算法；免疫算法；自适应聚 类算法。 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y , t h ed a t a b a s em a n a g e m e n t s y s t e mh a v e b e e na p p l i e dm o r ea n dm o r ew i d e l y , a n dt h es i z eo ft h ed a t a b a s eh a sc o n t i n u e dt o e x p a n d ，p e o p l eh a v ea c c u m u l a t e dm a s s i v ea m o u n to fb u s i n e s sd a t a , a n dh o wt of i n dt h e v a l u a b l ei n f o r m a t i o ni nt h ev a s to c e a n l i k ed a t ah a v eb e c o m ea nu r g e n tn e e dt ob es o l v e d f r o mt h i sd a t am i n i n gt e c h n i q u e sh a v ee m e r g e d ，w h i c hi so n eo ft h em o s tc u t t i n g - e d g e r e s e a r c ho ft h ed a t a b a s ea n di n f o r m a t i o nd e c i s i o n m a k i n g c l u s t e ra n a l y s i sa sa ni m p o r t a n t b r a n c ho fd a t am i n i n gi st h ea n a l y s i so fd a t a ss i m i l a r i t y , a n dd i v i d e dt h e l a r g ed a t as e t si n t o g r o u p s ，i nw h i c ht h ed a t ai n s i d et h es a m eg r o u pw a sm o s ts i m i l a rt oe a c ho t h e ra n dt h ed a t ai n d i f f e r e n tg r o u p sw a sd i f f e rf r o me a c ho t h e r c l u s t e r i n gi sa ne f f e c t i v em e a n so f f i n d i n gu s e f u l i n f o r m a t i o n b a s e do nt h ea b o v es t u d y , t h i sp a p e rm a i n l yd i s c u s s e sc - m e a n sc l u s t e r i n gm e t h o dw h i c h b a s e do nt h ei m m u n eg e n e t i ca l g o r i t h ma n dp a r t i c l es w a r l l l o p t i m i z a t i o na l g o r i t h ms e p a r a t e l y f o l l o w i n g i st h em a i n w o r kh a sb e e nd o n e ： 1 u s i n gd e n s i t yc l u s t e r i n ga l g o r i t h mf a s tc o n v e r g e n c e ，h i e r a r c h i c a lc l u s t e r i n ga l g o r i t h m s c a nb ea td i f f e r e n tl e v e l so fd a t ag r a n u l a r i t yt od e t e c t ，a n dv e r ye a s yt oi m p l e m e n ts i m i l a r i t y m e a s u r eo rd i s t a n c em e t r i ca d v a n t a g e st oa c q u i r ean e w d e n s i t y b a s e dh i e r a r c h i c a lc l u s t e r i n g a l g o r i t h m ，t h eh i e r a r c h i c a lc l u s t e r i n ga l g o r i t h mt oo v e r c o m et h et i m ec o m p l e x i t yo ft h e p r o b l e m ，g e ta b e t t e rc l u s t e r i n gr e s u l t s 2 t h ei m m u n ea l g o r i t h mf u z z yc l u s t e r i n g a l g o r i t h m ，f u z z yc l u s t e r i n ga l g o r i t h mt o o v e r c o m et h ei n i t i a lv a l u es e n s i t i v ee a s i l yt r a p p e di n t ol o c a lo p t i m i z a t i o np r o b l e m a n dt h e n e wc l u s t e r i n ga l g o r i t h mc a nn o tc l u s t e rt h eg i v e ni n i t i a lc o n d i t i o n s ，t h en u m b e ro fa c c u r a t e c l u s t e r i n gr e s u l t s 3 c o m b i n i n gt h et r a d i t i o n a lc l u s t e r i n ga l g o r i t h m sa n df u z z yc l u s t e r i n ga l g o r i t h m f o c a l p o i n tf o rt h eu s e o fd e n s i t ya l g o r i t h mi sn o ts e n s i t i v et ot h ea d v a n t a g e so ft h ed e n s i t yo f f u z z y c l u s t e r i n ga l g o r i t h mi sa p p l i e dt oo b t a i nan e wc l u s t e r i n ga l g o r i t h mi sa p p l i e dt ol a r g ed a t a s e t st h ea m o u n to fd a t a ，i t sa c c u r a c yr a t ew a ss i g n i f i c a n t l yh i g h e rt h a nt h ef u z z y c l u s t e r i n g a l g o r i t h ma n di m m u n ea l g o r i t h m 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 ；cm e a l lc l u s t e r ；d e n s i t yc l u s t e r i n ga l g o r i t h m ； h i e r a r c h i c a lc l u s t e r i n ga l g o r i t h m ；i m m u n ea l g o r i t h m ；a d a p t i v ec l u s t e r i n g a l g o r i t h m i j 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名： 却影i 中b 序叼影i 中b 启 e l 期：矽( 哞厂月p 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密冈。 ( 请在以上相应方框内打“ ) 作者签名： 导师签名： 却叶m 罗可 日期：沙【o 年3 月f 7 日 日期：扣i 厶年6 月2 、日 第一章绪论 1 1 数据挖掘概述 由于目前数据存储及收集等方面技术的迅速发展使得人们可以收集大量的 数据，这也造成了数据增长的速度远远超出从海量数据中提取对人们有用信息的 能力。虽然人们利用目前的数据库系统可以快效地实现数据的查询统计等功能， 但却没办法从中发现数据中存在的关联，传统所采用的分析数据方法已远不能满 足现实的需要。因此如何从海量数据中提取有用的信息，就成为一项非常艰巨而 重要的工作。人们迫切需要一种能够对数据进行深层次加工的自动化技术。能够 从海量的数据中提取知识和信息。数据挖掘d m ( d a t am i n i n g ) 技术就是在这种背 景下应运而生。数据挖掘出现于上世纪8 0 年代，于9 0 年代迅速发展，到了2 1 世纪仍然持续繁荣。还有许多与数据挖掘相近的术语，如数据库中的数据分析、 知识发现、决策支持等。数据挖掘技术将人工智能中的机器学习与数据库管理系 统相结合，用机器学习的方法来分析数据，用数据库管理系统来存储数据，自动 发现隐藏在少量数据中的有用知识。数据挖掘涉及了模式识别、机器学习、统计 学、知识获取、数据可视化、智能数据库、高性能计算等多个领域，是门交叉性 的学科，并着重讨论了那些隐藏在大型数据库中的发现技术模式的可行性、可伸 缩性及可行性等问题。从数据库中发现出来的知识可以用在信息管理、过程控制、 科学研究、决策支持等许多方面。数据挖掘技是面向应用的。它不仅是面向特定 数据库常规的使用，而且要对这些数据进行多层次综合、分析及推理等，以寻求 实际问题的解决方案，并企图发现事件间的相互联系，甚至还能利用现有的数据 对未来的事件进行推测【l 】。 从世纪9 0 年代开始，随着数据库技术和信息技术的飞速发展，人们可以非常 方便地通过各种渠道获取和存储大量的数据。传统的数据分析软件在面对大规模 的数据时只能进行一些简单的处理( 如统计、查询等) ，而不能获得数据之间的内 在联系及所包含的信息。要摆脱这种的困境，就需要一种能够把数据智能地转换 成对人们有用信息和知识的工具，数据挖掘技术正是在这种对强有力数据分析工 具的迫切需求下应运而生。 1 2 国内外研究现状 通俗的讲数据挖掘就是从数据库中发现有用知识，1 9 8 9 年8 月在美国召开的 第1 1 届国际人工智能联合会议的专题讨论会上【2 】首次出现了k d d ( k n o w l e d g e d i s c o v e ri nd a t a b a s e ) - - 词。紧接着在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行过d m 和k d d 讨论会，来自各个领域的研究人员汇集在一起集中讨论海量数据分析算 法、数据统计、知识运用、知识表示等问题。1 9 9 5 年在加拿大召开了第一届知 识发现( k n o w l e d g ed i s e o v e r yi nd a t a b a s e g o d ) 和数据挖掘( d a t a m i n i n g - d m ， 也称数据开采) 国际学术会议。从此数据挖掘开始成为热门课题。数据挖掘可以 说是“知识发现”概念的进一步表现。随着越来越多的研究人员及部门参与， k d d 会议开始将系统应用作为研究重点，并注重多种学科的相互渗透。1 9 9 9 年， 在北京召开的第三届p a k d d 会议收到近两百篇学术论文，足见数据挖掘已经成 为了当时的热门学科；数据库、信息处理、人工智能、知识工程等领域的国际学 术刊物也纷纷开辟了数据挖掘的专题或专刊，包括( ( a c m 数据库系统汇刊，数 据与知识工程，( ( i e e e 知识与数据工程汇刊，( ( a c m 杂志，v l d b 杂志， 智能信息系统国际杂志等【3 】。 在网络上也有不少数据挖掘方面的电子出版物，其中最著名的是半月刊杂 志( k n o w l e d g ed i s e c o v e r yn u g g e t ) 【4 1 。在网上还有很多这方面的论坛，如中文的 数据挖掘研究院。计算机网络和信息工程、并行计算处理等其他领域的国际学会、 学刊也把数据挖掘和知识发现列为专题讨论。 随着数据挖掘的出现，人们从海量数据中发现有用知识和信息成为了可能。 如今己有很多专门的小组，从事这方面的研究。比较著名的有r a g g r a w a l 领导 下的i b m a l m a d e n 实验室，还有国际k d d 知名学者加拿大s i m o n f r a s t e r 大学 韩加文( h a n j i a w e i ) 教授领导的课题组【5 1 。他们提出了很多很好的算法，为该领 域的发展奠定了深厚的基础。当今，数据挖掘技术正在蓬勃发展。数据挖掘技术 在该领域所展现出的应用价值吸引了众多的研究人员和商业机构。一批数据挖掘 系统也随之被开发出来，并在商业、金融、经济、管理等领域都取得了应用性成 果。目前，世界上比较有影响的数据挖掘系统有：i b m 公司的i n t e l l i g e n t m i n e r ， s a s 公司的e n t e r p i s e m i n e r ，s p s s 公司的c l e m e n i i n e 等。很多网站上也提供了 许多数据挖掘系统和工具的测试报告。以上系统代表了自2 0 世纪9 0 年代以来的 2 数据挖掘技术的发展概况。采用的发现方法综合了数据库、模式识别、专家系统、 统计学、机器学习、科学发现和数据分析等领域的研究成果。但总的说来，这些 系统在人机交互、系统效率等方面仍不尽人意【6 】。 到了2 1 世纪，数据仓库的出现为数据挖掘技术提供了新的用武之地，同时 也提出了更高的要求和挑战。如今数据挖掘和数据仓库的研究已经结合起来综合 考虑。数据挖掘在此前的研究对象主要是一般的数据库系统，并由此发展起来相 应的理论和方法。随着数据仓库的出现，数据挖掘现在将平台转移到数据仓库上 来。由于数据仓库与一般数据库本身所具备的不同特点，使得数据挖掘在数据仓 库上的研究发展提出了新的要求。 目前学术界和工业界对数据挖掘的广泛关注，充分体现了数据挖掘是目前国 际上信息决策和数据库的最前沿研究方向之一。一份最近的g a r t n e r 报告中显示， k d d 在今后3 到5 年内工业界将产生重要影响的五项关键技术中排名第一。同 时，这份报告认为今后5 年内公司应该投资的l o 个新技术领域中包括并行计算 机体系结构研究和k d d 7 1 。与国外相比，国内对数据挖掘的研究相对稍晚，不 过目前也有相当一部分的人员和单位在从事数据挖掘方面的研究。1 9 9 3 年国家 自然科学基金第一次支持数据挖掘领域方面的研究项目。北京系统工程研究所对 知识发现中模糊聚类方法的应用进行了深入研究：北京大学在对数据立方体代数 方面也进行了研究：华中科技大学、中国科技大学、复旦大学、中科院数学研究 所、吉林大学、浙江大学等单位开展了在关联规则挖掘算法的优化和改造方面进 行了探讨：上海交通大学、南京大学、四川大学等单位讨论分析了非结构化数据 的知识发现以及网络上的数据挖掘【s 】。 知识发现技术的发展虽然只经过了十几年，还远没有达到全面应用的程序， 但已有各方面的专家及研究人员，结合自己的专业，做了大量出色的工作。“数 据挖掘 的概念自从被提出以来，就得到了飞速的发展。只有从信息中及时地发 现知识，从数据中有效地提取信息，才能为人类所用，为人类的思维决策和战略 发展服务【圳。 1 3 数据挖掘的应用与发展趋势 随着越来越多的人参与到数据挖掘技术的研究中，这一技术已经越来越成 熟，很多技术已经应用于实践。目前，k d d 技术己经在许多领域得到应用并取 3 得了一定的成效，其中包括生物医学、气象领域、金融、保险业、d n a 、医疗 保健分和电信业等。 ( 1 ) 天文学、气象领域：气象卫星每天传回地球的气象数据非常巨大，如果想 仅凭着传统的数据分析工具已很难处理，因此功能更强大的智能化自动分析工具 在这种推动下应用而生，这种需求同时推动了k d d 技术在科学研究领域的应用 发展，并且已获得许多重要成果。 ( 2 ) 生物医学：人类有大约1 0 0 0 0 0 个基因，每个基因通常由成百个核酸按一定 次序组织而成。核酸按不同次序和序列可以形成不同的基因，因此这些序列的排 列组合将是个天文数字。从这些天文数字中找出导致各种疾病的特定基因序列模 式就成了极具意义及挑战性的问题。在数据挖掘中已经有很多有意义的序列模式 分析和相似检索技术，用数据挖掘来对基因进行分析是非常可靠及有效的。 ( 3 ) 医疗方面：通过分析医师的处方，药房可以判断哪些医师愿意购买他们的 产品：而通过分析病人的病史和当前用药，医师可以诊断如何用药并判断潜在的 问题。 ( 4 ) 金融方面：在银行业，数据挖掘技术能够帮助金融企业分析影响其业务的 一些关键因素，挖掘诸如平均一个优质客户能赚多少钱，平均一个不良客户能亏 损多少钱，创造新客户的成本有多少等方面的问题，从而帮助金融企业增加收入、 降低成本，使金融行业的管理决策更趋科学，客户分析更趋精确。 ( 5 ) 保险业：业务人员通过数据挖掘建立预测模型，识别出那些最有可能具有 欺诈性的赔偿要求，减少由于欺诈造成的损失。 ( 6 ) 电信行业：电信行业己经从单纯的提供通话服务演变成提供如语音、寻呼、 传真、移动电话、电子邮件和w e b 数据传输，以及其他数据通信服务的综合电 信服务。而且随着许多国家对电信业的开放和通信技术的发展，电信市场之间的 竞争变得更加激烈。因此，利用数据挖掘技术来更好地利用资源和提高服务质量 是非常有必要的【引。 数据挖掘在面对数据挖掘任务和数据挖掘方法的多样性时仍然具有很多困 难。如何开发数据挖掘语言、设计高效的数据挖掘方法、集成数据挖掘环境数据 以及如何用数据挖掘技术来解决当今比较大型的数据处理问题等，都是目前数据 挖掘研究和应用开发所面临的主要问题。目前，数据挖掘的研究方向和趋势主要 有： 4 ( 1 ) 数据挖掘应用研究 随着数据挖掘的应用越来越普及，它的应用领域从早期的帮助企业提高竞争 力等方面的应用扩展到如今包括：在网络入侵检测中的应用；数据挖掘在w e b 上 的应用。由于w e b 在当今的广泛利用，w 曲在当今社会扮演越来越重要的角色。 由于w e b 上存在海量数据信息，有关w e b 内容挖掘、w e b 日志挖掘和因特网上 的数据挖掘服务，将成为数据挖掘中一个最为重要和繁荣的子领域。 ( 2 ) 可伸缩的数据挖掘算法研究 数据挖掘所处理的数据是海量的，并且由于数据的持续增长，数据库的规模 也呈指数增长。因此开发针对单独的和集成的数据挖掘功能的可伸缩算法就显得 尤为重要。 ( 3 ) 可视化数据挖掘 可视化数据挖掘是指挖掘的结果容易被人理解，是发现知识的有效途径。通 过可视化数据挖掘，使数据更加形象生动。将数据通过图形展示，可以使用户或 分析人员更容易理解，因此可视化数据挖掘具有重要的应用价值。 ( 4 ) 复杂数据类型挖掘的新方法 数据挖掘在针对简单数据类型时能够入到比较好的结果，但事实上现实世界 更多的是复杂数据类型，而如何从复杂数据类型中挖掘出有用的信息，是数据挖 掘研究中一个重要的课题。虽然在地理空间挖掘、时序挖掘、多媒体挖掘等方面 取得了一定的成就，但是将它们运用到实际项目中却仍然有很长一段路要走，尤 其是如何用现存的数据挖掘技术对现存的数据类型进行集成，还需要更深入的研 究。 ( 5 ) 数据挖掘系统的交互性 尽管目前数据挖掘系统已经初步成熟，但是在人机交互上仍然存在严重不 足。数据挖掘中用户的背景知识和指导作用可以加快挖掘的过程，并且确保发现 的知识的有效性。一方面，交互界面接收用户查询要求及策略，为用户表达要求 和策略提供方便：另一方面，交互界面把系统分析的结果反馈给用户。反馈的结 果可以根据不同用户的需求以相应的形式展现出来，更加直观。因此，准确并且 直观地反映数据挖掘结果和友好而高效的用户界面也是目前一直在研究的课题。 ( 6 ) 数据挖掘中的隐私保护与信息安全 数据挖掘已经应用于日益普及的电信与计算机网络中，且取得了定的成 5 就。但是电信与计算机网络历来存在的隐私保护和信息安全的问题，也是数据挖 掘亟需要解决的。数据挖掘能从不同的维度和层面上分析数据，这将很容易侵犯 到数据的私有和安全性。因此需要继续改进数据挖掘的相关方法，以便在对数据 进行实际操作和挖掘中，即能满足用户的需求，又能实现数据的安全及隐私保护 【9 】 o 1 4 本文的内容及结构安排 本文详细介绍了数据挖掘中聚类方法的分类、主要问题与己有的解决方法， 介绍了传统聚类算法和扩展聚类算法。本文所做作工作主要有以下三点：首先在 传统聚类算法的基础上，提出了一种基于密度算法的层次聚类算法；然后又根据 模糊聚类算法，针对该算法对初始值敏感的缺点，提出了自适应的模糊聚类算法。 最后结合传统聚类算法和扩展聚类算法，提出了基于密度的模糊聚类算法。1 0 】。 本文的组织结构如下： 第1 章简要介绍了本文的课题背景、当前研究现状和研究内容，给出了研究 意义以及本文的主要工作。 第2 章详细介绍了数据挖掘中的聚类分析，介绍了聚类分析的数据结构和数 据类型，聚类算法的分类，并详细阐述了数据挖掘中用到的主要传统聚类算法以 及算法各自的优缺点。 第3 章介绍了一种对传统聚类算法进行了改进的聚类算法，并对改进的传统 聚类算法与改进前的聚类算法性能做了比较。 第4 章研究了基于划分的k - m e a n s 算法应用于聚类分析时所出现的缺点和不 足，对k m e a n s 算法进行改进，提出了自适应的c 均值模糊聚类算法。 第5 章中将模糊聚类算法与传统聚类算法进行了结合应用，得到新的模糊聚 类算法。最后通过仿真实验，对三种模糊聚类算法性能做了比较分析。 第6 章是总结和展望，总结本文所做的工作，并给出以后进一步的研究方向。 6 第二章聚类技术及其发展 2 1 聚类分析概述 俗话说“物以类聚”，即具有相同或相似个体通常聚在一起，聚类即是这样。 它是将具有相同或相似特性的个体划分为一类或一个簇，不同的个体分到不同的 类或簇中【l l 】。通常可以将一个簇中的个体或对象看成是一个整体。聚类分析是数 据挖掘的一项重要分支，而聚类算法是目前研究的核心与热点，聚类分析就是在 事先给定的样本集中使用聚类算法从中发现有意义的聚类。聚类并不等同于分类 或预测。大多数分类方法需要人们事先确定某种事物分类的标准与规则，分类过 程中就是比较分类的要素与各类别标准，然后将各要素划归于某一类中。因此如 何划分多少带有主观因素。但聚类分析是归纳的，并不需要事先确定分类的原则， 不考虑己知的类标记。通常训练数据中并不提供类标记，聚类的目标就是通过聚 类算法产生这种标记。聚类方法通过让簇内的对象相似性最大，簇与簇之间的个 体相似性最小来将对象进行分类，即对象的聚类这样形成。 聚类是一个非常热门且具有挑战性的研究领域，并且已经在数据挖掘实践中 取得了令人信服的成果，在实践中并不是仅仅采用某一种方法，而是采用多种方 法相结合。在实际需求中，数据挖掘对聚类的要求体现在以下9 个方面。 ( 1 ) 可伸缩性 可伸缩性是指算法不论对于小样本集还是大样本集，都应是可行的。在很多 聚类算法当中，对于数据对象在2 0 0 以下的小样本集时鲁棒性很好，而对于包含 成千上万个数据个体的大规模数据库进行聚类分析时，将会有得到不同的聚类结 果。另外随着数据库的不断增长，可伸缩性算法的运行时间应该呈线性变化。 ( 2 ) 处理不同字段类型的能力 聚类算法应该要具有处理不同类型数据的能力，包括分类标称类型，二元 类型( b i n a r y ) ，序数型( o r d i n a l ) ，或者这些混合数据类型。随着数据挖掘在商务、 科学、医学和其他领域的应用越来越广，处理多属性的技术也就显得尤为重要。 ( 3 ) 能够发现任意形状的聚类 有些簇具有规则的形状，但是更多的是簇可以具有任意形状。我们经常使用 欧几里德距离或曼哈坦距离来确定聚类，但基于这种方法的聚类往往只针对于球 7 状簇。对于一个簇可能是任意形状的情况，找到能发现任意形状簇的聚类算法是 很重要的。 ( 4 ) 处理高维数据的能力 很多聚类算法在处理低维数据如两到三维的数据具有很好的聚类效果。但是 在面对高维空间是却显得无能为力，或效果甚微，尤其是当这些数据是非常稀疏 的时候。例如，对不同地域进行测量所得到的温度数据集。如果温度是在同一个 地方很长的时间内反复地测量，则数据集的增长和测量的次数是成正比的。那些 针对低维数据开发的数据分析技术在面对这样的数据是通常不能很好地处理。 ( 5 ) 能够处理噪声数据 现实世界中的数据集经常包含那些空缺、孤立、未知数据或有错误的数据。 很多聚类算法常常会受这些孤立的数据所影响，得到比较差的聚类结果。因此我 们希望能够得到好的聚类算法，在面对这些孤立的噪声数据时，可以消除或者尽 量减少它们所带来的影响。 ( 6 ) 基于约束的聚类 在实际应用中对数据进行聚类时通常会遇到各种约束条件，聚类算法即要满 足这些特定的约束，又要得到良好的聚类特性。如何兼顾这两者，是聚类算法一 项具有挑战性的任务。 ( 7 ) 对记录输入顺序不敏感 一些聚类算法对于数据不同的输入顺序往往会得到差别很大的结果。如果一 个算法在处理同一个数据集时，仅仅因为该数据集数据的输入顺序不一样而产生 很大的差别，显然对于这样的算法，是不稳定的，也不是我们希望看到的结果。 因此研发出对输入顺序不敏感的算法就显得尤为重要。 ( 8 ) 可解释性和可用性 对用户而言，他们得到的信息应该是可理解和应用的，但是在实际挖掘中往 往不能令人满意。这对聚类算法提出的需求就是必须有一定的语义规则与解释。 聚类分析算法设计中领域的研究是一个很重要的研究方向【1 2 】。 2 2 聚类分析中的数据结构和数据类型 2 2 1 聚类分析中的数据结构 要对数据进行聚类分析，就需要把要聚类的对象按照一定形式组织起来。一 8 个好的数据结构将会对聚类的效率产生很大影响。本节主要介绍聚类分析中常见 的数据结构，以及在聚类分析之前是如何对它们进行预处理的。目前聚类算法一 般有如下两种有代表性的数据结构 ( 1 ) 数据矩阵( d a t a m a t r i x ，或称为对象变量结构) 数据矩阵是一个m * n 的矩阵，每列代表对象的一个属性，每个元组代表一 个数据对象。具有p 个属性的n 个对象( 如人的年龄、性别、籍贯) 可以看成 n * p 的矩阵【1 3 1 。 x l lx 1 2 x 2 lx 2 2 x 。lx 。2 x l 口 x 2 p x 印 ( 2 1 ) ( 2 ) 相异度矩阵( d i s s i m i l a r i t ym a t r i x ，或称为对象对象结构) 表现形式是n * n 维的矩阵，它用来表示n 个对象两两之间的差异性。 0 d ( 1 ，1 ) 0 0 d ( n ，1 ) d ( n ，2 ) 0 ( 2 2 ) 其中d ( i ，j ) 是对象i 和对象j 之间相异性的量化表示，d ( i ，j ) = d ( j ，i ) ，d o ， i ) = 0 。对象i 和对象j 越相似，表明它们之间的距离越近，则d ( i ，j ) 越接近于0 ， 相反，对象i 和对象j 的差异越大，表明它们之间的距离越远，则d ( i ，j ) 越大。 相异度矩阵是用距离公式计算得到。相异度矩阵又称为单模矩阵，它的行和列都 代表同一个样本个体。许多聚类算法一般都采用相异度矩阵。数据矩阵和相异度 矩阵可以相互转化 1 3 - 1 4 】。 2 - 2 2 聚类分析中的数据类型 聚类分析是从统计学发展而来的，因此以前的聚类分析方法一般以数值型数 据为研究对象。然而现实世界中的对象却并不仅仅是数值型的。概括地说，对象 属性包括的数据类型有标称型、二元变量、区问标度变量和序数型变量以及混合 类型的变量【b 】，这就要求聚类分析的方法不仅能够对属性为数值类型的数据进 行，而且要根据不同的数据类型进行相应的变化。 9 ( 1 ) 区间标度变量 区间标度变量的例子则包括经度和纬度坐标，以及温度等。为了将数据或对 象集合划分成不同类别，必须定义一个差异性标准来定义数据或对象间的差别。 同时要考虑不同的属性应该使用不同的度量单位。因为这些将影响到聚类分析的 结果，所以在数据进行差异性比较之前先要对数据进行标准化。 ( 2 ) - 元变量 二元变量只有两个状态：0 和1 。其中二元变量又分为对称的二元变量和不对 称的二元变量。前者是指变量的两个状态不具有优先权，后者对于不同的状态其 重要性是不同的。对称的二元变量的一个典型例子，如一台机器的丌与关状态。 ( 3 ) 标称型变量 标称变量是二元变量的推广，状态之间是无序的。具有这种数据类型的属性 也称分类( c a t e g o r i c a l ) 属性。例如，人的特性就是一个标称型变量，包括( 身高、 体重、性别等) 。 ( 4 ) 序数型变量 序数型变量类似于标称型变量，但它的各个状态是有意义的序列。序数型变 量对记录那些难以客观度量的主观评价是非常有用的。例如：在某个比赛中的相 对排名，如金牌、银牌和铜牌【1 6 舶】 2 3 传统聚类算法 2 3 1 基于划分的聚类算法 给定含有n 个个体的样本集，划分聚类算法要求事实给定簇的数目，通过使 目标函数最小的策略，将样本集划分为k 个簇类。因此划分聚类算法需要同时满 足以下两个条件：( 1 ) 每个簇至少包含一个数据个体；( 2 ) 每个数据个体必须属于且 唯一的属于一个簇。给定事先给定簇的数目k ，划分聚类算法首先创建一个预划 分，通常采用的方法是随机选取k 个数据个体作为初始聚类中心点，通过不断调 换簇内的个体来得到新的对象集，采用的准则是：在同一个簇中的数据对象尽可 能相似，不同的簇中的数据对象尽可能相异【1 9 2 1 1 。 基于划分的方法主要包括有k 平均值算法，k 中心点算法以及相应的扩展聚 类算法。由于下文将研究基于划分的k m e a n s 算法。下面对划分聚类算法进行介 绍。 1 0 1 、k m e a n s 算法 k m e a n s 算法的相似度计算根据一个簇中对象的平均值来进行。首先，选择 k 个对象作为初始的k 个簇的质心这个k 个对象的选择是随机的：然后计算样本集 中剩余对象与各个质心的距离，如果某个对象与某一质心距离最近，则将该对象 划分到该簇内，重复前一步，计算每个簇的质心。这个过程不断重复，直到目标 函数收敛。通常采用的准则函数为平方误差和最小目标函数，即 s s e ( s u mo f t h es q u a r e de r r o r ) ，其定义如下： s s e ：k 忪一m i l l 2 ( 2 3 ) 这里的s s e ( 平方误差和最小目标函数) 是样本集中所有对象个体的平方误 差总和，p 代表每个数据对象，m ，是每个簇c 的平均值。下面给出一般k m e a n s 算法的具体过程： ( 1 ) 给定大小为n 的数据集，选取k 个初始聚类中心z j ( i ) ，j = l ，2 ，3 ，k ( 2 ) 计算每个数据对象与聚类中心的距离d ( x ，z j ( i ) ) ，i = l ，2 ，3 ，n ， j = l ， 2 ，3 ，k ，如果满足 d ( x ，z 。( ，) ) = m i n d ( x ，z ，( ，) ) ，i = l ，2 ，3 ，n ) ( 2 4 ) 则x f c i ( 3 ) 计算k 个新的聚类中心 z + 1 ) = 去和门，j = k 晓5 ， ( 4 ) 判断：若z ，( ，+ 1 ) z ( ，) ，j 2 l ，2 ，3 ，k ，则i = i + 1 ，返回( 2 ) ，否则算 法结束【2 2 乏3 1 。 从上面聚类算法的步骤可以看出，由于初始中心点是随机选取的，不同的初 始中心点，其产生的聚类结果可能是不同的，因此如果有先验知识，选取具有代 表性的点，常常会有事半功倍的效果。 在步骤二中，计算每一个样本个体到质心的距离，这一步的时间复杂度为 o ( n k d ) ，其中n 样本集中所有样本个体的数目，k 是给定的簇类个数，d 是数据 对象的维数；每一次产生新的聚类，都要计算聚类中心，这个过程的时间复杂度 为o ( n d ) 。因此，这个算法一次迭代需要的总的时间复杂度为o ( n k d ) 。 假设给定如下要进行聚类的元组【2 4 1 ： 2 ，4 ，1 0 ，1 2 ，3 ，2 0 ，3 0 ，1 1 ，2 5 假设要求的簇的数量为k = 2 。 应用k - m e a n s 算法： 第一步：随机选取两个值作为质心，在这里，用前两个数值作为簇的质心， 这两个簇的质心分别是：m l = 2 ；m 2 = 4 ； 第二步：计算剩余数据对象与各个簇中心的距离，并将它赋给最近的簇， 可得： 2 ，3 ) 4 ，1 0 ，1 2 ，2 0 ，3 0 ，2 5 ) 数值3 与两个均值的距离相等，所以任意的选择k i 作为其所属的簇。 第三步：计算新的簇心 m 1 = ( 2 + 3 ) 2 = 2 5 ： m ：= ( 4 + l o + 1 2 + 2 0 + 3 0 + 1 1 + 2 5 ) 7 = 1 6 ； 对簇中的成员重新进行分配，可得k l = 2 ，3 ，4 ) 和k 2 = l o ，1 2 ，2 0 ，3 0 ， 1 l ，2 5 l ，不断重复该过程，得到下表的统计数据： 表2 1k 均值聚类算法 m lm 2k l k 2 31 8 2 , 3 ，4 ，1 0 1 2 ，2 0 ，3 0 ，1 i ，2 5 4 7 51 9 6 2 , 3 , 4 ，1 0 ，il ，1 2 2 0 ，3 0 ，2 5 7 2 5 2 , 3 ，4 ，1 0 ，1l ，1 2 2 0 ，3 0 ，2 5 从表2 1 可以看出，最后两步中簇的成员已经是一样了，均值不再变化，表 明均值已经收敛。 因此，该问题的答案为k 1 = 2 ，3 ，4 ，1 0 ，1 1 ，1 2 和k 2 = 2 0 ，3 0 ，2 5 。 k 模算法是k 均值算法的一个变体，是对k 均值的一个扩展。用模来表示类 的平均值，采用新的差异性度量方法对对象进行分类【2 5 1 。 k 原型算法是k 均值算法和k 模算法的一种综合算法，可以用来处理分类类 1 2 型属性和有数值类型的数据。e m ( e x p e c t a t i o n m a x i m i z a t i o n ) 算法使用若干统计分 布对数据建模，它根据对象与簇之间隶属关系发生的概率分配对象。而近年来应 用的比较多的模糊c 均值聚类算法，也是对传统k 均值聚类算法的扩展【2 6 之引。 2 、k 中心点算法 k m e a n s 算法对于孤立点敏感，一个噪声点可能对最终的聚类结果产生很大 的影响。选用簇类中位置最中心的个体，即中心点作为质心，则能够很好的处理 这些噪声点。 该算法基本思想：首先从样本集中为每个类随意选择一个对象作为代表；剩余 的对象根据其与该对象代表的距离，划分给最近的一个类。然后反复地用非对象 代表来替代对象代表，以改进聚类的效果。聚类结果的质量用一个代价函数来估 算。 p a m ( p a r t i t i o n i n ga r o u n dm e d o i d l 是最早提出的k 中心点算法之一【2 9 】。它 的基本策略是：最初随机选择k 个中心点后，该算法反复地试图找到更好的中心点。分析所有可能的对象对， 并将其中一个对象看成中心点。并根据各种可能的对象对分析聚类的质量。如果 有另一个对象所产生的最大平方误差值减少，则它将替代原来这个对象。而在这 一次迭代中产生的最优数据对象将作为下一次迭代的集合的中心点。该算法往往 得到比较好的聚类结果，但是当数据量比较大时，其时间复杂度和空间复杂度也 是相当高的。 2 3 2 基于密度的聚类算法 前一章已经提到聚类算法应该能够对任意形状的簇进行聚类，但实际上很多 使用距离来描述数据对象之间的相似性的聚类算法一般只针对球形簇聚类，在面 对任意形状的簇进行聚类时效果却很差，而本节提出的密度算法就是针对这种任 意形状的簇进行聚类的。基于密度的算法不仅能够对任意形状的簇进行有效聚 类，而且能够去除噪声点。比较典型的密度算法包括d b s c a n 和o p t i c s l 2 9 1 。 1 、d b s c a n 算法的主要思想是：只要在某个临近区域里的对象或数据点的数 目超过某个事先给定的值，该数据对象就属于此簇，该阈值往往根据先验经验设 定。然后继续聚类，直至所有的对象都唯一的划定到某一个簇中。 下面介绍一些有关密度的相关概念。 e 邻域：给定对象e 半径内的区域称为该对象的e 邻域。 核心对象：如果一个对象的e 邻域内包含至少m 个数据对象或者样本个 体，则该对象为核心对象，m 由用户根据先验经验给定。 直接密度可达：给定一个对象集合d ，如果p 是在q 的e 邻域内，而q 是 一个 核心对象，我们说对象p 从对象q 出发是直接密度可达的。 密度可达：如果在数据集d 中存在一条对象链p 。，p ：，p 。，对p 。属 于d ( 1 - i m i ) 根据密度划分将该n 个对象分为r 个新簇 修改n 和m i ，得到n i 和r i c l u s t ( n i ，r i ) ； f o r ( i = l ；i _ m i ；i + + ) 调用初始化优先队列子程序为每个区建立优先队列 w h i l e ( d i s t ( r ( i ) ，r ( j ) ) e ) b r e a k ； e l s e 合并r ( i ) ，r o ) 将剩下的k 个聚类用传统层次聚类算法进行聚合； r e t u r n 层次聚类图。 ) ) ) 2 1 3 3 仿真实验结果比较与分析 我们以包含2 4 0 个对象的二维示例数据集s a m p l e d 和美国加州大学信息与 计算机科学系的i r i s 数据集来对改进的层次聚类算法与传统层次聚类算法比较， 结果如下。 表3 1 传统聚类算法与改进聚类算法的比较 数据集维数对象个数聚类算法 m i 运算时间m s准确度 传统层次算法 91 6 4 09 4 4 s a m p l e d 22 4 0 改进层次算法 4 9 1 79 2 1 31 0 1 29 3 3 传统层次算法 61 0 2 49 5 2 i r i s41 5 0 改进层次算法 46 7 19 3 4 37 1 29 4 7 由实验结果可以看出，在保持结果的准确性的同时，改进的层次聚类算法在 时间上明显优于传统的层次聚类算法，并且根据不断的调整参数m i ，改进的层次 聚类算法还可以继续提高聚类准确度，从而很好的解决了层次聚类算法时间复杂 度过高的问题。 3 4 本章小结 本章在传统聚类算法的基础上提出了一种结合密度算法和层次算法的新的 聚类算法，并进行了仿真模拟，模拟结果显示，基于密度的层次聚类算法在时间 上明显优于传统的层次聚类算法，并且聚类结果也是非常准确的。 第四章扩展聚类算法的应用 在上两章中，系统地介绍了数据挖掘中的一些