基于極小極大博弈的水軍識別算法研究

穆云翔, 盛志偉, 盧嘉中

(成都信息工程大學網絡空間安全學院,四川 成都 610225)

0 引言

網絡水軍是指在網絡中針對特定內容發布特定信息的、被雇傭的網絡寫手,簡稱水軍,又名網絡槍手。他們通?；钴S在電子商務網站平臺中,通過發布虛假的商品評價來影響正常消費者的決策。

網絡的快速發展為水軍提供了滋生條件。一方面,網絡環境提供的便利:網絡開放性、即時性、自由性、交互性等特點為網絡水軍的發展壯大提供了環境支撐。網絡的開放性為網絡水軍提供了自由出入的媒體門戶,不需要提供任何真實信息即可徜徉于各大論壇、貼吧,在網絡上任意發表言論；網絡的即時性則有助于網絡水軍引導網民對輿情的推動,讓受眾在缺乏理性分析的前提下引爆預設議題。網絡的自由性塑造了無中心的狂歡廣場,任何網民都可自由發布信息,也為網絡水軍的“灌水”行為提供了便利。網絡的交互性為政府、媒體、網民之間的交流互動提供了便利,從而形成“圍觀”的力量。另一方面,網絡受眾的媒介素養偏低。中國網民群體龐大,但媒介素養參差不齊,整體不容樂觀,在一定程度上縱容了網絡水軍的發展壯大。一些年輕網民由于心態不成熟,往往不能客觀、全面、辯證地看待社會問題,容易受網絡負面情緒影響。面對網絡水軍故意炒作的熱點事件,極易非理性地跟風發帖,成為網絡水軍的“幫兇”。一些在經濟上比較失意的網民則容易產生“仇富”心態,當網絡上曝出諸如“房妹”等新聞熱點時,他們會不自覺地與網絡水軍站在同一戰壕；一些網民對娛樂化的追求不斷削弱主流媒體的權威性與影響力,為更能把握網民心理的網絡水軍提供了搶占先機的機會。

電子商務平臺提供在線評論系統作為商家與消費者的橋梁。消費者通過瀏覽評論細節來決定是否購買產品,產品評論成為影響消費者購買欲望的重要因素。由于消費者傾向于購買好評產品,而放棄購買負面評論產品,因此在競爭激烈的電商市場中,許多商家通過雇傭“水軍”,在自己的店鋪下用圖片偽造好評,操縱評論。并在競爭對手的門店下進行惡意評論,誤導消費者。水軍虛假評論的存在干擾了產品描述的真實性,對電商平臺和消費者產生了顯著的負面影響。因此,識別網絡水軍評論并保護消費者權益非常重要?？偠灾?通過大量同質行為或內容形成回聲室效應,從而影響其他用戶的觀點和決策,是網絡水軍的最終目的。

在電商平臺中,網絡水軍采取發布不實信息來混淆視聽。對于消費者而言,水軍的存在影響購買意愿；對于商家而言,如何請水軍刷好評變成了影響銷售的最大因素；對于市場而言,水軍擾亂了原有的市場秩序。這對于行業的發展具有很大的影響力,因此網絡水軍的監管成為一個亟待解決的難題。

本文主要關注Yelp 系統中的水軍。關于這類水軍識別器主要有以下缺點:(1)大多數識別器都假設水軍有相同的特征,并且可以根據這個特征來識別水軍。但是在現實世界里有很多種水軍,他們有不同的目標、對象和策略。如一個水軍可能想要推廣某一件商品,而另一個水軍想要貶低競爭對手。(2)專業水軍會研究最新的識別技術,并從中發掘新的策略來逃過識別器[1-2]。(3)現有的識別器大都基于精確率和召回率作為識別目標。而根據Luca[3]利用市場研究的現有成果,從商品評分變化的角度定義了網絡水軍的實際效應。實際效應可以用來表示水軍和平臺在對抗過程中的實際目標,假設水軍的目標是推廣目標商品,那么平臺的目標就是盡可能地減少推廣的程度。文獻[3]也通過實驗證明,即使在召回率很高的情況下,水軍依然可以達到很高的推廣效果。

