（信号与信息处理专业论文）文本分类相关算法的研究与实现.pdf

文本分类中的特征词选择方法的研究 摘要 文本分类一直是数据挖掘领域中的研究重点之一，其目的是为了能将大量的并且 无类别标注的文档进行类别上的归类。文本分类还是信息检索和信息过滤等信息处理 技术的重要基础。所以提高文本分类的技术水平会给目前的信息科技提供一些很有利 的支持点，来发展关于文本相关的信息应用科技。目前文本分类的技术早己从之前的 基础理论研究发展成为以算法的简便程度和算法的速度为研究目的的研究层次。所以 更好的算法是我们追求的目标之一。 文章在概述了文本分类的基本概念和算法的基础上，综述了其中文本分类整体过 程的一些情况，并重点讲述了特征词选择算法和分类算法部分。然后提出特征词提取 部分算法中的二元正态分离法的改进。文章分析了原有算法未加入词频统计的概念和 因此产生的不足，提出了分散度的概念，并设计了加入分散度概念的改进算法公式， 通过具体的文本分类实验表明该算法的改进在中文文本分类应用中较原算法和其他特 征词选择算法在分类效果上比较具有优势。 文章还对二元正态分离特征词选择算法及其改进形式进行了相关实验分析，结果 表明二元正态分离算法在分类表现上要优于其他算法，并且改进的算法强于源算法， 该算法在最优特征词数量上也具有优势，文章还对二元正态分离特征词选择算法在支 持向量机中的核函数使用情况进行实验对比分析，以及对惩罚因子和径向基核函数的 参数的寻优实验。 关键词：文本分类；特征词选择；二元正态分离 哈尔滨工程大学硕士学位论文 文本分类中的特征词选择方法的研究 a b s t r a c t t e x tc l a s s i f i c a t i o nh a sb e e no n eo ft h ek e yr e s e a r c hi nt h ef i e l do fd a t am i m n g ，i t s p u r p o s e1 st om a k el a r g en u m b e ro fu n c l a s s i f i e dd o c u m e n t sc l a s s i f i e di n t oi t sc a t e g o r y t e x t c l a s s i f i c a t i o ni sa l s oa ni m p o r t a n tf o 眦l d a t i o no fi n f b n i l a t i o nt e c l l i l o l o g yo f t e x ti m m a t i o n p r o c e s s i n g ，i n c l u d i n gi o m a t i o nr e t r i e v a la n dn l t e r i n g i h e r e f o r e ，t h ei m p r o v eo ft h el e v e l o ft e x tc l a s s i f i c a t i o nt e c l u l o l o g yc a ng i v es u p p o r tt 0m e i m p r o v eo fi n f b m a t i o nt e c l l l l o l o g y a j l di t sa p p l i c a t i o n t h er e s e a r c ha i mo ft e x tc l a s s i f i c a t i o nt e c l m o l o g yh a sb e e nc h a n g e d f o mt h er e s e a r c ho fm eb a s i ct h e o 巧t ot h es i m p l ea n d h i g hs p e e da l g o 甜i i l l n l e r e f o r e ， e m c i e n ta l g o t h ni so n eo fo u rg o a lo fo u rr e s e a r c h t 1 1 i sp a p e ro u t l i n e st 1 1 eb a s i cc o n c e p t sa n d a l g o t h m si nt e x tc l a s s i f i c a t i o n ，t 1 1 e ne v i e w s e a c hp a r to ft h ew h o l et e x tc l a s s i f i c a t i o np r o c e s s ，e s p e c i a l l ys o m e i m p o j a n tp a r ti nd e t a i l ， s u c ha sf e a t u r es e l e c t i o na n dt h ec l a s s m c a t i o na l g o r i t h m t h e ni m p r o v e m e n to ft h eb i n o m a ls e p e r a t i o nf - e a n l r es e l e c t i o nm e t l l o di nt e x tc l a s s i f i c a t i o n i sp r o p o s e d 1 1 1 i sp a p e r a n a l y z e dt h eo r i g i n a la l g o r i t h ma n df o u n dt h a tt 1 1 e r ei sn o tt h ec o n c e p to f 、o r d 舶q u e n c y s t a t i s t i c s ，w 1 1 i c hr e s u l t si nas h o i r t a g eo ft 1 1 eo r i g i i l a la l g o r i t l l i l l b ya d d i n gt 1 1 e c o n c e p to f d i s p e r s i o ni nt h ef o m u l a ，t h e i m p r o v e db i - n o 咖a ls e p e r a t i o nm e t h o ds h o 、v e db e t t e r p e r f e m l a n c et h a nm eo r i g i m la n dt h eo t h e rf e a t u r es e l e c t i o nm e t l l o di n t h ec 1 1 i n e s et e x t c l a s s i f i c a t i o ne x p e r i m e n t t h e 枷c l ea l s om a k e st h ee x p e d m e n t a la n a l y s i so nt h eb i n o 珊a ls e p a r a t i o nf e a t u r e s e l e c t i o nm e t h o da 1 1 dt 1 1 e i m p r o v e df o 吼a n dt h er e s u l ts h o w st h a tb i n o 衄a 1s e p a r a t i o n m e t h o di ss u p e r i o rt oo t h e ra l g o r i t so nt 1 1 ec l a s s i f i c a t i o np e 怕珊a n c ea n d i m p r o v e do n e i sb e 仳rt h a n 廿l eo r i g i m l e x p 嘶m e n ta l s os h o w s t 1 1 a tt l l i sm e t l l o dh a sa d v a n t a g ei nt l l eb e s t n 啪b e ro ff e a n 玳ss e l e c t e d ，n l ea n i c l ea l s om a k e sa j l a l y s i so f c o m p a r a t i v ee x p e r i m e m so n k e m e lf h n c t i o no fs v m 谢t hm eb i - n o n i l a ls e p m t i o nf b a t u r es e l e c t i o nm e t h o da 1 1 dt l l e e x p e r i m e n to ft l l e 叩t i m i z a t i o ne x p e n m e m so nt h ep e n a l 够f a c t o r 觚l dm e p a r a m e t e ro fr a d i a l b a s i sk e r n e l 矗h 1 c t i o n k e y w o r d s ：t e x tc l a s s i f i c a t i o n ；f e a t u r - es e l e c t i o n ；b i - n o n i l a ls e p a r a t i o n 哈尔滨工程大学硕士学位论文 第1 章绪论 第1 章绪论 1 1 研究背景及意义 在二十世纪中后期，电子计算机与互联网的出现与发展给社会带来了翻天覆地的 变化。随着现代电子计算机的发展与更新和计算机网络的提速与普及，计算机领域的 主要信息领域也在日新月异的高速发展。计算机处理信息的速度越来越快，已经出现 多核处理器，而且信息的存储量也大的惊人，现在一般的个人电脑的硬盘就可以达到 1 0 0 0 g b ，这在1 0 年前几乎是不可能的，可见其发展的速度之快。另外现在互联网的 发展与普及也是相当的快，韩国的网络视频直播可以达到高清的每秒数十兆的网络速 度。可见当今的科学技术的发展为信息处理、存储、传播、甚至搜索都提供了重要的 技术基础。 在所有处理的信息中，文本信息可以说是非常常见的信息表示形式【l 】，书籍、报 纸、杂志这些在日常生活中非常常见的纸质信息载体的信息表现形式就是文本信息， 在互联网中，各种网页、日志、社区帖等等，也都是文本类的信息。可见，无论在数 量上，还是在重要性上，文本信息可以说是在各种信息形式上都是至关重要的。由于 文本信息的存储量多，信息繁杂，没有事先进行归类，然而如果通过人工进行归类可 以说是一个海量的任务，所以在文本信息处理技术中，文本的分类技术是非常重要的 一种处理技术【2 】，通过文本分类，可以知晓文本所代表的信息标签，这个标签在实际 中的用处非常大，在信息搜索中，在垃圾邮件处理中，在网页过滤中都是非常重要的 技术基础【3 j 。 1 ) 在信息搜索引擎中，可以将已有的信息进行归类，然后在信息的搜索过程中 按类进行搜索，可以降低搜索范围，提高搜索精度。 2 ) 在垃圾邮件处理中，可以由学习好的计算机程序来对新来的邮件进行分类， 分清该邮件是垃圾邮件还是非垃圾邮件，还是是未分类邮件，以待邮箱拥有者来判 定。 3 ) 在网页过滤中，基本也和垃圾邮件的处理类似，也是判定该网页是合法、健 康的，还是不健康的，来决定该网页是否可以在互联网上显示。 在文本分类技术中，可以分为若干个子步骤，这些子技术在整个文本分类过程中 全都起到一个至关重要的作用。这些关键的步骤包括特征词的选取、文本模型的构 建、文本分类的实施算法等等【4 】，这些步骤基本上是对该环节以下的步骤有着重要的 堕签鎏兰堡奎兰堡主兰垡堡茎 影响，以至于对整个文本分类的最终效果有着重要的决定作用。所以文本分类的每个 环节的研究都是非常重要的。 1 2 文本分类的概述 文本信息是一种高复杂度的信息表示形式载体，因为语言的表达形式、方式有各 种各样的变换，故要分析文本信息的相关内容，就要将这种复杂的信息表示形式进行 分词整理，在信息进行分词整理之后，对文本信息进行以特征词为表达元素的表示形 式。但是对于中文来说，词的种类和个数十分的多，这就使得文本表达的维数十分的 巨大，一般可以达到上万或者几十万，并且词的重要性对于文本分类来说也有所不 同，故需要对文本的特征进行特征降维。降维的方法主要有两种，一种是特征词选 择，一种是特征词抽取1 5 j 。 对于特征选择降维方式，是从原始特征维数空间进行化简，得到原始特征词空间 的子集空间，这个化简的特征空间在重要性上要达到文本分类的要求，即要求能利用 这个特征空间对所有的文本进行类别的区分。特征的化简方法有很多种，但是主要的 思想是采用一定的评价标准，对原始特征空间的每一个词进行评价，通过评价的好坏 来决定该特征词是否被收入到新的特征词空间。这种特征降维方法在原理上比较直 接，并且容易理解和实施，在效果上表现也很不错【6 1 ，故目前主要的特征降维方式采 用这一种。 第二种特征降维的方式也被称为特征重新提取，这种降维可以理解为特征空间的 转化，而不是删减，因为在特征词中，很多是同义词，或者很多词都可以由一些属性 词来表达。所以在原理上这种特征降维方式更能表达语言的本身含义。这种特征降维 方式主要有以下几个方式：特征聚类7 1 、主成分分析、潜在语义标引【8 】o 对于文本分类的分类过程，总的来说就是将未分类的文本通过经过各种已经分类 的文本训练出的分类器进行类别归类p j 。 根据构建的分类器的模式的不同，可以将文本的分类过程分为基于领域规则的分 类方式和基于统计的分类方式。基于领域规则的分类方式【1 0 】是利用领域专家的经 验，来构造分类的专家系统。系统利用该领域的规律和专业知识来对未知的文档进行 分类。基于领域规则的分类器的构建由于各领域的知识的不同和不同，并且需要领域 专家的维护更新，所以这种构建方式的分类器在应用上很受限制。基于统计方式构建 的分类器【1 1 】是利用大量的已分类的文本进行模型的构建，来对统计模型的参数进行 确定。其中模型的构建是利用文本内的某些统计量的统计信息来确定模型的公式、参 第1 苹绪论 数等。该方式不要求领域内的专业知识，只需要对训练文本集进行统计即可，所以该 方式在实际的应用中较为广泛，但该方式会收到事先收集的训练文本集的涵盖量和偏 差度的影响，然而目前文本分类领域的主要研究的还是这种文本分类方式，本文也是 主要以这种方式进行探讨。 文本分类不只是单一的学科，它会涉及到各个领域的一些知识。文本分类是与语 言密切相关的一门学科，所以自然语言处理知识在文本分类中要对文本的基础表示元 素进行底层的构建，比如对文本进行分词等等。机器学习在文本分类中也是主要的一 门相关学科，机器学习是计算机在实验过程中搜集以往的经验数据来对模型进行构 建，机器学习的理论基础是统计学习理论【1 2 】，所以机器学习的各个方法在文本分类 中，也会起到一个主要的作用。 1 3 国内外研究现状 文本分类的理论研究文本分类的理论研究可以追溯到2 0 世纪6 0 年代初，其发展 过程大致可以划分为三个阶段： 第一阶段是2 0 世纪6 0 年代前。在这一时期，主要是将文本分类应用于信息检 索。在这一时期，提出了很多经典文本分类的数学模型。如概率标引 ( p r o b a b 订i s t i e i l l d e x i n g ) 模型，和向量空模型( v e c t o rs p a c em o d e l ，v s m ) 对文本进行描 述等等。 第二阶段是2 0 世纪8 0 年代。这一阶段主要是采用专家系统的形式，根据专家提 供的知识形成规则，手工建立分类器。这一时期，信息检索技术逐渐成熟应用，为文 本分类提供了许多技术支持，最著名的信息检索系统是s a l t o n 的s m a r t 系统。 r o o c l l i o 在1 9 7 1 年也提出了在用户查询中不断通过用户的反馈来修正类权重向量， 来构成简单的线性分类器。融j s b e 唱e n 提出了信息检索的评估标准如准确率、查 全率等。 第三阶段是2 0 世纪9 0 年代以后。在这一时期，文本分类的主要特点是采用统计 机器学习方法，自动建立分类器，学习和分类过程来自于机器对训练文本的自主学 习，从而不需要领域专家的支持，不需要人工干预，而分类效率和准确率得以提高。 如1 9 9 2 年提出的标准数据集r e u t e r s 2 2 1 7 3 ，并在此数据集上进行了实验测 试；g y i m i n g 对各种特征选择算法进行了分析比较，讨论了文档频率( d o c 啪e m f r e q u e n c y ，d f ) 、信息增益( i n f o 咖a t i o ng a i n ，i g ) 、互信息0 v i u h i - i n f o m a t i o n ，m 1 ) 和 c h i 等方法，结合k 卜n 分类器，得出i g 和c h i 方法分类效果相对较好的结论，对 哈尔滨工程大学硕士学位论文 后来的研究起到了重要的参考作用。 随着研究的深入，文本分类问题被进一步细化，如：分类算法，特征降维，性能 评价，样本学习，分类性能推广等，专家们试图从多个方面提高文本分类的效果。在 此，本文主要是对特征降维部分的文本特征选择算法进行了研究。 目前国内对文本分类中的特征词选择方法的研究大致为对经典方法的改进。 文献【3 7 】将文档频法中加入了词的频率统计信息元素，使得该方法在分类最终效 果上有所改进。文献【3 8 对互信息特征词选择方法进行了改进，定义一种新的特征词 文档频，采用阈值化的文档频来对特征词的互信息进行描述和评估，在最终的分类精 度效果上，有所增加。文献【3 9 】对互信息中加入最小词频的限定量，并且引入了最小 特征冗余度的模型定义，实验表明，该改进在各种度量参数上，均有所提高。文献 4 0 】分析了互信息的阈值定义中的缺点，引入了二次的t f i d f 度量方式，并从新设 计了互信息的定义公式，并进行了效果分析实验，并取得了理想的效果。文献【4 1 对 信息增益特征词选择方法进行了改进，针对该方法中对不出现在某个文本类别中的特 征词在其他类别中不出现的概率进行考察的情况进行了分析以及改进，提出这种考察 的不重要性，并提出应该考察在该文本类中不出现的特征词在其他文本类别中出现的 概率，该文献对这种改进进行了实验对比，均取得了良好的效果。文献 1 5 对卡方统 计特征词选择方法进行了分析并改进，对该方法中的负相关词的信息删除出去，只保 留正相关信息，结果显示这种改进有很好的效果。 1 4 创新点和主要工作 文章的主要创新点为分析了一种较新引入中文文本分类的特征词选择方法，二元 正态分离法，并对该方法进行优点分析，并做了实验验证。然后再对该方法没有涵盖 词的频率这一缺点进行分析，然后加入了分散度的概念，并设计了新的二元正态分离 法的公式，并做了实验验证。 另外本文的主要工作有： 1 ) 对各种常用特征词选择方法与二元正态分离法进行实验对比。 2 ) 本文提出的改进的二元正态分离特征词提取算法与原始算法进行实验比较。 3 ) 对与朴素贝叶斯算法配合的特征词选择算法( 二元正态分离法与其他常用特征 词选择算法对比) 的特征数量进行实验分析。 4 ) 对支持向量机在与二元正态分离法相配合时的核函数的选择上进行了实验分 析。和惩罚因子和径向基核函数中的参数g 利用粒子群优化算法进行了实验，并找出 第l 章绪论 最优参数位置。 1 5 本文的组织结构 本文主要研究了文本分类过程的特征词选择和分类算法的分析上，本文的具体组 织结构如下： 第一章：主要介绍了本课题的研究背景以及其主要的研究意义，并对本文的主要 研究内容进行了一个概述。 第二章：对文本分类的整体做了详要的介绍。其中包括预处理、特征选择过程、 文本的具体模型的表示方式、分类算法。 第三章：对特征选择过程以及具体的常见方法进行了介绍，并将一种较新的中文 文本特征词选择算法，二元正态分离法，进行分析和改进。 第四章：对具体的分类算法进行了介绍，主要有朴素贝叶斯分类法和支持向量机 分类法，还介绍了算法中参数的一种优化方法，粒子群优化方法。 第五章：对上述的主要工作中提到的实验进行了分析。 第六章：进行了本文的研究内容的总结，并对本文有待进一步研究的内容做了分 析、总结和展望。 哈尔滨工程大学硕士学位论文 第2 章中文文本分类技术 2 1 中文文本分类的整体过程 中文文本分类的整体过程主要可以分为训练过程和测试两大过程【13 1 。其中的训 练过程是利用搜集好的可以表示中文语言模型的文本训练集来对要形成的模型进行公 式和参数的确定。然后利用已经训练好的模型来对待测试的文本进行分类，后面的这 个过程是测试过程，来确定最终的分类类别。 提供特 征词 提供分 类模型 l 特征词统计信息提 取 文本的模型表示 图1 1 文本分类整体流程图 在测试过程，首先要对训练文本集进行预处理，其中包括分词和去除停用词，然 后对训练文本进行特征词选择，选择出能最能代表各个类别的若干特征词，然后再构 建文本表示模型，来形成分类器，这个过程是训练过程的主要步骤。测试过程的主要 步骤如下，首先也是对待测试文本进行预处理，然后利用训练过程提取的特征词进行 待测文本的模型表示，然后利用训练过程构建好的数学模型对待测文本进行分类的计 第2 章中文文本分类技术 算过程，来确定最终的分类结果。整体的过程的流程图如图1 1 。 2 2 文本的预处理 中文文本因为其语言的特点，不是像英文那样词与词之间是有间隔的，中文的词 语是连续的，需要文本的读者根据其语言知识来对词进行自行的分开。但是如果让计 算机来处理中文的文本，那就需要首先对文本的词与词进行分开，这个过程就是文本 的分词。 目前的中文分词算法主要有以下几种： 1 ) 按照现有的词典进行匹配的分词算法 该算法的主要思路是按照已经整理好的词典来对文本进行词典中的逐个词条进行 匹配，再按一定的切分规则来进行切分，匹配的方向可以为从后到前，也可以从前到 后，也可以从两边到中间，匹配搜索过程的长度可以任意设定，但根据中文的语法， 一个句子不能太长，故可以限定一个阈值来决定匹配搜索的长度，如果匹配成功，则 将结果输出为单词，将未匹配成功的按单字的词来进行输出。最大字符匹配法就是按 照这个原理进行匹配。虽然该算法的原理简单，效率也高，但是该算法对词典的依赖 程度过于强烈，使得当词典不是很完备时，无法进行高要求的分词任务。 2 ) 按照统计规律来进行分词 该算法的主要思路是统计每个字与字或字与词相邻的几率，从而断定这相邻的两 个单元是一个词的概率，如果概率高，则表明这个两个单元组成的是一个词。这也符 合中文的语言规则：因为词语在出现时必是两个单元成对出现，但是由于要进行统计 的元素个数过多，所以这种方法的效率不是很高。但是这种方法的优点正好能克服词 典匹配法的缺点，词典匹配法在词典的完全性上不容易满足，但是其算法的效率高， 统计规律法在完全性上容易满足，但是算法的效率低。这两种方法正好互相取长补短 【1 4 】 o 文本的分词对于文本分类来说是一个必不可少的步骤，更是关系到特征词选择， 模型的建立的过程，所以这个步骤会直接影响文本分类的最终效果i 】5 | ，目前有很多 研究机构，包括i b m 公司，清华、北大等，都从事于文本分类算法和技术的研究， 其中i c t c l a s 这个中科院的分词工具包在表现上最有优势，本文利用的就是这个工 具包。 另外，中文的文本有很多没有实际意义的虚词，比如“可是”、“虽然”、“等 等”、“的”等，这些是对于文本的分类没有贡献的词，在中文文本分类中被称为停 哈尔滨工程大学硕士学位论文 用词【1 6 】，相对于那些具有实际意义的名次、形容词等，这些词如果加入到文本分类 的各种计算中，会增加无用的计算量，所以在文本分类的起初步骤中要删除这些停用 词，以减少文本的特征维数。这是文本预处理的过程中要进行的两个步骤：文本的分 词和文本的停用词的删除。 在创建停用词时，可以用研究机构提供的已经确定好的停用词表，这些停用词表 所确定的停用词很具有代表性，也是研究机构经过实验确定下来的停用词表，具有一 定的权威性和实用性。另外，根据所进行实验的实验文本训练集的不同，停用词对于 不同的训练集也会有所不同，所以可以通过实验来确定属于该文本训练集的挺用词 表。实验的大概思想可以描述为如下步骤：对已经分好的单词进行统计，如果该单词 在每个类别中出现的文档数接近与该类别的文档总数，那么这个词对于文本分类来说 没有实际意义，因为这个词在各个类别中均出现，每次出现该词的类别几率都是相同 的，所以这样的词可以被划分为停用词。 2 3 文本的特征词选择 经过分词和去停用词后的文本是一些文本词的集合，这些文本词集合可以表示每 个文本，但是这些文本词集合的总数非常巨大，如果以这些文本词为表示特征，那么 其维数可以达到数十万甚至更大，这给后续的相应的计算带来巨大的问题。另外这些 、所有的文本词也不是都具有很高的代表性，所以就需要选择出最能代表要进行的分类 的特征次来表征这些文本的特质，来降低表示文本的特征的维数，也方便之后的计 算。 现在国内外已经研究出许多方法来对文本的特征词进行选择，目前常用于中文文 本特征词选择的方法有文档频率( d f ) 法、互信息( m i ) 法、信息增益( i g ) 法、卡 方估计( c h i ) 法等 1 7 】。对这几种方法在中午文本分类中的研究，国内外已经有大量 的文献，并给予了改进，改进效果也很不错。 2 4 文本的模型表示 文本是字符串的集合，要对文本进行各种各样的计算，就需要将这些文本字符串 表示成相应的数学模型。可以将各种文本涵盖的信息进行统计，来产生相应的数学模 型。目前主要有一下三种文本表示模型：布尔表示模型( b 0 0 1 e a i lm o d e l ) 、概率表 示模型( p r o b a b i l i s t i cm o d e l ) 、和空间向量模型( v e c t o rs p a c em o d e l ) 。 布尔表示模型( b o o l e a nm o d e l ) ：布尔模型的表示方式主要是将各个单元特征 第2 章中文文本分类技术 词是否在某个文档中出现表示布尔变量，如果出现了，变量为1 ，没有出现为o 。这 种表示模型的优势是简单易行，但是这种二元表示方式是以忽略其中包含的更重要的 信息为代价的，因为这种表示方式只是能显示出其是否与该文档相关，相关的程度无 法知道，所以这种表示方法在应用上效果欠佳。 概率表示模型( p r o b a b i l i s t i cm o d e l ) 【1 8 】：概率表示模型表示的是与文本相关的一 些特征统计数据，这些数据表示的是两者之间的相关程度，用这些信息来表征文档与 类别的相关程度。与布尔模型类似，这种表示模型表达的信息也过于单一，无法整体 的反映一篇文档的大部分重要的信息，所以其在实际应用中的表现效果也不是很很 好。但目前有很过关于这种模型的研究和改进，在应用效果上有所提高 空间向量模型( v e c t o rs p a c em o d e l ) ：空间向量模型是目前最成熟，应用最为 广泛的一种文本表示模型。因为其表达的文本信息多，表达的信息内容重要，所以其 在应用中表现的分类效果比较不错【19 1 。以下是这个模型的详细说明： 首先，该模型表示【2 0 】的文本文档( d o c 啪e n t ) 是由文本特征词组成，文本文档是一 个文章组成单元，这些特征词叫做文本特征项( t e m ) ，对于每个文本文档，可以 用特征项的权重( t e mw 色i g h t ) 组成的向量来表示，这些特征项的权重表示的是文 本特征词对于这篇文档的重要程度，这个重要程度有很多的表示概念在里面，其中比 如词的文档频率、词的文档内词频，词的分布规律等等。假设文本集合共有m 个文 档，选出来的特征次共有n 个，每个文档可以表示为d ，2 【w 1 ，w 2 ，) ，其中是特征 词在文档d ，中的权重表示，一般权重采用t f i d f 权值计算方法【2 1 1 ，权重计算公式 为 入， = 吮枣l o g ( 二) ( 2 1 ) 其中是文本七的第个特征词的权重，为训练集文本总数，厶是文本j i 中词7 出现的频率，玎，为训练集中含有词f 的文本数。 这时每个文档可以表示成具有与特征项数目相同维数的向量，所以这个模型被叫 做空间向量模型，那么所有的文档集合可以表示为： d = ( 4 ，破，叱) ( 2 2 ) 2 5 文本分类算法 在经过了文本预处理取得分好的词，再在这些词中选择出最具代表性的特征词 哈尔滨工程大学硕士学位论文 后，然后再利用这些特征词和具体的文本训练集建立好具体的文本表示模型后，最后 的一个重要的过程就是具体的文本分类算法。分类算法大体是要完成具体的分类器， 其中包括分类器中的模式和具体的函数，分类器利用这个模式和函数来对未知的文本 文档单元进行计算，以取得最终的分类结果。目前主要有以下的分类算法：k 邻近算 法、贝叶斯算法、神经网络算法、支持向量机算法【2 2 】。这些算法在各自的理论基础 上原理各不相同，但最终的目的都是分类算法。下面对上述的算法进行介绍。 1 ) k 邻近算法：k 邻近算法( k n e a r e s t n a b o r h o o d ，简称k n n 算法1 2 3 j ) 是一种 原理相对比较简单的分类算法。算法的主要过程【2 4 】如下：算法计算未分类的文档与 所有训练好的文档相似度或某些相关测量参数，目前研究中一般可以采用余弦相似度 计算1 25 1 ，其公式为 ( 2 3 ) 然后再报据这个相似度参数选取中其中k 个最相关的训练集的文档，再在这k 个最相关的训练集文档中选取数目最多文档的类别，这个类别即使最终的分类结果。 、该算法的流程图如2 2 。 ， 2 ) 神经网络算法：神经网络算法是一种模拟人的大脑神经网络来进行学习知识 的算法【2 6 | ，算法的计算单元是神经元，然后再将这些神经元进行连接，形成神经网 络，然后设计具体的神经元刺激和神经元连接特性，形成具体的神经网络后，再利用 经验来进行刺激( 学习) ，最后形成具有能解决问题的神经网络。 神经网络具有很多优点【2 ，首先神经网络具有学习能力，能根据先前经验来学 习其中包括的知识，以针对不同的问题产生不同神经网络，具有很广泛的应用能力。 再次神经网络具有存储能力，就会像人的大脑一样具有记忆能力。然后神经网络有自 反馈结构，这种结构对于神经网络学习过程的计算会产生反馈的作用，使计算会很快 求出相应的解。但是，神经网络有自身的缺点，神经网络在结构上无法直接反映出其 中的远离，有人将神经网络比喻成一个黑匣子，来表示神经网络无法清楚的解释其中 知识的原理。 3 ) 朴素贝叶斯分类算法：朴素贝叶斯算法是一种基于统计学的机器学习算法， 算法的最基本的原理是统计学中的贝叶斯原理公式【2 8 1 ，该算法将已经知晓的文本特 征词与训练集的文档的相应概率利用贝叶斯原理来转换成位置分类的文档与所有文本 l o 第2 章中文文本分类技术 特征词的关系，然后求出该文本最高的概率司能是的类别，这个类别即是最终的分类 结果。 贝叶斯基本公式为： 即旧= 警 ( 2 - 4 ) 其中尸( cd ) 表示文档d 或者特征词从属与文档d 的条件下该文档属于类别c 的 条件概率，尸( cd ) 表示在类别c 中，文档d 或者特征词在文档d 中出现的概率， 尸( c ) 、p ( d ) 分别表示类别c 和文档d 相应出现的概率。 图2 2 k 卜算法流程图 哈尔滨工程大学硕士学位论文 该算法的前提条件假设是文本文档中的特征词之间是相对独立的1 29 1 ，但是这在 中文文本中是不符合实际规律的，所以这是贝叶斯分类算法的一个不足之处，但是该 算法由于在分类的过程中不需要很多的计算量，这使得该算法有很快的分类速度，另 外该算法的正确率还是很不错的，贝叶斯分类算法也被广泛的纳入研究的热点对象中 【3 0 】 o 4 ) 支持向量机分类算法：支持向量机分类算法是一个二元分类算法，该算法对 于训练集的数据进行训练，取得一个最优的分类平面，来将已知的数据进行最大的函 数间隔的分类，所以这个分类器叫做最大边缘分类器【3 1 1 ，支持向量机分类算法不仅 能解决分类平面可解的线性问题，而且还能解决分类平面不可求的非线性问题，支持 向量机利用核函数将原问题域转换到高维可求解线性平面域【3 2 1 ，取得最大函数间隔 的分类平面，来对数据进行分类。能将原问题域转换到高维域的核函数主要有径向基 核函数、高斯( s i g m o i d ) 核函数、多项式核函数和线性核函数。针对不同的问题，利用 各个核函数的性质来确定能解决该特定的问题的核函数是支持向量机的主要应用上的 技术问题之一【3 3 1 。另外支持向量机是二元分类器，要进行多元分类就得将二元分类 转换成多元分类器【3 4 】。 ： 2 6 本章小结 本章主要讲述了文本分类的整体过程，其中包括了文本的预处理，文本的特征词 选择，文本的表示模型构建，以及文本的分类的算法。本章对这些基本环节都进行一 般的介绍，在下面的几章将会突出的论述其中的几个重要的部分：文本的特征词选择 算法和分类的算法。 第3 章特征词选择算法 第3 章特征词选择算法 对于文本分类的整体过程来说，特征词的选择是其中的比较重要的过程，特征词 选择的好坏，会直接影响文本表示模型的建立的好坏，因为文本特征词是模型建立的 维数的确定，并且这也会影响文本分类算法最终的分类效果，可见特征词的选择对于 文本分类来说至关重要p 5 | 。 特征词选择算法的大致流程如下： 首先对词袋中的词进行相关的属性值的计算【36 | ，比如互信息特征词选择法就绪 计算每个词的互信息。然后再将这些词按照计算出的属性值进行排列，再将排列好的 这些词选出最前面的n 个词，其中n 为要选词的个数，这n 个词即为特征词选择算 法的输出结果。 图3 - 1 特征词选择算法流程图 3 1 具体的特征选择算法的介绍 目前常用于中文文本特征词选择的方法有文档频率( d f ) 法、互信息( m i ) 法、信 息增益( i g ) 法、卡方估计( c h i ) 法等。下面将介绍这些经典的特征词选择算法。 3 1 1 文档频率选择法 文档频率选择法是这些文本特征词选择方法中较为简单的一种方法，所谓的文档 1 气 哈尔浜工程大学硕士学位论文 频率就是含有某个特征词的文档的频率数，该方法对文中的所有特征词对该参数进行 统计【3 7 1 ，然后确定一个频率阈值或者个数阈值，从而确定频率数较高的一些特征词 为所要选择的特征词。这种特征词选择方法原理简单，实现起来也比较容易，但是在 分类效果上差强人意，但是有很多文献对该方法进行了改进，分类效果在一定程度上 有所提高。 3 1 2 互信息选择法 在信息理论当中，互信息是表示两个信息单元之间的相互关联程度38 1 ，在文本 分类领域中，文本的单元词也可以说是一种信息，是文本中包含的信息，所以可以用 互信息来表示文本的特征词与文本的关系，这种关系可以被利用在文本的特征词的选 择算法上，于是就产生了互信息特征词选择算法。算法的大概思想是这样的，互信息 的公式【3 9 】为： 批札g 嚣 ( 3 - ，) 其中，m ( 厶q ) 为特征词f 与类别c ，的互信息，是衡量特征词与类别的相关程度 的，尸( ，i e ) 是类别e 与特征词同时出现的概率，也就是特征词在类别q 出现的总文档 数占所有的文档中的百分比jp ( c ) 是类别e 出现的概率，也就是类别e 的文档数占 所有的文档数的百分比。p ( ，) 是特征词出现的概率，也就是含有特征词f 的文档占所 有的文档的百分比。在实际应用中，会有很多的类别，对于每个特征词，要计算其与 每个类别的互信息，然后通过求期望值，或者最大值的方法来取得这个特征词与所有 类别的相关程度，这是值就是要进行总体比较以判别该特征词是否别划分为模型中的 特征词的依据。 3 1 3 信息增益选择法 信息增益的算法的理论基础也是来自于信息理论【4 ，该理论的思想是当一个词 出现在信息群中会增加该信息群所包含的信息量，通过这种思想来衡量一个信息对于 一个载体的重要性。在特征词的信息增益选择算法中，这种理论被用来进行文本的特 征词选择，来表征一个特征词对于一个文本文档或者一类文本文档的信息含量的增减 的重要性，来决定该特征词是否应该被划分为特征维数组当中。 信息增益的基本公式【4 2 1 是： 第3 章特征词选择算法 聊) _ 善州1 0 眺 ( 3 _ 2 ) + 尸( ，) 尸( jf ) l o g 尸( qf ) + 尸( f ) 尸( c ，if ) 1 0 9p ( q l ，) 扛1，- 1 公式中尸( cf ) 是所有含有特征词f 的文档中，类别为q 的文档占这些文档的百分 比。p ( qi ，) 是所有不包含特征词，的文档中，类别不是q 的文档占这些文档的百分 比。尸( c ，) 是类别c ，出现的概率，也就是类别c ，的文档数占总文档数的百分比。p ( ，) 是含有特征词，的文档的出现的概率，也就是含有特征词f 的文档数占总文档数的百 分比。尸( f ) 是不包含特征词f 的文档出现的百分比。 3 1 4 卡方统计值选择法 经过统计分析，文本中的特征词在语言分布中服从卡方分布【4 3 】，所以就可以利 用数理统计学理论中的卡方统计检验方法来对特征词进行分析，卡方统计检验是用来 度量数理统计量与其分部的相关程度，卡方统计量的值越大，那么这个数理统计量和 其分布的关系就越相关，讲这个原理应用在文本分类中，对于选定的特征词，其服从 于文本集总体的卡方分布，对其进行卡方统计检验，来衡量其与整个文本的相关程 度，来决定其是否为选定的特征词。卡方统计量的定义公式为： 倒( t 一) ：j 竺孥竺型型兰生 ( 3 3 ) 、。” ( 口+ c ) ( 6 + d ) ( 口+ 6 ) ( c + d ) 、7 其中，a 田( t ，e ) 表示特征词t 与类别e 的卡方统计量的值，口表示含有该特征词 t 并且属于类别q 的文档数，6 表示不含有该特征词t 并且属于类别e 的文档数，c 表 示含有该特征词t 并且不属于该类别的文档数，d 表示不含有该特征词t 并且不属于 该类别的文档数。 3 2 二元正态分离特征词选择法及其改进 根据文本中词在各类别中为标准正态分布的这种假设，二元正态分离算法利用 特征词在各个文本类中正态分布分位数之差【4 4 1 ，来决定该特征词是否被选中，其原 理与受试者工作特征曲线分析法类似。 3 2 1 受试者工作特征( r o c ) 曲线 受试者工作特征曲线分析法在医学检验领域是一种很强壮和有效的方法【4 5 】，其 哈尔滨工程大学硕士学位论文 大概原理可以理解为，对某个测试参数的阈值选择进行分析，如图3 2 所示，通过选 不同的参数阈值，可以确定不同的真阳性率、假阳性率、真阴性率、假阴性率。从而 来判定该参数阈值的选择会对本次医学检验的正确率、灵敏度和特异度的影响，再根 据待测样本的具体风险情况，来决定用哪个参数来确定该样本是否为阴性。 八 正繁缆 l 裘 ， t 舞嚣 l ! 觑j 二t 王 一，。争、。+ 、h - 。“一一 溅试誉熬 图3 2r o c 曲线分析法原理图 r o c 曲线分析中的真阳性率为已测样本中被判定为阳性而实际真为阳性的百分 比，假阳性率为已测样本中被判定为阳性而实际不为阳性的百分比，阴性率已测样本 中被判定为阴性而实际真为阴性的百分比，假阴性率已测样本中被判定为阴性而实际 却为阳性的百分比。而r o c 曲线分析中的正确率、灵敏度和特异度为效果评估参数 中的确定待测样本正确的评估方法的主要参数，因为根据所要分析的不同的情况，其 所能承受的风险程度也不，比如癌症的的晚期确定率，其误判的风险要求非常高，故 灵敏度参数高的方法是确定癌症晚期率的主选方法。而一般的病毒性感冒，则不需要 很高的灵敏度，只需要有一定的正确率即可，误判了也不会有什么风险。 一般r o c 曲线分析的方法如下，将r o c 曲线分析法中的某个阈值确定下来， 然后统计其中的真阴性、真阳性、假阴性、假阳性这四个参数，然后计算相应的灵敏 度和特意度，将这些不同的阈值所产生的分布参数记录下来，然后绘制r o c 曲线分 析图，以敏感度为纵坐标，以1 一特异性为横坐标，在该原理图中，因为该理论假设样 本是服从标准正态分布，并且真阳性率也就是正确肯定度等各个统计参数均已经确定 下来，这样，正常组和异常组的曲线相对位置也就会相应的确定了下来。这样可以直 观的解释不同的阈值所产生的各种风险度的不同。经过实际的检验，r o c 曲线分析 的有效性无论在理论分析还是在现实应用中均得到了很好的验证。 3 2 2 二元正态分离法算法原理 该算法假设文本中的每个词在文本中为标准正态分布，假定某个词t 从属于某个 肯定类，其在肯定类的所有文档中和非肯定类的所有文档中的概率分位数之差的绝对 第3 苹特征词选择算法 值b n s ( b i - n o m a ls e p a r a t i o n ) 为4 4 】： 胱= i 一( 缈) 一( 加) l f 3 4 ) 其中， t p r = t p p o s ，印r = 邱n e g ，p o s = 却+ m ，n e g ：t n 十邱，t p ( t r u ep o s i t i v e ) 为包含特 征词的肯定文档数，t n ( 缸u en e 垂i v e ) 为不包含特征词的否定文档数，邱( f a l s ep o s i 廿v e ) 为 包含特征词的否定文档数，m ( f a l s en e 垂i v e ) 为不包含特征词的肯定文档数。 。1三 八曲2 赤铲如 陆5 1 f ( x ) 为标准正态分布函数，- 1 ( x ) 为f ( x ) 的反函数，即f 。1 ( x ) 的值是标准正态 分布中概率x 的分位数。 该算法的具体原理可见图3 3 ，图中上部分的正态曲线为该词在肯定类中的分 布，其中t p 为正确肯定度t p