（计算机软件与理论专业论文）x2统计量在文本分类中的应用研究.pdf

中山大学硕士论文 f 统计量在文本分类中的应用研究 f 统计量在文本分类中的应用研究 计算机软件与理论 硕士生： 指导教师： 谭焕云 印鉴教授 摘要 随着i n t e m e t 上文档信息的迅猛发展，文本自动分类成为处理和组织大量文 档数据的关键技术。本文在已有研究的基础上对中文文本分类进行了分析研究。 由于x j 统计量能很好地体现特征和类别之间的相关性，因此成为特征选择中常 用的评估函数。本文分析了x 2 统计量在特征选择和分类决策阶段的性质，提出 了一种新的基于# 统计量的文档c h i 定义以及基于文档c h i 的文本相似度计算 公式，建立了一个适合中文文本分类的向量空间模型。常见的文本分类方法中， 类中心向量法计算量小，算法简单，但分类性能较差；k n n 算法分类准确率较 高，但计算量大。本文结合两种算法的优点，在k n n 算法中引入快速搜索机制， 利用类中心向量法对待分类文档进行初次类别判定，确定k n n 算法中二次搜索 的文档类别范围，利用此类别范围的训练集对待分类文档进行二次类别判定，从 而确定文本的晟终类别。实验结果表明基于文档c h l 向量和二次类别判定机制 的改进k n n 文本分类算法能大大减少k n n 算法的分类时间，并提高k n n 算法 的准确率和召回率。 关键词：文本分类；特征选择；k n n ；x 2 统计量 中山大学硕士论文 z 2 统计量在文本分类中的应用研究 r e s e a r c ho l l 矛s t a t i s t i ci nt e x tc a t e g o r i z a t i o n c o m p u t e rs c i e n c e n a m e ：t a n h u a n + y u n s u p e r v i s o r ：y i nj i a n a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fo n l i n ei n f o r m a t i o n ，t e x tc l a s s i f i c a t i o nh a sb e c o m et h e k e yt e c h n o l o g yi np r o c e s s i n ga n do r g a n i z i n gl a r g ea m o u n to fd o c u m e n td a t a f s t a t i s t i ci saw i d e l yu s e de v a l u a t i o nf u n c t i o ni nf e a t a r es e l e c t i o ns i n c ei tm e a s u r e st h e l a c ko fi n d e p e n d e n c eb e t w e e nat e r ma n dac l a s se f f e c t i v e l y t h i s - p a p e rp r o p o s e da n e wd e f i n i t i o nt om e a s u r et h el a c ko fi n d e p e n d e n c eb e t w e e nad o c u m e n ta n dac l a s s b a s e do n s t a t i s t i c ，a n dt h e nr e d e f i n e dt h es i m i l a r i t yb e t w e e nt w of i l e s t h i sp a p e r p r o p o s e dah y b r i dc l a s s i f i c a t i o nm e c h a n i s m ，a n dt h e na p p l i e dt h e mt oi m p r o v et h e t r a d i t i o n a l 洲t h en e wm e t h o dc l a s s i f i e dad o c u m e n tb yt w os t e p s ：f i r s ti tf o a n da s m a l l e rc l a s sr a n g eu s i n gt h ec l a s s i f i c a t i o nb a s e do nt h ec e n t e ro fc l a s s e s ，a n dt h e n d e t e r m i n e dt h ec l a s so ft h ed o c u m e n tu s i n gt r a d i t i o n a lk n n e x p e r i m e n t ss h o wt h a t t h en e wm e t h o dc a nr e d u c et e s tt i m eg r e a t l ya n di m p r o v et h ep r e c i s i o na n dr e c a l l c o m p a r e dw i t ht r a d i t i o n a lk n n i t sp e r f o r m a n c ei sh i g h e rt h a nt r a d i t i o n a lk n na n d c o m p a r a b l ew i t hs v m t o r c h k e yw o r d s ：t e x tc a t e g o r i z a t i o n ；x 2s t a t i s t i c ；k n n ；f e a t u r es e l e c t i o n i l 中山大学硕士论文 f 统计量在文本分类中的应用研究 第1 章引言 我们正处在一个高速发展的信息时代，特别是i n t e m e t 的迅速发展，信息的 数量级从9 0 年代初的m b 过渡到g b 、现在已上升到t b 。而且随着近年来电子 图书馆的日益普及，越来越多的文本信息表现为电子文档。文本数据库在数字图 书馆、办公自动化、软件工程、自动目录管理、图书报刊出版与发行以及涉及文 本信息存取的其它领域有着非常广泛的应用前景。面对如此庞大而且急剧膨胀的 信息海洋，如何高效地组织和管理这些信息，并快速、准确、全面地从中搜索到 用户所需要的信息是当前信息科学与技术领域面l | 台；的一大挑战【0 1 。 文本分类是语料库建设、信息检索和信息过滤等技术研究的基础，在互联网、 电子出版业、电子图书馆、电子邮件分检、网络安全等方面都有十分广泛的应用。 利用文本分类技术可以对数据巨大但缺乏结构的文本数据进行有序的组织，为信 息检索提供更高效的搜索策略和更精确的检索结果。目前，国外关于英文的文本 分类技术的研究已经比较成熟，出现了很多文本分类的软件，而国内关于中文文 本分类的研究尚不成熟，还没有模块化的软件出现。而i n m e t 的发展使得文本 数据极大丰富，对文本自动分类提出了更为迫切的要求。基于规则的分类技术的 精确度很高，但是对于如此众多的文本靠人工提取规则进行分类花费极大，传统 的人工分类无法满足时代发展的需要。因此文本的自动分类及其相关技术的研究 也正日益成为人们研究的热点。文本自动分类系统可以大大降低组织和整理文档 所耗费的人力资源，帮助用户快速找到所需信息。 现有的文本自动分类主要基于统计理论和机器学习方法 2 】，许多数据挖掘通 用的分类方法也可用于文本分类，如b a y e s 分类、心n 、支持向量机、线性最小 方差匹配、神经网络等。其中，作为在r e u t e r s 语料上取得最好结果之一的文本 分类算法，k n n ( k - n e a r e s t n e i g h b o r ) 得到了研究者广泛的关注。 k n n 算法分类准确率高，但计算量大，分类速度慢。而类中心向量法计算 量小，分类速度快，但准确率较差。本文主要针对k n n 算法中计算量大的不足， 结合k n n 算法和类中心向量法两者的优点，提出了一种基于两次类别判定的改 进k n n 算法。分类时利用基于类中心向量法的初次类别判定算法迅速判定测试 文档的可能类别，从而在k n n 算法中引入了快速搜索机制，在小的类别范围内 的训练集中进行k n n 分类。 中山大学硕上论文 x 2 统计量确文本分类中的应用研究 由于文本集的原始特征空间维数往往过大，过高的特征空间维数给分类算法 的时间和空间性能带来了更大的挑战，同时也引入了更多的噪声。因此文本分类 算法的一个重要步骤是特征选择，即从大量的属性中选择最好的属性子集用于分 类学习。矿统计量很好地体现了特征和类别之间的相关性，因此特征选择中常用 c h i 值作为评估函数，保留和类别相关性强的特征。但是在目前的分类算法中， c h i 并没有在决策过程中得到充分的利用。为此，本文分析了z 2 统计量的性质， 对特征的c h i 值进行了扩展，通过定义文档的c h i 向量和类别特征集，使c h i 方法应用到了文本分类的决策过程中。 本文的组织如下： 第2 章介绍了文本挖掘的一些相关知识，包括数据挖掘的背景、文本 挖掘的过程及不同研究方向、文本挖掘的应用等。 第3 章介绍了文本分类的基础知识，包括文本的向量空间模型、文本 分类的一般流程，并介绍了目前常用的文本分类方法。分析了 k n n 算法的缺点，为第四章的研究提供了依据。 第4 章本章是本文研究的主体。讨论了特征选择中包括c h i 方法在内 的不同的评估函数，通过分析c h i 的性质，定义了基于x 2 统计 量的文档c h i 和类别特征集，将c h i 方法的应用从特征选择阶 段扩展到了分类决策阶段，并结合k n n 算法和类中心向量法， 通过两次类别判定对传统k n n 算法进行了改进。 第5 章通过实验证明了基于文档c h i 向量和二次类别判定机制的改进 k n n 文本分类算法在分类性能上的优势。 第6 章 对全文工作进行了总结，并对下一步的研究工作进行了展望。 中山大学硕士论文 f 统计量在文本分类中的应用研究 第2 章文本数据挖掘概述 2 1 数据挖掘背景 随着时代的进步，人们产生和收集数据能力的提高，人们积累的数据呈指数 级的增长。数据的丰富带来了对强有力的数据分析工具的需求，传统的数据库查 询手段已经很难满足人们的需要，大量的数据被描述为“数据丰富，但信息贫 乏”。快速增长的海量数据收集、存放在大型和大量的数据库中，却由于缺乏将 这些数据转换成有价值的信息和知识的新技术和自动化工具，使得收集在大型数 据库中的数据变成了“数据坟墓”难得再访问的数据档案。人们开始考虑： “如何才能不被信息淹没，而是从中及时发现有用的知识、提高信息利用率? ” 人们迫切需要种能够对庞大的数据进行更高层次处理的技术，从中找出规律和 模式，以帮助人们更好地利用数据进行决策管理和研究，而数据挖掘技术从 大量数据中用非平凡的方法发现有用的知识的出现，引起了人们广泛的关 注，导致了数据挖掘研究的蓬勃发展。 数据挖掘( d a t a m i n i n g ) ，通常又称为数据中的知识发现( k n o w l e d g e d i s c o v e r y i nd a t a b a s e s ，k d d ) ，就是从存储在大型数据库、数据仓库或其他信息存储容器中 的大量的、不完全的、有噪声的、模糊的、随机的数据里提取人们感兴趣的知识， 这些知识是隐含的、事先未知的、对决策有潜在价值的有用信息 1 】。数据挖掘通 过预测未来趋势及行为，做出前摄的、基于知识的决策，其目的是从数据库中发 现隐含的、有意义的知识。它主要有以下五类功能：自动预测趋势和行为、关联 分析、聚类、概念描述和偏差检测。 数据挖掘研究兴起于二十世纪八十年代初，它是一个众多学科诸如人工智 能、机器学习、高性能计算、模式识别、统计学、数据库和知识库、数据可视化 等相互交叉、融合所形成的一个新兴的且具有广阔前景的领域。机器学习和数据 分析的理论及实践是数据挖掘研究的基础，极大的商业应用前景又是数据挖掘研 究工作的巨大推动力。近年来，数据挖掘技术引起了信息产业界的极大关注，其 主要原因是存在大量数据可以广泛使用，并且迫切需要将这些数据转换成有用的 中山大学颁士论文 f 统计量在文本分类中的应用研究 信息和知识。获取的信息和知识可以广泛用于各种应用，包括商务管理、生产控 制、市场分析、工程设计和科学探索等。 一份最近的g a r t n e rg r o u p 报告中列举了在今后3 5 年内对工业将产生重要 影响的五项关键技术，其中k d d 和人工智能排名第一。同时，这份报告将并行 计算机体系结构研究和k d d 列入今后5 年内公司应该投资的l o 个新技术领域。 可以看出，数据挖掘的研究和应用受到了学术界和实业界越来越多的重视，预计 还会形成更大的高潮。数据挖掘领域的几个热点包括网站的数据挖掘( w e bs i t e d a t am i n i n g ) 、生物信息或基因( b i o i n f o r m a t i c s g e n o m i c s ) 的数据挖掘及其文本 的数据挖掘( t e x t u a lm i n i n g ) 。 2 2 文本挖掘定义 以结构化数据为主的关系数据库、事务数据库和数据仓库为研究对象的数据 挖掘技术目前已经比较成熟。而随着数据处理工具、先进数据库技术以及网络技 术的迅速发展，大量的形式各异的复杂类型的数据不断涌现，这包括时空数据、 多媒体数据、文本数据和w e b 数据等等，因此对这些复杂类型数据的挖掘作为 一个重要课题开始引起人们的关注，出现了针对特定的复杂数据类型的数据挖掘 技术，如空间数据库挖掘、多媒体数据挖掘、时序数据和亭列数据的挖掘、w e b 挖掘和文本挖掘。 文本数据挖掘指利用基于关键字的关联和文档分类之类的方法从半结构化 的文本数据中发现知识的过程。由于现实世界中的大部分可获得的信息是存储在 文本数据库中的，因此文本数据挖掘成为人们研究的热点。文本挖掘的研究的数 据类型是半结构化数据，半结构化数据指既不是完全无结构的也不是完全结构化 的。如文档中的标题、作者等字段是结构化的，而内容是非结构化成分。针对这 些半结构化的数据挖掘涵盖了多种技术，包括信息抽取、信息检索、自然语言处 理和数据库等。 2 3 文本挖掘分类 文本挖掘的一般处理过程如图2 1 所示。首先需要从文本中提取特征，并用 结构化的形式保存，作为文本的中间表示形式。一般初始特征空间具有惊人的维 中山大学硕士论文 z 2 统计量在文本分类中的应用研究 数，需要进行特征选择以确定最优的特征子集。在完成特征向量维数的缩减后， 提取面向特定应用目的的知识模式并对获取的知识模型进行质量评价，若评价的 结果满足一定的要求，则存储该知识模式，否则返回到以前的某个环节，对算法 分析改进后重新挖掘。 图2 1 ：文本挖掘的一般处理流程 根据挖掘方法和知识模式类型的不同，文本挖掘可以大致分为文本检索、文 本过滤、关联分析、文本摘要、文本分类和文本聚类等几个方面，一般一个系统 中这几个方面是交叉的。 ( 1 ) 文本过滤和文本检索 文本过滤项目的任务定义是：给定一个主题描述( 用户需求) ，建立一个能 从文本流中自动选择最相关文本的过滤模板( f i l t e r i n g p r o f i l e ) 3 1o 随着文本流的 逐渐进入，过滤系统自动地接受或拒绝文本，并得到文本相关与否的反馈信息， 根据反馈信息自适应地修正过滤模板。文本过滤就是从大量的文本数据流中寻找 满足特定用户需求的文本的过程，它在档案管理、垃圾邮件过滤、网页不良信息 过滤等领域得到了广泛的应用。 文本检索是指从包含各种信息的文档集中查找所需要的知识或信息的过程， 这和文本过滤有很大的相似之处，二者的不同之处在于：文本检索有相对固定的 文本数据库和动态变化的检索需求，而文本过滤则有着相对固定的用户需求和动 态变化的文本数据流。 ( 2 ) 文本关联分析 基于关键字的文本关联分析首先收集经常一起出现的关键字或词汇，然后找 出其关联或相互关系。如果将文档数据库中的每一文档视为一个事务，文档中的 关键字视为事务中的一组事务项，则文本的关联分析就变成了事务数据库中事务 项的关联挖掘，这在数据挖掘中已经有成熟的算法，如a p r i o r i 、频繁模式增长 ( f r e q u e n t p a t t e r ng r o w t h ) 等算法。如b r i n 提出了一种从大量文本中发现一对 词语出现模式的算法，并用来在w e b 上寻找作者和书名的出现模式，从而发现 中山大学硕士论文# 统计量在文本分类中的应用研究 了数千本在a m a z o n 网站上找不到的新书籍【4 j 。 ( 3 ) 文本摘要 文本摘要又称文本总结，是指从文档中抽取关键信息，用简洁的形式对文档 内容进行总结或解释口1 。文本摘要的目的就是尽量减少用户阅读的文本量。许多 文档的主要思想最少可以用原文篇幅的2 0 来概括，因此摘要后的损失很少。这 样，用户不需要浏览全文就可以了解文档或文档集合的总体内容。文本摘要在有 些场合十分有用，例如，搜索引擎在向用户返回查询结果时，通常需要给出文档 的摘要。一些算法将首句和尾句中包含的词汇赋予较高的权重，而一些方法则寻 找能够表明一些句子很重要的关键词组 为重要的是”( m o s ti m p o r t a n t l y ) 等等。 例如“总之”( i nc o n c l u s i o n ) 和“尤 摘要技术总体上分为两类：基于统计的 机械摘要方法和基于知识的理解摘要方法。前者应用领域不受限制、速度快，但 局限于文档的字面表层，生成的摘要质量较著；后者采用了复杂的自然语言理解 和生成技术，因此摘要质量较好，但仅限于非常狭小的应用领域中。 ( 4 ) 文本聚类 文本聚类的目标是将文档集合分成若干个簇，要求同一簇内文档内容的相似 度尽可能地大，而不同簇间的相似度尽可能地小。目前有多种文本聚类算法，大 致可以分为两种类型：以g h a c 等算法为代表的层次凝聚法和以k m e a n s 等算 法为代表的平面划分法【”。层次聚类法是最为常用的聚类方法，它构造了一棵生 成树，其中包含了簇的层次信息以及所有簇内和簇间的相似度，从而生成层次化 的嵌套簇，且准确度较高。但在进行簇的合并时，需要全局地比较所有簇之间的 相似度，并选择出最佳的两个簇，因此运行速度较慢，1 i 适合处理大量文档的集 合。平面划分法与层次聚类法的区别在于：它将文档集合水平地分割为若干个簇， 而不是生成层次化的嵌套簇，因此在一定程度上提高了效率，适合于处理w e b 文 本这种具有大量数据的对象。但它必须事先确定k 的取值，且k 个初始聚类中心选 取的好坏对聚类结果有较大影响。 ( 5 ) 文本分类 文本分类是指按照预先定义的主题类别，为文档集合中的每个文档确定一 个类别【1 z6 1 。文本分类能方便对文档的检索和分析，它般的做法是：首先把一 组预先分类过的文档作为训练集，分析训练集以得到分类模式，然后用导出的分 类模式对其他文档加以分类。文本分类和文本聚类最大的不同在于，前者预先定 义了主题类别，是一种典型的有教师的机器学习问题，后者则是一种典型的无教 师的机器学习问题。 中山大学硕士论文 f 统计量在文本分类中的应用研究 文本挖掘中文本检索、文本过滤、文本摘要、文本分类和文本聚类等相关技 术联系日益密切，并在信息检索、文章摘要、文档分类、自动索引等领域得到了 综合应用，通常一个系统中上述几个方面是交叉的。例如，文本分类技术能够将 相似的、相关的文档有序地组织在一起，这为文本信息检索提供了高效的搜索策 略和更准确的结果。用户可以通过i 艮i i i 搜索的类别范围而使搜索更快捷和准确。 而h e a r s t 等人对“聚类假设”的研究表明，与用户查询相关的文档通常会聚类在 一起，并远离与用户查询不相关的文档。因此，通过文本聚类技术处理文本信息 检索返回的结果，将相关的文档聚类在一簇，这样，用户只需考虑那些相关的簇 中的文档，这大大缩小了用户所需浏览的结果集的范围。 2 4 文本挖掘的应用与发展 由于目前大多数的信息都是通过文本方式体现，如新闻文章、技术论文、书 籍、数字图书馆、电子邮件信息以及w e b 页面等，传统的信息检索技术已不适 应日益增加的大量文本数据处理的需要。因此随着信息技术的发展，文本挖掘技 术得到越来越多的重视，具有广阔的应用价值和商业前景。而文本挖掘和其他数 据挖掘分支的联系也日益紧密，例如对w e b 页面的文本挖掘研究。 w e b 挖掘可以分为w e b 内容挖掘、结构挖掘和使用挖掘。由于目前各w e b 站点主要是以h t m l 、x m l 等文本格式存放半结构化的文本数据，万维网因此 也可以视为一个巨大的、互连的动态文本数据库，w e b 内容挖掘和文本挖掘有着 密切的联系。文本挖掘可以对w e b 上大量文档集合的内容进行总结、分类、聚 类、关联分析，以及利用w e b 文档进行趋势预测等。但是w e b 文本和普通文本的 分类又有所不同，如：网页信息比文本信息更开放，风格不固定；网页的设计比 较随意，通常包含大量的广告、程序源代码、设计人员的注释以及版权声明等无 关信息，这些“噪音”降低了分类的查准率；网页分类的类别比文本分类的类别 更多，为了便于用户浏览和选择，一般要求类别有层次关系；网页的分类体系随 着信息的变化会做一些变动，并且很难有一个统一的标准等等。这表明w e b 文 本分类比普通文本的分类更复杂、更困难，需要针对其特点进行研究。另一方面， w e b 文档中特有的标记女l ， 等蕴含了额外的信息，我们可以利用 这些信息提高w e b 文本分类的性能【7 1 。 目前，w e b 文本挖掘技术在数字图书馆、主题搜索、个性化信息检索、搜索 中山大学硕士论文f 统计量任文本分类中的应用研究 引擎的目录导航、信息过滤、主动信息推送服务等领域得到了广泛的应用，国外 在相关领域的研究比较多，同时还有比较成熟的w e b 文本挖掘工具及产品提供， 例如，i b m 公司推出的w e b 文本挖掘工具i n t e l l i g e n t m i n e r f o r t e x t ，它是i b m 公 司开发的i n t e l l i g e n tm i n e r 家族的成员之一，主要包括三个部分：高级搜索引擎 t e x tm i n e r 、w e b 访问工具和文本分析工具。该工具提供了高效的文本信息挖掘 功能，可以实现全文检索、文本分析、w e b 文档查询和检索等。美国m e g a p u t e r 公司开发的一系列w e b 文本挖掘产品t e x t a n a l y s t 、t e x t r a c t o r 等基于w o r d n e t 和 神经网络技术，可以为用户提供文本总结、分类、聚类、信息抽取等各种功能。 但上述工具都是基于英文环境的，实用的中文w e b 文本挖掘系统还有待进一涉 的研究与开发。 中山大学硕士论文 f 统计量在文本分类中的应用研究 第3 章文本分类算法研究 文本分类是一种典型的有教师的机器学习问题，是按照预先定义的主题类 别，根据文档集合中每个文档的内容确定浚文档的类别。从数学角度来看，文本 分类是一个映射的过程，它将未标明类别的文本映射到已有的类别中，该映射可 以是一对一的映射，也可以是一对多的映射，因为一篇文本可以同多个类别相关 联，此时通常分类算法不会返回类标号，而返回类分布概率。用数学公式表示如 下： ，：爿斗b其中，彳为待分类的文本集合，占为分类体系中的类别集合 文本分类的映射规则f 是系统根据已经掌握的每类若干样本的数据信息，总 结分类的规律性而建立的判别公式和判别规则。系统在遇到新文本时，根据判别 规则，确定文本的类别。 本章介绍了文本分类的基础知识，包括文本的向量表示方法、文本相似度的 定义、文本分类的一般流程及其评价指标，并讨论了目前常用的文本分类方法。 分析了类中心向量法和k n n 算法各自的特点，为第四章的研究提供了依据。 3 1 文本内容的表示 由于文档数据库中存储最多的数据是半结构化数据，而现有的数据挖掘技术 处理的大多是结构化的数据，无法直接应用于其上。因此对文本内容的表示和处 理成为了文本挖掘的必要步骤。首先对文本进行预处理，抽取其特征并用结构化 的形式保存，作为文档的中间表示形式。文本的特征指的是关于文本的元数据， 分为描述性特征和语义性特征。其中描述性特征如文本的名称、日期、大小、类 型等，而语义性特征如文本的作者、机构、标题、内容等。 根据“贝叶斯假设”，假定组成文本的字或词在确定文本类别的作用上相互 独立，文本被看作相互无关的字或词的集合，不考虑字或词的上下文关系、出现 顺序、位置以及文章的长度等等 i 】。这样，就可以使用文本中出现的字或词的集 合来代替文本，无需对文档进行复杂的自然语言处理和语义处理，虽然这将丢失 大量关于文章内容的信息，如文档的篇章结构、语境等，但是这种假设可以使文 中山大学硕士论文 f 统计量在文本分类中的应用研究 本的表示和处理形式化，也使得文档不再依赖某个特定的领域，在文本分类中取 得了较好的效果，因此得到了广泛的应用。 文本内容的表示主要有布尔模型、向量空问模型和概率模型。其中向量空间 模型( v e c t o rs p a c em o d e l ，v s m ) 由r o c c h i o 在1 9 7 1 年最早提出f 8 ，9 】，是文本挖 掘中使用最多的表示方法。v s m 的基本思想是：用词袋表示文本，将每个词条 作为特征向量空问坐标系的一维，将文本看作特征空间的一个向量，用两个向量 之间的夹角来衡量两个文本之间的相似度。 v s m 将大量文本表示成词频矩阵，如表3 一l 所示。 表3 - 1 ：文本的词频矩阵 在该词频矩阵中，每一行表示一个文档向量，每一列表示一个特征项，每一 项，表示特征项t ，在文档d ，中的权值。即在v s m 中，每个文档d 。被表示成矢量 空削中的一点： 矿( 一) = ( ( ，心。) ，( t 2 ，w 。) ，( ，”0 ) ) 从而文档以向量的形式定义到了实数域，使得文档之间的比较变成了向量之间的 比较，这极大地提高了自然语言的可计算性和可操作性，而文档表示的形式化也 为文档处理和应用的形式化奠定了基础。 文档可以表示成一个广义集，集合中的每个元素为具有出现频数、出现位置 等属性的词或短语，各属性表明该词或短语相对于整篇文档的重要性的权重。因 此，需要解决两个问题：一是提取出哪些词作为集合中的项，二是如何判断候选 项对反映文档内容的程度。前者由预处理和特征选择完成，对中文文本而言，一 般可以选择字、词或词组。根据实验结果，普遍认为选取词作为特征项要优于字 和词组。因此，要将文本表示为向量空间中的一个向量，首先要将文本分词，由 这些词作为特征向量空间的维数 1 。后者在权值调整过程中完成，常见的权值函 数包括二进制加权、词频、词频和逆文档频率之积等。 中山大学硕士论文 f 统计量在文本分类中的应用研究 3 2 文档相似度的定义 目前，大多数的文本分类算法基于v s m ，文档之间的比较实际上变成了特 征向量之间的比较。对两个向量z = ( ，x 2 ，矗) 和j ，= ( y l ，y 2 ，) ，x 和y 之 间“临近性”的度量方式有多种，普遍应用的有两种：距离函数和相似系数。 ( 1 ) 距离函数：距离较小的向量之间性质比较相近。常用的距离函数有明 考斯基距离( m i n k o w s k i ) 。上述x 和y 的明考斯基距离定义为： 1 d ( x ，y ) = ( ：。i x i m n 4 ( 3 1 ) 当q 2 l 时，公式3 - 1 变为a ( x ，y ) = ：，i 墨一y i i ，称为曼哈坦距离；q = 2 r ： 时则变为d ( x ，y ) = ：。( t 一乃) ，称为欧几里德距离。 ( 2 ) 相似系数：相似系数较大的向量之间性质比较相近。常见的如余弦相 似度和内积等。余弦相似度定义向量x 、y 的相似性为向量之间夹角的余弦： c o s ( x ，y ) = e x , + y i = l 蹄$ 余弦相似度反映了向量空间中两个向量之间夹角越小，相似度越大。 3 3 文本分类的算法评价指标 ( 3 2 ) 由于文本分类从根本上说是一个映射过程，所以评估文本分类系统的指标是 映射的准确程度和映射的速度。所有文本分类系统的目标都是使文本分类过程更 准确、更快速。映射的速度取决于映射规则的复杂程度，而评估映射准确程度的 参照物是通过专家思考判断后对文本的分类结果( 这里假设人工分类完全正确并 且排除个人思维差异的因素) ，与人工分类结果越相近，分类的准确程度就越高。 单标注分类问题( 一个测试信息样本只属于一个类) 和多标注分类问题( 一个测 试信息样本可以属于多个类) 所使用的评估参数是不一样的【。目前使用比较多 的分类性能评估指标是准确率、召回率和f 指标【1 2 】。 中山大学硕士论文f 统计量在文本分类中的应用研究 准确率( p r e c i s i o n ) 是所有自动分类的文本中与人工分类结果吻合的文本所 占的比率，召回率( r e c a l l ) 是人工分类结果应有的文本中与分类系统吻合的文 本所占的比率。若记一为类q 中分类正确的文本数，y 。为分类系统中分类为c 。的 文本数，z 为人工分类为q 的文本数，共m 个类别，则类c 的分类准确率p ，、召 回率r 分别为： 只= 土 ( 3 - 3 ) r ：兰( 3 4 ) 三， 准确率和召回率反映了分类质量的两个不同方面，二者必须综合考虑，不可 偏废。因此，存在一种新的评估指标，即f 一指标，它是准确率p 和召回率r 的函数， 其数学公式为： f ，f w l ：望竺生 ( 3 _ 5 ) f 口，p 2 2 希 3 。5 公越5 中参数是p 和r 的权重比，一般取卢- l ，且9 f p 肋= 等 另外有微平均和宏平均两种计算准确率、召回率和f 1 值的方法。微平均是 对整个文档集的平均，而宏平均是对所有类的平均。 ( 1 ) 微平均( m i c r o 平均) ：计算每一类的准确率、召b l 率和f ，值。 m i c r o p = t 2 , ， ( 3 6 ) m i c r o r = x ( 3 7 ) m i c r o 曩= 焉筹s ， 如果分类系统能将每一个测试文档分到预定g j m 个类别之中，则有 咒= 乏，1 1 4 5 时m i c r o p 、m i c r o r 、m i c r o f l 三者相等。 ( 2 ) 宏平均( m a c m 平均) ：计算全部类的准确率、召回率和f i 值的平均值。 m a c r o p 夸| m ( 3 - 9 ) 中山大学硕士论文 f 统计量在文本分类中的应用研究 m a c r o r = i 珊 ( 3 1 0 ) 葛j | m a c ，o f ：2 * m a c r o p * m a c r o r ( 3 1 1 ) m a c r o p + m a c r o r 微平均f 常常用于不同分类方法之间的比较，而宏平均f 。只在某些场合使 用。显然，微平均指标( 包括r e c a l l p r e c i s i o n f 1 ) 很受那些大类的影响，而宏平均指 标相对微平均指标而言更受小类的影响。 除了准确率和速度以外，文本分类系统还可以通过其鲁棒性、可伸缩性、可 解释性和可扩展性等进行比较。例如，鲁棒性可以体现在系统在噪声数据上的准 确性，可伸缩性可以通过计算给定分类算法在渐增的数据集上的i 0 操作次数评 估，可解释性则比较主观，但我们还是可以使用诸如结果分类法的复杂性等客观 度量。而作为一个开放的机器学习过程，一个文档分类系统应该具备功能和性能 上的可扩展性，通过不断对新的实例进行学习来改善它对新环境的预测能力，这 就要求文档分类系统建立在模块化、可扩展的体系结构基础之上。真正反映信息 分类内在特征的性能评估模型可以作为改进和完善分类系统的目标函数。 3 4 文本分类的一般流程 通常情况下，文本分类需要解决以下五个问题【1 1 ： ( 1 ) 训练语料的选取 训练信息样本选择是否合适对信息分类器的性能有较大影响。训练信息样本 集应该能够广泛地代表分类系统所要处理的客观存在的各个信息类中的样本。一 般地，训练样本集应是公认的经人工分类的语料库，从而可以比较不同分类方法 和系统的性能。 ( 2 ) 文本表示模型的建立 即选用什么样的语言要素( 或者说信息样本属性) 和用怎样的数学形式组织 这些语言要素来表征信息样本。这是信息分类中的一个重要技术问题。目前的信 息分类方法和系统都是以词或词组作为表征信息语义的语言要素，表示模型则主 要有布尔模型和矢量空间模型。 ( 3 ) 文档属性选择 信息样本的大小、结构、包含的语言元素和信息都是开放的，因此它的属性 中山大学硕士论文f 统计量在文本分类中的应用研究 也是无限制的。信息分类系统应该选择尽可能少而准确且与信息主题概念密切相 关的信息样本属性进行信息分类。选择什么样的信息样本属性由具体的度量准则 确定。 ( 4 1 选择分类方法 就是说用什么方法建立从信息样本属性到信息类别的映射关系，这是分类的 核心问题。采用什么样的分类方法，直接决定了这个系统的性能。 ( 5 ) 性能评估模型 即如何评估分类方法和系统的性能或者说分类结果。真正反映信息分类内在 特征的性能评估模型可以作为改进和完善分类系统的目标函数。在文本分类中， 应该根据具体的分类问题决定使用何种评价参数。 针对上述的五个问题，文本分类的一般流程如图3 1 所示： 图3 - 1 ：文本分类的一般流程 其中，属性选择、分类训练和测试构成了一个循环。根据测试结果，调整属 性选择和分类训练的参数，使得分类器具备最佳的分类效果。 下面简要介绍文本分类中的各个阶段中的任务。 中山大学硕士论文 f 统计量在文本分类中的应用研究 3 4 1 数据预处理 数据预处理阶段包括：中文分词、数据清理、数据集成等。 ( 1 ) 中文分词 汉语语言文字的处理与英文相比，一个明显的不同是汉语没有词与词之间的 显式分隔标记，而英文中的单词是用空白自然分割的。另外汉语的形态不丰富， 书面语言的单词基本上没有形态变化。在这种情况下，书面汉语词法分析的主要 任务不是分析单词的形态变化，而是进行单词的自动切分，将语流中一个个词分 离出来，这就是汉语分词问题。但汉语词语的划分往往存在着歧义性，同一句话 所表达的意思会因不同的切分方式而不同，分词的难点在于切分歧义。 在中文分词问题上，主要有两类解决办法：一是基于词典的分词，为此需要 建立专门的词典，采用“词典+ 匹配”的模式，但是这种方法对于词典中未登录词 ( 主要是人名、地名、机构名、新技术术语等) 的处理能力较弱；另一种是无词典 的分词，一般采用基于词汇出现频率统计技术，分析和抽取文本流中的高频词。 这两种方法各有优缺点：基于词典的方法准确性高，但是需要建立词典，且与领 域相关：基于统计的方法不用建立词典，从而与领域无关，但是精度低。目前中 科院汉语词法分析系统i c t c l a s 是使用比较多的中文分词工具，该系统的功能 主要有中文分词、词性标注、未登录词识别等，分词正确率高达9 7 咀上，未登 录词识别召回率均高于9 0 。 ( 2 ) 数据清理和集成 现实中的文本数据一般是脏的、不完整和不一致的。数据预处理技术可以改 进数据的质量，从而有助于提高以后的文本挖掘过程的精度和性能。由于高质量 的决策必然依赖于高质量的数据，从而数据预处理是文本分类过程的重要步骤。 检测数据异常、尽早地调整数据，并规约待分析的数据，将在决策过程中得到高 回报。 数据清理将清除数据中的噪声，并纠正不一致的数据。例如建立停用词表， 删除不能表达类别特征的常用词和无用词，纠正无意义的错误分词等。数据集成 则将多个数据源中的数据结合起来存放在一个一致的数据存储中。英文中单词具 有丰富的形态变化，一组不同的词可能有相同的词根。例如，d r u g ，d r u g g e d ，d r u g s ， 三者有共同的词根d r u g ，预处理阶段需要识别出这类不同形态的词，对英文文档 进行复数名词转换为单数名词及动词转换为动词原型的工作。各种语言中一词多 义、多词同义等现象普遍存在，不少词汇之间存在内在和外在的联系。对这些词 中山大学硕士论文f 统计量在文本分类中的应用研究 可以建立专门词典予以识别，或者对词典中的词进行词汇内聚和概念外延的工 作，建立关联知识库。 3 4 2 特征选择 文本分类中的一个主要挑战是高维的特征空间。文本分类所处理的数据是非 结构化或者半结构化的，特别是训练文档库比较大的时候，提取的文本特征集合 的维数通常高达数万维甚至数十万维。直觉上，特征越多，提供的信息量也越大， 这有助于提高分类算法的性能：但同时也带来了更多的嘈杂特征，放大了训练集 的噪声，呵能干扰其它更有用的特征。对于一个给定的训练集，嘈杂的特征越多， 学习算法就越难将那些能很好概括训练集的特征找到。在判定树分类算法中一些 不考虑特征属性选择的算法( 如i d 3 、c 4 5 ) 常常会构造出非常大的判定树，c 4 ，5 通过剪枝以降低分类结果为代价来减小判定树的规模。另一方面，过高的特征空 间维数给分类算法的时间和空间复杂度带来了更大的挑战。因此分类问题中一个 难点是降维，即如何从大量的属性中选择最好的属性子集用于分类学习 m 1 。 降维技术有两类：特征重构和特征选择。 ( 1 ) 特征重构。它是通过合并或转化原特征构造新特征，以此达到降维的目 的。常用的特征重构方法是隐性语义索弓l ( l a t e n ts e m a n t i ci n d e x i n g ，l s i ) 。l s i 使 用矩阵论中的统计技术奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ，s v d ) 来估计这 个结构。给定t 个词和d 个文档的词频矩阵t d ，s v d 方法删除一些行和列， 使矩阵减小为k x k 。由于l s i 忽略频率矩阵中意义最小的部分，可以使得信息 丢失最小化。 f 2 ) 特征选择。它是指去除不能表示信息的词，以提高分类效率和减少计算 复杂度。通常一些通用的、在各个类别都普遍出现的特征对文本分类的作用可能 并不大，有些会干扰分类过程的特征属于噪声：而有些只在某些特定类频繁出现 而在其他类出现比重小的特征对分类的贡献大。因此特钲选择算法对前面提取到 的文档特征集进行筛选，去除部分对类信息表现力不强的特征，筛选出对文本分 类有效的特征子集以提高分类精度和降低算法的计算复杂度。特征选择是文本分 类中最常用的降维技术。 文档特征选择的具体步骤为1 ： 1 1 使用文本特征提取方法，从训练文档库中取得所有特征集合f ： 2 ) 对f 进一步削减冗余项，得到属性集合f 1 ； 中山大学硕士论文f 统计量在文本分类中的应用研究 3 1 对集合f 1 中的每一项用某一种评估函数进行打分。例如选用信息增益方 法，则对f l 中的任意特征项j 求i g ( j ) 。当f 1 中的所有项都打分完成后，按分 值由高到低进行排序； 4 1 假设需要选取n 个分类属性，则从f 1 中的选取分值高的n 个项，构成 最终的分类属性集f s ，f s 将用于进行信息分析处理。 3 4 3 权值调整 经过特征选择后，一部分无用单词被删除，特定数量的最有用的特征得以保 留，如果此时将余下所有特征词同等对待，则不能充分发挥特征选择的优点，因 为在得到的特征子集中，各特征对分类的有用程度是不一样的。因而在特征选择 后一般会进行权值调整，即根据各词条对分类的有用程度对特征赋权，其目的是 突出重要的特征，抑制次要的特征。 权值调整的做法一般是在v s m 特征空间坐标系中引入对特征重要性的测 度。最初的测度是布尔值，即如果文本中出现了该特征，那么文本向量的该维为 l ，否则为0 。布尔函数无法体现这个特征在该文本中的作用程度，所以逐渐被 更精确的函数代替。目前常用的测度是词频。 词频分为绝对词频和相对词频：绝对词频，即用词在文本中出现的频率表示 文本：相对词频为归一化的词频，其计算方法主要运用t f i d f 公式。t f i d f 公 式主要基于两个假设【1 5 j ： ( 1 ) t f 假设：在一篇文档中出现次数多的特征的重要性不低于出现次数少的 特征： ( 2 ) i d f 假设：不常见的特征并不意味着没有常见的特征重要。 目前存在多种t f i d f 公式，本文采用了一种比较普遍的计算公式： t f i a f ( t i ，嘭) = t f ( t ，t ) 4 1 0 9 并i ，g i f 。i ) ( 3 _ 1 2 ) 舯撒枷= 胪酣瓴码戮胗。 公式3 1 2 e ? t k 表示特征词，d ，表示文档，# ( ，d j ) 表示特征在文档中出现的 次数，iii 表示训l 练集内文档总数，群。( t k ) 表示训练集中该特征至少出现过一次 的文档数。公式中t f ( t 。，d ，) 部分体现了在一个文本中出现次数很多的单词，在另 中山大学硕士论文 f 统计量在文本分类中的应用研究 一个同类文本中出现次数也会很多，币 - l o g 再等告部分则体现一个单词出现的文 本频数越小，它区别不同类别的能力就越大，所以t f - i d f 公式中t f ( t k ，d j ) 和 1 0 9 二士两个部分分别很好地体现t t f ：f h i d f 假设。 讦l t f 女j 特征词在文档中出现的位置不同，其表达主题的能力可能也有差异。如出现 在标题和摘要中的特征词可能比出现在文档中一般位置的词重要。对于w e b 网页 在 、 、 等标记内的文字也更能体现该网页的特征，因而 研究者对特征进行位置加权 1 6 j ，如给w e b 网页 、 、 和 等标记内提取出的有关文字以较高的权重等。 一般算法中特征选择和权值调