基于粗糙集的文本分类研究

时间：2024-10-19 04:58:31 研究生论文我要投稿

相关推荐

基于粗糙集的文本分类研究

　　摘要：文本分类是信息检索和数据挖掘等领域的研究热点。在现有的一些文本分类方法中，文本都是基于向量空间模型表示的，所形成的特征空间维数相当高，导致分类算法效率不高，分类精度不理想。粗糙集应用到文本分类可以在不影响分类精度的条件下降低特征向量的维数，并且可以得到的显式表达的分类规则。本文旨在介绍文本分类一般过程，分析将粗糙集理论应用到文本分类中关键步骤，总结粗糙集与其他分类算法结合应用到文本分类的情况。

基于粗糙集的文本分类研究

　　关键词：文本分类;粗糙集理论;属性约简

　　1. 引言

　　近年来随着网络和信息技术的发展，我们的工作和生活得到了极大的便利，可获得的信息量急剧增长。但我们在得到便利的同时也被浩如烟海的数据所淹没，想要快速有效的找到所需的内容也越来越困难，若用传统的手工分类和处理不但耗费大量的人力和物力，而且在速度和精度方面也远远不能满足要求，这对文本的分类技术提出了迫切的要求。

　　文本分类是信息检索和信息智能处理的基础，近年来受到了广泛的关注，很多学者对此做了深入的研究。目前基于统计方法和机器学习的方法的已经应用到文本分类，并且取得了丰硕的成果。目前在文本分类中常用的分类方法有：朴素贝叶斯(Na?ve Bayes)、支持向量机(SVM)、决策树、K-紧邻(KNN)、人工神经网络等。在文本分类中，广泛使用向量空间模型(VSM)来表示文本。由于自然语言的复杂特性，文本的特征空间的维数会特别高，如中文字Bigram 特征集的大小高达上百万，如此高维的特征空间使得一些算法无法进行或者效率非常低。为此有些系统在频率统计的基础上，使用阈值过滤掉一些特征来降低维数，但是这样会造成信息的丢失，特别是对分类重要的低频特征，从而影响了分类效果。

　　粗糙集理论(Rough Set)是由波兰数学家Pawlak在1982 年提出的一种能够处理不精确、不一致、不完整信息与知识的数学理论。粗糙集理论能够有效的分析和处理不完备信息，已经成为一种重要的信息处理技术，并在机器学习、数据挖掘、决策支持与分析等方面得到了广泛的应用。粗糙集理论是建立在分类机制的基础上的，将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分，粗糙集理论用上下近似来描述这种划分。

　　上近似和下近似对应着确定属于给定类的最大的对象集合和可能属于给定类的最小的对象集合。通过其知识约简理论得到属性的最小子集，能够很好的近似分类，并可以显式表示分类规则。

　　本文主要介绍文本分类的一般过程与框架，粗糙集理论的特性以及应用到文本分类的可行性，然后分析基于粗糙集理论的文本分类模型。

　　2. 文本分类一般过程与框架

　　文本分类是基于文本的内容将未知类别标号的文本划分到一个或者多个预先给定的类别中，从而提高信息检索等应用的效率。文本分类的一般过程包括：文本的向量表示、特征降维、特征加权、分类器的构建与训练、分类结果的评价与反馈等。图1 是一个简单的文本分类系统的简单的框架图，其中实线表示分类器建立过程中的数据流，虚线表示分类器测试过程中的数据流。

　　2.1 文本的向量表示

　　将文档表示成计算机能处理的形式是进行文本分类的基础工作，目前广泛使用向量空间模型VSM 来表引文本，即把每个文本看作是由一系列特征词构成的集合。这部分工作主要包括处理乱码以及非文本内容、过滤停用词、合并词干、对中文文本进行分词处理等。中文分词技术目前比较有影响力的是中科院开发的汉语词法分析系统(ICTCLAS)，目前已经在文本分类系统中得到广泛应用。

　　2.2 特征降维

　　文档经过预处理以后，其特征空间通常是高维空间，这会导致一些分类算法无法进行或者效率非常低，所以必须对特征空间进行降维处理。特征降维的方法主要有两种：特征选择和特征抽取。特征选择就是从原特征集中选择一个真子集作为其特征集，选择的依据是特征对分类作用的大小，通常使用一个统计量来度量，如特征频度、文本频度、特征熵、互信息、信息增益、相关系数、Chi-square 等。特征抽取则是把高维的特征空间转换成一个低维的特征空间，实现降维，常用的特征抽取方法有三类：特征聚类、主成分分析和潜在语义表引。特征降维不仅能够大大降低处理开销，而且在很多情况下可以改善分类器的分类效果。

　　2.3 特征加权

　　为了更准确的描述特征在文本中的重要性，在文本用向量表示后，需要对文本向量中的特征赋予一定的权重。这主要通过词对分类的贡献程度的分析，把分类贡献大的特征赋予高的权值，而贡献度小的或不相关的数据则赋予低的权值。采用合理特征加权方式有助于增大特征词之间的差异、凸显文本的特性和提高分类的精度。目前有很多权重函数来计算关键字在文档向量中的权重，如布尔权重函数、TF-IDF 权重函数、ITC 权重函数、Okapi 权重函数等。

