顧 偉 任勇軍

（南京信息工程大學(xué)計算機(jī)與軟件學(xué)院 南京 210044）

1 引言

活躍于社交網(wǎng)絡(luò)平臺的社交機(jī)器人（Social Bot，SB）實(shí)質(zhì)是一個自動計算機(jī)程序［1］。這些SBs可分為僵尸SB、干擾SB和誠意SB。這些惡意SBs也稱為僵尸攻擊，它們分布于垃圾郵件、釣魚網(wǎng)。干擾SBs用于操控在線評論和評分，進(jìn)而干擾用戶的行為［2］。而誠意SBs正常地發(fā)布產(chǎn)品消息、新聞資信。

現(xiàn)有多種檢測在線社交網(wǎng)絡(luò)上的僵尸［3～4］算法。然而，僵尸會動態(tài)地改變其行為，進(jìn)而避免檢測。目前主要有基于機(jī)器學(xué)習(xí)、基于眾包（Crowdsourcing）和基于社會圖譜的僵尸檢測算法。

基于機(jī)器學(xué)習(xí)的檢測算法通過考慮多項(xiàng)特征數(shù)據(jù)，從SBs中分離合法的SB。文獻(xiàn)［5］提出基于隨機(jī)森林分類器的BotorNot檢測算法。文獻(xiàn)［6］采用了基于深度Q-學(xué)習(xí)的僵尸檢測算法。

基于眾包的檢測算法是利用專家?guī)鞓?gòu)建評判標(biāo)準(zhǔn)，進(jìn)而對SB進(jìn)行分類。例如，文獻(xiàn)［7］針對2000個賬戶數(shù)據(jù)，并基于10個專家評判，建立分類標(biāo)準(zhǔn)。

基于社會圖譜的檢測算法是采用社會網(wǎng)絡(luò)圖譜對SB進(jìn)行分類。目前，有基于用戶間的社會信任關(guān)系和基于中心測量和圖拓?fù)鋬煞N類型。文獻(xiàn)［8］采用基于Sybil隨機(jī)-漫步的方法檢測Sybil用戶，其中不信任用戶的分?jǐn)?shù)最低，而合法用戶的分?jǐn)?shù)最高。文獻(xiàn)［9］采用了基于中心測量的算法，并提出了基于神經(jīng)網(wǎng)絡(luò)、隨機(jī)森林和決策樹分類器。

在傳統(tǒng)的Q-學(xué)習(xí)算法中，所有學(xué)習(xí)動作均需計算其Q值。因此，Q-學(xué)習(xí)算法的收斂速度很慢，增加了存儲所有動作的Q-值的空間。

為此，提出基于深度Q-學(xué)習(xí)和粒子群優(yōu)化的僵尸檢測（Deep Q-Learning and Particle Swarm Optimization-based Bot Detection，DQL-PSO）算法。利用粒子群算法優(yōu)化Q-學(xué)習(xí)，進(jìn)而獲取最優(yōu)的學(xué)習(xí)動作序列。仿真結(jié)果表明，提出的DQL-PSO算法提高了檢測算法的收斂速度，并提高了檢測僵尸的準(zhǔn)確性。

2 網(wǎng)絡(luò)模型

引用如圖1所示的網(wǎng)絡(luò)架構(gòu)。每個粒子代表一個狀態(tài)，并且每個粒子有n個序列的學(xué)習(xí)動作，且每個序列對應(yīng)一個Q值。在隨機(jī)環(huán)境中，先計算每個粒子的適度值。再依據(jù)適度值，更新學(xué)習(xí)動作的局部和全局最優(yōu)序列。因此，通過載入新的粒子，更新迭代，進(jìn)而優(yōu)化性能。

圖1 網(wǎng)絡(luò)框架

3 DQL-PSO算法

3.1 基于PSO的Q函數(shù)的更新

