基于GA-IPSO-BSVM算法的新浪微博評論信息分類①

王嘉偉, 胡 曦, 丁子怡, 劉 雨

1(江漢大學(xué) 人工智能學(xué)院, 武漢 430056)

2(江漢大學(xué) 人工智能研究院, 武漢 430056)

隨著大數(shù)據(jù)時代的到來, 移動互聯(lián)網(wǎng)已融入到人們?nèi)粘Ｉ畹母鞣矫嬷衃1]. 截至2020年12月, 我國網(wǎng)民規(guī)模為9.89億, 互聯(lián)網(wǎng)普及率高達(dá)70.4%, 較2020年3月提升5.9個百分點(diǎn), 其中農(nóng)村網(wǎng)民規(guī)模為3.09億, 較2020年3月增長5 471萬; 農(nóng)村地區(qū)互聯(lián)網(wǎng)普及率為55.9%, 較2020年3月提升9.7個百分點(diǎn)[2].新浪微博(以下簡稱“微博”)作為一個流量較大的網(wǎng)絡(luò)社交平臺, 具有傳播速度快, 范圍廣, 監(jiān)管不嚴(yán)等特征,使微博稱為各類謠言的溫床. 《2021年2月微博辟謠月度工作報告》統(tǒng)計微博辟謠數(shù)據(jù)顯示, 2021年2月,微博站方共有效處理不實(shí)信息5 331條, 當(dāng)月發(fā)布微博辟謠信息51條. 微博辟謠及話題閱讀于2月1日至2月28日, 話題閱讀量增長0.6億, 總閱讀數(shù)93.9億[3].高便利性及樣本數(shù)量大導(dǎo)致輿情傳播的預(yù)防難度很大.此類信息造成了嚴(yán)重的社會負(fù)面影響, 帶來了極大的社會危害. 因此, 微博信息的分類及不良信息的快速定位和處理是社會關(guān)注的焦點(diǎn)問題之一.

1 相關(guān)工作

當(dāng)前針對微博信息分類及不良信息的快速定位和處理問題, 存在一系列文獻(xiàn)分析算法來處理高維微博信息數(shù)據(jù)[4–6], 如支持向量機(jī)(support vector machine,SVM)[7], 樸素貝葉斯(naive Bayesian)[8]. 其中, SVM作為一種高效的二分類模型, 由于其具有較好地解決少量樣本的精準(zhǔn)分類問題, 被廣泛應(yīng)用于處理各種分類問題. 蔡坤燁等[9]建立了基于 SVM 的多參數(shù)預(yù)測模型, 驗(yàn)證了該模型的有效性. Zhu等[10]提出了利用 SVM預(yù)測模型進(jìn)行在線診斷, 并驗(yàn)證了該方法的有效性.

而SVM的性能受其關(guān)鍵參數(shù)的影響較大, 需進(jìn)行參數(shù)尋優(yōu). Jiao等[11]提出利用改進(jìn)的狼群算法優(yōu)化SVM預(yù)測模型參數(shù). 黃斌[12]將改進(jìn)后的GM(1, 1)和SVM 進(jìn)行最優(yōu)化權(quán)重組合, 通過案例驗(yàn)證了該模型的有效性. Yang 等[13]提出了一種利用蟻群算法(ant colony optimization, ACO)來優(yōu)化 SVM 分類模型, 驗(yàn)證了該模型的有效性. 然而, 這些尋優(yōu)算法在處理高維微博信息數(shù)據(jù)仍存在一定的局限性, 如: GWO全局開發(fā)能力弱, 探索空間易重復(fù), 浪費(fèi)計算資源; ACO收斂速度慢,易陷入局部最優(yōu). 且上述基于SVM的分類方法均建立在完善的網(wǎng)絡(luò)數(shù)據(jù)條件下, 而真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)爬取當(dāng)中, 可能存在樣本數(shù)量不平均的現(xiàn)象, 會導(dǎo)致SVM出現(xiàn)較大的分類誤差問題. 因此, 本文提出非線性多分類均衡支持向量機(jī) (balanced SVM, BSVM) 以減小樣本量不平衡引起的誤差, 再采用遺傳-改進(jìn)粒子群優(yōu)化算法(genetic algorithm-improved particle swarm optimization,GA-IPSO) 優(yōu)化 BSVM 的參數(shù), 對微博評論數(shù)據(jù)進(jìn)行分類, 以獲得更好的分類效果.

