（信号与信息处理专业论文）网络文本信息的自动分类方法研究.pdf

网络义奉信息的白动分类方法研究摘要 网络文本信息的自动分类方法研究 摘要 随着网络信息量的迅速增长，网络信息分类已经成为人们获取有 用信息不可缺少的工具，文本自动分类系统是信息分类的重要研究方 向，它是指在给定的分类体系下，根据文本的内容自动判别文本类别 的过程。 本文首先回顾了文本自动分类的技术发展状况和与之相关的一 些看法，目前，向量空间模型是进行大规模文本处理的最佳模型，接 着本文对向量空间模型进行了回顾和总结，包括：向量空间模型的基 本概念、特征项的选择、特征项的提取算法等。然后，介绍并比较了 几种常用的基于向量空间模型的文本自动分类算法，同时描述了具体 的算法步骤。 本文讨论了一种实际可行的文本自动分类系统，它由训练过程、 分类过程两个部分组成，系统采用细致的模块化设计，具有很强的扩 展性和灵活性。在此基础上，进行了一系列的测试，对几种分类方法 的性能进行了比较，实验数据表明s v m 和k n n 方法的效果都好于n b 方法，而s v m 的分类效果一般也稍稍好于k n n 的效果。 本文针对不同类别的训练样本数量往往存在差异的情况，探讨了 训练集样本的不平衡对分类效果的影响，并且从样本和分类算法两个 角度提出了相应的解决办法，通过实验得到了相关的实验数据。这些 数据表明：训练样本的不平衡性通常会对分类效果产生影响，不平衡 的程度越大，影响的程度也越大；不平衡性对采用不同特征提取算法 的分类系统的影响不同，对采取信息增益的分类系统影响要比别的方 法的系统大一些。最后，通过样本增减和对分类算法的系数进行调整 的办法，对训练集的不平衡性进行控制，取得了一定的效果。 关键词：文本自动分类向量空间模型( v s m ) 文本预处理特征 网络文奉信息的自动分类方法研究 摘要 抽取不平衡学习 r e s e a r c hi n 玎可t e r n e t - 0 t i e n t e dt e x tc l a s s i f i c a t l 0 n a bs t r a c t i nt h i st h e s i s t h es t a t eo ft h ea r to fa u t o m a t i ct e x tc l a s s i f i c a t i o n t e c h n o l o g yi sr e v i e w e da n ds o m eo f t h ei s s u e sr e l a t e dt oa u t o m a t i ct e x t c l a s s i f i c a t i o na r ed i s c u s s e d an u m b e ro fc l a s s i f i c a t i o na p p r o a c h e s ，t h e s u p p o r t v e c t o rm a c h i n e ，k - n e a r e s tn e i g h b o ra n dn a i v eb a y e s ，a r e c o m p a r e d i nt h em e a n t i m e ，t h ep r o b l e mo fi m b a l a n c e dl e a r n i n g i s r e p o r t e d ，t h a ti s ，o n ec l a s si sr e p r e s e n t e db yal a r g en u m b e ro fs a m p l e s w h i l eo t h e r sa r eo n l yaf e w i ti sd e m o n s t r a t e de x p e r i m e n t a l l yi nt h e t h e s i st h a tt h ei m b a l a n c e si ns a m p l e sd od e g r a d et h ep e r f o r m a n c eo f s t a n d a r dc l a s s i f i e r s s e v e r a la p p r o a c h e sa r et h e ne m p l o y e dt od e a lw i t h t h ep r o b l e m t h ed e t a i lw o r ko ft h i st h e s i si si n t r o d u c e di nf o l l o w i n gt e x t a tf i r s t ，t h en e c e s s i t ya n dt h es t a t eo ft h ea r to fa u t o m a t i ct e x t cl a s s i f i c a t i o nt e c h n i q u ea r ei n t r o d u c e d t h em e t h o d sf o ra u t o m a t i c c a t e g o r i z a t i o ns y s t e m sd e s i g n i n ga r er e v i e w e d t h ea i ma n dt h es t r e s s e s o ft h i st h e s i sa r ea l s oe x p l a i n e d t h eb a s i cs t e p so fa u t o m a t i ct e x t c l a s s i f i c a t i o n i m p l e m e n t a t i o nt e c h n i q u e s ，i n c l u d i n g t h et e x t p r e p r o c e s s i n g ，t e x tr e p r e s e n t a t i o n ，f e a t u r es e l e c t i o na n dw e i g h t i n g ，a l e d i s c u s s e d s e c o n d l y , ac l a s s i f i c a t i o ns y s t e md e s i g n e di ss h o w n t h es y s t e mi s d i v i d e di n t ot w op a r t s ，t r a i n i n gp r o c e d u r e ，c l a s s i f y i n gp r o c e d u r e ，w i t ha g o o ds c a l a b i l i t ya n df l e x i b i l i t y b a s e do nt h es y s t e m ，t h e r ei s s h o w na n u m b e ro fd i f f e r e n ta p p r o a c h e st ot h ea u t o m a t i ct e x tc l a s s i f i c a t i o n ，s u c h a ss u p p o r tv e c t o rm a c h i n e ，k - n e a r e s tn e i g h b o ra n dn a i v eb a y e s ，a n dm u c h w o r ko na n a l y z i n go ft h e s em e t h o d sh a sb e e nc a r r i e do u t 2 网络义奉仿息的自动分类方法研究摘要 t h i r d l y , i m b a l a n c e dl e a r n i n gh a sb e e nd e a l tw i t h w ec o n c e n t r a t eo n f i n d i n go u tw h a tt y p e o fi m b a l a n c ei sm o s td a m a g i n gf o rs t a n d a r d c l a s s i f i e r s e v e r a lm e t h o d st ot a c k l et h ep r o b l e ma r ep r o p o s e da n de f f o r t s o nt e s t i n gh a v eb e e nm a d e a tl a s t ，a d v a n t a g e sa n ds h o r t c o m i n g so ft h ep r e s e n tr e s e a r c ho n a u t o m a t i ct e x tc l a s s i f i c a t i o na r ed i s c u s s e da n ds o m ed i r e c t i o n sf o r f u t u r er e s e a r c ha r es u g g e s t e d k e yw o r d s ：a u t o m a t i ct e x tc l a s s i f i c a t i o nv e c t o r s p a c e m o d e i ( v s m ) t e x tp r e p r o c e s s i n g f e a t u r e s e l e c t i o ni m b a l a n c e dl e a m i n g 3 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在蔓年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 网络文本信息的自动分类方泫研究绪论 1 1问题的提出 第一章绪论 2 1 世纪是信息的世纪，i n t e m e t 以惊人的速度在发展，信息也成为最宝贵的 资源。i n t e m e t 是当今世界上最大的全球性信息网络，是一个巨大的数据、信息 和知识的网络。它的高速发展对当前信息科学的现状和发展都产生了相当大的影 响。i n t e m e t 创造了一个崭新的信息网络环境，提供了便利的信息获取与传输的 渠道和工具。无论你需要什么信息，i n t e m e t 都将通多种方式来提供给你详实的、 超过其它方式的电子信息服务。只需要一台普通电脑，就可以通过i n t e m e t 联网， 利用i n t e m e t 所提供的服务性资源去查询和获取i n t e m e t 上的信息资源。可以说， i n t e m e t 现在已经成为世界上规模最大的信息资源宝库，它已经与人们的生活息息 相关，成为人们工作和生活中不可缺少的一部分。世界各地数以千力计的人都利 用i n t e m e t 进行信息交流，资源共享。你可以针对你所关心的主题，通过电子邮 件定期收到最新的信息，同时你还可以在网上尽情漫游，寻访和搜索各种类型的 信息库、图书馆。现在i n t e m e t 上蕴藏的数据、信息、知识已无法计量。w w w 的发展使信息量急剧膨胀，有用或无用的信息充斥在我们的眼前。因此，如何有 效地提取于己有用的信息成为一个亟待解决的问题。 面对海量的数据和信息，目前有几种获取有用信息的方式。譬如，可以通过 浏览相关的网站获取需要的信息；当信息无法定位而查询的目标又比较明确时， 可以通过搜索引擎首先进行信息的定位；另外还可以通过订阅电子报干| j 杂志获得 感兴趣的信息资源。但是，从近期的发展来看，i n t e m e t 上的信息资源寻找仍然 存在很多问题。例如，进入i n t e m e t 的信息在组织上的无序和缺乏规律性，使人 们要获得某一领域的全部信息必须付出相当的时间和精力，而结果却未必能令人 满意。此外，现有的搜索引擎虽然以目录结构提供信息，但是其搜索的结果往往 不能尽如人意。 所有这些亟待改善的现状都呼唤着信息自动分类技术的发展与应用。如果能 够将网络上的文本进行分类，使现有信息的组织性更强，就可以大大提高文本信 息的使用效率，方便人们获取更多的有用、有效的信息。因此，对文本自动分类、 尤其是对超文本文档的处理可以说是目前所急需的。信息自动分类作为一项基础 嘲络义奉信息的自动分类方法研究 绪论 性研究，对于已有的网络信息资源的组织以及搜索引擎性能的改善都将有很大的 帮助作用。另外，对于信息过滤技术，信息的分类也往往作为其关键部分而存在， 如网页过滤，电子邮件过滤等等。这些应用的核心技术之一就是要从大量的信息 中区分出需要保留或滤除的主题信息。过去人们对于所有的文本信息，都是通过 人工的方法进行分类加工，这项工作需要耗费专业人员大量的时间和精力去完 成。并且由于主观性的差别，难以保证一致性和准确性，导致适用性很差，有可 能在花费了大量的人力物力后，分类加工的结果还存在不小的差异。而随着网页 信息的快速增长，特别是i n t e m e t 在线文本信息的增长，再靠人工的方式来处理 是不切实际的。利用计算机对这些文本信息进行自动分类是一个可行的办法，它 速度快并且准确率较高，同时分类结果的可信度也相对比较高。因此，文本自动 分类技术已经成为一项具有较大实用价值的关键技术，近年来发展得很快。 1 2历史回顾 1 2 1 国外文本自动分类的研究 国外对于文本自动分类的研究始于上个世纪5 0 年代。经过几十年对文本自 动分类方法和实现技术的研究，已开发出若干种文本自动分类的方法。下面对一 些方法进行简单的介绍： 1 ) s v m ( s u p p o r t v e c t o rm a c h i n e s ，s v m ) s v m ( s u p p o r tv e c m rm a c h i n e s ，s v m ) 是一种相对较新的学习算法，由v a p k i n 等人于1 9 9 5 年提出 1 ，2 】。最初提出该算法是为了解决模式识别中的二分问题。 该算法基于结构风险最小化原理，对边界错误进行了理论上的探讨。该方法指在 一个向量空间中，寻求一个能够最好地区分出训练集在该空间中表示的向量点集 的决策面。为了更好地定义最佳决策面，引入了类别间余量的概念。在线性可分 空间中，最佳平面是一个超平面，s v m 方法就是要找出最大化这个余量的决策 面。 2 1k n n k 最近邻分类器，作为一种统计学习方法在模式识别领域已研究发展了4 0 多年。它是一种基于样例的懒惰的学习算法【4 】。这种算法的基本思想如下：从 训练集中求出与待分类文档的距离最近的k 个文档，然后根据这k 个文档的类别 来权衡待分类文档的类别。待分类文档的类别权重用它与相邻文档之问的相似度 度量。如果这k 个文档中有若干个属于同一个类别，则将它们的类别权重累加， 2 嘲络文本信息的自动分类方法研究绪论 得到的和就是待分类文档属于该类别的可能性度量值。对每个类别的可能度数值 进行排序，就得到了待分类文档归入各类别的可能性大小的排列。通过对每个类 别定义阈值，就可以判断待分类文档是否可以归入某一类别。每个类别的门限可 以通过对训练集的学习得到。在早期的文本自动分类的研究中就已应用了这一方 法。经过r e u t e r s 标准语料库的测试验证了基于这种分类算法的分类器具有比较 好的性能5 1 。 3 ) n a i v eb a y e s 模型 n a i v eb a y e s 概率分类器在机器学习中得到了比较深入的研究 6 ，7 】。n a i v e b a y e s 分类器的基本思想是用词与类别的互概率来估算某篇文档被归入某类的概 率。该模型的n a i v e 部分是假定词与词之间是相互独立的，即假定某类别中一个 词的条件概率与该类中其他词的条件概率无关。由于在单词预测过程中不使用单 词混和计算，使得其计算复杂度相对比较简单，也大大地提升了运行效率。 4 ) n e u r a ln e t w o r kq 附) n e u r a ln e t w o r k ( n n ) 技术在人工智能领域得到深入的研究 8 】。w i e n e r 9 】和 n g 1 0 曾分别用r e u t u e r s 2 1 4 5 0 语料集对通过这种方法实现的系统进行了测试。 w i e n e r 尝试了感知模型( 不含隐含层) 和三层神经网络( 含隐含层) 两种模型。 n g 只采用了不含隐含层的神经网络模型。他们所实现的系统为每个类别都分别 实现了一个分类器，对输入的词( 包括更复杂的特征项如文档空间的单文档向量) 和输出的类别之间的非线性映射进行学习。对n n 进行训练往往比训练一般分类 器需要多得多的时间。如果每个类别制造一个分类器，那么对r e u t e r s 测试集来 说，要训练出的所有类别将是一个非常巨大的工程。 5 1l l s f l l s f 由y i m i n gy a n g 提出【li i ，通过对训练集文档及其所属类别的自动学 习可得到多变量回归模型。训练集文档被表示为输入输出向量对，输入向量是训 练文档的空间向量表示( 每一维是带权重的词) ，输出向量是文档与类别之间关 系的二值化表示。通过在训练集上求解线性最小平方调整得到词与类别之间的回 归系数矩阵。这个矩阵代表了任意文档到类别权重向量的映射。对类别权重向量 进行排序，就得到某篇文档对各类别隶属度的排序。对每个类别进行学习得n f - 3 限阈值，就可以得到完整的分类模型了。这个阈值的确定也是通过对训练集的机 器自动学习得到的，类似于k n n 方法。 l l s f 方法和k n n 方法虽然在统计学上区别很大，但是用这两种方法实现 的分类器性能很相似。在对r e u t e r s 测试集，m e d l i n e 文摘集以及m a y oc l i n i c 患者纪录的测试中都显示了二者性能上的相似。 6 ) r o c c h i o 模型 嘲络义奉信息的自动分类方法研究绪论 r o c c h i o 是利用向量空间法进行分类的模型 1 2 】。利用训练集文档构造每个 类别的向量原型，待分类文档与类别之间的相似度度量由计算待分类文档的空间 向量和类别原型向量之间的距离决定。可以认为类中心向量法是它的特例。 r o c c h i o 公式 w - 弦：毗+ 盟一y 壁 ，2 ( t聆一刀( 其中w f 是类c 中心向量的权重，n 。是训练样本中正例的个数，一，是文档 向量的权重，分类的公式为 c s v c ( d , ) = w 。x ， z w q x g 面露。 1 2 2 国内文本自动分类领域的发展 国内文本自动分类的相关研究开始于上世纪八十年代初。到目前，我国已研 制出一批辅助分类系统及自动分类系统。 1 9 8 4 年，广州中山图书馆的莫少强制造出一个辅助归类系统，通过人工主题 分析，系统完成查表、自动归类及附表调用；【1 3 】 1 9 8 6 年，上海交通大学的朱兰娟构造出自动归类系统，定义类主题词表，检 索类主题词并累计其类隶属度，根据b a y e s 最小损失原则确定分类； 1 4 ，1 5 】 1 9 8 9 年，天津医学情报所的张炳恒制造出辅助归类系统，将分类法类名分解 为单元词，人工主题分析及单元词组配，系统确定类号；【1 6 ，1 7 】 1 9 9 5 年，南京大学的苏新宁等制造自动归类系统，定义主题词与类号关系表， 分类前控词典和停用词表，确定权重系数：【1 8 】 1 9 9 5 年，杭州应用工程技术学院的叶新明制造自动归类系统，运用类名主题 词表，组配词表，非用词表，匹配算法，二字先行，单字进或退；【1 9 】 1 9 9 5 年，清华大学电子工程系的吴军构造自动归类系统，以语料相关系数作 为分类依据，字频、词频及其常用搭配为补充，采用停用词表，人工指导分类； 【2 0 】 1 9 9 7 年，上海交通大学的王永成和张坤构造自动分类系统，采用部件词典技 术，自动分类用关键词分类归属表； 2 1 】 1 9 9 7 年，山西大学计算机系刘开瑛构造自动归类系统，采用三维加权算法， 分词采用最长匹配算法，类别词加权，语料中抽词。【2 2 】 4 嗍络文奉信息的自动分类方法研究绪论 1 9 9 8 年，东北大学计算机系的张月杰、姚天顺等研制的新闻预料汉语文本自 动分类模型，通过计算预定义类别和文本特征之间的相关性来进行自动分类。该 分类方法的特征向量规范化，采用多重加权处理方法。 2 3 】 1 9 9 9 年，邹涛、王继成等开发的中文技术文本自动分类系统采用了向量空间 模型和基于统计的特征词提取技术，能够根据文本的具体内容将其分配到一个或 者多个类别。 1 9 9 9 年北京系统工程研究所的何新贵、彭普阳研制的基于模糊技术的中文文 本自动分类系统。【2 4 】 1 2 3 文本自动分类目前存在的一些问题 从前面的介绍可以了解到，从国内外的发展来看，文本自动分类己取得了显 著的成效。尤其是一些西方国家对此领域的探讨使文本自动分类在理论和实践上 都取得了很大的进展。一方面，有关统计学习的算法越来越完善，另一方面，随 着硬件设备的发展，很大程度的提高了大规模的统计学习的运算速度。同样，国 内外的技术交流十分频繁，国外的新算法的出现，都会被很快的应用到中文文本 自动分类，目前国内的中文文本自动分类的发展与国际基本保持一致，但现在国 内的中文文本自动分类还存在一些问题： ( 1 ) 中文本身处理的方法还不完善。例如分词算法的不足。汉语词之间不像 英语等有自然的切分标记，到目前为止，各种分词算法对歧义切分都尚且没有较 好的解决方法。这一问题同样也困扰着自动文摘、自动翻译等领域。 ( 2 ) 分类主题词表的不足。各学科发展异常迅猛，分支学科、边缘学科不断 涌现，使得词表的编制总是落后于科学的发展，使得基于词典的切分算法总会有 一些新词切分不出，也就导致了一部分文献无法分类。这也是各系统都还需要人 工干预的原因。 ( 3 ) 程序、算法本身的不足。由于研究者个人知识水平的限制，且研究者大 多是个人行为，缺少合作，难以做到集思广益，往往使得软件仅能适用于某一个 小的领域，局限性很大，低水平重复现象比较普遍。另外，现有的算法虽然理论 上比较完善，但是实际实现时还会受到客观的条件限制，致使分类效果也受到影 响。在本文中将对几种常见的分类方法进行比较，通过实验说明究竟哪些因素在 影响分类效果。 ( 4 ) 分类的基础因素的不定性。例如，分类的语料库的问题，因为分类的时 候语料库的选取，以及语料库本身的构建方面存在的问题往往会直接影响分类的 网络义奉信息的自动分类方法研究 绪论 结果，尤其是分类语料的不平衡性，即可f l b ) l l 练语料中的某类很多或者很少，这 样对训练的结果有着很大的影响，并将进而影响到分类的结果，本文将就这种不 平衡性的解决办法予以探讨。 1 3 本论文的选题依据及组织结构 以自然语言形式存在的文本作为信息载体的一种主要形式，广泛的存在于互 联网上，因此文本自动分类问题具有很高的研究价值。 我们首先实现了一个文本自动分类的系统，再通过系统进行进一步的实验研 究，现有的文本自动分类的方法大约有十几种，作者首先对几种较为常用的方法， 即支持向量机( s v m ) 、k 最近邻分类器( k n n ) 、n a i v eb a y e s 模型方法( n b ) 进行比较研究，即在分类系统中的分类器构造模块通过以上三种方法进行实现， 这样分类器可以对几种方法都进行实验。本文中先对这几种算法进行了对比和评 价，从而对其各自的性能有一定的了解。 另一方面，我们从训练过程的角度出发，考虑训练集的具体情况对文本自动 分类的影响。一个文本自动分类系统的好坏不单单依靠它所采用的算法，还和其 他很多因素有关，如编程实现的方法、机器的性能、系统用来学习的训练集等， 其中作为文本自动分类的最基础的因素，训练集的质量起着十分重要的作用，它 的质量的好坏，直接影响到系统的最终能力。随着文本自动分类的不断发展，训 练集不平衡的学习方法也是现有文本自动分类的一个重要的研究方向，但是在某 些方面，尤其是在中文文本自动分类方面的工作十分有限。我们这里研究的有关 训练集的不平衡指的是训练样本数量的不平衡，即类别与类别之间的样本数量不 等导致的不平衡。当然训练集还有其它因素，如来源、是否进行处理等，由于时 间以及个人能力的原因，暂时未进行研究。研究将从不平衡与分类结果之间的关 系出发，即不平衡会对分类结果造成什么样的影响，并通过实验对此进行说明， 指出不平衡的程度与分类结果之间的关系。基于此基础之上，继而提出了几种解 决不平衡的办法，一方面从样本的角度去消除不平衡性，另一方面结合具体分类 算法，使得分类器对数量少的样本的识别能力有相应的提高，最后通过实验，对 几种方法进行了评价，取得了不错的效果。 具体论文组织结构如下： 第一章：绪论，阐述了文本自动分类技术的历史由来以及现在国内外的发展 现状，考察了已有分类方法和分类模型，并给出了本论文的选题方向和研究重点； 第二章：文本自动分类的关键技术探讨，详尽讨论了文本自动分类技术实现 6 网络义本信息的自动分类方法研究绪论 过程的若干关键环节，如文本预处理、篇章表示、特征抽取、权重评价等，并提 出分类类别的选取依据，同时以分类系统的构造过程为主线，分析了现有方法的 特点和存在的不足； 第三章：文本自动分类系统结构与介绍。通过对我们实现的自动分类系统的 结构的介绍，阐述分类各个环节具体的实现方法，最后介绍了分类的评价方法； 第四章：文本自动分类的方法，描述常见的几种分类方法，向量空间模型 ( v s m ) 方法、k n n 方法、朴素贝叶斯方法( n b ) ，并介绍它们各自的特点； 第五章：不平衡学习分类的研究，在对语料库技术的研究中发现，一般的分 类方法都是采用比较平衡的训练集来训练分类器，但是现实生活中又存在很多不 平衡的分类情况，所以就分类训练样本的不平衡性问题做了阐述，并就这种不平 衡性对分类可能造成的影响进行了分析，并提出了一些解决办法，对解决办法也 做了比较； 第六章：结束语。分析现在分类工作上已有的成绩及不足之处，阐述从事文 本自动分类研究的感想和对今后工作的几点看法。 7 嗍络义本信息的自动分类方法研究义本自动分类的关键技术探讨 第二章文本自动分类的关键技术探讨 2 1文本自动分类概述 文本自动分类本身来说是一个比较新的研究方向，它的出现来自于信息时 代对信息加工处理的需要，它的理论基础和相关技术则是在信息检索、自然语言 理解、机器学习和模式识别等学科领域已有的理论和技术基础上发展起来的。从 它的研究进展和已研制出的分类系统来看，中文和英文自动分类系统既有互通之 处又存在着差异。 简单的说，文本自动分类的任务是：在给定的分类体系下，根据文本的内容 自动确定与文本关联的类别，分类系统的输入是需要进行分类处理的大量文本， 而分类系统的输出是与文本关联的类别。 从数学角度来看，文本自动分类是一个映射的过程，它将未标明类别的文本 映射到分类体系下已有的类别中，该映射可以是一一映射，也可以是一对多的映 射，因为某些文本不但可以同一个类别相关联，也可以同多个类别相关联。该映 射用数学公式表示如下： f ：aj b 其中：a = ( d l ，d 2 ，或) b = ( c l ，c 2 c 。) ( 2 1 ) 即：a 为所有待分类的文本的集合，b 为给定分类体系下，所有类别的集合， a 可以为无限集合，而b 必须为有限集合。 文本自动分类的映射规则厂是文本自动分类系统的关键，它是系统根据已经 掌握的每类若干样本的数据信息，总结出分类的规律性而建立的判别公式和判别 规则。根据系统使用的学习方法的不同，这些判别公式和判别规则也有所不同。 在已经确定的映射规则的基础上，系统在遇到新文本时，通过计算和判断，最终 确定文本相关的类别。 2 2 文本的表示 大规模文本处理的对象是大量的真实文本，要使得计算机能够高效率、高性 能地处理自然文本，就必须找到一种理想的文本表示方法。文本表示最理想的境 8 网络文本信息的自动分类方i ：左研究文本自动分类的关键技术探讨 界就是模拟人所理解的语义，通过函数f ，使得： 人所理解的语义= f ( 文本) 一旦找到了合适的函数来表示人所理解的语义，那么整个问题就变得简单 了。对文本自动分类的过程就可以转化为一个搜索问题，即寻找和新文本函数值 差异最小的文本类。 目前大多数采用一种比较可行的方案是走统计学习的路线，研究从大规模语 料库中发现出来的统计规律，利用文本在字集合或词集合上的分布末近似表示语 义，并且做如下的假设： 两个分布完全一致的文本被认为是语义相同的。 两个分布相近的文本被认为是语义相近的。 当然，仅仅采用这种分布是不能精确反映人所理解的语义的，然而这种方案 却能够很方便地计算和操作，对于信息处理等应用领域，其表达效果还是可以接 受的。 根据以上思路，我们来考察文本，众所周知，文本是字词等代表特定含义的 符号按顺序连接的字符流。从这罩可以看出，文本有两个基本特征，一是组成文 本的所有字词符号，二是这些符号间的连接顺序，即一个中文文本可以由特征项 ( 字词符号) 的频率及其相互关系来完整表达。要表示文本中特征项的顺序信息， 就必然要用到有向的指针结构，这样，整个文本就变成了一个复杂的图，比如树 或网；与之相反的是表示文本中特征项的频率信息，仅仅使用一个向量就足够了。 信息检索和文本自动分类这些信息处理技术要求定义一种距离函数，以表示文本 之间的相似程度。如果使用复杂的图结构表示文本的话，则很难定义一种合理的 距离函数，因为存在这样的问题，怎样的两棵树才能说很相似? 又是什么样的两 个网爿能说距离比较小呢? 而使用向量束表示文本，则不会遇到这样的困难，数 学中有很多种定义距离的方式可供使用，例如欧式距离、相关系数等等。j 下因为 存在以上困难，所以我们不得不舍弃不好利用的顺序信息，只使用频率向量来表 示文本。 s a l t o n 等人于上世纪6 0 年代木提出了向量空间模型v s m ( v e c t o rs p a c e m o d e l ) 的概念，即使用向量表示文本，并成功应用于著名的s m a r t 系统中。 该模型及相关的技术在文本自动分类、自动索引、信息检索等领域得到了广泛的 应用，向量空间模型己逐渐成为最简便、最高效的文本表示模型之- - 2 5 。 下面先介绍有关向量空间模型的几个概念。 文档( d o c u m e n t ) 泛指一般的文本或者文本的片段( 段落、句群或句子) ， 一般指一篇文章。尽管文档可以是多媒体对象，但是在下面的讨论中我们只认为 是文本对象，并且对文本和文档不加以区别。 9 嘲络义本信息的自动分类方法研究文本自动分类的关键技术探讨 项( t e r m ) 文本的内容特征常常用它所含有的基本语占单位( 字、词、词 组或短语等) 来表示，这些基本的语言单位被统称为文本的项，即文本可以用项 集( t e r ml i s t ) 表示为d ( ，t 2 f ) ，其中，是项，1 f 。换句话说， 由这些项展开了一个向量空间，每个项表示一个维度。 项的权重( t e r mw e i g h t ) 对于含有n 个项的文本d ( t l ，r 2 f ，) ，项，常 常被赋予一定的权重w ，表示它们在文本d 中的重要程度，即d = d ( ，w 。；f 2 ， w 2 ；，w ) 简记为d - - d ( w i ，w 2 w ) 。 向量空间模型( v s m ) 给定的一文本d = d ( f 1 ，w 1 ；t 2 ，w 2 ；t 7 ，w _ ) ， 由于f ，在文本中既可以重复出现又会有先后次序的关系，分析起来仍有一定的难 度。为了简化分析，可以暂不考虑t ，在文档中的次序，并且要求，互异。这是可 以把f ，看成一个n 维坐标系，而w ，为相应的坐标值，因此d ( ，w 2 w ) 被看成是n 维空间的一个向量。 相似度( s i m il a r i t y ) 给定的两篇文本d 1 和d 2 ，它们的相关程度( d e g r e eo f r e l e v a n c e ) 常常用它们之间的相似度来度量。当用向量空间模型表示文本时， 它们的相似度由n 维空间中的相对位置决定，通常的办法是用两个向量间的夹角 来表示： s i m ( d l ，d 2 ) = c o s o = w l t 毒w 2 i k = i 、( 否w 叔否w ：t 2 ) tnn ( 2 2 ) 两者之问夹角越大，其余弦值越小，说明相似程度越低，两个文档分属不同 类的可能性增加。 那么选取什么作为特征项呢? 一般可以选择字、词或词组，甚至是句子或句 群等更高单位。项也可以是相应词语或者短语的语义概念类。因此，项的选择只 能由处理速度，精度，存储空间等方面的具体要求来决定。选出的项越具有代表 性，语言层次越高，所包含的信息就越丰富，但是分析的代价就越大，而且受分 析精度( 如句法分析的正确率) 的影响就越大。由于词汇是文本最基本的表示项， 在文本中的出现频率较高，呈现一定的统计规律，再考虑到处理大规模真实文本 所面临的困难，选择词或者短语作为特征项是比较合理的。这也是普遍认为选取 l o 嘲络义本信息的自动分类方法研究 文本自动分类的关键技术探讨 词作为特征项的原因。 在给特征项赋上权重时，应使文本越重要的项权重越大。第一种方法可以由 专家或者用户根据自己的经验与所掌握的领域知识人为地赋上权值。这种方法显 然随意性很大，而且效率也比较低，很难适用于大规模的文本处理。另一种方法 是运用统计的办法，也就是用文本的统计信息( 如词频等) 来计算项的权重。目 前被广泛采用的权重计算公式是t f i d f 公式。下面先介绍一下相关概念。 词频( t e r mf r e q u e n c y ) 是对词的一种最简单的测度，也是最常用的参数 之一。可以直接用它表示词在篇章或类别的权重，这种处理方法假定一个词的重 要程度与它出现的次数成比例。某个词在一篇文本中的权重被表达为：w ，= ，。 这里珥代表词t ，在文本中出现的次数。在信息检索领域的研究中，对于词频参 数的考虑能够提高查全率，但是不一定能够提高查准率。这一现象是可以解释的： 如果一个词在一篇文档中常常出现，那么说明这个词对文档具有代表性，例如“计 算机”这个词在计算机类的文档中出现的频率就要高一些，但是某些常用词或是 高频词不仅仅在一篇文档中出现，而且会大量地在各类文本中出现。因此，虽然 它们有很高的出现频率，但它们不具有重要性，它们对类别之间的区分能力不高， 甚至很低。例如“科学”在社会科学类和自然科学类的文本中都会出现，但是对 区别两类的文档帮助不大，所以要用到词篇分布的集中度，即通常常说的反篇章 频率( i n v e r s ed o c u m e n tf r e q u e n c y ) 。 词频反映了词在一篇文章中的出现次数，而词篇分布的集中度关注的则是词 在一篇文章中集中出现的情况。这种测度方法直观上的意义是，在一组文章中， 那些出现得较少的词含有更高的信息量。一个词的重要程度被认为与出现该词的 篇章数成反比。 基于以上基本因素的权重评价方法，综合词频和反篇章频率两个因素，并 且考虑到文本长度对权值的影响，进行归一化处理，将权值规范到 0 ，1 之间： w k , = 即嵫( ； + o o - ( 2 - 3 ) 瓯，表示项z 在文本d 。中出现的次数，n 表示全部训练集的文本数，n 。表 示训练文本中出现r 的文本数。 嘲络义本信息的自动分类方法研究文本白动分类的关键技术探讨 权重的计算至今没有普遍使用的“最优公式。t f i d f 公式是一种经验公式， 多年的实验表明，上述公式是文本处理中的一个有效工具。本文的研究也是基于 它作为文本表示模型而实现的。 2 3 文本的预处理 把英文的算法运用到中文分类中，关键问题就是中英文的单词在句子中的 出现方式不同，对待中文要增加切词的工作。中文自动分词是中文分类系统的预 处理，英文分类系统则不需要这一步骤。但是英文处理也有自身的特点，如动词 在语法上有时态的变化等。中文不像英文那样有空格将词与词区分开，中文文本 中词与词之间没有明确的分隔标记，而是连续的汉字串。汉语中存在大量的多义 词，语义模糊，歧义性大，识别词的边界比较困难。常用的中文分析算法有：基 于词表的分词，基于统计的分词，基于规则和基于统计相结合的分词。 从已有的分类方法中可以看到，英文文本自动分类系统的预处理一般有去 除原始h t m l 文件的一些t a g 标记、合并数字和人名等词汇、去除停用词( s t o p w o r dr e m o v i n g ) 和词形变化( s t e m m i n g ) 。同样的，中文文本自动分类在经过 分词后也需要首先去除停用词，比如某些助词，如“的”、“了”和某些语气词， 如“啊”、“吧等等。这些词中有些是高频词，即它们在各类文章中出现的几 率都很大，对类别之间的区分没有任何作用。另一些则是低频词，在文章中出现 的几率很小，或只是在某一篇文章中出现次数很多，但在其它同类型的文章中出 现几率很小，对基于类别的统计来说是没有意义的。 3 0 另外，很多词性，在文 本类别区分中明显作用不大，如数词、代词、量词等，它们有些显然是低频的， 也有些是高频但是区分度意义很小的，在预处理的过程中，可以考虑去掉这类词， 这样可以大大提高处理效率和分类的效果。 2 4 特征提取 构成文本的词汇数量是相当大的，所以，表示文本的向量空间的维数也相当 大，可以达到几万维，因此进行维数压缩的工作十分必要，这样做的目的主要有 两个：第一，为了提高程序的效率，提高运行速度，第二，所有几万个词汇对文 本自动分类的意义是不同的，一些通用的、各个类别都普遍存在的词汇对分类的 1 2 网络义本信息的自动分类方法研究文本自动分类的关键技术探讨 贡献小，在某特定类中出现比重大而在其它类中出现比重小的词汇对文本自动分 类的贡献大，为了提高分类精度，对于每一类，都应去除那些表现力不强的词汇， 筛选出针对该类的特征项集合。 国外的研究者在文本自动分类领域的特征抽取上进行了大量的研究。大多数 情况下，他们的分类系统中在文本预处理后进行特征抽取，即首先去除原始文本 中的停用词并对词形进行还原，然后在此基础上抽取特征。特征抽取的目的是剔 除文本中对于文本自动分类信息量小的词，减少计算复杂度。常用的特征抽取方 法有以下几种。 基于文档频数d f ( d o c u m e n tf r e q u e n c y ) 2 6 ，文档频数是最简单的评估 函数，其特征值为训练集合中该特征出现的文本数，词的d f 小于某个阈值去掉， 这是因为，如果特征出现频率太少，没有代表性；另一方面，如果d f 大于某个 阈值也应该去掉，因为特征出现的频率太高，也没有区分度。一般它不直接被用 于特征抽取。在实际运用中一般并不直接使用d f ，而是常把它作为评判其它评 估函数的基准 2 7 。我们用爿表示f 和e 同时出现的次数，b 为，出现而c ，没有出 现的次数，c 为c ，出现而，没有出现的次数，d 为，和c 都没有出现的次数，为 训练集中的文档总数。 信息增益i g ( i n f o r m a t i o ng a i n ) 的方法 2 8 ，它从信息论的角度出发，根 据各特征取值情况来划分样本空间时所获i g 的多少来选择相应的特征，其计算 公式为： i g ( ，) 叫，) 军p ( 帅) l o g 锗州f ) 军比l - ) l o g 帮( 2 - 4 ) 其中，p ( f ) = ( a + b ) n 、p ( q ) = ( a + c ) n 分别为单词，和类别q 在整个训练 集中出现的概率，p ( c fi f ) = a ( a + b ) 为单词，出现的文档属于类别c ，的文本中出 现的概率，p ( c ，i f ) = c ( 口屺) 为单词，不存在的文档属于类别c ，的文本中出现的 概率。需要指出的是，在i o g ( p ( c , i ，) p ( c ，) ) 中，如果，的出现倾向于表示文本属于 类别q ，则l o g 值为正；如果，的出现倾向于表示文本不属于类别c ，则l o g 值为 负；如果t 的出现与类别c ，是否出现无关，则l o g 值为0 。但是如果对l o g 值简单 求和，就会出现这样的问题：单词f ，与各类无关，其i g 接近于0 ；另一个单词f ， 的出现倾向于类别c ，出现、c ，不出现，这个单词本来非常重要，但是对各l o g 值 求和后正负l o g 值相抵消，其i g 也接近于0 。这样就无法将其与f ，区分开了。解 决这一问题有两种方法，一是对各l o g 值取绝对值后再相加，二是不考虑负相关， 略去l o g 值小于o 的情况。由于在实验中，第二种方法的效果要好于第一种，所 以计算i g 时，就不再考虑负相关了【2 9 】。 z 2 统计量统计方法( c h i ) ，c h i 定义单词，与类别c ，之问相关性的计算公式 如下： 网络文本信息的自动分类方法研究文本自动分类的关键技术探讨 z 2 ( ，q ) = 百琵两n 两x ( a 面d 瓦- 瓦cx 而b ) 2 而( 2 - 5 )z 【，q