AABC-SVM模型及其在商品评论情感分类中的应用

王丹丹 祖 颖 朱 平

(江南大学理学院 江苏 无锡 214122)

AABC-SVM模型及其在商品评论情感分类中的应用

王丹丹 祖 颖 朱 平*

(江南大学理学院 江苏 无锡 214122)

为了提高商品评论情感分类准确率，解决传统SVM分类时参数难以选择问题，在基本人工蜂群算法基础上，提出一种改进人工蜂群算法AABC(Advanced Artificial Bee Colony)来优化支持向量机(SVM)参数。以最小化商品评论分类错误率为优化目标，在人工蜂群算法的引领蜂阶段引入监督-响应机制增强蜂群算法开发能力，在跟随蜂阶段改进概率选择作用保证蜜源个体的差异性，提高算法收敛速度，避免算法陷入局部最优。不同商品评论情感分类结果表明，相比于GA-SVM模型、PSO-SVM模型和ABC-SVM模型，所提出的AABC-SVM模型能够寻优到更好的SVM参数组合，其分类准确率平均多提高了1%～3%，验证了所提模型的有效性。

人工蜂群算法 支持向量机 商品评论 情感分类

0 引 言

随着互联网技术的不断发展，电子商务已成为人们生活中不可或缺的一部分，越来越多的消费者选择网上购物。与实体店购物不同，网上购物无法切身感受商品质量，难以准确判断商品性能，消费者只能通过其他消费者的网上评论了解产品信息。因此，如何对商品评论进行有效分析，合理选择商品成为消费者日益关注的问题。而商品评论情感分类通过提取商品评论的情感特征，能够有效地对商品评论进行褒贬性分析，为消费者购买商品提供辅助决策[1-3]。

目前，商品评论情感分类方法主要包括基于情感知识的分类方法[4-5]和基于机器学习[6-8]的分类方法，其中，基于机器学习的分类方法因无需复杂的语言结构知识，只需通过数据挖掘方法发现潜在语义信息分类而受到广泛关注。主要包括K最近邻法、朴素贝叶斯法以及支持向量机法等[9]，其中基于SVM的商品评论情感分类方法因其具有较高的分类精度，同时能够克服“过学习”和“欠学习”等问题而受到广泛关注，但SVM仍存在参数难以选择问题，一定程度上制约了其分类性能。近几年，有学者采用群智能算法对SVM参数进行优化取得了较好的效果，文献[10-12]分别采用遗传算法、粒子群算法和蚁群算法优化SVM参数并进行分类研究，不仅具有较高的分类准确度，而且具有良好的泛化性能，这表明群智能算法是解决SVM参数选择问题的有效途径之一。

而人工蜂群算法ABC(Artificial Bee Colony)作为一种新的群智能算法，因结构简单、参数较少和易于实现的良好特性受到青睐，与遗传算法、差分进化算法和粒子群优化算法相比，ABC算法的求解质量相对较好[13-14]。本文为了提升ABC算法优化SVM参数性能，提高SVM对商品评论情感分类的准确率，提出了一种改进ABC算法AABC以优化SVM参数，在基本人工蜂群算法的引领蜂阶段引入监督-响应机制以增强算法开发能力，在跟随蜂阶段改进概率选择作用保持种群间的差异性，有效避免算法陷入局部最优的同时加快算法收敛速度。对不同商品评论情感分类的结果表明，采用AABC-SVM模型具有较高的准确率和良好的泛化性能。

1 支持向量机

支持向量机是一种基于结构风险最小化原则的机器学习算法，通过寻找满足分类要求的最优分类超平面，在保证准确分类的基础上，使得两类数据点到超平面的距离最大[15]。对于线性不可分的样本数据，则是通过选择适当的核函数将样本数据映射到一个高维线性特征空间中，使其在高维空间中线性可分，从而构造最优分类超平面完成样本分类。

(1)

其中，w为超平面法向量；C>0为惩罚因子；ζ为松弛变量；b∈R为阈值。

上述二次规划问题的对偶问题为：

(2)

其中，α=(α1,α2,…,αl)为Lagrange乘子，α中不为零的系数称为支持向量；K(xi,xj)为核函数。

求解可得最优分类函数为：

(3)