DQL-PSO算法利用粒子群優(yōu)化（Particle Swarm Optimization，PSO）對Q函數(shù)進(jìn)行更新。將僵尸的檢測問題轉(zhuǎn)化為優(yōu)化問題，提高檢測性能。

令S={s1,s2,…}和LA={α1,α2,…}分別表示狀態(tài)集和學(xué)習(xí)動作集。每個用戶行為關(guān)聯(lián)了狀態(tài)和學(xué)習(xí)動作，再依據(jù)用戶行為，對用戶進(jìn)行獎勵。

引用文獻(xiàn)［12］的定義，令st和令αt分別表示當(dāng)前的狀態(tài)和動作。令表示下一個狀態(tài)。在時間t獲取了獎勵rt。據(jù)此，定義狀態(tài)轉(zhuǎn)換函數(shù)：

通過優(yōu)化學(xué)習(xí)動作序列，進(jìn)而最大化累加獎勵R。用fst(A)表示優(yōu)化后的動作序列的適度函數(shù)：fst(A)=R(st,A)。而。

當(dāng)在時刻t執(zhí)行動作αt，位于狀態(tài)st的學(xué)習(xí)代理就得到獎勵rt。DQL-PSO算法的根本目的就是最大化累加獎勵，決策最優(yōu)的動作集序列。因此，對適度函數(shù)fst(A)進(jìn)行更新：

式中：T表示在每個學(xué)習(xí)時期內(nèi)總的學(xué)習(xí)動作數(shù)。rt表示第t個動作的當(dāng)前獎勵。而γ表示折扣因子，且γ∈(0,1)。

針對SB檢測問題，用動作集序列A={αt,αt+1,…}表示粒子位置；用狀態(tài)轉(zhuǎn)換率表示粒子速度。并且通過比較適度函數(shù)決定每個學(xué)習(xí)代理的局部最優(yōu)解和所有學(xué)習(xí)代理的全局最優(yōu)解。

式中：ω、c1和c2分別代表權(quán)重系統(tǒng)。而r1、r2為隨機(jī)數(shù)，且在0～1之間。Qi(st,αt)表示第i個粒子在狀態(tài)st所選擇的動作αt所形成的Q-值。而表示由第i個粒子決策的局部最優(yōu)Q值。Gbest(st,αt)表示由所有粒子決策的全局最優(yōu)Q值。

3.2 檢測步驟

DQL-PSO算法的檢測步驟如算法1所示。每個用戶的執(zhí)行步驟：

1）依據(jù)式（2）計算累加獎勵R；

2）依據(jù)最優(yōu)的學(xué)習(xí)動作集A，計算局部和全局最優(yōu)Q值；

3）再依據(jù)式（3）和式（4）更新速度和Q值。

重復(fù)上述過程，直到達(dá)到迭代次數(shù)。

Algorithm 1

Parameters：

R：Cumulative reward for Q-valueQ（s，α）

具體而言，首先對Qi(s,α)以及Vi(st,αt)進(jìn)行初始化。并以狀態(tài)s1進(jìn)行學(xué)習(xí)。然后，代理在時刻t執(zhí)行動作αt獲取當(dāng)前獎勵rt以及下一個相應(yīng)的狀態(tài)，并緩存經(jīng)歷值。

再依據(jù)式（2）計算獎勵值Ri，再更新粒子的局部最優(yōu)位置。若Ri小于或者＝－1，就將當(dāng)前位置作為局部最優(yōu)位置，并將當(dāng)前Q值作為局部最優(yōu)Q值，如式（5）所示：

將所有粒子中具有最高Q值的位置作為全局最優(yōu)解，如式（6）所示：

圖2給了DQL-PSO算法的執(zhí)行流程。先對參數(shù)進(jìn)行初始，再評估每個粒子的適度值。然后，再選擇局部最優(yōu)和全局最優(yōu)值。隨后，依據(jù)局部和全局最優(yōu)值更新每個粒子的位置和速度。并進(jìn)行迭代，若達(dá)到迭代次數(shù)，就停止迭代。