2 問題描述

由于現(xiàn)實(shí)網(wǎng)絡(luò)中評論信息對時效性要求較高, 則快速準(zhǔn)確的分類算法對于微博輿情的控制具有重要意義. 此類算法可考慮兩方面內(nèi)容:

(1) 小樣本及時處理;

(2) 分類算法快速收斂.

在輿情傳播的前期收集樣本數(shù)據(jù)時, 由于評論信息相對較少, 可能出現(xiàn)樣本類數(shù)量相對不足且不均衡的情況. 針對該種情況下微博評論信息的及時分類問題, 本文提出BSVM以盡可能降低由于樣本量不均衡而引起的誤差, 從而提升分類準(zhǔn)確率. 此外, SVM的分類效果受其參數(shù)的影響較大, 本文通過GA-IPSO算法來優(yōu)化BSVM的關(guān)鍵參數(shù), 提出GA-IPSO-BSVM的微博評論分類模型, 其具體流程如圖1所示.

圖1 GA-IPSO-BSVM的微博評論分類模型

3 改進(jìn)粒子群優(yōu)化算法(GA-IPSO)

粒子群算法(particle swarm optimization, PSO)由Kennedy和Eberhar于1995年提出, 是一種基于群體智能進(jìn)化優(yōu)化算法[14]. 該算法通過分析模擬鳥群, 昆蟲, 魚群等動物種群的覓食習(xí)慣, 考慮將每個動物個體看成所求尋優(yōu)問題的一個解(即: 相當(dāng)于問題中的粒子), 每個粒子具有速度和位置兩個屬性值, 通過種群個體間的合作, 種群之間的信息共享來尋找所求問題的最優(yōu)解, 用于求解優(yōu)化問題. 其表達(dá)式為式(1)和式(2):

由于PSO算法在收斂過程中存在大量聚集的低速粒子, 這些粒子既不加速算法的收斂也無法探索新區(qū)域, 導(dǎo)致粒子陷入局部最優(yōu)的概率較高, 且在迭代過程中仍消耗了大量資源, 降低了算法的收斂速度. 此外,PSO是一種易陷入局部最優(yōu)的算法模型, 導(dǎo)致算法無法實(shí)現(xiàn)全局最優(yōu).

基于上述兩個問題為克服微博評論信息快速分類,本文提出了兩種改進(jìn)方法:

1) 引入粒子淘汰機(jī)制. 在訓(xùn)練的迭代初期, 出現(xiàn)收斂趨勢時, 存在大量的低速且遠(yuǎn)離最優(yōu)解的粒子, 而這些粒子的探索范圍常遠(yuǎn)離最優(yōu)解范圍, 迭代其所需大量的計算量且收益率低, 于是在迭代前期采用GA算法, 通過粒子淘汰機(jī)制, 在迭代前期定期將適應(yīng)度最差且速度最慢的粒子淘汰刪除, 節(jié)約系統(tǒng)資源并極大加速收斂速度.

2) 改變粒子的拓?fù)浣Y(jié)構(gòu). 當(dāng)GA迭代次數(shù)D為:

其中,Tmax為粒子迭代次數(shù)上限,n為所求粒子維度數(shù).定義在第D次迭代時結(jié)束GA算法的迭代, 將所有的粒子進(jìn)行K-means聚類, 設(shè)置類別數(shù)量為2n.