SVM中常用的核函数有线性核函数、径向基核函数(RBF)、多项式函数和Sigmoid核函数。而实验表明核函数的具体形式对分类效果的影响不大，其核函数参数才是影响性能的关键因素[16]。本文选用SVM中应用广泛的径向基函数作为核函数，其公式为：

K(xi,xj)=exp(-‖xi-xj‖2/2σ2)

(4)

由式(4)可以看出径向基核函数受参数σ影响较大。而惩罚因子C影响着整个模型的拟合程度，对SVM分类性能有着至关重要的影响。因此，问题转化为如何寻找最优惩罚因子C和径向基核函数参数σ，使得SVM分类准确率最大。

2 人工蜂群算法及其改进

ABC算法是一种模拟蜜蜂采蜜行为的群体智能算法，该算法将蜂群分为引领蜂、跟随蜂和侦查蜂3类，并通过种群协同合作寻找最优蜜源[17]。在求解优化问题时，蜜源的位置表示潜在的可能解，蜜源质量的好坏表示所求解质量的优劣，以求解最小化问题为例，质量最好的蜜源就是所求问题的最小解。

对于一个优化问题，ABC算法首先随机产生N个D维蜜源，其中引领蜂和跟随蜂各占一半，表示蜜源位置(可行解)。引领蜂根据式(5)产生新的蜜源，计算蜜源更新前后的适应度值并进行贪婪选择，保留较好的蜜源。

vij=xij+rand×(xij-xkj)

(5)

其中，xij和vij分别为更新前后的蜜源，xkj为随机选择的蜜源，rand是[-1,1]之间的随机数。

跟随蜂根据引领蜂所产生的蜜源适应度信息，按照式(6)计算概率来选择是否对该蜜源进行深度搜索。

(6)

其中，fiti为第i个蜜源的适应度值。适应度值大的蜜源进行深度搜索的概率也越大。

当某个解经过一定次数的更新后，其解的质量仍未得到改善，此时，引领蜂将转化为侦查蜂，由式(7)重新产生一个新的蜜源。

xij=L+rand(0,1)×(U-L)

(7)

其中，L为所求解的下界，U为所求解的上界。

ABC算法虽然结构简单、性能优异，但其探索能力较强而开发能力不足，使得算法收敛速度较慢，容易陷入局部最优，出现“早熟”现象。本文为提高SVM的分类准确率，提升ABC算法对SVM参数的优化性能，对ABC算法在引领蜂、跟随蜂2个阶段的搜索策略进行改进。

在引领蜂阶段，基本的ABC算法每次迭代随机选择某一维分量进行更新，这种随机选择使得更新过程中对个体蜜源质量产生积极影响的分量难以在下次迭代继续搜索，而某些分量更新后未能提高蜜源质量，却在下次迭代中仍存在继续更新的可能，这样未能充分运用迭代过程中的有利信息，使得算法的收敛速度较慢，不利于求解。本文通过引入监督-响应机制对蜜源分量进行监督，在下一次迭代过程中通过判断监督器φ的状态选择是否对上次蜜源分量继续更新，如监督器φ=0则对上次蜜源分量继续更新，否则随机选择蜜源分量更新。其中，监督器φ的状态取决于上一次迭代过程中，该蜜源分量更新后蜜源质量是否提高，若提高则置监督器φ=0，否则φ=1。改进后的引领蜂更新方式有利于提高ABC算法的开发能力，加快算法收敛速度。

在跟随蜂阶段，跟随蜂根据一定概率选择是否对引领蜂蜜源进行搜索，概率的大小主要取决于引领蜂的蜜源质量，将直接决定跟随蜂能否对优异蜜源进行深度搜索。基本ABC算法的概率计算公式如式(6)所示，只有当蜜源之间的差异性较大时，不同质量的蜜源概率才有明显差别，且未能充分利用进化过程中的历史知识加强跟随蜂和引领峰之间的协同合作，发挥跟随蜂深度搜索作用，使得算法收敛速度变慢，极易陷入局部最优。因此，本文结合引领峰更新过程的监督器，对上一次迭代后质量未能提高的蜜源在跟随蜂阶段进行概率惩罚，改进后的概率公式为：

(8)

