（计算机软件与理论专业论文）中文文本聚类中的特征提取.pdf

摘要 摘要 随着信息处理技术的快速发展，文本聚类作为一种高智能的文本信息处理方 式越来越引起人们的注意。特征提取是文本聚类中的关键一环，只有选择出好 的特征才能较好地反映文本的类别属性，提高聚类效果。本文在参考前人工作 的基础上针对中文文本聚类的特征提取进行了系统的研究，并对词频特征提取 方法进行了改进，同时发现了中文文本特征在词性方面的一些规律，具体工作 如下： 首先，在分析各种特征选择算法的基础上，本文对特征选择的词频方法进行 了改进，既保证了文本向量的有效非零表示，又使得特征选择算法减少了对停 用词表的依赖，减少了特征空间的维数，提高了聚类准确度。 其次，本文对中文文本特征在词性上的潜在性质进行了深入的研究，发现了 中文名词特征的显著重要性，分析了产生这种情况的原因，并通过试验验证了 这一结果。 中文名词特征的显著重要性可以应用在特征提取阶段，进行特征提取时优先 甚至只选择名词特征；或者可以在聚类操作时，如运用k 一e a n s 算法进行聚类 操作时，增加名词特征的权重，提高聚类效果。 最后本文将上述结论在一数据集上利用k m e a n s 算法进行了实际聚类操作 的应用，验证了结论的正确性。 关键词：中文文本信息处理，中文文本聚类，特征选择，特征提取，自然 语言处理，模式识别 a b s t r a c t w i mt h em p i dd e v e l o p i n e n to fi i l f b r m a t i o np r o c e s s i i l gt e c l l i l o i o g y ，t e x tc l u s t e r i n g i sm c r e a s i n g l ya t h a c t i n go l l r 甜e 嘶o n f e a n 】r ee 】( t r a c t i o ni sak e ye l e m e mo ft e x t c l u s t e r i i l g g o o dt e x tf e a t i l r e sc a nr e n e c tt l l e 瑚t u r eo ft e x tb e 仕e ra n di m p r o v e 也e c l u s t e r i n gr e s i l l t t h i sp 印e r a 1 1 d d os y s t e m a t i cs t i l d y i n gt ot h ef e a t u r ee x 廿a c t i o n o fa l i r l c s et e x to nm eb 邪i so fp r e d e c e s s o r s r e s e a r c h t l l i sp 印e rg e ts o m e i m p r o v e m e m t ot l l ep r e s e n tf e a t i l r ee x 仃a c t i o nm e t h o da i l ds o m ec o n c l l l s i o no np a r to f s p e e c ho f c h i i l e s et e x tf c a t u r e f i r s y ，m i sp 印e rd oc e n a i ni m p r o v e m e n tt ot h ep r e s e n tf e a n l r ee x 扛a c t i o n m e t l l o d ，w o r d 丘e q u e n c y b yt l l i sm e t l l o d ，f b 栅ee x 仃a c t i o nc a nr e d u c ed 印e n d e n c e o ns t o pw o r dt a b l ea n df 色a t u r es p a c ed i m e n s i o n s ，i m p m v ec 】1 1 s t e 血ga c c l l r a c y s e c o n m y ，o n 山eb a s i so fn d 印血r e s e a r c ho fp a no fs p e e c ho fc h i i l e s et e x t f b a n i r e ，t h i sp a p e rd i s c o v e r e d t l l en o 诅b l e i m p o n a n c eo fc h i i l e s e n o u l lw o r d f b a t i l r e s ，a i l da n a l y z e 也er e 船0 1 1 sf o rt l l i ss i m a t i o n ，t h e nc e n i 母t l l ed i s c o v e r yb y e x p e r i m e n 切廿o n t h i sd i s c o v e r yc a nb eu s e di i lf e a t i l r ee x 昀c t i o ns t a g e ，b ys e l e c t i n gf e a t i l r e so f n o u nw o r d ；a n dc a na l s ob eu s e di nc l u s t e r i n gs t a g e ，b yi n c r e a s i i l gt 1 1 ew e i g h to fn o u n w o r df b 剐 u r e f i n a l l 弘t t l i sp 印e rd e v e l o p eac l u s t e r i n gs y s t e mo na t e s td a t as e t s a n dd e t a i l e d e x p e r i m e n t a lr e s l l l t sa r ep m v i d e d k e y w o r d s ：c h i n e s e i b x tp i d c e s s i n g ，f e a t l l r es e l e c t i o n ，f e 剐岫e x t r a c t i o n ，n l p ， p a t t e mr e c 0 鲥t i o n i i y3 6 8 霉 南开大学学位论文版权使用授权书 本人完全r 解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下 内部5 年( 最长5 年，可少于5 年) 秘密1 0 年( 最长1 0 年，可少于1 0 年) 机密2 0 年( 最 殳2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：压畚吼 1 6 年亨月弓f 日 第一章绪论 第一章绪论 第一节引言 以文字形式书写的文件自文字诞生以来一直是人类传递知识和信息的重要 媒介和载体。在几千年的历史发展中，人类积累了大量的文本文档，记录着人 类在各个领域所取得的知识和成就。2 0 世纪5 0 年代，电子计算机的诞生，为 我们以非纸介质的形成存储文本文档提供了可能，同时也为我们以自动化的方 式来处理文本文件提供了可能。自此，可以直接利用计算机进行信息处理的电 子文本文件出现了。近年来随着计算机处理性能和i m 巳喊的发展，数字图书馆 和一些新闻机构的创建，文本文件的数量开始以惊人的速度增长。于是，人们 迫切要求发展能够利用计算机以自动化的方法来帮助人们有效地从文本文档中 提取有用的信息。当然，人工进行这种操作固然也可以，而且能够达到最为理 想的准确度( 事实上，计算机诞生以前，人类一直是这样做的) ；但与大量的需 要处理的文本相比，人工进行这种操作的速度必然会非常的慢，而且这种工作 要求操作人员具有较多的专门知识，费用高，周期长，不能满足实际需要。 在这种情况下，模式识别技术应运而生。模式识别技术诞生于2 0 世纪2 0 年代。在西方世界中，有关模式识别基础的讨论最早可追溯到柏拉图，进而被 亚里士多德所发展。亚里士多德将事物的性质区分为“本质属性”( 某一类所有 成员共有的属性) 和“例外属性”( 类中成员间的不同属性) 。这些论述相当于 今天我们所讨论的模式识别中的特征提取的内容。后来随着计算机的出现和人 工智能的兴起，模式识别技术在2 0 世纪6 0 年代迅速发展成一门学科。统计科 学、机器学习和神经网络的发展大大丰富了模式识别的基础。其他一些如计算 机视觉、语音识别的发展有很大程度上又依赖于模式识别的发展。8 0 年来，模 式识别研究取得了大量的成果，在很多领域得到了成功的应用，如印刷体汉字 识别，医学图像处理等。如今，已经有数十种期刊、数千本书以及难以计数的 论文都是有关模式识别的，这个数目还在继续增长。本文所讨论的文本信息处 理是模式识别研究的一个重要方面。 利用模式识别技术进行文本信息处理当前主要有两种方案。一种方案是通过 在有监督的情况下进行文本分类操作。例如假设我们有一个带有类别标签的可 第一章绪论 用训练数据集，并通过挖掘一些有用的先验信息设计了分类器。这种设计方法 就是有监督模式识别( s u p e r v i s e d p a m r e c o g i l i t i o n ) 。一般来说，在有监督的 情况下所进行分类操作精度较高，容易满足人们预先设定好的目标。但是其自 主学习的性能差，而且要求训练文本的类别属性已知。这在某些情况下是难以 做到的。 另一种方式就是进行无监督的模式识别( u n s u p e n r i s e dp 甜e mr e c o g n i t i o n ) ， 也称为聚类( c l u s t e 血g ) 或无监督的文本分类。这种操作不需要在操作之前知 道训练样本的类别属性或者说没有己知类别标签的训练数据集可用。这种情况 在社会科学和工程中也会出现，例如遥感、图像分析、图像和语音编码。聚类 操作的类别结果( 类别数目或类别名称) 不是人工设定的，而是完全由计算机 自己决定。聚类分析也是数据挖掘的主要研究内容之一，它涉及到许多研究领 域，包括数据挖掘、概率统计、机器学习甚至生物学方面的知识。聚类是根据 数据集中数据的不同特征，将其划分为不同的簇，使得属于同一类簇的个体之 间的距离尽可能小，而属于不同类簇的个体之间的距离尽可能大。在文本聚类 中，这种个体之间的距离就是经过特征提取之后的文本向量之间的距离，可以 用向量问的欧氏距离表示，也可用任何一种向量范数表示。聚类操作的结果是 用几个少数类簇代表整个数据集的信息。这样做必然会丢失数据集中的一些细 节信息，但是这样却简化了数据集的表示。聚类分析也是一种重要的人类行为。 如一个人在小的时候，就无意识地不断地改进自己的“聚类模式”来学会如何 区分动物和植物。目前对数据进行聚类分析已经用于许多方面，包括模式识别、 图像处理、医学诊断等方面。通过对数据进行聚类操作，计算机能帮助人们识 别密集和稀疏的区域，进而可以发现全局的分布状态，以及数据属性之间的潜 在的联系。 特征提取是模式识别中的一个关键问题。其基本任务就是如何从许多的特征 中提取出最有效的特征。无论是人工进行文本信息的处理，还是用计算机实现 这样的功能，都要首先找到能有效表示文本类别属性的特征。特征通常可以分 为三类：物理的、结构的和数学的【l 】。人类对事物进行信息处理或归类的时候， 通常利用物理的或结构的特征，因为这些特征容易被视觉或触觉所发现。但使 用计算机进行这些操作的时候，必须使用数学的特征来表示物体，对文本信息 处理而言也是一样的道理。表示一个文本的特征有许多个，如文本中出现的不 同词语及各个词语出现的次数，各个词语之间的顺序等。这就引出了模式识别 2 第一章绪论 中的一个主要问题：维数灾难( c u r s eo f d i i i l e n s i o n a l 时) 。这是因为设计系统时 可以获得的特征数量相当大。这个数量在中文文本聚类中很容易达到数万。如 果直接利用这些特征进行聚类操作，一个问题是计算复杂性太高，二是可能存 在这种情况：虽然两个特征都具有很好的聚类性能，但是将他们组合起来看做 一个特征向量时，由于它们之间的相关性，可能会得不到任何信息。另一个进 行特征选择的主要原因是聚类算法的通用性要求必须这样做。 第二节文本聚类和特征提取的研究现状 1 2 1 聚类算法 在九十年代中期，文本聚类主要使用层次聚类的方法，这种方法利用相似 度( s i i n i l 撕t ) r ) ，或者称为距离( d i 咖n c e ) ，来衡量文本数据之间或者簇( c l l l s t e r ) 之 间的关系，从而决定聚类的过程。在这种算法中的每一步，都要估算现有数据 对象之间的相似程度，并且根据相似程度来进行合并，从而形成新簇。算法的 最后，将得到一个树状的层次结构，其中的每一层代表着聚类中簇的变化情况。 另一种比较基本的文本聚类方法是划分聚类( p a n i t i o n a lc l l l s t e 血g ) ，这种方 法首先按照某种原则，把数据集合划分成为若干个初始簇，所有的文本数据被 分配到不同的簇中，然后根据一个优化算法在簇之间调整数据的归属，使簇的 分布更具合理性，也就是使得簇内文本的相似程度较高，而簇间文本的相似程 度较低。这种方法的时问复杂程度要低于层次方法，但是聚类的结果在很大的 程度上要依赖于簇的初始情况。以文本形式存在的信息数量不断增加，最初的 简单层次聚类算法和划分聚类算法已经不再能够适应庞大文本集合的处理的复 杂性，于是新的方法不断出现，但是总的思想主要还是基于上面两种方法。其 中很多方法在效果上取得了非常显著的进步。本文所使用的k m e a n s 方法即为 划分聚类算法，为了克服k m e a i l s 对初始聚类中心的敏感性， 在文中我们采 用了三种不同的设定初始聚类中心的方法。 基于神经元网络的算法也被应用到文本聚类中。基于神经元网络的聚类算 法中最典型的是陬o h 8 2 】唧】、 g e r 9 9 】和 h o n 9 8 】中提出的自组织映射 ( s e l f o r g a n i z i i l gm 印，s o m ) 。该方法通过把高维空间的对象映射到低维空间上， 来达到聚类的目的。s o m 有两部分组成，样本数据和m a p 。首先对给定的网络 第一章绪论 中的每个神经元随机赋一权重，该权重和样本数据具有同样的维度：然后通过 不断的用样本数据来训练神经元网络，使相似的数据对象映射到同一个神经元 上，从而达到聚类的目的。s 0 m 方法己经在瞰w 0 3 】和【d m r 0 0 】被应用于文本 聚类，但是其初始的m a p 的拓扑结构不易确定，而拓扑结构对聚类结果有着很 大的影响；其次，s 0 m 算法对对象的输入顺序比较敏感；最后，和其他神经元 网络算法一样，s o m 需要不断地进行训练，时间复杂度比较高。 近年来，以模型为基础的数据分析方法引起了人们的关注。它的主要思想 是假设数据空间中的每一个数据都是产生于一个统一的模型。例如，当用某种 概率密度模型表示数据空间的时候，那么假设数据空间中的每一个数据都服从 该概率分布。在确定了产生数据的模型之后，可以通过数学的方法调整模型的 各种参数，使得模型能够很好的拟合数据空间，这样就得到了一个可以用来对 现有或者未知数据进行分析的模型。这种方法在数据挖掘、模式识别等方面得 到了广泛的应用，并且取得了很好的效果。 考虑到验证特征提取效果的通用性，在本文中采用k m e a n s 聚类算法进行 聚类系统的设计。 1 2 2 特征提取 文本聚类是文本信息检索的一个重要手段，它与有监督的文本分类的不同 之处在于它是在无监督的情况下进行文本的类别形成操作。在文本信息检索的 研究领域中，我们通常将大部分注意力放在文本分类中，对文本聚类的研究就相 对的较少，特征提取也是这样。通常在文件分类中，进行特征提取时因为文件 类别信息是已知的，可利用的先验信息较多，所提取的特征也较好。可是在文 本聚类中进行特征提取时，由于缺少文本的类别信息，做起来难度比较大，人 们在这方面的研究也比较少。 具体到中文文本的特征提取，由于中文文本的特点是词与词之间没有明显 的界限，从文本中提取词语时需要分词，因此目前在特征值的粒度单位上也各 有不同。一种是基于字的特征表示，即用汉字作为特征项。用汉字作特征项似 乎是一种非常机械和简单的想法。然而实际应用时，许多实验都表明这种方法 和用词汇、短语做特征项在正确率上并没有明显的下降，而且由于汉字的数量 远远小于词汇的数量，使得运算速度和需要的存储空间远远小于后者。产生这 4 第一章绪论 种现象的原因我们认为主要有两个方面：首先，汉语中存在着大量的单字词语， 这些单字词语多为高频词。据统计，汉语词汇的平均词长为1 6 个字。由此可 见，用汉字做文本特征项是可行的。另一个原因可能是当前汉语分词的效果不 够理想，还存在许多尚未解决的问题，如歧义判断，分词规范的确定、未登录 词语的识别等。这些问题会导致许多分词错误，许多领域有关的未登录词往往 是以单字出现的，因此，用汉字作为特征项可以避免分词的麻烦，系统设计较 容易实现。 另一种就是基于词的特征表示方法，这也是目前大多数研究者采用的方法。 基于词的特征表示是指用词作为特征项。从8 0 年代开始，人们就开始研究中文 分词，目前已取得了很多研究成果。文本采用的也是这种方法，分词软件为东 北大学自然语言处理实验室公布的开放软件“中文分词与词性标注系统 n e u c s p ( t o o l sf o rc h i i l e s es e g m e n t a t i o na 1 1 dp a no f s p e e c ht a g g i i l g ) ”。 关于用词做为特征有一个著名的“z i p f l a w ”1 19 】：即语料库中不同词的出 现频率f 和该词的分类等级r ( r a i l k o r d e r ) 的乘积是一个常数。如图1 1 所示： 0246 p i o to ft n eh y p e r b oj i cc u r v er e i a t i o nfa n dr - ( a d a p e df r o ms c h u i t zp a g e12 0 ) 图1 1 词频率与词语分类等级的关系图 y 轴为不同词的出现频率f ，x 轴代表分类等级r a i l ko r d e r ) 。双曲线形式 的曲线显示单词的频率和分类等级之间的关系。在u p p e r c l 】t - o f f 和l o 嗍l t o 圩 两条线之间的词为出现频率适中的s i 嘶f i c a m w o r d s ，两条线之外的部分是频率 第一章绪论 过高或过低的词汇。从i k s o l v i n gp o w e ro f s i g n j f i c a n tw o r d s 曲线中我们可以看出 频率适中的s i 画f i c a i l t w o r d s 对分类系统的贡献最大。这种方法的准确率和分词 的效果紧密相关；对不同领域的专业词汇和专有名词如果不能进行正确的分词， 将极大地影响特征项的准确程度。 另外也可以采用基于短语的特征表示方法。这种表示法与词的表示法有所 不同，而且从一定程度上来说短语比词更加具有语义表现性。比如“计算机科 学”就比“计算机”和“科学”这两个词更具有表现性。但是，这种方法在实 际应用中并不常见，这主要是因为短语的界定比较困难，特别是中心词的界定 难度较高。如上面的这个例子，如果文本中出现的是“电子计算机科学化定义”， 那么以哪个词为中心来划分短语呢? 现在尚且无法找到统一的标准。 此外，在部分论述中也有采用替换相关词的方法减少特征维数。如果词语 具有相关词，则把该词替换为“义项”+ “数字”的形式，数字为该词语在相关 词文件中所处的组号，如：“哀悼、默哀、悼念、志哀、追悼、吊唁”这几个词 处在第4 组，那么这些词都可替换为“义项4 ”。 第三节关键技术 1 3 1 强信息特征、弱信息特征和不相关特征 在文本信息处理中，特征对文本类别的作用包括两部分：一是特征具有的 分类能力，二是特征具有的描述能力。特征的分类能力是指特征在文本中出现 或不出现对文本信息处理预计文本类型所起作用的大小。当特征在文本中出现 时，处理系统能够以较大的概率预计文本的类型，那么该特征的分类能力就很 强。例如：“门诊”、“血压”等特征在文本中出现时对预计“医学”类文本的作 用是很大的；“大炮”、“战士”、“武器”等特征对预计“军事”类文本的作用是 很大的。因此，分类能力强的特征通常只出现在或者集中出现在相关类型的文 本中。要求特征具有强的分类能力是为了保证处理系统能够将不同类型的文本 区别开。特征的描述能力是指当特征在文本中出现时，为处理系统理解文本内 容提供的信息量大小。但由于目前文本信息处理采用的都是基于统计的机器学 习方法，在进行文本信息处理时，处理系统并没有对文本内容进行理解。因此 描述能力强的特征在基于统计的聚类方法中是难以体现的。 6 第一章绪论 在特征集中，特征的分类能力与描述能力有时是相互矛盾的。例如，对于 一些只在某类文本中出现的稀有特征，它们的分类能力很强，但也可能是噪声， 没有反映文本内容的语义信息。而对于一些常用的二字词，例如“我们”、“人 民”等，它们具有完整的语义信息，但通常均匀地分布在各类型的文本中，因 此，分类能力很弱。根据在分类时所起作用的大小，我们将特征分为三类：强 信息特征、弱信息特征和不相关特征。 强信息特征( s 仃o n gi n f o 肌a t i o nf e a t l 鹏s ) 是指那些对类别判别起很大作用 的特征。它们应该同时具有强的分类能力和强的描述能力。强信息特征是特征 选择的重点。强信息特征包括那些只出现在个别类型文本中的中、低频特征， 和不均匀分布在多个类型文本中的中、高频特征。 弱信息特征( w j a ki n f o 咖a 廿o nf e a t u r e s ) 是指那些对类别判别作用不大的 特征。它们或者分类能力弱，或者描述能力弱，或者两方面都不强。弱信息特 征在特征集中占有很大比例。为了达到一定的降维度，特征选择时需要过滤掉 全部或大部分弱信息特征。但是，删除弱信息特征是特征选择的主要问题，因 为这些特征的情况非常复杂，无法用一个指标进行准确地度量。它们常常在一 个统计量下是弱信息特征，但在另一个统计量下可能成为强信息特征。另一方 面，大部分统计量在度量低频特征的统计特性时准确性很低，这也增加了识别 弱信息特征的难度。 不相关特征( i 仃e l e v a n tf e a t u r e s ) 是指对分类没有作用的特征和对分类起干 扰作用的噪声特征。它们主要包括频度很低的稀有特征和均匀分布在各类型中 的特征。因为在进行特征提取时没有类别信息可以利用，不相关特征在文本聚 类下的特征提取的难点。 1 3 2 中文词语分词的技术 中文文本不同于用英语等西方文字的文本，英语文本中各个单词间的区分 只需要依据文本中的空格即可分开。然而我们的汉语是以字为书写单位的，文 本中词与词之间没有明确的分隔标记，而是连续的汉字串。这样为了将文件用 向量表示，必须对中文文本进行分词操作。在我们的聚类系统中，所使用的分 词软件为第三方软件。 7 第一章绪论 1 3 3 文本的向量表示 为了让计算机能够对文本进行聚类处理，必须以某种计算机能理解的方式 对文本进行表示。语言文字是人类文明进步的产物，但计算机不同于人。人能 通过阅读来对文本进行聚类或者分类，以及理解每个文件的具体内容。但是计 算机不能像人一样来“理解”文本，从本质上说，计算机只认识0 和l 。因此， 必须将以文字表示的文本变换为计算机可以识别的某种格式。目前通用的办法 是用“词袋法b o w ( b 矩o f w b r d ) ”表示文本。即文本可以用组成该文本的各 个词语和每个词语的出现次数表示。这种表示法意味着组成文本的各个词语与 各词语的顺序无关，即组成文本的各词语是相互独立的。很显然，这种假设并 不成立。可是如果把词语的位置信息考虑进去，则会使数据量太大而导致计算 机根本无法处理。采用“词袋法”后文本在计算机中就可以表示成一个文本向 量，向量的各个坐标轴就是“词袋法”中的各词语，而坐标轴对应的坐标值就 是该词语在文本中出现的次数。这种表示方法虽然丢弃了词语的位置信息，但 是易于计算机的处理，而且这种向量表示方便在统一的层面上进行不同具体领 域上( 如图像聚类等) 进行聚类算法的研究。 1 3 4 聚类算法的使用 为了验证特征提取的效果，必须用某种聚类算法对检验文本聚类。为了便 于和其他论文的结果进行比较，遵照本领域中其他研究者多数使用的文本聚类 算法，论文中用k m e a i l s 聚类算法对验证文本进行聚类。 第四节系统性能的评估标准 遵照国际上通用的标准，我们采用了两个常用的聚类评测标准，p r e c i s i o n 和e r l 仃o p y 。按照e r 帅p y 标准，e n 仃o p y 值越小越好，而p r e c i s i o n 评测标准则 相反，p r e c i s i o n 值越大越好【2 】。 1 4 1 p r e c i s i o n p r e c i s i o n 的计算公式较为简单，它假设一个类簇的类标识就等于这个类簇 第一章绪论 中数目最多的那个真实类的类标识，所以某一个类簇d 的p r e c i s i o n 就等于其中 数目最多的真实类所占的比例，其计算公式如式( 1 1 ) ： p r e c i s i o n ( d ) 2 南删小引肋叭4 ) - c 州) “- 1 ) d 表示类簇，d i 表示聚类结束后属于类簇d 的第i 个文件。整体的p r e c i s i o n 是所有类簇的p r e c i s i o n 的加权评价值，如式( 1 2 ) 所示： p r e c i s i 。n ：妻u 掣p r e c 西抽肝( d k ) ( 1 2 ) 智n 1 4 2e n t m p y e n 仃o p y 衡量的是聚类结果中每一个荚蔟的纯度。设c 和c 分别为聚荚所得 到的类簇数和数据集真实的类别数；d l 为聚类结果中的某一个类簇，并设这个 类簇中每一个文本吐d ( f - 1 ，l d l ) 的真正的类别标识为l a b e l ( d j ) ，其值可以 为。( _ ，= 1 ，c ) 。e n n o p y 的计算如公式( 1 3 ) 所示： e 一一薹掣弘砒圳 c 吲 孙2 高d i i l 妇l ( d i ) _ 。川 “4 第五节试验所使用的数据集 为了客观地评价经过特征选取之后聚类系统的性能，我们需要在测试数据 集上进行评估。但是中文文本聚类至今没有一个公开的、标准的语料库。在本 文中我们所采用的试验数据集是由复旦大学李荣陆老师所收集的一个文本分类 语料库。语料库中共有2 8 1 5 个文本，分为1 0 类。其中的大部分文本出自复旦 大学日月光华b b s 。试验中，因为类别“计算机”中的文本包含较多的英文字 符串，与本文的主题中文文本聚类的特征提取有些矛盾，故没有采用。所 9 第一章绪论 以我们采用了十个类别中的中九个类别。分别是：环境类2 0 0 个文本、经济类 3 2 5 个文本、艺术类2 4 8 个文本、军事类2 4 9 个文本、政治类5 0 5 个文本、交 通类2 1 4 个文本、体育类4 5 0 个文本、教育类2 2 0 个文本、医药类2 0 4 个文本， 共2 6 1 5 个文本文件。 为了更为客观地评测特征选择算法的优良性，我们在使用数据集时将该数 据集随机地分为五个独立的数据子集，每个子集有9 0 0 个文本，平均地分属九 个类别。 第六节论文研究的选题及目标 文本聚类是实现计算机高级智能的手段，特征选择是进行文本聚类的关键 环节，特征选择的主要目的是为聚类提供依据，以使内容相关的文本更多地聚 到一类中。本文针对中文文本聚类进行特征选择的研究。中文文本表现为一个 由汉字和标点符号组成的字符串形成的文本，其词语与词语之间没有分割符号， 因而进行基于词的特征选择时需要首先进行分词操作。本文在已分好词的基础 上研究特征选择方法，针对中文文本的特性，提出适合于中文文本聚类的特征 选择方法，并对词频特征选择方法进行了改进；同时深入研究中文文本特征在 词性上的分布规律，进而在词性方面发现了对特征选择具有指导意义的规律。 第七节本文的主要内容及章节组织 本文的研究内容可分为两步分：第一部分研究各种适合于文本聚类的特征 提取算法；第二部分研究文本聚类的算法。 第一部分是论文的主要部分。在有文本类别标识的情况下，适合于特征提 取的方法很多。但是在没有类别标识可以使用的情况下，可选择的方法就很有 限了。我们主要采用以下几种方法进行文本聚类中的特征提取：词频( w f ) 、 单词权( t s ) 、基于位置方差的词频( c w f ) 、基于信息熵的方法( e n ) 在第二部分中，我们主要研究了k m e a n s 聚类算法。包括针对算法对初 始中心的敏感性而采用的三种设置初始中心点的方法，以及使用不同的距离范 数来计算文本类别归属。 在第一章绪论中，我们主要介绍了文本聚类中的特征值提取的发展现状， 1 0 第一章绪论 以及我们工作的内容及其目标。 第二章介绍了我们着重介绍了目前所用的各种适合于文本聚类的特征提取 方法，并对本文取得的结论行了详细介绍。 在第三章中介绍了整个试验系统设计上的一些考虑，给出了试验结论及试 验所使用的试验环境。 我们在第四章中对五种特征选择方法中做了试验数据的分析，对本文所得 到的结论进行了试验证明。 在第五章中，我们对本文的结论进行了总结，并对特征选择未来的发展方 向及要解决的问题进行了描述，供读者参考。 试验过程中的所有程序都是在s u a lc + + 6 o 编程环境中实现的。 第八节本章小结 本章我们首先介绍文本聚类和特征选择方面的概念和发展情况，然后贪 绍7 现在的中文文本聚类和特征值提取中的研究现状，最岳食绍了本文中所用 的一些关键技术、选题意义及本文的结构组织， 第二章特征选择方法的研究 第二章特征选择方法的研究 第一节特征提取研究概述 在中文文献的自动处理工作中，诸如中文文本的自动标引、聚类、自动文 摘等处理技术的出发点都是寻找能表征文本主题的特征信息，也就是文本的描 述首先需要文本主题的特征信息。如何提取这些特征信息成为人们研究的重点。 经观察理解发现，人在提取特征信息时是以对原文的全面理解为基础的。而人 在理解原文时，能综合利用各种信息：如阅读者自身丰富的背景知识、专业知 识、语言知识、经验知识等，人可以对原文有一定程度的理解，进而便能确定 材料的相对重要性。而在文本的自动处理中，要实现上述功能至少在目前还是 不可能的。这也成为自然语言处理的一个难点问题。 又如应用在对网页进行特征描述时，首先需要关注的是网页的特征提取问 题。这项工作类似于中文文本的特征提取，当然更要考虑网页文本自身的特点。 通常特征提取要达到两个目标：一是选取最好的词；二是选取的词最少。显然， 如果对整个网页的词语都进行统计分析，势必会有大量冗余的词语，而多数词 语对分析该网页的内容信息贡献不大，并且大量的词语提取也会造成系统的开 销增大。因此，为了实现选取最少最好的词，在考虑网页文本特殊性的同时， 要对网页中出现的词语进行特征选择方面的分析。这些问题的解决都要依赖文 本分类或聚类中的特征提取问题的解决。 本文针对中文文本聚类的特征提取，文本聚类是无监督的分类操作。即有 一堆这样待聚类的文本，在不知道这些文本类别信息的情况下，根据已有的一 些聚类模型，建立聚类系统。这种聚类系统的一个基本原则是分析每个文本的 特征，找出相似的文本，组成结果中的一个类别。 当采用“词袋法b o w ( b a go f w b r d ) ”进行文本表示之后，整个文本数据 集中的所有词语可以看做是全部的特征，从理论上看我们当然可以采用这些全 部的特征进行聚类，但是这样做会有两个问题：一是运算复杂度高，聚类速度 缓慢；二是聚类准确度不够高。因此，我们必须在已有的特征基础上进行特征 选择。 文中所说的特征选择从较狭义的角度可以分为“特征提取”和“特征选择”。 第二章特征选择方法的研究 这里的“特征提取”指的是：原始特征的数量可能很大，即数据集中的样本处 在一个维度非常高的空间里，这时我们可以通过映射( 或称为变换) 的方法用 维数较低的空间来表示这些样本。因此，“特征提取”指的是一种变换：若用y 表示原始特征空间，维数为m ，用x 表示我们所求的特征空间，维数为n ，则 特征提取器可表示为变换： 彳：y 寸x 当变换为线性变换时，a 可用聆历的矩阵表示。进行文本聚类时，对总体 样本协方差矩阵进行k l 变换得到的矩阵就是一种线性特征提取器。 狭义的“特征选择”指的是：给定大量的特征，通过某种方法选择出其中 的重要特征，以减少特征数量，同时尽量保留有利于聚类的信息，这个过程称 为“特征选择”，有些论文种也称为“特征压缩”。这里的选择标准可以是选择 那些在特征向量空间种类间距离大而类内方差小的特征。 从上述讨论可知，“特征选择”是线性“特征提取”的一种特殊情况。当变 换矩阵a 的任何一行形如i o ，o ，1 ，o ，1 ，1l 时，“特征提取”就转化为：“特征选 择”。本文中的特征选择为广义的特征选择，讨论时并不区分“特征选择”和“特 征提取”。 第二节进行特征提取的必要性 文本对象的高维性：一篇文本，经过预处理，至少包括几百个甚至上千上 万个属性( 词语) ，这些数据与数据库中包括仅仅几个，至多十多个属性的数据 完全不同，导致直接在这些数据上进行聚类非常困难。随着数据对象维度的增 高，在聚类算法的可伸缩性、领域知识需求最小化、发现任意形状的簇以及处 理孤立点的能力等问题上，都面临着很大的问题。一些在低维数据上运行得很 好的聚类算法，在面对高维数据的时候，无论在性能还是效果上都有很大的下 降。这是在文本聚类中必须克服的。 文本对象的稀疏性：一个待聚类的文本集合经过预处理后，一般都是采用 词袋b o w ( b a go f w o r d ) 的向量表示形式。整个向量表示的是该集合中挑选 出来的所有词语，而属于一个文本中的词语可能仅仅占所有词语的很小的一部 分，从而导致了文本表示形式的高度稀疏性。稀疏性导致了对象之间的关系仅 第二章特征选择方法的研究 仅取决于很小一部分的属性，这种情况对于基于相似度的聚类算法会产生很大 的负面影啊，导致了同簇内的文本不相似性，违背了聚类算法的初衷：对基于 模型的算法，也会导致参数估计不准确、片面的缺点，严重影响了聚类质量。 由于文本对象的上述两个特性，从文本数据集中可提取出的特征都有很多， 进行聚类时必须要进行特征提取，这样做的原因有两个：一是减少计算复杂性 太高，避免维数灾难。二是为了聚类算法的通用性。下面我们用具体的例子说 明进行特征提取的必要性： ( a ) r f 2 f 3倒阿f 2 删一 一：痰1 _ - 矽： 。絮- 一 、。 。 t t：-t： ；- 图2 1 特征选择的必要性( 一) 在上面的a 、b 、c 三幅图中，我们分别用三维、二维和一维示例其中的7 5 个点。7 5 个点中分为3 类，每类各有2 5 个。在f l f 2 的特征空间中，3 个类 别服从二维高斯分布，而在f 3 的特征空间中，7 5 个点服从均匀分布。如a 所 示，当三个特征都采用时，7 5 个点的分布显的过于复杂，其类别分属情况难以 看清楚；而当只使用一个特征时( 如图c 所示) ，7 5 个点排成一条直线，3 个类 的任何一个都难以分出。而当使用特征f l 和f 2 时，如上图b 所示，我们能清楚 地分辩出三个服从高斯分布的类簇。 但是特征选择在有些情况下，又必须保留应有的特征： 图2 2 特征选择的必要性( 二) 由于文本聚类没有已知的类别信息可以利用，在上图中，去除x 或y 中的 任何一个特征都会使得最后的聚类情况难以确定。比如当只保留特征x 的时候， 1 4 第二章特征选择方法的研究 所有的向量会呈现如下的分布： 图2 3 特征选择的必要性( 三) 第三节文本特征的提取过程及文本表示 通过不同的评价函数计算出文本中出现的所有词的权值，并将之排序，我 们根据需要可有两种选择方式： ( 1 ) 选择权值最大的某一固定数n 个关键词。 ( 2 ) 选择权值大于某一阈值的关键词。 根据试验对比这两种方法各有优缺点，第一种方式将能保证关键词的覆盖 度，但有时可能不能选择最合适数量的关键词，因为不同文本内容所涉及的主 题概念不同，主题的分散度亦不同：第二种方式所选择的主题词和内容间的关 系相对紧密，但对于主题比较分散的文本，选择的主题词可能过少或过多。 在进行完特征选择后，将剩余的符合条件的词语做为特征。然后对选择的 各个文本进行特征表示的规整，使他们都是由相同的特征词所表示，只是这些 特征词按照权重不同来区分各个特征向量，对于在某一个文本中没有出现的特 征词我们将它的权重置为零。这样对于选择的文本集合中的每一个文本口，可 以表示为： d l = ( 正。，形。；正：，彬2 ；瓦，阡名) 其中弓为文本d f 中第j 个关键词，即为关键词毛在文本中的权重，其中 n 为特征的个数。 第二章特征选择方法的研究 第四节常用特征选择算法及评价 2 4 1 词频( w f ) 文本中的词频分布是极不均匀的，呈宽金字塔型。绝大多数词只出现一次， 高频词在数量上仅占极小的比例，但出现在大多数文本中，其中一些词的聚类 作用小，通过建立停用词表滤除低频词和常见高频词是必要的。以描述西班牙 “3 1 l ”事件的文本为例：在8 1 8 篇报道中，共有l l 0 0 0 ( 不包括标点) 个词语， 其中词频为l 的词有3 5 3 3 个，词频大于1 但只出现在1 个句子中的词有2 7 个， 词频大于6 0 0 的词有4 8 个。按是否具有通用性，词语可分为两类：第一类是常 见高频词，其在任何事件中都是常见词，如：“是、有、和、与、这、还、也、 被、上、据、将、在、中、的、但”等，第二类在特定事件常出现，是该类事 件的关键词，如：“西班牙、组织、爆炸案、袭击、基地、马德里、爆炸、政府” 等。 因此可以采用词频的方法进行特征选择。词频是最为简单的一种方法，它 指的是在整个数据集上每个词语的出现次数，然后优先选择出现次数高的词语 做为特征。出现次数较少的词语将被忽略。 词频方法的一个隐含的假设是出现次数少的词语要么不含有有用的信息， 要么太少而对聚类不足以产生影响，要么是噪音，所以可以删去。 这种方法的优点是简单易行，计算复杂度低，有利于文本向量的有效非零 表示；而且与其他特征提取方法相比聚类效果还可以，甚至在某些情况下还优 于其他特征选择方法。缺点是词频方法不能过滤那些出现频率高的弱信息特征 词。如词“的”，或者在某一关于计算机的数据集中( 此时聚类目的可以是聚成 操作系统，数据库等类别) ，词语“计算机”等。在我们的试验中，在进行了弱 信息词性词语的过虑后，词频方法与下面叙述的几种复杂的方法在聚类正确率 上并无很大的区别，甚至可以直接使用词频方法。我们认为这与中文词语在词 性分布上主要以名词为主有很大的关系。 2 4 2 单词权( t s ) 单词权的定义如式( 2 1 ) ： 1 6 第二章特征选择方法的研究 晒( f ) = p ( f 嘭i f 吐) ，或，嘭d n j 砌( 吐，d ，) ( 2 一1 ) 式中，4 ，嘭表示标号分别为f ，_ ，的两个文本，是相似阈值，用来决定 两个文本是否为相似文本对。 t s 方法的实质就是词语t 出现在文本哦的条件下，t 出现在文本d ，的概率 ( t ，d ，为相似文本对) 。其计算方法可用式( 2 2 ) 表示： 删= ( 。) ( 2 - 2 ) 1 “ 为两个文本中都出现t 的相似文本对数，p 1 1 为t 出现在任一文本的相似文 本对数。在此方法中，可依据两个文本向量夹角的余弦来判定两个文本是否为 相似文本对。 州) = 正。彳，d ，8 2 吲 其中，分子为文本向量z 和嘭的内积，分母为文本向量吐的长度乘以文本 向量嘭的长度。 因为单词权方法含有阈值参数( 如式( 2 1 ) 所示) ，在与其他方法比较 时必须先确定参数的最优值，对此在数据集上所作的试验结果如图2 4 所示： 第二章特征选择方法的研究 图2 4 p r e c i s i o n 在不同阈值参数口下的试验数据 试验的特征数为5 0 0 ，左图为p r e c i s i o n 曲线图，右图为e i 心o p y 曲线图 ( e n n d p y 越小越好) ，通过试验发现，当阈值大于o 7 时，由于相似对太少， 据此方法不能得到5 0 0 个特征，当阈值当为o 1 时t s 方法具有最优的表现性能。 但此时的计算量也会相应的增大一些。 此方法的计算复杂度较高，为d ( 2 r 2 ) 。为文本数据集中的文本数，丁 为此数据集中的所有不同词语数。在后面的试验中，参数的值均取为o 1 。 2 4 3 基于信息熵的方法( e n ) 熵是描述系统确定性的一种度量手段。但是在研究文本聚