（计算机应用技术专业论文）文本分类算法研究.pdf

奎查坌差墨兰堕茎 一 摘要 w 珊的出现导致网站上的文本成指数级增长，因此如何自动处理这些海量联机 文本成为目前重要的研究课题。自动文本分类是文本信息处理中的一个重要环节。 本文研究文本的自动分类算法。本文对常用的文本分类算法进行了评价，并 且对这些算法在文本分类的应用进行了讨论。文本分类算法是有监督的学习算法， 它需要一个分类好的，类别已标识的文本数据集训练分类器，然后用训练好的分 类器对未标识类别的文本分类。一般分类器的精度随着训练文本的增多而提高， 但人工分类好的文本是一种昂贵的资源，文本分类算法要解决的一个重要问题是 要减少训练集中人工分类的文本数量，同时保证其精度。针对这一问题，本文从 以下两个方面进行了研究。 首先，研究了在训练集较小的条件下提高分类精度的问题。本文在最近特征 线算法的基础上，结合k 近邻算法的思想，提出一种k 最近特征线文本分类算法。 实验结果表明，该算法在训练集较小的情况下，算法可以具有较好的性能。 本文的另一贡献是采用未标识文本来扩充训练集，提出了迭代t f i d f 算法。 网上存在大量文本，这些文本一般都没有类别标签，该算法可以利用大量廉价的 未标识文本，结合很少的手工标识文本，通过迭代训练出较高精度的t f i o f 文本 分类器。实验结果表明，在同等实验条件下，该算法精度高于已有的阴贝叶斯文 本分类算法。迭代t f i d f 算法属于爬山算法，初始值的选取对精度影响较大，算 法容易收敛到局部最优值。 针对迭代t f i d f 算法存在的局部最优问题，本文引入主动学习的概念，提出 了基于主动学习的迭代t f i d f 算法。实验结果表明，主动学习可以有效的抑制算 法收敛到局部最优值，进一步提高了算法精度。 关键词：文本分类，监督学习，e m 算法，t f l d f 算法，k 最近特征线算法 兰查坌鲞整堕蜒壅 一 a b s t r a c t w i t ht h e d e v e l o p m e n to f w w w , t h e n u m b e ro f d o c u m e n t so nt h ei n t e r n e t i n c r e a s e se x p o n e n t i a l l y o n ei m p o r t a n tr e s e a r c hf o c u so nh o w t od e a lw i t ht h e s eg r e a t c a p a c i t yo f o n l i n ed o c u m e n t s a u t o t e x tc l a s s i f i c a t i o ni so n ec r u c i a lp a r to f i n f o r m a t i o nm a n a g e m e n t t h i s 雕rm a i n l yf o c u s o nt h et e x tc l a s s i f i c a t i o na l g o r i t h m s t h ea l g o r i t h m so f t e x tc l a s s i f i c a t i o na r es u p e r v i s e d , w h i c hm e a n st h ec l a s s i f i e rt r a i n i n gn e e ds o m eh u m a n l a b e l e dd a t ao f f i x e d c l a s s e s g e n e r a l l y , t h ea c c u r a c y o f c l a s s i f i e ri sh i g h e rw i t hm o r e l a b e l e dd a t a b u tt h el a b e l e dd a t ab yh a n da r ee x p e n s i v er e s o u r c e o n ev i 攮lp r o b l e m w t ht e x tc l a s s i f i c a t i o ni sh o w t or e d u c et h en u m b e ro f l a b e l e dd a t aw h i l em a i n t a i nt h e p r o p e ra c c u r a c y t h i sp a p e rp a r t l ys o l v e st h i sp r o b l e mf r o mt w o d i f f e r e n ta s p e c t s f i r s t l y , w ew a l l t t od e a lw i t hs p a r s et r a i m n gd a t a b ys e l e c t i n gh i g hp e r f o r m a n c e a l g o r i t h m t h i sp a p e rp r o p o s e s 鑫n o v e lt e x tc l a s s i f i c a t i o na l g o r i t h m ，kn e a r e s t f e a t u r e i i n ea l g o r i t h m 、b a s e do nn e a r e s tf e a t u r el i n ea l g o r i t h mw h i c hi sp r o p o s e d 汹f a c e r e c o g n i t i o n t h ee x p e r i m e n t ss h o w t h a tt h i sa l g o r i t h mc a nd e a lw i t h s p a r s et r a i nd a t a w i t hr a t h e rh i 曲a c c u r a c y f r o ma n o t h e r p o i n t , t h e r ea r e ag r e a tn u m b e ro fu n l a b e l e dd o c u m e n t sa v a i l a b l e o n l i n e t k s p a p e ra p p r o a c h t oan o v e l a l g o r i t h m c a l l e di t e r a t i v et f i d f , w h i c h c o m b i n e sal a r g en u m b e ro fu n l a b e l e dd a t aw i t hs m a l l1 a b e l e dd a t at ot r a i nt h et f i d f c l a s s i f i e r t h ei t e r a t i v et f fr e d u c e st h en u m b e ro fl a b e l e dd o c u m e n t s u n d e rt h e s a m e e x p e r i m e n td a 糖e x p e r i m e n t r e s u l t ss h o wt h i s a l g o r i t h mh a sh i g h e r a c c u r a c y t h a ne m b a y e st e x tc l a s s i f i c a t i o n i t e r a t i v e 霸凇a l g o r i t h mb e l o n g st o h i l l c l i m b i n ga l g o r i t h m ，i th a s t h ec o m t n o n p r o b l e mo f c o n v e r g i n g t ol o c a lo p t i m a l v a l u ea n ds e n s i t i v et oi n i t i a lp o i n t t od e a lw i t hl e t a l o p t i m a lv a l u ep r o b l e m w e i n t r o d u c ea c t i v el e a r n i n g t e e h n o l o g y t or e d u c et h e c o n v e r g i n gs p e e d t o1 0 c a lo p t i m a lv a l u e 1 如r e s u l t ss h o w t h i sr e j o i ni s h e l p f u l ，a c t i v el e a r n i n g r e d u c e st h ec l a s s i f i c a t i o nb i a sa n db o o s t st h e a c c u r a c y 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 , e ma l g o r i t h m ，仃勋fa l g o r i t h m k n f l a l g o r i t h m n 奎查坌燮塑茎一 第一章引言 1 1 文本分类概述 随着网络的迅猛发展，网上的网页，电子邮件，数据库，聊天室和数字图书 馆等电子文本成几何级数不断增长，处理这些海量数据的一个重要方法就是将它 们分类。当我们浏览一个网站查找信息时，如果网页凌乱的堆积在一起没有类别 供我们查找，会使我们很难找到自己所需的信息。现在大型网站都将网页分类， 以方便人们浏览。比如，y a h o o 就将网页放在一个巨大的层次分类结构中，通过组 装维护这些类别，可以帮助人们查找知识和信息。网页自己没有类别，需要人工 分类，自动文本分类系统可以帮助人们检查文本、判断文本所属的类别。文本分 类系统所采用的算法就是文本分类算法并的系统。网页，邮件等各种格式的文档 经过文法分析都可以转化为纯文本。 文本分类领域是一个活跃的科研领域，它经历了几个不同的发展阶段。最先 文本分类由作者自已标识。到1 9 6 4 ，m o s t e l l e r 和w a l l a c e 【1 j 在鉴别文章作者身份的 工作中开创了文本分类的新阶段，他们考虑单词，句子长度，功能词的频率和词 汇的差异等特征项。更近期的文本分类具有广泛的应用：分类新闻组文章弘1 ；网页 分类唑自动学习读者的兴趣唑邮件过滤1 5 1 1 6 1 等。 自动文本分类中应用较早的机器学习方法是纯粹贝叶斯( n a i v eb a y e s ，简称 n b ) 7 j l s l 9 1 。大量其它机器学习的技术也被用于文本分类，如支持向量机( s u p p o r t v e c t o r m a c h i n e ，s v m ) 1 0 l ! 】，最大熵算法( m a x i m u m e n t r o p y ) 1 1 2 1 , 神经网络( n e u r a l n e t s ) ( 1 3 1 和规则学习算法【1 4 1 ，k 近邻算法i l 训( k n e a r e s t n e i g h b o r , k 瞄) 等。至今没有 哪个单独的技术体现出超出其他技术的明显优势，但最近的数据表明k 近邻法和 支持向量机在充足的训练样本的情况下性能较好l l “。 早期的算法基于手工构建规则集。这种方法人们要手工设置详细的分类规则 集。举个例子，规则可能为“如果工作广告中有j a v a 专家的短语则职业类别 为电脑程序员”。一些精确度很高的分类器通过这种方法构造，不过代价很高。 构造完整的规则集要大量的专业知识和大量的时间调整出正确的规则。所以除开 极少数特例，这种文本分类方法缺乏实用价值。改进的途径是通过监督学习构造 一个分类器。我们采用每个类别都有一些样本的样本集训练分类器找到分类的表 达式或决策规则。这种方法同样可以得到高精度的分类器，因为算法自动构造规 则所以比人工建立规则花费要小。 大多数文本分类采用词袋( b a g s - o f - w o r d s ) 表示法，即记录每个单词在文档中 出现的次数，或仅记录出现与否。加入语义信息或语言信息对分类器的精度都提 高不大f 用。 监督学习的文本分类算法别广泛应用与各个领域，如新闻分类，网页分类， 按读者兴趣分类，邮件分类等。不过这种监督学习的方法不象我们希望的那么容 量磊：主麓筹霎譬箍嚣 漂雾鬻黼燃岔墓舀慧 訾样! 菜笑黧鬻望蒜。1 0 比0 0 鬈蔷竺渊蚤燃嚣筹美爹蒙 趣一个人阅读并手工标识篇文章，一个分荚器只达剑5 0 叨猾辱。歪多裂 爰用系统的使用者不会有耐心标记1 0 0 0 篇文章的，而且只达到淬刍低塑楚譬：= 不使南者希望只标识十几篇而不是1 0 0 0 篇文章就能达到精确的分类。标识样本花 1 2 相关工作 文本分类算法是有监督学习的算法，它需要有一个已经手工分好类的训练文 档集，文档的类别已标识，在这个训练集上构造分类器，然后对新的文档分类。 如果训练集的类别未标识，就是无监督的学习算法，无监督学习算法从数据集中 找出存在的类别或者聚集。 常用的文本分类算法主要包括三大类。一类是基于标准的r o c c h i o l l s l 分类算法 的t f i d f i 伸】方法，其基本思想是利用t f i d f 权重公式计算一个词在文档中的重要 性，然后用c o s i n e 距离计算两个词向量的相似度，这类算法包扩t f i d f 算法，k 近邻算法d s 等：另一类方法则是基于概率和信息理论的分类器，如纯粹贝叶斯算 法最大熵算法1 1 2 】1 1 2 】等；第三类是基于知识学习的方法，如决策树( d e c i s i o n t r e e ) c 4 5 等算法1 1 4 1 。 不管是t f i d f 权值距离算法，还是概率分布类算法，要达到一定的分类精度， 建立一个较精确的模型，就要依靠大量已分类文档进行训练。当对一领域文档需 要建立一个新的分类器时，手工分类大规模训练集就成为快速建立高效准确的分 类器的瓶颈。 未标识样本相对于已分类的标识样本是一种廉价容易获得的资源，特别是对 文本而言网上有大量的网页，电子邮件和新闻消息，这些未标识的文本都随处可 得。收集工作可以自动完成，所以能快速，方便地得到大量的未标识数据。将这 些未标识的数据结合到监督学习中，使得在很少的手工标识文本的情况下建造较 高精度的分类器。 将已标识数据与未标识数据结合共同训练分类器的思想在统计学中早已存 在。早在1 9 6 8 年就有用已标识数据和未标识数据通过最大似然共同训练分类器 2 0 1 。d e m p s l c r e ta l l j l 9 7 7 年提出了e m ( e x p e c t a t i o n m a x i m i z a t i o n ) 算法的理 论框架，将以前提出的迭代最大似然估计缺失数据的技术形式化。它适用于结合 标识数据和未标识数据最大似然估计混合模型的参数，然后用模型进行分类。最 近，e m 算法在机器学习中得到了广泛的应用f 2 2 1 1 2 3 j 【2 4 j 。 在文本分类中，n i g a m 等人引入e m 算法结合贝叶斯文本分类算法，将未标 识文本结合到分类器的训练中。未标识文本因为没有类别标签，所以看成类别缺 少的不完整数据。算法首先用已标识文本训练贝叶斯分类器，用得到的分类器判 2 壅查坌茎蔓望堡壅一 断未标识文本属于每个类别的概率，然后用已标识和原来未标识现在有了颦率分 布的文本重新训练新一代贝叶斯分类器，然后又重新判断未标识文本属于每个类 的概率，用于计算下一代贝叶斯分类器，这样不断迭代直到指定的循环次数或模 型参数趋于稳定。 最大熵算法是另外一个利用未标识数据的分类算法f 2 ”。结合已标识和未标识 数据训练分类器的技术也被用于其它算法。扩展支持向量机算法用己标识样本找 到超平面线性分割线来最大化分割已标识样本和未标识样本1 2 6 】。支持向量机的研 究人员认为类分界处是样本密度较稀疏的地方，而未标识样本有助于找到这些区 域。未标识样本还被用于联合训练( c o - t r a i n i n g ) 算法【2 7 】以及作为背景知识为近邻 分类器判断类别提供背景支持怔。 人脸识别是模式识别中的另一重要课题，微软中国研究院的李予青博士提出 属于同一类的两个样本点的连线也代表了类空间的特性，基于特征脸模型和这一 思想提出了最近特征线算法，在较少的训练样本的情况下，算法在人脸识别中表 现出很好的性能【3 0 】。 1 3 研究动机 为了提高分类器的精度，一般算法要求较大的训练集，构造手工标识的训练 集耗费了人们大量时间和精力。而网上存在大量随手可得的未标识的文档，数目 远远超过己标识类别的文档。n i b a m 提出将大量未分类的文档和少量手工标识类 别的文档相结合，共同确定贝叶斯分类器概率分布。这个算法将e m 技术和贝叶 斯文本分类器结合，减小了贝叶斯分类器所需的已标识文档数目，提高了建立训 练集的效率。贝叶斯概率算法认为未标识文档的单词在类别中的概率分布及其类 别的概率分布是按模型的概率分布生成的，所以未标识文档含有模型信息，大量 未分类文档可以帮助确定模型参数。 e m 算法是一种迭代爬山算法1 2 1 】，用以在给定不完全数据下求解极大拟然估 计问题。e m 文本分类算法使用的是贝叶斯分类器，贝叶斯分类器假设单词之间是 独立无关的，在每个类别中单词服从特定的概率分布，每个文档类对应一组单词 概率模型。而现实数据是千差万别的，经常难以满足贝叶斯算法的混合概率组件 模型假设【2 3 l 。 距离模型认为同一类的样本点在高维空间中是相近的，而不同类的样本点 相似性则差得多，基于距离判断的非监督学习的聚类算法就是不断把未标识样本 分到聚类中，不断迭代优化，得到合理的聚类。对比e m 技术与聚类算法，我们 发现两种技术有共同点。e m 技术用最大似然估计未标识样本的类别概率分布，取 期望就得到分类器判断未标识样本的类别：聚类算法通过计算未标识样本到类中 心的距离判断类别。两者都是对未标识样本进行类别计算并迭代更新参数。如果 将e m 文本分类算法和聚类算法的迭代思想用于基于距离判断的文本分类算法， 效果会怎样? 我们用t f i d f 分类器将未标识文本分到各个类空间中，然后不断迭 代以逼近最优模型。这样迭代t f i d f 文本分类算法既有e m 文本分类算法的优点， 减小了对已标识文本的数量要求，又避免了e m 算法的假设要求。具有更强的数 据鲁棒性。如果结合最新的主动学习的技术，将进一步减小算法受初始值的影响， 文本分类算法研究 抑制了爬山算法容易收敛到局部最优值的周有问题。 微软的李子青博士在人脸识别中提出了最近特征线分类算法 3 0 l ，该算法基于 一定的人脸识别的特殊性，通过对已知样本点分析，挖掘潜在信息，认为同一类 中两个样本点的连线也代表了样本空间，是同一个人不同角度，不周光线亮度的 特征脸面，于是得到扩展的特征空间。变相的扩大了训练集，提高了算法利用己 标识样本点的效率。该算法具有领域的特殊性，同时又具有向量空间方法的一般 性。我们将特殊性推广到一般性，将算法应用到文本分类中，在文本分类实验中 表现出了较好的性能。在距离分类法中。k 近邻法的错误率一般小于近邻法【模式 识别1 ，我们将最近特征线法推广到k 最近特征线法口“。实验表明，在文本分类中， k 最近特征线算法精度要高于最近特征线算法。 1 4r a i n b o w 文本分类系统 r a i n b o w l i b b o 、v 【3 2 1 是卡内基梅隆大学的m c c a l l u m 等用标准c 语言开发的基 于l i n u x u n i x 的文本分类程序包。作为一个独立的系统，r a i n b o w 系统可以处理 各种类型的文档，包括纯文本，网页，邮件等，并实现了许多算法，可以对数据 集测试多种算法。它定义了灵活的数据结构，实现了丰富的函数调用，给出了规 范的算法接口，为实现新算法提供了方便。 r a i n b o w 文本分类系统首先要对以分类的训练集建立模型。训练集分为n 类，每 类对应个文件目录，目录名称就是它的类别名称，每个类的文档就放在这个目 录下。系统就对这些目录进行路径解析和文件名解析，把目录名保存为类别名 把文档路径和文档名保存为这篇文档的名称，在系统中文档。类别，单词都是用 整数序号代表的，序号所对应的实际文档名，类别名，单词都分别保存在数据文 件中。然后对文档进行文法分析，去掉常用词，忽略邮件头部，删除网页的特殊 标记，找出每篇文档对应的单词和每个单词在这篇文档中出现的频率。于是得到 文档到单词的词频统计矩阵。然后按照算法，对词频统计矩阵进行分析计算。得 到了这个算法的分类器。分类器建立好了就可以对新的文档进行分类，新文档进 行预处理变为词向量，向量中的数值就是单词在文档出现的频率，根据分类器模 型对文档中的每个单词重新设定权值，然后由分类器判断这篇文档是属于哪个类 的。如果是贝叶斯分类器就是计算文档属于每个类别的概率，概率值最高的类别 作为文档的类别：如果是t h d f 分类器则计算文档到每个类别的相似度距离，与 文档相似度距离最大的类别为文档的类别。 r a i n b o w 自动文本分类系统对算法留有专门的接口，本身就实现了很多算法， 包括贝叶斯算法，k 近邻算法。支持向量机算法，最大熵算法，e b t 算法等。每个 算法对应于一个独立的模块，模块包括算法的参数设置，数据操作函数，评价函 数，文档向量权值设置函数等函数。算法都基于统一的数据结构，其中个主要 结构是文档到单词的向量矩阵，也可转化为单词到文档的向量矩阵。这种文档到 单词的向量矩阵也可以作为类到单词的向量矩阵使用矩阵中的每一点都对应一 个结构，包括频率，单词索引号，分布概率，权值等。统计的单词放在词典中， 对应一个唯一的索引号。文档名也保存在文档列表中，对应唯一文档索引号。类 别名保存在类别列表中，对应相应的类别索引号。接口的一致和基本数据结构封 4 塞查坌鲞! 鲨堑塞 装使系统具有良好的可扩充性。 作为文本分类系统。r a i n b o w 为文本分类定义了专门的数据结构，实现了大 量的算法，是一个优良的算法测试平台它有如下特点： ( 1 ) 完整性。整个系统的源代码有7 万多行，定义了大量数据结构，实现了各 种功能模块和算法模块。从对原始数据的文法处理到实验结果的自动统计， 从i o 操作到数学函数，都有专门的方法实现，提供了强大的数据操作的 功能。 ( 2 ) 封装性。系统将许多数据结构和方法封装在一起，屏蔽了一些底层操作， 提供了灵活的函数调用的接口，使得系统有较好的可扩充性和稳定性，封 装了对原有结构的一些基本操作。 ( 3 ) 模块化。算法模块和功能模块独立性较强，各种算法都基于统一的数据结 构定义各自的操作函数，相同的函数接口可以调用不同算法的函数实现， 主程序只要调用函数接口而不用管算法的具体实现过程。 ( 4 ) 可扩展性。由于算法与主程序相对独立，算法都基于统一的数据结构，方 便在系统中添加新的算法模块，主程序有大量调试判另q 语句，易于发现错 误，保证了程序的一致性和正确性。 1 5 本文所做的工作 本文主要研究文本分类算法，主要工作总结如下： 1 对文本分类算法做了系统的理论和应用研究，深入研究分析了k 近邻文本分类 算法，纯粹贝叶斯文本分类算法和e m 文本分类算法，对算法的理论背景，实 现过程都做了细致的研究； 2 深入分析了r a i n b o w 文本分类系统，研究系统的体系结构，程序流程，研究了 其中的文法分析模块，文本数据结构，算法结构等： 3 将几种常用的文本分类算法应用于中文文本分类，对比了中英文分类的异同， 测试了s v m ，b i b ，k n n ，t f i d f 等算法在中英文中的分类性能： 4 基于人脸识别中的最近特征线算法，提出了k 最近特征线算法( k n f l ) ，在文 本分类系统中实现了这两个算法，测试对比了算法的性能，实验结果表明特征 线算法能够有效利用已标识文本，达到较高的分类精度： 5 基于将未标识文本结合到分类器训练过程中的思想，提出了迭代t f i d f 算法， 分析了算法的收敛性，该算法比概率迭代算法表现出更强的数据适应性和鲁棒 性，迭代t f i d f 算法的分类精度高于e m 贝叶斯迭代文本分类算法。 6 针对迭代t f i d f 算法中收敛到局部最优值问题，根据主动学习的概念，将主动 学习加入到迭代t f i d f 算法中，控制了收敛速度，有效的解决了局部最优问题， 使模型更加精确，进一步提高了算法精度。 全文主要包含以下六个章节：第一章引言包括文本分类概述。文本分类算 法的发展过程，相关工作，介绍文本分类系统以及本文所做的主要工作；第二章主 要算法性能研究及中文分类的应用，包括几种主要文本分类算法，文本分类过程， 对比了中英文文本分类实验，分析了实验结果和改进方法。第三章k 最近特征线 文本分类算法研究 算法及其在文本分类中的应用包括原有的最近特征线算法在文本分类中的实现， 分析了最近特征线算法的特殊性及其缺陷，改进算法及实验：第四章迭代t f i d f 算法包括e m 算法及模型的缺陷分析，一种结合了迭代算法思想的迭代t f i d f 文本分类算法，分析了算法的收敛性并进行了实验：第五章主动学习的迭代 t f i d f 算法，根据主动学习的思想，从未标识文本集中选择对模型最有帮助的未 标识文本加入到模型训练集中，进一步提高了模型的精度；第六章结束语总结 全文。 6 兰查坌茎兰鎏曼塞 第二章常用文本分类算法性能研究 2 1 引言 分类算法是试图设计某种分类器，以判断样本的类别。文本分类中有许多分 类算法，这些算法的理论基础，实现形式各各不相同，第一章提到了k n n 和s v m 被看作属于最好的分类算法，它们性能到底如何，哪个更优呢。 本章讨论几个常用的算法机制，测试对比其性能，分析文本分类系统的结构， 分类过程，算法实现过程，并将系统应用到中文文本分类中，为后面章节奠定了 理论和实验基础。 2 2 文本分类模型 分类算法一般基于“词袋”模型，即文档被看成是由相互无关的单词构成的 词的集合，不考虑单词之间的上下文关系，单词出现的顺序，位置以及文章的长 度等。统计出每个单词在每篇文档中出现的频率是进行算法建模的基础，统计所 有单词在所有文档中出现的频率就得到了单词到文档的词频统计矩阵。词频统计 矩阵是文本分类算法建立分类器模型的数据基础，训练集通过文法分析统计出词 频矩阵，矩阵中的一项就是某个单词在某篇训练文档中出现的频率。 首先要按路径对所有训练文档扫描，分析出不同的单词。对待英文，文法分 析的步骤为：按空格分出各个单词，去掉其中停用词，如t h e ，t h a t 等，如果是第 一次遇到的新词，就存入单词列表，也称词库，否则这个单词的统计次数加l ，其 中包括词干提取，如将p l a y e d , p l a y i n g 变为p l a y 还包括保存文档的文件名，类别 等工作。当把算法运用到中文分类中，关键问题就是中英文的单词在句子中的出 现方式不一样，对待中文要增加切词的工作。因为中文不象英文有空格将词与词 区分开，中文文本中词与词之间没有明确的分隔标记，而是连续的汉字串。汉语 中存在大量多义词，语义模糊，歧义性大，识别词的边界很难。常用的中文分词 算法有：基于词表的分词，基于统计的分词，基于规则和基于统计相结合的分词。 我们将采用基于词表匹配的分词方法，这种切分方法，需要语言资源( 仅需一个 词表，不需要任何词法、句法、语义知识) 最少，程序实现简单，我们将中文的 词法分析器代替原有的英文词法分析器，将词法分析模块插入到r a in b o w 系统中， 得到需要的词频矩阵，测试不同的算法在分类中的性能。 预处理之后，文章变为一个词集，单词也称为特征项或属性。把文档看成是 一个词向量( w o r d v e c t o r ) ，它的维数是所有不同的单词个数，词集中可以有数万 个不同的单词。对于特定的文章，它包含的单词数一般从几百到几千，篇文档 对应一个词向量，而一个词也在不同的文档中出现，所有出现这个单词的文档构 成了文档向量，所以整个文档与词集形成一个稀疏矩阵，矩阵中点的值就是单词 在文档中出现的频率。在系统中，矩阵以二维链表的形式保存。 7 文本分类算法研究 o l e m i n g 叨 3 j o u r n a l 2 i n t e l l i g e n c e 0忙n 0 a g e n t 一一，一_ lh e f l 3 e l 磊餮 0 w c b w a l c h c f 0 p e d 5 _ l v o l u m e 图2 1 词袋模型中文档词频向量示意图 词频统计矩阵是算法建模的基础。在词频统计矩阵的基础上根据特定的算法 构造分类器。构造好分类器后，当对一篇测试文档分类时，首先利用建立的分类 器模型给测试文档的词向量赋于相应的权值，然后由算法根据分类器和文档向量 计算此文档的类别。 词向量的权值按不同的算法有不同的计算方法和意义。在第一类算法中，权 值按t f i d f 公式计算，权值越大，表示这个词对文档越重要。t f ( t e r mf r e q u e n c y ) 是词在文档中出现的次数，如果一个词在篇文档中经常出现，那么说明这个词 对文档具有代表性。如“计算机”这个词在计算机类的文档中出现的频率显然要 高于政治类的文档。但如果一个单词在一篇文档中出现，但同时它也出现在很多 文档中，则降低了这个单词的重要性，如“科学”在社会科学类与自然科学类的 文档中都出现，对区别两类文档的帮助就不大，这就是反比文档频率i d f ( i n v e r s e d o c u m e n tf r e q u e n c y ) 的作用。把两项相乘得到的权值，就代表了单词对文档的整 体重要程度。 对于另一类概率算法，如纯粹贝叶斯算法，则通过词频统计矩阵计算每个词 属于每个类的概率。权值越大，表示单词在这个类中出现的概率大，得到了词到 类别的概率分布。贝叶斯算法认为新的文档满足建立的概率模型的单词的类概率 分布，把文档中的单词在每个类上的概率按类相乘，由此计算出文档属于每个类 别的概率。 上面所提的两类算法代表了两种基本文本分类模型。一类是由t f d f 公式定 义单词的权值，由c o s i n e 相似度距离公式计算样本点之间的相似度。一类是概率 权值。计算单词在类别上的概率分布，然后求得文档属于每个类别的概率。 兰查坌鲞兰堕墅塞一 2 3 几种文本分类算法的研究 在众多分类算法中，我们重点讨论三种方法：贝叶斯算法，支持向量机算法 和k 近邻法。 2 3 1 支持向量机 支持向量机方法支持矢量机( s u p p o r t v e c t o rm a c h i n e s ，s v m ) 是由vv a p n i k l j 川 与其领导的贝尔实验室的小组一起开发出来的一种机器学习技术。s v m 的理论 基础来自于v a p n i k 等提出的统计学习理论，它的基本思想是，对于一个给定的具 有有限数量训练样本的学习任务，如何在准确性( 对于给定训练集) 和机器容量 ( 机器可无错误地学习任意训练集的能力) 进行折衷，以得到最佳的推广性能。 它采用结构风险最小化( s t r u c t u r a lr i s km i n i m i z a t i o n ) 原则。s v i 算法不仅 具有扎实的理论基础，而且在应用到文本分类时取得了很好的结果i ”】。 设给定的训练集为 ( x l ，y 1 ) ，( x 2 ，y 2 ) ，( x ，y f ) ，x r “，y + 1 ，一1 ) 且可被一个超平面线性分割，该超平面记为 ( w - x ) + b = 0 ( 2 - 1 ) 如果一个训练集中的矢量能被一个超平面无错误地线性分割，且距该超平面最 近的矢量之间的距离最大，则称该超平面为最佳超平面( 如图2 2 所示) 。其中距 离超平面最近的点称为支持矢量( s u p p o r tv e c t o r ) 。对决策面设计起作用的点( 图 中圈中的点) 称为支持向量( s v ) 。 图2 - 2s v m 算法原理示意图 对于线性可分的情形，不失一般性，我们可假定训练集中的矢量满足下列不 等式： 即：1 ，f ，y = 1 , ( 2 - 2 ) w i l + 6 s l矿y t = - 1 我们称上述不等式为规范形式( c a n o n i c a t lf o r m ) 。可将上述不等式合并为 ) ，i ( w x + 6 ) lf - l ，( 2 3 ) 9 苎奎坌鲞! 兰璧塞 于是构造最佳超平面的问题转化为求 m(w)=im2(2-4) 的最小值的问题。事实上，支持矢量到超平面的距离为l h ，于是支持矢量之间 的间隔为2 l l w 0 。 寻求具有最大间隔的最佳超平面的依据是，一个规范超平面子集的v c 维数 满足下列不等式： h m i n ( r 2 a 2 】，n ) + 1 ( 2 - 5 ) 其中n 为矢量空间的维数，所有待分割的矢量位于半径为r 的超球内，而i i 删a 。 这样我们就可在固定经验风险的情况下，将使v c 置信度最小的问题转化为使f l w 8 最小的问题。构建最佳超平面来分割属于两类的训练集 ( x l ，y 1 ) ，( x 2 ，儿) ，( x ，h ) ，x r “，y ( + l ，一1 ) 的问题，转化为解决下述二次规划问题： 在约束条件 y j ( w x + 6 ) 2 l i = l ，f ( 2 6 ) 下，求 中( w ) = j 1 ( w - w ) ( 2 - 7 ) 的最小值。为了将线性推广到非线性，v a p n i k v a p n i k ，1 9 9 5 提出了支持矢量机的概 念，其基本思想是：通过事先确定的非线性映射将输入矢量i 映射到个高维的 特征空间( 一个l - i i l b e r t 空间) 中。然后在此高维特征空间中构建最佳超平面。 t h o s t e nj o a c h i m s l l q 将s v m 用于文本分类并比较了其它的分类算法。他的结 果显示s v m 要优于其它方法。 超平面是对两类分类的划分。对于有大于两类的多类文本分类，就对每个类 构造一个超平面，将这个类与其余的类分开。有多少个类就构造多少个超平面。 测试时就看哪个超平面最适合测试样本。 2 3 2k - 近邻法 近邻法是由c o v e r 和i t a r t 于1 9 6 8 年提出的，直至现在仍是模式识别非参数法 中最重要的方法之一。k n n 算法思想很简单：给一篇待识别的文章，系统在训练集 中找到最近的k 个近邻，看这k 个近邻中多数属于哪类，就把待识别的文章归 为哪一类k 近邻分类器在已分类文章中检索与待识别的文章最相似的文章，从而 获得被测文章的类别此算法有简单的优点，但存在问题，需要将所有样本存入 计算机中，每次决策都要计算待识别样本与全部训练样本之间的距离进行比较。 1 0 因燃麓裟需黑卷雹絮二项式赋值即如果单词在文档中i t t 1 u ) ,统计词在文档中的有两种定义，一种是二项式赋值即如果旱词征又桕甲 就设为1 ，否则设为0 ，这样计算就比较简单：另一种是计算单词在文档中出现的 频率，这样算法可以利用更多的信息，分类精度要高于第一种定义 8 1 。统计词频 矩阵后按t f i d f 公式给文档向量赋权值。 坝= l o 双碍+ 1 ) ( 2 8 ) ( 2 9 ) 其中n 为训练集中的文档数，t f , k 指第k 个单词在第i 篇文档中的频率，a f , 指 在整个训练集中，包含第k 个单词的文档个数。距离公式采用c o s i n e 相似度 距离公式： c o “孑，孑，) ：! i ( 2 1 0 ) 酬丸办卜而而知 心一 2 3 3n a i v eb a y e s 算法 贝叶斯概率分类器在机器学习领域中被广泛的研究f 7 】。贝叶斯分类器由m a r o n 提出，将文章看作独立的单词集合，通过训练集，由贝叶斯理论得到每个单词在 不同类的概率大小，构造出贝叶斯模型，模型由参数0 决定。贝叶斯算法假设文档 由混合模型产生，每个类别对应混合模型的一个分量。用符号c ，ec = c ，。蚓) 代 表第个类别，设整个词库y ： ，模型臼由以下参数组成： 一= 尸( w ，fc 口) ， l ，i v l ) ，c j c ；p ( c j i 口) ，c j c ) ( 2 1 1 ) 算法假设模型分量与类别一一对应，文档由模型产生，先选择一个类别，然后按 这个类别的模型分量产生一篇文档。那么一篇文档属于这个模型的可能性为： 旧 p ( t 1 口) = 艺尸( c ，l o ) e ( d ，口) j - i ( 2 - 1 2 ) 文档4 被看成词的无关事件集合，用y m 表示文档4 的第七个独立单词，以是词 库矿= 中的第九个索引标识。文档属于某一个类的条件概率为单 词的类条件概率的乘积： 文本分类算法研究 l 面j 户( 矾i 勺；研= 兀尸( b ；口) k - i ( 2 1 3 ) 建立贝叶斯分类器的任务就是确定参数口。口的估计值记为蚕，对训练集按以下公 式计算得到蚕： 。，。、l + ：n ( w ，矾) 尸( c ，i 矾) 盹h 卜而袁誊意赫 驯舡号半 ( 2 - 1 4 ) ( 2 - 1 5 ) 9 i l i a d = 矾，谚。) 中的文档类别已知，jo l 为训练集的大小，p ( c jj4 ) 等于0 或l ，当4 芒c j 或t c j 。( w ，d ，) 表示单词在文档吐中的出现次数。 得到模型的参数估计后，由公式( 2 5 ) ，( 26 ) 和贝叶斯法则就可以计算一篇新文档在 模型中的后验条件概率： p ( c j1 d ；口) = p ( c ji 护) j p ( 4i c ，；口) ：一 j p ( 410 ) 尸( 勺i 舀) 丌i d ap ( ic j ；d ) = 盟百一 ( 2 1 6 ) ：。p ( c ，i 舀) 1 p ( w 。ic ，；舀) 分类器判断新文档属于后验条件概率最大的类别分量。 2 4 各种算法的性能评价 u s e n e t 新闻组数据库是1 9 9 4 年在u s e n e t 上下载的2 0 个类的新闻组讨论英文 文章( 2 0 一n e - s g r o u p s ) 。数据库中的文档放在2 0 个目录下，每个目录的名字就是 新闻组的类别。每个类大约是1 0 0 0 篇，共2 0 0 1 7 篇。为了提高实验效率，基于前 述的新闻组文档数据库，r a i n b o w 中还建立了一个微型数据库( m i n i ，newsgroups) 该数据库从n e w s g r o p u s 数据库中每个类选出1 0 0 篇文章，共2 0 0 0 篇。 对m i n i n e w s g r o u p s 数据集的2 0 0 0 篇英文文本进行词频统计，共找出3 6 8 6 4 个不同的词。 文本分类算法研究 表2 - i2 0 个新闻组类别 a l t a t h e i s m r e c s p o r t h o c k e y c o m p g r a p h i c ss c i c r y p t c o m p o s m s - w i n d o w s m i s c s c i e l e c t r o n i c s c o m p s y s i b m p c h a r d w a r e s c i m e d c o m p s y s m a c h a r d w a r es c i s p a c e c o m p w i n d o w s xs o c r e l i g i o n c h r is t i a n m i s c f o r s a l e t a l k p o l i t i c s g u n s r e c a u t o s t a l k p o l i t i c s m i d e a s t r e c m o t o r c y c l e s t a l k p o l i t i c s m i s c r e c s p o r t b a s e b a l1 t a l k p o l i t i c s m i s c 在建立模型时，文本分类系统r a i n b o w 首先按给定的参数从每类随机选择相 同的篇数，参数可以是训练集的篇数，或者是整个数据库的百分比数。在从剩下 的文章中每类随机抽取相同数目的文档作为测试文档，用来测试建立的分类器的 精度。这些测试文档的类别对分类器而言是不可见的。 在训练模型时，对训练集再次进行词频统计，构造出训练集的词频统计矩阵。 算法根据训练集的词频统计矩阵进行计算，按前面所介绍的过程构造出算法对应 的分类器模型。分类器模型建立后就进行测试，不同的算法建立不同的模型，对 一篇测试文档，按分类器模型计算其权值和模型需要的数值，然后评价测试文档 应属的类别。其实测试文档的类别是已知的，但算法并不知道测试文档的类别， 而赋予测试文档一个判断后的类别，用类别判断正确的文档数目除以整个测试文 档数就得到分类器的精度。 我们对k - 近邻考察了k 分别为 1 ，1 0 ，2 0 ，3 0 ，6 0 ，1 0 0 时的性