段落及类别分布的特征选择方法

杨凤芹,樊 娜,孙红光,孙铁利,彭 杨

1(东北师范大学 计算机科学与信息技术学院,长春 130117) 2(智能信息处理吉林省高校重点实验室,长春 130117)

1 引 言

随着Internet技术的发展,电子文本信息的数量迅猛增长.如何自动高效地组织这些文本信息是文本分类研究所面临的重要问题.文本分类技术根据文本的内容将文本分成相应的类别.向量空间模型是文本分类过程中常用的文本表示模型.在这种表示模型中,每个文档对应一个特征向量,文档中的每个特征词是向量中的一个特征项.然后利用特征加权方法对每个特征项进行加权,常用的特征加权方法有TF[1],TF*IDF[2]和TF-IGM[3]等,所有文档特征向量构成了特征向量空间[4].由于特征向量空间模型将出现在文档集合中的每个词看作一个特征项,因此特征向量空间会包含上万个特征,从而导致了文档表示向量的高维性和稀疏性.这不仅会增加存储负担和执行时间,而且会增加分类的错误率.错误率增加的原因是特征向量中包含了很多不相关的特征,也就是说特征空间中存在很多噪音.因此,有必要在文本分类过程中引入特征选择技术来减少文本表示中的噪音数据,选择有效特征,从而节省存储空间和执行时间,并提高分类的准确率[5].

本文将特征词在文档中的段落分布信息与其在类别内和类别间的分布信息相结合,提出了一种新的特征选择方法.实验结果表明,与其它特征选择方法相比,所提出的方法能够在选择较少数目特征的前提下,达到最优的分类效果.

2 相关工作

特征选择问题可以看作状态空间搜索问题,空间中的每个状态代表一个可能的特征子集.在文本分类中,特征向量的维数非常高,所以不可能穷尽搜索每个特征子集.因此,为了避免穷尽搜索所有的特征子集,研究者提出利用特征评价函数来计算每个特征的重要程度.根据特征的重要程度对特征进行排序,从而选择得分高的特征构成最后的特征子集.广泛应用的特征评价函数有文档频率(Document Frequency,DF)[6],信息增益(Information Gain,IG),卡方统计(CHI square)和基于类内和类间综合度量的特征选择方法(feature selection based on comprehensive measurement both in inter category and intra category,CMFS)[7].下面介绍一下这些评价函数的基本原理.

假设训练集包含N篇文档,这些文档属于|C|个类别,类别集合C={C1,C2,…,C|C|}.这N篇文档共包含|V|个不同特征,ti为第i个特征.对于特定类别Ck,k∈{1,2,…,|C|},a为Ck中包含特征ti的文档数;b为Ck中不含ti的文档数;c为包含ti但不属于C|C|的文档数;d为不含ti也不属于Ck的文档数.

文档频率的基本思想:类别Ck中包含特征ti的文档数越多,ti对Ck的代表能力越强,特征评价函数为:

DF(ti,Ck)=a

(1)

信息增益是一种基于熵的特征评价方式,度量了某个特征的出现或不出现对文本正确分类所提供的信息量,特征ti的信息增益得分计算方式如下:

(2)

卡方统计度量了特征和类别的相互依赖程度.卡方统计根据包含特征ti的文档和类别Ck的四种关系,定义ti和Ck的相互依赖程度如公式(3).

(3)

CMFS特征选择方法综合衡量了特征在类内的相对重要性和在整个训练集中的相对重要性,度量标准依赖于特征的词频,函数定义为:

(4)

其中tf(ti,Ck)是特征ti在类别Ck中的出现频率,tf(ti)是ti在整个训练集中的频率,tf(t,Ck)是类别Ck中所有特征的频率之和.

此外,还有一些其他的特征评价标准.文献[8]利用特征类内和训练集的平均词频以及文档平均词频差异程度的综合值作为特征评价标准.文献[9]提出了基于词频的t-test特征选择方法,该方法计算特征项在训练集中词频平均值和类内词频平均值的差异程度和波动情况.文献[10]提出了基于泊松分布偏差度量的特征选择方法,将特征的文档频率代入泊松偏差,并结合特征与类别的关系计算特征的重要程度.文献[11]利用特征项的词频替换特征项的文档频率对多个特征选择方法进行了改进,实验结果证明了词频对于特征选择的作用.

现有的特征选择方法把词频或文档频率作为特征重要性的基本度量标准.但是,特征的词频无法区分特征在类内各文档间的均匀分布程度;特征的文档频率无法区分特征在文档中的均匀分布程度[12].为了克服特征的词频和文档频率的缺点,本文提出了特征的段落频率,并将其与特征的类别分布信息相结合,提出了一种新的特征选择方法.