當(dāng)粒子完成聚類后按照聚類結(jié)果進(jìn)行PSO算法,每個粒子在當(dāng)前社區(qū)進(jìn)行尋優(yōu), 最終各區(qū)域最優(yōu)粒子組成為優(yōu)秀群體的初始粒子種群開始PSO算法, 該算法的優(yōu)勢為: 即使存在社區(qū)的粒子陷入局部最優(yōu), 其他社區(qū)的粒子仍然能夠在解空間內(nèi)繼續(xù)尋找最優(yōu)解, 較好地保證了解的全局最優(yōu)性.

在引入上述兩種改進(jìn)機(jī)制后, 本文提出粒子群算法的改進(jìn)GA-IPSO算法. 首先該算法在粒子迭代的迭代前期使用GA算法, 在粒子迭代過程中刪除掉適應(yīng)度相對較差或邊緣的惰性粒子, 其次在迭代中期進(jìn)行K均值聚類算法對于剩余粒子進(jìn)行粒子分區(qū), 在每個社區(qū)中進(jìn)行粒子群算法直到粒子收斂. 最后在迭代后期將所有社區(qū)中最優(yōu)粒子組合成一個新的優(yōu)秀粒子群體進(jìn)行最終迭代, 獲取最優(yōu)解.

GA-IPSO算法步驟可以描述為:

(1) 初始化解空間中所有的初始粒子種群.

(2) 將粒子種群進(jìn)行GA算法進(jìn)化, 在該進(jìn)化過程中, 分別記錄不同迭代次數(shù)下不同粒子不同位置的適應(yīng)度, 并將適應(yīng)度進(jìn)行排序.

(3) 按照粒子淘汰機(jī)制所設(shè)定的淘汰比例將適應(yīng)度最低的批次粒子定義為惰性粒子.

(4) 刪除惰性粒子, 并將剩下粒子種群定義為活躍粒子種群.

(5) 將活躍粒子種群進(jìn)行K-均值聚類, 種群依照聚類結(jié)果進(jìn)行社區(qū)劃分, 定義為: 活躍A社區(qū), 活躍B社區(qū), …, 活躍N社區(qū).

(6) 每個粒子在其所在社區(qū)中進(jìn)行PSO算法的迭代, 直到算法收斂或達(dá)到最大迭代次數(shù), 再定義各自社區(qū)中所有粒子位置中適應(yīng)度最高的位置為優(yōu)秀粒子,并記錄為: A社區(qū)優(yōu)秀粒子, B社區(qū)優(yōu)秀粒子, C社區(qū)優(yōu)秀粒子, …,N社區(qū)優(yōu)秀粒子.

(7) 將所有的優(yōu)秀粒子組成為粒子群體, 定義為優(yōu)秀群體, 優(yōu)秀群體進(jìn)行PSO算法迭代, 直至算法收斂或達(dá)到最大迭代次數(shù), 從而得到最優(yōu)解.

4 非線性多分類均衡支持向量機(jī)(BSVM)的建立

4.1 SVM簡介

SVM算法是Vapnik于1995年提出的一種基于統(tǒng)計學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法[15]. 其結(jié)構(gòu)簡單, 訓(xùn)練時間少, 具有良好的泛化能力, 所需的訓(xùn)練樣本少, 精度也較高, SVM分類的基本思想可表述為: 給定兩類樣本點(diǎn), 尋找最優(yōu)線性超平面使兩類樣本點(diǎn)分離, 且最大化超平面和距離分類平面最近的樣本點(diǎn)之間的距離.

在線性可分條件下, SVM可表述為:

對于給定數(shù)據(jù)集:

分類超平面的函數(shù)為:

歸一化處理之后, 滿足:

其中,x是輸入向量;w是權(quán)重向量;b是分類閾值. 整理后可將求取該超平面的問題轉(zhuǎn)化為求解問題:

對于線性不可分條件下, 引入懲罰因子C和松弛變量ξi≥0,C為懲罰系數(shù), 主要用于平衡支持向量的復(fù)雜度和誤分類率兩者的關(guān)系. 其中,C太大會引起過擬合,C太小會導(dǎo)致模型的泛化能力差. 若所有樣本都被準(zhǔn)確分類, ξi=0, 反之,此外, 對于上述凸優(yōu)化問題的求解, 引入拉格朗日乘子法轉(zhuǎn)化為求其對偶問題, 最終優(yōu)化分類函數(shù)為:

