（计算机应用技术专业论文）符号聚类新方法的研究及应用.pdf

摘要 摘要 聚类是一门非常重要的技术。所谓聚类就是按照某种度量( 相似性度量、不相似性 度量或距离) ，根据一定的准则将个体集合分成若干类，使得同类个体之间的相似程度 大于不同类个体之间的相似程度即做到”物以类聚 ，其目的是要挖掘出个体集合的信 息。目前的常用聚类方法大致可以分为层次聚类、划分聚类、基于模型的聚类、基于密 度的聚类、基于网格的聚类等。聚类技术已经被广泛得应用于分类学、生物信息学、商 业、医学、图像处理等领域。 传统的聚类技术处理的对象都是连续的数值型数据( 我们称之为传统数据，其中包 括模糊数据) 。但是，现在我们发现，在很多场合中我们无法用传统的数据来很好得表 达信息，例如物体的颜色( 或许你会认为，可以用不同的数值来代表不同的颜色，但是 那样的数值也仅仅是不同颜色的代码，已不再是传统意义上的数值，自然不能用传统的 数值方法来处理) 、用户的反馈、某个地区某段时间内的气温范围等等，这些数据不像 传统的数据那样有序、单值、连续，而且有时候同一个体的不同特征的取值之间存在着 一定的关系，我们把这类数据统称为符号数据。随着符号数据越来越多得出现，产生了 专门分析处理符号数据的领域符号数据分析( s d a ，s y m b o l i cd a t aa n a l y s i s ) ，而聚 类是其中重要且不可替代的分支。符号聚类分析就是研究如何将传统聚类中的技术引入 符号数据分析中，并且在需要的情况下创造出符合符号数据特性的新聚类理论和方法。 本着这个原则，本论文主要针对三种常见的符号数据名词性数据、区间数据、混合 数据( 即一部分特征是符号特征，一部分特征是传统特征) ，在前人工作的基础上，做 了一些研究改进。 对于名词性数据，过去常用h a m m i n g d i s t a n c e 来简单度量，但是h a m m i n g d i s t a n c e 太粗糙，不能充分挖掘隐藏在数据中的信息。本论文中采用了智能优化算法中粒群优化 算法( p s o ，p a r t i c l es w a r mo p t i m i z a t i o n ) ，通过训练得到适合于对应数据集的距离公式。 层次聚类的实验结果表明了，在度量名词性数据上，通过p s o 学习得到距离要优于简 单的h a m m i n g d i s t a n c e 。 对于区间数据，我们采用了相互距离( m d ，m u t u a ld i s t a n c e ) 的概念，给出了一个 适用于区间数据的相互距离公式，并在此度量的基础了，引进了最新的聚类方法一相 似性传播聚类( a p c ，a f f i n i t yp r o p a g a t i o nc l u s t e r i n g ) ，避免了符号聚类中心如何表示的 问题。最后的实验证明了我们的算法要优于基于e u c l i d e a nd i s t a n c e 的c 均值算法 ( c m ，c m e a n s ) 。 对于混合数据，由于之前的混合数据聚类中没有考虑到不同的特征对于聚类的贡献 不一样。因此本文在对混合数据进行模糊c 均值聚类( f c m ，f u z z yc m e a n s ) 时，考 虑特征权重问题，推导出适用于混合数据的带特征权重的模糊c 均值算法。最后的实验 也表明了考虑特征权重的合理性和必要性。 关键词：聚类；符号数据；符号数据分析；符号聚类；名词性数据；层次聚类；粒群优化；区 间数据；相互距离；相似性传播聚类；混合数据；特征权重；模糊c 均值算法 ， a b s t r a c t a b s t r a c t c l u s t e r i n gt e c h n o l o g y i sv e r yi m p o r t a n t b a s e do no n em e t r i c ( s i m i l a r i t ym e t r i c ， d i s s i m i l a r i t ym e t r i co rd i s t a n c e ) ，s oc a l l e dc l u s t e r i n gi st od i v i d es e to fi n d i v i d u a l si n t os o m e s u b s e ts ot h a ti ti sm o r es i m i l a rb e t w e e ni n d i v i d u a l si nt h es a m es u b s e tt h a ni nd i f f e r e n t s u b s e t sa c c o r d i n gt ot h ec e r t a i nc r i t e r i a , t h ep u r p o s eo fw h i c hi st om i n et h ei n f o r m a t i o nf r o m d a t a s e t a tp r e s e n t ，t h ec o m m o nm e t h o d so fc l u s t e r i n gm a i n l yi n c l u d eh i e r a r c h i c a lc l u s t e r i n g ， d i v i d i n gc l u s t e r i n g ，m o d e l b a s e dc l u s t e r i n g ，d e n s i t y b a s e dc l u s t e r i n g ，g r i d b a s e d c l u s t e r i n ga n ds oo n t h et e c h n o l o g yo fc l u s t e r i n gh a sb e e nw i d e l ya p p l i e dt ot a x o n o m y , b i o i n f o r m a t i c s ，b u s i n e s s ，m e d i c i n e ，i m a g ep r o c e s sa n ds oo n t h eo b j e c tp r o c e s s e db yt h et r a d i t i o n a lt e c h n o l o g yo fc l u s t e r i n gi sc o n t i n u o u sn u m e r i c a l d a t a ( i ti sc a l l e dt r a d i t i o n a ld a t ai n c l u d i n gf u z z yd a t a ) h o w e v e r , n o ww ef i n dt h a ts o m e i n f o r m a t i o ni nm a n yc a s e sc a n tb ep r e s e n t e da p p r o p r i a t e l yb yt r a d i t i o n a ld a t a , f o re x a m p l e ， c o l o r ( y o um i g h tu s ed i f f e r e n tn u m b e r st op r e s e n td i f f e r e n tc o l o r s ，h o w e v e r , t h en u m b e r si s n o tv a l u e si nt r a d i t i o n a ld a t ab u tc o d e so fc o l o r s ) ，c u s t o m e r s f e e d b a c k ，t e m p e r a t u r er a n g eo f a na r e af o rap e r i o dt i m ea n ds oo n t h ed a t ai sn o ts oo r d e r l y , s i n g l e - v a l u e d ，a n dc o n t i n u o u s a st r a d i t i o n a ld a t a , s o m e t i m e st h e r ea r er e l a t i o n sb e t w e e nd i f f e r e n tf e a t u r e so ft h es a m e i n d i v i d u a l ，w ec a l l t h i sl 【i n do fd a t as y m b o l i cd a t a w i t ht h ee m e r g i n go fm o r ea n dm o r e s y m b o l i cd a t a ，t h es p e c i a lf i e l dt oa n a l y z ea n dp r o c e s ss y m b o l i cd a t a - - s y m b o l i cd a t aa n a l y s i s ( s d a ，s y m b o l i cd a t aa n a l y s i s ) i se s t a b l i s h e d ，a m o n gw h i c hc l u s t e r i n gf o rs y m b o l i cd a t ai s a ni r r e p l a c e a b l eb r a n c h t h ep u r p o s eo ft h ec l u s t e r i n ga n a l y s i sf o rs y m b o l i cd a t ai st oa p p l y t h et e c h n o l o g i e si nt r a d i t i o n a lc l u s t e r i n gt oc l u s t e r i n gf o rs y m b o l i ca n dt oc r e a t en e w t h e o r y a n dm e t h o d so fc l u s t e r i n gw h i c ha r ec o n s i s t e n tw i t ht h ec h a r a c t e r i s t i c so fs y m b o l i cd a t ai nt h e n e e do ft h et i m e a c c o r d i n gt ot h ea b o v et h ep u r p o s e ，s o m er e s e a r c ha n di m p r o v e m e n to f c l u s t e r i n gf o rt h r e ec o m m o nk i n d so fs y m b o l i cd a t a - - n o m i n a ld a t a , i n t e r v a ld a t aa n dm i x e d d a t a ( t h e r ee x i s tt r a d i t i o n a lf e a t u r e sa sw e l la ss y m b o l i cf e a t u r e s ) a r em a d ei nt h ed i s s e r t a t i o n b a s e do nt h ef o r m e rw o r k s f o rn o m i n a ld a t a ，h a m m i n gd i s t a n c ei su s e du s u a l l y , b u ti ti st o or o u g ht om i n ef u l l yt h e i n f o r m a t i o nh i d d e ni nd a t a ，n l ep a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) i ni n t e l l i g e n t o p t i m i z a t i o na l g o r i t h mi su s e dt og e tt h ed i s t a n c ew h i c hi ss u i t a b l ef o rt h ec e r t a i nd a t a s e t t h r o u g ht r a i n i n g t h ee x p e r i m e n t so fh i e r a r c h i c a lc l u s t e r i n gs h o wt h a tt h ed i s t a n c ew h i c hi s g o t t e nt h r o u g hp s ot r a i n i n go u t p e r f o r mh a m m i n g d i s t a n c ef o rn o m i n a ld a t a f o ri n t e r v a ld a t a , i nt h ed i s s e r t a t i o n ，t h ec o n c e p to fm u t u a ld i s t a n c ei sa d o p t e da n do n e m e t r i co fm u t u a ld i s t a n c es u i t a b l ef o ri n t e r v a ld a t ai sp r o p o s e d ，a n db a s e dt h em e t r i c ，o n e n e wm e t h o do fc l u s t e r i n g - a f f i n i t yp r o p a g a t i o nc l u s t e r i n g ( a p c ) i si n t r o d u c e dt oa v o i dt h e t r o u b l eo fp r e s e n t a t i o no fc e n t e r si nc l u s t e r i n gf o rs y m b o l i cd a t a f i n a l l y , t h ee x p e r i m e n t s s h o wt h a tt h ep r o p o s e da l g o r i t h mi sb e t t e rt h ec m e a n s ( c m ) b a s e de u c l i d e a nd i s t a n c e f o rm i x e dd a t a , f e a t u r ew e i g h tw a sn o tc o n s i d e r e di nt h ef o r m e rc l u s t e r i n gf o rm i x e d d a t a , s ot h ef e a t u r ew e i g h ti sc o n s i d e r e di nt h ed i s s e r t a t i o nt og e tt h ef u z z yc - m e a n sw i t l l f e a t u r ew e i g h tf o rm i x e dd a t a t h ee x p e r i m e n t si n d i c a t et h a tc o n s i d e r i n gf e a t u r ew e i g h ti s r a t i o n a la n dn e c e s s a r y i i a b s t r a c t k e y w o r d s ：c l u s t e r i n g ；s y m b o l i cd a t a ；s y m b o l i cd a t aa n a l y s i s ；c l u s t e r i n gf o rs y m b o l i c ； n o m i n a ld a t a ；h i e r a r c h i c a lc l u s t e r i n g ；p a r t i c l es w a r mo p t i m i z a t i o n ；i n t e r v a ld a t a ；m u t u a l d i s t a n c e ；a f f i n i t yp r o p a g a t i o nc l u s t e r i n g ；m i x e dd a t a ；f e a t u r ew e i g h t ；f u z z y c - m e a n s a l g o r i t h m l i i 独创性：声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签 名：疆互盈蔓 日 期：垭： ： 壁 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签 名：雅丑番 导师签名：二荔么卜日期：。狸臣上眨一 第一章绪论 第一章绪论 符号数据分析( s d a ，s y m b o l i cd a t aa n a l y s i s ) 是上个世纪末兴起的一个研究领域。 由于在现实领域中，符号数据( 例如我们经常遇到的名词性数据、区间数据、布尔数据 等，有时也称为非传统数据) 越来越频繁的出现，人们开始研究符号数据的处理方法以 及相关的理论，符号分析就是对这一个研究及应用领域的总称。其中，符号聚类是符号 分析中一项十分重要的技术，它是对传统聚类技术的重要扩展。 1 1 研究背景 传统的数据主要指那些连续的数值型数据，但是在很多实际应用中出现的数据并非 如此，例如某一种产品的不同品牌的不同配置( 名词性数据) ，各个城市的各个月份的 气温范围( 区间数据) ，各个选民对不同候选者的投票( 布尔数据) 等等，这些数据不 同于传统数据，他们可以是离散的、多值、无序的并且同一个数据项的不同特征值之间 还可能有关联。针对这些数据的特殊性，人们开始研究适用于这些数据的方法和理论， 于是便逐渐形成了符号数据分析，其研究的对象我们称之为符号数据。符号数据分析提 供了聚类、因子分析技术、决策树等等，其中聚类是其中一个重要的分支，也是本论文 要研究的问题。 1 2 研究现状 在这小节中，我们分别简单介绍名词性数据聚类、区间数据聚类和混合数据聚类的 研究现状。 虽然在聚类中适用的度量有很多种，但是对于名词性数据，目前大都使用h a m m i n g d i s t a n c e t 啦】，使用h a m m i n gd i s t a n c e 时，两个对应特征值若相等则距离值为0 ，否则为 1 。为了处理传统数据与符号数据的混合，在一些文章中定义了一些相似性度量，但是 在这些度量，对于名词性特征仍然使用h a m m i n gd i s t a n c e 【j ，4 j 。很明显，h a m m i n gd i s t a n c e 太简单，太粗糙，不能体现名词性特征不同取值之间的细微差别。 2 0 0 4 年，s o u z a 和d ec a r v a l l o 基于c i t y b l o c k 距离提出了适用于区间数据的可调整 的动态聚类算法【5 1 ；f r a n c i s c od ea t 等人在2 0 0 4 年至2 0 0 6 年分别给出了基于可调整的 c h e b y s h e vd i s t a n c e 的区间聚类、基于可调整的h a u s d o r f f d i s t a n c e 的区间动态聚类、基 于可调整的e u c l i d e a n e a nd i s t a n c e 的区间模糊聚类1 6 , 7 , 8 1 ；但是这些度量只考虑单向的距 离，即x ( y ) 到y ( x ) 的距离就是x 与】，之间的距离，用这样的方式去度量传统数 据或许可以，而在符号数据中，这样做不一定合适。同时，我们可以将传统聚类中大量 的理论及方法引入符号聚类中，可是在引入的过程中我们会发现很多问题，例如聚类中 心的表示，由于在传统聚类中，数据是连续且有序的，我们可以用求平均值的方法简单 地获得聚类中心，但在符号聚类中有时这样做是行不通的。关于区间数据，有些聚类算 法选择避开中心的问题，比如使用层次聚类等，有些算法没有避开但也只是使用一些类 似于求平均值的方法来简单地求取聚类中心。 1 9 9 5 年，k c h i d a n a n d ag o w d a 等人将基于p o s i t i o n 、s p a n 、c o n t e n t 的相似性度量 江南大学硕士学位论文 应用于符号混合数据( 有别于混合数据，其中不包括传统特征) 的凝聚层次聚类中【9 】； 1 9 9 8 年，e 1 s o n b a t y 和i s m a i l 将经典的c m e a n s 算法应用于符号混合数据中，同样使用 基于p o s i t i o n 、s p a n 、c o n t e n t 的不相似性度量i l o j ；2 0 0 4 年，m i i n s h e ny a n g 等人对上诉 文章中使用的不相似性度量进行了一定的改进，并将其应用于混合数据的模糊聚类中 】。但是这些混合聚类中都没有考虑特征权重，而我们知道，聚类中不同特征所起的作 用是不一样的。 1 3 研究意义与目标 符号数据越来越频繁地出现在实际的应用领域，符号分析越来越多地引起人们的关 注，而其中符号聚类是符号分析中不可替代的重要分支。符号聚类作为传统聚类的重要 扩展，传统聚类中的很多技术可以应用到符号聚类中，但由于符号数据一些特有的性质， 很多时候不可以照搬传统聚类中的技术，例如度量、中心的表示等，需要做一定的改变 甚至需要提出新的方法。 在实际应用中，名词性数据、区间数据、混合数据经常被涉及到，因此本论文主要 针对这三类数据展开符号聚类的研究。在名词性数据聚类中，我们将解决名词性度量的 问题；在区间数据聚类中，我们将应用了一个全新的聚类方法解决了初始化敏感的问题 并提出了一个相互距离度量；在混合数据聚类中，我们将解决特征权重的问题。 1 4 论文结构 接下来，本论文的内容安排如下： 在第二章，我们将对符号聚类领域的相关理论和方法进行一定的概述，包括：符号 数据的概念与介绍、符号度量、符号聚类中心的表示、常用的符号聚类方法以及符号聚 类的评价准则。 在第三章，我们对名词性数据的聚类进行一定研究。 在第四章，对区间数据的聚类进行一些研究。 在第五章，主要讲述混合数据的聚类。 一 第六章是对本论文工作的总结以及对将来工作的展望。 2 第二章符号聚类概述 第二章符号聚类概述 我们知道，对于一个聚类算法主要涉及三个方面：度量( 相似性度量、不相似性度 量或距离) 、聚类的方法、评价准则。同样，对于符号聚类也涉及到这三个方面。同时， 在一些符号聚类中，还涉及到中心的表示，这也是一个比较麻烦的问题，由于符号数据 的无序性、离散性、多值性，所以符号聚类的中心不能简单得为类中各个点的平均值。 因此在本章中，我们专门拿出一节来说明符号聚类中心的表示。在分别讨论符号度量、 符号聚类中心的表示、聚类方法、评价准则之前，我们先对符号数据作个简单的介绍。 2 1 符号数据 总体上讲，符号数据大致分为三类：多值符号数据，区间数据，模型符号数据【l 引。 随机变量】，的值域为y ，y 可以取y 的一个或多个的值，y 可以是有限或无限的；根据y 中的元素是质型还是量型的，我们可以】，分别称为多值质型符号数据或多值量型符号数 据，简称为质型符号数据或量型符号数据；如果一个质型符号数据只能取有限的值域中 的一个值，称这样的质型符号数据就为名词性数据，本论文第三章专门讲述名词性数据 聚类。例如，】，表示某一类病人所患癌症，值域y = f l u n g ，l i v e r ， ，质型符号数据 i = l u n g ) ，k = l u n g ，s t o m a c h ，b o n e ；量型符号数据z 为各个品牌汽车没公里的耗油 量，值域z = j 8 ，2 0 ，3 0 ，1 3 ，1 5 ，z l = 1 8 、z 2 = 3 0 ) 、z 3 = 1 3 ) 分别表示t o y o t a 、 f o r d 、c h i n a - m o t o r 的耗油量。 所谓区间数据，随机变量的取值是以区间的形式出现的。区间数据y = 口，b 1 ，其中 a b ，a b r ，y 的区间可以是半开的，也可以全开的，但通常情况下，我们处理的 区间数据都是闭区间的。例如，各个病人一天之内的血压范围，各个城市一年之内的气 温范围等等，都是区间数据。我们将在第四章讲述区间数据聚类。 模型符号数据以这样的形式出现：y = r , 万 ，r 可以是多值符号数据也可以是区间数据 甚至还可以是传统的数据，万可以表示r 的权重，出现的概率，以及可信度等等。对于 这种类型的符号数据，本论文没有对它进行专门的研究，但是它在聚类中心的表示上很 有用，在混合数据聚类那一章我们将会用到这种数据表达形式来表示聚类中心。 2 2 符号度量 我们知道度量是传统聚类中的关键性问题，对于符号聚类同样如此。我们以往都是 在传统数据的空间中来考虑度量问题，得到了很多相关的度量公式：m i n k o w s h id i s t a n c e 、 e u c l i d e a nd i s t a n c e ，c i t y b l o c kd i s t a n c e ，s u pd i s t a n c e 、m a h a l a n o b i sd i s t a n c e ，p e a r s o n c o r r e l a t i o n 、p o i n ts y m m e t r yd i s t a n c e 、c o s i n es i m i l a r i t y 1 3 j 。但是由于符号数据的无序、离 散、多值等特性，使得无法将许多传统度量研究成果直接应用于符号空间，需要进行改 动有时还得考虑全新的度量。接下来我们来看看，人们在名词性数据，区问数据，以及 混合数据( 符号混合数据包含在其中进行讨论) 的度量上都作了哪些工作。 江南大学硕士学位论文 对于名词性数据，目前大都用h a m m i n gd i s t a n c e 来度量【1 2 】。h a m m i n gd i s t a n c e 将两 个名词性数据的距离规定为非0 即1 ，当它们相同时为1 否则为o 。这样的度量太粗糙， 不能充分挖掘数据里的信息，体现名词性数据之间的细微差别。 对于区间数据度量，主要是f r a n c i s c od ea t d ec a r v a l h o 等人( 2 0 0 4 2 0 0 6 ) 提出了 a d a p t i v ec h e b y s h e vd i s t a n c e t 6 1 、a d a p t i v eh a u s d o r f fd i s t a n c e 7 1 、s i n g l ea d a p t i v e e u c l i d e a n e a nd i s t a n c e 引、a d a p t i v ee u c l i d e a n e a nd i s t a n c e 1 4 1 ；s o u z a 等人( 2 0 0 4 ) 使用 c i t y b l o c kd i s t a n c e 度量区间数据1 5 j 。但是这些度量只是在原有传统度量的基础上进行一 定的调整，没有考虑区间数据度量的不对称性，即x 到】，的距离不一定等于】，到x 的距 离。 较之名词性数据和区间数据，符号混合数据和混合数据的度量要困难得多，因为它 要同时考虑多种数据类型各自的特性。k c g o w d a ( 1 9 9 1 1 9 9 5 ) 等人提出来基于位置 ( p o s i t i o n ) 、范围( s p a n ) 、内容( c o n t e n t ) 的符号混合数据度量1 2 , 1 5 , 1 卅；i c h i n o 等人 ( 1 9 9 4 ) 使用g e n e r a l i z e dm i n k o w s k im e t r i c s 来度量混合数据f 1 7 1 ；m i i n s h e ny a n g 等人 ( 2 0 0 4 ) 在k c g o w d a 等人工作的基础上，提出了一种混合数据的度量【l ，对于混合 数据中的符号特征，m i i s h e ny a n g 采用l l5 j 中的不相似性度量，对于传统数据采用 h a t h a w a y 的参数方法【1 8 和y a n g 的不相似性度量【1 9 1 。但是它们都没有考虑不同特征在聚 类中所起的贡献是不一样的，即特征权重不同。 2 3 符号聚类中心的表示 很多时候，用一个点来代表一个类。如果这个点是属于该类的一个点，我们称这样 的点为类代表点( p r o t o t y p e 或e x a m p l e ) ；如果不是类中的点，而是类中各个点的平均值、 中间值或通过其他更为复杂的方式得到的一个类中不一定存在的点( 它的表示可以跟类 中的点一样也可以不一样；它也可能与类中存在的某个点相等) ，我们称之为类中心。 在一些符号聚类中没有设涉及类代表点或类中心问题，例如：层次聚类( h c ： h i e r a r c h i c a lc l u s t e r i n g ) ；还有一些聚类只涉及到类代表点，例如：相似性传播聚类( a p ： a f f i n i t yp r o p a g a t i o n ) 2 0 】；但是有一些聚类算法涉及类中心，例如：模糊c 均值算法( f c m ： f u z z yc m e a n s ) ，对于这些聚类我们就得寻找恰当的中心表示。 c h a v e n t 和l e c h e v a l l i e r ( 2 0 0 2 ) 将数据集中第，点的第k 个特征的区间数据表示成： 啄，b j k = m j k k ，m j k + k ，其中，= ( + ) 2 ，k = ( 一) 2 ，j = l ，2 ，n ， k = 1 ，2 ，d ，其中为数据集大小，d 为数据点的维数；将第i 类中心表示成： 4 = ( h 。一a 。，u j 。+ 五，】， 一如，甜函+ 】) ，其中u i k = m e d 。i a n , n j k ，丸= 肌p 驷k 口1 1 。 2 0 0 4 年，c h a v e n t 又将中心表示成： 4 = ( 【，屈。】，【，屈d 】) ， 其中 2 m 同a x a p + m 尸i n a j t ) 2 ，厥2 ( 、m 同a x b ，雷+ 噗p ) 2 瞄1 。b o c k ( 2 0 0 5 ) 将区间数据的 中心表示成：4 = ( 【。，屈，】，【q d ，如】) ，其中= 百i ，玩= 古，m 为第 4 第二章符号聚类概述 f 类的大小田j 。 对于符号混合数据，y a s s e re l s o n b a t y 和m a i s m a i l ( 1 9 9 8 ) 提出了一种全新的表示 方法，对于符号中心而言，一个中心由若干个特征组成，每个特征由若干个事件组成， 设是第f 个聚类中心的第k 个特征的第p 个事件，对应的表示该事件隶属于第i 个 聚类中心的第k 个特征的程度。因此第f 个聚类中心的第k 个特征为 以= i ( 以。，。) ，( ，) ，1 ，同时带有约束条件：o 1 、= l 、n = a 、 一pp u = u ，其中，如果事件不是第f 中心的第七个特征的一部分，则= o ； p 如果第f 个中心的第七个特征只包含事件4 肇，则= 1 【1 0 1 。m i i n - s h e ny a n g 等人( 2 0 0 4 ) 提出了混合数据中心表示方法，中心的符号特征与传统特征分开表示，对于符号特征， 采用1 1 0 中的方法，对于传统特征，根据l r 型模糊模型，将其表示成 4 = 朋( l ，a j k 2 ，口腩3 ，口腩4 ) ，其中a j k l 、鲰2 、3 、4 分别表示l r 模型的参数【1 1 1 。 2 4 聚类方法 由于符号聚类与传统聚类的原理相通，所以现在符号聚类所使用的绝大部分方法都 是从传统聚类中引进的。在这一节我们将比较详细的介绍几个符号聚类中常用基本方 法，许多方法都是对它们进行一定的改进得到的。注意我们这里介绍的是通用性的方法， 并不一定针对具体的数据类型。 2 4 1c 均值 c 均值聚类( c m ，c m e a n s ) 2 4 1 在传统和符号聚类中经常用到。基本过程如下： 1 ) 初始化c 个聚类中心( 这里可以随机或使用一定方法来选择c 个数据点作为初始的聚 类中心) ； 2 ) 根据选定的度量，把数据集中的每个数据点赋给与其最相似的那个中心； 3 ) 计算得到的每个聚类的中心( 计算中心的方法视具体情况而不同) ； 4 ) 重复2 ) - - 一3 ) 直到迭代停止的条件别满足。 c 均值简单且能够解决许多实际的问题。当聚类空间结构为超球状且类内数据分布 紧凑时，c 均值的聚类效果很好。时间复杂度是o ( n d c ) ，由于维数d 和聚类数目c 通 常要远小于数据集规模，所以c 均值可以用于大规模数据集。但是c 均值也存在一些 缺陷： 1 ) 至今无有效和统一的方法来确定聚类数目c 和初始化聚类中心； 2 ) 不能保证迭代的过程能收敛于全局最优值； 3 ) 对局外点和噪音比较敏感。 2 4 2 模糊c 均值 聚类可以被分为硬聚类和模糊聚类( 也称为软聚类) 。对于硬聚类，任何一个数据点 只能属于一个聚类；而在模糊聚类中，一个数据点能以不同的隶属程度属于于多个聚类， 这对我们来说很用，特别是在自然科学领域中，有时聚类之间不能清晰划分或存在二义 江南大学硕士学位论文 性，同时，这种隶属度能够让我们得到更多给定数据点和聚类之间的关系。模糊c 均值 ( f c m ，f u z z yc m e a n s ) 【1 3 】是最经典的模糊聚类，它是要在给定的数据集 五，五，k ，一r d ，j = 1 ，2 ，n 中找到一个模糊划分来最小化代价函数： j ( v ，彳) = 坼m 。岛 ( 1 ) ( 1 ) 式中 u - - u , ， 。模糊隶属度矩阵，其中，【o ，1 】是第_ ，个数据点属于第f 类的模糊隶属 度； a = 【4 ，4 ，4 】聚类中心矩阵； m f 1 ，) 模糊参数，通常设置为1 5 至2 5 之间，多数情况下取2 ； 岛x ，和4 之间的距离。 为了最小化公式( 1 ) ，在限制条件甜u = 1 ，= 1 ，n 下，我们对( 1 ) 式使用梯度下降 法，得到u 和彳迭代公式： ，：1 f ，窆( 岛岛) 驰叫 ( 净1 ，歹：1 ，) ( 2 ) 4 = 陲u t , j ”胞u i m , j p ， 模糊c 均值具体步骤如下： 1 ) 选择c 和m ，初始化聚类中心； 2 ) 根据公式( 2 ) 更新u ； 3 ) 根据公式( 3 ) 更新彳； 4 ) 重复步骤2 ) 3 ) 直到迭代停止的条件被满足为止。 模糊c 均值算法的复杂度接近o ( n 1 。它跟c 均值一样同样被初始化所困扰并且容易 受局外点和噪声影响。 2 4 3 层次聚类 前两个聚类方法形成的类与类之间没有任何的联系。用计算机科学的术语来说，这 种数据描述方法是“平坦的。但是在现实世界中存在很多这样的情况，一个大类包含 很多子类，子类又包含很多更小的子类。比如，在生物分类学中，整个生物界被分成各 个门，门包括很多纲，纲包括很多目，目由很多科组成，等等，直到特定的个体生物。 层次聚类( h c ，h i e r a r c h i c a lc l u s t e r i n g ) 1 1 3 1 便是这种思想在聚类中的应用。层次聚类的 基本思想是递归地对数据进行合并或分裂，将数据集划分成嵌套的类层次结构或类谱系 图。根据采用合并还是分裂的方式进行聚类，层次聚类又可分为自下而上的凝聚层次聚 类和自上而下的划分层次聚类。在符号聚类中，大多数情况下使用凝聚层次聚类，所以 接下来我们只对凝聚层次聚类做简单介绍。 让我们考虑对个数据点聚成c 类的情况。首先，将所有数据点分成类，每个类 6 第二章符号聚类概述 正好含有一个数据点，接着，我们找出距离最小的两个类进行合并，这样便形成了一l 类，同样接下去是一2 类，如此下去，直到所有数据点都被归成一类。我们称聚类数 目c = n k + 1 对应层次结构的第k 层，因此第1 层对应个类别而第层对应一个类 别。对层次结构的任意一层及其该层中的任意两个数据点，如果它们在该层中属于同一 类，而且在更高的层次一直属于同一类，这样的序列称为“层次聚类 。 最自然的表达“层次聚类 的方式就是树，它能体现各个数据点是如何聚在一起的。 图1 中给出的树图对应的是8 个数据点的简单情况。在第1 层k = 1 时，有8 个类。在第 2 层，数据点咒和墨先被聚在一起，因为他们的之间的距离最小，并在后面的层次中 始终处于同一类中。当在某层次中，类与类之间的距离都比较均匀，那么就没有足够的 理由说某些类应该聚在一起；相反，如果第k 层对应3 个类别，第k 一1 层对应4 个类别， 而这两层的距离相差很大，那么我们就比较有把握地说聚成4 类是比较合理的。 在每一层中，我们选择靠得最近的两个类合成，判断类与类之间的距离的方法有很 多，常用的有s i n g l e 、c o m p l e t e 、a v e r a g e 、m e a n 等。其中，s i n g l e 指类间距离为类间靠 得最近的两个数据点之间的距离、c o m p l e t e 指类间距离为类间离得最远的两个数据点之 间的距离、a v e r a g e 指类间距离为类间两两数据点之间距离的平均值、c e n t r o i d 指类间距 离为类中心之间的距离。s i n g l e 与c o m p l e t e 代表类间距离的两个极端，它们对某些噪声 和孤立点非常敏感，用a v e r a g e 和m e a n 可以改善这些问题。 凝聚层次聚类步骤如下： 1 ) 每个数据点自成一类； 2 ) 找出所有类中距离最小的两个类，将它们合并成一个类； 3 ) 重复步骤2 ) 直到得到c 个类。 k = 1 _ k = 2 一+ k = 3 k = 4 _ k = 5 k = 6 k = 7 _ k = 8 一一一一- x lx tx、x、x，xbx 1x 图1 凝聚层次聚类树图 f i g u r e 1t r e eo fa 9 9 1 0 m e r a t eh i e r a r c h i c a lc l u s t e r i n g 凝聚层次聚类算法的复杂度为d ( 2 d 2 c ) 。凝聚聚类使用方便比且能够挖掘数据集的 层次关系。但是它也有其缺陷：时间复杂度大、对局外点和噪声敏感、无法处理先前的 7 江南大学硕士学位论文 误分即一旦在某一层中将一个数据点误分到一个类中那么在其后的聚类中都无法对其 修正。 2 5 评价准则 对于同一个数据集可以有多种不同的划分，哪些好哪些差，可以通过恰当的评价准 则对不同的划分进行比较。有时也可以使用评价准则对通过两个不同聚类算法得到的同 一个数据集的两种不同划分进行评价，从该评价中判断出两个算法的相对优劣。在这一 节中，我们将介绍四种符号聚类的常用评价准则。 2 5 1c r 准则 c r ( c o r r e c t e dr a n di n d e x ) 准则【7 】是个外部评价准则即不依赖于聚类中所选择的度 量，但它只能用在已知标准聚类的情况下。已知标准的聚类为刁= 7 7 l ，7 7 2 ，仍， ，而 实际聚类的结果为p = 岛，岛9 o0 9 p ，成 ，则 c r = 喜喜( ) 一( 多) - l 喜( 箩 喜( 多7 三 喜( + 喜( 多刁 一( 多) - l 喜( 多 喜( 多7 ( 4 ) 式中 数据集大小； m 聚类仍的大小； ，聚类p ，的大小5 统与p ，的交集的大小； 防掣。 。 c