（计算机软件与理论专业论文）信息检索中的文本分类与降维技术研究.pdf

摘要 网络信息量的指数增长对信息检索提出了更高的要求。为方便信息检索，有 必要先对海量的电子信息按其内容加以分类。文本分类作为处理和组织大量文本 数据的关键技术，可以在较大程度上解决信息杂乱的问题，已经在信息检索、信 息过滤、搜索引擎、数字化图书馆等领域广泛的应用。 本文首先对文本分类领域的几个关键问题进行了描述，同时给出了典型的文 本分类过程及系统框架。然后，对文本的表示、相似性度量、权重的计算、文本 分类模型、降维技术以及评价标准作了详细的阐述。 若要有效地实现文本分类，维数约减是必不可少的，它不仅可以去除冗余和 噪声数据，节省存储空间，降低计算的复杂度，而且直接影响到分类器的设计及 分类的精度。它在信息榆索、机器学习和模式识别中也是至关重要的一步。本文 主要针对信息检索中的文本分类的降维技术进行了研究，主要工作包括以下几个 方面： 第一， 特征选择在文本分类领域里一直扮演着重要的角色。本文通过引 入特征项的权重，改进了原有的信息增益、期望交叉熵、文本证 据权特征选择方法的评估函数，提出了一种加权的文本特征选择 方法。 第二， 为了更好的利用权重信息，本文从特征项与类之间关系的角度考 虑，提出了一种基于模糊关系的文本特征选择方法。通过权值确 定隶属度，再用其隶属度构造了一个评估函数，用它来对原始空 间进行特征选择。 第三， 文本处理过程中的一个基础性问题是文本的表示和索引。本文从 判别能力上分析，提出了一种称为有监督的保局索引( s l p i ) 算 法，s l p i 目标是发现文本空间的局部结构，它是一种线性的维数 约减技术。并利用“核方法”将其推广到非线性的情况，即有监 督的核保局索引( s k l p i ) 。 关键词：文本分类，特征项权重，特征选择，有监督保局索引，特征提取 a b s t r a c t t h ee x p o n e m i a lg m 、v t ho f t l l en e t w o r ki b m m t i o nq u a n t i t yw a s p u tf o ，a r dt h e l l i g h e rr e q u e s tf o ri n f 0 邢a t i o nr e 仃i e v a i f o rt 1 1 ec o n v e n i e n c eo fi o n a t i o nr e 嫡e v a l ， i ti sn e c e s s a r yt oc a t e g o r i z et t l el a 唱en u m b e ro fe l e c t r o i l i ci n f 豳a t i o na c c o r d i n gt 0 i t sc o n t e n t s t e x tc a t e g o r i z a t i o ni st h ek e yt e c h n i q u et oh a i l d l ea 1 1 do r g a n i z ea 掣c a t d e a lo ft e x td a t a ，a i l d “c a i ls o l v et h eq u e s t i o no fd i s o r d e r e di n f b 舯a t i o nt os o m e e x t e n t nh a sb e e nw i d e l ya p p i i e dt om a i l yf i e l d ss u c ha si n f b r r n a t i o nr m i e v a l ， i n t o r m a “o nf i l t e r i n g ，s e a r c he n g i n e e r ，d i g i t a ll i b r a me t c i nt l l i sp 印e r ，w ed e p i c ts e v e r a lk c yq u e s t i o n smt h ef i e l do ft e x tc a t e g o r i z a t i o n ， a n dr e p r e s e n tt 上l ep r o c e s so f t y p i c a lt e x tc a t e g o r i z a t i o na sw e l la ss y s t e mf m m e 、v o r k a l s o ，i t sd e s c r i b e do ft e x tr e p r e s e m a t i o n ，s i m i l 撕t ym e 埘c ，w e i g h t sc a l c u l a t i o n ， c l a s s i f i c a t i o nm o d e l ，d i m e n s i o n a l i t yr e d u c t i o na n de v a l u a “o nc r i t e r i a d i m e n s i o n a l i t y r e d u c t i o ni s i n d i s p e n s a b l e t o e 仃e c t i v c l yp e 而m t e x t c a t e g o r i z a t i o n i tn o to n l yc a i lg e t “d eo fr e d u n d a n c ya n dn o i s e ，s a v es t o r a b l es p a c e ， r c d u c e 血ec o m p l e x i t yo fc o m p u t a t i o n ，b u ta l s od i r e c t l yi m p a c tt l l e d e s i g na n dt h e a c c u r a c yo fc l a s s i f i e tm o r e o v e r ，“i sm o r ei m p o r t a l l tf o ri n f o n a t i o nr e m e v a l ， m a c h i n e1 e 枷i n g ，a i l d p a t t e mr e c o g n m o n 1 1 l e p a p e rm a i n l y r e s e a r c h e st h e d i m e n s i o n a l i t yr e d u c t i o nt e c h n i q u eo ft e x tc a t e g o r i z a t i o ni ni n f o r n l a t i o nr e t r i e v a l 0 u r w o r k sm o s t l yi n c l u d et h ef 0 1 l o w i n ga s p e c t s ： 1 f e a t u r es e l e c t i o ni ss t i l lp l a y i n ga ni m p o r t a mr o l e i nt h ef i e l do ft e x t c a t e g o r i z a t i o n t h eo r i g i n a lm e 血o do ff e a t l l r es e l e c t i o ns u c ha si n f o m l a t i o n g a i n ( i g ) ，e x p e c t e dc r o s se n t r o p y ( e c e ) ，w e i 曲to fe v i d e n c ef 研t e x t ( w e t ) i si m p r o v e db yi m p o r t i n gt e n nw e i g h t s an o v e lf e a t u r es e l e c t i o n m e t l l o dw i t ht e m lw e i 曲t si sp r o p o s c d 2 f o rm o r ee f f e c t i v e l yu t i l i z i n gt e r n lw e i g h t s ，劬mt h ev i e w so ft h er e l a t i o n b e t w e e nt e ma l l dc l a s s ，t l l em e t h o do ft e x tf e a t u r es e l e c t i o nb a s e do nm z z y r e l a t i o ni sp r o p o s e d g i v e nt h ed e 掣e eo fm e m b e r s 上l i pi nt e m so ft e m l w e i 曲t s ，a i le v a l u a t i o nf l l n c t i o ni sc o n s m l c t e db yi t t h u s ，、v ec a nm a k ef u u u s eo f i tf o rf e a t i l r es e l e c t i o ni no r i g i i l a lf c a t u r es p a c e 3 t e x tr e p r e s e n t a t i o na n di n d e x i n gi saf o u n d a t i o n a l p r o b l e m i nt e x t p r o c e s s i n g f r o mt h ep o i mo fd i s c r i m i n a t i v ep o w e r ，i nt l l ep a p e ran e w a l g o r i t h m c a l l e d s u p e r v i s e dl o c a l i t yp r e s e r v i n gi n d e x i n g( s l p i )i s p r o p o s e d s l p ia i m st od i s c o v e rt h el o c a ls t r u c t u r eo f t e x ts p a c e n sal i n e a r d i m e n s i o n a l i t yr e d u c t i o nt e c h n i q u e m o r e o v e r ，w ec a n u s ek e m e lm e t l l o dt o g e n e r a l i z c “t on o n l i n e a rc a s e ，i e s u p e n r i s e dk e m e ll o c a l i t yp r e s e r v i n g i n d e x i n g ( s l a ，p i ) k e y w o r d s ： t e x tc a t e g o r i z a t 溉t c r mw e i 出s ，f e a t u r es e l e c t i o i l s u p e r v i s c d l o c a l i t yp r e s e r v i n gi n d e x i n g ，f e a “l r ee x t i j a c t i o n 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： ( 注：手写亲笔签名) 学位论文使用授权说明 甄，毛，龙 知0 3 年o5 旯，器b 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ：亟! 三蕉 知。旁年口多月，牙日 ( 注：手写亲笔签名) 河海大学硕士学位论文第一章绪论 第一章绪论 1 1 研究目的及背景 网络信息量的指数增长对信息检索( i n f o a t i o nr e t r i e v a l ，i r ) 提出了 更高的要求。一方面，人们希望获得越来越多的信息：另一方面，在大量的信息 中，快速有效地检索到所需要的信息变得有些力不从心。因此，迫切需要对大规 模文本信息进行有效的处理。为方便信息检索，有必要先对海量的电子信息按其 内容加以分类。文本分类作为处理和组织大规模文本数据的关键技术，可以在较 大程度上解决信息杂乱的问题，也是提高其他文本处理功能和质量的有效手段。 通过文本分类，人们可以按类别进行文本存贮、检索和进一步处理。而且，许多 文本处理问题都可以归结为文本分类。例如：信息检索可以看成是文本与查询是 否相关的二分类问题；文本过滤也是一个二分类问题。 文本分类是对用自然语言写成的文本按照预先定义的主题类别进行分类。可 以应用到任何需要文档管理或信息分发的任务中，在文本分类的基础上，可以更 好地进行信息的检索和信息的个性化服务。传统的文本分类工作是由特定领域的 专家人工完成的，这种人工分类方法需要消耗大量的时间和精力，特别是随着文 本信息量的增加，人工方法已经很难满足分类的需求，因此利用计算机对文本进 行自动分类的研究同益受到重视。自动文本分类的研究最早可以追溯到二十世纪 六十年代m a r o n 的研究工作。从那时起，该技术便逐渐应用到信息检索、文本组 织、文档过滤等方面。二十世纪八十年代之前，自动文本分类中主导地位的一直 是基于知识工程的分类方法，即由专业人员人工编写分类规则柬指导分类，其中 晟著名的系统是卡内基梅隆大学为路透社开发的c o n s t r u e 系统。基于知识工程 的方法存在分类规则制定困难、推广性差的缺点，因此很难大规模推广。二寸。世 纪九十年代以来，随着信息存储技术和通信技术的迅猛发展，大量的文字信息开 始以计算机可读的形式存在，以统计理论和机器学习为主的信息分类技术逐渐取 代了基于知识工程的方法，成为自动文本分类的主流技术“1 。 1 2 信息检索的概念 信息检索广义上是指将信息按一定的方式组织和存储起来，并根据用户的需 要找出相关信息的过程和技术，又叫信息存储与检索。狭义的信息检索则仅指该 过程的后半部分，即从某一信息集合中找出所需信息的过程，相当于人们通常所 说的信息查询。信息检索涉及数据库技术、图书和情报科学、人工智能、自然语 河海大学硕士学位论文 第一章绪论 言处理、机器学习等众多知识和学科领域。信息检索的主要目的是对信息表示、 存储与组织，使用户更容易得到所需要或者感兴趣的信息。信息检索的过程可以 简单地描述为：用户提交查询请求，信息检索系统根据该查询条件在文档集中检 索出与其相关的文档子集，对这些相关文档子集中的文档按照与查询条件的相关 性进行排序，最后返回给用户有序的文档子集。 1 3 文本分类对检索的意义 自动文本分类与信息检索技术是相辅相成，密不可分的。自动文本分类技术 的实现和提高使得信息检索的精确度和速度得以相应提高，信息检索也为自动文 本分类技术提出了更高的要求。如网上信息量的增大，内容的增多为自动文本分 类的研究提出了新课题。 自动文本分类的目的就是对文本集进行有序的组织，把相关或者相近的文本 组织到一起。作为一种知识的组织工具，它为信息检索提供了更高效的搜索策略 和更有效的搜索结果。高效性在于用户可事先确定查询的可能类别，以减少进一 步查询的文本数量。有效性在于相似的文本可能与相同的查询有关，于是查询的 查全率和查准率得到了提高。如今，网络信息量的日益猛增对高效、快速地信息 处理提出了更高的要求。这为自动文本分类的研究施展其信息处理的作用提供了 更大的舞台”1 。 1 4 本文的主要工作 自动文本分类技术首先要对训练集中的文本进行表示，现在普遍采用的是向 量空间模型( v e c t o rs p a c em o d e l ，v s m ) 。v s m 表示方法的一个严重的问题，就 是维数过高，使文本分类的性能急剧下降，因此迫切需要通过特征选择和特征提 取的维数约减技术来优化文本的向量表示，以提高文本分类的性能。本文在此基 础上，重点作了以下几个方面的工作。 ( 1 ) 鉴于已有的文本特征选择方法只利用了文本数的信息，没有考虑特征 项权重。而单词被赋予一个权值表示其在文本中的重要性，所以词的权重也应当 作为特征选择的一项内容。基于这样的考虑，我们把权重引入到文本的特征选择 之中，并对已有的方法进行了改进，提出了一种加权的文本特征选择方法。在 r e u t e r s 一2 1 5 7 8 标准数据集上进行了测试，实验结果说明所提出的方法是可行的 和有效的。 ( 2 ) 本文在给出两种权重计算方法的基础上，从特征项与类之间模糊关系 的角度出发，通过权值确定隶属度，再用其隶属度构造了一个评估函数，用它来 对原始特征空间进行特征选择。为了测试提出方法的效果，选用k n n 分类器，在 2 河海大学硕士学位论文第一章绪论 r e u t e r s 一2 1 5 7 8 标准数据集上进行了实验，结果表明该方法能够挑选出有用的特 征，并且提高分类的精度。 ( 3 ) 信息检索领域里，对原始文本进行表示以后，面临特征空间的维数非 常的高，然而，我们有理由相信数据的固有维数是很低的。可以考虑特征提取， 在低维的特征空间中表示数据。本文提出了一种有监督的保局索引( s u p e r v i s e d l o c a l i t yp r e s e r v i n gi n d e x i n g ，s l p i ) 算法，并且利用“核方法”将其推广到 有监督的核保局索引( s u p e r v i s e dk e r n e ll o c a l i t yp r e s e r v i n gi n d e x i n g ， s k l p i ) 。k n n 作为文本分类器在r e u t e r s 一2 1 5 7 8 数据集上对s l p i 和l s i 进行了 测试验证。实验结果表明s l p i 比l s i 具有更强的判别能力。 1 5 论文组织 本文各章节的内容安排如下： 第一章：绪论，简单介绍了自动文本分类研究的意义，信息检索的概念以及 文本分类与信息检索的关系。阐述了本文的主要工作。 第二章：文本分类与降维的相关技术，概括地描述了文本分类的定义、过程 及系统框架。详细地介绍了文本预处理、文本表示方法、分类模型、降维技术和 评价标准等几个部分。 第三章：基于权重的文本特征选择方法，提出了一种加权的文本特征选择方 法和基于模糊关系的文本特征选择方法。 第四章：基于有监督保局索引的文本分类，提出了一种有监督保局索引的文 本特征提取方法，并将其推广到非线性的情形。 第五章：总结与展望，对全文进行了总结，并对未来的工作进行了展望。 河海大学硕士学位论文第二章文本分类与降维的相关技术 第二章文本分类与降维的相关技术 2 1 文本分类 所谓文本分类( t e x tc a t e g o r i z a t i o no rt e x tc l a s s i f i c a t i o n ，t c ) 就是 由计算机提取文本的特征项，根据它的内容，将其自动分类到预先确定的一个或 多个类别的过程。文本分类属于有监督机器学习( s u p e r v i s e dl e a r n i n g ) 。文 本分类问题的形式化定义如下： 定义2 1 ：给定训练样本集合d = 碣，以，以 和已知类标号集合 c = q ，乞，吒 ，计算从样本集合到类标号集合的映射函数：厂：d 卜2 。，即 样本集合中的4 分配到某一个类别或多个类别c ，中，有 o = z i ( z ) = 勺，吐d ，1 f n 映射函数厂称为一个分类器( c l a s s i f i e r ) ，它体现出映射到类标号的幂集上。 即当文本只属于一个类别时，称无兼类分类问题。当文本属于多个类别时，称为 有兼类的分类问题。 2 1 1 文本分类过程 自动文本分类过程中包含了许多的技术环节，一般来讲，大致需要以下几个 步骤： ( 1 ) 获取训练集 ( 2 ) 文本预处理 ( 3 ) 文本的表示 ( 4 ) 降维技术，也称维数约减 ( 5 ) 选择分类方法 ( 6 ) 性能评估模型 其中，维数约减和分类方法是主要的关键的技术环节。通过约减维数，文本 中最具代表性的那组特征被选中，同时在保证分类精度的基础上使特征的维数得 以降低。图2 1 给出了一般的自动文本分类系统框架嗍。 4 河海大学硕士学位论文第二章文本分类与降维的相关技术 2 1 1 _ l 文本预处理 图2 1 文本分类系统框槊 进行文本分类前，首先需要对文本进行预处理。文本预处理主要包括：去除 如h t m l 文档的一些t a g 标记、去除停用词( s t o pw o r d s ) 、英文词根还原、中文 分词、词频统计、权重计算等等。其中，英文文本的预处理主要是词千提取，而 中文文本的预处理主要是分词。文本预处理最终目的是提取出能够充分代表文本 内容的特征项( t e r m ) 。特征项( 索引项) 用来刻画文本的内容或主题，通常可 以是字、词或词组等，它们的出现具有一定的规律，对文本或文本类有一定的代 表性。 2 1 1 2 文本的表示 文本的形式化表示是文本分类的基础性问题。知识表示始终是知识处理的主 要瓶颈之一，特别是在以自然语言为研究对象的知识处理和知识获取问题中更是 如此。1 。在信息检索领域，比较有代表性的文本表示模型有概率模型 ( p r o b a b i l i s t i c l o d e l ) ，白尔模型( b o o l e a nm o d e l ) ，向量空间模型( v e c t o r s p a c em o d e l ，v s m ) 等等。目前，在文本分类中，最常用的文本表示模型是s a l t o n 等人提出的向量空间模型。它在信息检索、搜索引擎、模式识别等许多领域里都 有广泛的应用，并取得了很好效果。在v s m 中，文本被看作是由文本中的一组正 交的词条丁( 乃r m ) 构成的特征向量d = ( ，f 2 ，0 ) 7 ，一个文本向量就是一个词袋 ( ab a go fw o r d s ) 。这里f 为词条( 特征项) f 的权重，表示该词条在文本中的 重要程度。如果有”个文本，则可以构成一个二维的研圩阶的矩阵一，形式化 描述如下： 河海大学硕士学位论文第二章文本分类与降维的相关技术 爿一三 三主j i 警：_ 一至 2 ，1 1 ，3 相似性度量 定义2 3 ：相似度( s i m i l a r i t y )当文本被表示为向量空间模型时，借助于向量 就可以计算任何两个文本吐和d ，之问的相似程度5 砌( 4 ，d ，) 。 相似度的计算方法有很多，在信息检索里，常用的有以下几种： ( 1 ) 内积( i n n e rp r o d u c t ) ：j 砌( z ，嘭) = 珥嘭= ，文本之间相 i 互匹配的特征项的权重乘积之和。也可写成k n d ，i 。其中，表示文本砖中的 索引项| j 的权重，口。表示文本d ，中的索引项后的权重。内积主要用于有多少索 引项匹配成功，而不计算有多少索弓l 项匹配失败。对长文本有利，因为长的文本 包含大量独立的特征项，每个特征项均多次出现。 ( 2 ) 余弦( c o s i n e ) 相似度：s 咖( z ，t ) 弦相似度计算两个向量之间的夹角，它是利用向量长度对内积进行归一化的结 果，如图2 3 所示。也可写成 6 每尘扩 嘭一阮 谚一引 俐丽 河海大学硕士学位论文第二章文本分类与降维的相关技术 田2 3 文档之问的亲弦相似度 ( 3 ) d i c 繇孰咧卜黼2 2 - 靠 蓉面7 li 也可写成 o v e 山一妒蒜= 毒舞一 成瑞 ( 5 ) m c a r 繇热州圳2 赫 2 瑟再宝孑丽 j a c c a r d 系数是信息检索经常采用的一种相似性度量方法，并取得了很好的效 舭一写成矧= 抵撤槲它来一似 矩阵，并作为文本之间相似的权重。 2 1 1 4 权重的计算 定义2 4 ：特征项的权重( 死删耽动坫)对于含有聊个特征项的文本 d = ( ，f 2 ，) 7 ，特征项常常被赋予一定的权重w f ，表示它们在文本中的重 要程度，即d = ( ，；屯，w 2 ；f 。，0 ) 7 ，简记为d = ( w l ，w 2 ，) 7 。这时说特征 项t 的权重为w 。 权重的计算方法有很多，如概率的方法，信息论的方法等等。但一般都是基 t t n 一+ 陋一hb 河海大学硕士学位论文 第二章文本分类与降维的相关技术 于以下两种考虑： ( 1 ) 一个单词在某篇文档中出现的次数越多，则对识别文档的贡献越大。 ( 2 ) 一个单词在不同文档中出现的次数越多，则它区分不同文档的能力越 弱。 权重可以分为两大类型：局部权重( l o c a lw e i g h t ) 是基于每篇文档内的特 征项权值和全局权重( g l o b a lw e i g h t ) 是基于整个文档集上的特征项权值。下 面，我们介绍几种常见的权重计算方法。先作符号约定：表示特征项( 词条) f 在文档，中的权重，巩表示特征项f 在文档，中的出现次数， 是总文本数。 ( 1 ) 局部权重 词频权重( f r e q u e n c yw e i g h t ) 是一种简单而有效的权重计算方式，如公式 ( 2 1 ) 所示。这种方法基于的思想是：特征在文本中出现次数越多，它就越重 要。用词频作为权重的特征向量被称为词频向量( f r e q u e n c yv e c t o r ) ，它通常 作为文本标引的第一步。根据词频向量，可以很方便地计算其他权重。 = ，；i ( 2 - 1 ) ( 2 ) 全局权重 文档频率( d o c u m e n tf r e q u e n c y ) 是整个文档集合中出现特征项f 的文档 数目。词频权重没有考虑词的文档频率信息。逆向文档频率彬( i n v e r s e d o c u m e n tf r e q u e n c y ) 是信息检索领域中计算词与文档相关权重的经典计算方 法，在信息检索中占据了很重要的位置。它的核心思想是，在大多数文档中都出 现的特征项不如只在小部分文档中出现的特征项重要，并且能够弱化一些在大多 数文档中都出现的高频特征项的重要度，同时增强一些在小部分文档中出现的低 频特征项的重要度。由于同时考虑了矿和渺的信息，所以称为矿一彬算法。 矿一i 矿权重：以词的逆向文档频率对词的词频作加权处理；即认为词在某 篇文本中出现的次数越多，越重要；词在很多的文本中都出现，越不重要。计算 公式如式( 2 2 ) 。= 蛎+ f 够，其中磁= l 。g z 昙 吩2 孵籼g z 荔 池2 ) 船1 c 权重：矿一巧权重没有考虑文档长度的不同，对词的权重的影响。对 式( 2 2 ) 进行c o s i n e 归一化处理后得到式( 2 3 ) ，可以使每个文本的特征向量 河海大学硕士学位论文第二章文本分类与降维的相关技术 都变成长度为1 的单位向量。 嘞2 纠荔 ( 2 3 ) 三z c 权重：也是矿一c 矿权重的一种变形形式；其计算方式没有直接使用词 条的词频信息，而是采用了一种词频的变换：对词频取对数。经过这样的处理， 可以降低词频大小的差异对权重计算的影响。 ( 2 4 ) 三昭一点h 护咧权重：来源于信息论中熵的概念，如公式( 2 5 ) 所示。使用 对数熵模型的目的是降低高频词的相对重要性，而给那些用来区分文档的词一个 较高的权重。 q _ ( 1 。9 2 ( 1 螂) ( 1 + 击( 莩驴蝎) ) ( 2 5 ) 其中岛。厶7 莩石，南( 莩岛l o g ：毋) 指特征的熵。 2 1 2 文本分类模型 文本分类问题，一直是信息检索领域研究的基础。目前，已经提出了许多基 于统计理论和机器学习的文本分类模型。其中比较著名的有：r o c c h i o 分类器“， k 近邻( kn e a r e s tn e i g h b o r ，k n n ) 分类器。7 “，朴素贝叶斯分类器( n a i v e b a y e s ，n b ) “4 1 ，决策树( d e c i s i o nt r e e ，d t ) “。1 ，线性最小二乘拟合( l i n e a r l e a s ts q u a r e sf i t ，l l s f ) ，神经嘲络( n e u r a ln e t w o r k ，n n ) “1 ，支持向量 机( s u p p o r tv e c t o rm a c h i n e ，s v m ) “1 等等。文献 2 对几种常用的文本分类 算法进行了分析和比较。实验结果表明，支持向量机，k 近邻，朴素贝叶斯是三 种比较好的文本分类算法，其中s v m 具有最高的分类精度但速度最慢，n b 具有 最高的分类速度但精度最低，k n n 的分类精度略低于s v m 但选择参数少。 ( 1 ) r o c c h i o 方法 r o c c h i o 分类器是一种p r o f i l e b a s e d 的文本分类方法。它是基于向量空问 9 扣j 海大学硕士学位论文第二章文本分类与降维的相关技术 模型，为每个类型c 建立一个原型( p r o t y p e ) ，即类型向量： 砭= ( 。，w 2 。，) 7 ，其中，为特征在类别c 中的权重。采用 r o c c h i o 公式( 2 6 ) 。在式( 2 6 ) 中，k 的权重由两部分组成：一部分为正样 本贡献的权重，另一部分是负样本贡献的权重。它的基本思想是：类型向量应该 尽量靠近正样本，远离负样本。 计算步骤：将文本表示为向量空间中的一个向量，按照训练集中正例的向量 赋予j 下的权值，反例的向量赋予负的权值，相加平均计算每一类的中心。对于属 于测试集的文本，计算它到每一个类别中心的相似度( 通常采用余弦相似度) ， 将此文本归类于与其相似度最大的类别。其训练过程及分类过程可以描述如下： a ) 训练时：每个类别由一个类中心向量来表示： 口屹+ 卢班一y 丛 ( 2 6 ) = 口吃+ 卢兰生曼辽一y 兰型竖竺 ( 2 6 ) 初值屹置o ，为特征气在训练文本4 中的权重；表示正例训i 练集合中文本 个数，行为总文本数。a o ，控制上一次计算所得到的m k 对本次计算产生的影 响；o ，0 ，且+ ，= l ，是调节正、负样本对类型向量贡献大小的参数“。 为了强调正样本的作用，抑制负样本的作用，在实现时，通常增大参数口，减小 参数y 。 b ) 分类时：对于某个文本，它和哪个类中心最近，则认为它属于哪个类。 以呦一c d i2 捻 隰7 ) 该分类器的优点是容易实现，分类速度快，与其他分类器相比，分类效果也 很有竞争力“。”1 。如果对那些类间距离比较大而类内距离比较小的类别分布情 况，r o c c h i o 方法能达到较好的分类精度；但对文本集分布很分散，或出现多峰 值分布时，分类效果不理想1 。 ( 2 ) k n n 方法 k n n 也称为l a z yl e a r n i n g ( 懒惰学习) 或c a s e - b a s e dl e a r n i n g ( 基于实 例学习) 。它是统计模式识别、信息检索等领域中被广泛应用的一种经典的分类 方法。在四十多年之前，它就很早的被应用在文本分类领域，并取得了非常好的 结果。 k 近邻分类器的原理简单直观：给定一个待分的测试文本，将它和训练集中 1 0 河海人学硕士学位论文第二章文奉分类与降维的相关技术 所有已分好类的文本进行比较，找出最相似的k 篇文本，根据这k 篇文本的类别 来决定待分类文本的类别。而最相似的k 篇文本和待分文本的相似度作为近邻文 本所在类的类权重，决策函数定义如下： l ( oi 膏) = 鼢( x ，) ( 2 8 ) j = 1 其中，矿( c ，l x ) 表示测试文本x 属于类c ，的权值，权值越大，则认为文本向量x 属 于类c ，的概率越大。) ，f o ，l 是类别属性，表示文本x ，是否属于类c ，如果属 于类c ，则虼= 1 ，否则= o 。跏”( x ，t ) 表示测试文本和训练文本的相似度， 可以使用欧式距离，内积或者余弦相似度，以及2 1 1 3 小节所给出的相似性度 量方法。 k 近邻分类器的一个关键问题是参数k 的选取。如果k 的取值过小，不能充 分体现测试文本的特点，而k 的取值过大，会造成噪声增加，导致一些和测试文 本实际上并不相似的文本也被包含进来，使得分类精度降低。目前，k 值的确定 并没有很好的方法，一般是先给定一个初值，然后根据实验测试结果调整k 值。 k n n 不需要进行分类器的学习，没有离线训练阶段，所有的计算都是在分类 时进行的，这也是称它为懒惰学习的原因。因此，分类时计算量较大，实时性不 好，但是在分类性能上，是效果最好的分类器之一。而且，k 近邻分类器可以解 决文本分布出现多峰值的情况，分类性能稳定”。本文第3 、4 章的实验就采用 了k n n 作为文本分类器。 ( 3 ) n a v eb a y e s 分类方法 n a i v eb a y e s 分类器( 简称n b ) 是一个简单而又非常有效的分类器。它是一 种典型的基于概率统计的分类器，其数学基础是贝叶斯定理。主要思想就是计算 在给定一待分类文本的条件下对各个类别的条件概率。它将文本分类看作是应用 贝叶斯公式对待分文本所属类别的条件概率估计。这个概率估计的关键是，根据 训练集将类别的先验概率转化为后验概率。 地；兰坐型生 ( 2 9 ) p ( c ll 乃) 。兰戈署卫 2 9 其中，p ( c ) 为类t 的先验概率；p ( d ，ic 。) 为给定类q 下文本d ，的条件概率； p ( d ，) 为文本d ，的概率。p ( d ，) 对于所有类均为常数，因此，式( 2 9 ) 可以简化 为式( 2 1 0 ) p ( qi d ，) 虻p ( q ) p ( d ，i q ) ( 2 1 0 ) 河海大学硕士学位论文 第二章文本分类与降维的相关技术 朴素贝叶斯分类器的假设前提是：特征对于给定类的影响独立于其他特征。 对文本分类来说，它假设各个单词f ，和0 之间相互独立，如图2 4 所示。由特征 独立性假设，可得式( 2 “) 。 圉2 4 朴素皿叶斯结构 m 尸( 以h ) = 尸( w l ，w 2 ，w 唧旧) = 兀，( h ) ( 2 1 1 ) = l 为了避免p ( l q ) 等于o ，可以采用拉普拉斯概率估计，计算公式如下： 讹= 塑笺学“制 弦蚴 式中，l m l 为特征项的个数，i d f k ii 为类q 中出现特征项雌的文本数，n 。为训练集 中属于类c 的文本数。 球弘掣攀“嚣 汜 式中，i c i 为训i 练集中类的个数，n 为训l 练集中总文本数。 实际上，计算尸( d ，i c ，) 和p ( c 。) 的过程就是建立分类模型的过程，或者说学 习的过程。最后，朴素贝叶斯分类器选择条件概率最高的那个类别为该文本所属 的类别，即式( 2 1 4 ) 。 p ( ol d ) = m a x p ( ql d ) 尸( q ) f = l ，2 ，七 ( 2 1 4 ) 在实际情况中，特征的独立性假设是不成立的，但是基于该假设的贝叶斯分 类器训练时问小，且具有较好的分类效果。因此在文本分类中得到广泛地应用。 ( 4 ) 神经网络( n n e t ) 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) 是人工智能中比较成熟 的技术之一，按照k o h o l e n 给出的定义：它是由具有适应性的简单单元组成的广 泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交 互反应。组成神经网络的单个神经元的结构简单，功能有限，但是，由大量神经 元构成的网络系统可以实现强大的功能。神经网络具有信息分布存放、运算全局 1 2 河海大学硕士学位论文 第二章文本分类与降维的相关技术 并行、处理非线性等特点，适用于学习一个复杂的非线性映射，在信息检索、模 式识别、计算机视觉、智能控制、知识处理、机器学习等领域都有着广泛的应用 背景。 根据网络结构和学习算法的不同，神经网络可分为前馈神经网络、自组织特 征映射及反馈神经网络。在文本分类领域中，常用的人工神经网络模型是采用误 差反传算法或其变化形式的多层感知机网络b p 网络，图2 5 显示的就是一 个单隐层的b p 网络。 雕 k n 口 一_ _ _ 一， o ， 构a 展 隐层 辅出甚 图2 5 单隐层b p 罔络磊型 国2 6 口= l o g j 喀( 疗) 网络中的节点均按照层次结构组织，每一层的节点均与下一层的所有节点相 连接，节点之间有连接权值，每个节点也都有一个激活函数。b p 网络中使用的 激活函数是l o g s i 鲫o i d 函数。图形是s 一形的，如图2 6 所示。它是严格的递 增函数，在线性和非线性行为之间显示出较好的平衡，函数定义为： ，( 2 r 南，并且厂( x ) = ，( 功i 【1 一，( 曲】 b p 网络的学习过程由j 下向计算传播和误差反向传播组成，通过迭代地处理 一组训练样本，将每个样本的理想输出与实际输出作比较，将比较结果反馈的网 络的前层单元中，修改单元之间的连接权值，使得理想输出和实际输出之间的均 方误差达到最小。 b p 算法描述如下： 1 初始化以一个随机分布随机地挑选连接权值和阈值； 2 正向计算设一个训练样本是( x ( ”) ，y ( 叻) ，输入向量x ( 疗) 指向感知节 点的输入层和期望响应向量y ( 胛) 指向计算节点的输出层。不断地经由网络一层一 层地前进，可以计算网络的净输入和激活函数。在层f 的神经元，的净输入 ”甜：，) ( 胛) 为式( 2 1 5 ) ， 删乳h ) = 彬( 以) 矿”( ) ( 2 1 5 ) l ；1 河海大学硕士学位论文 第二章文本分类与降维的相关技术 这里一( 玎) 是迭代订时前面第z 一1 层的神经元f 的输出，而w ：( 玎) 是从第 ，一l 层的神经元f 指向第z 层的神经元，的权值。如果神经元，在输出层( 即，= 上， 这里的工为网络的深度) ，令y ；。= d ( 聆) ，计算误差f ，( ，z ) = ，j ( n ) 一o j ( ”) ，r ，( 聍) 是 理想输出向量f ( n ) 的第，个分量，o ( 疗) 是实际输出向量y ( 功的第，个分量。 3 反向计算计算网络的j ( 即局部梯度) ，定义为： i e ( 聆) ( h “尹( 胛”对输出层上的神经元， 彰。( ”) 2 力( 刀。& ) ) 至，+ - o ) 皑圳( ) 对隐含层，的神经元f 2 1 6 l 根据广义d e l t a 规则调节网络第，层的连接权值： w ：研+ 1 ) = w 字( + 口【w ? 一1 ) 】+ 玎占；”( n ) _ y ；“( 栉) ，叩为学习率，口为 动量常数。学习率和动量常数随着训练迭代次数的增加而逐步减小。 4 迭代通过新的一回合样本，重复第3 和第4 步，直到满足停止条件。 ( 5 ) 支持向量机( s v m ) 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 最先由俄罗斯人v a p n i k 和他 的合作者在1 9 9 5 年提出的，主要用于解决二分类模式识别问题。它是基于小样 本学习、结构风险最小准则( s t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l e ) 等统 计学习理论的一种全新的统计学习方法”。它通过使结构风险最小，保证了分类 器的泛化能力最好。1 9 9 8 年，j o a c h i m s 将支持向量机引入到文本分类中，取得 了非常理想的分类效果。于是，用支持向量机进行文本分类被大量地研究。 对于文本分类的二分类问题，就是要找一个最优超平面，将这两类文本分开。 对于线性可分的情况，在二维空间上的最优超平面如图2 7 所示。 图2 7 支持向量机中的最优超平面 离最优超平面最近的向量称为支持向量。最优超平面是由支持向量决定的， 与非支持向量无关。所以，s v m 的复杂性取决于支持向量的数目。若要找到最优 超平面，则需要解决下面的约束优化问题： 1 4 河海大学硕上学位论文第二章文本分类与降维的相关技术 定义2 5 ：给定训练样本集：( 而，y 。) ，( x ：，娩) ，( ，儿) 工。冠”，y 。 + l ，一l ， ”= 1 为样本的类别标记，t 为相应的样本，找到权值向量w 和偏置6 的最优值 使得它们满足式( 2 1 7 ) 的约束条件： 儿 w 置+ 6 ) 一1 o ，f = l ，2 ，- ，疗 ( 2 1 7 ) 并且权值向量w 最小化代价函数如式( 2 1 8 ) 中( w ) ：钏2