本文提出一種利用用戶行為特征的水軍識別算法(FBS),將FBS 應用到一個水軍對抗模型,最終訓練出的識別器在公開數據集YelpChi 上取得了不錯的性能表現。并利用網絡水軍賬號的一些特點,提出幾種新的用戶特征和一個基于用戶行為特征分析的水軍識別算法(FBS)。將FBS 應用到一個水軍對抗模型中,最終訓練出的識別算法性能相較于以前有明顯提升。

1 相關工作

1.1 AP 算法

AP(affinity propagation)算法[4]無需事先指定聚類數目,且沒有明確的質心(聚類中心點),樣本中的所有數據點都可能成為AP 算法中的質心。根據現實環境中網絡水軍種類繁多,且同類型水軍之間較為類似的特點,再基于AP 算法的上述特征,將其應用到水軍對抗模型。

1.2 分類器的選擇

目前最常見的分類器有人工神經網絡、K-近鄰(K-NN)、樸素貝葉斯和決策樹。盡管這些分類算法在幾十年的發展中衍生出很多的改進算法,但是仍然沒有一種完美的分類算法能適應所有的環境問題。根據Kotsiantis[5]在主流分類算法性能比較,人工神經網絡和支持向量機對大規模數據訓練比較困難,且對缺失數據敏感；K-NN 時間復雜度和空間復雜度高,可解釋性差；樸素貝葉斯通常準確率較低,且只能用于處理二分類問題；相對于其他幾種分類算法,決策樹計算量簡單,可解釋性強,比較適合處理有缺失屬性值的樣本,能夠處理不相關的特征。此外,決策樹能夠很好地處理同時具有離散和連續屬性的分類問題。因此,使用決策樹算法進行分類識別最為合適,詳情如表1 所示。

表1 機器學習常用分類算法比較

1.3 網絡水軍對抗模型

2020年Dou 等[6]利用強化學習建立的水軍對抗模型,提出一種全新的水軍識別性能的評測指標PE(practical effect)。該模型利用多個水軍識別算法和多種水軍攻擊策略進行博弈,將博弈過程轉換為兩條相互依賴的馬爾可夫決策過程。利用雙方博弈直至達到納什均衡,此時的水軍識別算法即可認為是當前環境下的最優算法。本文將提出FBS 并將其應用到對抗模型中,以此訓練出的水軍識別算法達到的效果相較于以前PE 提升了8%。

1.4 研究現狀

現有識別網絡水軍的方法主要有3 種:基于文本與情感分析法、基于行為特征分析法和基于圖結構法。其中,基于文本與情感分析需要花費較長時間進行訓練,且隨著NLP 等人工智能算法的發展,水軍文本內容已經和普通用戶的評論文本差別越來越小。因此,基于文本分析法的性能相較于其他兩種普遍偏低。

早期的水軍由于發布的評論信息都很類似,因此研究方法大多基于語言學特征。其中,詞袋特征是大部分研究者的首選語言特征。M Mccord 等[7]提取重復評論的bigram 特征,在推特數據集訓練回歸模型,利用隨機森林分類器識別只關注品牌的評論和評論文本無關的兩類垃圾評論,精確率高達95.7%。

Li 等[8]基于新擴展的黃金標準數據集識別網絡水軍,該數據集由來自3 個不同領域(酒店、餐廳、醫生)的數據組成,每個領域都包含3 種類型的評論,即客戶生成的真實評論、網絡水軍生成的欺騙性評論和員工(領域專家)生成的欺瞞性評論。該文試圖捕捉欺騙性評論和真實評論之間語言特征的一般差異和水軍檢測的領域遷移性問題。實驗表明該模型在餐廳數據集上分類準確率都能達到75%左右,而在醫生數據集上準確率只有50%左右。實驗表明該特征用于水軍的虛假評論檢測的領域遷移性差。