3 本文特征选择方法

3.1 特征选择的基本原则

一般来说,选择有代表性的特征应该遵循以下三个原则.

1.文档中分布均匀.均匀分散在文档各个部分的特征比只集中出现在文档某一小部分的特征应具有更高的得分[12].一些特征仅在文档的一小段集中出现,而且出现频率相对较高.如果仅根据特征词频对特征重要性排序,会使特征选择方法更倾向于选择具有这种特点的特征,忽视了文档中分布相对均匀的更具有代表性的特征.

2.类内广泛分布.在同一类别中出现概率较大的特征应赋予较高的得分[13].就某一特定类别而言,如果某个特征在类内分布广泛,说明该特征表示这个类内文档的能力更强.

3.语料库中分布相对集中.当某个特征在特定类别中的出现水平远高于在整个训练集中的出现水平时,应赋予其较高的得分[14].如果一个特征在所有类别中出现情况都相同,那么这个特征代表特定类别的能力就会减弱.如果特征在某一类别中频繁出现而在其它类中出现次数相对较少,这样的特征更倾向于表达特定类别信息.

3.2 基于段落分布的特征选择方法

通常,在写作过程中,作者首先根据主题对文章进行段落划分,一个段落就是作者想要表达的一个语义群.因此,段落是构成文章的基本单位.针对3.1节中特征选择原则1,将特征在文档段落中的分布信息作为衡量特征重要性的影响因素之一.为了量化特征在文档中均匀分布的程度,本文定义了特征的段落频率.具体地说,我们根据文档的自然段来对文档进行分割,如果特征ti在某个自然段中出现,那么该特征的段落频率得分加1.特征ti在文档dj中的段落频率PF(ti,dj)定义如下:

(5)

其中,ParaNum表示文档dj中的自然段数目,IsContain(ti,Pp)表示段落Pp中是否包含特征ti,如果Pp中包含ti,则IsContain(ti,Pp)=1,否则IsContain(ti,Pp)=0.

文本数据区别于其它数据的一个显著特点就是不同文档的长度差别很大.同一语料库不同类别的文档长度相差很大,甚至同一类别中的不同文档长度差别也非常大.为了消除文档长度对特征段落频率的影响,对特征ti在文档dj中的段落频率PF(ti,dj)进行规范化,规范化公式为:

(6)

其中,|V|表示文档集合中特征的总数.

根据特征在文档中的段落频率,可以计算特征在类别中的段落频率.特征ti在类别Ck中的段落频率的计算公式如下:

(7)

其中,|Ck|表示类别Ck包含的文档数.

3.3 基于类别分布的特征选择

针对3.1节中特征选择原则2和原则3,本文用特征ti在类别Ck中出现的概率,即P(ti|Ck),来刻画特征ti对类别Ck的描述能力,同时用P(Ck|ti)来刻画特征ti在整个训练集中区分各个类别文档的能力.根据特征的文档频率,概率P(ti|Ck)和P(Ck|ti)的定义如公式(8)和公式(9)所示.

(8)

(9)

文献[11,15]和文献[16]已经证明了概率P(ti|Ck)和P(Ck|ti)对特征ti重要性的刻画能力.文献[15]提出的改进的GINI方法公式(10)和文献[16]中提出的DFS方法公式(11)均采用了这两个概率.

(10)

(11)

两个方法的核心部分都是概率P(ti|Ck)和P(Ck|ti),区别在于引入了不同的平滑因子.

3.4 基于段落分布及类别分布的特征选择方法

研究已证明概率P(ti|Ck)和P(Ck|ti)能够刻画特征ti对类别Ck的代表能力和对各类文档的区分能力.但在现有的方法中大多用特征的文档频率来描述这两个概率.特征的文档频率并没有考虑特征在文档中的分布情况,也就是说文档频率并不能区分特征是在整个文档中是均匀出现还是集中出现在文档中的某个部分.因此,基于文档频率的特征选择方法并不满足3.1节中特征选择的原则(1),而本文3.2节中提出的特征的段落频率充分考虑了特征在文档中的均匀分布程度.

为了满足3.1节中特征选择的3个原则,用特征的段落频率,即公式(7)中的CPF(ti,Ck),来替换公式(8)和公式(9)中的文档频率,重新定义概率P(ti|Ck)和P(Ck|ti)如公式(12)和公式(13)所示.

(12)

(13)

根据公式(12)和公式(13),我们定义基于段落分布和类别分布的特征选择函数FSPC为:

(14)

