（计算机软件与理论专业论文）基于遗传算法的文本聚类技术研究.pdf

摘要 文本聚类是信息检索( i n f o n t l a t i o nr 晰i e v a l ：i r ) 和数据挖掘( d a t am i n i n g ：d m ) 等领域的一个重要研究方向。它是一种无监督的分类方法，根据样本自身的特点 分成若干类，使得类内样本的相似性尽可能大、类间样本的相似性尽可能小。常 用的系统聚类法聚类比较准确，但计算量很大。对样本数很多且维数很高的问题， 这种方法的缺陷更为显现。受迭代方法思想的启发，人们提出了动态聚类法( 也 称逐步调整法) ，从而减少了计算量，这种算法的执行与参数设置是否得当密切 相关，往往需要对样本数据的物理意义进行必要的分析。在高维且数据量大的情 况下，设置合理的参数尤为困难，只能通过多次实验比较来选定；另一方面，聚 类的初始数据集和目标函数都是离散量，存在许多局部极值点，而通常的动态聚 类法没有判别劣值的机制，因此初始聚类中心和样本输入的次序对最终结果有着 很大的影响。 遗传算法( g e n t i c a l g o r 曲m ：g a ) 是一种模拟自然进化过程在全局搜索最优 解的方法。本文利用遗传算法来解决对初始解敏感、易陷于局部最优的文本聚类 问题，提出了基于遗传算法的动态文本聚类。我们采用二进制编码方式对聚类中 心进行编码，以类内中的点与其类中心的欧氏距离作为适应度函数。通过遗传算 法的选择、交叉、变异三个算子操作对类中心进行逐步迭代调整，直至适应度函 数收敛，得到使聚类划分效果最好的聚类结果。在英文语料库r e u t e r s 2 1 5 7 8 上的 前1 0 个常见类( t o p l o ) 实验结果表明：1 ) 该方法可以克服局部极值点的问题：2 ) 聚类结果的评价指标纯度( p u r i t y ) 也比较好。如何把本方法运用于中文语料库和海 量数据集有待我们进一步研究。 本文的创新之处主要有： 1 ) 在k 一均值文本聚类算法的基础上，引入了遗传算法的思想； 2 ) 验证和分析了本文算法在英文数据集上的聚类性能，并把它与其它聚类算 法的性能进行了比较。 关键词：文本聚类；遗传算法；维数约简；潜在语义索引；纯度 a b s t r a c t d o c u m e n tc i u s t e r i n gi so n eo fm o s ti m p o r t a n tr c s e a r c ht o p i ci ni n f o m a t i o nr e i e v a l ( i r ) a n dd a t am i l l i n g ( d m ) c l u s t e r i n g ，a nu n s u p e r v i s e dc l 船s i f y i n gm e t h o d s ，i st h e p r o c e s so ff o u p i n gt o g e m e rs i n l i l a r 出唿i n t oan u m b e ro fc l u s t e r s h i a r c h i c a l c l u s t e r i n gm 础o d c a l lc l u s t e ra c c u r 如1 y ，b u ti tn c e d sl o t so f c a l c u l a t i o n ，e s p e c i a l l y ，h e n 廿1 en u m b e r 蛐dt l i ed i m e n s i o no fs a m p l e sa r en u m 盯e s s t i 玎e db yt l l ei t e 啪c ei nt h e m a m e m a t i c s ，d ”枷i cc l u s t e r i n gm e t h o di si n v e n t e d ，a i l di tc 锄d e d u c ec a l c u l a t i o n t h e o p e r a t i o no ft 1 1 ed ”a m i cc l u s t e r i n gm e t l l o di ss e n s i t i v et 0t 1 1 es e to fp a r a m e t e r ，w h i c h s h o u l d 锄a l y s i st 1 1 ep h y s i c a lm 黜so f t h es a m p l e s ow h 朋t l l en u m b e r 柚dt l l ed i m e n s i o n o f s a m p l e sa r en u m e r e s ，i ti st o od i 伍c u l tt o tp a 豫m e t e r s t bc h o i c ep a r 锄e t e r si so n l y d e n p e n d e do nl o t so f e x p e r i m e n t s ，0 no m e r h 锄d ，t h ei i l i t i a lc o 啦u s 锄dt h et a r g e tf u n c t i o n a r es e p a t e d ，锄d 也e 佗m a yh a v es o m ee x n 弓m 啪s h 删v e v e r ，t h eu s e da l 剃也mh a sn o t am e c h a n i s mt oa v o i dm ew o r r c 蛐l t 1 1 1 u st t l ec l u s t e r i n gr e s u l t s 黜s e n s “i v et oi n i t i a l c l u s t e r i n gc e n t e r sa n dt h eo r d e ro f i i l p u ts a l l l p l e s g 朗e t i ca l g o r i m m s ，m o t i v 戤e db yn a t t l m le v o i u t i o n ，m a k eu s eo fe v 0 1 u t i o n a r y 叩e r a t o r sa n dap o p u l a 廿o no f s o l u t i o n st oo b t a i nt l l e9 1 0 b a l l yo p t i m a lp a r t i t i o no f t l l ed a 诅 t h i sp a p e ri n 仃i ) d u c e st 1 1 eg c n c t i ca l g o r i m mt od e a i 、v i t l lt h ep r o b l 锄t l l a ts o m ed y n a m i c c l u s t e r i n ga l g o r i t l l m sa ms e n s i t i v et 0i n i t i a ls o l u t i o na n dc l u s t e r i n gc e n t e r sc o n v e 唱ea t e x t r e m u m s i nt t l i sp a p e lt h ec l u s t e n gc e n t e ri se n c o d e db yb i i l 趾y ，t 1 1 es u mo ft h e e u c l i d e a nd s t a n c e sb 吒i 押哪nm ep o i n t s 彻dt h e i rr e s p e c t i v ec e n t e 硌i sa d o p t e da s 廿l e f l t n e s sf i l n c t i o na i i dr e s u l t sa 陀g a i n e dt h m u g hs e l t i o n ，c r o s s o v e ra i l dm u 协t i 帆t h e e x p e r i m 朋t a lr e s u l t so nr e u t e r s 2 1 5 7 81 o pl os h o wt h a t ：1 ) m i sa l g o r i t h mc a ng a i ng o o d 陀s u l te 疏c t i v e l y ；2 ) t l l ec i u s t 耐n gc r i t 嘶o nf i l f l c t i o n ( p u r i t y ) d e f i n e do v e rt h ee n t i r e c l u s t e r i n gs o l u t i o ni s 目。o d h o w e v e r ，h o wt o 印p l yt l l em e m o d o nt l l ec h i n e s ec o 甲s ea i l d w h a ti st h er e s u l tw h e nn l ea l g 甜m m0 p e r a l o r r so nm eh i 曲e rd i m e n s i 册a r et ob e r e s o l v e di no u rf b t l i r er e s e a r c h t h em a i nc o n 仃i b u l i o no f t l l i sp a p e ri sa sf o l l o w s ： l 、g i v e nan e w a l g 砥t t l mf o rt l l ed o c u m e mc l u 毗r i n g ； 2 、弧f ya n da n a i y s i st h ea l 鲥t h mo nt l l er e a ld a t a s e t s k e y w o r d s ：d o c u m 蚰tc l u s t e r i n g ；g e n e t i ca l g o r i t h m ；d 砷饥s i o nr e d u c t i o n ；l d t e n t s e m 粕t i ci n d e x ；p t l r i 毋 江西师范大学硕士学位论文 基于遗传算法的文本聚类技术研究 第1 章引言 1 1 研究背景 随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，已经从 点( 单台机器) 发展到面( 网络) ，甚至到i n t e m 吐全球信息系统，使得无论是公司 企业、科研机构还是政府部门。在过去的几年都积累了海量数据资料。人类社会己 经步入一个信息化时代，在人们的日常活动中也在不断地获取信息、分析信息，并 以此来决策自我行为。从某种程度上说，信息的拥有量己经成为决定和制约人类社 会发展的重要因素。面对如此繁杂的数据，仅靠数据库的查询机制和统计方法远远 不能满足现实的需要，它迫切需要能自动、智能地将待处理的数据转化为有用的信 息或知识，从而达到加以利用的目的。数据挖掘”“1 正是为迎合这种需要而产生并 迅速发展起来的用于开发信息资源的一种新的数据处理技术。 数据挖掘是信息技术发展的自然结果，它是从大量数据中挖掘出隐含的、先前 未知的但却具有潜在价值的信息或知识。数据挖掘技术白9 0 年代产生以来，其得到 了广泛的理论研究，它的研究范围涉及关联规则挖掘、分类规则挖掘、聚类规则挖 掘、趋势分析、孤立点分析、演变分析等方面。同时，数据挖掘在现实生活和生产 中也得到了广泛的应用，包括商务管理、生产控制、市场分析、工程设计和科学探 索等等。 聚类分析1 工3 ，8 1 是数据挖掘的研究内容之一，它涉及到许多研究领域，包括数据 挖掘、统计学、生物学以及机器学习等。聚类是根据数据集中各样本自身的不同特 点，将其划分为不同的簇，使得属于同一簇内的个体之间尽可能相似，而不同簇问 的个体尽可能的不同。从而可以用少数几个簇的代表元素来描述整个数据集( 当然， 这可能会丢失数据集中的一些细节信息，但这样却简化了数据集的表示、节省了数 据集的存储空间) 。更为重要且有实际意义的是，由此可能能发现数据集中所蕴涵 的信息或知识。聚类分析是一种重要的人类行为。早在孩提时候，我们就不断地对 我们所见到的一切进行聚类，并通过改进下意识中的聚类模式来学会如何区分动物、 植物，认识世界。通过聚类，人们能够识别出密集的或稀疏的区域，从而发现全局 江西师范大学硕士学位论文基于遗传算法的文本聚类技术研究 的分布模式和数据属性间有趣的相互关系。目前，聚类分析已应用于很多方面，譬 如模式识别、数据压缩、地质学、图像处理、声音处理，以及市场分析等等。 1 2 本文的工作 聚类是根据待判事物的自身性质( 而不管其历史资料和原始数据能分的类数) 和某种判别依据，把性质相近的归为一类，把性质不同的归为不同类。经过几十年 的发展，文本聚类技术得到了长足发展，提出了不少的算法。但在信息量急剧丰富 的今天，文本聚类也面临一些新的挑战。目前运用较广的系统聚类法聚类比较准确， 只要聚类统计量和聚类方法确定了，那么聚类就比较客观，不太受其它因素的影响， 但它计算量大，尤其是当样品个数很大时，计算距离矩阵很费时间。在海量信息的 今天，它的应用受到极大的限制。计算机科学家受到计算方法中迭代法思想的启发： 能否先给一个粗糙的初始分类，然后用某种原则进行调整，直至聚类比较合理为止。 采用这种思想产生的聚类方法就称为动态聚类法( 也称逐步调整法) 。动态聚类法计 算量小、方法简便，同时也可以根据经验先作主观初步分类，选定好初始凝聚点( 所 谓凝聚点，即为类的中心点) ，再根据已选定的样本相似性计算公式对剩下的样本依 照选定的聚类规则进行归类，算出新得到类的重心并以它作为新的凝聚点，反复若 干次，直到结果收敛。然而目前一些动态算法与参数设置是否得当密切相关( 这在 数据量较大，特别是在高维情况下，设置合理的参数尤为困难) ；另一方面，聚类的 初始数据集和目标函数都是离散量，存在许多局部极值点，而通常的算法又没有判 别劣值的机制，因此初始聚类中心和样本输入的次序对最终结果有着很大的影响。 目前采用的对策是用若干个不同的初始中心和聚类数目分别对文档集进行聚类，然 后选择最佳的一个作为最终的聚类结果。但这种策略对于海量数据而言，不仅工作 量巨大，而且有可能落入极值点而不能保证聚类结果的最优性。 基于以上的分析，如能找到理论上能够解决对初始解敏感、易陷于局部最优的 问题，那将有利于文本聚类。遗传算法g a ( g 锄e t i c a l g o r i t l l m ) m 巩7 1 是一种模拟自 然进化过程，通过选择、交叉和变异等操作在全局进行搜索的技术，理论上可以克 服局部虽优，搜索到全局最优解。有鉴于此，本文把它与传统的k 均值算法相结合 用于文本聚类。我们主要的工作如下： 2 江西师范大学硕士学位论文 基于遗传算法的文本聚类技术研究 l 、对英文文档集进行预处理，找出适合的文档表示方法，对维数过高的现象先 采用文档频率提取前1 0 0 0 个特征，然后再用l s i 方法进行降维； 2 、将标准遗传算法与传统的k 均值聚类算法相结合，构建基于遗传算法的聚 类算法； 3 、对表示后的文档利用本文提出的算法进行聚类划分，得到聚类结果； 4 、比较聚类结果与实验数据集的类标签信息，计算聚类评价函数的值，从而获 得本文算法的有效性。 1 3 论文的组织 本文的具体安排如下： 第一章：引言。介绍了本文的研究背景以及本文的工作。 第二章：文本聚类概述。介绍了与文本聚类有关的知识、文本聚类的问题描述 和技术的种类，并介绍了几种比较重要的聚类算法。 第三章：遗传算法的简介。介绍了遗传算法的基本概念，并着重介绍了标准遗 传算法的处理过程及其采用的技术。 第四章：基于遗传算法的动态文本聚类。该章节为本文的重点，集中介绍了本 文所做的工作。针对目前聚类方法有赖于初始聚类中心的选择、样本输入的次序， 并且有可能会产生陷入局部极值点的问题，将遗传算法的思想引入到文本聚类中， 提出了基于遗传算法的文本聚类方法。说明了本文如何把遗传算法的思想应用到 k - m e 舭聚类中去，给出了算法的描述。 第五章：实验和分析。集中介绍了我们采用的数据集和所做的实验，并对实验 结果进行了分析与比较。 第六章：总结与展望。对全文工作进行了总结并提出下一步的工作展望。 扛西师范大学硕士学位论文基于遗传算法的文本聚类技术研究 第2 章文本聚类综述 2 1文本聚类的基本概念 文本聚类的首要问题就是要解决文本的处理问题，或称表示问耐7 ，8 ，9 1 0 儿12 1 。也 e 麓 其中每行表示一篇文档，每列表示一个词。口i ，度量第j 个词在第i 篇文档出现的情 在向量模型中，的值为第j 个词在第i 篇文档中出现的频率 ( t e m - 舶q n c y ，t f ) 。本模型还有加权方式。： 定义： n 表示系统中的文档总数，一表示包含标记词七的文档数目，加吼，表示 词t 在文档嘭中的初始频率。则文献乃中词毛的标准化频率为：z ，2 彘 最大值是通过计算文档d ，中出现的所有词来获得的。如果词七f 不出现在文档d ，中， 则z ，：o ，词毛的逆文档频率域定义为：硼= l o g 盟 最著名的词加权方法”5 1 6 1 定义为：，= ，l o g 等 或者是这个公式的变形。这种词加权方法称为矿一豇扩方法。 在布尔模型中，表示为第j 个词是否在第i 篇文档中出现，出现为1 ，不出现 江西师范大学硕士学位论文 基于遗传算法的文本聚类技术研究 似性度量方法距离和相似系数p ，8 ，9 1 0 ，1 1 ，12 1 。 一、距离 设有m 个样本，p 个指标，数据矩阵为： ，其中元素为表示第i 个样品的第j 个指标。 因每个样本有p 个指标，故每个样品可以看成是p 维空间中的一个点，m 个样 品就构成维空间上的n 个点。因此，我们可以用距离来度量样本之间相似的程度。 常用的距离： 1 ) 阕可夫斯基( m 椭s l ( i ) 距离 如( g ) ：f 芝l 耳，一_ ，| 9 “9 当g2 l 时，为绝对距离。 当口：2 时，为欧氏距离。 当日= 3 时，为切比雪夫距离。 当各变量的测量值相差悬殊时，采用闵氏距离并不合理( 会产生“大数吃掉小 数”的现象) ，需要先对数据标准化，然后用标准化后的数据计算距离。 闵氏距离特别是其中的欧氏距离是人们较为熟悉的，也是使用最多的距离。但 闵氏距离存在不足之处，主要表现在两个方面：第一，它与各指标的量纲有关；第 二，它没有考虑指标之间的相关性，欧氏距离也不例外。 2 ) 马氏距离 设表示指标的协差阵即： z ：p 。k ，其中2 击荟( 一置w 一弓) “：l ，p i = 去磐弓= 吉言 如果z 。1 存在，则两个样本之间的马氏距离为 _ ， ， ， h ；靠 江西师范大学硕士学位论文 基于遗传算法的文本聚类技术研究 司( ，) = ( 而一并，) 1 ( t x ，) 这里x ，为样本的p 个指标组成的向量，即原始资料阵的第f 行向量与样本x ， 类似。 样本工到总体g 的马氏距离定义为： d 2 ( r ，g ) = ( x 一) 。( r 一) 其中为总体的均值向量，为协方差阵。 马氏距离既排除了各指标之间相关性的干扰，而且还不受各指标量纲的影响。 除此之外，它还有一些优点：将原数据作一线性交换后，马氏距离仍不变等。 3 ) 兰氏距离 。 州驴吉萎剿“乩，疗 此距离仅使用于一切。f o 的情况，这个距离有助于克服各指标之间的量纲影 响，但没有考虑指标之间的相关性。 计算任何两个样本t 与工，之间的距离d 口，其值越小表示两个样本接近程度越 大，d 口值越大表示两个样本接近程度越小。如果把任何两个样本的距离都算出来后， 可排成距离阵d ： d = 而，西：，吐。 d 2 l ，以2 ，畋。 d m 以2 ，d 。 其中哦，2 以：一。叱2 0 。d 是一个实对称阵，所以只须计算上三角形部分 或下三角形部分即可。根据d 可对疗个点进行聚类，距离近的点归为一类，距离远 的点归为不同的类。 二、相似系数 1 ) 夹角余弦 将任何两个样本暑与互，看成p 维空间的两个向量，这两个向量的夹角余弦用 江西师范大学硕士学位论文 基于遗传算法的文本聚类技术研究 c o s 岛表示。则 c o s 以= 杰 n a l 1 磐塾且。岛引。 1 口# l a = 1日f2 1 当。0 8 吼，说明两个样本与z ，完全相似；c o s 岛接近l ，说明两个样本t 与 。，相似密切；。0 8 吼= o ，说明与x ，完全不一样；c o s 巳接近o ，说明t 与x 差别 大。把所有两两样本的相似系数都算出，可排成相似系数矩阵： 日= c o s b l ，c o s 只2 ，c o s 岛。 c o s 岛t ，c o s 岛2 ，c o s 见。 c o s 见”c o s 瓯2 ，c o s 既 ，其中c o s b l = c o s b 2 - 一c o s = l 。 日是也一个实对称阵，所以只须计算上三角形部分或下三角形部分。根据日可 对疗个样本进行分类，把比较相似的样本归为一类，不怎么相似的样本归为不同的 类。 2 ) 相关系数 通常所说相关系数，一般指变量间的相关系数。作为刻划样本间的相似关系也 可类似给出定义，即第f 个样本与第，个样本之间的相关系数定义为： = 圭 。一i ) o ，一弓) 且一1 s s l 其中i2 吉妻，刁2 吉喜如。 实际上， o 就是两个向量z ，一置与一e 的夹角余弦，其中 置= ( 置，i ) ，置2 ( 弓，弓) r 。若将原始数据标准化，则置= 墨= o ，这时 2c 。s 嘭。把两两样本的相关系数都算出来，可排成样本相关系数矩阵： 江西师范大学硕士学位论文 基于遗传算法的文本聚类技术研究 r = ( 0 ) = ，l i ， 2 ， 吩l ，2 2 ，吃月 l 2 ， 其中叶- 2 ，2 z 一一2 l ，根据r 可对玎个样本进行聚类。 由前述相似形度量的定义可知道， 用距离度量相似性时，距离越小意味 着越相似；用相似系数作为相似形度 量时，相似系数越大则越相似。另外， 需要注意的是在不同意义下的定义下 得到相似形度可能不一定等价。这可 从图2 1 看出：如果从距离的角度来看， 图2 1 c a 和b 比a 和c 更相似；但从相似系数的角度来看，a 和c 则比a 和b 更相似。所以， 在进行聚类的过程中，应适当地选择不同的相似形度量方法。 2 1 3 聚类的概念 r 1 1 定义1 。给定由一些元组组成的数据库d = ，l ，2 ，) 和整数值七，则聚类问 题就是定义一个映射，：d 斗 1 ，t ) ，其中第i 个元组被映射到第j 个簇k ，中去。 第j 个簇k ，由所有被映射到该簇中的元组组成， 即 置，= i ，( ) = 置，l s ，sj ，d ) 。 r 1 1 定义2 1 给定由一些元组组成的数据库d = ，乞，) 以及两个元组，d 之间的相似性度量s 棚( ，) 和整数值k ，则聚类问题就是定义一个映射 ，：j d _ l ，七 ，其中第i 个元组被映射到第j 个簇k ，中去，l s ，s 七。给定簇置， 封千、tn t i 。k i 都t i t k i 南s h 心# ，t 0 s i 娟4 ，t ) n 定义2 是给出了一个更加严格的备选的聚类定义，其中的相似性关系只是期望 得到的，实际上并不一定能够得到。一般而言，定义1 用的更为普遍。根据以上的 定义，胄”空间中的聚类问题可以描述为：对于给定的n 个样本，按照它们之间的 江西师范大学硕士学位论文 基于遗传算法的文本聚类技术研究 相似性划分为k 个集合。设s = “，屯，矗) 代表n 个原始样本构成的集合， c l ，c 2 ，g 代表聚类后得到的k 个样本集合，则满足 1 ) e o ，f _ l ，2 ，七； 2 ) c ：n c ，= a ，f = l ，2 ，七；，= l ，2 ，女；f ，； i 3 ) u q = s 。 聚类分析也称群分析、点群分析，它是研究分类问题的一种多元统计方法 8 ，1 仉l l ，1 2 ，1 5 ，1 6 1 一一一一。它和判别分析都属于分类方法，但判别分析属于“有师可学”的分类， 而聚类分析属于“无师可学”的分类。它不像判别分析那样有历史资料可循，往往 没有任何历史资料，甚至能分多少类都不清楚，只能根据待判事物的自身性质，把 性质相近的归成同一类，把性质不同的归成不同类。聚类分析根据分类对象不同分 m 9 ，1 0 ，1 1 ，1 2 1 为q 型聚类和r 型聚类一：q 型聚类是指对样本进行聚类，可以用来进行 预测、样本分布划分的研究等：r 型聚类是指对变量进行聚类( 即分类处理) ，可 用于对变量的选择，从而达到维数约简。r 型聚类分析的主要作用是： 1 不但可以了解个别变量之间的关系的亲疏程度，而且可以了解变量组中各 个变量之间的亲疏程度： 2 根据变量的分类结果以及它们之间的关系，可以选择主要变量进行回归分 析或o 型聚类分析。 q 型聚类分析的优点是： 1 、可以综合利用多个变量的信息对样本进行分类； 2 、分类结果是直观的，聚类谱系图非常清楚地表现其数值分类结果； 3 、聚类分析所得到的结果比传统分类方法更细致、全面、合理。 2 1 4 聚类的应用领域 正如前面所述，聚类分析( c l u s 时a n a l y s i s ) 是数理统计中研究“物以类聚” 的一种方法，它是多元分析的一个分支，目前已被广泛地应用于信息检索【1 t 2 0 1 、模 f 1 5 。1 7 1【1 8 ，删2 1 1 式识别一。、机器学习一、图象处理一等研究领域。在农业领域中，有关作物种 植区划、病虫害发生区域、病原菌分类、病害流行类型等许多现象都涉及到分类问 题。在各种领域，可以从时间上聚类，也可以从地域上聚类，还可以从性质、成因 l o 江西师范大学硕士学位论文 基于遗传算法的文本聚类技术研究 或形态上进行聚类。聚类分析是根据样本的属性和特征用数学方法确定样本的亲疏 关系，按其亲疏程度自然地、客观地进行聚类，以得到合理的聚类系统。 2 2 降维技术 大多数情况下，由前面得到的文本表示矩阵都是高维的。也就是说，它的维数 可能是成千上百，甚至上万。如此高的维数不仅影响聚类的速度，更为重要的是它 还会影响到聚类的效果，因为任何数据在带来信息的同时还会带来噪音。特别是那 些对聚类贡献不大，甚至是对聚类效果有负作用的属性，它们还会导致不良的聚类 效果。所以在正式进行聚类前，有必要对原始粗糙的文本数据进行降维处理 1 0 儿1 2 1 3 。2 2 3 - 2 4 。5 3 6 刀捌。有研究表明，对经过降维处理后的特征空间进行数据聚类 不但不会降低聚类算法的聚类性能，反而有助于提高聚类的精度。目前，用得最多 的降维技术有特征选择( f e a t u r es e l e c t i o n ) 和特征提取( f e 咖e x t r t i o n ) 。 2 2 1 特征选择 m j 3 0 4 t2 7 工8 ，5 8 1 特征选择一一1 ，又叫独立评估法。在特征选择时一般都是利用某种评价 函数独立地对每个原始特征项进行评分，然后将它们按分值的高低排序，从中选取 若干个分值最高的特征项来代替原始的特征。现有的降维技术大部分采用这种方法， 但是通过这种方法选择的特征项中可能还包含着一些彼此相关的因素，也就是说还 存在一些冗余现象。 目前，在降维过程中得到应用的特征选择方法主要有以下几种： 1 文档频数( d o c u m e n tf 怕q u e l l c y ，d f ) 文档频数是指包含某特征的文本数目，它的计算方法如下： 如果用p ( w i ，d ，) 表示特征是不是在文本d ，中出现，则它有二元值： p c h ，嘭，= ：ii ， 若n 为所有训练文本的总数，则d f 定义为： d f ( ) = | p ( ，嘭) 。 d f 方法是特征选择方法中最简单的一个，计算相对简单，能适应规模较大的 降维处理，但d f 方法一般仅作为辅助方法使用，而非主要方法。 塑垄塑里苎兰翌壁兰丝兰苎 苎王望堡竺鎏塑塞查塞耋垫查堑窒 2 互信息m i ( m u t u a li n f o r n l a t i o n l 在统计学中，互信息用于表征两个变量的相关性，常被用于文本特征相关的统 计模型及其相关应用的方法。文本特征矽与类别q 的互信息埘( 缈，c ，) 定义如下： m ( 啊) - l 。g 鬻， 。1 1 + 艺( 矿，4 ) 其中，p ( 7 q ) 2 = _ 童惫r 。p ( 矽q ) 为w 在c ，中出现的概率，i d i m + 艺艺( 彬，砖) 。 为该类的训练文本数，( ，4 ) 为词w 在珥中的词频，州为该类总词数， 艺艺( 彬，4 ) 为该类所有词的词频和； 恻 1 + ( 矿，巧) p ( 形) 2 直刍，它表示特征w 出现的概率，为某词在所有训练文 m + 艺艺( 形，4 ) 本中的比重。其中，l d i 为训练集文本数，m 为训练集总词数，兰兰( 形，吐) 为训 练集所有词的词频和。 互信息的直观意义是：对于每个词，用它在每个类别中的出现次数与它在整个 文本集中的出现次数的比率作为该词对每个类别的贡献。 3 z 2 统计量( z 2s t a t i s t i c ) 跟互信息相同，z 2 统计量也用于表征两个变量的相关性。我们可以给出两个 变量( 如文本词组矿和类q ) 的列联表，z 2 统计量则由此表来检验项：文本词组矿 和类q 之间是独立无关的还是具有显著的依赖关系。对于类别c ，和文本词组矿的 矿统计量定义如下： 以k 咿业鼍磊鬻掣 。 ，( ) p ( f y ) p ( c ，) p ( c ) 其中，p ( 矽，q ) 为文本包含词组矿并同时属于类q 的概率；p ( 矿，e ) 为文本不包含 1 2 江西师范大学硕士学位论文 基于遗传算法的文本聚类技术研究 词组形也不属于类c ，的概率：p ( 矿，c ，) 为文本不包含词组矿但属于类c ，的概率： p ( 缈，c ，) 为文本包含词组矿但不属于类c ，的概率；p ( ) 和p ( 矿) 为词组矽是否出 现的概率；p ( c ，) 和j p ( c ，) 为类c ，是否出现的概率。 4 信息增益i g ( i n f o 眦a t i o ng a i n ) 信息增益常被应用于机器学习”领域中，它通过文本词组在文本出现与不出现 的情况来推算该词组的信息量。定义某一词组在文本中出现前后的信息熵之差，文 本特征( 词组) 矽对于类别c ，的信息增益阿( 矿，c ，) 定义如下： 姗剐廿( 啪( 咿) i o g 暑署”( 即( 咿) 1 0 9 与署， 其中，p ( 阡0 为特征矿出现的概率；p ( c ，矿) 为包含特征的文本属于类别c ，的概 率；，( c ，) 为类别c ，出现的概率：p ( 矿) 为特征矽不出现的概率；p ( c 。旷) 为不包 含特征旷的文本属于类别c ，的概率。 当然，除了以上这些特征选择方法之外，还有其它方法，如文本证据权、奇率、 r e l e v a i l c ys c o r e 、g s sc o c 币c i t 函数等，可参看文献一。 2 2 2 特征提取 特征提取8 9 ，1 。1 1 2 1 耻5 乩2 射，也叫综合评估法。特征提取在广义上是一种数学变 换，即通过映射( 或变换) 的方法把高维的特征向量变映射到低维的特征向量，并保 持足够的信息来鉴别事物之间的类别，映射后的特征通常是原始特征的某些组合。 特征提取的基本思想是利用映射( 或变换) 的方法把原始特征项集映射到较低维的 空间中，映射后的特征叫二次特征，它们是原始特征的某种组合( 通常是线性组合) 。 对几个特征作线性组合是一种特别具有吸引力的方法，因为线性组合容易计算，并 且能够进行解析分析。从本质上来说，线性方法是把高维的数据映影到低维空间中。 通过降维映射的方法，构造数日较少的新特征，每个特征都是原有特征的函数，并 通过新特征进行识别。在对数据进行特征提取的过程中，必须保证以下几点： ( 1 ) 保嫡性即通过变换后不丢失信息的特征； ( 2 ) 去相关性 即去掉彼此相关性较强的信息； 江西师范大学硕士学位论文基于遗传算法的文本聚类技术研究 ( 3 ) 能量不变性即保证信息在两种离散空间进行转换时保持能量不变； ( 4 ) 能量的重新分配和集中 即在变换域中尽量使能量集中在少数几个变换 系数上。 目前，在降维过程中得到应用的特征提取方法主要有以下几种： 1 主成分分析( 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 ) 主成分分析又称k l ( k a r h u i l e n - l o e v e ) 变换，是一种基于数据统计特征的多维正 交线性变换，是在最小均方差误差准则的意义下获得最能够代表原始数据特征的投 影方向。该变换的目的是在n 维的数据空间中找出一组m 个正交向量，将数据 从原来的n 维空间投影到由这组正交向量所组成的m 维子空间上。它具有提取 信号的主要特征、抑制噪声、压缩维数等功能，在数据压缩、图像处理、遥感监测、 信号分析等方面有着广泛的应用。 k l 变换产生的矩阵通常取为训练样本集的总体类内离散度矩阵和总体类间离 散度矩阵。对q 0 = l ，2 ，) 的样本集，其总体类内离散度矩阵瓯和总体类间离散 度矩阵最分别定义为： & = 窆只，其中，= 占 ( x 一朋) o 一一) 7 、j q 和 f i 一一 瓯；# 一) ( “一) 7 ，其中卑为各类的先验概率，鸬为各类均值向量，为 总体均值向量，f 为总体协方差矩阵。 在实际应用中，常以样本均值挪l 、样本集总平均向量册、样本方差s 作为h 、 卢和。的估计。 2 项聚类( t e 咖c l u s t e r r i n g ) 项聚类就是试图将在语义方面具有高度关联的项或词进行分组，从而用该分组 的代表元代替原始项来构成向量空间中的维度。项聚类与特征选择是不同的，因为 前者着重阐述项与项( 或词与词) 之间的关联性，而后者则主要是着眼于能够提供 信息的项。 除了以上介绍的两种特征提取方法外，还有其它方法n 1 0 3 8 斯鲫蛳明，如潜在语 义索引( l a t e n ts e m t i ch l d e x i n g ，l s i ) 、f i s h e r 判别分析( f i s h e rd i s c r i m i n a i l t 粕a i y s i s ) 、 1 4 江西师范大学硕士学位论文基于遗传算法的文本聚共技术研究 独立成分分析等。潜在语义索引是本文主要用到的特征提取方法，它在第五章5 1 2 节还会作详细的介绍。 2 3 异常点分析 正如前面所述，聚类分析是根据样本间自身的特性来进行分组的。那么可能出 现这样一些样本点，它们与其他的样本点有着显著不同的特点，通常称为异常点。 在聚类分析中，对异常点的处理是非常困难的。因为强行把异常点归为某个簇或保 留异常点的簇，都可能会导致产生效果不好的聚类。因此，对异常点进行分析是必 f l23 1 要的。 异常点的存在可能说明数据中存在错误( 例如一个发生故障的传感器记录下的 不正确的数据值) ，也可能是一些正确的数据值，只不过这些数值与其他数据非常不 同。譬如，一个身高2 5 米的人与多数人相比就显得过高了。那么在分析个人身高 时，就可把这个值视为异常点。当存在异常点时，许多聚类技术的效果都不理想。 为了保证聚类效果，聚类算法可以发现并剔除异常点。但在实际剔除异常点时一定 要谨慎。例如，假设在数据挖掘中我们进行聚类的目的是水灾预报。与正常水位值 相比，非常高的水位值很少发生，因此可视为异常点。但如果剔除了该异常点，就 不能有效地预报水灾。 异常点检测或异常点挖掘是指在数据集中标识出异常点的过程。发现异常点 后，利用聚类或其他数据挖掘算法可以剔除它们或者按不同方式处理。许多异常点 检测是基于统计技术的。通常假设数据集服从一个已知的分布，然后通过众所周知 的不一致性检验来检测出异常点。但是由于现实世界数据集不一定服从简单的数据 分布，所以这种方法对于真实数据是不适用的。另外，大多数统计检验都假设使用 单属性数值，而现实世界数据集中的数据都是多属性的。采用基于距离测度的检测 技术可能是一条可行的途径。 2 4 聚类统计量与评价函数 ( 一)聚类统计量 一般用到的聚类统计量有：类内距离和类间距离一一。根据距离的不同定 1 4 0 3 j 6 3 7 州 义方式，又有不同的聚类统计量，如绝对值距离、欧氏距离、闵可夫斯基距离、马 江西师范大学硕士学位论文 基于遗传算法的文本聚类技术研究 氏距离。其中欧氏距离用得较普遍，其定义如下 类内距离：i n d i s t a n c f 其中，n 表示类数； s u m ( i ) 表示第i 类包含的文档数； 蕾表示第i 类的类中心。 类内距离是每一类中的文档与其中心距离的总和。它表明类的凝聚程度，一般是越 小越好； 1 类间距离：o u t d i s t 柚c 萨i 其中，n 表示类数； c ，c ，表示第i 和第j 类的类中心。 类间距离是类与类之间距离的总和，它表明类的区分程度，一般是越大越好。 类内距离和类间距离是相互联系且又矛盾的：一般地，类间距离增大，类内距 离相应地会减小；类间距离越大则类内距离就越小。 ( 二) 评价函数 目前采用的评价函数有含混矩阵( c o n f i l s i o n m a 埔x ) 和纯度( p l l r i t y ) 。这两个 评价指标也是有关联的：它们都是对聚类的结果与原始的类标签信息之间的包含关 系进行刻划的，其本质是一致的。 r 蚰s 1 1 含混矩阵在文献一1 中有详细的描述。它是一个矩阵e n 姆，其元素e r l t r y ( o ，i ) 定义如下：由原始的第i 类中的文档而聚类到第。类中的文档数。本矩阵如果每一 行都只有一个元素较大，而其他元素都比之小很多( 最好为o ) ，那么表明该聚类结 果很好；否则，不太好。 纯度在文献一中有详细的描述。它是一个评价聚类后每个类包含原始类某类中 的文档数数目的指标。其定义如下： 1 6 江西师范大学硕士学位论文 基于遗传算法的文本聚类技术研究 p u r 时= 当尸( s ，) l = l ， 其中，s 表示一个类大小为珥的类；k 表示类数；n 表示整个文档数： ，( 墨) 表示是单个类s 的纯度，它定义为：p ( s ) = 二胁x ，( 一) ，一是第 珥 i 个输入类中的文档被聚类到第i 类的数目。 高的纯度表明总的聚类结果与原始类的包含关系越接近，即是原始类的“纯”。 子类。一般的，纯度越高，聚类效果越好。 本文采用类内距离和类间距离作为聚类统计量、纯度指标作为评价函数。 2 5 聚类方法的分类及其典型算法 如前所述，由于聚类算法能够较好地解决众多实际问题。它已经广泛应用于模 式识别f 1 5 】、信息检索【1 6 州、机器学习【1 8 删、图像处理口”、经济等诸多学科和领域。 聚类算法已得到广泛的研究和开发，它大体可以划分为以下几类 ”2 ，3 触1 。1 1 ，1 2 ，1 3 ，1 4 ，2 9 风3 1 阐：划分方法、层次方法、动态聚类法、基于密度的方法、基 于网格的方法和基于模型的方法。 2 5 1 划分方法( p a r t i t i i n gm e t h o d ) 划分方法【1 3 3 8 。4 3 1 3 8 删的主要思想是：给定一个包含n 个数据对象或元组的数 据库，一个划分方法构建数据的c 个划分，每个划分表示一个簇，且c n 。也就是 说，它将数据划分为c 个组，同时满足如下的要求：( 1 ) 每个组至少包含一个对象； ( 2 ) 每个对象必须属于且只能属于一组。通常会采用一个划分准则( 经常称为相似 度函数，例如距离) ，以便保证：同一个簇中的对象是“相似的”，而不同簇中的对 象是“相异的”。这些聚类方法对在中小规模的数据库中发现球状簇很适用。为了对 大规模的数据集进行聚类和处理复杂原始数据形状( 如圆形、环行等) 的聚类，基 于划分的方法需要进一步的扩展。 典型的划分方法包括：k - m e d o i d s ( k 一中心点算法) 、c l a 哦c 1 u s 蜘n gl a 娼。 a p p l i c a t i o n ) 和c l a r a n s ( c l u 咖r i n gl a r g ea p p l i c a t i o nb a s e du p r a n d o m i z e d s e a r c h ) 。划分方法中最早提出的一些算法大多对小数据集非常有效，但对大数据 江西师范大学硕士学位论文基于遗传算法的文本聚类技术研究 集没有良好的可伸缩性，如p a m ( p a r t | t i o n i n ga r o u n dm e d o i d ，围绕中心点的划分) 。 c l a r a 是基于选择的算法，能处理更大的数据集合。c l a r a 算法的主要思想是： 不考虑整个数据集合，而是随机的选择实际数据的一小部分作为样本，然后用p a m 方法从样本中选择中心点。这样从中选出的中心点很可能和整个数据集合中选出的 非常近似。重复此方法，最后返回最好的聚类结果作为输出。其性能取决于样本的 选择：若选中了最佳的中心点，则能得到好的结果；否则永远不能找到最佳聚类结 果。c l a r a n s 是c l r a 算法的一个改进算法。不象c l a r a 那样每个阶段选取个 固定样本，它在搜索的每一步都带一定随机性的选取一个样本，在替换了一个中心 点后得到的聚类结果被称为当前聚类结果的邻居，搜索的邻居点数目被用户定义的