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

基于粗糙集的文本自动分类研究 摘要 随着互联网技术的迅速发展，网络已经成为人们进行信息交互和处理的有效平台，各 种以文本形式表示的信息以极高的速度增长，如何能够有效地组织和分析海量的w e b 信息 资源，使人们能够按照内容实现对文本的自动分类，帮助用户迅速地获取其所需要的知识 和信息，是计算机科学领域目前的研究热点之一，且具有广泛的应用背景和实用价值。 粗糙集理论是由波兰科学家z p a w l a k 在1 9 8 2 年提出的一种处理含糊和不精确问题 的新型数学工具。它不需要任何行先验信息，能够有效分析和处理不完备、不一致、不精 确的数据。自该理论9 0 年代被引入到机器学习、人t 智能等领域后，已经在知识获取、规 则提取、决策分析、模式识别、数据挖掘等领域获得广泛的应用。本文结合粗糙集理论对 文本分类进行了研究，主要进行了以f 工作： i 、对中文文本进行分类的一个前提条件是对中文文本进行分词处理，中文分词也是 进行中文信息处理的一个难点。针对这一现状，本文在已有的分词方法基础上， 设计了一种快速分词算法。该方法考虑到了对歧义词的处理，并将分词和特征集 缩减结合在一起，从而增强了分词准确度，减少了特征缩减过程，降低了时间复 杂度； 2 、采用了文本分类中新的特征权重算法，考虑了特征项的类内和类间分布。 3 、改进了一种粗糙集决策表的值约简算法，并将其应用到文本分类规则的提取中。 首先将每一文本的每个特征项的权值进行离散化处理，然后通过粗糙集约简提取 出文本的分类规则。其生成的规则属性较少，分类准确度较高。 关键词：文本分类、粗糙集、文本特征抽取、分词、约简算法、文本聚类 基于粗糙集的文本自动分类研究 第一章绪论 随着网络的迅速发展，越来越多的文本信息表现为电子文档的形式，面对如此庞大的 而且急剧膨胀的信息海洋，如何有效的组织和管理这些信息，并且快速、准确、全面的找 到用户所需要的信息是当前信息科学和技术领域面临的一大挑战。文本分类作为处理和组 织大量的文本数据的关键技术，能将大量的文本自动分类，可以较大程度上解决信息杂乱 的问题，方便用户准确地定位所需的信息和分流信息。因此文本自动分类作为信息处理的 关键技术，具有广泛的研究背景和现实意义。 1 1 文本分类的国内外研究现状 国外对丁文本分类的研究开展较早，5 0 年代末，h p l u h n 在这一领域进行了开创性的 研究，提出了词频统计思想用于自动分类。1 9 6 0 年，m a r o n l 2 j 发表了关于自动分类的第一 篇论文，随后，众多学者在这一领域进行了卓有成效的研究工作。到目前为止，国外的文 本挖掘研究已经从最初的可行性基础研究经历了试验性研究进入到了实用化阶段，并在邮 件分类、电子会议、信息过滤等方面取得了较为广泛的应用。下面列出了一些著名的国外 文本挖掘工具： ( 1 ) i b m 的文本智能挖掘机 i b m 的文本智能挖掘机由高级搜索引擎( a d v a n c e ds e a r c he n g i n e ) 、t e x tm i n e r 、w e b 访问工具( w e b a c c e s s t o o l s ) t l 文本分析工具( t e x t a n a 【y s i s t o o _ i s ) 组成。其主要功能是特征提 取、文档聚集、文档分类和检索，支持1 6 种语言的多种格式文本的检索，采用深层次的文 本分析和索引方法，支持全文搜索和索引搜索，搜索条件可以是自然语言和布尔逻辑条件， 是c l i e n t s e r v e r 结构，支持大量并发用户做检索任务，联机更新索引，同时义能完成其他 的搜索任务。t e x tm i l l e r 的特征抽取器主要从文档中抽取人名、组织名和地名以及由多个 字组成的复合词，也能抽取表达数字的词汇，例如：“钱”、“百分比”、“时间”等。 佗1 a u t o n o m y 公司的核心的产品是c o n c e p t a g e n t s 。在经过训练以后。它能自动从文本 中抽取概念。该产品的算法提出者是迈可林奇，他认为，按照香农的信息论，文档中除有 效概念外，还有大量的冗余信息。而词或短语是否为冗余可根据它在文档中的随机度( 概率) 来判定。如果滤除冗余，就可以从文档中自动抽取表达文档主题的概念。 林奇的技术路线是，首先对系统进行训练，处理一些文档，由使用者对非冗余概念做 出认定和识别。按照贝叶斯概率理论。这一步实际上是让系统获得关于概念的先验概率。 然后，系统根据这些概念在文档中出现的实际情况，按贝叶斯公式求出后验概率，以此作 为冗余过滤的依据。这一方法与语种无关，由于每个用户都要对系统进行个别训练，因而 系统的文本挖掘具有高度个性化的特点。 到目前为l ，包括报业巨头默多克的新闻集团在内的一批知名公司已经成为a u t o n o m y 的客户，c o m p a q 公司也已经将a u t o n o m y 的技术和产品纳入其知识管理解决方案并在客户 中推广。 基于粗糙集的文本自动分类研究 0 ) t e l t e e h 公司 提供专家服务，专业文献检索服务，产品与厂商检索服务，t e l t e e h 成功的关键是建立 了高性能的知识结构。它采用主题法，其主题词表分为不同专业，共有3 万多个，由数位 知识工程师维护，每周更新5 0 0 1 2 0 0 个词。 国内对于文本自动分类的研究起步较晚，1 9 8 1 年，侯汉清教授对于计算机在文本挖掘 工作中的应用做了探讨，并介绍了国外计算机管理分类表、计算机分类检索、计算机自动 分类、计算机编制分类表等方面的情况。此后，我国陆续研制出一批计算机辅助分类系统 和自动分类系统。表1 1 列出了国内文本挖掘方面的研究现状： 表1 1 文本挖掘国内研究现状 序号校、院、所带头人内容发表主要期刊 汉语语法分析器大规模中文文本处 1 复且大学吴立德 理9 7 翻译、汉语分词、自然语言讨论、软件学报9 7 ( 1 ) 中科院计算机语句法分析、语义分析、首字转换、中文信息学报 2言信息工程研究陈肇雄自动分词、中文文本分类特征抽2 0 0 4 - ( 0 1 ) 中心取中文信息学报 2 0 0 5 ( 0 5 ) 汉语词性标注、建立中文概率分计算机下程2 0 0 1 上海交通大学计 类的新算法 ( 0 2 ) 3 算机科学与工程陆汝占 上海交通大学学 报2 0 0 1 ( 0 9 ) 系 计算机工程与应 用2 0 0 4 ( 3 6 ) 音字转换、自动文摘、手写汉字计算机研究与发 识别、自动分词、中文词句快速展9 7 - 9 ( 5 ) 哈尔滨上业人学 王开铸 查找系统、中文自动校对系统软件学报9 8 ( 1 ) 4计算机科学与工 王小龙 计算机工程与设 程系计9 8 ( 1 9 ) 哈尔滨工业大学学 报2 0 0 1 ( 0 1 ) 2 基于粗糙集的文本自动分类研究 词性标注、继承理论( 将无限的自计算机研究与发 然语言处理转换成有限的类别处展9 7 - 9 ( 5 1 理) 、中文信息自动抽取、词类搭软件学报9 7 9 ( 3 ) 配规则、语音识别模型、文本的小型微型计算机系 姚天顺 时问信息分析( 时态逻辑) 、短语统9 7 - 9 ( 4 ) 5东北大学 结构规则自动获取方法、模糊聚东北大学学报9 7 朱靖波 类分析用于语音识别领域、语言( 1 0 ) 异化、基于神经网络的模糊知识中文信息学报 自动获取方法、英文中动词的远 2 0 0 5 t 9 ( 2 ) 程搭配、中文姓名识别、汉语文 本自动分类模型设计与实现 自动标注汉语词类( 神经网络模计算机工程与应 北京邮电人学信型) 、自动文摘( 文摘语文本结构关用2 0 0 1 1 9 ( 4 ) 6钟义信 息工程系系) 、提出了基于言语行为理论的计算机科学 话语分析方法 2 0 0 2 2 9 ( 7 ) 汉语基本名次短语分析模型、识计算机学报9 9 ( 2 ) 精华大学计算机黄昌宁 别模型、文本词语标注、语言建清华大学学报 7模、分词歧义算法、上f 文无关 2 0 0 1 - 4 l ( 7 ) 技术与科学系陆玉昌 分析、语素和构词研究计算机世界报 2 0 0 2 ( 2 4 ) 1 2 本文的主要研究内容 本文主要完成以下几个方面的工作： ( 1 ) 对中文文本进行分析的一个前提条件是对中文文本进行分词处理，中文分词也是 进行中文信息处理的一个难点。针对这一现状，本文在深入分析以前的分词方法基础上， 设计了一种快速分词算法。该方法将常用静态词典分为停用词和非停用词两类词，在建立 词典时，将是否是停用词作为词的一个特眭。分词的过程考虑了对歧义词的处理，增加了 分词的准确度。另外，在分词的同时根据词的类别将对分类没有意义的停用词去掉，大大 降低了特征维数。这种分词算法将分词和特征集缩减结合在一起，从而减少了特征缩减过 程而使时间复杂度大大降低。 ( 2 ) 针对传统权重算法的不足，采用了一种新的权值计算公式，传统t f i d f 公式是 将文档集作为雅体来考虑，特别是其中i d f 的计算，并没有考虑到了特征项在类间和类内 的分布情况。如果某一特征项在某个类别大量山现，而在其它类别很少出现，这样的特征 项的分类能力显然是很强；另一方面，类内分布相对均匀的特征项的权重应该比分布不均 匀的要高。因此在传统t f - i d f 的基础上，结合分布信息d i 进行联合加权，从而使特征项 的选择更有代表性。 ( 3 ) 对一种粗糙集值约简算法进行了改进，并且将该算法应用到文本分类。该方法 可以自动提取分类规则，比人工建立规则库容易实现得多。在基于粗糙集理论的文本分类 3 一一 苎王望墼壅竺壅查鱼垫坌壅型茎一 甭耳i 鬲：将文本特征项的权值作为规则的条件属性，文本所属的类别用作决策属性，构造 决策信息表。首先将每一文本的每个特征项的权值进行离散化处理，然后通过约简算法提 取出文本的分类规则。文本的评价方法采用了查准率、查全率和f 1 测试值实践证明， 该方法生成的规则易于理解，属性值较少，分类的准确度和速度都有一定的提高 4 基于粗糙集的文本自动分类研究 2 1 文本分类的概述 2 1 1 文本挖掘的定义 第二章文本分类和粗糙集 文本挖掘( t e x tm i n i n g ，简称t m ) 是信息挖掘的一个分支，用于基于文本信息的知识发 现。一般来说，文本挖掘和文本数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nt e x t u a l d a t a b a s e ，简称k d d 被认为是具有相同含义舸两个词，最早由r o n e n f e l d m a n 等人提出”j ： “t h ep r o c e s so fe x l t a c t i n g i n t e r e s t i n gp a t t e m sf r o mv e r yl a r g et e x tc o l l e c t i o n s f o rt h e p u r p o s eo f d i s c o v e r i n gk n o w l e d g e n ” 其含义为：文本挖掘即文本数据库中的知识发现，是从大量文本的集合或语料库中发 现隐含的，令人感兴趣的，有潜在使用价值的模式和知识。 文本挖掘是利用智能算法，如神经网络。粗糙集，知识网格，基于案例的推理，可能 性推理等并结合文字处理技术，分析大量的非结构化文本源( 如文档，电子表格，客户电子 邮件，问题查询，网页等) ，抽取或标记关键字概念，文字间的关系，并按照内容对文档进 行分类，获取有用的知识和信息。文本挖掘是分析和发现人量非结构化文本中的关系。由 于文本信息源的特殊性，使得现有的数据挖掘技术无法直接得到应用，所以需要对文本进 行特征表示和预处理，抽取其元数据。文本挖掘的关键在于文本内容的量化表征。 从文本挖掘的定义可以看出，文本挖掘就是从文本或文本集合中提取有用知识的过程， 而知识的表达方式是多种多样的，例如，可以是概念( c o n c e p 0 ，规贝j j ( r u l e ) ，规律( r e g u l a r i t y ) ， 模式( p a t t e r n ) 或者约束( c o n s t r a i n t ) 等。 2 1 2 文本挖掘的过程 文本数据挖掘的一般处理过程可以用图2 1 米概括描述。首先选取待处理和分析的文 本，对挖掘的文本进行分词处理，把文本切分成特征词条，建立挖掘对象的特征表示。特 征表示一般采用文档特征向量。但是分词后的初始特征向量具有惊人的维数，因而特征向 量的缩减处理成为文本挖掘处理过程中一个必不可少的环节。在完成特征向量维数的缩减 后，确定应用范围，包括收集应用所涉及领域内的背景知识，理解应用要求并且确定应用 所要达到的目标，便可以利用机器学习的方法来提取面向特定应用目的的知识模式。最后 对获取的知识模型进行质量评价。若评价的结果满足一定的要求，则存储该知识模式，否 则返回到以前的某个环节分析改进后进行新一轮的挖掘上作。 基于粗糙集的文本自动分类研究 图2 ，l 文本挖掘的过程 根据挖掘山的知识类型不同，可以把文本挖掘任务分为以下几类： 文本分类( t e x tc l a s s i f i c a t i o n ) ，聚类分析( c l u s t e r i n ga n a l y s i s ) ，关联规则( a s s o c i a t i o n r u l e ) ，文本总结( t e x ts u m m a r i z a t i o n ) ，趋势预测( t r e n dp r e d i c t i o n ) 等。 2 1 3 文本分类 文本分类是指根据带有类别的文本集合的特点，根据每一个类别的文本子集合的共有 特点，找出一个分类函数或分类模型( 分类器) ，根据该模型可以把其他文本映射到已有类 别中的一个，从而实现自动对文本分类。这样，用户不但能够方便地浏览文档，而且可以 通过限制搜索范围来使文档的查找更为容易。y a h o o ，s o h u 等搜索引擎都是利用文本分类 技术对大量文档进行快速有效地自动分类。 2 2 文档自动分类算法 2 2 1 文档自动分类算法的分类 目前，已有的主要文档自动分类算法可以分为三类： ( 1 ) 词匹配法。词匹配法又可以分为简单词匹配法和基丁同义词的词匹配法两种。简单 词匹配法是最简单、最直观的文档分类算法，它根据文档和类名中共同出现的词决定文档 属于哪些类。显然，这种算法的分类规则过于简单，分类效果也很差。基于同义词的词匹 配法是对简单词匹配法的改进，它先定义一张同义词表，然后根据文档和类名以及类的描 述中共同出现的词( 含同义词) 决定文档属于哪些类。这种分类算法扩大了词的匹配范围， 在性能上要优于简单词匹配法。不过，这种算法的分类规则仍然根机械，而且同义词表的 构成是静态的，对文档的上r 文不敏感，无法正确处理文档中其具体含义依赖于上下文的 词，分类的准确度也很低。 ( 2 ) 基于知识工程的方法。基于知识工程的文档分类方法，需要知识t 程师手丁地编制 大量的推理规则，这些规则通常面向具体的领域，当处理不同领域的分类问题时，需要不 同领域的专家制定不同的推理规则，而且分类质量严重依赖于推理规则的质量。因此，在 实际的分类系统中较少使用基于知识工程的学习法。 ( 3 ) 统计学习法。统计学习法和词匹配法在分类机制上有着本质的不同。它的基本思路 6 基于粗糙集的文本自动分类研究 是先收集一些与待分类文档同处一个领域的文档作为训练集，并由专家进行人工分类，保 证分类的准确性，然后分析这些已经分好类的文档，从中挖掘关键词和类之间的联系，最 后再利用这些学到的知识对文档分类，而不是机械地按词进行匹配。因此，这种方法通常 忽略文档的语言学结构，而用关键词来表示文档，通过有指导的机器学习来训练分类器， 最后利用训练过的分类器来对待分类的文档进行分类。这种基于统计的经验学习法由于具 有较好的理论基础、简单的实现机制、以及较好的文档分类质量等优点，目前实用的分类 系统基本上都是采用这种分类方法。 图2 2 文档自动分类算法的分类 2 2 2 实现中文文本自动分类的般过程 在应用基于案例的有指导的机器学习方法中实现文本自动分类的过程有一个基本的假 设：文档的内容与其中所包含的词之间有着必然的联系，同一类的文档之间总存在多个共 同的词，而不同类的文档所包含的词之间差异很大。因此，分类器的训练过程可以看作是 在已知文档类别的情况下，统计不同类别内的词的分布，即在预先定义的类别集合c ( c = c 1 ，c k ，c 。) ) 与词项集合t ( t = t i ，t b ，t ) ) 的幂集之间建立一种加权的 映射关系，形成一种向量表示；相应的，分类器的分类过程，可以看作在已知一篇文档内 所包含词的分布( 用一个向量表示) 情况卜- ，和在训练中形成的每个类别的向鼍表示进行 对比，来确定该文档与类别之间的隶属关系。 同普通英文文档相比，中文文本信息具有自身的特性：中文文本的内容使用中文书 写，不像英文单词之间存在自然的形态间隔，因此为了对中文文本进行有效地处理，首先 需要进行分词处理，而且分词的效果将显著地影响分类效果。 结合中文文本的特性，图2 3 给出了实现中文文本自动分类的一般过程。其中预处理 包括分词以及副词、助词等虚词的处理。 7 基于粗糙集的文本自动分类研究 图2 3 文本分类系统过程 2 2 3 中文文本自动分类的关键技术 从图2 3 所示的中文文本分类器的_ 下作原理图可以看出，为了实现中文文本的自动分 类，通常需要关注训练分类器使用的训练样本集、特征选敬算法、分类算法、分类系统的 性能评价值指标等方面的问题。 ( 1 ) 训练样本集 为了评价各种文档自动分类算法的优劣，推进信息检索领域的发展，由美国国家标准 和技术研究院( n i s t ) 、信息技术实验室( i t l ) 检索小组、美国国防部高级研究计划署 ( d a r p a ) 信息技术处、高级研究开发机构( a r a d a ) 等单位共同发起了有全球影响的文 档检索会议( t r e c ) 。从1 9 9 2 年起，每年一次，t r e c 会议实际上是文本信息检索系统的 擂台赛，可以说，在t r e c 上展示的文本分类系统代表了文本分类领域的最新研究成果。 一些大学，如c v l u 、b e p d r , l l e y 、c o r n e l l 等和一些公司带着自己开发的文本分类系统 参加会议，由大会使用相同的训练集和测试集对这些系统进行评测。中国科学院计算所、 清华大学等单位近几年也有派队参加，并取得了不错的成绩。也逐步开始提供标准的英文 网页语料米评测w e b 信息检索系统。 与面向英文的分类系统相比，中文分类系统的起步比较晚。从第五次t r e c 会议开始， 增加了对中文分类系统的评测。实际上参加t r e c 2 5 的中文分类系统处理的重点还停留在中 文的分词问题上，而且处理的对象还是新华社的新闻稿这类普通的中文文本。基于案例的 有指导的机器学习方法是实现中文文本自动分类的理论基础。因此，中文文本训练集是实 现中文文本自动分类的前提条件。 基于粗糙集的文本自动分类研究 ( 2 ) 特征选取算法 实现文本自动分类的基本困难之一是特征项空间的维数过高。所谓“特征项”，在中 文文本中主要指分词处理后得到的词汇，而特征项的维数则对应不同词汇的个数。数量过 大的特征项一方面导致分类算法的代价过高，另一方面导致无法准确地提取文档的类别信 息，造成分类效果不佳。因此，需要在不牺牲分类质量的前提下尽可能地降低特征项空间 的维数。“特征选取”的任务就是要将信息量小，“不重要”的词汇从特征项空间中删除， 从而减少特征项的个数，它是文本自动分类系统中的一个关键步骤。 为便于后面的描述，这里简要给出特征选取的一般过程。给定训练文档集合d o c s = d l ，”，d ) ，设t e r m s = t 1 ，t 2 ，t m ) 为对d o c s 中的文档做分词后得到的词汇全集，用 m 表示集合( 1 ，2 ，m ) 。所谓“特征选取”可以看成是确定从t e r m s 到 的一个卜1 映射， 即 f - s e l e c t i o n ：t e r m s - - ) m 然后根据计算开销的考虑，取一个i m ，认为t e r m s 中那些函数值不小丁i 的词汇为“选 取的特征项”，记作t e r m s 。 在完成了特征选取后，分类就是基于t e p d s 。，即以其中的元素为基础，用一个向量来 表达每一个文档。分类的过程就是按照某种算法来比较待分类文档的表示向量和训练集文 档的表示向量，取最相近者所处于的类为待分类文档的类。 人们已经研究了多种特征选取方法，如：文档频率( d o c u m e n t f r e q u e n c y ，d f ) 、信息 增益( i n f o r m a t i o ng a i n ，i g ) 、互信息( m u t u a li n f o r m a t i o n ，m i ) 、开方拟和检验( x2 t e s t ， c l i i ) 、术语强度( t e r ms t r e n g t h ，t s ) 等。实验结果表明：c h i 和i g 方法的效果最佳：d f 方法的性能同i g 和c h i 的性能大体相当，而且d f 方法还具有实现简单、算法复杂度低等 优点；t s 方法性能一般；m i 方法的性能最差。 ( 3 ) 分类算法 本文的第2 2 1 。1 ，介绍了各种文档自动分类算法的分类。r 面对几个比较典型的分类 算法进行具体的介绍。 ik n n 算法 k n n 分类算法是一种传统的基于统计的模式识别方法。算法思想很简单：对于一篇 = 待分类文档z ，系统在训练集中找到k 个最相近的邻居，使用这k 个邻居的类别为该文档 的候选类别。该文档与k 个邻居之间的相似度按类别分别求和，减去一个预先得到的截尾 闽值，就得到该文档的类别测度。用k n n 也表示所选k 个晟相近文档的集合，公式( 2 4 ) 刻画了上述思想”。 其中 y ( z ，c ，) = s 砌( 牙，z ) ) ，( 孑。，c ，) 一b ( 2 4 ) ie 删 9 基于粗糙集的文本自动分类研究 牙为一篇待分类网页的向量表示；孑为训练集中的一篇实例网页的向量表示：c j 为一 类别： y ( 乏，c ，) ( 0 , 1 1 ( 当孑属于c ，时取1 ：当孑不属于c - 时取o ) ；b j 为预先计算得到的 c 。的最优截尾阈值： s i r e ( 2 ，孑。) 为待分类网页与网页实例之间的相似度，由公式( 2 5 ) 计算得到： c 0 8 x , 如2 晶 ( 2 5 ) k n n 算法本身简单有效，它是一种l a z y - - l e a r n i n g 算法，分类器不需要使用训练集进 j q i l l 练，训练时间复杂度为0 。k n n 分类的计算复杂度和i ) l l 练集中的文档数目成正比，也就 是说，如果训练集中文档总数为n ，那么k n n 的分类时间复杂度为0 ( n ) 。 i in b ( n a i v eb a y e s ) 算法 n b 算法是基于贝叶斯全概率公式的一种分类算法。贝叶斯全概率公式的定义如公式 ( 2 - 6 ) 所示。 刑阱警 ( 2 - 6 ) 给定一个类口以及文档d ( a 。，a 2 ，a 。) ，其中a 。表示文档中出现的第i 个特征项 r l 为文档中出现的特征项的总数。根据全概率公式，可以得到公式( 2 7 ) ： p ( c i d ) = p ( d i c ) ，( c ) p ( a lc ) + 尸( 2c ) e ( a 。jc ) + p ( c ) 一 p ( d )p ( d ) ( 2 7 ) 其中：p ( cd ) 表示文档d 属于类别c 的概率：p ( c ) 表示待分类的文档所处的领域中， 文档属于这个类的概率。在具体的计算时，可以分别用训练集中属于这个类的文档所占的 比例代替；p ( a 。i c ) 表示在类别c 中特征项a ：出现的概率。可以近似地用特征项在训练集中 所有属丁：这个类的文档中的出现次数与训练集中该类别的文档总数之比值表示。 由此可以看出，n b 算法假设文档之间的特征项都是相互独立的。但是，这一假设对语 义丰富的语言文字信息往往过丁简单，这也崔一定程度上限制了算法的性能。 n b 算法需要使用训练集对分类器进行训练，也就是需要分别计算每个p ( a 。i c ) 。假设训 练集共有m 个类别，n 个特征项，待分类文档共有k 个特征项，那么训练的时间复杂度为 o ( m n ) 。分类的时间复杂度为o ( k ) 。 1 0 基于粗糙集的文本自动分类研究 决策树( d t r e e ，d e c i s i o nt r e e ) 算法 决策树算法通过对训练数据的学习，总结出一般化的规则，然后再利用这些规则解决 问题。用决策树进行文档分类的基本思路是这样的；先用训练集为预先定义的每一个类构 造一棵决策树，构造方法如下： 以训练集作为树的根结点，它表示所有的训练文档，将它标记为“未被检测”。 找到一个标记为“未被检测”的叶结点，如果它表示的所有文档都属于这个类，或 者都不属于这个类，将这个叶结点的标记改为“已被检测”，然后直接跳到第三步；否则， 挑选当前最能区分这个结点表示的文档集中属于这个类的文档和不属于这个类的文档的特 征项作为这个结点的属性值，然后以这个结点为父结点，增添两个新的叶结点，都标记为 “未被检测”，父结点表示的训练文档集中含有这个特征项的所有文档用左子结点表示，所 有不含有这个特征项的文档用右子结点表示。 重复第二步操作，直到所有的叶结点都被检洌4 过。 对每棵决策树，从它的根结点开始，判断结点的属性值( 特征项) 是否在待分类的文 档中出现，如果出现，则沿着左子树向下走；否则沿着右子树向下，再继续判断当前结点 的属性值是否在待分类的文档中出现，直到到达决策树的某个叶结点，如果这个叶结点表 示的训练文档都属丁这个类，则判定这篇待分类的文档也属丁- 这个类；反之亦然。 1 vr o c c h i o 算法 r o c c h i o 算法的基本思想是使用训练集为每个类构造一个原型向量，构造方法如下： 给定一个类，训练集中所有属于这个类的文档对应向量的分量用正数表示，所有不属于这 个类的文档对应向量的分量用负数表示，然后把所有的向量加起来，得到的和向量就是这 个类的原型向量，定义两个向量的相似度为这两个向量夹角的余弦。逐一计算训练集中所 有文档和原型向量的相似度，然后按一定的算法从中挑选某个相似度作为界。给定一篇文 档，如果这篇文档与原型向量的相似度比较人，则这篇文档属于这个类，否则这篇文档就 不属于这个类。r o c c h i o 算法的突出优点是容易实现，计算( 训练和分类) 特别简单，它 通常用来实现衡量分类系统性能的基准系统，而实用的分类系统很少采用这种算法解决具 体的分类问题。 文献 1 6 比较研究了支持向量机s v m 、k n n 、n b 、l i n e a rl e a s ts q u a r e sf i t s ( l l s f ) 和n e u r a ln e t w o r k ( n n e t ) 算法。研究结果表明，当训练集中每个类的正面实例比较少( 少 于1 0 个) 的情况下，s v m 、k n n 、l l s f 的性能明显优于n n e t 和n b 算法。 ( 4 ) 分类系统的性能评价指标 在信息检索领域，通常采用表2 - 1 来定义查准率和查全率”，人们通常借鉴这些标准 来评价分类系统的优劣。 基于粗糙集的文本自动分类研究 表2 1 信息检索系统的评价标准 与检索相关的文档与检索不相关的文档 实际上作为结果集返回 ab 的文档 实际上未返回的文档 d 其中，a 表示根据检索条件，检索系统返回的符合检索意图的文档个数：b 表示根据检 索条件，检索系统返同的不符合检索意图的文档个数；c 表示文档集中包括的本来符合检 索意图，但是未能被检索系统返同的文档个数：d 表示文档集中包括的不符合检索意图， 也没有被检索系统返回的文档个数。 疗 查准率口= 二 ( 2 - 8 ) 1 口+ b 一 查全率，= ( 2 - 9 ) 口+ c 从公式( 2 8 ) 的定义可以看出，查准率表示在所有被检索出的文档结果集中，真正符 合检索意图的文档所占的比率，它体现了系统检索结果的准确程度。从公式( 2 - 9 ) 的定义 可以看出，查全率表示被检索出的文档结果中真正符合检索意图的文档数在所有符合检索 意图的文档集中所占的比率，它体现了系统检索所有相关文档的完备性。查准率和查全率 这两个标准是互补的，单纯提高查准率就会导致查全率的降低，反之亦然。因此，尽管一 个好的检索系统应该同时具有较高的查准率和较高的查全率，但是实际的检索系统往往需 要在两者之间做出一些折衷，而不至于其中个指标过低。 为方便起见，人们还定义了一个f - 值“”，以图反映查准率和查全率的综合效果，其定 义如公式( 2 10 ) 所示。 鼻：望( 2 - 1 0 ) p + ， 其中：p 为查准率；r 为查全率。 对于f 1 值t 从公式( 2 1 0 ) 可以看出，它反映了查准率p 和查全率r 之间的平衡关系： 只有当p 和r 比较接近，并且取值都比较大时，f 1 才比较大。反之，当p 和r 相差比较悬 殊，或者取值都比较小时，f l 值就比较小。所以，f l 综合反映了分类器的整体性能。 2 3 聚类分析 聚类分析是指将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能地大， 而不同簇间的相似度尽可能地小，从而发现整个文本集合的整体分布特点。它与分类的不 同之处在于，聚类没有预先定义好的主题类别。h e a r s t 等人的研究己经证明了“聚类假设”， 即与用户查询相关的文档通常会聚类的比较靠近，而远离与用户查询不相关的文档“1 。因 此，我们可以利用文本聚类技术将搜索引擎的检索结果划分为若干个簇，用户只需要考虑 1 2 苎量塑墼叁塑苎查鱼垫坌鲞竺塑 那些相关的簇，大大缩小了所需要浏览的结果数量。目前，有多种文本聚类算法，大致可 分为两种类型：以h a c 等算法为代表的层次聚类法”1 ，以k - m e a n s 等算法为代表的平面划 分法，文献“”介绍了将h a c 和k - m e a n s 算法结合起来的b u e h s h o t 方法和f r a c t i o n a t i o n 方 法。 分类和聚类早在数据挖掘和文本挖掘兴起之前，在统计学、机器学习和模式识别等领 域中己得到较深入的研究。在数据挖掘和文本挖掘技术兴起之后，它们又得到进一步的研 究，以适应数据挖掘和文本挖掘应_ h j 的需要。在机器学习中，它们分别属于有教师学习和 无教师学习两个类别，而关联规则是从数据挖掘领域中新提出的一种技术。在文本挖掘中 也得到广泛研究和应用。另外，值得一提的是，给定一个文本集合，从中可以发现的知识 类型不是唯一的，往往其中隐藏着多种知识类型。各种技术也不是绝对相互独立的，若能 综合运用各种技术，或者将发现知识的技术很好地集成在一起，就可能高效地尽可能多地 发现潜在的有用知识。 2 4 租糙集理论 粗糙集理论是一种新的处理模糊和不确定性知识的数学丁具，其主要思想就是在保持 分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。目前，粗糙集已经 被成功地运用于机器学习、决策分析、过程控制、模式识别与数据挖掘、文本挖掘等领域， 本章介绍标准粗糙集理论( p a w l a k 粗糙集) 的基本概念，作为后续章节的基础。 2 4 1 粗糙集理论的基奉概念 粗糙集理论假定知识是一种对对象进行分类的能力，这里的“对象”是指我们所能言 及的任何事物，比如实物、状态、抽象概念、过程和时刻等等。也就是说，知识必须与具 体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定部分称之为论域 ( u n i v e r s e ) ，简称为域。对于论域及知识的特性并没有任何特别假设，事实上，知识构成了 某一感兴趣领域中各种分类模式的一个族集( f a m i l y ) ，这个族集提供了关于现实的显事实， 以及能够从这些显事实中推导出隐事实的推理能力。 为数学处理方便，在下面定义中用等价关系来表示分类，详细内容可参看”1 。 定义2 1 一个知识库( k n o w l e d g eb a s e ) 可以表示为一个关系系统 x = 亿，置j ( 2 - 1 1 ) 其中u 是非空有限对象集合，称为论域( u n i v e r s e ) ；r 为u 上的等价关系集。 定义2 2 设p c r ，且p 西，则p 中所有等价关系的交集称为u 上的一种不可区分 关系( i n d i s c e m i b i l i t yr e l a t i o n ) ，记作i n d ( p ) ，即 冈。= n 工k r e p 其中， x k 表示关系r 中包含元素x u 的等价类。 1 3 ( 2 - 1 2 ) 基于粗糙集的文本自动分类研究 定义2 3 设集合z u 为域的任一子集( 概念) ，r 是u 上的等价关系，则称 星x = 工u ：【z 】r j ) l y = x u ：瞳】r n x ) ( 2 - 1 3 ) 佗- 1 4 ) 分别称为x 的r 一下近似( 1 0 w e ra p p r o x i m a t i o n ) 和x 的r 一上近似( u p p e r a p p r o x i m a t i o n ) 而b n r ( x ) = 面一_ r x 则称为x 的矗一边界区域( b o u n d a l yr e g i o n ) 。 如果b n r ( j ) 妒，即r x ，意味着工不能通过月的等价类精确地刻画，即x 不能用现有的知识( 或关系) 进行完全的表示，称x 为粗糙i 拘( r o u g h ) ：反之称z 为精确 的( e d s p ) 。墼包含了所有使用知识r 可确切分类到x 中的元素，r x 包含了所有那些可 能是属于x 的元素，而b n r ( x ) 则由不能肯定分类到z 或其补集中的元素组成。 倒2 1 给定u = ( 1 ，2 , 3 456 ，7 ，8 上的等价关系r = ( 1 ，2 ， 3 ，4 ， 5 ，6 ， 7 ，8 ) ) ，根据 当前的知识，我们有组元1 和组元2 相x c t - r 来讲是不可区分的，且有 1 k = 2 k = 1 ，2 ) ； 其他等价类如同。 给定域的一个子集x = i 357 ，我们可以求出r ( x ) = i ，2 ，3 ，4 ，5 ，6 ，7 8 = u ，而 星( x ) = ，我们可以知道x 中并没有任何元素可以肯定在其中，而从集合论的观点看， 1 x ，为什么反而说组元1 不可以肯定是z 中的元素呢? 我们可以这样解释这个问题： 我们只知道域u 上的等价关系r ，如在此例中，r = e l ，e 2 ，e 3 ，e 4 ，对其中每一 个等价类我们知道其描述分别为e ，f = 1 , 2 ，3 ，4 。而对于每一个体而言，我们并不知其描述 方式。因此，由堡( 石) = 矿我们只能得出上述结论，这一点与模糊集中的元素隶属方式不 太一样，因为粗糙集解决的是分类问题，而非元素与集合的隶属问题。 在粗糙集理论中，概念( 域的子集) 的不确定性是由于边界区域的存在而引起的。集 合的边界区域越人，其精确性越低。为了更精确地表示这一点。下面引入不精确性的度量。 定义2 4 由等价关系r 定义的非空集合x u 的近似精度为 1 4 基于粗糙集的文本自动分类研究 州耻篇 其中l x l 表示集合石的势( c a r d m l h y ) 。 ( 2 - 1 5 ) 由于夏置2 ，f l j f l ：o 口。( j ，) l 。根据近似精度，我们可以从量化的角度来定 义概念x 是否为精确的。 当口r ( ) = 1 时，概念z 是精确的，因为r x = _ z x 等i r x i 爿i ： 当0 口。( ) 1 时，概念x 是粗糙的。 知识约筒是粗糙集理论的核心内容之。众所周知，知识库中的知识并不是同等重要 的，基于某些知识是冗余的。所谓的知识约简，就是知识库分类能力保持不变的条件f ， 删除其中不相关或不重要的知识。 知识约简有两个基本概念：约简( r e d u c t ) 和核( c o 哟。直观地讲，所谓知识的约简就是 指知识的本质部分，它足以定义所考虑的知识中所遇到的所有基本概念，而核是其最重要 的部分。 定义2 5 设且是u 上的等价关系族，且r r ，若n d 纽j = n d ( 矗一 r ) ) ，称其 是r 中可缺省的( d i s p e n s a b l e ) ，否则是不可缺省的。如果置中的所有关系均是不可缺省的， 称r 是独立的( i n d e p e n d e n t ) ，否则称其是依赖的或是非独立的。 定义2 6 设q p 是独立的，并且n d ( q ) = i n d ( p ) ，称q 是关系族集p 的一个 约简。在族集p 中所有不可缺省的关系构成的集合称为p 的核，以c o r e ( p ) 表示，即 c o r e ( p ) ： p p li n d ( p ) i n d ( p 一 p ) ) ) 定理2 7 族集p 的核等于它的所有约简的交集，即 c o r e ( p ) = n r e d ( p ) ( 2 1 6 ) 其中，r e d ( p ) 是p 的所有约简的族集。 从定理2 7 中可以看出，核的概念有的两方面意义：其一，可以作为计算所有约简的 基础，因为核包含于每一个约简中，并且其计算是直接的；其二，核可以解释为知识最重 要部分的集合，进行知识约简时不能删除它。 在实际应用中，一个分类相对于另一个分类的关系十分重要，因此引入知识的相对约 简( r e l a t i v er e d u c t ) 和相对核( r e l a t i v ec o r e ) 的概念，首先需要定义一个分类关于另一个分类的 正区域( p o s i t i v er e g i o n ) 。 1 5 苎王塑塑叁堕奎查皂垫坌塑垄 定义2 0 设p 和q 是全域u 上的等价关系，所谓q 的p 一正区域，记为p o s p q ， 定义为： p o s p a = x o o ( m ( 2 - 1 7 ) 其中，u q 表示q 在u 上的所有等价关系构成的集合。q 的尸一正区域是全域上的 那些使用分类u p 所表达的知识，这些知识能够止确地分类于u o 的等价类之间的对象 的集合。 定义2 9 设p 和q 是全域u 上的等价关系的族集，且有p p ，若 p o s m d ( p ) 1 n d ( q ) = p o s 衄( p 删) i n d ( q ) ( 2 _ 1 8 ) 则称关系p 在族集p 中是q 一可缺省的，否则称为q 一不可缺省的：如果关系族集p 中的每个关系都是q 一不可缺省的，则称p 是q 一独立的，否则就称为依赖的。为方便起 见，一般用符号p o s ，q 代替p o s i n d ( q ) a 定义2 1 0r 量p 称为p 的q 约简，记为r e d q p ，当且仅当r 是满足性质 p o s p q = p o s r q 的最小子集，即 ( 1 ) p o s p q = p o s r q ； ( 2 ) v s c r ，p o s p q p o s s q ： 族集p 中的所有q 不可缺省的关系的集合，称为p 的q 核，记为c o r e o p a 定义2 1 1 设世= ( u ，r ) 是一知识库，p ，q r ，我们称知识q 以依赖度k 依赖于知 识p ，记作p j t q ，当且仅当 砷p q _ 并 ( 2 _ 1 9 ) 在粗糙集理论中，知识是用信息系统表示的。信息系统可以简单地看成是一张数据表， 基于租糙集的文本自动分类研究 表中的行对应研究的对象，或称为组元，列对应于对象的属性，对象的信息是通过指定对 象的各属性值米表示的。如果信息系统中的属性进一步分成为条件属性和决策属性，则该 信息系统称为决策表，下面给出信息系统的形式化定义。 定义2 1 2 个系统s 可以表示为一个四元组 s = ，a ，v ，) ( 2 - 2 0 ) 其中，u 是对象的集合，即论域；a 是属性的集合；v = u 。圪，v a 表示属性口的 值域；厂：u x a v 是一个信息函数，它指定域中某一具体对象z 在属性口上的取值，即 v x u ，口a ，f ( x ，) 圪a 如果属性集彳可以分为两个互不相交的集合c 与d 的并集，即a = c u d ，且 c n d 中，则称此信息系统为决策系统或决策表，其中d 通常仅含有一个属性，称为单 决策信息系统。 容易看出，一个属性对应一个等价关系，个数据表可以看作是定义的族等价关系， 即知识库。前面所讨论的问题都可以用一种新的语言来表示，即属性一属性值对米表示， 知识的约简可以转化为属性约简。 对一个决策系统，c 中的各个属性之间往往存在某种程度的关联或依赖，相对于属性 集d 来说某些属性可能是冗余的。求属性的约简就是用最简单条件属性集代替原来的条件 属性集，而仍能根据剩下的条件属性判断山决策属性，不丢失决策系统的任何信息。 设p 和q 是全域u 上的等价关系的族集，所谓的9 的p 正区域，记作p o s ，( q ) ， 定义为：p o s ，( 9 = u p _ ( x ) ，x u q 。它是全域u 上的所有那些使用分类u p 表达的知识能够正确地分类于u q 的等价类的个体的集合。 c 称为c