（计算机软件与理论专业论文）基于支持向量机的文本分类研究.pdf

硕士学位论文 摘要 随着信息技术的发展，互联网数据及资源呈现海量特征，而且，越来越多的信息以 电子文本的形式存在。为了有效地管理和利用这些分布的海量信息，基于内容的信息检 索和数据挖掘逐渐成为备受关注的领域。文本分类技术是信息检索和文本挖掘的重要基 础，近年来逐渐成为人们研究的热点问题。 本文对文本分类整个过程中涉及到的每个步骤进行了深入研究，包括预处理、文本 表示、特征提取、分类算法以及性能评估。对于中文文本分类，到目前为止，尚没有标 准的中文语料库可供使用。因此，自己动手收集文献标题作为语料库，并对典型的特征 提取算法和分类算法进行了实验对比研究。实验结果表明支持向量机是目前分类性能最 好的方法。 为进一步提高文本分类的准确率，使用潜在语义索引获得原始词文档矩阵的潜在 语义结构。通过使用潜在语义索引和不使用潜在语义索引的对比实验发现，在文本分类 中，使用潜在语义索引的效果并不理想，这是因为潜在语义索引在进行奇异值分解过程 中没有充分考虑分类信息。为解决该问题，提出了一种改进的局部潜在语义索引方法， 利用支持向量机的分类优势来产生局部区域，这样选择的局部区域，能够更好地表示某 类文档的潜在语义结构，从而提高了分类的准确率。 标准的支持向量机是针对两类分类问题设计的，不能直接用于多类分类问题。为使 支持向量能够进行多类分类，必须对支持向量机进行扩展。二叉树方法是一种常用的多 类分类方法，而它的关键问题在于如何构造合理的结构以获得较高的推广能力。为解决 该问题，按照h u f h n a n 树的构造过程自下向上地构造二叉树，使易于分割的类处于上层 结点，从而构造了合理的二叉树结构。 关键词：机器学习；文本分类：支持向量机；潜在语义索引；多类分类；二叉树；h u 仟m a n 树 硕士学位沦文 a b s t r a e t w i 饿t h ed e v e l o p m e 嫩o fi n f o r m a t o 糕t e e h n o l o 戥壤e 幽圭aa n d 羚s o u r c e si n 也ei 狂l e m e t 妇o wt 沁e h a r a c 耗r i 鞋主co fm a s a n dm o r c 赫dl n o 瓣i n f o m a 耄i o ne x i s 专s 氇氇e o r mo f e l e c t r o n i ct e x t i no r d e rt oe f r e c t i v e l ym a l l a g ea n dm a k eu s eo ft h e s ed i s t r i b u t e dm a s s i v e i n 南m a t i o n ，i n f o h i l a t i o nr e t r i e v a la n dd a t am i n i n gb a s e do nc o n t e n tb e c o m et h eh i g h l y e o 粒e m 旌a 羚a 静建疆a l 弛强蛾e l 鑫s s i 羹c 鑫专i 潍主s 鞠i 瓣p o 岙秘l 如珏拄巷越i o 薹薹f o r 霸稻艄鑫专i o 嚣 r e 打i e v a la n dd a 【瓴m i n i n g ，a n dg r a d u a l l yb e c o m e sah o tm s e a r c hi s s u ei nr c c e n ty e a r s i nt h i s p a p e r ，w es t u d yt h ee v e 秽s t e po ft e x t c l a s s i f i c a t i o ni n d e p t h ，i n c l u d i n g p r e p r o c e s s i n 舀t e ) ( tp r e s e n t a t i o 羲，受a 钯f es e l e e t o n ，c l a s s i 蠡c a t i q na l g o r i 谯糯a n dp e r f o r 黼a n e e e v a k a 圭i o n f o r 也ec h i n e s et e x c l a s s i 蠡c a t i o 秘，磕e r ei sn os 玩n 幽砖e o 糟u sa v 赫l a b l es o 董戤 t h e r e f o r e ，w ec o l l e c tp a p e rt i t l e sa st h ec h i n e s ec o 砷u s ，a n dm a k eu s eo fw h i c h ，w ec o n d u c t t h ec o m p a r i s o ne x p e r i m e n to nt h et y p i c a lf e a t u r es e l e c t i o na l g o r i t h m sa n dc l a s s i f i c a t j o n a l g o 蠢氇攥s 。强e 羚s l | l 专建o w st h 采s 疆p p o 纛v e e 甜擞a e 囊i i s 氇e 泌s t 蠢g q 砖醢糯遮辫娲熊8 鑫 s of a r t bm r t h e ri 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 n ，w eu s el a t e n ts e m a n t i ci n d e x i n gt o g a i nt h el a t e n ls 锄a n t i c 懿燃e t u r eo f 硼g i n a lw o r d d o c u m e n tm 毪臼i x 。瑟l u 曲t h ec o m p 嚣i s o n e x p 酬瑚e n 毫b e 俯e 翎疆s i n gl a 耋e l l 砉s 锄鞠毫i ei n d e x i n g 黼dn o 章u s i n gl a 毛锻ts e m a n 圭i ei n 蠢e x i n 岛 w ef i n dt h a tt h ee f r e c to fu s i n gl a t e n ts e m a n t i ci n d e x i n gi sn o ti d e a l ，b e c a u s ec l a s s i f i c a t i o n i n f o r n l a t i o ni sn o t 血i l yc o n s i d e r e di nt h ep r o c e s so fs i n g u l a rv a l u ed e c o m p o s i t i o no fl a t e n t s e 擞a 鼓t ci 蕤巷e x i 曩g 。bs g l v o 像e 筘o b l e 搬，黻i 趱p 羚v e dl c a ll a 圭e 鞋ts e 掇褫ei 珏d e x i 建g 瓣穗l o d i sp r o p o s e d ，脚【i n ga d v a n 馈g eo fs u p p o r tv e c t o rm a c h i n el og e n e r a t et h el o c a ir e g i o n s u c h l o c a jr e g i o nc a nb e t t e rr e p r e s c n td o c u m e n t s ? l a t e n ts e m a n t i cs t r u c t u r eb e l o n g i n gt ot h es a m e c a t e g o t h e r e b yi m p r o v i n gt h ea c c u 豫c y 硝t h ee l a s s 添c a t i o n ， s 谯魏d a 撼s 毛l p p o 趱v e e 埝r 氆a c h i n ei sd e s i g n e df & s o l v i n g 镪ee l a s s i 薮e a 耄i 锄p 妁b 酶激w i m t v 旧c l a s s e s ，a n dc a nn o tb ed i r e c t l yu s e dt os o l v et h ep r o b l e mw i t hm u l t ic l a s s e s 1 os o l v et h e p r o b l e mw i t hm u l t ic l a s s e s ，w em u s te x t e n dt h es u p p o r cv e c t o rm a c h i n ea l g o r i t h m t h eb i n a u 稔e e 擞确。纛o f 滋驻l ic l a s sc l 鑫s s i 磊e 采i o 薹l 弧鑫蓬。趔i n a 黟懋。攮o d ，壤ek e yi s s 珏eo fw h 瓷hi s 纛o w t oc o n s t r u c tar e a s o n a b l es t m c 掘r et om a i n t a 洫h i 曲g e n e r a l i z a t i o na b i l i 够孙s o l v et h e p r o b l e m ，ab i n a 唧t r e ei sc o n s t n l c t e df 而md o w nt ou pa c c o r d i n gt ot h ec o n s t r u c t i o np r o c c s so f h u f 蕊a nt 粥e ，m a k i n gt h ec l a s se a s yt o s e p a r a t el i e si l l 像eu p p e rn o d ea n dt h e l e b ya 羚a s o n 曲l eb i n a 搿l r e es 掰e t u 托i se o n s 秘挂c 绝d 。 l l 硕士。位论文 k e yw o r d s ：m a c h i n el e a m i n g ；t e x tc l a s s i f i c a t i o n ；s u p p o r tv e c t o rm a c h i n e ；l a t e n ts e m a n t i c i n d e x i n g ；m u l t ic l a s sc l a s s i f i c a t i o n ；b i n a qt r e e ；h u f h n a nt r e e i i i 硕士学位论文 插图索引 图l + l 文本分类流程图2 图2 1 文本的向量空闯模型及文本问的相似度7 图2 2s 、m 原理1 4 图3 1n b 、k n n 和s v m 在特征数为2 5 0 0 时的比较f ，( ) 2 3 圈4 。薹蛉壬与s ￥沪毛毛s 王在不同特征德上的徽平均暴值比较2 9 图4 2l l s i 与s v 舻l l s i 在教育类上的f l 值比较2 9 图4 3l l s i 与s v m _ l l s i 在法律类上的f 1 值比较2 9 图5 。ld a g s 豫结构图- 3 3 圈5 2 二叉树方法 4 类分类) 结构图3 4 l v 硕l ：学位论文 附表索引 表2 1 二值分类列联表19 表3 1 文献标题样例2 1 表3 2c h i 、i g 、d f 、m i 的比毫迂( m i c r o f 1 ) 2 2 表4 1 不同特征数目下分类器性能比较表( 微平均准确率) 2 6 表4 2l l s i 与s v m - l l s i 取得最大f 1 值时使用的特征数比较3 0 表4 3l l s i 与s v m _ l l s i 取得最大f l 值时s v d 需要的时间比较( 单位：秒) 3 0 表5 1e c o c 示意3 4 表5 2 数据集基本信息表3 7 表5 3 四种多类分类方法的分类精度比较( ) 3 7 v 兰州理工大学 学位论文原创性声明 本人郑重声明：质量交的论文是本入在导师的指导下独立进行磺究所取得的研究成 果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体融经发表 、 或撰写的成果作品。对本文的研究做出重要贡献憨个入和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 参 嗍：垆抄刖日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向 国家有关部门或机构送交论文的复印件和电子版，允谗论文被查阅和借阅。本人授权兰 州理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密露适用本授权书。 2 、不保密囤。 ( 请在以上楣应方框内打“ ) 作者签名： 如多夸，墨期：岬年，月f 墨 导师签名：胪衣 日期：弘年_ ，未月p 日 硕： j 学位论文 1 1 概述 第1 章绪论 随着信息技术的发展，互联网数据及资源呈现海量特征，而且，越来越多的信息以 电子文本的形式存在。统计表明，目前网页的数量呈指数型增长，平均每年增加一倍。 截至1 9 9 9 年2 月，i n t e m e t 上大约有3 0 0 万台服务器和至少8 亿个页面，信息量高达1 5 t b 。 为了有效地管理和利用这些分布的海量信息，基于内容的信息检索和数据挖掘逐渐 成为备受关注的领域。其中，文本分类( t e x tc l a s s i f i c a t i o n ) 技术是信息检索和文本挖 掘的重要基础。文本分类在自然语言处理、信息组织与管理、内容信息过滤等领域都有 着广泛的应用。2 0 世纪9 0 年代逐渐成熟的基于机器学习的文本分类方法，更注重分类 器的模型自动挖掘和生成及动态优化能力，在分类效果和灵活性上都比之前基于知识工 程的文本分类模式有所突破，成为相关领域研究和应用的经典范例【1 j 。 所谓文本自动分类，就是由计算机自动提取文本的特征项，依据一定的算法，将文 本按内容归到一个或多个类别的过程。研究这个算法是文本自动分类研究的核心内容。 从数学上来讲，若文本d 根据一定的算法厂分到类c ，中去，则可以表示成 ：d j e ，f = o ，l ，；其中d 是单个文本，而c 。可以是一个类，也可以是多个类，即可 以是一对一或一对多的关系【2 1 。 一般来讲，文本分类主要涉及到五方面的问题【3 】： 1 获取训练文档集 训练文档集的选择是否合适对文档分类器的性能有较大影响。训练文档集应该能够 广泛地代表分类系统所要处理的客观存在的各个文档类中的文档。一般而言，训练文档 集应该是公认的经人工分类的语料库。目前，r e u t e r s - 2 1 5 7 8 【4 】是国际上最重要的基准语 料，常见的语料还包括o h s u m e d ，2 0 n e w s g r o u p s ，w e b k b 及a p 等【引。 2 建立文档表示模型 即选用什么样的语言要素( 或者说文档特征) 和用怎样的数学形式组织这些语言要 素来表征文档。这是文本分类中的一个重要技术问题。目前的文本分类方法和系统人多 以词或词组作为表征文档的语言要素；向量空间模型( v e c t o rs p a c em o d e l ) 仍是文本表 示的主要方法【6 j 。 3 文档特征选择 语言是一个开放的系统。作为语言的一种书面物化或者电子化的文档也是开放的。 它的大小、结构、包含的语言元素和信息都是开放的，因此它的特征也是无限制的。文 本分类系统应该选择尽可能少而准确且与文档主题概念密切相关的文档特征进行文本 嫠】支持同蹙机的文本分类研究 分类。常见的特征选择方法有：文档频率( t e mf 懈q u e n c y ) 、信息增益( i n f o r n l a t i o ng a i n ) 、 蔓信惑( m 鞋l l il 羲稻黼a 菱i o n ) 、墨2 统计量 o ，我们将其称为学习率，用来控制 权重向量w 的变化速度，以及每一个耨的训练样本对它的影响。w h 可以看作一个梯度 下降过程，因为2 ( q 芬一q ) 哦恰好是平方差( c 一乞) 2 的梯度。因此，w h 总是沿着方差 减小最快的方向来移动。 3 。e x l ，o 牲e n t i a t o d g l 喇i e n t 算法 e g 算法类似于w h 算法，每次使用一个训练样本对旧的类别向量进行更新。但是， 类裂淘量的第i 维限制为毫负筐，并且进行了懿一纯。初始时刻，我们设 置权重向量晌每 维都相等，即q = ( 1 d ，l 以，l d ) ，硝特征空间的维数。e g 算法的更新规则如下： 铅：= 蹬生塑竺生业( 2 2 5 ) 铲爱雨磊丽蔫 茹2 2 4 3k 近邻 心蹦是一种稳定而有效的文本分类方法【l 8 ，1 1 2 2 1 。它的做法是：给定一个测试文档， 系统在调练集中查找离他最近的素个邻居，并根据这些邻居的分类来给该文档的候选分 类评分。把邻居文档和测试文档的相似度作为邻居文档所在分类的权重，如果这阶邻 居中躲部分文档属予同一个类，焱将该分类中的每个邻器的权重求窝并作为该分类和测 试文档的相似度。通过对候选分类评分的排序，给出一个阈值，就可以判定测试文档的 分类，决策规煲| j 可以写作： j ，( 墨勺) = s 切z ( x ，d ) y ( d ，q ) 一屯 ( 2 2 6 ) d e k n n 英中，x 为一篇待分类文档离量表示，蠢为训练集中的一篇实铡文档向量褒示，c ；势 类别：y ( j ，c ，) “0 ，l 】( 当d 属于c ，时取1 ；当d 彳属于c f 时取0 ) ，6 f 为预先计算得到的c f 的最筑截尾阈值。s 渤( 毒，露) 表示测试文档舅和训练文档昀稆织度；通常采取计算两个 向量的夹角余弦作为它们的相似度。 埝烈方法豹优点在于有受高的分类准确性釉稳定性【l4 1 。它是一种基于要求的或懒惰 的学习方法，它存放所有的训练样本，无需事先对文本进行训练，直到测试样本需要分 类时才建立分类。在有训练文档的反文档检索时，复杂度为0 ( 三m ) ，上是大于o 的 基于支持向鼍机的文本分类研究 文档向量的元素数目，是训练集的大小。所以它的分类时间是非线性的。k n n 的缺点 是当训练文档数增加时，其分类时间将急剧增加。 2 4 4 支持向量机 支持向量机由v a p n i k 在1 9 9 5 年提出1 5 ，2 4 ，2 5 1 ，是二种基于统计学习理论的新型的通 用学习方法，它建立在统计学习理论的v c 理论和结构风险最小化原理的基础上，根据 有限样本信息在模型的复杂性( 即对特定训练样本的学习精度) 和学习能力( 即无错误 的识别任意样本的能力) 之间寻求最佳折衷，以期获得更好的泛化能力。其基本思想是 首先通过非线性变换将输入空间映射到一个高维特征空间，然后在这个新空间中求取最 优线性分类面，而这种非线性变换是通过定义适当的内积函数( 核函数) 来实现的。 1 广义最优分类面 s v m 是从线性可分情况下的最优分类面发展而来的，基本思想可用图2 2 的两维情 况说明。 图2 2s v m 原理 ， 图中，实心点和空心点代表两类样本，h 为分类线，h l 、h 2 分别为过各类中离分类 线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔( m a 略i n ) ，所谓 最优分类线就是要求分类线不但能将两类正确分开( 训练错误率为o ) ，而且使分类间隔 最大。分类线方程为x w + 6 = o ，我们可以对它进行归一化，使得对线性可分的样本集 ( 葺，咒) ，f = l ， ，x r d ，少 + l ，一l ，满足 咒【( w 薯) 十6 卜l o ，= l ，刀( 2 2 7 ) 此时分类间隔等于2 l l w | i 使间隔最大等价于1 1 w i | 2 最小。满足条件( 2 2 7 ) 且使妻0 w 0 2 最小 的分类面就叫做最优分类面，h l 、h 2 上的训练样本点就称作支持向量。 使分类间隔最大实际上就是对推广能力的控制，这是s v m 的核心思想之一。统计学 习理论指出，在维空间中，设样本分布在一个半径为r 的超球范围内，则满足条件 8 w | j o 是一个常数，它控制对错分样本惩罚的程度。广义最优分类面的对偶问题与线性可分情 况下几乎完全相同，只是条件磁0 ，扛l ，刀变为 0 c ，f = 1 ，刀 ( 2 3 5 ) 2 支持向量机 对于维空间中的线性函数，其v c 维为+ 1 ，但根据式( 2 2 8 ) 的结论，在i | w | 降彳的 约束下其v c 维可能大大减小，即使在十分高维的空间中也可以得到较小v c 维的函数集， 以保证有较好的推广性。同时我们看到，通过把原问题转化为对偶问题，计算的复杂度 不再取决于空间维数，而是取决于样本数，尤其是样本中的支持向量数。这些特点使有 效地对付高维问题成为可能。 对非线性问题，可以通过非线性变换转化为某个高维空间中的线性问题，在变换空 问求最优分类面。这种变换可能比较复杂，因此这种思路在一般情况下不易实现。但是 注意到，在上面的对偶问题中，不论是寻优函数( 2 31 ) 还是分类函数( 2 3 2 ) 都只涉及训练 基于_ 支持向最枫的文本分类研究 样本之间的内积运算( 一x ，) ，这样，在高维空间实际上只需进行内积运算，而这种内积 运算是可以用原空闻中麓丞数实现的，我们甚至没有必要靠道交换的形式。撒据泛瑟的 有关理论，只要一种核函数k ( 薯，x ，) 满足m e r c e r 条件，它就对应某一变换空间中的内积。 因此，在最优分类面中采用适当的内积函数岸( 焉，工，) 就可以实现某一非线性变换后 的线性分类，嚣计算复杂度却没有增加，此时目标函数( 2 3 1 ) 变为 q ( 口) = q 一去q q 彭乃趸( _ ) ( 2 3 6 ) f 燃l 厶，= l 而相应的分类函数也变为 ” 歹( 力掣s 舻 群咒爱( 麓力+ 矿 o 3 7 ) f 直l 这就是支持向量机 概括地说，支持向量机就是首先通过用内积黼数定义的菲线性变换将输入空间变换 到一个离维空闻，在这个空闻孛求( 广义) 最优分类匿。s v m 分类蘧数形式上类似予一 个神经网络，输出是中间节点的线性组合，每个中间节点列应一个支持向量。 3 核函数 s v l 镰中不同的蠹积核函数将澎藏不同的算法，露蘸砑究最多的核函数主簧有三类， 一是多项式核函数 岸( x ，薯) = 【( 戈薯) 十l r ( 2 3 8 ) 所得到的是譬阶多项式分类器；二是径向基函数( r b f ) 11 2 彭取，茏) ：e x p 一堡二李 ( 2 4 0 ) c r 所得分类器与传统r b f 方法的重要区别是，这里每个基函数中心对应一个支持向量，它 们及输出权值都是由算法自动确定的。也可以采用s i g 攥。话丞数作为内积，酃 x ( 以誓= t a n h ( v ( x 薯) + c )。( 2 4 1 ) 这时s v m 实现的就是包含一个隐层的多层感知器，隐层节点数是由算法自动确定 的，而且算法不存在困扰神经网络方法的局部极小点问题。 s 闷题可敬通过二次线牲规划技术来计算。可以通过在s 巾弓 入软分类边界 ( s o nm a 糟i n ) 或者将原来的数据空问映射到更高维空间( 该空间中的新特征包原空间 中特征的交互作用，该新空间中线性可分) 的方法将解决线性可分情况推广到解决线 性不可分的情况。 4 实现技术 支持向量分类的关键是解得珥，f = l ，2 ，捍，但是实践中训练集很大是直接使用标准 技术的障碍，因为仅仅存储系数矩阵就需要一个随样本大小二次增长的内存空间，即使 样本只有几千令，内存空闯也要超畿上百凳字节。 基于以上原因，下面我们介绍序贯最小优化算法( s m 0 ) 【2 6 】： 1 6 硕：e 学位论文 s m o 算法是将分解算法思想推向极致得出的，而每次迭代仅优化两个点的最小子 集。这项技术的威力在于两个数据点的优化问题可以获得解析解，从而不需要将二次规 划优化算法作为算法一部分。 对条件m q = o 需要在迭代中实现，意味着每步能优化的乘子最小个数为2 ；无论 何时一个乘子被更新，至少需要调整另一个乘子来保持条件成立。 每步s m o 择两个元素q 和口，共同优化，在其他参数固定的前提下，找到这两个元素 参数的最优值，并更新相应的口向量。这两个点的选择是启发式的，而这两个点的乘子 的优化可以获得解析解。 s m o 算法的伪码和软件包可以在网站w 、v w s u p p o r t - v e c t o r n e t 上获得。 2 4 5 最大熵模型 有关最大熵的概念可以追溯到很早以前，它反映了人类认识世界的一个朴素原则， 即在对某个事件一无所知的情况下，选择一个模型使它的分布尽可能均匀。而现实世界 中我们面对的更多的问题是，在已经知道事件的许多先验知识的情况下，如何选择一个 合适的模型来对事件做出预测。最大熵模型正是用来解决这个问题的。直观地来说，最 大熵模型就是按惯例的所有已知事实，保持对未知事件的未知状态。换而言之，就是给 定一些事实集，选择一种模型与现有事实一致，对于未知事件尽可能使其分布均匀。 从上个世纪9 0 年代开始，最大熵方法开始用于大规模真实文本的处理【2 7 ，2 引。它是 用来进行概率估计的。如果将一个文档分到某个类别看作是一个事件，记为口，将文档 中出现的词看成是这个事件发生的环境( 或称上下文) ，记为6 。那么包含词6 的文档属 于某一类口的概率就是p ( 口，6 ) 。 如果给定一个训练集，定义彳= “，呸，) 是文档所属的类别集，口= 6 l ，如，以) 是文档的特征词集，”甜所( q ，6 ，) 为训练集中二元组( q ，6 ，) 出现的次数，那么根据s h a n n o n 的定义，熵的计算公式为： 日( 尸) = 一p ( 6 ) p ( 订l6 ) l o g p ( 口1 6 ) ( 2 4 2 ) 万 求解满足最大熵原则的概率分布的公式如下： p = a 唱m a xh ( 尸)( 2 4 3 ) 为求上式的最大值，一种最优解的经典算法是拉格朗日乘子算法，计算公式如下： 1 ，七 、 矿2 志唧l 善似似 6 j q 4 4 ) 其中，万( 6 ) 是归一化因子，其计算公式如下： 厂七、 万( 6 ) = e x p i 乃z ( 口，6 ) l ( 2 4 5 ) 基于爻持向莆机的文本分类研究 参数矗为特征函数的权值，其值可以通过在训练集上进行学习获得。知道了五的值， 就得到了概率分布函数，完成了最大熵模型的构造。设一是事件集的大小，耄是特征函 数的数豳，从公式( 2 4 4 ) 可知，最大熵模型的时间复杂度为d ( | i h ) 。 2 5 分类性能评估 文本分类的评估释j 和具体应用有关。不同的应用，其性熊评估的方法和准翼| j 不尽相 同。可以有如下几个指标； 1 领域独立性 现有文档分类技术基本上是基予特征嚣售患，这使得文档分类需要借动予词典帮使 用专门的分词技术。方面，不同领域的词典在例的选择上各有侧重，而编撰通用的面 向不同领域的词典是很困难的，也不现实。就中文文档分类而言，分词是一项非常复杂 的工作。分词系统一般都比较复杂和庞大，切词速度慢，且准确度不高。因此，研究无 须词典支持、领域独立的文本分类系统无疑具有重要价值，这使得文档分类系统成为真 正意义上的通用系统。 2 时间无关性 语亩是一个开放系统，随着时闻的变化，语言耩语言中的谣氇在不断交纯。新的词 和表达会不断涌现；而有些已经存在的词和表达会慢慢被淘汰，消失于文档之中。这意 味着词典是随时间变化的。依赖于词典的文档分类系统，必须定期对词典进行更新。 3 w 扩展性 每一个文档分类系统都是建立在某一具体盼文档分类方法基础之上。只要人们还在 不断探索和研究，更准确、更高效的文档属性选择和文档分类新方法会不断出现：另一 方面，文档分类作为一个机器学习过程，它也是开放的，应当能够不断对新的实例进行 学习，以改善它的对新环境的颈测能力。因此，一个文档分类系统应该具备功貔纛性麓 上的可扩展性，这就要求文档分类系统建立在模块化、可扩展的体系结构基础之上。 4 空间和时间代价 算法的空间和时间代价是分两个阶段来考虑的，一些算法的训练时间是线 雯的，但 是分类时阙是非线性的，如k n n ；一些训练时间是鼋# 线性豹，分类时闻是线性的，如最 大熵模型和s v m ；还有一些训练时间和分类时间都是线性的，如n a i v eb a y e s ；一般来说， 在训练阶段，高昂的空问和时间代价是可以忍受的；但是，分类阶段则不然。 上述这些指标没法定量测量，蹶以文本分类般不是使用这些指标，焉使用信患检 索中的查全率和查准率这些指标来衡量系统的性能。文本分类巍用可以归纳为如下两 类，对于这两类应用它们查全率和查准率的计算公式亦有所不同。 l 。m u l t i p l eb i n a 翠c l a s s i f i c a t i o n ：存在多个文档类，假每个文档只裰于其中的一个类，分 类结果是给每个文档赋予一个文档类标号。这类碰用也称为单类赋值( s i n g l ec 鑫t c g o 翠 a s s i g n m e n t ) ； 1 8 硕：l 学位论文 2 m u r i c l a s sa n dm u f l i 1 a b e lc l a s s i f i c a t i o n ：存在多个文档类，且每个文档可以属于其中 酶多个类。分类结果建给每个文档所属的类努分并排序。摊在最翦面的类，说明该文档 属于该类的可能性最大。这类应用也称为多类排序( m u 衔一c a t e g o 巧r a n k i n g ) 。 2 5 1 单类赋值 文档分类审普遍使焉的性麓谨彳鸯指标有查全率( r e e a l l ，簿记力产) 、查准率( 融e i s i o 狂， 简记为p ) 。对于文档类中的每一个类别，使用列联表( c o n t i n g e n c y1 a b l e ) 来计算查全 率和查准率。表2 1 为一个列联表示例。 表2 。l 二值分类列联表 这时，和p 分别定义为： 口 ，= 一疗+ c 球 p 2 了 口+ 办 ( 2 。4 6 ) ( 2 4 7 ) 1 宏平均和微平均( m a c r o a n dm 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 ) 。宏观平均是先对每一个类 统计，、p 值，然后对所有的类求，、p 的平均值；微观平均是先建立一个全局列联表，然 爱根据这个全局列联表进行计算，、p 的僮。显然，宏平均是对类的平均，所以容易受小 类的影响，而徽平均煲| 是对文档的平均，容易受到大类的影响。 2 平衡点( b r e a k e v e np o i n t ) 对于分类系统来说，瘌p 值是甄相影响的。提高哙引起p 的减小，反之亦然。因此， 隽了更全面遗反映分类系统的性能，一种做法是选取薅瑟妒相等时的僮来表薤系统性毙， 这个值叫做平衡点( b r e a k e v e np o i n t ，简称b e p ) 值。当然，有时通过测试可能得不到 ，| 币咿相等的值。这时取最接近的，和p 值的平均值作为b e p 值，称为插值b e p 。 3 f 值( f m e a s h f e ) 另种常用的将查全率和查准率结合起来的性能评价方法是瑚l 量，其计算公式为： 名= 警 其中，是一个簿来调节查全率和查准率权重的参数。夕一般敢值为l ，这时( 公式2 。2 5 ) 转化为： 1 9 基于支持j i u 最机的文本分类研究 曩= 2 仞( ，+ p )( 2 4 9 ) 显然，b e p 是e 特殊形式，因为当，= p 时，有e = 艇p 。 2 5 2 多类排序 对于这类问题，首先应给定一个门限值，以确立文档和类之间的所属关系。对每一 个输入的测试文档，都会返回一个排序后的文档类列表。这时，两个指标分别定义为： p = 舞鬻篙簇器 亿5 。， ， 判断为该文档所属类的类别数目 p 7 r ：垫型塑鲨茎堂堑星堕垩堕耋墨! 塑旦r 2s 1 、r = = i ，、ii 该文档所属的所有类别数目 卜“v 整个分类器的评估应该是对所有测试文档的这两个指标的统计平均。通常使用的统 计平均为1 l 点插值平均查准率( i n t e r p o l a t e dl l - p o i n t a v e r a g ep r e c i s i o n ) 。 硕士学位论文 3 1 语料库 第3 章中文语料上的实验对比研究 语料库是实现文本分类的前提和基础。语料库可划分为训练集和测试集两个部分， 训练集用于分类模型的学习，测试集用于评价分类模型。 国外文本分类的研究起步较早，所以有多个标准的、开放的英文语料库可供使用， 这样就可以客观地比较不同分类方法和系统的性能。常用的开放英文分类语料库有 r e u t e r s 2 1 5 7 8 ，o h s u m e d ，2 0 n e w s g r o u p s ，w 曲k b 及a p 。著名的信息检索会议t r e c ， 自1 9 9 2 年起每年一次。t r e c 会议实际上是文本信息检索系统的擂台赛，可以说，在 t r e c 上展示的文本分类系统代表了文本分类领域的最新研究成果。一些大学，如c m u 、 b e r k l e y 、c o r n e l l 等和一些公司带着自己开发的文本分类系统参加会议，由大会 使用相同的训练集和测试集对这些系统进行评测。中国科学院计算所、清华大学、复旦 大学等单位近几年也有派队参加，并取得了不错的成绩。同时我们注意到，由于w 曲 技术的发展，啊也c 也逐步开始提供标准的英文网页语料来评测w r e b 信息检索系统。 与面向英文的文本分类相比，中文文本分类的研究起步比较晚。从第五次t r e c 会 议开始，增加了对中文文本分类系统的评测。实际上参加t i 辽c 5 的中文文本分类系统 处理的重点还停留在中文的分词问题上，采用的语料库是新华社的新闻稿。基于案例的 有指导的机器学习方法是实现中文文本分类的理论基础。凶此，中文文本训练集是实现 中文文本分类的前提条件。但是，到目前为止，还没有出现标准的中文语料库可供使用。 研究者们一般自己建立文档集，进行训练和测试，测试效果可比性较差，这一现状己经 引起国内文本处理界的重视。 凶此，我们从c n k i 上收集了5 0 0 0 篇文献标题作为分类语料，这些文献标题可以 分为法律、教育、农业、数学、医学共5 个类别，每类有1 0 0 0 篇。训练集和测试集按 照1 ：l 的比例来划分。其中的样例，如表3 1 所示。 表3 1 文献标题样例 类别 文献标题 法律司法功效的法理学分析：地方立法应注重科学性；用法律保障民工的安全 教育当代中国情感教育理论研究检视；关于高校考试改革的几点思考 农业冬枣采后病害及其防治技术；水稻田化学除草技术：生态法巧治蔬菜蚜虫 数学正定矩阵的子式阵仍是正定矩阵的一个充要条件；幂级数求和法例谈 医学痤疮的中医药治疗进展；慢性肾脏疾病与药理学反应：高向压辨治五法 2 l 基于支将阳鼍机的文本分类研究 3 2 实验设置 为了定量地对不同的特征选择方法和分类方法在中文语料上进行比较，我们首先实 现了一个最基本的分类器。该分类器的具体设计方案如下： 1 使用中科院计算所的“汉语训法分析系统i c t c l a s ”系统进行分词，并且按照 词性标注的结采只保留了名词和动词。 词是最小的能够独立活动的有意义的语言成分。但汉语是以字为基本的书写单位， 词语之间没有明显的区分标记，因此，中文词语分析是中文信息处理的基础与关键。为 此，我们使用中科院计算所研制的汉语词法分析系统l c l l a s ( 1 n s t i t u t eo f c o 黼p u t l n g r c h o l o g y ，c h i n e s el e x i e a la 髓l y s i ss y s l e m ) 进行分词和词性标注。l c t c l a s 所有的源 代码、论文和技术文档都可以在他b 鲤；丛缀盥n ! 乜：q 憋：盟或者 h 鲤；丛必腿亟：堑：曼壁鱼璺嫩垒型免费得到。 2 。对不同分类方法的比较，使用z 2 统计量对分词结果进行特征提取。 3 文献标题用向囊空间模型表示，用t f i d f 方法进行特征加权。 4 在l s l ( 后文会提到) 过程中，需要进行奇异值分解，使用m 棚，a b 朱完成这 项工作。词一文本矩阵采用稀疏矩阵格式，这样可以大大减少存储空闻，然后调用s v d s 丞数对原始矩阵进行奇异值分解。 5 对不同特征选择方法的比较，使用s v m 作为分类器，s v m 多类分类器的构造 采用o n e 哺g a i n s t a l l 方法，核函数使用高斯径向基核函数。 我们使焉s 珊的个实现l 两s v 热- 2 。8 2 f 期。毛扬s v 趱是一款麓单、易用、高效的霜予 s 讧分类和回归的软件，可以在廷鲤；旌竖塑照逸塾翅：璺幽趣主翊l i 型i i 垫墨y 堡免费得到。 3 3 特征选择方法实验对比研究 为了观察特征项的个数对分类器性能的影响，我们分射馊用c 疆、l g 、e 眼、m l 特 征选取算法挑选出不同个数的特征项。表3 2 表示嬲取不同的特征数时，分类器微平均