（计算机应用技术专业论文）文本分类方法及应用研究.pdf

中国科学技术大学硕士学位论文 摘要 摘要 i n t e m e t 为人们提供了极其丰富的信息资源，在这些海量、异构的w e b 信息 资源中蕴含着具有巨大潜在价值的知识。但是，面对信息的汪洋大海，人们往往 感到无所适从，出现了所谓的“信息过载”和“信息迷向”的现象。对信息进行 自动分类可以在较大程度上解决网上信息异构、杂乱的现象，从而缩减搜索空间， 加快检索速度，提高查询精度。针对目前文本分类方法存在的问题，本文提出了 基于本体的语义分类方法以及基于f i s h e r 判别式的层次分类改进方法，并且将层 次分类技术应用到对等网络中，设计出一种新的文件共享系统。主要工作如下： 1 ) 提出了一种基于本体的文本语义分类方法，扩展了传统的基于统计的贝叶斯 分类策略。我们提出的o n t o n a i v e c l a s s i f i e r 分类算法通过考虑概念对本体的支 持度p 品和单词对概念的支持度r 。，可以实现对文档按照本体分类的目的。 o n t o n a i v e c l a s s i f i e r 算法不仅仅考虑统计结果，而且包含了本体和w o r d n e t 提 供的领域背景知识。通过试验结果，我们发现即使在小训练样本的情况下， o n t o n a i v e c l a s s i f i e r 仍然能够保持较高的准确性。 2 1 提出了一种基于f i s h e r 判别式的改进型层次文档分类方法。该算法利用f i s h e r 判别式来提取每个类的特征词，特征词既不需要假设条件也不会因为层次的 增加而失效，而且特征词的维数显著减少，降低了计算复杂度。更重要的是， 我们提出的改进型方法强调层次分类的全局性，对处于分类树上较高层次的 类别，不再仅仅着眼于目标文档与单个类别的关系，而是考虑目标文档与以 这些类别为根的子树的关系，从而提高了层次分类的正确率。实验结果表明， 我们提出的改进算法在精确率和召回率方面明显优于其它的层次分类算法。 3 ) 利用层次分类方法管理和组织p 2 p 系统的共享文件信息，设计出一种新的信息 网络构架c t b c h o r d 。总的策略是利用c h o r d 系统定位高效的优势，引入文本 层次分类方法，将分类树作为系统的中心数据结构，形成一个新的信息网络 框架。用户的信息发布、更新以及获取不再基于关键字而是依赖于其类别属 性。由于分类树本质上是概念细化的一种体现，能够提供一种清晰的资源导 航作用，所以在我们设计的新型p 2 p 文件共享系统中，信息检索将会变得容易 很多。不仅如此，分类树具有良好的可重构性，用户可以部分下载自己所感 兴趣的子树，组装成自己的个人分类树，进行个性化的共享信息定制。 关键词：文本分类、本体、语义分类、层次分类 中国科学技术大学硕士学位论文 a b s t r a c l a b s t r a c t t h ei n f o r m a t i o no nt h ei n t e m e ti sv e r ya b u n d a n t h o w e v e ro nt h eo t h e rh a n d ，t h e i n f o r m a t i o nn e e d e dc a n n o tb ec o n v e n i e n t l yf o u n d t h er e a s o ni st h a tt h ei n f o r m a t i o n s y s t e m sn o we x i s t i n gh a v en o tw e l lo r g a n i z e dt h e i n f o r m a t i o nr e s o u r c e s t e x t c l a s s i f i c a t i o ni sh e l p f u li nr e s o l v i n gt h i sp r o b l e m i nt h i sp a p e r , w ef i r s t l y p r o p o s ean o v e ls e m a n t i c a l l y - b a s e dc l a s s i f i c a t i o n a l g o r i t h m g i v e na no n t o l o g ys e t ，w ew i l lc a l c u l a t ec a t e g o r yp r o b a b i l i t yo faw e b d o c u m e n tt oag i v e no n t o l o g yb yn a i v eb a y e sm e t h o di n t e g r a t i n gt h es u p p o r tp c d ( t h e s u p p o r tf o rac o n c e p t t oi t sa f f i l i a t e do n t o l o g y ) a n dp 。( t h es u p p o r to ft h ew o r di nt h e w e bd o c u m e n tt oe v e r yo n t o l o g yc o n c e p t ) t h ee x p e r i m e n t a lr e s u l t ss h o wo u r a l g o r i t h mi se f f e c t i v ef o ro n t o l o g y b a s e dc l a s s i f i c a t i o n t h e n ，w ep r e s e n tah i e r a r c h i c a lt e x tc l a s s i f i c a t i o na l g o r i t h mb a s eo nf i s h e rl i n e a r d i s c r i m i n a n t t h ea l g o r i t h mo v e r c o m e st h ea s s u m p t i o nt h a tt h ef e a t u r ew o r d sa p p e a r i n d e p e n d l yi nd o c u m e n t s c o m p a r e dw i t ho t h e rh i e r a r c h i c a lc l a s s i f i c a t i o na l g o r i t h m s ， t h ef e a t u r ew o r dd i m e n s i o no ff i s h e rm e t h o di sr e m a r k a b l yr e d u c e d w h a t sm o r e ， o u ra l g o r i t h md e a l sw i t ht h ep r o b l e mo f “g l o b a l - c l a s s i f i e r s b yc o n d i s e r i n gt h e r e l a t i o n s h i po fad o c u m e n tw i t has u b t r e e i nc o m p a r i s o nw i t ho t h e ra l g o r i t h mb y u s i n gt h em e a s u r eo fr e c a l la n dp r e c i s i o n ，t h ee x p e r i m e n t a lr e s u l t ss h o wo u ra l g o r i t h m i sm o r ee f f e c t i v ea n dp r e c i s e a tl a s t ，w ed e s i g nap 2 pf i l es h a r i n gs y s y t mn a m e dc t b c h o r d i ti n t r o d u c e st h e c a t e g o r yn o t a t i o nt os l o v et h ep r o b l e mo ft h ed i s o r d e r l yi n f o r m a t i o nm a n a g e m e n ti n p 2 pn e t w o r k c a t e g o r yt r e e ，ah i e r a r c h i c a l l yi n d e x e ds t r u c t u r ea n da ni n f o r m a t i o n m a n a g e m e n ts t r u c t u r eu s i n gt h eh i e r a r c h i c a lc o n c e p t ，i st h ek e r n e ls t r u c t u r ea sw e l la s t h ei n n o v a t i o ni nc t b c h o r d i tp r o v i d e sas i m p l ew a yf o ru s e r st op u b l i s ha n do b t a i n t h ef i l e s ，a n df o r m san o v e li n f o r m a t i o nn e t w o r kf r a m e t h ee x p e r i m e n t a lr e s u l t s s h o wt h a tc t b c h o r dh a st h ep r o p e r t i e so fs c a l a b i l i t y ，e f f e c t i v e n e s sa n df r i e n d l i n e s s 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 ，o n t o l o g y , s e m a n t i c a l l y b a s e dc l a s s i f i c a t i o n ， h i e r a r c h i c a lc l a s s i f i c a t i o n h 中国科学技术大学硕士学位论文图表目录 图表目录 2 1 文档分类流程图8 2 2o n t o l o g ya n dw e bi n t e l l i g e n c e 1 7 2 3d lj a m e sh e n d l e r 的主贞一2 0 3 1u n i v e r s i t y 本体2 3 3 2c o m p a r i s o no ft h ea c c u r a c yo fo n t o n a i v e c l a s s i f i e ra n dn a i v eb a y e s 2 9 3 3c o m p a r i s o no ft h ea c c u r a c yo fo n t o n a i v e c l a s s i f i e ra n dn a i v eb a y e s 2 9 3 4 c o m p a r i s o no f t h e a c c u r a c yo f o n t o n a i v e c l a s s i f i e r a n d n a i v e b a y e s 2 9 4 1 分类树结构示例3 2 4 2f i s h e r 判别方法示意图3 4 4 3c a t e g o r yt r e e sf r o mr e u t e r sc o l l e c t i o n ，4 1 4 4 特征词个数s 与分类精度关系图4 2 5 1c t b c h o r d 层次结构 5 2c t b c h o r d 查找路由举例图 5 3 搜索平均跳转次数( n = 5 ) 5 4 搜索平均跳转次数( n = 1 0 ) 4 7 4 8 5 5 一 一5 6 3 1c o n c e p t sw i t ht h e i ir e l e v a n tw o r d s 3 2o n t o l o g yu s e di no a re x p e r i m e n t ， 4 1 分类树使用训练文档和测试文档的数目 一2 3 2 8 ，一4 1 4 2 分类结果的精确率与召回率比较 5 1 搜索平均跳转次数( n = 5 ) 5 2 搜索平均跳转次数( n = 1 0 ) 4 2 一) ) 一 5 6 v 图图图图图图图图图图图图图图图 表表表表表表 中国科学技术大学硕士学位论文第1 章引言 第1 章引言 1 1 文本分类的目的和应用领域 2 0 世纪9 0 年代以来，i n t e r n e t 作为一个开放的、分布式的信息空间得到了飞 速发展，i n t e r n e t 上的资源和服务均呈现出指数级的增长趋势。人们真正处于一个 “信息爆炸”的时代。一方面，i n t e m e t 为人们提供了极其丰富的信息资源，包括 技术资料、新闻报道、商业广告、影视娱乐等多种类型和形式的信息l lj 。在这些 海量、异构的w e b 信息资源中，蕴含着具有巨大潜在价值的知识：另一方面，面 对信息的汪洋大海，人们往往感到束手无策、无所适从，出现了所谓的“信息过 载”和“信息迷向”的现象吼人们迫切需要能够从w e b 上快速有效地发现、过 滤和管理资源和知识的工具。 为了帮助人们提高信息检索( i n f o r m a t i o nr e t r i e v a l ) 2 9 】的质量和效率，陆续 有一些功能强大的搜索引擎( 例如：g o o g l e 、y a h o o 、a l t av i s t a ) 问世。这些搜 索引擎在给人们带来很大便利的同时，也暴露出以关键词为基本索引单位的搜索 引擎仍然存在着很多不足：一方面，无论怎样选择关键词，都会返回过多的候选 信息，其中用户真正需要的信息往往只占很小一部分，用户不得不花费相当多的 时间对候选结果进行人工筛选：另一方面，由于许多与查找主题有关的文档中并 不包含用户输入的关键词，故搜索引擎不能找出这些文档。对信息进行自动分类 是解决上述问题的有效途径，它可以在较大程度上解决网上信息异构、杂乱的现 象，从而缩减搜索空间，加快检索速度，提高查询精度。因此对网络信息资源进 行自动分类成为信息检索过程中具有较大实用价值的关键技术，也是信息产业面 临的新的挑战和新的发展契机。 信息检索的对象包含文本、图形、图像和声音等内容口1 3j ，由于目前网上信息 的表现形式大多数为文本，比如新闻、电子杂志、电子邮件、技术报告以及网上 图书馆等等，而且文本也是广大用户所习惯接受的形式，因此本文主要讨论文本 分类的方法和应用。 目前利用文本分类技术，在短期内可能有所突破的研究工作主要在一下几个 方面【4 】o 冗余过滤 美国斯坦福大学教授n a r a y a n a ns h i v a k u m a r 对i n t e r n e t 上网页进行统计的结 果表明，近似网页数lr t 总网页数的比例高达2 2 ，快速检测这些冗余文档- j i ：从资 源库中删除，可以节省大量的存储空间，提高信息检索的质量。冗余文档有两种 类型：一种是重复文档，它们是没有一点改动的拷贝，知识文件的的物理位置、 中国科学技术大学硕士学位论文第1 章；f 言 建立和修改的时间或者格式不同；另一种是近似( n e a r - - r e p l i c a s ) 文档，它们 只作了微小的修改，例如网络新闻标题、正文略作修改就被大量转载。采用文本 分类技术可以比较所有文档之间的相似度，如果两篇文档的相似度超过某一闽 值，就可以认为它们是相同的。冗余过滤的正确率一般都比较高，在9 5 左右。 组织管理 信息的加工和整理能够使人们更好地掌握信息。在搜索引擎上，随便输入一 个查询式，就能得到成千上万个返回结果，如果你想作全局了解的话，除了逐篇 阅读别无他途。一种可行的解决办法就是把获得的大量信息进行条理化，自动地 将页面分类到不同的类目当中【6 】。分类法的特征在于知识的系统性。y a h o o 采用 人工分类的方法来填充其分类类目，而g o o g l e 则利用文本分类技术填充其分类类 目。很难比较两个搜索引擎的分类体系优劣差别，不过有一点非常明显，g o o g l e 收藏的网站个数远远多于y a h o o 收藏的网站个数，因此，采用文本分类技术来辅 助网络信息资源的组织和管理，不仅能够节省大量的人力，而且能够管理更多的 资源。 智能检索 现在的很多声名显赫的搜索引擎，比如g o o g l e 、y a h o o 、e x c i t e 等，尽管它 们的检索能力己经非常有效，但并非所有问题都已经解决。实际使用过搜索引擎 的人想必都有过这回综体会：想查的东西查不着，不相关的东西倒是很多。构造 更好的信息检索系统仍然是人们努力的目标。在搜索引擎的构建过程中，可以利 用文本分类技术来概念区别，改进相关度排序，也可以对被检索的信息按照一定 的分类体系进行自动分类。 用户个性化服务 每个用户都有自己特定的信息需求，很多时候用户希望自己能够像订阅报纸 一样，可以订阅i n t e r n e t 上的信息。信息过滤系统可以利用文本分类技术，根据一 个初始信息发现命令，然后根据用户反馈来调整其兴趣变化，或者干脆连这一步 都省略掉，由某种机制从用户的浏览历史行为中学习出用户的兴趣，进而使用这 些信息需求组成过滤条件，对信息资源进行过滤，就能把符合条件的信息抽取出 来进行服务。这种信息过滤系统可以提供个性化、主动化的“信息找人”服务【8 】a 个性化的实质是针对性，即对不同的用户采取不同的服务策略，提供不同的服务 内容；主动服务的实质是主动性，即不需要用户做什么，系统会自动按照用户的 需求来提供相应的服务。 以上所说的只是文本分类技术应用的几个m ，它们还可以用在元数据提 取、构建索引、歧义消解、文本过滤等领域。凶此，辽欠利科学家f a b r i z i os e b a s t i a n i 中国科学技术大学硕士学位论文第1 章引言 认为文本分类技术可以被看作是所有基于内容的文本信息管理的基础1 9 1 。由此可 以看出文本分类技术在信息处理领域的重要性。 1 。2 文本分类技术的发展 文本分类技术的发展有三个阶段：基于知识工程的人工文本分类、基于统计 和机器学习方法的文本自动分类、基于自然语言理解和背景知识的智能型信息分 类。 人工文本分类 传统的基于知识工程的文本分类方法要求在领域专家的辅助下对每一个分 类的特征进行人工判定，给出识别的规则。这是一个极其耗时耗力的工作，性能 的好坏依赖于专家的水平，并且当类别发生变化时，需要专家重新定义规则。随 着电子文档爆炸式的增长，以及对文本分类的要求越来越高、分类的需求变化越 来越频繁，传统的基于知识工程的方法已经显得苍白无力，无法满足新的需求。 文本自动分类 目前，已有不少统计分类法和机器学习方法被应用到文本分类中，且都取得 了相当好的效果，这其中包括：向量空间模型【1 0 1 、最近k 邻居方法【1 1 i 、决策树 模型【、n a i v eb a y e s 模型1 ”、支持向量机【1 5 】和神经网络 1 6 】等。基于统计和机 器学习的自动文本分类方法自动化程度高、性能稳定、适应性强，并且相比比人 工文本分类更加有效，所以现在得到了广泛的应用。 智能型文本分类 g o o g l e 和y a h o o 等目前最先进的搜索引擎，进行信息检索时仅仅依赖于字 符串匹配或者模糊匹配，使得搜索结果缺乏精确性和灵活性，根本不能满足用户 的需求。人们迫切希望搜索引擎能够更多些智能，能在上网过程中更多地了解 和学习自己喜好的信息类别，并且系统能够及时将互联网上对用户有用的东西送 到眼前，实现“信息主动找人”的梦想，而不是今天的“人找信息”，就像“智 能狂拼”等智能型汉字输入法一样( 学习使用者的输入习惯，形成对应于该使用 者的输入词库) ，这是可以做到的n 从上个世纪九十年代开始，基于自然语吉 理解和背景知识的智能型信息分类技术正受到越来越多的关注，在下一代语义网 ( s e m a n t i cw e b ) 1 2 0 】时代它将成为重要和主流的文本分类技术。 1 3 文本分类方法的种类 根据预先给定的分类体系和最终的分类结果的不同，文本分类算法可以分为 两类：平面分类( f l a tc l a s s i f i c a t i o n ) 和层次分类( h i e r a r c h i c a lc l a s s i f i c a t i o n 、 在分类过程中，我们角书把义欠0 0 看成是互不相交的，它们处在同一个一- u j ，、 中国科学技术大学硕士学位论文第1 章引言 次上。实际上，现有的绝大多数文档分类系统也就是这样处理的。然而，文档概 念类别之间存在着层次关系，即一个大类往往包含许多小类，小类之下又有更小 的类。而且，当文档库特别庞大时，人们往往也是按照概念层次结构对文档库中 的文档进行管理。因此，按照层次结构对文档库进行分类更能体现文档之间的语 义关系。目前文本的平面分类技术已经发展的比较成熟，分类的正确率平均达到 9 0 以上，但是分类器对于文本层次分类和并行处理方面的研究有待加强，这也 是制约其应用到搜索引擎上的瓶颈。 1 。4 目前文本分类方法存在的不足 1 , 4 。1 基于统计和机器学习的文本分类方法存在的问题 目前，人们使用最多的是基于统计和机器学习的自动文本分类方法。但是， 基于统计和机器学习的分类方法都是通过分析训练文档得到分类的模式，它们存 在难以克服的弊端1 9 j 。 1 ) 抗干扰能力差，必须对大量的训练文档进行分析模拟，才能有一定的精确度。 2 ) 通过机器学习和统计的方法对类别提取的特征信息往往比较庞大，因此运算 开销很大。 3 ) 在文本分类的有关研究中，当前比较流行并且被证明为有效的数学模型是向 量空间模型( v e c t o rs p a c em o d e l ，v s m ) 。向量空间中的特征向量是由“特 征项”构成的。在文本分类的研究中很多人都用词表示特征向量中的特征项。 这样做的结果只是注重了词形，而没有考虑词义。作为文章和类别的表示， 特征向量并不一定代表了文章所要表达的意思。采用词作为特征项、以向量 空间模型作为数学模型的文本分类方法，在达到一定程度的分类效果之后， 没有进一步的提高【7 j 。所以将语义信息应用于文本分类，会取得更好的分类 效果。 1 。4 2 文本层次分类算法存在的问题 目前常见的文本层次分类算法采取“分而治之”的策略，即将层次分类问题 逐层分化为一个个的局部分类问题，在分类树的每内部节点分别建立分类器。 虽然目时层次分类算法有许多陋55 1 ，但是这些算法的 二耍区别在f 它们选择不同 的平面分类算法构造分类树内部节点的子分类器，l l i i i 肯的选择n a i v eb a y e s ， 有的则选择s v m 疗法等等。目前的文本层次分类算法仍存存搬移小足，主要有 中国科学技术大学硕士学位论文第1 章引言 下几个方面 s o , s t 。 1 层次分类算法特征词( f e a t u r ew o r d s ) 的选取方法很多( 1 7 - l 9 1 它们有的需要 一定的假设条件，例如n a 飓b a y e s 模型就假定特征词之间满足独立性条件。但 这些假设不一定成立，因此方法不够准确；也有利用层次结构的特点来提取特征 词，但是随着层次的增加将会失效。 2 大多数层次分类方法将要归类的文档分配到分类树的叶节点，而事实上有的 文档( 如综合性的、边缘性的、交叉性的) 可能涉及到若干个类，如果硬性将它 归于叶节点显然不太适合，而应该分配到层次更高的节点( 内部节点) 。 3 更要的是，层次分类其实是一个全局性的问题，但是实际操作中人们往往只 追求“局部最近”，造成分类的准确率不高。目前几乎所有的层次分类算法沿着 分类树从上往下为目标文档选择合适的类别时，在同一层次只会按照某种分类算 法选择和目标文档最接近的一个类别，然后沿着以该类别为根的子树继续往下判 别。这是十分不精确的，因为我们无法通过某个祖先节点和目标文档的关联度就 能断定其子孙节点和目标文档的关联度。而且，如果我们只追求“局部最近”的 原则，那么所有的文档都将只能最终归为一个类别，这对很多交叉性的文档也是 不合理的。 4 为了达到准确分类的目标，目前一些层次分类算法只能采取两种策略：第一 增加对每个类选取特征词的数量，使得每个类的局部分类器更加准确；第二考虑 全局性，尽可能对分类树的更多类别进行判定。这两种策略都将大大增加层次分 类的计算量，降低分类速度。特别是对于分类树结构庞大或者存在多棵分类树的 情况，这种追求分类精度的方法是不实际的。所以说对于目前的文本层次分类算 法，如何同时达到较低的计算复杂度和较高的分类精度是一个亟待解决的目标。 1 5 本文主要工作和贡献 针对目前文本分类方法存在的问题，本文提出了基于本体的语义分类方法以 及基于f i s h e r 的层次分类的改进方法，并且将层次分类技术应用到对等网络中， 设计出一种新的文件共享系统。主要内容如下： 1 ) 提出了一种基于本体的文本语义分类方法，扩展了传统的基于统计的贝叶斯 分类策略。我们提出的o n m n a i v e c l a s s i f i e r 分类算法通过考虑概念对本体的 支持度p c o 和单词对概念的支持度p w c ，可以实现对文档按照本体分类的目 的。因为o n t o n a i v e c l a s s f i e r 不仪仪考虑统计结果，而且包含了本体和 w o r d n e t 提供的领域背景知识，嘲此在小训练样本的情况下， o n t o n a i v e c l a s s i f i e r 仍然能够保持较尚的准确性。 2 ) 提出了一种基于f i s h e r 线性判别，的。i 进型层次文档分类方法。一方面，它 中国科学技术大学硕士学位论文 第1 章引言 利用f i s h e r 线性判别式的思想来提取每个类的特征词，特征词既不需要假设 条件，也不会因为层次的增加而失效。相对于其它的分类算法，用f i s h e r 方 法提取每个类的特征词的维数会显著减少，大大降低了计算复杂度；另一方 面，改进型方法强调层次分类的全局性，对于处于分类树上较高层次的类别， 不再仅仅着眼于目标文档与类别自身的关系，而是考虑目标文档与以这些类 别为根的子树的关系，这样可保证在减少计算量的同时提高层次分类的正确 率。 。 3 ) 利用层次分类方法管理和组织p 2 p 系统的共享文件信息，设计出一种新的信 息网络构架c t b c h o r d 。总的策略是利用c h o r d 系统定位高效的优势，引入 文本层次分类方法，将分类树作为系统的中心数据结构，形成了一个新的信 息网络框架。分类树本质上是概念细化的一种体现，它提供了一种清晰的资 源导航作用。用户的信息发布、更新以及获取不再基于关键字而是依赖于其 类别属性。在这个新型的p 2 p 文件共享系统中，信息将变得有序，从海量信 息中进行信息发现也会变得容易很多。不仅如此，由于分类树具有很大的可 重构性，用户可以部分下载自己所感兴趣的子树，组装成自己的个人分类树， 进行个性化的共享信息定制。 1 6 论文组织结构 本文共分为六章，每一章内容如下： 第一章：引言。提出了文本分类的目的和应用背景，并简要介绍了文本分类 技术的发展和目前面临的问题随后阐述了进行基于语义分类的意义。最后 提出了本文的研究焦点和研究成果。 第二章：文本分类方法概述以及相关技术。简要介绍了文本分类的定义、要 解决的问题，以及常见的分类算法。并阐述了本体和w o r d n e t 等语义背景知 识。 第三章：基于本体的文本语义分类算法。 第四章：基于f i s h e r 的改进型文本层次分类算法。 第五章：基于层次分类的p 2 p 文件共享系统。 第六章：结论与工作展望。总结了全文，并对进一步的工作进行了说明。 中国科学技术大学硕士学位论文 第2 章文本分类方法概述及其相关技术 第2 章文本分类方法概述及其相关技术 分类是人类认识世界、区分客观事务的一种思维活动，也是根据事务的“共 性”与“特性”聚集相同事物、区分不同事物的手段。人们既可以通过分来来认 识与区分事物，也可以通过分类使大量的繁杂事物条理化和系统化，从而为进一 步探讨事物本质、开展科学研究创造条件。 文本分类是按照预先定义的主题类别，在分析文本内容的基础上为每个文档 确定一个或多个合适的类别。分类在数据挖掘中是一项非常重要的任务。通过文 本自动分类，一方面可以提高信息检索的准确度，另方面更能大大减少网络的 数据流量。用户不但能够方便的浏览文档，而且可以通过限制搜索范围来使文档 的查找更为容易。文本分类作为组织和管理数据的一种有力手段，可被用于文本 过滤、基于控制词汇的自动文本索引”l 、词义排歧t 2 “、类y a h o o ! 方式的对w e b 资源进行层次管理口5 】以及其它的一些要求文件管理或文件选择性发送的领域【2 刨 等。 这一章我们将简要的介绍文本分类的定义、关键技术和常见的分类算法。在 此基础上，我们将介绍语义分类的相关概念和背景。 2 1 文本自动分类问题的一般描述 文本自动分类是一个有监督的学习过程。一般地，它根据一个已经被标注( 即 分好类) 的训练文档集合，找到文档特征和文档类别之间的关系模型，然后利用 这种学习得到的关系模式对新的文档进行类别判断。 简单地说，文本分类系统的任务是：在给定的分类体系下，根据文本的内容 自动地确定文本关联的类别。从数学角度来看，文本分类是一个映射的过程，它 将未标明类别的文本映射到已有的类别中，该映射可以是一一映射，也可以是一 对多的映射，因为通常篇文本可以同多个类别相关联。用数学公式表示如下： f ：a 斗b 其中，a 为待分类的文本集合，b 为分类体系中的类别集合 文本分类的映射规则是系统根据已经掌握的每类若干样本的数据信息，总结 出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据总结 出的判别规则，确定文本相关的类别。 总体上，文本自动分类主要有五个问题需要解决：获取i l l 练文档集、建立文 档表示模型、文档特征抽取、选择或设计分类模型、性能评估模型。 文本的自动分类算法的流程结构如图2 1 所示。 中国科学技术大学硕士学位论文第2 章文本分类方法概述及其相关技术 图2 1 文档分类流程图 由图可见，属性选择、分类训练和测试评估构成一个循环：根据测试结果 调整属性选择和分类训练的参数，使得分类器具备更佳的分类效果。 2 1 1 获取训练文档集 训练文档集选择是否适合对文档分类器的性能有较大影响。训练文档集应该 能够广泛代表分类系统所要处理的、实际存在的各个类别中的文档。一般地，训 练文档集应该是公认的经人工分类的语料库。国外文档分类研究都使用共同的测 试文档库，这样就可以比较不同分类方法和系统的性能。 2 1 2 建立文档表示模型 建立文档表示模型是一个重要的技术问题，它将决定选用什么样的文档特征 来表征文档。文档表示模型主要有布尔模型和向量空间模型。目前在信息处理领 域，文本的表示主要采用向量空间模型( v s m ) 。向量空间模型的基本思想是以 向量( w w 2 , ，w 。) 来表示文本，其中w ，为第爪特征项的权重。那么选取什么作 为特征项呢? 一般可以选择字、词或词组，根据实验结果，普遍认为选取词作为 特征项要优于字和词组。因此，要将文本表示为向量空间中的一个向量，就首先 要将文本分词，经过简单地预处理程序( 比如去除停用词、还原词根等) ，然后 统计词频，最终表示为上面描述的向量。由这些浏作为向量的维来表示文本。最 初的向量表示采用二值形式，即如果文本中出现了凌词，那么文本向量的该维设 置为l ，否则为0 。由于只用0 和1 无法细致地体现词存文本中的作用程度所咀这 种二值表示法逐渐被更精确的词频代替。词频分为绝对词频和相对词频。绝对词 频即使用词在文本中出现的频率来表示文本，干h 州洲频为归一化的词频，其计算 方法主要运用t f i d f 口“公式。 中国科学技术大学硕士学位论文第2 章文本分类方法概述及其相关技术 绝对词频表示法 集合d 是文档集合，它的元素用d 表示。集合产t 2 , 一：靠) 表示所有在d 中出 现的不同的单词集合。t f ( d , o 表示t e r m 庄文档d 中出现的频率。绝对词频表示方法 用向量t d = - ( t f ( d , h ) ，。t q f 圳表示一篇文档，f 提由文档集d 中每个单词在某篇文档 d 中出现的频率组成的矢量。 相对词频表示法 t f i d f 方法不同于绝对词频表示法，它乘以一个因子来削弱那些几乎在所有 文档中出现的单词的频率。t f i d f 的计算公式如下： n l t f i d f ( d ，f ) ：= l o g ( d ，t ) + 1 ) + l o g ( 蔷某) 可u j 其中d f ( o 表示的是单词f 在其中出现的文档的频率。 现在我们用频率t f i d f 4 弋替绝对词频向量耐中的频率乒于是我们将向量 耐：= ( t f ( d , t j ) ，；c ，m t o ) 修正为t f i d f = ( t f i d f ( d , h ) ，一5 t f i d f ( d , 锄。这个结果就是通过 t f i d f 方法得到的文档的相对词频表示向量。我们可以看到那些出现过少或者过 多的单词对聚类结果的贡献是很小的。 2 1 3 文档特征抽取 文档分类系统应该选择尽可能少、准确并且与文档主题密切相关的文档属性 进行文档分类。但是由于构成文本的词汇数量是相当大的，表示文本的向量空间 的维数也相当大，可以达到几万维。因此我们需要进行维数约减的工作，这样做 的目的主要有两个：第一，提高程序的效率，提高运行速度；第二，所有几万个 词汇对文本分类的意义是不同的，一些通用的、各个类别都普遍存在的词汇对分 类的贡献小，在某特定类中出现比重大而在其他类中出现比重小的词汇对文本分 类的贡献大。为了提高分类精度，对于每一类，我们应去除那些表现力不强的词 汇，筛选出针对该类的特征项集合。存在多种筛选特征项的算法，比如根据词和 类别的互信息量判断、根据词熵判断以及根据k l 距离判断。目前利用词和类别 的互信息量进行特征项抽取的判断标准比较常见，其算法过程如下： 1 ) 初始情况下，该特征项集合包含所有在该类中出现的词。 p ，wr 、 2 ) 对于每个词，计算词和类别的互信息量l o g ( 二妄未三卫) 。 其中，尸( 缈i c ) = l + ：( ，) y l + 羔，： 一，p ( i c ，) 为f 嘧g 中出现的比 d ，) 重，1 d l 为该类的训1 练文本数，r 阿：以，山浏在西中的词频，i ”为总词数 中国科学技术大学硕士学位论文 第2 章文本分类方法概述及其相关技术 竺詈( k ，一) 为该类所有词的词频和。而p r 聊同上面的计算公式相同， 知识计算词在所有训练文本中的比重，其中，为全体训练文本数。 3 ) 对于该类中所有的词，依据上面计算的互信息量排序。 4 ) 按照排序，取一定数量的词作为特征项。具体需要抽取多少维的特征项，目 前无很好的解决办法，般采用先定初始值，然后根据实验测试和统计结果 确定最佳值，初始值一般定在几千左右。 5 ) 将每类中所有的训练文本，根据抽取的特征项，进行向量维数约减，精简向 量表示。 其它抽取特征项的算法，除判断函数上有所差别，主要过程类似。 2 1 4 选择或设计分类模型 选择分类模型实际上就是要使用某种方法，建立从文档特征到文档类别的映 射关系，是文本分类的核心问题。现有的分类方法主要来自两个方面：统计和机 器学习。基于机器学习的英文自动分类已经取得了很好的成绩，提出了多种特征 抽取方法和分类器。如回归模型、最近邻分类、朴素贝叶斯分类、决策树、支持 向量机、规则学习算法、相关反馈、选举分类、神经网络、最大熵等。国内在中 文分类领域也进行了大量的研究，但由于语料和评价方法各不相同，很难对它们 做出严格的比较。 2 1 5 性能评估模型 文本分类系统的建立，需要对系统使用的分类方法或分类器进行性能评价分 析，性能评测是分类处理流程中的重要一环。同时，寻找能够真正反映文档分类 内在特征的性能评估模型，对改进和完善分类系统也具有指导意义。目前使用比 较多的分类性能评估指标为准确率和查全率，这是来源于信息检索的两个术语。 准确率是所有判断的文本中与人工分类结果吻合的文本所占的比率。其数学 公式表示如下：准确率( e c i s i o n ) = 萎 | ；| 昙罴 查全率是人工分类结果应有的文本中分类系统吻台的文本所占的比率，其数 学公式表示如下：查全率c r e c 洲，= 坌篙墨；霎；墨竽 准确率和查全率反映了分类质量的两个不同方嘶，两者必须综合考虑，不可 偏废，因此，存在一种新的评估指标，f 1 删试值，其数学公式如下： 中国科学技术大学硕士学位论文第2 章文本分类方法概述及其相关技术 砌撇= 篙鬻 另外有微平均和宏平均两种计算准确率、查全率和f l 值的方法。 微平均：计算每一类的准确率、查全率和f l 值。 宏平均：计算全部类的准确率、查全率和f l 值。 所有文本分类系统的目标都是使文本分类过程更准确，更快速。 2 2 常用分类算法 文档分类解决的是将一个文档分到一个或多个己确定的主题类别中的问题， 它的研究最早可以追溯n 2 0 世纪6 0 年代初期，但是直到2 0 世纪9 0 年代才被得以重 视。目前，文档分类问题己经得到非常深入且广泛的研究，常见的基于统计的分 类方法有简单向量距离分类法、贝叶斯分类法、近邻学习算法、支持向量机等， 基于机器学习的方法有决策树方法和神经网络方法等。这些优秀的分类方法陆续 被提出并广泛应用到信息检索口”、信息过滤、知识管理、专家系统等应用系统中。 这里简单介绍几种常用文档分类方法。 2 2 1 简单向量距离分类法 该方法的分类思路十分简单，根据算术平均为每类文本集生成一个代表该类 的中心向量，然后在新文本来到时，确定新文本向量，计算该向量与每类中心向 量间的距离( 相似度) ，最后判定文本属于与文本距离最近的类，具体步骤如下： 1 ) 计算每类文本集的中心向量，计算方法为所有训练文本向量简单的算术平均 2 1 新文本到来后，分词，将文本表示为特征向量 3 ) 计算新文本特征向量和每类中心向量问的相似度，公式为： s i m ( d ，d ，) = 。 其中，西为新文本的特征向量，砖为第，类的中心向量，m 为特征向量的维 数，为向量的第雠。 4 ) 比较每类中心向量与新文本的相似度，将史术分到相似度最大的那个类中。 中国科学技术大学硕士学位论文 第2 章文本分类方法概述及其相关技术 2 2 2k n n ( k 最近邻居) 算法 近邻学习算法的分类方式是通过查询已知类似例子的情况，来判断新例子与 已知例子是否属于同一类。这是惰性学习的范例( l a z yl e a r n i n gp a r a d i g m ) 。尽 管近邻算法存在许多变种但其一般思路是：首先存储全部( 或选择部分) 训练 例子。对于测试例子，通过相似性函数计算它与所存储的训练例子的距离以决定 类别的归属。k 最近邻算法是在模式识别领域非常著名的统计算法，它在文档分 类研究开始兴起时就已经被应用到了文档分类上，并且也已经被证明是最优秀的 文档分类方法之一 2 8 1 。 该算法的基本思路是：在给定新文本后，考虑在训练文本集中与该新文本距 离最近( 最相似) 的k 篇文本，根据这k 篇文本所属的类别判定新文本所属 的类别，具体的算法步骤如下： 1 ) 根据特征项集合重新描述训练文本向量 2 ) 在新文本到达后，根据特征词分词新文本，确定新文本的向量表示 3 ) 在训练文本集中选出与新文本最相似的k 个文本，计算公式为： s i m ( d i ，d s ) = x 1 ( 否m 嚷) ( 荟m 略) 其中，k 值的确定目前没有很好的方法，一般采用先定一个初始值，然后根 据实验测试的结果调整k 值，一般初始值定为几百到几千之间。 4 ) 在新文本的k 个邻居中，依次计算每类的权重，计算公式如下： p ( 夏，c ，) = s i m ( 哥，d ，) ，( d 。，c ，) 一b ， d e k n n 其中，牙为新文本的特征向量，s i m ( 牙，d i ) 为相似度计算公式，与上一步骤的 计算公式相同，而y ( 孑，c ，) 为类别属性函数，即如果z 属于类c j ，那么函数 值为1 ，否则为0 。6 j 为一个给定的