其中，Pi为第i个引领蜂蜜源概率，fi为第i个蜜源的适应度值，fmin为最小适应度值，η为概率惩罚参数，φi为第i个蜜源的监督器状态。由式(8)可以看出，改进后的概率公式充分利用了引领峰进化过程中的历史知识，对更新后质量未提高的蜜源进行概率惩罚，不仅能增强不同质量蜜源之间更新概率的差异性，而且能够加强跟随蜂和引领峰之间的协同进化，有利于保证优异蜜源得以进一步搜索，避免算法陷入局部最优。

3 改进人工蜂群算法优化SVM的商品评论情感分类

支持向量机中的惩罚因子C和径向基核函数参数σ对商品评论分类准确率具有较大影响，采用改进的人工蜂群算法对SVM参数进行优化进一步提高商品评论情感分类准确率。

具体步骤如下：

步骤1初始化参数。设种群数量为N，最大迭代次数为Max_it，蜜源淘汰次数为Max_trial；设置SVM惩罚参数C和径向基核参数σ的上下限，同时在其取值范围内随机产生N/2个蜜源，即(C,σ)组合，零初始化监督器SP={sp0,sp1,…,spN/2}。

步骤2引领蜂更新。每个引领蜂随机选择相邻蜜源并与其产生新蜜源，并通过判断监督器状态是否对上次蜜源分量继续更新，更新完成后，将更新前后的蜜源按照式(3)分别计算最优分类函数，并判断分类是否正确。为满足最小化目标的要求，以商品评论分类错误率为优化目标，即适应度函数，计算公式如下：

(9)

其中，E为分类错误率，T为分类正确的评论数，Q为总评论数。

步骤3跟随蜂的概率选择更新。采用改进后的概率选择式(8)计算蜜源概率，跟随蜂根据概率选择决定是否对该蜜源进一步更新。如需进一步更新，则按照步骤2中引领蜂更新方式进行更新。

步骤4侦查蜂转变更新。如果引领蜂和跟随蜂在达到Max_trial更新次数后，蜜源质量没有提高则认为该解陷入局部最优，引领蜂转变为侦查蜂重新产生新解。

步骤5判断是否达到最大迭代次数Max_it，如没有则返回步骤2，否则结束并输出SVM最优参数。

步骤6通过最优个体得到SVM参数(C,σ)，构造AABC-SVM分类器，得出最终分类结果。

4 实验结果分析

4.1 改进人工蜂群算法标准函数测试结果

为了验证以上对ABC算法改进的有效性，选取了以下三个函数进行测试。

(1) Sphere函数：

其中xi∈[-100,100]，n为变量维数。

(2) Rastrigin函数：

其中xi∈[-5.12,5.12]，n为变量维数。

(3) Griewank函数：

其中xi∈[-600,600]，n为变量维数。

将AABC算法与基本ABC算法进行比较，设置种群数量为50，最大迭代次数为3 000，蜜源淘汰次数为250，概率惩罚参数η为10，测试函数变量为30维，分别采用这2种算法在MATLAB上独立运行30次，测试结果如图1-图3所示。

图1 Sphere函数进化曲线

图2 Rastrigin函数进化曲线

图3 Griewank函数进化曲线

由图1-图3可以看出，无论是单峰函数Sphere，还是多峰函数Rastrigin和Griewank，本文所提的AABC算法相比于ABC算法，在收敛精度和收敛速度上都有所提高，尤其对于两个多峰函数，都能够快速寻找到理论最优点，而基本ABC算法，在到达一定收敛精度时，极易陷入局部最优。这是由于本文在引领峰阶段引入监督-响应机制加快了优异蜜源的更新速度，通过概率惩罚作用增大了种群个体差异，降低较差蜜源的更新概率，有效提高了解的收敛速度和精度。综合以上分析，表明AABC算法具有更加优异的寻优性能。

4.2 商品评论分类数据来源与实验设计