Noekhah S 等[9]通過提取分析詞頻、信息豐富度、內容定罪等特征,實現了基于欺騙性語言的評論文本在線欺騙識別系統。將這些特征集應用到之前使用的3 個分類器(支持向量機、樸素貝葉斯和C4.5 決策樹),并使用5 倍交叉驗證。最終的實驗結果表明,識別欺騙性評論的準確率達到80%,但是該識別方法時間復雜度很高,并不適用于一些較大的數據集。

Wang 等[10]首先提出虛假評價檢測中的冷啟動問題,在Yelp 評價數據上提取一部分“新的評價”,即該用戶只發布了一條評價。作者將之前研究中提到的文本和行為特征檢測模型應用到這些新評價上,發現檢測的效果并不好。為解決這種冷啟動問題,一種直觀的想法是從歷史數據中去尋找和這個新評價發布者特征相似的評論者,然后把最相似的評價者或者評價的標簽作為該新評價的標簽?？偠灾?雖然新評價信息很少,但可以通過深度學習,在歷史數據上學習到有效的關系嵌入(embedding),然后利用該模型得到新的數據嵌入,這樣就可以結合歷史嵌入和其標簽來預測新數據的標簽。

Hooi B 等[11]利用二部圖提出了Fraudar 算法。Fraudar 定義了一個可以表達結點平均可疑度的全局度量G(·),在逐步貪心移除可疑度最小結點的迭代過程中,使G(·)達到最大的留存結點組成可疑度最高的致密子圖。在此算法中,由于無法模仿每個節點與其他節點的聯系,因此準確率大幅度提升。但是Fraudar 的一個缺點是它的串行運算特性導致在大規模二部圖上運算緩慢,其每次迭代只動態地刪除一個結點并更新剩余結點狀態。

Wang 等[12]除了利用用戶本身的一些信息,還利用用戶在社交網絡中的好友關系對一些可疑用戶進行識別。作者基于圖結構的方法將水軍和水軍的虛假評論識別看作聯合分類或排序問題,再采用馬爾科夫隨機場模型和LBP[13](loopy belief propagation)計算每個節點的可疑程度。還對LBP 算法進行優化,提高了算法的效率并且有收斂性的保證。實驗表明,該模型在新浪微博數據集上的分類Accuracy 都能達到75%。

Shah N 等[14]提出利用網絡結構特征來識別在亞馬遜上通過眾包發送水軍虛假評論的用戶,提出TwoFace 算法,更多關注召回率,該算法有的召回率能夠達到91%。該算法也有缺點,ground truth 的可信度不是很高。

S Rayana[2]提出SPEAGLE 框架來做網絡水軍識別,利用關聯數據和元數據,結合了圖、行為和文本進行水軍識別,該方法中圖由user-review-product 圖構成,3 種類型的結點都有標簽,user:水軍與否,review:虛假與否,product:為被攻擊目標與否。論文用圖來做分類,用metadata 來估計有關節點的類分布的先驗知識。該算法在數據集YelpZip 上的準確率可以達到79.4%。

盡管研究者們都針對不同情況下的用戶特征進行深入研究,但其往往集中在某幾個方面。隨著平臺和水軍的發展,上述方法大多只能識別出某一類水軍,適用性并不夠廣泛。

2 FBS-基于行為特征的水軍識別算法

2.1 問題描述

由于現實環境中電商平臺的網絡水軍復雜且多樣,因此水軍檢測主要面臨的困難在于水軍檢測涉及的特征難以規范化表達。一方面,水軍覆蓋范圍廣,在不同平臺其特征不盡相同,導致沒有一個標準的水軍特征集；另一方面,水軍經過多年發展,不斷通過模仿正常用戶來偽裝自己,導致識別模型準確率不高。因此特征的選擇變得尤為重要,應選用水軍無法模仿的一些特征加入特征集。

2.2 特征定義

在Yelp 系統中,刻畫用戶的特征有很多,如MNR(一天內寫的最大評論數)、PR(積極評論比例)、NR(負面評論比例)等。結合Mukherjee 等[1]的研究,選取了4 個原始特征,如表2 所示。

