一种基于黏液菌觅食机制的特征选择算法及其在文本情感识别中的应用

徐济惠,颜晨阳

(宁波城市职业技术学院 信息与智能工程学院,浙江 宁波 315211)

文本情感分析指的是从文本中提取情感信息,进而对文本感情极性进行分类。词袋模型(Bag of words,BOW)结合各类机器学习分类算法是目前进行文本情感分析的主要方法之一,但词袋模型可能会生成维度极高、冗余度极大,甚至包含了许多噪声的特征空间,将这些特征直接用于机器学习分类算法会造成“维度灾难”,且会造成数据处理中所谓GIGO(Garbage in,garbage out)[1]的后果,特征选择正是解决这一问题的有效工具。

特征选择实际上是一类子集求解问题(Sub set problem,SSP),且是一个NP-hard问题[2]。常见的特征选择方法可以分为三类[3]:(1)过滤方法(Filter),也即采用某种指标计算对每个特征评分,由高到低选择特征,特征选择过程与后续分类模型无关。常见的有reliefF系列算法[4]、基于粗糙集理论(Rough set theory)[5]、相关系数(Correlation coefficient)[6]、互信息(Mutual information)[7],卡方检验(Chi squared test)[8],信息增益(Information gain)[9],词频-逆文档频率(tf-idf)[10]等等的方法。(2)基于封装器的方法(Wrapper),即在候选集合中搜索使用特定分类模型能够获得最好性能的特征子集,封装器方法往往和具体启发式搜索算法[11],尤其是一些集群仿生优化算法[12,13]结合在一起,如进化算法[14,15]、粒子群优化算法[16,17]、蚁群优化算法[18,19],以及其他各类启发式算法[20-22]。(3)嵌入式方法(Embedded)。嵌入式选择是将特征选择过程与学习器训练过程融合为一体,两者在同一个优化过程中完成,即在学习器训练过程中自动地进行了特征选择。最典型的就是基于L1正则化的学习方法,如LASSO[23]和l1-SVM[24]等。

本文将提出一种模仿黏液菌觅食决策的特征选择算法(Slime-FS),这种算法大体上仍是一种封装方法,但也有过滤方法的一些特点。在具体构建和实现层面上,算法模仿了一种黏液菌(Slime mold)的觅食的动力学过程,以期获得冗余度更小和噪声更少的特征子集。本文将阐述Slime-FS算法的框架和具体实现,并将其应用到了慕课评论文本情感分析中,在实验中与遗传特征选择算法、粒子群特征选择算法和蚁群优化特征选择算法进行了对比。

1 黏液菌启发

研究表明,被认为没有任何智力的一些物种都拥有与环境交互并解决相对复杂问题的能力[25]。其中最为特别的是一种称为多头绒泡菌(Physarum polycephalum)的黏液菌,这是一种介于原生动物和真菌之间的多核单细胞生物,但却拥有解决一些特定复杂问题的能力,这些能力至少部分地源于其特殊的生理和运动觅食机制。多头绒泡菌形态为网状,网络的管道由细胞质流通构成,觅食得到的营养和生物化学信号可以通过这些管道进行传递,同时这些细胞质管道能够形成伪足按照一定的规则感知并探索周边环境。到目前为止,研究发现其至少拥有如下能力:迷宫寻径[26]、路径寻优[27]、多目标寻优[28]、预测周期性事件[29]、构建复杂网络[30]、拥有外部记忆[31],甚至展现出了进行探索利用权衡决策(Exploration-exploitation tradeoff)以获得最大收益的能力[32]。其中本文最为感兴趣的是Nakagaki、Fricker等所开展的关于黏液菌构建复杂网络研究[30]。这项研究仿照日本东京周边地理搭建了模型,将黏液菌置于东京位置展开觅食,其他每一个城市则以一块食物作为标志,并以黏液菌不喜的灯光强度来模仿地形与障碍,黏液菌形态最终会收敛为“城市”间的网状通道,且这一网络与现实中东京周边的铁路网络的效率、容错率和开销惊人地一致,如图1所示[30]。

图1 黏液菌网络觅食进化动态模拟图

图1中t表示进化时间,黏液菌最终收敛成为一个与东京周边的铁路网络几乎没有差别的网络。正是受该模型启发,本文将特征选择这一最优子集求解问题转化为求最优子图问题。将候选特征集合中的特征视为一张无向完全图中的顶点,也是黏液菌食物所在,黏液菌在这张图上通过各条边按照一定规则来流通觅食,黏液菌最终收敛构成一张完全子图,该子图上的所有顶点就是所求的特征子集,如图2所示。

