粗糙集理论在文本分类算法中的应用

王珍珍：粗糙集理论在文本分类算法中的应用1粗糙集理论在文本分类算法中的应用王珍珍(枣庄学院，枣庄277160)摘要：文本分类常采用的算法一般是基于向量比较的分类技术。文本中关键字较多，形成的特征向量维数相当高，因而会导致分类比较处理的运算量太大，而降低维数后又会不可避免地丢失有用信息。将粗糙集理论应用于分类处理过程中可有效地解决此问题。关键词：文本分类；粗糙集；约简；文本分类算法中图分类号：TP301文献标识码：A文章编号：1673—1980(2009)04—0166—03文本分类(TextCategorization)是中文信息处理的一个重要研究领域．其目标是在分析文本内容的基础上，给文本分配一个或多个比较合适的类别，从而提高文本检索、存储等应用的处理效率。目前已经有许多文本分类方法应用于该领域．如支持向量机方法(SVM)，K近邻方法(KNN)、朴素贝叶斯方法(NaiveBayes)、决策树方法(DecisionTree)等等。在常用的文本分类算法处理过程中．每个文本都用维数特别高的向量来描述．其向量维数通常高达上万维，即使处理能力最强的计算机也难以处理。很多系统在频率统计的基础上使用了阈值过滤降低向量的维数，却不可避免地丢失一些有用的信息，特别是对于分类很重要的低频词，最终影响到分类的准确度。如果将粗糙集理论应用在分类处理过程中，即可有效地解决此问题。1粗糙集理论应用于文本分类的可行性分析粗糙集理论(RoughSetsorRS)是由波兰华沙理工大学教授Pawlak于1982年提出。用于研究不完整数据、不精确知识的表达、学习、归纳等方法。该理论以对观察和测量所得的数据进行分类的能力为基础，将知识理解为对数据的划分，这种划分在特定空间上由等价关系构成。与其他方法相比，粗糙集理论用于分类有以下优势：(1)粗糙集理论无需提供除问题所需处理的数据集合之外的任何先验信息；(2)它包括了知识的一种形式模型，将知识定义为不可区分关系的一个族集，使得知识有了清晰的数据意义。并且可用数学方法分析处理；(3)它能够获得分类所需的最小特征属性集，可以在不影响分类精度的条件下降低特征向量的维数；(4)它可以得到最简约的显式表达的分类规则，而其他方法无法得到显式规则，如朴素贝叶斯方法和K近邻方法，有的得到的规则含有大量的冗余条件，如决策树方法；(5)粗糙集理论和模糊逻辑、神经网络、概率推理、信度网络、链接计算、遗传算法一起形成了软计算方法的基础。为问题的处理提供了成本较低的解决方案。将粗糙集理论应用于文本分类模型，主要利用粗糙集对知识的等价划分思想，保持了文本的概念信息。首先从已经分好类的文本集中提取区别文本类别的最小关键词向量作为规则的前提条件。文件所属的类别用作规则决策，构成分类决策表；再利用知识约简理论提出文本分类规则。利用这些规则对新文本进行分类验证；最后输出符合分类要求的规则。这样的分类规则容易理解，可使知识系统的处理过程简单化。2应用粗糙集后的分类模型应用了粗糙集理论后的文本分类模型主要包含训练模块、测试模块两部分。基本工作原理如下：首先利用训练模块生成一个分类器．然后选取一部分分好类的文本对分类器进行分类效果测试，如果分类的准确性不能满足要求，则重新回到训练模块，如此反复，直到分类准确性达到要求才能输出最后的分类器，而此时这个经过训练的分类器才能对新文本信息进行分类。引入粗糙集理论的文本分类器工作过程如图1所示。(1)从语料库中选出训练文本和测试文本，每篇样本由人工预先分类，并标上唯一的类别标志。(2)对所有训练文本进行预处理，即首先进行分词处理，将文档变成无序、分散的词条集合，然后将集合中存在的一些频率很高但无意义的虚词和功能词，如“这、是、了、不仅、但是”等词去除，合并同义词、近义词，最后进行词频统王珍珍：粗糙集理论在文本分类算法中的应用2计，形成词频矩阵如表1所示。(3)接着提取并表示文本特征。上一步生成的矩阵特征维数仍然很高，因此需要构造一个评价函数，选取预定数目的最佳特征作为结果特征子集。常用特征权重算法考虑特征项的频率信息TF和反文档频率IDF，即TF—IDF公式：其中：表示词条t在文档D中出现的频率；』v表示全部样本文档的总数：nk表示包含词条tk的文档数。此外还需要考虑词条的位置信息。比如文章标题、副标题、关键字表中出现的词条，应全部保留下来。(4)离散化特征权值。在文本的向量空间模型中，权重是连续型数据，而粗糙集只能处理离散数据，必须先对特征权值进行离散化处理。离散化还可以减少属性值的个数。提高所得到规则的适应度。(5)构造决策信息表。以文本中提取的特征子集作为决策表的条件属性集，文本所属的类别集合作为决策属性集，表中的值是离散化后属性值的表示符。(6)决策表的属性约简。原始决策表信息系统中的条件属性并不是同等重要的。甚至其中某些条件属性是冗余的，因此需要去除对决策没有贡献或贡献小的条件属性．得出对于分类起主要作用的最小特征项(词条)集合，提高处理速度，简化处理过程。一般来讲．一个决策表的条件属性相对于决策属性的相对约简不是唯一的。即对同一个决策表可能存在多个相对约简。因此，人们往往期望找到具有最少条件属性的约简，即最小约简。(7)决策表的值约简。经过属性约简后的决策表中每一个记录可以作为一条规则，但并不是每一条记录的每一个属性值都对信息系统最后决策规则的提取产生作用．因此，必须对属性约简后的结果继续简化，即约简规则。(8)利用上一步生成的最简决策表提取决策规则，即初步生成分类器。(9)利用测试文档验证训练结果的正确性，对选‘取出的测试文本经过上述预处理、约简等过程后生成由属性值构成的集合样本，然后根据决策规则得出最终的类别标号，并与人工预先设置的类别号进行比较以验证分类结果的准确性，通常使用查全率和查准率进行判定。其公式如下：其中：口表示被正确分到该类的文档数；b表示被错误分到该类的文档数：c表示本应属于该类，但没有分到该类的文档数。假如测试结果大于某一设定分类正确度f阈值)，则输出规则，结束运算，否则需要返回到第(3)步重新选取特征子集，重复以上所有的过程。3结语将粗糙集理论应用于文本分类算法，主要利用其对不完整数据、不精确知识的表达、学习、归纳等方法．通过等价类形成的上近似和下近似来描述集合的粗糙性。而上近似和下近似间形成了一个边界集合．包含了所有不能确切地判定是否属于给定类的对象。因此，利用本模型对文本进行分类，可有效地提高分类结果的查全率及查准率。·参考文献[1]王国胤．Rough集理论与知识获取[M]．西安：西安交通大学出版社．2001．[2]王加阳，陈松乔，罗安．粗糙集动态约简研究[J]．小型计算机系统，2006，27(11)：2506-2508．[3】陈欢．基于粗糙集理论的值约简及规则提取[J]．福州大学学报(自然科学版)，2004，32(4)：472—475．[4]王明春．粗糙集的数据及文本挖掘方法研究[D]．天津：天津大学．2005．[5]刘红岩，陈剑，陈国青．数据挖掘中的分类算法综述[J]．清华大学学报，2002，42(6)：727．730．[6】常梨云，王国胤，一种基于RoughSet理论的属性约简及规则提取方法[J]．软件学报，1999，10(11)：1206—12l1．[7]张文宇，贾嵘咖识发现过程中连续属性离散化方法研究[J]．西安理工大学学报，2002(3)：249-254．ApplicationofRoughSetTheoryinTextClassifyingArithmetic王珍珍：粗糙集理论在文本分类算法中的应用3WANGZhen-zhen．(ZaozhuangUniversity，Zaozhuang277160)Abstract：Presently，thepopulararithmeticoftextclassificationistheclassifyingtechniquesbasedonvectorcomparison．However，astherearetoomanykeywordsinthetextformingaratherhilghdimensionofeigenvector,whichconsequentlyeitherleadstoaverybigoperationamountinclassifyingdisposalorsurelymissesusefulinformationafterloweringthedimension．Ifroughsettheorycanbeappliedintheprocessofclassifyingdisposal，thisproblemcanbeeasilydealtwith．Keywords：textclassification；roughset；reduction；textclassifyingarithmetic