表2 原始特征描述

針對當前網絡水軍特征覆蓋面不足導致識別率不高的問題,綜合Yelp 系統中水軍用戶與正常用戶的差異性,結合水軍用戶的一些突出特征,本文提出AW、ISR、ERD、ETG、SQD 等5 個新特征,以此來擴充現有特征集對網絡水軍特征的覆蓋面。

定義1 AW 是用戶發表的第一條評論和最后一條評論的時間差。通常情況下,水軍的時間差較短。因為部分水軍可能只是為了某幾次完成任務而注冊,且完成刷分之后便棄用賬號。

定義2 ISR 是用戶是否僅有唯一評論。水軍賬號的注冊可能僅是為了某一次的刷分行為,在之后便不再使用,而正常用戶的使用大多是長期的。

定義3 ERD 是用戶評論的時間分布熵。分布熵是對不同概率分布的刻畫,它是概率分布的不確定性的期望值。值越大,表示時間分布的不確定性越大。正常用戶的評論時間一般是長期且穩定的,不會在短時間內出現大量的評論,因此時間分布的不確定性較大,分布熵較大。而水軍大多情況下,在任務集中時存在爆發式的評論。因此,時間分布的不確定性較低,分布熵較小。

其中pi表示第i個類別出現的概率,一般可以通過用屬于此類別的樣本數量除以樣本容量來估計該值。

定義4 ETG 是用戶評論的評分分布熵。一般來說,正常用戶的評分分布不穩定,而水軍的評分分布大多分布在最高分和最低分。因此,正常用戶的評分分布熵較高,而水軍的評分分布熵較低。

定義5 SQD 是用戶評分中最高評分和最低評分在全部評論中的占比。因水軍是為了提高或降低某一商品的評分,故水軍的最高評分和最低評分在全部評論中的占比較高,正常用戶占比較低。

為驗證所選取特征與構建的新特征的有效性,本文利用卡方檢驗算法[13]對上述特征進行相關性驗證,得到的特征P值排序結果,如表3 所示。

表3 特征P 值排序

從表3 可以看出,所提出的SQD、ISR、AW、ERD、ETG 的特征P值分別排在第2 名、第4 名、第5 名、第7 名、第8 名。因此,新構造的5 個特征和數據任務相關性較強,具有一定的有效性。因此,將采用這9 個特征作為水軍特征集。

2.3 FBS 算法模型

結合網絡水軍與正常用戶之間的差異,給出一個能準確反映水軍和正常用戶之間差異的特征集合,采用AP 聚類算法的特征集,引入AP 聚類算法,通過刻畫用戶和用戶之間的相似性,結合同一類別水軍高度相似的特點,解決多類別水軍適應性問題,再通過引入一個合適的歐氏距離閾值Radius,將閾值之內所有未標注用戶標注為其所屬質心的標簽,再將擴充后的標注集通過C4.5 決策樹算法進行分類模型訓練,其流程如圖1 所示。

圖1 FBS 流程

2.4 算法描述和分析

具體算法描述如下。

輸入:Yelp 用戶信息集合U{u1,u2,u3,…,un}

輸出:每個Yelp 用戶u,為水軍的可能性大小y,

方法:按以下步驟執行

步驟1:對于Yelp 用戶u1,按照表2 的內容提取原始特征；

步驟2:利用上一步提取的基礎特征,分別計算AW、ISR、ERD、ETG、SQD；

步驟3:將按上述步驟處理好特征后的數據集輸入到AP 聚類模型中進行聚類,對以標注數據為質心的簇,引入Radius 閾值,將Radius 范圍內所有未標注數據標注未與其所屬質心同一標簽；

步驟4:將步驟3 中得到的新標注集和原始標注集一起輸入到C4.5 決策樹中進行模型訓練；

步驟5:將測試集輸入到步驟4 中訓練好的分類模型中,輸出識別結果每個Yelp 用戶u,為水軍的可能性大小y；

步驟6:計算模型PE 值,算法結束。

2.5 使用的識別器和水軍攻擊策略

