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

摘要 摘要 因特网上文本信息的迅猛增长给文本分类的精度与速度提出了新的标准与挑战。这 就要求文本分类在提高精度的同时，还要进一步提升训练与分类速度。为了面对时代的 挑战，作者对快速文本分类技术进行了探索和研究，取得了一定的成果。 本文首先介绍了文本分类的发展概况和文本分类过程中的相关技术，重点介绍和分 析了文本表示、分词方法、特征选择、和常用的分类算法等，为后续章节的研究提供了 理论和实验基础。随后，概括总结了现有快速文本分类技术及其方法，包括索引技术、 样本裁减技术和降维技术，并重点介绍了降维技术的理论和方法。最后，本文提出了一 种基于边界可信度相似的快速文本分类算法和在其基础上改进的基于类别分布特征的 快速文本分类算法，依据类别分布特征调整文本与类别的相似度，克服了数据集类别间 样本分布不均衡和类别中样本密度不均的缺点，提高分类的性能。实验结果表明该算法 提高了文本分类的效果，显示出了较好的鲁棒性，并显著提高了文本分类效率。 关键词：快速文本分类；文本挖掘；机器学习；信息检索；分布特征 a b s t r a c t 一- _ _ - - _ _ - _ - _ _ _ l _ - _ _ _ _ - - - _ _ _ _ _ _ _ - - _ - _ _ _ _ _ - _ _ _ _ _ - _ - _ _ _ _ _ _ - _ _ - - - _ _ - _ - _ - _ _ _ - _ _ _ _ _ - _ - _ _ _ _ l _ - _ _ _ _ - _ _ _ _ - 一 a b s t r a c t t h er a p i dg r o w t ho ft e x ti n f o r m a t i o no ft h ei n t e r n e tb r i n g sf o r w a r dn e ws t a n d a r d sa n d c h a l l e n g e sf o rt e x tc a t e g o r i z a t i o nw i t hr e s p e c tt oa c c u r a c ya n ds p e e d s ot h et r e n dr e q u e s t su s n o to n l yt ob o o s tt h ea c c u r a c yb u ta l s ot oa c c e l e r a t et h es p e e d i no r d e rt oc o n f r o n tt h e c h a l l e n g e ，t h ea u t h o rc o n d u c t sa ne x t e n s i v er e s e a r c ho nt h ep e r s p e c t i v e so ft e c h n o l o g i e so f f a s tt e x tc a t e g o r i z a t i o n a n da c h i e v e sac e r t a i ne x t e n tp r o g r e s s t h et h e s i sf i r s t l yi n t r o d u c e sg e n e r a ld e v e l o p m e n to fa u t o m a t e dt e x tc a t e g o r i z a t i o n s p e c i a l l y , s o m ei n t r o d u c e sa n da n a l y s e sa r em a d et oc o m p a r et h ep e r f o r m a n c e so fs o m e t y p i c a lt e x tc a t e g o r i z a t i o nt e c h n o l o g i e ss u c h a st e x tr e p r e s e n t a t i o n ，w o r ds e g m e n t ，f e a t u r e s e l e c t i o n , t e x tc a t e g o r i z a t i o na l g o r i t h m sa n ds oo n ，l a y i n gb a s i ct h e o r e t i c a la n de x p e r i m e n t a l s u p p o r t sf o rt h er e s e a r c hi nt h ef o l l o w i n gc h a p t e r s t h e nt h et e c h n o l o g ya n da l g o r i t h ms t a t u s o ff a s tt e x tc a t e g o r i z a t i o n , i n c l u d i n gm u l t i d i m e n s i o n a li n d e x i n g ，s a m p l er e d u c t i o na n df e a t u r e r e d u c t i o na r eg e n e r a l i z e d ，e s p e c i a l l yt h et h e o r ya n da l g o r i t h mo ff e a t u r er e d u c t i o n f i n a l l y , u s i n gt h ed i s t r i b u t i o n c h a r a c t e ra s t h ec r i t e r i o nf o rt e x tc a t e g o r i z a t i o n , a f a s tt e x t c a t e g o r i z a t i o na p p r o a c ha n di t si m p r o v e da p p r o a c hb a s e do nt h ed i s t r i b u t i o n c h a r a c t e ro f c l a s s ( d c c ) h a db e e np r e s e n t e d i nt h i sp a p e r b ya d j u s t i n gt h es i m i l a r i t yo fat e x tt oi t sc l a s s b a s e do nt h ed i s t r i b u t i o nc h a r a c t e r , t h ed i s a d v a n t a g e so ft h ei m b a l a n c eo ft h ec l a s s e sa n dt h e d i s t r i b u t i o no ft h es a m p l e sc a nb eo v e r c o m es u c ht h a tt h ep e r f o r m a n c eo ft e x tc a t e g o r i z a t i o n m a yb ee n h a n c e d t h ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h ea d v a n t a g eo ft h ep r o p o s e d a p p r o a c hi na c c u r a c ya n dr o b u s t n e s s ，e s p e c i a l l yi ns p e e d k e y w o r d s ：f a s tt e x tc a t e g o r i z a t i o n ；t e x t d i s t r i b u t i o nc h a r a c t e r ； m i n i n g ；m a c h i n el e a r n i n g ；i n f o r m a t i o nr e t r i e v a l ； h 独创性：声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签 名：肠幽 日 期：加多2 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名： 导师签名： 第一章引言 第一章引言帚一早，li l 1 研究背景 以因特网为主体的信息高速公路不断普及和发展，使得信息技术已经渗透到我们社 会生活的各个角落，它正以前所未有的速度和能力改变着我们生活和工作的方方面面， 我们正处在一个信息爆炸的时代。 一方面，因特网上面蕴涵的海量信息远远超过人们的想象，且不断快速增长。加利 福尼亚大学伯克利分校的一项研究结果表明，世界范围内信息生产量以平均每年3 0 左 右的速度递增，每三年就翻一番。尤其因特网上的信息量增长态势更是惊人：1 9 9 8 年初 因特网仅有3 2 亿个w e b 页面，1 9 9 9 年2 月该数字上升为8 亿个，到2 0 0 0 年7 月已经 发展为2 l 亿个，且仍在以每天7 0 0 万个页面、每8 个月就翻一番的速度增长着。截止 到2 0 0 4 年1 2 月，g o o g l e 宣称已经索引的网页数量已经超过8 0 亿。即使如此，仍有专 家指出，因特网还尚未到达它的快速增长期。 另一方面，在信息数据保持高速增长的同时，我们的吸收能力却并没有随之增强。 面对信息的汪洋大海，我们往往束手无策，得不到最急需的信息。这就是我们经常所说 的“信息发达，知识贫乏”。这种局面促使我们迫切需要一种高效而快速的办法来帮助 组织与管理这些海量信息，进而帮助我们有效地选择和利用所感兴趣的信息。其中一个 直接而成功的范例就是将信息分门别类。 鉴于大部分信息都以文本的形式存在。因此，文本信息的分类就显得更加迫切、更 加与人们的工作与生活密切相关。同时，爆炸式增长的文本信息给文本分类的速度提出 了新的标准与挑战。这要求文本分类在达到应有精度的同时，还要进一步提升分类速度。 这就是快速文本分类算法的基本要求。 1 2 研究意义 ( 1 ) 信息组织。对文本进行组织可以提高用户查找的效率。比如目前图书馆的归 类体系，就能够避免读者进行遍历式查找。再如当今的门户网站如新浪、搜狐、雅虎等 都把网页按照内容进行层次归类，这样就能让读者们很快浏览到所需要的信息。目前大 多数文档归类工作都由人工完成，这无疑将耗费极大的人力物力。若能够采用计算机自 动文本分类技术来辅助文档归类，必将大大地提高分类的效率。 ( 2 ) 信息过滤。随着信息获取方便性的提高，人们对获取更为相关的信息的需求 也在不断增长，迫切需要一种智能的信息过滤技术根据用户的需要对源源不断到来的文 本进行动态的分类、筛选。从而保留有用信息，屏蔽无关信息。从文本分类的角度来说， 它属于两类文本分类问题，它将所有文本区分为“相关文本”与“无关文本 。 ( 3 ) 邮件分类。电子邮件作为最广泛和成功的i n t e m e t 服务已经成为人们日常生活 中不可缺少的组成部分。但它在给人们带来巨大方便的同时，也同益显示出其负面影响， 那就是我们每天收到的邮件中有很大一部分是那种“不请自来 的“垃圾”邮件，如 江南人学硕十学位论文 推销广告或病毒等有害信息。这些垃圾邮件不仅对网络安全形成威胁，而且还造成了各 方面资金上的巨大浪费，对垃圾邮件进行“围剿 已经刻不容缓。目前邮件分类可以看 作通常的文本分类问题，它可以分为两种模式，其一是两类模式，即按照垃圾与非垃圾 来分类；另一种是多类模式，比如工作、会议、垃圾等。 ( 4 ) 话题跟踪。话题识别与跟踪的基本思想源于1 9 9 6 年，目的是要开发一种新技 术，能在没有人工干预的情况下自动判断新闻数据流的主题。从文本挖掘的角度上来说， 话题识别类似于文本聚类，而话题跟踪类似于多类文本分类。作为一项旨在帮助人们应 对信息过载问题的研究，这类新技术是现实中急需的，比如：自动监控各种信息源( 如 广播、电视等) ，并从中识别出各种突发事件、新事件以及关于已知事件的新信息，这 可广泛用于信息安全、证券市场分析等领域。另外，还可以找出有关用户某一感兴趣话 题的所有报道，研究这一话题的发展历程等等。 ( 5 ) 新信息检测。文档信息检索技术能够在一定程度上满足文档的检索需求，但 是往往会包含大量的无关的、重复冗余的信息，同时信息粒度偏大。为此，人们希望研 发出一种新的检索技术，该技术能够检索出粒度比文档更小的相关信息，并进一步排除 冗余、陈旧的信息。这里的粒度与文档相对应，我们一般称之为片断( p a s s a g e ) ，包括段 落( p a r a g r a p h ) 、句子集( s e n t e n c ec l u s t e r ) 和句子。为了评价与计算，常采用句子作为这种 信息检索的粒度，称之为句子级新信息检测( n o v e l t yd e t e c t i o na ts e n t e n c el e v e l ) ，它包 含着两个主要内容：相关句子检索与新信息内容的检测。 1 3 研究历史 1 9 5 8 年，l u h n 提出了采用词频统计来提取摘要的思想【l 】。他采用词语的频率与分 布信息来估计每个词语的相对重要度。然后再估计每个句子的相对重要度，得分高的句 子就被抽取为摘要。 6 0 年代，m a r o n 的工作把文本分类向前推进了大步【2 】。他开创性地采用了贝叶斯 公式来进行文本分类，用一组标引词来代表一篇文档，统计每个标引词在每个类别下的 概率，计算该组标引词同每个类别的后验概率，最后挑选后验概率最大的类别作为该篇 文档的类别。为简化后验概率的计算，m a r o n 作出了特征独立性假设与类别排它性假设， 即被广泛采用的“贝叶斯假设”。更值得一提的是他采用了s h a n n o n 熵来选择最有分类 能力的特征( 标引词) 。 从6 0 年代到8 0 年代，采用知识工程的文本自动方法一直处于领导地位。这一阶段 的主要特点是采用人工的方式来构建分类器，因此需要大量领域专家和知识工程师的参 与。这样带来两个方面的困难：一是耗费大量的研发经费；二是难以保证知识与规则的 正确性与一致性。但是这段时期内也涌现了一批性能不错的分类系统，如路透社使用的 c o n s t r u e 系统。它能够自动地对路透社每天的成千上万篇稿件进行分类。 9 0 年代以后，基于机器学习的自动文本分类方法逐步占据统治地位。因为基于机器 学习的自动文本分类的正确性完全可与人工专家相当，但分类速度却要远远高于人工专 家。同时，基于机器学习的自动文本分类无需领域专家与知识工程师的参与，而通常的 2 第一章引言 机器学习算法都具有良好的领域移植性。因此，基于机器学习的自动文本分类具有更低 的开发费用、更快的开发速度、更好的推广性能。 几乎所有重要的机器学习算法都被引入到文本领域中来。比如最小二乘拟和回归模 型、最近邻、贝叶斯、决策树、神经网络、线性分类器等等【3 】。其中回归模型与最近邻 分类器的分类质量表现较为出色。 9 0 年代中期v a p n i k 4 】提出了著名的支持向量机。支持向量机利用了结构风险最小化 的原则，对有限样本情况下的分类器设计具有很好的效果。它从两类线性可分问题发展 而来，目标是不但要找到一个可以正确地分开两类样本的分类面，还要求分类间隔最大。 j o a c h i m s 率先将其引入到文本分类中来【5 】。在这以后的很多文献中，支持向量机都表现 出了较好的分类质量。 1 4 研究现状 目前，文本分类是信息检索领域中的一个非常活跃的研究方向。众多学者们在这个 方向上进行了广泛而深入的研究，主要集中于以下几个方面。 1 4 1 特征选择与压缩 文本数据的难点就是特征的高维性与稀疏性，由此给分类算法带来两个方面的问 题：一是将会在训练与分类时间上带来很大的开销；二是过多的特征往往会导致人们常 说的“维数灾难 。因此对文本数据进行维数压缩就变得极为重要。目前的特征压缩算 法大体可以分为特征选择( f e a t u r es e l e c t i o n ) 6 1 与特征提i r ( f e a t u r ee x t r a c t i o n ) t 7 1 。特征选择 是根据某种准则从原始特征中选择部分最有类别区分能力的特征；特征提取是依据某种 原则构造从原始特征空间到低维空间的一个变换，从而将原始特征空间所包含的分类信 息转移到新的低维空间中来。 特征选择又可以细分为过滤法( f i l t e r ) 与融合法( w r a p p e r ) 。前者不依赖于分类器，只 是根据某种标准对特征进行排序并选择前刀个特征；后者需要跟分类器结合，根据分类 精度判断某个特征子集的优劣。过滤法因为其简单性在文本领域中被广泛的应用。目前 许多特征衡量标准被引入到文本中来，如文档频率、信息增益、互信息、c h i 统计等【6 】。 在特征提取方面，主成分分析、线性区分分析、概念索引等【_ 7 】众多方法都先后被提出或 引入到文本领域。 1 4 2 分类器组合 分类器组合( c o m b i n a t i o n ) 【8 】【9 1 又叫分类器委员会( c o m m i t t e e ) 、熔合( f u s i o n ) 、整体 ( e n s e m b l e ) 和聚合( a g g r e g a t i o n ) 等，它的思想起源于多专家决策。很显然，多个专家要比 单个专家作出更好的决策。在文本分类领域，就是指采用多个分类器进行训练，然后分 类时组合每个分类的决策。根据是否对训练集进行取样，分类器组合大体上可以分为两 类：分类器简单组合方式与重采样方式。 在分类器简单组合方式中，训练时各成员分类器独立进行，分类时组合所有成员分 类器的分类结果，实验表明组合分类器能够对其成员分类器进行取长补短。重采样方式 江南人学硕士学位论文 对训练集进行多次有放回采样，然后采用某个弱分类器算法在这些采样出来的多个训练 集上训练出多个分类器。b a g g i n g 与b o o s t i n g 就是这类方法的代表。b a g g i n g 采用均匀 采样；而b o o s t i n g 根据已经产生的分类器的分类效果对训练集进行采样，重点突出错分 样本。 1 4 3 小样本问题 有监督学习算法的一个主要困难是需要大量标记的训练样本来学习。但实际上获得 标记的训练样本常常需要较大的人力物力，所以分类器所能得到标记的训练样本往往是 有限的，而获得大量无标签的样本却很容易。有限的标记训练样本不能很好地刻画出数 据的总体分布特性，通过其学习得到的分类器的质量往往欠佳。因此，很自然地产生了 如何利用少量的有标签样本和大量的无标签样本训练出一个较好的学习机的问题。 传统的归纳式学习中，分类算法的目标是从有限的训练样本集中训练出一个对整个 样本空间而言期望判别误差尽可能小的分类器。然而，这样的高标准在许多实际问题中 没有必要，因为我们仅仅是对一些特定的样本进行识别和分类，希望能够对这一特定测 试集获得误差尽可能小的分类。如果把这一特定测试集有机地加入到分类器的设计和训 练过程中，则不但可以对这一特定测试集获得良好的分类效果，而且可以在很大程度上 提高原有归纳式学习算法的推广性能。这就是直推式学习的基本思想f jo 】。 1 4 4 层次文本分类 大多数文本分类算法仅关注非层次化的“平面”型分类。事实上，层次化分类较之 平面型分类更为实用、有效。这主要体现在两个方面：一是以层次形式组织的文档更符 合用户的思维模式，也更容易被用户访问与获取；二是层次化分类方法在高层即可滤除 许多与测试文档( 即被分类文档) 无关的类别，这使得该方法能在保证分类结果准确性的 前提下具备更快的分类速度。 根据袁时金【1 1 】的总结，层次化文档分类可以有三种实现途径：一种就是把层次分类 问题转化为只包含基类( 即叶节点类别) 的平面型分类问题；第二种是按照文档类别层次 结构树，将层次分类问题逐层分化为一个个的局部分类问题，在类树的每一内部节点分 别建立分类器，第三种是把层次化分类问题看成是一个更一般的多类、多标注分类问题 来进行求解。 1 4 5 样本不均衡问题 样本不均衡问题【1 2 】指的是某些大类占据了绝大部分训练样本，而其余小类却只包含 少数样本。事实上大部分文本分类问题都是样本不均衡问题，而大部分经典的机器学习 算法都是建立在均衡训练样本之上，因而这些算法在不均衡语料上的表现常常难以令人 满意。它们在大类上精度很高，但在小类上精度很差。 许多学者在这个问题上进行了大量研究，提出了许多解决办法。这些方法大致可以 分为三类：基于取样、基于误差加权与基于识别。基于取样的方法使用最广泛，包括上 取样、下取样、混合取样【1 3 】。虽然使用取样的办法非常简单直接，但也存在一些不足之 4 第一章引言 处，就是上取样会增加噪音；下取样会损失有用信息。基于误差加权的方法通过加大小 类样本的错分成本，来增加小类对分类器训练的影响。基于识别的方法通过单从小类来 学习分类规则。 1 5 研究内容 本文对快速文本分类方法及其相关技术进行了深入研究，主要内容包括： 第一章对文本分类进行了综述性介绍。本章首先介绍了文本分类的研究背景。然后 从信息组织、信息过滤、邮件分类、话题跟踪与新信息检测等方面概述了文本分类的重 要意义。然后评述了文本分类的发展历史。第四节从特征选择与压缩、分类器组合、小 样本问题、层次分类、样本不均衡问题等方面介绍了文本分类的研究现状及发展方向。 第二章对文本分类的几个方面，即文本表示、分词方法、分类算法、评价方法等， 进行了详细而全面的概述。文本表示主要从文本向量表示、特征权重表示等方面来介绍。 在文本特征表示方面，主要介绍了字、词、短语、概念、n g r a m 等等；在文本向量的 特征权重表示方面，主要介绍了布尔模型方法、词频权重方法、t f - i d f 方法等；分词 方法主要介绍了基于字符串匹配、基于统计、专家系统和神经网络等方法；特征选择主 要介绍了词频、信息增益、互信息等方法；文本分类方法主要介绍了常见的贝叶斯、最 近邻，决策树、支持向量机、神经网络等方法；最后针对分类评价方法介绍了召回率与 精确率、b e p 与f m e a s u r e 以及微平均与宏平均等指标。 第三章重点介绍了快速文本分类的相关技术，主要包括降维技术、索引技术和样本 裁减技术。降维是文本分类过程中的关键技术，也是实现快速文本分类的重要课题，本 章重点分析和总结了降维技术中类别可分离性判据、特征提取方法、特征搜索和特征排 序技术，阐述了各相关技术的特点和作用；在宏观上，针对大规模样本集处理，介绍了 r 树、s s 树、v p 树、g r i d 文件等高维索引结构；同时介绍了现有文献中祛除躁声提高 分类精度、缩减样本规模提高分类速度而使用的样本裁减技术，主要包括最近邻编辑法、 样本学习法以及样本修正法。尽管已有学者关注探索快速文本分类的方法，但目前尚没 有专门的文献研究快速文本分类技术，本章较为系统全面地总结阐述了相关技术的特点 和应用，有利于今后进一步的研究和探索。 第四章在总结前面快速文本分类相关技术的基础上提出了一种基于边界可信度相 似的快速文本分类算法。该算法针对现有经典分类算法的不足，考虑类别中心和边界距 离描述类别分布特征，引入边界可信度参数，并据此计算和修正待分文本与类别中心的 距离。实验证明该算法及在实现文本快速分类的同时也提高了文本分类精度，并显示出 较好的鲁棒性。 第五章在前一章的基础上总结了类别分布特征对文本分类的影响和均衡类别分布 的对策，提出了一种基于类别分布特征的快速文本分类算法，继承了原算法的优点，克 服了对可信度参数的依赖，提升了文本分类性能。 第六章对全文进行了总结，并对未来研究途径和方向进行了展望。 5 江南大学硕十学位论文 第二章文本分类方法概述 随着信息技术的迅速发展，大量文字信息急剧增加，需要进行文本分类有效地组织 和管理这些信息。这些杂乱的文本在自动分类之前，首先需要进行形式化处理，以便于 计算机处理。文本的形式化表示，一般都采用向量空间模型，其中通常采用词作为特征 向量，这就需要对文本进行分词处理。直接由分词得到的特征向量维数很大，需要其进 行特征选择。然后是设计文本分类模型，最后对分类方法进行评估。本章介绍了文本表 示、分词方法、特征选择方法、分类方法和分类评估方法五个关键技术。 2 1 文本的表示 为了便于计算机处理，需要对文本进行转化，将文本表示成计算机可以处理的形式。 目前文本表示模型主要有向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 、潜在语义索引 ( l a t e n ts e m a n t i ci n d e x ，l s i ) 模型和概率模型等。其中，向量空间模型( v e c t o rs p a c em o d e l ， v s m ) 1 4 】是最简单有效的文本表示模型。在该模型中，每一个文档都被表示为空间向量 中的一个点。该向量中的每一维的值表示了该词在文档中的权重，这样文档信息的表示 与匹配问题就转化成为空间向量的表示与匹配问题。 向量空间模型将文档以向量的形式定义到实数域中，提高了自然语言文档的可计算 性和可操作性，同时也忽略了特征项之间的顺序，损失了大量的文本结构和语义信息。 另外向量空间模型是建立在所有特征项两两j 下交这一假设的基础上的，没有考虑特征项 之间的相关性。但是由于向量空间模型方法简单、容易实现，所以一般都采用该模型来 表示文本。在特征向量与文本类别密切相关的前提下，文本可形式化地表示为： 一，、 f ：d 一 ( ， w i ，d ( 2 1 ) 、 、 7 ， 其中，孑表示文本，f 表示该文本的特征项，w f f ，孑l 表示特征项的权重。于是在向量空 、， 间模型中，文本d 被形式化为n 维向量空间的一个向量。 d = w l ， ( 2 2 ) 2 1 1 文本向量的表示方法 中文文本特征项可以采用字、词、短语、概念、n g r a m 等形式来表示【1 5 】【1 6 】。 ( 1 ) 字特征：使用字为特征项的优点是方法简单，容易实现，不需要做任何处理，可 以直接使用，工作量小，复杂度低。缺点是不能完整地表示一个语义范畴，对文本的表 示能力较差。 ( 2 ) 词特征：现有的大部分研究中都采用词作为特征项的方法，即每个关键词表示一 个分量。以词为单位比较符合自然思维习惯，便于系统处理。与字为单位相比，采用词 作为特征向量的优点是蕴含了较丰富的语义资源，能更准确、完整的表达文本信息。缺 点是需要进行分词和特征抽取处理，因此增加了处理的工作量和复杂度。 ( 3 ) 短语特征：文本表示中，起关键作用的是中频词，往往高频词和低频词对文本分 6 第二章文本分类方法概述 类没有什么贡献甚至是噪音数据，因此可以使用一些短语来代替高频词，降低其出现频 率，提高其对文本的表达能力。生成短语特征需要进行句法分析，筛选出合乎一定规则 的短语，这种方法比较复杂。 ( 4 ) 概念特征：合并同义词或近义词，使得特征项的选择尽可能地集中，对文本进行 语义理解。这样比单纯词的表达能力更强，但是概念本身的判断和处理相对复杂，划分 概念特征项和确定概念类的处理加大了文本处理的复杂度。 ( 5 ) n g r a m 特征：n g r a m 项一般由相邻字构成。例如从“计算机 中提取2 g r a m 项，可以得到“计算”、“算机”两个2 - g r a m 项。n g r a m 项作为文档的特征，可以避免 庞大的词典和复杂的分词程序。n g r a m 项的提取相对比较容易。但随着n 的增长， n g r a m 项的数目会呈指数增长，使算法的时间和空间消耗大大增加。 受自然语言处理技术的影响，选择词作为文本组成的特征，符合人们的思维习惯。 目前相对成熟的方法大都以词作为文本的特征向量，且忽略它们在文本中出现的顺序， 即不考虑结构信息。在多数分类模型中，这种文本的表示方法均取得了良好的效果。 2 1 2 文本向量的特征权重表示方法 假设w ( ，孑1 为词汇，在文本孑中的权重，而矿f ，孑1 为词汇f 在文本孑中的词频，n 为训练文本的总数，巩为训练文本集中出现词汇f 的文本数，m 为训练文本集中词汇的 总数。常用的向量权重表示法有以下几种【1 7 】【1 8 】： ( 1 ) 布尔模型方法：依据是词汇，是否在文本孑中出现，如果出现则w f ，d l 为1 ，否 则为0 。布尔模型的优点是简单速度快，缺点是作为文本的表示不精确，不能反映特征 项对于文本的重要性，缺乏定量的分析和灵活性。 ( 2 ) 词频权重方法：根据词汇，在文本孑中出现的频率来确定其重要程度。该方法实 现也比较简单，但实际意义不大。一些连词、虚词在一篇文本中出现的频率很高，但对 文本分类的贡献很小，因此单独使用词频权重的方法是有缺陷的。 ( 3 ) t f i d f 方法：即项频度逆向文档频度( t e r mf r e q u e n c y i n v e r s ed o c u m e n t f r e q u e n c y ) j h 权法，该方法是由s a l t o n 在19 8 8 年提出： w l ，d ) = t f l ，d 妙i ，d l ( 2 3 ) 其中，矿( ，孑) 表示词汇，在文本孑中的频数，矽( ，孑) 表示词汇f 出现的文本频数的 反比。目前计算权重较为常用的公式如下： ，、 w ( t ，孑) = 矿( f ，孑) 1 0 9 l 竺+ o 0 1i ( 2 4 ) 7、7 l 吩 公式( 2 4 ) 的含义是：如果词汇在所有文本中出现的频率越高，那么它所包含的信 息嫡就越少，如果词汇的出现较为集中，只是少量文本中有较高的出现频率，那么它就 会拥有较高的信息熵。考虑到文本长度对权值的影响，还应该对权值公式做归一化处理， 将各项权值规范n o ，1 之间： 7 江南人学硕士学位论文 w ( ，a ) - 矿( ，孑) ，。g ( 鲁+ 。) ( 2 5 ) 2 2 分词方法 分词是将连续的字串或序列按照一定的规范重新组合成词序列的过程。英文中单词 之间以空格作为自然分界符，不需要进行分词处理。中文的最小单位是字，而中文信息 处理的诸多重要领域都需要在词的基础上进行处理。因而需要使用中文分词技术将中文 文本中字与字、词与词之间的分界线找出来，这是中文信息处理技术的基础。常用的分 词方法主要有【1 9 】：基于字符串匹配的分词方法、基于统计的分词方法、专家系统分词 方法和神经网络分词方法。 2 2 1 基于字符串匹配的分词方法 这种方法又称为机械分词法或基于词典的分词法，主要思想是：事先建立一个词典， 对待切分的字符串按照己经确定的策略与词典中的词汇进行匹配，若在词典中找到某个 字符串，则匹配成功，即识别出一个词，否则继续下一步的匹配，直到所有汉字串都被 成功地切分出来。该方法的优点是简单易实现，实用性强；缺点是受词典的影响较大， 处理歧义的能力较差。 2 2 2 基于统计的分词方法 词是由稳定的字组合而成的，在上下文中相邻的汉字同时出现的次数越多，就越有 可能是一个词。因此字与字相邻共现的频率能够较好地反映是否为词的概率。当字符串 的紧密程度高于某一个阀值时，便可认为此字符串是一个词。这种方法只需对语料库中 的字符串组合频率进行统计，不需要事先建立词典，因而又叫做无词典分词方法。 这种方法的优点是提供了消歧的方式，处理自然语言具有很好的一致性和健壮性； 缺点是低频词很难被切分出来，而一些共现频度高但并不是词的常用字组常被抽出。 2 2 3 专家系统分词方法 该方法从模拟人脑的功能出发，将分词过程看作是知识推理的过程。首先构造推理 网络，将分词所需的中文词法、句法、语义知识分离出来。该方法把知识表示、知识库 结构与维护作为关键技术，其中知识库按常识性知识和启发性知识分别进行组织。对于 常识性知识采用“语义网络 表示，对于启发性知识采用“产生式规则 表示。每进行 一步推理，既启动常识性知识库又启动启发性知识库，对于非歧义字段使用一般语法知 识，对歧义字段则使用与其歧义有关的语法知识和语义知识。一个句子不管其中是否含 有歧义字段，其切分过程都可归结为生成该句子词语树的过程。这种统一的分词方法不 仅使整个分词处理过程简明，也使整个系统运行效率得到提高。 专家系统的优点是知识库易于维护和管理，但对外界的信息变化不敏感，反应缓慢， 8 第二章文本分类方法概述 不能从经验中学习。 2 2 4 神经网络的分词方法 神经网络的分词方法模拟人脑的运行进行分布处理，它需要建立计算模型，将分词 知识分散、隐式地存入神经网络内部，通过学习和训练改变内部的权值，从而达到正确 的分词效果。优点是对外界变化敏感、反应迅速，且具有自学习、自组织的能力；缺点 是需要大量的实例学习，对己有知识维护更新困难，网络模型表达复杂，训练时间长。 2 3 特征选择 直接由分词得到的特征向量有以下特点：一是表示文本的特征向量的维数一般都很 巨大，如此高维的特征向量使得分类效率较低；二是特征向量的出现频率不均衡，常用 词频率高，冷僻词汇频率低；三是特征向量的噪音多，影响分类的精度。因此需要通过 特征选择由高维向量中产生与之相近且维数小的特征子集，得到数量上尽量少、噪音少、 与其所属类别语义相关且含义尽量明确的特征向量。这样不仅可以降低向量的维数，提 高分类效率，而且减少噪音向量的干扰，提高分类精度。 特征选择( f e a t u r es e l e c t i o n ，f s ) 的思想剐2 0 】：构造一个评价函数，对初始向量中的 每个特征进行独立的评估以获得一个评估分值，然后对所有的特征按照其评估结果进行 排序，选取预定数目的特征子集。常用特征选择方法有词频法、信息增益、互信息、交 叉熵、文本证据权、c h i 统计及几率比等方法。 为便于描述，本节中令c l ，g 表示类别，k 为类别数，m 为特征词的总数， r 为 训练文本的总数，表示特定的词汇，p ( q ) 为q 类文本在训练集中的概率，尸( ，) 为训 练集中包含词汇，的文本概率，尸( qi ，) 为文本包含词汇f 且属于q 类的条件概率，尸( f ) 为训练集中不包含词汇t 的文本概率，p ( c ，1 1 为文本不包含词汇t 但属于c ，类的条件概 率。 2 3 1 词频方法 词频( d o c u m e n tf r e q u e n c y , d f ) 是指语料库中出现某词汇的文本数目，低频词对分类 的影响力较小可以忽略，中频词对分类影响较大，被认为是重要的词汇。该方法的具体 步骤是计算训练集中每个词的词频，排除词频数小于预定阀值的词，保留对分类有一定 影响力的词。该方法简单、计算复杂度低，随着训练集的增加而线性增加，适合于大规 模的语料库；但有的低频词汇集中出现在某一类别中，也可能包含重要的信息，简单的 除去会影响分类的准确率，常用作辅助特征选择方法。 2 3 2 信息增益方法 信息增益( i n f o r m a t i o ng a i n ，i g ) 指一个词汇为整个分类所能提供的信息量，该方法通 过统计词汇在一篇文本中出现或不出现的概率来决定是否被选取为特征向量。词汇t 的 i g 评价函数为： 9 江南人学硕+ 学位论文 佑( f ) = 一尸( q ) 1 0 9 尸( q ) + p ( ，) 尸( q1 1 ) 1 0 9 p ( c , l f ) 产1 。 严1 ( 2 6 )l、， + 尸( ；) 窆尸( q 卿。g 尸( qf ；) 词汇的信息增益值越大，其在某个类别上分布越集中，被选取的可能性越大。 2 3 3 互信息方法 互信息( m u t u a li n f o r m a t i o n ，m i ) 方法根据某个词汇f 和类别c ，之间的共现程度来衡 量词汇和类别之间的相关性。词汇t 的m i 评价函数为： ) - l 。吐帮 ， t 和c ，相互独立时，两者的互信息为0 。m i 值越大，类别和词汇之间的相关程度越 高，被选取的可能性越大。 2 3 4 交叉熵方法 交叉熵( e x p e c t e dc r o s se n 仃o p y ，c e ) 方法中词汇f 的c e 评价函数为： 哪矽( ，) ；k 恸) l o g 帮 亿8 ， 交叉熵法的原理与信息增益方法相同，唯一的不同之处在于：信息增益方法考虑了 词汇在文本中发生和不发生的两种情况，而交叉熵方法只考虑词汇在文本中发生一种情 况。不出现的词汇一般是噪声的来源，因此期望交叉熵比信息增益要优越一些。 2 3 5 文本证据权方法 文本证据权( w e i g h to f e v i d e n c ef o rt e x t ，w e t ) 方法中词汇，的、e t 评价函数为： 咧沪即) ；k 巾) 1 1 0 9 ( 2 9 ) 文本证据权方法的值反映的是类概率与在给定某一特征值下的类概率的差别，它只 考虑词汇t 在文本中出现的情况。 2 3 6c h i 统计方法 c h i 统计方法计算词汇t 与文档类别c ，之间的相关程度，并假设t 和c ，之间符合具 有一阶自由度的z 2 分布。词汇对于某类的z 2 统计值越高，它与该类之间的相关性越大， 具有的类别信息也越多。 令彳表示属于c 类且包含，的文档频数，b 表示不属于c ，类但是包含，的文档频数， c 表示属于c ，类但是不包含，的文档频数，d 是既不属于c ，类也不包含f 的文档频数。 则t 对于c ；类的c h i 值计算如下： 1 0 第二章文本分类方法概述 雄q ) 2 而滞 亿 当词汇f 和类别c ，之间完全独立的时候，z 2 统计量为0 。z 2 统计量和互信息的差别 在于它是归一化的统计量。对于多类问题，分别计算t 对于每个类别c ，的c h i 值，可以 用以下两种标准计算词汇t 对于整个训练集的c h i 值： 磊( f ) = ：。p ( q ) z 2 ( ，q ) ( 2 1 1 ) 磊( f ) = m a x ；。z 2t ，q ) ( 2 1 2 ) 2 3 7 几率比方法 几率比, ( o d d sr a t i o ，o r ) 方法只关心目标类值，而不同等对待所有类，评价函数为： 晰。g 篱渊 亿埘 其中，c 渺表示正例集的情况，c 獬表示负例集的情况。 为了适用于多类别的情况，通常采用的多类别几率l l ( m u l t i c l a s so d d sr a t i o ，m c o r ) 的变体形式为： 一锹(力=蔷kmc 尸( q ) i 锨( 圳= 骞尸( q ) l l 。g 暑碧猢l c214)t 一锹( ，) = 尸( q ) i 锨( 圳= 尸( q ) o g 杀鲁等言者罴l ( 2 产lj - 1 l ，lil 出儿l oi l l 乙，jj l 其中，表示除第c ，类外的所有类别，即把当前的第q 类当作正例集，其它类别合 起来作为负例集，从而有公式2 。1 5 。 砷= 帮 ( 2 1 5 ) 2 4 分类方法 文本向量经过特征选择之后，就可以使用这些特征向量来表示文本。文本分类方法 通过构造某种分类模型( 也称为分类器) ，并以此判断样本所属的类别。分类器的构造方 法有许多种【3 】【1 5 1 ，本节将介绍常见的贝叶斯方法、k 近邻方法、决策树方法、支持向量 机方法、神经网络方法、投票方法、r o c c h i o 方法和s l e e p i n ge x p e r t 方法，其中k - 近邻 方法在第4 章中还有详细介绍。 2 4 1 贝叶斯方法 贝叶斯方法( b a y e sm e t h o d ，b m ) 有两种：一种是朴素9 2 叶斯方法( n a i v eb a y e sm e t h o d ， n b m ) ，它假设每个特征都独立于其它特征，即特征独立性假设。但往往文本特征之间 的依赖关系是存在的，所以特征独立性假设会影响朴素贝叶斯分类的结果。另一种是贝 叶斯网络分类方法( b a y e sn e tm e t h o d ，b n m ) ，它考虑特征之间的依赖关系，该方法更能 真实地反映文本的情况，但是其计算复杂度比朴素贝叶斯高得多。 江南大学硕十学位论文 2 4 2k 近邻方法 k 近邻方法( 1 ( n e a r e s tn e i g h b o r , k n n ) 是由c o v e r 和h a r t 于19 6 8 年提出的，直至现在 仍在很多领域中应用。k 近邻方法是一种基于统计的分类方法，该方法根据测试文本在 训练文本集中与之最相近的k 篇文本的类别来判定它的类别。 2 4 3 决策树方法 决策树( d e c i s i o nt r e e s ，d t ) 方法是一种是以实例为基础的归纳学习算法，其任务是 通过一组无次序、无规则的实例推理出树型的分类规则。它采用自顶向下的递归方式， 在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支， 在决策树的叶结点得到结论。所以从根结点到叶结点的一条路径就对应着一条合取规 则，整棵决策树就对应着一组析取表达式规则。 决策树方法的优点是它在学习过