（计算机应用技术专业论文）一种基于关键向量的文本分类模型的研究.pdf

哈尔滨理工大学工学硕士学位论文 一种基于关键向量的文本分类模型的研究 摘要 随着计算机与网络技术的快速发展，网络已成为人们存储与获取信息的 主要手段，存储于网上的文本数量也成指数级增长。这在为用户提供了海量 信息的同时，也给用户从中获取有用信息带来了困难。如何能够快速又精准 的在如此大量的信息中检索到用户所需的内容已成为当今重要的研究课题。 文本的自动分类技术能够有效地将文本信息组织起来，帮助人们准确高效的 定位文本信息，为用户获取所需信息提供有力的支持。自从上个世纪六十年 代被提出至今，文本的自动分类技术已经有了极大的发展，有许多分类算法 被提出，文本自动分类技术已经在搜索引擎，数字图书馆，信息检索等领域 得到了广泛的应用。 向量空间模型是目前进行大规模文本处理的一种通用模型，当前主流的 分类算法如k 近邻算法( k n n ) ，支持向量机算法( s v m ) 等均是基于该模型的 分类算法。虽然人们对这些算法已经有了深入的研究和广泛的应用，但是在 其性能上仍有许多不尽人意的地方。课题首先在系统的理论学习和对国内外 文献研究的基础上，分析了向量空间模型的特点和当前主流文本自动类算法 的缺点和不足。针对目前主流分类算法对待训练文档过于简单的特点提出了 一个基于向量空间模型的文本分类算法，引入了关键向量的概念，通过对训 练文档进行分析，找出每一类别的关键向量，并赋予其一定的权值，使其为 下一步的分类工作提供更多的信息，最后利用其对测试文档进行分类。 在此之后，应用实验对该算法进行了测试，并与传统分类算法进行了比 较。实验结果表明，与传统算法相比，该分类算法可以在一定程度改善分类 速度与精度。 关键词数据挖掘；文本分类；向量空间模型；关键向量 哈尔滨理工大学丁学硕：l ：学位论文 s t u d yo f t e x tc l a s s i f i c a t i o nm o d e lb a s e do n k e y v e c t o r a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e ra n dn e t w o r kt e c h n o l o g y , i n t e r n e t h a sb e c o m et h ep r i m a r ym e a n so fs t o r a g ea n da c c e s st oi n f o r m a t i o n ，t h ea m o u n t o ft e x ts t o r e di nt h eo n l i n eg r o w t he x p o n e n t i a l l y t h i sp r o v i d e su s e r sw i t h m a s s i v ei n f o r m a t i o n ，b u ta l s oi ti sh a r df o ru s e r st og a i nh e l p f u lm e s s a g ef r o mi t a tp r e s e n th o wc a nr e t r i e v et h en e e d e di n f o r m a t i o nq u i c k l ya n da c c u r a t i l yh a s b e c o m ea ni m p o r t a n tr e s e a r c ht o p i c t e x tc l a s s i f i c a t i o nt e c h n o l o g yc a no r g a n i z e t e x tm e s s a g e se f f e c t i v e l y , h e l pp e o p l ep o s i t i o n i n gt e x tm e s s a g e sa c c u r a t i l ya n d e f f i c i e n t l y s i n c eb e e nr a i s e di n19 6 0 sa u t o m a t i ct e x tc l a s s i f i c a t i o nt e c h n o l o g y h a sb e e nag r e a td e a lo fd e v e l o p m e n ta n dh a sb e e nw i d e l ya p p l i e ds u c ha ss e a r c h e n g i n e s ，d i g i t a ll i b r a r i e sa n di n f o r m a t i o nr e t r i e v a l v e c t o rs p a c em o d e li sag e n e r i cm o d e lu s e di nl a r g e s c a l et e x tp r o c e s s i n g ， t h ec u r r e n tm a i n s t r e a mc l a s s i f i c a t i o na l g o r i t h ma l lb a s e do nt h i sm o d e ll i k ek n e a r e s tn e i g h b o r s ( k n n ) a n ds u r p o r tv e c t o rm a c h i n e ( s v m ) a l t h o u g ht h e s e a l g o r i t h m sh a sab r o a da n di n d e p t hs t u d ya n da p p l i c a t i o nb u tt h e r e a r es t i l lm a n y u n s a t i s f yp l a c e b a s e do nt h e o r e t i c a ls t u d ya n dr e s e a r c hl i t e r a t u r e ，t h i st o p i c r e s e a r c h e dt h ef e a t u r e so fv e c t o rs p a c em o d e l ，a n a l y s i st h es h o t c o m i n g so f e x i s t i n ga l g o r i t h m s t a r g e t e da tt h ef e a t u r eo ft r e a tt r a i n i n gd o c u m e n tt o os i m p l e o fm a i n s t r e a ma l g o r i t h m s ，t h i sa l g o r i t h mr a i s e dat e x tc l a s s i f i c a t i o na l g o r i t h m b a s e do nt h ev e c t o rs p a c em o d e l ，i n t r o d u c t e dt h ec o n c e p to fk e yv e c t o r , b yt h e a n a l y s i so f t h et r a i n i n gd o c u m e n t s ，i d e n t i f yt h ek e yv e c t o r si ne a c hc a t e g o r ya n d g i v e naw e i g h tt ot h e mt op r o v i d em o r ei n f o r m a t i o nf o rt h ec a t e g o r y , f i n a l l y , c l a s s i f i c a t i o nt h et e s t i n gd o c u m e n t sb yt h i sk e yv e c t o r s t h e nt h i sa l g o r i t h mh a sb e e nt e s t e da n dc o m p a r e dw i t ht r a d i t i o n a l a l g o r i t h m s t h er e s u l t ss h o wt h a t t h i sc l a s s i f i c a t i o na l g o r i t h mc a ni m p r o v e c l a s s i f i c a t i o na c c u r a c ya n ds p e e dc o m p a r e dw i t ht h et r a d i t i o n a la l g o r i t h m k e y w o r d s d a t am i n i n g ，t e x tc l a s s i f i c a t i o n ，v e c t o rs p a c em o d e l ，k e yv e c t o r - i i - 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文一种基于关键向量的文本分 类模型的研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间 独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含 他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均 已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名： 日期羽。g 年习p 曰 哈尔滨理工大学硕士学位论文使用授权书 一种基于关键向量的文本分类模型的研究系本人在哈尔滨理工大学攻 读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔 滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了 解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部 门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可 以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内 容。 本学位论文属于 保密 厂 ， 在年解密后适用授权书。 不保密i 叼。 ( 请在以上相应方框内打) 作者签名：酬 导师躲j 彳鸟 日期：圳留年3t 刁。臼 隰2 呻习剐逦 哈尔滨理工大学工学硕士学位论文 第1 章绪论 2 0 世纪9 0 年代以来，i n t e m e t 以惊人的速度发展起来，它容纳了海量的 各种类型的原始信息，包括文本信息、声音信息、图象信息等等。如何在浩 若烟海而又纷繁复杂的内容中掌握最有效的信息始终是信息处理的一大目 标。基于人工智能技术的文本自动分类系统能依据文本的语义将大量的文本 自动分门别类，从而更好地帮助人们把握文本信息。近年来，文本分类技术 已经逐渐与搜索引擎、信息推送、信息过滤等信息处理技术相结合，有效地 提高了信息服务的质量。作为搜索引擎核心技术之一的文本自动分类技术逐 渐成为一个研究的热点，人们对于分类的精度与速度的要求日益提高，研究 出更加快速与准确的分类器已成为机器学习领域的一个发展方向。 1 1 论文研究的的背景及意义 文本分类最初是应信息检索( i n f o r m a t i o nr e t r i e v a l ) 系统的要求出现的，通 过分类对文本集进行有序组织，把相似的，相关的文本组织在一起。文本分 类作为知识的组织工具，为信息检索提供了更高效的搜索策略和更准确的查 询结果。其中，高效性来自于用户可以首先确定查询的可能类别，以减少需 进一步匹配的文本数量。有效性在于相似的文本很可能与相同的查询相关， 这样，检索的查全率和准确率都得到了提高。传统的文本分类是基于知识工 程的分类，即由专业人员手工进行分类，并加以组织和整理，为人们提供一 种相对有效的信息获取手段。但是，人工分类非常费时，效率过低，而且存 在分类结果一致性不高的问题。目前有很多大型网络信息系统( 如y a h o o ! ) 已经 建立了巨大的网络信息资源库，但他们大多以人工方法建立，这样做在准确 性上相对有一些保障，但足之处也很明显，那就是互联网巨大的信息量造成 人力消耗过大，分类效率低下。 网络文本信息的激增使得自动分类处理技术越发显示出其优越性，相对 人工分类，文本自动分类系统具有以下特点： 1 高效率，高速度文本自动分类的效率将是人工分类的百倍甚至千倍， 从而大量节约人力。 2 较高的准确度充分利用计算的高可靠性，消除了人为错误产生的可能 性。 3 良好的自适应性可快速适应文本的更新及类别设置的变化，适应不同 哈尔滨理工大学工学硕士学位论文 环境及需求。 目前，文本自动分类技术的主要应用领域有： 1 信息过滤信息过滤的主要目的是帮助用户在大量的信息中找到其所需 的信息，其本质是一个两类分类的问题，既可以用来将用户反感的信息过滤 掉，如黄色，淫秽，反动信息，也可以用来将用户感兴趣的信息过滤出来，主 动地推送给用户，方便了用户快速准确地获取信息。 2 信息检索信息检索就是把大量的文本信息按主题层次归类组织，可以 极大地简化对信息的检索。如按照类别对文档进行检索或对检索结果进行一次 文档分类，都可以提高检索的查准率。目前很多w e b 搜索引擎站点都使用了 w e b 文档层次化分类组织，只是目前很多以人工分类为主，如y a h o o ! 。 3 文本数据库随着研究的深入，文本数据库的功能已经不再局限于存 储，组织和查询文档信息，而是要提供多层次的服务，如文本挖掘等。文本 分类技术不仅对文本数据库如何存储，组织文档具有重要的意义，而且也是 文本挖掘的重要内容。 4 数字国书馆图书馆的数字化管理是大势所趋，图书期刊全文数字化的 比重正日益增大。对图书归类时，图书管理员不可能对各个学科都非常了 解，使用自动文本分类技术，可以帮助正确地对图书资料进行归类。 可见，文本分类的研究有着广阔的应用前景，可以创造巨大的经济和社 会效益瞳引。 1 2 国内外研究现状 自上个世纪6 0 年代以来，有许多自动文本分类方面的统计方法和机器学 习方法被提出，如k n i g a m 和a m c c a l l u m 等人提出了基于贝叶斯原理的用 少量带标签的文本和大量不带标签的文本进行文本分类的方法，这种方法具 有增量学习的能力；g s a l t o n 等人在2 0 世纪6 0 年代提出了向量空间模型 ( v e c t o rs p a c em o d e l ，v s m ) ，它把文档简化为以项的权重为分量的向量表示， 把分类过程简化为空间向量的运算，使得文本分类问题的复杂性大大减低。 1 9 6 8 年，c o v e r t 和h a r t 提出了基于向量空间模型的k n n 算法，这种算法方 法通过计算测试文档与训练集中的所有文档的距离，从中选择k 个距离最小 的进行综合，以决定其类别。 目前，国内外在文本分类技术以及相关的信息检索，信息抽取等领域进 行了比较深入的研究，取得了不少研究成果，并产生了一些可用的文本分类 系统。如：自动分类新闻稿件的文本分类器、自动分类w e b 页的文本分类 哈尔滨理工大学工学硕士学位论文 器、自动跟踪用户阅读兴趣的分类分析器等。这些系统大都建立在向量空间 模型的基础上，着重解决特征项的选择和权重，机器学习算法等问题，以提 高系统的性能和效率。至今，在以下方面取得了不错的成果： 1 向量空间模型的研究日益成熟由s a l t o n 等人于上世纪6 0 年代末提出 了向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 在文本分类，自动索引，信息检 索等领域得到了广泛的应用，已经成为简便高效的文本表示模型之一。它把 文档简化为以项的权重为分量的向量表示，把分类过程简化为空间向量的运 算，使得文本分类问题的复杂性大大减低。1 9 6 8 年，c o v e r t 和h a r t 提出了基 于向量空间模型的k n n 算法，这种算法方法首先计算待分类文本向量到训练 集中的所有文本向量的距离，然后从训练文本集中选择k 个最小的向量进行 综合，以决定其类别。1 9 9 5 年v i n p i k 提出了利用支撑量机来进行文本分类的 方法，该算法基于结构风险最小化原理，将原始数据集合压缩到支撑向量集 合( 通常为前者的3 5 ) ，然后用支撑向量集学习得到新知识。同时也给 出由这些支撑向量决定的规则z ，并且可得到学习错误的概率上界，即支撑向 量的期望数目。为了对文本分类系统进行定量性质的评测，在美国举办了两 个会议系列：消息理解会议( m u c ) 和文本检索会议( t r e c ) 。评测结果表明， 向量空间模型( v s m ) 是大规模语料库最佳的表示模型。目前，大多数文本处理 系统都建立在v s m 基础上，着重解决项的选取、权重评价等问题，以提高系 统的查准率和查全率等性能。 2 对特征选择进行了较深入的研究对于英法德等语种，文本可以由 w o r d s ，c l u s t e r so fw o r d s ，p h r a s e s ，c l u s t e r so fp h r a s e s 或其它特征项进行表 示，a n d r e w 和l e w i s 等学者对这些特征项进行了仔细的分析，并且在 r e u t e r 2 1 5 7 8 等标准语料库上进行实验，得到了比较一致的结论：使用优化合 并后的w o r d s 作为特征项在文本应用中效果最佳。此外，也有不少学者正在努 力突破以上特征的选择空间，定义自己的文本表示方法，如s a ms c o t t 定义了 一套符号系统，利用w o r d s 和附加的符号信息表示文本，也取得了一定的成 果。 3 较为完整的分类算法的研究和比较国外对于文本分类算法的研究开展 得较早，也很完整。如：b a y e s ，k n n ，s v m ，神经网络等算法，都有比较详 细的研究和性能比较，但是都没有得到统一的结论。总体上讲，这些算法在分 类性能上差别不大，以k n n 和s v m 最好。 4 较标准的测试语料目前常用的语料库有r e u t e r s 语料库、o h s u m e d 语 料库、n e w s g r o u p s 语料库等，其中r e u t e r s 语料库的2 1 5 7 8 版本使用最为广 哈尔滨理t 大学工学硕士学位论文 泛，它包含了1 3 5 个类别的2 1 5 7 8 篇文章，这也是本文所采用的语料库。 5 规范的测试评价方法因为文本分类从根本上说是一个映射过程，所以评 估文本分类系统的标志是映射的准确程度和映射的速度。映射的速度取决于映 射规则的复杂程度，而评估映射准确程度的参照物是通过专家思考判断后对文 本的分类结果( 这里假设人工分类完全正确并且排除个人思维差异的因素) 。与 人工分类结果越相近，分类的准确程度就越高。目前文本分类技术的主要评价 指标有准确率( p r e c i s i o n ) 、查全率( r e c a l l ) 、f 1 值以及宏观平均值( m a c r o a v e r a g e ds c o r e ) 矛l 微观平均值( m i c r o a v e r a g e ds c o r e ) 等标准。 与国外相比，我国的文本自动分类技术的研究起步较晚。1 9 8 1 年，侯汉清 教授对计算机在文献分类中的应用作了探讨，并介绍了国外在计算机管理分类 表，计算机分类检索，计算机自动分类，计算机编制分类表等方面的概况。此 后，我国陆续研制出一批计算机辅助分类系统和自动分类系统。国内的研究基 本上是在英文文本分类研究的基础上采取相应策略，结合中文文本的特点，形 成相应的中文文本分类系统，取得了一定的成果。但是，总的来讲，仍存在一 些问题： 1 缺少统一的标准语料库相对于国外成熟的英语文本自动分类技术，中 文文本分类的研究缺少标准的用于测试的语料库，研究者各自收集自己的文档 集，并在此基础上展开研究，因此，系统的可比性不强。同时由于个人的能力 有限，一般收集的中文语料库的规模普遍不大。 2 特征项的提取的研究不深与英文以词为基本单位不同，中文文档的最 小单位是字，而字通常不具有最基本的意义，这就需要对中文特征项的选择进 行研究。国内这方面的研究还没有深入开展，没有对字，词还是短语的选取进 行全面的比较和测试。另外，在分词算法方面也有待于进一步的系统而深入的 研究。 3 测试标准不统一在国内，由于缺少标准的用于分类的中文语料库，所 以文本分类系统的性能测试可比性较差，测试方法也较简单，通常仅给出整个 系统的准确率，很少分析训练文档数量和质量对文本分类系统性能的影响四1 。 总之，国内外在文本分类系统上已经进行了很多的研究、也取得了不小 的成果，但是仍然存在很多尚待解决的问题，相信随着研究的深入和相关技 术的进步，会进一步推动文本分类技术的研究，取得更多的研究成果。 1 3 本文研究内容及论文组织结构 本文的研究内容主要集中在对向量空间模型的研究上，通过对传统的基 哈尔滨理- t 大学工学硕+ 学位论文 于向量空间模型的分类方法的分析，指出其中的缺陷并针对其缺陷提出解决 的方法，然后通过理论分析和实验手段验证本文提出的改进向量空间模型在 性能上的提高。 目前的文本分类技术虽然已经有了广泛的研究和应用，但在其性能上仍 有许多不尽人意的方面。如k n n 算法的分类时间过大，精度不高，s v m 算 法对不同的应用领域核函数的选择较难，对较复杂问题分类精度不高以及对 大规模分类问题训练时间长等。通过对其分类思想的分析可以看出，这些算 法对训练集的处理都过于简单，仅计算了它们与测试文档之间的关系而没有 考虑它们之间的关系( 相同类别之间和不同类别之间) 更不会考虑每个测试文档 在分类时的不同权重。这是造成了现有分类器性能无法提升的主要原因。 本课题研究了一个基于向量空间模型的分类算法，主要思想是：首先将 训练文档投影到向量空间中，根据一定算法，找出每一类中最具“代表性”的k 个文档。这些文档应能在该类文档集中具有相当的代表性，我们可以将其称 之为关键向量。生成关键向量的原则是：如果一个向量在向量空间中与其同 类的文档距离较近( 较相似) ，而与其不同类的文档距离较远( 不相似) ，则该文 档在其所在类别中具有较高的代表性。在对测试文档进行分类的时候，计算 测试文档与每类中的这k 个关键向量的距离，找出与之距离最近的一类，作 为分类结果。 全文共分五章： 第一章是引言部分，首先对本课题的目的和意义做了介绍，然后讨论了 目前国内外研究现状，介绍了文本分类的基本概念、发展以及目前文本分类 领域的主要研究方向，最后，对本课题主要的研究内容和本文的组织结构做 了简要的介绍。 第二章概括性地介绍了基于向量空间模型的文本分类系统，主要讨论了 向量空间模型的基本概念，并介绍了各种文本分类算法，包括k 近邻算法， 支持向量机算法和朴素贝叶斯算法等，给出了算法的理论基础和算法公式， 它们的特点以及分类器的评价方法。 第三章针对目前现有分类算法的缺点和不足，引入了一个关键向量的概 念，提出了一个基于该关键向量的分类模型，介绍了该模型的理论基础、主 要思想以及特点，并建立了相应的文本分类算法。 第四章对分类算法加以实现，介绍了程序的主要结构和各主要功能模块 的工作流程。 第五章将该分类器应用于r e u t e r s 2 1 5 7 8 语料库，对其进行测试，并对测 哈尔滨理工大学工学硕士学位论文 试结果进行分析并与其它分类器的结果进行比较。最后，对所做的工作加以 总结，并提出了有待进一步研究的问题。 哈尔滨理工大学工学硕士学位论文 第2 章向量空间模型 向量空间模型是最为常用的一种文本表示方法，文本中出现的字词等通 常作为文本的特征项，研究表明，向量空间模型是大规模语料库的较好的表 示模型，它在大规模真实文本处理方面具有很强的优势。在向量空间模型 中，文本不再是字或词顺序连接的字符串，而成为了方便于计算机处理的向 量，语料库中所有的文本都统一在向量空间模型中，从而可以利用计算机快 捷地处理它们。虽然文本的向量化丢失了原先蕴涵的大量信息，但是通过实 践证明，在文本分类等信息处理领域中，基于向量空间模型的信息处理系统 仍然能够达到较高的性能。 本章主要讨论基于向量空间模型的文本分类技术，着重讨论文本的表 示，特征项权重和相似度的计算以及常用的基于向量空间模型的文本分类算 法的特点及性能。 2 1 文本表不 在大规模的文本处理中，如文本检索、聚类、过滤等，文本表示一直是 一个广受关注的问题。当然最理想的情况是采用全文本的表示，但这样会增 加很多计算和存储的负担，而且就目前来讲，在现有的研究技术条件下，采 用全文本表示对各种文本处理并无显著帮助。主流的方法是，通过抽取文本 特征来简洁的表示文本，也便于文本处理。 2 1 1 特征项抽取作为文本特征 一般要具备两个特点，一是彻底性，指它能够覆盖文本主题的程度；二 是专门性，指它能够反映文本的独特的、具体的内容。文本特征的抽取是文 本处理的首要任务，抽取文本特征为后续的文本分类、文本检索、文本过滤 等文本处理奠定了有力的基础。由于目前研究水平还不能完全理解文本的语 义，不可能完全依据语义层次，比如主题思想等来抽取相应的特征，一般的 方法是采用统计的方法来获得文本特征的信息，并辅之以句法、语义等方面 的技术。可以用来表示文本内容的特征项根据所处的不同语言层次，有很多 种类别，最低层次的特征项就是以字作为特征项，再高一级的就是以词、短 语或句子等作为特征，如果把语义等高级的语言理解技术考虑进去的话，特 征项也可以为相应词或短语的语义概念类。如何选择文本的特征项，要按具 体的要求来决定，不同的处理问题需要抽取不同的特征。比如文摘可能倾向 哈尔滨理工大学工学硕十学位论文 于选取句子作为文本的特征项，而文本检索和过滤则倾向于选择词或短语作 为特征项。同时，特征的抽取也要考虑处理速度、精度、存储空间等方面的 要求。一般来讲，特征项的语言层次越高，项所包含的信息就越完整越丰 富，分析的代价也越大。同时由于其层次比较高，所以分析的精度对下面各 层的精度依赖就越大，即每一层的错误都会不断向上层累积，导致最后上层 的结果精度可能会不高，影响特征项的质量。由于字、词、短语等特征项， 在文档中出现频度较高，呈现一定统计规律，比较适用于信息检索、过滤等 系统，所以本文主要采用以词作为文本的特征。下面我们主要介绍一下词汇 特征项的抽取，并简单介绍一下其它特征项的抽取。 1 词汇特征项词汇是文档最基本的表示项。不同的词汇对文档表示的作 用是不同的。一般来说，常用词在大多数文档中都有较高的频率；生僻词在 文档集中出现次数非常少，难以确定它们的统计规律，因此这两类词的区分 度都比较低。而中等频率的词汇则一般与文档的主题相近，区分度较大。因 此简单地把所有的词汇都作为文档特征项，效果并不是很好。还有一种情况 就是，不论哪种语言的文本，都存在一些没有实在意义，但使用频率很高的 虚词和功能词，如汉语中的“的”、“了”、“呢”、“把”等，英语中的“o f 、 t h e ”、“a t 等，在我们不使用句法分析等高层语言分析技术的情况下，这些词 汇往往把真正具有区分度的词汇淹没掉。解决这个问题的方法通常是构造一 个停用词( s t o pw o r d s ) 表，把这些词从特征集中过滤掉1 。 2 其它特征项字特征项：字是汉语的基本语言单位，一般来讲，字不能 完整地表示一个语义范畴，对文档的表示能力应该是比较差的。但许多系统 的实验表明，用汉字作为特征项来表示文档，和用词汇作为特征来表示文档 的分类、检索系统，在性能上并没有明显的下降。这可能有两个方面的原 因，一是汉语中的单字词占了很大比重；二是文档中一般都含有很多未登录 词，分词系统并不能很好地解决这些词的识别，造成了一些误差。短语特征 项：短语相对于词汇，表现能力更强，更能反映文档真实的主题。比如，一 篇文档中含有“自然”和“语言”两个词汇，我们并不能判断这篇文档是否和自然 语言相关，但是如果文档中含有短语“自然语言”，那么我们基本就可以认为文 档和“自然语言”相关了。概念特征项：概念主要描述了自然语言的本身的一些 现象，比如一词多义、同义词、反义词等。采用概念作为特征项要复杂的 多，不在本文的讨论范围之内。 哈尔滨理工大学工学硕士学位论文 2 1 2 特征项权重计算t f i d f 公式 在向量空间模型中，特征项对分类所起到的作用并不相同，因此，必须 针对它们对分类所起到不同的作用赋予不同的权重。赋权方式有布尔权重， t f i d f 权重及基于熵概念的权重。其中，应用最广泛的是t f i d f 权重，以 下将对其加以详细介绍。 t f i d f 公式由s a l t o n 于1 9 8 8 年提出，其中t f ( t e r mf r e q u e n c y ) 是词频， 或称特征频率。一篇文档中t f 较大的特征项在该类文档中具有较高的权重。 也就是说如果一个词在某类文档中经常出现，那么说明这个词对该类文档具 有代表性，t f 越大，表明这个词对文档越重要。 但是只有词频不足以表示一个词对文档的有用程度，文档中大量出现的 停用词( s t o pw o r d s ) 会干扰特征权重的计算。比如对于分类帮助很小的“的”， “地”，“得”或英文中的“o f ，“a n d ”等词，在所有文档中出现的频率都比较高， 对文档分类的贡献度却很小。为了处理这些词可以使用反比文档频率( i d f i n v e r s ed o c u m e n tf r e q u e n c y ) 。i d f 是特征项在文档集中分布情况的量化，特 征项的i d f 值越大，它在文档中的分布越集中，说明它在区分该类文档的能 力就越大。i d f 应用时经常采用对数形式，其计算方法为l o g ( n n ，+ 纱，其中， ，的取值通过实验来确定。为文档集中的总文档数，n ，为出现特征项矗的文 档数。 i d f 算法的核心思想是，在大多数文档中都出现的特征项不如只在小部分 文档中出现的特征项重要。也就是如果一个词在一篇文档中出现，但同时它 也出现在很多文档中，则降低了这个词的重要性。i d f 算法能够弱化一些在大 多数文档中都出现的高频特征项的重要度，同时增强一些在小部分文档中出 现的低频特征项的重要度。 t f i d f 公式就是特征项频率t f 与反比文档频率i d f 的联合使用，目前 常用的两种t f i d f 公式如下所示： 形化d ) = 丝丝丝丝些丝( 2 1 ) 。z t f ( t 。d ) x l 0 9 2 ( n n t + i ) 】2 、ft e d 或 形f ，f ，d ) _ 丝丝丝丝型丝丝丝丝上( 2 2 ) 。y , ( 1 + l 0 9 2 t f ( t ，d ) x l 0 9 2 ( n n t ) ) 2 vt e d 其中，职t 力为词r 在文档d 中的权重，而吠，田为词t 在文档d 中的词 哈尔滨理工大学工学硕士学位论文 频；为训练文本的总数，胁为训练文本集中出现f 的文本数。 另外，对于特征较为明显的文本类别，往往有少数项的出现频率远远大于 其他项，根据上述计算公式计算了权值会很高，这样会抑制其他项的作用， 因此在计算各项权重时，应对统计出的词频做适当的均衡处理，较为简单的 方法是对统计出的权值进行开平方处理。 2 1 3 相似度计算 向量空间模型中的相似度s i m ( d d 2 ) 用于度量两个文档d ，与功之间的内 容相关程度。当文档被表示为文档空间的向量，就可以利用向量之间的距离 公式来表示文档之间的相似度。文档的分类过程可以转化为计算文档向量之 间的距离。相似度大的文档，相对应的向量之间的距离就近；反之，相似度 小的文档，相对应的向量之间的距离就远。常采用的距离计算方法为欧氏距 离： 厅一 s i m ( d l ，d 2 ) = ( t w l t ) 2 ( 2 _ 3 ) yk = l 或余弦距离： l ( 形t r v 2 l i t l i t t ) 二一、 7 s i m ( d l ，砬) 2 毛尘f( 2 4 ) 荟：荟暧 相似度计算即计算测试文档向量与训练文档向量之间的位置关系从而对 测试文档进行分类。 2 2 向量空间模型 2 2 1 向量空间模型的基本概念 向量空间模型的基本概念如下： 1 文档( d o c u m e n t ) 泛指一般的文本或文本中的片段，一般指一篇文章。 2 项( t e r m ) 文档的内容特征常常用它所含有的基本语言单位( 字，词，词 组或短语等) 来表示，这些基本的语言单位统称为项，即文档可以用项集表示 为dp j ，t 2 , ，纠，其中如是项，j = 七 - 。 3 项的权重( t e r mw e i g h t ) 对于含有个项的文档d ( h ，t 2 ，t n ) ，项玖常常 被赋予一定的权重毗，表示它们在文档d 中的重要程度，即： d = d ( 力，w ，；t e ，w 2 ；，t n , w u ) ，简记为d = d ( w l ，w 2 ，w u ) 。即此时项玖的权重为w k ， 哈尔滨理工大学工学硕十学位论文 j 0 为l a g r a n g e 乘数，对和b 求偏微分并令其为o ，原问 题转换成如下对偶问题：在约束条件： l 咒q = 优q d ，f = j 刀 ( 2 - 9 ) i = l 下对嘞求解下列函数的最大值： q f ，口) = q 一去q 吩只m f ，b q ) ( 2 - 1 0 ) i = l j = l 如果仅产为最优解，再由公式 国+ = 珥+ x y j d j ( 2 - 1 1 ) t = l 得出最优分类面的权系数向量。为了判断某个样本是否属于类c ，计算 如下最优分类函数： l r d ) = s i g n ( 缈宰d 夕+ b * l = s i 朋j r 乏：q 只f ，口d ) + b 半夕 ( 2 - 1 2 ) 面 若倒= j ，d 就属于该类：否则就不属于该类。对于线性不可分的情 况，可以引入松弛因子，在求最优解的限制条件中加入对松弛因子的惩罚函 数。完整的支持向量机还包括通过核函数的非线性变换将输入空间变换到一 个高维空间，然后在高维空间中求取线性分类面。以上的乐观想法并不适合 大样本集，因为随着样本集的不断增大，所需的内存也不断增加。可以通过 将训练集分成若干块，提取每一块的s v m 来解决计算复杂度和存储空间问 题。最后，将这些支持向量融合起来。另外前面谈到的s v m 是基于二分分类 的，可以把它与二叉决策树的基本思想结合起来构成多类别的分类器，称这 种方法为s v m 决策树方法n 纠训。 在对s v m 的研究中，提高它的分类能力( 泛化能力) 是所有研究的出发点 和归宿。s v m 和其他分类方法相比具有较高的分类精度，但目前在s v m 的 应用中还存在一些问题，如对不同的应用问题核函数参数的选择较难位，对较 复杂问题其分类精度不是很高以及对大规模分类问题训练时间长等。已有的 解决方法包括建立分类性能的评价函数，然后对s v m 中的核函数的参数进行 优化，或者使用直推方法对给定待样本设计最优的s v m 。所有这些方法的设 计和计算都非常复杂，实现的代价都很高晗2 一引。 3 n a t i v eb a y e s 算法( 朴素贝叶斯算法) 朴素叶贝斯算法是贝叶斯( b a y e s ) 哈尔滨理工大学工学硕士学位论文 分类方法的一种，它假设特征对于给定类的影响独立于其它特征，即特征独 立性假设。对文本分类来说，它假设各个单词彤和孵之间两两独立，设训练 样本集分为k 类，记为c = c 1 ，c e , ，g ，则每个类g 的先验概率为p ( g ) ， i = 1 ，2 ，k ，其值为g 类的样本数除以训练集总样本数n 。对于新样本d ，其属 于c f 类的条件概率是p ( d l c ，) 。根据贝叶斯定理，c f 类的后验概率为p ( g l 力： p ( qid ) ：型掣( 2 - 1 3 ) p l 口j p ( 园对于所有类均为常数，则上式可简化为： p 俺i 矽p i c a p ( c a( 2 - 1 4 ) 为避免p ( c j ) 等于0 ，采用拉普阿斯概率估计： p 俐= 蒜篙 ( 2 - 1 5 ) 式中i c l 为训练集中类的数目，i 如l 为训练集中属于类g 的文档数，i d c l 为训练集包含的总文档数。 贝叶斯分类模型的优点是：算法逻辑简单，易于实现，分类过程中时空 开销小，算法稳定，对于不同的数据特点其分类性能差别不大，也就是说健 壮性比较好。它的缺点是在独立性假设的时候，在许多实际中并不能够成 立，这样就会引起分类的误差。 4 r o c c h i o 算法r o c c h i o 算法是情报检索领域最经典的算法。在该算法中， 我们首先为每一个类g 建立一个原型向量( 即训练集中g 类的所有样本的平 均向量) ，然后通过计算文档向量d 与每一个原型向量的距离来给d 分类。下 式是r o c c h i o 公式： 吻吻 = 口w 如+ 尘l 一7 皇l ( 2 - 1 7 ) b en 一 其中w 加指类g 中心向量的权重，勖是指文档向量的权重，玎是所有训练 样本的数目，n c 是训练集中属于类c ，的正例样本的个数，z n c 为反例样本的个 数。 在此，a 、) ，分别用来控制初始向量、正例集和反例集所占的权重。通 常，为了强调正例文本的重要性，正例的权值取得较大，而反例的权值取得 比较小。 哈尔滨理t 大学工学硕士学位论文 2 4 本章小结 向量空间模型是文档分类技术常用到的一个工具，本章详细介绍了向量 空间模型的基本概念和原理，着重介绍了文本分类过程中常用到的特征项的 抽取方法和计算特征权重的t f i d f 公式。最后介绍了常用的几种基于向量空 间模型的文本分类算法的主要思想和特点，通过这些研究，为下一步的研究 作技术准备。 哈尔滨理1 = 大学工学硕士学位论文 第3 章基于关键向量的文本分类算法 以k n n 算法和s v m 为代表的基于向量空间模型的几种算法自提出以来 在信息检索以及文本分类等领域得到了广泛的应用。但随着信息技术的发展 和用户需求的变化，现有的算法也逐渐显露出存在的缺陷，许多学者也就此 进行了科学研究并提出了不少改进的算法。本章将在对传统的基于向量空间 模型算法的不足进行深入分析的基础上提出一种新型的向量空间模型的分类 算法。 3 1 基本思路介绍 3 1 1 传统的基于向量空间模型算法的不足 现有的基于向量空间模型算法的主要基本思路是：将训练文档与测试文 档表示为同一多维向量空间上的向量，通过比较测试文档与训练文档之间的 位置关系，对测试文档进行分类。在这一过程中，对所有训练文档相互之间 的位置关系未加进一步分析而是对其一视同仁的对待。这样简单的处理，其 不足之