將提出的FBS 算法引入到Dou 等[6]提出的水軍對抗模型中,訓練出在YelpChi 上性能更好的識別器。具體使用到的識別算法和水軍攻擊策略如下:

識別器:采用如下幾種識別算法作為博弈中的水軍識別方。

(1)GANG[14]:基于馬爾科夫隨機場的識別器,利用有向圖模型識別水軍用戶的方法。

(2)SpEagle[2]:對用戶、評論與商品組成的馬爾科夫隨機場進行概率推算的識別器。

(3)fBox[14]:基于SVD 的識別器,利用子圖密度尋找小規模的可疑用戶。

(4)Fraudar[11]:找出所有用戶中最善于偽裝的水軍簇的識別器。

(5)FBS:基于用戶行為特征的水軍識別器。

水軍攻擊策略:采用Dou 等[6]提出的IncBP、IncDS、IncPR、Singleton 攻擊方法,具體如下:

(1)IncBP:利用VIP 用戶,盡量避開利用用戶行為特征的FBS 識別器和利用圖形信息的GANG 和SpEagle 識別器。具體是利用在用戶節點組成的馬爾科夫隨機場上進行置信傳播,用可疑度最低的用戶節點發布水軍的虛假評論。

(2)IncDS:每輪先計算用戶節點組成的子圖密度,用子圖密度最小的用戶節點發布水軍的虛假評論。

(3)IncPR:每輪攻擊前計算用戶行為特征的可疑程度,用可疑程度最小的用戶節點發布水軍的虛假評論。

(4)Singleton:創建新用戶,用新用戶發布水軍的虛假評論。

訓練過程如圖2 所示。

圖2 訓練過程

水軍攻擊的實際效應:假設p為水軍的攻擊策略,q為識別器的策略,R(p,q)則為水軍策略為p、識別器策略為q時一輪攻擊之后未被識別出的水軍用戶。這輪水軍攻擊的實際效應算法如下:

水軍的目標就是優化策略p,使PE(v；R,p,q)的值最大化。

識別器的實際目標:優化識別策略q,使PE(v；R,p,q)的值最小化。

水軍和識別器的目標已經確定:水軍要使目標商品的銷售額提升,而識別器要抑制這種提高。雙方將在實際的場景中進行零和博弈,假設水軍攻擊策略為p,識別器策略為q,則雙方的博弈目標:

利用上述的幾種水軍識別算法和水軍攻擊算法進行訓練,最終訓練出Hybrid detect。如此訓練出的水軍識別算法為當前環境下性能最優的水軍識別算法。

3 實驗

實驗運行環境為:Windows10 操作系統,2.90GHz 6 核處理器,16 GB 內存,算法的性能實驗利用PyCharm 軟件實現。

3.1 衡量指標

平均評分的提升或降低會實際影響產品的銷售額,在M Luca 的研究中發現,平均評分每提升1 分(滿分5 分),其銷售額會增長5% ～9%。并且普通用戶與VIP 用戶的評論對商品的銷售額的影響也有所不同,VIP 用戶的評論對產品收益[3]的影響更大。因為他們在評論系統中對產品的評價更重要,比普通用戶的評論更頻繁地呈現給客戶。利用這項研究的結果,設計了一種更能表現水軍實際影響力的指標:實際效應PE。計算方法:

其中,ERI 用來計算VIP 用戶評論的影響,RI 用來計算所有用戶評論的影響。β0和β1是兩種影響的系數,β0=0.035,β1=0.036。這兩個系數的值是用Yelp 的數據估算的。

3.2數據集

為準確地驗證本文所提算法的效果,準備了2 套數據集。第一套為公開數據集YelpChi[1],數據集中包含標記的水軍的虛假評論和正常評論。第二套數據集(YMX)通過購買的方式獲得,其中有300 條水軍的虛假評論為新用戶所發,正常評論是公開數據集YelpNYC[1]中被標記的正常評論。兩套數據集均是在Yelp 平臺獲得的數據。YMX 將作為訓練集使用,YelpChi 將作為測試集使用。