將高維空間中的點(diǎn)積運(yùn)算替換成核函數(shù):

則最優(yōu)分類函數(shù)可表示為:

在SVM中, 核函數(shù)的引入解決了因數(shù)據(jù)維度過高且線性不可分導(dǎo)致計算能力不足的缺陷. 一般核函數(shù)的選擇對于問題的求解極為重要, 常見的核函數(shù)有線性核(linear), 多項式核(poly), 雙曲正切核(Sigmoid),高斯徑向基核(rbf)等.

線性核函數(shù)和多項式核函數(shù)在非線性數(shù)據(jù)上的性能不穩(wěn)定: 若數(shù)據(jù)相對線性可分, 則性能效果較好; 若如環(huán)狀非線性數(shù)據(jù)一樣完全不可分, 則性能效果較差.在線性數(shù)據(jù)集上, 即使存在有擾動項干擾, 線性核函數(shù)和多項式核函數(shù)的分類效果仍較好, 可知多項式核函數(shù)在線性數(shù)據(jù)集上功能更強(qiáng). 雙曲正切核在非線性數(shù)據(jù)上強(qiáng)于兩個線性核函數(shù), 但效果不如高斯徑向基核函數(shù), 在線性核函數(shù)上表現(xiàn)較差, 對擾動項的抵抗較弱[16], 高斯徑向基核函數(shù)在全部數(shù)據(jù)集上的表現(xiàn)都較優(yōu), 對擾動項的抵抗力也較強(qiáng)[17]. 綜上分析, 本文對于位置分布未知的數(shù)據(jù)分類任務(wù), 選擇高斯徑向基核函數(shù)作為SVM模型中的核函數(shù).

SVM多分類方法主要包括2種: 一種是直接求解法, 但該方法的時間復(fù)雜度高, 實(shí)現(xiàn)起來較為困難, 且存在大量數(shù)據(jù)待處理的情況下計算性能不足的問題;另一種是將多分類問題轉(zhuǎn)化成多個二分類問題. 本文選擇第2種方法, 常見的轉(zhuǎn)化方式有一對一OAO (one against one)[18], 多對多, 有向環(huán)形圖和二叉樹等方法.在上述二分轉(zhuǎn)化方法中, 由于所需構(gòu)造的二叉樹數(shù)量不同, 二叉樹結(jié)構(gòu)的多分類方法訓(xùn)練的二分類器的數(shù)量也不盡相同, 本文采用偏二叉樹的結(jié)構(gòu)實(shí)現(xiàn)多層分類, 先將所有樣本分為第一類和其他類, 再在剩下類別中重復(fù)此操作直到所有類別都單獨(dú)分為一個葉子節(jié)點(diǎn),最終完成多層分類.

4.2 建立非線性多分類均衡支持向量機(jī)(BSVM)

SVM作為一種常用的變形預(yù)測模型[19], 在處理高維數(shù)據(jù), 非線性問題上具有良好的魯棒性和泛化能力.由于微博數(shù)據(jù)存在獲取容易和樣本數(shù)量不均衡的特性,本文提出非線性多分類均衡支持向量機(jī)BSVM以降低微博樣本量不平衡引起的誤差問題.

其中, θyi為均衡因子, θyi值的增加表示類別yi所占權(quán)重增大, 則yi中的樣本被錯誤分類的概率就會降低. 因此,對于樣本數(shù)量相對較少的類, BSVM能增大其相應(yīng)的均衡因子θyi, 有效地降低樣本數(shù)不平衡引起的誤差.

5 建立優(yōu)化目標(biāo)函數(shù)GA-IPSO-BSVM

