（计算机应用技术专业论文）基于rough+set理论的文本分类器研究.pdf

硕士学位论文 摘要 摘要 本文选择了信息检索领域的关键问题文本分类作为研究对象。将文本分类操作 的分类算法和怎样将r o u g hs e t 理论应用于分类操作作为研究重点。 由于r o u g hs e t 理论是一种较新的软计算方法，可以有效地分析和处理不完备 信息。在许多科学与工程领域得到成功的应用，但是在信息检索领域的应用研究相 对较少。所以本文将怎样把r o u g hs e t 理论应用于文本分类模型这个典型问题作为 研究的重点。研究分析了r o u g hs e t 理论应用于文本操作的现状、论述了r o u g hs e t 理论应用的优势以及局限性和文本操作所面临的困难。本文的一个基本观点是“不 完备和不一致的文本信息系统的“规则”是不可靠的”。所以应用r o u g hs e t 理论的 重点不从“属性约简”、“规则提取”的角度的进行。 本文提出一种新的训练模型，即将训练预分类标准和关键字出现视为不可分关 系，形成确定的知识，同时又将其视为不确定的知识。并以此作为粗糙操作的基础。 给出了基于r o u g hs e t 理论的文本训练类别和特征关键字在给定文本集合中的关联 关系的研究结果。即从集合的角度总结出由特征引起的集合与由训练类别引起的集 合之间存在的几种典型关系，以及在粗糙集模型下的相应结论。解决了关键字描述 能力和分类能力的表达问题，内容还涉及退化、约简等内容。最后，提出一种基于 r o u g hs e t 理论的单分类器模型算法。它从r o u g hs e t 理论的知识近似表示、表示精 度及集合计算操作的角度进行应用。该方法提出“将文本训练过程视为经典粗糙集， 将测试过程视为模糊集”的思想，通过特征与类别之间在r o u g hs e t 模型下的关联关 系设计出单分类器的算法，并将粗糙精度的概念引入具体计算过程。算法解决了结 果精确隶属的问题，可以被用于多重分类问题。然后针对应用过程中产生的退化问 题设计出双向近似的单文本分类器的算法。该算法同时实现了属性的自然约简。通 过实验证明以上算法是算法简单、有效。 另外，本文还将容差r o u g hs e t 理论应用于文本分类，提出一种基于容差r o u g h s e t 理论的多文本分类器模型算法。它从r o u g hs e t 理论的关系定义及上近似和下近 似含义扩展的角度进行应用。该模型将上近似理解为概念在语义上的扩展，而将下 近似理解为概念的核。并且将该思想应用于文本简单分类法。 关键字：r o u g h s e t ；分类模型：容差关系：模糊集：双向近似 硕士学位论文 a b s t r a c t a b s t r a c t t h ep a p e rt a k e st e x tc a t e g o r i z a t i o ni n f i e l do fi n f o r m a t i o nr e t r i e v ea so b j e c tt ob e s t u d i e d t h e r ea r et w ok e yp o i n t so n ei st h em e t h o d so ft e x tc a t e g o r i z a t i o nt h eo t h e ri st h a t h o wt op u tt h e o r yo fr o u g hs e ti n t oa p p l i c a t i o n si na u t oc l a s s i f i c a t i o n s t h e o r yo fr o u g hs e ti san e wm a t h e m a t i c a lt 0 0 1 b e c a u s ei ti sg o o da td e a l i n gw i t h i n c o m p l e t ei n f o r m a t i o ns y s t e m si ti su s e di nm a n yf i e l d ss u c c e s s f u l l y b u tt h ea p p l i c a t i o n i nf i e l do fi n f o r m a t i o nr e t r i e v ei sr e l a t i v e l yl i t t l ea n dr e s e a r c hu s i n gr o u g hs e tl i k e w i s e s o i n t h i sp a p e rt h ea t t e n t i o ni sm a i n l yf o c u s e do nt h i st o p i ct h r o u g ha n a l y z i n ga c t u a l i t y ， d i f f i c u l t i e sa n do p p o r t u n i t i e s t h eb a s i cp o i n to fv i e wo ft h i sp a p e ri st h a tr u l e se x t r a c t e d f r o mi n f o r m a t i o ns y s t e ma r eu n c e r t a i n t y s os t u d ya n dr e s e a r c hi nt h i sp a p e rw i l ln o tb e p r o c e e d i n gi nt h i sw a y i nt h i sp a p e rw ec o n s t r u c tan e wm o d e lo ft r a i n i n gt h a tt a k ep r e i n d e xt r a i n i n gc l a s s s t a n d a r d sa n dt h ek e y w o r d se m e r g e da sb o t ha p p r o x i m a t e da n dp r r c i s e dk n o w l e d g ea n d d r a ws o m ec o n c l u s i o n sa b o u tt h er e l a t i o n s h i pb e t w e e nt r a i n i n gc l a s sa n dk e yf e a t u r e si n m o d e lo fr o u g hs e t i nt h i sp a p e r ，w ed e v e l o pan e wm o d e lo fs i n g l et e x tc a t e g o r i z a t i o n b a s e do nt h e o r yo fr o u g hs e t t h em o d e lu s er o u g hs e ti nt h ew a yo ft h ek n o w l e d g e a p p r o x i m a t i o na n dc o r r e s p o n d i n gc o m p u t a t i o n t h i sm o d e la l s os o l v e st h ep r o b l e mo f c a t e g o r i z a t i o nm e a s u r e m e n tb a s e do nt h es t a n d p o i n t st h a t “t a k ec l a s s i cr o u g hs e ta sp r o c e s s o ft r a i n i n gw h i l ef u s s ys e ta st e s tr e s u l t ”b yu s i n gt h ec o n c l u s i o nm e n t i o n e da b o v ea b o u t r e l a t i o n sb e t w e e nf e a t u r e sa n dc l a s s e st od e s i g nac l a s s i f i c a t i o na l g o r i t h m a n dt a k et h e c o n c e p t o f r o u g h p r e c i s ei n t o c o m p u t a t i o n t h ea l g o r i t h m c a nb eu s e di n m u l t i c l a s s i f i c a t i o n w ea l s og i v ea l g o r i t h mn a m e dd o u b l eo r i e n t a t i o n a p p r o x i m a t i o n c l a s s i f i c a t i o na l g o r i t h mt od e a lw i t hp r o b l e m so fd e g e n e r a t i n ga ts a n l et i m et os o l v et h e p r o b l e m so ff e a t u r er e d u c t i o n i nt h i sp a p e r , w ea l s od e v e l o pan e wm o d e lo fm u l t i t e x tc a t e g o r i z a t i o nb a s e do n t h e o r yo ft o l e r a n c er o u g hs e t t h em o d e lu s er o u g hs e ti nt h ew a yo ft h ea p p r o x i m a t i o n s e m a n t i ce x t e n s i o na n dp r o p e rr e l a t i o nd e f i n i t i o n i tt a k eu p p e ra p p r o x i m a t i o na sl a t e n t s e m a n t i ce x t e n s i o nw h i l el o w e ra p p r o x i m a t i o na sc o r eo fc o n c e p t k e yw o r d s ：r o u g hs e t ；t e x tc a t e g o r i z a t i o nm o d e l ；t o l e r a n c er e l a t i o n ；f u z z ys e t ；d o u b l e o r i e n t a t i o na p p r o x i m a t i o n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得鞍山科技大学或其它教育机构的学位或证书而使用过的材料，与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 签名：叠翌笪巨日期：2 1 1 1 ：兰：锣 关于论文使用授权的说明 本人完全了解鞍山科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手 段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：叠至聋 导师签名：癌至! 型日期：皇竺蟹够 硕士学位论文第一章绪论 第一章绪论 本文所研究的问题属于信息检索领域。在本章中首先介绍信息检索及其关键问题 一文本分类的研究的背景以及现状，然后介绍文本分类的相关研究，最后给出本文的 主要研究工作。 1 1 引言 网络的普及带来了海量信息，怎样从中获取目标信息一直是人们关注的焦点。另 外，以信息检索理论为核心技术的相关应用系统已经成功的应用于各个领域，取得了 巨大的经济和社会效益。反过来，市场的认可又对中文信息处理提出了更高的要求。 所以，信息检索理论的相关关键问题的解决是一项具有挑战性的任务，吸引着越来越 多的团体的关注。 1 2 研究的目的、意义及研究背景 信息革命推动着全球经济以前所未有的速度向前发展。信息及信息技术已经成为 社会最基本的生产力，也是各国政府推动国家经济建设和民族进步的战略制高点。各 国，特别是西方发达国家，从政策、资金、人才等各个方面对信息产业的发展给予重 点保证，力图在这场高技术竞争中占据有利位置。同时，信息技术也深刻地改变着人 们的工作和生活方式。网络技术、数据库技术的普及和发展为信息革命提供了技术保 证和平台。现在，人类的大部分信息已经由纸质载体过渡到电子载体，而且这种过渡 正在加速发展。i n t e r n e t 更是一个透明的、覆盖全球的信息网。通过i n t e m e t ，人们可 以方便地获取世界各地的信息资源，也可以向世界发布自己已有的信息。这种开放、 自由的信息共享和流动方式带来了信息的巨大积累。在这些信息中，大部分是非结构 化或半结构化的文本信息。现在，一方面，人们希望获得越来越多的信息；另一方面， 在大量的信息中，快速有效地检索所需要的内容越来越困难。 现代信息检索应运而生。首先，现代信息检索要完成基本检索要求，即数据检索， 硕士学位论文第一章绪论 它的实质是将描述特定用户所需信息的提问特征，与信息存储的检索标识进行异同的 比较，从中找出与提问特征一致或基本一致的信息。提问特征是对信息的需求进行分 析，从中选择出能代表信息需求的主题词、分类号或其它符号。其次，现代信息检索 还要求信息检索智能化。这是信息检索系统的发展方向，信息检索尽可能的根据用户 的要求自动进行分析，查找出用户所需要的信息需求。现代信息检索还要求信息检索 个性化。信息检索的个性化就是要求信息检索系统能够根据不同用户的需求开展个别 服务，针对不同用户提供不同的检索策略和检索服务模式。它主要是基于信息用户的 信息检索行为、习惯、偏好和特点，向用户提供满足其个体信息需求的一种服务。信 息检索智能化、个性化可以被理解为现代信息检索i r 。 现代信息检索技术主要包括：文本分类、信息过滤、自动索引、自动文摘、信息 抽取。其中文本分类是高效检索的基础，是海量文本信息库的一种数据组织技术，准确 精细的文本分类可大大提高检索的速度和精度，其本身也是一种高效的检索手段。 文本分类相关技术可以应用到许多社会领域，文本分类作为组织和管理数据的一 种有力手段，可被用于抽取符号知识、新闻发布耻1 、排序电子邮件”1 、学习用户兴趣 【4 j 等方面。因此，对文本分类进行研究具有重要的理论意义和实用价值。 现代信息检索与模式识别和机器学习密切相关，它研究能够通过经验改进自身性 能的计算系统。主要分为两个方面：一方面有指导的学习，即通过从人工标注好的 训练样例中学习概念来实现对样本的自动分类。另一方面是无指导的学习，即事先不 经过人工的标注，将样本自动聚为有意义的组。其实质还是分类问题。现代信息检索 属于模式识别和机器学习的一个应用方向，现代信息检索的发展离不开模式识别和机 器学习的进步。 1 3 文本分类发展过程 作为机器学习的应用领域，文本分类的理论研究可以追朔n 2 0 世纪6 0 年代初。它 的发展过程大致可以划分为三个阶段【5 l = 第一阶段是2 0 世纪8 0 年代前。在这一时期，模式识别和信息检索相继发展成为一 门学科。m a r o n 和k u h n s 提出概率标引模型，并应用于信息检索中；g e r a l ds a l t o n 提出 了向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 用于对文本进行描述。这一阶段主要是 硕士学位论文第一章绪论 集中在对分类理论的研究，应用方面则主要是用于信息检索。 第二阶段是2 0 世纪8 0 年代。这一阶段主要是采用传统的知识工程技术，根据专家 提供的知识形成规则，手工建立分类器。这实际上是专家系统。在这一时期，信息检 索技术逐渐成熟应用，为文本分类提供了许多技术支持，最著名的i r 系统是s a l t o n 的 s m a r t 。手工建立分类器的特点有：一是依赖于专家；二是面向领域，一旦应用领 域变化，需要重新生成规则。三是分类器建设周期长，工作量大，分类质量难以保证。 第三阶段是2 0 世纪9 0 年代以后。互联网技术的发展，对文本分类提出了迫切要求。 在这一时期，文本分类的主要特点是采用统计机器学习方法，自动建立分类器。基于 机器学习的文本分类方法克服了以前手工建立分类器的缺点，使得文本分类具有了真 正的实用价值。主要特点有：一是分类知识来源于机器对训练集的自动学习，不再依 赖于领域专家；二是学习和分类过程不需要人工干预，分类效率和准确率得以提高。 目前所说的文本分类主要是指第三阶段的基于机器学习的文本分类。 因此，文本分类的研究严格来说只有十几年的历史。在开始时期，研究的重点是 将机器学习、信息检索等相关领域中的成果应用到文本分类中。随着研究的深入，文 本分类问题被进一步细化，研究人员对各个子问题进行深入研究，例如：分类方法， 特征降维，性能评价，大，j 、样本学习，分类性能推广，语言知识利用等。试图在对 文本内容更多理解的基础上，提高文本分类的效果。 1 4 文本分类定义 文本分类是将用自然语言表不的文本，根据其内容，自动分类到预先设定的类型 集合中，使得一篇文本对应类型集合中的一( 几) 类。文本分类问题可以形式化定义 如下【1 1 ： 给定问题： c = c l ，一，c 。) ，d = d l d ，) ，a = ( d 口) ，日口= 0 ，l 其中： c = 。l ，- ，c 。) 为预先设定的类型集合， 2 为类型数； d = d 。d ，) 为某一领域的所有文本集合，为文本总数：a = ( a 。) 为 m 矩阵，元素d 。= o ，1 ) ，表示文本d ，按照其内容是否属于类型c ，。假定在 硕士学位论文 第一章绪论 文本与类型之间存在一个未知的映射函数： f ：d cj 0 , 1 ) 而且，文本集d = j 。d ，) 中部分文本d = d 。d 。) ，”，已经被分好 类，即矩阵a = ( 。) 中的子矩阵a = ( o 。) 已经确定。文本分类就是要找一个 函数： f + ：d c 寸 0 , 1 ) 尽量逼近未知的真实函数。在文本分类中，函数，称为一个分类器( c l a s s i f i e r ) 。 ；g e e ：d = m 时，为多分类 问题，当2 = m 时为单分类问题。多分类问题都可以转化为多个单分类问题。 1 5 文本分类步骤 文本分类一般有训练和测试两个阶段。为了建立一个高性能的分类器，训练和测 试多次反复，组成一个反馈系统。完整的文本分类过程一般包含6 个步骤【5 j ：建立数 据集、文本标引、降维，机器学习、测试、评价。系统结构如图( 1 1 ) 所示。 圈1 1 文本分类结构图 5 1 1 建立数据集 这一步主要是收集文本，并进行预处理，包括处理乱码、非文本内容等；机器内 码转换；处理词干( s t e m m i n g ) 及停用词( s t o pw o r d s ) ；删除无效文本；按类型集进 行人工分类；按一定比例随机划分训练集和测试集。 2 文本标引 确定特征单位，并按一定的描述模型对文本进行标引。它的作用是将文本的内容 硕士学位论文 第一章绪论 按照一种计算机能够理解的格式用特征( f e a t u r e ，t e r m ) 描述出来，使机器能够 对文本进行处理和运算。 3 降维 用于文本标引的特征空间通常具有很大的维数，这会影响分类的效率，甚至超出 机器或算法的处理能力。因此，需要进行特征降维，生成一个更紧凑的特征空间。 4 机器学习 在训练集上进行机器学习，确定分类器的各个参数，建立分类器。机器学习的依 据是文本的内容，不能依据文本的其他元信息。在文本分类中，类型符号只是一 些标记。 5 测试 用分类器对测试集进行分类，得到机器分类的结果。测试有封闭测试和开放测试。 封闭测试时，测试集是训练集的一部分；开放测试时，测试集与训练集是服从同 一分布、相互独立的两个数据集。封闭测试不具有可比性，文本分类中主要采用 开放测试。 6 评价 采用一定的评价指标，对机器分类的结果进行评价。不符合要求时，需要返回到 前面的某一步骤，调整参数，重新再做。 1 6 文本分类相关研究 1 6 1 分类器 基于机器学习的英文自动分类已经取得了很好的成绩，提出了多种特征抽取方 法和分类器，如最大熵【1 5 】、回归模型【1 6 】、最近邻分类【1 6 1 、朴素贝叶斯分类【1 7 】、决策 树”1 、支持向量机”1 、规则学习算法【”1 、相关反馈2 0 1 、选举分类2 1 1 、神经网络2 2 1 等， 还建立了o h s u m e d 、r e u t e r s 等标准的分类熟语料和统一的评价方法。国内在中文分 类领域也进行了大量的研究【2 4 1 1 25 1 ，但由于语料和评价方法各不相同，很难对它们 做出严格的比较。 下面简要介绍几个常用的分类方法。下面的内容是是前人研究基础上的一般性 认识。 硕士学位论文 第一章绪论 1 6 1 1n a i v eb a y e s n a i v eb a y e s 分类方法( 以下简称n b 法) 是一种简单而又非常有效的分类方法。 n b 法的一个前提假设是：在给定的文档类语境下，文档属性是相互独立的。假设d 为 一任意文档，它属于文档类c ，中的某一类c = k ，c ：c 。，。根据n b 分类法如公式 ( 1 1 ) d ，ij、j p ( f ，) p ( d ，ic f ) “。川卜= 专萨 p ( d ) = 艺尸( c ，) 尸( d ，ic j ) 对文档d ，进行分类，就是计算所有文档类在给定d ，情况下的概率，概率值最大 的那个类就是d 所在的类，即： i t 勺i fp ( c g 旧) 2m a x ； p ( c ，) ) 对于给定分类背景和测试文档，用n b 法分类的关键就是计算p ( c ，) 和p ( d ，lc ，) 。 计算p ( c ，) 和p ( d ，1c j ) 的过程就是建立分类模型( 或者说学习) 的过程。 1 6 1 2 支撑向量机 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理基础 上的，根据有限的样本信息在模型的复杂性( 即对特定训练样本的学习精度，a c c u r a c y ) 和学习能力( 即无错误地识别任意样本的能力) 之间寻求最佳折衷，以期获得最好的推 广能力( g e n e r a l i z a t i o na b i l i t y ) 。s v m 是从线性可分情况下的最优分类面发展而来 的，基本思想可用图( 1 j 2 ) 的两维情况说明。图( 1 2 ) 中，实心点和空心点代表两类样 本，h 为分类线，h 1 、h 2 分别为过各类中离分类线最近的样本且平行于分类线的直 线，它们之间的距离叫做分类间隔( m a r g i n ) 。所谓最优分类线就是要求分类线不但 能将两类f 确分开( 训练错误率为0 ) ，而且使分类间隔最大。 6 一 硕士学位论文第一章绪论 1 6 1 3k n n 图1 2 最优分类面【6 i 具有埘个类c ，c 2 i 一，c m 的文本分类问题，其k n n 分类决策过程如下：对于一 个给定的测试文档乃，分别计算它与训练样本集中每一个文档的距离( 或相似度) ， 找到与之最近的| j ( 1 ) 个训练文档，其中属于c f 类的文档数有t 。个，则定义判别函 数如公式( 1 2 ) g i ( x ) 2t 。，i = 1 h 2 朋 ( 1 2 ) 那么分类的决策规则为：若g ，( x ) ：m a 】( ( ，) ，i ：l ，2 ，研，则决策x 6 c 。 1 6 1 4 决策树，决策规则分类器( d e c i s i o nt r e e r u l e sc l a s s i f i e r ) 决策树分类器是一种基于规则的分类器。它采用“分而治之”( d i v i d e a n d c o n q u e r ) 的策略，通过学习，自顶向下构造一棵决策树。树的内部节点是特征，分支表示特征 到不同状态的权重，叶子节点为类型。建立一个决策树分类器一般包括以下四步： 1 从特征集中选择信息量最大的特征，作为当前节点； 2 按所选特征的所有状态( 权重值) 将训练集分类，得到相应的子类，生成分支； 3 对各子类递归进行以上两步操作，直到子类中的样本都属于同一类型( 树的叶 子) ，得到决策树； 4 对决策树进行修剪，生成更紧凑的决策树； 在建立决策树时，选择节点的依据是特征含有的信息量，常用的有信息增益、信 硕士学位论文第一章绪论 息增益率( i gr a t i o ) 、信息熵等。对决策权进行修剪是为了防止决策树过大，将部分 子树合并成一个叶子节点，叶子节点的类型由子树中的文本子集决定。修剪技术有 r e p 、f o i l 、g r o w 、i r e p 等。目前，决策树分类器有许多成熟的软件包可用，如：i d 3 、 c 4 5 等。决策规则分类器与决策树分类器本质上是一样的，也是从训练集中学习规则。 不同的是，决策规则分类器是自底向上生成规则集。首先根据训练集生成一个大的原 始规则集，覆盖所有的训练文本及其分类；再对原始规则集进行合并、修剪等操作， 得到一个紧凑的规则集，表现为一些条件从句( c o n d i t i o n a lc l a u s e s ) 。基于规则的分类 器被广泛应在文本分类中，或者作为单独的分类器，或者作为组合分类器的成员。 1 6 1 5r o c c h i o 分类器 r o c c h i o 分类器是一种p r o f i l e b a s e d 的文本分类方法。它基于v s m 模型，为每个类 型c 建立一个原型( p r o t y p e ) ，即类型向量： 巧= j ，w 2 ，) 其中：为特征f 。在类型c ，中的权重。采用r o c c h i o 公式进行计算，如公式 ( 1 3 ) 所示。 2 阿青刁；。篆一阿管司篆 3 ， 2 阿网；。奇一向京 。3 其中： z 阿q i 指出现特征并属于类型q 的文本集，也叫正样本， 阿l z c 指出现特征但不属于类型q 的文本集，即负样本；为特征。在训练 文本吐中的权重；口 o ，p o 且口+ 一，是调节正、负样本对类型向量贡献大小 的参数。在r o c c h i o 公式中，的权重由两部分组成：一部分为正样本贡献的权重， 另一部分是负样本贡献的权重。它的基本思想是：在向量空间中，类型向量应该尽量 靠近正样本，远离负样本。为了强调正样本的作用，抑制负样本的作用，在实现时， 通常增大参数a ，减少参数。类型向量一描述了c ，的轮廓( p r o f i l e ) 信息。当要决 定任意文本的类型时，将文本向量与类型向量进行相似度比较，根据它们之间的距离 决定文本所属的类型。在r o c c h i o 方法中，那些与正样本相似的负样本是最难与正样 本分开的，因此它们对类型向量的作用很大，而那些与正样本相距很远的负样本的作 硕士学位论文 第一章绪论 用很小，甚至会产生干扰。为了限制负样本的范围，提出了检索区( q u a r yz o n e ) 的 概念。采用各种检索区的r o c c h i o 方法在文本检索中都改善了检索效果。 许多学者对不同分类器进行了实验比较1 1 1 1 2 6 1 2 7 1 1 2 8 1 2 9 删】【3 2 1 和理论研究【1 3 1 【1 4 1 。从 实验结果来看，普遍认为组合分类器、支持向量机、k 近邻等分类效果最好，但是相 对于r o c c h i o 等分类器，它们的训练或分类的效率很低。有些学者报告了相反的结论。 比较统一的结论是：数据集对分类效果的影响很大，基于不同的数据集会得到不同的 结论；没有最优的分类器，应该根据分类任务的特点选择分类器；根据数据集对分类 器进行优化，可以显著地改善分类器的性能；分类器的比较应基于相同的实验条件。 1 6 2 实验数据集 语料库原指语言资料库，是为字词典编撰提供例句或给语言学家研究语言提供第 一手资料。后引入到计算机信息处理领域。意为计算机可以处理的大规模真实文本的 有序集合。在自动分类中，语料库是按照一定的类别组织起来的文本集合，是构建分 类器的基础。 基于训练语料的自动分类过程通常由训练和分类两个阶段组成。在训练阶段，采 用统计的方法从大规模训练文本，即由人工分类的各类别文献组成的集合中学习各类 的特征，建立规范化的类别特征向量，以得到分类器。在分类阶段，将待分类文献的 特征词串与分类器各个类目特征进行计算比较，得出分类概率最大的类。 目前，采用机器学习从训练语料中发现类目特征进行文本分类的方法有很多种， 如决策树法、支持向量机、贝叶斯分类、k 一近邻分类和神经网络算法等。这种基于 训练语料的自动分类模式广泛为计算机界所采用，它比较适合面向主题或行业的粗分 类，是自动分类发展的一个主要趋势。 基于标准的数据集进行文本分类研究，不仅可以减少建设数据集的费用，也使得 分类结果具有可比性。国际上用于文本分类的英文标准数据集主要有4 个： r e u t e r s 一2 1 5 7 8 ，o h s u m e d ，2 0 n e w s g r o u p s 和t r e c 。除了t r e c 需要参加其组织 的比赛以外，其他3 个数据集都是可以免费下载的。它由l e w i s 博士1 9 9 7 年整理， 包含了r e u t e r s 新闻社1 9 8 7 的经济类新闻，其中8 月份之前的新闻作为训练集( 9 6 0 3 篇) ，其他的作为测试集( 3 2 9 9 篇) ，按新闻主题分为1 2 0 个类型。去掉没有标注 类型的文本后，得到1 0 7 8 9 篇文本，其中：训练集7 7 7 0 篇，测试集3 0 1 9 篇，分布在 硕十学位论文第一章绪论 篇，测试集3 0 1 9 篇，分布在9 0 个非空类型中。t r e c 是由美国n 1 s t 和美国国防部联 合资助的、基于大规模真实文本的i r 比赛，从1 9 9 2 年开始每年举行一次，到2 0 0 3 年已举办了1 2 届。 国内有影响力的中文生语料库、词语语料库、句法语料库有：公开发行的人民 日报的语料库，它收集了4 8 年的全部文字和图像内容。北京大学计算语言学研究 所与富士通公司( f u j i t s u ) 合作，加工2 7 0 0 万字的人民日报语料库，加工项目 包括词语切分、词性标注、专有名词( 专有名词短语) 标注。还要对多音词注音。复 旦大学中文文本分类语料库。该语料库总共有1 9 6 3 7 篇文档，其中测试文档9 8 3 3 篇 训练文档9 8 0 4 篇1 3 3 | ： 1 7 文本分类系统框架 为了便于对本文算法以及系统更加容易理解和把握，这里先简要地介绍整个系统 的框架结构，如图( 1 3 ) 所示： 幽1 3 文本分类结构幽 整个系统可以分为两部分，部分是左面的训练过程，另一部分是右面的测试过 程，研究内容以左边的训练过程为主，训练所得的结果供测试部分应用，而测试的结 果反馈给训练部分，改进训练方法。 硕士学位论文 第一章绪论 1 8 本文研究的问题 目前，关于文本分类的研究大多集中在机器学习领域，采用的各种分类器的分类 结果多数以确定的形式给出，这种情况是不符合客观事实的。实际上，对测试文档的 类别判别是发生在一定概率下的，原因是学习过程和测试过程都是一种抽象过程，会 造成知识的丢失。另外，文本信息的类别归属问题本身就是模糊问题，语义和概念的 表达具有多义性和误解性。但是目前的基于各种方法的分类器都没有体现出这一重要 事实，结果会造成分类发生错误，最重要的是不能从本质上解决多重分类的问题。 关于这方面的论述大都是基于模糊数学的方法解决。但是r o u g hs e t 理论在处理 含糊问题上具有独特的优势。例如，从研究对象上看，模糊集研究的是属于同一类的 不同对象的隶属关系，重在隶属程度，而粗糙集研究的是不同类的对象组成的集合之 间的关系，重在分类。所以，它更适合于文本分类器的构建。另外，目f i i j r o u g hs e t 理论应用于文本分类大多集中在分类规则提取的研究上，这实质上是应用数据挖掘 ( 结构化数据挖掘) 的方法来处理文本分类( 非结构化数据挖掘) 。文本所组成的信 息系统是不完备，不一致的，这会限制数据挖掘的应用效果。本文将利用r o u g hs e t 理论从全新的角度构建新型文本分类器，解决分类的模糊性度量的问题。 要在r o u g hs e t 模型下解决分类的模糊性度量问题，必须解决原始问题中的特征 与训练类别之间的关系问题。因为在一般情况下可以用集合描述关系，而集合的运算 是r o u g hs e t 运算操作的基础。本文的目标是通过对大量原始数据进行训练，得出训 练类别与特征之问的关系，通过运用这种关系解决类别隶属问题。 语义扩展是信息检索领域的另外一个重要问题。为了进行操作，适合的文本表示 方法是必须的。当前，最流行的方法是将文本表示为多维向量空间，“维”代表语义 单位t e r m ( 词) 。这样文本对象就成为“b a go fw o r d s ”。高维数问题造成计算的复杂 性高甚至是不可能的完成的。所以，要选择最能表达文本内容的词作为特征属性即 i n d e xt e r m 。由于进行了i n d e xt e r m ，自然语言变成词的集合的过程中存在语义损失， 对文本的表达程度下降，对文本的操作结果产生不利影响。语义扩展成为解决问题的 关键。采用r o u g hs e t 理论中的近似理论在一定程度上可以解决此问题，它也是r o u g h s e t 应用上的重要方面。相对于l s i 潜在语义分析有它自己的特点。本文基于此作了 相关的分析研究，解决了在分类器上的应用问题。 堡主兰垡垒兰 兰墨! i 鱼 1 9 目前r o u g hs e t 应用于本文分类操作的研究 本小节主要介绍目前r o u g hs e t 应用于文本分类操作的方法及方向。在文献【7 】中 介绍了粗糙集在文本分类中基于规则的分类方法。它将文档中的关键词向量作为规则 的前提条件，文档所属类作为规则决策： 巧( 印= 烈吐岛) 反z 岛) 以z 砖) d 口气如，一吨u 其中t 是关键词，u 是关键 词集，d 是一个文档，d 是一个文档类。( 力是应用于d 的第i 条规则。这是r o u 曲s e l 较为典型的应用，它的重点在于对文本信息系统进行属性约简，建立核属性后，利用 近似集合之间的关系进行规则的提取。从实验结果上看取德了较好的分类结果。 虽然基于规则的分类方法有弊端，但是该方法还是有它的应用点。例如文献 8 有了较好的应用。它在对象的层次上进行近似操作，而不是在属性的层次。这样将属 性信息进行综合化比较，避免了局部信息过细而限制了规则的产生。对于任意给定的 c u ，记为n g u q 屿葺相似的文档的集合。由，j = l z ，删组成的集合记为 c = x 。，置，以) 。根据决策属性d 将u 分成g 类，d = k ，e ，l 决策表上的第i 个决策规则定义为d e s c ( x , ) j d g ( r ) ，x ，c 。，y ，。文献 9 中介绍的屡次聚类 方法也是基于这一原理进行文本操作。文献 i o 】中提出一种较新的文本直接聚类方 法。并在此基础上利用信息嫡对信息系统进行属性和值的约简，约简后的结果郧为规 则。 1 1 0 本文的研究重点 本文的研究工 乍主要集中在考察文本关系的信息检索领域。研究重点是怎样把 r o u g hs e t 理论应用于文本分类。解决“怎样应用”的问题，即通过研究r o u g hs e t 理论中与文本分类操作之间的关系和关联。从方法学的角度进行分析与探讨，解决文 本分类问题。 硕士学位论文 第一章绪论 1 1 1 本文组织结构 本章，介绍了文本分类的研究目的、研究现状、相关算法和一些典型代表系统的 基础上，从检索的角度给出我们工作的意义和目的，主要的研究内容和重点要解决的 t 问题。系统框架以及实验数据集。本文余下章节的组织如下： 在第二章介绍r o u g hs e t 理论模型的基本概念并且做了必要的解释。介绍了粗糙 集理论的产生、应用的局限及优势和文本操作的困难。重点表达怎样利用粗糙集理论 的优势解决文本操作上的困难。 在第三章介绍了文本操作预处理的一般方法。重点内容是研究特征关键字和训练 预标记类别在r o u g hs e t 模型下的关系。它是后面将要介绍的单向和双向单分类器算 法的理论基础。 在第四章首先提出了一种基于r o u g hs e t 理论的单分类器模型。这部分是本论文 的重点内容，它详细的介绍了模型提出的背景、过程及主要思路，给出了相应的算法 和详细的实现过程和计算步骤，并通过一个实例贯穿整个过程。本模型主要从r o u g h s e t 理论知识近似表示、表示精度及由此产生的计算操作的角度进行应用。本章最后 针对实际应用中产生的退化问题设计出双向近似的单文本分类器的算法。并且实现了 属性的自然约简，同样给出了相应的算法和实例。另外，本章还将上述的两个算法从 基于经典r o u g hs e t 扩展为变精度r o u g hs e t ，使这两个分类模型更具有实用性。 在第五章首先介绍了容差r o u g hs e t 的基本概念、应用情况。并以此为基础提出 一种基于容差r o u g hs e t 理论的多分类器模型。同样，给出了必要的分析和思路及相 应的算法。它从r o u g hs e t 理论的关系定义及上近似和下近似的含义扩展的角度进行 应用。本章还针对设计实现过程中发现的问题进行了改进，并配以实现算法说明。 在第六章针对上文提出的基于粗糙集的相关算法设计了实验系统，以验证算法是 否有效为目的设计了测评的指标和实验的步骤。从实验数据上可以得出结论，基于 r o u g hs e t 理论的分类器模型是可行的、有效的。也证明了上文的相关分析是正确的。 第七章对整个研究工作做总结回顾，并提出一些后续工作的难点和展望，以作为 论文的结束语。 硕士学位论文 第二章r o u g hb e 理论基率模型 第二章r o u g hs e t 理论基本模型 本章主要介绍本文的研究工作所涉及的基本理论、定义和概念。它是分析、探讨 问题的基础，是本文采用的基本数学工具，本章将从概述、概念和应用几个方面进行 论述。另外，重点解决为什么采用r o u g hs e t 理论进行文本操作研究。 2 1 r o u g hs e t 理论简介 粗糙集( r o u g hs e t ，r s ) 理论是一种刻划不完整性和不确定性的数学工具，能有效 地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识， 揭示潜在的规律。r s 理论是由波兰学者p a w l a k z 在1 9 8 2 年提出的。1 9 9 1 年p a w l a k z 出版了专著，系统全面地阐述了r s 理论，奠定了严密的数学基础。该书与1 9 9 2 年出版的r s 理论应用专集较好地总结了这一时期r s 理论与实践的研究成果，促进 了它的进一步发展，现已成为学习和应用r s 理论的重要文献。从1 9 9 2 年至今，每 年都召丌以r s 为主题的国际会议，推动了r s 理论的拓展和应用。国际上成立了粗 糙集学术研究会，参加的成员来自波兰、美国、加拿大、日本、挪威、俄罗斯、乌克 兰和印度等国家。目前r s 理论已成为人工智能领域中一个较新的学术热点，引起了 越来越多的科研人员的关注。 r s 理论的生命力在于它具有较强的实用性，从诞生到现在虽然只有十几年的时 间，但已经在许多领域取得了令人鼓舞的成果。广泛被应用模式识别 3 4 1 、知识发现 ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 【3 5 ，36 1 、专家系统( e s ) 、决策分析4 叫和粗糙 控制( r o u g hc o n t r 0 1 ) 3 6 , 3 7 1 等等。 2 2 为什么采用r o u g hs e t 理论 2 2 1 粗糙集理论的产生背景 经典逻辑：只有真、假二值之分。但是现实生活：存在许多含糊的现象，并不能 硕士学位论文第二章r o u g hs e t 理论基本模型 简单地用真、假值来表示。所以，提出了边界的问题。在1 9 0 4 年，谓词逻辑的创始 人g f r e g e 提出了含糊( v a g u e ) 一词，他把含糊现象归结到边界线上。但是，全域上 存在一些个体不能在其某个子集上分类，也不能在该子集的补集上分类。f u z z ys e t s 理论( f s ) 和r o u g hs e t s 理论应运而生。1 9 6 5 年，la z a d e h 提出f u z z ys e t s 的概 念，试图通过这一理论解决g f r e g e 的含糊概念。f s 方法：利用隶属函数描述边界上 的不确定对象。1 9 8 2 年，波兰华沙理工大学z p a w l a k 教授针对gf r e g e 的边界线区 域思想提出了r o u g hs e t s 理论。r s 方法把无法确认的个体都归属于边界区域，把边 界区域