（计算机软件与理论专业论文）中文文本分类算法的研究与实现.pdf

摘要 文本分类最初是应文本信息检索的要求出现的，但是随着文本数据的激增， 传统的研究方法已经不适合大规模文本分类，文本数据挖掘应运而生。作为文本 数据挖掘的一个重要功能，文本分类技术日益成为研究热点。 文本分类目的是对文本集有序组织，便于文本信息高效管理，为人的决策提 供支持。但是传统的人工分类的做法存在许多弊端，不仅是耗费大量人力、物力 和精力，而且受人为因素影响较大，分类结果一致性不高。与之相比，文本自动 分类具有快速、高效的特点，且分类准确率较高。 本文主要研究中文文本分类算法及其实现，采用基于关联分析和聚类分析两 种方法，设计和开发了中文文本分类系统a c t c ，实现中文文本分类功能，在理 论和实践上论证两种方法的可行性和正确性。 系统用向量空间模型表示中文文本，采用基于统计的文本分类模型。本文从 理论和应用角度对现有文本分类算法进行了较为深入的研究，提出一种新的关联 分类算法频繁模式增长p f pg r o w t h 算法，并基于信息粒度原理将聚类算法用于 中文文本分类。 a c t c 系统能够快速高效对大规模中文文本分类，具有良好的自适应性的和 可扩充性，而且为研究文本分类算法提供了个的实验平台。 关键词：文本数据挖掘文本分类关联分析聚类分析 a b s t r a c t t e x t c a t e g o r i z a t i o na p p e a r si n i t i a l l y f o rt e x ti n f o r m a t i o nr e t r i e v a l s y s t e m ； h o w e v e rt e x td a t ai n c r e a s e ss of a s tt h a tt r a d i t i o n a lr e s e a r c hm e t h o d sh a v e b e e n i m p r o p e rf o rl a r g e s c a l et e x tc a t e g o r i z a t i o n s ot e x td a t am i n i n ge m e r g e s ，a n dt e x t c a t e g o r i z a t i o nb e c o m e s m o r ea n dm o r e i m p o n a n t a sa m a j o r r e s e a r c hf i e l do f i t t h e p u r p o s eo f t e x tc a t e g o r i z a t i o ni st oo r g a n i z et e x tb yo r d e r , s oa st om a n a g e t e x ti n f o r m a t i o n e f f i c i e n t l y a n d s u p p o r t d e c i s i o n so fh u m a n b e i n g h o w e v e r c a t e g o r i z a t i o nb yh a n dn o to n l yc o n s u m e sp l e n t yo fm a n p o w e r ，m a t e r i a lr e s o u r c e s a n de n e r g y , b u ta l s om a k e sc a t e g o r i z a t i o n a c c u r a c yi n c o n s i s t e n t c o m p a r e dw i t h c a t e g o r i z a t i o nb yh a n d ，a u t o m a t i ct e x tc a t e g o r i z a t i o nc l a s s i f i e st e x t s f a s t e ra n di t s c a t e g o r i z a t i o na c c u r a c y r a t e sh i g h e r t h i s d i s q u i s i t i o n f o c u s e so nr e s e a r c ha n d i m p l e m e n t a t i o n o fc h i n e s et e x t c a t e g o r i z a t i o na l g o r i t h m s t oc l a s s i f y c h i n e s et e x t s ，a u t o m a t i cc h i n e s et e x t c a t e g o r i z a t i o ns y s t e ma c t c i sd e v e l o p e dw i t ht w om e t h o d s ：a s s o c i a t i o na n a l y s i sa n d c l u s t e r i n ga n a l y s i st h a th a v eb e e np r o v e dc o r r e c ta n df e a s i b l ei nb o t ht h e o r ya n d p r a c t i c e a c t cu s e sv e c t o r s p a c e m o d e lt o e x p r e s s c h i n e s et e x ta n d a d o p t s t e x t c l a s s i f i c a t i o nm o d e l sb a s e do ns t a t i s t i c s t h i sp a p e ro f f e r sat h o r o u i 曲r e s e a r c hf o r r e s e a r c ha n di m p l e m e n t a t i o no fe x i s t i n gt e x t c a t e g o r i z a t i o na l g o r i t h m s a n d p u t s f o r w a r dap r o j e c t f r e q u e n tp a t t e r ng r o w t hp f p g r o w t ha l g o r i t h m t h a ti sn e wi n a s s o c i a t i o nc l a s s i f i c a t i o nf i e l d a c l u s t e r i n ga l g o r i t h m b a s e do l li n f o r m a t i o n g r a n u l a r i t yt h e o r y i sa l s op r a c t i c e di na c t c a c t co f f e r sa ne x p e r i m e n tp l a t f o r mo fr e s e a r c hf o rc a t e g o r i z a t i o na l g o r i t h m s a n dc l a s s i f i e sc h i n e s et e x t sq u i c k l ya n d e f f c i e n t l y i th a sg o o da d a p t a b i l i t ya n d i se a s y t oe x p a n d k e yw o r d s ：t e x td a t am i n i n g ，t e x tc a t e g o r i z a t i o n ，a s s o c i a t i o na n a l y s i s ，c l u s t e r i n g a n a l y s i s n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 笺鱼盘笙日期 关于论文使用授权的说明 2 争厂i 5 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：i 垒! 叁兰 导师签名 碑嗍坐业拶 第l 章绪论 i 第1 章绪论 1 1 文本自动分类研究的背景和意义 分类最初是应信息检索( i n f o r m a t i o nr e t r i e v a l ，简称i r ) 系统的要求而 出现的，也是数据挖掘应用领域的重要技术之- - ( ”。随着全球计算机与通讯技术 的飞速发展、互联网的普及与应用，信息爆炸的现实使人们越来越注重对自动分 类的研究，文本自动分类及其相关技术的研究也日益成为一项研究热点。 信息检索系统必须操纵大量的文本数据，其文本信息库可能相当庞大。如何 在海量文本信息中获取潜在的、有价值的知识，模型或规则? 这就需要引入文本 数据挖掘概念。数据挖掘是从大量的文本数据中提取出事先未知的、可理解的、 可应用的信息和知识的过程 ”1 。文本数据挖掘是以文本数据为特定挖掘对象的数 据挖掘，主要提供文本关联分析、文本分类和文本总结三种功能模式。文本数据 挖掘的原则和目标是根据决策目标，分析海量文本数据、确立分析方法、构建数 学模型、定制应用系统、提供决策支持【3 8 】。 网络信息的激增一方面增加了对于快速、自动分类的迫切要求，另一方面为 基于机器学习的文本分类方法准各了丰富的资源。 文本自动分类系统的目的就是对文本集进行有序组织，把相似、相关的文本 组织在一起。它作为知识的组织工具，为信息检索提供了更高效能搜索策略积更 准确地查询结果。其中，高效性来自于用户可以首先准确查询的可能性，以减少 需要进一步匹配的文本数量。有效性在于相似的文本很可能与相同的查询有关。 这样，检索的查全率和准确率都得到了提高。 传统的人工分类的做法存在许多弊端，不仅是耗费大量入力、物力和精力， 而且存在分类结果一致性不高的问题。甚至同一个人，在不同时间作分类也可能 存在不同的结果。 采用文本分类技术建立起的文本自动分类系统，相对人工分类，具有以下特 点： 1 自动分类的效率将是人工分类的百倍甚至于倍，从而大量的节约人 力消耗。 北京工业大学工学硕士论文 2 较高的准确度。消除了人为错误产生的可能。 3 良好的自适应性。可快速适应文本的更新及类别设置的变化，适应 不同环境及需求。 4 可扩充性。文本分类系统可为研究多种文本分类算法提供实验平台， 促进文本分类实用化和不断扩充。 1 2 问题的描述 文本自动分类是指计算机根据文本的内容，将其自动归到一个或者几个类别 中去。从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映 射到已有的类别中，该映射可以是一一映射，也可以是一对多的映射，因为通常 一篇文本可以同多个类别相关联。用数学公式表示如下： ，：4 - - - b其中，4 为待分类的文本集合，b 为分类体系中的类别集合 文本分类的映射规则是系统根据已经掌握的每类若干样本的数据信息，总结 出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据总结 出的判别规则，确定文本相关的类别。 自动分类的一般做法是，根据文本数据集的特点构造一个分类器，利用分类 器对未知类别的文本赋予类别。构造分类器的过程一般分为训练和测试两个步 骤。在训练阶段，分析训练数据集的特点，为每一个类别产生一个相应数据集的 准确描述或者模型。在测试阶段，利用类别的描述或者模型对测试集合进行分类， 测试其分类的准确度。一般来说，测试阶段的代价远远低于训练阶段。 文本数据的来源多种多样，可以是报告、单据、新闻、邮件等。文本的类别 和数量可以是预订好的，这需要相关专家知识；也可以是不确定的，要经过文本 的白组织、聚类后才能得到。需要预先定义类别体系的文本分类为有指导的学习 ( s u p e r v i s e dl e a r n i n g ) 的分类，也称文本自动分类：类别体系不确定的文本 分类为无指导的( u n s u p e r v i s e dl e a r n i n g ) 的分类，也称文本自动聚类 ( c l u s t e r i n g ) 【2 8 】。自动聚类系统不需要训练文本，划分出的文本类别也是不确 定的。 本文研究有指导和无指导两种学习方式的中文文本分类。 第1 章绪论 1 3 国内外文本自动分类研究动态 1 3 1文本自动分类在国内外研究现状 国外对于文本自动分类的研究开始较早，5 0 年代末，h p l u h n 在这一领域 进行了开创性的研究，提出了词频统计思想用于自动分类。1 9 6 0 年，m a r o n 发表 了关于自动分类的第一篇论文。随后众多学者在这一领域进行了卓有成效的研究 工作，到目前为止，国外的自动分类研究已经从最初的可行性基础研究经历的实 验性研究进入到了实用阶段，并在邮件分类、电子会议、信息过滤方面取得了比 较广泛的应用，其中比较成功的例子有麻省理工学院( m i t ) 为白宫开发的邮件 分类系统、卡内基集团为路透社开发的c o n s t r u e 系统等。 国内对于文本自动分类的研究起步比较晚，1 9 8 1 年，侯汉清教授对于计算 机在文本分类工作中的应用作了探讨，并介绍了国外计算机管理分类表、计算机 分类检索、计算机自动分类、计算机编制分类表等方面的概况。此后，我国陆续 研究出一批计算机辅助分类系统和自动分类系统。例如，广东省中山图书馆的莫 少强开发的计算机辅助图书分类系统( c - a b c ) 、清华大学吴军研制的自动分类系 统、山西大学刘开瑛等人开发的金融自动分类系统、东北大学图书馆的图书馆分 类专家系统，上海交通大学王永成等研制的基于神经网络优化算法的中文文本自 动分类系统。近期研究中比较突出的是中科院的中文文本智多星分类器，它采用 多种分类方法。虽然中英文之间存在较大差异，无法直接参照国外的研究成果， 但是，随着中文信息处理技术特别是中文自动分词技术的日渐成熟，以此为基础 的中文文本分类技术的研究得到了飞速发展，在短短2 0 多年中完成了从可行性 探索到实用化阶段的转变。 1 3 2 文本自动分类研究技术现状 根据分类知识的获取方法不同，可将文本分类系统划分为两种类型：一是基 于知识工程的分类系统，一个基于机器学习分类系统。 基于知识工程的方法主要依赖语言学知识，一般由知识库和推理机两大基础 部分组成。知识库储存了从专家那里获得的关于某领域的专门知识，推理机具有 北京工业大学工学硕士论文 推理的能力，即根据知识推导出结论，而不仅仅是简单搜索现成的答案。由于需 要由知识工程师手工编制大量的推理规则作为分类知识，实现相当复杂，因此开 发费用相当昂贵。一个典型例子是卡内基集团为路透社开发的c o n s t r u e 系统。 该系统的开发工作量达到了1 0 个人年。由此可见，知识工程的方法不适用较为 复杂的系统。 基于机器学习方法，研究从观测样本出发，寻找规律( 即利用一些做好标识 的训练数据自动地构造分类器) ，利用这些对未来样本进行预测。现有机器学习 的重要理论基础之一是统计学。传统统计学研究的是样本数目趋于无穷大时的渐 近理论，现有学习方法也多是基于大数定律的结论。 一般情况下，用户对分类要求的准确程度在9 5 以上，但是因为分类词表和 分词算法的不足、分类法的不足、分类算法的不足以及知识库的规模不够大等原 因，目前的自动分类系统的准确率主要在8 0 左右，只有限制在一定的范围内， 这些系统才能取得相对好一些的效果，通用的、能够满足大规模商品化应用要求 的系统还需要进一步的研究。 1 4 课题来源和主要研究内容 本课题来源于国家8 6 3 资助项目多源空间数据挖掘技术，中文文本分类系统 属于其予课题文本数据挖掘。各级政府政务活动中按照行政规定，以中文文本的 形式，上报当地社会、经济活动，包括发生各种自然灾害等方面的报告。为了及 时整理这些报告文本，需要研制中文文本分类系统，对报告文本加以分类。 本文主要研究中文文本分类算法及其实现，采用基于关联分析和聚类分析两 种方法实现中文文本分类功能，并在理论和实践上论证两种算法的可行性和正确 眭。 1 5 本文组织结构 第一章是绪论部分，主要介绍了什么是文本分类、文本分类研究的产生背景、 意义以及国内外相关研究成果，并明确课题来源和主要研究内容。 第二章介绍常见文本分类技术，包括基于统计的分类模型、文本的向量空间 模型( v s m ) 表示、文本预处理、目前常用文本分类算法和文本分类的评估标准。 4 第1 苹绪论 第三章是中文文本分类系统a c t c 的总体设计部分。首先从系统需求角度描 述系统结构和处理流程。其次，介绍a c t c 系统两个主要模块训练模块和分类模 块如何设计。 第四章是基于关联分析的中文文本分类算法的设计和实现部分。本章首先介 绍了什么是关联规则和关联分析在文本分类中的应用：其次，分析目前最常用的 两种关联分析算法一a p r i o r i 算法和基于f p j t e e 的f p _ g r o w t h 算法的性能， 重点介绍f p _ g r o w t h 算法的一个改进算法投影频繁模式增长算法p f p _ g r o w t h 算 法，以算法及如何应用于中文本本分类。 第五章是基于聚类分析的中文文本分类算法的设计和实现部分。本章首先介 绍了什么是聚类分析和聚类分析在文本分类中的应用：其次，分析目前最常用的 两种聚类分析法系统聚类法和动态聚类法的特点、性能。再次，引入信息粒 度原理，在此基础上给出本文所采用的聚类分类算法基于粒度原理的聚类分 类算法。最后，结合文本分类特点将算法应用于中文文本分类。 第六章是系统性能分析。给出本系统开发测试环境和数据集，分析本系统的 性能，提出进一步改善系统性能的可行性措施。 结论部分总结了分类算法研究的可行性和正确性，对未来中文文本分类研究 提出展望。 1 6 本章小结 本章主要介绍文本分类研究的产生背景、意义，研究国内外相关研究成果， 明确课题来源和主要研究内容，并给出论文全文的组织结构。 北京工业大学工学硕士论文 第2 章中文文本分类技术研究 本文研究的是基于统计的中文文本自动分类，其研究对象是中文文本，由于 中西文之间存在差异，所以面向中文的文本自动分类既有与西文文本分类的共同 之处，又具有其自身特点。 中文文本分类需要解决的如下几个问题：中文文本如何表示、分词处理、文 本的特征选择和特征抽取、如何选取分类模型、分类模型如何评估。 2 1 基于统计的分类模型 近期的研究中，较为常用的研究方法是采用基于统计的方法抽取关键词( 文 本特征) ，运用信息检索中的计算模型进行特征加权，采用机器学习的算法对类 别学习。 基于统计的分类方法具有如下特点：忽略文本的语言学结构：把文本作 为特征项集合对待；利用加权特征项构成向量作为文本表示：根据词频信息 对文本特征进行加权。 统计方法因其相对简单实现机制，以及在实际环境中所表现出来的良好性 能，而为大多数文本分类系统所采用。利用统计方法实现文本分类速度快、实现 简单，而且分类准确度也比较高，可以满足一般的应用要求。因此，本系统采用 基于统计的分类模型。 2 2 文本的向量空间模型( v s m ) 表示 为了使计算机能够真正处理文本特征，必须对文本特征进行特征加权，将文 本表示成计算机可以处理的数学向量。目前在信息处理方面有布尔模型( b o o l e a n m o d e l ) 、向量空间模型( v e c t o rs p a c e m o d e l ) 、概念模型( p r o b a b i l i s t i cm o d e l ) 等。这些模型从不同的角度出发，是用不同的方法处理特征加权、类别学习和相 似计算等问题。本节主要介绍文本的向量空间模型( v s m ) 表示。 6 第2 章中文文本分类技术研究 2 2 1 向量空间模型的基本概念和特点 向量空间模型( v e c t o rs p a c em o d e l ，简称v s m ) 旺6 1 是现在得到最广泛应用 的基于统计的模型。它由美国的g s a l t o n 等人在2 0 世纪6 0 年代提出。向量空 间模型的基本思想是以向量表示文本。 假设用户目标为i ，未知文本为j ，两者的相似程度可用向量之间的夹角来 度量。夹角越小说明相似度越高。相似度计算公式如下： k = l fm m 、f ( 孵) ( 吆) y 一jk = l 向量空间模型把文本简化成以项的为分量的向量表示，把分类过程简化称为 空间向量的运算，使得问题的复杂性大大降低。此外，向量空间模型对项的权重 评价、相似度计算都没有统一的规定，只是供一个理论框架，可以使用不同的权 重评价函数和相似度的计算方法，使得该模型有广泛的适应性 3 2 】。 2 2 2 特征项的选择及权重计算 一般可以选择字、词或词组作为特征项。由于一般“词”能表达完整的语义 对象，有实验结果表明。“，选取词作为特征项要优于字和词组，因此在文本处理 中通常选用“词”作为文本特征项，将词作为向量的维数来表示文本。 最初的向量表示完全是0 、1 形式，即如果文本中出现了该词，那么文本向 量的该维为1 ，否则为0 。这种方法无法体现这个词在文本中的作用程度，所以 逐渐0 、1 被更精确的词频代替。 词频分为绝对词频和相对词频。绝对词频使用词在文本中出现的频率表示文 本，相对词频为归一化的词频，其计算方法主要运用t f - i d f 公式。目前存在多 种t f i d f 公式，我们在系统中采用了一种比较普遍的t f i d f 公式： 即 另2 厦t f 蒸( t , d ) 萧xl o g ( 菰n n , i + 0 0 丽1 )、。于i 矿o ，d ) l o g ( n ，+ o 0 1 ) j 北京工业大学工学硕士论文 其中，w ( t ，罚为词t 在文本，中的权重，而矿( f ，萄为词t 在文本孑 中的词频，n 为训练文本的总数，n ，为训练文本集中出现t 的文本数，分母为 归一化因子。 文本经过分词程序分词后，首先去除停用词，合并数字和人名等词汇，然后 统计词频，最终表示为上面描述的向量。 2 3 文本预处理 2 3 1 文本半结构化 文本数据与常见的结构化关系数据不同，它是非结构化的，没有属性值对 的结构，称为无结构或者半结构化数据。对于非结构化的文本数据进行挖掘，目 前有两种处理途径：一是采用全新的算法，直接对非结构化文本数据进行挖掘； 二是将非结构化文本数据进行转化，将其转化为结构化文本数据，再进行挖掘。 由于直接构造新算法难度较大，而且开发造价高，实现难度较大，所以目前通常 采用人工处理的方法，把非结构化的文本数据转化为结构化的文本数据。 2 3 2 自动分词 自动分词是针对与中文的一种自然语言处理技术。西方语言体系中，句子中 各个词汇之间有固定的空格作为分隔，计算机处理时可以非常容易地从文本中识 别出一个一个的单词。而在汉语体系中，书写以句子为单位，句间用标点隔开， 句内字词则是连续排列的，之间没有任何分隔。因此，如果要对中文文本进行分 类、检索等基于词的处理，需要首先对中文文本进行词条切分处理( 简称分词) ， 才能正确识别每个词。 中文文本的分词处理就是指在中文文本中连续的能够代表语义单元的词或 者n 一元词条间加入分隔符，将中文文本的连续字节流形式转化为离散单词流形 式的过程。 自动分词技术是各种中文信息处理技术的基础，也是中西文研究文本自动分 类的主要差别所在，中文文本分类要在自动分词的基础上进行，对中文文本进行 第2 章中文文本分类技术研究 分词的过程也是文本特征集的确定过程。 2 3 3 特征选择和提取 特征选择和特征抽取可咀降低特征空间的维数，从而达到降低计算复杂度 和提高分类准确率的目的，并为以后的分类器设计提供参数。 2 2 3 1 特征选择 文本特征选择是文本分类的首要任务和关键问题f 2 】。简单的说，特征选择是 从一组特征中选出一部分最有代表性的特征吼特征抽取可以看作从测量空间到 特征空间的一种映射( m a p p i n g ) 或者变换( t r a n s f o r m ) 。 如果采用文本中的词条t ( t o k e n ) 作为特征项，文本可以表示为特征向量， 即d = ( t 1 ，t 2 ，t n ) ，元素t i 是词条。由于构成文本的词条数量是相当 大，表示文本的向量空间的维数也相当大，可以达到几万维，一般的学习算法无 法对其进行类别学习，因此我们需要进行维数压缩，进行特征选择和提取。 根据齐普夫z i p f 定律4 5 1 ，每个词在一篇文章中的出现频率f ，按照频率值 多高到低递减的顺序排列的次序号r 的乘积约是一个常数，即：r * f = c 。其中 c 是一个围绕中心值上下波动的常数。 显然，高频词和低频词的区分能力都不是最强。例如，助词“的”“了”， “我们”这些单词几乎在每类文本集的每篇文本中都出现，而且出现频率很高， 但是对文本类别的区分度不大，所以不能作为特征词。而某些单词比如“地震” “震级”这些单词虽然在所有的文本集中出现频率不是很高，但在地震类文本中 出现频率很高，对于地震类别具有很强的区分度，所以应该选为地震类别特征词。 由此可见，特征项应该在某特定类别文本中的发生频率较高，而在整个文本 集合中出现的频率较低的特征词。 特征选择可以在两个方面提高系统性能：一是分类速度，通过特征选择，可 以大大减少特征集合中的特征数，降低文本向量的特征数，提高系统运行速度。 二是准确度，通过适当的特征选择，不但不会降低系统准确性，反而会使系统精 确度提高【2 1 。 2 3 3 2 特征提取 特征提取的目的是找到特征项，一般方法是：首先通过构造一个特征评分函 9 北京工业大学工学硕士论文 数，把测量空间的数据投影到特征空间，得到特征空间的值，然后根据特征空间 中的值对每个特征进行评估，特征选择就成了特征值最高的若干特征。 下面介绍几种常见特征评分函数1 2 4 】。 1 ) 文本频率( d o c u m e n t f r e q u e n c y ，简称d f ) 。 文本频率指训练集中包含该特征的文本总数。所谓文本包含特征是指这 个特征在该文本中出现，忽略其在文本中的出现次数。d f 方法提取d f 值 较高的特征，它的目的是去掉在训练集上出现次数过少的特征，保留出现达 到一定次数、具有一定影响力的特征。在各个特征提取方法中，d f 方法的 计算是最简单的。 2 ) 信息增益( i n f o r m a t i o ng a i n ，简称i g ) 。 i g 值代表了特征在训练集上的分布情况，它通过统计特征在各个类别 中的出现次数来计算，公式如下： g ( f ) = 一：。p ( c f ) l o g p ( q ) + p ( f ) 三。p ( c f i t ) l o g p , ( q l f ) + p ( - ) ：。p ( c f i - t ) l o g p ，( c , 1 i ) 其中t 代表特征，c i 代表第i 个类别，m 为类别数，p ，代表概率。i g 值越高 表示该特征在训练集中的类别上分布越集中。i g 方法提取i g 值较高的特征，其 基本思想为分布越集中的特征越重要。 3 ) 互信息( m u t u a li n f o r m a t i o n ，简称m i ) 它通过计算特征t 和类别c 间的相关性来完成提取。计算公式为： m ，c ) = l 。8 丽e a t c ) 为方便计算，简化为： m ，c ) * l 。8 西丽a x 可n 而 其中n 为训l 练集中包含的文本总数，a 为t 与c 同时出现的次数，b 为t 出 现而c 不出现的次数，c 为c 出现而t 不出现的次数。通过该公式就可以取得特 征与各类别间的互信息值。为了能取得特征在数据集上的整体评价，有以下两种 计算方法： k ( f ) = p ，( c i ) i ( t ，c a ，! ，。彗錾圣窒垄塑套黧。，。，。， t 。( f ) = m a x i ( t ，c 。) 前者代表了特征和各类别的平均互信息值，后者则取特征与各类别互信息 值中的最大值。m i 方法提取互信息值较高的特征，其基本思想为与类别相关性 越高的特征越重要。 三种特征提取函数相比较，文本频率最简单，但是忽略了特征项和和类别间 的依赖程度；信息增益考虑特征词在类中出现和不出现的两种情况，但是计算过 于复杂；互信息体现特征和类别间的依赖程度，与类别关系越紧密的特征越重要， 计算复杂度介于两者中间。我在特征提取算法中采用互信息作为特征提取函数。 2 4 分类算法 基于机器学习的分类算法可以分为两类1 5 ：有指导分类( s u p e r v i s e d c l a s s i f i c a t i o n ) 和无指导分类( u n s u p e r v i s e dc l a s s i f i c a t i o n ) 。 2 4 1 有指导分类算法 有指导分类属于机器学习中的示例学习，即给出若干学习例子( x i ，v ( x i ) ) ( i = l ，2 ，n ) ，学习函数f 提出一个用于判断该x i 类别的规则。 目前，已经提出了许多理论上较为优秀的有指导分类算法，例如基于统计的 支持向量机、朴素贝叶斯方法、基于关联规则类算法，基于机器学习的决策树以 及神经网路的向后传播算法等，并且已经应用于微型影像，信誉风险和移动控制 等实际分类问题【2 8 】。 然而，没有一个算法对于每个数据集合都是最好的，采用哪一个分类算法最 终由数据集合的特性决定。本文要处理的数据集是中文文本数据，所以从文本数 据集的角度出发，分析和评价几种表现性能较好的分类算法。 2 4 1 1 基于t f i d f 的r o c c h i 0 算法 r o c c h i o 算法来源于向量空间模型理论，采用向量来表示文本，把对文本的 处理转化为空间向量的运算。基于t f i d f 的r o c c h i o 是这种思想的一种实现方 法。一篇文本以一个n 维向量来表示( 向量维数n 即特征数目) ，向量分量是特 征的权重表示，权值的计算采用t f i d f 公式。采用r o c c h i o 算法对文本分类步 北京工业大学工学硕士论文 骤如下： 1 ) 将训练集中的每个类别文本表示为向量，向量正规化，使每个向量具有 相同的长度； 2 ) 计算每个类中所有文本向量的平均值，形成类别特征向量； 3 ) 给定一个未知文本，生成该文本的向量； 4 ) 计算该向量与各类别特征向量的相似度； 5 ) 将该文本分到与其相似度最大的文本类别中去； 总体来看，r o c c h i o 算法简单易行，运行速度尤其是分类速度较快。 对于一个文本d ，其特征w 的权值为t i e ( w ，d ) ，m f ( w ) ，其中t f ，d ) 为特征 w 在文本d 中的出现次数，i d f ( w ) = l o g l 面 ，其中蚓为训练集中的文本总 数，d e ( w ) 为训练集中包含w 的文本数( 即w 的d f 值) 。所以i d r ( w ) 正比于 w 在训练集中的稀有程度。 向量的相似度度量一般采用欧几里德e u c l i d 距离和向量夹角余弦值，以x ，y 代表向量( x 。y l 代表向量分量) ，两种距离定义如下： ”欧几里德距离：加。) 2 、蔷( x i - y i ) 2 ，d i s 值越小表示距离越近r 向 量的相似度越高： e x i x y ， 2 ) 向量夹角：c o s ( = ，y ) = 1 坠1 一，c o s 值越高表示角度越小，向量 1 善21 蕃咒2 的相似度越高。 2 4 1 2 朴素贝叶斯模型 贝叶斯分类是一种统计学分类方法，它基于贝叶斯定理，可以用来预测类成 员关系的可能性，给出文本属于某特定类别的概率。分类时根据预测结果将该样 本分到概率最高的类别中去即可。假定有m 个类c l ，c 2 ，c 。，给定未知文 本x ，贝叶斯分类将给出条件x 下具有最高后验概率的类别，即最大化p ( c ，ix ) 。 根据贝叶斯定理可得： 1 2 第2 章中文文奉分类技术研究 p ( g i x ) = 警 显而易见，p ( x ) 对于所有类是个常数，刚只需最大化p ( z f c ) p ( g ) 即可。 p ( c f ) 可以根据训练集中的类别分布来计算，即p ( c f ) = ；i 舄，其中1 c i l 为类别 c i 包含的文本数，蚓为训练集中的文本总数。 在一个具有许多属性的事例中，计算p ( x i e ) 的开销会非常大，为了降低这 种开销而引出了称为类条件独立的朴素假定：假定文本的一个属性对于分类的影 响独立于其他属性，即文本的属性之间是不相关的。这就是朴素贝叶斯( n a i v e b a y e s ) 的由来。这样就可以简单的以各个属性在类别c i 上出现的概率来推算 以x i g ) 。通常使用拉普拉斯估计( l a p l a c e a np r i o r ) 来推算。又因实现细节的 不同有两种朴素贝叶斯模型，多元模型( m u l t i - v a f i a t eb e r n o u l l im o d e l ) 只考虑 了特征在文本中是否出现( 出现记为1 ，否则记为0 ) ，多项式模型( m u l t i n o m i a l m o d e l ) 考虑了特征在文本中的出现次数： 1 ) 多元模型中p ( x l c ) = 兀( 吃p ( i g ) + ( 1 t 。) ( 1 一j p ( w f i q ) ) ) ，其中w 。 代表第t 个特征( 即向量的第t 分量) ，i v l 代表特征总数，b 、。表示w 。是 否在文本x 中出现( 出现记为l ，否则为0 ) 。其中 酏= 坚蔫藉端竽。 2 ) 多项式模型中p ( x i g ) = n 学，这里n x 。代表了特征t 在文本 x 中的出现次数a 而p c l q ，= 万 主妻溉，其中酬代 表训练文本总数，i v | f 弋表特征总数，n i t 代表特征t 在文本吐中的出现次 数，n j s 代表特征s 在文本d i 中的出现次数。 朴素贝叶斯分类模型训练的过程其实就是统计每一个特征在各类中出现规 律的过程a 从理论上讲，贝叶斯分类的出错率最小，然而试验结果表明，朴素贝 北京工业大学工学硕士论文 叶斯在大型的数据集上表现出来难得的速度和准确度。 2 4 1 3 决策树 决策树( d e c i s i o nt r e e ) 是一个类似于流程图的树结构，其中每个节点代表 一个属性上的测试，每个分支代表一个测试输出，最后的叶结点代表类别。决策 树方便改写为形如i f - t h e n 的分类规则，易于理解。 决策树的核心算法是一种贪心算法，它以自顶向下的方式在训练集的基础上 构造决策树，之后取未知文本的属性在决策树上测试，路径由根结点到叶结点， 从而得到该文本的所属类别。决策树的算法有c 4 5 ( 发展于i d 3 ) ，c a r t ，c h a i d 等，他们的区别在于构造决策树与树枝剪除的算法细节不同【4 7 1 。决策树可以很 好的抵抗噪声。最大的缺点在于不适应大规模的数据集，此种情况下决策树的构 造会变得效率低下。 2 4 1 4 向后传播算法 向后传播是一种神经网络学习算法。粗略的说，神经网络是一组连接的输入 输出单元，其中每个连接都与一个权相相连。在学习阶段，通过调整神经网络 的权，能够预测输入样本的正确标号。用在文本分类上，输入即为文本在各个特 征上的各分量值，输出为样本的类别。 神经网络实际上是一组连接的输入输出单元，其中每一个连接都具有一定的 权值。通过训练集来训练的过程就是调整这些权值的过程，使得神经网络可以正 确的预测类别。 2 4 1 5k 最近邻居算法 k 最近邻居( k n e a r e s tn e i g h b o r ，简称k n n ) 分类的思想也来源于向量空 间模型，同样采用将文本转化为向量的思想。 该算法的基本思路是：在给定新文本后，考虑在训练文本集中与该新文本距 离最近( 最相似) 的k 篇文本，根据这k 篇文本所属的类别判定新文本所属的 类别，具体的算法步骤如下： 1 ) 根据特征项集合重新描述训练文本向量 2 ) 在新文本到达后，根据特征词分词新文本，确定新文本的向量表示 3 ) 在训练文本集中选出与新文本最相似的k 个文本，计算公式为： 1 4 第2 章中文文本分类技术研究 s k n ( d ，d j ) 了等严 、( k = l 耀) ( k = l 吆) 其中，k 值的确定目前没有很好的方法，一般采用先定一个初始值，然 后根据实验测试的结果调整k 值，一般初始值定为几百到几千之间。 4 ) 在新文本的k 个邻居中，依次计算每类的权重，计算公式如下： p ( z 0 3 ，q ) = 互s t m ( x 一, d i ) y ( d i ，q ) m e k n n 其中，为新文本的特征向量，s i m ( x w , 勘为相似度计算公式，与上一 步骤的计算公式相同，而y ( 菇c ，) 为类别属性函数，即，如果茁属 于类c ，那么函数值为l ，否则为o 。 5 ) 比较类的权重，将文本分到权重最大的那个类别中。 k n n 是一种基于类比的分类方法。在训练的过程中k n n 会生成所有训练例的 特征向量，并将其保存下来。给定一个未知文本，首先生成它的特征向量，之后 k n n 会搜索所有的训练例，通过向量相似度比较从中找出k 个最接近的训练例， 然后将未知文本分到这k 个近邻中最普遍的类别中去。相似度可以通过欧几里德 距离或向量间夹角来度量。 它没有学习过程，只是存放所有的训练例，直到接到未知文本的时候才建立 分类，是一种懒散的方法。k n n 的训练过程较快，而且可以随时添加或更新训 练例来调整。但它分类的开销会很大，因为需要很大的空间来保存训练例，而且 分类效率很差。有看法认为在小数据集上k n n 的表现优异f 1 。 2 4 1 6 支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 是基于统计学习理论提 出的一种新的机器学习方法。它以结构风险最小化原则为理论基础，通过适当的 选择函数子集及其子集中的判别函数使学习机的实际风险达到最小。保证了通过 有限训练样本得到的小误差分类器对独立测试集的测试误差最小，得到一个具有 最优分类能力和推广泛化能力的学习机。目前支持向量机已经用于文本分类“i 。 北京工业大学工学硕士论文 | i i i i 2 4 2 无指导分类算法 无指导分类也就是聚类，它可以看作观察学习( 1 e a r n i n g f r o mo b s e r v a t i o n ) ， 即对无指导分类器给出一些观察样本，采用无指导的方法对样本进行分类。 无指导分类的研究目标是寻找相似性，对数据进行方便而有效的分组。同组样本 彼此相似，不同组样本彼此相异。 与分类不同，聚类分析数据对象，而不考虑已知的类标记。目前典型的聚类 算法有基于划分的k 一平均方法 4 8 】，基于层次的b i r c h ，c u r e 和c h a m e l e o n 算法， 基于密度的d b s c a n ，o p t i c s 和d e n c l u e 算法，基于网格的s t i n g ，w a v e c l u s t e r 和c l i q u e 算法等【3 8 。 2 5 评估标准 文本分类效果可以从准确率、查全率、遗漏率、正确率、错误率五个方面评 估。“。假设： a 表示判为c 类且确实属于c 类的文本数目； b 表示判为c 类且但实际不属于c 类的文本数目； c 表示判为非c 类且确实不属于c 类的文本数目； d 表示判为非c 类且但实际上却属于c 类的文本数目； a + d 表示实际属于c 类的文本数目： b + c 表示实际不属于c 类的文本数目； 可以定义： 准确率= a ( a + b ) 查全率= a ( a + d ) 遗漏率= b ( b + c ) 正确率=( a + c ) 1 2 ，n = a + b + c + d 错误率=( b + d ) n ，1 1 = a + b + e + d 因为文本分类从根本上说是一个映射过程，所以评估文本分类系统的标志是 映射的准确程度和映射的速度。所以，文本分类系统的最重要的两个指标是：准 确率( p r e c i s e ) 和查全率( r e c a l l ) 。 第2 章中文文本分类技术研冤 准确率和查全率反映了分类质量的两个不同方面，两者必须综合考虑，不可 偏废，因此，存在一种新的评估指标，f 1 测试值，其数学公式如下： 砌撇= 鼍鬻 另外有微平均和宏平均两种计算准确率、查全率和f 1 测试值的方法。 微平均：计算每一类的准确率、查全率和f l 测试值。 宏平均：计算全部类的准确率、查全率和f l 测试值。 本文采用微平均评估文本分类效果，分别计算每一类文本的准确率、查全率 和f l 测试值。 2 6 本章小结 本章结合中文文本的特点，在基于统计模型的基础上介绍常见文本分类技 术，包括文本的向量空间模型( v s m ) 表示、文本预处理、目前常用文本分类算 法和文本分类的评估标准。 1 7 北京工业火学工学硕士论文