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

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

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

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

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

1 相關工作

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

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

2 問題描述

由于現實網絡中評論信息對時效性要求較高, 則快速準確的分類算法對于微博輿情的控制具有重要意義. 此類算法可考慮兩方面內容:

(1) 小樣本及時處理;

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

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

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

3 改進粒子群優化算法(GA-IPSO)

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

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

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

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

2) 改變粒子的拓撲結構. 當GA迭代次數D為:

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

當粒子完成聚類后按照聚類結果進行PSO算法,每個粒子在當前社區進行尋優, 最終各區域最優粒子組成為優秀群體的初始粒子種群開始PSO算法, 該算法的優勢為: 即使存在社區的粒子陷入局部最優, 其他社區的粒子仍然能夠在解空間內繼續尋找最優解, 較好地保證了解的全局最優性.

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

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

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

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

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

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

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

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

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

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

4.1 SVM簡介

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

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

對于給定數據集:

分類超平面的函數為:

歸一化處理之后, 滿足:

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

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

將高維空間中的點積運算替換成核函數:

則最優分類函數可表示為:

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

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

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

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

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

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

5 建立優化目標函數GA-IPSO-BSVM

為克服SVM算法超參數選擇速度慢, 易陷入局部最優問題, 本文結合PSO的快速收斂性和SVM多維出來高可靠性的特點, 提出改進的GA-IPSO算法對BSVM模型進行超參數尋優, 以實現微博信息的快速準確分類.

當前研究多集中于針對PSO算法中慣性權重的動態改變[20], 但每一次慣性權重的計算需都花費一定的系統資源. 因此, 本文提出基于引入GA和新拓撲結構的PSO以獲得更好的參數尋優效果, 又提出非線性多分類均衡支持向量機BSVM以減少樣本量不平衡引起的誤差. 具體實施流程如圖2所示.

圖2 GA-IPSO-BSVM具體實施流程圖

6 GA-IPSO-BSVM算法對比驗證

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

其中, 函數只有唯一極值點f(0,0)=0, 優化前后的PSO算法均設置為最大迭代次數100, 初始粒子數100, 且將兩次實驗中初始粒子群標準化, 得到如圖3和圖4結果.

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

圖3 f6函數尋優效果對比

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

圖4 f7函數尋優效果對比

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

7 微博評論信息分類的實驗設計和結果分析

7.1 數據來源

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

7.2 分類效果

本文將16 000條數據按照4:1的比例分為訓練集和測試集, 檢驗模型識別的準確率. 表1列出不同評論的分類正確率, 樣本數量.

表1 不同評論樣本數據及其分類正確率

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

7.3 多種算法效果對比

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

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

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

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

其中,yi為 真實值,預測值.

表2為基于BPNN, CNN, SAFa st-SVM和GAIPSO-BSVM對于微博評論數據分類的效果對比, 從中可以看出在RMSE誤差衡量標準當中, GA-IPSO-SVM的誤差顯著低于BPNN的18.63和CNN的15.769, 略低于SAFast-LSSVM的8.674, 是RMSE標準下精度最高的算法. 且在MAPE誤差衡量標準中, GA-IPSO-SVM的誤差顯著低于BPNN的0.385和CNN的0.294, 低于SAFast-LSSVM的0.187, 是MAPE標準下精度最高的算法. 實驗證明相對于傳統算法, GA-IPSO-SVM在尋優精度上有更好的表現.

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

8 結束語

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