　　2.4 分类器的构建与训练

　　选择不同分类算法决定着分类器的性能好坏，目前基于统计方法和机器学习的文本分类比较成熟，在很多文本分类系统中得到应用。另外还有基于语义和概念网络的文本分类方法，但是由于自然语言处理领域的研究进展相对较慢，所以在这方面还没有太大发展。常用的分类算法有：支持向量机(SVM)、朴素贝叶斯(Na?ve Bayes)、K 近邻方法(KNN)、Rocchio、TFIDF、决策树、神经网络等。

　　2.5 组合分类器

　　各种分类器都有自己分类优势，如果将多个分类器的分类结果优化组合起来会比单个分类器的分类效果好。已有学者证明，如果单个分类器相互独立，当分类器的个数趋于无穷时，组合分类器的分类错误会趋向于零。组合的策略主要有多数选举、加权组合、动态分类器选择和自适应分类器组合等。组合分类器已在文本分类系统中广泛的应用，并取得了不错的分类效果。

　　2.6 评价标准

　　文本分类的评价是通过实验数据分析获得的，在该部分把测试集中的每个文本进行预处理后，输入到分类器进行分类。通过对分类结果的统计分析然后进行评价。现在常用的评价标准有：准确率/召回率、break-even 点、F-measure、11 点平均准确率图、精度/错误率等;另外还有微平均和宏平均分别用来描述一个类和全部类的分类情况。

　　2.7 数据集

　　在构建和测试文本分类系统的时候需要用到大量的文本资料，如果能使用一个标准的数据集进行研究，不仅可以减少建设数据集的费用，而且可以使得不同研究者的分类结果具有可比性。现在国际上用于文本分类的英文标准数据集主要有以下几个：Reuters-21578，OHSUMED，20Newsgroups 和TREC 等。目前为止还没有标准的中文数据集，不过研究中比较常用的有搜狗语料库、复旦大学中文语料库和北京大学语料库等等。

　　3. 基于粗糙集理论的文本分类模型

　　粗糙集理论是一种分析不确定知识的强有力的数学工具，可以对不精确、不一致、不完整等各种不完备信息进行有效分析和处理，并从中发现隐含的知识，揭示信息中潜在的规律。粗糙集理论研究的是不同类中的对象组成的集合关系，利用不可分辨关系进行分类[16~18]。无需提供除所需处理的数据集合外的任何先验信息，对问题的处理比较客观。通过对原始决策表的约简，可以在保持决策一致(即分类能力不发生改变)的前提下对属性进行约简，可以大大降低特征向量的维数，从而方便处理提高效率。通过粗糙集理论进行分类，可以得到最约简显式表达的分类规则。

　　尽管粗糙集理论在处理不确定性不完备的信息有着不可替代的优势，但是粗糙集理论也存在着某些片面性和不足。粗糙集理论模型要处理的分类必须是完全正确或肯定的，严格的按照等价类进行分类，所以在实际应用中多使用粗糙集理论的改进模型，如Ziarko[19]基于多数包含关系的提出的可变精度粗糙集模型等。

　　将粗糙集理论应用到文本分类模型，主要是利用了粗糙集理论对知识等价划分的思想。

　　首先将文本的特征词作为条件属性，类别作为决策属性，构建决策表;通过加权规则对特征值进行加权;然后对加权后的权值进行离散处理;再利用粗糙集理论的知识约简在决策表中得到最分类规则;最后建立相应的匹配规则，通过对测试集分类对该分类器性能进行评估。

　　概括起来主要有四个步骤：文本预处理、属性约简、构建分类器和性能评价。基于粗糙集理论的文本分类模型，其中实线表示分类器建立过程中的数据流，虚线代表分类器测试过程中的数据流。

　　3.1 关键步骤

　　3.1.1 构建决策表

　　利用粗糙集理论获得规则是通过对决策表里面的条件属性和决策属性进行属性的约简得到的，在此训练集的文本要表示成本粗糙集理论能够处理的决策表形式。使用向量空间模型VSM 来表引文本，将文本的特征词作为条件属性，文本的类别作为决策属性，构建决策表。

　　3.1.2 数据离散

　　粗糙集理论分析要求数据的值必须以离散的形式表达，然而在实际应用中对特征进行加权后得到的权值的值域为连续值，所以在应用粗糙集理论方法处理之前，必须采用一种适宜的离散方法将连续数据转化为离散区间，经过数据离散后可能会减小原始数据表示的精度，但将会提高其一般性。

　　数据离散的结果直接影响到分类的效果。在粗糙集理论中应用的离散算法很多，大体上可以将其分为两类：一类是直接借用其它学科中的离散算法，如等距离划分、等频率划分等;另一类是考虑到粗糙集理论对决策表的特殊要求，采用结合的方法来解决离散化问题，如Na?ve Scaler 算法，Semi Na?ve Scaler 算法，布尔逻辑和Rough 集理论相结合，以及基于断点重要性、属性重要性和聚类的离散算法等。

