（计算机科学与技术专业论文）基于seam算法的集成聚类及在文本应用中的研究.pdf

中文摘要 随着网络技术和数据库技术的快速发展，数据挖掘技术应运而生。聚类分析 是数据挖掘中的重要分支之，是一种数据划分的重要手段和方法。聚类的应用 是非常广泛的，无论是在商务领域，还是在生物学、w e b 文档分类、图像处理等 其它领域，都得到了有效的应用。 虽然有些聚类算法已经得到了广泛应用，但由于一般聚类分析算法对数据集 都有诸多的限制，所以很难找到一种算法适合所有的数据集。由此，聚类集成算 法应运而生。聚类集成是将多个对同一组对象的不同划分进行合并，而不使用对 象原有的特征。实验证明，该方法能够得到比单一算法更为优越的结果，但集成 聚类远未达到成熟的地步，如关键参数的确定、共识函数的设计等问题。在前人 工作的基础上，本文所做的工作如下： 1 在深入了解集成聚类算法的基础上，设计出一种新的集成聚类算法，基于 s e a m ( s q u a r e de r r o ra d j a c e n tm a t r i x ) 算法的集成聚类，简称为e s e a m 算法 ( e n s e m b l em e t h o db a s e do ns e a m ) 。首先得到数据集的多个聚类结果，即得到聚类 成员的集体；然后根据聚类成员的集体，得到可以反映原数据集分布的一个相似 矩阵；最后，将s e a m 算法应用在这个相似矩阵中，得到最终的聚类划分。文中 通过实验验证了该算法的有效性。 2 本文还对聚类分析的应用领域之一文本挖掘进行了研究。将文中所提出的 e s e a m 算法应用于文本中，并对实验结果做了分析。 由于集成聚类算法可以集成多个聚类算法得到的结果，而在给定相似矩阵的 情况下，s e a m 算法可以自动确定聚类数，所以e s e a m 算法避免了算法选择和聚 类数选择的双重问题。 关键词：数据挖掘；聚类；聚类集成；共识函数；s e a m 算法；文本聚类 分类号：t p 3 9 1 = | 匕宝垒适厶堂亟堂位途塞 垦s 王必! a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h en e t w o r ka n dd a t a b a s et e c h n o l o g y , d a t am i n i n gi s p r o d u c e d c l u s t e r i n gi so n eo f t h ei m p o r t a n tt a s k si nt h ef i e l do fd a t am i n i n ga n di sa n i m p o r t a n tm e t h o do fd a t ap a r t i t i o no rg r o u p i n g c l u s t e r i n gh a sb e e ns t u d i e di nm a n y r e s e a r c ha r e a si n c l u d i n gp a t t e r nr e c o g n i t i o n ，m a c h i n el e a r n i n g ，s t a t i s t i c a ll e a r n i n g ，d a t a m i n i n g ，t e x tm i n i n g ，a n dh a sb e e nu s e di n v a r i o u sa p p l i c a t i o nd o m a i n ss u c ha si n c o m m e r c e ，m a r k e ta n a l y s i s ，b i o l o g y , w e b ，c l a s s i f i c a t i o na n ds oo n a l t h o u g hs o m eo ft h ec l u s t e r i n ga l g o r i t h m sh a v e b e e na p p l i e dw i d e l y , i ti sh a r df o r p e o p l et of i n dt h es u i t a b l ec l u s t e r i n ga l g o r i t h mf o r ag i v e nd a t a s e t ，b e c a u s et h e r ea r e m a n yr e s t r i c t so nt h o s ed a t as e tf o rc l u s t e r i n g s oc l u s t e r i n ge n s e m b l e se m e r g e da st h e t i m e sr e q u i r e d t h ep r o b l e mo fc l u s t e r i n ge n s e m b l e si st oc o m b i n em u l t i p l ep a r t i t i o n so f as e to fo b j e c t sw i t h o u ta c c e s s i n gt h eo r i g i n a lf e a t u r e s e x p e r i m e n t a lr e s u l t sp r o v e dt h a t t h r o u g hc l u s t e r i n ge n s e m b l e sw ec a ng e tb e t t e rr e s u l tt h a ns i n g l ec l u s t e r i n ga l g o r i t h m b u tt h i sm e t h o di sf a rf r o mm a t u r e ，s u c ha st h ec h o i c eo fs o m ek e yp a r a m e t e r s ，t h e d e s i g no ft h ec o n s e n s u sf u n c t i o n s ，a n ds oo n t h em a i nw o r k si nt h i sp a p e ra r e d e s c r i b e da sf o l l o w s ： 1 o nt h eb a s i so fh a v i n gs t u d i e dc l u s t e r i n ge n s e m b l e st h o r o u g h l y , an e w m e t h o do fc l u s t e r i n ge n s e m b l e si sd e s i g n e di nt h i sp a p e r , t h ec l u s t e r i n ge n s e m b l e s b a s e do nt h es e a m ( s q u a r e de r r o ra d j a c e n tm a t r i x ) a l g o r i t h m ，c a l l e de s e a m ( e n s e m b l em e t h o db a s e do ns e a m ) a l g o r i t h mf o rs h o r t g i v e nm u l t i p l ep a r t i t i o n s o fad a t a s e t ，as i m i l a r i t ym a t r i xi sg e n e r a t e db ym e a s u r i n gt h ec o - o c c u r r e dt i m e so f p a i r so f d a t ao b j e c t si nt h es a m ec l u s t e r t h e nt h es e a ma l g o r i t h mi sa p p l i e do nt h i s s i m i l a r i t ym a t r i xt og e tt h ef i n a ld a t ap a r t i t i o n 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 i s m e t h o di se f f e c t i v e 2 t h et e x tc l u s t e r i n g ，o n eo ft h ea p p l i c a t i o nf i e l d so fc l u s t e ra n a l y s i si s r e v i e w e d t h ee n s e m b l em e t h o dp r o p o s e di nt h i sp a p e ri sa p p l i e do nt e x td a t a s e t t h ee x p e r i m e n t a lr e s u l t sa r ed i s c u s s e d c l u s t e r i n g e n s e m b l e sc a nc o m b i n et h er e s u l t so fm a n yi n d i v i d u a lc l u s t e r i n g a l g o r i t h m s ，a n dg i v e nt h es i m i l a r i t ym a t r i xt h es e a ma l g o r i t h mc a nf i n d t h ef i n a l p a r t i t i o n sa u t o m a t i c a l l yw i t h o u tp r e d e f i n i n gt h en u m b e ro fc l u s t e r so ro t h e ri n i t i a l i z e d p a r a m e t e r s s ot h ec l u s t e r i n ge n s e m b l e sa l g o r i t h mb a s e do nt h es e a ma l g o r i t h m ，t h e e s e a ma l g o r i t h m ，c a na v o i dt h ep r o b l e m so fc h o o s i n gt h ep r o p e rc l u s t e r i n ga l g o r i t h m a n dt h en u m b e ro fc l u s t e r sf o rag i v e nd a t a s e t 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 l g o r i t h m ；c l u s t e r i n ge n s e m b l e s ；c o n s e n s u s f u n c t i o n ；s q u a r e de r r o ra d j a c e n tm a t r i x ( s e a m ) a l g o r i t h m ；t e x td a t a s e t c l a s s n 0 ：t p 3 9 1 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：杨丽丽 签字h 期： 彻穸年 莎月同 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：桶丽丽 导师签名 签字日期：铆? 年矿月肜日 签字r 期： 致谢 本论文的工作足在我的导师于剑教授，贾彩燕老师的悉心指导和热心鼓励下 完成的。于老师宽广的学术视野，渊博的知识，高尚的学术道德，严谨的治学态 度和科学的工作方法都让我深感敬佩，他在科学研究上的孜孜不倦的进取精神深 深地激励和鼓舞着我。贾老师悉心指导我们完成了实验室的科研工作，在我论文 的完成阶段给了我细心的指导和帮助，在f 1 常的学习和生活上都给予了我很大的 关心和帮助。在此，谨向两位老师表示最真诚的感谢和崇高的敬意! 感谢在实验室工作及撰写论文期问，景丽萍老师和周雪忠老师的热心指导， 感谢各位评审老师和答辩老师对论文修改提出的宝贵意见。 感谢各位师兄、师姐和同学们的帮助，感谢人工智能实验室的所有同学，他 们给了我很多的指导和各种帮助，提供了很多有价值的参考意见，为我创造了一 个良好的学术讨论环境。他们给我的帮助，我将永远铭刻在心! 另外还要感谢我的父母和亲人，感谢我的男友刘合元，他们无私的关心和照 顾给予我无尽的温暖，使我安心于研究和学习；他们在精神上给予我的理解和支 持，是我坚持和自订进的动力。我的每一点进步，每一点成绩的取得，都离不开他 们的关心体贴和帮助。 感谢所有曾经给予我指导、帮助、关心和支持的人们! 1 1研究背景 1 绪论 近十几年，科学技术的飞速发展带动着经济和社会都取得了极大的进步。在 各个领域产生了大量的数据，如人类对太空的探索，银行每天的巨额交易数据。 显然在这些数据中存在着丰富的信息，如何处理这些数据并从中得到有益的信息， 人们进行了有益的探索。计算机技术、网络技术和信息技术的迅速发展，人们生 产和搜集数据的能力的大幅度提高，使得数据处理成为可能，同样也推动了数据 库技术的极大发展，但是面对不断增加的数据，人们不再满足于数据库的查询功 能，提出了深层次问题：能不能从数据中提取信息或者知识为决策服务，就数据 库技术而言己经显得无能为力了。同样，传统的统计技术也面临着极大的挑战。 这就急需有新的方法来处理这些海量的数据。 于是，人们结合统计学、数据库、机器学习等技术，提出数据挖掘来解决这 一难题。数据挖掘技术提出后显示出自i 所未有的强大生命力，并逐渐成为研究的 热点，吸引了很多人进行研究。而作为数据挖掘技术之一的聚类分析，无论是在 模式识别、数据分析，还是在图像处理和市场分析方向都有着广泛的应用，所以 越来越受到研究者的关注。由于聚类分析领域的长足发展，各种文献提出了众多 的聚类算法，可分为划分方法、层次方法、基于密度的方法、基于网格的方法、 基于模型的方法、基于相似矩阵的算法等。 虽然存在许多的聚类方法，但是没有一个通用的万能的聚类算法，能适合于 任何的聚类问题。由于单个聚类算法往往存在这样那样的问题，所以为了提高算 法的稳定性和平均性能，近年来出现了许多聚类集成算法的研究。集成聚类算法 将不同聚类算法或在同一算法下使用不同参数得到的结果进行集成，从而得到比 单一算法更为优越的结果。近几年的研究和实验表明，聚类集成方法可以很好的 提高聚类算法的鲁棒性和稳定性。目前，已经在医学诊断、基因表达分析、非数 值型数据聚类等方面有了一定的应用。因此，研究聚类集成方法有着广泛的科研 和实际应用价值。 1 2 数据挖掘技术 在过去的三十年，随着计算机硬件技术、数据收集技术和数据存储技术的快 速发展，人们利用信息技术生产和搜集数据的能力大幅的提高，各行各业都逐步 建立起自己各自的数据库体系。在这些数据库中存放着大量的数据，如何有效的 利用这些数据的背后隐藏的具有决策意义的信息，使之能为生产实践所利用，成 为企业面临的重要问题。随着数据库容量的膨胀，特别是数据仓库及w e b 等新型 数据源的同益普及，联机分析处理、决策支持以及分类、聚类等复杂应用成为必 然。在这种情况下，数据挖掘技术应运而生，并显示出强大的生命力。 从技术的角度讲，数据挖掘就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取出隐含在其中的、人们事先不知道的、但又是现实 有用的信息和知识的过程【l 】。人们把原始数据看作是形成知识的源泉，就像从矿石 中采矿一样。原始数据可以是结构化的，如关系型数据库中的数据，也可以是半 结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现 知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。 发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以 用于数据自身的维护。因此，它是计算机技术研究中的一个很有应用价值的新领 域，融合了数据库、人工智能、机器学习、统计学、知识工程、面向对象方法等 多个领域的理论和技术，目前已经成为国际上数据库和信息决策领域中最前沿的 研究方向之一，引起了学术界和工业界的广泛关注。 数据挖掘可以解决大量的商业问题，基于这些商业问题的性质，把这些问题 分成下面几种数据挖掘任务：分类和预测、聚类分析、关联分析、回归分析、序 列分析和偏差分析。由于数据挖掘带来的显著经济效益，使数据挖掘越来越普及。 数据挖掘可以应用在各个不同的领域。电讯公司和信用卡公司是用数据挖掘检测 欺诈行为的先行者。保险公司和证券公司也开始采用数据挖掘来减少欺诈。医疗 应用是另一个前景广阔的产业：数据挖掘可以用来预测外科手术、医疗试验和药 物治疗的效果。零销商更多的使用数据挖掘来决定每种商品在不同地点的库存， 通过数据挖掘更灵活的使用促销和优惠券手段。制药公司通过挖掘巨大的化学物 质和基因对疾病的影响的数据库来判断哪些物质可能对治疗某种疾病产生效果。 1 3聚类及聚类集成技术 聚类分析作为数据挖掘领域中的一个重要研究课题，是一种无监督的数据挖 掘技术，它是在预先不知道目标数据库到底有多少类的情况下，依据数据对象的 特点和对象之间的关系将所有的记录组成不同的类( 簇) 或者说聚类，其目标是 使得分在一个组内的对象具有较大的相似性，而分在不同组中的对象具有较高的 相异性。 2 聚类分析是人类活动中的一个重要内容。早在儿奄时期，一个人就是通过不 断完善潜意识中的分类模式，来学会识别不同物体，如狗和猫，或动物和植物等。 通过聚类，人可以辨认出空旷和拥挤的区域，进而发现整个的分布模式，以及数 据属性之问所存在有价值的相关关系。因此它广泛应用于模式。 叭1 - 1 别、数据分析、 图像处理和市场分析等许多领域。 在数据挖掘领域，大多数工作都集中在发现能够有效、高效地对大数据库进 行聚类分析的方法上。相关的研究课题包括：聚类方法的可扩展性、复杂形状和 复杂数据类型的聚类分析的有效高效性、高维聚类技术，以及混合数值属性与符 号属性数据库中的聚类分析方法等。基本的聚类方法大致可以分为如下几种类别： 基于划分的聚类算法、层次聚类算法、基于密度的聚类算法、基于网格的聚类算 法，基于模型的聚类算法，以及基于相似性的聚类算法等。 数据对象分布多种多样，虽然存在许多的聚类方法，但任何聚类算法都对数 据集本身有一定的预先假设，根据“n of r e el u n c h ”理论【2 】，如果数据集本身的分 布并不符合预先的假设，则算法的结果将毫无意义，甚至可以说该结果只是给出 了一个错误的分布，或是给数据集强加了一个虚构的分布，因此没有一个通用的 万能的聚类算法，能适合于任何的聚类问题。面对特定的应用问题，单个聚类算 法往往存在这样那样的问题，因此，如何选择合适的聚类算法是聚类分析研究中 的一个重要课题。 聚类集成算法的提出解决了上述问题。聚类集成算法将不同算法或者同一算 法下使用不同参数得到的聚类结果进行合并，从而得到比单一算法更为优越的结 果【3 】。在分类算法和回归模型中，集成方法已经发展的比较成熟，该方法能克服分 类、回归中的不稳定性，并给出较好的结果。但在非监督机器学习领域，由于缺 乏数据集的先验知识，所以分类和回归模型中的集成方法就不能直接用于聚类算 法，这导致了在聚类领域中对集成方法研究的起步较晚，近几年才开始出现。研 究和实验表明，聚类集成方法能很好地提高聚类算法的鲁棒性、稳定性等性能， 有着很好的发展自 景。 聚类集成算法是2 0 0 2 年由a s t r e h l 和j g h o s h 4 j 提出的，但早在2 0 0 1 年a 。l f r e d 【5 】就己经进行了类似的研究。聚类集成是将多个对同一组数据进行划分的不同 结果进行合并，在合并的过程中不使用对象原有的特征。在聚类集成中，先要产 生对数据集的不同聚类结果，然后对这些聚类结果进行合并得到一个一致的划分 结果。因此，近年来的研究也主要集中在两个方面：( 1 ) 如何产生有差异性的聚类 成员；( 2 ) 如何设计有效的共识函数以便对聚类成员进行合并。a t o p c h y 【6 】指出了 在鲁棒性、适用性、稳定性、并行性和可扩展性几个方面，聚类集成可以比单一 聚类算法得到更好的结果。 3 = 匕立銮适厶堂殛堂位| 佥塞绪途 现存的聚类集成算法远未达到成熟的程度，未来的研究可在以下方面展开i 3 j ： 1 参数的确定。确定聚类的个数足聚类分析研究的热点问题，在聚类集成中 如何确定每个聚类成员的聚类数、最终聚类的个数以及它们之f h j 的关系将是一个 值得探讨的问题。 2 在聚类成员的产生方面，需要进一步研究不同聚类算法之问的高效集成以 及选择不同聚类算法的准则。 3 聚类成员互不独立时的聚类集成，高维数据、海量数据的聚类集成，聚类 之问存在混叠数据的聚类集成都对聚类集成提出了挑战。 1 4论文的主要内容及组织结构 如前所述，聚类分析是数据挖掘的一项重要任务，但传统的聚类算法在一些 方面存在着局限，集成聚类的提出弥补了单一聚类算法的缺陷，但在现有集成聚 类的共识函数中，最终聚类数的确定一直是一个未解决的难题。本文提出了一种 可以自动确定聚类数的共识函数，避免了聚类数选择的问题，并将该算法在人工 数据集，u c i 标准数据集和文本数据集中分别做了实验，验证了算法的有效性。 本文的具体组织结构如下： 第一章为绪论，对数据挖掘技术，聚类分析技术进行简要介绍，然后简要介 绍聚类集成算法； 第二章重点介绍聚类分析的基础知识，描述了聚类分析的定义、研究内容、 发展现状、经典算法以及优缺点比较等； 第三章介绍了集成聚类技术，首先介绍了集成学习技术，然后从聚类成员的 生成，共识函数的设计和存在的问题三个方面详细阐述了集成聚类的发展现状； 第四章提出了一种新的集成聚类算法e s e a m 算法，首先介绍s e a m 算法的 思想，给出算法的具体步骤，然后介绍了基于s e a m 算法的集成聚算法( e s e a m 算法) 的思想及算法流程，文中选用了部分人工数据集和u c i 中的标准测试数据 集进行实验，验证了算法的有效性； 第五章将e s e a m 算法应用于文本数据集，这部分中首先介绍了文本处理的背 景知识，分析了文本的预处理过程，特征降维的常用算法，文本相似性的度量方 式，文本常用的聚类算法等，然后将e s e a m 算法应用在文本中，解决了文本聚类 中存在的聚类数选择和算法选择的问题，并通过实验验证了该算法的性能。 第六章是对论文内容和下一步研究方向的一个概括总结。 4 2 1聚类分析的定义 2 聚类分析基础知识 聚类分析起源于分类学，在考古的分类学中，人们主要依靠经验和专业知识 来实现分类。随着生产技术和科学的发展，人类的认识不断加深，分类越来越细， 要求也越来越高，有时单凭经验和专业知识是难以进行确切分类的，往往需要定 性的定量分析结合起来去分类，于是数学工具逐渐被引进分类学中，形成了数值 分类学。后来随着多元统计分析的引进，聚类分析又逐渐从数值分类学中分离出 来而形成了一个相对独立的分支【7 j 。 聚类是人类一项最基本的认识活动。“人以群分，物以类聚”，聚类作为一个 古老的问题，它伴随着人类社会的产生和发展而不断深化，人们要认识世界就必 须区别不同的事物并认识事物间的相似性。通过适当聚类，事物才便于研究，事 物的内部规律才可能为人类所掌握。 所谓聚类就是按照一定的要求和规律，把事物聚集成若干类或簇( c l u s t e r ) ，使 类内相似性尽可能大，类问的相似性尽可能小。聚类是一个无监督的学习过程， 它同分类的根本区别在于：分类算法是一个有监督的学习过程，它需要对标注数 据集合进行训练；聚类算法则不需要“教师”的指导，不需要提供训练数据，倾 向于数据的自然划分，因此被称为无监督的学习或自动学习。 在很多应用中，聚类分析作为一种数据预处理过程，是进一步分析和处理数 据的基础。例如在商业方面，聚类分析能够帮助市场分析人员从客户基本库中发 现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学中，聚 类分析能用于获取动物或植物所存在的层次结构，对基因进行分析，获得对种群 中固有结构的深入了解。聚类分析也可以用于在泥土观测数据库中对相似地区的 区分，也可以根据房子的类型、价值和地域对一个城市中的房屋进行分类。聚类 分析也能用于分类w e b 文档以便进行信息发现。作为数据挖掘的功能，聚类分析 也可以作为一个独立的工具，来帮助获得数据分布情况、观察每个类的特征和确 定感兴趣的类以便进一步分析。通过聚类，能够识别密集和稀疏的区域，发现全 局的分布模式，以及数据属性之间的相互关系等。 一个能产生高质量聚类的算法必须满足下面两个条件： ( 1 ) 类内( i n t r a c l a s s ) 数据或对象的相似性最强； ( 2 ) 类间( i n t e r - c l a s s ) 数据或对象的相似性最弱。 聚类结构的好坏取决于算法设计者对聚类的具体定义和表示，对象问的相似 5 度定义及聚类算法的具体实现。 聚类是一个富有挑战性的研究领域，它的潜在应用提出了各自特殊的要求。 一般来说，数据挖掘对聚类分析的典型要求如下【i j ： 1 可伸缩性 许多聚类算法在小于2 0 0 个数据对象大小的数据集合上运行良好；然而，大 规模数据库出现在越来越多的领域中，它们可能包含几百力个对象，在这样的大 规模数据集合样本上进行聚类可能会导致有偏差的结果，设计具有高度可伸缩性、 适用于海量数据的聚类算法显得尤为迫切。 2 发现任意形状的簇 许多聚类算法采用欧几旱德距离或者曼哈顿距离来衡量不同数据对象之间的 相似度，而基于这类距离的聚类算法总是趋向于发现具有相近大小和密度的球形 簇。然而，在实际应用中的数据集可能具有不同粒度和密度的簇，这些簇也可能 是任意形状的，因此，设计出能发现任意形状类集的聚类算法是非常重要的。 3 用于决定输入参数的领域知识最小化 数据挖掘用户非数据挖掘专家，常常只具有自己领域的背景知识。因此，输 入参数的确定对他们来说是相对困难的。许多聚类算法在聚类分析中要求用户输 入一定的参数，例如希望产生的簇的个数，聚类的结果通常都与输入参数密切相 关。这些参数通常很难确定，要求用户输入参数不仅增加了用户的负担，也使得 聚类质量难以控制。 4 处理噪声数据的能力 绝大多数真实世界中的数据集都包含孤立点、缺失数据甚至错误的数据。许 多聚类算法都对噪声数据较为敏感，并会导致较低质量的聚类结果。 5 对于输入对象的顺序不敏感 一些聚类算法对于数据集中对象的输入顺序较为敏感，对于相同的数据集， 不同的输入顺序可能导致截然不同的聚类结果，使得算法具有较差的稳定性，设 计对于输入对象的顺序不敏感的聚类算法也是非常重要的。 6 处理不同类型属性的能力 现有的大多数聚类算法通常都被设计为处理数值类型的数据。然而，真实世 界的应用中可能要求处理其它类型的数据，比如二元数据( 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 ) 数据，甚至这些类型的数据组合等。这对聚 类算法提出了新的要求，如何对不同类型的数据进行整合，也是目前的一个研究 热点。 7 高维性 在目前的许多应用领域中，都存在着高维数据集，例如文本数据库、电信领 6 域的帐务数据、音频视频数据等等。这给现有的聚类算法提出了更高的挑战，许 多算法只在处理低维的数据时运行良好。 稀疏性，传统的距离度量方式逐渐失效， 8 基于约束的聚类 此外，由于高维特征空间中数据同有的 这给聚类算法带来了很大的困难。 现实世界中的应用可能需要在各种约束条件下进行聚类。例如在某一城市中 确定一些新加油站的位置，就需要考虑到城市中的河流、高速路，以及每个地区 的客户要求等情况下居民驻地的聚类分析。设计能够发现满足特定约束条件且具 有较好聚类质量的聚类算法是一项具有挑战性的任务。 9 可解释性和可用性 数据挖掘的目标是找到可解释的、可理解的和可用的模式，也就是说，聚类 可能需要处理特定的语义解释和应用。因此，研究应用目标如何影响聚类方法的 选择是很重要的。 2 2相似性的度量方式 所有聚类技术的根本问题是两个对象间的距离或相似度度量的选择，选择适 当的相似性度量是保证聚类质量的重要问题。所以，在讨论不同的聚类算法之前， 首先来讨论相似性( 距离) 的度量。 刻画样本点之间的相似性主要有以下两类函数： 1 相似函数：描述两个样本之间的相似程度，两个样本越相似，则相似值越 接近1 ；两个样本越不相似，则相似值越接近0 ； 2 距离函数：两个样本点越相似，则距离越小，距离函数值越小；两个样本 点越不相似，则距离越远，距离函数值越大； 由上述描述我们可以发现，两个数据对象的相似函数和距离函数成反比关系， 两者之间的距离越小，则越相似，相反若两者之间的距离越大，则越不相似，显 然这是符合人们的一般认识的。 距离函数或相似函数在计算机中一般用一个相异度或相似度矩阵来表示，以 相似函数来举例，相似度矩阵是一个对象对象结构。它存放所有n 个对象彼此之 间的相似度。它一般采用行x n 矩阵来表示，如公式( 2 1 ) 所示。 l s ( 2 ，1 ) 1 s ( 3 ，1 ) s ( 3 ，2 ) 1 s ( n ，1 ) s ( n ，2 ) 1 7 ( 2 1 ) 其中s ( f ，j ) 表示对象f 和对象_ ，之i 日j 的相似程度。通常s ( i ，) 为一个 o ，l 】之间 的数；当对象f 和对象，非常相似或彼此“接近”时，该数值接近l ；该数值越小， 就表示对象f 和对象越不相似。由于有s ( f ，) = s ( ，f ) 且s ( i ，f ) = l ，因此就有上面所 示三角矩阵。许多聚类算法都是基于相似度矩阵进行聚类分析的。相异度矩阵的 定义与相似度矩阵类似，只不过矩阵中的值表示的是对象之间的差异程度。 聚类分析起源于统计学，传统的分析方法大多只能处理数值类型的数据。然 而在数据挖掘领域，要分析的对象复杂多样，这要求聚类分析的方法不仅可针对 属性为数值类型的数据，而且要可以处理其它类型的数据。一般而言，在数据挖 掘中，经常出现的数据类型有：区间标度变量、二元变量、标称型、序数型和比 例标度型变量。对于不同类型的数据，对象之间的相异度有着不同的度量方法。 下面就分别介绍聚类中常见的数据类型及其各自的相似性或距离的度量方式【7 】。 1 区间标度变量 区问标度变量是一个粗略线性标度的连续度量。典型的例子则包括重量和高 度，经度和纬度坐标，以及大气温度等。考虑到数据的多个属性使用的可能是不 同的度量单位，这将直接影响到聚类分析的结果，所以在计算数据的相似性之前 先要进行数据的标准化。 对于一个给定的有n 个对象的m 维( 属性) 数据集，可用公式( 2 2 ) 的方法进行 标准化： 首先计算平均绝对误差只 dz 蚓i g , , 一m 一 ( 2 2 ) & = 上l 一 、7 这罩表示的是第i 个数据对象在属性k 上的取值，m 。是属性k 上的平均 值，即： x i 。 m t2l 以 然后计算标准化度量乙 z 漾= b 啦一m k 、) isk 数据标准化处理以后就可以进行属性值的相似性测量了， 的距离。对于，z 维向量薯和工，有以下几种距离函数： 欧氏距离： d ( 薯，_ ) = 0 一_ 0 = 曼哈顿距离： ( 2 3 ) ( 2 4 ) 通常是计算对象间 ( 2 5 ) d ( 薯，_ ) = l 一颤i ( 2 6 ) 一般化的明考斯基( m i n k o w a k i ) 距离： d ( x i ，x v ) = i ( 吒一以) ”i ( 2 7 ) 当m = 2 时，明氏距离即为欧氏距离；当m = l 时，明氏距离即为曼哈顿距离。 2 二元变量( b i n a r yv a r i a b l e ) 二元变量只有两个状态：o 和1 。其中二元变量又分为对称的二元变量和不对 称的二元变量。如果一个二值属性的两个状态所表示的内容同样重要，则它是对 称的，否则是不对称的。 对于对称的二元变量，度量两个变量的差异度由简单匹配系数决定，而对于 非对称的二元变量，一般采用j a c c a r d 系数决定。设两个对象和x ，n ，。是属性值 在两个对象中都为1 的属性个数，啊。是属性值在薯中为l 而在x ，中为o 的属性个数， 是属性值在薯中为o 而在x ，中为l 的属性个数，l 。是属性值在两个对象中都为0 的属性个数。则简单匹配系数： d ( ，x s ) = * ( 2 8 ) n l l + n l o + n o l + n o o 、7 注意到n 。+ ，z 。为取值不同的属性个数，+ 刀，。为取值相同的属性个数。 j a c c a r d 系数： d ( ，x j ) = # 譬导 ( 2 9 ) 刀i i + o + n o l 、7 对于不对称的二值变量，如果认为取值1 比取值0 更重要，更有意义，那么对 于这样的二值变量就好像只有一种状态，对象五，x ，均取值为0 的情况被认为不重要 而忽略了n 。 3 标称型、序数型和比例标度型变量 标称变量也称分类( c a t e g o r i c a l ) 属性，。它可以有多个状态值，是二元变量的推 广，状态之间是无序的。例如颜色变量可以有红、黄、蓝、粉色四个状态。它的 差异度可用简单匹配法来计算： d ( 葺，x ，) = 型( 2 1 0 ) p 其中，m 是对象薯和x ，中取相同状态的属性个数，而p 是全部属性个数，p m 为对象五和x ，中取不同状态的属性个数。 序数型变量类似于标称型变量，但它的各个状态是有意义的序列。例如职称 就是一个序数型变量，它是按照助教、讲师、副教授、教授的顺序排列的。在计 算对象间的差异程度时，序数型变量的处理方法与区间标度变量的处理方法类似。 9 比例标度型变量就是在非线性的标度所获得的正的测量值，例如指数标度， 近似遵循a e 厨或a e 一，其中a ，b 是正常数。在计算比例型变量所描述对象i b j 的距 离时，可利用变换( 如对数转换y i , = l o g ( x i 。) ) 来处理第f 个对象中属性k 的值得 到儿，将虼当作区间标度变量进行处理。这罩的变换需要根据具体定义或应用要 求而选择l o g 或l o g - l o g ，或其他变换。 变量之间的相似性测度除了可以使用上述的距离函数之外，还可以使用以下 的相似函数。 1 由距离函数转换来的相似函数 可以通过一个单调的减函数，将距离转换成相似性度量，相似性度量的取值 一般在 o ，1 】之间，值越大，说明两个对象越相似。例如，可以采用以下变换： ( 1 ) 若距离在 0 ，1 】之间，可采用与l 的差作为相似系数，即 s ( 葺，x j ) = l d ( ，x j ) ( 2 1 1 ) ( 2 ) 采用负指数函数将欧氏距离转换为相似性函数， s ( 薯，x j ) = e - 叫k 。 ( 2 1 2 ) ( 3 )采用距离的倒数，为了避免分母为0 的情况，在分母上加1 ， ，1 s ( x i , _ ) 2 瓦磊而( 2 1 3 ) 2 夹角余弦 s ( 五，x j ) = x j k k = i ( 2 1 4 ) 夹角余弦函数忽略各个向量的绝对长度，着重从形状方面考虑它们之间的关 系。当两个向量的方向相近时，夹角余弦值较大，反之则较小。特殊地，当两个 向量平行时，夹角余弦值为1 ，而正交时余弦值为0 。 3 相关系数 s ( 薯，x j ) = 喜( 一i ) 。( 一i ) 其中 一坛一 而2 旦n 一，_ 2 旦n 一。 1 0 ( 2 1 5 ) ( 2 1 6 ) 相关系数足对向量做标准差标准化后的央角余弦，它表示两个向量的线性相 关程度，具有平移不变性。 4 最大最小法 s ( 薯，一) = m i n ( x i k ，x s k ) l m a x ( x , ，) ( 2 1 7 ) k = lk = l 2 3主要的聚类算法 在过去的十年中，提出了许多有关聚类分析的算法。聚类算法的选择取决于 聚类问题中的数据类型以及实际的应用场景。在本节中，我们主要介绍现有的几 类聚类算法以及存在的问题【。 2 3 1 基于划分( p a r t i t i o n i n g ) f 1 f j 方法 基于划分的聚类方法为给定数据集合指定合理的平滑划分，每个对象都被指 定给唯一的类。类的个数k 是需要用户指定的输入参数。给定一个包含n 个对象 的数据集及要生成的类的数目k ，基于划分的聚类算法将数据对象划分为k 个子 集，其中每个子集构成一个聚类。这些子集满足两个要求：每个子集中至少应包 含一个对象，且每个对象必须只能属于某一个子集。后一个要求在一些模糊划分 方法中可以放宽。 给定需要划分的个数k ，一个划分方法首先要创建一个初始的划分，然后利用 迭代再定位技术，尝试通过对象在划分间移动来改进划分。根据所采用的相似度 函数的差异，不同的算法通常具有不同的划分准则，以便聚类中对象是相似的， 聚类间对象是相异的。典型的基于划分的算法有k m e a n s 算法【8 】，k m e d o i d s 算法p 】 和它们的变种c l a r a n s 和c l a r a 。k m e a n s 算法在每次迭代过程中，每一个聚 类均用相应聚类中对象的均值来表示，而k m e d o i d s 算法在每次迭代过程中，每 一个聚类均用相应聚类中离聚类中心最近的对象来表示。 k m e a n s 算法是目前最简单、最流行的划分算法之一，给定聚类的个数k 后， 它首先随机选择k 个点作为初始的聚类中心，对于剩下的其他对象，根据他们与这 些聚类中心的相似度( 距离) ，分别分配给离它最近的聚类中心代表的类，从而得 到一个初始聚类。然后计算各个聚类的均值作为新的聚类中心，并把每个对象重 新分配给最近的中心所代表的类，基于一个目标函数，如果新的聚类质量优于前 一次的聚类，则用新的聚类代替原聚类。这个过程不断重复，直到聚类质量不再 提高或达到规定的迭代次数为止。常用的目标函数为最小平方误差和准则，如公 式( 2 1 8 ) 所示。 e = 忙一m j | 1 2( 2 1 8 ) 2 lj ，e c j 其中e 足数据集中所有数据对象的平方误差的总和，x i 是给定的数据对象， m ，足类c ，的平均值： 月 m ，= _ ( 2 1 9 ) ，= l 其中n ，为第个类中包含的数据点的个数。 这是一种贪婪搜索策略，所以它的结果受初始选择的k 个均值点的影响，经常 会陷于局部最优点。k m e a n s 优点是可以处理大数据集，是相对可伸缩和高效的， 算法的时间复杂性是线性的o ( n t k ) ，其中n 为对象个数，k 为聚类个数，t 为迭代 次数，通常有t 刀，k n ，因此它的时间复杂度通常也用o ( n ) 表示。 2 3 2 基于层次( h i e r a r c h i c a l ) 的方法 层次聚类方法将数据对象形成一棵以聚类为节点的树。根据层次分解是自底 向上还是自顶向下形成，层次的聚类方法可以进一步分为凝聚的( a g g l o m e r a t i v e ) 和分裂的( d i v i s i v e ) 层次聚类。 凝聚的层次聚类方法首先将每个对象作为一个聚类，然后不断地合并两个原 子聚类，直到所有的对象都在一个类中，或满足某种终止条件。大多数的层次聚 类算法都属于这类方法，但聚类内部对象间距离定义的描述方面可能有所不同。 而分裂的层次聚类则首先将所有对象置于同一类中，然后逐渐将其分解，变成越 来越小但个数越来越多的类，直到每个对象自成一类，或者达到终止条件，例如 达到了某个希望的聚类数目，或者两个最近的聚类之间的距离超过了某个阈值。 在层次聚类方法中，聚类的合并和分解要按照一定的相似性或相异性度量原 则，这种方法可以在不同粒度水平上对数据进行探测，而在对非单点的聚类进行 合并或分解时，需要将两个点之i 、日j 的距离推广到两个点集之问的距离。通常这种 扩展方法有三种： 1 单连接( s i n g l el i n k ) 单连接即最短距离法。两个类之间的距离用从两个类中抽取的每对样本的最 小距离表示。一旦两个类的距离超过某个给定的阈值，算法就自动结束。 2 全连接( c o m p l e t el i n k ) 全连接即最长距离法，与单连接方式不同的是，全连接中两个类之间的距离 定义为两个类中任意两点的最大距离。 1 2 3 平均连接( a v e r a g el i n k ) 平均连接方法中两个类之间的距离定义为分别在两个类中的任意两点组成的 点对的平均距离。 单纯的层次聚类算法经常会遇到合并或分裂点的选择的困难，而且在进行合 并或分裂聚类操作后无法回溯，这很可能导致聚类结果质量很低。另外，由于需 要检查和估算大量的对象或聚类j 能决定合并或分裂的对象，所以这种方法的可 扩展性较差。因此，通常在解决实际聚类问题时要把层次方法和其它聚类技术结 合起来，形成多阶段聚类，从而