（计算机系统结构专业论文）中文文本分类和聚类中的特征选择研究.pdf

中x 文本分类取1 聚娄中的特 d ：选择研究 中文文本分类和聚类中的特征选择研究 计算机系统结构 硕士生：雷琼 指导教师：印鉴教授 摘要 文本分类和聚类是数据挖掘中应用最广泛、研究得最多的一个分支，特征选 择是文本分类和聚类中文本预处理最关键的一个环节，再加上中文语言有着与英 文不同的特点，所以研究中文文本分类和聚类中的特征选择就更有意义。 本文就中文文本分类和聚类中的特征选择问题，从特征选择的评估函数角度 出发进行了深入的研究，用大量的实验综合比较了有监督和无监督的特征选择方 法在中文文本分类和聚类上的特点。此外，根掘基于类别区分词的特征选择方法 中缺少类别区分词的不足，提出了改进方案，即用本文中介绍的有监督特征选择 方法重新获取类别区分词以弥补这种不足，通过在两个中文语料上进行的实验表 明，改进的类别区分词特征选择方法有更好的分类效果。为了研究有监督特征选 择和无监督特征选择的结台问题，把原本用于文本聚类的词同现特征选择，加上 有监督特征选择巾评估函数提供的类信息改进此方法用于文本分类，经过实验表 明，两者的结合取得比较好的文本分类结果。 关键词；特征选择，分类和聚类，词同现，类别区分同 中文文本分类和聚类中的特 i _ 选扦研究 f e a t u r es e l e c t i o nr e s e a r c hf o rc h i n e s et e x tc a t e g o r i z a t i o n a n dc l u s t e r i n g c o m p u t e rs y s t e ma r c h i t e c t n r e n a m e ：l e iq i o n g s u p e r v i s o r ： i nj i a np r o f e s s o r a b s t r a c t t e x tc a t e g o r i z a t i o na n dc l u s t e r i n gi so n ea s p e c to fd a t am i n i n gw h i c hi ss t u d i e d f x e q u e n f l yb yr e s e a r c h e r sa n dh a sb e e na p p l i e de x t e n s i v e l y w h i l ef e a t u r es e l e c t i o ni s t h ek e ys t e pi nt h et e x tp r o c e s so ft e x tc a t e g o r i z a t i o na n dc l u s t e r i n g m o r e o v e r f o rt h e g r e a td i f f e r e n c eb e t w e e nc h i n e s ea n de n g l i s h ，i t sm o r em e a n i n g f u lt os t u d yo nt h e p r o b l e m & c h i n e s e t e x tc a t e g o r i z a t i o na n dc l u s t e r i n g i nt h i s p a p e r , w i t ht h e c o r ec o n t e n to ff e a t u r es e l e c t i o ni nc h i n e s et e x t c a t e g o r i z a t i o na n dc l u s t e r i n g ，w ee x p l o r e dd e e p l yi n t ot h ef e a t u r ee v a l u a t i o np r o b l e m al o to fe x p e r i m e n t sw e r ed e s i g n e dt oc o m p a r et h es u p e r v i s e df e a t u r es e l e c t i o na n d t h eu n s u p e r v i s e di nc h i n e s et e x tc a t e g o r i z a t i o na n dc l u s t e r i n g f o rt h es h o r t a g eo f c l a s s d i s c r i m i n a t ；n gw o r d si n t h ec l a s sc l a s s d i s c r j n l i n a t i n g w o r d sf e a t u r es e l e c t i o n m e t h o d ，an e wm e t h o du s i n gt h et r a d i t i o n a ls u p e r v i s e df e a t u r es e l e c t i o nt or e e v a l u a t e t h ec i a s s d i s c r l m i n a t j n g w o r dw a sp r o p o s e dt or e m e d yt h ep r o b l e m b e t t e rt e x t c a t e g o r i z a t i o nr e s u l t sw e r es h o w e di nt h ee x p e r i m e n t sb yt h en e w m e t h o d i no r d e rt o s t u d yt h ec o m b i n a t i o no ft h es u p e r v i s e df e a t u r es e l e c t i o na n dt h eu n s u p e r v i s e d ，t h e p r e v i o u sf e a t u r es e l e c t i o nm e t h o db a s e d o nw o r dc o o c c u r r e n c ei nt e x tc l u s t e r i n gw a s m o d i f i e db yt r a d i t i o n a lf e a t u r ee v a l u a t i o nf u n c t i o n a n di n t h ee x p e r i m e n t s ，t h e c o m b i n a t i o nm e t h o dg o tag o o dr e s u l ti nt h et e x tc a t e g o r i z a t i o n ， k e yw o r d s ： f e a t u r es e l e c t i o n ，t e x tc a t e g o r i z a t i o na n dt e x tc l u s t e r i n g ，w o r d c o o c c u r r e n c e ，c l a s s d i s c r i m i n a t i n gw o r d s i i 中文文本分类和粜类中的特 j 【= 选择研究 己i 圭 jii = i 随着科学技术的不断发展和互联网的飞速发展与普及，信息量在急速膨胀一 一不管是网络信息、企业信息还是个人信息。作为信息最重要的载体一文本，其 增长速度更是惊人。要想在海量的信息中找到并获取自己所需的信息无异于大海 捞针，没有特定的技术几乎是不可能实现的。因此用于管理和组织信息的先进的 技术就成为时代急需，数据挖掘正是适应这一需要而产生并迅速发展起来的用于 开发信息资源的种新的数据处理技术。 所谓“数据挖掘”，简而言之，就是从庞大的数据库中寻找出有价值的隐藏 信息、模式和趋势，籍由统计及人工智能的科学技术，对资料做深入分析，找出 其中的知识，并提供决策时的参考依据 j 】。 因为在现实生活中，人们可以获取的大部分信息都是存储在文本数据库中， 由来自各种数据源( 如新闻文章、研究论文、书籍、数字图书馆、电子邮件消息 和w e b 页面) 的大量文本组成，这就使得文本挖掘成为了数掘挖掘中的一个最 重要的分支。同时近年来也取得了长足的发展。 其中文本挖掘领域中研究最多也最深入的是文本的分类和聚类问题。文本分 类指的是将一个未知的文本分到一个或多个己确定的主题类别中，其研究最早可 以追溯到二十世纪六十年代初期，但直到二十世纪九十年代刁被得以重视。文本 聚类又被称为自动文本分类，它是指在没有任何预知信息的情况下，将一堆文本 中相似的文本聚在一起，将不相似的文本分开，从而自动形成多个文本类。 文本挖掘处理的文本数据一般是半结构化的，既不是完全无结构的也不是完 全结构化的。一个文本中可能包括结构字段如标题、作者、出版日期等，电可能 包含大量非结构化的文本成分如摘要和内容。故要进行文本分类和聚类，首先必 须对文本数据进行数学描述，现在用得壤多的模型是向量空间模型( v e c t o rs p a c e m o d e l ，v s m ) 。在这种描述模型中，每一个不同的单词都作为特征空间中的一维， 每一个文本是特征空间中的一个向量。但这种描述方法引发了一个非常严重的问 题高维稀疏问题。此外文本数据中还可能出现近义词和多义词两个特有的浯 言现象。如“今天天气真好”和“今天天气真不错”属于近义词现象：如“c h i n a ” 既可以指中国又可以指瓷器，属于多义词现象。文本数据所特有的这三个问题不 仅使得文本分类和文本聚类具有相当高的时间复杂度，而且极大地干扰了分类和 聚类学习算法的准确性，使文本分类和文本聚类的性能急剧下降，因此迫切需要 通过其它技术优化文本的向量表示以帮助提高文本分类和文本聚类的性能。 这些优化技术总制酬1 分为两类：权重调整方法和降维技术。如t f * i d f 权 重调整方法使得一个单词能尽量与文本在语义上相关。但并没有解决上述的三大 中文艾本分类羊n 聚黉中的特f i ：选择研究 问题。不同于啦词权重凋整，降维技术是通过降低文本空问的维度来优化文本的 表示，降维不仅能极大降低特征空间的维度，使文本分类和文本聚类的时间复杂 度大大降低，而且还能非常有效地消除近义词和多义词所引发的噪声和歧义问 题，使文本数据具有更符合其真实浯义勺特征捕述，从而能大幅提高文本分类和 文本聚类的性能。 特征选择和特征抽墩是降维的常见方式。其中特征选择指的是按照定的规 则从原始的特征集合中选择出一小部分最为有效的特征 2 】 3 1 。这些特征仍旧保持 原来的台义，所以能够更好地帮助用户理解文本数据、分类或者聚类的规则和过 程。特征抽取是通过特定的映射函数对原始空问进行旋转、拉伸或者扭曲等变换 从而得到一个新的特征空间p 1 【”。在新的空问中，新的特征能更好地表征原始数 据在概念或者巍语义| = _ - 的分布，这样数据能更好地被分类或聚类。 从上面所叙述的j 知，特征选择是文本分类和聚类中预处理环节最关键的一 个部分，另外由于中文语言的处理特点和中文文字在世界各地的广泛传播，所以 研究中义文本分类和聚类中的特征选择更具有现实意义。本文的主要- l 作如下： ( 1 ) 详细研究了有监督和无j 监督特征选择方法在巾文文本和聚类中的作用，并通 过大量的实验比较了各自的特点，同时针对多个特征选择方法结合使用的问题进 行了实验比较。( 2 ) 改进了一利i 用于文本分类的类别区分词特征选择方浊，实验 结果表明，这样的分类效果更好。( 3 ) 以常用的有监督特征选择方法改进无监督 的词同现特征选择方法为基础研究了有监督特征选择利无雌督特征选择的结合 问题，实验结果表明，这利r 结合在分类中取得了较好的分类效果。 本文研究的意义在丁：通过一些典型的文本源进行特征选择分析，从而总结 出了有峪督和无监督特征选择方法应用于中文文本分类和聚类的特l l ，在此堪础 上还考察了其他一些有用的特征选择方法，为特征选择广泛应用于中文文本挖捌 进行了有益的探索。 本文共分四章，各章主要内容简述如下： 第一章 介绍中文文本分类和文本聚类的关键技术及各自的基本知识。 第二章 介绍特征选择的概念，原因，分类和过程等。 第三章 先简单介绍了类别区分词特征选择方法。然后刈用于改进此方法 的有监督特征选择方法进行实验，找出它i 1 在中文文本分类中的 特点，最后给山了改进算法并进行了实验验证。 第四章 首先介绍了七种无监督的特征选择方法，并在中文文本聚类实验 中比较了各自的特点，最后从改进的无监督同同圳选择方法出发， 结合第三章介绍的有监督特征选择方法，研究r 中文文本分类中 有峤督和无监督特征选择的结合问题，并进行了实验验证。 中文文本分类和聚类中的特征选择研究 第1 章文本分类和聚类概述 1 1中文文本分类和聚类的关键技术 任何原始数据在计算机中都必须采用特定的数学模型进行表示，文本数据也 不例外。建立文本数据数学描述的过程分为三个步骤：文本预处理、建立向量空 问模型和优化文本向量。文本预处理主要采用分词、停用词过滤等技术将原始的 文本字符串转化为词条串或者特定的符号串。文本预处理之后，每一个文本的词 条串被进一步转换为一个文本向量，向量的每一维对应一个词条，其值反映的是 这个词条与这个文本之间的相似度。相似度有很多不同的计算方法，所以优化文 本向量就是采用最为合适的计算方法来规范化文本向量，使其能更好地应用于文 本分类和文本聚类等方面。下面分别介绍这三个方面的关键技术h l 。 1 1 1 自动分词技术 中文自然语言处理与英文自然语言处理存在着一个较大的差异，即英文文章 中的词是独立的，词与词之间有空格作为划分，而中文文章中词与词之间是连续 无标已分隔的，为了提取文本中的关键词，分词是中文自然语言处理的一个必不 可少的步骤。 汉语自动分词是把输入计算机的汉语语句自动切分为词的序列的过程。特定 情况下，分词结果中也包括一些词组和词素。一般来说建造一个好的自动分词系 统，关键是选择一个好的自动分词算法和建立一个好的自动分词词库( 汉语字 典) 。目前国内分词系统所采用的或者砸在研究的方法基本上分为以下几判卅： 1 ) 词典匹配法：如最大匹配法、逆向匹配法、增字或减字匹配法、双向扫 描法、二次扫描法、逐词遍历法、部件词典法。 2 ) 没立标志法：如切分标志法、统计标引法、多层次列举法。 3 ) 词频统计法：如高频优先法、基于期望法、最少分词词频法。 4 1 联想词群法：如联想回溯a b 法、词链法、多遍扫描联想法、联想树分 析法、无词库法。 5 ) 语义语用法：如邻接约束法、扩充转移网络法、综合匹配法、后缀分词 法。 6 1 知识与规则法：如切词规则法、切分与语义校正法、规则描述切词法、 中文文奉分类和聚类中的特钔。选择埘究 生成测试法、语境相关法、短语结构法、词语结构类比法。 7 、人 - i 智能法：如专家系统法、神经刚络方法等。 上述的方法大多数都基于词典，进行字符串匹配，辅之以少量词法、晤法和 语义规则。从本质上可将它们归为2 类：机械分词和理解性分词。从应用的角度 看，主要有以下三类分词方法：( 1 ) 基于字典的机械分词方法；( 2 ) 是基于统计 的机械分词方法；( 3 ) 一类是基于规则和统计的分词方法。 汉语自动分词的难点在下：一是词法的复杂性，汉语字的组词非常灵活，难 以确定字在词中的位置，比如“牛奶”可以分成两个词，但“水牛”却只能作为 一个词而不能分成“水”和“牛”两个词：二足切分的模糊性，例如对“认真实 行”这一汉字宁符串的j l 种可能切分为“认真”、“真实”、“实行”；三是歧义 语句的正确叨分及语法的复杂性问题。目前，由于互联网络通信技术和大容量存 储技术的发展，使传统的语言信息处理方法发生了明显的改变。汉语自然语言处 理系统处理的目标是越来越多的大规模真实文本，例如h ：联网的汉语信息搜索引 擎必须处理网络中海量的真实中文文本数据，所以分词的速度和分词算法的易实 现性变得相当关键，它将强接影响系统的性能。 由于木沦文重点在丁特征选择的研究，所以本论文汝有采用以上的自动分间 方法来分同，而是直接运用中科院计算机研究所的汉语分词系统口】来进行分词， 具体的分词工作主要是使用李荣陆开发的文本分类系统】中的分词模块进行。 1 1 2 向量空问模型( v s m ) 文本自动分类和聚类首先要涉及到分类和聚类文档的表示问题，文档表示是 指以一定的特征项( 如词语) 来代表文档信息，用这些特征项来评价未知文档与类 的相关程度。文档表示所采用的模型众多，但应用较多且效果较好的是向量空州 模型( v e c t o rs p a c em o d e l ) 。 v s m 最基本的思想就是用词袋法( b a g o f - w o r d s ) 表示文本，即将每一个不同 的词条都看成是特征空间中的独立一维，将每一个文本看成是特征空叫中的一个 向量。但是正如引言中所提到的那样，即使是普通规模的文本数据集， f i 通常会 有一万个以上的单词( 维度高) ，但是每一个文本往往只包含印词集中极小的一部 分( 即文本向量上很多维度上为0 ) ，所以这种模型引发了严重的高维稀疏问题。 下面举一个简单的英文文本例子来蜕明v s m 的使用。圈1 一l 中有三个文本 t l 、t 2 、t 3 。除去“f a sa n d ”两个停用词之后，总共得到7 个不同的单词，所 以这个义本数据集的特征空问为7 维，每一维对应一个单同，比如“f e a t u r e ”对 应第一维，这里标识为w l 。然后为每个文本建立相应的文本向量，即为文本 向量的每一维计算相应的值，这个值代表了这个单词与这个文本之j 训的相关程 中文文奉分类和聚类中的特征选择研究 度。公式( 1 一1 ) 使用的是最简单的计算方法：对于某一个文本向量的某一维，如果 这一维所对应的单词出现在这个文本中，那么这一维所对应的值就为1 ，否则就 为0 。这个计算方法用数学来描述的话，如公式( 1 1 ) 所示，其中f 代表一个单词， d 代表一个文本，0 代表文本d 在单词维度上的值。 屹：广酬 l 0 ，p 瓜p ( 1 - 1 、 t i ：f e a t u r es e l e c t i o nf o rt e x tc l u s t e r i n g t 2 ：t e x tc l u s t e r i n ga n dt e x tc a t e g o r i z a t i o n t 3 ：f e a t u r ee x t r a c t i o na n df e a t u r es e l e c t i o nf o rt e x tm i n i n f e a t u r es e l e c t i o nt e x tc l u s t e r i n ac a t e g o r i z a t i o ne x t r a c t i o nm i n i n w lw 2w 3w 4w 5w 6w 7 w l w 2w 3w 4w 5w 6w 7 t 1llll000 t 2 ool1100 t 3 1 1100ll 曼+ + + v e c t o r i n d e x i n gv e c t o r 图l - lv s m 示例 中空文奉分类和聚类中的特稍：选择埘f 究 两个向量之间的距离或者相似度一般用余弦相似度来计算，设v 和v ! 为两个 文本向量，其余弦相似度定义为： l r l 其中v ，v ：为标准向量点积，定义为w 。w ：。，分母中的j 和lv ：1 分别表 = 】 示两个量的长度，定义为卢i 百。 1 1 3 单词权重的计算 在文本由v s m 表示并以单词作为文本的特征项之后，还需要考虑特征项的 权重评价问题，它将作为直接决定文档分类和聚类效果的词文档矩阵的数据 项。 单词权重的考虑因素主要有：词频( t f ) 和文档频数( d f ) 。浏频指的是一个t 誓 词在一个文本中出现的次数。通常情况下，对于一个文本来说，如果一个单同在 这个文本中出现得非常多，那么它就非常可能与这个文本的主题密切相关，所以 重要性就很高：反之，如果一个单词在这个文小中只出现一次，那么它很可能只 是起语法修饰、语言辅助作用的单词，与文本的主题无关，所以重要性就很低。 文档频数指的是这个单词在整个文本数据集中出现的频率。冈为一个单词除了表 达一个文本的主题之外，还有一个重要的功能就是区分这个文本与其他文本。如 果一个单词出现在文本数据集中大部分的文本当中，那么通过这个单词是无法区 分一大批与之相关的文本的。并且如果使用这个单同进行榆索的晒，将返回所有 包含这个单词的文本，即文本数据集中大部分的文本。另一方面，如果一个单词 只出现少数几个文本中，那么它的特殊性就很高，区分与之相关和不相关文本的 能力就很强。所以从这个角度来说，一个币河的重要性与这个单词存一个文本数 据集中出现的频率成反比，即一个单词在越多的文本中出现，它的重要性就越低， 在越少的文本中出现，它的重要性就越高。 综卜所述，币词权重不仅要考虑单词的局部权蘑，即单词在一个特定义本中 的重要性，还要考虑单同的全局权重，即单词在整个文本数据集中的重要性。将 此两因素结合在起，即得到单词权重的通用公式( 1 3 ) ： w m = l o c a l ( t ，d ) + g l o b a l ( f ) ( i 一3 ) 中文文本分类和聚类中的特征选择研究 其中l o e a l ( t ，d ) 表示局部权重，g l o b a l ( t ) 表示全局权重。 t f + i d f 常用的单词权重计算方法是t f * i d f o 占最早由s a l t o n 和b u c k l e y ( 1 9 9 8 ) 提出， 已经被公认为是一种标准的文本向量表示方法。t f t m f 非常有效地将一个单词 的局部权重和全局权重结合在一起，其典型的计算公式如下： ， w t d = 卵( ，d ) g 赢+ 0 0 1 ) ( 1 _ 4 ) 第一项表示t f ( 词频) ，即单词t 在文本d 中出现的次数。第二项表示f ( 逆 文档频数1 ，其中n 代表的是整个文本数据集的文本数，d f 代表的是单词的文档 频数，即在多少个文本中出现。此外考虑到不同文本之间的差异很大，有的文本 可能会很长，比如好几十页，而有的文本却很短，只有一两句话。所以为了使不 同长度的文本具有可比性，t f * i d f 还需要对每一个文本向量进行规一化，即使 文本向量的长度都规范化为l ，归一化的计算见公式( 1 5 ) 所示： 兰型( 1 5 ) | 川 荟”三 规一化之后所有w t d 的值都将介于0 - l 之问，并且两个文本向量在计算余弦 相似度时，其值就直接等于两个向量的点积，如公式( 1 - 6 ) 所示： s i m ( v ，v ，j = v ，v ：= 。w ( 卜6 ) f - 1 t f * i d f 的改进 t f * i d f 是局部权重和全局权重的综合，但它只是表达了一个单词对一个文 本的区分能力，而并没有包含这个单词区分一个类和其他类的能力。很显然，对 文本分类和文本聚类来 兑，更为重要的是一个单词的类区分能力。所以有很多入 针对此问题提出了很多的改进方法，但这些改进方法的目标都是一致的，即要尽 量提高具有类区分力单词的权重，同时降低缺乏类区分力单词的权重。这个调整 的过程用数学公式可以简单地表示为公式( 1 7 ) ，其实就是在公式( 1 3 ) 的基础上扩 展了一项单词的类区分力： w d = l o c a l ( f ，d ) + g l o b a l + c l a s s d i s c ( f ) ( i 一7 ) 其中c t a s s d i s c ( t ) 表示的就是单词的类区z jr z , b e , 力。这个类区分能力在后面就 中文文本分类珥聚类中( 冉特 ：i _ 选样错究 相应的表示为有监督和无临督特征选择中的评估函数值，本论文对这两种情况都 进行了研究。 1 2 文本分类概述 文术分类解决的是将一个未知的文本分到一个或多个已确定的辛题类别中， 其研究丌始于二十世纪六十年代初期，, j - 十世纪几十年代才得到关注。1 7 i 前， 文本分类问题已经得以非常深入且广泛的研究，包括k 最近邻、支持向量机、神 经网络、p e r c e p t r o n w i t hm a r g i n 、b o o s t i n g 等在内一系列非常优秀的分类算法陆 续地被提出并广泛地应用刘信息检索、信息过滤、知识管理、专家系统等应用系 统中。比如使用文本分类技术来自动将各个专利归类一】：将文本分类技术应用存 新闻系统中自动过滤和分类新闻 i o j ；使用文木分类技术来过滤垃圾邮件并将非 垃圾邮件分到相应的类别中】；使用文本分类技术来通过中词所在的上下文来区 分同个单词的不同含义；使用文本分类技术来在w w w 上寻找用户感兴趣的 信息1 ：用文本分类技术来为w w w 上的网页建立分层树来帮助用户一更快捷地浏 览网页等。 因为本论文的重点并不在于研究文小分类算法，而是研究用于文奉分类和 聚类的特征选择，所以这一节只是简单介绍与论文相关的文本分类知识。 1 2 1 文本分类的基本概念 文本分类的任务是为每一个文本类别( d ，0 ) d c 对设定一个布尔值， 其中d 代表个未知文本集，c 代表己确定的一组类别，如果( d ，c ) 被设为“真 ( t r u e ) ”，则表示文本d ，属于类c ，：如果被殴为“假( f a l s e ) ”，则表示义本d ，不属 于类c 。进一步说，文本分类是为了求得一个目标方程中：d c - - - ) 矿，f 用以描 述文本的分类规则，并且使这个方程和未知的理想目标方程中：d c j t ，f 最 为接近。中：d c 斗 t ，f 通常被称为分类器，所以换句话说，文水分类就是求 一个分类器，这个分类器桷结果能最接近理想的分类结果。 文本分类过程如图l 一2 所示，总体上可分为两个步骤：训练和分类。首先是 训练步骤：先将原始的训练文本数据表示成文本向量，然后连同它们的类倩息一 起放入学习系统，由分类学习算法进行学习以生成分类器，分类器包含了所有产 生的分类规则。训练数据指的是一堆已知类别的数据，它是分类问题最为重要的 中文文本分类和聚娄中的特征选择训究 特征之一，也是分类与聚类之间最根本的区别。其次是分类步骤：先将未知的新 文本表示成文本向量，然后使用训练步骤生成的分类器来进行分类以得到它所属 的类别。 训练数据 训练步骤 分类步骤 图卜2 文本分类过程 文本分类分为：单分类和多分类。如果一个未知文本只能被分到一个类里边， 称为单分类。反之，如果一个未知文本可以被分到多个类里边，称为多分类。比 如后一节我们要提到的k 最近邻算法，当k 取l 时，未知文本将被分到与其最相似 的己知文本所在的类，所以是单分类。而支持向量机算法为每一个类别都生成了 一个二元分类器，一个未知文本在每一个二元分类器下都得到一个二元的分类结 果，即属于或者不属于这个类。所以一个未知文本经过分类之后可能不属于任何 一个类，也可能属于多个类甚至所有的类，这就是多分类。单分类和多分类明确 说明了一个文本与一个类之间的关系：要么属于、要么不属于。这种结果有时候 过于武断，所以相对于它们。人们还提出了模糊分类的概念。模糊分类并不明确 指出一个文本是否属于一个类，而是用概率来描述个文本属于一个类的可能 性。当然，概率越大说明这个文本与这个类越相关，属于这个类的可能性也就越 大。 1 2 2 常用的文本分类算法 文本分类的算法众多，主要有k n n 、线性最小方差、贝叶斯网络、决 策树、s v m l l7 、神经网络、r o c c h i o 算法、p e r c e p t r o n w i t h m a r g i n 、b o o s t i n g 等等。 因为各个方法而向的对象不同，所以很难综合比较这些算法性能的差异，至 今为止还没有一篇文章非常科学、客观、全而地比较了所有这些分类算法。但是 通过对所有相关文献所得到的分类结果的统计和比较，可以得到以下一些公认的 结论【”i ： 中更文奉分类和聚类中f i 勺特托选择埘究 s v m l i b o o s t i n g 是最为优秀的分类算法； k n n 、神经网络、线性最小方差比s v m 利b o o s t i n g 略差，其中k n n 还有 一个很突出的优点，那就是其分类模型相对最为简单； 贝叶斯、r o c c h i o 算法和决策树等分类算法的性能相对较差。 由于k n n 的思想非常简单，通过它能很好地理解分类的概念，所以本节只 简单介绍一f k - 仆i 。 k n n c s g i 沩k 最近邻) 是识别领域非常著名的统计算法，它在文本分类研究丌 始兴起之前就己经被应用到了文本分类卜，并且也已经被证明是最优秀的文本 分类算法之。 k n n 思想非常简单：给定一个未知文本，在训练数据中找出与其最为相似 的k 个训练文本，这k 个训练文本即为这个未知文本的k 个“近邻”。然后根据这 k 个近邻来便可确定未知文本所属的类，比如最常用的方式就是未知样本被分到 k 个近邻中最相似的类中。文本与某个类相似度的计算公式为f 1 8 ) ： k s i m i t a r i t y ( x ，q ) = s i m ( x ，吐) ( z ，c 。) ( 1 8 ) 仁( 其中s i m ( x ，d ，) 是未知文小x 与第i 个最近邻文本之问的相似度( c o s i n e 距离) ， ，( 吐，c ，) e0 ，1 是一个函数，当d ，的类为c ，时，其值为l ，否则为0 。 1 2 3 文本分类结果的评价方法 文水分类结果的优劣必须有特定的评价标准才能进行比较。一般来说从三个 方面进行评价：有效性、计算复杂度和算法拙述的简洁度。其中有效性衡量一个 分类器砸确分类的能力：计算复杂度包括时间复杂度和空间复杂度，若按照分类 步骤来分，计算复杂度又可分为训练复杂度和分类计算复杂度；算法描述的简洁 度容易理解，算法越简洁越好。其中以有效性最重要，不管分类器速度多快，算 法多简洁，如果不能正确分类，那这个分类器是无用的。本文中关于分类结果的 评价就是关于有效性的评价。 下而介绍有效性评价中三个最为常用的标准：p r e c i s i o n ，r e c a l l 和f m e a s u r e 。 p r e c i s i o n 和r e c a l l 是信息检索叶最为重要的评价方法，也被广泛地应用于文 本分类的评价之中。在介绍p r e c i s i o n 和r e c a l l 含义之前，先看一下相依表 ( c o n t i n g e n c yt a b l e ) 。相依表是针对某一个类而言的，它统计了所有测试文本与 这个特定类之问的分类情况。 中文文本分类年1 聚类中的特征选择研究 表卜j 类。的相依表 实际属于这个类 实际不属于这个类 分类器认为属于这个类 t p if p i 分类器认为不属于这个类 f n 刑j 表卜1 所示的就是相依表，表中一共有四项，其中 碣一指的是被分类器正确分到类c ，的文本数i q 一指的是实际不属于类c ，却被分类器错误分到类巳的文本数； t n ，一指的是实际属于类勺但分类器却没有将其正确分到类c ，的文本数； ，m 一指的是实际不属于类c ，且没有被分类器分到类c ，的文本数。 根据相依表，p r e c i s i o n 和r e c a l l 分别定义为公式( 1 9 ) 平1 1 公式( 1 一l o ) ： 弘：l ( t - 9 ) j d = 一 i t p r 七f p i r ，：# 等 ( 1 - 1 0 ) = 一 ( 1 一) i t p j + t n i 从公式可知，p r e c i s i o n 衡量的是所有被分类器分到类。，的文本中正确文本的 比率；r e c a l l 衡量的是所有实际属于类勺的文本被分类器分到类c ，中的比率。 p r e c i s i o n 和r e c a l l 是两个互相矛盾的衡量标准，一般情况下，p r e c i s i o n 会随 着r e c a l l 的升高而降低，两者不可兼得，所以很多情况下需要将它们综合在一起 考虑。最常用的综合方法就是f - m e a s u r e ，它的定义如公式( 1 一1 1 ) 所示： w 问= 等” 其中是一个调整参数，用于以不同的权重综合p r e c i s i o n 和r e c a l l 。当卢等于1 时，p r e c i s i o n 和r e c a l l 被平等对待，如公式( 1 t 2 ) 所示，此时f - m e a s u r e 也被称 为f l 。 中文文本分类和策类中的特征选择研究 f ( j p ，凡) ：竺( 1 一1 2 ) ，+ 月 p r e c i s i o n 和r e c a l l 及f 1 都是针对甲个类的分类情况而高的，当需要评价某 个分类算法的时候，还需要将所有类上的结果综合起来得到平均的结果。综合的 方法通常有两种：m i c r o a v e r a g i n g ( 微平均) 和m a c r o - a v e r a g i n g 【宏平均) 。 m i c r o a v e r a g i n g 在计算时，首先需要将所有类的相依表累加起来得到一个全局的 相依表，如表12 所示，然后再分别计算m i c r o - a v e r a g i n gp r e c i s i o n ， m i c r o a v e r a g i n gr e c a l l 和m i c r o - a v e r a g i n gfl 。 表卜2 全局相依表 实际属于这个类 实际不属于这个类 分类器认为属于这个类i c 【c ”= 玛f p = 嘎 分类器认为不属于这个类c |o i 刑= 巩f n = f n ， 埘c r 【) 一p ：! ( 卜t 3 ) ip+p 删c 阳一r ：! ( 卜1 4 ) j l p 十7 7 m i c r 。f 1 ：2 x m i c r o - p x m i c r o - r ( 1 - ts ) m t c r o p + m t c r o r m a c r o a v e r a g i n gp r e c i s i o n ，m a c r o a v e r a g i n gr e c a l l s h m a c r o - a v e r a g i n gf 1 的计算公 式分别如公式( 1 1 6 ) 、公式( 1 1 7 ) 和公式( 1 一i8 ) 所示： 施。一j d ：盟1 6 ) 删一只：盟( 1 _ c 胁c r 。一f 1 ：2 x m a c r o - p 。m a c r o - r ( 1 - t s ) v l a c r o p + a 矗1 c r o r 中文文本分类和聚类中的特征选择研究 1 3 文本聚类概述 文本聚类也是文本挖掘中个非常重要的问题，它是将一堆文本中语义相近 的文本聚在一起。文本聚类己经被广泛地应用在很多地方，比如将其应用在信息 检索系统中用以提高信息检索的效率 i ”、用文本聚类来组织搜索引擎返回的结 果【2 0 】、用文本聚类来帮助用户浏览超大规模的文本数据洲、通过文本聚类来生 成w e b 文本的分类层次树22 1 、还有用文本聚类来帮助用户管理和组织个人 e m a i l 、电子文档等。 文本聚类又是一个非常难的问题，因为一方面聚类本身很困难，没有任何预 知信息，它对所要划分的类是未知的。另一方面，文本数据本身的特点又让文本 聚类难上加难，因为单词之间复杂的语义联系和过高的维度都会导致聚类性能的 急剧下降。 本章只对文本聚类进行简单的介绍。 1 3 1 文本聚类的一些基本概念 文本聚类的一般定义为： 设d = u d ，代表一个文本数据集，c ，代表d 的一个子集，那么文本聚类 f = i ，n 的任务就是将d 分割成k 个子集，并使其满足： d = u c ，且巳n c ，：= 妒 ( 卜1 9 ) j = tk 这个条件容易满足，但是文本聚类更重要的是要使聚类中的文本在语义上尽 可能相似，而与其他聚类中的文本在语义上尽可能“相隔”较远或者不同。 文本聚类过程与文本分类不同，没有训练步骤，故比较简单，如图卜3 所示。 它首先将原始的文本数据表示成文本向量，然后采用聚类算法进行聚类，最终得 到多个文本簇。 ! ：! ：! 兰兰坐! ! 鲞塑墨鲞! 塑塑型垄堑塑塑 1 3 2 常用的文本聚类算法 图卜3 文本聚类的过程 二十世纪六十年代开始的聚类算法研究直到九十年代才吲起广泛的关注，到 目前为【e 仍然是一个热点问题。总体上聚类算法可以分为划分聚类算法、层次聚 类算法、基于密度的聚类算法、基于网格的聚类算法、基于模型的聚类算法以及 其他算法等几个类，每一个类中都有些代表性的聚类算法【1 1 。 划分粲类算法 给定个具有n 个对象的数据集，划分聚类算法就是构建这些数据的k 个 划分，每一个划分代表一个聚类或者簇，并且k n ；聚类算法存执行时，会首 先创建一个初始划分，然后采用一种迭代的重定位技术，通过将对象在不同划分 间的移动来改进划分，直到局部最优。其中最具代表性的算法就是k m e a n s ，1 9 6 7 年被提出。此外还有e m 、k - m e d o i d 、p a m 、c l a r a c l a r a n s 等。 层次聚类算法 层次聚类算法将数据对象组成一棵聚类的树。根据层次的分解是自底向上还 是白顶向下形成，层次聚类算法又进一步分为凝聚的和分裂的层次聚类算法。在 凝聚的层次聚类算法中，开始时每一个对象都作为单独的一个组，然后相继地合 并最相近的两个组直到只剩下一个组或者达到个终【e 条件。分裂的层次聚类算 法与凝聚的层次聚类算法刚好相反，它丌始时将所有的对象都放在一个组中，然 后在每一步中，将一个组分裂为两个更小的组，直到所有的对象都各自成组。层 次聚类有一个更大的缺点在于其不可逆性，也就是说一旦一次合并或者分裂完 成，就升i 能被撤销。 层次聚类算法主要包括s i n g l e l i n k 、c o m p l e t e l i n k 、d i a n a 、a g e n s 、 中文文本分类和聚娄中的特征选择研究 b i r c h 、c u r e 、r o c k 、c h a m e l e o n 等。 基于密度的聚类算法 基于密度的算法最大的优点就在于能够发现任意形状的簇，之所以具有这样 的优点是因为它将簇看成是数据空间中被低密度区域分割开的高密度对象区域。 这类算法在聚类中采用如下策略：只要临近区域的密度( 对象的数目) 超过某个闽 值，就继续聚类。最具有代表性的算法是d b s c a n ，此外还有o p t i c s 和 d e n c i ，ij e 。 基于网格的聚类算法 基于网格的聚类算法把对象空间量化为有限数目的单元，形成了一个网络结 构。所有的聚类操作都在这个网格空间上进行。这类算法的优点是处理速度非常 快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。 典型例子是s t i n g 算法。c l i q u e 和w a v e c l u s t e r 这两种算法既是基于网格的， 又是基于密度的聚类算法。 基于模型的聚类算法 基于模型的聚类算法为每一个簇假定了一个模型，然后寻找数据与给定模型 的最佳拟合。这类算法主要分为两类：统计学方法和神经网络方法。 上述这些算法基本上都是不针对文本数据而提出的，但是它们其中一些己经 被广泛应用于文本聚类，主要包括k m e a n s ，s i n g l e l i n k 和d b s c a n ，这三个 算法同时也是划分聚类算法、层次聚类算法和基于密度的聚类算法的典型代表。 k m e a n s ，s i n g l e l i n k 和d b s c a n 都有一个共同的特征就是建立在距离或者说相 似度计算的基础之上，但是文本数据因为其高维稀疏、近义词和多义词等属性使 得文本数据之间的距离在任何一种距离计算方式下都不准确，所以这些算法在某 些情况下会产生不理想的聚类结果，比如s i n g l e l i n k 可能产生链式聚类结果， d b s c a n 可能产生一个大类加上许多只包含一个文本的小类的结果。为此，也 有很多不基于距离的聚类算法被提出并应用于文本聚类。比如有作者提出了使用 关联规则和主要成分的方法来建立文本数据之间的连线图 2 ”，然后使用图的分 割理论来产生聚类的算法，还有提出了名为“s u f f i x t r e e c l u s t e r i n g ( s t c ) ”的文 本聚类方法 2 ”，这个方法通过寻找多个文本之间的共有词组来创建文本簇等等。 下面简单介绍一下论文中用到的k m e a n s 算法。 k - m e a n s 是最早和最典型的划分聚类算法，己经广泛地应用于文本聚类。 k m e a n s 的聚类过程很简单，首先随机地选择k 个对象，每个对象初始地代 表了一个簇的平均值或者说中心。对剩余的每个对象，根据其与各个簇中心的距 中文文本分类剐聚类中的特征选择研究 离，将它赋给离它最近的簇。然后重新计算每一个簇的中心。这个过平旱不断重复 直到准则函数收敛。通常准则函数采用平方误差，如公式( 1 _ 2 0 ) 所示： e = i 其中e 是所有对象平方误差的总和，p 是一个对象，m ，是簇c ，的中心，此