　　3.1.3 属性约简

　　属性约简是粗糙集理论的核心内容之一，也是应用粗糙集理论构建分类器的重要部分。

　　属性约简的目标就是要从条件属性集合中找出部分必要条件属性，使得这部分条件属性和所有的条件属性相对于决策属性有相同的分类能力。经过属性约简去除了不必要的属性，实现信息属性的约简，从而分析所得约简中的条件属性对于决策属性的决策规则。

　　目前常用的约简算法可分为两类，一类是不借助任何启发信息的属性约简，另一类是启发式算法，如基于属性重要度的属性约简算法、基于Skowron 差别矩阵的属性约简算法、以及基于信息熵的属性约简算法等，基于蚁群算法的属性约简算法等。

　　3.1.4 值约简和规则合成

　　通过属性约简得到的约简并不是唯一的，但是还没有充分去掉决策表中的冗余信息，还需要进一步对决策表进行处理，得到更加简化的决策表，这部分工作就是决策表值约简。然后按照一定的策略将多个约简表中的相应规则进行合成，得到最终的分类决策规则。决策表值约简算法有一般值约简算法、归纳值约简算法、启发式值约简算法和基于决策矩阵的值约简算法等。

　　3.2 粗糙集理论与其他算法构建的文本分类模型

　　粗糙集理论的属性约简理论可以降低文本分类过程中的向量维数，减少特征数，从而提高了分类速度。利用这一优势可以与其他分类算法结合构成性能不错的分类器。李钝等在空间向量模型的基础上将文本聚类和粗糙集理论的属性约简相结合，提出了一种新的文本分类方法，实验表明该方法可提高文本分类效率。张著英将粗糙集理论应用到KNN 算法中,实现属性约简,提出了一种新的KNN 分类方法,解决了KNN 算法分类效率低的缺点，从而可使KNN 算法能够得到更广泛的应用。王效岳等结合粗糙集理论的属性约简和神经网络的分类机理提出一种混合算法，分类速度得到提高，并体现较好的稳定性及容错性。

　　上述模型主要是应用粗糙集理论的属性约简作为分类系统的预处理器，把冗余的属性从决策表中删去，然后运用其他分类算法进行分类。还有一些研究者将粗糙集理论以其他的方式应用到文本分类中，比如Miao 等提出基于变精度粗糙集的混合算法，利用KNN 和粗糙集理论对样本空间进行划分，然后用简单快速的Rocchio 进行分类，并取得了不错的分类结果;将粗糙集理论的分类质量应用到特征加权[27], 改进了文本样本在整个空间中的分布，使得类内距离减少，类间距离增大，提高样本的可分性等。

　　4. 总结

　　文本分类近年来已经得到很大的发展，有很多比较成熟的分类算法得到了应用，但是过高的特征空间维数限制了分类的效率和精度。特征选择虽然可以降低特征数量，但也不可避免的造成了有用信息的丢失，降低了分类效果。将粗糙集理论应用到的文本分类模型中，可以利用粗糙集理论知识约简理论，在保持分类能力的情况下得到最小的属性约简并得到显式的规则。不过由于粗糙集理论本身限制条件较强，在实际应用中多利用其扩展模型或与其他算法相结合的方式，概括来说有三种方式：一是利用粗糙集理论作为预处理器，实现降维，结合其他分类算法构建分类器;二是利用粗糙集理论的约简理论直接得到分类规则构建分类器;三是利用粗糙集理论的上下近似对样本空间进行划分，提高样本的可分性。

　　参考文献

　　[1] 王国胤，姚一豫，于洪.粗糙集理论与应用研究综述[J].计算机学报，2009，32(7):1229-1246.

　　[2] 张文修，吴伟志.粗糙集理论介绍和研究综述[J].模糊系统与数学，2000，14(4): 1-12.

　　[3] 唐春生，张磊，潘东，等.文本分类研究进展

　　[4] 靳小波.文本分类综述[J].自动化博览. 2006 23(z1): 24-29.

　　[5] 薛德军.中文文本自动分类中的关键问题研究[D].北京：清华大学，2004.

　　[6] 苏金树，张博锋，徐昕.基于机器学习的文本分类技术研究进展[J].软件学报2006, 17(9):1848-1855.

　　[7] 蒲筱哥.Web 自动文本分类技术研究综述[J].情报学报 2009,28(2):233-241.

　　[8] 钱晓东.数据挖掘中分类方法综述[J].图书情报工作，2007，51(3):68-71.

　　[9] 王国胤.Rough 集理论与知识获取[M]. 西安：西安交通大学出版社，2001.

　　[10] 菅利荣.面向不确定性决策的杂合粗糙集方法及其应用[M]. 科学出版社，2008.

　　[11] Ziarko W.. A variable precision rough set model [J]. Journal of Computer and System Sciences, 1993, 46:39-59.