（计算机软件与理论专业论文）模糊聚类算法及其在文本挖掘中的应用.pdf

摘要 摘要 聚类分析是机器学习中很重要的个研究领域。聚类分析所涉及 的领域包括：数据挖掘、统计学、机器学习、空间数据库技术、生物 学等。由于各应用数据库所包含的数据量越来越大，聚类分析己成为 数据挖掘研究中一个非常活跃的研究课题。在众多聚类算法中，模糊 聚类算法是最常用的算法之一。至今，文献中仍然不断有新的模糊聚 类算法出现。 本文对基于划分的模糊聚类算法进行了研究，从理论上证明了 l e e s 算法并不是f c m 算法的改进算法，应该属于p c m 型算法。 属性选择和加权是聚类分析中另一个重要的研究课题。本文提出 了一种新的基于属性加权的模糊c 均值聚类算法。之后又给出了使用 该算法时的参数选择理论规则。 除此以外，本文还对聚类分析的应用领域一文本挖掘进行了研 究。将文中所提出的新算法应用于文本，并对实验结果做了分析。 全文共分六章，各章的主要内容如下： 第一章介绍了聚类的定义、分类情况以及与本文联系较为密切的 两种基于划分的聚类算法。确定本文的研究范围和基本框架。 第二章在对p c m 型算法介绍之后，对一种模糊聚类算法进行了深 入研究，从理论上证明了该算法的正确归类。 第三章首先介绍了属性加权聚类算法的研究现状，尤其是对两种 属性加权c 均值算法进行了详细介绍。在此基础上，提出了一种新的 属性加权的模糊c 均值聚类算法，并对该算法目标函数的海森矩阵进 北京交通大学硕士学位论文 行分析，得出使用该算法时的参数选择规则。之后，对属性加权模糊 c 均值算法和前文重点介绍的两种加权聚类算法进行了实验比较。 第四章介绍了文本挖掘的一些基本概念和常用技术。具体分析了 文本挖掘尤其是文本聚类的研究意义。重点介绍了文本挖掘中的预处 理步骤和策略，对自动分词、特征表示以及特征提取进行了详细阐述。 第五章中，将本文提出的属性加权模糊c 均值算法( a w f c m ) 应用 于文本，实现了文本聚类过程中的预处理操作，并分别使用c 均值和 a w f c m 算法对预处理所得的文档表示矩阵进行了聚类，之后根据实验 结果得出了有意义的结论。 第六章对全文总结，讨论了模糊聚类算法研究中存在的问题，以 及该类算法应用于文本挖掘时所面临的挑战，给出了下一步的研究目 标。 关键词：聚类分析，权重，模糊指数，属性加权，文本聚类 a b s t r a c t a b s t r a c t a u s t e ra n a l y s i si so n eo ft h em o s ti m p o n a n tr c s e a r c hf i e l d si m a c h i n el e a m i n g ni sf e l a t e dt od a t am i i l i n 舀s t a t i s t i c s ，m a c h i n el e a m i n g ， s p a t i a ld a t a b a s e ，b i o l o g ya n ds oo n f o rt h er c a s o t i l a tt h ev o l u m eo f a p p l i c a t i o nd a 劬a s eb e c o m e sl 叫净a n dl a r g e f ，c l u s t c ra i i a l y s i sh a sb e c n a na c t i v ef i e l di nd a t am i i i i g f u z z yd u s t e r i n ga 1 p r o f i 圭h i l li so n eo ft i l e m o s tw j d e 】yu s e da l g o f i t l l m s u n t i ln o w 珊o r ea l l dm o r cr e s e a f c hr e s u l t s o ff u z z yc l u s t e r i i l gd l 舯r i t l l mh a v ea p p e a r e di nt h el i t c r a t u r e i nt h i st h e s 咄佗s t u d yo t l l ef i l z z yp a r t i t i o n a ld u s t e r i l l ga l g o r i t h m s a n dp r o v et h a tt h ea 1 9 0 i i t h mp r o p o s e db yl e e ( c a l i e da si 七e7 sa l 鲥t l l m ) i s n tak i n do ff i l z z yc m e a n s a 1 9 0 f i t h m ( c a l i e d 勰f c m ) b u ta 蚋c i a lc a s e o fp c mw l l i c hw a sp r o p o s e db y 蛋0 r i s h n a p u r a m k c l l c ri 1 9 9 3 a n r i b u t es e l c c t i o na n dw e i 曲t i n gi sa ni m p o n a n tr e s e a r c hf i e l di n c l u s t e ra n a l y s i s i nt l l i st h e s i s ，an e wa t t r i b u t ew e i g h t i n gf i l z z yc m e a 玎s a l g 嘶t h 】m a t t f i b u t ew e i g b t e df u z z y c m e a n s c l u s t e f i n ga 1 9 0 f i t h m ( a 、1 1 c m ) i sp m p o s e da i i dat h c o r e t i c a lr u l eo fp a r a m e t e 心s e l e c t i o no f t h i sn o v e la 1 9 0 r i t h mb yt h e 柚a l y s l so ft b eh e s s i a nm a 啊xo fi t so b j e c t i v e f i l n c t i o ni sg i v e b e s i d c st h a t ，t h ed u s t e r 龃a l y s i s sa p p l i c a t i o - d o ( - m m e mc l u s t e r i i i gi s r e v i e w e d a n d 也ea i g c 峨t h mp m p o s e di nt h i s 也e s i so nd o 饥m e n ti s i m p l e m e n t e d t h ee x p e r i m e t ，sn s u l t sa r ed i s c u s s e d t h et h e s i sc o n s i s t so fs i xc h a p t e r s ： c h a p t e rlr e v i e 、v st l i ed e 6 i t j o no fd u s t e r i n c l a s s i f i c a i i o no fc l u s t e r m e t h o d sa i l dt w op a n i t i o n a id u s t e r i n ga i g o r i t h m sb c i i i gi m p o n a n tt ot h i s t h e s i s i td e l i i l l i t st h et a s ka n dd e m e n tf r a m eo ft l l i st h e s i s i i lc h a p t e i 2 ，m ep o s s i b i l i s t i cc m e a i l sa l g o i i t h ma i l ds o m ea l g o r i t h m d e f i v e df i d mi ti si n 仃o d u c e df i r s n y k e sa l g o r i t h mi sp 州e dn o tt ob ea k i n do fm o d i f i e df c m a l g o i i t t l mb u tas p e c i a lc a s eo fp c mb yt h e o r e t i c a l a n de x p e d m e t a lm e t h o d s 北京交通大学硕十学位论文 c h a p t c r 3r c v i e w st w oa t t r i b u t e w e i g h t e dc m e 卸sd u s t e r i n g a l g o r i t i i i i lr e s p e d i v e ly t h e a w f c ma l g o r i t h m 啪sp f o p o s e d i no r d c rt o g j v ct l l eg u i d e h n eo fp a r a l n e t c f s s e l e c | i 加w h e u s i n ga w f c m t h e h e s s i a nm a t f i xo ft h en e wa l 窖o i i t l l m so b j e d i v ef i l n c t i o ni s 卸a l v z e d t h e p e f f b 栅卸c e o fn o v da l g o i i t i i mi st e s t e di nt e m so fn u m e r i c a l e x p e r i m e n t s t h er e s l l l t so fe x p c i i m e n t sd e m o n s t r a t et h ev d b d i t vo fo l l r a i g o r i t t i m 强dt h et h e o r c t i c a l 群i d d i n eo fp a m m e t e r s s c l e c t i o c h a p t e r4r e v i e w st h ec o n c c p 虹粕dt e c l l n o l o 画e so fd o c i l m e n t1 l l i l l i n g c o n s i d e r i n g t h a tt h e p r e p m c e 蟠i n g i s i m p o n a m ，t h em e t h o d sa i l d s t r a t e 百e s i nd o ( 姗e n t p f c p m c e s s i n g a r ei n m ) d u c e d t h ew o m 删6 0 n i l i 岛f e a t u 佗d 曲o t a 石佃粕df c a t u r ee x t 糟c t i o n a r cr c v i e w e di n d e t a i l h c h a p t c r5 ，筒f c ma l 鲥t h mi si m p i 锄e n t e do nd o c i l i e n t s a p r e p f o c 皓s j n g0 fd o c i i m e n tc l u s t e f i n gi i l d u d e s t h ef o n 吣面gs t e p s ： p a n i t i o n i i 塔腻，r c m o v i n gs t o p p i n g ，o f 咄e 】【t m d i n g 颤i t u r el e 咖s ， c a l c u l a t i n g w o r dh u c c y ，i 印r e s c n t i n gb yam a t r i x g m e a 璐a i i d a w f c m a l g o t h l na r cj m p 王锄朋t c d 彻t h i sm a n j x s 砌e n c l 璐i o n sa r c d i 矾ma f t e r 姐a l y s i so ft h ee x p e r i m e n t s r c 鲫i t s c h a p t c r 6s u 衄a i i z e st l l e 也鹤i s 锄dd i s c u s s c ss 鲫e p m b l e m s e x i s t i n gi nf i l z z yd u s t e i i n ga l g o r i t h l i l 卸dc h a l l e n g 皓w h 钮u 凼gt h e mo d o c i i m c n t s i nt h e 丘n a l ，t h cp r o s p c di sd e s 两b e d 1 【e y w o f d s ：a u s t e ra i l a l y s i s ，、v e i 曲t ，f u z z ye x p o n e n t ，a 矧b u t ew e i 曲t e d ， d 0 c u m 如t c l u s t e i j n g 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、使用学位论 文的规定，即：学校有权保留送交论文的复印件，允许 论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。论 文中所有创新和成果归北京交通大学计算机与信息技 术学院所有。未经许可，任何单位和个人不得拷贝。版 权所有，违者必究。 本人签名：篮 日期：趟年玉月血日 独创性声明 。雾8 7 9 7 3 9 本人声明，所呈交的学位论文是我个人在导师指导 下进行的研究工作及取得的研究成果。尽本人所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北 京交通大学或其他教学机构的学位或证书而使用过的 材料。与我一起工作的同志对本研究所做的任何贡献已 在论文中作了明确的说明并表示了谢意。 本人签名：套墼霾 日期：丝年土月血日 1 综述 1 1 聚类的定义 聚类( c l u s t e r i n g ) 是一个将数据集合划分为若干簇或类 ( c l u s t e r ) 的过程，使得同一簇内的数据之间具有较高的相似度，而 不同簇的数据对象间具有较高的相异度。相似或相异的度量通常利用 各对象问的距离来进行描述。将一个物理的或抽象的对象集合，根据 对象之间的相似程度，分为若干簇( 或类) ，其中相似的对象构成一簇， 这一过程就称为聚类过程( c l u s t e r i n g ) 。所谓一个类或簇，就是由彼 此相似的一组对象所构成的集合”。在许多应用中，一个簇中的所有 对象常常被当作一个对象来进行处理或分析。在机器学习中，聚类分 析与分类学习不同，聚类过程中没有教师指导，是一种无监督的学习。 无( 教师) 监督学习不依靠事先确定的数据类别，以及标有数据类别 的学习训练样本集合。正因为如此，聚类分析是一种观察式学习法 ( 1 e a r n i n gb yo b s e r v a t i o n ) ，而不是示例式学习法( 1 e a r n i n gb y e x a m p l e ) 。 聚类分析渗透到日常生活的各个方面，也是一种重要的人类行 为。人们在孩提时代就开始通过不断完善潜意识中的分类模式，来学 会识别不同的物体，如：红色和绿色，动物和植物等。人类要认识世 界就必须区别不同的事物并认识事物问的相似性。 聚类分析所涉及的领域包括：数据挖掘、统计学、机器学习、空 间数据库技术、生物学和市场学等。由于各应用数据库所包含的数据 量越来越大，聚类分析己成为数据挖掘研究中一个非常活跃的研究课 题。 作为统计学的一个分支，聚类分析已有多年的历史。许多统计软 件包，诸如：s p s s 和s a s ，都包含基于k 均值( 也叫c 均值) 、k 中心等诸 多聚类分析方法。在数据挖掘中，大多数工作都集中在设计能够有效、 高效地对大数据库进行聚类分析的方法上。相关的研究课题包括：聚 北京交通大学硕+ 学位论文 类方法的可扩展性、复杂形状和复杂数据类型的聚类分析及其高效 性、高维聚类技术，以及混合数据属性与符号属性数据库中的聚类分 析方法等。 聚类分析己被应用到许多领域，其中包括：模式识别、数据分析、 图象处理、市场分析和信息检索等。通过聚类，市场人员可以发现顾 客群中所存在的不同特征的组群，并可以利用购买模式来描述这些具 有不同特征的顾客组群；生物学研究者可以获取动物或植物所存在的 层次结构，根据基因功能对其进行分类以获得对人群中所固有的结构 更深入的了解：医学研究者可以用来标识混在同一诊断下的不同子疾 病类型。此外，还可以帮助分类识别互联网上的文档以便进行信息发 现。作为数据挖掘的一项功能，聚类分析还可以作为一个单独使用的 工具，来帮助分析数据的分布、了解各数据类的特征、确定所感兴趣 的数据类以便作进一步分析。当然聚类分析也可以作为其他算法( 诸 如：分类和定性归纳算法) 的预处理步骤。目前，随着互联弼技术的发 展，聚类也可以对服务器上的用户访问记录进行分类，以求通过用户 的访问模式来发现用户的兴趣，为其提供个性服务1 2 】1 3 l 。 1 2 聚类方法的分类 文献中已有的聚类算法数不胜数。算法的选择取决于数据的类 型、聚类的目的和应用。如果聚类分析被用作描述或探查的工具，可 以对同样的数据尝试多种算法，以发现数据可能揭示的结果。 大体上，主要的聚类算法可以划分为如下几类 1 1 ： ( 1 ) 基于划分的方法 给定一个包含”个对象或元组的数据库，一个划分方法构建数据 集合的七个划分，每个划分表示一个类。它将数据划分为量个组的同时 需满足以下要求：( i ) 每个组至少包括一个对象。( i i ) 每个对象必须 属于且只属于一个组。但是在某些模糊划分技术中，第二个要求可以 放宽。 给定要构建的划分的数目尼，划分方法首先创建一个初始划分。然 2 综述 后采用一种迭代的重定位技术，尝试通过对象在划分间的移动来改进 划分。一个好的划分的一般准则是：在同一个类中的对象尽可能相近 或相关，而不同类中的对象之间尽可能远离或不同。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划 分。实际上，绝大多数应用采用的是以下两个比较流行的启发式方法： 个是k 均值( k e a n s 或c m e a n s ) 算法，在该算法中，每个类用该 类中对象的均值来表示；另一个是k 中心点( k - e d o i d s ) 算法，在该算 法中，每个类用接近聚类中心的一个对象来表示。这些启发式聚类算 法对发现球状类很适用。为了对大规模的数据集进行聚类以及处理复 杂形状的类别，基于划分的方法需要进一步的扩展。 ( 2 ) 基于层次的方法 层次的方法对给定的数据对象集合进行层次的分解。根据层次的 形成方式，层次方法可以分为凝聚的和分裂的。凝聚的方法，也称为 自底向上的方法，一开始将每个对象作为单独的一个类，然后相继地 合并相近的对象或类，直到所有的类合并成一个或达到某一终止条 件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于 一个类中，在迭代的每一步中，一个类被分裂为更小的类，直到最终 每个对象在单独的一个类中或达到某一终止条件。 基于层次的方法的缺点在于，一旦一个步骤( 合并或分裂) 完成， 它就不能被撤销。因此，该技术不能更正错误的决定。对于层次聚类 算法的改进算法有c u r e 和c h a m e l e o n ，以及b i r c h 算法。 ( 3 ) 基于密度的方法 绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只 能发现球状的类，而难以发现任意形状的类。基于密度的聚类方法的 主要思想是：只要临近区域的密度( 对象或数据点的数日) 超过某个阈 值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定 范围的区域中必须至少包含一定数目的点。这样的方法可以用来过滤 噪声孤立点数据，发现任意形状的类。有代表性的密度聚类方法有 北京交通大学硕士学位论文 d b s c a n 和0 p r i c s 。 ( 4 ) 基于网格的方法 基于网格的方法把对象空间量化为有限数目的单元，形成网格结 构。所有的聚类都在这个网格结构( 即量化的空问) 上进行。这种方法 的优点是处理速度很快，其处理时间独立于数据对象的数目，只与量 化空间中每一单元的数目有关。s t i n g 算法就是一种基于网格的聚类 算法。 ( 5 ) 基于模型的方法 基于模型的方法为每个类假定了一个模型，寻找数据对给定模型 的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布 的密度函数来定位聚类。它也基于标准的统计数字来自动决定聚类的 数目，考虑噪声数据和孤立点，从而产生健壮的聚类算法。基于模型 的方法主要有两类：统计学方法和神经网络方法。 在实际应用中，有些聚类算法集成了很多种聚类算法的思想，所 以有时将某一算法单纯地划分为某类就显得有些困难。除此以外，为 了满足实际应用中特定的聚类标准，也需要综合多个聚类技术。 1 3 硬划分聚类算法 正如l - 1 节所言，由于聚类分析应用广泛，所以各种不同的聚类 算法层出不穷。在众多的聚类算法中，最早由研究者提出的聚类方法 是硬划分方法，其中以c 均值( c m e a n s ) 算法最为有名 假设x = “，z ：， 是一个包含h 个s 维对象的数据集合，被划分 为c 类矿= 饥，叱，雌) ，每一类可以用它的类中心q 来表示。一般来说， 算法的目的是使得类内每个样本点到该类中心的误差平方和达到最 小。用数学语言描述，c 均值算法的目标函数可以重述如下【1 l ： ，以，v ) = ：。：。i k q | 1 2 ，这里 o ，玎，；= 1 2 1 。( 1 1 ) c 均值聚类算法的计算步骤为： 4 s t e p l ：选取聚类个数凸从数据集中随机选定、向量作为初始聚类中 心，给出最大迭代次数碲阈值。 龇p2 ：将需分类的样本按欧氏距离分配给最近的类中心。根据公式 ( 1 2 ) 计算划分矩阵 ，：1 j f f = a 倒恤一q 8 2 ( 1 - 2 ) 4 l oo t h e r w i s e s t e p3 ：根据式( 1 1 ) 计算新的目标函数值，如果它相对于上次目标函 数值的改变量小于s 或者是迭代次数达到z 时，算法停止； s t e p4 ：根据公式( 1 3 ) 计算新的类中心，转到s t e p 2 。 ， u = 气：。“妒 ( 1 - 3 ) c 均值算法是目前使用较为广泛的一种划分聚类算法，其思想简 单，实现容易，收敛快，运行速度快，内存消耗小，可以有效地处理 大数据集，当样本数据是密集的，且类与类之间的区别较为明显的时 候，该算法的效果较好。但是它也存在一些缺点，隶属度不是0 就是 1 ，把每个待处理的对象严格地划分到某个类中，这与现实世界中数 据间的归类并不太严格相矛盾；对初始点选择敏感；需要预先给定聚 类数，不能动态地添加新的聚类；对孤立点敏感；每个数据点对聚类 的影响一样；由于每类用类中心来代表，不适合对名词性数据进行聚 类等。 1 4 模糊c 均值聚类算法( f c m ) z e d e h 所提出的模糊集合理论为解决c 均值算法中的硬划分问题 提供了有力的工具。人们开始用隶属度来刻画界限并不鲜明的划分问 题。模糊聚类方法就是在此基础上发展起来的。这种类型的聚类方法 用隶属度来描述样本隶属的不确定性，能够比较客观地反映现实世 界。其中，由d u n n 首先提出，之后又被b e z d e k 加以推广的模糊c 均 值( f u z z yc m e a n s ，f c m ) 算法是被实践证明的最有效的方法之一。 为了更好的描述f c m 算法。我们做如下假设： 北京交通大学硕士学位论文 x z “，屯，毛 c 彤是一个数据集，= 恤。k 。肘b 是一个隶属度 矩阵，v = “，叱，v c ，是c 个聚类中心，叶f ，2 c s ，l ，f c m 算法的 目标函数如下哪： l ，v ) 2 荟弘l k w ( 1 4 ) 式中，芝= 1 ，( 0 ，1 ) ，小通常叫做模糊指数。 模糊c 均值聚类算法的迭代过程与c 均值算法类似。其区别在于 划分矩阵和类中心的计算上。f ( ：m 算法的目标即是求出使目标函数 i ，。达到最小值的隶属度矩阵。初始时，类中心和隶属度矩阵都是随 机产生的，之后根据如下更新规则对其进行迭代更新。 q2 荟吼“( h ) h 。：( 1 气一吒1 1 2 ) 班1 。；，( 8 耳一v 川2 ) “ 因此，f 嗍算法的基本步骤可描述如下。 s t e p1 ：指定算法中的参数，包括类数日c ， 次数r 和阈值s 。 ( 1 6 ) 权重指数m ，最大迭代 s t e p2 ：初始化隶属度矩阵u ，使其满足约束条件 ：。1 1 ，( o ，1 ) 。 s t 印3 ：使用式( i 一5 ) 计算c 个聚类中心k ( 1 s f s c ) 。 s t e p 4 ：计算新的目标函数值l 似v ) 。如果它与上一次目标函数值之 差小于阈值f 或者迭代次数大于l 算法停止。 s t e p5 ：用( 卜6 ) 式计算新的隶属度矩阵u 。返回s t e p3 。 6 综述 f c m 算法计算简单而且运算速度快，具有比较直观的几何意义， 但是与c 均值算法一样，只用类中心来表示类，这样只适合于发现球 状类型的簇。在很多情况下，算法对噪音数据敏感。b e z d e k 6 等人 已经证明了f c m 算法只能保证收敛到公式( 卜4 ) 和( 卜5 ) 的不动点，不 能保证收敛到目标函数的极小值点，有时会收敛到目标函数的鞍点。 f c m 算法与c 均值算法相比，引入了模糊指数研，而m 选择的好坏直接影 响聚类的效果。由于f c m 算法存在种种缺陷，许多人对f c m 算法进行改 进，并提出了新的模糊聚类算法。其中为了克服f c m 算法对噪声敏感 提出的算法有：k r i s h n a p u 栅和k e i l e d 基于可能性理论所提出的可能c 均值( p o s s i b j l j s t i cc m e 扎s ，p c m ) 算法；l e e 于1 9 9 4 年嘲在改变f c m 算法 约束条件的基础上所提出的算法( 以下称该算法为k e s 算法) 等等。 1 5 本文的组织和工作 本文主要是针对模糊聚类算法进行讨论和研究，并且假设聚类算 法的目标函数可微，除了初始化，没有采取任何的抽样技术。下面就 本文要研究的主要内容和结构做一简单介绍。 本文的目的是对文献中已有的聚类算法进行研究和比较分析，并 在此基础上针对实际的应用问题，提出了基于属性加权的新算法，之 后对文本聚类这一应用领域进行了研究，将新算法在文本测试集合上 作了一些实验。本文的组织结构安排如下： 第一章介绍了聚类的概念及其应用领域，并重述了常用的两个基 于划分的经典算法。确定本文的研究范围和基本框架。 第二章对l e e 于1 9 9 4 年所提出的算法进行了研究，确定了该算法 的正确归类。 第三章基于前人的研究成果，结合目前高维数据频出的实际应用 现状，提出了基于属性加权的模糊聚类算法。 第四章介绍了文本聚类的研究现状和背景，重点阐述了文本预处 理技术。 第五章中，实现了文本聚类过程中的预处理操作，对第三章所提 北京交通大学硕士学位论文 出的属性加权聚类算法进行了实验，并对实验结果作了分析。 第六章总结全文，提出了基于划分的聚类算法在文本挖掘中应用 时所存在的问题，并对其发展前景进行了讨论。 种模糊聚类算法归类的研究 2 一种模糊聚类算法归类的研究 2 1 引言 随着互联网技术的发展和计算机处理能力的不断提升。处理海量 数据成了目前计算机的主要任务之。如何把海量数据很好的进行归 类以发现知识也成了很多学科领域的研究重点。和简单的分类相比， 聚类根据“物以类聚”的原则，按照数据间的相似程度进行区分和分 类。在这个过程中，事先并不清楚每个数据的类别，是一种无监督的 分类过程。其目的是要获得一个划分，这些划分将一组数据集合分成 几个子集，每个子集为一类，划分的标准是同类的数据在某种意义下 相似性较高，不同类的数据在相同意义下相似性较低w 。 在众多的聚类算法中，最早由研究者提出的聚类方法是硬划分方 法，其中以c 均值算法最为有名。c 均值算法中的隶属度不是0 就是1 ， 也就是说，硬c 均值算法会把每个待处理的对象严格地划分到某个类 中，而现实世界中数据的归类有时并没有如此严格的界限。z e d e h 所 提出的模糊集合理论为解决这一问题提供了有力的工具。人们开始用 隶属度来刻画界限并不鲜明的划分问题。模糊聚类方法就是在此基础 上发展起来的。这种类型的聚类方法用隶属度来描述样本隶属的不确 定性，能够比较客观地反映现实世界。其中，由d u n n 首先提出，之后 又被b e z d e k 加以推广的模糊c 均值( f u z z yc m e a n s ，f c m ) 算法是被实 践证明的最有效的方法之一。f c m 算法本身也存在一些缺点，其中以 对噪声数据敏感尤为突出。为克服该缺点，有很多学者进行了相应研 究，并提出了不少新算法，例如i 【r i s h n a p u r a l 和k e l l e r m 基于可能性 理论所提出的可能c 均值( p o s s i b i l i s t i cc m e a n s ，p c m ) 算法，以及 l e e 于1 9 9 4 年在改变f c m 算法约束条件的基础上所提出的算法( 以下称 该算法为k e s 算法) 等等。 由于f c m 算法中数据点在类之问的隶属度之和等于l ，对于包含n 个数据点的待分类集合来说，所有隶属度的和就是，l 。在条件相同的 9 北京交通大学硕士学位论文 情况下，k e s 算法中所有隶属度的和也为腮。两者都根据有关隶属度 的约束条件来求得隶属度和类中心的更新迭代公式。表面上看起来， k e s 算法和f c m 算法中的类中心之间互相影响，彼此并不独立。故而， 很多学者认为k s 算法是f c m 型的算法。但是，本章可以从理论上证 明，i j e e s 算法并不是真正意义上的f c m 算法的改进算法，而是p c m 算法 的一种特殊模型。 本章将利用理论和实验两种手段证明k e s 算法应该属于p c m 型的 算法，这将有助于聚类算法使用者们正确地认识k e s 算法，使其能够 根据实际应用需要合理地选择聚类算法。 2 2p c m 算法介绍 p c m 算法放松了对隶属度归一化的要求，改变了隶属度函数的约 束条件，对噪声数据有较好的处理能力。p c m 算法中，各个数据点的 隶属度只需满足大于零的条件，并且在产生隶属度和类中心更新迭代 公式时，也没有归一化的约束条件。通过这种方法产生的各个类中心 之间相互独立，即：某一类中心的改变并不会影响到其他的类中心。 因此，p c m 算法中的隶属度可以解释为数据点属于某一类的绝对程度 的值。 p c m 算法的目标函数如下： j 帆v ) 2 荟荟丸+ 善氆荟( 1 一广 2 1 这里，o s s 1 ，叩f 是一个合适的正整数，“= 恢一圳2 ( 本 节中，若未做特殊说明，如定义与此相同) 。 利用拉格朗日乘子法，可以得到使得式( 2 一1 ) 取最小值的必要条 件如下： 1 0 一种模糊聚类算法归类的研究 薹“飘 u = = l 一 善畦 ( 2 2 ) h ，。= 【1 + 何饥，扣叫】。1 ( 2 3 ) 其中，k r i s h n a p u r a 和k e l l e r 还给出了吃的定义为： 郴娑，蹦 ( 2 - 4 ) 荟“： p c m 算法首次把可能性理论运用于聚类，可以较好地处理噪声数 据。但是，它也存在一定的缺点。由于f c m 算法中各个类中心之间互 相影响，所以产生重合类中心的概率很小。而对于p 翻算法，情况就 截然不同了。p c m 算法中各个类中心之间相互独立，彼此并不影响， 易于产生重合的类中心。显然，此时产生的结果是不理想的结果，我 们并不期望这种情况发生。1 9 9 6 年b a r n i 等对p c m 的这一缺点进行了 详细描述。也有一些研究者提出了其他的聚类算法，如s c h n e i d e r 在 2 0 0 0 年所提出的w p c m 算法，这些聚类算法的目标函数及更薪公式与式 ( 2 一1 ) 式( 2 3 ) 相似，我们称这类算法为p c m 型算法。 2 3l e e s 算法介绍 l e e 于1 9 9 4 年提出了一种改进的模糊c 均值算法。l e e s 算法的目标 函数为： ，“，v ) = 荟善“：如 ( 2 5 ) 这里，v 啦，0 ，善荟2 n 类中心k 和隶属度的更新公式 1 1 北京交通大学硕十学位论文 如下： 芝“飘 k = 号- 一 荟“： ；华! ( 2 - 7 ) 荟荟硭。m 如果能够证明l e e s 算法的目标函数与p c m 型算法的目标函数等 价，并且隶属度和类中心的更新迭代等式也分别与p c m 型算法的相 同，那么就可以证明l e e s 算法是p c 哺型的算法。 把式( 2 7 ) 代人到式( 2 6 ) 中去，可以得到如下等式： k ：娑。挲兰 荟“：荟矿训 ( 2 _ 8 ) 得知，同时使用式( 2 6 ) 和式( 2 7 ) 进行迭代与只用式( 2 8 ) 进行 迭代完全相同。下边来分析p c m 型算法的目标函数和类中心及隶属度 的更新公式。 把i ( r i s h n a p u r 锄等于1 9 9 3 年提出的p c m 算法，s c h n e i d e r 等在2 0 0 0 年1 1 0 l 所提出的w p c l 算法，以及k r i s h n a p u r 锄等在1 9 9 6 年i l l l 提出的算法 综合起来，p c m 型算法的目标函数一般为如下形式： j 2 荟善编+ ，魄) 2 9 式中，0 。) 是的函数。 如果取， m ) 一荟善m ，那么就变成了如下形式： 种模糊聚类算法归类的研究 抱咖荟弘妒荟善删* ( 2 10 ) 利用拉格朗日乘子法，可求得式( 2 一1 0 ) 取最小值的必要条件为： “：。：d ! 。“( 2 1 1 ) 类中心”的迭代与式( 2 6 ) 相同，如果把式( 2 1 1 ) 代到式( 2 6 ) 中去， 那么式( 2 7 ) 就变成了与式( 2 8 ) 完全相同的形式，也就是说，对于同 数据集合，若如定义相同，m 取值也相同，l e e s 算法中类中心的更 新公式与( 2 6 ) 是完全一样的。 可以证明，在式( 2 1 1 ) 成立的条件下，最小化式( 2 一l o ) 和最小化 k e s 算法的目标函数式( 2 5 ) 也等价。在此，将以目标函数为式 ( 2 1 0 ) ，隶属度更新公式为式( 2 1 1 ) ，类中心更新公式为式( 2 6 ) 的 聚类算法称作p c m l 算法。 综上所述，l e e s 算法模型的目标函数、迭代过程和p c m 算法的 一种特殊模型p c m l 算法的目标函数、迭代过程分别等价，换句话说， l e e s 算法模型是p c m 型的算法，而非改进的f c m 算法。 2 4 数值实验 本节通过实验来验证以上的结论。为了验证本文提出的观点，分 别对i r i s 数据和人为数据进行了实验。在做实验时，f c m 算法的目标 函数和迭代分别采用第l 节中给出的式( 卜1 ) 和式( 卜2 ) 与式( 卜3 ) ： p c m 算法的目标函数和迭代分别采用第2 节中给出的式( 2 1 ) 和式( 2 2 ) 和式( 2 3 ) ，采用式( 2 4 ) 的定义；l e e s 算法的目标函数和迭代分别 采用式( 2 5 ) 和式( 2 6 ) 及( 2 7 ) ，p c m l 算法的目标函数和迭代分别采 用第3 节中给出的式( 2 1 0 ) 和式( 2 8 ) 。 实验l 在本实验中，采用i r i s 数据作为待聚类的数据集合。i r i s 数据 集合中包含3 类，每一类有5 0 个样本点，其中有两个类的样本点之间 北京交通大学硕士学位论文 有重合。每一样本点有4 个属性特征。本实验中只取前三维属性，权 重指数州取值为2 ，迭代次数为l o o 次，误差取为0 0 00 0 1 ，类别个数 为3 。图争1 为i r i s 数据分布图，从中可以清楚地看到数据的分布情况。 s 6 姜4 2 粤 s 圈2 一li r i s 数据分布图 表2 1 列出了实验结果。从表2 一l 中可看出，f c m 算法的结果基本 上可以代表数据的结构，输出了3 个类中心，而p c m 算法得到的却是3 个重合的类中心，同样，当l e e s 算法的初始类中心与我们所推导出的 p c m l 算法相同时，得到了与p c m l 算法完全相同的3 个重合的类中心， 这与前边的推断一致。 实验2 随机产生如图2 _ 2 所示的数据集合，m 仍然取2 ，迭代次数取1 0 0 次，误差为o 0 0 0o l ，类另n 个数为2 。数据集中样本点的个数为2 0 0 ， 每个样本点有2 个属性。其数据分布图如图2 2 所示，实验结果如表2 2 所示。从表2 2 可以看出，f c m 算法得到了2 个不同的类中心，p c m 算 法得到的是重合的类中心，p c m l 和k e s 算法得到的却是近乎重合的2 个类中心。 实验3 采用与实验2 相同的数据集合，类别个数取2 。m 取1 8 ，迭代次 数取l o o 次，误差为0 0 0 0o l ，实验结果如表2 3 所示。表2 3 的结果 仍然是f c m 算法可以得到指定的2 个不同的类中心，p c m 算法得到的是 重合的类中心，p c m i 及l e e s 算法得到的又是2 个近乎重合的类中心。 1 4 一种模糊聚类算法归类的研究 表2 1 实验l 结果 掣c m 图2 2 人工数据分布图 如果正如有些研究者认为，l e e s 算法是改进的f c m 算法，那么类 中心彼此影响，就不会产生重合的类中心。而如果它是p c m 型的算法， 它就会有p c m 型算法的缺点，也就是容易产生重合的类中心。从实验 结果表2 一l 、表2 2 、表2 3 可以看出，当初始划分相同时，l e e s 算法 的聚类结果与我们所推导出的p c m l 算法的结果完全相同，丽与f c m 算 法的结果差别较大；每次实验中，f c m 算法所产生的类中心都各不相 同，而p c m 算法和p c m l 算法及l e e s 算法产生的却是重合的类中心，这 北京交通大学硕士学位论文 与我们前边的理论分析完全一致。 表2 2 实验2 结果 表2 - 3 实验3 结果 2 5 结论 在本章中，对l e e s 算法模型进行了深入研究：从理论上证明了 l e e s 算法并不是f c m 算法的改进算法，应该属于p c m 型算法：通过实 验验证了l e e s 算法易于产生重合类中心的缺点。这将有助于聚类算法 的研究者重新认识l e e s 算法，又可以为算法使用者们合理地使用聚类 算法提供一定的理论依据。 2 6 本章小结 本章首先介绍了k r i s h n a p u r a l 和k e l l e r 基于可能性理论所提出 1 6 一种模糊聚类算法归类的研究 的可能c 均值( p c m ) 算法，之后又介绍了l e e 于1 9 9 4 年在改变f c m 算法约 束条件的基础上所提出的k e s 算法。l e e 的算法看起来好像仅仅是放 松了传统f c m 中隶属度约束条件的一种，然而通过本章中对该算法的 深入研究发现，它应该是p c m 算法的一种特殊情形。数值实验的结果 更进一步地验证了这一论断。 北京交通大学硕十学位论文 3 一种新的属性加权模糊聚类算法 3 1 引言 属性选择和属性加权是聚类分析中很重要的一个研究课题【1 2 a i 。 文献i 中总结了很多基于不同理论所提出的聚类算法。c 均值算法也 好，模糊c 均值算法也罢，它们都假设在聚类过程中数据对象的所有 属性对聚类结果的贡献相同。然而，这一假设并不适用于现实世界中 的所有情况。对于高维数据而言，很多情况下，某些属性并不相关而 且还可能是噪声数据，这些噪声数据的存在会隐藏已有的聚类结构， 进而影响聚类的效果。也就是说，在决定聚类结构时，一部分属性可 能会比另一部分属性的地位更为重要。既然如此，如何区别这些属性 的重要性呢? d e s a r b o 等在文献【1 3 】中介绍了第一种属性加权的k 均值型聚类算 法s 州c l u s 算法。s y n c l u s 过程可以划分为两个步骤。首先第一个 过程开始于一个初始的权值集合，s y n c l u s 算法使用k 均值算法把数 据集合划分成j 类。接着，把权值均方离差作为花费函数，来估计新 的权值集合。这两个步骤不停地进行重复迭代，直到收敛到一个优化 的权值集合时，算法才会停止。s y n c l u s 算法是个耗时的计算过程f 1 2 j ， 因此不适合对海量数据集合进行聚类。 d es o e t e 在文献1 1 4 】t 旧中提出了一种属性加权的层次聚类方法。因 为层次聚类算法的时间复杂度很高，