（应用数学专业论文）文本挖掘方法探讨及应用.pdf

摘要 随着i n t e r n e t 的大规模普及和企业信息化程度的提高，因此如何自动处理 这些海量联机文本成为目前重要的研究课题。文本挖掘( t e x tm i n i n g ) 技术就可 以快速、有效的从海量的数据中提取出对用户有用的信息，而文本分类是文本 挖掘中最重要和应用最广的一项技术。 本文首先介绍了文本挖掘的一些基本概念和文本挖掘的相关知识背景，各 种理论和方法。对文本挖掘所涉及的关键技术，包括文本表示模型、特征提取、 评估方法和常用方法进行了详细的理论阐述和算法描述。并着重对特征提取和 朴素贝叶斯分类算法进行了详细的介绍。 然后本文提出并实现了一种改进互信息的特征提取和支持朴素贝叶斯的文 本分类系统，介绍了系统实现中主要过程和一些主要的技术问题。 最后，对改进互信息的特征提取和朴素贝叶斯的文本分类系统进行试验， 结果表明本算法和系统具有较高的分类准确率。 关键词：文本挖掘；文本分类；特征提取；改进互信息；朴素贝叶斯 a b s t r a c t w i t hag r e a ts c a l ep o p u l a r i z a t i o no fi n t e r n e ta n di m p r o v e m e n to ft h e i n f o r m a t i o no fc o r p o r a t i o n t h e r e f o r eh o wt od e a l 溺t ht h e s eb i gc a p a c i t i e so fo n l i n e d o c u m e n t sh a sb e e nt h ei m p o r t a n tr e s e a r c hs u b j e c t t e c h n i q u eo ft e x tm i n i n gc a r l q u i c k l ya n de f f e c t i v e l y a b s t r a c tt h eu s e f u li n f o r m a t i o nf r o mt h em a n yd a t a t e x t c l a s s i f i c a t i o ni so n eo f t h em o s ti m p o r t a n ta n dp o p u l a rt e c h n i q u e si nt e x tm i n i n g s o m eb a s i cc o n c e p t s 、r e l a t i v eu n d e r g r o u n do f t e x tm i n i n g 、a l lt h et h e o r i e sa n d e a c hk i n do fm e t h o d sa r ei n t r o d u c e df i r s t l yi nt h i sp a p e r t h ek e yt e c h n i q u e so ft e x t m i n i n gr e l a t e di n c l u d i n gt e x td e s c r i b i n gm o d e l 、f e a t u r ea b s t r a c t i n g 、a p p r a i s a l m e t h o da n dc l a s s i f i c a t i o nm e t h o da r et a k e ni n t e n s i v et h e o r ya n da r i t h m e t i c d e s c r i p t i o n ，a n dm a d ead e t a i li n t r o d u c t i o no ff e a t u r ea b s t r a c t i n ga n dn a f v eb 孵e s c l a s s i f i c a t i o n i na d d i t i o n ，t h i sp a p e ro f f e ra n dt a k ea f f e c tak i n d t e x tc l a s s i f i c a t i o ns y s t e m b a s e do ni m p r o v e m e n tm u t u a li n f o r m a t i o na n ds u p p o r t i n gn a y v eb a y e s ，a n dt a k e s a f f e c tt h em a i np r o c e s sa n dt e c h n i q u ep r o b l e mi nt h es y s t e mp r o c e s s i n e n d ，d o i n g s o m ee x p e r i m e n t so ft e x tc l a s s i f i c a t i o ns y s t e mb a s e do n i m p r o v e m e n tm u t u a li n f o r m a t i o na n ds u p p o r t i n gn a f v eb a y e s ，e x p e r i m e n t r e s u l t s p r o v et h ea r i t h m a t i c sa n ds y s t e mb e i n gh i g hc l a s s i f i c a t i o nr a t i o k e y w o r d s ：t e x tm i n i n g ；t e x tc l a s s i f i c a t i o n ；f e a t u r ea b s t r a c t i n g ；i m p r o v e dm u t u a l i n f o r m a t i o n ；n a f v eb a y e s i i 第l 章前言 1 。1 选题依据 第1 章前言 近年来，随着i n t e r n e t 的大规模普及和企业信息化程度的提高，各种资源 呈几何爆炸式增长，然而，大部分信息都是存储在文本数据库中，对于这种半 结构或无结构化的数据，用传统方法获取特定内容信息的手段却较弱，导致信 息搜寻困难和信息利用率低下。文本表达了大量的、丰富的信息，同时包含了 许多未被所有者发现的潜在知识。面对浩瀚的文本资源，传统的文档和文本处 理工具已经不能满足用户的需求。于是在人工智能研究领域结合结构化数据库 中的数据挖掘技术，提出了一种有效的、可以充分利用这些文本数据的新的信 息处理技术文本挖掘“3 ( t e x tm i n i n g ) 。 在大多数文本数据库所存放数据都是半结构化的数据，即它们即不是完全 结构化也不是完全无结构的。如：一个文档中包含一些结构化的字段，诸如标 题、作者、出版时间、长度和类别等，但也包含大量无结构的文本内容，诸如 摘要和内容。近年来在数据库研究领域，对半结构化数据集如何进行建模和操 作己有了许多研究成果。此外信息检索技术，如文本索引方法，也已应用到了 对非结构化文档的处理上。 随着文本数据的快速增加，传统的信息检索技术己无法满足实际的需要。 在不知道文档中具体的内容时，要想给出精确精致的查询是比较困难的。在处 理大量文档时，需要对文档进行比较、分类和发现多文档的模式与趋势，可以 将互联网看作是一个巨大的动态文档数据库，随着互联网的飞速发展，文本挖 掘将起着越来越重要的角色。本章参考了文献 3 卜 7 。 1 2 国内外研究现状 国外对于文本挖掘的研究开展较早，到目前为止，国外的文本挖掘研究已 经从最初的可行性基础研究到试验性研究进入到了实用化阶段，并在邮件分类、 电子会议、信息过滤、w e b 文本挖掘方面取得了较为广泛的应用。并且出现了 很多融合文本挖掘思想和技术的应用，s e m i o 公司研发的s e m i o m a p 工具可以提 供自动的文本处理，i b m 公司出品的智能化文本挖掘器( i n t e l l i g e n t m i n e rf o r t e x t ) 适合大型软件公司的开发人员使用。 国内进行文本挖掘的研究较晚，但对中文文本挖掘取得了最初成果，如中 成都理工大学硕士学位论文 科院计算机语言信息工程研究中心研究的内容是汉语分词、自然语言接口、句 法分析、语义分析、自动分词等等，清华大学电子系的丁晓青、吴佑寿研究的 是手写汉字识别( 动态匹配) 、汉字识别多分类器集成( 综合识别法) 等”1 。 目前，对文本挖掘的理论方法和技术实现国内外都在进行深入的研究和探 讨，研究表明文本挖掘技术可以应用于： 基于内容检索，传统的基于几个关键词的检索很难描述具有丰富内涵的 信息，而文本挖掘采用基于内容的检索技术可以从文本信息中抽取些更为详 细的、经过特殊加工的特征信息，大大提高检索的全面性和准确性。 信息智能代理：主要为分布式信息网络环境下的信息的查询服务。用户 可以不知道所要检索的信息的具体形式、存储于何地、何种介质中，只要用户 提出查找要求，文本挖掘技术会自动把各种信息源中各种形式的相关信息都检 索出来。 信息过滤：根据用户需要，通过对多个不同信息集之间的比较，进行信 息过滤，产生适量的、合乎用户需求的信息。 文本信息文摘：用包括题目和具有代表性的关键词进行抽取、计算和表 达，自动选择重要的句子，产生文本信息摘要。 1 3 本文的主要研究工作 文本挖掘包含的内容和涉及的面很多，应用的范围较广泛，因此本文不可 能讨论所有的内容。本文的主要研究目标是通过对文本挖掘的一些关键技术、 方法的研究和探讨，提出更有效的模型与算法，具体包括特征选择算法的改进 和文本分类的应用。 针对以上研究目标，本文的具体研究内容如下： 文本挖掘所涉及的关键技术，包括文本表示模型、特征提取、评估方法 和常用的方法进行了详细的理论阐述和算法描述。 讨论了基于互信息的特征选取算法在文本分类中的性能睡题，分析了币用 这种特征选取算法存在分类精度不高的原因，认为互信息为负值的特征在分类中 具有很重要的作用。在此基础上提出了一种基于互信息特征选取的改进算法，该 算法加强了互信息为负值的特征在分类中的作用。 设计弗实现了一个朴素贝叶斯方法的文本分类系统，介绍了系统实现中 的一些主要技术问题。文本表示采用向量空间模型，文本的评价方法采用了查 准率和查全率，文本的特征提取采用改进互信息方法。 2 第l 章前言 1 4 本文的组织结构 本文共分为六章，第一章为前言，第六章为结束语，第二章到第五章为本 文研究内容，其中： 第二章为文本挖掘基本方法，本章主要介绍了文本挖掘的定义、过程、应 用领域，主要方法和评估方法。 第三章为改进互信息特征提取，本章详细介绍了特征提取的概念、作用和 一些常用的方法，最后提出了一种改进互信息特征提取方法。 第四章为朴素贝叶斯分类算法，本章讲述了贝叶斯方法的发展、理论以及 朴素贝叶斯算法的原理和过程，介绍了一种改进的朴素贝叶斯分类器的特点及 原理。 第五章为朴素贝叶斯文本分类的应用，本章提出并实现了一种改进互信息 的特征提取和支持朴素贝叶斯的文本分类系统，介绍了系统实现中主要过程和 一些主要的技术问题，并对文本分类的应用进行了测试。 第2 章文本挖掘基本方法 第2 章文本挖掘基本方法 文本挖掘是指以计算语言学、统计数理分析为理论基础，结合机器学习和 信息检索技术从大量文本数据中抽取事先未知的、可理解的、最终可用的知识 的过程，同时运用这些知识更好地组织信息以便将来参考。文本挖掘涉及多个 学科领域：数据库、信息检索、信息提取、机器学习、自然语言处理、计算语 言学、统计数据分析、线性几何、概率理论，甚至还有图论。 直观的说，当数据挖掘的对象完全由文本这种数据类型组成时，这个过程 就称为文本挖掘。 文本挖掘也称为文本数据挖掘或文本知识发现，文本挖掘的主要目的是从 非结构化文本文档中提取有趣的、重要的模式和知识。可以看成是基于数据库 的数据挖掘或知识发现的扩展。 文本挖掘是从数据挖掘发展而来，因此其定义与我们熟知的数据挖掘定义 相类似。但与传统的数据挖掘相比，文本挖掘有其独特之处，主要表现在：文 档本身是半结构化或非结构化的，无确定形式并且缺乏机器可理解的语义，而 数据挖掘的对象以数据库中的结构化数据为主，并利用关系表等存储结构来发 现知识。因此，有些数据挖掘技术并不适用于文本挖掘，即使可用，也需要建 立在对文本集预处理的基础之上。 2 1 文本挖掘过程咖 有些人把文本挖掘视为另一常用术语文本知识发现( k d t ) 的同义词，而 另一些人只是把文本挖掘视为文本知识发现过程的一个基本步骤。文本挖掘的 一般过程主要由以下步骤组成，如图2 一l ： 图2 1 文本挖掘一般过程 特征集的建立 与数据库中的结构化数据相比，文本具有有限的结构，或者根本就没有结 构，即使具有一些结构，也还是着重于格式，而非文本内容，不同类型文本的结 4 成都理工大学硕士学位论文 构也不一致。此外，文本的内容是人类所使用的自然语言，现在计算机还很难处 理其语义。文本信息源的这些特殊形式使得现有的数据挖掘技术无法直接应用于 其上。我们需要对文本进行预处理，抽取代表其特征的元数据这些特征可以用结 构化的形式保存，作为文本的中间表示形式。 我们认为文本特征可分为描述性特征和语义性特征。描述性特征包括文本的 名称、日期、大小、类型等，语义性特征包括文本的作者、机构、标题、内容等。 描述性特征容易获得，而语义性特征较难得到。 特征集的缩减 当我们将文本转化为一种类似于关系数据库中记录的较规整且能反映文本 内容特征的表示( 文本特征向量) 后，我们会发现一个不合人意的地方：文本特征 向量具有惊人的维数。使得特征集的缩减成为文本数据挖掘中必不可少的一步。 特征集的缩减包括横向选择和纵向投影两种方式。横向选择是指剔除噪声文档以 改进挖掘精度，或者在文档数量过多时仅选取一部分样本以提高挖掘效率。纵向 投影是指按照挖掘目标选取有用的特征，通过特征集的缩减，就可以得到代表文 档集合地有效的、精简的特征子集，在此基础上可以开展各种文本挖掘工作。 学习和知识模式的提取 完成文本特征向量的维数的缩减后，便可利用机器学习的各种方法来提取面 向特定应用目的的知识模式( 进行分类或聚类操作等等) 。 模式质量评价 对所获取的知识模型进行质量评价，若评价结果满足一定的要求，则保存该 知识模式，否则返回以前的某个环节进行分析改进后进行新一轮的挖掘工作( 对 分类或聚类的结果进行评价) 。 2 2 文本挖掘应用领域凹1 文本挖掘是抽取有效、新颖、有用、可理解的、散布在文本文件中的有价 值知识，并利用这些知识更好地组织信息的过程。文本挖掘是信息挖掘的一个 研究分支，用于基于文本信息的知识发现。文本挖掘是利用智能算法，如神经 网络、基于案例的推理、可能性推理等，并结合文字处理技术，分析大量的非 结构化文本源( 如文档、电子表格、客户电子邮件、问题查询、网页等) ，抽取 或标记关键字概念，文字间的关系，并按照内容对文档进行分类，获取有用的 知识和信息。 进行文本挖掘的主要目的有：文本分类、文本聚类、文本总结、信息提取 等。其中文本分类问题是最重要的，也是应用较多的文本挖掘技术。 第2 章文本挖掘基本方法 文本分类是指按照预先定义的主题类别，为文档集合中的每篇文档确定 个类别。这样用户不仅可方便地阅读文档，而且可以通过限制搜索范围来使文 档查找更容易。目前，y a h o o 已实现用文本自动分类技术对w e b 文档进行自动分 类，这大大提高了效率。自动文本分类中应用较早的机器学习方法是纯粹贝叶 斯( n a i v eb a y e s ，简称n b ) 。大量其它机器学习的技术也被用于文本分类，如支 持向量机( s u p p o r tv e c t o rm a c h i n e ，s w ) ，最大熵算法( m a x i m u me n t r o p y ) ， 神经网络( n e u r a ln e t s ) 和规则学习算法，k 近邻算法( kn e a r e s tn e i g h b o r ， k n n ) 等。至今没有哪个单独的技术体现出超出其他技术的明显优势，但最近的 数据表明k 近邻法和支持向量机在充足的训练样本的情况下性能较好。 文档聚类同文档分类相比，最主要的区别就是分类学习的样本或数据对象 有类别标记，而聚类的样本则没有标记，需要由聚类学习算法来自动确定。因 此，在机器学习中聚类又称作无监督归纳( u n s u p e r v i s e di n d u c t i o n ) 。 聚类是指把一组对象集合按照相似性归成若干类别。它的目的是使得属于 同一类别的对象之间的相似度最大，而不同类别的对象间的相似度最小。一般 情况下，对某一问题没有唯一的或是最好的解决方案。在文本挖掘中利用聚类 可以进行诸如来自客户e m a i l 邮件的主题分析。聚类的效果使文本集分割成为若 干子集，子集内部具有某种特征的相关性。聚类可以按照文档内容聚类，也可 以按照文档属性聚类( 如：日期、长度、价钱等) 。文本挖掘中的聚类能被用于： 提供大规模文档集内容的总括；识别隐藏的文档间的相似度；减轻浏览相关、 相似信息的过程。聚类方法通常有如下四种：分割聚类、层次聚类、自组织映 射和平衡迭代消减聚类法( b i r c h ) 。 文档总结也是文本挖掘的一个重要内容。文档总结就是指从文档中抽取关 键信息，用简洁的形式对文档的主要内容进行摘要或解释。这样用户不需阅读 全文就可了解文档或文档集合的总体内容，一般摘要的内容能减到原文内容的 2 0 。搜索引擎向用户返回查询结果时，通常需要给出文档摘要，这就是文档总 结的一个实例。目前绝大多数搜索引擎采用的方法是简单截取文档前几行，显 然有很大缺陷。 有多种摘要算法，但关键技术都采用词性标注，进行语义分析；用统计方 法提取高词频( 去除停用词之后) ，以确定摘要。有些算法对开始旬和结束句中 出现的短语给予较高的权重。还有一些方法通过寻找关键短语，确定重要的句 子，例如结论旬等。 文本挖掘中的信息提取，不是简单地进行文本数据的顺序分析或是从文本 中简单提取一些高频词，而是通过挖掘从文本中获得更多隐含信息，如短语间 的关系、规则、典型的框架等。这些信息将体现主题、意图、期望及要求等。 6 成都理_ 大学硕士学位论文 信息提取有很好的商业价值，对用户需求、市场预测、趋向分析等都很有帮助。 目前，信息提取主要征对如下3 个方面：名字提取、缩写识别、关系提取。主要 的技术是基于语言学的激发启发式规则，利用自然语言处理技术提取文本中的 信息。通过建立各种词表，如同义词表、蕴含词表等解决一词多义及一义多词 的语言复杂性。把文档中出现的单词分成不同的类并且度量它们对文档内容的 重要性。充分利用文本中有限的结构信息，如明显的排版式样和其它语言规律 ，眭。 2 3 文本挖掘中文本的表示模型曲 为了使计算机能够真正处理文本特征，必须对文本特征进行特征加权，将 文本表示成计算机可以处理的数学向量。自从文木检索( a u t o m a t i ct e x tr e t r i e v a l ) 和信息检索( i n f o r m a t i o nr e t r i e v a l ) 概念首次被提出后，出现了许多基 于文档( d o c u m e n t ) 和问题( q u e r y ) 之间相关词语比较的计算模型，具有代表性的 有布尔模型( b o o l e a nm o d e l ) 、向量空间模型( v e c t o rs p a c em o d e l ) 、概率模 型( p r o b a b i l i s t i cm o d e l ) 等。这些模型从不同角度出发，使用不同的方法处 理特征加权、类别学习和相似计算等问题。向量空间模型中，一篇文档表示为 特征空间中的一个向量，这个向量也称为文档向量。文档向量中每一维对应于 文档中的一个特征，它的权值为该向量维对应的特征在文档库中的权值，一般 采用t f - i d f 方法计算。两篇文档的相似度，则通过计算对应文档向量的夹角余 弦得到。 布尔模型是基于特征项的严格匹配模型，它可以看作是向量模型的一种 特例，根据特征是否在文档中出现，特征的权值只能取l 或0 。首先，建立一个 二值变量的集合，这些变量对应于文本的特征项。文本用这些特征变量来表示， 如果出现相应的特征项，则特征变量取1 ；否则，特征交量取0 。查询由特征项 和逻辑运算符“a n d ”、“o r ”和“n o t ”组成。文本与查询的匹配规则遵循布 尔运算的法则。 布尔模型在二十世纪六、七十年代得到了较大的发展，出现了许多基于布 尔模型的商用检索系统，如d i a l o g ，s t a i r s 等。其主要优点是；速度快，易于 表达一定程度的结构化信息，如同义关系( 电脑o r 微机o r 机算机) 或词组 ( 文本a n d 过滤a n d 系统) 。其缺点是：把布尔模烈作为文本的表示很不精 确，不能反映特征项对于文本的重要性，缺乏定量的分析；过于严格，缺乏灵 活性，更谈不上模糊匹配，这往往忽略了许多满足用户需求的文本。 在向量空间模型中，文档d 被看作一系列无序词条的集合，对每个词条加 第2 章文本挖掘基本方法 上一个对应的权值，矢量空间模型以矢量表示文本：( c o ，彩：，国f ，缈。) ，其 中。为第i 个特征项的权重。耍将文本表示为矢量空间中的一个矢量，首先要 将文本分词，由这些词作为向量的维数来表示文本。最初的矢量表示完全是0 、 l 形式，当文本中出现了该词，那么文本向量的该词为1 ，否则为0 。这种方法无 法体现这个词在文本中的作用程度，逐渐被更精确的词频代替。词频分为绝对 词频和相对词频，前者即词在文本中出现的频率表示文本，后者为归一化的词 频。矢量空间模型将文档映射为一个特征矢量：矿( d ) = ( f 。，国，( j ) ，f 。，脚。( d ) ) ， 其中r 。为词条项，棚( d ) 为在d 中的权值。缈，( d ) 一般被定义为f ，在d 中出现频 率t f , ( d ) 的函数，即国：( d ) = ( 矿( d ) ) a 在信息检索中常用的词条权值计算方法 为t f i d f 函数y ：矿( d ) 。l 。g ( 盟) ，其中为所有文档的数目，n 。为含有词条t 的 一 文档数目。 下面是一个常用的t f - i d f 公式： k ( d ) = 娠( 讪g ( 生+ 0 0 1 ) 仇 唇丙币 ( 2 - 1 ) 其中，如( d ) 表示词条t 。在文档d 中出现的频率，表示全部样本文档的总数， h 。表示包含词条的文档数。 根据t f i d f 公式，文档集中包含某一词条的文档越多，说明它区分文档类 别属性的能力越低，其权值越小；另一方面，某一文档中某词条出现的频率 越高，说明它区分文档内容属性的能力越强，其权值越大。 向量空间模型的优点在于：将文本和查询简化为项及权重集合的向量表示， 从而把检索操作变成向量空间上的向量运算，其权重计算可以通过简单的频数 统计来完成，通过定量的分析，匹配文本和查询。在这个基础上，引入各种成 熟的统计方法，更大程度的挖掘文本中蕴含的语义信息。如主成分、因子分析、 聚类分析等。 向量空间模型的缺点在于项之间线性无关的假设。在自然语言中，词或短 语之间存在着十分密切的联系，即存在“斜交”想象，很难满足假定条件，因 成都理工大学硕士学位论文 此对计算结果的可靠性造成一定的影响。此外，将复杂的语义关系归结为简单 的向量结构，丢失了许多有价值的线索。因此，有许多改进的技术，以获取深 层潜藏的语义结构。 概率模型是基于概率排序原则，对于给定用户查询q ，对所有文本计算 概率，并从大到小进行排序，概率公式为p ( r i d ，q ) 。其中，r 表示文本d 与 用户查询q 相关。另外，用r 表示文本d 与用户查询q 不相关，有 p ( r i d ，q ) + e ( r 。i d ，q ) = l ，也就是二值形式判断相关性。 把文本用特征向量表示：x = ( 工，x ：，x 。) 。其中，n 为特征项的个数，_ 为0 或1 ，分别表示特征项i 在文本中出现或不出现。 在信息检索中，估计参数是困难的，一般并不直接计算p ，而是把计算 p ( 五j d ，q 。) 换为计算户( 点i x , q 。) ，这样处理略去了公式中与文本无关的特征项， 计算的结果可能与实际不符。为了容易计算，现在假设：包含相同特征项的文 本，经过计算后，它们的可能性是相同的。经所有文本按相关概率p 进行排序， 等价于将所有文本按特征向量排序。任一文本d 的概率相关性的计算为： 尸( 尺i 。，q ) 2 莩x ix l g 删 2 2 ) 其中，只= p ( x ，= 1 i r ，q ) ，q ，= p ( x 。= 1 1 只，q ) a 参数p ，q 1 主要是通过相关反馈进行估计，简单的方法如下： p 。= ，q 。= ( 胛，一) ( 卵一，) ( 2 - 3 ) 其中，n 为反馈文本集所含文本总数，r 为与用户查询相关的文本数，n ，为 特征i 出现的文本个数，n 为特征i 出现且与用户查询相关的文本个数。 决策树方法、关联规则方法和b o o s t i n g 方法就是基于布尔模型：而k n n 法、 s v g 方法、l l s f 是基于向量模型。b a y e s 推理网分类方法，则考虑了文档中词之 间的依赖关系。 2 4 文本挖掘方法 文本挖掘可以用通用的数据挖掘的方法进于亍处理。常用的文本挖掘有贝叶 斯分类法、决策树分类法、支持向量机算法、神经网络方法、最大平均熵方法 和k 近邻方法等，下面我们主要介绍一下支持向量机、k 近邻法和神经网络算法。 9 第2 章文本挖掘基本方法 2 4 1 支持向量机。” 支持矢量机( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 的理论基础来自于统计学习 的理论，它的基本思想是，对于一个给定的具有有限数量训练样本的学习任务， 如何在准确性( 对于给定训练集) 和机器容量( 机器可无错误地学习任意训练集 的能力) 进行折衷，以得到最佳的推广性能。它采用结构风险最小化原则。s v m 算法不仅具有扎实的理论基础，而且在应用到文本分类时取得了很好的结果。 设给定的训练集为( z i ，y i ) ，( x 2 ，y 2 ) ，( ，y r ) ，其中z ，r ”，i = 1 , 2 ，f 是z 个 胛维训练样本，每个样本对应的标记为y 。 l ，一1 ) ，i = 1 , 2 ，标明该向量属于两 类中的那一类。如果一个训练集中的矢量能被一个超平面无错误地线性分割， 且距该超平面最近的矢量之间的距离最大，则称该超平面为最佳超平面。根据 统计学习理论，最佳超平面不但能将两类样本正确分开，而且能使分类间隔 ( m a r g i n ) 最大。如图2 - 2 所示情况下，圆圈加号和圆圈减号分别代表两类样本， 实线为分界面，虚线分别为过各类中离分界面最近的样本且平行于分界面的面， 它们之间的距离就叫做分类间隔。虽然图中虚线也能将两类样本分开，但它的 分类间隔比h 小。其中距离超平面最近的点称为支持矢量( s u p p o r tv e c t o r ) 。 图2 - 2 量佳超平面图 若”维空间中线性判别函数w x + 6 能将训练样本分开，则有 w x 。+ 6 1 矿y ，= l ， w - x ，+ 6 l 矿y 。= 一l 。 我们称上述不等式为规范形式。可将上述不等式合并为： y ，( w x f + 6 ) 1 i = 1 ，- ， 1 0 ( 2 4 ) ( 2 - 5 ) ( 2 6 ) 成都理工大学硕士学位论文 于是构造最佳超平面的问题转化为求： o ( w ) = | | w 2 ( 2 7 ) 的最小值问题。事实上，支持矢量到超平面的距离为绷w ，于是支持矢量之 间的间隔为衫w 寻求具有最大间隔的最佳超平面的依据是，一个规范超平面子集的v c 维数 满足下列不等式： h r a m ( r2 a 2 】，n ) + 1 ( 2 - 8 ) 其中n 为矢量空间的维数，所有待分割的矢量位于半径为r 的超球内，1 1 w 临a 。 这样我们就可在固定经验风险的情况下，将使v c 置信度最小的问题转化为使 l lw l j 最小的问题。构建最佳超平面来分割属于两类的训练集 ( x 1 ，y 1 ) ，( x 2 ，y 2 ) ，( x f ，2 ，) ，x r ”，y + 1 ，- 1 ) ( 2 - 9 ) 的问题，转化为解决下述二次规划问题： 在约束条件 y 。( w 工+ 1 f = l ，z ( 2 1 0 ) 下，求 1 中( w ) = 去( w w ) ( 2 - 1 1 ) 二 的最小值。为了将线性推广到非线性，v a p n i k 提出了支持矢量机的概念，其基 本思想是：通过事先确定的非线性映射将输入矢量x 映射到一个高维的特征空间 ( 一个h i l b e r t 空间) 中，然后在此高维特征空间中构建最佳超平面。 超平面是对两类分类的划分，对于有大于两类的多类文本分类，就对每个 类构造一个超平面，将这一个类与其余的类分开。有多少个类就构造多少个超 平面。测试时就看哪个超平面最适合测试样本。 t h o s t e nj o a c h i m s 将s 硪用于文本分类并比较了其它的分类算法。他的结果 显示s v m 要优于其它方法。 2 4 2k 近邻法m 1 k 近邻法( kn e a r e s tn e i g h b o r ，k n n ) 是 鱼c e v e r 和h a r t 于1 9 6 8 年提出的， 直至现在仍是模式识别非参数法中最重要的方法之一。k n n 算法思想很简单：给 一篇待识别的文章，系统在训练集中找到最近的k 个近邻，看这k 个近邻中多数 属于哪一类，就把待识别的文章归为哪一类。k 近邻分类器在己分类文章中检索 与待识别的文章最相似的文章，从而获得被测文章的类别。此算法有简单的优 第2 章文本挖掘基本方法 点，但存在问题，需要将所有样本存入计算机中，每次决策都要计算待识别样 本与全部训练样本之间的距离进行比较。因此计算新文档时存储量和计算量都 较大。 统计词在文档中的有两种定义，一种是二项式赋值，即如果单词在文档中 出现就设为1 ，否则设为0 ，这样计算就比较简单：另一种是计算单词在文档中 出现的频率，这样算法可以利用更多的信息，分类精度要高于第一种定义。统 计词频矩阵后按t f i d f 公式给文档向量赋权值。 = 以十i a f k ( 2 - 1 2 ) i a l = l o g ( n a l + 1 ) ( 2 - 1 3 ) 其中n 为训练集中的文档数，如指第_ j 个单词在第i 篇文档中的频率，矾 指在整个训练集中，包含第k 个单词的文档个数。距离公式采用c o s i n e 相似度 距离公式： c o s ( d 毛d 一) ：生()s 2 - 1 4 ，) = - l 乇一 () d ， d ，l 2 4 3 朴素贝叶斯方法 朴素贝叶斯方法是本文的重点，将在第4 章详细讲述。此处略。 2 4 3 神经网络方法“” 神经网络模式识别方法是近几年兴起的模式识别领域的一个新的研究方 向。由于神经网络的高速并行处理，分布存储信息等特性符合人类思维系统的 基本工作原则，具有很强的自学习性、自组织性、容错性、高度非线性性、高 的鲁棒性、联想记忆功能和推理意识功能等，能够实现目前基于计算理论层次 上的模式识别理论所无法完成的模式信息处理工作，所以采用神经网络进行模 式识别，突破了传统模式识别技术的束缚，开辟了模式识别发展的新途径。同 时，神经网络模式识别也成为神经网络最成功和最有前途的应用领域之一。 神经网络文本分类器可采用一种三层前馈型b p 网络，来进行自动知识获取， 如图2 3 所示。b p 网络有三个基本层，即输入层、隐含层和输出层。每个层都包 含若干个节点( 神经元) ，输入层的节点数通常为矢量的个数，输出层节点数为 输出矢量的个数。层与层之间的每个连接都有一个可以调整的权，它决定一个 输入矢量对输出矢量的影响。 成都理工大学硕士学位论文 输入 输入层隐含层输出层 固2 - 3三层前馈型b p 神经网络图 值c j 简单的，给定一段文本及其特征集，输入层神经元的个数设定为特征词集 的大小，输出层神经元的个数设定为类别集的大小，可以定义该神经网络的输 入层第个分量f 。和输出层第，个分量c ，为： f1 ，文本中存在特征集中的第i 个特征词； 。 0 ，文本中不存在特征集中的第i 个特征词。 i1 ，文本属于文本集中的第，类； 1 1 0 ，文本不属于文本集中的第，类。 2 5 评估方法1 5 1 评估方法在文本分类中具有非常重要的作用，特征提取和分类器训练都需 要使用评估方法，分类系统的训练过程是以评估方法作为依据进行的。文本分 类的性能评估方法主要有两种： 准确率招回率曲线 这类方法是从信息检索的角度，把文本分类作为一个排序问题进行评估。 评估围绕着准确率招回率曲线进行，最直接的方法是完整描绘出准确率一 一招回率曲线。为了比较的方便，有时需要计算一个确定的数值，如准确率一 一招回率等值点( p r e c i s i o n r e c a l l b r e n k e v e np o i n t ) 曲线，来反映整条准确 率招回率曲线的结果。 7 分类准确率( p r e c i s i o n ) ，分类招回率( r e c a l l ) 与f 值 这类方法是从模式识别的角度出发，将文本分类作为一个识别问题进行评 估的。评估不是围绕一条曲线而是针对某一个点进行的。传统模式识别多使用 第2 章文本挖掘基本方法 半均决策损失作为优化分荚器的目标，但文本分类中常用的指标为分类招回率， 分类准确率和曩值。这里，我们介绍国际上通用的准确率p 、招回率r 和e 值 系统性能评估方法，准确率和查全率反映了分类质量的两个不同方面，两者必 须综合考虑。因此，出现了一种新的评估方法f 值法。 假设有，l 篇文本d i , - - , d ，分别属于n 个类别c l ，t ，q 中，分别由专家和 分类程序对全部文本进行分类，对于类别c j ，其准确率只、招回率r 。与e ，评 估值公式分别如下： 只：孥( 2 - i 5 ) 。 r ：孥( 2 - 1 6 ) e 。：尝 ( 2 _ 1 7 ) “ ( 胄。+ z ) 札是m 篇文本中专家认为属于c 。类的文本数；。是m 篇文本中分类器预测为 c l 类的文本数；心。是专家和程序都认为属于c ；类的文本数，即被正确分类的 文本数。 微平均和宏平均是评测系统整体性能的两种方法。用m r 、m p 和m e 表示 微平均中的微观招回率、微观准确率和微观f 值，则分类系统的微平均计算公 式如下： m p = j 堕一 虬， 。 2 m r + m 尸 舢= 一 1 ( m r + r a p ) ( 2 1 8 ) ( 2 - 1 9 ) ( 2 2 0 ) 用m r 、m p 和柳e 。表示宏平均中的宏观招回率、宏观准确率和宏观e 值，则 分类系统的宏平均计算公式如下： 1 4 成都理工大学硕士学位论文 m r ：一1 ) n ，尺 咒智 ( 2 - 2 1 ) 御= 三y 1 只 m f , ：2 * m r * m p ( 2 2 3 ) ( m r + m p ) 一般来说，微平均易受到大类分类结果的影响，而宏平均是对全部类别取均值 相对易受小类分类结果的影响。 第3 章改进互信息特征提取 第3 章改进互信息特征提取 文本分类中的特征选择( f e a t u r es e l e c t i o n ) 和特征提取( f e a t u r ee x t r a c t i o n ) 是用机器学习方法进行文本分类的首要任务和关键问题。这里文本的特征 就直接采用文本中的词条t ( t o k e n ) 作为特征项，于是文本可以表示为特征的向 量，即x = ( ，t ：，f 。) ，元素t ，是词条。同样，类别也可以用特征表示为 c = ( t it 2 ，t ) 。 原始特征的数量可能很大，或者说样本是处于一个高维空间中，通过映射 ( m a p p i n g ) 或变换( t r a n s f o r m ) 的方法可以用低维空间来表示样本，这个过程叫 特征提取。映射后的特征叫二次特征，它们是原始特征的某种组合( 通常是线性 组合) 。所谓特征提取在广义上就是指一种变换，若l ，是测量空间，x 是特征空 间，则变换a ：y 斗x 就叫做特征提取变换。 从一组特征中挑选出一些最有效的特征以达到降低特征空间维数的目的， 这个过程叫特征选择。特征选择和特征提取可以降低特征空间的维数，从而达 到降低计算复杂度和提高分类的准确率的目的，并为后面的分类器的设计提供 参数。 特征提取一般是通过构造一个特征评分函数，把测量空间的数据投影到特 征空间，得到在特征空间的值，然后根据特征空间中的值对每个特征进行评估， 特征选择就成了选择值最高的若干个特征“”。另外，为提高分类器的性能，也 须把高维的特征空间压缩到低维的空间。我们在这章中首先介绍了几种常用的 特征提取方法，然后提出了一种改进互信息的特征提取方法。本章参考了文献 1 7 一 2 0 。 3 1 常用的特征提取方法”羽 文本分类中的特征提取方法主要有：特征词的文档频率法d f ( d o c u m e n tf r e q u e n c y ) 、信息增益法i g ( i n f o r m a t i o ng a i n ) 、互信息法m i ( m u t u a li n f o r m a t i o n ) 、五2 统计法( c h i ) 、交叉熵( c r o s se n t r o p y ) 、主成分分析p c a ( p r i m a r y c o m p o n e n ta n a l y s i s ) 等。 3 1 1 特征词的文档频率( d f ) 一个特征的文档频率( d o c u m e n tf r e q u e n c y ) 是指在文档集中含有该特征的 文档数目。采用d f 作为特征选择，基于如下基本假设：d f 值低于某个阈值的词 1 6 成都理工大学硕士学位论文 条是低频词，它们不含或含有较少的类别信息。我们假定很少出现的特征词携 带的信息量为0 ，或者说对分类性能的影响不大。将这样的词条从原始特征空间 中除去，不但能够降低特征空间的维数，而且还有可能提高分类的精度。文档 频率是最简单的特征抽取技术，由于其相对于训练语料规模具有线性的计算复 杂度，它能够很容易被用于大规模语料统计。而在信息检索研究中通常却认为 d f 值低的词条相对于d f 值高的词条具有较多的信息量，不应该将它们完全移除。 不同的应用将对d f 值的认识不同，因此应具体情况来选择该方法。 该方法通常用作辅助的特征提取方法。 3 1 2 信息增益方法( 1 g ) 信息增量( i n f o r m a t i o ng a i n ) 表示文档中包含某一特征值时文档类的平均 信息量。它定义为某一特征在文档中出现前后的信息熵之差。信息增益值度量 了当知道一个特征词是否在文档中，进行类预测所获得的信息比特数。信息增 益的计算公式如下： i ( t ，f ) = e ( t ) 一e ( t i t ) ( 3 - 1 ) = 一p r ( t ( d ) = c ) l o g p r ( t ( d ) 2c ) + 饨c p r ( t ( d ) = c ，t = 0 ) l o g p r ( t ( d ) = c ，f = o ) + 饨c p r ( t ( d ) = c ，t = 1 ) l o g p r ( t ( d ) = c ，= 1 ) ( 3 - 2 ) 磊 其中e ( t ) 表示所有的类的平均信息熵，e ( t i t ) 表示在知道特征词r 是否在 文档中出现的条件下所有类的平均条件信息熵。它们之间的差值表示了特征词、 所蕴涵的信息量，从而量化了特征词r 在分类过程中的重要程度。 p r ( t ( d ) = c ，t = 0 ) ，表示了不出现特征词t 的文档在类c 中出现的概率。其他的 定义类似。 将特征词按信息增益值由大到小排列，选取前k 个特征词构成最终的特征 词集合矿( v l - 七) 。还可以类似于d f 方法一样去除信息增益值小于预定义阀值的 特征词。计算每个特征词的信息增益值的时间复杂度为o ( m ) ( m 为类别数) ，则 特征提取的总时间复杂度为o ( v m ) ( 矿为特征词的总数) 。每个特征词最多在n 个训练文档中出现( n 为训练文档总数) ，空间复杂度为o ( v n ) 。 1 7 第3 章改进互信息特征提取 3 1 3 主成分分析( p c a ) 主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ) 的思想进行坐标轴变换，使 得数据的变异性最大。数据的变异性用数据的协方差矩阵来度量。 设变换后的坐标轴为单位向量d ，训练数据为x 1x ：，x 。，组成矩阵以。， 变换后的协方差矩阵为： 盯。2 ：( 肠) 7x a = a t 皤7 z ：a r ( x r r x ) a ( 3 - 3 ) a a 求上式的极大值转化为求r a y l e i g h 熵。当a 取x 7 最大的特征值对应的特 征向量时，式( 3 8 ) 取极大。 取前m 个主成分作为变换后的正交坐标系。每个训练样本在该坐标系下的 坐标为： 只= ( 岛，p 2 ，孽艚) 7 t ，i