为了验证所改进人工蜂群算法优化SVM参数模型(AABC-SVM)能够有效提高商品评论分类准确率，本文选取中科院谭松波博士收集整理的实际商品评论作为实验原始语料数据集(http://www.nlpir.org)[18]，分别选取酒店、书籍和电脑商品评论500条、500条和1 000条，其中正面评论与负面评论各占一半，分别存储在pos和neg两个文件夹下。随机选取各数据集总评论的80%作为训练集，其余为测试集。使用武汉大学的ROST软件(http://download.csdn.net/tag/ROST)对3类商品评论进行分词，剔除停用词，统计词频等文本预处理操作，并根据极性词典选取各条评论的极性词，采用向量空间形式表示商品评论情感特征。

4.3 分类结果分析

本文将AABC-SVM模型与遗传算法优化SVM参数模型(GA-SVM)、粒子群算法优化SVM参数模型(PSO-SVM)以及传统蜂群算法优化SVM参数模型(ABC-SVM)作对比实验。实验中，SVM的惩罚参数C取值范围为C∈(0,10]，径向基参数σ取值范围为σ∈(0,1]；各算法的最大迭代次数设为30，种群数量设为10；GA算法的交叉概率设为0.8，变异概率设为0.01，PSO算法的学习因子设为c1=c2=2，ABC算法和AABC算法的蜜源淘汰次数为Max_trial=20，经多次实验，将AABC算法的概率惩罚参数η为10时求解结果较好。为使实验结果更加可靠，降低随机性带来的风险，分别将每种模型单独运行20次，记录每次分类准确率，计算20次分类准确率的均值和标准差，表1-表3分别为3个不同数据集采用不同模型的分类结果，其中worse和best为20次中最差和最好准确率，mean为均值，std为标准差。

表1 4种不同模型对酒店评论分类准确率比较 %

表2 4种不同模型对书籍评论分类准确率比较 %

表3 4种不同模型对电脑评论分类准确率比较 %

由表1-表3可以看出，相比于GA-SVM模型、PSO-SVM模型和ABC-SVM模型，所提出的AABC-SVM模型对酒店、书籍和电脑商品评论进行情感分类时，不仅具有较高的准确率，而且其分类结果的方差较小，说明所求结果的稳定性良好。同时表明所提出的改进人工蜂群算法优化SVM模型能够有效寻到最优参数组合，具有较强的寻优能力。此外，AABC-SVM模型对3类不同商品评论分类都取得了较好结果，这也表明所提模型的泛化能力较强，对不同数据类型和数据规模的依赖性较小，能够为商品评论情感分析提供有效的决策支持。

为了更加直观地分析每种模型的分类性能，将4种模型分别对3种不同数据集的迭代寻优过程绘制成图，如图4-图6所示。

图4 4种模型对酒店评论分类结果对比图

图5 4种模型对书籍评论分类结果对比图

图6 4种模型对电脑评论分类结果对比图

由图4-图6可以清晰地看出，采用4种模型分别对3类商品评论进行分类，其分类准确率都得到了一定程度的提高，但相比于GA-SVM模型、PSO-SVM模型和ABC-SVM模型，所提出的AABC-SVM模型能够寻优到更好的参数组合，使得SVM分类准确率更高。另外，可以看出AABC-SVM模型不仅具有较高的分类准确率，而且其寻优过程不易陷入局部最优，能够在较短的时间内取得较好的分类结果。综合上述分析，表明采用改进的人工蜂群算法优化SVM参数模型能够有效提高商品评论分类准确率。

5 结 语

针对采用SVM对商品评论情感分类时，其惩罚参数和核函数参数难以选择问题，提出了一种改进人工蜂群算法来优化SVM参数模型。考虑到人工蜂群算法存在“早熟”风险和开发能力不足的缺陷，本文通过在引领蜂阶段，引入监督-响应机制增强算法开发能力，在跟随蜂阶段改进概率选择作用增加蜜源差异性，提高算法收敛速度，避免算法陷入局部最优。对比GA-SVM模型、PSO-SVM模型和ABC-SVM模型在3个商品评论数据集的分类结果表明，所提出的AABC-SVM模型具有较高的分类准确率和较快的收敛速度，能够有效地对商品评论进行情感分类，为商品评论情感分类研究提供了一种新思路。后续将在本文基础上进一步考虑语义特征以提高商品评论情感分类准确率。

[1] Mudambi S M,Schuff D.What makes a helpful review? a study of customer reviews on amazon.com[J].MIS Quarterly,2010,34(1):185-200.

[2] 张紫琼,叶强,李一军.互联网商品评论情感分析研究综述[J].管理科学学报,2010,13(6):84-96.

[3] 林煜明,王晓玲,朱涛,等.用户评论的质量检测与控制研究综述[J].软件学报,2014,25(3):506-527.

[4] Chen C C,Tseng Y.Quality evaluation of product reviews using an information quality framework[J].Decision Support Systems,2011,50(4):755-768.

[5] Pang B,Lee L.Opinion mining and sentiment analysis[J].Foundations and trends in information retrieval,2008,2(1/2):1-135.

[6] 周杰,林琛,李弼程.基于机器学习的网络新闻评论情感分类研究[J].计算机应用,2010,30(4):1011-1014.

[7] Pang B,Lee L,Vaithyanathan S.Thumbs up? Sentiment Classification Using Machine Learning Techniques [C]//Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP’02),Stroudsburg,Philadelphia,USA.Stroudsburg:ACL,2002:79-86.

[8] 郝媛媛,叶强,李一军.基于影评数据的在线评论有用性影响因素研究[J].管理科学学报,2010,13(8):78-88.

[9] 唐慧丰,谭松波,程学旗.基于监督学习的中文情感分类技术比较研究[J].中文信息学报,2007,21(6):88-94.

[10] Abdullah S G,Azuraliza A B,Abdul R H.Hybrid feature selection based on enhanced genetic algorithm for text categorization[J].Expert Systems With Applications,2016,49:31-47.

[11] Bao Y,Hu Z,Xiong T.A PSO and Pattern Search based Memetic Algorithm for SVMs Parameters Optimization[J].Neurocomputing,2014,117(14):98-106.

[12] 高雷阜,张秀丽,王飞.改进蚁群算法在SVM参数优化研究中的应用[J].计算机工程与应用,2015,51(13):139-144.

[13] 秦全德,程适,李丽,等.人工蜂群算法研究综述[J].智能系统学报,2014,9(2):127-135.

[14] Li Xianneng,Yang Guangfei.Artificial bee colony algorithm with memory[J].Applied Soft Computing,2016,41:362-372.

[15] Li Huan,Chung Fulai,Wang Shitong.A SVM based classification method for homogeneous data[J].Applied Soft Computing,2015,36:228-235.

[16] 周绍磊,廖剑,史贤俊.基于Fisher准则和最大熵原理的核参数选择方法[J].控制与决策,2014,29(11):1991-1996.

[17] Gao Weifeng,Liu Sanyang,Huang Lingling.Enhancing artificial bee colony algorithm using more information-based search equations[J].Information Sciences,2014,270:112-133.

[18] 赵妍妍,秦兵,刘挺.文本情感分析[J].软件学报,2010,21(8):1834-1848.

ADVANCEDARTIFICIALBEECOLONYALGORITHMFORSVMOPTIMIZATIONANDITSAPPLICATIONONSENTIMENTCLASSIFICATIONOFPRODUCTREVIEWS

Wang Dandan Zu Ying Zhu Ping*

(SchoolofScience,JiangnanUniversity,Wuxi214122,Jiangsu,China)

In order to improve the accuracy of sentiment classification for online product reviews and solve the problem that the traditional SVM parameters are difficult to choose, based on the standard artificial bee colony algorithm, an advanced artificial bee colony (AABC) algorithm is proposed, which can further optimize the SVM parameter. This model puts the sentiment classification accuracy of the texts as the optimization objective. The supervision and response mechanism is adopted to enhance the capacity of population exploitation, and the probabilistic selection is enhanced to maintain the population diversity, thus it can effectively avoid the algorithm falling into local optimal. Compared to the GA-SVM model, PSO-SVM model and ABC-SVM model, experiments on different data sets, the AABC-SVM model can achieve better SVM parameters and the average classification accuracy increased by 1%～3%, which verifies the effectiveness of the proposed model.

Artificial bee colony algorithm Support vector machine (SVM) Product reviews Sentiment classification

TP18 TP391

A

10.3969/j.issn.1000-386x.2017.09.007

2016-09-08。国家自然科学基金项目(11271163)。王丹丹，硕士生，主研领域：智能计算，生物信息学。祖颖，硕士生。朱平，教授。