通过公式(14)可以计算得到特征ti对类别Ck的重要性得分,然后利用最大化的方法得到ti在训练集所有类别中最大的重要性得分,并将其作为ti在整个训练集中的重要性得分,如公式(15).

(15)

根据函数FSPC(ti)对特征进行降序排列,选择函数值大的特征作为特征选择结果.

4 实验与分析

4.1 实验设置

实验使用复旦数据集*http://www.nlpir.org/download/tc-corpus-answer.rar和搜狐新闻数据集*http://www.sogou.com/labs/resource/cs.php作为实验数据,通过选择不同数量的文档构造了一个均衡和一个相对失衡的复旦数据集,数据的具体描述如表1所示.搜狐新闻语料库选择Business,Yule,Learning,Fund,Sport,Music,Dealer,Digi 8个类别,每类800篇作为训练集,200篇作为测试集.

采用支持向量机[17]和朴素贝叶斯[18]作为文本分类器,将本文提出的方法FSPC与CHI square,DF,IG和CMFS四种特征选择方法进行实验对比分析,将F1值[19]作为评价指标.

实验采用eclipse和weka作为实验平台,利用中科院分词系统*http://ictclas.nlpir.org/newsdown loads?DocId=389进行分词,并根据中文停用词表去停用词,只保留汉字且长度大于1的词项,并删除文档频率低于3的词,采用归一化的TFIDF方案[10]对文档进行加权表示.

表1 复旦数据集
Table 1 FuDan datasets

ImbalancedFuDanbalancedFuDanClassTrainTestTrainTestArt450150450150Computer450150450150Sport450150450150Agriculture450150450150Policy750250450150Economic1200400450150Count375012502700900

4.2 实验结果分析

为了分析各种特征选择方法的性能,本文参照文献[7-11,13-16]将选择的特征数目设置为50,100,200,400,600,800,1000,1200,1400,1600,1800,2000,3000,4000和5000.

4.2.1 均衡复旦数据集上实验结果分析

下页表2给出了在均衡数据集上支持向量机和朴素贝叶斯分类器的实验结果.分类性能的变化曲线如图1和图2所示.

对于支持向量机分类器,从整体上看,CMFS和FSPC都优于CHI Square,DF和IG,而FSPC优于CMFS.特征数目为200时,FSPC达到了最佳性能,F1值为96.9%,而CMFS达到最佳性能时(F1值为96.8%),特征数是1000.CHI Square,DF和IG分别在特征数为1000,600和1600时达到其峰值96.3%,95.5%和94.9%.

对于朴素贝叶斯分类器来说,CMFS和FSPC都优于CHI Square,DF和IG,而FSPC优于CMFS.特征数为400时,FSPC的分类性能达到最高值92.9%.CMFS达到它的最高性能时,F1值为92.1%,特征数为1600.

4.2.2 非均衡复旦数据集上实验结果分析

表3给出了在失衡数据集上支持向量机和朴素贝叶斯分类器的实验结果.分类结果变化曲线如下页图3和图4所示.

表2 在复旦均衡数据集上分类器支持向量机(a)和朴素贝叶斯(b)的F1值(%)
Table 2 F1 (%) measure on the balanced FuDan dataset using (a) SVM and (b) Naïve Bayes

Featuresize50100200400600800100012001400160018002000300040005000(a)IG74．675．777．282．991．192．292．993．994．794．994．893．392．491．892．2DF81．183．189．694．495．594．394．695．595．295．295．493．892．692．392．6CHISquare85．689．393．495．195．896．196．396．295．995．395．694．093．993．092．7CMFS89．093．896．796．596．496．696．896．396．196．095．894．594．293．893．4FSPC92．094．196．996．796．696．896．596．496．296．195．994．794．393．993．8(b)IG62．864．164．771．177．378．882．282．283．683．383．581．478．478．878．1DF71．772．778．583．384．684．185．886．285．685．687．284．582．381．580．4CHISquare71．476．684．386．089．691．491．290．590．590．090．788．187．987．387．2CMFS83．486．589．690．289．590．491．191．791．392．191．990．790．289．588．9FSPC86．087．990．792．992．091．491．992．192．491．891．890．389．689．990．1

图1 在均衡数据集上支持向量机的F1值(%)变化曲线Fig.1 F1 (%) measure curves on the balanced FuDan dataset using SVM

图2 在均衡数据集上朴素贝叶斯的F1值(%)变化曲线Fig.2 F1 (%) measure curves on the balanced FuDan dataset using naive bayes