為克服SVM算法超參數(shù)選擇速度慢, 易陷入局部最優(yōu)問題, 本文結(jié)合PSO的快速收斂性和SVM多維出來高可靠性的特點(diǎn), 提出改進(jìn)的GA-IPSO算法對BSVM模型進(jìn)行超參數(shù)尋優(yōu), 以實(shí)現(xiàn)微博信息的快速準(zhǔn)確分類.

當(dāng)前研究多集中于針對PSO算法中慣性權(quán)重的動態(tài)改變[20], 但每一次慣性權(quán)重的計算需都花費(fèi)一定的系統(tǒng)資源. 因此, 本文提出基于引入GA和新拓?fù)浣Y(jié)構(gòu)的PSO以獲得更好的參數(shù)尋優(yōu)效果, 又提出非線性多分類均衡支持向量機(jī)BSVM以減少樣本量不平衡引起的誤差. 具體實(shí)施流程如圖2所示.

圖2 GA-IPSO-BSVM具體實(shí)施流程圖

6 GA-IPSO-BSVM算法對比驗(yàn)證

設(shè)置解決n維問題時在迭代次數(shù)D時聚類, K-均值聚類類別數(shù)量為Z=4. 將GA-IPSO-BSVM算法與傳統(tǒng)PSO算法進(jìn)行對比, 驗(yàn)證粒子淘汰機(jī)制和聚類分區(qū)機(jī)制引入的有效性, 使用函數(shù)為Shaffer函數(shù)的f6和f7:

其中, 函數(shù)只有唯一極值點(diǎn)f(0,0)=0, 優(yōu)化前后的PSO算法均設(shè)置為最大迭代次數(shù)100, 初始粒子數(shù)100, 且將兩次實(shí)驗(yàn)中初始粒子群標(biāo)準(zhǔn)化, 得到如圖3和圖4結(jié)果.

從圖3可看出, 兩種算法在第20次迭代時均找到了同一適應(yīng)度的位置, 適應(yīng)度為0.018, 然而GAIPSO-BSVM算法在第45次粒子收斂時不再陷入局部最優(yōu), 找到了適應(yīng)度更好的位置, 適應(yīng)度為0.007,而未改進(jìn)的PSO算法直到達(dá)到最大迭代次數(shù)仍陷入局部最優(yōu).

圖3 f6函數(shù)尋優(yōu)效果對比

從圖4可看出, 兩種算法在第83次迭代時都找到了同一適應(yīng)度的位置, 適應(yīng)度為0.01. 然而GA-IPSOBSVM算法在第15次迭代之后, 在任何一個相同的迭代次數(shù)下都能找到比原算法適應(yīng)度更高的位置, 說明GA-IPSO-BSVM算法收斂速度更快.

圖4 f7函數(shù)尋優(yōu)效果對比

綜合上述結(jié)果看出, GA-IPSO-BSVM算法能夠有效地加快粒子收斂速度, 且避免陷入局部最優(yōu), 更易找到全局最優(yōu)點(diǎn).

7 微博評論信息分類的實(shí)驗(yàn)設(shè)計和結(jié)果分析

7.1 數(shù)據(jù)來源

由于微博評論信息具有復(fù)雜性, 用戶的年紀(jì)跨度和信息渠道的不同, 用戶發(fā)博的隨機(jī)性, 單用戶多次發(fā)表評論的不確定性等多個特征, 導(dǎo)致數(shù)據(jù)可能產(chǎn)生噪聲干擾, 本文每隔一小時對于10個不同的評論區(qū)間進(jìn)行信息采集, 再經(jīng)過數(shù)據(jù)清洗和特征篩選后得到離散型7維數(shù)據(jù)和3個二值數(shù)據(jù). 其中, 離散型7維數(shù)據(jù)能夠較為完整地反映出當(dāng)前微博評論信息的相關(guān)信息,其包括: 評論時間, 昨天發(fā)博數(shù), 閱讀數(shù), 閱讀人數(shù), 互動數(shù), 關(guān)注數(shù), 粉絲數(shù); 二值數(shù)據(jù)記錄用戶類別, 主要包括用戶性別, 用戶是否加V, 用戶是否認(rèn)證. 再通過所提出的GA-IPSO-SVM算法可預(yù)測一個3種分類的輸出結(jié)果, 包括: “正面結(jié)果”“負(fù)面結(jié)果”“中立結(jié)果”. 最后, 本文基于這3種分類輸出結(jié)果得到分類準(zhǔn)確率.

