（通信与信息系统专业论文）中文文本自动分类中的若干问题研究.pdf

捅要 本文首先基于类别概念，讨论了文本自动分类中文档类别i h j 的关系，在此基础上对 文本自动分类的定义进行补充说明，并讨论了文本自动分类中与全体文档集合、训练集、 类集合相关的若干问题，并结合具体分类算法进行了相关论述。具体内容如下： ( 1 ) 基于概念间的关系，讨论类别问的关系，分析了每种关系对应的实际分类问题； ( 2 ) 从集合论的角度出发，对文本自动分类问题的定义进行补充说明，指出文本自 动分类是对全体文档集合的划分； ( 3 ) 将现有文本表示模型归纳为3 种：“词袋模型”，“空间向量模型 ，“图模型 ， 在此基础上分析了每种模型对应的全体文档集合； ( 4 ) 论述了训练集的相关性质，定量分析了训练集的稀疏性； ( 5 ) 论述了真实类集合和由分类器划分的类集合间的关系，在此基础上分析了分类 器错分结果类型，指出分类器对错误是敏感的，提出分类器的错误敏感性； ( 6 ) 基于类别概念，从全体文档集合、等价关系、类集合3 个方面分析了常见分类 算法，重点给出了常见分类算法所得类集合的几何性质； ( 7 ) 提出基于向量空间模型分类算法的“重要点结论，论述了重要点对提高分类 器性能的重要性，并结合重要点，讨论基于类中心的“推拉调整策略 ，提出了两种改 进策略； 文章接着针对特征选择，论述了常见特征选择方法的缺点，并在分析、归纳文本权 值计算框架的基础上，提出两种全局最优特征选择模型。模型一以最大化类中心距离为 目标，模型二以最大化类中心距离方差为目标，本文给出了两种模型的具体算法。 最后，设计并构建文本自动分类系统，对本文给出的特征选择算法和对推拉策略的 改进算法进行了相关实验，并分析了互信息和交叉熵两种特征选择算法性能较差的原 因。 关键词：文本自动分类：类别；错误敏感性；重要点；推拉策略；特征选择；全局 最优化 ab s t r a c t 1 1 1 i sp a p e rd i s c u s s e sm er e l a t i o n s h i p s 锄o n gd if f e r e n tc a t e g o r i e sb a s e do nt h ed e 行n i t i o n o fc i a s se r s t l y ，觚dt h e nm a k e sa d d i t i o n a lr e m a r k so na u t o m a t i ct e x tc a t e g o r i z a t i o np r o b l e m ， d i s c u s s e ss o m ep r o b l e m sa b o u tt h ew h o l et e x ts e t 、t r a i n i n gc o 叩u s 、c a t e g o r i e s ，锄da n a l y s i s s e v e r a lc o m m o nc l a s s i 6 e r sw i t ht h e s ep r o b l e m s t h em a i np o i n t so ft h es t u d ya r es u m m a r i z e d a sf 0 1 l o w i n g ： ( 1 ) d i s c u s s e st h er e l a t i o n s h i p s 锄o n gd i f r e r e n tc a t e g o r i e sb a s e do nt h ed e 6 n i t i o no fc l a s s ， m a p st h er e l a t i o n s h i p st oa c t u a lc a t e g o r i z a t i o np r o b l e m s ； ( 2 ) m a l ( e sa d d i t i o n a lr e m a r k so n 卸t o m a t i ct e x tc a t e g o r i z a t i o np r o b l e mb a s e do ns e t t l l e o r ) ，； ( 3 ) d i v i d e st h em e m o d so ft e x te x p r e s s i o ni n t ot h r e ec l a u s s e s ：“b a g g i n gm e t h o d ”，v e c t o r s p a c em e t l l o d ”，g r 印hm e t h o d ”，t h e n 锄a l y s i st h ew h o l et e x t s e to fe a c hm 甜l o d s ； ( 4 ) d i s c u s s e st l l ep r o p e n i e so fn 面n i n gc o 印u s ，锄dq u m i t a t i v e 锄a l y s i st h es p a r s 时o f 俩i l i n gc o 印u s ； ( 5 ) d i s c u s s e st 量1 er e l a t i o n s h i pb e 锕e e nt m ec l a s ss e t 觚dr e a lt l l ec l 邪ss e t ，锄da n a l y s i st 1 1 e t y p e so fe r m rr e s u l t so fc l 嬲s i 6 e r s ，t 1 1 e nt ：h ee r r o rs e n s i t i v i 哆o f c l a s s i f i e ri sp r e m e d ； ( 6 ) b 邪e do nt h ed e f i i l i t i o no fc l a s s ，a i l a l y s i st l l ec o m m o nc l 嬲s i f i e r 晰t l lt l l ew h o l et e x t s e t 、e q u i v a l e n c er e l a t i o n 、f e a lc l a s s e s ，觚dp r e s e n t st l l eg e o m e t 叮p r o p e r t yo f r e a lc l 弱s e sf o r e a c hc l 舔s i f i e r ； ( 7 ) p r e s e n t st l l ei i i l p o n m tp o i n t st 1 1 e o d ro fc l a s s i f i e r b a s e do nt l l et l l e o r y ，m a k e s a r e s e a r c ho n 也ep u s h i n 分捌n gs 臼锄e g y 锄dm a l ( ea 锄e n d i i l e mo nt l l i ss 臼锄e 黟 t l l e n 廿l i sp a p e rd i s c 鸿s e st 1 1 ed e f e c t s 恤c o m m o n 凫a t u r e l e c t i o nm 础o d s ，r a i s e sa f e a n 鹏l e c t i o nc o m p u t a t i o nm e t l l o d s 纳m e ，锄dt h e np r e s e i l t st 、o 酉o b a lo p t i i i l i z e df e a t u f e l e c t i o nm o d e l s ：t l l i so b j e c t i o no ft l l ef i r s tm o d e li st om a ) ( i 血z ed i s t a n t 锄o n gc a t e g o r i e s c a n c r o i d s ，a i l dt h es e c o n dm o d e l so b j e c t i o ni st 0m a x i m i z et l l ed e v i a t i o no fd i s t a n t 锄o n g c a t e g o r i e sc 锄c r o i d s a tl 缄b u i l d e su pat e x tc a t e g o r i 刎i o ns y s t e m ，m a l ( ee x p e r i m e n to na l g o r i t h h l st l l i sp a p e r r a i s e d k e yw o r d s ： a u t o m a t i ct e x tc a t e g o r i 刎i o n ；c a t e g o r i z a t i o n ；e n 0 rs e n s i t i v i t y ；i m p o r t a n tp o i n t s ； p u s h i n g _ d r a w i n gs t r a g e d y ；f e a t u r es e i e c t i o n ；g l o b l eo p t i m i z i t i o n 海南大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所譬交的学位论文，是本人在导师的指导f ，独立进行研究工作所取得的成果。 除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品或成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人 承担。 论文作者签名： 日期：，耐年石月尹日 学位论文版权使用授权说明 本人完全了解海南大学关于收集、保存、使用学位论文的规定，即：学校有权保留并向国家有 关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权海南大学可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文。本人在导师指导下完成的论文成果，知识产权归属海南大学。 保密论文在解密后遵守此规定。 论文作者签名： 日期：加0 年 导师签名：圜 日期：年月 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的学位论文提交 论文作者签名： 日期：加占年月f 7 日 发布，并可按“章程”中规定享受相关权益。回童迨塞 导师签名： 圜 日期：年月日 1 绪论 1 1 研究背景和研究意义 随着互联网等各种信息传播媒介广泛应用与发展，人们同常生活所面对的数据量不 断膨胀，如何高效地获取和管理信息成为信息科学迫切需要解决的问题。在各种信息传 播载体中，文本仍是主要的信息载体。文本自动分类技术作为获取和管理文本信息的有 效方式，近年来受到学者们的广泛关注和研究。 文本自动分类是在给定的类别体系下，让计算机根据文本的内容确定与其相对应的 类别。这罩所指的文本可以是媒体新闻、科技报告、电子邮件、技术专利、网页、书籍 等。文本分类问题关注的文本类别最常见的是文本反映的主题或话题( 如体育、政治、 经济、艺术等) ，也可以是文本的文体风格( 如流派) 或文本反映的主题、话题或文体 风格等与其它事物( 如连垃圾邮件等) 之间的联系( 相关或不相关) 。 文本自动分类已被广泛应用到文本信息处理的各个方面。文本自动分类首先是一种 有效的信息组织方式。将各种不同的文本，按照不同的类别，分门别类的存放，便于管 理和加工。图书馆利用图书分类法来管理所收藏的图书，y 抽0 0 等搜索引擎采用分类的 方法组织管理网页，这些都说明分类处理信息的有效性，采用自动化的文本分类技术同 还可节约大量的人力和物力。文本自动分类同时是一种有效的信息过滤方式。随着互联 网的发展和普及，网络上包含的信息千罗万象，其中不乏垃圾信息和有害信息，如垃圾 邮件、色情网站等，采用文本自动分类技术可以很方便的将这些信息过滤掉，从而避免 这些信息对人们生活产生不利影响。文本自动分类还为信息查询提供了一种有效的途 径。学者们需要了解学术发展动态的信息，商人需要了解市场动态等等。按不同的需求 组织信息并呈现给相关的用户，可以使用户查询信息的方式更加有效。 随着信息技术迅猛发展和广泛应用，文本自动分类技术已与人们的日常生活息息相 关，对文本自动分类技术的研究显得更加必要。 1 2 研究现状 文本自动分类研究始于2 0 世纪5 0 年代末，h p l u h n 首先将词频统计思想用于自 动分类，在该领域进行了开创性的研究。1 9 6 0 年，m a r o n 在j o u r n a lo fa s m 上发表了 有关自动分类的第一篇论文o nr e l e v a n c ep r o b a b i l i s t i ci n d e x i n ga n di n f o r m a t i o n r e t r i e v a l ，其后许多学者在这一领域进行了卓有成效的研究工作。从2 0 世纪6 0 年代 到2 0 世纪8 0 年代末，这期间最有效的文本分类系统一直是由专家人工构建的基于知识 工程技术的分类系统。其典型应用就是卡内基集团为路透社开发的c o n s t r u e 系统，它 由专业人员编写分类规则指导分类，在r e u t e r s 的部分语料库上它的效果非常好，平均 精确率和召回率大约都可达到9 0 ，f 县是在其它的应用领域采用c 0 s t r l e 系统将会消耗 大量的人力和物力。这种自动分类器构造方法的缺点是知识获取瓶颈的存在，它必须要 为领域专家获取的知识和知识工程师的知识表示之间架起桥梁，二者缺一不可。9 0 年 代初期，基于机器学习( m a c h in el e a r n in g ) 的分类技术开始取代基于知识工程的方法成 为文本分类的主流技术。这种方法通过归纳文本集的特征自动创建一个分类器，这些文 本集事先被领域专家人工地分类到类集，分类器可作为一个规则决定文本是否属于某一 类。如果类集被更新或者系统要应用于其它不同的领域，只需要重新构造一个人工分类 文本集合，通过机器学习，自动地构造一个分类器。由于这种分类方法不再完全依赖于 知识工程师和领域专家，节约了大量的专家人力资源，同时加快了分类系统的建立速度。 近年来，学者们结合机器学习方法、人工智能、自然语言处理等相关技术，对文本 自动分类进行了大胆的探讨，研究的问题越来越深入，越来越广泛，已形成了比较系统 化的文本自动分类研究框架。通常将文本自动分类分为四个环节：语料库相关和文本预 处理，特征选择和文本表示，分类器的构建，对新文本的预测。 1 2 1 语料库和文本预处理 文本分类语料库的相关研究主要集中在语料库的构建方面，目的是构建大规模、高 质量的文本分类语料库。其中研究的问题包括：语料信息的抽取和组织，语料的采集和 评估。如刘华f l 】提出了构建大规模标注语料库的标准，王丁1 2 l 等人提出了一种语料库评 估模型等。关于文本分类语料库相关的理论研究还没有成为国内外学者研究的重点。主 要原因是研究文本分类的学者将主要的研究重点放在构建分类模型相关问题上，认为构 建语料库是语言学专家的事情。而语言学专家在语料库方面的研究主要集中在语言学方 面，语言学专家建立的语料库主要是为研究语言相关内容服务的。现在还没有一个标准 的、通用的文本分类语料库。现有的文本分类语料库基本上都是文本分类研究者或某些 组织( 如搜狗实验室，复旦大学) 根据自己的需要建立的，采用人工收集标注的方式。 已建立的中文语料库如复旦大学文本分类语料库、搜狗实验室文本分类语料库。英文语 料库如r e u t e r s 的文本分类语料库、n e w s g r o u p 语料库、i n d u s t r y s e c t o r 语料库、w e b k b 语料库等。有关文本分类语料库的研究应该引起学者们的广泛关注，其是进行文本分类 及相关评测的前提。语料库的工作是整理收集原始语料，文本预处理是对语料的再加工， 去除语料中的噪声，并根据分类的需求将语料转换形式。关于中文文本预处理涉及到的 问题有：分词，编码识别，去噪。分词是一个独立的研究热点，其是中文信息处理的必 不可少的过程，现已形成了比较完善的分词框架和算法集合。分词需要解决的主要问题 包括：交叉歧义和组合歧义的处理，命名实体识别( 人名、地名、机构名等) ，新词发 现。有关分词的相关论述可见参考文献i 孓s 】等。现有的比较成熟的分词系统有海量分词 系统、中科院分词系统、北大分词系统、清华分词系统等。编码识别同分词一样，也是 独立于分类问题的。相关的编码识别算法如：基于内码分饰的编码识别方法，基于编码 非重叠区域的编码识别，基于标点符号的编码识别，基于字频分布的编码识刖，基于 n g r a m 模型的编码识别等等。这些方法被实践证明是有效地，且被己被广泛的采用。有 关编码识别的相关论述可见参考文献1 9 j 。去噪的目的是去除与表达文本主题不相关内容， 避免这些内容对分类算法的影响，多被应用在网页分类中。y i m i n gy a n g i iu j 提出了通过 去掉网页中的噪音内容来提高网页分类质量的方法，j o n a t h a na z d z j a r s k i i j 提出了 基于贝叶斯的文本去噪方法，张志刚l l2 1 等给出了一种基于启发式规则的网页去噪方法。 所有的网页去噪方法都采用“规则+ 统计”的方法进行。 1 2 2 特征选择 文本特征选择方法是文本分类研究的一个热点，其是文本自动分类的关键技术之一， 其相关结论与方法之多令人眼花缭乱，同一方法其各家所得结论也有所不同。产生这种 局面的原因有三方面：一方面特征选择是基于原则指导性质的，特征选择的原则有2 个： 一是所选特征应能反映文本的主题，二是所选特征应具有一定的类别区分能力。这两大 指导性原则给研究者提供了广阔的发挥空间。研究者关注的重点不一样，其采用的方法 不同，所得的特征选择公式就不相同。另一方面在于研究者所选的训练集和测试集不统 一，在不同的测试集下所得的结论往往差异很大。最后一个原因是经特征选择所得的特 征子空间没很好的评价标准，特征子空间优劣都是通过分类器分类精度是否有所提高来 评价的。由于各个分类器采取的分类策略不同，其适用的问题也不同。因此，不能简单 的通过分类精度的提高说明特征选择方法的好坏。常见的特征选择的方法有：文档频率 一逆文档频率( t f i d f ) ，信息增益( i g ) ，互信息( m i ) ，卡方统计( c h i ) ，期望交叉熵 ( e c e ) ，几率比( 0 r ) 等等。新近出现的特征选择方法如：基于关联规则的特征选择方法i l 川， 基于核主成份的特征选择方法【1 4 】，基于粗糙集的特征选择方法1 1 5 l ，基于潜在语义的特征 选择方法，基于最大熵原理的特征选择方法等等1 1 6 j 。各种特征选择方法采取的策略不同， 但其都遵循上述所说的两大原则。 1 2 3 文本分类器 文本分类的另一大核心技术是分类器的构建，分类器通常指某一分类算法。根据算 法依据的数学原理可将分类器划分为2 类：基于统计的文本分类器和基于规则的文本分 类器。常见的基于统计的文本分类器有：类中心分类器，r o c c h i o 分类器，k 一近邻分类 器，朴素贝叶斯分类器，支持向量机分类器，w i n n o w 分类器，神经网络分类器，核方法 分类器等。常见的基于规则的分类器有：基于决策树的分类器，基于粗糙集的分类器， 基于模糊集合的分类器等。关文本分类器的研究主要集中在以下几个方面。一是如何利 用已有的理论建立新的文本分类模型，这方面的研究比较困难，但也有不少结论。如 k a m a ln i g a m l l 7 1 。首次提过了基于最大熵模型的文本分类算法，李荣陆1 1 8 】等人基于中文 对该模型做了相关研究。陈家会、周水庚i 】川等人研究了潜在语义索引技术并用到文本分 类领域。黄海英1 2 0 j 在此基础上提出了基于概念空问的文本分类方法等等。分类器研究的 另一个重点是针对现有分类器的改进。如对k n n 算法运算速度慢的缺点，乔玉龙1 2 l 】等人 结合h a r r 小波变换提出了改进的快速k n n 算法，张国英i z 2 】等人将粒子群算法用于k n n ， 王煜等人提出了一种快速迭代算法1 2 3 1 ，同时还将结合神经网络等设计了另一种快速k 、n 算法弘4 。对于贝叶斯分类算法，针对其假设词语之问相互独立的不合理性，构建了贝叶 斯语义网络模型，将相关度大的词联系起来。这种方法构建的语义网络通常比较复杂， 可能产生错误关联，且计算量较大，为此n i rf r i e d m a n | 2 5 j 等人提出了“t r e ea u g m e n t e d n a t i v eb a y e s 模型( 通常简称为t a n ) ，该模型在构建网络时只考虑一阶关联，实践证 明该方法是有效地，其已成为b a y e s 分类算法中典型代表。类似t a n 算法，王潇1 2 6 l 等人 提出了树桩模型，其与t a n 模型的区别在于构建的树中，分支节点可能是一个词语集合。 支持向量机是最受关注的一种分类算法，因其具有结构风险最小化的优点且其表现出 色。支持向量机最大的问题是其训练速度慢，针对此p 】a t t l 2 7 1 提出了序贯最小优化( s m o ) 来解决这一问题，k e e r t h i l 2 8 j 等人对p l a t t 提出的方法进一步给出了改进，j o e c h i m s f 2 9 】 等人提出了通过改进训练集的选择策略，并利用支持向量机的属性提出了缩减训练集的 假设，从而使算法能较好地处理大规模训练集。支持向量机的另一个研究热点是核函数 的相关研究，常用的核函数有：高斯核函数，多项式核函数等。分类器的另一个研究重 点是多分类器问题，现在已形成两种比较成熟的模型：“词袋法 ，“提升法。两种方 法基本思路都是通过选取多个分类器，每一步只训练一个分类器，通过反馈、迭代优化 分类中的相关数值( 如文档概率，词的类别概率等) 。两者的不同是：“词袋法 的通过 训练集抽样，对不同的分类器抽取不同的训练集样本，训练并反馈。“提升法 是利用 每次训练完后所得分类器的错误分类结果来调整相关数值。“词袋法 由b r e i 帆n 在i 刈 中提出s c h a p i r e 和f r e u n d 在【3 1 0 2 1 中提出。值得一提的是中科院谭松波【3 3 d 叼博士等人 提出了一种“推拉策略 多分类器。该策略源自于“类中心算法 ，利用每一步迭代产 生的错误分类信息调整类中心的位置。实验表明该算法有着和支持向量机基本同样的分 类效果，其训练速度和预测速度远远小于支持向量机。谭还将此策略应用到贝叶斯分类 器和k n n 分类器。 1 3 问题提出 进行文本分类研究，首先必须清楚分类过程中与“类别 相关的若干概念及其这些 概念间存在的关系。与类别相关的“概念包括：类别、类、分类、全体文档集合、类 集合等。这些概念间存在的关系包括：类别与类的关系，类之间的关系，类与全体文档 集合的关系，类集合间的关系等。这些问题是文本分类的基础问题，对分类工作都具有 很强的指导性。如根据类别问的关系可对分类问题进行分类，根据类集合间的关系可以 更清楚的认识分类器错误，通过类集合的几何特性研究提出改进分类器的策略等。这些 基本问题的研究还没有见诸于文本分类的相关文献。本文将对此做尝试性的研究。 对于特征选择已有很多结论，从现有常见特征选择方法采取的策略分析，其都采用 “贪心策略”，即先制定评价指标，每一步只选出一个特征词。贪心策略保证了局部最 优，但不能保证所选特征是全局最优的。因此有必要对全局最优化的特征选择方法作相 关研究。 对于文本的权值计算，已有诸多方法，基本上都是基于词频，文档频率。特征词的 4 权值表示的是词语与文档主题的相关度，词频和文档频率只是体现相关度的2 个因素， 词语本身的属性是其与主题产生相关性的根本原因。词性作为词语的一种本质属性，不 仅能反映语义相关信息，更能反映词语之| h j 的相互联系。同时完整的语义是基于上下文 的，一篇文档的核心词出现的频率可能很低，其在特征选择时可能会被过滤掉，如果在 特征选择的时候基于上下文关系并考虑词性，那么特征选择的结果将更能体现文档的语 义信息。因此，有必要对词性以及词语的上下文关系在文本自动分类中的应用作相关研 究，并可提出一种较为完善的权值计算框架。 关于分类器的改进，“推拉策略 是新近提出的一种有效方法。有必要对“推拉策略 的理论根据和其中可能存在改进进行相关论述。 1 4 本文组织 针对1 3 提出的问题，本文具体组织如下： 第一章对文本分类作综述性的介绍。首先简单介绍研究文本自动分类的背景和意义， 指出研究文本分类的必要性。接着就文本分类的3 个环节的研究现状做简单总结，这3 个环节包括：语料库和文本预处理、特征选择、分类器。在此基础上提出本文的研究问 题。 第二章对文本分类技术的各个方面做较为详细的介绍和总结，包括：文本预处理， 特征选择方法，文本表示，分类算法，多分类器，文本分类评价指标。文本预处理部分 介绍分词、去噪、编码识别3 个问题。特征选择介绍常见的特征选择方法和它们之间的 差异，文本表示总结文本表示模型，分类算法，介绍常见的分类算法和其扩展，并介绍 3 种多分类器策略，评价指标部分介绍常用的评价指标，并讨论其优缺点。 第三章对文本分类中的“类别相关概念作相关论述。包括：类别、类、分类、全 体文档集合、类集合等，论述这些概念内部及之间存在的关系，并由类集合间的关系讨 论分类器的错误敏感性，在此基础上，基于常见分类算法，对这些概念进一步分析，并 引出分类器重要点结论。基于重要点，讨论“推拉策略，并提出修正。 第四章首先基于词语与文本主题的相关性分析，讨论了词性和词语上下文关系对词 语权值的影响，提出词语权值的计算框架。在此基础上提出两种全局最优化特征选择模 型，并分析模型给出具体算法。 第五章构建文本分类系统，对常用特征选择方法和本文提出的特征选择方法、“推拉 策略”的类中心分类算法进行相关实验 第六章总结全文，指出文章的不足和需要继续研究的问题。 2 文本分类相关技术 2 1 文本分类流程 文本自动分类可以描述为：在给定的分类体系下，根据文档的内容让计算机自动地确 定与文档对应的类别。从数学角度来看，文档分类过程是一个映射的过程，将未知类别 的文档映射到已有的类别体系中。该映射可以是一一映射，也可以是一对多的映射。用 数学公式表示如下： 厂：d 岭c( 2 1 ) 其中，d = 吐，吐，d 。) 为待分类的文档集合，z ( 扛1 ，2 ，刀) 表示文档集合d 中的一篇 文档，一为d 中的文档总数。c = q ，q ，) 为分类体系中的类别集合，c ，( j r = l ，2 ，肌) 为分类体系中某一确定的类别，m 为分类体系中的类别总数，为将文档关联到类别的 映射。该映射是在给定训练集的情况下，根据训练集中各个类别文档问的关系训练得到。 在实际操作中通常表现为建立数学模型，通过训练确定模型中的相关参数，得到判别函 数厂。整个过程如图2 1 所示。 待分文档集 类别集合 图2 i 文本分类示意 上述的过程转化为具体的实际操作流程，可分解成五个步骤：训练集的采集与标注， 文本的预处理，特征选择，文本表示，分类器训练和预测。图2 2 表示了整个流程。整 个流程可描述如下： ( 1 ) 定义类别集合c = q ，c ：，c 。 ( m 为类别总数) ，构建语料库 ( 2 ) 对语料库进行预处理 ( 3 ) 进行特征选择 ( 4 ) 根据采取的分类器对利用特征集合表示文档 ( 5 ) 对所选分类器进行训练，并在测试集上测试，调整分类器相天参数 6 ( 6 ) 对新文档进行预测 训练集测试集 上0 文档预处理 上； 特征选择 卜 文本表示 j0 分类器训练 1 - 1 分类器测试 1 1i 上 对朱知文档预测 图2 2 分类流程图 2 2 文本预处理 文本预处理是对语料再加工，目的是将文档规范化，降低文档中的噪声，便于进行 特征选择。训练集基本都是由人工整理的，因其来源不同，文本的组织形式可能存在差 异，其可能包含较大的噪声，对于中文，文本的编码方式也可能不尽相同，中文还需要 分词。因此，根据实际情况，需要对语料进行预处理。通常的预处理可能包含以下几个 方面：编码识别，去噪和文本抽取，分词。这部分工作对训练集和预测集是相同的。文 本预处理涉及到的技术基本上都是中文信息处理中的通用技术，本文只给出简单的概 述。 2 2 1 编码识别 在中文网页分类中都会涉及到编码识别问题，这是由网页编码不规范造成的。现有 的中文编码方式有：u t f 一8 ，g b 2 3 1 2 ，g b k ，g b l 3 0 8 0 ，b i 9 5 ，u t f 1 6 等，其中g b l 3 0 8 0 是新的国家标准。由于历史原因，现在上述各种编码形式共存。其中b i 9 5 为台湾繁体 汉字的编码方式。有关汉字编码相关内容请参考全国信息技术标准化委员会网站1 3 7 1 。比 较成熟的编码识别方式有四种：基于内码分布的识别算法，基于非重叠区的识别算法， 基于字频分布的识别算法，基于n g r a m 模型的识别算法。基于内码分布的编码识别算 法主要针对g b 2 3 1 2 和b i 9 5 ，其思想是将文本的每个字节视为无符号整数，计算所有汉 字的第一个字节的内码平均值，该平均值于1 8 4 比较1 3 引，如果大于1 8 4 则判断为g b 2 3 1 2 编码，否则为b i9 5 编码。该算法在速度和准确性方面是可以接受的。基于编码非重叠 区的彭 别算法，主要是利用各编码集合不完全重卺，利用非重叠区字符的编码来识别， 该算法速度快，但非重叠区的字符数量有限，导致算法的容错性能不好。基于字频分稚 7 的识别算法利用汉字字符使用频率差异较大的特点达到识别的目的。大量的统计显示 1 0 0 0 个最常用汉字字符的使用频率占所有汉字使用频率的9 0 以上，2 5 0 0 个常用汉字 的使用频率占9 7 以上。先利用某种编码方式解码，再统计常用汉字频率的总频率，总 频率大的编码方式确认为该文本的编码方式。基于n g r a m 模型的识别算法，将文本视 为一个n 阶m a r k o v 过程，文本在某种编码下的生成概率越大，其为该编码方式的概率 就越大，u n i g r a m 是该模型的简化实例，其实质是对字频分布方法的改进。李继锋1 3 9 l 等 人提出该模型，并利用u n i g r a m 做了相关实验，实验表明该算法在速度和精确度方面都 是令人满意的。 2 2 2 去噪 在信号处理领域，噪声是对有效信号产生干扰的信号，其降低信号质量，给信号分 析带来困难。在文本分类中也会遇到同样的问题，如网页分类。通常网页中包含大量与 表达主题不相关的内容，如广告，导航栏等。这些信息同样会对分类效果产生影响。现 在文本分类相关的去噪研究主要集中在网页去噪方面。 网页去噪主要采取对标签评估的方法，基本思路是建立网页的d o m 树，根据树中每 个节点提供的信息和标签的种类对标签进行评估，根据评估结果判断该标签是否为网页 噪声。文献1 2 哪2 j 对网页去噪作了相关论述。 2 2 3 分词 对于中文信息处理，分词是往往是不可缺少的步骤。中文分词就是将输入的汉字句 子切分成一个一个的词语串。分词也是中文信息处理领域一个研究热点，其研究成果众 多。中文分词需要解决三大问题：歧义的识别，命名实体识别，新词发现。其中分词歧 义分为两种：交叉歧义和组合歧义。命名实体识别包括：人名识别，地名识别，机构名 识别。现有的分词算法根据其采用的方法可以归纳为3 类：基于规则的分词算法，基 于统计的分词算法，基于“规则+ 统计”的分词算法。 基于规则的分词算法先整理分词词典，词典包含尽可能多的词语，切分时根据匹配 规则选取字串，并在词典中匹配字串。如果匹配成功，则将该字串切分为词语，否则， 根据规则重新选取字串匹配。常见的匹配算法有：正向最大匹配算法，逆向最大匹配算 法，双向最大匹配算法，最小切分算法等。这些都是早期中文信息处理的常用算法。基 于规则的分词算法时间复杂度低，有一定的歧义识别能力，但其对命名实体能力较差， 不能发现新词，对词典的依赖很强。 随着统计自然语言的发展，出现了基于统计的分词算法。基于统计的分词算法主要 利用词语的统计信息基于语言学模型进行分词。常见的基于统计的分词算法如：基于最 大概率的分词算法，基于n g r a m 模型的分词算法，基于隐马尔科夫的分词算法等。基 于统计的分词算法考虑了词语之间的统计语义信息。具有一定的命名实体识别和新词发 现能力，但时间复杂度也高。现在通常采用将两者结合的策略设计分词算法，如中科院 设计的基于层叠隐马尔科夫分词算法，基于最大熵的分词算法等。这些算法将问题分解， 采用机器学习相关理论，针对每个问题学习采用不同的模型，有针对性逐个解决。 2 3 特征选择 通过预处理阶段得到规范的文本语料，但文本本身不能直接用于分类。从类别概念 出发，类别是具有共同属性的事物的集合，这螳属性是事物属于某个类的特征。分类是 以类别特征为依据的。因此，分类之前需要确定每个类别的特征。文本通常反映某一主 题或概念，类别是对这些概念的抽象和总结。因此，确定类别的特征首先需要确定文本 的特征，再从文本特征及其相互联系确定类别特征。文本的特征根据特征粒度的大小有： 字，词，句，篇，章。显然篇，章作为文本特征在实际操作中是比较困难的。其表述的 语义信息依赖于底层的字，词，旬。对字，词，句的研究表明，词作为文本特征是比较 适合的，词不仅具有表达完整的语义信息的能力，而且其分布也不是稀疏的，有较好的 统计特性。因此，现在基本都是以词作为文本的特征。文本的主题或表述的概念是通过 词语之间的相互联系反映的，因此，文本分类中类别的特征实质是词语及其之间的相互 联系。通常一篇文本中包含的词语可能很多，不同的词语与其所在的文本表达的主题或 概念之间联系的紧密程度是不同的。实词与文本主题之间的联系要强于虚词。因为实词 能表达某一具体概念或概念之间的相互联系，而虚词通常是用来支撑句子结构的。在一 篇文档中虚词的使用频率通常要比实词高，而且某些虚词会在所有或绝大多数文本中频 繁出现。这些词不能很好的体现类别之间的差异，反而影响分类，因此不应该作为进行 分类的特征。特征选择应该选取那些具有较强类别区分能力的词，这种区分能力往往是 通过：词语本身的语义属性，词语的统计特性，词语之间的相互联系体现的。 进行特征选择的另一个原因是：如果将去掉停用词后的所有词语作为特征项，则在 利用分类算法分类时的计算量将会很大，而且将所有词语作为特征项集合，各个特征之 间的联系将会很复杂，也有可能降低分类效果。 常用的特征选择方法有：文档频率( d f ) ，信息增益( i g ) ，z 2 统计量( c h i ) ，互 信息( m i ) ，优势率( o r ) 。 2 3 1 文档频率 一个特征的文档频率( d o c u m e n tf r e q u e n c y ，简记为d f ) 是指在文档集中含有该特征 的文档数目。采用d f 进行特征选择选择是基于如下假设：d f 值低于某个阈值的词条是 低频词，它们不含或含有较少的类别信息。将这样的词条从原始特征空间中除去，降低 了特征空间的维数以及特征项之问联系的复杂性。文档频率是最简单的特征抽取技术， 由于其相对于训练语料规模具有线性的计算复杂度，它能够很容易被用于大规模语料统 计。但其假设存在不合王里的地方，即某些虚词的d f 可能异常的高，而其类别区分能力 却很差，因此，通常在使用d f 之前需要将这些类别区分能力差的词做成停用词表，在 分词时过滤掉或特征选择时不考虑。 9 2 2 2 信息增益 信息增益( 1 n f o r m a ti o ng a i n ，简记为i g ) 在机器学习领域被广泛使用。其从信息论 中互信息( m u t u a li n f o r m a t i o n ) 的概念出发，用于度量已知某一特征项的分布时，类 别系统不确定性的减少。该值越大说明其在各个类中的分布越不均匀，其类别表示能力 越强。反之，说明其类别区分能力差。某一特征项，的信息增益定义如下： 佑( ，) = 一p ( q ) l o g 尸( q ) + p ( ，) p ( q o g p ( ql ，) + p ( f ) p ( qi 丁) l o g p ( ei7 - ) ( 2 1 ) 其中，为某一特征词，类别集合记为c = c l ，巳，气) ，朋为类别总数，c ( 1 f m ) 为 类别集合中的某一类，p ( q ) 表示类别q 出现的概率。在计算时用训练集中属于q 类的文 档数与训练集中包含的总文档数比值近似。p ( f ) 表示包含特征词，的文档出现的概率， 用训练集中包含特征词，的文档数与总文档数的比值近似。p ( ql ，) 是包含特征词，的文 档属于q 类的概率，用q 类中包含r 的文档总数与训练集中包含特征词r 的文档总数比值 近似。p ( - ) 表示不包含特征词，的文档出现的概率，有p ( f ) = 1 - p ( f ) 。p ( ql 乃表示不 包含特征词f 的文档属于q 类的概率，用q 类中不包含，的文档总数与训练集中不包含， 的文档总数比值近似。若记 h ( c ) = 一p ( q ) l o g p ( q ) j 暑l ( 2 2 ) i开，一 日( c l ，) = 一p ( f ) p ( qf f ) l o g p ( qi ，) 一p ( 乃p ( qi - ) l o g p ( qi d ( 2 3 ) 则按照信息论的解释，日( c ) 表示训练集中文档类别分布的不确定性，( c ir ) 表示已知 特征项f 概率分布的情况下，训练集中文档类别分布的不确定性。则有 佑( ，) = h ( c ) 一日( c l ，)( 2 4 ) 将上是重新记为 ( c ，) = h ( c ) 一日( cl ，) ( 2 5 ) 则( 2 5 ) 为随机变量c 与随即变量，的互信息，其表示已知，的情况下，随机变量c 不 确定性的减少，即，对于类别随机变量c 不确定性的消除。 2 2 3 互信息 互信息( m u t u a li n f o r m a t jo n ，简记为m i ) 在统计语吉模型中被广泛采用。类别e 与 l o 特征词，之间的互信息定义如下： 加砧刮。g 篇刮。g 等 亿6 ) 其表示特征项，与类别q 的关联程度。j ( ，q ) 越大说明特征项，与类别q 的关联越紧密。 如果用彳表示包含特征词，且属于类别e 的文档频数，b 为包含特征词，但是不属于q 的 文档频数，c 表示属于e 但是不包含特征词，的文档频数，表示语料中文档总数，则 互信息公式可近似如下： 彳 坤，q ) = l o g ( 2 7 ) ( 彳+ b ) ( 彳+ c ) 求，( ，q ) 的期望，则特征词f 的类别互信息如下： m c ) = 喜删( f ，c ：i ) = 薯俐。g 等 ( 2 8 ) ( 2 8 ) 的表现形式在信息论中被称为相对熵( r e l a t i v ee n t r o p y ) 或“k u l l b a c k - l e i b l e r 距离”，严格意义上它不符合距离定义( 不满足对称性和三角不等式) 。 2 2 4 卡方统计 z 2 统计方法度量特征词f 和文档类别q 之间的相关程度，并假设f 和q 之间符合具有 一阶自由度的z 2 分布。特征词f 对于某类的z 2 统计值越高，它与该类之间的相关性越大， 携带的类别信息也较多。令，彳，b ，c 的含义同上述2 2 3 中描述的相同，d 是既不 属于c 也不包含特征词f 的文档频数。若彳d 0 和匆，针对每个类别，对于训练集中的每个样本d ，计算 ，( z ) = w z + 6 t ，当，( 谚) 9 ，如果z 属于e 类，则g ( w ) = w ，表示分类准确，原系数 保持不变，如果z 不属于c 类，则g ( w ) = 口w ( 0 口 9 ，则判断该文本属于类别q 。w i n n o w 分类器 有很多变形，如b a l a n c ew in n o w l 4 9 l ，r e g u l a rw i n n o w 【5 0 1 等。其主要区别是z ( 工) 的形式 和更新函数g ( w ) 不同。w i n n o w 方法对于特征问相关度很小的分类问题有很高的使用价 值，其方法简单，训练和预测速度都很快。 其它的分类器还有很多，如基于神经网络分类器，基于核方法的分类器，基于决策 树的分类器，基于粗糙集的分类器等。每种分类器都有很多变形与改进。很多实验表明， 最近邻分类器和支持向量机分类器在多类问题中的效果比其它分类器好，贝叶斯分类 器，w i n n o w 分类器，r o c c h i o 分类器在两类问题中应用广泛。 2 6 多分类器 为了提高分类器的分类效果，考虑到构建分类器构建时涉及到的3 个关键因素：训 练文本，特征权重，分类器，人们提过了各种整体改进策略，其中一种策略是在改进的 过程中涉及到多个分类器，称为多分类器策略。其涉及到的多个分类器可以是同一类型 的分类器，也可以是不同类型的分类器，通常都被称为基分类器。其理论依据为优化理 论中的“没有免费的午餐定理 。典型的多分类器策略有3 种：“b a g i n g 策略 ( b a g i n g s t r a t e g y ) ，“b 0 0 s t i n g 策略，( b o o s t i n gs t r a t e