Featuresize(a)50100200400600800100012001400160018002000300040005000(a)IG71．674．376．486．789．292．793．293．993．294．195．193．893．493．593．7DF73．577．585．892．093．094．694．194．694．795．394．592．893．594．593．8CHISquare87．691．692．095．096．096．795．996．396．095．996．094．393．894．294．4CMFS90．893．995．795．996．096．296．496．696．096．295．594．594．894．994．4FSPC92．894．796．096．996．996．996．596．496．396．296．094．894．394．194．2(b)IG58．759．361．473．077．079．380．682．381．683．382．680．779．278．678．1DF70．071．174．079．881．484．984．284．384．785．284．781．181．179．479．3CHISquare70．781．581．985．788．688．889．288．488．988．288．289．290．590．490．2CMFS86．988．688．487．687．889．088．588．388．288．988．789．489．690．290．1FSPC88．989．089．690．690．690．790．890．790．489．989．889．989．789．689．4

就支持向量机分类器的性能来说,CMFS和FSPC都优于CHI Square,DF和IG,而FSPC优于CMFS.特征数目为400时,FSPC取得了最佳性能,F1值为96.9%.CMFS达到了它的最佳性能时,F1值为96.6%,特征数为1200.

就朴素贝叶斯分类结果来说,CMFS和FSPC都优于CHI Square,DF和IG.特征数为1000时,FSPC的分类性能达到峰值90.8%.CMFS取得的最佳结果时,F1值为90.2%,特征数为4000.

4.2.3 搜狐新闻数据集上实验结果分析

表4给出了在搜狐新闻数据集上支持向量机和朴素贝叶斯分类器的实验结果.分类性能的变化曲线如图5和图6所示.

对于支持向量机分类器,从整体上看,FSPC优于CMFS,CHI Square,DF和IG.特征数目为800时,FSPC达到了最佳性能,F1值为92.5%,其它方法在特征数少于或等于800时均未能取得这样的性能.此外,通过性能变化曲线我们可以发现,随着特征数目的增加分类性能没有明显的提升.

图3 在失衡数据上支持向量机的F1值(%)变化曲线Fig.3 F1 (%) measure curves on the imbalanced FuDan dataset using SVM

对于朴素贝叶斯分类器来说,特征数为3000时,FSPC的分类性能达到最高值88.3%,之后趋于平缓.其它方法也未能在特征数少于3000时超越FSPC.

图4 在失衡数据上朴素贝叶斯的F1值(%)变化曲线Fig.4 F1 (%) measure curves on the imbalanced FuDan dataset using Naive Bayes

从上述实验结果可以看出,分类器的性能基本呈现先升后降或趋于平稳的趋势,这说明特征数目过少时,所选的特征无法精确描述文档的语义,但如果特征数目过多,选择的特征会包含一些噪声,也会影响文档的语义描述.从整体性能来说,CHI Square、DF和IG的性能都不及CMFS和FSPC两种方法,而本文提出的FSPC方法总能够以最少的特征数目获得最好的分类性能,这充分验证了FSPC方法能够选择最有效的文本特征,并剔除冗余的噪音特征.

表4 在搜狐数据集上分类器支持向量机(a)和朴素贝叶斯(b)的F1值(%)
Table 4 F1 (%) measure on SogouCS dataset using (a) SVM and (b) Naïve Bayes

Featuresize(a)50100200400600800100012001400160018002000300040005000(a)IG57．667．579．586．888．889．589．990．189．990．090．590．891．291．591．4DF84．087．589．790．891．091．491．191．391．391．291．391．691．691．491．6CHISquare85．988．289．190．691．391．992．091．991．892．092．092．091．992．092．2CMFS85．989．290．191．191．592．392．592．392．292．291．892．192．092．292．2FSPC86．189．390．791．491．892．592．392．092．192．192．392．291．791．691．8(b)IG49．959．368．476．179．681．883．884．584．985．085．685．585．786．086．0DF73．381．083．184．485．085．886．086．786．587．087．187．387．387．187．5CHISquare71．079．276．679．381．984．184．685．186．087．786．787．087．787．788．2CMFS69．477．080．884．685．186．387．187．487．487．787．887．888．188．288．3FSPC73．381．483．485．486．287．287．687．988．188．188．287．988．388．388．2

图5 在搜狐数据上支持向量机的F1值(%)变化曲线Fig.5 F1 (%) measure curves on SogouCS dataset using SVM

5 结束语

