（计算机软件与理论专业论文）中文web文本分类新技术的研究和应用.pdf

摘要 摘要 随着网络信息技术的高速发展，i n t e r n e t 上的w e b 页面数量呈指数增长，如何有效的 组织和处理这些海量信息，如何更好地搜索、过滤和管理这些网络资源，成了一个亟待 解决的问题。其中，w e b 文本分类技术是信息检索和数据挖掘的核心内容，基于机器学 习的文本分类方法已经取得了较好效果，但是它仍然存在如何提高分类精度和分类速度 两大难题。 。 本文研究的对象是中文w e b 本文，针对中文文本的特殊性，首先研究了中文分词 方法，并提出了一种基于二元语法的n 一最大概率中文粗分模型，该模型能够较好地得 到少量高召回率、高效率的粗分结果，更大程度地保留歧义字段和未登录词，进而提高 后续分词质量。然后针对中文w e b 本文的信息量巨大且内容更新速度快等特点，提出 了一种新的w e b 文本表示方法，即基于新词发现的表示方法：用词和新词共同来表示 w e b 文本，理论和实验表明该方法可以帮助识别未登录词并扩充现有字典，能够增强 w e b 文本表示能力，改善w e b 文本的特征项质量，最终提高w e b 文本分类效果。 在现有分类算法中，k n n 算法是一种简单、有效、非参数的分类算法，在w e b 文 本分类中得到广泛的应用并取得较好的分类效果；但是该算法存在两个显著不足，其一： 计算量巨大，它要求计算未知文本与所有训练样本间的相似度进而得到k 个最近邻样 本；其二：当类别问有较多共性，且p - i ) l l 练样本间有较多特征交叉现象时，k n n 分类的 精度将下降。针对k n n 这两个问题，本文提出了一种改进的k n n 分类算法，即先通 过r o c c h i o 算法快速得到k 0 个候选类别，然后在k 0 个类别中采用改进的相似度计算方 法来提高分类精度。由于w e b 文本资源通常采用层次结构来组织，因此本文也探讨了 层次分类，提出了层次结构和k n n 算法相结合的w e b 文本分类算法，利用层次结构来 提高分类速度，而k n n 算法弥补层次分类中的精度问题。实验表明，以上两种改进的 k n n 分类算法都能很大程度地提高分类效率，同时也一定程度上提高了分类精度。 关键词：中文分词；特征选择；w e b 文本表示；w e b 文本分类；k n n 算法；层次结构 ab s t r a c t a b s t r a c t a sr a p idd e v do p m e n to fn e t w o r ka n din f o r m a t io nt e c h n o lo g y ，w e bp a g e so nt h ein t e r n e t w e r ee x p o n e n t i a lg r o w t h ，h o wt oo r g a n i z ea n dd e a lw i t ht h e s ev a s ta m o u n t so fi n f o r m a t i o n e f f e c t i v e l y ，a n dh o w t os e a r c h ，f il t e ra n dm 钔a g et h e s er e s o u r c e sb e t t e r ；t h e s eh a v eb e c o m ea n u r g e n tp r o b l e m t h e v v e b t e x tc l a s s i f i c a t i o ni s t h e c o r e c o n t e n to fd a t a m in n ga n di n f o r m a t i o n r e t r i e v a lt e c h n o l o g y ，a n dt e x td a s s i f i c a t i o nm e t h o db a s e do nm a c h i n el e a r n i n gh a sb e e n a c h i e , t e dg o o dr e s u l t s , b u th o wt oi m p r o v ec l a s s i f i c a t i o na c c u r 瓮：ya n dd a s s i f i c a t i o ns p e e di s s t i l la p r o b l e m t h i sp a p e rm a in l ys t u d i e sc h in e s ew e bt e x t ，f ir s t l ya n a l y s e sc h in e s ew o r ds e g m e n t a t i o n m e t h o db e c a j 9 eo ft h es p e c ia ln a t u r eo ft h ec h in e s et e x t 。a n dt h e np r e s e n t san e m o d e lo f r o u g hs e g m e n t a t io n ，w h ic hisb a s e do nb i g r a ma n dn - m o s tp r o b a b lym e t h o d int h isn e ， m o d e lw ea i ma to b t a i n i n gf e nh i g hr e c a l l i n gr a t ea n dh i g he f f i c i e n tr o u g hr e s u l t ，w h i c ht r i e s t oc o v e rt h ec o r r e c ts e g m e n t a t io na n du n k n o w nw o r d sa sm u c ha sp o s s ib les u c ht h a tt h e q u a i lt yf o rt h ef o llo w in gs e g 删a t io nc a nb ee n h a n c e d l a s t l y ，a sc h i n e s ew e be o n t e n tis i r t f o r m a t i v ea n du p d a t e df a s t ，an e wm e t h o do fw e br e p r e s e n t a t i o nl sp r e s e n t e d 。w h i c hi s b a s e do nb e n w o r dd is c o v e r y ，a n dw er e p r e s e n t st h ew e bd o c u m e n tu s ln gw o r d sa n d n e , v - w o r d sf i n a l l y t h ee p e r i r n e n t a lr e s u l t ss h o wt h a ti tc a nh e l pu st oi d e n t i f yu n k n o w n w o r d sa n de x t e n dt h ec u r r e n td ic t io n a r y ，s t r e n g t h e nt h er e p r e s e n t a t io no fw e bd o c u m e n t s , im p r o v et h eq u a li t yo ft h ea d o p t e dv e c t o r , a i din c r e a s et h ee f f e c to fw e bd o c u m e n t d a s s i f i c a t i o n a sa s i m p l e , e f f e c t i v ea n dn o n p a r a r n e t r i cd a s s i f i c a t i o nm e t h o d ，k n nm e t h o di sw i d e l y u s e di nw e bt e x td a s s i f i c a t i o n b u tt h em e t h o dn o to n l yh a sl a r g ec o m p u t a t i o n a ld e m a l d b e c a u s ei tm u s tc o m p u t e t h es i m i l a r i t yb e t w e e nu n l a z e l e dt e x ta i da n yt r a i n i n gt e x t ；b u ta l s o m a yd e c r e a s et h ep r e c i s i o no fd a s s i f i c a t i o nb e c a j 9 eo ft h ec o m m o n n e 稿o fd a s s e s int h i s p a p e r 。f i nim p r o v e c | kn nm e t h o disp r e s e n t e d ，w h ic hs o l v e st w op r o b le m sm e n t io n e da b o v e , i nt h i sm e t h o df i r s t l yg e t st h em o s tk oc l a s s e sf a s tb yr o c c h i om e t h o d ，a n dt h e nu 翳k n n a r i t h m e t i ci ns o m er e p r e s e n t a t i v et r a n i n gt e x t so ft h ek oc l a s s e s ；a tl a s tw em 水ed a s sb y a ni m p r o v e ds i m i l a ra r i t h m e t i ci nk n n 。t h er e s u l to fr e s e a r c hi n d i c a t e st 憾t h ei m p a c to ft h e f l e wm e t h o disb e t t e r a tt h es a m et im e , b e c 盖t u s et h ew e br e s o u r c e sc o m m o n lyu 9 e dt ob e o r g a n i z e db yh i e r a r c h i c a ls t r u c t u r e , t h i sp a p e ra l s od i s c u s s e s t h el e - , e lc l a s s i f i c a t i o na n db r i n g s f o r w a r do n em e t h o do fw e bt e x td a s s i f i c a t i o nb a s e do nt h ec o m b i n a t i o no f h i e r a r c h i c a l s t r u c t u r ea n dk n n int h i sn e wa l g o r i t h m ，w eu s eh i e r a r c h i c a ls t r u c t u r et of a s tt h e d a s s i f i c a t i o ns p e e d ，a n dk n na l g o r i t h mf i l l sl 创dd a s s i f i c a t i o no f p r e c i s i o n b o t h e x p e r i m e n t ss h o wt h a tt h e s et w oi m p r o v e dk n nd 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 d a s s i f i c a t i o ne f f i c i e n c yi nal a r g ee x t e n t ，b u ta l s ot os o m ee t e n ti m p r o v e dd a s s i f i c a t i o n a c c u r 笛- y k e y w o r d s ：c h i n e s e w o r d s s e g m e n t a t i o n ；f e a t u r e s e l e c t i o n ；w e b t e x tr e p r e s e n t a t i o n ；w e b t e x t d 销i f i c a t i o n ；k n na r i t h m e t i c ；h i e r a r c h i c a ls t r u c t u r e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 签 名：箬盔塑 日 凝：沙口罗占，f 毫 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名： 导师签名： 日 期： 第一章绪论 第一章绪论 1 1 研究背景 自从上个世纪9 0 年代后期以来，因特网技术发展迅猛，w e b 页面极大增多和网络 数据的急剧膨胀使人们感受到了信息浪潮带来的冲击，因特网已经成为世界上最大的信 息资源地。然而，在互联网上信息不断增加、信息的种类不断扩张的同时，人们获取信 息的能力并没有随之增加，一方面人们感觉自己淹没在信息海洋中，但另一方面又发现 得不到自己需要的信息。 在信息爆炸时代，大规模的数据就是信息，人们想得到正确的有用的信息就需要对 数据进行分析，发现其中蕴含的规律【1 胴。这时数据挖掘、信息检索技术应运而生，数 据挖掘( d a t am i n i n g ) 是从大量的、有噪声的、模糊的和随机的数据中，提取隐含在其中 的、人们事先不知道的、但又是潜在有用的信息和知识的过程，它是一种综合应用统计 分析、数据库和智能语言等来分析庞大数据资料的智能化技术 3 1 1 4 ；信息检索 ( in f o r m a t i o nr e t r i e v a l ) ，是指将信息按一定的方式组织和存储起来，并根据信息用户的需 要找出有关信息的过程，所以它又叫“信息的存储与检索( i n f o r m a t i o ns t o r a g e a n d r e t r i e v a l ) 。这是广义的信息检索。无论是数据挖掘还是信息检索技术，其中核心内容都是 文本分类( t e x tc l a s s i f i c a t i o n ) 其主要任务是指在给定文本分类体系下，根据文本内容 判定文本所属类别【5 j 。 鉴于因特网上的大部分信息都以文本形式存在，w e b 文本信息的分类就显得更加迫 切，因为它与人们的工作和生活密切相关；同时，爆炸式增长的文本信息给文本分类的 精度和速度提出了新的标准与挑战。这要求文本分类在提高精度的同时，还要进一步提 升训练与分类的速度，这就是本文研究的一个出发点和期望达到的目标。 1 2 研究意义 信息组织 对文本进行组织可以提高用户查找的效率，比如图书馆的归类体系，就能够方便读 者进行查找；再如新浪、搜狐、雅虎等都把网页按照内容进行层次归类，这样让读者们 很快浏览到所需要的信息。显然文档组织属于典型的多类别文本分类问题，而目前大多 数文档归类工作都由人工完成，就连新浪、搜狐、雅虎等大部分归类都由人工完成；这 很显然耗费了大量的人力物力，若能够采用自动文本分类技术来辅助文档归类，这必将 大大地提高分类的效率。 信息过滤 随着信息获取方便性的提高，人们对获取网络信息的需求也在不断增长，于是， 人们迫切需要一种智能的信息过滤技术，该技术能够根据用户的需要，对源源不断到来 的文本进行动态的分类、筛选，从而保留有用信息，屏蔽无关信息。这就是搜索引擎表 现出来的巨大功能，从文本分类的角度来说，它属于两类文本分类问题，即它将所有文 江南大学硕士学位论文 本区分为“相关文本”与“无关文本”。信息过滤能够主动地获取用户特定的信息需求，进 而使用这些信息需求组成过滤条件，对信息资源进行过滤，就能把符合条件的信息抽取 出进而满足用户需求。 邮件分类 电子邮件作为最广泛和成功的i n t e r n e t 服务已经成为人们日常生活中不可缺少的组 成部分，但在给人们带来巨大方便的同时，也日益显示出其负面影响，那就是我们每天 收到的邮件中有很大一部分是那种“不请自来”的所谓“垃圾”邮件，它们或者是推销广告， 或者是一些有害的不良信息，甚至是病毒。目前邮件分类可以看作通常的文本分类问题， 它可以分为两种模式：其一是两类模式，即按照垃圾与非垃圾来分类；另一种是多类模 式，比如工作、会议、垃圾等。 1 3 研究现状 文本分类是指在给定的分类模型下，根据文本内容确定文本类别的过程，简单来说 它经历了三个阶段的发展。第一阶段：上个世纪6 0 年代到8 0 年代大部分的文本分类器 都是基于知识工程【5 j ，在分类精度上达到了较好的效果，但是也面临着很多问题，第一 就是各个领域的专家耗费了很多经费，第二就是随着互联网的逐渐兴起，需要处理更多 更复杂的数据。第二阶段：9 0 年代后基于机器学习的文本分类算法占主要地位，它不但 在分类精度上可以和专家系统相比，在分类速度上也远远好于前者，适合处理大量数据， 在这期间机器学习的大量算法被应用到文本分类领域，包括最近邻闭、贝叶斯 8 1 、决策 树嘲、神经网络【10 l 等等。第三阶段：9 0 年代中后期，人们将支持向量机这个概念引入到 文本分类领域，s v m 【1 1 】的分类器也取得了非常好的效果。 目前，w e b 文本分类是信息检索和数据挖掘领域中一个非常活跃的研究方向。众多 学者对这个方向进行了广泛而深入的研究，研究的热点主要集中在以下几个方面： 特征的表示和压缩 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 1 2 1 是文本分类领域被广泛使用而证明有 效果的模型，它的一个前提就是特征的表示。一个文本通常被表示为向量形式，它的特 征具体可以是字、词、词语、n g r a m 、概念等，普遍认为是基于词的特征表示效果好； 但对于中文w e b 文本来说，中文分词又是一个研究的课题。 目前的特征压缩算法大体可以分为两类：特征选择( f e a t u r es e l e c t i o n ) 13 l 与特征抽取 ( f e a t u r ee x t r a c t i o n ) 4 】。特征选择是根据某种准则从原始特征中选择部分最有类别区分能 力的特征；特征抽取是依据某种原则构造从原始特征空间到低维空间的一个变换，从而 将原始特征空间所包含的分类信息转移到新的低维空间中来。 特征选择又可以细分为过滤法( f i l t e r ) 与融合法( w r a p p e r ) 。过滤法不依赖于分类器， 它只是根据某种标准对特征进行排序，然后选择前n 个特征；而融合法需要跟分类器 密切结合，并根据分类精度来判断某个特征子集的优劣。在特征抽取方面，主成分分析、 线性区分分析、概念索5 11 1 司等等众多方法都先后被提出或引入到文本领域。 样本不均衡问题 2 第一章绪论 当样本集的文本数量很大时，往往会发生样本不均衡问题，类别之间的样本数量有 可能存在数量级的差距，这种情况下由于样本集中数据分布的不均匀使得分类精度受到 很大的影响，分类器被大类所主导，严重影响分类效果。与此同时，大部分的经典算法 都是基于分布均匀的样本数据集，因此这类问题引起了很多学者的关注闭。 目前较为常用的解决方法对策有：( 1 ) 在取样的时候，弱化大类，强化小类。但存在 的问题也很明显的，即可能增加很多的干扰信息【1 石i ；( 2 ) 通过误差加权增大小类样本对分 类器的贡献【1 7 1 ：( 3 ) 通过不同的特征选择方法来分别对大类和小类进行提取特征向量【1 8 1 。 解决这类问题的关键就是如何加大分类器对于小类样本特征的重视。 分类器组合问题 分类器组合( c o m b i n a i o n ) 1 川又叫分类器委员会( c o m m i t t 嘲，它的思想起源于多专家 决策，很显然，多个专家要比单个专家做出更好的决策。在文本分类领域，就是指采用 多个分类器进行训练，然后分类时组合每个分类器的决策。根据是否对训练集进行取样， 分类器组合大体上可以分为两类：分类器简单组合方式与重采样方式。 在分类器简单组合方式中，训练集对所有成员分类器而言保持不变，训练时各成员 分类器独立进行，分类时组合所有成员分类器的分类结果。l a r k e y 设计了一个基于 r o o c h i o 、贝叶斯与最近邻的组合分类器【2 a 1 ，+ 他的实验结果表明任何两两组合的分类精 度要高于单个分类器的分类精度；而三个分类器组合的分类精度要高于任何两两组合的 分类精度；l a r k e y 的实验在一定程度上表明了组合分类器能够对其成员分类器进行取 长补短。 重采样方式对训练集进行多次有放回采样，然后采用某个弱分类器算法在这些采样 出来的多个训练集上训练出多个分类器，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 根据已经产生的分类器的分类效果对训练集进行 采样，重点突出错分样本。s c h a p i r e 开发了b o o s t e x t e r 系纠2 1 】，该系统采用决策树作 为弱分类器，实现了两个b o o s t i n g 算法，实验结果表明该方法具有不错的分类质量。 层次分类问题 层次分类又称多层分类。互联网上的海量信息往往都是有层次的，每一个大类包含 着若干个小类，构成了一种类似于树状结构的组织。这种分类问题的最大好处就是可以 提高分类效率，在多层分类的高层就可以过滤掉很多不相关的文档。我们平常所研究的 文本分类方法( 平面分类方法) 可以看成是多层分类的最低层次【1 明，是多层分类技术的 特例。多层分类的问题在于类别之间关系的复杂度，以及不同层次之间分类所造成的误 差。 袁时金 2 2 1 总结了层次化文档分类的三种实现途径。第一种就是把层次分类问题转化 为只包含基类( 即叶节点类别) 的平面型分类问题；第二种方法是，按照文档类别层次结 构树，将层次分类问题逐层分化为一个个的局部分类问题，在类树的每一内部节点分别 建立分类器。第三种方案是把层次化分类问题看成是一个更一般的多类、多标注分类问 题来进行求解。 小样本问题 3 江南大学硕士学位论文 小样本问题，指在样本集中存在着大量未标记数据集。随着互联网的兴起，使人们 可以方便快捷的获得大量数据，但要想获得大量的有标记数据样本集，还是要耗费大量 的人力物力，如何才能更好的利用大量未标记数据集，引起了很多学者的关注闼。 n i g a r 4 硐在他的博士论文中首次利用e m 算法结合朴素贝叶斯分类器对这类问题进 行了深入研究，它的主要思想是利用己标注样本集训练得到初始分类器，利用朴素贝叶 斯分类器和e m 算法估计未标记样本的所属类别，之后重新训练分类器，如此反复直到 迭代为止得到最终的分类器。j a o c h i n l s 提出的直推式支持向量机( t m ) 2 4 】，它的主要 思想是首先利用有标记样本集通过s v m 方法训练得到一个分类器，在这基础之上对未 标记样本集进行误差预测，将误差较小的一些样本加入到有标记样本集中得到新的分类 器，反复迭代直到收敛为止。 w e b 文本分类问题 我们之前讨论的对象大多都是普通文本，但如果信息来源于w e b 文本，就需要考虑 网页结构等信息；在越来越多的研究中发现，网页结构信息可以有效得帮助改善分类效 果担纠，因此如何利用h t m l 结构引起了很多学者的关注。 第一种考虑就是如何利用网页的超链接信息，大部分网页的超链接信息是噪音信息， 然而有些超链接内容又包含有有用信息，因此如何在这之间做出平衡摆在很多学者面前 的问题。l i 【2 5 l 等人提出了一种基于网页结构的模型，考虑到一个网站内部噪音结构的相 似性来达到去除噪音改善分类效果的目的。 第二种情况则是范焱闭等人提出的组合分类器思想，重点考虑网页信息中所包含的 例如标题，加粗字段，这些文本内容的权值都要比普通的文本大，继而利用文本类别相 似度算法对不同的网页进行分类，达到较好的分类效果。 1 4 研究内容 本文研究的对象是中文w e b 文本，目的是提高w e b 文本分类的精度和速度，主要 针对中文w e b 文本的表示以及分类算法进行了深入地探讨，主要内容包括： 第一章是绪论，共4 节。第1 节介绍本文的研究背景；第2 节是该课题的研究意义； 第3 节为w e b 文本分类的研究现状；第4 节为本文的研究内容。 第二章是中文w e b 文本分类概述，共4 节。第1 节为w e b 文本预处理和表示，预 处理分为中文分词和去除h t m l 结构信息等；第2 节为特征选择相关算法，介绍了目 前常用一些特征选择方法；第3 节为文本分类相关算法，总结了当前常用的相关分类算 法；第4 节为性能评价标准及常用语料的相关介绍。 第三章是基于二元语法的n 一最大概率中文粗分模型，共4 节。第1 节介绍n 一最短 路径粗分模型，包括基本原理和模型求解；第2 节详细介绍了本文的分词模型，包括二 元语法、参数估计和数据平滑；第3 节是实验与结果，首先是粗分模型求解过程，然后 设计实验，最后分析实验结果；第4 节为本章小结。 4 第一章绪论 第四章是基于新词发现的w e b 文本表示方法，共5 节。第1 节为w e b 文本净化； 第2 节详细介绍了新词概述和新词发现的过程；第3 节为w e b 文本表示的新方法；第4 节为新方法的实验及结果；第5 节为本章小结。 第五章是w e b 文本k n n 分类算法的研究，共4 节。第1 节为k n n 分类算法简介； 第2 节为改进的k n nw e b 文本分类算法，先通过r o c c h i o 分类快速得到k 。个最有可能 的侯选类别，然后在个类中心区域采用k n n 算法，最后结合r o c c h i o 分类结果，由 一种改进的相似度计算方法决定最终的文本所属类别，并设计了相关实验来说明该方法 的有效性；第3 节为层次结构和k n n 相结合的w e b 文本分类算法，首先介绍层次结构 模型的建立和基本分类过程，然后结合k n n 分类算法，最后通过实验来说明分类精度 和分类速度都得到了提高；第4 节为本章小结。 第六章是总结与展望，共2 节。第1 节对本文的总结；第2 节为该课题的展望。 5 江南大学硕士学位论文 第二章中文w e b 文本分类概述 2 1 w 曲文本表示与计算 2 1 1w e b 文本预处理 文本预处理是文本分类的前提，如何将一个普通的文本转化为可以处理的数据是研 究的重点。同时为了适应各种不同的情况，文本预处理也会有所不同，其主旨是将文本 处理为适合分类器的数据集。一般来说中文w e b 文本预处理主要包括：中文分词、去 除停用词、处理h t m l 结构化信息等问题。 中文分词 中文分词技术是中文分类中特有的概念，由于英文单词之间有空格将各个词自然分 开，而中文则是根据词和词之间的概念来区分，所以中文分词是中文文本分类预处理的 关键一步。目前针对中文分词已经提出许多方法，主要有两类：基于规则分词和基于统 计分词【2 7 l 。 1 基于规则方法 基于规则的方法也称基于词典方法，它的基本思想是：首先建立一个包含所有可能 出现的词库，然后对给定待分词的汉字串s ，按照某种确定的算法切取s 的子串，若该 子串与词库中的某词条相匹配，则该子串是词，继续分割剩余的部分，直到剩余部分为 空；否则，该子串不是词，重新切取s 的子串进行匹配。使用该方法，词典的涵盖程度 决定了词汇切分的准确率，要做到这一点很不容易。此外，该方法无法正确切分出词表 中未收录的新词，不具备自适应性。 2 基于统计方法 基于统计的分词方法也称无词典分词方法，它是基于这样一个语言信息：在文章中， 相邻间字同时出现的次数越多，就越有可能构成一个词，所以字与字相邻共现的频率或 概率能够较好地反映它们成为词的可信度。通过设定一个阈值，使得当可信度高于某一 个阈值时，便认为两个字可能构成了一个词，采用无词典分词，得到的非真实词条会非 常多，识别精度较差，时空开销大。 在实际应用的分词系统中通常都采用规则和统计相结合的方法：使用一部基本的分 词词典( 常用词词典) 进行串匹配分词，同时利用统计方法来消除歧义和未登录词识别， 既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词算法结合上下文识别 生词、自动消除歧义等优点。 去除停用词 停用词是指一些常见常用但对文本分类没有贡献的词或字符，这类词主要包含三类， 其一：常见名词没有特殊的含义，如“我们”、“他们”、“什么”等；其二：语气词，助词 等等，例如：“吗”、“呀”、“的”等：上述这些词的特点是没有明确的涵义，同时在文本 中多次出现，对文本分类没有贡献或者贡献很小。而第三类停用词是标点符号和非法字 符，因为这些字符不能表达文本的内容信息，对文本分类没有实质性的意义。因此，去 6 第二章中文w 曲文本分类概述 除停用词就是把这三类词或字符过滤掉，进而改善最终文本表示和分类效果。 处理h t 儿结构化信息 互联网是信息的载体，构成互联网的w e b 网页则是载体的基本单元。w e b 网页不同 于普通的文本，多数是由半结构化的h t m l 语言构成，如何提取出w e b 网页中相对有 用的信息是w e b 文本分类中重要的一环。大体上有以下几种处理方法，首先将w e b 网 页中所有文字都认为是有用信息，这就造成可能包含大量的噪音信息；第二种情况是将 诸如网页标题、字体加粗文字和链接信息等看成是有用信息，而其他的信息则过滤掉， 这种方法相对于第一种而言做出了相对的平衡，可以达到较好的效果；最后一种是根据 一定的规则判断出要保留哪些信息，对于特定的网页分类而言，有特定的规则，这种方 法无疑是预处理中最好的，但该方法无法普遍应用。 2 1 2 文本特征的表示 计算机并不具有人类的智能，人在阅读文章之后，根据自身的理解能力可以产生对 文章内容的模糊认识，而计算机并不能轻易地“读懂”文章，从根本上说，它只认识0 和 1 。因此，跟所有机器学习问题一样，要想让计算机自动对文本进行分类，就需要把一 篇文本表示成一个个特征，比如词( 包括字) 、n - g r a n 、词组、概念等等。很显然，这将 丢失大量关于文章内容的信息，但是这种表示可以使文本的处理形式化，并且可以在文 本分类中取得较好的效果。 其中，词是文本分类中使用最广泛的特征【2 8 1 ，对于英文来说，采用空格或标点将词 隔开，所以词的获取非常简单；但对中文来说，由于词与词之间没有空格，因此词的获 取必须通过分词来实现。n - g r a n 是不考虑组成文本的语义单位，如字、词还是词组，而 是将整个文本看成是由不同字符组成的字符串，因而可以方便地表示各种语言文本。概 念表示法，相比词语而言，具有更高的抽象性；一个概念可以对应文中的一个词，也可 以对应若干个有语义联系的词，从原理上来说，采用概念作为文本特征具有很多好处【硼。 2 1 3 文本相似度的计算 布尔模型 布尔模型是早期信息检索系统中常用的一种模型，在该模型中，每篇文档表示成文 档中出现的特征集合，即文档表示为特征空间上的一个向量，向量中每个分量权重为0 或1 ，1 表示词条出现，而o 则表示未出现。不过，这种模型通常只能用于信息检索中 计算简单的相关性，而无法利用该模型计算两个文档更深层次的相似度，无法在更多的 文本处理应用中使用。 向量空间模型 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 由s a l t o n 1 2 1 等人在6 0 年代末提出，此模型 被认为是处理信息检索领域问题的最佳模型。它的主要思想是：对于一个文本集合d ， 选择刀个最具代表性特征，构成特征集合丁，每一个特征集合中的特征f ，就对应空间 模型中的一维，文本d 就可以表示为一个n 维的向量，其中堆为第f 维特征在该文本中 的权重。这样，每一个文本就可以映射为向量空间模型中的一个点，文本之间的相关性 7 江南大学硕士学位论文 就可以通过向量之间的距离来计算。将文档表示成向量空间模型主要有两部分组成，第 一是特征项，第二是特征项的权重，每一个特征项对应一个特征权重，表示此特征项在 文本中的重要程度。 对于特征项而言，利用前面提到的分词和去停用词等技术来得到，而权重有多种不 同计算方法，目前较常用有两种：布尔权重和通过t f - i d f ( 怕mf r e q u e n 叫一n v e r d o c u m e n tf r e q u e n c y ) 来计算权重。布尔权重考虑的方式相对简单，如果特征项在文本中 不出现则权重是0 ，相反则为1 ，布尔权重无法体现出词条的重要程度。t f - i d f 不但考 虑特征项在文本中出现的频度，同时还考虑了其在整个语料中的分布情况，因此被认为 是较好的特征项权重计算公式；其中t f 是特征项在文本中的绝对频率，t f 越大表示 该特征在这个文本中越重要，而i d f 表示特征项在文本中的文本内频数，它反映了特 征在整个语料中的分布情况，i d f 越大表示其在整个文本中的分布相对集中，反而越不 重要。目前存在多种t f - i d f 计算公式，一种比较普遍使用的t f - i d f 公式闭，如下： ( ，d ) ：毒磐尘型丝型型需 ( 2 1 ) 压【矿( ，d ) i o g ( n n , + o 0 1 ) 】2 、 v 函 其中，w ( t ，d ) 为词t 在文本d 中的权重，t f ( t 。d ) 为词t 在文本d 中出现的词频( 绝对词频即 词在文本d 中出现的频次；相对词频即为归一化后的词频) ，n 为训练文本的总数，以，为 训练文本集中出现词t 的文本数，0 0 1 为常数因子，眇( f ，d ) l o g ( ，+ o 0 1 ) 】2 为 vt e d 归一化因子；这样，文本d 可表示为向量空间模型为： v ( d ) = ( ，w ( ，d ) ：f 2 ，w ( t 2 ，d ) 厶，w ( 乙，d ) )( 2 2 ) 概率检索模型 布尔模型和向量空间模型都是将文档表示词条视为相互独立的项，忽略了表示词条 之间的关联性。而概率模型则考虑了词条、文档间的内在联系，利用词条之间以及词条 与文档间的概率相依性进行信息的检索。该模型最早由m a r o n 和k u h n s 于1 9 6 0 年提 出【3 1 1 。经过多年的发展，概率模型已经衍生出一系列检索模型，被应用到很多系统中， 并取得不错的效果。 2 2 特征选择相关算法 特征选择是指从一组特征中挑选出一些最有用的特征以达到降低特征空间维数的 目的。换句话说，特征选择就是从一组数量为w 的特征中选择出数量为w ( w w ) 的一 组特征来。常用的特征选择方法有：文档频次( d f ) 、互信息( m 1 ) 、信息增益( 1g ) 、z 2 统 计量( c h i ) 、交叉熵( c 日等，在实验中【13 1 3 2 j 表明，i g 和c h i 是两种相对不错的方法。 2 2 1 文档频率 文档频率( d o c u m e n tf r e q u e n c y ，d f ) 是最简单的一种特征选择方法，但也是很有效 的一种方法。该方法通过文档频次进行特征选择，就是将文档频次小于某一阈值的词删 除，从而降低特征空间的维数。d f 评估函数的理论假设是稀有单词要么不含有用信息， 8 第二章中文w e b 文本分类概述 要么有用信息太少而不足以对分类产生影响，所以可以删去。显然它在计算量上比其它 评估函数要小得多，在实际运用中它的效果也不错，但d f 也有缺点，因为稀有单词可 能在某一类文本中并不稀有，而且包含着重要的标志信息。 2 2 2 互信息 互信息( m u t u a li n f o r m a t i o n ，mr ) 在统计语言模型中被广泛采用。互信息是信息熵的 引申概念，是对两个随机事件的相关性度量。特征项对于类别的互信息越大，它们之间 的共现概率也越大。将低于特定阈值的特征从原始特征空间中移除，保留高于阂值的特 征项。词条和类别之间的互信息计算公式如下： 哪= l o g 锱 ( 2 3 ) 其中p ( t ，c i ) 表示特征项，在类别q 中出现的概率，p ( t ，c ) 表示特征项在所有文档中出现 的概率；如果在现有的测试集上定义类c ，若a 用来表示特征项t 和类c 同时发生的次 数；b 表示特征项t 发生而类c 不发生的次数；c 表示特征项t 不发生而类c 发生的次 数；n 是指总体的文档数目，则特征项t 和类c 之间的m i 值计算公式如下： m ( ) 咖两 ( 2 岛 互信息的缺点是受临界特征的概率影响较大，它经常倾向于选择稀有单词。然而对 于文本分类而言，出现次数较多的单词比出现次数较少的单词具有更大的作用，所以互 信息在文本分类中表现较差。 2 2 3 信息增益 信息增益( i n f o r m a t i o ng a i n ，t g ) 通过特征项在文本中是否出现来判断其携带信息量 的多少，其计算公式如下： 硒( f ) 一尸( q ) 旧尸( q ) + 尸( f ) 尸( cit ) l o o e ( c , it ) 矧圈 ( 2 5 ) + 尸( ；) p ( e 时0 9 尸( gi ；) 其中尸( q ) 表示任意一篇文本属于第f 类的概率，p ( f ) 表示特征项f 在文本集中出现 的概率。尸( ，) 表示除f 外的特征项在文本集中出现的概率。j p ( qi ，) 表示任意一篇包含f 的 文本属于第i 类的概率。尸qi ，) 表示不包含f 的文本属于第f 类的概率。 2 2 42 2 统计量 该方法度量词条t 和文档类别c 之间的相关程度，并假设t 和c 之间符合具有一阶自 由度的贮分布；词条对于某类的x 2 统计值越高，它与该类之间的相关性越大，携带的 类别信息也越多。令n 表示训练语料中的文档总数，c 为某一特定类别，t 表示特定的 词条，a 表示属于c 类且包含t 的文档频数，b 表示不属于c 类但是包含t 的文档频数， 9 江南大学硕士学位论文 c 表示属于c 类但是不包含t 的文档频数，d 是既不属于c 也不包含t 的文档频数。则t 对于c 的c h i 值计算公式如下： 舭加两矗筹篇 ( 2 6 ) 2 2 5 期望交叉值 期望交叉熵( e x p e c t e dc r o s s e n t r o p y ，e c e ) 反映了文本类别的概率分布和出现某特 定特征项条件下的文本类别概率分布之间的距离。特征项的熵越大，则对文本越重要。 计算公式如下： e c e ( 归善pc i - o g 错 ( 2 7 ) j = 1 1 lo ， 其中尸( qi ，) 表示文档包含特征项，时属于q 类的条件概率，尸( q ) 表示c i 类文档在样本 集中出现的概率。如果特征项和类别强相关，也就是p ( qi t ) 大，且相应的类别出现概 率小，则说明特征项对分类的影响大，相应的e c e ( t 1 值就大，就很可能被选中作为目 标特征项。 2 3 文本分类相关算法 文本分类属于机器学习的一个分支，许多经典的机器学习算法都被引入到文本分类 中来 3 3 1 。常见的分类算法有文本相似度算法，朴素贝叶斯分类算法 8 1 ，k 近邻分类算法 7 1 ，神经网络分类算法i 、支持向量机洲和决策树 9 1 等等。 2 3 1 文本相似度算法 这种方法的思路相对简单，利用向量空间模型，通过特征项来代表每一个文本，同 时根据相应的提取规则为每一类生成一个代表该类的特征向量集合。当判断一个未知文 本类别时，计算该文本向量与每一类别向量之间的相似度，计算公式如下： s i m ( d ，c ) = k = 1 ( 2 8 ) 其中s i m ( d ，c ) 表示文本d 和类别c 之间的相似度，表示文本d 的第k 个特征权重， 表示类别c 的第k 个特征权重；最后把未知文本归属于相似度最大的那个类别。 2 3 2 朴素贝叶斯 朴素贝叶斯是一种线性分类器。依据贝叶斯条件概率公式，假设样本的特征是相互 独立，计算样本属于不同类别的条件概率，然后依据最大似然原理将该文档归为具有最 大后验概率的那一类。这种方法之所以在文本分类领域得到了广泛的应用，是因为做出 了较强的特征相互独立假设，对于这种假设一方面大大简化了贝叶斯分类器的计算量； 另一方面也导致了分类器的分类质量不稳定性。该模型将样本看作独立的词条集合，根 1 0 第二章中文w e b 文本分类概述 据贝叶斯理论在训练集的基础上得到词条在不l 司类别的概率，构造出贝叶斯模型。