分布式天牛群優(yōu)化算法在分類中的應用

黃 嵩，陳宏偉，邊 帆，楊威威，楊智慧

(湖北工業(yè)大學計算機學院，湖北 武漢 430068)

邏輯回歸分類器作為一種文本情感分類器在自然語言處理中得到了廣泛的應用，它的一些參數(shù)通常由人為經(jīng)驗設定，容易欠擬合，無法達到最佳分類效果。為了解決上述類似的問題，一些研究人員選擇使用群智能算法來優(yōu)化分類模型的超參數(shù)[1-3]，使得優(yōu)化后的模型在處理分類問題時性能有所提高。因此，通過優(yōu)化模型的關鍵參數(shù)，可以進一步提高邏輯回歸分類器模型在文本情感分類的準確率。本文提出了天牛群優(yōu)化算法(BSO)來優(yōu)化Logistic回歸分類器模型的參數(shù)，該模型可以通過BSO算法自適應調(diào)整參數(shù)并獲得最佳分類結(jié)果。BSO算法是2017年由Jiang[4]等提出的一種新的生物啟發(fā)式智能算法Beetle Antennae Search Algorithm(BAS)演化而來。受粒子群算法(PSO)的啟發(fā)，結(jié)合BAS和PSO算法的優(yōu)點[5-7]，將研究對象從天牛個體擴展到天牛群體，既保留了天牛個體的特征，又包含了群算法的優(yōu)點，在一定程度上解決算法的單一性，提高算法的局部和全局尋優(yōu)能力。

針對大規(guī)模計算中文本數(shù)據(jù)量大、時間復雜度高的問題, 本文提出一種基于Spark計算框架的分布式BSO算法。實驗采用推特評論數(shù)據(jù)集，通過提出的算法模型對評論文本進行情感傾向分類。實驗結(jié)果表明，分布式BSO算法在保證模型分類精度的基礎上，能夠更快、更有效地找到最優(yōu)參數(shù)組合。

1 IM-BSO算法的原理與改進策略

1.1 學習因子與慣性權重的自適應調(diào)整策略

在一般情況下，BSO算法的學習因子與慣性權重被設置為常數(shù)，這樣做無法使算法達到最優(yōu)，且影響算法的效率。一些學者提出自適應的動態(tài)調(diào)整學習因子[8-9]與權重[10-11]的策略。本文采取如下策略：

(1)

(2)

其中C1和C2是學習因子，ω為慣性權重，Gbest為全局最優(yōu)值，fitness為適應度值，t和T_max分別是當前迭代次數(shù)和最大迭代次數(shù)。

由式(2)知，天牛個體的適應度值比較小的時候，它的權重值就會比較大，因為當前天牛個體所在的位置比較差，需要加大搜索的步長，以便能搜索到更好的位置。而當天牛個體的適應度值比較大的時候，它的權重值就會比較小，因為當前天牛個體所在的位置已經(jīng)很好了，只需緩慢地搜索到全局最優(yōu)的位置，避免出現(xiàn)過擬合現(xiàn)象。

1.2 精英反向?qū)W習策略

(3)

其中，xmin和xmax是天牛個體位置的取值區(qū)間的最小值和最大值。精英學習的具體步驟如：

1.3 K均值聚類

K-means是機器學習中最常用的聚類方法，它的原理是求解數(shù)據(jù)點間的歐氏距離，然后根據(jù)距離的大小來劃分類別，兩個數(shù)據(jù)點的歐氏距離越近，相似度就越大，就會被劃分到一類。

在本節(jié)中，K-means聚類的目標是把天牛群中n個天牛個體劃分到k個聚類中，形成k個天牛子簇，子群中的每個天牛個體都具有相似的特性。在算法每次迭代后都會進行一次聚類操作，以便得到最好的聚類效果。

K-means算法的步驟如下所示：

Step1：選取初始化天牛群中K個天牛個體作為初始的聚類中心點(a1,a2,…,ak);

Step2：針對天牛群中每個天牛個體xi，計算天牛個體到k個聚類中心的距離，并將距離最小的天牛個體劃分到其所對應的類中；

Step3：在每次迭代中，針對每個類別aj，根據(jù)公式(4)重新計算其聚類中心；

Step4：重復Step2和Step3這兩個步驟，直到達到最大迭代次數(shù)。

(4)

式中，dis(xj,ak)表示天牛個體到聚類中心點的歐氏距離，其中j=(1,2,…,N),K=(1,2,…,K)。

經(jīng)過K-means劃分種群后，天牛群速度更新公式可以如下：

(5)

(6)

其中，dmax為干擾因子最大值，dmin為干擾因子最小值。

1.4 拓撲機制