针对现有特征选择方法没有利用特征在文档段落中分布信息的问题,本文充分考虑特征的段落分布和特征的类内和类间的分布,提出了一种新的特征选择方法FSPC.提出的方法可以选择出在文档中均匀分布的特征,在特定类别中频繁出现的特征,并剔除在整个语料库的各类文档中都频繁出现的无用特征.在真实数据集上,采用支持向量机和朴素贝叶斯分类器进行实验,将文本提出的FSPC方法与CHI Square,DF,IG和CMFS四种特征选择方法进行实验对比分析.实验结果验证了本文提出的特征选择方法的有效性.下一步工作的重点是研究文本内容的主题检测方法,应用这些方法更加细致地划分文档结构,从而进一步提高特征选择效率.

图6 在搜狐数据上朴素贝叶斯的F1值(%)变化曲线Fig.6 F1 (%) measure curves on SogouCS dataset using Naive Bayes

[1] Lopes L,Fernandes P,Vieira R.Estimating term domain relevance through term frequency,disjoint corpora frequency-tf-dcf [J].Knowledge Based Systems,2016,97(C):237-249.

[2] Lan M,Tan C L,Su J,et al.Supervised and traditional term weighting methods for automatic text categorization [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(4):721-735.

[3] Chen Ke-wen,Zhang Zu-ping,Long Jun,et al.Turning from TF-IDF to TF-IGM for term weighting in text classification[C].Expert Systems with Applications,2016,66(C):245-260.

[4] Pinheiro R H W,Cavalcanti G D C,Ren T I.Data-driven global-ranking local feature selection methods for text categorization [J].Expert Systems with Applications,2015,42(4):1941-1949.

[5] Xiao Yi-nan,Xie Rong,Du Juan.Feature selection method for data classification based on t-test and elastic net [J].Journal of Chinese Computer Systems,2015,36(10):2213-2217.

[6] Yang Yi-ming,Pedersen Jan O.A comparative study on feature selection in text categorization [C].In Proceedings of the 14th International Conference on Machine Learning,1997,4(3):412-420.

[7] Yang Jie-ming,Liu Yuan-ning,Zhu Xiao-dong,et al.A new feature selection based on comprehensive measurement both in inter-category and intra-category for text categorization [J].Information Processing and Management,2012,48(4):741-754.

[8] Zhou Hong-fang,Guo Jie,Wang Ying-hui.A feature selection approach based on term distributions [J].Springerplus,2016,5(1):1-14.

[9] Wang De-qing,Zhang Hui,Liu Rui,et al.t-Test feature selection approach based on term frequency for text categorization[J].Pattern Recognition Letters,2014,45(11):1-10.

[10] Ogura H,Amano H,Kondo M.Feature selection with a measure of deviations from Poisson in text categorization [J].Expert Systems with Applications,2009,36(3):6826-6832.

[11] Azam N,Yao Jing-tao.Comparison of term frequency and document frequency based feature selection metrics in text categorization[J].Expert Systems with Applications,2012,39(5):4760-4768.

[12] Xue Xiao-bing,Zhou Zhi-hua.Distributional features for text categorization [J].IEEE Transactions on Knowledge and Data Engineering,2009,21(3):428-442.

[13] Uysal A K,Gunal S.A novel probabilistic feature selection method for text classification[J].Knowledge Based Systems,2012,36(6):226-235.

[14] Rehman A,Javed K,Babri H A,et al.Relative discrimination criterion-A novel feature ranking method for text data[J].Expert Systems with Applications,2015,42(7):3670-3681.

[15] Shang Wen-qian,Huang Hou-kuan,Zhu Hai-bin,et al.A novel feature selection algorithm for text categorization[J].Expert Systems with Applications,2007,33(1):1-5.

[16] Zong Wei,Wu Feng,Chu LapKeung,et al.A discriminative and semantic feature selection method for text categorization[J].International Journal of Production Economics,2015,165:215-222.

[17] Wang Zhen-fei,Liu Kai-li,Zheng Zhi-yun,et al.Prediction retweeting of microblog based on logistic regression model[J].Journal of Chinese Computer Systems,2016,37(8):1651-1655.

[18] Zhang Lun-gan,Jiang Liang-xiao,Li Chao-qun,et al.Two feature weighting approaches for naive Bayes text classifiers[C].Knowledge Based Systems,2016,100(C):137-144.

[19] Kim H K,Kim M.Model-induced term weighting schemes for text classification[J].Applied Intelligence,2016,45(1):30-43.

附中文参考文献：

[5] 肖忆南,谢 榕,杜 娟.基于t检验和弹性网的数据分类特征选择方法[J].小型微型计算机系统,2015,36(10):2213-2217.

[17] 王振飞,刘凯莉,郑志蕴,等.基于逻辑回归模型的微博转发预测[J].小型微型计算机系统,2016,37(8):1651-1655.