基于模糊软集合理论的文本分类方法

基于模糊软集合理论的文本分类方法摘要：为提高文本分类精度，提出一种基于模糊软集合理论的文本分类方法。该方法把文本训练集表示成模糊软集合表格形式，通过约简、构造软集合对照表方法找出待分类文本所属类别，并针对文本特征提取过程中由于相近特征而导致分类精度下降问题给出一种基于正则化互信息特征选择算法，有效地解决了上述问题。与传统的KNN和SVM分类算法相比，模糊软集合方法在文本分类的精度和准度上都有所提高。关键词：文本分类；软集合；模糊软集合；特征选择；互信息1概述软集合理论是学者于1999年提出的一种新的处理不确定、模糊及未被清楚定义的对象的数学工具。目前被广泛应用处理不确定性问题的数学理论和工具有：概率论，模糊集理论，区间数学，粗糙集等，但是所有这些理论和结果都有其不完善的方面，产生这些问题的主要原因在于参数化工具的不足。而软集合理论就是处理不确定性且不存在上述问题的强有力数学工具。当前，有越来越多的学者投入到软集理论及应用的研究，有文献对软集的基本理论进行了研究，并给出软集在决策中的一些应用；Cheng和Tsang给出了基于软集理论的属性约简方法并和粗糙集中的属性约简作了相应的比较；有文献在考虑增加属性及次优选择问题上给出了正则化属性约简原理并给出相应的约简算法；Zhou和Xiao给出使用软集来分析不完备信息系统的方法。文本自动分类是信息检索与数据挖掘领域的研究热点与核心技术，数量巨大的训练样本和过高的向量维数是文本分类的2大特点。这2个特点决定了文本分类问题是一个运算时间和空间复杂度很高的问题。目前产生一些可用的分类系统，并取得了一定的成果，但仍然存在很多尚未解决的问题，文本分类算法的研究不完整、文本的特征选择和特征抽取方法有待进一步改进，基于此，本文首先在文本特征选择阶段提出一种新的基于正则化互信息的特征选择算法，然后结合软集合理论与文本分类的特点提出一种基于软集合理论的文本分类新方法。为了叙述方便，给出软集合相关理论：定义1设U是给定的论域，E是一个参数集，一个集合对(F,E)被称为域U上的一个软集合(softset)当且仅当F是E到所有的U子集中某集合的映射，如F:E→P(U)，其中，P(U)是U的幂集。软集合是U的子集的一个参数族。该参数族中每个集合F(ε)(ε∈E)可以看成软集合(F,E)的ε个元素的集合，或者是软集合的ε个相似元素的集合。定义2若有一个二元运算符，记为*，(F,A)与(G,B)为论域U上的2个软集，那么在软集上的运算*可以定义为：(F,A)*(G,B)=(H,A×B)，其中，H(α,β)=F(α)*G(β),a∈A,b∈B,A×B是集合A与集合B的笛卡尔集。2软集合相关理论定义3P(U)为U上所有模糊集，E为一参数集，Ai⊂E，集合(Fi,Ai)被称为U上的一个模糊软集当且仅当Fi是Ai到P(U)的一个映射，如:Fi:Ai→P(U)。定义4一个信息系统可以形式化为S=(U,A)，其中,U为对象的非空有限集合；A为属性的非空有限集合，并且使得满足对于任意的a∈A有:a:U→Va,V为属性a的值域。定义5对模糊软集(F,E),E={e1,e2,…,em}，若存在E的子集A={e`1,e`2,…,e`p}满足，则A不是必要的,否则A是必要的。若B是必要的且,则B为E的一个正则化约简，即E-B是满足fE-B(.)为一常数的E的最大子集。文本分类中的训练集的向量维数往往非常庞大，可以达到几万维，所以，要对维数进行压缩是文本分类的主要任务之一，它一方面提高了程序的效率和运行速度，另一方面也是关键的方面，由于各个类别都普遍存在对分类没有多大影响的词，因此去掉那些词不仅能压缩维数，而且还能把对分类起代表性的词体现出来，提高了分类精度。本文采用正则化互信息特征选择方法(NMIFS)，并且提出一种贪心选择算法对文本集进行特征选择，该方法既考虑了特征与类别的互信息，也计算了特征与特征之间的互信息，解决了文本中相近的特征同时被选择而导致的性能下降问题，并且能够得到较优的特征子集，具体算法如下：设给定输入数据χ含N个样本，每个样本有M个属性F={fi,i=1,2,…,M},目标类别变量为c,特征选择问题就是要找出最能刻化c的一个含有m个特征{fi}的特征子集S,NMIFS第m个特征选择公式如下：3基于NMIFS的特征选择算法

算法1基于NMIFS特征选择算法输入N个样本χ,目标类别c(每个样本含M个属性F={fi,i=1,2,…,M})

输出特征子集SStep1初始化：给出特征集F={fi,i=1,2,…,M}，S={φ}为空集。Step2对每个特征fi∈F，计算I(fi,c)。Step3选出第1个特征,使得，。Step4进行贪心选择：重复以下(1)、(2)直到|S|=k，其中，|S|为候选集合S的维度。(1)对所有的(fi,fs)计算I(fi,fs)，其中,fi∈F,fs∈S且(fi,fs)这一对互信息没有被计算过；

(2)从F中选择满足式(1)的并设置，。

4.1文本的软集合表示按照第3节方法对训练集中文本进行特征选择得到文本的特征属性集，对所有训练集中的文本提取得到文本的特征向量。在进行文本分类时，以文本的特征属性作为参数集为训练集中的样本文本，按文献[2]中类似的图表方式，文本知识系统表示见表1(因为文本特征属性有几千维，样本量很大，所以表中只给出部分样本及部分属性)。4基于软集合的文本分类方法

4.2软集合(F,E)对照表的构造一个含有n个对象的软集合(F,E)其对照表由n行n列构成，其中，n为软集合中对象个数，表中单元格记为Cij，其取值为:在软集合(F,E)中对象Xi的取值大于等于Xj值所对应的参数个数。显然有0≤Cij≤d且Cij=d,∀i,j,d为参数集E中参数个数，因此,Cij为对象oi在Cij

个属性上取值上大于等于oj

，表1所对应的对比表如表2所示:

,i=1,2,…,n(2)第j列总和记为tj

，其计算如式(3)所示：,j=1,2,…,n(3)给每个对象oi赋于一个重要性值Si

，其计算公式如下：Si=ri−ti

i=1,2,…,n(4)

4.3基于软集理论的分类算法基于软集合理论的文本分类算法首先要把文本特征向量表示为软集合图表，再根据最优值不变原则进行约简，最后选择最佳分类，具体算法如下：算法2基于软集合理论的分类算法输入训练样本的特征向量与待选择的文本特征向量输出所属类别(1)由训练样本的特征向量，构造软集合图表。(2)采用正则化参数约简法[3]进行约简。(3)计算每个文本类别的聚类中心特征向量。(4)重复步骤(3)直到求出所有类别的中心特征向量。(5)由步骤(4)中c个类别中心向量构造一个C×M软集合图表，其中，M为约简后的文本的特征属性个数；C为预先划分好的文本类别数，每个单元格为Vij(i=1,2,…,n,j=1,2,…,m)，矩阵每一行Ci为一个文本类别的中心特征向量。(6)给定一个待分类的文本，计算出其特征向量Vf

。(7)由Vf与步骤(5)中所得的表格构成新的表格，新表单元格Vij计算公式如下:(8)根据步骤(7)得到的软集合图表求出其对照表。(9)由式(2)~式(4)求出步骤(8)中对照表的Si,i=1,2,…,C。(10)求出最优Ci=maxiSi

，即待分类文本的所属类别。5实验结果分析为了验证基于软集合理论的文本分类方法的性能采用复旦大学国际数据库中心李荣陆提供的中文文本分类语料库作为训练集和测试集，从中提取知识并对分类算法进行评价，1882篇文本作为训练集，934篇文本作为测试集，其中的文本涉及10个主题：即交通、体育、军事、医药、政治、教育、环境、经济、艺术、计算机。评价分类性能[7]的2种常用指标是准确率p和召回率r。为了评估算法在整个数据集上的性能，有2种平均的方法可供使用，分别称为宏平均(macro_average)和微平均(micro_average)。宏平均是每一个类的性能指标的算术平均值，而微平均是每一个实例(文档)的性能指标的算术平均。分别从以下2个方面来对基于软集合理论的分类方法进行测试：(1)选不同数量的特征时分类器的性能；(2)与KNN和SVM分类器的性能比较。在实验中选择特征数从400~2800之间对KNN,SVM及基于软集合方法进行