（计算机应用技术专业论文）基于贝叶斯理论的增量文本分类算法研究.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重麽查g 鱼太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：易压垮 签字嗍聊年5 月姗 学位论文版权使用授权书 本学位论文作者完全了解重麽邮电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权 重麽自电太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 易槲 l 签字日期：罗年多月乡矿日 导师签名： 唆姘 签字日期：。刁年厂月弓日 | 重庆邮电大学硕士论文 摘要 摘要 传统的文本分类算法需要大量的标注文本，但标注大量训练文本需要 艰苦而缓慢的手工劳动，从而制约了整个分类系统的构建。增量学习技术 可以利用少量的已标注文本对大量的未标注文本进行标注，可以有效解决 标注瓶颈问题，因此逐渐引起人们的关注。 由于贝叶斯方法能够充分利用先验知识，使它成为增量式文本分类的 重要选择。基于0 1 分类损失的增量贝叶斯分类算法是通过计算测试集中 文本的分类损失大小来确定新增训练集中文本加入到原始训练集的顺序。 但该算法存在下述三个问题： 首先，噪音数据影响分类器精度的问题。由于当前分类器存在知识储 备不足等因素而容易产生噪音数据，一旦这些噪音数据被过早地加入到原 始训练集中，就会降低当前分类器的性能，进而影响整体分类精度。 其次，新增训练集的规模影响增量学习效率的问题。当新增训练集规 模过大时会增加增量学习时间。因此在处理大规模新增训练集时，如何提 高效率成为增量学习的一个重要问题。 此外，如何利用新增训练集中有用知识的问题。新增训练集中存在一 种有用知识一一具有高度相似性的文本，把这些文本作为一个整体来处 理，它能够有效改善增量学习的性能。 针对以上问题，本文提出的基于序列选择增量贝叶斯分类算法，该算 法既通过选择合理的增量学习序列解决噪音数据影响分类器精度的问题， 又通过基于划分的思想对新增训练集进行分割解决新增训练集规模影响 增量学习效率的问题；还提出了基于快速聚类的增量贝叶斯分类算法来解 决新增训练集中有用知识的利用问题，即通过近邻传播算法对新增训练集 中的高度相似文本进行聚类，实现增量学习过程中的批量学习，从而显著 提高了增量学习的效率。最后通过实验验证这些算法的有效性。 关键词：文本分类，贝叶斯，增量学习，半监督学习，a p 算法 重庆邮电大学硕士论文a b s t r l c t a bs t r a c t l a 玛en 啪b e r so fl d b e l e dt e x t sa r er e q u i r e di i lm o s tc o i e m i o n a la l g o r i t h m so ft e x t c a t e g o r i z a t i o n ，w 1 1 i l et o1 a b e lt l l e s e 仃a i l l i n gt e x t sd e m a i l d sa 仃e m e n d o u s 锄。眦o f t o u 曲a n ds l o wm m m a l w o r k ，w m c hh a s 伊e a t l yr e s t r i c t e dm ec o n s t n l c t i o no ft 1 1 ew h o l e c l a s s i f i c a t i o ns y s t e m b e c a u s et h et e c l l l l o l o g yo fi n c r e m e n t a l l e a n 血gc a nm a k eam a s s o fu 1 1 l a b e l e dt e x t sl a b e l e du s i n gas p o to fl a b e l e dt e x t s ，w h i c hr e s o l v e st l l eb o t t l e - n e c ko f t e x t sm a r k i n gp r o b l e me 伍c i e n t l y ，嬲ar e s u l tt h em a j o r i t yo fr e s e a r c h e r sp a ym o r ea n d m o r ea t t e n t i o nt ot l l ei i l c r e m e n t a l l e a m i i l gt e c l l i l o l o 醪 b e c a u s eb a y e sm e t l l o dc a nm a k eg o o du s eo fi t sp r i o rk n o w l e d g e ，i tb e c o m e sa g o o dc h o i c eo fi 1 1 c r e m e n _ t a l t e x tc a t e g o r i z a t i o n t h ec o n v e n t i o m li n c r e m e n t a lb a y e s c l a s s i f i c a t i o na l g o 打c l l mb a s e do no - 11 0 s sr a t ed e t e m i n e st l l eo r d e ri 1 1w l l i c ht h en e w i i l c r e m e n t a l 舰i l l i i l gs e t s a r ea d d e d 恤t om eo r i 百1 1 a l 仃a i n i i l gs e t sb yc a l 9 u l a t i n gm e c a t e g o r i z a t i o nl o s s0 ft l l et e x t si i lt h et e s t i i l gs e t h o w e v e rt 1 1 e r ea r em r e ef 0 1 l o w i n g p r o b l e m si i lm i si i l c r e m e n t a ll e a n l i n ga l g o r i l m f i r s t l y n o i s yd a t am a ya f r e c tt 1 1 ep r e c i s i o no f 缸1 e “盯e n tc l a s s i f i e r b e c a u s eo fm e s h o r t a g eo ft h eb a y e sc l a s s i f i e r si n f o m a t i o ns t o r a g e ，n o i s yd a 协m a ye m e 唱ee a s i l y i f t l l e s en o i s y 出船a r ea d d e dt 0m eb a y e sc l a s s i f i e re a r l y ，i tw i l lr e d u c em e p e r f b n n a n c eo f c u r r e n tc l a l s s i f i e ra 1 1 dt h e ni i n p a c tm ep r e c i s i o no ft h ew h 0 1 ec l a s s i 丘c a t i o n s e c o n d l y ，t h es c a l eo ft l l en e wi i l c r e m e n t m 仃a “n gs e t sm j g h tr e d u c em el e 觚血g e 伍c i e n c y n l et 妇eo fi n c r e 】 i l e n t a ll e 踟：l i n gw i l lb ep r o l o n g e dw h e nt l l es i z eo ft h en e w m c r e m e n t a li st o ol a 唱e s oi ti sac m c i a li s s u et oi m p r o v et 1 1 ee m c i e n c yo fi n c r e m e m a l l e a m i i l gw h e nd e a l i n gw i ml a 唱es c a l en e wi n c r e m e m a l 仃a i l l i n gs e t s r h a “sm o r e ，h o wt 0m a k eu s eo ft l l eh o w l e d g eo ft l l en e wi n c r e m e n t a lt m i m n g s e ti sa l s o1 1 0 t i c e a b l e a c t u a l l y ，t l l e r ea r em a n ys i m i l a rt e x t si i lm en e wi n c r e m e l l t a l 仃a i m i 培s e t s ，ak i n do fv 朗yu s e f h lk i l o w l e d g e ，恤c hc a i lb ea d d e dt o 舭c l a s s i f i e ra sa w h o l e 1 k sw i l li m p r o v ei n c r 锄e n t a l l e a r n j i 】ge 伍c i e n c y 黟e a t l y f o rr e s o l v i n gt h e s ep r o b l e m s ，an e wi l l c r e m e n t a lb a y e sl e 枷n ga l g o f i m mo f c a t e g o r i z a t i o nb a s e do ns e q u e n c e1e a m i i l gm e t h o di sp r o p o s e di nt l l i sp a p e r o n t l l eo n e l l a 】 1 d ，b yc h o o s i n gr e a s o n a b l ei n c r e m e m a ll e 砌n gs e q u e n c e ，t h en e wi n c r e m e n t a l l e a n 曲ga l g o r i m mw e a k e i l st h en e g a t i v ei m p a c to fm en o i s yd a t a o nm eo m e rh a l l d ，i t c a ni i l l l r o v et h ee 伍c i e n c yo fi n c r e m e n t a l l e a n l i n gb yp 枷t i o l l i n gt h en e wi i l c r e m e n t a l t e x ts e t 证t 0s u b s e t s a d d i t i o m l l y ，i no r d e rt 0u t i l i z et h ek n o w l e d g ei 1 1 l en e w 1 1 重庆邮电人学硕士论文 a b s 仃a c t i i l c r e m e n t a ls e t ，a i li n c r e m e n t a lb a y e sc l a s s i f i c a t i o na l g o r i m mb a s e do nq u i c kc l u s t e r i n g i sp mf 0 刑a r d i i lt h i s a l g o r i t l l m ，s i i l l i l a rt e x t s i i lt h en e wi n c r e m e n t a lt e x ts e ta r e c l u s t e r e di n t og r o u p sb yu s i i l ga 伍i l i t yp r o p a g a t i o na l g o r i t h m ，i i i l p l e m e n t i n gb a t c h l e a h l i n g ，w t l i c hi m p r o v e si i l c r e m e n t a ll e a n l i n ge 伍c i e n c y - t h ee x p e r i m e n t a lr e s u l t s p r o v et h a tt l l ec l a s s i f i c a t i o ne 伍c i e n c ya n dp r e c i s i o na r eb o t ha d v a n c e db yu s i n gt h e s e i m p r o v e da l g o r i t s k e yw o r d s ：t e x tc a t e g o r i z a t i o n ，b a y e s ，i i l c r e m e m m1 e a m i i l g ，s e m i s u p e r v i s e d l e a n = l i n g ，a pa l g o r i t h m i i l 重庆邮电大学硕士论文目录 目录 摘要i a b s n a c t i i 第一章绪论l 1 1 论文选题背景1 1 2 国内外研究现状2 1 - 3 论文主要工作3 1 4 论文组织结构。：4 第二章文本分类与增量学习技术基础5 2 1 文本分类技术5 2 1 1 文本分类的定义5 2 1 2 文本的表示模型5 2 1 3 文本特征项的权重6 2 1 4 特征选择和特征提取7 2 1 5 文本分类算法”1o 2 2 增量学习算法1 2 2 2 1 基于e m 的增量学习算法13 2 2 2 基于协同训练的增量学习算法1 4 2 2 - 3 基于实例的增量学习算法15 2 2 4 基于支持向量机的增量学习算法1 6 2 2 5 基于集成学习的增量学习算法1 6 2 3 小结16 第三章基于序列选择的增量贝叶斯分类算法1 7 3 1 引言17 3 2 基于贝叶斯的增量学习模型1 7 3 3 增量贝叶斯算法存在的问题和解决的策略。1 9 3 4 基于序列选择的增量贝叶斯分类算法2 0 3 4 1 算法思想”2 0 3 4 2 算法描述2 0 3 5 实验测试2 3 3 5 1 实验性能评估指标2 3 i v 重庆邮电大学硕士论文 目录 3 5 2 实验特征选择”2 3 3 5 3 实验结果与分析2 3 3 6 小结2 6 第四章基于快速聚类的增量贝叶斯分类算法2 7 4 1 引言2 7 4 2 近邻传播( a p ) 聚类算法一2 8 4 3 基于快速聚类的增量贝叶斯分类算法3 0 4 3 1 算法思想”3 0 4 3 2 算法描述”3 2 4 4 实验测试一3 5 4 4 1 实验性能评估指标3 5 4 4 2 实验特征选择一3 6 4 4 3 实验结果与分析3 6 。4 5 小结3 9 第五章总结及未来工作4 0 5 1 总结4 0 5 2 未来工作一4 1 致 射”4 3 攻硕期间从事的科研工作及取得的研究成果4 4 参考文献一4 5 v 重庆邮电大学硕士论文第一章绪论 1 1 论文选题背景 第一章绪论 随着信息技术的发展，互联网数据及资源呈现海量特征。为了有效地 管理和利用这些分布的海量信息，基于内容的信息检索和数据挖掘逐渐成 为备受关注的领域。其中，文本分类( t e x tc a t e g o r i z a t i o n ，简称t c ) 技术是 信息检索和文本挖掘的重要基础，其主要任务是在预先给定的类别标记集 合下，根据文本内容判定它的类别。文本分类在自然语言处理与理解、信 息组织与管理、内容信息过滤等领域都有着广泛的应用。2 0 世纪9 0 年代 逐渐成熟的基于机器学习的文本分类方法，更注重分类器模型的自动挖掘 和生成及动态优化能力，在分类效果和灵活性上都比之前基于知识工程和 专家系统的文本分类模式有所突破，成为相关领域研究和应用的经典范例 【l 】 o 传统的文本分类方法，即非增量学习算法，或者称为一次性学习算法， 根据当前所获得的所有训练文本计算得到文本分类模型，如中心法 2 】、朴 素贝叶斯( n b ) 【3 1 、k 最近邻方法( k n n ) 【4 1 、支持向量机( s v m ) 【5 1 、神经网络 算法( n e u r a ln e t w o r k ，n n ) 【6 1 、决策树方法( d e c i s i o nt r e e ) 【7 】【8 1 等。然而它 们并不总是有效，原因如下： 训练文本标注瓶颈问题。传统的文本分类算法需要大量的标注文本， 但标注大量训练文本需要艰苦而缓慢的手工劳动，从而制约了整个系统的 构建。现实中比较容易获得少量的、蕴含信息有限的已标注文本以及大量 的、接近整个样本空间上数据分布的未标注文本。由于增量学习技术可以 利用少量的已标注文本对大量的未标注文本进标注，可以有效解决标注瓶 颈问题。 训练文本很难一次性获得。在实际应用中，我们很难一次性获得足够 多的训练语料，我们也不可能等到获得全部训练文本后再进行学习。因此， 训练数据分阶段获得的情况应当是我们研究的重点。当新的训练文本到来 时，传统学习方法需要对包括已训练文本在内的所有训练文本进行学习， 这将花费很大的计算开销；同时为了保存已训练文本也需要相当大的存储 开销。 难以处理大规模数据集。由于中文文本蕴含的特征属性比较多等原因 重庆邮电大学硕士论文 第一章绪论 使得一般增量学习算法难以处理大规模语料集。因此有效提高每个增量步 的文本数量是实现处理大规模文本集的重点和难点。其中，对每一批文本 进行增量学习得到一个新的模型，称为经过一个增量步。 内存限制。即使能获得足够的数据，由于内存限制，也不一定能将所 有数据一次装入内存进行学习，我们需要分批处理这些数据。 在这种情况下，我们需要根据已经获得的分类器模型，增量式学习新 的训练文本，并更新现有的分类器模型。增量学习使得一种学习算法更适 合于现实应用，使学习算法的时间和空间资源消耗保持在可以管理和控制 的水平；或者用于训练数据不足时需要做出分类决定的情形，比如在线环 境中。 1 2 国内外研究现状 一般认为，增量学习的研究始于b s h a h s h a h a n i 和d l a n d g r e b e 的工作 p j ，但未标记文本的价值实际上早在上世纪8 0 年代末就已经被一些研究者 意识到了【1 0 】。d j m i l l e r 和h s u y a r 】认为，增量学习的研究起步相对较 晚，可能是因为在当时的主流机器学习技术( 例如前馈神经网络) 中考虑 未标记文本相对比较困难。随着统计学习技术的不断发展，以及传统的学 习算法需要大量的标注文本这一需求的日渐强烈，增量学习才在近年来逐 渐成为一个研究热点。 n i g a m 首先利用基于期望最大化( e m ) 的方法从未标注文本中学习，利 用测试文本改进了b a y e s 分类器的分类效果【1 2 】；另一种用于未标注文本学 习的方法是直推( t r a n s d u c t i v ei n f e r e n c e ) ，使得分类器首先通过对已标注文 本的学习且仅对当前的少量未知文本进行误差最小的预测，而暂不考虑对 未来所有实例预期性能的最优性。之后，将这些文本加入到学习过程中来， 以改进分类器的效果；j a o c h i m 使用了直推式支持向量机( t s v m ) 进行文 本分类【1 3 】，文献 1 4 】中进行了改进；文献 1 5 中讨论了直推式b o o s t i n g 文 本分类；文献【l6 】和【17 】采用合作训练( c o t r a i n i n g ) 的方法，使用未标注的 文本进行e m a i l 与文本的分类，其思想是从两个视角将文本的特征划分为 两个信息充足的子集，分别在两个子集上建立分类器，利用标注文本进行 合作学习。另外，文献【18 】仅使用正例文本和未标注文本进行学习；文献 【1 9 】中利用了s v m 主动( a c t i v e ) 学习。上述方法在标注文本较少的情况下 对提高分类器的性能有很大的帮助，虽然部分地缓解了标注瓶颈问题，但 2 重庆邮电人学硕士论文第一章绪论 大量迭代为代价。另外，不同的从未标注文本学习的方法之间，还没有在 同一标准下的比较性工作。 目前，利用未标记文本的增量学习技术主要有三大类【2 们，即半监督学 习、直推学习和主动学习。这三类技术都是试图利用大量的未标记文本来 辅助对少量有标记文本的学习，但它们的基本思想却有显著的不同。在半 监督学习【2 0 】【2 1 】中，学习器试图自行利用未标记文本，即整个学习过程不需 人工干预，仅基于学习器自身对未标记文本进行利用。直推学习【1 3 】【2 2 】与半 监督学习的相似之处是它也是由学习器自行利用未标记文本，但不同的 是，直推学习假定未标记文本就是测试例，即学习的目的就是在这些未标 记文本上取得最佳泛化能力。换句话说，半监督学习考虑的是一个“开放 世界 ，即在进行学习时并不知道要预测的文本是什么，而直推学习考虑 的则是一个“封闭世晃，在学习时已经知道了需要预测哪些文本。实际 上，直推学习这一思路直接来源于统计学习理论【2 2 1 ，并被一些学者认为是 统计学习理论对机器学习思想的最重要的贡献。v v a p n i k 认为，经典的归 纳学习假设期望得出一个在整个样本分布上具有低错误率的决策函数，这 实际上把问题复杂化了，因为在很多情况下，人们并不关心决策函数在整 个样本分布上性能怎么样，而只是期望在给定的要预测的样本上达到最好 的性能。后者比前者简单，因此，在学习过程中可以显式地考虑测试样本 从而更容易地达到目的。直推学习作为一种重要的利用未标记文本的技 术，则已经受到了众多学者的关注。主动学习【2 3 】【2 4 】【2 5 1 和前面两类技术不 同，在主动学习中，学习器自行挑选出一些未标记文本并通过查询获得这 些文本的标记，然后再将这些有标记文本作为训练例来进行常规的监督学 习，而其技术难点则在于如何使用尽可能少的查询来获得强泛化能力。对 比半监督学习、直推学习和主动学习可以看出，后者在利用未标记文本的 过程中需要与外界进行交互，而前两者则完全依靠学习器自身，正因为此， 也有些研究者将直推学习作为一种半监督学习技术来进行研究。 1 3 论文主要工作 在宫秀军等提出的基于o 一1 损失的增量贝叶斯学习模型的基础上，针 对该模型中存在的一些不足，本文提出两种新的有效的增量贝叶斯分类算 法，不仅可以通过选择合理的增量学习序列等方法来弱化噪音数据对分类 器的影响和提高分类器的较强类型辨别能力，从而强化了较完备数据对分 重庆邮电大学硕士论文第一章绪论 类的积极影响同时弱化了噪音数据的消极影响；还充分利用未标注新增训 练集中的有用知识，以此实现了从单个文本增量学习转化为批量文本增量 学习，从而可以更加显著地提高增量学习的效率。 本文的研究工作主要从以下几个方面开展： ( 1 ) 针对噪音数据影响分类器精度的问题，本文通过选择合理的增量 学习序列来弱化噪音数据对分类器的影响和提高分类器的较强类 型辨别能力，从而强化了较完备数据对分类的积极影响同时弱化 了噪音数据的消极影响。 ( 2 ) 针对新增训练集的规模影响增量学习效率的问题，本文利用基于 划分的思想对新增训练集进行分割，从而实现处理大规模新增训 练集并有效提高了增量学习的效率。 ( 3 ) 针对如何利用新增训练集中有用知识的问题，本文研究了新增未 标注训练集中文本之间的相似关系，并利用a p 算法实现对中文文 本的快速聚类； ( 4 ) 针对增量贝叶斯分类算法选择单一文本作为一个增量步而难以提 高增量学习效率的问题，本文提出一种有效的基于快速聚类的增 量贝叶斯分类算法，该算法可以实现每个增量步选择批量文本进 行学习，从而更为显著的提高了增量学习的效率。 1 4 论文组织结构 本论文组织结构如下： 第一章介绍了增量学习技术的研究状况，以及本文的研究背景和主要 工作。 第二章介绍了文本分类与增量学习技术理论基础。 第三章提出一种基于序列选择的增量贝叶斯分类算法。该算法不仅通 过选择合理的增量学习序列而弱化噪音数据的影响；还通过基于划分思想 对新增训练集的分割处理，提高了增量学习的效率。最后给出的实验验证 了该算法有效提高了增量贝叶斯学习的性能。 第四章提出一种基于快速聚类的增量贝叶斯分类算法。本章首先介绍 了a p 算法的一般原理，并且测试了a p 算法用于中文文本聚类的有效性。 然后给出算法的主要思想及流程并对该算法进行相关实验验证。 第五章对本文进行了总结，提出下一步的研究计划。 4 重庆邮电大学硕士论文 第二章文本分类与增量学习技术基础 第二章文本分类与增量学习技术基础 2 1 文本分类技术 文本分类的研究包括若干学科领域，包括语言学中的自然语言处理， 图书馆科学中的分类学，数学领域的统计学等知识，以及计算机领域的模 式识别、人工智能、神经网络等研究课题。本节将分别介绍文本分类的基 本概念，文本分类所涉及的主要技术和方法。 2 1 1 文本分类的定义 文本分类是指按照预先定义的分类体系，根据文本的内容自动地将文 本集合的每个文本归入某个类别，系统的输入是需要进行分类处理的大量 文本，而系统的输出是与文本关联的类别。简单地说，文本分类就是对文 本标以合适的类标签。从数学角度看，可以说文本分类就是一个映射过程， 它将未标明类别的文本映射到分类体系下已有的类别中。文献 2 6 】给出了 文本分类的形式化定义。文本分类就是将一个二元组( 4 ，c ，) d c 映射到 一个布尔值的任务。该映射用数学公式( 2 1 ) 表示如下： ：d c 一留，) ( 2 1 ) 式中：d 是有待分类的文本的集合，d = ( 吐，以，以) ；c 是给定分类体 系下所有预先定义的类别的集合，c = ( c l ，c 2 ，c 。) ；是判别公式和判别规 则，根据已掌握的每类若干文本的数据信息而总结出分类的规律性而建 立。 d 可以是无限集合，而c 必须是有限集合。如果将二元组( 吐，c ，) 映射 值为丁( 枷p ) ，则认为文本4 属于类别c ，否则认为文本z 不属于类别c ，。 2 1 2 文本的表示模型 1 布尔模型 布尔模型可以看作是向量模型的一种特例，根据特征是否在文本中出 现，特征的权值只能取1 或o 。许多时候，使用二值特征的分类效果结果并 不比考虑特征频率的差。布尔模型的缺点是它分类时是基于二进制的规 5 重庆邮电大学硕士论文第二章文本分类与增量学习技术基础 则，不能很好的真实的反应文本的语法特征，因此应用范围比较有限。 2 向量空间模型 向量空间模型是由s a l t o n 【2 7 】等提出的，是现在得到广泛应用的基于统 计的模型。在向量空间模型中，每一个文本都被表示为由一组规范化正交 词条向量所张成的向量空间的一个点，即形式化为n 维空间中的向量，空 间的一维是倒排表( i n v e r t e di n d e x ) 中的一个元素，下式( 2 2 ) 所示： 皿= ( ( 疋，。) ，( 疋：，哌：) ，( 瓦，) ) ( 2 2 ) 式中瓦i 表示特征项词条；既表示特征词条的权重。 该向量中的每一维的值表示了该词语在此文本中的权重，用以刻画该 词语在描述该文本内容时所起作用的重要程度。权值越大，表示该词在文 本中的分量越重，即该词越能反映文本d ，的内容。权值的取值范围是 0 ， 1 。文本信息的表示与匹配问题就转化成为空间向量的表示与匹配问题。 向量空间模型是目前广泛使用的文本表示模型，具有如下优点：提 高了自然语言文本的可计算性和可操作性，文本内容被形式化到多维空间 中的一个点，通过向量形式给出，将文本以向量的形式定义到了实数域中； 为词引进权值，通过调节词对应权值的大小来反映词与所在文本的相关 程度，部分地克服了传统布尔模型的缺陷；匹配通过计算文本之间的相 似度，使属性相似的文本尽量聚拢在一起，以提高匹配效率。满足用户 需求多样化以及匹配手段多样化的需要。用户可以根据需求特点选择一组 可供使用的匹配手段。 但该模型也存在一些缺点，主要表现为：向量空间的维数往往很高， 导致计算量大，影响系统速度；向量中的特征权值较难确定。 2 1 3 文本特征项的权重 在向量空间模型中，常通过特征项的权重综合反映该特征项对标识文 本内容的贡献度和文本之间的区分能力。由于各个特征项在不同文本中的 出现频率满足一定的统计规律，因此可根据特征项的频率特性来分配特征 项的权重。 目前，特征项的权重计算通常有布尔函数、t f i d f 函数等多种方法。 令名表示词f 在文本后中出现的频率，为集合中文本的总数，肘为 经过预处理后保留的词的个数，z ，为词f 在文本集合中出现的总次数，下面 介绍几种计算权重的方法： 6 重庆邮电入学硕士论文第二章文本分类与增量学习技术基础 1 布尔权重 布尔权重是一种最简单的方法：如果该词在文本中出现，其权重就为 l ，否则为o ，下式( 2 3 ) 所示： = 1i ioi f 厶 0t h e n = 1e l s e = o ( 2 3 ) 从布尔函数公式不难看出，布尔函数具有权重大小与频率无关的特 性，不能体现特征项的区分性。 2 t f i d f 权重 t f i d f 权重是目前广泛采用的权重计算公式之一，它的指导思想是： 在一个文本中出现次数很多的单词，在另一个同类文本中出现次数也会很 多，反之亦然。 该方法是根据特征词的重要性与特征词的文本内频数成正比，与训练 文本中出现该词条的文本频数成反比的原理构造的。常用频率因子和文本 集因子的乘积表示，如下式( 2 4 ) 所示： = 厶幸l o g 【刀f ) ( 2 4 ) 3 t f c 权重 t f i d f 权重没有考虑到集合中的文本长度的问题，t f c 权重与t f i d f 权重十分相似，但是它将长度归一化因子作为计算词权重的因素，如下式 ( 2 5 ) 所示： 口膻2 兀g l ，z i ( 2 5 ) 4 l t c 权重 l t c 权重与t f c 稍有不同，它没有简单的取用词频，而使用了词频的 对数，因此减少了词频上的差异构成的影响，计算公式由( 2 6 ) 所示： 2 崦c 纠g 2 1 4 特征选择和特征提取 ( 2 6 ) 由于文本数据的半结构化甚至无结构化的特点，使得用特征向量对文 本进行表示的时候，特征向量通常会达到几万维甚至于几十万维。这样高 7 重庆邮电大学硕士论文 第二章文本分类与增量学习技术基础 维的特征空间对于几乎所有的分类算法来说都偏大，对分类机器学习未必 全是至关重要和有益的。因此文本分类系统应该选择尽可能少而精的特 征，寻求一种有效的特征选择与特征提取方法，降低特征空间的维数，提 高分类的效率和精度是研究的重点之一。研究表明，在经过特征压缩后的 特征空间中进行文本分类不但不会降低分类系统的分类性能，而且会有助 于提高分类的精确度28 1 。 以下针对几种特征选取中常见的评价函数【2 9 】进行分析： 1 文本频数 文本频数( d f ) 是指训练集中出现某个特征项w 的文本数在总的文本数 的概率。用公式( 2 7 ) 表示为： 胛( w ) = 出现w 的文本数训练集的文本总数( 2 7 ) 其主要思想是：在训练文本集中对每个特征计算它的文本频次，若该 项的胛值小于某个阈值则将其剔除，若其钟值大于某个阈值也将其去 掉。 2 信息增益 信息增益( i g ) 是一种在机器学习领域应用较为广泛的特征选择方法， 它是一个基于熵的评估方法，定义某个特征项为整个分类所能提供的信息 量( 不考虑任何特征的熵和考虑该特征后的熵的差值) 。根据训练数据，计 算出各个特征项的信息增益，按照信息增益从大到小排序，剔除信息增益 很小的特征。 信息增益评估函数定义如下式( 2 8 ) ： 阿( w ) = 一p ( 勺) 1 0 9 p ( c ，) + p ( w ) p ( 勺i 计1 0 9 p ( 勺i 计 + p ( w ) p ( 勺1w ) l o g p ( 勺l 叻 叫喀叱。g 等州品) 喜鹏协。g 等( 2 8 ， 式中w 代表特征项；p ( w ) 代表w 发生的概率；p ( c ，) 代表第类文本发 生的概率；p ( c ，1w ) 代表文本出现w 时属于c ，的概率。 从信息论角度出发，i g 方法的本质即用各个特征的取值情况来划分学 习样本空间，根据所获信息增益的多寡，来选择相应的特征。信息增益的 不足之处在于它考虑了特征词未发生的情况。 3 期望交叉熵 期望交叉熵反映了文本类别的概率分布和在出现了某个特定词条的 重庆邮电大学硕十论文 第二章文本分类与增量学习技术基础 条件下文本类别的概率分布之间的距离，词条的交叉熵越大，对文本类别 分布的影响也就越大。期望交叉熵用以下公式( 2 9 ) 计算： 陬幽砂( w ) 叫嘻p ( 州1 0 9 等 ( 2 9 ) 其中各符号意义与信息增益中定义相似。它与i g 的唯一的不同之处 在于忽略词没有发生的情况，如果特征项和类别强相关，p ( c ，1w ) 就大，若 p ( c ，) 很小的话，则说明该特征对分类的影响大。此时相应的函数值就大， 就有可能被选中作为特征值。 4 互信息 互信息( m i ) 是一种广泛用于建立特征项关联统计模型的标准，它体现 了特征项与类别的相关程度。对于特征项和某一类别c ，( c l ，c 2 ，q ) ，在c ， 中出现的概率高，而在其它类别中出现的概率低的特征项w 将获得较高的 互信息，也就有可能被选取为类别c ，的特征。w 和c ，的互信息定义如式 ( 2 1 0 ) ： 恻w c ) = 套p ( 训。g 篇 ( 2 1 0 ) 式中p ( w i c ，) 表示在c ，文本中特征项出现的概率 在实际计算中，这些概率可以用训练集中相应的出现频率予以近似。 类似于信息增益，互信息的计算复杂度为d ( 甩2 ) 。互信息有一个很大的缺点， 即没有考虑特征项发生的频率，特征分值受词条的边缘概率的影响较大， 这造成了互信息评估函数经常倾向于选择稀有单词。用这种方法进行特征 选取删掉了很多高频的有用词条。对于有相等条件概率p ( wc ，) 的词，稀有 词比常用词得分还要高，因此对频率相差很大的词，特征分值是不具备可 比性的。 5 z 2 统计法 z 2 统计法( c h i ) 用于度量特征项和类别之间独立性的缺乏程度，它同 时考虑了特征存在与不存在的情况。z 2 越大，独立性越小，相关性越大。 z 2 的统计量由式( 2 1 1 ) 给出： 积w c ) = 两者瓮篙丽 亿 式中c 代表类别；代表总文本数；彳代表w 和c 同时出现的次数；召 代表w 出现而c 没有出现的次数；c 代表c 出现而w 没有出现的次数；d 代 表w 和c 都没有出现的次数 词条的z 2 ( c 田) 统计值比较了词条对一个类别的贡献和对其余类别的 9 重庆邮电大学硕士论文 第二章文本分类与增量学习技术基础 贡献，以及词条和其它词条对分类的影响。当特征项w 和类别c 之间完全 独立的时候，仰一b c = o ，z 2 ( c 脚) 的值为o ；若肋一召c o ，说明w 与c ， 正相关，即词条出现说明某个类别也可能出现；反之，若肋一b c o 的特征项w 作为 特征值。z 2 统计量与互信息的差别在于它是归一化的统计量，但是它对低 频特征项的区分效果也不好。 2 1 5 文本分类算法 研究文本自动分类的关键问题是如何构造分类器，分类函数需要通过 某种算法进行学习获得。目前，常用的文本分类技术多是通过统计方法或 知识工程的方法实现的。知识工程方法主要依赖于语言学知识，需要编制 大量的推理规则，实现相当复杂。因为自然语言的复杂性，现阶段还无法 完全实现自然语言的机器理解，当前对文本分类技术的研究主要是偏重于 统计学方法实现的文本分类。相对于知识工程方法来说，基于统计学方法 实现的文本分类具有速度快、实现简单等特点，并且分类的准确率也较高， 能够满足一般应用的要求。在众多的文本分类算法中，本文主要介绍的算 法有中心向量比较算法( r o c c h i o ) 【2 1 、朴素贝叶斯分类算法( n b ) 【3 1 、k 近邻 算法( k n n ) 【4 1 ，支持向量机分类算法( s v m ) 【5 1 ，神经网络算法( n n ) 【6 1 。另 外常用的还有决策树( d e c i s i o nt r e e ) 【7 】【8 】等。 1 中心向量比较法 该算法的分类思路【2 】十分简单，首先在训练阶段求出训练文本各个类 别的中心向量。如：训练文本中“政治”类的文本有聊篇，那么政治类的中 心向量的第7 分量c ，为这所篇文本对应的特征向量的平均值，则c ，计算方 法下式所示( 2 1 1 ) ： 勺：率 亿， 式中c ，代表中心向量的第，分量；代表该类文本中第f 篇文本的第， 个权值；聊代表该类中包含的文本总数。 对新文本进行分类的过程就是一个比较相似度大小的过程，相似度表 示为新文本与各个类别中心向量的夹角余弦值。设第七类的中心向量为 以，新文本向量为口，则文本d f 与第七类中心的相似度可有式( 2 1 2 ) 计算 得出。 1 0 重庆邮电大学硕+ 论文第二章文本分类与增量学习技术基础 删一 疋户面等鼢 亿 式中c “代表第七类文本的第个权值的大小；九代笔特征总数。 相似度越大说明两个向量之间的夹角越小，两个向量越接近，因此， 分类结果将输出与新文本的相似度最大的类别，把它作为新文本的类别。 2 朴素贝叶斯算法 朴素贝叶斯分类器【3 】是以贝叶斯定理为理论基础的一种在已知先验概 率与条件概率的情况下得到后验概率的模式识别方法，用这种方法可以确 定一个给定文本属于一个特定类的概率。目前基于朴素贝叶斯方法的分类 器被认为是一个简单、有效而且在实际应用中很成功的分类器。 通过贝叶斯定理可知，给定文本4 的条件下，z 属于类别c ，的概率可 以通过计算p ( c ，i 谚) 的值而取得，使p ( c ，i z ) 取得最大值的那个类别就是盔 所属的类别，如式( 2 1 3 ) 所示： = 鹕m a ) 【p ( c ，) p ( 谚ic ，) ( 2 1 3 ) 式中p ( c ，) 代表类别c ，在整个训练文本集上出现的概率；代表输出 具有最大后验概率的类标签c 。 在朴素贝叶斯分类方法