（计算机软件与理论专业论文）基于团结构的文本分类技术研究.pdf

摘要 近年来，随着网上电子文档的数量以指数级的速度增长，文本分类技术在信 息检索、信息过滤以及内容管理等各项应用中变得越来越重要，已经成为信息检 索和机器学习中的前沿研究领域。文本自动分类是组织和管理文本信息的有力手 段，可以在较大程度上解决信息杂乱无章的问题，使用户更容易更准确地定位所 需的信息。文本自动分类是指在给定的分类体系下，对未知类别的文档进行自动 处理，并根据文档特征来判断其所属类别的过程；基于机器学习的文本分类技术 已经成为主流技术。 目前，研究者已经提出了许多成熟的文本分类算法，这些算法大都来自于模 式分类，如k n n 分类算法，支持向量机算法等。这些现有的文本分类算法大都基 于向量空间模型，没有考虑文档的语义特征信息、结构信息等。本文针对传统分 类器的不足对文本分类及其相关技术进行了研究，提出了两种有效的解决或改进 的方法和技术。 本文的研究内容和创新工作主要包括如下两点。 1 ) 本文研究了一种基于文本团的文本分类方法，通过在训练集上由文本相 似矩阵构造文本相似图，从图中提取文本团( 完全子图) ，由每个类别的团信息来 构造分类器，进而与s v m 等分类器进行组合。在复旦大学中文文本分类语料库和 2 0n e w s g r o u p s 语料库上进行实验，并同时在相同的预处理条件下，与传统的分 类方法进行了对比实验，实验表明我们提出的方法在两个数据集上较大改进了分 类性能。 2 ) 随着网页信息的快速增长，特别是i n t e r n e t 上在线信息的增加，再靠人工 的方式来处理信息是不切实际的。因此，网页自动分类己成为一项具有较大实用 价值的关键技术，是组织和管理数据的有力手段。为了有效地组织i n t e r n e t 上极 其丰富的信息资源，网页自动分类成为一个日益重要的研究领域。由于w e b 文档 有其自身的特点，近年来受到很多学者的关注，对于w e b 文档的分类，传统的文 本分类器有其自身的局限性，因此针对w e b 文档的特点，我们在传统分类器的基 础上利用了w e b 文档丰富的链接信息。在北大天网提供的数据集上的实验表明本 文分类方法再结合网页的链接信息对分类的效果有所提高。 关键词：文本分类；文本团；图模型；链接；网页分类 l i a b s t r a c t w i t ht h er a p i dg r o w t ho ft h eo n l i n ee l e c t r o n i cd o c u m e n t s ，t h ea u t o m a t e dt e x t c a t e g o r i z a t i o n ( o rt e x tc l a s s i f i c a t i o n ，t c ) b e c o m e sm o r ei m p o r t a n ti nt h ea p p l i c a t i o n s o fi n 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 nf i l t e ra n dc o n t e n tm a n a g e m e n ti nt h el a s t d e c a d e ，a n dh a sb e c a m ef o r w a r dr e s e a r c ha r e ao fi ra n dm a c h i n el e a r n i n g ( m l ) a s o n eo ft h em o s te f f e c t i v et e x ti n f o r m a t i o nm a n a g e m e n tm e t h o d s ，a u t o m a t e dt e x t c a t e g o r i z a t i o n ( t c ) h e l p sp e o p l eo r g a n i z i n ga n dm a n a g i n gt h ee l e c t r o n i ct e x tm o r e q u i c k l ya n de a s i l y t e x tc a t e g o r i z a t i o ni s t h ep r o c e d u r eo fa u t o m a t i c a l l ya s s i g n p r e d e f m e dc a t e g o r i e st of r e et e x td o c u m e n t s ，a n dt h et cm e t h o db a s e d - l e a r n i n gh a s b e c a m em a i n s t r e a mt e c h n o l o g y a tp r e s e n t ，r e s e a r c h e r sh a v ep u tf o r w a r dal o to fm a t u r et e x tc l a s s i f i c a t i o n a l g o r i t h m ，m o s to ft h e ma r ec o m ef r o mt h ep a t t e r nc l a s s i f i c a t i o n ，e x i s t i n gt e x t c l a s s i f i c a t i o na l g o r i t h m ss u c ha s ：k n na n ds v m m o s to fw h i c ha r eb a s e do nv e c t o r s p a c em o d e l ，w i t h o u tc o n s i d e r i n gt h es e m a n t i cf e a t u r eo ft h e s ed o c u m e n t s s t a r t i n g f r o mt h ei n a d e q u a c yo ft h et r a d i t i o n a lc l a s s i f i c a t i o n ，t h ea u t h o ro ft h i st h e s i sa t t e m p t s t 0d o s o m er e s e a r c ho nt e x tc l a s s i f i c a t i o na n di t sr e l a t e dt e c h n o l o g i e s s e v e r a l m e t h o d sa n dt e c h n i q u e sa r ep r e s e n t e d t h em a i nc o n t r i b u t i o n so ft h i sp a p e ra r ea sf o l l o w s ： 1 ) ac l i q u e b a s e d t e x tc l a s s i f i c a t i o nm e t h o di sp u tf o r w a r d ，w h i c h ，t h r o u g h c o n s t r u c t i n gas i m i l a rg r a p ho ft h ec o n t e x tb yas i m i l a rm a t r i xo ft h ec o n t e x tb a s e do n t h et r a i nt e x t ，a n dt h e ne x t r a c t i n gt h ec l i q u eo ft h ec o n t e x t ( c o m p l e t eg r a p h ) f r o mt h e s i m i l a rg r a p ho ft h ec o n t e x t ，w ec o n s t r u c tt h ec l a s s i f i e ru s i n gc l i q u ei n f o r m a t i o no f e a c hc a t e g o r y , a n dc o m b i n ew i t ht h es v mo rk n nc l a s s i f i e r e x p e r i m e n t so n 2 0 n e w s g r o u p sc o r p u sa n df u d a nu n i v e r s i t yc o r p u ss h o wt h a tt h em e t h o di m p r o v e d t h ec l a s s i f i c a t i o np e r f o r m a n c e 2 ) w i mt h er a p i dg r o w t ho fw e b s i t ei n f o r m a t i o n ，e s p e c i a l l yo n l i n ei n f o r m a t i o n i n c r e a s e d i ti su n r e a l i s t i ct or e l yo nh u m a nt od e a lw i t hi n f o r m a t i o n t h e r e f o r e ，t h e a u t o m a t i cc l a s s i f i c a t i o nh a sb e c o m eac r i t i c a lt e c h n o l o g yo fg r e a tp r a c t i c a lv a l u e ，a n d i ti sap o w e r f u lt o o lt om a n a g ea n do r g a n i z ed a t a i no r g a n i z i n ge f f e c t i v e l yt h e e x t r e m e l y r i c hi n f o r m a t i o nr e s o u r c e sf r o m i n t e m e t ，w 曲p a g e a u t o m a t i c c a t e g o r i z a t i o nh a sb e c o m ea ni n c r e a s i n g l yi m p o r t a n ta r e ao fs t u d y b e c a u s eo f i t so w n c h a r a c t e r i s t i c s ，t h ec l a s s i f i c a t i o no fw e bd o c u m e n th a sa t t r a c t e da t t e n t i o nf r o mm a n y s c h o l a r si nr e c e n ty e a r s b a s e do nt h et r a d i t i o n a lc l a s s i f i e r , w em a k eu s eo ft h er i c h l i n ki n f o r m a t i o n e x p e r i m e n t so nt h es e 、枞c o r p u ss h o wt h a tt h ec o m b i n a t i o no ft h e m e t h o dp r o p o s e di nt h i st h e s i sw i t hl i n ki n f o r m a t i o no fw e bd o c u m e n t si m p r o v et h e c l a s s i f i c a t i o np e r f o r m a n c e k e yw o r d s ：t e x tc l a s s i f i c a t i o n ；t e x tc l i q u e ；g r a p hm o d e l ；l i n k ；w e b p a g e s i i i c l a s s i f i c a t i o n i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：签字日期i 年月 日 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字e l 期：年月 日 导师签名： 签字日期：年月 日 基丁团结构的文本分类技术研究 第一章引言 1 1 研究背景 随着全球信息化浪潮的到来，信息的重要性与日俱增。尤其是近年来随着国 际互联网技术的发展，网络上的信息资源呈指数级增长，w e b 己经成为拥有几十 亿个页面的分布式信息空间，而这个数字仍以每4 至6 个月翻一番的速度增加。这 样一个信息化的时代，不但在给人们带来丰富信息资源的同时，也使人们陷入了 所谓的“信息灾难 。一方面，人们希望获得越来越多的信息；另一方面，在这 信息的汪洋之中，人们获取所需要的内容越来越困难。如何有效地组织和管理这 些信息，并快速、准确、全面地从中找到用户所需要的信息是当前信息科学和技 术领域面临的一大挑战。 文本自动分类( a u t o m a t e dt e x tc a t e g o r i z a t i o n ) ，是组织和管理文本信息的有 力手段，它可以在较大程度上解决信息杂乱无章的问题，使用户更容易更准确地 定位所需的信息。因此，自动文本分类已经成为一项具有重要实用价值的技术受 到广泛的关注，并得到了空前的发展和应用，例如邮件自动分类、网页搜索、网 页分类、主题索引和大型学术会议的论文组织与管理等等。并且，自动文本分类 技术在数字图书馆、个性化推送、信息过滤等领域也具有极高的研究价值和广阔 的应用前景。 自动文本分类( 简称文本分类) 是将自然文本文件根据内容自动分为预先定 义的一个或者几个类别的过程【1 ，2 1 。它是一种有指导的学习，根据一个已经被标 注的训练文档集合，找到文档特征和文档类别之间的关系模型，然后利用这种学 习到的关系模型对未被标注的文档进行类别判断。 从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文档映射 到分类体系下已有的类别中。该映射可以是一一映射，也可以是一对多的映射， 因为某些文档不但可以与一个类别相关联，也可以与多个类别相关联。该映射用 数学公式表示如下： f ：a 一) b ( 1 1 ) 其中，a 为待分类的文档集合，b 为分类体系中的类别集合。 文本分类的映射规则f 是文本分类系统的关键；它是分类系统根据已经掌握 的每类若干样本的数据信息，总结出分类的规律性而建立的判别公式或判别规 则。根据系统使用的学习方法的不同，这些判别公式和判别规则的建立和使用方 硕士学位论文 式也各有不同。在已经确定的映射规则的基础上，系统在遇到新文档时，通过计 算和判断，最终确定文档相关的类别。 自动文本分类根据其实现的技术又可以分为两类：基于知识库的方法和基于 归纳学习的方法。基于知识也称基于规则的，它的知识库存储了从专家那里获得 的关于某领域的专门知识，分类规则需要领域专家手工建立，也需要制定大量的 推理规则【3 】。这种分类方法的优点是分类准确率很高，但是由于它基于一种预先 定义的模式，存在知识库更新慢，难以移植难以保持一致性和正确性，并且需要 各领域专家，耗费大量的人力和时间。基于归纳学习的分类方法，是指利用机器 学习技术，从己知类别的训练集构造出分类函数或分类模型( 分类器) ，并利用 此分类器将未知的文档映射到给定的类别空间。实践证明，基于归纳学习的分类 方法有较强的适应性和良好的反映能力，目前几乎所有重要的机器学习算法在自 动文本分类领域都得到了广泛的应用，例如语音识别、机器翻译、字符识别等领 域中。基于机器学习的文本分类技术已经成为文本分类的主流技术，本文重点研 究基于机器学习的文本分类技术。 1 2 本文工作 从发展现状来看，文本分类技术现在已经相对成熟，但由于文本信息所固有 的一些特点，如维数过高，同义词，多义词，近义词大量存在的现象，以及分词 方法，训练集不足等等，极大的影响了分类的性能。在使用向量空间模型【4 l 的文 本分类过程中，虽然文档集的维数动辄数万，但这些属性提供的信息往往含有大 量的噪音。同时科学在发展的过程中，许多的学科总是相辅相成的，一学科的发 展会促进另一学科的发展，有的甚至不断的结合在一起成为交叉学科，因而反应 这类学科的文本信息并不能绝对的属于某类或不属于某类。现有的文本分类算法 如：k n n 、s v m 大都基于向量空间模型，没有考虑文档的语义特征信息。 在向量空间模型中，如何把文档的结构信息( 如词的位置信息、链接信息、引 用信息、作者关联信息) 结合到分类模型中，是改进分类器性能的主要方法之一， r a l i t s a a n g e l o v a 和g e r h a r dw e i k u m 5 】提出的基于图模型的分类方法，通过提取文 档的邻居信息与支持向量机【6 域贝叶斯等经典模型组合。文献【7 】通过带权标号图 表达文档的特征词条及其位置关联信息，并用于中文文本分类。 针对上述问题，我们提出了一种基于文本团的文本分类方法，通过对文本相 似矩阵构造文本相似图，从图中提取文本团( 完全子图) ，由每个类别的所有团来 构造分类器，进而与s v m 分类器进行组合【8 】。实验表明本文方法“2 0 n e w s g r o u p s 语料库”和“复旦大学中文文本分类语料库”两个数据集上均取得了比s v m 模型和 2 基丁团结构的文本分类技术研究 k n n 模型更好的文本分类效果。 本文的工作主要包括以下几点： ( 1 ) 分析了经典分类器的不足，并且针对不足之处，在传统模型的基础上， 提出了一种新的文本分类方法：基于团的文本分类方法。通过在训练集 上文本相似矩阵构造文本相似图，从图中提取文本团( 完全子图) ，在提取 文本团的算法中通过阈值来控制文本团的数量以及文本团的阶，以使文 本团的分布尽可能均匀。 ( 2 ) 在英文文本分类语料库 2 0 n e w s g r o u p s 语料库”和中文文本分类语料库 “复旦大学中文文本分类语料库”下，与s v m “g h t 等经典分类模型进行实验 比较，验证了本文提出的方法在英文文本和中文文本语料库上的分类性 能。 ( 3 ) 由于w e b 文档有其自身的特点，如w e b 文档只有较少的文本信息，大 量的噪音信息，丰富的链接信息，极大地影响了传统分类器的性能，在 传统基于内容分类器的基础上，考虑链接信息建立网页分类器；在北京 大学组织的中文w e b 信息检索评测的数据集上进行实验，分析实验结果 并验证了丰富的链接信息对w e b 文档分类的有效性。 ( 4 ) 实现了一个文本分类实验平台，能够完成多种分类模型的文本分类实验。 1 3 论文组织 本文的组织如下： 第一章：引言。简介文本分类技术的研究背景、研究目的及其意义，简述了 本文主要的研究工作。最后，罗列了本文的组织结构。 第二章：文本分类综述。介绍文本分类的基本概念、分类的流程、应用领域 以及发展前景。同时详细介绍应用于文本分类的相关技术，按文本分类系统的实 现步骤，介绍文本集合的预处理、文本表示方法、常用的分类器算法、文本 分类器的测试和性能的评价。 第三章：详细阐述了基于文本团的文本分类方法的原理和思想，并给出了具 体的算法及相应的试验结果和分析。 第四章：详细阐述了一种基于引用信息的w e b 文档分类方法及具体的思想。 并给出了相应的试验结果和分析。 硕士学位论文 第五章：总结全文，并展望进一步的工作。 4 基于团结构的文本分类技术研究 第二章文本分类概述 2 1 文本分类的基本概念 文本分类是根据给定文本的内容，将其判别为实现确定的若干个文本类别中 的某一类或某几类的过程。简而言之，文本分类就是先根据已有的样例文本，从 中找出能描述并区分文本类别的分类器( 或规则、假设、模型) ，然后利用该分 类器对新的未分类文本进行分类。它的任务就是在给定的分类体系下，根据文本 的内容自动地确定与文本关联的类别。从数学的角度而言，分类的实质是一个映 射的过程，它将未标明类别的文本映射到已有的类别中，该映射可以是一一映射， 也可以是一对多的映射。文本分类的形式化一般定义为【l ，6 1 ，对于给定的文本集 合d o c = d i ，d z ，以) 其中盈表示第f 篇文档，d o c 由m 篇文档组成；预先定义 的文档类别集合c a t = q ，c 2 ，c l c l ，c a t 总共有l c l 个类别。假设文档集合和类 别存在一个未知的目标函数： ：d o c x c a t 一 t r u e ，f a l s e ( 2 - 1 ) 文本分类任务可以描述为找到一个函数： ：d o c xc a tj t r u e ，f a l s e ( 2 2 ) 尽量逼近未知的目标函数。函数面称为一个分类器( c l a s s i f i e r ) ，或者是分类 模型( m o d e l ) 。如果面( 喀，c j ) = t r u e ，表示文档d l 属于类别c j ，并且4 为c j 的正 例；面( 喀，c j ) = f a l s e ，表示文档d i 不属于类别c j ，并n - 4 为c ，的反例。 2 1 1 文本分类任务的特点 文本分类就是将大量文本划分为一个或一组类别，使得各个类别代表不同的 概念主题。这实际上是一个模式分类任务，所以很多模式分类的算法可以应用文 本分类中。但是，文本分类是和文档的语义紧密相关，所以与普通的模式分类任 务相比有许多独特之处 9 1 。 ( 1 ) 高维特征空间 在文档特征提取的时候，有大量的候选特征。如果使用词语作为文档特征， 即使一个1 0 0 0 0 篇左右的训练文档，一般也会产生上万的候选特征。如果使用这 些特征来构造文档向量，那么向量空间的维数非常高。 ( 2 ) 特征语义相关 考虑一种避免“高维灾难 的解决办法是，假设特征之间是相互独立的，即 一个特征出现与否与其他的特征并无关系。但是，一般地，文本分类中很多特征 5 硕十学位论文 包含一些相互依赖的关系，例如：“中共 、“中央”两个词共同出现的概率较大， 存在相互依赖关系。 ( 3 ) 特征存在多义和同义现象 文本分类中一般使用词、短语等作为表征文档语义的文档特征。但是，这些 特征往往无法清晰地表达一种含义。一个特征可能有多种含义，即多义现象，如： “教授 这个特征既可以表示一种职称的含义，也可以表示一种传授知识的含义。 同时，许多相同的含义可以用不同的特征来描述，即同义现象，例如：“计算机 和“电脑”这两个特征都表示相同的含义。 ( 4 ) 特征分布稀疏 用特征词来表示文档的时候，往往特征维数非常高，而文档所出现的特征词 只占总特征词的小部分。特别是对于一篇比较短的文档来说，特征空间中，仅仅 出现少量的特征词，因此，多数特征词的出现频率都为零，导致了文档向量中大 多数的特征的值都是0 ，特征的分布非常稀疏。 ( 5 ) 基本线性可分【9 j 文本分类中，大部分类别之间不存在双螺旋结构，是基本线性可分的。所以 一些复杂的、在其他模式分类任务中应用很成功的方法，在文本分类中未必会取 得很好的效果。 2 1 2 文本分类系统的流程 要能够实现文本的自动分类，必须要有完整的文本分类系统和一整套的数据 处理流程。一般来说，一个完整的文本分类系统通常包括如下几个主要阶段：文 本预处理、文本的表示、维数约减、分类器的学习、分类器的测试以及性能评价， 如图所示： 图2 1 文本分类系统一般过 ( 1 ) 文本预处理 包括对文档集合进行格式分析并提取出重要内容，对中文进行分词、去除 停用词和稀有词等操作；对于英文要进行词干化、去除停用词和稀有词等操作。 目前对于英文的预处理技术相对比较成熟，对于中文来说，分词是最具有挑战 性的难题。 6 基于团结构的文本分类技术研究 ( 2 ) 文本特征的表示 将文本看成是出现在文本中的关键词的集合，这些关键词就是特征项。为 了能让计算机处理文本信息，必须把文本转换成计算机容易处理的表示方式。 通常将这些文档集用向量空间模型( v e c t o rs p a c em o d e l ：v s m ) 来表示。 ( 3 ) 特征降维 从文本集合得到的特征数量很大，用众多的特征来表示文本不仅不能提高 分类效率反而会导致“维数灾难。因此利用一定的方法，从预处理数据中抽 取出若干最有利于分类的特征项( 可以是具体的单词、短语，也可以是抽象的语 义、概念单元) ，每个特征项根据其重要性确定相应的权值，并把每个文档表示 成特征向量的形式。 ( 4 )训练分类器 这也是文本分类系统的核心。选择文档集合中的若干文档构成训练集，确 定分类器的各个参数或者是阈值，最终构造一个分类器。 ( 5 )分类器的测试和评价 用分类器对文档集合的测试集进行分类，得到分类结果。采用一定的评价 指标，对分类结果进行评价。 下面我们将上面五个处理模块分别进行介绍。 2 2 文本预处理 文本预处理是进行文本自动分类的第一个步骤。一般情况下，需要分类系统 处理的文档，是不能直接交由分类模型进行分类的。预处理的好坏直接影响分类 结果，各种类型文档的存储格式差别很大，而且文档可能是残缺不全或含有噪声 信息；必须经过一定的预处理，去除语料库中的噪音信息，规范化其内容，使得 文档符合分类模型的输入要求。 文本预处理操作，目的是从语料库中规范地提取主要内容，一般包括去除文 档中的格式标记、过滤非法字符、字母大小写转换、去除停用词和稀有词、词干 化处理和中文分词处理等处理步骤。 2 2 1 去除语料库中的格式标记 每个语料库都有各自固定的存储格式，有很大一部分是以网页形式存在的。 网页文件的存储格式采用的是超文本标记语言( h y p e rt e x tm a r k u pl a n g u a g e ： h t m l ) ，而h t m l 文件中都存在大量表示格式信息的标记( t a g ) 。另外，有 很多实验用的标准文本分类语料库采用了标准通用标记语言( s t a n d a r d g e n e r a l i z e dm a r k u pl a n g u a g e ：s g m l ) ；与h t m l 类似，s g m l 中的格式标记 信息一般也是需要滤去的。 当然，文档中的格式标记并不是没有用处，它可以帮助我们提取出文档中特 7 硕七学位论文 定部分的内容，同时去除无关的一些格式标记。比如对h t m l 文件来说，一般 我们只关心其中的正文、标题和超链接部分的内容，处理时就可以通过 、 和 等标签提取出相应部分的文档内容。目前对于这类语料库， 网上已经有一些开源工具以供研究者使用，例如s o u r c ef o r g e 网站上提供的 h t m l 解析器：h t m lp a r s e r 以及微软亚洲研究院提供的基于视觉的网页分割算 法( v i s i o n b a s e dp a g es e g m e n t a t i o n ：玩船) l l l l 等等。 2 2 2 去除停用词、稀有词和词干化 停用词是指一些在文档集中出现频率很高，明显对分类任务没有贡献或贡献 很小的词。一般情况下，这样的词携带的信息量很少；滤去以后可以提高分类器 的计算效率，而且对分类器的性能不会有什么影响。 事实上，停用词是语言中的功能词，中文一般称其为虚词。如文档集中出现 的副词、代词、冠词、介词和连词等不表示实际语义的虚词，都是属于停用词的 范畴。英文的功能词包括冠词、代词、介词等等，具体的比如中文包括“你、 “我 、“他、“的、“昵”、“啊 等等；英文中的a ，t h e ，i s ，a r e ，o f 等单词。 这些词本身没有太多的意义，而且往往频繁出现在每一篇文档中；因此对文档的 分类贡献不大，在试验中通常都会滤掉这些词。 另外，文档集中的一些出现频率极低的稀有词，也可以考虑滤去。因为这些 词很有可能是由于拼写错误而造成【l2 1 。 词干化处理主要是对英文语料库而言的，实际就是去除英文单词的前缀、后 缀，提取单词的词干部分。英文的单词常由前缀、词根、后缀等部分组成。具体 到句子中，单词还有性、数、格以及时态引起的词形变化。但实际上，一个单词 的不同词形，还是可以认为是在表示同一个意思。如w a l k ，w a l k e r ，w a l k e d 和 w a l k i n g ，这几个单词就可以认为是表述同一个概念的；经过词干化处理后，就 可以提取出代表这四个单词的共同词干：w a l k 。通过这样地处理，这样就可以极 大地减少文档集的文档特征项数量。 词干化处理常常采用基于自动机的规则方法，即将词形变化的规律总结成规 则，然后通过自动机的方法对词形进行转换。转换的过程当中可使用或者不使用 词典。但是，要做一个百分之百正确的词干化处理也是非常困难的，需要用到诃 性分析、句法分析甚至语义分析的信息。好在，文本分类任务对词干化处理的要 求不是很高，利用不同词干化处理算法的分类结果相差不大。 目前使用最广泛的词干化处理算法是m a r t i np o r t e r 提出的p o g e rs t e m m e r 算 法【1 3 】，本文采用的也是这一词干化处理算法。 2 2 3 中文分词 中文分词是中文信息处理所特有的步骤。与字相比，词具有更多的语义信息， 但是中文不像英文那样可以通过天然的切分标志空格分开的，而是一连串连 8 基丁团结构的文本分类技术研究 续的汉字，词与词之间没有明显的分隔。为了提取中文的词作为特征项，就必须 进行分词处理。因此，自动识别词的边界，将汉字串切分为正确的词串的中文分 词问题无疑是实现中文信息处理的各项任务的首要问题，也是中文信息处理的基 础。 目前的中文分词方法大致可以分为如下几类： ( 1 ) 机械分词方法：是基于分词词表，通过对已有词典的机械匹配来得到 分词结果。所谓机械匹配，是指与已有词典里的词进行一一匹配，若在词典中找 到某个字符串，则匹配成功，匹配不到的词常以单字的形式输出。按照每次匹配 时是优先考虑长词还是短词，机械匹配又可以分为最大匹配和最小匹配【1 4 】。按照 扫描方向的不同，机械匹配又可以分为正向匹配和逆向配配。使用较为广泛的是 最大匹配法( m a x i m u mm a t c h i n g ：m m ) ，该方法依据一个分词词表和一个基本的 切分评估原则，即“长词优先 原则，来进行分词。 对于基于词典的分词方法，影响其精度的因素有：机器词典中词目的选择和 词条的数量、机器可读词典与待切分文本中词汇的匹配关系、切分歧义、未登录 词、分词方法。词典对分词精度造成的影响远远大于分词方法本身产生的歧义切 分错误1 1 5 】。 ( 2 ) 基于统计的分词方法：该方法利用机器学习手段从语料库中直接获取分 词所需要的某些使用知识，而不需要任何词典就可以得到分词结果，因此就产生 了基于统计语言模型( s t a t i s t i c a ll a n g u a g em o d e l s ) 的分词算法。该类算法的主 要思想是：词是稳定的汉字组合，在上下文中汉字与汉字相邻共现的概率能够较 好地反映成词的可信度。基于统计语言模型的分词方法具有良好的切分歧义处理 能力。 ( 3 ) 基于人工智能技术的分词方法：应用人工智能中的神经网络和专家系统 来进行中文自动分词【l6 1 ，以实现智能化的中文自动分词是近年来研究的一个热 点。该类算法的分词过程是对人脑思维方式的模拟，试图用数学模型来逼近人们 对语言认识的过程。 中文分词技术面临的两个最大问题是切分歧义和未定义词识别问题。前者要 解决自然语言理解的问题，根据上下文环境，在不同切分结果中选择最优解：后 者要解决词典中未收录词( 如人名、地名、机构名等) 的识别。虽然可以在机械 匹配的基础上通过规则的方法来求解上述两个问题，然而规则方法很难穷尽真实 文本的各种现象。目前比较主流的方法是通过对真实文本的概率统计来求解切分 歧义和未定义词识别问题。 目前，国内有多家单位进行了中文分词方面的研究；其中包括清华大学、北 京大学、中科院计算所、微软研究院、东北大学和哈工大等多家研究机构。他们 在这方面的研究取得了一定的成果，并开发出了一些较为成熟的中文分词系统。 经过比较，本文实验的中文分词处理部分，采用了分词效果比较好的中科院 q 硕士学位论文 计算所开源项目“汉语词法分析系统i c t c l a s 系统( 下载地址为： h t t p ：w w w n i p o r g c 邮r o j e c t p h p ? p r o j _ i d _ 6 ) 。 2 3 文本表示方法 计算机并不具有人类的智能，人在阅读文章后，可以根据自身的理解能力产 生对文章内容的认识，而计算机并不能轻易地“读懂”文章。所以我们必需把得到 的文档信息转换为计算机可以接受和识别的格式。 为了处理上的方便，通常的文本表示方法大都采用贝叶斯假设。贝叶斯假设 认为组成文本的字或词在确定文本类别的作用上相互独立；这样就可以使用文档 中出现的字或词的集合来代替文档。这样处理将丢失大量关于文档内容的信息， 特别是文档中的所有结构信息都将丢失；但文本只使用向量表示要方便很多。文 档的形式化的表示方式使得我们可以采用各种统计和机器学习的方法对文档进 行处理。从已有的研究结果看，这种文本表示方式是可以在文本分类任务中取得 较好效果的。 目前，在文本分类任务中，人们普遍使用的文本表示方法是向量空间模型 ( v e c t o rs p a c em o d e l ：v s m ) 0 7 , 1 8 , 1 9 1 。在v s m 中，文档被看作是由一组正交词 条构成的向量v ( d ) ：v ( d ) = ( a l ，a 2 ，a l t l ) 其中a j 为词条j 的权值，表示该词 条在文本中的重要程度。这样如果有n 个文本，则可以构成一个二维的n * m 阶 的矩阵a ，其中第i 行代表第i 个文本，第j 列代表第k 个词条( 特征) ，a i k 则 代表第k 个词条在第i 个文本中所具有的权值。 权值的计算方法有很多，如概率的方法，信息论的方法等 2 0 , 2 1 】；但一般都是 基于以下两种考虑： ( 1 ) 一个词在某篇文档中出现的次数越多，则对识别文档的贡献越大； ( 2 ) 一个词在不同文档中出现的次数越多，则它区分不同文档的能力越弱。 2 3 1 布尔权重 布尔权重( b o o l e a nw e i g h t i n g ) 也称为二元权重或二值权重( b i n a r y w e i g h t i n g ) ，是最简单的一种权重计算方式。即，如果文档中出现了该词，那么 文档向量的该值为1 ，否则为0 。 即： ：j l i f 驴o ( 2 - 3 ) l 0o t h e r 这种方法的缺点是无法体现这个词在文本中的作用程度。 2 3 2 词频权重 词频权重( 庇嗍f r e q u e n 钞w e i g h t i n g ) 也是一种较为简单的权重表示方式， 1 0 基于团结构的文本分类技术研究 即，使用词的频数作为词的权重。在词频权重中，词i 在文档k 中出现的频率就 是词i 在文档k 中的权重，即： a k = 丘( 2 4 ) 2 3 3t f - id f 权重 前两种权重都没有考虑词的文档频数信息。o a f 权重( t e r m sf r e q u e n c y l n v e r s ed o c u m e n tf r e q u e n c ew e i g h t i n g ) 2 0 , 2 2 1 综合考虑了矿和缈的影响，不但考 虑了词的文档频率信息，而且也利用词的逆向文档频数对词频作加权处理，这种 权重计算方法认为词的文档频数越大，该词的重要性越低。 ：f kx l o g f 盟1 ( 2 - 5 ) 吩 公式( 2 5 ) 中，当_ ，l ，时，权重为0 ，在小数据集中经常发生这种情况， 为了防止这种情况发生，一般会对公式做平滑处理，公式转化为如下式所示： = l o g ( 川o ) 北g ( 半j ( 2 - 6 ) 2 3 4t f c 权重 t f i d f 权重没有考虑文档长度的不同，对词的权重的影响。加权重不仅考虑 矿和彬的影响，也考虑了文档长度不同对词权重的影响。咖权重【2 0 1 对矿缈权 重作了“归一化处理，这样可以使每个文本的特征权向量都变成长度为1 的单 位向量。 口髓2 f axl o g ( i n ) ( 2 - 7 ) 2 3 5it c 权重 讹权型2 1 1 是矿砂权重的一种变化形式，可以看成是对公式( 2 7 ) 的归一 化处理，其计算方式没有直接使用词条的词频信息，而是采用了一种词频的变换 形式：词频的对数形式。经过这样的处理，可以降低词频大小的差异对权重计算 的影响。加权重公式如下式所示： 口趾2 崦cf a + 1 o ) xl o g n 鲁 ( 2 - 8 ) 硕+ 学位论文 或 口磕2 - 咄+ 1 o , x l o g ( 鲁“。) ( 2 9 ) 2 4 降维技术 文本分类的一个核心难题就是特征空间的高维性( 1 l i g hd i m e n s i o n a l i t y ) ，一个 文档集中的特征项动辄就是上万维，这么高的维数特征不仅带来极高的计算复杂 度，产生维度灾难，也给分类过程带来了大量的噪音，且容易产生过度拟合( o v e r f i t ) 的问题，因而有必要简化原始的特征集，这种简化技术就是降维技术。降维技术 主要分成两大类：特征选择和特征提取也称特征重构。下面我们简单介绍常用的 特征选择和特征提取算法。 2 4 1 特征选择 特征选择又称独立评估法，在进行特征选择时一般都是利用某种评价函数独 立地对每个原始特征项进行评分，然后将它们按分值的高低排序，从中选取若干 个分值最高的特征项。选择并没有改变原始特征空间的性质，只是从原始特征空 间选择了一部分重要的特征，组成一个新的低维空间。评价函数的好坏是影响特 征选择的关键问题。目前比较成熟的特征选择方法主要有：文档频数、信息增益、 期望交叉熵、互信息、文本证据权、几率比、卡方统计量( c h i ) 2 3 1 等。 1 基于文档频率的d f ( d o c u m e n tf r e q u e n c y ) 方法 这是最简单的一种评价函数，文档频数d f ( t ，) 是指在所有的训练文本中出现 了项厶的文本数。该方法假设所谓重要的项是指那些属于同一类而频繁出现于一 组文档中的项，能很好表示类别主题的项集应该被属于同一类的大多数文档所采 用。虽然该方法的原理简单，但从实际的使用情况看【l 】，其效果还是很不错的。 但文档频率也有缺点，因为稀有单词可能包含着重要的判断信息，不宜用d f 大 幅度地删除词。 2 信息增益( i n f o r m a t i o ng a i n ) 信息增益是通过观察一个项是否出现在文档中所获得的能够用于分类预期 的信息量，常用于决策树技术中选择最佳节点。它利用的是信息论中熵( e n t r o p y ) 的概念。 在信息论中，熵是对事物不确定性的一种度量。设s 是s 个文本构成的训练 集合。c ： c 。，c ：，c 。) 为类别集合。设s ，是s 中属于类c ，的文本数，则一个文本 关于其类别的熵( 即期望不确定度) 为： 1 2 基丁团结构的文本分类技术研究 ( s l ，s 2 ，霸) = _ 矗l 0 9 2 ) ( 2 1 0 ) 其中，p ，是任意样本属于类c ，的概率，该概率可以用唧s 来估计。 根据项t 是否在文本中出现，可把样本集分为两类，一类a 是t 在其中出现了 的文本，另一类b 是t 没有在其中出现的文本。则a 类中的文本关于其类别的熵为： 耶) = - 比i t ) l 0 9 2 鹏l t ) ( 2 - 1 1 ) 其中，p ( c ，it ) 表示当to a 现在文本中时，文本属于类c ，的概率，可用a 中属 于类c i 的文本数与a 中所有文本数的比值来估计。与之类似，b 类中的文本关于其 类别的熵为： = - x p ( c ，it ) l 0 9 2p ( c fif ) ( 2 1 2 ) 其中，p ( c ，i 力表示当t 没有出现在文本中时，文本属于类c ，的概率，可用b 中属于类c ，的文本数与b 中所有文本数的比值来估计。 因此，如果训练文本集按项t 来划分的话，文本关于其类别熵将变为： ，o ) = p ( f ) e o ) + p ( f ) e ( 0 ：一p ( f ) 窆p ( c ，。g ：p ( c ，lf ) 一p ( f ) 窆p ( q 。g ：p ( qif ) 2 1 3 其中p ( t ) 为项t 在文本中出现的概率，可以用 ai 。s 来估计，p ( f ) 为项t 不在 文本中出现的概率，可以用lb l s 来估计。一般情况下，此时的熵将比原来的熵 i ( s l ，s 2 ，s n ) 更小，即这个项给我们提供了一定的信息，使得分类时的不确