兩個數據集的詳細情況如表4 所示。

表4 數據集詳細信息

水軍攻擊策略設置:在測試集中共添加600 條水軍的虛假評論,包含450 個用戶和100 件商品。

識別策略設置:每一次識別器進行節點可疑度計算之后,將可疑度排名靠前的1%節點作為水軍刪除。

VIP 用戶選擇:由于無法從Yelp 抓取這些用戶的VIP 信息,Yelp 將用戶評論的數量作為是否為VIP 的關鍵因素,因此把每個數據集中單個用戶評論超過10 條的作為VIP 用戶,分別占YelpChi 的1.4%,YMX 的1.2%。

3.3 FBS 算法的驗證

為驗證FBS 算法在Hybrid detect 中的有效性和其在識別模型中的影響,在本文所構建的水軍識別模型的基礎上,將利用加入FBS 的Hybrid detect 和未加入FBS 的Hybrid detect 在數據集YelpChi 的實際效應進行對比,實驗結果如圖3 所示。

圖3 不同的Hybrid detect 的實際效應

由圖3 可以看出,不包含FBS 的Hybrid detect 的實際效應高,能達到4.11。而加入FBS 之后,實際效應能夠降到3.69,說明FBS 能夠有效地識別出原本識別不出的網絡水軍,使模型性能提高。

3.4 對比算法

為驗證本文算法的有效性,實驗選擇的對比算法有GANG、SpEagle、fBox、Fraudar、Nash detect 算法。首先驗證了以GANG、SpEagle、fBox、Fraudar、Prior 算法為基礎訓練出的Nash detect 在數據集(YelpChi)上的效果,再驗證以GANG、SpEagle、fBox、Fraudar、FBS 算法為基礎在訓練出的Hybrid detect 在數據集(YelpChi)上的效果,以此驗證引入FBS 的有效性。再將Hybrid detect 與當前先進的水軍識別模型Tow Face 做對比。

3.5 Hybrid detect 性能測試

表5 顯示了單個識別器面對單個攻擊時的實際效果?？梢钥吹?每個識別器只有識別特定類型的水軍效果較好。如果識別器選用了單個的識別器,那么水軍可以采用相應策略使其效果大大減弱。

表5 識別器對抗各種攻擊的實際效果

在訓練階段,每種識別器的權重每一輪都在改變,變化如圖4 所示,每種識別算法的遺漏水軍數量如圖5所示。

圖4 每種識別器在多輪博弈后的權重

圖5 每種識別器每輪未檢測到的水軍數量

從圖4 可以看出,Hybrid detect 在前40 輪訓練中,各水軍識別算法的權重都在平穩地向最優配置移動。并且在40 輪訓練之后,各個權重都已趨于平穩,說明此時Hybrid detect 已經收斂到最優配置。

從圖5 可以看出,Hybrid detect 在40 輪訓練后漏檢的水軍數量是最少的,并且在40 輪后漏檢水軍數量也不會發生明顯變化,這一結果也和圖4 的結論相同。

在訓練階段,在訓練集上進行了60 輪訓練,混合識別器在最終訓練完成后PE 值明顯低于Nash detect和Tow Face?；旌献R別器在測試集上也取得了最優的成績,其PE 值達到3.69,而其余識別器的PE 值都高于3.9,性能提升約8%。結果如圖6 和圖7 所示。

圖6 每種檢測器在多輪博弈后的實際效應

圖7 幾種識別器在測試集的實際效應

4 結束語

分析了現有的水軍識別器存在的一些問題,利用博弈論的知識對現有識別器進行改進。針對不同場景的水軍,只要設計好目標函數、攻擊方法和識別器,通過運行該算法,就可以在線下找到最優的識別器配置。為解決傳統水軍識別方法中存在的一些問題,提出一種新的水軍識別方法,該方法能充分利用用戶信息的特征。最后,將Hybrid detect 與Nash detect、Two Face這兩種識別器進行對比,實驗結果表明本文的方法具有更好的性能。