（计算机应用技术专业论文）基于半监督学习的中文文档分类技术研究.pdf

中南大学硕士学位论文 摘要 摘要 文本分类是指分析文本内容并按一定的策略把文本归入一个或 多个合适的类别的应用技术。随着i n t e r n e t 的出现，大量的文字信 息开始以计算机可读的形式存在，以传统的手工方式对这些信息进行 组织整理既费时费力且效果不理想，文本分类由于利用机器来对文本 进行分析整理，使用户从繁琐的文档处理工作中解放出来，并能极大 地提高信息的利用率，而受到越来越多的重视，已广泛应用于文本处 理和文本检索的各个领域，成为处理和组织大规模文本信息的关键技 术，并推动了信息处理朝着自动化的方向发展。 本文首先研究了文本分类的背景和发展现状，阐述其系统结构， 对文本分类的几个关键技术：文本特征生成、特征选择与降维、权重 的计算和文本分类技术的各个算法进行了分析和评价。 然后鉴于高分类精度需要大规模已标记训练集而已标记文档缺 乏，利用未标识文档进行学习的半监督学习算法已成为文本分类的研 究重点这一情况，着重研究了半监督分类算法。对现有的各个算法进 行了比较分析，发现当已标识文档很少时，比如每类少于1 0 个已标识 文档时，这些算法会错误地估计最初的数据分布而降低了其分类的正 确性。对此提出了一个基于聚类的分类算法，对已标识文档和未标识 文档一起聚类，通过聚类扩大已标识文档集，提高了分类器分类的准 确性。 最后本文设计了一个中文文本分类原型系统，为保证测试的准确 性，采用了不同的数据源进行测试，并根据网页文档的特殊格式、特 征词的频率、文档的长度以及特征词的长度四个因素对文本特征进行 了加权处理，最后用s v m ，t s v m ，c o t r a i n i n g 与本文提出的算法进 行了有监督学习性能测试和半监督学习性能测试。通过以上测试表 明，当有足够的已标识文档时，本算法与其它算法性能相当，但当已 标识文档很少时，本算法优于现有的其它算法。 关键词：信息分类，文本分类，半监督学习，聚类 中南大学硕士学位论文 a b s t r a c t a b s t r a c t t e x tc l a s s i f i c a t i o ni sas u p e r v i s e dl e a r n i n gt a s ko fa s s i g n i n gn a t u r a l l a n g u a g et e x td o c u m e n t st oo n eo rm o r ep r e d e f i n e dc a t e g o r i e so rc l a s s e s a c c o r d i n g t ot h e i rc o n t e n t s i th a s r e c e n t l ya t t r a c t e d a n i n c r e a s i n g a m m o u n to f a t t e n t i o nd u et ot h ee v e - e x p a n d i n ga m o u n to f t e x td o c u m e n t s a v a i l a b l ei nd i g i t a lf o r m t e x tc l a s s i f i c a t i o ni sw i d e l ya p p l i e di ne v e r y f i e l d so ft e x tp r o c e s sa n di n f o r m a t i o nr e t r i e v a l ，h a sb e c a m et h ek e y t e c h n i q u ei np r o c e s sa n do r g a n i z el a r g e s c a l et e x ti n f o r m a t i o n ，a n d i m p u l s e st h ei n f o r m a t i o np r o c e s st ot h ed i r e c t i o no fa u t o m a t i o n t h i st h e s i s f i r s t l y i n t r o d u c e s g e n e r a ld e v e l o p m e n t a n ds o m e t e c h n i q u e s o fi n f o r m a t i o nc l a s s i f i c a t i o n t h e n s o m e a n a l y s e s a n d r e m a r k sa r em a d et o c o m p a r e t h e p e r f o r m a n c e o fs o m e t y p i c a l c l a s s i f i c a t i o n ia l g o r i t h m so ff e a t u r es e l e c t i o n ，f e a c t u r ee x t r a c t i o n ，a n d w e i g h tc a l c u l a t i o n ，c l a s s i f i c a t i o na l g o r i t h m s e c o n d l yc o n s i d e r i n g t h ec o n t r a d i c i t o no fd e a d l yn e e df o rl a r g e l a b e l e dt r a i n - s e tt oo b t a i nh i g hc l a s s i f i c a t i o na c c u r a c ya n dt h es c a r c i t yo f l a b e l e dd o c u m e n t s ，t h i st h e s i s e m p h a s i z e s o n i m p r o v e m e n t o f s e m i s u p e r v i s e d c l a s s i f i c a t i o n a l g o r i t h m s ，a n a l y s i s a l lt h ee x i s t i e d s e m i - s u p e r v i s e dc l a s s i f i c a t i o na l o g r i t h m n sa n df i n dw h i l eu n l a b e l e dd a t a s a m p l e sc a r lh e l pt oi m p r o v et h ea c c u r a c yo ft r a i n e dm o d e l st oc e r t a i n e x t e n t , e x i s t i n gm e t h o d s s t i l lf a c ed i f f i c u l t i e sw h e nl a b e l e dd a t ai s 6 x t r e m e l ys m a l l ，e g c o n t a i n i n gl e s st h a n1 0l a b e l e de x a m p l e si ne a c h c l a s s ，a n db i a s e da g a i n s tt h eu n d e r l y i n gd a t ad i s t r i b u t i o n t h i sp a p e r p r e s e n tac l u s t e r i n gb a s e dc l a s s i f i c a t i o na p p r o a c h , u s i n gt h i sa p p r o a c h ， t r a i n i n gd a t a , i n c l u d i n gb o t ht h el a b e l e da n du n l a b e l e dd a t a , i sf i r s t c l u s t e r e dw i t ht h eg u i d a n c eo ft h el a b e l e dd a t a s o m eo fu n l a b e l e dd a t a s a m p l e sa r et h e nl a b e l e db a s e do nt h ec l u s t e r so b t a i n e d d i s c r i m i n a t i v e c l a s s i f i e r sc a ns u b s e q u e n t l yb et r a i n e dw i t ht h ee x p a n d e dl a b e l e dd a t a s e t t h ee f f e c t i v e n e s so f t h ep r o p o s e dm e t h o di sj u s t i f i e da n a l y t i c a l l y f i n a l l yid e s i g nad o c u m e n tc l a s s i f i c a t i o ns y s t e ma n dc o n d u c t e d n i 中南犬学硕p 学位论文a b s l l b 研 c o m p r e h e n s i v ee x p e r i m e n t st ov a l i d a t eo u ra p p r o a c ha n ds t u d yr e l a t e d i s s u e s t h ee x p e r i m e n t ss h o w e dt h es u p e r i o rp e r f o r m a n c eo fo u rm e t h o d o v e re x i s t i n gm e t h o d ss u c ha st s v ma n dc o - t r a i n i n gw h e nl a b e l e dd a t a s i z ei se x t r e m e l ys m a l l w h e nt h e r ei ss u 伍c i e n tl a b e l e dd a t a , o u rm e t h o d i sc o m p a r a b l et ot s v ma n d c o t r a i n i n g k e yw o r d s ：i n f o r m a t i o nc l a s s i f i c a t i o n ，t e x tc l a s s i f i c a t i o n , s e m i - s u p e r v i s e dl e a r n i n g ，c l u s t e r i n g 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学 位或证书而使用过的材料。与我共同工作的同志对本研究工作所做的贡献均己在 论文中作了明确的说明。 作者签名：厶虿塾 日期：巡年生月竺日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位 论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容， 可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部 门规定送交学位论文。 中南大学硕七学位论文 第一章文本分类概述 第一章文本分类概述 文本分类是大规模文本处理的应用技术之一。近年来，随着信息存储技术和 通信技术的迅猛发展，大量的文字信息开始以计算机可读的形式存在，并且数量 每天都在急剧增加。这些文字信息的内容包罗万象，具体的信息用户往往只需要 其中的很少一部分。如果仅仅通过人工的手段对庞大的原始文档集进行组织和整 理，不仅在人力、物力、财力上都是很大的浪费，效果也未必很理想：相比之下， 若能由计算机直接对文档信息进行过滤、分类，把用户真正感兴趣的部分提交给 用户，就能使用户从繁琐的文档处理工作中解放出来，并能极大地提高信息的利 用率m 。 1 1 文本分类的概念 文本分类是指在分析文本内容的基础上按一定的策略把文本归入一个或多 个合适的类别的应用技术” 根据是否有固定的类别体系可分为有监督( s u p e r v i s e d ) 的分类( 也称为自动 归类) 和无监督( u n s u p e r v i s e d ) 的分类( 也称为自动聚类) 。 自动归类是先抽取待分类文本的特征，将之与各类别中文本所具有的共同特 征或一定的分类标准、分类参数进行比较，然后将待分类文本划归为特征相近的 类，并赋予相应的分类号。它一般分为训练和测试两个阶段，训练阶段所用到的 文本集合由属于预先定义好类别体系的文本组成，分类系统先通过训练文本集学 习分类知识，然后在测试阶段根据所学的知识为待分类的文本确定一个或多个合 适的类别，例如文本的分流和信息的过滤。 无监督分类首先从文本中抽取有关特征，再根据一定的法则或需要利用聚类 算法将具有相同或相近特征的文本定义为一类，划分出的类别是不确定的，要求 同一类内文本内容的相似度尽可能大，而不同类间的相似度尽可能地小。 从数学角度来看，文本分类( 文本归类) 是一个映射的过程，它将未标明类别 的文本映射到已有的类别中，该映射可以是一一映射，也可以是一对多的映射， 因为通常一篇文本可以同多个类别相关联。用数学公式表示如下： f ：a b ( 1 1 ) 其中，a 为待分类的文本集合，b 为分类体系中的类别集合。 这里所指的文本可以是媒体新闻、科技报告、电子邮件，技术专利、网页、 书籍或其中的一部分。 文本分类问题关注的文本种类，最常见的是文本所涉及的主题或话题( 如体 育、政治、经济、艺术等) ，也可以是文本的文体风格( 如流派等) ，或文本与其 中南大学硕士学位论丈 第一章文奉分类概述 他事物( 如垃圾邮件或成人网页等) 之间的联系( 相关或不相关) 1 2 文本分类的背景和意义 文本分类最初是应信息检索( i n f o r m a t i o nr e t r i e v a l ，简称i r ) 系统的要求而出 现的。它提供了文本集良好的组织与结构，大大简化了在庞大文本信息库中存取 文本的操作，为信息检索提供了更高效的搜索策略和更准确的查询结果p l 。 文本自动分类研究是文本挖掘领域的一个重要分支，是数据挖掘领域中对复 杂类型数据的挖掘技术。因而，文本挖掘成为数据挖掘与信息检索两门学科的交 叉边缘学科，近年来己经成为一个相对独立的研究学科，取得了长足的发展。但 是，文本挖掘又与传统的数据挖掘有很大的区别。传统的数据挖掘所处理的数据 是结构化的，其特征数目通常不超过几百个。而文本挖掘所处理的文本数据无结 构可言，特征数目也相当庞大，传统数据挖掘与信息检索的技术根本不可能处理 这种超大规模的数据，必须研究新情况下文本的自动分类技术。 文本分类作为组织和管理数据的一种有力手段，在以下环境得到广泛应用： ( 1 ) 信息检索服务【3 l 信息检索系统必须操纵大量的数据，其文本信息库可能是相当庞大的；同时 用来表示文本内容的词汇数量又是成千上万的。文本分类系统的目的就是对文本 集进行有序的组织，把相似的、相关的文本组织在一起。它作为知识的组织工具， 为信息检索提供了更高效的搜索策略和更准确的查询结果。 ( 2 ) 邮件分类1 4 对用户收到的电子邮件进行分类。例如：麻省理工学院为白宫开发的邮件分 类系统都能自动地确定每天发送给总统的大量的电子邮件所属的类别，如外交、 税收、环保、家居等，以安排适当的人员对信息进行答复。 ( 3 ) 电子会议例 电子会议是一种新兴的会议方式，所有与会者通过网络电脑系统举行会议， 与会者是匿名的，便于形成平等的气氛，以调动与会者的积极性，因此能产生大 量的意见和建议。接下来再由分类系统对这些意见进行聚类和组织，最后确定需 进一步讨论的主题。 ( 4 ) 学习用户兴趣1 6 l 把用户的兴趣做成分类模板，信息服务器可采用分类技术把特定的信息分发 给可能感兴趣的用户。 1 3 文本分类技术的国内外发展现状 长期以来，文本分类是自然语言处理的一个重要的应用领域。8 0 年代末以前， 在文本分类方面占主导地位的一直是基于知识工程的分类方法，它的主要思想是 2 中南大学硕士学位论文第一章文本分类概述 手工建造一个能进行分类决策的专家系统。这类专家系统包括了一些形如i f t h e n 的规则。一个d n f 公式是把一些连接在一起的 子旬分离开，如果至少满足其中的一个子旬，那么就可以归到该对应的类别中。 这种专家系统严格意义上来说也应该归于“手工”方法一类，这种方法的缺点是 构建自动分类器时必须要为领域专家获取的知识和知识工程师的知识表示之间 架起桥梁，二者缺一不可。如果这种分类器被转到完全不同的领域( 如不同的类 集) ，工作必须得重新开始。 9 0 年代以来，随着信息存储技术和通信技术的迅猛发展，大量的文字信息开 始以计算机可读的形式存在，并且其数量每天仍在急剧增加。这一方面增加了对 于快速、自动的文本分类的迫切需要，另一方面又为基于机器学习的文本分类方 法准备了充分的资源。后文所提到的文本分类将都默认地指文本自动分类。这种 方法通常由训练和分类两个阶段组成，把文本作为特征向量的集合对待，在训练 阶段，使用训练样本进行特征选择和分类器训练，学习分类知识，建立分类器； 在分类阶段，根据选择的特征形式化待分类的输入样本，然后输入到分类器进行 类别判定，最终得到输入样本的类别。这种方法实现简单，分类准确度也较高。 在机器学习领域，分类属于监督学习。 目前世界上一些大学、机构和公司都在致力于i n t e r n e t 上文本数据挖掘系 统的研究和开发，比如：w e bw a t c h e r l 7 j 与p e r s o n a lw e bw a t c h e r ( c 姗研制开 发) 8 1 、a l t a v i s t ad i s c o v e r y ( d e c ) 【9 】以及w o r d n e t 1 0 l 系统。 w e bw a t c h e r 7 1 是由c m u 开发的可安装在一个w w w 站点商的导游器，它对来访 的用户访问行为进行在线学习，通过对站点主页的超文本结构和以前用户浏览路 径的学习，建立起一个经验模型。当一个用户进入该站点时，系统提供一个接口 来启动w e bw a t c h e r 的导游功能，它将陪伴用户进入每一个网页，同时通过对用 户兴趣的分析，向用户建议下一步要访问的链接。 p e r s o n a lw e bw a t c h e r i s 】是一个个人化导游器，它与w e bw a t c h e r 的功用 很相似，区别在于它是面向特定的用户。 a l t a v i s t ad i s c o v e r y 9 1 是由d e c 公司开发的一个新型的桌面信息检索工具， 它提供面向桌面、i n t e r n e t 、u s e n e t 数据的无缝集成。它可以基于内容在不同 搜索空间进行检索，可自动对所搜索到的文档进行总结，寻找与当前网页相关联 的网页，如内容相似、曾对该网页进行过引用的网页。 w o r d n e t 1 0 l 是由普林斯顿大学认知科学实验室的m i l l e r ，b e c k w i t h 等人于 1 9 8 5 年起致力构造的词汇来组织词汇系统。它的最具特色之处是根据词义而不 是根据词形来组织词汇信息，可以说，它是一部基于心理语言学原理的语义词典。 它的名词按层次结构组织，动词按搭配关系组织，而形容词和副词则是以n 维超 空间方式组织的。它包含9 5 6 0 0 个不同的词形，7 1 0 0 种词义。其中名词大约有 3 中南大学硕士学位论文 第一章文本分类概述 5 7 0 0 0 个词形，4 8 8 0 0 个词义。w o r d n e t 的构造方法是：将英语词汇组织为同义 词集合( s y n s e t s ) ，以每个集合标明一个词汇概念；而每个概念又具有若干个指 针，分别指向其上位词、下位词、反义词、部分词及其完全词等关系，这样就构 成了一个比较完整的词汇语义体系。w o r d n e t 已经成为众多文本分类系统进行词 汇语义处理的词典。 国内研究起步较晚，1 9 8 1 年，候汉清【l i l 先生首先对自动分类在文献分类中的 应用做了探讨，从计算机管理分类表、计算机分类检索、计算机自动分类、机编 分类表等四个方面介绍了国外的发展概况。之后，中国科学院、清华大学、上海 交通大学、复旦大学、南京大学、山西大学、东北大学以及新加坡、香港和台湾 的一些大学的著名学者在该领域做出了一些研究成果，研制出一批基于词典法和 基于专家系统的自动分类系统。由于中文与英文存在较大的差异，不能照搬国外 的研究成果，中文文本分类的研究基本上是在英文文本分类的研究策略上，结合 中文文本的特点，继而形成中文文本自动分类研究体系。 由于自然语言理解技术本身存在的问题，在当前的计算机技术条件下，还不 可能处理具有高度不确定和模糊性的文章，因此各分类系统只能在有限的领域内 获得成功。目前，各分类系统的分类正确率都在8 0 左右“4 ，离实用化、商品 化尚有一定的距离，主要原因包括：分词算法的不足、分类主题词表的更新缓慢、 分类方法的缺陷、知识库的规模较小等。 1 4 文本分类技术简介 分类过程 图卜1 文本分类过程 一般自动文本分类有以下个阶段【1 l ( 图1 - 1 ) ： ( 1 ) 生成训练语料库的文本特征全集。 ( 2 ) 文本特征提取，形成特征子集。 ( 3 ) 采用某种数学模型和分类方法进行分类器构造。 ( 4 ) 利用训练语料库中的文本对分类器进行训练，得到分类器的相关参数。其 间，需要根据提取的特征形式化训练语料库中的文本，形式化文本的过程可以看 作是将非线性空问中的点通过非线性映射，映射到线性空问中的点的过程，或者 4 中南大学硕士学位论文第一章文本分类概述 也可以说是将文本抽象为构造分类器时所采用的数学模型的过程。 ( 5 ) 利用测试语料库，对分类系统进行测试。 由于中西文之间的差异，中文文本自动分类既有与西文文本自动分类的共同 之处，又具有自身的特点。 中文文本自动分类主要有两类方法：( i ) 基于外延的分类方法；( 2 ) 基于语义的分 类方法。 基于外延的分类方法不关心文本的语义，仅仅根据文本的外在特征进行分 类，即上文提到的统计方法。基于语义的分类方法采用全部或部分理解文本的语 义进行分类。但这种方法的进一步发展受到了自然语言处理技术的制约。目前有 研究者提出了一种基于序列的文本自动分类算法【1 3 j ，该算法利用了文本中两个层 次的语义相关性：字模式和概念节点之间的相关性，实现了对关键词的动态加权。 对含有关键词的子模式采用m a r k o v 模型来对其信号幅度进行估计，从而生成一 个待分类文本的特征序列。基于概念的归类技术t 1 4 1 抽取短语周围的文本和潜在的 语义概念进行文本类别的确定，不需要理解全文的语义，这在当i i 对中文自然语 言的理解水平尚处于初级阶段的现状来说无疑是一个较好的方法。 本文研究的是基于统计的中文文本自动分类，所涉及到的关键技术包括以下 几个方面： ( 1 ) 自动分词 自动分词是针对中文的一种自然语言处理技术。中文与英文不同，句子中各 个词条间没有固定的分割，因此首先需要对中文文本进行分词。分词是指将大字 符集上的连续字串分割成能够代表语义单元的词或者n 元词条。自动分词是中文 文本自动分类的基础，自动分词过程也是原始文本特征集的确定过程。 ( 文本模型 为了使计算机能够真正的处理文本，必须将文本表示成计算机可以处理的数 学模型。目前文本模型主要有g e r a r d s a l t o n 和m c g i l l ”】于1 9 6 9 年提出的向量空 间模型( v s m ) ，d u m a i s ，f u m a s ，l a n d a v e r 和h a r s h m a n t ”j 于1 9 9 0 年提出隐性语 义索引( l s i ) 模型，b e l k i n 和c r o a t 7 1 于1 9 9 2 年提出概率模型。这些模型从不同角 度如发，使用不同方法处理特征加权、类别学习和相似度计算问题。 ( 3 ) 特征选择 特征选择是文本分类中的一个重要环节。由于构成文本的词的数量非常之大 导致了表示文本的向量的维数也相当多，使得进行特征子集的抽取变得十分必 要。特征选择是指去除不能表示信息的词，它可以从两个方面提高系统性能：一 是提高分类效率，通过特征选择，可以大大减少原始文本特征集合中的特征维数， 提高系统的运行速度和减少运算复杂度；二是提高系统精度，通过适当的特征选 择，去除与信息表示无关的词不但不会降低系统的准确性，反而会使系统精度提 中南大学硕士学位论文第一章文本分类概述 高1 。 ( 4 ) 分类算法 文本分类方法有很多，如图1 2 所示。如，k - 近邻( i ) 【1 州，b a y e s 2 们，决 策树( d c c i s i o n t r c c ) 1 2 ，神经网络( n e u r a ln e t w o r k ) 1 2 2 ，支持向量机( s v n d 2 3 j 等。 但常用的大多数文本分类研究都趋向于两类分类问题，即一个文本与预先确定的 主题要么相关，要么不相关。然而现实中大量的文本都是由不同的主题组成的， 这样就提出了文本多类别分类问题。现在解决这个问题的常用方法是先用几种两 类分类器分类，再把预测的结果融合成一个决策。这种方法最大的缺点是忽略了 图卜2 自动文本分类算法 1 5 本文主要工作内容 本文对中文文本自动分类中所涉及的各种技术进行了全面的论述，并通过实 验方法对文本分类算法进行了深入的研究。 为了提高分类器精度，一般分类算法要求有较大的训练样本集，构造手工标 识的训练样本集耗费了人们大量的时间和精力，而网上存在大量随手可得的未标 识的文档，数目远远超过已标识类别的文档，对此本文重点研究了利用未标识文 档的半监督学习算法，通过分析，发现现有通过性能测试，发现当已标识文档很 少时，这些半监督分类算法仍然不很精确，究其原因是过于依赖已标识文档的最 初分布，没有充分利用未标识文档信息。对此，本文分类前加了聚类一步，利用 了具有代表性的未标识文档信息。并在第二步采用了专门针对于小文本的分类算 法t s v m ，有效地克服了t s v m 必须人为地指定待训练的无标识样本中的正标 识样本数的缺点。 最后，对今后的研究工作进行了展望。 本文各章安排如下： 第一章：介绍了文本分类的概念和发展状况，阐述了文本分类的系统结构，对其 应用范围进行了描述 6 中南大学硕士学位论文 第一苹文本分类概述 第二章：对文本分类各个关键技术进行了详细论述。 第三章：介绍聚类，并学习了几种聚类技术，重点分析了k - m e a n s 方法。 第四章：分析比较了各个半监督学习算法，重点讨论了t s v m ( 直推式支持向量 机) ，针对半监督算法在已标识文档很少时性能急剧下降的情况，分析其原因并 提出了基于聚类的半监督学习算法。 第五章：介绍了中文文本自动分类原型系统的设计实现和实验分析。 第六章：对本文的研究工作进行了总结。 7 中南大学硕士学位论文第二章文本分类关键技术 第二章文本分类关键技术 对于一般的模式识别系统，主要由4 个部分组成：数据获取，预处理，特征 提取和分类决策。而对于文本分类这样特定的模式识别系统，初始的数据是所给 定的电子文档，数据获取的过程可以省略掉。预处理的目的是去除噪声，加强有 用的信息，并且为后面的特征提取做准备。为了有效地实现分类识别，就要对原 始数据进行变换，得到最能反映分类本质的特征，这就是特征提取的过程，一般 把特征提取后得到的分类识别赖以进行的空间叫特征空间，在文本分类中特征空 间大多是采用文档中的关键词来表示。分类决策就是在特征空间中用统计方法把 被识别对象归为某一类别。基本做法是在样本训练集基础上确定某个判决规则， 使按这种判决规则对被识别对象进行分类所造成的错误识别率最小或引起的损 失最小。 2 1 文本特征生成 2 1 1 文本表示 常用的文本表示有：b a g - o f - w o r d s , n - g r a m s ，t e r mw e i g h t 等，计算机并不具有人 类的智能，人在阅读文章后，根据自身的理解能力可以产生对文章内容的模糊认 识，而计算机并不能轻易地“读懂”文章，从根本上说，它只认识0 和l ，所以 必须将文本转换为计算机可以识别的格式。根据“贝叶斯假设，假定组成文本的 字或词在确定文本类别的作用上相互独立，这样，可以使用文本中出现的字或词 的集合来代替文本，不言而喻，这将丢失大量关于文章内容的信息，但是这种假 设可以使文本的表示和处理形式化，并且可以在文本分类中取得较好的效果。 文本表示模型有多种，常用的有布尔逻辑模型、概率型、向量空间模型 f v s m ) 【1 5 1 【1 7 1 等。 布尔逻辑模型是一种传统的、简单而普遍使用的严格匹配模型。在布尔逻辑 模型中，它以文本中是否包含关键词做为判断依据，基于关系运算符的逻辑表达 式和关键词匹配 2 4 1 。 概率型基于贝叶斯概率论原理，不同于布尔和向量空间模型，它利用相关反 馈的归纳方法，获取匹配函数。 向量空间模型( v s m ) 是目前主要采用的文本表示模型。向量空间模型的基本思想 是以向量来表示文本：( w l ，w 2 ，w 3 w d ，其中w 为第i 个特征项的权重，特征 项一般可以选择字、词或词组，根据实验结果，普遍认为选取词作为特征项要优 8 中南大学硕士学位论文 第二章文本分类关键技术 于字和词组，因此，要将文本表示为向量空间中的一个向量，就首先要将文本分 词，由这些词作为向量的维数来表示文本，最初的向量表示完全是o 、l 形式， 即，如果文本中出现了该词，那么文本向量的该维为l ，否则为0 。这种方法无 法体现这个词在文本中的作用程度，所以逐渐0 、l 被更精确的词频代替，词频 分为绝对词频和相对词频，绝对词频，即使用词在文本中出现的频率表示文本， 相对词频为归一化的词频，其计算方法主要运用t f i d f 公式，该公式本文将在 权重的计算中详细介绍。 2 1 2 文本特征 文本特征应具有以下特征【2 5 j ； ( 1 ) 能够对文本进行充分表示的语言单位； ( 2 ) 文本在特征空间中的分布具有较明显的统计规律； ( 3 ) 特征的提取比较容易实现，计算复杂度不太大； 事实上，任何文本都可以看作是由最基本的语言符号所组成的字符串。西文 文本是由字母和标点组成的字符串，而中文文本是由汉字和标点组成的字符串。 在中文文本中，汉字是最基本的语言单位，词或短语是最小的具有语义的语言单 位。字构成词，词构成短语。因此在中文文本分类中可以采用字、词或短语作为 文本的特征。另外，在中文文本分类中也可以采用n g r a m 项作为文本的特征( 比 如在“文本特征”一词中，“文本”、“特征”、。本特”、“文本特”都可以称作n g r m n 项1 。由于文本分类是面向语义的操作，而词或短语是最小的具有语义的语言单 位，所以在中文文本分类中常采用词作为文本的特征，这样，每一个特征项用词 代表，称为特征词。 文本特征除了常用的特征词的词频9 h ( t e r mf r e q u e n c y ) 还有语义特征( s e m a n t i c f e a t u r e ) 。而将词作为分类或聚类等分析的对象是大多数文本挖掘系统的选择， 因为： ( 1 ) 词频处理不涉及语法分析，易于实现。 ( 2 ) 由于自然语言本身的复杂性，语义特征处理的过程比词频处理复杂，需 要消耗不菲的处理器时间和暂寸空间，因此在面对大量待处理文本时，效率不高。 ( 3 ) 词频相较语义特征的表示形式更直观统一，故以它为基础构建的系统更 易扩展和移植。 当然，语义特征也有词频特征无法替代的优点，例如它更加深刻地反映了文 本的褒贬倾向。对浅层语义分析的研究使得将语义特征作为文本分类的基础特征 在理论和技术上也逐渐成为可能。 9 中南大学硕士学位论文第二章文本分类关键技术 2 1 3 分词 现有的中文文本分类系统中常采用分词的方法来生成文本的特征。分词是指 将没有明显分界标志的汉字串自动切分为汉词串。它需要先建立起一部词语粒度 大小适中，数据结构合理的机器词典，再根据合适的分词算法和机器词典，将汉 字串切分为汉词串啪j 。 常用的分词方法有以下几种【2 7 】【冽： ( 1 ) 正向最大匹配法：基本思想是这样的，假定自动分词词典中的最长词是 i 个字，则取被处理材料的当前被处理字串序列中的前i 个字作为匹配字段，以 首字为入口，查找词典，若词典中存在这样的一个i 字词，则匹配成功，匹配 字段作为一个词被切分出来；如果词典中找不到这样一个i 字词，则匹配失败， 匹配字段去掉最后一个汉字，剩下的字串作为新的匹配字段，再进行匹配，如 此进行下去，直到匹配成功为止，也即完成一轮匹配，切分出一个词为止。如 果一直匹配不成功，则得到长度为l 的单字词。 。 ( 2 ) 逆向最大匹配法：基本原理与m m 法相同，不同的是分词切分方向：它 从被处理材料的末端开始匹配( 句子尾或文章尾) ，每次最末端的i 个字作为匹配 字段，匹配失败则去掉最前面的一个字。r m m 法要求配置以逆序分词词典。 ( 3 ) 逐词遍历匹配法：这是把词典中的词按照由长到短递减的顺序逐个搜索 匹配整个待处理材料，直到把所有的词都切分出来为止的方法。 ( 4 ) 设立切分标志法：这种方法首先要收集那些标志符号( 称为自然切分标志) 以外的众多非自然切分标志。例如，只充当词首的字或词尾的字，不构成词的 单字词，多字节单纯词等等。进行分词时，先扫描整个待处理材料，对这些非 自然切分标志进行搜索，根据这些标志，把句子切分为若干较短的字段，然后 再使用m m 法或者r m m 法对这些较短的字段作进一步的切分。 ( 5 ) 最佳匹配法：分为正向的最佳匹配和逆向的最佳匹配。其出发点是：在 词典中按词频的大小顺序排列词条，以求缩短对分词词典的检索时间，达到最佳 效果，从而降低分词的时间复杂度，加快分词速度。 ( 6 ) 双向匹配法：该法对同一个字串分别采用m m 法和r m m 法两种方法进 行切分处理，如果能够得到相同的切分结果，则认为切分成功，否则认为有疑点， 进行人工干预，选取一种切分为正确的切分。 ( 7 ) 最短路径法：该方法对当前被处理字串建立起字段有向图模型，即：将 当前被处理字串中所有的词都标记出( 标记的过程实质上也是字符串的匹配过 程) ，相应地，每个词赋予一条有向边，边的权值置为1 ，从中选择一条最短路径 作为切分结果( 该路径所代表的词数为最少) 。 1 0 中南大学硕士学位论文第二章文本分类关键技术 对未登录词的识别和歧义切分处理是传统分词方法中无法避免的两大难 题，这两者限制了传统分词方法的切分精度。而且，词典对切分精度造成的影响 远远大于分词方法自身产生的歧义切分错误。据统计，在含有l 万5 千个词条的 语料库中，即使用含有7 万个词条的词典进行切分，仍然有3 0 以上的词条没有 被收录，影响到后续的特征提取的效果 2 9 1 。因而在一些文本分类系统中，也开始 采用文本中的n - g r a m 项作为文本分类的特征。采用文本中的n - g r a m 项作为文 本分类的特征，不需要进行复杂的切词处理，摆脱了对词典的依赖【3 0 l 。虽然对英 文文本的分类不需要进行分词处理，但要进行词根还原的处理。即：w o r d i n g s t e m i n g t 3 1 1 。 通过对训练语料库中的中文文本进行分词后，获得整个训练文本的全部原 始特征。 2 2 特征选择与降维 经过以上步骤，得到的特征向量的维数是非常高的，如此高维的特征对即将 进行的分类学习未必全是重要、有益的，而且高维的特征会大大增加机器的学习 时间而产生很多诸如一词多义、同音异型字、同义词等等情况，或者其他一些无 意义的虚词。为了删除噪声，减少冗余度，尽可能提高分类器效率，且不影响它 的准确率，必须进行空间降维。 空间降维的方法有特征选择和特征抽取两种。特征选择所得到的特征是原来 特征集t 的子集，而用特征抽取得到的并不是原来特征集的子集，而且所提取出 来的特征集与原来特征集并不相似，如原来t 是词的集合，但提取的t 可能不 是词集。当然t 仍然是由原来的t 通过合成与转换得到的。 2 2 1 特征选择 特征选择算法一般是构造一个评价函数，对特征集中的每个特征进行独立的 评估，这样每个特征都获得一个评估分( 也称之为权值) ，然后对所有的特征按照 其权值大小排序，选取预定数目的最佳特征作为结果的特征子集。所以，选取多 少个最佳特征以及采用什么评价函数都要针对一个具体的问题通过实验来决定。 特征选择主要用于排除那些被认为无关或关联性不大的特征，依据文档集统 计数据，这些特征处于王信息量的状态：并自动将那些低频的特征用正交合并成 高频特征。 下面对目前常用的五种特征选择方法做介绍：文档频数( d o c u m e n t f r e q u e n c y ) ，信息增益( i n f o r m a t i o ng a i n ) ，互信息( m u t u a li n f o r m a t i o n ) ，妒统计法 ( c h i ) ，词条权( t e r ms t r e n g t h ) t 3 2 1 1 3 3 1 。 中南大学硕士学位论文第二章文本分类关键技术 ( 1 ) 文档频数( d f ) 在训练语料库中出现该词条的文本数。d f 值低于某个值的词条没有代表性， 从原始特征空间中移除，d f 值高于某个值的词条没有区分性，也从原始特征空 间中移除。d f 是最简单的特征提取技术，由于其具有相对于训练语料库规模的 线性计算复杂度，能够容易地被用于大规模语料统计。但是d f 值低的词条相对 于d f 值高的词条具有较多的信息量，不应该将它们从原始特征空间中完全移除。 比如，在整个训练语料库的所有文本中都出现的词条的d f 值肯定大于只在某个 或某几个类中出现的词条的d f 值，但后者所携带的信息量肯定大于前者。 ( 2 ) 信息增益( i g ) 指词条w 对于分类所能提供的信息量，也就是不考虑该词条特征的熵与考 虑了该词条特征的熵之后的差值，计算公式如下： 佑一再p ( c j ) l o gp ( c j ) + p ( 矿荟p 【c j i w ) l o gp ( c j l w ) ，( 2 1 ) + p ( w ) p ( c ，w ) l o gp ( c j w ) ；l 其中，p ( c j ) 代表c j 类文本数在整个训练语料库中所占的比例，p ( w ) 代表词w 出现的文本数在整个训练语料库中所占的比例，p ( c j w ) 代表在词w 所出现的文 本中c 类的文本所占的比例。p ( 旷) 代表词w 没有出现的文本数在整个训练语 料库中所占的比例，p ( c ，i f ) 代表在词w 所没有出现的文本中c 。类的文本所 占的比例。对原始特征空间中的词条计算其i g 值，并将i g 值低于某个值的词条 从原始特征空间中移除。 ( 3 ) 互信息( m d m i 是统计语言模型中文字相关性的一个标准测试值。在现有的测试集上定 义类c ，事先a 用来表示术语t 和类c 同时发生的次数：事件b 表示术语t 发生而 类c 不发生的次数：事件c 表示术语t 不发生而类c 发生的次数：n 是指总体的 文档数目：如此术语t 和类c 之间的m i 值就可以计算出： ， i ( t ，c ) = l o g 只( t a t ) ( 只( f ) 书只( c ) )( 2 2 ) 可用下式近似得出其估计值： ，g c ) = l o g ( a 幸忉( 似+ o 幸( 彳+ 功)( 2 3 ) 当术语t 和类c 相互独立时，上式值为零。利用这个互信息值即可得到术语t 的权值： ，一( f ) = p ，( c ，) j ( f ，c ，) j = 1 ( 2 - 4 ) 中南大学硕士学位论文第二章文本分类关键技术 ，一( f ) = m 川a x ，( f ，c f ) ) ( 2 - 5 ) ( 4 ) x 2 统计法( c h i ) 该方法类似于m i 。在现有的测试集上定义类c ，事件a 用来表示术语t 和 类c 同时发生的次数：事件b 表示术语t 发生而类c 不发生的次数；事件c 表示 术语t 不发生而类c 发生的次数；事件d 表示术语t 和类c 同时不发生的次数； n 是指总体的文档数目；如此术语t 和类c 之间的f 值就可以计算： z 2 ( f 力= 百两可n 甬* ( a 矿d - 函c b 面) 2 丽( 2 - 6 )“+ c ) ( 口+ d ) + q + 动( c + d ) 当术语t 和类c 相互独立时，上式值为零。利用这个值即可得到术语t 的权值： x 乞( f ) = e r ( c ；) x 2 ( f ，c ，) ( 2 - 7 ) x 三戤o ) = m ，m i x 2 0 ，q ) ( 2 8 ) f 的统计法效果也较好，但是文档中含低频词时，由于f 统计法的结果是规 格化的，这种情况下规格化的影响比较大。 ( 5 ) 词条权口s ) t s 方法基于术语l 在邻近相关文档中出现的频率来测试术语t 的强度。x 和 y 是任意不同但相关的文档，术语t 的权值可由下式计算出： 占( f ) = 尸，( f y t x ) ( 2 - 9 ) 但是实际中发现某些t s 值