（计算机软件与理论专业论文）基于svm的网络文本分类问题研究与应用.pdf

摘要 摘要 随着i n t e m e t 的迅速发展，尤其是w 硎dw i d ew e b 的全球普及，w 曲上信 息资源已涵盖了社会生活的各个方面，网络信息过载( i n f o r m a t i o n o v e r l o a d ) 问题 日益突出，这促使w 曲挖掘技术和w e b 信息检索技术迅速发展。处理这些海量 数据的一个重要方法就是将它们分类。通过自动分类不仅仅可以将网络文本按 照类别信息分别建立相应的数据库，提高中文搜索引擎的查全率和查准率；而 且可以建立自动的分类信息资源，为用户提供分类信息目录。 本文对文本分类的基本概念和相关算法以及s v m 算法的国内外研究现状进 行介绍和讨论。针对不同的基于s v m 多类别分类方法分别进行了研究，在此基 础上，做了以下工作： 首先，本文研究分析文本分类的总体过程，包括：信息预处理、特征表示、 特征提取。重点研究分析了特征表示与特征提取技术，文本的分类算法，并根 据实际情况提出了一种综合特征提取方法。 其次，认真研究了统计学习理论的主要内容和s v m 算法的基本原理，并且 就s v m 的多种多类别分类算法分别加以讨论。针对传统的支持向量机大类别分 类算法存在的不足，结合支持向量机快速准确的分类性能和纠错输出编码误差 修正的特点，提出一种多类分类s v m 网络分类方法。 最后在完成基于s v m 多类别分类的理论研究的基础上，将其理论应用于实 践，构建了一个了基于s v m 的网络文本分类模型。在该模型的基础上，以 l i b s v m 为工具软件，结合实验语料集分别验证了基于s v m 的多类分类方法， 得以证明多类分类s v m 网络分类方法有较好的实用性。 关键词：文本分类；s v m ；网络文本；多类分类； a b s t r a c t a b s t r a c t t h ei n f o r m a t i o nr e s o u r c eo nt h ew e bh a sc o v e r e dv a r i o u sf i e l d sw i t ht h er a p i d d e v e l o p m e n to fi n t e r a c t , e s p e c i a l l yt h ep r e v a l e n c eo fw o r l dw i d ew e b t os o l v et h e p r o b l e mo fi n f o r m a t i o no v e r l o a d ，t h et e c h n i q u e so fw e bm i i l i n ga n dw e bi n f o r m a t i o n r e t r i e v a lh a v e b e e ng r e a t l yd e v e l o p e d a ni m p o r t a n tm e t h o dt od e a lw i t hl a r g e s c a l e d a t ai st oc l a s s i f yt h e m i tn o to n l yc a r ls e tu pc o r r e s p o n d i n gw e bt e x td a t a b a s e s e p a r a t e l ya c c o r d i n gt oc l a s s i f i c a t i o ni n f o r m a t i o n ，b u ta l s oc a ni m p r o v er e c a l la n d p r e c i s i o no ft h es e a r c he n g i n e i ta l s oc a r ls e tu pa u t o m a t i cc a t e g o r i z e di n f o r m a t i o n r e s o r r c ea n do f f e rt h ec l a s s i f i e di n f o r m a t i o nc a t a l o g u et ou s e r s i nt h i st h e s i s ，as u r v e yo nt h er e l a t e dr e s e a r c ha n dr e c e n td e v e l o p m e n to ft e x t c a t e g o r i z a t i o na n dr e l a t e da l g o r i t h m sw a sg i v e nf i r s t b a s e do nt h er e s e a r c h i n go f d i f f e r e n ts v m a l g o r i t h m sf o rm u l t i c l a s s ，t h em a i nw o r ko f t h et h e s i si sa sb e l o w ： f i r s t l y , t h et e x ta n a l y z e st h et o t a lp r o c e d u r eo ft e x tc a t e g o r i z a t i o n , i n c l u d i n gt h e i n f o r m a t i o np r e p r o c e s s i n g ，f e a t u r er e p r e s e n t a t i o na n df e a t u r ec a t c h i n g t h ea u t h o r a n a l y z e st e c h n o l o g i e so ff e a t u r er e p r e s e n t a t i o na n dc a t c h i n ga n dt e x tc a t e g o r i z a t i o n a l g o r i t h me s p e c i a l l y , a n db r i n gf o r w a r da l li n t e g r a t i v ef e a t u r ec a t c h i n gf u n c t i o n s e c o n d l y , t h et e x ts t u d i e st h es t a t i s t i c a ll e a r n i n gt h c o r y ( s t l ) a n ds u p p o r t v e c t o r m a c h i n e ( s v m ) t h e o r ys e r i o u s l y , d i s c u s s e sm u l t i c a t e g o r y c l a s s i f i c a t i o n a l g o r i t h m so fs v m i no r d e rt o m a k eu pf o rt h ed e f i c i e n c yo ft h et r a d i t i o n a l m u l t i - c l a s sc l a s s i f i c a t i o no fs v m ，am u d t i - c l a s sc l a s s i f i c a t i o nm e t h o do fs v m n e t w o r ki sp u tf o r w a r db yc o m b i n i n gt h eh i g h p o w e r e dc l a s s i f i c a t i o na n de r r o r c o r r e c t i n gc a p a c i t yo f e r r o rc o r r e c t i n go u t p u tc o d e s ( e c o c ) o fs v m f i n a l l y , b a s e do nb a s i cr e s e a r c ho f m u l t i - c l a s sc a t e g o r i z a t i o no fs v m ，t h et e x t a p p l i e st h et h e o r yt op r a c t i c ea n da n a l y z e sa w e bt e x tc a t e g o r i z a t i o nm o d e lb a s e do n s v mn e t w o r k b a s e do nt h em o d e l ，u s i n gt h el i b s v ma sat o o l ，t h ea u t h o rc o n f i r m s t h e s em u l t i - c a t e g o r yc l a s s i f i c a t i o n so fs v mb yt h ee x p e r i m e n t sa n dp r o v et h e m u l t i - c l a s sc l a s s i f i c a t i o nm e t h o do fs v mn e t w o r kh a sb c t t e ru s a b i l i t y k e yw o r d s ：t e x tc a t e g o r i z a t i o n ；s v m ；w e bt e x t ；m u l t i - c l a s sc l a s s i f i c a t i o n 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得直昌太堂或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名( 手写) ：刊清签字日期：跏7 年，j 月矽日 学位论文版权使用授权书 本学位论文作者完全了解直昌太堂有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权直昌盔堂可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编本学位论文。同时授权中国科学技术信息研究 所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作 签字日期： 圩日 第1 章绪论 第1 章绪论 1 1 课题的来源、目的及研究意义 本课题来源于江西省教育厅科技计划( 赣教技字 2 0 0 5 4 4 号) ，旨在研究网 络信息数据挖掘。 随着i n t e r n e t 的飞速发展，w w w ( w o r l dw i d ew e b ) 已经成为一个遍及全球 的广泛使用信息中心，拥有丰富的超级链接信息以及网页浏览信息，使得人类 全部的信息资源以前所未有的方式和程度在全球内互相联通，w e b 上的信息量 也随之呈几何指数增长。 同时，企业数据化程度的提高，文本信息的快速积累使企业、政府、科研 机构等面临前所未有的挑战。一方面，互联网和企业信息系统每天都不断产生 大量文本信息，这些文本资源中蕴含着许多有用信息；而另一方面由于技术手 段的落后，用户从w e b 上海量、动态、异构的丰富信息资源中快速、有效地查 找自己感兴趣的信息从而获取潜在的有价值的知识十分困难，即人们面临着“信 息爆炸”而“知识贫乏”。 因此，人们迫切需要研究出有效的方法和技术从大规模文本信息资源中提 取符合需要的简洁、精炼、可理解的知识。网络数据挖掘就是为解决这类问题 而产生的研究方向。 目前，i n t e r n e t 上大多信息的表现形式为文本，如何在浩瀚的文本信息中挖 掘到潜在的知识是一个急待解决的问题。文本挖掘( t e x t m i n i n g ) 是指从非结构化 的文本中发现潜在的知识，其目的是从不同格式的文本中发现有用的知识，这 是一个分析文本并从中抽取特定信息的过程。与数据库中的数据相比，文本数 据结构隐含、松散，相对比较难以处理。文本挖掘可以从来自异构数据源的大 规模的文本资源中提取符合需要的简洁、精炼、可理解的知识。由于分类可以 在较大程度上解决目前网络信息杂乱的现象，方便用户准确地定位所需的信息 和分流信息。因此，文本分类是文本挖掘中的一项具有较大实用价值的关键技 术，是组织和管理网络信息的有效手段“1 。在文本自动分类中，分类模型( 分类 器) 是决定分类效果好坏的一个关键部分，现有的文本分类模型主要有决策树 第l 章绪论 ( d e c i s i o nt r e e ，简称d t ) 、支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 、 贝叶斯网络、k 一最邻近法( k n n ) 等。 统计学习理论是一种专门研究有限样本条件下机器学习规律的理论。该理 论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规 则不仅考虑了渐近性能的要求，而且追求在现有有限信息的条件下得到最优结 果。统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学 习问题提供了一个统一的框架。在这一理论基础上发展了一种新的通用学习方 法一s v m ，该方法已初步表现出很多优于已有方法的性能。s v m 方法是建立在 统计学习理论的v c 维理论和结构风险最小化原理基础上的，根据有限的样本信 息在模型的复杂性( h p 对特定训练样本的学习精度，a c c u r a c ：y ) 和学习能力( 即无错 误地识别任意样本的能力) 之间寻求最佳折衷，以期获得最好的推广能力 ( g e n e r a l i z a t i o n a b i l i y t ) 。目前，s v m 算法在模式识别、回归估计、概率密度函数 估计等方面都有应用。例如，在模式识别方面，对于手写数字识别、语音识别、 人脸图像识别、文章分类等问题，s v m 算法在精度上已经超过传统的学习算法 或与之不相上下o 。3 ，。 本文正是根据s v m 的特点和已有的研究经验及成果，实现了一个基于s v m 的网络文本分类器，对s v m 在网络文本自动分类中的应用效果、优缺点及其应 用潜力进行了初步的研究。 1 2 文本分类概述 文本自动分类是利用对文本集( 或其他实体对象) 按照一定的分类体系或 标准进行自动分类标记，属于同一类别的文本被标上相同的类别标记，为文本 信息的处理提供系统化的解决方案“1 。文本分类的一个关键问题是特征词的选择 及其权重分配，为此需要在已有数据的基础上构造出一个分类模型，即分类器。 分类器一般分为训练和分类两个阶段。 文本分类是按照预先定义的主题类别，在分析文本内容的基础上为文本集 合中的每个文本确定一个类别。这样，用户不仅能方便地浏览文本，而且可以 通过限制搜索范围来使文本的查找更为容易。利用文本分类技术可以对大量文 本进行快速、有效地自动分类。 一般来讲，文本分类主要有以下五个问题需要解决【”： 2 第1 章绪论 ( 1 ) 获取训练文本集合。训练文本集合选择是否合适，对文本分类器的性能 有较大影响。训练文本集合应该能够广泛地代表分类系统所要处理的、实际存 在的各个文本类别中的文本。一般地，训练文本集合应该是公认的、经人工分 类的语料库。 ( 2 ) 建立文本表示模型。建立文本表示模型是一个重要的技术问题，它将决 定选用什么样的文本特征( 或属性) 来表征文本。目前的文本分类系统，绝大 多数都是以词语来表征文本的，至于具体形式，则可能是关键词或短语、主题 词、概念等。当然，不同语言的文本，在获取文本的词语属性时，需要采取不 同技术，例如抽词或切分词。鉴于中文文本信息的特殊性，有些中文文本分类 系统采用了基于统计的n g r a m 属性，以避开词语切分的困扰。 ( 3 ) 文本特征抽取。对于使用自然语言表达的文本集合来说，文本特征是开 放的、无限制的。一个分类系统对于所获取的特征必须进行筛选和优化，从特 征的全集中抽取一个最优的特征子集。惟有如此，才能保证分类算法的效率呦 ( 4 ) 选择或设计分类模型。选取分类模型实际上就是要使用某种方法，建立 从文本特征( 或属性) 到文本类别的映射关系，是文本分类的核心问题。现有的分 类方法主要来自两个方面：统计和机器学习，比较著名的文本分类方法有k - n n n a i v eb a y e s 、s v m 等。 ( 5 ) 性能评测模型。文本分类系统的建立，需要对系统使用的分类方法或分 类器进行性能评价分析，性能评测是分类处理流程中的重要一环。同时，寻找 能够真正反映文本分类内在特征的性能评估模型，对改进和完善分类系统也具 有指导意义。 1 3 国内外的现状与发展 1 3 1 网络文本分类的现状与发展 目前，文本的自动分类最初是应信息检索( i n f o r m a t i o n r e t r i e v a l ) 系统的要求 出现的，它是由计算机自动完成对文本的分类。文本自动分类及其相关技术的 研究正日益成为一项技术热点。在国外，文本自动分类的研究起步较早，2 0 世 纪5 0 年代末，h p l u n h n ”1 就在这一领域进行了开创性研究，提出了将词频统 计思想用于文本自动分类。到目前为止，国外的自动文本分类研究已在邮件分 3 第1 章绪论 类、电子会议、信息过滤等方面取得了较为广泛的应用，其中有麻省理工学院 为白宫开发的邮件分类系统、卡内基集团为路透社开发的c o n s t r u e 系统等“。 国外当前流行的文本分类方法有r o c c h i o 法及其变异方法、k 近邻法( k n n ) 、 决策树、朴素贝叶斯、s v m ( s v m ) 等方法。这些方法在英文以及欧洲语种文本 自动分类上有广泛的研究，而且很多研究表明k n n 和s v m 是英文文本分类的最 好方法。国外很多研究人员对英文文本分类领域的各个问题都有相当深入的研 究，对几种流行的方法进行了大量的对比研究。s u s a no u m a i s 等学者对这5 种方 法进行了专门的比较研究n ”。 在国内，对于这项技术的研究主要是从1 9 8 1 年开始，候汉清教授对计算机 在文本分类工作中的应用做了探讨，以后我国陆续研制出批计算机辅助分类 系统，如广东省中山图书馆的莫少强开发的计算机辅助图书分类系统等。相比 于英文文本分类，中文文本分类的一个重要的差别在于预处理阶段：中文文本 的读取需要分词，不像英文文本的单词那样有空格来区分。从简单的查词典的 方法，到后来的基于统计语占模型的分词方法，中文分词的技术已趋于成熟。 比较有影响力的当属中国科学院计算所开发的汉语词法分析系统i c t c l a s ，现 已公开发布供中文文本分类的研究使用。 1 3 2s v m 算法研究的现状与发展 在传统学习理论基础上发展起来的s v m ( s v m ) 算法，是一种专门研究有限 样本预测的学习方法。与传统统计学相比，s v m 算法没有以传统的经验风险最 小化原则作为基础，而是建立在结构最小化原理基础之上，发展成为一种新型 的结构化学习方法。它能很好地解决有限数量样本的高维模型构造问题，而且 所构造的模型具有很好的预测性能。 s v m 是v a p “i k 等人于2 0 世纪9 0 年代根据统计学习理论提出的一种新的机器 学习方法，它以结构风险最小化原则为理论基础，通过适当选择函数子集及该 子集中的判别函数使学习机的实际风险达到最小，保证了通过有限训练样本得 到的小误差分类器对独立测试集的测试误差仍然小，得到一个具有最优分类能 力和推广泛化能力的学习机“。 作为统计学习理论中最年轻的分支，s v m 的理论已经取得重大进展，其算 法实现策略以及实际应用也在发展迅速。可以确信，该技术的研究已发展成为 4 第1 章绪论 机器学习中的一个独立的子领域，在理论和实践两方面都有着光明的前景。 目前，s v m 己被越来越多地应用到模式识别领域，如手写体文字识别、人 脸识别等“”1 。在图像压缩和数据分类的应用中，s v m 也显示出了较好的性能。 作为一种分类精度较高的技术，如今s v m 算法已经广泛应用于生物、工程技术、 运筹学、计算机技术、图像处理、模式识别、社会科学等领域解决组合优化、 机器学习、自适应控制等问题。尤其适用于处理传统分类方法难于解决的、复 杂非线性问题。 1 4 本文的组织结构 本文主要研究基于s v m 的网络文本分类方法。利用解决文本自动分类问题 的网络文本预处理方法，在此基础上以v s m 形式表示训练实例集来更加有效地 找出测试集实例的归属类别；同时利用s v m 算法良好的分类精度等优点，解决 网络文本分类问题。但为避免单纯采用该算法所具有的局限性与缺陷，借助纠 错输出编码方法对标准s v m 算法加以改进优化，结合l i b s v m 工具软件来解决 网络文本分类问题。本文的整体结构如下： 首先是绪论，介绍了本文的选题的研究背景，概括性地分析了文本分类的 研究现状、s v m 的研究状况和内容。 接着分析了文本分类的基本概念和方法；然后主要分析了文本分类的过程、 文本的表示及特征项的提取；重点分析研究了文本的特征表示与特征提取技术 和文本的分类算法。根据实际情况，提出了一种综合特征提取方法。 其次是统计学习理论概述，主要分析研究统计学习理论研究内容：经验风 险最小化，v c 维，结构风险最小化。 然后是s v m 的主要研究内容：s v m 的主要理论基础，s v m 的多类分类问 题及相关算法的分析，提出了一种多类分类的s v m 网络结构。 然后研究了一个基于s v m 的网络文本分类模型。分析了网络文本的预处理、 采用s v m 网络结构的算法的设计思想及实现，并结合实验加以验证。 最后对全文作出总结和展望。 5 第2 章文本分类技术 第2 章文本分类技术 w e b 文本挖掘的数据对象既可以是结构化的，也可以是非结构化的、半结 构化的。w e b 文本挖掘的结果既可以是对某个文本内容的概括，也可以是对整 个文本集合的分类结果或聚类结果。目前w e b 文本挖掘的主要研究内容是对w e b 上大量文本集合的内容进行总结、分类、聚类、关联分析、科学文献资料浏览 导航，以及利用w e b 文本进行趋势预测等。其一般处理过程如图2 1 所示： 2 1 文本分类模型 2 1 1 问题描述 图2 1w e b 文本数据挖掘的一般处理过程 简单地说，文本分类系统的任务是：在给定的分类体系下，根据已经掌握 的每类若干样本的数据信息，总结出分类规律性，建立判别公式和判别规则， 然后，当遇到新样本点时，只需根据总结出的判别公式和判别规则，就能判别 该样本点的所属类别。 从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映 射到分类体系下已有的类别中。该映射可以是一一映射，也可以是一对多的映 射，因为通常某些文本不但可以同一个类别相关联，也可以同多个类别相关联， 该映射用用数学公式表示如下： ，：a b 其中：a = ( d m ，d 2 ，见) ，b = ( c 1 ，c 2 ，q ) ( 2 1 1 ) 即：a 为所有待分类的文本集合，b 为给定分类体系下所有类别集合，可以 6 第2 章文本分类技术 为无限集合，而b 必须为有限集合。 文本分类的映射规则厂是文本分类系统的关键，学习方法不同，厂也有所 不同。在已经确定的映射规则基础上，系统在遇到新文本时，通过计算和判断， 最终确定文本的相关类别。 2 1 2 文本分类的阶段流程 文本分类是一种典型的有教师的机器学习问题，一般分为训练和分类两个 阶段，如图2 2 所示，具体过程如下。 图2 2 文本分类框架 类过程 训练阶段： ( 1 ) 定义类别集合c = b ，c ，。，) ，这些类别可以是层次式的，也可以是并 列式的； ( 2 ) 给出训练文本集合s = “，j s 。) ，每个训练文本j ，被标上所属的类 别标识c ； ( 3 ) 统计s 中所有文本的特征矢量v ( s ，) ； ( 4 ) 进行特征选择，确定代表c 中每个类别的特征矢量v ( c ，) ； 分类阶段： ( 1 ) 对于测试文本集合t = 矾，以，d ，) 中的每个待分类文本血，计算其特 征矢v ( d 。) 与每个v ( c 。) 之日j 的相似度s i r e ( 巩，c ) ； ( 2 ) 选取相似度最大的一个类别a r g m a x ，s i m ( d 女，c ，) 作为巩的类别。 有时也可以为以指定多个类别，只要d k 与这些类别之间的相似度超过某个 7 第2 章文本分类技术 预定的阅值。如果4 与所有类别的相似度均低于阈值，那么通常将该文本放在 一边，由用户来做最终决定。对于类别与预定义类别不匹配的文本而言，这是 合理的，也是必须的。如果这种情况经常发生，则说明需要修改预定义类别。 然后重新进行上述训练与分类过程。 在计算s i m ( 以，c ) 时，有多种方法可供选择。最简单的方法是仅考虑两个特 l j 一i 征矢量中所包含的词条的重叠程度，即s i m ( d k ，q ) = 躺，其中，k n q i 是 p t u c t l y ( 巩) 和v ( c ，) 具有的相同词条数目，k u c ，i 是矿( 巩) 和v ( c ) 具有的所有词条 数目；最常用的方法是考虑两个特征矢量之间的夹角余弦，即 s i r e ( d k ，c i ) = 2 2 自动分词 v ( a i ) v ( c ，) 而骊砸砑。 ( 2 1 2 ) 由于计算机无法直接对文本进行分类，利用计算机进行文本分类前，必须 将文本表示成计算机能处理的数据形式。在文本分类中较普遍应用的是对文本 进行分词，这样计算机所面临的不再是无法理解的文本。 中文分词是中文文本信息处理的基础，为了能够进行文本分类，首先要对 文本的内容进行分词，已有的分词技术有很多，有按照语义进行分法等，这类 分词技术，更多地关注对自然语言自身的语言信息的处理；也有机械式分词法 如基于词频统计法等，基于词频统计主要是统计文本中重复出现的字，计算它 们的频度，超出预先给定的闭值，即为词。 在中文文本中，对文本进行分词后，词集中有很多虚词在文章中仅起到连 接作用，没有多少实际意义，一些词尽管在文中多次出现，但是对于文本的分 类没有任何作用，比如“的”。在”“虽然”“可是”等等这些在文本中大量出现 的词；还有一些词在整个语料中出现频率高但在每篇文档中出现概率大致相等， 对分类来说作用不大，这些词称为停用词。为了降低这些词给分类的精度造成 的影响，在特征集中将其去掉，即去除“停用词”。 常用的分词算法有机械分词、基于理解的分词和基于统计的分词等。 8 第2 章文本分类技术 2 3 文本表示模型 2 3 1 文本表示方法 中文具有多种表达方式和复杂的语法，若不对文本表达进行转换，机械的 计算机是很难对其理解和处理的。文本表示是为了自动抽取出能够表达文本内 容的词汇，常用的文本表示方法有三种： ( 1 ) 句法分析法。句法分析法是通过应用句法分析程序，筛选出合乎一定过 滤规则的词条。句法分析法的标引结果大多数为有意义的名词短语。为了保证 词条语义的完整性，通常需要借助词典和语料库，否则程序的分析结果往往是 合乎句法的句子而不是词。句法分析法比较复杂，应用实例较为少见。 ( 2 ) 词库匹配法。词库匹配法是将输入文本与词库中的词汇进行匹配，以便 将文本中被词库收录的词条按照分词匹配方法被抽取出来，抽取出来的词条就 是文本的关键词。词库匹配法虽然能够保证每个关键词在语义上都是完整的， 但是并不能保证文献中所有的关键词都能被抽取出来，也不能保证抽取出来的 关键词就是文献真正的关键词。 。 ( 3 ) 词频统计法。词频统计法是中文文本分类中最常用的文本表示方法，具 体实现包括两个步骤，一是进行分词，将文本转化为只包含能够表达文本内容 的词汇；二是词汇权重计算，以此反映词汇对表达文本内容所起的作用。本文 所研究的网络文本分类的网络文本表示采用的是词频统计法。 大多数基于词频统计的文本表达方法都基于两点经验性的共识：词汇在某 一特定文本类别中的出现频率越高，与该文本的类别就越相关；而词汇在所有 文本集中的出现频率越高，与该文本的类别就越不相关。 2 3 2 向量空间模型 要正确地执行文本分类的任务，首先要将文本的有用信息输入计算机中， 为此应对文本进行科学的抽象，建立它的数学模型，用以描述和代替文本。用 简单而准确饷方法将文档表示成计算机能够处理的形式是进行文本分类的基 础。目前，在信息处理方向上，文本的表示主要采用向量空间模型( v e c t o r s p a c e m o d e ) 。在这种模型中，每一对象模型化为空间中的点，两对象间的差异由多维 9 第2 章文本分类技术 空间中两点间的距离表示。向量空间模型的基本思想是以向量来表示文本： ( 昕，o ) 其中，为第，个特征项的权重，一般选择字、词或词组作为特征 项。根据实验结果，普遍认为选取词作为特征项要优于字和词组，因此，要将 文本表示为向量空间中的一个向量，就首先要将文本分词，由这些词作为向量 的维数来表示文本，最初的向量表示完全是o 、1 形式，即：如果文本中出现了 该词，那么文本向量的该维为l ，否则为0 。这种方法无法体现这个词在文本中 的作用程度，所以逐渐o 、1 被更精确的词频代替。词频有绝对词频和相对词频 之分。绝对词频是指词在文本中出现的频率；相对词频是规范化的词频，即要 求所有向量分量的平方和为1 ，其计算方法主要运用t f i d f 公式m 1 。目前存在 多种t f i d f 公式，比较普遍的t f i d f 公式如下所示： 咿r f ，d ) = 矿( f ，孑) l o g ( n n , + o 0 1 ) j 喜 _ ) l o g ( 叭+ o 0 1 ) 】2 ( 2 3 1 ) 其中，亿j ) 为词薤文本d 中的权重，而矿o ，d ) 为词在文本d 中的词频， 肋训练文本的总数，硇向量的维数，为向量第价分量对应的特征项，为 训练文本集中出现六的文本数，仃。为训练文本集中出现f 的文本数，分母为规范 化因子。文本经过分词程序分词后，首先去除停用词，合并数字和人名等词汇， 然后统计词频，最终表示为上面描述的文本向量。 ， ，- 。) w ，w 2 ) t 3 图2 3 文本的向量空间模型 向量空间模型有效地解决了非结构化文本数据的处理问题，提高了文本处 理的速度和效率，把对文本的操作转变为对特征向量的操作。 1 0 第2 章文本分类技术 2 4 文本特征选择 经过对中文文本自动分词之后，文本就可以表示成向量空间模型中的文本 特征向量，这为计算机对文本分类提供了可行的解决方法。运用机器学习和统 计学习方法进行中文文本分类问题的研究，首先需要将文本表示成特征向量。 中文文本分类问题的最大特点和困难之一是特征空间的高维性和文档表示向量 的稀疏性。对于一般规模的文本分类问题，其所对应的文本特征空间都具有多 达数万甚至更多的维数，直接在这样的一个高维空间上进行文本分类，就会面 临两方面的问题：一方面使得一些在低维空间具有良好性能的统计分类方法的 计算效率降低，难以取得理想的分类效果；另一方面，不是所有的特征信息都 对分类有帮助，过多的特征使得分类算法难以对类别进行判断，降低了分类器 的推广能力，出现所谓“维数灾难”和“过学习”现象。 2 4 1 文本特征项 特征项的选择对向量空间模型的表达效果有着很重要的意义一1 。字、词、 短语或者更高层次的语占单位都可作为特征项。特征项也可以是相应词语或者 短语的语义概念类。特征项选择一般遵循以下原则：一是尽量选择包含语义信 息较多，对文本的表示能力较强的语言单位：二是特征项的分布应当有比较明 显的统计规律性；三是实现的时问和空问开销不能太复杂。通常可以选择以下 特征项： ( 1 ) 字作为特征项。对于中文来讲，分词过程本身就是难点，并且在汉语中， 汉字的数量大大少于词的数量，所以，选择字作为特征项，特征选择的难度会 降低。但是字是汉语中最基本的语言单位，以它作为特征项对文本语义的表述 能力相对较差。 ( 2 ) 词作为特征项。从语言学上来讲，词是构成中文文本的主体，是最能够 反映文本语义的基本单位，选择词作为特征项能够充分表示汉语的语义，分类 系统的性能明显优于选择字作为特征项的系统。但是直接选用文本中的词作为 文本特征项也会存在数量巨大和无实意用词过多的问题。通过词切分得到特征 项之后，还需要进行特征选择和降维处理。 ( 3 ) 概念作为特征项。由于汉语中存在大量的同义词和近义词，可以考虑将 其语义集中，使用概念作为特征项。在文本分类中概念是指代表一类同义词或 1 l 第2 章文本分类技术 近义词的条目，使用概念作为特征项可以使特征项的选择较为集中并且贴近语 义。概念本身的判断和处理相对复杂，存在同义关系( 如诞辰和生日) ，近义关 系( 如欢乐和喜悦) ，从属关系( 主机和主板) ，关联关系( 老师和学生) 等关系， 如何很好地划分概念特征项，确定概念类都是关键性问题。因此概念作为特征 项的文本分类在实现上比较复杂。 ( 4 ) n 元模型作为特征项。以字作为特征项，粒度太大，所包含的语义信息 较少；以词作为特征项，需要基于词典进行分词；以概念作为特征项，受到对 中文自然语言理解水平的限制。而n 元( n g a r m ) 模型，使文本自动分类系统摆脱 了对复杂分词处理程序和庞大词库的依赖。n 元模型是一种概率模型，其中规定 当前元素( 如：词，词性等) 出现的概率只同它前面出现的n - 1 个元素有关。n = i 时就是一元模型( u n i g a r m ) ，n = 2 时就是二元模型( b i g r a m ) ，n = 3 时就是三元模型 ( 岍g r a m ) 。数学模型如下： e ( w ) = p ( w i ) p ( w 2 ) p ( w 3 1 w l w 2 ) p ( w 1 1 w 一+ l 叱一i ) ，、 2 ii “e ( w , 1 w , 一+ l h - l 实际使用中n 通常取值2 或3 。采用n g a r m 作为中文文本特征项更关注词语的 上下文信息。n g a r m 获取技术中的领域无关性和时间无关性的实现是有代价的， n g a r m 的提取对系统资源的要求较高。 2 4 2 特征降维方法 不同的特征项对于文档的重要性和区分度是不同的，通常高频特征项在多 个类中出现，并且分布较为均匀，因此区分度较小；而低频特征项由于对文档 向量的贡献较小，因此重要性也较低。1 。去除区分度较小的噪音特征项可以提 高分类正确率，去除重要性较低的低频特征项可以加快运行速度。因此需要建 立合适的特征评价函数，对特征项进行选择。特征降维方法普遍通过对特征项 所包含的嫡值进行估算，得出能够反映特征项信息含量的数值，或者是特征项 区分文档的能力值。常用的方法有文档频次( d f ：d o c u m e n tf r e q u e n e y ) 、互信息 ( m i ：m u t u a l i n f o r m a t i o n ) 、信息嫡( i g ：i n f o r m a t i o n c a i n ) 、x 2 ( 希腊语字母表第 2 2 字母) 统计量等方法”到，下面将对其进行简要介绍。 ( 1 ) 文档频次方法( d f ) 。文档频次就是文档集合中出现某个特征项的文档数 目。在特征项选择中，计算每个特征项在训练集合中出现的频次，根据预先设 1 2 第2 章文本分类技术 定的阈值去除那些文档频次特别低和特别高的特征项。文档频次的计算复杂度 较低，随训练集的增加而线性增加，能够适用于大规模语料，因此是特征降维 的常用方法。其基本原则是：很少出现的特征对分类价值极小，对整个分类系 统的效果影响也很小，因此，将这些特征去掉有助于降低特征空间维数，并且 当这些不常出现的特征为噪音时，还会有助于提高分类正确率。“。 d f 的优点是在计算量上比其它评估函数小得多，但在实际运用中它的效果 却很好；缺点是稀有单词可能在某一类文本中并不稀有，也可能包含着重要的 判断信息，简单地舍弃，可能影响分类器的精度。因此，在实际运用中一般并 不直接使用d f 。 ( 2 ) 互信息方法( m i ) ”。互信息可以度量特征项和类别的共现关系，特征项 对于类别的互信息越大，它们之间的共现概率也越大。假设文档集合c 分为k 类，记为c l ，c 2 ，c t ，特征项w 对于文档类别c ，的互信息m i ( w , c j ) 的计算公 式如下： 。 加( 蚓= l o g 船 ( 2 4 2 ) 其中p ( w ，c j ) 为特征项w 出现在类e 中的概率，p ( w ，c ) 为特征项w 在所有 文档中的出现概率。 下面给出基于互信息的特征降维算法步骤： 1 ) 如果特征项w 不是停用词，对于每一个文档类c j ，1 f k ，计算w 对 于c f 的互信息m l ( w , e ) m ( 蚓= l o g 篙岩 ( 2 4 3 ) 其中f r e q ( w ，e ) 是w 在文档类别c i 中出现的次数，f r e q ( w , c ) 是w 在整个文 档集c 中出现的次数。 2 ) 特征项w 对于文档集合c 的互信息m l ( w ，c ) = m l ( w , q ) ，其中q 是特征 项w 的互信息最大类别 七= 心( 篙嚣 眨a t ， 3 ) 给定闽值口，选择m i ( w , c ) t t f 的特征项组成特征空间。 互信息有一个很大的缺点就是容易受到一个词语边缘概率的影响。例如， 如果两个词语具有相同的条件概率p ( w ，e ) ，那么出现次数少的词语会比出现次 1 3 第2 章文本分类技术 数多的词语得到更大的m 1 值。 互信息的优点是：对于低频词，其互信息比常用词互信息要高；缺点是： 过于倾向低频词，在低频词过多的情况下，将影响分类效果。 ( 3 ) 信息嫡方法( i g ) 。信息嫡可以度量特征项在某种分类下表示信息量的 多少，以正反两类( 用h o t ，c o l d 来代表) 的情况为例，通过计算信息嫡得到那些 在正例样本中出现频率高而在反例样本中出现频率低的特征项，以及那些在反 例样本中出现频率高而在正例样本中出现频率低的特征项。信息嫡e ( w ，s ) 的计 算过程如下： e ( w ，s ) = ，( s ) 一【p ( 矿= p r e s e n t ) l ( s 。，。w ) + ，( 阡7 = 6 j e 以f ) j ( s 。h 。“) 】( 2 4 5 ) 其中，( s ) = - p ( s 。) l 0 9 2 ( p ( 足) ) ( 2 4 6 ) c e ( h o t c o d ) p ( = p r e s e n t ) 是特征项在文档集合中的出现概率，即出现了特征项矿 的文档总数除以总文档个数，s 。指包含w 的文档集合，p ( w = a b s e n t ) 是 特征项在文档集合中不出现的概率，即没有出现特征项的文档总数除以总 文档个数，s 。指不包含w 的文档集合；足是属于类别c 的文档集合，( e ( s 。” 为出现了特征项的文档并且属于e 类的概率。 假设共有n 篇文档，其中1 1 l 篇文档为用户感兴趣的文档，1 1 2 篇文档为用户 不感兴趣的文档；共有m 篇文档含有特征项矿，其中用户感兴趣的文档中共有 m l 篇文档含有特征项，用户不感兴趣的文档中共有m 2 篇文档含有特征项形。 贝0 p ( m ) = 生，p ( 曼蒯) = 竺， ( 2 4 7 ) 仃 n 推导成 j ( s ) ：一n ll 0 9 2 ( 堕) 一n 21 0 9 2 ( 竺王) ( 2 4 8 ) nnnn 由此， i ( s 。m ) = 一堕i 0 9 2 ( 堕) 一生l 0 9 2 ( 粤) ， r nmml h i ( s ，“) = 一旦 孚l 0 9 2 ( 旦l 堕) 一等兰l o g ：( 笙导) ， n mn i nn mh m e ( w = p r e s e n t ) = 一m ，p ( w = a b s e n t ) = n - m 。 1 4 第2 章文本分类技术 式( 2 4 5 ) 可以写成： e ( ，s ) = ，( s ) 一 尸( f r = p r e s e n t ) l ( s , 。) + p ( 矿= a b s e n t ) l ( & ；m 。) 】 = 一生l 0 9 2 ( 堕) 一生l 0 9 2 ( 生) 一l 里( 一m tl 0 9 2 ( 堕) 一m 2l 0 9 2 ( 堕) ) hnnn 、- n mr at ht n + 旦竺( 一旦l 二堕1 0 9 ：( 生丑) 一竺二鉴l 0 9 2 ( 竺2 二堕) ) l ” n i r an t n ”一聊 n m j ( 2 4 9 ) = 一生l o g ：( 堕) 一生l 0 9 2 芦) + 堕l o g ：( 堕) + 竺l 0 9 2 ( 生) + 尘旦l 0 9 2 ( 生兰) 一竺二塑l o g ：( 兰2 二丝) 选择e ( w ，s ) 较大的特征项，组成维数较低的特征向量空间。 信息嫡法的优势在于对未出现词可能对文本产生的影响做了考虑，不足之 处是在进行特征值选择时计算量大，影响了效率。 ( 4 ) z 2 统计量方法( c h i ) 。z 2 统计量用于度量特征项w 和类别c 之日j 的独 立性。w 表示