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)。王丹丹，碩士生，主研領域：智能計算，生物信息學。祖穎，碩士生。朱平，教授。