圖2 DQL-PSO算法的執(zhí)行流程

4 性能仿真

為了更好地分析DQL-PSO算法的性能，選擇文獻(xiàn)［10］的用戶群數(shù)據(jù)庫（User Popularity Dataset，UPD）作為實(shí)驗(yàn)數(shù)據(jù)。其中用戶數(shù)為453853，合法用戶數(shù)為476，僵尸個數(shù)為320。最大的迭代次數(shù)為30。其余的仿真參數(shù)如表1所示。

表1 仿真參數(shù)

選擇文獻(xiàn)［11］提出的同步策略的PSO算法（Heterogeneous Strategy PSO，HS-PSO）和文獻(xiàn)［6］提出的自適應(yīng)深度Q-學(xué)習(xí)的（Adaptive Deep Q-learning，ADQL）算法作為參照。主要比較它們的達(dá)到最優(yōu)狀態(tài)的動作序列數(shù)（以下簡稱為最優(yōu)-動作序列數(shù)）、準(zhǔn)確率Pprecision和重放率PRecall。

式中：NP表示正確地將僵尸評判為僵尸的數(shù)量。而ND表示錯誤地將SB評判為合法的SB的數(shù)量。而NPN表示將合法用戶評判為僵尸的數(shù)量。

4.1 最優(yōu)-動作序列數(shù)

首先，分析在不同迭代次數(shù)下的DQL-PSO算法的最優(yōu)-動作序列數(shù)，如圖3所示。圖3記錄了30次的迭代次數(shù)。

圖3 最優(yōu)-動作序列數(shù)

從圖3可知，相比于HS-PSO算法，提出的DQL-PSO算法在同等的迭代次數(shù)環(huán)境下，所需的學(xué)習(xí)動作數(shù)少，降低了最優(yōu)-動作序列數(shù)。例如，迭代次數(shù)為25次時，HS-PSO算法的最優(yōu)-動作序列數(shù)達(dá)到約28.5，而DQL-PSO算法的最優(yōu)-動作序列數(shù)低至22。

4.2 準(zhǔn)確率

圖4顯示了在不同學(xué)習(xí)時期下ADQL和DQL-PSO算法的準(zhǔn)確率。圖4反映了兩項(xiàng)信息：1）收斂性；2）準(zhǔn)確值。從收斂角度，DQL-PSO算法的性能優(yōu)于ADQL算法。DQL-PSO算法未到300個學(xué)習(xí)時期收斂，并收斂于95%。而ADQL算法約在350個學(xué)習(xí)時期收斂。從準(zhǔn)確值角度，DQL-PSO算法的準(zhǔn)確值也優(yōu)于ADQL算法。DQL-PSO算法的準(zhǔn)確值收斂于95%，而ADQL算法的準(zhǔn)確值收斂于約92%。

圖4 準(zhǔn)確率

4.3 重回率

最后，分析DQL-PSO算法和ADQL算法的重回率，如圖5所示。相比于ADQL算法，提出的DQL-PSO算法的重回率得到提升。例如，ADQL算法的合法用戶的重回率約93%，而DQL-PSO算法的重回率約95%。

圖5 重回率

5 結(jié)語

在深度Q-學(xué)習(xí)算法中，學(xué)習(xí)代理依據(jù)更新Q-值自動學(xué)習(xí)。此外，通過有效選擇更新策略可以快速地收斂。本文采用DQL-PSO算法檢測僵尸。利用粒子群優(yōu)化算法更新Q函數(shù)。并利用局部最優(yōu)Q值和全局最優(yōu)Q值更新Q值。

利用UPD數(shù)據(jù)庫進(jìn)行分析，并與HS-PSO和ADQL算法進(jìn)行比較，仿真結(jié)果表明，提出的DQL-PSO算法能達(dá)到95%的檢測準(zhǔn)確率和93%的重回率。相比于HS-PSO算法，DQL-PSO算法提升了收斂速度。