（计算机应用技术专业论文）基于粗糙集的文本分类技术研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着互联网的普及和规模的急剧扩张，作为网络8 0 以上信息的主要表达 方式，各种各样的电子文本得以迅速膨胀，往往造成大量无用信息淹没了有用 信息，出现了信息极大丰富知识却相对贫乏的网络信息搜索现状如何有效地 组织和管理这些海量信息资源，使人们能够按照文本内容实现对其自动分类， 帮助用户迅速准确地获取其所需要的知识和信息，是计算机科学领域目前的研 究热点之一，具有广泛的应用背景和实用价值。 粗糙集是由波兰数学家z p a w l a k 于1 9 8 2 年提出的一种处理含糊和不确定 问题的集合理论，建立了知识和分类能力的联系，其主要思想是在保持分类能 力不变的前提下，通过知识约简，导出决策或分类规则。该理论自9 0 年代被 引入到机器学习、人工智能等领域后，己经成功地用于知识获取、规则提取、 决策分析、模式识别、数据挖掘等领域。本文结合粗糙集理论对文本分类进行 研究，主要进行了以下工作： 研究文本分类过程中的特征选择方法和文本向量模型的权值计算公式 i t i d f ，采取不同的特征选取方法，比较基于文本特征选择方法的改进t f - i d f 权值计算公式效果，确定进行文本分类的合适权值计算公式。 研究将粗糙集应用于文本分类技术，通过简单的等距离数据离散化方法， 生成易于理解的文本分类规则。 研究粗糙集理论中的属性约简算法，对利用文本特征选择方法和粗糙集理 论本身的两种不同属性重要性的评价方法进行综合，并详细比较各种属性评价 方法在精确约简和近似约简的表现，从中找出合适的用于启发式属性约简的属 性重要性衡量方法。 对于粗糙集理论中的启发式属性约简算法进行改进，利用两种约简信息， 变传统的一次约简为二次约简。 本文研究结果证明，将粗糙集的属性约简理论应用于文本分类，可以较大 降低文本描述维数，很好地解决文本向量维数过大的问题。通过属性约简生成 的文本分类规则，具有较高的文本分类正确率和较大的应用价值。 关键词：文本分类特征选择权值计算粗糙集属性约简 西南交通大学硕士研究生学位论文第l | 页 a b s tr a c t w i t ht h ew i d e s p r e a du s i n ga n dd e v e l o p m e n to fi n t e r n e t , v a r i o u se - t e x t s , a st h e m a i ne x p r e s s i o no fo v e r8 0p e r c e n th t e m e ti n f o r m a t i o n , h a v ea p p e a r e da ta f a n t a s t i cs p e e d t h u s ，m o s to ft h eu s e f u li n f o r m a t i o nh a v eu s u a l l yb e e nc o v e r e db y t h eu s e l e s s ，w h i c hr e s u l t si nt h ep h e n o m e n o no f “i n f o r m a t i o nm o r ea b u n d a n tb u t k n o w l e d g em o r ep o o r h o wt oo r g a n i z ea n dm a n a g et h e s eo v e r l a r g ei n f o r m a t i o n e - t e x t s a u t o - c l a s s i f yt h e s ei n f b 血a t i o na c c o r d i n gt ot h ec o n t e n to ft e x ta n dh e l p l i s c 辟o b t a i nu s e f u lk n o w l e d g ea n di n f o r m a t i o ne x a c t l y , h a sb e e naf o c u so nt h e c o m p u t e rs c i e n t i f i cf i e l d ，o n t h eo t h e rh a n d ，t h er e s e a r c ha l s oh a v eaw i d e l y a p p l y i n gc o n t e x ta n dp r a c t i c a lv a l u e r o u g hs e t , p r o p o s e db yp o l i s hs c i e n t i s t 乙p a w l a ki n1 9 8 2 , i sn o to n l yas e t t h e o r yt o d e a lw i t ht h ev a g u ea n du n c 白恤p r o b l e m sb u ta l s ot ob u i l dt h e r e l a t i o n s h i p sb e t w e e nk n o w l e d g ea n dc l a s s i f i c a t i o n t h em a i ni d e ao ft h i st h e o r yi s i nt h ep r e c o n d i t i o no ft h es a m ec l a s s i f y i n gc a p a b i l i t y , t oc o n d u c td e c i s i o no r c l a s s i f i c a t i o nr u l e sb yk n o w l e d g er e d u c t i o n a f t e rb e i n gc o n d u c t e dt ot h ea r e a so f m a c h i n el e a r n i n g , a r t i f i c i a li n t e l l i g e n c ea n de t a ，i nt h e1 9 9 0 s t h i st h e o r yh a sb e e n s u c c e s s f u l l yu s e di nv a r i o u sf i e l d ss u c ha sk n o w l e d g eo b t a i n , r u l ee x t r a c t i o n , d e c i s i o na n a l y s i s ，p a t t e mr e c o g n i t i o n , d a t am i n i n g , a n ds oo n s o m er e s e a r c ho ft e x tc l a s s i f i c a t i o nb a s e do nr o u g hs c tt h e o r yh a sb e e nd o n e a n dt h em a i nw o r ki ss h o w e da sf o l l o w s ： t h ef e a t u r es e l e c t i o nm e t h o d su s e di nt e x tc l a s s i f i c a t i o na n dt h ew e i g h t c a l c u l a t i n gf o r m u l ao ft f - i d fb e l o n g i n gt ot e x tv e c t o rm o d e lh a v eb e e ns t u d i e d , t h e n ，t h i sp a p e rc o m p a r et h ep e r f o r m a n c eo ft h ei m p r o v e dw e i g h tc a l c u l a t i n g f o r m u l ac a l l e dt f - i d fw h i c hb a s e do nt e x tf e a t u r es e l e c t i o nm e t h o d s ，t i n a l l y , c h o o s ew h i c hf o r m u l ai sb e t t e rt of i tt oc a l c u l a t e b yu s i n gs i m p l ee q u a l - d i s t a n c ed a t ad i s c r e t i z i n gm e t h o d ，t e x tc l a s s i f i c a t i o n b a s e do nr o u g hs e tt h e o r yr e s u l t si nas e r i a lo fc o m p r e h e n s i b l et e x tc l a s s i f i c a t i o n r u l e s d u n gs t u d y i n ga t t r i b u t e sr e d u c t i o na l g o r i t h mb a s e do nr o u g h s e tt h e o r yt w o 西南奎夔奎学硕士研究生学位论文第l ii 页 d i f f e r e n ta t t r i b u t e si m p o r t a n c e 。m e a s u r e sb e t w e e nt e x tf e a t u r es e l e c t i o i lm e t h o d sa n d r o u g hs e tt h e o r y sh a v eb e e ni n t e g r a t e d , m e a n w h i l e ，t h i sp a p e rd e t a i l e d l yc o m p a r e s t h ep e r f o r m a n c e sa m o n gv a r i o u sa t t r i b u t em e a s u r e sb o t hi np r e c i s i o nr e d u c t i o na n d c o n c i s er e d u c t i o nt om i n i n ga na p p r o p r i a t ea p p r o a c ht om e a s u r et h ea t t r i b u t e s i m p o r t a n c ef o rh e u r i s t i ca t t r i b u t e sr e d u c t i o n u s i n gb o t hr e d u c t i o ni n f o r m a t i o na n dc h a n g i n gr e d u c i n gt i m e sf r o mo l l c et o t w i c e ，a l li m p r o v e dh e u r i s t i ca t t r i b u t e sr e d u c t i o na l g o r i t h mi sp u tf o r w a r di nt h i s p a p e r t h ee x p e r i m e n tr e s u l t si n d i c a t et h a tt h ea t t r i b u t e sr e d u c t i o nb a s e do 、nr o u g h s e tt h e o r y , w h i c ha p p l i e df o rt e x tc l a s s i f i c a t i o n , c a ns i g n i f i c a n t l yr e d u c et h et e x t d e s c r i b i n gd i m e n s i o n s ，s o l v et h e “h i g h e rd i m e n s i o n a ld i s a s t e r p r o b l e me f f e c t i v e l y a n dh a v eaa p p r o p r i a t ec l a s s i f y i n gc o r r e c tr a t ef o rt e x tc l a s s i f i c a t i o nr u l e sw h i c h g e n e r a t e db yr e d u c i n ga t t r i b u t e s ， k e yw 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 , w e i g h tc a l c u l a t i o n , r o u g hs e t , a t t r i b u t e sr e d u c t i o n 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 论文研究的背景及意义 随着互联网的普及和规模的急剧扩张，作为网络8 0 以上信息的主要表达 方式，各种各样的电子文本得以迅速膨胀，1 9 9 9 年的统计结果表明，i n t e r a e t 上有约3 5 亿个静态h t m l 页面，每天增加将近1 0 0 万【1 】，目前，著名的搜索 引擎g o o g l e 所能搜索的网页数量达8 0 亿之多：中文搜索的百度可搜索超过1 0 亿的中文网页，并且这些网页的数量每天以千万级的速度在增长所以，在我 们日常所接触的海量信息中，往往造成大量无用的信息淹没了有用信息，这就 是信息极大丰富但知识却相对贫乏的网络信息搜索现状。 如何有效地组织和管理这些海量的信息资源，使入们能够按照文本内容实 现对其自动分类，帮助用户迅速准确地获取其所需要的知识和信息，解决信息 杂乱现象的问题，是计算机科学领域目前的研究热点之一，具有广泛的应用背 景和实用价值。 文本分类 2 - 3 1 ( t e x tc l a s s i f i c a t i o n ) 是指在给定的文本分类体系下，根据所 提供新文本的内容自动确定出其应属的文本类别。文本的来源是多种多样的， 有报告、单据、新闻和邮件等。文本分类作为信息过滤m 】( i n f o r m a t i o n f i l t e r i n g ) 、信息检索( i n f o r m a t i o nr e t r i e v a l ) f 6 】、搜索引擎( s e a r c he n g i n e ) 1 7 1 、 邮件分类、数字化图书馆等领域的技术基础，在许多环境下有着应用前景。这 些环境包括： ( 1 ) 进行文本信息过滤 根据信息用户个人的爱好和习惯形成各种分类过滤器，信息服务者在给用 户传送数据前先调用其相应的分类过滤器，使只有通过过滤的信息才送达到信 息用户。另外网络信息良莠不齐，有必要对一些反面的信息进行屏蔽，维护一 个良好的网络环境。 ( 2 ) 为信息检索和搜索引擎服务 信息检索系统操作的文本信息库相当庞大( 如检索电子图书馆中的文献 库) ，如果把大量的文本信息按主题层次归类，可以极大迨降低对信息的检索 规模，为信息检索提供更高效的搜索策略和更准确的查询结果；对于搜索引擎 西南交通大学硕士研究生学位论文第2 页 来讲，如果对搜索到的网页文本再进行一次文本分类处理，可以大大提高信息 的提供质量并减少用户查看的网页数量。目前很多w e b 搜索引擎站点都使用 了w e b 文本层次化分类组织。只是，目前主要以人工分类为主，y a h o o 就是这 样。 ( 3 ) 数字图书馆 数字图书馆是世界各国图书馆建设的重点，数字化图书期刊在社会和高校 的比重正日益增大。对图书归类时，图书管理员不可能对各个学科都非常了解， 进行自动文本分类处理，可以帮助其正确对图书文献进行归类。 ( 4 ) 邮件分类 对用户收到的电子邮件进行自动分类，以便进行相应处理。例如，麻省理 工学院为白宫开发的邮件分类系统能自动地分辨每天发送给总统的大量电子 邮件所属的类别，归为外交、环保、税收、家居等类别，便于适当的人员对信 件分类进行回复。 ( 5 ) 电予会议 电子会议是一种新兴的会议方式，与会者通过网络系统举行会议，由于与 会者是匿名的，便于形成平等的气氛，、从而调动了与会者的积极性，常常会产 生大量的意见和建议。对这些意见和建议进行自动分类处理后，便于确定需进 一步讨论的会议主题。 ， 文本自动分类是一种典型的有监督的机器学 - 3 t 8 ( m a c h i n e1 c a m i n g ) 问题， 一般分为两部分：一、建立相应分类模型，描述给定的文本分类体系下预定的 数据类集或概念集。二、利用分类模型，分别采用不同的文本分类方法对新文 本进行分类。 常用的文本分类方法主要有基于向量比较的文本分类技术和基于规则抽 取的文本分类技术。基于向量比较的常用文本分类技术有：简单中心向量比较 算法1 9 、k 近邻算法【1 0 1 ( k n e a r e s tn e i g h b o r ) 、支持向量机算法【l l - 1 2 1 ( s u p p o r t v e c t o r m a c h i n e ) 。此类方法首先将文本抽象描述为由一组特征项( t l ，t 2 ， k ) 组成的n 维向量，具体到一个文本中，每个特征项再被赋予一个权重，以 表示特征项在该文本中的重要程度，其向量表示为( w l t , w t 2 ，w i n ) ，权重表 示特征项b 对当前文本进行分类的贡献程度；然后通过在训练阶段由人工给出 分类的类别集合和训练文本的集合，并且每个训练文本被标上所属的类别标 西南交通大学硕士研究生学位论文第3 页 志，根据训练文本的特征，利用统计的方法建立起分类模型；在分类阶段，对 待分类文本进行向量描述，通过已建立起的分类模型选取和其相似度最大训练 文本的类别作为该文本的类别 但在实际处理过程中能够发现，对文本这样的高维数据进行分类是一件很 困难的事。特别对于多数信息检索系统来说，每个文本都用维数特别高的描述 向量来描述，常常造成文本的向量维数高达上万维，虽然它表达了所有问题， 但其要求的处理能力甚至超出了最强的计算机处理能力。另外，向量维数的过 于巨大增长了计算机处理文本的时间，往往为用户所不能容忍。 为了降低文本描述向量的维数，很多系统在频率统计的基础上使用了阈值 过滤方法，即将文本描述向量中低于阙值的分量全部去除。这样做虽然能降低 向量的维数，却不可避免地丢失一些有用信息，特别是对于分类很重要的低频 词( 比如某些类别中的专有名词，虽然出现频率很低，但区分类别的作用却很 大) ，最终影响文本检索的精度。 基于规则的文本分类技术，将文本的特征项向量作为规则的前提条件，文 件所属的类别用作规则的决策结果，在训练阶段针对训练文本提取出分类规 则，然后利用这些规则对新文本进行分类验证，最后输出符合分类要求的规则。 基于规则的文本分类技术不像基于向量比较的分类器那样，每个向量的维数必 须等于关键词空间的维数，所以简化了知识系统的处理过程。并且通过这样的 文本描述向量的特征项集合( 分类的前提条件) 是易于被理解的 基于粗糙集l ( r o u g hs e t ) 理论的文本分类算法步骤是：首先给定文本 全集和一个已经分类的文本集合，从己分类的文本集中，得出区别文本类别最 小的特征项集合，然后利用知识约简提取出文本分类的规则，通过将新文本的 向量描述与分类规则是否匹配( 文本适用) 来确定其类别。实际应用系统中表 明，粗糙集理论中的属性约简能够有效地解决文本描述向量维数过大的问题， 而且粗糙集理论还能够产生便于理解和实用的文本分类规则。目前该理论己经 应用到邮件分类和网页分类中，取得了一定效果。 1 2 论文主要工作介绍 本文主要完成以下工作： 1 、研究文本分类过程中的特征选择方法和文本向量模型的权值计算公式 西南交通大学硕士研究生学位论文第4 页 t f - i d f ，采用不同的特征选取方法，对基于文本特征选择方法的改进 t f - i d f 权值计算公式效果进行比较，具体为t f i d f 、t f - s 、t f - i d f s 三种权值计算公式的比较，从而确定出进行文本分类的合适权值计算 公式。 2 、进行粗糙集理论应用于文本分类的研究，生成便于理解的文本分类规 则，具体说来将文本向量离散化处理成“高”、“中”、“低”三种程度 衡量某个特征项在文本中所占的分量，并依此进行分类规则表达。 3 、研究粗糙集理论中的属性约简算法，对利用文本特征选择方法和粗糙 集理论本身的两种不同属性重要性的评价方法进行综合，利用不同的 权重计算公式将c h i 特征选择方法和租糙集理论两种不同属性重要性 评价标准进行组合，详细比较各种属性评价方法在精确约简和近似约 简的表现，从中找出合适的用手启发式属性约简的属性重要性衡量方 法 4 、对于粗糙集理论中的启发式属性约简算法进行改进，将c h i 特征选择 方法和粗糙集理论的缩减分辨能力的组合信息作为一次属性约简信 息，使用粗糙集理论的扩张分辨能力作为二次属性约简信息，从而变 传统的一次约简为二次约简，大大减少了冗余属性，缩减了属性的维 数。 1 3 论文的结构和安排 本文各章的内容安排如下： 第一章：介绍课题研究的背景和论文内容结构 第二章：概述文本自动分类的一般过程，详细介绍包括文本分词、文本描 述模型及常用于文本自动分类的各种方法。 第三章：详细介绍文本特征选择方法，对于经典的文本向量权值计算公式 t f - i d f 进行研究和比较实验。 第四章：概述粗糙集理论及其基于粗糙集理论的文本分类系统各个步骤。 第五章：重点研究基于粗糙集理论的启发式知识约简算法中属性重要性的 衡量方法，并对启发式知识约简算法进行改进。最后通过实验进 行比较研究。 西南交通大学硕士研究生学位论文第5 页 第2 章文本分类概述 一个文本自动分类系统的任务是，在给定的文本分类体系下，根据所提供 新文本的内容自动确定出其应属的文本类别。分类系统分两部分： 1 、建立相应分类模型，描述给定的文本分类体系下预定的数据类集或概 念集。 2 、利用分类模型，分别采用不同的文本分类方法对新文本进行分类。 文本分类过程如图2 - 1 ，图2 - 2 所示： 耋馨娑篥赛诗h 特征选择h 选取合薹斋柰姜柔模型描h 训驾；主骞嚣洗 图2 - 1 文本分类训练过程 选取测试集， 进行文本分词 根据文本描述模型 描述测试文本集 对测试文本集 进行分类 图2 - 2 文本分类测试过程 下面按步骤逐一介绍。 2 1 文本分词( t e x ts e g m e n t a t i o n ) 对分类算法进 行评价分析 文本的基本元素是词、词组和短语，分析文本，就是分析组成文本的词、 词组和短语。文本分词【1 4 1 所起的作用就是将原本连续的字串或序列按照一定的 规范重新组合成词序列以便进行分析。 对于英文文本，单词之间以空格作为自然分界符，不需要进行分词处理， 只需进行还原词根的处理。同英文文本的词与词之间有自然的分隔不一样，中 文的词与词之间没有自然的分隔。另外中文的最小语义单位是词或短语，词是 中文中能独立活动的、有语义的基本语言单元；中文的最小构成单位是字，只 有当由单个汉字组成的句子转化成词之后，才能进行概念抽取，以至于自然语 言理解。但是中文文本中字与字之间、词与词之间并没有明显的分隔界限，这 西南交通大学硕士研究生学位论文第6 页 就需要使用中文分词技术，让计算机自动地把中文中的词与词之间的分界线找 出来。所以，中文分词技术是进行中文信息处理的基础。 中文分词处理是中文信息处理所特有的文本预处理步骤。目前的中文分词 方法m 1 9 j 可以分为两大类：一种是机械匹配的分词方法，其通过和已建立词典 中的词的机械匹配来进行分词处理。所谓机械匹配，是指与己有词典里的词按 一定策略进行匹配，若匹配成功，则将匹配上的词输出到结果，即识别出一个 词，如匹配不上的词常以单字的形式输出。基于机械匹配的分词方法简单，程 序容易实现，开发周期短，实用性强。但受词典的影响大，处理歧义的能力差 另一种是基于概率统计的分词方法。组成中文文本的词是由稳定搭配在一起的 字组成的，因此字与字相邻共现的频率能较好地反映是否为词的概率。在上下 文中，相邻的汉字同时出现的次数越多，就越有可能是一个词。当字符串的出 现频率高于某一阈值时，即可定此字符串为一个词。基于概率统计分词方法只 需对语料库中的字符串组合频率进行统计，并不需要建立专门的词典，所以又 称为无词典分词方法。此方法提供了消除切分歧义的处理方法，处理自然语言 具有很好的一致性和健壮性。但低频词很难被切分出来，还经常抽出一些出现 频度高但并不是词的常用字组。 实际研究中，中文分词技术面临的两个最大问题是切分歧义和未定义词i 捌 的识别。前者属于自然语言理解的问题，根据上下文环境，在不同切分结果中 选择最优解；后者要解决词典中未收录词( 如人名、地名、机构名等) 的识别。 虽然可以在机械匹配的基础上通过规则的方法来解决上述两个问题，然而规则 很难适应多种多样的真实文本。目前比较主流的方法是通过对文字搭配的概率 统计来解决切分歧义和未定义词的识别问题。 国内已经存在很好的中文分词系统，准确率相当高，已经达到实用要求水 平。其中，举两个有代表的分词系统。一个为基于马尔科夫链模型的中国科学 院计算技术研究所汉语词法分析系统【2 l i i c t c l a s ( i n s t i t u t eo fc o m p u t i n g t e c h n o l o g y , c h l l l c s el e x i c a la n a l y s i ss y s t e m ) ，该系统的功能有：中文分词、词 性标注、未登录词识别。分词正确率高达9 7 以上，未登录词识别召回率均高 于9 0 ，其中中国人名的识别召回率接近9 8 ，处理速度为3 1 5 k b y t e s s i c t c l a s 的特色还在于；可以根据需要输出多个高概率结果，有多种输出格 式，支持北大词性标注集和9 7 3 专家组给出的词性标注集合。另一个为天津海 西南交通大学硕士研究生学位论文第7 页 量科技中文分词系统 2 2 1 ，海量科技以“砌词”为突破口，巧妙地解决困扰分词最 大的问题未登录词的识别问题，在其他问题上博采众长各个击破，采用复 方概念平衡各算法，所谓复方，相当于用中药中的复方概念，即用不同的药才 综合起来去医治疾病，使海量分词在大规模语料测试中的准确率达到了9 9 5 ， 分词效率2 0 0 0 万字分钟。 由于中科院的中文分词系统提供源码支持，更适合科研的实际要求，所以 本文的研究都是基于中科院的分词系统基础之上的。 2 2 特征选择( f e a t u r es e l e c t i o n ，f s ) 文本进行分词后，每个词所表示的信息量是不同的，重要性也是不一样的。 一些通用的、多个类别都普遍存在的词对分类所起作用小，而只在某一特定类 别中出现机率大且在其它类别中出现机率小的词汇对文本分类所起作用大。另 外，进行分词后直接得到词的数目往往非常巨大，如果直接用其作为文本处理， 往往使计算机分类处理效率低下，有时甚至超出计算机处理能力。 进行特征选择，就是指尽可能去除那些不能很好表示文本分类信息的词， 保留那些对分类有益的词，从而提高分类效率和减少计算复杂度，也就是从特 征集r - f l ，乞，厶 中选择一个真子集t - “，乞，厶 伽t 露) 其中，n 为原始特征 集的元素个数，m 为选择后的特征集的元素个数。进行选择的准则是经特征选 择后能有效提高文本分类准确率。选择并不改变原始特征空间的性质，只是从 原始特征空间中选择一部分重要的特征，组成了一个新的能完全代表原始特征 空间的低维空间。 特征选择( f e a t u r es e l e c t i o n , f s ) 的思想如文献1 2 3 - 2 7 】所述：构造评价函 数，对原始特征空问中的每个特征进行评价，使得每个特征都获得一个评价分 值，然后对所有的特征按照其评价分值的大小进行排列，按照一定策略选取特 定数目的特征子集。具体选取多少个最佳特征以及采用什么评价函数都需要针 对具体问题通过实验来决定。 在实际进行的文本分类中，用于特征选择的统计量大致有：特征频度( t e r m f r e q u e n c y ) 、文档频度( d o c u m e n tf r e q u e n c y ) 、特征熵( t e r me n t r o p y ) 、互信 息( m u l t i i n f o r m a t i o n ) 、信息增益( i n f o r m a t i o ng a i n ) 、z 2 统计量、特征权( t e r m s t r e n g t h ) 、期望交叉熵( e x p e c t e dc r o s se n t r o p y ) 等 2 8 - 3 2 1 这些统计量从不同的 西南交通大学硕士研究生学位论文第8 页 角度度量特征对分类所起的作用。 对于这些特征选择的介绍和效果将在第3 章进行，在此不作进一步说明。 2 3 文本描述( t e x tr e s p r e s e n t a t i o n ) 进行文本特征选择后，就可以使用得到的特征项来对文本进行描述，这样 各个文本在统一的标准格式下形成可比性。文本的原始内容是人类所使用的自 然语言，表达了丰富的信息，但不能被计算机直接理解，为了让计算机能够理 解，需要把这些信息编码为一种标准形式。基于自然语言处理和统计数据分析 的文本分类中的文本描述实现的就是对从文本中抽取出的元数据( 特征项) 进 行量化，并以结构化形式描述文本信息。这些特征项作为文本的中间表示形式， 在分类时用以评价未知文本与用户目标文本的吻合程度 文本描述现在有很多模型，经常使用的经典模型如下： 2 3 1 布尔模型( b o o l e a nm o d e l ) 布尔模型【3 3 1 是基于集合论和布尔代数最简单的文本描述模型，也是其它文 本描述模型的基础。它是一种简单的严格匹配模型，通过一个二值变量集合来 表示文本，一个变量对应于文本中一个相应的特征项，如果特征项对文本内容 有贡献，则赋为1 ，否则为0 。利用布尔表达式表示用户的查询串，查询串通 常以语义精确的布尔表达式【卅的方式定义，如口- f l 也v - f 3 ) ，t ，为特征项权 值，通过文本与查询串的逻辑比较进行匹配文本与查询串相关度定义为： 跏) - 僻嚣( 2 - 1 ) 如果s i m ( d ；，口) = 1 ，表示查询串q 与文本喀相关，否则就表示q 与文本喀 不相关。 布尔模型优点是实现简单，检索速度快。但是，布尔模型存在以下缺陷： 1 、匹配策略基于二元判定标准( b i n a r yd e c i s i o nc r i t e r i o n ) ，对于一篇文本 的查询来说，只有相关和不相关两种状态，缺乏文本相关性排序( r a n k i n g ) 概 念，精确的完全匹配会导致太多或太少的结果文本被返回，限制了文本查询功 能。 2 、- 布尔表达式需要有精确的语义定义，但实际上用户常常很难将查询需 西南交通大学硕士研究生学位论文第9 页 求的信息转换为布尔表达式。 布尔模型定义特征项只具有两种状态，即在某一篇文本中出现或不出现， 这就导致了特征项权重只表现为二元性，即= 0 ，1 ) 针对特征项权重的选 择，引出了向量空间模型。 2 3 2 空间向量模型( v e c t o rs p a c em o d e l ) 向量空间模型 3 s l ( v e c t o rs p a c em o d a l ，简称v s m ) ，是由g s a l t o n 等人 在2 0 世纪6 0 年代提出的，效果较好、近些年来被广泛应用的一种方法。 向量空间模型的基本思想是使用词袋法【3 6 j ( b a go f w o r d ) 表示文本。这种 表示法基于这样一个关键假设，文章中词条出现的顺序无关紧要，它们对于文 本的类别所起的作用是相互独立的，每个特征词对应特征空间的一维，将文本 表示成欧氏空间的一个向量。 向量空间模型中，文本d i 被看作为由一组特征项( t 1 ，t 2 ，e ee $ t n ) 组成的 n 维向量，在一个文本中。每个特征项都被赋予一个权重，以表示特征项在该 文本中的重要程度，文本正简化为以特征项的权重为分量的向量表示 ( w i t , w 跏w i a ) ，权重啊表示特征项自对文本d 。分类的贡献程度。这样就把非 结构化的文本表示为向量形式，使得各种数学处理成为可能。 所有文本都可映射到此文本向量空间，从而将文本信息的匹配问题转化为 向量空闯中的矢量匹配问题。n 维空间中点的距离用向量之间的余弦夹角来度 量，也即表示了文本间的相似程度。待分类文本x 同样可以表示成向量形式 ( w n ，w 珐。w 。) ，通过比较x 和已经知道的标准文本d - 夹角，夹角越小说明 两文本的相似度越高。其计算公式如下： s i r e ( e l i ，z ) ( 2 2 ) v s m 只是提供了一个理论框架，对于特征项的权值计算、相似度的计算 没有统一的规定，可以使用不同的权重评价函数和相似度计算方法，从而使得 此模型有广泛的适应性，特别是随着网上信息的迅速膨胀，它的应用己经不仅 仅局限于文本检索、自动文摘、关键词自动提取等传统问题，还可以应用到搜 索引擎、个人信息代理、网上新闻发布等信息检索领域中 西南交通大学硕士研究生学位论文第10 页 具体说来，向量空间模型具有以下优点： ( 1 ) 由于文本的内容被形式化为多维空间的一个点，把文本以向量的形式定 义到实数域中，能够使用模式识别和其它领域中各种成熟的计算方法， 极大地提高了自然语言文本的可计算性和可操作性。 ( 2 ) 为特征项引进权重评价函数，通过调节特征项对应权值的大小来反映词 语所在文本的重要程度，部分地克服了传统布尔模型的缺陷。 ( 3 ) 通过计算文本之间的相似度，使属性相似的文本尽量聚拢在一起，可以 适应用户查询多样化以及匹配手段多样化的需要。用户可以根据需求 特点选择一组可供使用的匹配手段。 知识表示( k n o w l e d g er e p r e s e n t a t i o n ) 始终是知识处理( k n o w l e d g e p r o c e s s i n g ) 的主要瓶颈之一，特别在以自然语言为研究对象的知识处理和知识 获取( k n o w l e d g ea c q u i s i t i o n ) 问题中更为突出。向量空间模型的最大优点在于 知识表示方法上的巨大优势。 但该模型也存在一些缺点，主要表现为： ( 1 ) 向量空间的维数往往很高，导致计算量大，有时超出计算机处理能力。 ( 2 ) 向量中特征项的权重衡量标准较难确定。 2 3 3 概率模型( p r o b a b i l i s f i cm o d e l ) 概率模型f 3 3 l 基于以下的基本假设( 概率原刚) ：给定一个用户查询q 和文 本集中的一个文本吐，概率模型试图估计用户找到其感兴趣的文本正的概率， 模型假设这个相关概率只是依赖于查询和文本的表示。 对于概率模型，特征项的权重都是二值的，即峋 o ，1 ， o ，1 ) 。设r 是已知的相关文本集，r 是r 的补集，表示已知的不相关文本集。设p ( r i 彤) 是文本d ；与查询q 相关的概率，p ( r i 彤) 是文本面与查询q 不相关的概率。文 本t 与查询q 的相关度s i m ，口) 可以定义为一个比值 州埘黼 ( 2 3 ) 使用贝叶斯定理，比值写成 嘲) i 勰 ) 其中，p ( 彬i r ) 代表从相关文本集r 中随机选择文本d ，的概率。p ( r ) 代表 西南交通大学硕士研究生学位论文第11 页 从整个文本集中随机选择一个文本是相关的概率。以磁l 尺) 代表类似的从补集 中选择文本的概率，p i r ) 代表从整个文本集中随机选择一个文本是不相关的 概率。因为对文本集中的所有文本来说，p 皿) 和p f 瓦1 都是一样的，于是相关 度可以写为 s i r e ( d , ，g ) 勰 ( 2 5 ) 假设特征项是独立的，那么 s i m ( d i 劫辩鬻 沼6 ， 其中，p o ，l r ) 是特征项f ，在r 集合中某个文本中出现的概率，尸( f “r ) 是 特征项t ；不在r 集合中某个文本中出现的概率。对于集合r ，相似的概率具有 相似的含义。而 p o i r ) + p ( f l r ) - 1 ( 2 - 7 ) p ( f ji r ) + p ( f | r ) - 1 ( 2 - 8 ) 对公式2 6 取对数，有 砌) 一蠢柚g 面p ( t j 丽i s l ) + l o g 絮哿】( 2 9 ) 在公式2 - 9 中关键是要知道p o ，l r ) 1 1 f 率和p ( t si r ) 值。概率模型就是采用 相关反馈的方法，从假设两个初始的概率开始，不断调整概率估计值，直到得 到一个满意的概率排序。 概率模型的主要优点是：从理论上，文本按照其相关概率的降序排列。其 主要缺点包括：需要最初将文本分为相关和不相关的集合：这个方法不考虑特 征项在文本出现的次数，即所有的权重都是二值的。 由于空间向量模型的简单性和高效性，本文的分类系统采用向量空间模 型。 2 4 分类算法( c l a s s i f i c a t i o n a l g o r i t h m ) 原始文本经过分词处理、特征选择等预处理后，利用文本描述模型形成特 征向量用来表示文本，然后就可以进行分类研究了。文本分类方法是一种有指 导的学习方法，它需要利用一个已标记好类别的文本数据集( 即训练集) 来构 西南交通大学硕士研究生学位论文第12 页 造某种分类模型( 也称为分类器) ，然后用训练好的分类器对未标识类别的文 本进行分类。分类器的构造方法有许多种 r m z ，但大部分来自于模式分类，基 本上可以分为三大类。一种是基于统计的方法，如n a i v eb a y e s 、k n n 、类中 心向量、回归模型、支持向量机、最大熵模型等；另一种是基于连接的方法， 即人工神经网络：还有一种是基于规则的方法，如决策树、关联规则等，这些 方法的主要区别在于规则获取方法。 下面介绍一些比较经典的算法： 2 4 1 朴素贝叶斯算法( n a i v eb a y e s ) 朴素贝叶斯分类是一种统计学分类方法，其思想是计算文本属于各个类别 的概率，从中选取概率最大的类别作为文本所属类别。朴素贝叶斯算法首先利 用贝叶斯条件概率公式，计算在已知文本描述向量的条件下该文本属于不同文 本类别的条件概率( 即后验概率) ；然后根据最大似然原理将该文本归为具有 最大后验概率的那一类。之所以称其为朴素的，在于其假设构成文本描述向量 的各个特征项之间相互独立。朴素贝叶斯算法在文本分类研究中受到了广泛重 视和普遍运用。 该模型将文本看作相互独立的特征项集合，通过训练集合，由贝叶斯理论 得到每个特征项在不同类的概率，构造出贝叶斯模型。首先，计算特征项属于 每个类别的概率，特征项吃属于类别c ，的概率为： 毗卜横辩熟 协 在测试新文本时，按下面的公式计算文本d ；属于类c 。的概率： e ( c ；l a , ；b ) - 裂器络 。 其中，p ( c l 占) - 毫燃，p ( c ，i 旬为相似含义，i c i 为文本类别的 总数， r ( m ，4 ) 为特征项m 在4 中的词频，丑为特征项总数。 2 4 2k n n ( k - n e a r e s tn e i g h b o r ) 算法 k n n 算法是一种应用十分广泛的统计模式识别方法，至今己有5 0 多年的 西南交通大学硕士研究生学位论文第13 页 历史。k n n 算法也是最早应用于文本分类的机器学习算法之一k n n 算法的 原理非常简单，对于待判定的新文本，它首先找到与之最为相似的k 个训练样 本。然后根据这k 个训练样本的类别来确定测试样本的类别。 k n n 算法有多种不同的实现形式。对于给定的正整数k 和同一个测试文 本，不同的相似性度量将产生不同的k 近邻集合。最常用的相似度度量为欧拉 距离，或是余弦距离。对于单类别文本分类问题，通常用简单多数( s i r a p l e m a j o r i t y ) 原则确定测试文本的类别。即将k 近邻集合中出现次数最多的类别 作为测试文本的类别。对于多类别文本分类问题，通常用下式计算测试文本的 类别之间的相似度： y 似，q ) 罗5 妇 ，d ) ) ， ，q ) 一6 j ( 2 1 2 ) 其中，s 拥 ，d ) 为d 与d 之间的余弦距离；如果d 属于类别岛，则 y ( d ，c j ) - 1 ，如果d 不属于类别q ，则】， ，q ) - 0 ；b j 为阈值如果 y q ，q ) - o ) o ，k 近邻算法判别测试样本d 属于类别c i ，否则认为测试文本d 不属于类别a ， 在k n n 算法中，一个重要的参数是k 值的选择，k 值选择过小，不能充 分体现待分类文本的特点，而如果k 值选择过大，一些和待分类文本实际上并 不相似的文本却被包含进来，造成噪声增加而导致分类效果的降低。在实际研 究过程中，k 值一般采用测试的方法得到经验值，从而确定k 值。 k n n 是一种懒散的方法，它没有进行学习的训练过程，只是事先简单存 放所有的训练文本集实例，直到接到未知文本的时候才建立分类器。所