（计算机软件与理论专业论文）基于潜在语义索引的文本分类技术的研究.pdf

东北大学硕士学位论文摘要 摘要 在过去的十几年中，将文本自 动地归于事先定义好的类别的技术获得了长 足发展，这主要是因为以数字形式存储的文档的数目急剧增长，引起了将它们 进行有效组织以便于利用的需求。这一过程主要是用机器学习的方法，在事先 构造的训练语料上学习各个类别的特征，自 动构建出一个分类器。 传统的文本分类方法都是用词作为特征来构建的，而用词来表示文本的特 征虽然简单直观，但有其固有的局限性，主要有包含的类别信息太少，维数过 高从而造成数据稀疏等两个问题。用特征串作为类别特征可以在一定程度上解 决第一个问题，但又会进一步加剧数据稀疏问题。对第二个问题的解决方法一 般是进行降维，去掉一些对分类结果没有影响或影响很小的特征，用剩余的特 征 来表示文本。 根据结果特征的 特点，降维方法可以分为( i ) 特征提取:结果是 原 始特征的子集; ( 2 ) 特征抽取:结果不是原始特征的 子集。潜在语义索引是一 种特征抽取的方法，它可以将特征从词空间映射到语义空间，同时解决这两个 问题。 潜在语义索引能够预知查询中真正“ 暗含” 的查询项和可以应用到文本中的潜 在语义关系， 它能从原始的特征中提取出正交基， 这些正交基的数目 比 原始的 特 征数目 要少很多，并且可以用它们来表示原始的特征，这样就将原来的高维空 间 压缩到低维的特征空间去，一般称之为语义空间。 传统的用来进行潜在语义索引的方法是奇异值分解，它的效果很好，但运 算速率漫，转换后的矩阵是三个双精度的稠密矩阵， 所需的存储空间太大。另 一种方法是半离散矩阵分解，它的运算速度很快，转换后的矩阵是两个可以 用。 、i 和一 1 来表示的矩阵和一个单精度的 对角矩阵， 所需要的存储空间大大降 低，但这种方法的效果有所下降。 本文主要研究了把潜在语义索引用于文本分类的效果，对可能产生影响的 因素进行分析，主要考查了不同的特征选取方法和权重计算方案对潜在语义索 引的 影响。我们还提出了 一个潜在语义索引的改进模型， 这个模型对提高半离 散矩阵分解的效果有很明显的作用。 我们在中英文两个不同的语料上进行了试验，用k n n的方法来构造分类 器。试验结果表明，特征选取方法和权重计算方案都对分类效果有明显的影 响，但不同的语料需要不同的方法，没有哪一种方法适用于所有的情况。试验 东北大学硕士学位论文摘要 还表明，我们的方法对半离散矩阵分解的效果有明显的提高，可以达到与奇异 值分解相当的水平。 关键词:文本分类，潜在语义索引，奇异值分解，半离散矩阵分解 东北大学硕士学位论文ab s t r a c ab s t r a c t t h e a u t o m a t e d c l a s s i fi c a t i o n o f t e x t s i n t o p r e - s p e c i fi e d c a t e g o r i e s h a s g a i n e d a r a p i d p r o g r e s s i n t h e l as t t e n y e a r s , d u e t o t h e i n c r e a s e d a v a i l a b i l i t y o f d o c u m e n t s i n d i g i t a l f o r m a n d t h e e n s u in g n e e d t o o r g a n i z e t h e m . m a c h i n g l e a rn in g t e c h n o lo g i e s a r e u s e d i n t h i s p r o c e s s t o a u t o m a t i c a l ly b u i l d s a c l ass i fi e r b y l e a rni n g , fr o m a s e t o f p r e v i o u s l y c l as s i fi e d d o c u m e n t s , t h e c h a r a c t e r i s t i c s o f c a t e g o r i e s . t h e t r a d i t i o n a l l y t c m e th o d s a r e b a s e d o n b a g o f w o r d s w h i c h h a s t w o m a i n fl a w s : o n e i s l e s s c a t e g o r y i n f o rm a t i o n , a n d t h e o t h e r i s h i g h d i m e n s io n a l i ty w h i c h c a u s e s d a t a s p a r s e . p h r a s e c a n b e u s e d t o r e l i e v e t h e fi r s t p r o b l e m b u t i t w i l l a g g r a v a t e t h e s e c o n d o n e . f o r t h e s e c o n d o n e , t h e u s u a l w a y i s u s i n g d i m e n s i o n a l i t y r e d u c - t i o n ( d r) me t h o d s wh i c h c a n r e mo v e n o n e - e ff e c t o r l e s s - e f f e c t f e a t u r e s a n d t h e l e f t f e a t u r e s a r e u s e d t o r e p r e s e n t e t h e t e x t . a c c o r d i n g t o t h e n a t u r e o f t h e r e s u lt t e r n s , d r c a n b e d e v i d e d in t o tw o t y p e s : ( 1 ) t e r m s e l e c t i o n : t h e r e s u l t t e r ms i s a s u b s e t o f t h e o r i g i n a l t e r m s ; ( 2 ) t e r m e x t r a c t i o n : t h e r e s u l t t e r m s i s n o t a s u b s e t o f t h e o r i g - in a l t e r m s . l a t e n t s e m a n t i c i n d e x i n g ( l s i ) i s o n e o f t h e t e r m e x t r a c t i o n m e t h o d s w h i c h c a n p r o j e c t t h e t e r m s f o r m w o r d s p a c e t o l a t e n s e m a n t i c s p a d e , a n d s o l v e t h e t w o p r o b le m s a t t h e s a m e t i m e . s i n g u l a r v a l u e d e c o m p o s i t i o n ( s v d) i s a t r a d i t i o n a l l s i m e t h o d s , i t h a s g a i n e d v e ry g o o d p e r f o r m a n c e . t h e m a in fl o w s o f s v d a r e s p e e d a n d m e m o ry . s e m i - d e s c r e t e d e c o m p o s i t i o n ( s d d ) i s a n o t h e r l s i m a t h o d , i t h a s f a s t e r s p e e d a n d l e s s m e m o ry n e e d w i t h t h e s a c r i fi c e o f a l i t t le r e d u c e i n p e r o r m a n c e . i n t h i s p a p e r , w e s t u d y t e x t c l a s s ifi c a t i o n b as e d o n l s i . w e s t u d y t h e f a c t o r s w h i c h m a y a ff e c t t h e p o r f o r m a n c e , m a i n l y i n d i ff e r e n t t e r m s e l e c t i o n m e t h o d s a n d i n d i ff e r e n t w e i g h t i n g m e t h o d s . we a l s o a p p r o v e a n i m p o v e m e n t m e t h o d o f l s i m o d e l , t h i s m e t h o d c a n im p r o v e t h e p o r f o r m a n c e o f s d d r e m a r k a b ly . w e d e s i g n a s e r i a l o f e x p e r i m e n t s o n t w o c o r p u s , c h i n e s e a n d e n g l i s h , a n d w e u s e k n n as t h e c l a s s i fi e r . t h e r e s u l t s o f e x p e r i m e n t s s h o w e d t h a t m e t h o d s o f d i ff e r e n t f e a t u r e s e l e c t io n a n d d i ff e r e n t t e r m w e i g h t i n g h a v e a l o t e ff e c t o n l s i . b u t t h e r e i s n o o n e m e t h o d i s p e r f o r m w e l l u n d e r a l l c o n d i t i o n s . t h e r e s u l t s a l s e s a i d t h a t o u r i m p r o v e m e n t m e t h o d h as a v e ry g o o d e ff e c t o n s d d . 一i v 一 东北大学硕士学位论文 ab s t r a c t k e y wo r d s : t e x t c l a s s i fi c a t i o n , l a t e n t s e m a n t i c i n d e x i n g , s i n g u l a r v a l u e d e c o m - p o s i t i o n , s e m i - d i s c r e t e ma t r i x d e c o m p o s i t i o n 一v 一 独创性声明 本人声明 所呈交的学位论文是在导师的指导下完成的。 论文中 取得的研究成果除加以 标注和致谢的地方外，不包含其他人己经发 表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示谢意。 学 位 论 文 作 者 签 名 :全 、镜， 日期 :， 。 斗 4j 二月 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用 学位论文的规定:即学校有权保留并向国家有关部门或机构送交论 文的复印件和磁盘，允许论文被查阅和借阅。本人授权东北大学可 以将学位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名;否则视为不同意。 ) 口t耳乃 ;， !计飞呵 学 位 论 文 作 者 签 名 : 分 沂 分 尸 一【 / l 夕 签 字 日 期 : 2- 0-0 件 ，么 q 导师签名 签字日期: 7 0 0 - 臂 ， 甲 东 l 大学硕士学位论文第一章 简介 第一章简介 1 . 1研究背景 文本分类( t e x t c l as s ifi c a t i o n , t c ) 就是把由自 然语言组成的 文本标记上预先 定义的类别。文本分类从6 0 年代开始就己经出现，但一直到2 0 世纪9 0 年代后， 才逐渐成为一个活跃的话题。 直到 2 0 世纪8 0 年代后期，流行的 t c 系统都是基于知识工程( k n o w l e d g e e n g i n e e ri n g , k e) 的。 将如何把一篇文档放到给定的 类别里去的 专家知识， 用手 工的方式编码成一条条的规则，添加到规则库中。从9 0 年代开始，这种方法渐 渐失宠， 人们开始转向了 机器学习 ( m a c h i n e l e a r n i n g , m l ) 的方法j 。它能自 动 地从预先分好类的文本中学习各个类别的特征，从而生成一个自 动分类器。机 器学习方法的优点是:1 . 效果与基于规则的 方法差不多， 甚至更好; 2 . 要构建分 类器或将分类器用于其它领域的时候，不需要知识工程师和领域专家，从而大 大地节省了人力。因此，现在绝大多数的研究都是针对基于机器学习的文本分 类方法的。 现在的文本分类处于机器学习和信息检索的交叉点上，它还具有其它一些 任务如信息抽取、文本挖掘等的特点。文本挖掘指的是，通过对大量文本的分 析，检测使用模式，来抽取可能有用的信息;从这点上看，文本分类也是文本 挖掘的一种。 1 . 2文本分类的应用 自 动文本分类至少起源于上个世纪6 0 年代。从那以后，文本分类开始应用 于不同的领域。在这一小节里我们将简要介绍一个最主要的几个应用方面，有 一些应用之间的边界是很模糊的，有些可能属于另外一些类别的特征情况。其 它一些没有提到的情况包括: ( 1 ) 通过语音识别和文本分类进行语音分类， ( 2 ) 通 过文本标题进行多媒体文档分类， ( 3 ) 通过文字分析对不明确的作者进行分 类，( 4 ) 未知语言文本的识别，( 5 ) 文学流派的自 动识别2 1 等。 一 1一 东北大学硕士学位论文第一章 简介 1 . 2 . ，布尔信息检索系统的自动索引 在一个受控词典上对信息检索系统进行自 动文档索引，是最先使用自 动文 本分类的领域，并且为文本分类提供了诸多早期的研究工作，其中最著名的就 是布尔系统了。在布尔系统中，为每一篇文档分配一个或多个关键词或关键短 语用来描述它的内容，关键词或关键短语属于一个叫做控制词典的有限集合， 并通常由一个主题层次辞典组成。这个分配过程通常由一个经过训练的人工索 引员来完成，因此代价是很高的。 如果把控制词典里的词条看做类别，文本索引就可以看做是文本分类任务 的一种了。已经有人在把分类用于文本索引方面做了尝试。 利用控制词典来进行自 动索引的课题与自 动元数据生成很相近。元数据是 用来在不同方面对文档进行描述的，如生成日 期、文档类型和格式等。在数字 图书馆中通常用元数据来给文档进行标记。通常有一些元数据是主题相关的， 它们的角色是通过目录编码、关键词或关键短语来描述文档的语义信息。这 样，这些元数据的生成就可以被看做是一个用控制词典进行文档索引的问题， 同样可以用文本分类的技术来解决。一个将文本分类技术用于自 动元数据生成 的样例是k l a r i t y系统。 1 . 2 . 2文本组织 用控制词典进行索引是文本组织问题的一个例子。通常，有许多别的问题 属于文本组织和过滤，不过是为了把人工组织一个共同的文本库或对其进行结 构化和问题用文本分类的技术来解决。举个例子，像在一个报社的办公室里， 来了一个分类广告，必须在印刷前将其分类到该报社所采用的分类体系下面。 典型的类别可能有个人、汽车销售、房地产等。大多数的报社可能用手工的方 法来做这个工作，那些要处理大量分类广告可能宁愿用一个自动系统来选择一 个广告最合适的类别。在这种情况下一个典型的约束是每个文档有且只能有一 个类别。 1 . 2 . 3文本过滤 文本 过滤 对一个文本的 动态 集合 ( 如一 个由 信息制 造者以 一种异步 方式分 派 到信息消费者的 文档流) 进行分类。 一个典型的事例是新闻 供给， 其中 制造者是 一个新闻机构( 如路透社) ，消费者是一个报社。在这里过滤系统应该阻止把消 一z一 东北大学硕士学位论文第一章 简介 1 . 2 . ，布尔信息检索系统的自动索引 在一个受控词典上对信息检索系统进行自 动文档索引，是最先使用自 动文 本分类的领域，并且为文本分类提供了诸多早期的研究工作，其中最著名的就 是布尔系统了。在布尔系统中，为每一篇文档分配一个或多个关键词或关键短 语用来描述它的内容，关键词或关键短语属于一个叫做控制词典的有限集合， 并通常由一个主题层次辞典组成。这个分配过程通常由一个经过训练的人工索 引员来完成，因此代价是很高的。 如果把控制词典里的词条看做类别，文本索引就可以看做是文本分类任务 的一种了。已经有人在把分类用于文本索引方面做了尝试。 利用控制词典来进行自 动索引的课题与自 动元数据生成很相近。元数据是 用来在不同方面对文档进行描述的，如生成日 期、文档类型和格式等。在数字 图书馆中通常用元数据来给文档进行标记。通常有一些元数据是主题相关的， 它们的角色是通过目录编码、关键词或关键短语来描述文档的语义信息。这 样，这些元数据的生成就可以被看做是一个用控制词典进行文档索引的问题， 同样可以用文本分类的技术来解决。一个将文本分类技术用于自 动元数据生成 的样例是k l a r i t y系统。 1 . 2 . 2文本组织 用控制词典进行索引是文本组织问题的一个例子。通常，有许多别的问题 属于文本组织和过滤，不过是为了把人工组织一个共同的文本库或对其进行结 构化和问题用文本分类的技术来解决。举个例子，像在一个报社的办公室里， 来了一个分类广告，必须在印刷前将其分类到该报社所采用的分类体系下面。 典型的类别可能有个人、汽车销售、房地产等。大多数的报社可能用手工的方 法来做这个工作，那些要处理大量分类广告可能宁愿用一个自动系统来选择一 个广告最合适的类别。在这种情况下一个典型的约束是每个文档有且只能有一 个类别。 1 . 2 . 3文本过滤 文本 过滤 对一个文本的 动态 集合 ( 如一 个由 信息制 造者以 一种异步 方式分 派 到信息消费者的 文档流) 进行分类。 一个典型的事例是新闻 供给， 其中 制造者是 一个新闻机构( 如路透社) ，消费者是一个报社。在这里过滤系统应该阻止把消 一z一 东北大学硕士学位论文第一章 简介 费者不感兴趣的文档提供给消费者，如对一个体育报社来说，所有非体育类的 信息都不是他想要的。 过滤可以被看做是一个单标签分类问 题，到来的文档被 分到两个不相交的类别中:相关的和不相关的。另外，过滤系统还可以将文本 进一步分类到消费者所需要的类别中去。在上面的例子中，所有关于体育的文 章都是相关的，并且可以按所讲述的体育运动的类别进行进一步分类，从而可 以让不同体育项目的专项记者找到他们最感兴趣的文档。 类似地，一个电子邮 件过滤器可以经过训练来屏蔽垃圾邮件，并且可以进一步将邮件按用户要求的 类别进行分类。 1 .2 .4词义消歧 词义消 歧( w o r d s e n s e d i s a m b i g u a t i o n , ws d) 指， 给定一个在文本中 有歧义 的 词( 多义词或同 义词) ，找到它并给出它在出 现地方的 准确含义。ws d对一些 应用来说是很重要的，包括自 然语言理解，或通过词义来建立文档索引，而不 是为信息检索而用词来建立索引等。如果我们把文档看做上下文，词义看做类 别，ws d就以看成是一个分类任务。 1 .2 .5网页层次分类 自 动文本分类也带动了将它用于i n t e rne t 可行性的研究。其中一个就是自 动 地将网页或网站按流行的i n t e rne t 门户网站的商业层次类别分到一个或多个类别 下面。当网页按这种方式组织以后，一个要查找相关信息的人就可以首先浏览 这个类别层次，然后在相关的类别下面查找，这比向一个网页搜索引擎提出请 求要容易很多。 对网页进行自 动分类很有优势，因为要手工对大量的网页进行分类是不切 实际的。 点: 与前面讨论的文本分类的应用相比，网页的自 动分类有两个不同的特 ( 1 ) 文档的 超文本特性:超链接包含了丰富的信息，可以把它们看做是被链接 的内容与链接网页的相似度的一种体现。 ( 2 ) 类别集合的层次结构:可以 利用这一点把分类问 题分解成一系列的与内部 节点上的分支对应的小一些的分类问题。 一3一 东北大学硕士学位论文第一章 简介 费者不感兴趣的文档提供给消费者，如对一个体育报社来说，所有非体育类的 信息都不是他想要的。 过滤可以被看做是一个单标签分类问 题，到来的文档被 分到两个不相交的类别中:相关的和不相关的。另外，过滤系统还可以将文本 进一步分类到消费者所需要的类别中去。在上面的例子中，所有关于体育的文 章都是相关的，并且可以按所讲述的体育运动的类别进行进一步分类，从而可 以让不同体育项目的专项记者找到他们最感兴趣的文档。 类似地，一个电子邮 件过滤器可以经过训练来屏蔽垃圾邮件，并且可以进一步将邮件按用户要求的 类别进行分类。 1 .2 .4词义消歧 词义消 歧( w o r d s e n s e d i s a m b i g u a t i o n , ws d) 指， 给定一个在文本中 有歧义 的 词( 多义词或同 义词) ，找到它并给出它在出 现地方的 准确含义。ws d对一些 应用来说是很重要的，包括自 然语言理解，或通过词义来建立文档索引，而不 是为信息检索而用词来建立索引等。如果我们把文档看做上下文，词义看做类 别，ws d就以看成是一个分类任务。 1 .2 .5网页层次分类 自 动文本分类也带动了将它用于i n t e rne t 可行性的研究。其中一个就是自 动 地将网页或网站按流行的i n t e rne t 门户网站的商业层次类别分到一个或多个类别 下面。当网页按这种方式组织以后，一个要查找相关信息的人就可以首先浏览 这个类别层次，然后在相关的类别下面查找，这比向一个网页搜索引擎提出请 求要容易很多。 对网页进行自 动分类很有优势，因为要手工对大量的网页进行分类是不切 实际的。 点: 与前面讨论的文本分类的应用相比，网页的自 动分类有两个不同的特 ( 1 ) 文档的 超文本特性:超链接包含了丰富的信息，可以把它们看做是被链接 的内容与链接网页的相似度的一种体现。 ( 2 ) 类别集合的层次结构:可以 利用这一点把分类问 题分解成一系列的与内部 节点上的分支对应的小一些的分类问题。 一3一 东北大学硕士学位论文第一章 简介 1 . 3文本分类系统 文本分类是一个复杂的系统，由很多不同的模块组成，根据在分类中的不 同阶段，整个流程可以分为训练过程和分类过程两部分。训练过程主要由训练 语料的预处理、特征抽取、 语料的重新生成以及构建训练器几个模块组成。分 类过程主要包括对测试文本的预处理和分类两部分。文本分类系统的一般框图 如图 1 . 1 所示。 训练过程分类过程 训练文本测试文本 预处理预处理 分类结果 评测 分类和输出 训练 分类器 征维 特降 训练文本 格式化 图1 . 1 文本分类系统结构图 f i g 1 . 1 f r a m e o f t e x t c l a s s i fi c a t i o n s y s t e m 文本分类的各个主要模块简述如下: 1 . 3 . ，预处理 预处理主要是将原始文本转换成适合计算机表达的形式，其中不同的语种 对不同的技术有所侧重，如东方语言要进行处理的第一步就是对文本进行分 词，而西文语言中大多是不需要这一过程的;另外英文中还有词形还原等，这 在东方语言中一般是没有的。 1 . 3 . 2降维 传统的文本分类方法都是用词作为特征来构建的，而用词来表示文本的 特 征虽然简单直观，但有一个很大的缺陷就是特征的维数过高，从而造成数据稀 一4一 东北大学硕士学位论文第一章 简介 1 . 3文本分类系统 文本分类是一个复杂的系统，由很多不同的模块组成，根据在分类中的不 同阶段，整个流程可以分为训练过程和分类过程两部分。训练过程主要由训练 语料的预处理、特征抽取、 语料的重新生成以及构建训练器几个模块组成。分 类过程主要包括对测试文本的预处理和分类两部分。文本分类系统的一般框图 如图 1 . 1 所示。 训练过程分类过程 训练文本测试文本 预处理预处理 分类结果 评测 分类和输出 训练 分类器 征维 特降 训练文本 格式化 图1 . 1 文本分类系统结构图 f i g 1 . 1 f r a m e o f t e x t c l a s s i fi c a t i o n s y s t e m 文本分类的各个主要模块简述如下: 1 . 3 . ，预处理 预处理主要是将原始文本转换成适合计算机表达的形式，其中不同的语种 对不同的技术有所侧重，如东方语言要进行处理的第一步就是对文本进行分 词，而西文语言中大多是不需要这一过程的;另外英文中还有词形还原等，这 在东方语言中一般是没有的。 1 . 3 . 2降维 传统的文本分类方法都是用词作为特征来构建的，而用词来表示文本的 特 征虽然简单直观，但有一个很大的缺陷就是特征的维数过高，从而造成数据稀 一4一 东北大学硕士学位论文第一章 简介 疏。为了解决这个问题，通常要采用降维的方法来对原始的特征进行处理，即 去掉一些对分类结果没有影响或影响很小的特征，用剩余的特征来表示文本。 根据结果特征项的 特点，降维方法可以 分为( i ) 特征提取:结果特征是原始特征 的子集: ( 2 ) 特征抽取:结果特征不是原始特征的子集。 1 . 3 . 3格式化 这一步骤的目 地是将预处理过的文本用降维后的特征进行处理，把文本从 原始的特征空间映射到新的特征空间去;并采用一种合适的方法来计算各个特 征项的权重，将文本表示成新空间上的一个个向量，以便后面训练分类器的时 候使用。 ， 3 .4训练分类器 在分类器的构建过程中，主要是用各种机器学习的方法对训练数据进行分 析，从中学习出各个类别的不同特点，从而生成所需的分类器。这一步骤是文 本分类中最关键的一步，它综合利用了特征降维、特征项权重计算、相似度计 算等各种技术，可以按照不同的要求构造出不同的分类器来。 1 . 3 . 5测试文本预处理 当一篇测试文本到来的时候，也要对其进行预处理才能送进分类器中进行 分类。对测试文本的预处理包括对训练文本处理中的两个步骤:预处理和格式 化。 1 . 3 . 6分类和输出 在分类器构造出来以后，就可以把预处理过的测试文本送入分类器中进行 分类了。分类器利用从训练语料中学习得到的各个类别的特征数据对测试文本 进行判断，输出它可能属于的类别。 1 . 3 .7评t il l 对于分类结果的评测，也有很多的方法，其中最主要也最常用评测手段是 正确率，召回率和f值。 一5一 东北大学硕士学位论文第一章 简介 疏。为了解决这个问题，通常要采用降维的方法来对原始的特征进行处理，即 去掉一些对分类结果没有影响或影响很小的特征，用剩余的特征来表示文本。 根据结果特征项的 特点，降维方法可以 分为( i ) 特征提取:结果特征是原始特征 的子集: ( 2 ) 特征抽取:结果特征不是原始特征的子集。 1 . 3 . 3格式化 这一步骤的目 地是将预处理过的文本用降维后的特征进行处理，把文本从 原始的特征空间映射到新的特征空间去;并采用一种合适的方法来计算各个特 征项的权重，将文本表示成新空间上的一个个向量，以便后面训练分类器的时 候使用。 ， 3 .4训练分类器 在分类器的构建过程中，主要是用各种机器学习的方法对训练数据进行分 析，从中学习出各个类别的不同特点，从而生成所需的分类器。这一步骤是文 本分类中最关键的一步，它综合利用了特征降维、特征项权重计算、相似度计 算等各种技术，可以按照不同的要求构造出不同的分类器来。 1 . 3 . 5测试文本预处理 当一篇测试文本到来的时候，也要对其进行预处理才能送进分类器中进行 分类。对测试文本的预处理包括对训练文本处理中的两个步骤:预处理和格式 化。 1 . 3 . 6分类和输出 在分类器构造出来以后，就可以把预处理过的测试文本送入分类器中进行 分类了。分类器利用从训练语料中学习得到的各个类别的特征数据对测试文本 进行判断，输出它可能属于的类别。 1 . 3 .7评t il l 对于分类结果的评测，也有很多的方法，其中最主要也最常用评测手段是 正确率，召回率和f值。 一5一 东北大学硕士学位论文第一章 简介 1 . 4潜在语义索引 传统的分类模型一般是用词来作为特征的。为了降低系统的复杂度，一般 认为词与词之间是相互独立的，这显然是与事实相违背的，因此向量空间模 型的效果一直不太好。1 9 9 0 年，s c o tt d e e r w e s t e r 提出了潜在语义索引 ( l a t e n s e m a n t i c i n d e x in g , l s i )的方法3 ，并将它用在信息检索上，取得了很好的效 果。此后，人们对l s i 在信息检索上的应用进行了深入的研究，并取得了大量 的 成 果 ，5 。 在用词来表示文本的时候，由于大量存在的同义词、近义词和多义词，使 得特征之间相互独立的假设不能成立。l s i 通过统计大量文本中这些词的共现 信息，来发掘它们的内部联系，称为文本的语义。l s i 认为每篇文章都包含有 几种语义，这些之间是相互独立的，如果可以用这些语义来表示文档，并拿它 们来进行计算，则在降低计算复杂度的同时，还可以保持很好的效果。由于这 种语义不能直接得到，只能通过对文章特征的分析得到，是潜藏在文章特征之 间的，所以称为 “ 潜在语义”。l s i 的一个缺点是它有可能使一个本来区分能 力很强的特征在转换到新的空间之后被淹没掉。 传统的潜在语义是通过奇异值分解的方法来计算的，它可以得到很好的效 果， 但是时间复杂度和空间复杂度都比 较高。为了解决这个问 题， 在o l e a r y 工作6 的基础上，k o l d a 开发出了一个新的矩阵估计算法叫半离散矩阵分解 ( s e m i- d i s c r e t e d e c o m p o s it io n , s d d) n ， 来 代 替s v d。s d d分 解 后的 矩阵 值 取 自 集 合 0 , 1 , = 1 ， 这样用两 个比 特就可以 表示一 个值， 从而大大减少了 存储空 间的要求，另外，通过提出的新算法，使时间复杂度也大大降低。 1 . 5研究现状及发展趋势 一般来说，l s i 较多地用在信息检索上3 - 5 , 8 ，这与信息检索发展得较早不 无关系。近年来，随着文本分类研究的兴起，人们也开始将潜在语义分解用于 解决文本中的问 题。 1 9 9 5 年，s c h u t z e 等0 将l s i 用于文本分 类， 并与用护进 行特征选取的方法进行比较，在三种不同的分类器上进行了实验。实验结果证 明l s i 在逻辑回归等两个容易过学习的分类器上的表现远远好于扩， 而在神经 元网络分类器上则不相上下。w i e n e r 等11 0 1 用两种不同的方式来使用l s i ，一是 为几个类别集合分别建立不同的l s i 表示，二是建立为所有的类别建立一个唯 一6一 东北大学硕士学位论文第一章 简介 1 . 4潜在语义索引 传统的分类模型一般是用词来作为特征的。为了降低系统的复杂度，一般 认为词与词之间是相互独立的，这显然是与事实相违背的，因此向量空间模 型的效果一直不太好。1 9 9 0 年，s c o tt d e e r w e s t e r 提出了潜在语义索引 ( l a t e n s e m a n t i c i n d e x in g , l s i )的方法3 ，并将它用在信息检索上，取得了很好的效 果。此后，人们对l s i 在信息检索上的应用进行了深入的研究，并取得了大量 的 成 果 ，5 。 在用词来表示文本的时候，由于大量存在的同义词、近义词和多义词，使 得特征之间相互独立的假设不能成立。l s i 通过统计大量文本中这些词的共现 信息，来发掘它们的内部联系，称为文本的语义。l s i 认为每篇文章都包含有 几种语义，这些之间是相互独立的，如果可以用这些语义来表示文档，并拿它 们来进行计算，则在降低计算复杂度的同时，还可以保持很好的效果。由于这 种语义不能直接得到，只能通过对文章特征的分析得到，是潜藏在文章特征之 间的，所以称为 “ 潜在语义”。l s i 的一个缺点是它有可能使一个本来区分能 力很强的特征在转换到新的空间之后被淹没掉。 传统的潜在语义是通过奇异值分解的方法来计算的，它可以得到很好的效 果， 但是时间复杂度和空间复杂度都比 较高。为了解决这个问 题， 在o l e a r y 工作6 的基础上，k o l d a 开发出了一个新的矩阵估计算法叫半离散矩阵分解 ( s e m i- d i s c r e t e d e c o m p o s it io n , s d d) n ， 来 代 替s v d。s d d分 解 后的 矩阵 值 取 自 集 合 0 , 1 , = 1 ， 这样用两 个比 特就可以 表示一 个值， 从而大大减少了 存储空 间的要求，另外，通过提出的新算法，使时间复杂度也大大降低。 1 . 5研究现状及发展趋势 一般来说，l s i 较多地用在信息检索上3 - 5 , 8 ，这与信息检索发展得较早不 无关系。近年来，随着文本分类研究的兴起，人们也开始将潜在语义分解用于 解决文本中的问 题。 1 9 9 5 年，s c h u t z e 等0 将l s i 用于文本分 类， 并与用护进 行特征选取的方法进行比较，在三种不同的分类器上进行了实验。实验结果证 明l s i 在逻辑回归等两个容易过学习的分类器上的表现远远好于扩， 而在神经 元网络分类器上则不相上下。w i e n e r 等11 0 1 用两种不同的方式来使用l s i ，一是 为几个类别集合分别建立不同的l s i 表示，二是建立为所有的类别建立一个唯 一6一 东北大学硕士学位论文第一章 简介 一的l s i 表示。他们的试验表明第一种方法要比第二个好，而这两种方法都比 普通的特征选取的方法效果好。这主要是因为l s i 是一种无监督的方法，在计 算潜在语义的时候把原来的训练文本的类别信息都丢掉了，从而造成信息的丢 失。如果用局部l s i 则会把类别信息保留下来，这就减小了信息的丢失，使其 分类的效果比全局l s i 要好。 国内对潜在语义索引的研究相对起步较晚，东北大学自然语言处理实验 室在这方面做了大量的研究工作( 1 1 - 14 1 ，打下了坚实的基础。其它的研究也主要 集中在怎样将潜在语义索引用于信息检索1 5 , 1 6 、文本过滤上面 1 7 , 1 8 ，只有张俊 梅 i 9 对潜在语义索引在中文文本分类中的应用进行了初步探索，刘昌任2 0 用潜 在语义索引的方法来解决b b s 环境下的分类问题。 文本分类的研究现在主要集中在以下几个方面: ( i ) 文本表示，即如何才能更有效把文本所蕴含的 深层含义表示出 来。 包括特 征选取和权重计算。如用聚类的方法对词进行聚类，然后用这些类别来表 示文本2 1 ;或者由文档聚类后形成的簇的中心向量构成概念空间，把文本 转换到概念空间上来表示(2 2 , 2 3 1 等等。 ( 2 )自 动文本分类方法，主要是把人工智能和机器学习等领域的先进知识引入 到文本分类中来，以提高分类的效果。如把在模式识别中取得很好效果的 支持向 量机 s v m) 方法引入到文本分类中来， 取得了 很好的效果2 4 , 2 5 ( 3 ) 无标注语料的使用。由 于在训练分类器的时候需要大量的人工标注的语 料，这是一项对人力、物力需求都很大的工程;同时互连网有大量的无标 注的语料存在。能否利用这些无标注的语料，而降低手工标注语料的规 模， 也 是一个 研究的 热点 2 6 1 . 6本文的工作 目 前，在对l s i 的研究中，主要是将它用在信息检索上，在文本分类方面 的 研究相对较少。而且一般的用法是把l s i 仅仅当做一种降维的方法来使用， 并没有考虑到可能对l s i 本身产生影响的因素。 对这些问题的研究将会给以后的研究工作打下坚实的基础，使以后的工作 有一个很好的起点。为了这个目 的，我们设计了一系列的试验，来探讨各种因 素对 l s i 的影响。我们认为，下列因素可能会对 l s i 本身的效果产生影响: 一7一 东北大学硕士学位论文第一章 简介 一的l s i 表示。他们的试验表明第一种方法要比第二个好，而这两种方法都比 普通的特征选取的方法效果好。这主要是因为l s i 是一种无监督的方法，在计 算潜在语义的时候把原来的训练文本的类别信息都丢掉了，从而造成信息的丢 失。如果用局部l s i 则会把类别信息保留下来，这就减小了信息的丢失，使其 分类的效果比全局l s i 要好。 国内对潜在语义索引的研究相对起步较晚，东北大学自然语言处理实验 室在这方面做了大量的研究工作( 1 1 - 14 1 ，打下了坚实的基础。其它的研究也主要 集中在怎样将潜在语义索引用于信息检索1 5 , 1 6 、文本过滤上面 1 7 , 1 8 ，只有张俊 梅 i 9 对潜在语义索引在中文文本分类中的应用进行了初步探索，刘昌任2 0 用潜 在语义索引的方法来解决b b s 环境下的分类问题。 文本分类的研究现在主要集中在以下几个方面: ( i ) 文本表示，即如何才能更有效把文本所蕴含的 深层含义表示出 来。 包括特 征选取和权重计算。如用聚类的方法对词进行聚类，然后用这些类别来表 示文本2 1 ;或者由文档聚类后形成的簇的中心向量构成概念空间，把文本 转换到概念空间上来表示(2 2 , 2 3 1 等等。 ( 2 )自 动文本分类方法，主要是把人工智能和机器学习等领域的先进知识引入 到文本分类中来，以提高分类的效果。如把在模式识别中取得很好效果的 支持向 量机 s v m) 方法引入到文本分类中来， 取得了 很好的效果2 4 , 2 5 ( 3 ) 无标注语料的使用。由 于在训练分类器的时候需要大量的人工标注的语 料，这是一项对人力、物力需求都很大的工程;同时互连网有大量的无标 注的语料存在。能否利用这些无标注的语料，而降低手工标注语料的规 模， 也 是一个 研究的 热点 2 6 1 . 6本文的工作 目 前，在对l s i 的研究中，主要是将它用在信息检索上，在文本分类方面 的 研究相对较少。而且一般的用法是把l s i 仅仅当做一种降维的方法来使用， 并没有考虑到可能对l s i 本身产生影响的因素。 对这些问题的研究将会给以后的研究工作打下坚实的基础，使以后的工作 有一个很好的起点。为了这个目 的，我们设计了一系列的试验，来探讨各种因 素对 l s i 的影响。我们认为，下列因素可能会对 l s i 本身的效果产生影响: 一7一 东北大学硕士学位论文第一章 简介 ( i ) 数据稀疏;由 于l s i 是利用特征的 共现信息来进行计算的， 而共现信息与 数据稀疏程度是密切相关的。因此数据稀疏程度的不同将对l s i 的效果产 生较大的影响。 ( z ) 权重计算;一个特征对文本的 表示能力是由通过其权重来表现的， 不同的 权重计算方法对一个特征的表示能力有很大的影响，只有好的权重计算方 法才能使特征更好地表示文本。而l s i 正是利用这些信息来处理的，因此 权重计算对l s i 的效果也有很大的影响。 ( 3 ) 特征选取。 文本，使得 由于数据稀疏对 l s i 的效果影响很大，所以用什么特征来表示 l s i 的效果最好，也是一个要探讨的课题。 另外，在试验的基础上，我们提出了一种对l s i 的改进模型。这种模型不 但可以大大改善用半离散矩阵分解时的分类效果，还可以进一步减少所需存储 空间的要求。 1 . 7本文的组织 本文共分五章，第一章是简介，介绍相关的背景知识，提出了我们要研究 的内容;在第二章，我们简要介绍了一些背景知识，主要是文本分类的评测方 法，我们用到的语料，以及在本文中用到的i n n分类器;第三章中，重点介 绍了一些常用的特征选取方法，和一般的权重计算方法;第四章，我们重点介 绍了潜在语义索引及其用到的两种方法:奇异值分解和半离散矩阵分解，并给 出我们的试验结果和对结果的分析;在第五章，我们提出了一种对潜在语义索 引的改进方法，该方法不但可以明显地提高s d d的效果，还可以降低分解后对 存储空间的要求;最后，我们对本文的工作作了一个总结，并对将来的工作进 行了展望。 一8一 东北大学硕士学位论文第一章 简介 ( i ) 数据稀疏;由 于l