（计算机软件与理论专业论文）基于两步策略的英文文本分类研究.pdf

重庆邮电大学硕士论文 摘要 进入九十年代以来，互联网得到了极大的发展，产生了海量的非结构化和半 结构化文本信息。如何对之进行有效的组织和管理，使用户能方便、准确地查找 到所需要的信息，是信息处理的一大目标。基于人工智能技术的自动文本分类已 成为信息处理的关键技术，它能根据文本的语义将大量的文本自动分类，有效地 解决有关文本信息的组织、管理等关键问题。 文本分类的方法很多，典型的有朴素贝叶斯分类器、基于向量空间模型的分 类器、基于实例的分类器和用支持向量机建立的分类器等，以及由几位学者提出 的基于两步策略的高性能文本分类方法，主要是对中文两类文本、多类单标签文 本分类。这就提出了两个问题：能不能将两步分类策略从单标签分类问题推广 到多标签( 兼类) 分类问题? 如果能，如何将它推广到多标签文本分类? 能不 能把两步策略应用到英文文本分类中去? 本文阐述了文本分类的关键技术，包括分类的一般过程、特征抽取、特征选 择和分类方法等；重点描述、分析和对比了常用的特征选择算法和分类方法。提 出了基于两步策略的三种多类多标签英文文本分类方法，1 ) 以贝叶斯为分类器， 以抽取词根的单词和未抽词根的单词分别作为第一、第二步使用特征的两步方法； 2 ) 以贝叶斯和决策树分别为第一、第二步使用分类器的两步方法；3 ) 以i d 3 、c 4 5 和贝叶斯的组合分类器对部分特定类别进行分类，然后对余下类别采用方法2 进 行二次分类的混合两步方法。在此基础上，还提出了一种优化算法，在 r e u t e r s 一2 1 5 7 8 语料上的实验表明，本文提出的方法具有较高的性能，三种方法中， 方法3 具有最好的性能。 关键词：文本分类，两步分类策略，分类器，兼类分类 重庆邮电大学硕士论文 a b s t r a c t s i n c et h eb e g i n n i n go ft h e1 9 9 0 s 。t h ei n t e m e th a sg o tag r e a td e v e l o p m e n t t h e r ei sal o to f u n s t r u c t u r e da n ds e m i - s t r u c t u r e dt e x ti n f o r m a t i o ng e n e r a t e d0 1 3 t h ei n t e r a c te v e r y d a y h o wt o o r g a n i ca n dm a i l a g ot h e me f f e c t i v e l y ，a n de n a b l e su s e r st oi d e n t i 母t h en e e d so f t h ei n f o r m a t i o n 鲻i l ya n d 淞u 胁l y 7t h c y 眦a l lt h em a j o rg o a l so fi n f o r m a t i o np r o c e s s i n g a u t o m a t i ct e x t c l a s s i f i c a t i o nb a s e do na r t i f i c i a li n t e l l i g e n c et e c h n o l o g yh a sb e c o m ea k e yi ni n f o r m a t i o np 站i n g t e c h n o l o g y , a c c o r d i n gt ot h em e a n i n go f t e x t s , i tc a ua m o m a t i c a l l yc l a s s i f yal a r g em o u n to f t e x t s i tr e s o l v e st h ek e yi s s u e se f f e c t i v e l yi n c l u d i n gt h eo r g a n i z a t i o na n dm a n a g e m e n ta b o u tr e l e v a n tt e x t i n f o r m a t i o n t h e r ea m a n ym e t h o d sf o rt e x tc l a s s i f i c a t i o n ，n mn a i v eb a y e s i a nc l a s s i f i e r s , v e o t o rs p a c e m o d e lb a s e dc l a s s i f i e r s , e x a m p l e b a s e dc l a s s i f i e r sa n dc l a s s i f i e r sb a s e do ns u p p o r tv e c t o rm a c h i n e s & r e5 0 m ot y p i c a lo n e s s e v e r a lr e s e a r c h e r sp r o p o s e das o - p e r f o r m a n c et e x tc a t e g o r i z a t i o nm e t h o d b a s e do nt w o - s t e ps l r a t e g y , w h i c hf o c u so i lb i n a r yc l a s sa n dm u l t i - c l a s sw i t hs i n g l el a b e lo i lt h e c h i n e s et e x t sc l a s s i f i c a t i o n t h e r ea r et w om a j o rp r o b l e m sf o rt h i sm e t h o d c a nas i n g l el a b e l c l a s s i f i c a t i o no f t h et w o - s t e ps t r a t e g yb ee x t e n d e dt om u l t i l a b e lc l a s s i f i c a t i o n ? i f s o ，h o wc a ni tb e e x t e n d e dt ot h em u l t i l a b e lt e x tc l a s s i f i c a t i o n ? c o u l dw eu 辩t h et w o - s t e ps t r a t e g yi l ie n g l i s ht e x t c l a s s i f i c a t i o n ? 1 1 l i sp a p e ri n 昀d u c 器s o m ek e yt e c h n o l o g i e so ft e x t c a t e g o r i z a t i o n , i n c l u d i n gi t sg e n e r a l p c c 鹤，f e a t u r ee x t r a c t i o n , s e l e c t i o na n dc l a s s i f i c a t i o n i tf o c u s e so i if e a t u r es e l e c t i o na n d c l a s s i f i c a t i o n i nt h i sp a p e rt h r e em u l t i - c l a s sm u l t i l a b e le n g l i s ht e x tc a t e g o r i z a t i o nm e t h o d sb a s e d o i lt w o - s t e p ss t r a t e g ya mp r o p o s e d 1 1 l cf i r s tm e t h o dc l a s s i f i e st e x t su s i n gb a y e sc l a s s i f i e rw h i c h 嘲s t e m m e da n dn os t e m m e dw o r d sa sf e a t u r e ss e p a r a t e l yi nt h ef i r s ta n ds e c o n ds t e p 1 1 1 es e c o n d m e t h o du s e sb a y e sc l a s s i f i e ri i lt h ef i r s ts t e pa n dd e c i s i o nt r e ec l a s s i f i e ri nt h es e c o n ds t e p t h et h i r d m e t h o dc l a s s i f i e ss o m es p e c i a lc a t e g o r i e sb ya ne n s e m b l ec l a s s i f i e rw h i c hi sac o m b i n a t i o no f i d 3 、 c 4 5a n db a y e sc l a s s i f i e ra tf i r s t , a n dt h e nt h er e s tc a t e g o r i e sa l oc l a s s i f i c du s i n gt h es e c o n dm e t h o d a no p t i m i z a t i o na l g o r i t h mi sf u l l h e rd e v e l o p e d e x p e r i m e n tr e s u l t ss h o wt h a tt h et h r e em e t h o d s a b o v e h a v e g o o d e f f e c t i v e n e s s a n d p e r f o r m a n c e t h e t h i r d m e t h o d i s t h e b e s t 0 1 1 0 1 ( e yw o r d s ：t e x tc a t e g o r i z a t i o n ) t w o - s t e p sc l a s s i f i c a t i o ns 咖；c i a a s i f i e r ) m u l t i - c l a s s m u l t i l a b e lc l a s s i f y i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知。除了文中特别加以标注和致谢的地方外，论文中不包 含其他入已经发表或撰写过韵研究成果也不包含为获得重鏖墼壹太堂或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位敝作者躲做醉签字眺砷年伽彦日 学位论文版权使用授权书 本学位论文作者完全了解 重医邮虫太堂有关保留、使用学位论文的 靓定，有权保留并商国家有关部门或机构送交论文的复印件移磁盘。允许论文 被查阅和借阅。本人授权重废邮垒太堂 可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后适用本授权书) 靴敝储鹳。傅蚌 签字日期； 西7 年f 月含日 导师签名：刀鲺属乙， 签字日期, 7 , o - 7 年月7 重庆邮电大学硕士论文第一章绪论 1 1 引言 第一章绪论 进入上世纪九十年代以来，随着互联网络技术的高速发展，越来越多的传统 媒体如报章杂志等开始发行电子出版物同时，采用互联网来发布信息这种方式 也逐渐被人们所接受，越来越多的人习惯在互联网上查找和发布信息。互联网上 的信息量呈爆炸式的增长，已经成为一个庞大的信息数据库。 如此巨大的信息量帮助人们开阔了视野，丰富了知识。同时，如何从这些海 量信息中快速准确地找到自己所需要的内容，已成为一个问题，这也是信息处理 的一大挑战。信息处理的一大耳标是有效地组织和管理众多的电子信息，使用户 能方便、准确地查找到所需要的信息。目前，相关学者已提出了文本检索、文本 分类、主题概念识别等多种信息组织管理技术。基于人工智能技术的自动文本分 类已成为信息检索和文本挖掘的关键技术，它能根据文本的语义将大量的文本自 动分类，有效地解决了有关文本信息的组织、管理等关键问题 文本自动分类是指在给定的分类体系下，根据文本的内容自动判别文本类别 的过程。通过文本分类技术可以弥补传统搜索引擎的不足，过滤用户不需要的文 章，并将检索结果自动分类，使用户能够方便地查找到自己所需要的内容在信 息服务过程中，文本自动分类技术是文本挖掘的基础与核心，是自然语言处理中 重要的研究方向之一；同时在大规模信息处理方面是重要的应用技术之一。通过 文本自动分类系统，能够很好地帮助用户整理、获取信息，在提高信息检索的速 度和准确率方面具有重要的研究价值。 国外在文本自动分类以及信息检索、信息抽取等相关的领域进行了较为深入 的研究。作为机器学习的应用领域，文本分类的理论研究可以追朔到2 0 世纪6 0 年代初【”。它的发展过程大致可以划分为以下三个阶段1 2 l = 第一阶段是2 0 世纪8 0 年代前。在这一时期，模式识别和信息检索相继发 展成为- - t 学科。一些学者相继提出了概率标引( p r o b a b i l i s t i ci n d e x i n g ) 模型、感知 机( p e r c e p t r o n ) 、向量空间模型( v e c t o rs p a c em o d e l ，v s d 用于对文本分类。这一阶 段主要是集中在对分类理论的研究，应用方面则主要集中在信息检索。 第二阶段是2 0 世纪8 0 年代。这一阶段主要是采用传统的知识工程 ( k n o w l e d g ee n g i n e e r i n g ) 技术，根据专家提供的知识形成规则，手工建立分类器。 这实际上是专家系统。 第三阶段是2 0 世纪9 0 年代以后互联网技术的发展，对文本分类提出了 重庆邮电大学硕士论文第一章绪论 迫切需求。在这一时期，文本分类的主要特点是采用统计机器学习方法，自动建 立分类器【i 】。基于机器学习的文本分类方法克服了以前手工建立分类器的缺点，使 得文本分类具有了真正的实用价值。主要特点有：一是分类知识来源于机器对训 练集的自动学习，不再依赖于领域专家；二是学习和分类过程不需要人工干预， 分类效率和准确率得以提高。 基于机器学习文本分类的基础技术由文本的表示( r e p r e s e n t a t i o n ) 、分类方法及 效果( e 雎c t i v c 北站) 评估三部分组成口】。s e b a s t i a n i 在文献【l 】中对文本分类发展历程及 当时的技术进行了总结，主要内容包括：( 1 ) 文本关于项( t e r m ) 或特征的向量空间 表示模型( v s m ) 及特征选择( s e l e c t i o n ) 与特征提取( e x t r a c t i o n ) 两种表示空间降维 ( d i m e n s i o n a l i t yr e d u c t i o n ) 策略，讨论了f 、i g 、m 【、o r 等用于特征过滤的显著性 统计量及项聚类和隐含语义索引( l s i ) 等特征提取方法；( 2 ) 当时较成熟的分类 模型方法，即分类器的归纳构造( i n d u c t i v ec o n s t r u c t i o n ) 或模型的挖掘学习过程；( 3 ) 分类效果评估指标，如正确率( p r e c i s i o n ) 、召回率( r e c a l l ) 、均衡点( b e p ) 、f b ( 常用 f i ) 和精度( a c c u r a c y ) 等，以及之前报道的在r e u t e r s 等基准语料上的效果参考比较。 文本分类的方法很多【l 】，典型的有朴素贝时斯分类器m 】、基于向量空间模型 的分类器m 、基于实例的分类器【8 1 和用支持向量机( s v m ) 建立的分类器【9 4 川， 以及多分类器的集成学习等。文本分类方法研究的主要目标是提高分类效果，实 用的系统还必须兼顾存储和计算能力受限等条件下，学习过程的可扩展性和分类 过程的吞吐率( 速度) ”一。近年来，采用多( m u l t i p l e ) 分类器集成学( e n s e m b l el e a r n i n g ) 的方法被普遍接受；而支持向量机( s v m ) 仍然代表了单重( s i n g l e ) 方法的发展水 平；另一方面，b a y e s 、线性分类、决策树及k - n n 等方法的能力相对较弱，但它 们的模型简单，效率较高，这些方法的修正和改进引起了人们持续的关注。 樊和孙【1 2 j 提出了一种基于贝叶斯分类器的高性能的两类中文文本分类方法， 并于文献l l 川在两类的基础上提出了多类两步中文文本分类方法，这两种方法的主 要思想是考虑文本特征对文本的区分能力，部分文本特征对部分文本区分能力强， 而其他文本特征对另一部分文本的区分能力更显著。据此提出第一步由通用性较 强( 泛化能力强) 的文本特征对大部分的文本进行分类，并由此划分一个分类不 可靠区域。对于落在这个区域的文本。进入第二步由对这些文本区分能力更强的 特征来对它们作分类决策。 樊和孙提出的基于两步策略的高性能文本分类方法，主要是对中文两类文本、 多类单标签文本分类。这就提出了两个问题：能不能将两步分类策略从单标签 分类问题推广到多标签( 兼类) 分类问题? 如果能，如何将它推广到多标签文本 分类? 能不能把两步策略应用到英文文本分类中去? 本文针对这两个问题，以 多项式贝叶斯分类器为实现工具，从不同特征、不同分类器两个方面研究了基于 2 重庆邮电大学硕士论文第一章绪论 两步策略的多类多标签英文文本分类方法。 1 2 论文主要工作 分类器是文本分类中最关键的技术，本文通过修改文本分类器来研究基于不 同特征、不同分类器的两步策略对英文文本分类的意义。由于r e u t e r s 2 1 5 7 8 是文 本分类领域中最常用的测试平台，本文使用该文本集并通过实验来检查所设计策 略的效果。具体的工作如下： 1 对分类技术的研究在向量空间模型( v s m ) 的基础上构建文本表示模型，对 现有的特征选择及提取算法、分类器的分类函数、兼类文本分类算法进行研究， 以此构建文本分类系统，为基于两步策略的文本分类算法搭好研究平台。 2 不同特征的两步策略提出了以贝叶斯为分类器，以抽取词根的英文单词作 为第一步的文本特征，以未抽词根的单词、二元串、抽取词根与未抽词根的混合 特征分别作为第二步特征的两步策略，特征选择方式均采用信息增益的方法。 3 不同分类器的两步策略提出了第一步以贝叶斯为分类器，第二步以决策树 为分类器的两步策略。 4 混合两步分类方法设计了组合投票分类( 集成学习) 与两步策略的混合两步 分类方法。 5 优化算法根据r e u t e r s - 2 1 5 7 8 语料的自身特点，提出了一种优化算法。 6 通过对以上提出的方法进行试验，表明这些方法均是可行的，可以达到较 高的分类性能。 1 3 论文组织结构 本文以基于两步策略的英文文本分类技术为阐述对象，其组织结构如下： 第一章：绪论。主要介绍了文本分类技术的发展和应用，以及本论文的研究 背景和主要工作； 第二章：文本分类技术。研究了文本分类技术的一般过程，详细介绍了文本 特征抽取、特征选择的方法，分析对比了各特征选择方法，给出了文本分类的常 用评估指标； 第三章：常用文本分类器。介绍了文本分类领域的常用分类器，并进行了深 入的分析，同时阐述了集成分类算法； 第四章：兼类文本分类。总结了当前一些学者在文本分类领域提出的兼类文 本分类的方法，主要有问题转换和修改现有分类器形成的适应性算法两大类： 重庆邮电大学硕士论文 第一章绪论 第五章：两步策略文本分类。介绍两步策略对文本自动分类的思想，提出了 基于两步策略的多类多标签英文文本分类算法，包括不同特征的两步策略和不同 分类器的两步策略，并详细阐述了算法的实现； 第六章：评估实验。通过设计多组实验分别验证不同特征的两步策略和不同 分类器的两步策略对文本分类效果的提高，以及组合分类与两步策略的混合两步 方法，并提出了优化算法； 第七章：结束语本章对全文工作进行总结，指出了还需改进的地方以及未 来工作的展望。 重庆邮电大学硕士论文 第二章文本分类技术 第二章文本分类技术 文本分类( t e x tc a t e g o r i z a t i o n ) 就是把自然语言文本按给定的分类集进行标记 分类。该问题可定义为：假设预定义的文本分类集为c = q ，乞，) ，要进行分 类的文本类型集为d = 4 ，吃，以) ，文本分类的任务就是给每一个 e d c 分配一个布尔值( t ，f ) ，表示嘭是否属于q 判” 2 1 文本分类的一般过程 文本分类的一般过程如图2 1 所示，首先对训练文本进行预处理，把抽取出来 的特征用特征选择算法进行过滤，得到一个特征空间( 常用的有特征向量空间 v s m ) ，对特征空间用分类算法学习获得一个分类器；预处理测试文本形成一个测 试文本特征空间，把这些文本向量输入到分类器，分类器实现对测试文本的分类。 k 二1 一q 测l ” 除= = = 爿越 睦富 i 鐾笙奎塑；j 程 淹囱 l 南 髫 分类器 ：k ：壁堑室塑jj 翮 1，一 在文本分类中，广泛使用向量空间模型v s m 作为特征空问。在v s m 中，文 本d 被看成是由特征二元组组成的特征向量( f e a t u r e v e c t o r ) ； d = “，d ) ，以，m o ) ，以，m o ) ( 2 1 ) 其中：( t k ，w u ) l s j s j 为特征f i 的二元组，w k f 为，i 在文本d 中的权重，s 为 特征集的大小。在v s m 中，没有考虑特征在文本中的位置信息以及语法作用等。 重庆邮电大学硕士论文第二章文本分类技术 2 2 文本特征抽取 构成文本的词汇，数量是相当大的，同时，表示文本的向量空间的维数也相 当大，可以达到几万维，因此我们需要进行维数压缩的工作，这样做的目的主要 有两个：第一，为了提高程序的效率，提高运行速度；第二，所有几万个词汇对 文本分类的意义是不同的，一些通用的、各个类别都普遍存在的词汇对分类的贡 献小，在某特定类中出现比重大而在其他类中出现比重小的词汇对文本分类的贡 献大，为了提高分类精度，对于每一类，我们应去除那些表现力不强的词汇，筛 选出针对该类的特征项集合。所以我们需要对文档进行预处理： 1 禁用词( s t o pw o r d s ) 的去除 这些词在文档中出现的频率非常高，但却没有任何意义。( 如：的、是、了， 英文中的t h e 、i s 、b i n 、a r c ) 2 词根抽取 从文件或查询中去掉词的前后缀，用以形成和系统内部模型相一致的词项。 做这件事是为了把具有同样概念意义的词( 如w a l k , w a l k e d , w a l k e r , w a l k i n g ) 统一处 理 3 ( 中文) 分词、词性标注、短语识别 由于西方语言多数为拼音文字，词与词之间有形式符号( 如空格) 分开，不存在 分词问题；而汉语为表意文字，词与词之间无形式符号，所以要对中文文档进行 分词，把句子切分成字、词和短语作为特征项，标注出动词、名词、形容词和副 词。根据实验结果，通常认为选取词作为特征要优于字和短语。 4 词频统计 幻词频( t e r mf r e q u e n c y ) 指某特征项在一篇文档中出现的次数。词频分为绝对词频和相对词频，绝对 词频，即使用词在文本中出现的频率表示文本，相对词频为归一化的词频，其计 算方法主要运用t f i d f 公式，目前存在多种t f i d f 公式，普遍采用的t f - i d f 公 式如下： w ( t ，d ) = 抛，西l o g ( 型+ 0 0 1 ) n i ( 2 2 ) 其中。彤( f ，刁) 为词f 在文本露中的权重，雨矿( f ，孑) 为词f 在文本孑中的词 频，n 为训练文本的总数，为训练文本集中出现t 的文本数，分母为归一化因 子 6 重庆邮电大学硕士论文第二章文本分类技术 根据 i f i d f 公式，文档集中包含某一词条的文档越多，说明它区分文档类别 属性的能力越低，其权值越小；另一方面，某一文档中某一词条出现的频率越高， 说明它区分文档内容属性的能力越强，其权值越大。 ”文档频率( d o c u m e n tf r e q u e n c y ) 所有文档集合中出现某特征的文档数目。 5 去除区分度较小的噪音特征项可以提高分类准确率，去除重要性较低的低 频特征项可以加快运行速度。 2 3 文本特征选择 文本特征选择就是从特征集t = ，i ，j ) 中选择一个真子集 ? 7 t t ，f ， ( s ，j 脚。， 但需要注意的是，这些结果仅仅是象征性的；对于这些函数的相对优点，只 有在完全控制条件下以及大量不同状态( 如不同分类器，不同的语料库等等) 下做比较实验才能得出更一般的结论。 代六玲等【1 9 】采用支持向量机( s v m ) 和i d 州两种不同的分类器比较了文档频 率d f 、信息增益i g 、c h i 统计和互息信m i 四神特征选择方法对中文文本分类效 果的影响，发现利用类别信息的特征抽取方法由于对低频词的倚重和中文的特征 空间维数远远高于英文特征空间维数两个方面的原因，导致在不加以修正的情况 下并不适合中文文本分类。 2 4 文本分类器 研究文本自动分类的关键问题是如何构造分类器，分类函数需要通过某种算 法进行学习获得。目前，常用的文本分类技术多是通过统计方法或知识工程的方 法实现的。知识工程方法主要依赖于语言学知识，需要编制大量的推理规则，实 现相当复杂。因为自然语言的复杂性，现阶段还无法完全实现自然语言的机器理 解，当前对文本分类技术的研究主要是偏重于统计学方法实现的文本分类。相对 于知识工程方法来说，基于统计学方法实现的文本分类具有速度快、实现简单等 特点，并且分类的准确率也较高，能够满足一般应用的要求。 本文将在第三章详细介绍常用的文本分类器。 2 5 评估指标 由于不能对自然语言进行严格的形式化，因此对分类器的性能评价主要是通 过实验进行的。对于二分类问题，常用的评价标准有：准确率，召回率、b r e a k e v e n 点、f - m e a s u r e 、精度错误率等。在多分类问题中。为了对整个分类系统进行评价， 通常对单个分类器的分类指标进行宏平均或微平均 1 0 重庆邮电大学硕士论文 第二章文本分类技术 2 5 1 二分类问题 表2 1 列出了单个类别q 的邻接表，则计算该类别的精确率、召回率和f l 值 有如下公式： 专家分类为c 类别a y e sn o 分类罂 y e s弛船 分类为c n o f n t 力讥 1 精确率( p r e c i s i o n ，p ) 只：堡( 2 1 0 ) 弛+ f p , 精确率是所有输入系统进行分类处理的文本中与专家分类结果完全吻合的 文本所占的比率，p 描述了分类结果中的准确程度，即分类结果中有多少是正确 的。 2 召回率( r e c a l l ，r ) 置= 丑t g + f n , ( 2 1 1 ) 召回率是人工分类结果应有文本中分类系统分类正确的文本所占的比率。r 描述了正确分类的能力，即已知的文本中，有多少分类正确 3 f - m e a s u r e 对于一次测试，准确率和召回率一般是成反比的。提高准确率，召回率会下 降；提高召回率，准确率会下降。f - m e a s u r e 综合了p 和r 两个指标，可以对 分类器进行整体评价。 乃：氅掣 ( 2 1 2 ) 8 9 e 七r i 其中：芦是调节p 和r 相对重要程度的常数，当多= 0 时，f - m e a s u r e 为准 确率；当寸m 时，为召回率。通常取= l ，对p 和r 平等看待，这时得到 最常用的f l - m e a s u r e 指标( 简称f 1 ) e ：! 兰塑( 2 。1 3 ) ，= 一 z 。l j j 。 p 七r 4 b r e a k - e v e n 点( b r e a k - e v e np o i n t , b p ) 重庆邮电大学硕士论文第二章文本分类技术 b r e a k e v e n 点是另一个常用的综合评价指标。它是当分类器的准确率等于召 回率时的值。通常b r e a k - e v e a 点很难找到，这时通常可以采用线性插值的方法确 定。 2 5 2 多分类问题 在多分类问题中，为了对整个分类系统进行评价，通常需要对所有类别的分 类指标进行宏平均或微平均 一个多类分类测试集的分类结果可以用如下邻接表( 表2 2 ) 来表示： 表2 2所有类别的邻接表 类别集合专家分类 c = c ”，c l d y e s n o y e s 即：呈码即：墨肥 分类器 l d 州；呈巩 n o 剧= 川 决策结果 加ii - ! 宏平均是指对各分类器的评价指标求算术平均值。 宏平蝴率：一一秤 荆獬：一小鲁 宏平均f i ；一母瞥 ( 2 1 5 ) ( 2 1 6 ) 2 微平均 微平均是指将单个分类器的邻接表合并成一个总邻接表，然后在总邻接表上 计算评价指标 微平均精确率胁伽小鼎= 赫l c l t p 泣m 重庆邮电大学硕士论文 第二章文本分类技术 微平均硼率：研加一而t p = 意y 荠l c l t 蒜p 他m 微平均f l ：砌小特 ( 2 1 9 ) 其中，i c i 表示多分类中类别的个数。 在微平均和宏平均两个评价指标上，分类器每次分类对整个分类结果的影响 程度是不一样的。在微平均看来，每一次分类的地位是平等的，这适用于对文本 相同对待的情况，微平均有利于大类型。对宏平均来说，各个类型的地位是平等 的。宏平均对小类型文本敏感相对而言，在文本分类中，微平均比宏平均使用 得更广。 2 6 小结 本章详细介绍了文本分类技术的一般过程，包括文本特征抽取所需要处理的 要点，深入分析对比了文档频率、互信息、信息增益、统计量、n g l 系数、g s s 系数等多种特征选择方式，介绍了文本分类的常用评估指标。 重庆邮电大学硕士论文第三章常用文本分类器 第三章常用文本分类器 文本分类中，分类方法( 分类器) 主要来源于机器学习、信息论等领域，它 也是文本分类系统的核心过去学者提出了很多分类算法，这些算法主要区别在 于获取分类规则的方法不同本章将介绍几种常用的文本分类器。 3 1 贝叶斯分类器 贝叶斯分类器是一类常用的分类器，最基本的形式是简单贝叶斯( n a t v o b a y e s ，也称为朴素贝叶斯) 分类器即】1 2 1 1 。该算法的基本思路是计算文本属于类别 的概率，文本属于类别的概率等于文本中每个词属于类别的概率的综合表达式。 其原理是计算文本正属于某个类别的概率尸( qa x ) ，将文本分到概率最大的类别 中去。计算尸( 巳i t ) 时，利用了贝叶斯公式： ，( c jid , ) = p ( c j 矿) p ( d i c j ) ( 3 。1 ) 尸( 勺) 是类的先验概率，p ( 4iq ) 是类条件概率。对同一篇文本，( 或) 不变 引入文本分布假设，对，( 以l 巳) 进行概率估计a 基于不同的分布假设，会得到不 同的概率分类器。例如引入朴素贝叶斯假设：设t 表示为特征集合( ，t 2 ，) ， ，l 为特征个数，假设特征之间相互独立，这时，尸( 吃l 巳) 可以看成是各特征的概率 积，如公式( 3 2 ) 所示 ，( 以i c ，) = _ p ( r i i c ) + p ( t 2 l 勺) + ，( lc ，) = l l ，( f ，l 勺) ( 3 2 ) i p ( c ，) 和尸“l c ) 都可以利用训练集估计。 e y h e r a m e n d y 等【2 2 】比较了基于泊松、贝努利、多项式、负二项式等四个不同分 布假设的贝叶斯分类器的概率模型的性能，采用的数据集为m d r 、n e w s g r o u p s 的1 8 8 2 8 篇文本、r e u t e r s - 2 1 5 7 8 、以及在r e u t e r s 一2 1 5 7 8 中选取的1 0 个类别这4 个 数据集，分别测试了宏平均、微平均的召回率、精确率和f 测试值。实验表明。 所有的数据集中多项式模型在宏平均、微平均的f 测试值中至少有一个最高的， 在其中2 个数据集上宏平均和微平均的f 测试值都是最高的。泊松模型在 n e w s g r o u p s 上和多项式模型比较类似，但在r e u t e r s 2 1 5 7 8 的l o 类数据集上比多 项式模型要稍微差一点。贝努利模型在m d r 和r e u t e r s - 2 1 5 7 8 两个数据集上都与 多项式模型的性能比较类似。负二项式模型是性能最差的一个 重庆邮电大学硕士论文 第三章常用文本分类器 3 2k n n 分类器 心j n ( k - n e a r e s t n e i g h b o r ) t 1 川咧，代表七个最近邻分类法，通过七个最与之邻近 的历史记录的组合来辨别新的记录。 该算法韵基本思路是：在给定新文本后，考虑在训练文本集中与该新文本距 离最近( 最相似) 的七篇文本，根据这k 篇文本所属的类别判定新文本所属的类别。 如下图3 1 为一个基于实例的懒散j 论i n 分类器。 图3 1 基于实例的懒散i n n 分类器- a 类，o - b 类k 常取3 或5 分类函数如公式( 3 3 ) 所示。 厂协) = v o t e ( ( d , ) i e ：e i g h b o r ( d ) ) ( 3 3 ) 其中：n e i g h b o r k ( d ) 为待分类文本d 在训练集中的k 个最近邻居；v o t e o 为 选举函数。 k 近邻分类器中，邻居的选择可以是任何判断文本相似的方法，例如：概率 方法，相似度方法等。v o t e o i 函数可以是多数选举( m a j o r i t yv o t i n g ) ，或者加权组 合( w e i g h t i n gc o m b i n a t i o n ) 等。多数选举是指在选举时。七个邻居中每个邻居的地 位是一样的；加权组合是指选举时，各个邻居的地位不同，具有不同的权重。 k n n 方法基于类比学习，是一种非参数的分类技术，在基于统计的模式识别 中非常有效。对于未知和非正态分布可以取得较高的分类准确率，具有鲁棒性、 概念清晰等诸多优点。l n n 方法虽然从原理上也依赖于极限定理，但在类别决策 时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不 平衡问题。从分类过程来看，k n n 最直接地利用了样本和样本之间的关系，减少 了类别特征选择不当对分类造成的不利影响，可以最大程度地减少分类过程中的 误差项。另外，对于一些类别特征不明显的类别而言，k n n 方法更能体现出其分 类规则独立性的优势，使得方便快捷的分类实现成为可能从对多种算法的测试 重庆邮电大学硕士论文 第三章常用文本分类器 表明，k n n 算法在分类效果上是最佳的，同时在训练过程中投入的时间最少。 但在文本分类中，k n n 方法的缺陷也突出地暴露出来，主要有：首先k n n 算法 是懒散的分类算法，对于分类所需的计算都推迟到分类时才进行，在其分类器中 存储有大量的样本向量在未知类别样本需要分类时，再计算所有存储样本和未 知类别样本的距离，对于高维文本向量或样本集规模较大的情况其时问和空闻复 杂度较高( 时间代价为o ( n m ) ，n 为v s m 空间特征维数，m 为样本集大小) ；其次， k n n 方法是建立在v s m 模型上的，其样本距离的测度使用欧式距离，各维权值相 同，也就是认定各维对于分类的贡献是相同的，显然这是不符合实际情况的，同 等的权重使得特征向量之间距离或者夹角余弦的计算不够准确，进而影响分类精 度：最后，对于文本的高维向量，对于分类起主要作用的维数远远低于文本本身 的维数，相当多维对于文本分类意义不大甚至是噪声数据。 基于上面的缺点，出现了很多种改进的k n n 算法，如：应用特征聚合进行的 改进l 羽n 算法、基于隐含语义的改进k n n 算法、强化语义链属性因子的改进k n n 算法、与检索相结合的迭代近邻法等。通过强化语义链因子的作用来k n n 分类， 在封闭测试中结果很好，强化了特征关联和共现的作用。基于隐含语义的k n n 方 法以一个较小而更健壮的统计导出的索引概念空间替代原来基于独立词索引的文 档向量空间，表现出明显的性能优势。基于特征聚合模式的k n n 文本分类，分类 算法能够解决关联特征维的提取和向量空间维数高的问题，明显提高了分类的准 确率和召回率。基于k n n 和自动检索的优化分类算法迭代近邻法，能使自动分类 系统的整体查全率和查准率有一定的提高，特别是在训练样本数量不足的环境下 优化效果更为明显唧】 李和胡 2 5 1 针对k n n 方法计算量大，而且训练样本的分布不均匀会造成分类准 确率的下降这两个问题，提出了一种基于密度的k n n 分类器训练样本裁剪方法，降 低了k n n 方法的计算量，而且使训练样本的分布密度趋于均匀，减少了边界点处测 试样本的误判。 3 3 支持向量机 支持向量机( s u p p o r t v e c t o r m a c h i n e s v m ) 【1 0 i 2 6 1 t 2 7 1 是_ 类基于v a p n i k 的统计 学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，s l t ) 和w o l f e 对偶规划理论的分类和函数估计 方法。它是针对结构风险最小化原则提出的，改变了传统的经验风险最小化原则， 具有很好的泛化能力。 不失一般性，考虑两分类问题，给定一组训练样本， ( 而，y i ) ，( 而，y 。) ，( ，y u ) ，一e r ”，y 一1 ，+ 1 ，求最优分类决策函数。对于线性 1 6 重庆邮电大学硕士论文第三章常用文本分类器 可分类问题，为了求解线性超平面决策函数f c x ) = j t 印也刁+ 6 ) ( 其中s i g n o 为指 示函数，x 0 时输出为l ，工 从w ( l l s f n n e t n b ： 在宏层次上，对f 值计算s t e s t ，t t e s t ，t 7 一t e s t 得到的结果是 ( s v u ，n w ，工三s 研 n b ，加v m ；在微层次上，当基于误分率的p t e s t 值时得到 的结果为 s v m ，i n n l l s f n n e t n b 。j o a e h i m s l 3 l 】使用r e u t e r s 2 1 5 7 8 1 七较了 b a y e s ，r o c c h i o ，c 4 5 ，k n n ，s v m 的p r e c i s i o n r e x a l l - b r e a k e v e np o m t 值和m i c r o a v e r a g e d 值，得出s v l “和k n n 的性能优于b a y e s ，r o c c h i o ，c 4 5 等几个常用的分类算 法，s v m 同时表现出在高维特征空间很好的扩展能力。 s v m 、k n n 在分类准确性和稳定性方面优于其他分类方法。但k n n 是一种懒 惰学习方法，保存所有训练样本直至测试样本需要分类时，通过计算样本间距离确 定分类，因此其分类时间是非线性的，当训练文本数或特征数增加时，分类时间急剧 1 9 重庆邮电大学硕士论文第三章常用文本分类器 增加。s 、m 目前被认为是分类准确性最好的分类器。当训练样本分布不均匀时，其分 类质量比k n n 还要好。但由于s v m 本质上是两类分类器，对两类分类问题而言， s v m 是线性分类器。但是，当用s v m 实现多类分类时，必须构造多个s v m 分类器，即 将多类分类问题转化成两类分类问题，一般使用一对剩余方法( o a e - v s - r e s t ) 进行多类 分类。对于七类分类问题，需要构造女个分类器，当类别数增多时，其分类时间明显增 加；s v m 的另一个不足就是训练样本数日较大时，内存开销很大，训练时间长。 3 7 集成分类方法 由于集成学习是一个仍在迅速发展中的研究领域，因此关于“什么是集成学 习”，机器学习界目前还没有最终达成共识。狭义地说，集成学习是指利尉多个同 质的学习器来对同一个问题进行学习，这里的“同质”是指所使用的学习器属于同一 种类型，例如所有的学习器都是决策树、都是神经网络等等。广义地来说，只要 是使用多个学习器来解决问题，就是集成学习。集成学习的思路是在对新的实例 进行分类的时候，把若干个