（计算机软件与理论专业论文）中文文本分类特征选择方法研究.pdf

摘要 中文文本分类特征选择方法研究 计算机软件与理论专业硕士研究生王小青 指导教师陈宏刚教授 摘要 随着科技的发展和网络的普及，人们可获得的数据量越来越多，这些数据多数是以 文本形式存在的。而这些文本数据大多是比较繁杂的，这就导致了数据量大但信息却比 较匮乏的状况。如何从这些繁杂的文本数据中获得有用的信息越来越受到人们的关注。 “在文本文档中发现有意义或有用的模式的过程 n 1 的文本挖掘技术为解决这一问题提 供了一个有效的途径。而文本分类技术是文本挖掘技术的一个重要分支，是有效处理和 组织错综复杂的文本数据的关键技术，能够有效的帮助人们组织和分流信息。文本分类 的两个重要的研究方向是：特征选择与文本分类算法。 特征选择是指从高维的文本特征空间中选择出最能代表文本内容的特征，好的特征 选择方法一方面能够降低文本特征空间的维数，以利于提高文本分类的效率，另一方面 好的特征选择方法通过去除对文本分类无效的特征也有利于提高文本分类的分类精度。 而好的文本分类方法则能够直接有效地提高文本分类的效果。 文本分类的一个重要环节就是对高维的特征空间进行压缩，以选择出最能代表文本 内容的特征词。特征选择方法的好坏直接影响文本分类的效果。本文通过对目前常用的 特征选择方法进行分析比较发现，目前大多数常用的特征选择方法都是通过对特征词条 重要程度的某个方面进行度量来决定是否选择该特征词条，缺乏对特征词条重要程度的 综合度量。鉴于上述缺陷，本文提出了一种新的特征选择方法，从特征词条在文档中出 现的次数、特征词条的文档频数、类别区分能力、类内分散偏差、位置重要性等几个方 面来综合度量特征词条的重要性，作为特征选择的依据。 为了为本文实验搭建实验平台，本文的另一个工作是构造一个中文文本分类系统， 该系统由分词模块、特征选择模块、文本分类模块组成。三个模块之间相互独立且具有 统一的接口，对其中任何一个模块的更改对其他模块都不会产生影响，同时由于具有统 西南大学硕士学位论文 一的接口，所以模块之间的调用也十分的方便。 为了验证本文所提特征选择方法的有效性和可行性，本文在中文文本分类系统上将 本文所提的特征选择方法与文档频特征选择方法以及r 统计量特征选择方法进行了对 比实验。通过对文本分类混淆矩阵、类别查全率、查准率、f l 值以及总体查全率、查准 率、f 1 值的对比分析，本文得到如下结论：即无论是混淆矩阵中正确分类的文档总数， 还是类别查全率、查准率、f 1 值还是总体查全率、查准率、f 1 值，本文所提特征选择 方法相对于文档频特征选择方法以及工统计量特征选择方法都有所提高，而实验过程中 除了特征选择方法的不同外其它条件包括实验语料库、分词方法、分类算法、各种参数 等都相同，从而证明了本文所提特征选择方法的有效性和可行性。 关键词：文本分类特征选择中文文本分类系统 i l a b s t r a c t a b s t r a c t w i mt h ed e v e l o p m e n to ft e c h n o l o g ya n dn e t w o r k sp e n e t r a t i o n , m o r ea n dm o r ed a t ai s a v a i l a b l et op e o p l ea n dm o s to ft h e s ed a t ai si nt h ef o r mo ft e x t t h e s eu n s t r u c t u r e df o r mo f d a t al e a d st oas t a t u sw i t hl a r g ev o l u m eo fd a t ab u t 谢t hr e l a t i v e l yr a r ei n f o r m a t i o n h o wt o o b t a i nu s e f u ii n f o r m a t i o nf r o mt h e s ed a t aw i t hu n s t r u c t u r e df o r mh a sb e c o m i n ga l lc o n c e r n e d i s s u ei n c r e a s i n g l y t e x tm i n i n gt e c h n o l o g yw h i c hm e a n sf i n dm e a n i n g f u lp a t t e r no ru s e f u l p r o c e s si nt h et e x th a sp r o v i d e sa l le f f e c t i v ew a y t os o l v et h i sp r o b l e m t e x tc l a s s i f i c a t i o n t e c h n o l o g yi sab r a n c ho ft e x tm i n i n gt e c h n o l o g y , w h i c hm e a n si ti so n ek e yt e c h n o l o g yo f m a n a g e m e n t i n ga n do r g a n i z i n gc o m p l e xt e x td a t ae f f e c t i v e l y t e x tm i n i n gc a l lh e l pp e o p l e o r g a n i z ea n ds t r e a mi n f o r m a t i o ne f f e c t i v e l y t w oi m p o r t a n tr e s e a r c hd i r e c t i o n so ft e x t c l a s s i f i c a t i o na r e ：f e a t u r es e l e c t i o nm e t h o da n dt e x tc l a s s i f i c a t i o na l g o r i t h m f e a t u r es e l e c t i o nm e a l 魑t os e l e c tt h ef e a t u r et e r m sw h i c hc a l lb e s t r e p r e s e n tt h e c h a r a c t e r i s t i c so ft e x tf r o mh i 曲一d i m e n s i o n a lf e a t u r et e r ms p a c e g o o df e a t u r es e l e c t i o n m e t h o do no n eh a n dc a l lr e d u c et h ed i m e n s i o no ft h et e x tf e a t u r es p a c e ，r e s u l t i n gi nt h e i m p r o v e m e n to ft e x tc l a s s i f i c a t i o ne f f i c i e n t l y , o nt h eo t h e rh a n dg o o df e a t u r es e l e c t i o nm e t h o d c a ni m p r o v et h ea c c u r a c yo ft e x tc l a s s i f i c a t i o nt h r o u g hr e m o v i n gi n v a l i df e a t u r et e r m s g o o d t e x tc l a s s i f i c a t i o nm e t h o di sa b l et oi m p r o v et e x tc l a s s i f i c a t i o nr e s u l td i r e c t l y o n ei m p o r t a n ta s p e c to ft e x tc l a s s i f i c a t i o ni st oc o m p r e s st h eh i g h - d i m e n s i o n a lf e a t u r e t e r m ss p a c e ，t os e l e c tt h ef e a t u r et e r m sw h i c hc a l lm o s tr e p r e s e n tt h et e x tc o n t e n t t e x tf e a t u r e s e l e c t i o nm e t h o dc a na f f e c tt h ee f f e c to ft e x tc l a s s i f i c a t i o nd i r e c t l y t h r o u g ht h ea n a l y s i so f c u r r e n tc o m m o n l yu s e df e a t u r es e l e c t i o nm e t h o d sw ef i n dt h a t ，a tp r e s e n tm o s to ft h e c o m m o n l yu s e df e a t u r es e l e c t i o nm e t h o d sa r eb a s e do no n eo rt w oi m p o r t a n ta s p e c t so f f e a t u r et e r mt od e c i d ew h e t h e rt os e l e c tt h i sf e a t u r et e r n l ，l a c k i n gac o m p r e h e n s i v em e a s u r eo f f e a t u r et e r m i nt h i sp a p e r , w ep u tf o r w a r dan e wf e a t u r es e l e c t i o nm e t h o dw i t ha c o m p r e h e n s i v ea s s e m b l yo ft e r m si m p o r t a n c ea s p e c t sf r o ma p p e a r a n c en u m b e ro ft e r mi n d o c u m e n t ，d o c u m e n tf r e q u e n c yo ft e r m s ，a b i l i t yo fd i s t i n g u i s h i n gc a t e g o r i e s ，d e v i a t i o no f w i t h i n - c l a s ss p r e a d ，i m p o r t a n c eo ft h ep o s i t i o n , e n t r o p yo fi n f o r m a t i o no ft e r mi nt h ev i e wo f a b o v es h o r t c o m i n g i no r d e rt ob u i l dt h ee x p e r i m e n t a lp l a t f o r mf o re x p e r i m e n t ，t h i sp a p e r sa n o t h e rw o r ki st o c o n s t r u c to n ec h i n e s et e x tc l a s s i f i c a t i o ns y s t e m t b j sc h i n e s et e x tc l a s s i f i c a t i o ns y s t e m c o n s i s t so fc h i n e s et e r ms e g m e n t a t i o n m o d u l e ，f e a t u r es e l e c t i o nm o d u l ea n dt e x t c l a s s i f i c a t i o nm o d u l e t h e s em o d u l e sa r ei n d e p e n d e n ta m o n ge a c ho t h e rb u tw i t hau n i f i e d i n t e r f a c ew h i c hm e a n st h ec h a n g e so fo n em o d u l ew i l ln o ti m p a c to t h e rt w om o d u l e sa n dt h e c a l l sa m o n gm o d u l e sa r ev e r yc o n v e n i e n t i no r d e rt ov a l i d a t et h a tt h ep r o p o s e df e a t u r es e l e c t i o nm e t h o do ft h i sp a p e ri se f f e c t i v e a n df e a s i b l e ，w ed oc o m p a r a t i v ee x p e r i m e n t sa m o n gt h e t h ef e a t u r es e l e c t i o nm e t h o dw h i c hi s i l l 两南大学硕士学位论文 p u tf o r w a r db yt h i sp a p e ra n dd o c u m e n tf r e q u e n c y f e a t u r es e l e c t i o nm e t h o da n dc h if e a t u r e s e l e c t i o nm e t h o db a s e do nt h ec h i n e s et e x tc l a s s i f i c a t i o ns y s t e m w eg e tt h ef o l l o w i n g c o n c l u s i o nt h a t 也et o t a ln u m b e ro fc o r r e c tc l a s s i f i e dd o c u m e n t sg e t t i n gf r o mc o n f u s i o n m a t r i x ，t h er e ：c a l lr a t e t h ep r e c i s i o nr a t ea n dt h ev a l u eo ff 1o fe a c hc a t e g o r ya n dt h eo v e r a l l c a t e g o r yw h i c hu s i n gt h i sp a p e r sf e a t u r es e l e c t i o nm e t h o da l lh a v eg o ti n c r e a s e dt os o m e d e g r e ec o m p r i s i n gu s i n gd o e a m e n tf r e q u e n c yf e a t u r es e l e c t i o nm e t h o da n dc h if e a t u r e s e l e c t i o nm e t h o d i nt h e p r o c e s so fc o m p a r a t i v ee x p e r i m e n t st h ec h i n e s et e x tt e r m s e g m e n t a t i o nm e t h o d , t h ec l a s s i f i c a t i o na l g o r i t h ma n dt h ev a r i o u sp a r a m e t e r sa lea l lt h es a m e e x c e p tf e a t u r es e l e c t i o nm e t h o d , t h u sp r o v e st h a tt h ep r o p o s e df e a t u r es e l e c t i o nm e t h o do ft h i s p a p o ri se f f c c t i v ea n df e a s i b l e k e y w o r d s ：t e x tc l a s s i f i c a t i o n ；f e a t u r es e l e c t i o n ；c h i n e s et e x tc l a s s i f i c a t i o ns y s t e m 独创性声明 本人提交的学位论文是在导师指导下进行的研究工作及取得的研究成 果。论文中引用他人已经发表或出版过的研究成果，文中己加了标注。 学位论文作者：王t 1i 每签字目期：2 秒p 年罗月汐日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅和借阅。本人授权西南大学研究生部可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：曰不保密，口保 密期限至年月止) 。 学位论文作者签名：至 南导师签名： c ( 2 1 ) g 把一个待分类的文本映射到一个预定义的类别中。对d 中的文档d 来说，g ( d ) 是已知的。这样通 过对文本分类训练文本集的有指导的学习就可以得到一个近似于g 的分类模型m ，m 表示为： m ：d 一 c( 2 2 ) 有了分类模型m 之后，对于待分类文本磊，其分类结果就可以用m ( 么) 来表示。文本分类系统的搭 建或者文本分类的学习目的就是要找到一个和g 最相似的分类模型m 。用公式表示为： m i 刀( 芝= 厂( g ( 西) 一m ( 西) ) ) ( 2 3 ) 其中i d l 表示待分类文本集的大小，为判断g 和m 是否相似的评估函数。 需要说明的是，待分类文本到预定义主题类别的映射可以是一对一的映射，即待分类文本只属 于一个类别；待分类文本到预定义主题类别的映射也可以是一对二的映射，例如对垃圾邮件的判定 就是一个一对二的分类映射；待分类文本到预定义主题类别的映射还可以是一对多的映射，即多类 映射，通常情况下一般将多类映射问题转化为一对二映射问题进行研究。 2 2 文本分类流程 6 第3 章特征选择方法研究 文本分类主要由两个阶段组成：第一阶段为分类器的训练阶段，主要工作是利用训练样本集对 分类器进行训练，同时对分类器的分类效果进行评估，从而对分类器进行调整，以期得到具有最佳 分类效果的分类器；第二阶段为分类阶段，即利用第一阶段得到的分类器对待分类文本集中的文本 进行分类处理。文本分类流程如图2 - 1 所示。 2 3 文本预处理技术 图2 - 1 文本分类流程 f i g u r e2 - 1p r o c e s so ft e x tc i a s s i f i c a t i 0 1 1 训练阶段 分类阶段 文本预处理技术主要包括以下几个方面： ( 1 ) 文本标记的处理 一般情况下，文本中除了表示文本内容的信息外，一般还会包括一些与内容无关的标记，如控 制文本显示外观的标记、标点符号、图像、声音、动画等其它媒体信息，甚至有可能是乱码。这些 标记具有如下特点：即它们与文本内容无关，对文本的分类没有帮助。由于中文文本分类处理对象 是纯文本信息，所以说这些标记都是中文文本分类中的噪声数据，在对待文本进行分类处理之前需 要对待分类文本进行预处理，去除这些对分类没有贡献的标记。 ( 2 ) 分词处理 由于中文文本的词与词之间不像英文的单词与单词之间具有一个形式化的分界符，所以在对中 文文本进行分类处理之前需要对待分类的文本进行分词处理。中文文本的分词处理技术就是将连续 的汉字序列按照一定的规则重新切分为词或词组的过程。由于汉语句子具有复杂性和多样性的特点， 7 西南大学硕士学位论文 使得中文分词处理成为中文文本分类的一大难题。目前，常用的分词算法主要有以下三类5 儿嘲： 基于词典匹配的分词方法 基于词典匹配的分词方法又称为机械性分词方法，其主要思想是：将待分词的中文字符串按照 某种策略与词典中的词条进行匹配，如果在词典中找到了某个字符串，则表示识别出了一个词， 匹配成功；按照对待分词字符串扫描方向的不同，基于词典匹配的分词方法可分为正向匹配、 逆向匹配以及双向匹配。按照不同长度优先匹配情况，基于词典匹配的分词方法又可分为最大 匹配、最小匹配；基于词典匹配的分词方法分词算法简单、分词效率也较高，但是它具有完全 依靠分词词典的缺点。由于汉语语法复杂，导致分词词典具有不完备、规则不一致的问题，这 也使得完全依靠分词词典的基于词典匹配的分词方法无法胜任大规模文本分词处理任务。目前 常用的基于词典匹配的分词方法主要有：正向最大匹配、逆向最大匹配、最少切分、全切分等。 基于统计的分词方法 从形式上看，词是稳定的字的组合，在上下文中，相邻的字同时出现的次数越多，就越有可能 构成一个词n 7 1 。也就是说字与字相邻出现的概率可以作为判断相邻字能否组成一个词的依据。 基于统计的分词方法就是对待分词字符串中的各个字的组合频率进行统计。把各个字的组合频 率作为判断其能否构成一个词的依据。当字与字之间的组合频率高于某个阈值时，便认为此字 组可以构成一个词，否则则认为此字组不能组合成一个词。从基于统计的分词方法的分词依据 我们可以看出该分词方法并不需要分词词典，完全依靠对待分词字符串序列进行字组频率统计 来进行分词处理，所以该分词方法又称为无词典分词方法。基于统计的分词方法具有经常识别 出共项频率高但并不是有意义词的缺点，由于汉语语法的复杂性，基于统计的分词方法的分词 精准度较低，且时空开销比较大。在实际应用中，通常的做法是将基于词典匹配的分词方法和 基于统计的分词方法相结合，即在利用一部基本的分词词典进行串匹配操作的同时使用基于统 计的分词方法来识别出一些新的词。将串匹配分词与串频统计的方法相结合，在发挥串匹配分 词切分速度快、效率高优点的同时，又发挥了串频统计分词方法识别新词、自动消除歧义的优 点。 基于理解的分词方法 基于理解的分词方法主要是通过让计算机模拟人类对自然语句的理解，来达到分词的目的。基 于理解的分词方法的基本思想是：在对待分词字符串序列进行分词的同时，对该字符串序列进 行句法、语义的分析，通过对句法和语义进行分析来处理歧义现象。基于理解的分词方法通常 由三个部分组成：一是分词子系统，二是句法语义分析子系统，三是总控系统。其一般的处理 8 第3 章特征选择方法研究 流程是：首先总控系统控制协调整个分词操作，句法语义分析子系统对待分词字符串序列进行 句法和语义的分析，在此基础上分词子系统对待分词字符串序列进行分词以及歧义处理操作。 从上面的处理流程可以看出，基于理解的分词方法模拟了人类对自然语言的处理，它需要使用 大量的语言知识和信息。由于汉语语言知识的复杂性，目前还难以将各个汉语语言知识和信息 组织成计算机可以直接理解的形式，因此目前基于理解的分词方法还处于试验阶段，仍存在大 量值得研究的地方。 ( 3 ) 去除停用词 一般情况下我们通过名词、动词和形容词等实词来体现文本的内容，两虚词以及在文本中经常 出现但并不表示文本内容的词称为停用词( s t o p w o r d ) 。由于这些停用词并不表示文本的实际意义， 所以它们对文本分类没有任何贡献，相反它们反而会增加分类算法处理文本的时空复杂度。所以为 了降低存储空间，提高文本分类算法的分类效率和分类精度，我们需要对文本进行去除停用词的处 理。通常情况下对文本进行去除停用词的处理是通过构造停用词表来实现的，即将分词所得到的文 本初始特征词集中的每个词与停用词表中的词进行匹配，如果该词在停用词表中出现，则表示该词 为停用词，应该去除，否则，保留该特征。由于对文本去除停用词的处理依赖于停用词表，所以停 用词表的完备性和科学性对去除停用词的处理结果有较大的影响。 2 4 文本表示模型 由于文本数据的无结构化特性，使得在对其进行分类处理之前必须把它转化为计算机分类算法 易于处理的形式，即对文本数据进行形式化的表示。目前，常用的文本形式化表示方法主要有：向 量空间模型( v e c t o rs p a c em o d a l ) 、布尔模型( b o o l e a nm o d e l ) 、概率模型( p r o b a b i l i s t i cm o d e l ) 等。 2 4 1 向量空间模型 向量空间模型“舯( v e c t o rs p a c em o d a l ，简称v s m ) 是由g s a l t o n 教授等人在2 0 世纪6 0 年代 提出的文本表示模型，它具有文本形式化表示效果好、应用广泛的特点。v s m 模型最早应用于信息 捡索领域，后来随着文本分类技术的发展，v s m 模型又在文本分类领域得到了广泛的应用。v 蹦模型 用向量的形式表示文本，是信息检索领域经典的文本表示模型。 向量空间模型的基本思想是：以特征向量的形式表示文本，两个文本之间的相似度通过文本特 征向量之间的相关度来计算。向量空间模型中，文本d 表示为由特征词条和特征词条的权重所组成 9 西南大学硕士学位论文 的向量，形式m y ( ( f ，w o ( t 2 ，w 2 ) 似，慨) ) ，其中f f 表示特征词条，w 坝u 表示特征词条t i 的权重。 而两个文本的相似度就通过两个文本向量之间的相关度来度量。目前，常用的计算文本特征向量相 关度的方法主要有：基于向量内积的方法和基于向量夹角的方法。 v s m 模型的优点是：通过把文本相似度的计算转化为两个向量相关度的计算，通过计算两个向 量的夹角或内积来度量两个文本的相似度，降低了文本相似度计算的复杂度；v s m 模型对特征项的 权重以及相似度的计算并没有作严格的规定，可以根据实际情况选择不同的权重评估函数和相似度 计算方法，这使得向量空间模型的应用非常的广泛。 v s m 模型的缺点是：认为文本的内容与特征项的位置以及顺序等信息没有关系，这使得向量空 间模型损失了大量的有关文本结构和语义等的重要信息。 2 4 2 布尔模型 布尔模型n 刚( b o o l e a nm o d e l ) 是基于特征项的严格匹配模型。其基本思想是：通过建立对应于文 本特征项的二值特征变量集合，把文本用这些特征变量来表示，如果文本中包含相应的特征项，则 该特征变量取值为。t r u e ”，否则特征变量取值为“f a l s e 。在具体应用中，通常用特征变量数值“l ” 表示文本中包含该特征项，用特征变量数值“0 ”表示文本中不包含该特征项。相应的，在布尔模型 中，用户的查询也表示为布尔表达式，检索时，根据用户提交的检索条件是否和文本中的逻辑关系 一致将检索文本分为相关文本集和不相关文本集。 布尔模型具有结构简单，检索速度快的优点。但是由于布尔模型使用的是基于二元判定标准 ( b i n a r yd e c i s i o nc r i t e r i o n ) 的匹配策略，对于文本检索，只有相关和不相关两种状态，缺乏对 文本相关性排序( r a n k i n g ) 的概念，从而限制了检索功能。其次，在实际应用中，将用户的查询转 换为布尔表达式并不是一件容易的事情。 2 4 3 概率模型 概率模型是基于概率排队原则的文本表示模型。概率排队原则的基本思想是：当文本按概率降 序的原则进行排列时可以获得最好的检索性能。对于用户给定的查询，概率模型计算所有文档的概 率，然后依照文档概率的大小对文本进行降序排列。概率模型是利用词条与词条以及词条与文档之 间的概念相关性来进行信息检索的文本表示模型，它克服了v s m 模型和布尔模型忽略词条相关性的 缺点。 概率模型中，用特征向量喀= ( 。，w 2 ，) 表示文本d ，特征向量吼= ( 。，k 2 ，) 表示用 1 0 第3 章特征选择方法研究 曼笪曼曼曼曼曼曼曼曼曼曼曼皇皇曼曼曼曼曼量曼曼量曼曼曼曼曼曼鼍曼曼曼i i i 一 一一l l i l 曼曼皇 户查询串q ，其中向量西，孕的权重计算都采用二值计算方法，即嘞 0 ，1 ) ， o ，1 ) ，1 表示特 征项出现，0 表示特征项不出现。文本d 与用户查询串q 的概念相关性计算公式如下所示： p ( 咖) = l o g 黜 ( 2 4 ) 其中a = ，；r ，吼= ( z - r ，) ( f - r ) 。f 为训练文档集中的文档总数，r 为文档集中与用户查询相 关的文档数，z 表示训练文档集中包含特征现的文档数，；表示r 个相关文档中包含特征项的 文档数。 概率模型按照相关概率的降序排列规则对文本进行处理，综合考虑了文本集的整体情况。但是 概率模型只采用了二值形式，对向量权重的计算较为简单。 2 5 特征选择技术 中文文本经过分词处理后，所得的词条数量非常大，即使经过去除停用词等处理仍然会有大量 的词条留下。这就造成了当用向量空闻模型表示文本时，向量空闻的维数通常高达上万维甚至几十 万维的状况。这样的高维特征向量空间一方面加大了分类算法学习的时间，降低了分类效率，另一 方面，由于很多与文本内容无关且对提高分类效果没有贡献的噪声数据的存在，导致了分类精度的 降低。所以说十分有必要对特征向量空间进行降维处理，而特征选择是目前最常用的特征向量空间 降维技术。 特征选择通过选择出能够很好代表文本内容的特征词条，以降低文本向量空间的维数，提高文 本分类的分类效率和分类精度。本文将在第3 章中对特征选择技术进行详细阐述。 2 6 文本分类方法 文本分类( t e x tc l a s s i f i c a t i o n 或t e x tc a t e g o r i z a t i o n ) 就是将待分类的文本按照其主题划 分到预先定义好的一个或若干个类别中。文本分类方法是文本分类技术研究的重点，也是设计文本 分类器的理论基础。根据分类规则的不同以及类别判断方法的不同，文本分类方法大体上可以分为 以下两类： ( 1 ) 基于规则的分类方法 基于规则的分类方法的基本原理是：由推理机根据领域专家系统知识推导分类。由此可以看出， 该分类方法的基础和前提是领域专家知识，需要在领域专家编制大量推理规则的前提下才能进行有 西南大学硕士学位论文 效的分类操作。基于规则的分类方法具有分类正确率高、分类体系合理的优点。但是由于其分类的 效果严重依赖推理规则，开发、管理、扩展费用高且领域性强，不易移植，所以在实际分类系统的 设计中很少使用这种分类方法。 ( 2 ) 基于统计的分类方法心1 基于统计的分类方法的基本原理是：将文本看作是互不相关的特征词集合，忽略文本的语义结 构信息，通过对训练样本的统计和计算，得到可以代表文本和类别的关键特征词条。分类器以所选 择的特征形式化待分类的文本，然后分类器根据训练阶段所得到的文本与类别的关系来判定待分类 文本的类别。基于统计的分类方法实现简单，同时由于其分类知识是通过对训练语料库分析得到的， 分类依据可信度高，所以该分类方法还具有分类准确度高的优点。但是由于基于统计的分类方法实 质上是非确定性的定量推理过程，所以存在对小类别文本忽视的缺点。 下面将详细介绍几种常用的文本分类方法。 2 6 1n a v ieb a y e s 方法 n a v i eb a y e s 1 是一种以贝叶斯定理为理论基础的统计学的分类方法，是一种在已知先验概率和 条件概率的情况下求后验概率的模式识别方法。n a v i eb a y e s 分类方法是一种简单有效的分类方法。 n a v i eb a y e s 分类方法的基本思想是：在已知先验概率和条件概率的情况下，计算待分类文本 属于各个类别的后验概率，然后将待分类文本分到后验概率最大的类别中。其中文本属于某个类别 的概率为文本中各个特征词属于该类别概率的综合表达式。n a v i eb a y e s 的一个前提假设是：文本 的特征词之间是相互独立的，即文本的一个特征词对分类的影响独立于其他特征词对分类的影响。 n a v i eb a y e s 分类方法中，西= ( 坳，m 忽9 0 0 * s 愀) 表示任一待分类的文本，表示待分类文本中的特征 词条，c = c l ，乞，& ) 为预定义的文档类别，n a b i eb a y e s 的分类方法有如下定义： ( 1 ) 特征词条条件独立性假设： ( 2 ) 文本哦属于类别勺的概率： 1 2 p ( 芬i c j ) = 兀p ( l 勺) k = l p ( 州) = 掣 ( 2 5 ) ( 2 6 ) 第3 章特征选择方法研究 各项的计算方法如下： p c 臼，= ! 警2 端丁孑t 精 2 7 ) p h ，= 磊蒜鬻筹器器丽蒜 q 8 ) p ，lc ，卜石习两而鬲支百百爵豇丽而丽幂丽雨矛两再瓦 ”一7 由于n a v i eb a y e s 分类方法是在特征独立性假设的前提下进行文本分类操作的，该假设会影响 n a v i eb a y e s 的分类结果。 2 6 2k n n 方法 k n n 叫( kn e a r e a tn e i g h b o r s ，简称k n n ) 分类算法是一种传统的基于统计的分类方法。k n n 分 类算法的基本思想为：在训练样本集中找到与待分类文本最近的k 个文本，看这k 个近邻文本中多 数属于哪一类。就把待分类文本分到哪一类。k n n 是一种简单高效的文本分类方法，其分类基本步 骤如下： ( 1 ) 根据特征项集合扫描 j l l 练文本向量： ( 2 ) 对待分类文本进行向量表示： ( 3 ) 在训练文本集合中找到与待分类文本最近的k 个近邻，近邻的判别标准一般采用文档向量余弦 相似度方法来计算。k 值的确定目前还没有好的方法，一般是先设定一个初始值，然后根据实 验具体情况再对k 值进行调整。 ( 4 ) 依次计算待分类文本的k 的近邻文本相对于各个类的权重，计算方法如下： 形( o ) = s i m ( d ，西沙( 赢，o ) ( 2 9 ) 其中，d 表示待分类文本。西表示d 的k 近邻文本，y ( 西。o ) 为文档类别判定函数，如果文档 西属于类别o 则y ( 西。o ) 取值为1 ，否则为0 。s i m ( d ，西) 为待分类文本与k 近邻文本的相似 度，一般采用文档向量余弦相似度计算方法： d h ： c o s ( d ，哆) 2 丽南 2 1 0 ( 5 ) 根据各个类的权重计算结果，将待分类文本划分到权重最大的类别中。 k n n 分类方法具有分类方法简单、易于实现、分类出错率低的优点。但是由于需要较大的空间 来存储训练样本集，而且对于每个待分类的文本。都要计算其与训练样本集中各个文本的相似度， 1 3 西南大学硕士学位论文 分类开销较大，因此该分类方法并不适用于大规模的数据集，相反在小规模数据集上该分类方法能 够取得较好的分类效果。 通过对k n n 算法的研究，我发现z n n 算法的效率很大程度上依赖于k 值的选取，于是我提出了 基于并行遗传算法的k n n 分类方法，该方法采用粗粒度模型的并行遗传算法进行设计，通过种群内 的遗传、变异和种群间的并行进化、联姻得到优化的k 值和分类结果。详细内容在我攻读硕士期间 发表的论文中有详细的说明。 2 6 3 类中心向量方法 类中心向量方法幢钔是一种基于向量空间模型的简单分类方法。类中心向量分类方法的基本思想 是：在分类器的训练阶段，利用训练样本集获得每个类所对应的中心向量。然后在分类阶段，将待 分类的文本也用向量表示，计算待分类文本向量与训练阶段所获得的每个类的中心向量的相似度， 然后将待分类文本划分到相似度最大的类别中去。如果希望待分类文本可以属于多个类别，则可以 按照相似度降序的方法对类别进行排序，然后设定一个相似度阈值，将待分类文本划分到相似度大 于等于相似度阈值的类别中去。目前，常用的类中心向量分类方法主要有：r o c c h i o 方法、 w i n d r o w - h o f f 方法、e g 方法等。 类中心向量分类方法具有分类方法简单易行、分类速度快的优点。 2 6 4 神经网络方法 神经网络饰儿州嘲( a r t i f i c i a ln e u r a ln e t w o r k s ，简称n n ) 分类方法通过模拟人脑神经网络的基 本组织特性来完成文本的分类操作。神经网络分类系统通常为三层组织结构，即输入层、输出层和 至少一个隐层，其中输入层神经元的个数代表样本的特征数，输出层神经元的个数代表样本类别数。 神经网络实际上是由多个输入、输出连接组成的，其中每个输入、输出连接都有一定的权重。神经 网络分类方法的基本思想为：训练阶段，利用训练样本集对神经网络分类系统中的每一个输入、输 出连接的权重进行调整，以期得到具有最佳分类效果的神经网络分类器；分类阶段，当一个新的待 分类文本到来时，利用训练阶段所得到的分类器将待分类文本从神经网络输入层传输到一个合适的 神经网络输出层，完成待分类文本的类别判定工作。 目前，常用的神经网络模型主要有：多层感知机、自适应映射网络等。神经网络分类方法具有 自适应性强、鲁棒性以及容错性高的优点。但是由于神经网络分类方法采用“黑盒”策略，缺乏解 释能力，且其分类效果在很大程度上依赖于训练样本集，分类训练过程慢，所以并不适用于大规模 1 4 第3 章特征选择方法研究 训练语料库的训练学习啪1 。 2 6 5 支持向量机方法 支持向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 最早是由v a p n i k 在1 9 9 5 年提出，并在2 0 世纪9 0 年代中后期得以发展和完善。支持向量机主要是根据统计学理论解决二分类模式识别问题啪1 。 j o a c h i m s 最早将s v m 方法应用于文本分类。在文本分类问题中，s v m 将分类问题转化为一系列二 分问题。 s 的目的是找到一个可以将训练样本集中的文本分为两类的超平面，以满足类别边界沿垂直 于该超平面方向的距离最大，保证最小的分类错误率。用( 薯，咒) 表示线性可分样本集，其中而欠d ， 咒为类别标识，y i c - 1 ，+ b ，r d 为d 维欧式空间。用方程g ( 力= 国石+ 6 表示n 维空问线性判别 函数，纵+ b = 0 表示分类平面，经过对判别函数进行归一化处理，使得两类中的所有样本满足条 件l g ( 功1 1 ，则两个类别之间的间隔为2 l l 缈l | 。这样为了满足类别边界沿垂直于超平面方向距离 最大的条件，只需要使i i 国l i 取值最小即可。为了使分类超平面能够对所有样本正确分类，只需满足 条件： y f 【( 国薯) + 6 一l o ，f = 1 ，n ( 2 1 1 ) 则| l 国i l 取值最小且满足上述条件的分类面就是所要求的最优分类面h 。可以将求解最优分类面的问 题看作约束优化问题进行求解，使用l a g r a n g e 乘数法求解的最小值。 上面主要是支持向量机方法在两类分类问题中应用，对于多类分类问题，支持向量机的实现方 法主要有：通过对一系列的两类分类器的组合实现多类分类问题；通过合并多个分类面的参数到一 个最优化问题，然后求解该最优化问题实现多类分类。 由于支持向量机是针对有限样本情况的分类方法，它能够在有限样本情况下得到全局最优解。 同时它对稀疏数据不敏感，能够更好的捕捉数据的内容特征。分类准确率高。其缺点是：难以根据 实际问题选择合适的函数、参数调节比较困难、分类比较耗时。 2 6 6 决策树方法 决策树方法是一种多级分类方法，它通过分级的形式把复杂的多类别分类问题转化为若干个简 单的分类问题。它采用自上而下的递推方法，通过对实例的推导学习得到分类规则。 决策树分类方法的的基本思想是：训练阶段，从根节点开始对训练语料库中的样本进行测试， 1 5 西南大学硕十学位论文 根据测试结果将训练语料库中的样本划分为若干个样本子集，每个样本子集构成决策树的一个子节 点，递归这一过程，直到各个子节点中的训练样本子集都属于同一类或满足终止条件。这样，就得 到了一颗决策树，该决策树由一个根节点，若干个内部节点和若干个终止节点组成。每个终止节点 代表一个类别。然后当一个待分类样本出现时，就利用训练阶段所得到的决策树对该待分类文本进 行分类操作，把他划分到决策树的某一叶子节点，即某一类别中。 决策树分类方法具有抗噪声能力强、分类精度高的优点。其缺点是在处理大规模样本数据集时 分类效率不高。目前，典型的决策树方法主要有c a r t 方法、c 4 5 方法以及i d 3 方法。 2 7 实验评估方法 分类评价指标是指在实验过程中使用的一些用来评价分类器分类准确度的量化指标。对于文本 分类系统，文本分类评价指标的选择是需要考虑的一个关键点。目前已经有很多种分类评估方法被 提出，其中部分评价指标都是从某个角度来对分类器的效果进行评测，即衡量分类器在某个方面的 性能。对于文本分类系统的评估测试，国际上有通用的评价指标，其中最常用的包括查全率( r e c a l l ) 、 差准率( p r e c i s i o n ) 、宏平均、微平均等口“翻，下面将详细介绍。 2 7 1 查全率与查准率 查全率是指在一个类别中，分类