有生物學家發(fā)現(xiàn)了歐椋鳥群的飛行機制中，個體之間存在拓撲相互作用，且與距離的大小無關[12]。這一機制同樣也能運用到天牛群算法中，天牛群中每個簇可以看作是一個整體，每個簇間的個體的飛行方向和速度都與所屬簇中的個體保持一致。Montes[13]等人在上述理論上，模擬出歐椋鳥群的拓撲機制并運用到粒子群算法中。本節(jié)將這一拓撲機制融入到天牛群算法中，融入拓撲機制的天牛群速度更新公式如下：

(7)

(8)

1.5 IM-BSO算法

假設在D維空間上有n個天牛，則模擬天牛群位置變化的公式如：

(9)

(10)

(11)

式中，d0為天牛左右兩觸角之間的距離。

2 DIBSO-LR分類模型

2.1 DIBSO算法原理

首先對 Spark 群集中的并行天牛群進行編碼，設有n個天牛種群，最終會生成一個由k個分區(qū)組成的POPRDD，分別存儲當前天牛群的位置(x)、速度(v)、天牛左右兩觸角的適應度值(fl、fr)和歷史最佳位置(pbest)。圖1是POP的編碼結(jié)構(gòu)。

圖 1 POP編碼結(jié)構(gòu)示意圖

其中N=(1,2,…,n)表示天牛種群的個數(shù)，D=(1,2,…,d)表示天牛個體的維度。然后將POP轉(zhuǎn)換為POPRDD，在后續(xù)算法迭代過程中，直接更新POPRDD中的子組信息即可。

分布式計算的過程主要分為兩個部分，一部分是天牛群自身的計算，一部分是與數(shù)據(jù)結(jié)合計算天牛群的適應度值。當天牛群只做自身計算時，POPRDD只進行map操作，然后計算后的值覆蓋POPRDD中所對應的值。當與數(shù)據(jù)結(jié)合來計算天牛群的適應度值時，首先取得天牛群的位置信息并廣播，此時的天牛群位置信息為廣播變量，進行分布式計算的數(shù)據(jù)是來自Hadoop中分布式文件系統(tǒng)HDFS中的數(shù)據(jù)，然后進行map操作得到每個分區(qū)的天牛群適應度值，最后進行reduce操作求得天牛群的適應度平均值。DIBSO算法的分布式過程與算法流程分別見圖2和圖3。

圖 2 DIBSO算法分布式過程

圖 3 DIBSO算法流程圖

2.2 基于DIBSO-LR的情感分類

本文采用DIBSO算法自適應控制邏輯回歸的正則化系數(shù)，增強模型的自適應擬合能力。模型的分類準確率作為算法的評價指標。情感分類的框架圖見圖4。

圖 4 情感分類框架圖

3 實驗與結(jié)果分析

在分布式實驗中，推特數(shù)據(jù)集的數(shù)據(jù)大小分別為20 萬、50 萬和100 萬。基于分布式改進BSO算法(DIBSO)，在不同規(guī)模的數(shù)據(jù)集上獨立運行10次，先計算不同數(shù)據(jù)集的分類精度，然后用1、2、3、4、5個計算節(jié)點計算，并比較它們的平均運行速度和加速比。加速比是反映分布式算法性能和優(yōu)化效率的重要指標。通過比較不同數(shù)據(jù)集中算法的加速比，可以體現(xiàn)分布式算法的加速效果(圖5、圖6)。

圖 5 情感分類準確率

(a)20 萬

由圖6可看出，隨著節(jié)點數(shù)的增加，由DIBSO-LR分類模型計算出的分類準確率基本保持不變，且計算時間逐漸減小。對于20 萬樣本，當節(jié)點數(shù)從1增加到2和3增加到4時，加速效果明顯。對于50 萬樣本，當節(jié)點數(shù)從1增加到3時，加速效果顯著。對于100 萬樣本，加速效果最為突出，節(jié)點數(shù)從1增加到5時，加速比接近線性增長。由此可以看出，隨著節(jié)點數(shù)的增加，DIBSO-LR分類模型在確保分類準確率不發(fā)生重大變化的同時，加速了模型的計算速度，且隨著數(shù)據(jù)量的增大，加速效果更明顯。

4 結(jié)論

本文基于Hadoop和Spark，將大數(shù)據(jù)技術應用于情感分類，提出了DIBSO-LR分類模型，從實驗結(jié)果來看，DIBSO-LR模型在情感分類問題上取得了不錯的效果，尤其在計算效率方面，體現(xiàn)了大數(shù)據(jù)技術的高效。相信隨著對相關領域進一步深入研究和大數(shù)據(jù)技術的不斷發(fā)展，把大數(shù)據(jù)技術與智能算法相結(jié)合，在一定程度上，能夠提高智能算法在優(yōu)化問題上的計算效率。