（计算机应用技术专业论文）文本聚类集成关键技术研究.pdf

f c l a s s i f i e di n d e x ： u d c ： ad is s e r t a ti o nf o r t h ed e g r e eo fd e n g r e s e a r c h o f k e yt e c h n o l o g i e so nd o c u m e n t c l u s t e re n s e m b l e c a n d i d a t e ：x us e n s u p e r v is o r ：p r o f g ug u o c h a n g a c a d e m i cd e g r e ea p p li e df o r ：d o c t o ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra p p l i e dt e c h n o l o g y d a t eo fs u b m is si o n ： j a n u a r y 。2 01 0 d a t eo fo r a le x a m i n a ti o n ：m a r c h ，2 01 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y ，ir f l 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引用 已在文中指出，并与参考文献相对应。除文中已注明引用的内 容外，本论文不包含任何其他个人或集体已经公开发表的作品 成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本人完全意识到本声明的法律结果由本人承 担。 作者( 签字) ：乃竽淼 日期：如l 口年3 月f q 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 囱在授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ： 孑余森导师( 签字) ：布乏回砖 日期：如l 口年弓月f 8 日20 , 0 年月l 宕日 文本聚类集成关键技术研究 摘要 聚类分析是数据挖掘、模式识别等方向的重要研究内容之一，已被广泛 用于数据压缩、信息检索、语音识别、字符识别、图像分割和文本聚类等。 另外，在生物学、地质学、地理学、市场营销和异常数据检测等方面也受到 越来越多的关注。目前，已有上千种聚类算法，然而没有一种算法可以成功 识别出具有不同大小、不同形状、不同密度甚至可能包含噪声的簇。文本数 据具有高维、稀疏等特点，这使得许多聚类算法并不适用于文本聚类；另外， 文本集规模的海量性对聚类算法的运行效率也提出了很高的要求。作为传统 聚类算法的重要扩展，聚类集成技术具备了传统聚类算法所不具备的诸多优 点。目前，聚类集成已经发展成为机器学习领域的研究热点之一。本文以文 本聚类为应用背景，针对文本聚类集成中的关键问题进行了研究，取得的创 新性研究成果包括： ( 1 ) 鉴于谱聚类方法的诸多优点，本文将基于矩阵扰动理论和谱图理论 的谱聚类算法引入到文本聚类集成问题中。针对谱聚类算法计算复杂度高的 问题，本文基于代数变换，首先将大规模矩阵的特征值分解问题转化为等价 的奇异值分解问题，并进一步转化为小规模矩阵的特征值分解问题。由此设 计了两个不同的文本聚类集成谱算法s m s a 和t m s a 。实验结果表明：本文 的代数变换方法是切实可行的，代数变换前后算法的运行时间大幅度减少， 而且获得的结果非常接近；s m s a 和t m s a 比基于图划分的聚类集成算法更 优越，是解决文本聚类集成问题行之有效的方法。 ( 2 ) 本文研究了谱聚类算法的关键思想，从求解“最佳 子空间出发， 同时推导出文本和超边的低维嵌入，由此设计了两个基于子空间相似度的聚 类集成算法s s i c a 和s s d c a ，实验结果表明：s s i c a 和s s d c a 都获得了 比基于图划分的聚类集成算法更优越的结果；s s i c a 的聚类质量略高于 s s d c a 。本文进一步泛化s s i c a ，设计出基于低维嵌入的文本聚类集成方法。 哈尔滨t 稃大学博十学位论文 该方法首先通过不同的谱聚类算法获得了超边的低维嵌入；随后通过映射的 复合间接获得了文本的低维嵌入；最后根据文本在低维空间下的坐标使用简 单k 均值算法聚类。实验结果表明，该方法比其它常见的基于图划分的聚类 集成方法优越，可以有效解决文本聚类集成问题。 ( 3 ) 本文将非负矩阵分解( n m f ) 引入到文本聚类集成问题中，设计 了b n m f 算法；由于n m f 算法收敛速度较慢、易于收敛到较差的局部最优 解，本文使用k 均值初始化n m f ，设计出n m f k 算法；另外，针对k 均值 算法随机初始化所带来的聚类结果不稳定问题，本文使用最小最大原则确定 k 均值算法的初值，设计出n m f k m m p 算法。实验结果表明：使用k 均值 算法初始化n m f 是有效的，n m f k 获得了比b n m f 算法更加优越、稳定的 结果，且运行效率也比b n m f 高出许多；n m f k m m p 算法可以有效解决文 本聚类集成问题，n m f k m m p 算法运行高效，并且获得了比其它常见的聚类 集成算法更加优越的结果。 ( 4 ) 超球k 均值算法不能有效识别非超球状的簇，因此易于产生精度 较低的文本聚类集成成员。为了进一步提高文本聚类集成算法的聚类质量， 本文在集成成员生成阶段引入了c h a m e l e o n 算法的关键思想“分裂 合并 ( d m ) 策略。首先在聚类成员生成阶段运行使用d m 策略的s k m 算法，次，每次生成较多的文本子簇，并根据子簇的相似性使用w a r d 算法 合并这些子簇，得到，个聚类成员，随后在聚类集成阶段采用本文设计的聚 类集成算法进行集成。实验结果显示，除了基于图划分的聚类集成算法外， 基于层次聚类方法的4 个聚类集成算法以及本文设计的基于谱聚类方法、基 于低维嵌入方法和基于非负矩阵分解方法的多个文本聚类集成算法在使用 d m 策略后获得的平均规范化互信息( n m i ) 都有不同程度的提高，这表明 d m 策略可以有效提高聚类集成算法的聚类质量。 关键词：聚类分析；文本聚类集成；代数变换；低维嵌入；非负矩阵分解； 分裂合并 。 文本聚类集成关键技术研究 a b s t r a c t a so n eo ft h em o s ti m p o r t a n tr e s e a r c ht o p i c si nd a t am i n i n ga n dp a t t e m r e e o g n i t i o r t , c l u s t e r i n ga n a l y s i sh a sb e e nw i d e l yu s e d i na r e a ss u c ha sd a t a c o m p r e s s i n g ，i n f o r m a t i o nr e t r i e v a l ，s p e e c hr e c o g n i t i o n , c h a r a c t e r sr e c o g n i t i o n , i m a g es e g m e n t a t i o n , d o c u m e n tc l u s t e r i n g ，e t c b e s i d e s ，i th a sb e e na t t r a c t e dm o r e a n dm o r ea t t e n t i o ni nb i o l o g y , g e o l o g y , g e o g r a p h y , m a r k e t i n ga n da b n o r m a ld a t a d e t e c t i o n n 1 0 n s a n d so fc l u s t e r i n ga l g o r i t h m se x i s t y e tn oo n ec a ns u c c e s s f u l l y r e c o g n i z ec l u s t e r sw i t hd i f f e r e n ts i z e s ，d i f f e r e n ts h a p e s ，a n dd i f f e r e n td e n s i t i e so r e v e nw i t hn o i s e s m a n yo ft h e ma r en o ta p p l i c a b l ef o rd o c u m e n tc l u s t e r i n gd u et o t h eh i g hd i m e n s i o n a l i t ya n ds p a r s e n e s so fd o c u m e n t s ；f u r t h e r m o r e ，t h e m a g n a n i m i t yo fd o c u m e n ts e t si m p o s e sh i g he f f i c i e n c yo nc l u s t e r i n ga l g o r i t h m s a sa ni m p o r t a n te x t e n s i o nt oc o n v e n i e n tc l u s t e r i n ga l g o r i t h m s ，c l u s t e re n s e m b l e t e c h n i q u eh a sb e c o m eah o t s p o ti nm a c h i n el e a r n i n ga r e ab e c a u s ei th a sm a n y a d v a n t a g e st h a tc o n v e n i e n tc l u s t e r i n ga l g o r i t h m sd on o th a v e t a k i n gd o c u m e n t c l u s t e r i n ga sa p p l i c a t i o nb a c k g r o u n d ，t h i sd i s s e r t a t i o ns t u d i e st h ek e yp r o b l e m si n d o c u m e n tc l u s t e re n s e m b l e ，a n do b t a i n st h ef o l l o w i n gi n n o v a t i v ec o n t r i b u t i o n s ： ( 1 ) s p e c t r a lc l u s t e r i n ga l g o r i t h m sw h i c ha r eb a s e do nm a t r i xp e r t u r b a t i o n t h e o r ya n ds p e c t r a lg r a p ht h e o r y , r e s p e c t i v e l y , a r eb r o u g h ti n t od o c u m e n tc l u s t e r e n s e m b l ep r o b l e m t om a k et h ea l g o r i t h m se x t e n s i b l et ol a r g es c a l ea p p l i c a t i o n s ， t h ee i g e n v a l u ed e c o m p o s i t i o np r o b l e mo fl a r g es c a l e dm a t r i x e si sa v o i d e db y s o l v i n gt h ee i g e n v a l u ed e c o m p o s i t i o no fs m a l lm a t r i x e s a n dt h u sc o m p u t a t i o n a l c o m p l e x i t yo ft h ea l g o r i t h m si se f f e c t i v e l yr e d u c e d e x p e r i m e n t so nr e a l w o r l d d o c u m e n ts e t ss h o wt h a t ( a ) t h ea l g e b r a i ct r a n s f o r m a t i o ni sf e a s i b l e ；( b ) b o t ho f t h e p r o p o s e de n s e m b l ea l g o r i t h m sb a s e do ns p e c t r a lc l u a t e r i n ga l g o r i t h m s o u t p e r f o r m o t h e rc o m m o nc l u s t e re n s e m b l e t e c h n i q u e s b a s e do n g r a p h p a r t i t i o n i n g ，a n dt h e yc a l le f f e c t i v e l ys o l v ed o c u m e n tc l u s t e re n s e m b l ep r o b l e m ( 2 ) t h ek e yi d e ao fs p e c t r a lc l u s t e r i n ga l g o r i t h m si si n t r o d u c e di n t os o l v i n g d o c u m e n tc l u s t e re n s e m b l ep r o b l e m b e g i n n i n gw i t hs e e k i n gt h e “b e s t s u b s p a c e ， t h el o wd i m e n s i o n a le m b e d d i n g so fd o c u m e n t sa n dh y p e r e d g e sa r ea t t a i n e d s i m u l t a n e o u s l y , w h e r e u p o nt w os i m p l ea n df a s ta l g o r i t h m s ，s s i c aa n ds s d c a ， a r ep r o p o s e d e x p e r i m e n t so nr e a l w o r l dd o c u m e n ts e t ss h o wt h a tt h ep r o p o s e d a l g o r i t h m so u t p e r f o r mo t h e rc o m m o nm e t h o d sa n ds s i c ai sal i t t l eb e t t e rt h a n s s d c a s s i c ai sf u r t h e re x t e n d e da n dal o wd i m e n s i o n a le m b e d d i n gm e t h o di s 哈尔滨t 程大学博十学位论文 p r o p o s e d f i r s t l y ，s p e c t r a lc l u s t e r i n ga l g o r i t h m sa r ep e r f o r m e dt oo b t a i nt h el o w d i m e n s i o n a le m b e d d i n g so f h y p e r e d g e s t h e nt h el o wd i m e n s i o n a le m b e d d i n g so f d o c u m e n t sa r ea t t a i n e di n d i r e c t l yb yc o m p o s i t i o no fm a p p i n g sa n df i n a l l y k m e a n sa l g o r i t h mi sp e r f o r m e dt oc l u s t e rt h ed o c u m e n t sa c c o r d i n gt ot h e i r c o o r d i n a t e si nt h el o wd i m e n s i o n a ls p a c e e x p e r i m e n t so nr e a l w o r l dd o c u m e n t s e t ss h o wt h a tt l l ep r o p o s e dm e t h o do u t p e r f o r m so t h e rc o m m o nc l u s t e re n s e m b l e t e c h n o l o g i e sb a s e do ng r a p hp a r t i t i o n i n ga l g o r i t h m sa n dc a r la l s oe f f e c t i v e l ys o l v e d o c u m e n tc l u s t e re n s e m b l ep r o b l e m ( 3 ) n o n n e g a t i v em a t r i xf a c t o r i z a t i o n ( n m f ) i sb r o u g h tf o r t hi n t od o c u m e n t c l u s t e re n s e m b l ep r o b l e ma n db n m fi sp r o p o s e d s i n c en m f c o n v e r g e ss l o w l y a n dt e n d st oc o n v e r g et op o o rs o l u t i o n , n m f ki sp r o p o s e dw h i c hu s ek - m e a n st o i n i t i a l i z en m f f u r t h e r m o r e i no r d e rt os o l v et h eu n s t a b l ep r o b l e md u et ot h e r a n d o mi n i t i a l i z a t i o no fk m e a n s n m f k m m pi sp r o p o s e dw h i c hu s e sm i n i m u m a n dm a x i m u mp r i n c i p l et oa t t a i nt h ei n i t i a lc e n t r o i d s e x p e r i m e n t a lr e s u l t ss h o w t h a t ：( a ) u s i n gk m e a n st oi n i t i a l i z en m fi se f f e c t i v eb e c a u s en m f k c a l lg e t b e t t e ra n dm o r es t a b l er e s u l t st h a nb n m ea n di ti sm o r ee f f i c i e n tt h a nb n m f ；( b ) n m f k m m pc a ne f f e c t i v e l ys o l v ed o c u m e n tc l u s t e re n s e m b l ep r o b l e mb e c a u s ei t o u t p e r f o r m so t h e rc l u s t e re n s e m b l et e c h n o l o g i e sa n di sv e r ye 伍c i e n t ( 4 ) t of u r t h e rb o o s tt h ep e r f o r m a n c eo fc l u s t e re n s e m b l ea l g o r i t h m ，t h ek e y i d e ao fc h a m e l e o n ，d i v i d ea n d m e r g e ( d m ) s t r a t e g y , i si n t r o d u c e dt o r e i n f o r c et h ea b i l i t yo fs p h e r i c a lk - m e a n sa l g o r i t h mt od i s c o v e rc l u s t e r s 、 ，i m i r r e g u l a rs h a p e s i ne n s e m b l em e m b e rg e n e r a t i o np h a s e ，s k mw a sf n s tp e r f o r m e d t oo b t a i nm u l t i p l ed o c u m e n ts u b c l u s t e r sf o rrt i m e s ，e a c ht i m eu s i n gw a r d ，a n a g g l o m e r a t i v eh i e r a r c h i c a lm e t h o d ，t om e r g et h e s es u b c l u s t e r sa c c o r d i n gt ot h e i r s i m i l 撕t y , a n da t t a i n e da ne n s e m b l eo frc l u s t e r i n g s t h e nt h ec l u s t e re n s e m b l e a l g o r i t h m s a r e p e r f o r m e dt oe n s e m b l et h e ，c l u s t e r i n g s e x p e r i m e n t so n r e a l - w o r l dd o c u m e n ts e t ss h o wt h a td m s t r a t e g yi n c r e a s e dw i t hd i f f e r e n td e g r e e s t h en o r m a l i z e dm u t u a li n f o r m a t i o n ( n m i ) s c o r e so ft h ec l u s t e re n s e m b l e a l g o r i t h m s b a s e do nh i e r a r c h i c a l c l u s t e r i n gm e t h o d , s p e c t r a lm e t h o d ，l o w d i m e n s i o n a le m b e d d i n gm e t h o da n dn o n - n e g a t i v em a t r i xf a c t o r i z a t i o nm e t h o d e x c e p tf o r 恤g r a p hp a r t i t i o n i n g - b a s e dm e t h o d t h e s er e s u l t sp r o v et h a td m s t r a t e g yc a ne f f e c t i v e l yi m p r o v et h ep e r f o r m a n c eo fd o c u m e n tc l u s t e re n s e m b l e a l g o r i t h m s k e y w o r d s ：c l u s t e r i n ga n a l y s i s ；d o c u m e n t c l u s t e r e n s e m b l e ；a l g e b r a i c t r a n s f o r m a t i o n ；l o wd i m e n s i o n a le m b e d d i n g ；n o n - n e g a t i v em a t r i xf a e t o r i z a t i o n ； d i v i d ea n dm e r g e 文本聚类集成关键技术研究 第1 章 1 1 1 2 1 3 1 4 第2 章 2 1 2 2 2 3 2 4 2 5 2 6 目录 绪论l 研究背景及意义。l 文本聚类概述3 1 2 1文本表示3 1 2 2 维数约简4 1 2 3 传统的聚类分析方法5 1 2 4 聚类集成方法1 2 1 2 5 聚类结果评价。2 0 研究内容2 2 论文结构2 4 基于谱聚类的文本聚类集成方法2 6 引言2 6 谱聚类方法2 7 2 2 1 国内外研究现状2 8 2 2 2 谱聚类方法存在的关键问题2 9 基于相似度矩阵的谱算法3 1 2 3 1 算法描述与分析3 3 2 3 2 算法有效性分析3 4 基于转移概率矩阵的谱算法。3 7 2 4 1 算法描述与分析3 8 2 4 2 算法有效性分析3 9 实验设计与结果分析4 5 2 5 1 代数变换的有效性4 6 2 5 2 对比实验。4 8 本章小结5l 哈尔滨1 ：= 程大学博士学位论文 第3 章基于低维嵌入的文本聚类集成方法5 2 3 1 引言5 2 3 2 基于子空间相似度的文本聚类集成方法5 4 3 2 1问题描述5 4 3 2 。2 问题求解5 6 3 2 3 基于子空间相似度的直接聚类算法5 8 3 2 4 基于子空间相似度的间接聚类算法6 3 3 2 5 对比实验6 4 3 - 3 基于低维嵌入的文本聚类集成方法6 6 3 4 实验设计与结果分析6 9 3 5 本章小结7 2 第4 章基于非负矩阵分解的文本聚类集成方法7 3 4 1 引言7 3 4 2 n m f 方法7 4 4 2 1基本原理7 4 4 。2 2 乘法更新公式：7 5 4 2 3n m f 算法7 7 4 2 4 n m f 算法存在的问题7 7 4 3结合k 均值与n m f 的文本聚类集成算法7 8 4 3 1 基于n m f 的文本聚类集成算法8 0 4 3 2 使用k 均值算法初始化n m f 8 1 4 3 3 使用最小最大原则确定k 均值算法的初始质心8 2 4 4 实验设计与结果分析8 3 4 4 1 k 均值初始化n m f 的有效性8 4 4 4 2 对比实验8 7 4 5 本章小结9 0 第5 章文本聚类集成中的成员生成方法9 1 5 1引言9 1 文本聚类集成关键技术研究 5 2 聚类成员生成国内外研究现状。9 2 5 3使用d m 策略产生文本聚类集成成员9 4 5 3 1c h a m e l e 0 l n 算法9 4 5 - 3 2 使用d m 策略的文本聚类集成算法9 5 5 4 实验设计与结果分析9 8 5 5 本章小结1 0 5 l 右论10 6 参考文献1 0 8 攻读博士学位期间发表的论文1 2 0 j 疋谢1 2 1 第1 章绪论 1 1 研究背景及意义 第1 章绪论 聚类分析已有四十多年的研究历史，它是数据挖掘、模式识别等方向的 重要研究内容之一，主要应用于数据压缩、信息检索、语音识别、字符识别、 图像分割和文本聚类等【m l ，另外在生物学、地质学、地理学、市场营销和异 常数据检测等方面也受到越来越多的关注【3 】。 随着i n t e m e t 的迅速发展，快速获取有效的信息是人们的迫切要求，这 种需求驱动了文本处理的研究与发展。当前，文本挖掘已经引起了众多研究 者的关注，成为国际上的研究热点之一。文本挖掘是一项综合技术，涉及数 据挖掘、机器学习、模式识别、信息检索、自然语言处理、计算语言学等多 个领域。 文本分类和文本聚类是文本挖掘的两个主要研究内容。文本分类属于有 监督( s u p e r v i s e d ) 学习，然而，通过人工收集并标记大型样本集非常费时费 力，并且i n t e m e t 中的很多信息都是涌现性的，我们对其内部结构并不了解。 因此，作为无监督( u n s u p e r v i s e d ) 学习的主要方法之一，聚类分析可以作为 一种探索性工作，揭示这些信息的内部结构和规律。 与文本分类技术一样，文本聚类也是对大量文本进行自动整理并归类的 技术。不同的是，文本聚类主要是通过对文本集进行分析从而给出一个“最 佳 的划分，而不需要预先对文本进行人工标注类别，因此是一种无监督的 学习方法。 聚类分析可以发现无结构文本集中的“潜在概念 ，并用这些概念来给 出文本集的概要或者标签，因此，它可以有效地组织和搜索大规模文本集。 此外，聚类分析在文本摘要、语义分析和导航搜索引擎的检索结果等方面也 哈尔滨1 二程大学博士学位论文 宣i i 宣昌宣_ 置宣宣宣一r mi i 宣眚i 毫暑宣i i i 嗣皇暑宣置审暑i i i 暑 发挥了重要作用【1 2 1 。 目前，许多著名的国际会议都收录了大量与文本聚类相关的论文，如数 据挖掘领域的k d d ( k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ) 、i c d m ( i e e e i n t e r n a t i o n a lc o n f e r e n c eo nd a t am i n i n g ) 、s d m ( s o c i e t yf o ri n d u s t r i a la n d a p p l i e dm a t h e m a t i c sc o n f e r e n c eo l ld a t am i n i n g ) 、机器学习领域的i c m l ( i n t e r n a t i o n a lc o n f e r e n c eo nm a c h i n el e a r n i n g ) 、e c m l ( e u r o p e a nc o n f e r e n c e o nm a c h i n el e a r n i n g ) 、模式识别领域的i c p r ( i n t e r n a t i o n a lc o n f e r e n c eo n p a t t e mr e c o g n i t i o n ) 、i c d a r ( i n t e r n a t i o n a lc o n f e r e n c eo nd o c u m e n ta n a l y s i s a n dr e c o g n i t i o n ) 、信息检索领域的s i g i r ( a c ms i g i rc o n f e r e n c eo n i n f o r m a t i o nr e t r i e v a l ) 、自然语言处理和计算语言学领域的c o l i n g ( i n t e r n a t i o n a lc o n f e r e n c eo nc o m p u t a t i o n a ll i n g u i s t i c s ) 、c o n l l ( c o n f e r e n c e o nn a t u r a l l a n g u a g el e a r n i n g ) 、e a c l ( a n n u a lm e e t i n go fe u r o p e a n a s s o c i a t i o nc o m p u t a t i o n a ll i n g u i s t i c s ) 、e m n l p ( e m p i r i c a lm e t h o d si nn a t u r a l l a n g u a g ep r o c e s s i n g ) 等。 目前，文本聚类研究中存在的挑战性问题主要有以下三方面。( 1 ) 文本 数据是高维的，会产生b e l l m a n 的维数灾难( c u r s eo f d i m e n s i o n a l i t y ) 现象【4 】。 维数灾难现象表明，在给定模型精度的情况下估计模型，需要的样本数量将 随着维数的增加呈指数增长。与此相关的问题是空空间现象( e m p t ys p a c e p h e n o m e n o n ) 1 5 】，即高维空间本质上是稀疏空间。由此产生的问题是，在多 元统计分析中缺乏一般性的方法来直接估计高维空间的密度，因为相对低密 度的区域包含了样本集的大部分，而高密度区域可能完全没有数据存在。( 2 ) 可扩展性。许多聚类算法在小规模数据集上可以有很高的运行速度，然而实 际应用中文本集的规模通常是数以亿计的。因此，如何设计出高效的文本聚 类算法，使其能够扩展到大规模应用领域是极具挑战性的问题。( 3 ) 如何评 价聚类效果以便进行算法选择与参数选择也是一个重要的问题，例如簇个数 的选取、准则函数的设置等。 2 第1 章绪论 1 2 文本聚类概述 研究文本聚类问题，首先要解决文本的表示和文本特征提取问题。聚类 分析中最有挑战性的步骤就是特征提取或对象表示。许多聚类算法设计者只 是简单地把对象作为聚类算法的输入，避免了这个问题。对于小的数据集， 研究者或许可以根据对该问题的研究经验获得对象的合理表示。然而，对于 大规模数据集，研究人员很难把握每个特征在该问题领域的重要性。对该过 程的有效处理不但可以保持原始数据的完整性、增强数据的可操作性，而且 能提高后续聚类算法的处理效率。对于聚类算法产生的结果如何给出真实、 客观、可信的评价也是文本聚类的一个必不可少的环节。图1 1 给出了实现文 本聚类的主要流程，其中聚类分析方法可以分为传统的聚类分析方法和聚类 集成方法，本文的主要研究内容是针对文本数据的聚类集成方法。下面本节 将首先简要介绍文本的表示和维数约简，随后概述传统的聚类分析方法，并 重点介绍聚类集成方法的提出及其研究现状，最后介绍聚类结果的评价。 1 2 1文本表示 图1 1 文本聚类的主要流程 f i g 1 1f l o w c h a r to fd o c u m e mc l u s t e r i n g s a l t o n 和m c g i l l t 6 】提出了著名的向量空间模型( v e c t o rs p a c em o d e l ， v s m ) ，其基本思想是根据文本的加权词频统计把文本表示为v s m 中的一个 向量，并使用余弦相似度( c o s i n es i m i l a r i t y ) 来计算文本之间的相似度。通 常采用t f i d f ( t e r mf r e q u e n c y i n v e r s ed o c u m e n tf r e q u e n c y ) 对文本进行加权， 哈尔滨丁稗大学博士学位论文 对于空问中( d 为表示描述文本集的特征词个数，亦为向量空i 训的维数) 的文本向量确，其分量劫如下计算： b = 以域x $ i 其中以= o ，o ，嘶= l o g ( h i n ) ，岛= 、( 杉，彬) 2 ，d 为每个词在劫 中的出现次数，n j 为每个词出现在不同文本中的次数。可以看出，嘶捕获了 文本而中词m 的重要性，f 彩捕获了词坳在文本集中的重要性。 s a l t o n 和b u c l d e y | 7 1 于1 9 8 8 年提出了毋项，对文本向量进行归一化 ( n o r m a l i z a t i o n ) 处理，使得文本向量的欧几里德范数为1 。利用该方法，文 机哺的相似度咖“刚= c o s ( 以如删2 编叩硝。因此，欲 求两个文本的相似度，只需计算文本向量之间的点积，而无需每次都计算向 量的长度，这样就可以有效提高聚类算法的运行效率。 1 2 2 维数约简 对于许多应用，例如文本聚类、图像分割等，数据集通常由数以万计的 特征来描述，这就引发了维数灾难问题，因而出现了很多降维技术。维数约 简的目标是把原始的高维数据转换为低维空间表示，同时要保持数据集的内 在结构。 一般来讲，数据挖掘中的许多聚类算法都可以经过维数约简后用于文本 聚类。对于t 个彤空间中的列向量组成的矩阵4 ，每列代表一个文本，而每 行代表描述文本的一个特征词，维数约简可以解释为对么的行通过“聚类 的方法，去掉高度相关或冗余的特征或者合并相关特征。最常用的降维方法 是使用线性代数技术，将数据由高维空间投影到低维空间，如主成份分析 ( p r i n c i p a lc o m p o n e n ta n a l y s i s ，p c a ) 【8 】、核主成分分析( k e r n e lp c a ) 【9 】、 奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ，s v d ) 【1 0 】等。 4 第1 章绪论 1 2 3 传统的聚类分析方法 根据k a n t 学说，任何理论应该包括3 个要素：问题的表达；问题的解决 方法：证明【】。这一评述的要点是一种思想，即理论的这3 个要素在某种意 义上是独立和同等重要的，遗憾的是，聚类分析并不包