（计算机应用技术专业论文）超文本的集成分类算法研究.pdf

工程硕士学位论文 摘要 随着i n t e r n e t 技术的发展，万维网上的文档数目成指数级增长，在如此浩 瀚的信息库中，用户非常难找寻到自己所需要的信息。因此如何自动且高效地处 理这些海量文档信息成为目前重要的研究课题。文本分类是将从网上抽取到的文 档信息自动有效地分成一定的类别，以便于信息的检索。基于此，本文主要研究 文本信息分类和超文本信息分类的相关算法。 首先，本文介绍了文本分类的发展概况和相关技术，研究了常用的分类算法， 并分析相关算法的性能，为文本分类和超文本分类算法的研究提供理论基础。 其次，对于文本分类，本文研究与分析了贝叶斯分类算法，贝叶斯分类算法 是基于概率统计原理的一种分类方法，但是朴素贝叶斯分类器主要存在的问题是 需要属性之间条件独立的假设，由于文本单词之间相互存在很多的关联，同时也 存在有很大的“噪声，很难满足其属性之间条件独立的假设。本文利用树增广朴 素贝叶斯网络分类器，提出了一种基于贝叶斯的集成分类算法。通过k m e a n 聚类方法，构建相互独立的条件属性子集，然后在条件属性子集建立t a n 分类器， 并将这些分类结果进行集成。在2 0 新闻组和微型新闻组上进行实验，实验结果表 明，集成分类算法在所有的类别上取得了更好的泛化性能。 再次，一研究了超文本中的多元化信息规则，并分析了不同分类算法在不同规 则中的分类性能。本文通过对抽取到的数据集文档中的标题，超连接和标记等超 文本信息，以及文档内容本身分别建立分类模型，然后根据神经网络集成各个分 类模型得判别结果。提出一种基于元信息的超文本集成分类算法，该算法更好的 综合利用了超文本的多元结构化信息。实验结果表明，相较于单独利用某种超文 本结构信息进行分类的方法，基于元信息的超文本集成分类算法具有更好的分类 性能。 关键词：文本分类；超文本分类；集成算法；元信息 h a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ei n t e r n e tt e c h n i q u e s ，t h ei n f o r m a t i o no nt h ei n t e r n e t i n c r e a s e se x p o n e n t i a l l y i t sv e r yd i f f i c u l tf o ru s o rt of i n dw h a th ew a n t e di nt h em a s s o fi n f o r m a t i o n o n ei m p o r t a n tr e s e a r c hf o c u s e so nh o wt o d e a lw i t ht h e s eg r e a t c a p a c i t i e so fo n l i n ed o c u m e n t s t e s tc l a s s i f i c a t i o n i st oc l a s s i f yt h ei n f o r m a t i o n e x t r a c t e d6 - o mt h ei n t e r n e ti n t oc a t e g o r i e s ，f o rt h ec o n v e n i e n c eo fr e t r i e v a l t h i s t h e s i sm a i n l ys t u d i e ss o m er e l a t e da l g o r i t h m so nt e x t c l a s s i f i c a t i o na n dh y p e r t e x t c l a s s i f i c a t i o n f i r s t l y t h i st h e s i si n t r o d u c e sg e n e r a ld e v e l o p m e n ta n d s o m et e c h n i q u e so f i n f b r n l a t i o nc l a s s i f i c a t i o n t h e n ，s o m ea n a l y s e sa n dr e m a r k sa r e m a d et oc o m p a r et h e p e r f o r m a n c eo fs o m et y p 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 e r e o f , b a s i ct h e o r ys u p p o r t o ft e x tc l a s s i f c ；i c a t i o na n dh y p e r t e x tc l a s s i f i c a t i o ni sp r o v i d e d s e c o n d l y , i nt h er e s e a r c ho f t e x tc l a s s i f i c a t i o n ，t h i st h e s i ss t u d ya n da n a l y s et h e b a y e sc l a s s i f i c a t i o nw h i c hi sb a s e do np r o b a b i l i t yp r i n c i p l e b u tt h ec l a s s i f i c a t i o n i s b u i ro nt h eh y p o t h e s i so fa t t r i b u t ei n d e p e n d e n c y h o w e v e r ，t h e r ee x s i s t s s om u c h r e l a t i o n sb e t w e e nt e x ta t t r i b u t e sa n di nt e x ti n f o r m a t i o nt h e r ei sm u c h “n o i s e ，t h e a s u m p t i o ni s n tm e e t u s i n g t r e ea u g m e n t e dn a i v e b a y e s ( t a n ) t h i st h e s i sp r o p o s e d a ne n s e n l b l ec l a s s i f i c a t i o na l g o r i t h mw i t hb a y e s ( e c b ) v i ak - m e a nc l u s t e r i n g ，t h e i n d e p e n d e n ta t t r i b u t es u b s e t sa r ed i s t i l l e d ，a n dt a n c l a s s i f i e r so nt h e s es u b s e t sa r e c o n s t r u c t e da n dt h e s ec l a s s i f i t c a t i o na r ee n s e m b l e d t h ee x p e r i m e n ti sc a r r i e do n2 0 n e w s g r o u pa n dm i n i n e w s g r o u p ，a n dt h ee x p e r i m e n t a l r e s u l t ss h o wt h a tt h ee c b g a i n e dm o r er o b u s tp e r f o r m a n c e t h i r d l y , n nt h e r e s e a r c ho fh y p e r t e x tc l a s s i f i c a t i o n ，t h i s t h e s i ss t u d yt h e h y p e r t e x ti n f o r m a t i o nr u l e sa n da n a l y s i st h e c l a s s i f i c a t i o np e r f o r m a n c ew i t ht h e s e r u l e s v i as u b s t r a c t i n gt h eh y p e r t e x tr u l e ss o m ec l a s s i f i e r sa r ec o n s t r u c t e da n dn e u r a l n e t w o r ki su s e dt oe n s e m b l et h e s er e s u r s a n d a ne n s e m b l eh y p e r t e x t m e t a i n f o r m a t i o nc l a s s i f i c a t i o ni sp r o p o s e d ( e h c ) t h i sc l a s s i f i c a t i o nc a ni n t e g r a t et h e s t n l c n l r ei n f o r m a t i o ne f f e c t l y t h ee x p e r i m e n t s h o w st h a te h cg a i n e d b e t t e r p e r f o r m a n c ec o n t r a s tt oo n l yu s i n gs i n g l er u l e k e yw o r d s ：t e x tc l a s s i f i c a t i o n ；h y p e r t e x t c l a s s i f i c a t i o n ；e n s e m b l ea l g o r i t h m ； m e t a i n f om a t i o n i i i 超文本的集成分类算法研究 插图索引 图2 1 文本分类器模型8 图2 2 文档词频向量9 图2 3 一个典型的决策树结构1 0 图2 4 最佳超平面1 2 图4 1 朴素贝叶斯分类模型结构图2 4 图4 2t a n 分类模型结构图2 5 图4 3e c b 分类模型结构图2 6 图4 4 几种分类算法在2 0 新闻组分类精度比较2 8 图4 5n e w s g r o u p sd a t a s e t 中所有类别上的s n 和s p ( d = 6 0 ) 2 9 图4 6n e w s g r o u p sd a t a s e t 中所有类别上的s n 和s p ( d = 1 2 0 ) 3 0 图4 7 几种分类算法在m i n i n e w s g r o u p s 实验的分类精度比较3 1 图4 8m i n i n e w s g r o u p s 中所有类别上的s n 和s p ( d = 2 0 ) 3 2 图4 9m i n i n e w s g r o u p s 中所有类别上的s n 和s p ( d = 4 0 ) 3 3 图5 1 超文本分类模型3 7 图5 2 超文本分类的集成分类模型3 8 图5 3c o u r s e 数据集上分类的精度比较4 0 图5 4f a c u l t y 数据集上分类的精度比较4 l 图5 5h o o v e r s 5 数据集上分类的精度比较4 l v 1 t 工程硕士学位论文 附表索引 表4 1 混乱矩阵2 8 表5 1 分别用不同超文本信息分类精度比较3 9 v m 工程硕士学位论文 第1 章绪论 1 1 论文选题目的与研究意义 随着i n t e r n e t 的迅速增长，w w w 上超过2 0 亿个网页是通过超链接互连的， 这使得在w e b 上找到准确的信息日益困难。如何自动处理这些海量信息成为目前 热门和重要的研究课题n 1 。 智能信息分类是人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 和信息分类相结合的 一个交叉学科，是一种智能化的计算机信息分类系统，它模拟人类关于信息处理 的思维过程和智能活动，实现信息知识的抽取、分类和检索，并向用户提供智能 辅助。许多传统的分类算法是在研究人工智能领域中的机器学习【2 】( m a c h i n e l e a r n i n g ，m l ) 方法的基础上提出的【3 1 。通过智能方法，有效地自动分类与日俱增 的信息成为信息处理的重要研究趋势之一。 文本信息分类是将从网上抽取到的文档信息自动有效地分成一定的类别，以 便于信息的检索。研究表明【4 】，用户经常通过导航栏目录来浏览网页，这种提供 目录检索网页的方式非常方便，同时效率也很高，用户可以在较短的时间内找到 更多的相关信息。例如，y o h o o ! 就支持这种目录结构的网页检索和浏览。超文 本有别于普通的纯文本，包含有丰富的结构化信息，例如超链接、h t m l 标记、 元信息和标题等等。这些结构化信息为提高分类效率提供了非常丰富而有效的资 源，使得自动的超文本分类方法的研究变得越来越重要，同样也为自动文本分类 提出了挑战。 1 2 国内外研究现状 本文主要研究文本分类中的集成分类算法。超文本是一种特殊的文本形式， 是一种包含有的结构化信息的文本。网页，邮件等各种格式的超文本文档经过文 法分析都可以转化为纯文本，而纯文本较为容易分析和处理。超文本分类则是在 研究文本分类的基础上，结合超文本信息( 如网页、视频数据和音频数据等) 的 结构特性，来提高对超文本信息分类效率的研究。 1 2 1 文本分类 文本分类是信息分类实际应用中的一种，通过制定的计算机分类模型，并进 行训练，根据文本的内容，将其自动的分配到指定的类别中去。文本分类是人工 智能技术和信息获取技术相结合的研究领域，是进行基于内容的自动信息管理的 超文本的集成分类算法研究 核心技术【5 1 。国内外在自动文本分类领域进行了较为深入的研究【6 】。 最早的文本类别由作者自己标识。到1 9 6 4 ，m o s t e l l e r 和w a l l a c e 在鉴别文章 作者身份的工作中开创了文本分类的新阶段，他们考虑单词，句子长度，功能词 的频率和词汇的差异等特征项。到8 0 年代，自动文本分类以知识工程的方法为主， 根据专家对给定文本集合的分类经验，通过人工提取出一组逻辑规则并将其作为 计算机自动文本分类的依据【7 1 。从9 0 年代以来，基于统计的自动文本分类方法得 到了大家的重视，它在准确率和稳定性方面具有明显的优势。 从文本分类的方法来看，现有的文本分类技术主要采用三种类型的方法：基 于统计的方法，基于连接的方法和基于规则的方法。 国外当前流行的基于统计的分类方法有朴素贝叶斯( n a i v eb a y e s ，n b ) 【2 】、 k n n ( kn e a r e s tn e i g h b o r , k n n ) e 3 1 、回归模型【8 1 、支持向量机( s u p p o r tv e c t o r m a c h i n e ，s v m ) 【9 1 、最大熵模型( m a x i m u me n t r o p y ) 【1 0 】等。 基于连接的方法，即人工神经网络( a r t i f i c i a ln e u r a ln e t s ，a n n ) i h ，是设 计来模拟人脑神经网络的，并期望能像大脑一样地运作，像大脑一样地学习从而 产生智慧。这种方法具有信息分布存放、运算全局并行、处理的非线性、容错性 等特点，适用于学习一个复杂的非线性映射。但是使用它学习所形成的知识结构 是人所难以理解的，系统本身对于使用的人来说就象是一个变魔术的黑盒子，根 据输入给出输出，答案正确但不知道是怎么算出来的。 基于规则的方法是一种唯理主义方法，本质上是阿一种确定性的演绎推理方 法，优点在于根据上下文对确定性事件进行定性描述，能充分利用现有的语言学 成果。它成立的前提是有大量的知识，而这些知识是人类专家总结出来的，至少 解释这些知识的各种“事实 以及对事实的解释“规则 是专家总结归纳的。由 于必须有人的参与，所以对于知识的可理解性，可读性非常重视。同时，在不确 定性事件的描述，规则之间的相容性等方面存在一些缺陷和限制。但是，有些统 计方法无法解决的问题，利用规则却很容易解决。常用的基于规则的方法有决策 树【1 2 1 、关联规则等【13 1 。 不管是哪种分类算法，要达到一定的分类精度，建立一个较精确的模型，就 要依靠大量已标识文档进行训练。至今没有哪个单独的技术体现出超出其他技术 的明显优势。 1 2 2 超文本分类 w w w 上超过2 0 亿个网页是通过超链接互连的，这使得在w e b 上找到准确 的信息的困难日益增加【1 4 1 。超文本是具有特殊格式的文本。在文本分类的研究基 础上，研究者们发现大量超文本信息( 如超链接、h t m l 标题和元信息等) 对于 提高分类效率有极大的帮助【1 5 】。【1 引。 2 工程硕士学位论文 c h a k r a b a r t i 研究了i b m 专利文档分类之间的引用，将专利文档之间的引用看 成是超链接，将相关论题的文档分在同一目录下f 4 】。同样c h a k r a b a r t i 也对一个小 型的具有超链接的w e b 网页数据集( 从y a h o o ! 上搜索的的9 0 0 个网页) 也做了类 似的试验。运用系统预分类的类标记给文档以及相临近的文档以强制性的类标记。 c h a k r a b a r t i 的试验结果表明，相对于用纯文本文档的分类，利用了超链接的的超 文本分类减少了3 l 的错误率。此外，他们还直接将链接的文档当作本地纯文档 来分类，结果分类错误率还高出原来纯文本分类的6 。 h y o j u n go h 等人对一个韩国百科全书的数据集也做了相类似的试验【1 5 1 。他 们利用超链接系统预分类的方法，分类性能提高了1 3 ；而直接用相链接的文档 当作本地纯文档来分类，性能反而降低了2 4 。 f u r n k r a n z 用w e b k b 网页数据集的一部分作为试验数据集，通过链接上的文 字以及此链接附近的文字，来预测此链接指向的文档的类别【l6 1 。通过指向文档的 所有链接上的文字以及链接文档的标题，来表示原文档。 j o a c h i m s 采用带有不同核函数的支持向量机( s v m s ) 算法作了类似的研究，同 样用w e b k b 作为数据集，采用支持向量机的一种核函数来表示超文本的本地文 档，另一种核函数来表示超文本的超级链接【1 7 】。j o a c h i m s 分析实验结果，指出不 同的s v m 核函数能更好的利用超文本的超级链接提高分类性能。 y a n g 对近年来的工作加以分析，指出超文本分类一些未解决的问题【l 引，例如， 为什么用类似的方法分类对于不同数据集效果不同? 数据集的不同对分类性能的 影响有什么不同? 此外，用不同的分类算法对分类性能的影响有什么不同? 近年 这些工作对这些问题都没有直接的比较和分析。y a n g 总结了一些利用超文本信息 的规则，并且对于不同算法和不同的超文本数据集，就这些不同的信息规则做了直 接的比较和总结，但是并没有对这些信息规则加以综合分析和利用。 1 2 3r a i n b o w 分类系统 r a i n b o w 是卡内基梅隆大学的m c c a l l u m 等用标准c 语言开发的基于 l i n u x u n i x 的信息分类程序包【1 9 。作为一个独立的系统，r a i n b o w 系统可以处理 各种类型的文档，包括纯文本，网页，邮件等，并实现了许多算法，可以对数据 集测试多种算法。它定义了灵活的数据结构，实现了丰富的函数调用，给出了规 范的算法接口，为实现新算法提供了方便。 r a i n b o w 系统主要使用的是u s e n e t 新闻组数据库，数据库是1 9 9 4 年在u s e n e t 上下载的2 0 个类的新闻组讨论英文文章( 2 0 一n e w s g r o u p s ) 。数据库中的文档放在 2 0 个目录下，每个目录的名字就是新闻组的类别。每个类大约是1 0 0 0 篇。 2 0 n e w s g r o u p s 的另一个版本m i n i _ n e w s g r o u p s 为了减小每次实验运行的时间，从 每个类中选出1 0 0 篇文档，组成小型新闻组数据库( m i n i n e w s g r o u p s ) 。 超文本的集成分类算法研究 r a i n b o w 分类系统首先要对以分类的训练集建立模型。训练集分为n 类，每类 对应一个文件目录，目录名称就是它的类别名称，每个类的文档就放在这个目录 下。系统就对这些目录进行路径解析和文件名解析，把目录名保存为类别名，把 文档路径和文档名保存为这篇文档的名称，在系统中文档，类别，单词都是用整 数序号代表的，序号所对应的实际文档名，类别名，单词都分别保存在数据文件 中【2 0 1 。 1 3 本文的研究工作 本文研究了文本信息分类中的集成分类算法，主要探讨了文本分类和超文本 分类的工作原理及相关算法，在此基础上，研究了文本分类和超文本分类的集成 分类算法，并提出一种基于贝叶斯的集成分类算法和一种利用超文本元信息的集 成分类算法。主要工作如下： 1 对信息分类的常用算法做了比较系统的分析，比较深入地研究分析了各种 分类算法在超文本分类上的分类原理，并比较和分析各种算法在普通文本和超文 本的分类性能。 2 研究与分析了贝叶斯分类算法，贝叶斯分类算法是基于属性之间条件独立 的假设，由于文本单词之间相互存在很多的关联，同时也存在有很大的“噪声”， 很难满足其属性之间条件独立的假设。本文利用树增广朴素贝叶斯网络分类器， 提出了一种基于贝叶斯的集成分类算法。通过妒m e a n 聚类方法，构建相互独立 的条件属性子集，然后在条件属性子集建立t a n 分类器，并将这些分类结果进行 集成。 3 研究了超文本中的多元化信息规则，并分析了不同分类算法在不同规则中 的分类性能。通过对抽取到的数据集文档中的标题，超连接和标记等超文本信息， 以及文档内容本身分别建立分类模型，然后根据神经网络集成各个分类模型得判 别结果。提出一种基于元信息的超文本集成分类算法，该算法更好的综合利用了 超文本的多元结构化信息。 1 4 本文的组织结构 全文分为六个章节，组织结构如下： 第1 章：绪论。介绍了本论文的选题目的和研究意义，分析了国内外文本分 类和超文本分类的研究现状，并给出了论文的研究工作和论文的组织结构； 第2 章：文本分类概述。介绍文本分类的中文本的表达形式，文本分类的基 本步骤，并介绍和分析了常见的分类算法，最后给出了分类算法的性能评价； 第3 章：文本文档信息处理方法。介绍文本分类中的文本文档信息处理方法， 4 工程硕士学位论文 文本的预处理方法，以及文本特征选择方法； 第4 章：一种基于贝叶斯的集成分类算法。研究和分析朴素贝叶斯算法，利 用树增广朴素贝叶斯网络分类器，提出了一种基于贝叶斯的集成分类算法。在2 0 新闻组和微型新闻组上进行实验析，实验结果表明，集成分类算法在所有的类别 上取得了更好的泛化性能； 第5 章：一种利用超文本元信息的集成分类算法。研究了超文本中的多元化 信息规则，根据不同的规则分别建立分类模型，然后根据神经网络集成各个分类 模型得判别结果。提出一种基于元信息的超文本集成分类算法。实验结果表明， 基于元信息的超文本集成分类算法具有更好的分类性能，该算法更好的综合利用 了超文本的多元结构化信息；对超文本的集成分类算法研究进行总结与展望，并 给出了下一步的研究工作方向。 超文本的集成分类算法研究 2 1 文本分类简介 第2 章文本分类研究概述 文本分类是一种最常用的信息分类系统，利用文本的表达形式，通过制定的 计算机分类模型进行训练，然后根据文本的内容，将其自动的分配到指定的类别 中去。文本分类是人工智能技术和信息获取技术相结合的研究领域，是进行基于 内容的自动信息管理的核心技术【2 1 1 。文本分类算法是设计实现分类器的理论基 础，也是研究超文本分类的理论基础【2 2 】【2 3 1 。 本章首先介绍文本的表达形式，以及文本分类的基本步骤，然后介绍文本分 类中常见的分类算法，这些分类算法的理论基础，实现形式各不相同，算法的性 能各异，有各自的特性。最后，介绍了算法的性能评价体系。 2 2 超文本分类方法 超文本的结构是半结构化的，且多数页面文本内容短小，如果用平常的文本 分类器去分类，则分类效果明显不好，如何有效地利用超文本中的结构信息，是 当前超文本分类研究中急待解决的问题。目前对超文本的分类，主要涉及页面的 纯文本分类、超文本结构信息分类、页面中的超链接信息分类、以及综合分类等。 2 2 1 纯文本分类 在基于页面文本分类的方法中，没有用超文本页面中的任何结构信息，只是 将此页面当作一个普通文本来看待，用一般的文本分类器来进行分类，这主要是 早期的超文本分类器的分类方法。 2 2 2 超文本结构信息分类 超文本页面中含有大量有用的结构信息，这些信息可能包括该页面标题、重 要的子标题等重要的内容。如果将这些结构信息用于分类页面，一方面可以有效 地提高分类精度，另一方面可以减少计算的复杂度。因此，我们将 和 ， 和 ， 和 ， 和 等文档结构信息提取出来，再用相应 的分类器进行分类，这就用较少的文本信息，达到了更好的分类效果。 2 2 3 结合超链接的挖掘 超文本中含有很多的超链接，抽取超链接中的内容，并通过对其内容的分析 可能对分类结果具有一定的指导作用。如可以通过超链接得到邻居w e b 页面，为 6 工程硕士学位论文 分类提供有效的辅助参考；也可以通过超链接得到w e b 页面的权重，为页面分类 提供参考。另外，通过超链接可以得到多个网页间的关系和不同网页的权重，比 如被链接多的可能就是重要网页，而被链接少的，可能就是次要网页。 2 2 4 综合分类 以上多种类器，是对不同的信息内容进行分类的。那么，可否将其结合，从 而更有效地提高分类效果? 基于此设想，我们探索了将多种分类结合起来的集成分 类方法。目前一般采用的二者选最大值法等，分类效果并不理想。目前有关超文 本分类研究的内容很多，各个分类器分类的内容不同，分类结果也各有优劣，如 何有效协调这些分类器对超文本的分类，值得深入研究。 2 3 文本文档的表达形式 2 3 1 词袋 目前主要的文本分类系统都采用词袋( b a g s o f - w o r d s ) 表示法，即记录每个 单词在文档中出现的次数，或仅记录出现与否。有研究表明加入语义信息或语言 信息对分类器的精度都提高不大【2 4 1 。因此，分类算法一般基于“词袋”模型，即文 档被看成是由相互无关的单词构成的集合，不考虑单词之间的上下文关系，单词 、- 出现的顺序，位置以及文章的长度等。统计出每个单词在每篇文档中出现的频率，j 。女 根据所有单词在所有文档中出现的频率建立单词对于文档的词频统计矩阵。 ： 2 3 2 词频矩阵 词频统计矩阵是文本分类算法建立分类器模型的数据基础，训练集通过文法 分析统计出词频矩阵，一篇文档可以看作成矩阵中的某一行，该行中的一个元素 就是某个单词在这篇训练文档中出现的频率。 2 3 3 空间向量模型 向量空间模型( v s m ) 的基本思想是用词条法来表示文本，将每个词条作为特 征空间坐标系的一维，将文本看作特征空间的一个向量，用两个向量之间的夹角 来衡量两个文本之间的相似度。 空间向量模型目前应用较多并且证实效果较好的一种文本分类模型。对于任 意一个文本d f 表示为关键词条空间中的一个以维矢量： d i = ( t i l ，w i l ；t i 2 ，w i 2 t i n ，w i n ) ( 2 1 ) 其中：t i k 为i 类文本空间向量中的第k 个关键词分量； w i k 为对应的权值。 当有二个文本4 和彳，则二个文档之间的相关程序常常用它们之间的相似度 7 超文本的集成分类算法研究 j 加( 4 ，4 ) 来衡量： m s i m ( 4 ，4 ) = 啄 ( 2 2 ) k = l 这样在这个模型中，文档之间的相互比较就转变成为特征向量之间的比较了。 2 4 文本分类的基本步骤 文本分类系统的基本步骤如图2 1 所示。 圄 图2 1 文本分类器模型 第一步，对文档进行预处理。扫描文本文档数据集中所有训练文档，根据文 法分析方法分析出不同的单词，建立单词库。文法分析包括：1 ) 单词分割：按空 格分出每个单词；2 ) 禁用词：根据禁用词表去掉禁用词，如t h e ，t h a t 等；3 ) 词 干提取：提取主要词干，如将p l a y e d ，p l a y i n g 提取词干p l a y ；在预处理过程中， 如果是第一次遇到的新词，就存入单词列表，也称词库，否则这个单词的统计次 数加1 ，还包括其他工作，比如：保存文档的文件名，类别等工作。 第二步，建立词频矩阵。预处理之后，将文章变为一个词集，单词也称为特 征项或属性。把文档看成是一个词向量( w o r dv e c t o r ) ，它的维数是所有不同的 单词个数，词集中可以有数万个不同的单词。对于特定的文章，它包含的单词数 一般从几百到几千，一篇文档对应一个词向量( 图2 2 ) ，而一个词也在不同的文 档中出现，所有出现这个单词的文档构成了文档向量，所以整个文档与词集构成 一个矩阵，矩阵中的元素就是单词在文档中出现的频率。 嚣筘嚣怒淼囊一怒凇慧2 5 】决策树 。 超文本的集成分类算法研究 感。 冈 小、 匆西 图2 3 一个典型的决策树结构 2 5 2k n n 算法 邻近法( n e a r e s tn e i g h b o r ，n n ) 是在模式识别中广泛使用的分类方法，是模 式识别非参数法中最重要的方法之一【2 7 】 【2 8 1 。k 近邻法( kn e a r e s tn e i g h b o r ，k n n ) 是最近邻法的一个推广。当k 取1 时就是最邻近法。k 近邻分类算法是一种懒散的 分类算法。假设每个文本代表空间中的一个点，给定一个未知样本，k n n 搜索模 式空间，找出最接近未知样本的k 个训练样本，这k 个样本就是未知样本的k 个“近 邻 。 k n n 法【2 9 】最初是由c o v e r 和h a r t 于19 6 8 年提出的。算法的基本思想是：根 据向量空间模型，文本内容被形式化为特征空间中的加权特一征伺量 d = d ( 五，彤；互，；巧，) 。对于一个需进行测试的文本，通过计算它与训练样 本集中每个文本的相似度，找出k 个最相似的文本，根据加权距离来判断测试文 本所属的类别。在衡量测试文本和训练样本集的相似度时，一般是采用欧几里德 距离，也就是说其“临近性用欧氏距离来定义。 即两个点x = ( 五，屯，毛) 和y 2 瓴，y 2 ，y 。) 的欧氏距离为： 厅一 d ( x ，d = 、( 薯一乃) 2 ( 2 3 ) yi = l 除此之外还可以利用两个向量夹角的余弦来表示测试文本与训练样本集的相 似度的方法，其公式如下【2 6 】： s i m ( d i 。d 1 ) 2 ( 2 4 ) 在式2 4 中，面为测试文本的特征向量，嘭为训练文本的特征向量；m 为特 征向量维数；吸为向量的第k 维。k 的大小具体根据应用的环境选择，一般的在 1 0 z b 露纠 工程硕士学位论文 几十到几百之间。 k n n 方法基于类比学习，是一种非参数的分类技术，没有训练过程，对于未 知和非正态分布可以取得较高的分类准确率，具有鲁棒性、概念清晰等优点。但同 时k n n 也是懒散的学 - 3 方法，它存放所有的训练样本，直到新的样本需要判别时， 都要计算待识别样本与全部训练样本之间的距离进行比较。当测试文本数量较大时 其时问和空间开销均相当的大；此外计算相似度时，特征向量的维数比较高，没有 考虑特征词间的关系。 2 5 3n a i v eb a y e s 算法 贝叶斯算法( n a i v eb a y c s ，n b ) 【2 6 】是一种简单而有效的传统分类算法， 它有一个假设：在给定的文档类情况下，文档的特征项( 即单词项) 是相互独 立的。用符号c ，c = c l ，c | c f ) 代表第_ ，个类别，n b 算法先计算先验概率 只wic j ) ，即在给定文档类c ，的条件下，已标记类别中文档词汇表v 中每个独立 单词心的条件概率；以及p ( c j ) ，即每一类的先验概率： 毗，= 斋i vl弋j,燮ivl!d篇i 亿5 ， 以训u 2 衰巍惹蒜 q 5 其中( w ，4 ) 表示单词w 在文档或中出现的次数：p ( c ji 珥) o ，l 当磷仨c ， 或而c ，等于0 或1 。d = 盔，i ) 为已标记的文档集合，l d i 表示其中文档 的数导。i y l 表示文档总词汇表v = 中的词汇数量。每一类的先验 概率p ( c ，) 计算公式为： 妙错 ( 2 6 ) 其中l c i 表示类别总数。在统计过单词、词频和文档的相关信息后，计算测 试文档对于每一类的后验概率p ( c j l4 ) ，由p ( 4 ) 为常数和基于文档中单词出现的 概率相对独立的假设可知： p ( c j1 4 ) = 掣o c p ( c j ) p ( 4 i c j ) = p ( 巳) 堪p ( w 砒l c j ) ( 2 7 ) 其中，岷，七表示第i 篇文档d i 的第k 个单词。在计算出每一类对测试文档 d i 的后验概率后，选择后验概率最大的类为该测试文档的类别。 贝叶斯概率分类器在机器学习领域中被广泛的研究【3 0 1 。贝叶斯分类器由 m a r o n 提出，将文章看作独立的单词集合，通过训练集，由贝叶斯理论得到每个 单词在不同类的概率大小，构造出贝叶斯模型，模型由参数汐决定。贝叶斯算法 假设文档由混合模型产生，每个类别对应混合模型的一个分量。模型0 由以下参 数组成： 超文本的集成分类算法研究 口= 尸( w tl 勺；口) ，t l ，。，i 矿i ) ，勺c ；p ( c jl p ) ，勺c ( 2 8 ) 算法假设模型分量与类别一一对应，文档由模型产生，先选择一个类别，然 后按这个类别的模型分量产生一篇文档。那么一篇文档属于这个模型的可能性为： 且 尸( 喀1 秒) = p ( c 1ig ) p ( 4 lc j ；o )( 2 9 ) ，- l 2 5 4 支持向量机 支持矢量机( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 3 1 】【3 2 】建立在计算学习理论 的结构风险最小化的原则( s t r u c t u r a lr i s km i n i m i z a t i o n ) 之上，其主要思 想是针对两类分类问题，在高维空间中寻找一个超平面作为两类的分割，以保 证最小的分类错误率。s v m 算法不仅具有扎实的理论基础，而且在应用到文本 分类时取得了很好的结果。 超平面是对两类分类的划分，如果一个训练集中的矢量能被一个超平面无 错误地线性分割，且距该超平面最近的矢量之间的距离最大( 又称为间隔 ( m a r g i n ) 最大) ，则称该超平面为最佳超平面。其中距离超平面最近的点称为 支持向量( s u p p o r tv e c t o r ) 。支持向量机从训练样本集中选择一组特征子集，使 得对子集的划分等价于对整个训练样本集的划分，这组特征子集被称为支持向 量( s v ) ( 图2 4 ) 。 图2 4 最佳超平面 图中的实心点和空心点分别表示两类的训练样本，对于线性可分的情况， 即通过一条直线日可以把两个类别无错误的分开，以，制爿2 分别为过各类样本中 离分类线最近的点且平行于分类线日的直线，1 - 1 1 利1 - 1 2 之间的距离叫做两类的分 类空隙或分类间隔( m a r g i n ) 。最优分类线定义为：该分类线不但能将两类样本分 开，而且要使两类的分类间隔最大。直线t - l t 利t - 1 2 上的训练样本叫做支持向量， 因为它们支撑了最佳分类面。在图2 4 中的分类线日是最佳分类线。当推广到 高维空间时，最优分类线就成为最佳超平面。 支持向量机是一种能在训练样本很小的情况下达到很好分类推广能力的算 1 2 工程硕士学位论文 法，在非线性及高维模式识别问题中有比较明显的优势，特别是能做到与数据 的维数无关，这一特点对算法可能导致的“维数灾难 问题带来了新的解决方 法。 t h o s t e nj o a c h i m s 将s v m 用于文本分类并比较了其它的分类算法。他的结 果显示s v m 要优于其它方法。超平面是对两类分类的划分，对于有大于两类的 多类文本分类，就对每个类构造一个超平面，将这一个类与其余的类分开。有 一多少个类就构造多少个超平面。测试时就看哪个超平面最适合测试样本。 2 5 5t f i d f 算法 在t f i d f 文本分类算法中，采用的是向量空间模型，每个单词看成是一个 特征项气，每篇文档看成由单词组成的向量乏= ( w 。，w 2 ，) ，单词t k ( 1 k n ，n 为所有不同单词的总数) 被赋予一个数值，表示气在文献中的重要程度， 称为k 的权重，即有： = 娠幸坝( 2 1 0 ) 坝= l o g ( n 识+ 1 ) ( 2 1 1 ) 其中，词频吮指某个特征项气在文档喀中出现的次数，文档频率妩指整个 文档集合中，包含特征项气的文档个数，坝是特征项反比文档频率，为 所有文档总数。t f i d f 算法将属于同一类的所有文档向量加起来，得到每一个类 勺( 勺c ，c 表示所有类另懒集合) 的特征向量弓= ( m ，w j ：，) 。利用t f t d f 一 模型测试一篇文档所属的类别时，通过计算这篇文档的向量云和每个类特征向 量苓，的相似度距离s i m ( 乏，孑，) ，相似度距离最大的类向量石，所属的第_ ，类就是测 试文档的类别。计算公式如下【2 8 】： 孑，= 乏：面 ( 2 1 2 ) c l a s s ( d , ) = a r g m a x s i m ( d i ，弓) ( 2 1 3 ) c ，c ， 砌瓯轳赫2 面z 畿n w 亿 t f i d f 算法是有监督学习的文本分类算法， - e 的训练集是已标识的文档， 它对训练集规模很敏感，随着训练集规模的增大，分类精度显著提高。而聚类 算法有着特殊的优势，可以在未标识的数据集上学习，体现了机器学习的自动， 超文本的集成分类算法研究 快速的特点，缺点是分类精度较低，初始化过程需要定义大量经验参数。能否 将监督学习和非监督学习的优点结合起来是现在研究的热门方向。 2 5 6b o o s t i n g 方法 严格来说，b o o s t i n g 方法并不是一种特定的学习方法，而是一种在已有的 学习方法基础上进行“投票”的技术。b o o s t i n g 算法是一种特殊的组合分类器方 一法，其组合分类器中有n 个分类器( 称为弱假设) 是由相同的学习算法( 称为弱学 习器) 形成的，并且n 个弱学习器都采用相同的文本表示方法【3 3 1 。最简单的弱假 设的定义为： 翻假设删删制功啦擀个断劫 b o o s t i n g 方法通过对这一组分类器进行加权求和得到最终的分类器( 强规 则) ，由于b o o s t i n g 的弱规则常采用基于规则的方法，因此一般将其归属于基于 规则的文本分类方法之中。b o o s t i n g 方法有很多种形式，常见的有：a d a b o o s t 、 a d a b o o s t m l 、a d a b o o s t m h 等，b o o s t i n g 方