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

南京理工大学博士学位论文 基于辊糙集理论的文本自动分类研究 摘要 文本自动分类是目前信息检索和自然语言处理领域的研究热点之一。九 十年代以后，机器学习方法逐步广泛应用于文本自动分类。基于机器学习 的文本自动分类是一个非常复杂的信息处理任务，目前仍然面临着许多亟 待解决的难题。本文将针对文本自动分类涉及的几个主要问题进行比较深 入的研究和探索。具体研究内容和创新性研究成果概括如下： ( 1 ) 基于n - g r a m 的中英文文本表达方法。文本表达是指将表达文献主 题内容的词汇抽取出来的过程。常用的向量空间表达法主要采用t f i d f 等 权重法。该类权重法普遍存在两大缺点：一是需要计算词汇在整个数据集 中频率，标引效率较低；二是不能直接应用于中文等东方语种文献。否则， 必须首先解决分词技术问题。本文的研究成果是提出了一种不需要进行中 文分词，且不依赖文本数据集，能够同时适宜于中英文文献的文本表达方 法。该方法的主要创新点包括：提出了基于n - g r a m 的g f g l 权重法，能够 根据单篇文献中各个n - g r a 珥的出现频率和长度计算它们表达文献主题内容 的重要性；提出了根据文献n - g r a m 权重值和子父串关系筛选文献关键词的 算法。该算法不需要复杂的参数定义，能够灵活控制文献标引深度和标引 专指度。实验结果表明，本文提出的文本表达方法能够获得比t f i d f 更优 的标引性能。 ( 2 ) 标引词的语义异构性处理。通过文本表达获得的标引词，通常是没 有进行语义规范控制的自由词。如果直接将这些标引词作为特征项输入文 本自动分类算法，会直接导致计算时间复杂度的增加和分类性能的降低。 人工方法和经典相似度计算方法是目前建立标引词语义转换关系的主要方 式。本文的研究成果是提出了一种基于粗糙集理论和索引语言理论的标弓i 词语义转换模型，可以用于建立来源于多个索引语言的标引词之间的语义 关系，解决标引词的语义异构性问题。该模型的优点表现在：克服了人工 转换方法成本高、效率低的缺点；克服了经典相似度计算方法单向性和不 能明确定义标引词之间语义关系的缺点；能够快速有效地实现多个索引语 言在不同兼容水平上的标引词语义双向转换；能够较大范围地集成具有语 义关系的标引词，克服特征抽取方法受限于数据集的缺点。该方法既可用 于文本表达结果的规范控制，也可用于文献检索系统中多种索引语言的自 动语义集成，从而实现应用单种索引语言进行跨数据库检索。 ( 3 ) 粗糙集理论在文本自动分类中的应用问题研究。决策树、神经网络、 摘要 博士论文 支持向量机和贝叶斯等机器学习方法已经广泛用于文本自动分类。产生于 2 0 世纪八十年代初的粗糙集理论是一种处理模糊和不确定性知识的数学工 具。租糙集理论的最大特点在于从知识分类的角度分析概念之间、分类对 象之间和属性之间的关系。基于粗糙集理论的分类系统一般不需要相关数 据集合外的任何先验知识，通过知识约简等简单操作便可以推导出易于理 解和验证的分类规则。因此，从理论上讲，租糙集理论在大规模文本自动 分类任务中应该具有良好的应用前景。本文的研究成果是设计了一个基于 粗糙集理论的文本自动分类方案。创新性研究工作主要包括：提出了一种 可以简单有效自动识别同义词的方法；提出了一种新型的特征项重要性计 算方法和属性约简算法，以确保特征项选择在全局和局部都达到最优化； 提出了一种能够在尽可能保证分类准确度的情况下，提高规则匹配能力的 上下近似规则生成算法和一系列规则匹配方法；提出了一种能够根据输入 新文献与分类规则的匹配状态自动扩展新类别的方法，避免了频繁维护训 练集和更新分类规则的难题。实验结果表明，本文设计的分类系统可以获 得比较令人满意的性能。通过进步完善，可以推广应用于提供分类服务 的各类文献信息检索系统。 关键词z 文本表达关键词抽取粗糙集理论语义异构性分类算法 文本自动分类分类规则机器学习 南京理工大学博士学位论文基于粗糙集理论的文本自动分类研究 a b s t r a c t a u t o m a t i ct e x tc a t e g o r i z a t i o n ( a t c ) i sp r e s e n t l yo n eo ft h eh o t t e s tr e s e a r c h i s s u e si ni n f o r m a t i o nr e t r i e v a la n dn a t u r a ll a n g u a g ep r o c e s s i n g s i n c e1 9 9 0 s m a c h i n el e a r n i n ga p p r o a c h e sh a v eb e e np o p u l a r l ya p p f i e di na t c a 1 t h o u g h t h e yh a v ea c h i e v e db e t t e rp e r f o r m a n c et h a nt r a d i t i o n a lo n e s ，t l e ys t i l lf a c es o m e s i g n i f i c a n tp r o b l e m s t h i sp a p e rm a i n l ya i m st os t u d yo nt h ep r o b l e m so fr o u g h s e tt h e o r yi na t c t h er e s e a r c hr e s u l t sa r ed e s c r i e da sf o l l o w si nd e t a i l f i r s to fa 1 1 al a n g u a g e - i n d e p e n d e n ta p p r o a c ht ot e x tr e p r e s e n t a t i o no fc h i n e s e a n de n 【蚰s hd o c u m e n t si sp r e s e n t e d t e x tr e p r e s e n t a t i o na p p r o a c h e sw i t ht e r m w e i g h t i n gs c h e m e ss u c ha sc o m m o n l yu s e dt f i d f a r ew i d e l yu s e dt oe x t r a c t i n d e x i n gt e r m so fd o c u m e n t s ，t e r mf r e q u e n c yo rt e r md o c u m e n tf r e q u e n c y a l e u s u a l l yc o m p u t e di nt h ew h o l ed o c u m e n t t h e r e f o r e ，m u c hm o r ec o m p u t a t i o n a l c o m p l e x i t y a n ds t o r a g es p a c ea r er e q u i r e d ，i na d d i d o n ，t h e s ea p p r o a c h e s i n i t i a l l yd e v e l o p e df o re n 班s hd o c u m e n t sc a n n o tb ed i r e c t l ya p p l i e dt oc h i n e s e d o c u m e n t sw i t h o u tu s i n gc h i n e s ew o r ds e g m e n t a t i o nt e c h n i q u e s ，w h i c hh a v e b l o c k e dt h ep e r f o r m a n c eo fc h i n e s et e x tr e p r e s e n t a t i o n t h i sp a p e rp r e s e n t sa n a p p r o a c hi n d e p e n d e n to nw o r ds e g m e n t a t i o nt e c h n i q u e sa n dt e x tc o t l e c t i o n s i n t h i sa p p r o a c h ，g f g lw e i g h t i n gs c h e m ei sp r o p o s e dt om e l t s u r et h ec o n t e n t i m p o r t a n c eo fe a c hn g r a mi na l li n d i v i d u a ld o c u m e n t , a n dt h e na na l g o r i t h m i s d e v e l o p e d t of i l t e rf i n a lk e y w o r d s t h ee x p e r i m e n t a lr e s u l t sp r o v et h a to u r p r o p o s e da p p r o a c hc a r lm o r ee f f e c t i v e l ye x t r a c ti n d e x i n gt e r m so fc h i n e s ea n d e n 西s hd o c u m e n t s t h a nt f i d fb a s e da p p r o a c h s e c o n d l y , am o d e li sp r o p o s e dt ot r e a ts e m a n t i ch e t e r o g e n e i t yo fi n d e x i n g t e r m s t h e i n d e x i n gt e r m se x t r a c t e db y t e x tr e p r e s e n t a t i o na p p r o a c h e sa r e n o r m a l l yu n c o n w o l l e d i nt h i s c a s e ，o n ec o n c e p ti su s u a l l yi n d e x e dw i t h d i f f e r e n tt e r m s i nm a c h i n el e a r n i n gb a s e dt e x tc a t e g o r i z a t i o n ，s e m a n t i c h e t e r o g e n e i t yo fi n d e x i n gt e r m sm a yl e a d t ot h ei n c r e a s eo fc o m p u t a t i o n a l c o m p l e x i t ya n dt h ed e c r e a s eo fc l a s s i f i c a t i o np e r f o r m a n c e t h i sp a p e rp r o p o s e s ar o l l 曲s e t - b a s 甜w a n s f e r ( r s dm o d e lc r e a t es e m a n t i ct r a n s f e rr e l a t i o n s b e t w e e nt h et e r m so fv a r i o u si n d e x i n gl a n g u a g e s t h ee x p e r i m e n t sp r o v et h a t r s tc a no v e r c o m et h ep r o b l e m so fi n t e l l e c t u a lm e t h o d sa n dc l a s s i c a ls i m i l a r i t y m e a s u r e se f f e c t i v e l y m 博士论文 f i n a l l y , t h ep r o b l e m so fr o w l g hs e tt h e o r yi na t ca r ed i s c u s s e di nd e t a i l r o u g hs e tt h e o r yi n t r o d u c e dj ne a r l y19 8 0 si saf o n t a lm a t h e m a t i c a lt o o lt o t r e a tv a g u ea n du n c e r t a i nk n o w l e d g e i ni o u g hs e tt h e o r yb a s e dp r a c t i c a l a p p f i c a f i o n s ，a n yp r e l i m i n a r yo fa d d i t i o n a li n f o r m a t i o na b o u td a t ai sn e e d e d ， a n dr e a d a b l ed e c i s i o nr u l e s 瓣e a s i l yi n d u c t e dw i t hl o w e rc o m p u t a t i o n a l c o m p l e x i t y i th a sa l r e a d yb e e na p p f i e dt oav e r y 谢d ev a r i e t yo fd o m a i n s 谢血 s a t i s f a c t o r yr e s u l t s t h e o r e t i c a l l y , i tw o u l dh a v eap r o m i s i n gp r o s p e c ti na t c t h i sp a p e rp r o p o s e sai o u 曲s e tt h e o r yb a s e da p p r o a c ht ot e x tc a t e g o r i z a t i o n i n p a r t i c u l a r , as y n o n y mi d e n t i f i c a t i o nm e t h o d ，af e a t u r ei m p o r t a n c em e a s u r e , a f e a t u r er e d u c t i o na l g o n t l l m , a i l a p p r o x i m a t i o n r u l e a l g o r i t h m ，a s e to f c o m p l e t e p a r t i a lm a t c h i n gr o l e sa n dad y n a m i cc a t e g o r ye x t e n s i o na p p r o a c ha r e d i s c u s s e dd e x a i l e d t h e e x p e r i m e n t a l r e s u l t ss h o wt h a tas a t i s f a c t o r y p e r f o r m a n c ec a nb ea c h i e v e d w i t h o u rp r o p o s e da p p r o a c h w i t hf u r t h e r i m p r o v e m e n t ，i tc o u l db ee x t e n d e di nk i n d so ft e x ti n f o r m a t i o nr e t r i e v a ls y s t e m s p r o v i d i n gc l a s s i f i c a t i o ns e r v i c e s k e y w o r d s ：t e x tr e p r e s e n t a t i o n k e y w o r de x v a c f i o nr o u 曲s e tt h e o r y h e t e r o g e n e o u sc o n c e p tt r e a t m e n t a u t o m a t i ct e x tc a t e g o r i z 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 m c l a s s i f i c a t i o nr u l e sm a c h i n el e a r n i n g i 、， 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：缢盈童珂年锄日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全都或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：弛磊垄 。声月毋日 南京理工大学博士学位论文 基于粗糙集理论的文本自动分类研究 第1 章绪论 文本自动分类( a u t o m a t i ct e x tc a t e g o r i z a t i o n ，a r c ) 能够合理地、 有效地组织海量信息资源，向用户提供简单有效的检索服务，被广泛应用 于自动标引、文本过滤和词歧义切分等文本自动处理技术。文本自动分类 涉及信息检索、自然语言处理、计算语言学、机器学习、统计学和心理学 等多个学科领域：目前仍然面临着许多亟待解决的难题。文本信息资源爆 炸性的增长趋势，使人们认识到文本自动分类研究的重要理论意义及其广 阔应用前景。 1 1 研究背量 1 。1 。i 文本自动分类研究的必要性 随着信息技术的飞速发展，特别是存储设备的迅速更新换代和i n t e r n e t 的普及，电子文本信息资源1 激剧增长。截止2 0 0 4 年1 1 月底， g o o g l e ( h a p = ，w w w g o o s e c o m ) 和百度( h t t p ：删b a i d u c o m ，世界上最大的 中文搜索引擎) 索引的页面已分别超过8 0 亿和3 亿。此外，大量的图书馆、 出版社和信息中心等机构也纷纷建立文本数据库，以提供目录、全文和摘 要等信息检索服务。尽管用户对图像、视频和音频等信息资源的检索需求 也在急剧增加，文本仍然是最主要的非结构化信息资源 1 2 。通过人工 方法来组织管理海量信息资源，绝大多数机构面临着人力、物力和财力资 源不足的困境。大量研究表明，自动标引 3 ，4 、自动分类 5 ，6 ，7 、自动 聚类 8 j 、自动摘要 9 、文本过滤 i o 、叙词表自动构建 1 l ，1 2 、相关反 馈 1 3 和主题发现 z 4 等文本自动处理技术，可以有效地组织、管理和分 析大规模文本信息资源，向用户提供高效的信息检索服务。 文本自动分类采用分类思想组织文献，不仅符合人们的思维习惯和应用 习惯，而且需求资源较少，操作简单，能够适应大规模文本处理的要求。 文本自动分类是当前信息检索和自然语言处理领域最活跃的研究主题之 a 1 。1 。2 文本自动分类面临的主要问蠢 文本自动分类最早可以追溯到1 9 5 8 年，l u h n 通过统计词汇在文献的标 题或者文摘中的出现频率来选择文献的标引类目 1 6 。早期的文本自动分 本文将网页和其它各种形式的文本型信息资源统称为文本。本文所研究的内容和方法都是针对文 本文献，此后不再特别说明。 第1 章绪论博士论文 类基本上都采取词拒匹配法，根据文献和类名中共现的词汇来决定文献的 归属类别。由于分类规则过于简单机械，分类效果不太理想。八十年代后 期，人们主要集中于知识工程方法的研究，由知识工程师手工编制决策树 等推理规则或者专家系统 1 7 。由c a r n e g i eg r o u p 开发的c o n s t r u e 系统 能够对路透社每天发表的文献进行自动分类，在7 5 0 个测试样本上的平均 分类准确率高达9 0 以上 1 8 。然而，系统中的推理规则全都由专家人工编 制，面且针对特定的学科领域和应用环境，根本不可能直接移植于其它应 用系统。与此同时，机器学习方法在语音识别等领域取得了较大的进展。 九十年代以后，越来越多的学者开始致力于研究机器学习在文本自动分类 中的应用 1 9 3 5 。 基于机器学习的文本自动分类，实现机制比较简单，不需要人工干预， 可以达到甚至超过知识工程和人工分类的效果 5 。目前大多数实用文本自 动分类系统都采用机器学习方法2 。文本自动分类是一个非常复杂的信息处 理任务，涉及信息检索、自然语言处理、计算语言学、机器学习、统计学 和心理学等多个学科领域。目前面临主要问题包括： ( 1 ) 独立于语种的文本表达方法 不同自然语言之间本身存在着较大的区别，比如中文和英文。传统的 文本表达方法比较适用于英文等西方语言，但不能直接有效地应用于东方 语言。因此，自动分词成为汉语等东方语种文献在信息检索和自然语言处 理面临的最大障碍之一 3 6 。目前，越来越多的检索系统，比如搜索引擎 和数字图书馆文献系统，同时收录多种语种文献，甚至同一篇文献中也存 在多种语言形式。因此，新型的文本表达方法必须满足两个条件：一是能 够同时适宜于多种语种文献；二是方法简单有效，能够对大规模文本实现 快速自动标引。 ( 2 ) 标引词的语义异构性处理 文本表达的结果通常是没有经过语义控制的自由标引词。同一概念往 往有多种不同的表达方式。概念表达的异构性不仅增加特征项的维度，导 致计算复杂度的增加，而且会严重影响自动分类的效果。毫无疑问，依靠 人工方式可以建立高质量的标引词语义转换关系。但是，随着系统涉及学 科领域的增多，大多数机构都会面临人力和物力匮乏的困境 3 7 。潜在语 义标引和标引词聚类等特征抽取方法虽然可以在一定程度上解决这个问 本文主要讨论基于机器学习的文本自动分类，下文不再特别说明。 2 南京理工大学博士学位论文基于粗糙集理论的文本自动分类研究 题，但是其计算复杂度和效果却难以满足实用系统的要求。因此，必须研 究更简单但更有效的方法，解决标引词的语义异构性问题。 ( 3 ) 基于机器学习的高性能分类方法 九十年代以后，机器学习方法广泛应用于文本自动分类。这些方法可 以概括为以下三种： a 基于向量的方法。支持向量机 2 4 、近邻分类器 3 8 ，3 9 、神经网络 4 0 和r o c c h i o 算法 4 1 等是目前比较流行的文本分类算法。高维度是限 制大多数此类算法推广应用的主要原因，一般应用系统难以满足大容量的 存贮空间和计算时间要求。另外，关键词向量一般被假设为文献空间的一 组正交基向量。从语义角度看，这意味着每个关键词必须是完全优化的， 即每个关键词都描述不同的概念，相似的关键词不可以用作不同的向量。 但是，在实际应用中，自然语言本身存在一定的复杂性，比如同义词、近 义词和多义词等现象 4 2 ，完全优化标引词比较困难。 b 基于概率的方法。贝叶斯分类器( b a y e s i a nc l a s s i f i e r ) 4 3 ，4 4 和 回归模型( r e g r e s s i o nm o d e l ) 4 5 ，4 6 3 是典型的基于概率的机器学习方法。 其最显著的优点就是速度快。遗憾的是，人们往往很难理解条件概率所假 定的词汇之间的语义关系。但是，由于此类方法可以比较灵活地解决分类 效率问题，它们在机器学习方法中一直占有举足轻重的作用。 c 基于规则的方法。该类方法所需要的计算要求远远低子基于向量的 方法，而且能够达到与之相当的分类性能。最简单的词汇布尔匹配法就可 以比较有效地实现文本的自动分类 2 2 。其它基于规则的方法都是研究如 何判断规则和文献的匹配程度。例如，模糊集方法 4 7 5 1 3 ，对于给定的 待分类文献，可以使用多个模糊规则进行分类成员关系的判断。决策树 4 3 和粗糙集 5 2 ，5 3 将在第二章和第五章详细讨论。该类方法的主要优点是计 算时间复杂度相对较低，分类规则比较容易理解。然而，现有的大多数规 则推导技术仍然非常复杂 5 4 。部分研究表明，粗糙集是一种极有潜力的 分类方法，不仅可以大大简化规则推导的复杂度，而且可以定义特征项之 间的语义关系 5 0 3 。目前关于褪糙集在文本自动分类方面的研究还比较少。 ( 4 ) 新类别的自动扩展 基于机器学习的文本自动分类系统，往往需要比较固定的训练集。由 于新文献层出不穷，涉及的内容又干差万别，训练集中的文献不可能代表 所有待分类文献( 新文献) 的主题内容。因此，新文献无法进行类别预测的 情况时有发生。如果通过定期或者不定期地更新训练集，不仅需要大量的 3 苎三兰二l i 兰一 堡圭堡皇 掣i 练时间，而且容易造成分类系统中分类结果的不一致性。新类别自动扩 展方法可以屏蔽频繁维护训练集的问题，节省训练时间和保持分类系统的 一致性。目前自动分类系统中新类别自动扩展阅题尚未弓 起人们的重视， 有待进步的深入研究。 ( 5 ) 标准数据集的建立 为了便于评价文本自动分类的性能，必须建立统一的实验数据集和性 能测试标准。著名的文本检索会议t r e c 为此做了大量的工作，但是以提供 英文实验数据集为主。目前尚无用于分类的中文标准数据集。 ( 6 ) 合理的性能评价指标 自动分类方法性能测试主要沿用信息检索中的一些指标，比如查全率 和查准率。但是，自动分类毕竟不完全等同于信息检索。因此有必要建立 更加合理的性能测试指标。 ( 7 ) 分类体系对分类系统性能的影响研究 从理论上讲，合理的分类体系可以在一定程度上提高分类器的性能。 例如，如果分类法的类别之间交叉重叠越少，训练集中各类别文献之间的 差异就越大，类别和标引词之间的模糊性就越小。在这种基础上训练得到 的分类知识就比较有利于新文献的分类预测。目前关于分类体系对分类系 统性能影响的研究还较少。 1 1 3 本文的选墨臂鼍及研究环境 由德国k o b i e n z - l a n d a u 大学计算机系j t l r g e nk r a u s e 教授领导的社会 科学信息中心，是德国数字化图书馆和信息检索领域的著名研究机构之一。 该中心致力于数字化图书馆、信息检索、自然语言处理和人工智能等方面 的科学研究和信息检索系统开发。该中心的主要研究方向包括异构检索系 统的兼容集成、基于机器学习的文本自动分类和索引语言的语义异构性处 理。涉及的科研项目有：由德国科研基金会( d f g ) 资助的社会科学虚拟图书 馆v i b s o z 项目、由德国教育和科研部资助的c a r m e n 项目以及由b m b f 资助 的i n f o c o n e x 项目等。多年来，研发组专家和博士研究生在上述领域迸行 了大量深入的研究，积累了丰富的实验数据和研究成果。波恩大学是德国 一所著名的综合性大学。由a t t a i nb c r e m e r s 教授领导的计算机系信息检 索教研室，主要从事信息检索理论和方法的研究。 南京理工大学刘风玉教授、张宏教授领导的计算机应用课题组，在计算 机网络安全和性能保持等方向进行了大量深入的研究。目前承揎的科工委 “十五”预研课题“基于粗糙集的互联网故障信息自动分类”，旨在研究 d 南京理工大学博士学位论文 基于粗糙集理论曲文车自动分类研究 粗糙集理论及其在网络故障信息自动分类中的应用。 应2 0 0 2 年国家留学基金委的要求，本人参加了同济大学留德预备部为 期一年的德语学习，经德国学术交流协会( d a a d ) 和国家留学基金委联合选 拔，获得了两年零两个月的中德联合培养d a a d 奖学金，用于资助本人在德 国期间的德语学习和由中德导师共同指导的博士论文研究。具体培养方式 为：在完成南京理工大学学位课程的情况下，选修德国波恩大学计算机系 相关课程，在德国社会科学信息中心进行课题研究，j t l r g e nk r a u s e 教授为 德方指导老师。 作为第一个在波思大学计算机系和德国社会科学信息中心进行博士论 文研究的中国d a a d 奖学金生，除了正常的学习和学术研究之外，还肩负着 促进中德研究机构合作交流的义务和责任。在刘凤玉教授、张宏教授、d a a d 和本人的共同努力下，j u r g e nk r a u s e 教授于2 0 0 2 年6 月对南京理工大学 进行了一周的学术访问。2 0 0 3 年1 1 月，双方签定了正式的科研合作协议。 2 0 0 4 年1 0 月，刘凤玉教授由d a a d 和南京理工大学提供资助，在德国进行 了为期一个月的学术交流访问。访问期间，刘教授和3 t l r g e nk r a u s e 教授 就本人己完成的研究成果和将来的研究计划进行了详细的指导，并迸一步 讨论了双方今后的研究合作方向。与此同时，刘教授访问了波恩大学计算 机系，并同a r m i nb c r e m e r s 教授讨论了校际之间的研究生合作培养和科 研合作项目意向。本人的博士论文研究是三方机构的第一项正式科研合作， 其成功与否对今后的进一步合作有着重要影响。 本论文选题“基于粗糙集理论的文本自动分类研究”，既是当前信息检 索和自然语言处理领域的热点研究问殛，也是德国社会科学信息中心科研 项目的核心内容。本文研究希望借助德国社会科学信息中心在文本自动分 类领域的优良研究环境，以南京理工大学计算机应用课题组在粗糙集理论 方面的研究成果为基础，比较深入全面地探讨文本自动分类研究目前面临 的一些核心问题及其解决方法。 1 2 本文的工作 1 2 1 本文的主翼研究内容 本文研究的总体思路是；首先，简要阐述本文的研究背景及主要研究工 作、文本自动分类的相关过程与研究方法，以及粗糙集理论及其在分类任 务中的应用。其次，比较深入地研究文本自动分类目前面临的几个核心子 问题。最后，总结本文的研究成果，分析需要进一步研究的问题。 第l 章绪论 博士论文 本文的主要研究内容可以概括为以下几个方面： ( 1 ) 研究机器学习在文本自动分类中的应用 文本自动分类研究已有近五十年的历史，在不同的历史阶段产生了不 同的研究方法。本文主要研究基于机器学习的文本自动分类技术，比较全 面她分析与之相关的各种子阀题，特别是文本表达方法、常用机器学习方 法的实现原理及其优缺点、中英文标准实验数据集的现状以及文本自动分 类技术的应用领域。 ( 2 ) 分析研究粗糙理论和方法在分类任务中的应用 粗糙集理论是一种较新的处理模糊和不确定性知识的数学工具，在文 本自动分类应用研究还比较少。本文对粗糙集理论在分类任务中的应用问 题，比如属性约简算法、近似决策规则算法、规则匹配方法以及粗糙集在 信息检索中的应用情况进行了比较深入的研究分析。 ( 3 ) 研究适宜于中英文的文本表达方法 本文旨在研究一种能够同时适用于中英文的文本表达方法。该方法不 需要采用任何中文分词技术，能够通过计算单篇文献中所有n - g r a m 表达内 容重要性的权值以及字符串的子父关系，快速准确地抽取文献的标引词。 ( 4 ) 基于粗糙集理论的标引词语义异构性处理方法研究 最近几年，国外部分专家学者开始提倡应用基于并行文献数据库的标 引词语义异构性自动处理的方法。本文在深入分析信息检索理论和粗糙集 理论的基础上，构建一种能够有效建立标引词语义转换关系的模型。 ( 5 ) 基于粗糙集理论的文本自动分类系统研究 本文试图设计一个基于粗糙集理论的文本自动分类方案。该方案研究 内容主要包括同义词自动识别方法、基于特征重要性的属性约简算法、近 似决策规则算法和规则匹配方法等。 ( 6 ) 动态类别扩展方法研究 动态类别扩展主要用于解决训练集和训练规则的更新维护问题。随着新 文献的不断输入，已有的训练规则会越来越难以满足新文献的分类要求。 本文研究一种基于粗糙集的新类别动态扩展算法，以便能够在保持系统分 类结果一致性的条件下，避免训练集维护的难题。 1 2 2 本文的创新性工作 本文创新性的研究成果主要体现在以下四个方面： ( 1 ) 提出了一种基于n - g r a m 频率统计的文本表达方法。该方法区别于 传统的基于t f i d f 词汇权重法的文本表达方法，可以根据单篇文献中所有 6 南京理工大学博士学位论文 基于粗糙集理论的文本自动分类研究 n g r a m 盼长度和出现频率，计算n - g r a m 表达文献内容重要性的权值，然后 根据权值的大小和每个n - g r a m 与其它n - g r a m 的子父串关系，筛选出文献 的关键词。这种基于n - g r a m 的关键词抽取方法，可以同时应用于中英文文 献。该方法将每个汉字或英文单词都看作一个g r a m 。因此，该方法应用于 中文文献时，不需要进行中文分词，从而克服了中文分词技术对文本表达 性能的影响。尤其特别是，关键词筛选算法可以灵活控制标引专指度和标 引深度。实验结果表明，本文提出的文本表达方法可以快速有效地抽取文 献的关键词，其性能明显优于一种基于中文分词和t f i d f 的方法，可以推 广应用于各种具有关键词抽取过程的大规模文本自动处理系统。 ( 2 ) 提出了一种基于粗糙集理论的标引词语义转换模型。该模型通过利 用不同索引语言标引词在并行文献数据库中的出现频率、共现频率和平均 文献标引长度等信息，定义标引词在不同兼容水平下的语义关系和语义相 似度。该模型既克服了人工方法主观性强、高成本和低效率的缺点，又克 服了基于经典相似度系数方法单向性、低准确性和不能确定定义语义关系 的缺点。实验结果表明，本文提出的转换模型可以有效集成各种索引语言 的标引词，建立不同标引词之间的语义转换关系，从而解决标引词的语义 异构性问题。该方法既可用于文本表达结果的规范控制，也可用于集成文 献检索系统的索引语言，实现跨数据库检索。 ( 3 ) 设计了一种基于粗糙集理论的文本自动分类方案。该方案不仅涉及 基于粗糙集理论的分类规则推导、近似规则生成和规则匹配等常规过程， 而且提出了分类类别的动态扩展过程。本文提出的同义词自动识别方法、 特征项重要性计算方法、属性约简算法、上下近似规则生成算法，一系列 完全部分规则匹配方法和新类别动态扩展方法，可以使文本自动分类系统 获得比较令人满意的分类性能。其主要优点表现在：通过同义词识别等操 作可以较大程度地降低计算时间复杂度和提高分类性能；近似决策规则和 完全部分匹配方法能够在保持较高分类准确率的情况下，较大程度地提高 新文献与分类规则的匹配能力；属性约简算法简单，可以快速推导出易于 理解的分类规则；类剔动态扩展有效地解决训练集维护的难题。 i 2 。3 本文购翁构与组织 本文各章的内容安排如下：第一章简要概述文本自动分类研究的重要 性和面临的主要问题，并就本文的选题和研究背景做了简单介绍。第二章 概述文本自动分类的一般过程、文本表达方法的研究现状以及常用于文本 自动分类的机器学习方法。第三章概述粗糙集理论及其在分类任务中的应 7 第1 章绪论博士论文 用方法。第四章研究一种适宜于中英文的文本表达方法，并对实验结果进 行了评估。第五章研究一种基于粗糙集理论的标引词语义异构性处理方法。 第六章研究粗糙集理论在文本自动分类中的应用问题。第七章在总结分析 全文研究成果的基础上，提出需要进一步研究的问题。 1 3 缩论 文本自动分类的研究已经具有几十年的历史。随着近年来信息技术的 发展，机器学习等方法逐步引入文本自动分类领域，并取得了一定的进展。 文本自动分类涉及多种学科，是一种较为复杂的信息处理任务。本章首先 简要阐述了文本自动分类研究的必要性，以及机器学习方法在文本自动分 类中面临的主要问题。其次，本章概述了全文的主要研究工作内容和研究 成果，并对全文各个章节的内容安排做了简单介绍。 8 南京理工大学博士学位论文 基于粗糙集理论的文本自动分类研究 第2 章文本自动分类概述 文本自动分类，是指在给定的分类体系下，根据文献的内容自动判别文 献类别的过程 3 ，5 ，5 5 。基于机器学习的分类方法分为有指导的分类和无 指导的分类两种。有指导的分类是指运用从已经建立分类标记的训练集中 学习到的分类知识来判断新文献的归属类别；无指导的分类( 主要指自动聚 类) 是将一组文献按照相似程度分成若干个类别，对训练样本不需要事先进 行类别标记。虽然有指导的分类需要事先依靠人工将训练集进行分类，但 是这种人工智力劳动的介入使得分类系统能够取得较好的分类效果。目前 大多数分类系统都采用有指导的分类学习方法。本文主要研究有指导的文 本自动分类方法。 2 1 文本自动分类一般过程 基于机器学习的文本自动分类根据分类结果可以分为独立二元分类和 多元分类两种类型。独立二元分类是指对每篇待分类文献，分类系统对每 一个类别都独立地判断该文献是否属于该类，各个类别互不影响。多元分 类则计算待分类文献与所有预定义类别的相似度，然后根据设定的阈值， 输出候选类列表。例如，决策树、神经网络、贝叶斯、支持向量机和r o c c h i o 等都是独立二元分类算法，k n n 、模糊集和粗糙集等都是多元分类算法。文 本自动分类过程主要包括文本表达、分类器训练和新文献分类三个部分( 见 图2 1 1 ) 。 2 1 1 文本自动分类的一量过墨 9 第2 童文本自动分类概述博士论文 2 2 文本表达法 文本表达是为了自动抽取出能够表达文献主题的词汇，也就是标引词， 通常情况下为关键词。常用的文本表达方法有三种： ( 1 ) 句法分析法。句法分析法是通过应用句法分析程序，筛选出合乎 一定过滤规则的词条。句法分析法的标引结果大多数为有意义的名词短语。 为了保证词条语义的完整性，通常需要借助词典和语料库，否则程序的分 析结果往往是合乎句法的句子而不是词。句法分析法比较复杂，应用实例 较为少见。 ( 2 ) 词库匹配法。词库匹配法是将输入文献与关键词库中的词汇进行 匹配，以便将文献中被词库收录的词条按照最长匹配法抽取出来，抽取出 来的词条就是文献的关键词。词库匹配法虽然能够保证每个关键词在语义 上都是完整的，但是并不能保证文献中所有的关键词都能被抽取出来，也 不能保证抽取出来的关键词就是文献真正的关键词 5 6 。另外，关键词库 往往滞后于文献，文献中新出现的关键词往往很难被及时地收到关键词库 中。 ( 3 ) 基于词频统计的词汇权重法。词汇权重法是目前最常用的文本表 达方法，其具体实现包括预处理和词汇权重计算两大步聚 5 7 。预处理指 通过h t m l 或者其它标签符号清除、停用词过滤和词根还原等操作，将文本 转化为只包含能够表达文本内容的词汇。词汇权重计算则通过定义和计算 各个词的权重或值来反映该词汇对表达文本内容所起的作用，比如著名的 t f i d f 权重法，然后根据设定的闽值筛选出文本的关键词 3 。下文主要描 述基于词频统计的文本表达方法。 在进行文本表达操作之前，首先要确定标引词的粒度。常用的粒度方 式有词( w o r d ) 、词组或短语( p h r a s e ) 、概念( c o n c e p z ) 、n 元组( n - g r a m ，一 组连续排列的词串或字符串) 和优化组合后的标引词。一般认为概念和优化 组合后的标引词优于其它几种表达粒度，但是这两种方法比较难以自动实 现 2 8 。 大多数基于词频统计的文本表达方法都基于两点经验性的共识：词汇 在某一特定文献中的出现频率越高，与该文献的主题就越相关；而词汇在 整个数据集中的出现频率越高，与该文献的主题越不相关，被选作标引词 的可能性就越低 3 5 7 。 假设a i 。表示文献k 中词汇i 相对于表达一个文献内容的重要程度，f i t 表示文献k 中词汇i 的出现频率，n 表示数据集中的文献总数，m 表示数据 1 0 南京理工大学博士学位论文 基于粗糙集理论的文本自动分娄研究 集中所有文献形式转换之后的词汇总数，n 。表示词汇i 在整个数据集中的出 现频率。常用的词汇权重法主要有以下几种： 布尔权重法 布尔权重法是最简单一种加权法。如果某个词汇在一篇文献中出现，则 将其a i 。值定义为1 ，否则为0 。 词频权重法 词频权重法，是根据每个词汇在特定文献中的出现频率来确定其重要程 度的一种加权方法，即a i k _ f ：。它基于这样的假设：当某个作者要深入阐述 或解释他的话题时，常常会重复使用某些特定的词。 t f i d f 权重法 布尔权重法和词频权重法都没有考虑词汇在整个数据集的出现情况。 t f i d f 定义文献k 中词汇i 的权重与其在该篇文献中的出现频率成正比， 而与其在整个数据集中的出现频率成反比 5 7 。词汇在整个数据集中至少 要出现一次。t f ( t e r mf r e q u e n c y ) 表示在单个文献中的出现频率， i d f ( i n v e r s ed o c u m e n tf r e q u e n c y ) 表示词汇在整个数据集中的出现频率。 t f i d f 是目前研究和应用最为广泛的一种权重法。t f i d