图2 模仿黏液菌解觅食运动行为来决特征选择问题的示意图

图2中每个顶点都表示一个候选特征,也是黏液菌食物所在。所有顶点是候选特征集合,模拟黏液菌在该图上运动觅食。如果设计规则合理,可预期与构建交通网络一样,黏液菌形态最终将收敛成为一个子图,该子图上所有顶点即为被选择的特征子集。本文将这种模型称为基于黏液菌觅食决策的特征选择算法(Slime-FS)。算法虽然受启发于Nakagaki等提出的模型[33],在方法论层面上有所相似,但在算法的具体构建和实现层面上却大相径庭。

2 算法构建

2.1 问题简述

2.2 算法框架

Slime-FS算法引入一个特征图G,这个图中每个顶点Vi(0

表1 Slime-FS算法框架

2.3 预处理

(1)分词。本文选择了“结巴中文分词”[34]作为分词工具。

(2)去除停用词(Stop words)。利用中科院计算所中文自然语言处理开放平台发布的1 208个停用词的中文停用词表[35]。

(3)特征提取。使用Scikit-learn[36]中所提供的tf-idf特征权值计算来实现:BOW模型中第i个词(特征)的权值wi为语料库所有文本向量中该词(特征)的L2正则化的tf-idf值的平均,因此这个权值wi的范围为wi∈[0,1)。算法设置了一个阈值t,所有权值低于t的词(特征)都将被过滤掉。

(4)分类器确定。情感分类问题的最终结果主要在于特征提取的质量。但为了比较起见,算法仍然使用了两种不同的分类器:①支撑向量机,采用的是LIBLINER[37]中的L2-regularized L2-loss SVC实现;②朴素贝叶斯分类器,采用的是Scikit-learn[36]中的Multinomial Naive Bayes实现。

2.4 初始化

2.5 流量计算(flow)

首先算法为了方便起见,引入一个虚拟顶点V0,这个是菌落觅食的起点,那么过程flow(V,D)具体步骤如下:设Pk(t)为菌落k当前已经流经的顶点集合,Duv为顶点Vu到顶点Vv的导通性,那么算法将概率P的按式(1)确定性选择下一个顶点Vw

(1)

并且以概率1-P按照式(2)概率性地选择下一个顶点Vw

(2)

式中:m为参数,规定了菌落最多流经的顶点数目,如果m=|S|,那么即表示上限即为所有待选顶点(特征)数目。

最直观地,可以使用特征的tf-idf值作为算法中的特征Vv回报值Rv(Pk(t)),所有的特征if-idf值都已经在预处理中计算完成了,因此计算开销为零,但tf-idf也不能特别有效地反映在Pk(t)构建完成情况下,增加词特征Vv所带来得回报。因此,算法引入了粗糙集中的属性依赖度(Attribute dependencies)概念,计算特征Vv(条件属性)在Pk(t)(关系)下关于分类(决策属性)的重要性(Significance)作为算法中的特征回报值Rv(Pk(t)),由于有指数复杂度,在预处理中计算好所有的特征回报值是不可行的,因此将实时计算特征回报值(可将缓存以备下次用到)。至于导通性Duv(t)将在下面一节中进行详细阐述,式(2)中的α是用于调节导通性与回报值重要性的参数。

如果菌落连续10次选择的顶点获得的短期回报值都小于流通回报阈值ε,这时菌落的本次流通就结束了。或在若干次流通后,由于导通性的收敛,与剩余顶点相关的边上的导通性都变成0了,菌落的本次流通自然也就结束了。

2.6 导通性计算(renew)

根据文献[33]构建的模型的假设,黏液菌从顶点Vi到顶点Vj流的导通性在时间上和流量存在着如式(3)所示的关系,其中的f(Qij)是一个递增的函数,且f(0)=0,r是一个用于调节导通率的参数,0

(3)

本文模型中也引入了这个假设,由于本文的模型是离散的,因此获得了如式(4)所示的关系

Dij(t)=f(Qij(t-1))-Dij(t-1)e-r

(4)

算法中f(Qij)定义如式(5)所示

(5)

2.7 算法时间复杂度分析

与算法时间复杂度相关的参数有:最大迭代次数I、菌落数n、特征数m和训练样本样例集合数目N。

表2 算法时间复杂度上限

从表2可知,如果使用重要性来计算特征回报值的话,理论上算法时间复杂度还是相当高的,但本文前面提到过的样本E为典型的稀疏矩阵,样本向量的平均非零特征数一般要远远小于所有特征数量m,且在实际中也远远小于样本数目N,因此算法的实际时间复杂度要远低于其理论值。因为对课程的评论都不会很长,数据中文本平均包括21.0个有效词,而样本数要大2到3个数量级。

3 实验与结果

3.1 实验数据

原始语料库来自于用Scrapy爬虫[38]对中国大学慕课平台中《Linux系统管理》等三门课程的历史评论数据的爬取,并使用HTMLParser和正则表达式等工具对原始语料进行了清洗,随机抽取了其中一部分作为测试数据,经过人工情感标注、分词、去除停用词和特征提取后(经过调适,算法将特征提取的权值过滤阈值t设为0.6),对于实验中的语料库,可以过滤掉大约5/6左右的低权值特征。

测试数据集具体情况如表3所示。

表3 测试数据集

3.2 对比算法

主要的比较对象是启发式(Metaheuristic)的封装器算法。首先使用不带特征选择的SVM和NB算法作为比对基准,4个对比算法分别如下:Sklearn-genetic[39],scikit-learn包中的遗传特征选择模块;Entropy Weighted Genetic Algorithm[40],一种使用特征信息增益作为启发信息的遗传特征选择算法;Multi-Swarm PSO[17],一种多种群的粒子群特征选择算法;Ant Colony Optimization[18],一种基于蚁群优化的特征选择算法。

3.3 实验参数

本算法的参数有:最大迭代次数I、菌落数n、流通确定性概率P,流通回报阈值ε,导通权值α,回报权值λ。在本文的实验中,本算法参数均设置如下:最大迭代次数I=100;菌落数n=20;流通确定性概率P=0.2;流通回报阈值ε:如果短期回报采用的是特征的L2正则化tf-idf均值的话,ε=0.65,如果短期回报采用的是特征在当前已选顶点集合下关于分类的重要性的话,ε=0.001;导通率调整参数r=0.5;导通权值α=2;回报权值λ=0.4。

本文并没有针对算法的参数进行特别的优化,只是根据若干次调试的经验确定的较优的值。

同时,对照算法的各项参数设置都参考了各自文献中的设定。

EWGA参数设置如下[15]:(1)迭代次数I=200;(2)种群大小population=50;(3)交叉率crossover0.6;(4)变异率mutation=0.01;(5)变异常数 mutation operator constant=0.1。

Sklearn-genetic参数设置如下[39]:(1)迭代次数generation=50;(2)种群大小n_population=200;(3)交叉率crossover_proba=0.5;(4)变异率mutation_proba=0.2;(5)crossover_independent_proba=0.5;(6)mutation_independent_proba=0.05;(7)进化到下一代的个体数目tournament_size=5。

MSPSO参数设置如下[17]:(1)种群数目T=5;(2)种群大小m=40;(3)迭代次数I=30;(4)惯性系数inertia coefficient=0.6893;(5)加速因子c1,c2=1.42964。

ACO参数设置如下[18]:(1)迭代次数I=50;(2)种群大小m=100;(3)信息素初始值τ0=1;(4)信息素与启发信息相对权值α=1,β=0.1。

基准算法和所有比对算法的分类器都使用到了前面提到的L2-regularized L2-loss SVC以及Multinomial Naive Bayes,其中SVC的惩罚系数C=0.8。各个算法使用的待选特征集合均为经过预处理后的特征集合。对于所有的测试算法包括对比算法都在测试数据集上进行了10重交叉校验(10-fold cross validation)。

3.4 结果与分析

本文将给出算法的试验结果并进行简要分析。首先给出是采用不同短期回报计算方法,即分别采用特征L2正则化的tf-dif平均值和特征重要性作为短期回报值,和不同分类器(L2-regularized L2-loss SVC和Multinomial Naive Bayes)的Slime-FS算法实验结果。

图3中虚线表示平均值(Mean),实线表示中位数(Median)。从图3可以看到,采用何种分类器对于最终分类性能的影响并不大,sig+NB和sig+SVC无论是平均值、中值还是整体表现都极其接近,tfidf+NB和tfidf+SVC亦是如此。但是,采用何种短期回报值计算方法对最终性能会产生一定影响,可以明显观察到tf-idf一组算法在性能上要稍稍差于sig组的算法。

图3 采用不同短期回报计算方法和不同分类器四类不同Slime-FS算法在10重交叉校验测试下的F1-measure值盒图

图4给出了4类SFS算法构建的特征子集中特征的平均数目随着迭代次数的变化。表4给出了4类SFS算法的平均执行时间。从图4中可以观察到,4个算法选择的特征平均数目最终都收敛在备选特征值的20%到35%之间,其中sig一组算法获得的特征子集要稍稍小于tf-idf一组的算法。

图4 4类不同Slime-FS算法在每次迭代中构建的特征子集平均特征数(占备选集合特征总数百分比)

表4 4类不同Slime-FS算法10次10重交叉校验测试平均执行时间

综合来看,sig一组的算法显然在本实验的数据集上能够获得性能更好且更加简洁的解。从表4中可以得知,算法性能上的提升是以计算复杂度提升为代价的,sig一组算法的 10次10重交叉校验测试平均执行时间大约是tf-idf一组的算法的两倍左右。

为了更加直观展示算法对于情感表达特征的选择能力,表5给出了Slime-FS(sig+SVC)在10重交叉校验测试中被选择概率平均值最高的20个特征,从表中可以观察到其中有12个特征(用#标识)本身就带有明确的感情色彩。

表5 Slime-FS在10次10重交叉校验测试中被选择概率平均值最高的20个特征

图5给出的是Slime-FS与基准算法NB、SVC,以及对比算法sklearn-genetic、EWGA、MSPSO和ACO 算法在10重交叉校验测试下的F1-measure值的盒图。Slime-FS中的虚线表示均值(mean),实线表示中位值(median)。可以观察到无论采用何种分类器,Slime-FS获得的F1-Measure值无论是平均值、中值还是总体分布都要远远优于基准算法、EWGA和sklearn-genetic;同时也要明显优于ACO;在平均值上要略优MSPSO,在中值和分布上仍明显优于MSPSO。

图5 Slime-FS和基准算法(NB、SVC)、sklearn-genetic、EWGA、MSPSO和ACO 算法分别使用两种不同分类器在10重交叉校验测试下的F1-measure值盒图

表6给出了各个算法(使用SVC作为分类器)在10次10重交叉校验测试中平均执行时间和获取特征子集中平均特征数(用占初始特征集的百分比来表示)。可观察到,在平均执行时间上,Slime-FS要劣于MSPOS和ACO,与sklearn-genetic基本持平,好于EWGA。在选择的特征子集大小上,Slime-FS要稍大于MSPOS,与ACO和sklearn-genetic基本持平,但小于EWGA。Slime-FS在产生特征子集分类性能指标要优于MSPOS,但产生特征子集要略大于MSPSO,且算法执行时间更长,从降维(Dimension reduction)的角度来说,Slime-FS牺牲了一些算法时间性能作为代价,选择了更加合理的鉴别特征集合。在实际应用问题中,特征选择往往是数据预处理中的一个部分,最终分类性能往往比时间性能更重要。因此,可以从某种程度上认为Slime-FS的性能要优于MSPOS。

表6 各个算法在10次10重交叉校验测试中平均执行时间和获取特征子集中平均特征数

综合上面的对比测试结果可以合理地推断,Slime-FS在综合指标上不仅优于基准、sklearn-genetic、EWGA和ACO算法,而且也略优于MSPSO算法。

4 结束语

本文综述了特征选择问题及当前研究现状,阐述了黏液菌觅食决策和原理,论文提出了黏液菌觅食决策应当如何与特征选择问题相结合,进而在此基础上提出一种黏液菌觅食决策的特征选择算法Slime-FS,并将其应用在慕课评论的情感识别问题中。

论文阐述了算法及其参数设置,并用Slime-FS算法在某慕课平台实际慕课评论数据集上与EWGA、sklearn-genetic、MSPSO和ACO算法对比测试,结果表明了Slime-FS算法所采用策略能够指导算法对从候选特征集合中选择一个合理的特征子集,在训练数据集上能够获得良好的分类性能。从分类性能、时间性能的对比来看,Slime-FS算法无疑很好地达成了对数据集降维、过滤冗余、无关特征的预期目标。

当然,Slime-FS算法只是受黏液菌觅食行为启发的一个相对初步的特征选择算法,算法的可用性和可靠性也无法同已经大规模应用于实践中的成熟算法相比较。这个算法只是对于黏液菌觅食在特征选择中应用的初步探索。后续的研究中,一方面将对算法进行完善,另一方面也将对黏液菌觅食行为仿生算法进行进一步探索,使其能够应用到其他问题中去。