7.2 分類效果

本文將16 000條數(shù)據(jù)按照4:1的比例分為訓(xùn)練集和測試集, 檢驗(yàn)?zāi)Ｐ妥R別的準(zhǔn)確率. 表1列出不同評論的分類正確率, 樣本數(shù)量.

表1 不同評論樣本數(shù)據(jù)及其分類正確率

SVM的核函數(shù)采用RBF核函數(shù). IPSO優(yōu)化參數(shù)均設(shè)置為: 粒子初始種群數(shù)量100, 最大迭代次數(shù)1 000, 慣性因子w設(shè)置為0.8, 學(xué)習(xí)因子c1,c2分別設(shè)置為0.5和0.7. GA優(yōu)化參數(shù)設(shè)置為交叉概率為0.9,變異概率為1E–7.

7.3 多種算法效果對比

用GA-IPSO-SVM算法與BPNN算法[21], CNN算法[22], SAFsat-LSSVM算法[23]對相同微博評論信息進(jìn)行實(shí)驗(yàn)對比, 如圖5所示.

圖5 多種算法對于微博評論信息分類的效果對比

由圖5結(jié)果可看出, 在分類準(zhǔn)確率方面, 本文使用的GA-IPSO-SVM更高; 在收斂速度方面GA-IPSOSVM迭代次數(shù)上更少, 所使用的的模型能找出全局最優(yōu)的SVM超參數(shù), 較好地克服了PSO易陷入局部最優(yōu)解的缺陷, 在微博評論信息的分類任務(wù)上可以進(jìn)行快速有效的處理.

并進(jìn)行不同模型在不同時間段的造成誤差的均方根誤差(root mean squared error,RMSE)和平均絕對相對誤差(mean absolute percentage error,MAPE)進(jìn)行比較,RMSE和MAPE計算公式分別為:

其中,yi為 真實(shí)值,預(yù)測值.

表2為基于BPNN, CNN, SAFa st-SVM和GAIPSO-BSVM對于微博評論數(shù)據(jù)分類的效果對比, 從中可以看出在RMSE誤差衡量標(biāo)準(zhǔn)當(dāng)中, GA-IPSO-SVM的誤差顯著低于BPNN的18.63和CNN的15.769, 略低于SAFast-LSSVM的8.674, 是RMSE標(biāo)準(zhǔn)下精度最高的算法. 且在MAPE誤差衡量標(biāo)準(zhǔn)中, GA-IPSO-SVM的誤差顯著低于BPNN的0.385和CNN的0.294, 低于SAFast-LSSVM的0.187, 是MAPE標(biāo)準(zhǔn)下精度最高的算法. 實(shí)驗(yàn)證明相對于傳統(tǒng)算法, GA-IPSO-SVM在尋優(yōu)精度上有更好的表現(xiàn).

表2 各種分類算法的誤差值

8 結(jié)束語

針對微博評論信息的分類任務(wù), 利用相關(guān)數(shù)據(jù), 本文提出了采用多分類偏二叉樹結(jié)構(gòu)的GA-IPSO-SVM對信息進(jìn)行分類的方法, 模型通過粒子淘汰機(jī)制的引入節(jié)約了迭代大量無用粒子的時間, 使粒子的收斂速度更快, 能在一定程度上完成快速尋優(yōu), 基于聚類算法的粒子分區(qū)機(jī)制引入使粒子不再局部最優(yōu)的能力更強(qiáng).最終在多個公開數(shù)據(jù)集及微博信息分類上進(jìn)行相較傳統(tǒng)算法的對比驗(yàn)證, 本文提出的算法具有更高的分類精度和有效性.