基于在線聚類的協同作弊團體識別方法

孫 勇 譚文安 金 婷 周亮廣

1(南京航空航天大學計算機科學與技術學院 南京 211106) 2 (安徽省地理信息集成應用協同創新中心(滁州學院) 安徽滁州 239000) (ysun.nuaa@yahoo.com)

隨著云計算、服務計算以及社會計算等新技術不斷應用于企業信息領域，越來越多的業務過程跨越了企業組織邊界，構成了不同組織間松散耦合的云計算應用系統.云計算的廣泛應用將傳統的封閉、靜態、可控的企業計算環境遷移到以開放、動態、不確定為特征的面向大規模服務計算的分布式系統.支持云計算應用系統的可信服務評估模型正面臨著協同作弊和虛假評價等各種惡意攻擊[1-2]，嚴重影響了企業之間的協同工作效率[3].而且，傳統的服務評估模型只適用于小規模企業信息系統，難以滿足大數據環境下云計算應用系統的服務可信度評估和實時計算的要求.

在互聯網應用中，協同服務系統日志的反饋數據可能存在著大量的虛假內容，嚴重干擾了云計算應用系統從海量的反饋數據中發現高可信的服務.在此背景下，盡管面向服務的云計算應用系統憑借集成第三方服務，降低了業務運作的成本，但也隱藏著巨大的風險.現有的跨組織云平臺缺乏行之有效的可信評價機制應對惡意欺詐行為[4-8]，而是假設反饋用戶的評分值是真實可靠的，不存在虛假行為.但是，在現實世界中，攻擊用戶為了個體組織利益，對某些服務故意給出虛假錯誤的評價，影響了服務協同系統的預測評分質量.虛假用戶可以通過欺詐行為獲取利益，僅靠服務用戶的自律難以確保云端服務的質量，應設計出更有效的可信服務評估機制，以消除欺騙行為所產生的負面影響，為跨組織業務推薦可信的服務，從而提高云計算應用系統的運行穩定性和可靠性[9-10].

服務用戶虛假反饋評價和基于信譽的服務用戶信任分析模型主要研究了個體服務用戶惡意攻擊.針對個體服務用戶的虛假反饋評價，基于偏離率和聲望值的用戶信任評估方法通過迭代計算，分析反饋用戶的評分真實性，從而估算出用戶的信譽值[11].偏離率被用于評價服務用戶的可信性，而聲望值則用來計算服務用戶的重要性.服務用戶的偏離率越大，其可信度越低；用戶的聲望值越大，則表明用戶的重要度越高[12].基于偏離率和聲望值的信任評估方法遏制了個體欺詐提供者的一般惡意行為，但在應對協同作弊及策略攻擊等惡意行為時，缺乏有效的評估機制.

基于聚類的可信度分析算法通過預處理基本用戶信息進行離線聚類，能夠有效地識別出協同作弊問題的服務用戶群體[13-14].然而，大規模服務計算系統的大數據特性直接影響著協同作弊團體識別與檢測的計算速度與質量.傳統基于聚類的可信度分析算法存在居多限制：聚類過程采用了基于完全批量的訓練學習方法，其算法的時間效率較低；當協同計算應用系統日志中服務用戶反饋數據在線更新時，需要重新訓練全部樣本數據，難以適應大規模服務計算環境下服務反饋評分數據量大且變化快的特點.不同于基于完全批量學習的聚類方法，基于隨機梯度下降法的在線聚類模型每次從全部服務反饋訓練樣本中隨機抽取單個樣本，并且僅對一個服務反饋樣本數據進行學習，然后通過調整聚類模型權值參數以減少預測誤差，該方法適用于實時在線服務檢測分析[15-18].基于隨機梯度下降法的在線聚類模型采用了隨機抽樣方法，減小了學習基數的規模量，極大程度地提高了協同作弊群體檢測的時間效率，但是同時也降低了預測精度.

綜上所述，支持跨組織云計算應用的協同作弊用戶在線檢測分析是一個復雜的綜合問題，不僅需要考慮大規模服務計算的時效性問題，而且還需要考慮共謀欺騙檢測與協同作弊用戶團體識別等問題.針對時效性和協作惡意攻擊問題，本文提出了一種基于在線聚類的協同作弊團體識別模型及其高效算法，主要貢獻有3個方面：

1) 綜合考慮大規模服務計算的大數據性特征，提出一種新穎的基于改進更新規則的在線聚類算法，采用小批量學習訓練方法，通過基于自適應權重修正的聚類分組方差計算，并進行遞減增量優化更新規則的動量性參數，以提高在線KMeans算法的聚類質量.

2) 建立了一套協同作弊檢測機制，用以識別出協作虛假攻擊行為.針對惡意團體協同作弊及策略攻擊等惡意行為，充分考慮團體的同謀行為特征和協同攻擊現象，利用聚類的性質以及團體的異常性，提出了基于同謀特征的決策圖檢測方法，快速自動識別出協同作弊行為.

3) 仿真驗證分析了基于在線聚類的協同作弊用戶識別算法，實驗結果表明所提出的在線共謀團體識別算法具有良好時間性能，并有效地解決大規模服務計算中服務協作反饋欺騙的問題.

1 基于改進更新規則的在線聚類

大數據環境下，面向服務的集成應用平臺中不斷涌現出大批量的新用戶及其評價數據，服務用戶的反饋評價具有主觀性高、規范低、更新快以及數量極大等特征，傳統的基于聚類的服務可信度評估算法在進行聚類分析時會造成大量的時間開銷，難以滿足大規模服務可信度評估分析的實時性需求.因此，本文提出了基于改進更新規則的在線KMeans聚類分析技術，針對基于隨機梯度法的在線聚類算法精度問題，采取一種改進的基于小批量學習的在線KMeans聚類算法；并且，通過自動修正權重的聚類分組方差優化方法，提高了在線KMeans算法的聚類質量，同時保證了聚類算法的時間效率.

1.1 在線聚類模型分析

KMeans聚類根據服務特征的相似性，將原始數據集劃分為K個分組(cluster).KMeans聚類的輸入包括類別數目K和訓練樣本數據，輸出則為K個類別的分組集合[19].假設用戶服務評分訓練樣本為R={rt|t=1,2,…,N}，隨機初始化K個聚類中心的參考向量為mi,i=1,2,…,K，根據參考向量mi，將所有的訓練樣本分配到K個用戶聚類分組Gi,i=1,2,…,K中，聚類方法按可計算為

(1)

在每次迭代時，基于大批量學習的KMeans聚類方法求出同類所有用戶的服務評價平均值作為臨時中心點，更新分組中心的方法計算為

(2)

其中，ni為聚類分組Gi的用戶數量.

(3)

其中

(4)

式(3)采用隨機梯度下降法，得到rt的更新變量計算為

(5)

由式(5)可得到rt的更新規則為

mi←mi+η·(rt-mi).

(6)

盡管基于隨機梯度下降的在線聚類算法(SGDKMeans)適用于大規模服務可信度評估分析應用，但是SGDKMeans的聚類質量并不佳.因此，本文采用了基于小批量學習的在線聚類算法(MiniKMeans)，通過小批量樣本學習，逐步考慮小批量樣本實例，每一步進行少許更新.基于小批量學習的在線聚類算法是批量梯度學習法和隨機梯度下降法的一種折衷方案，介于兩者之間.

綜上分析，基于小批量學習的在線聚類算法每次選取適量的訓練樣本進行迭代優化，直到收斂，其算法描述如下：

算法1. 基于小批量學習的在線聚類算法(MiniKMeans).

輸入：服務用戶-服務評分信息D=(U,I,R)、聚類數目K；

輸出：聚類結果.

① 隨機選取K個用戶作為聚類中心；

② 將訓練樣本Batches劃分為多個小樣本batch；

③ REPEAT

④ FORbatchINBatchesDO

⑤ FORrt∈batchDO*用戶評分信息rt屬于小批量樣本中*

⑦ 采用小批量學習的更新規則：mi←mi+η·(rt-mi)；

⑧ END FOR

⑨ END FOR

⑩ UNTILmi收斂.*聚類中心點不變*

根據算法1可知，在每次迭代時，只選擇batch個訓練樣本，其中batch遠小于所有訓練樣本數據，因此，基于小批量學習的在線聚類算法能滿足大規模服務可信度評估分析的在線實時性需求.

1.2 在線聚類算法的更新規則改進

在線KMeans聚類算法是將所有聚類分組中數據對象之間的距離之和作為最小化目標，忽視了每個聚類分組的距離之和不平衡現象，聚類獲得的結果可能存在一種現象：一些分組內的距離之和較大，而另外一些分組的距離之和較小，采用所有分組距離累加的方法掩蓋了某些聚類分組效果不佳的問題，導致在線KMeans聚類算法陷入局部最優[20].針對局部聚類分組的距離誤差優化不平衡問題，基于小批量學習的在線聚類算法引入了自適應加權距離的計算方法，最小化所有聚類分組的最大距離誤差，解決各聚類分組的距離誤差不平衡問題，實現在線聚類的最優化，其定義為

(7)

其中，Emax(mi|rt)是所有聚類分組的最大距離誤差，直接最小化Emax(mi|rt)是一個非常復雜的最優化求解問題.為了適用于在線聚類的優化模式，采用自適應加權距離方法，將Emax(mi|rt)最小化目標松弛為

(8)

(9)

采用拉格朗日乘數法求解式(9)，計算可得：

(10)

(11)

根據更新規則式(11)，將訓練樣本在線地劃分到加權距離最小的聚類分組中，相比于標準的樣本分派距離，改進的更新規則融入了自適應權值修正方法.我們分析加權距離可知，若分組誤差距離大，其權值也大，導致一部分距離該分組較遠的樣本被劃分到其他分組；相反，具有權值較小且誤差距離也小特征的分組吸收到部分樣本.在聚類過程中，通過加權懲罰較高誤差的分組，有效地平衡了局部聚類分組的距離誤差.

(12)

(13)

w(t)=β·w(t-1)+(1-β) ·w(t)，

(14)

其中，β控制了上次權重對當前權值的影響，保證了聚類過程的穩定性.

同時，為了確保在線聚類正常收斂，針對聚類更新規則的動量項參數η難以確定的問題，本文采取一種新的η值計算優化模型，通過逐漸減少動量項參數η以更新聚類中心.

由聚類更新公式可知：

(15)

由式(15)推導可得：

(16)

可得:

(17)

比較式(17)和式(6)，可選取η=1ni.

對于高速公路工程建設過程中的中心試驗室工作人員來講，要根據工程實際施工質量，不斷學習先進的試驗檢測技術，并定期向工程管理人員匯報工作質量，不斷提升高速公路工程的整體管理效率。例如，在某高速公路工程當中，中心試驗室檢測人員通過與工程管理人員進行有效溝通，不僅能夠提升高速公路工程整體管理效率，而且有效降低工程施工材料的損耗率[3]。

綜上分析，基于改進更新規則的在線聚類算法(MyKMeans)通過修改聚類更新規則的參數，進一步優化了基于小批量學習的在線聚類算法，MyKMeans可描述如下：

算法2. 基于改進更新規則的在線聚類算法(MyKMeans).

輸入：服務用戶-服務評分信息D=(U,I,R)和聚類數目k;

輸出：聚類結果.

① 隨機選取K個用戶作為聚類中心；

② 將訓練樣本Batches劃分為多個小樣本batch；

③ REPEAT

④ FORbatchinBatchesDO

⑤ FORrt∈batchDO*用戶評分信息rt屬于小批量樣本中*

⑧ END FOR

⑨ END FOR

⑩ UNTILmi收斂.*聚類中心點不變*

2 協同作弊用戶識別

基于在線聚類的服務可信度分析方法將高相似性的服務用戶劃分到同一個聚類分組，其中可信的反饋評分用戶占著絕大多數.虛假服務用戶與可信服務用戶評價行為存在明顯的不同，2類用戶的評分會出現較大的偏差，通常虛假用戶表現出評價行為高度一致性.因此，當通過在線學習方法計算得出的聚類分組相似度較大時，極有可能是同謀團體.

2.1 協同作弊特征分析

協同作弊行為通常具有3個特征[21]：1)協同作弊團隊表現出明顯的整體性，在評價行為上保持高度的一致性；2)協同作弊團隊與正常用戶相比表現出異常性；3)協同作弊團隊的攻擊時間幾乎相近，因為集中攻擊能提高作弊的效果[22].通過深入分析協同作弊的攻擊行為特征，本文將協同作弊的特征刻畫方法進行了改進，提出一種新的基于協同作弊特征決策圖的檢測方法，用以識別出協同作弊團隊.

協同作弊團體又稱為同謀團體，同謀用戶往往評分較大或較小，有強的關聯性，采用聚類方法能識別協同作弊行為.同謀攻擊者之間具有非常高的一致性特征，其相似度大于0.9，在評價行為上表現出高度的一致性[23-24].因此，相似度極高的聚類分組很有可能是協同作弊團體.

定義1. 協同作弊團體的整體性.針對協同作弊團隊行為高度一致性問題，假設通過基于在線KMeans聚類的計算得到聚類分組為{Gi|i=1,2,…,K}，聚類Gi中ni個用戶反饋數據，采用團體評分一致性(group ratings consistency,GRC)評估聚類分組Gi的行為整體性，GRC(Gi)計算方法可定義為

(18)

GRC(Gi)表示聚類分組Gi整體性的程度，值越小則說明Gi整體性越高.實際上，協同作弊團體不僅具有高度整體性的特征，而且，相對正常用戶，其數量較少.本文不采用平均值描述同謀團體的整體性特征，而是通過對所有值求和來刻畫聚類分組的整體性特征，為了與協同作弊團體的異常性評價數值范圍一致性，采用了協同作弊團體整體性計算值的倒數作為協同作弊的評價指標，其定義為

(19)

當聚類分組的GRC(Gi)值較高時，則表明該聚類分組協同作弊的可能性大.

定義2. 協同作弊團體的異常性.假設通過在線聚類計算得到了K個聚類分組{Gi|i=1,2,…,K}，當協同作弊團隊與正常聚類分組相比，通常表現出異常性.通過計算用戶聚類分組之間的差異性，能夠檢測出同謀團體.因此，定義了一種團體評分偏差度(group ratings deviation,GRD)的指標函數，以識別出協同作弊團體的異常性，GRD定義為

(20)

其中，|R|表示所有的反饋用戶數量;|Gj|代表聚類分組Gj的服務用戶數量；D(·)表示偏差函數；聚類分組整體的偏離度GRD(Gi)大小反映了聚類分組Gi評價與真實值的偏差程度.因此，聚類分組的GRD(Gi)值越大，則表示該聚類分組越有可能是協同作弊團體.

定義3. 協同作弊團體的攻擊時間相似性.協同作弊團體的攻擊時間幾乎相近，因此，將時間作為描述協同作弊團體的輔助評價指標[25-26].通過計算協同作弊團體中評價時間最大值和最小時間之間的時間窗，衡量協作團體的共謀攻擊可能性.時間評價指標采用團體評分的時間相似度(group rating time similarity,GTS)表示，時間窗口函數定義為TW(rj)，表示聚類分組Gi中用戶j的評分時間窗口:

(21)

其中，T(rj)表示用戶j的評分時間，j=1,2,…,K；τ是時間比較參數，表示可能作弊的評分時間窗.

本文采用聚類分組中反饋用戶的最大評價時間窗TW(rj)作為協同作弊的評價指標，其定義如下：

GTS(Gi)=max{TW(rj)}，

(22)

其中，j=1,2,…,K.

針對協同作弊團隊的攻擊行為特征，根據同謀欺騙惡意行為的特征定義，從聚類分組的整體性GRC(Gj)、行為異常性GRD(Gi)以及評分時間相似性GTS(Gi)三個方面進行協同作弊行為的檢測分析.

Rodriguez和Laio[27]最近在《Science》提出了一種密度中心聚類算法，將密度值和斥群值表示在一個2維度的決策圖上，受此算法的啟發，本文提出了一種基于2維特征決策圖的協同作弊團體識別方法，對于每個在線聚類分組，可為其計算出(GRC(Gi),GRD(Gi))，將二元組(GRC(Gi),GRD(Gi))分別以行為整體性為橫軸、行為異常性為縱軸，從而形成了協同作弊特征決策圖，該圖能夠幫助決策者快速發現離群作弊團體.在此基礎上，將攻擊時間作為輔助評價指標，進一步對聚類分組進行評分時間相似性GTS(Gi)計算，以更好地識別出同謀團隊.

2.2 協同作弊團體發現框架與算法

支持跨組織業務應用的協同作弊團體發現算法框架，根據大規模服務系統日志中服務用戶反饋評分信息，綜合考慮大規模服務計算的大數據特性問題.首先采用了一種改進的基于小批量學習的在線聚類方法，并通過自動修正權重的聚類分組方差計算進行遞減增量優化，將所有高相似性的服務用戶聚到同一分組，通過計算目標服務用戶與分組中心的相似性確定其所屬的類別分組；然后，分析團體的同謀行為特征和協同攻擊現象，利用聚類的性質和同謀團體異常性的特征，檢測出協同作弊團體，其算法集成框架如圖1所示:

Fig.1 Integration framework of collaborative collusion evaluation圖1 協同作弊團體發現算法集成框架

綜上所述，基于在線聚類的協同作弊團體發現算法的具體步驟如算法3所示：

算法3. 基于在線聚類的協同作弊團體發現.

輸入：服務用戶-服務評分信息D=(U,I,R)；

輸出：協同作弊團體.

①RData←PreProcess(U,I,R)；*數據預處理*

②Groups←MyKMeans(RData)；*調用基于改進更新規則的在線KMeans算法對所有服務用戶聚類分組*

③ FORGiINGroupsDO*計算分析每個聚類分組*

④ 利用在線聚類求解結果，計算所有服務用戶分組的整體性：

⑥ 計算所有服務用戶分組的攻擊時間相似性：GTS(Gi)←max{TW(rj)},其中，j=1,2,…,K；

⑦ END FOR

⑧DecDiagram(GRC(Gi),GRD(Gi))；

⑨ 利用攻擊時間相似性驗證共謀欺騙分組.

基于在線聚類的協同作弊用戶識別方法的程序執行時間主要是在聚類過程產生的，假定采用基于完全批量的聚類方法，時間復雜度為O(n×K×d×i)；當采用基于隨機梯度下降法的在線聚類方法[28]時，時間復雜度為O(1×K×d×i)；當采用基于小批量在線學習的聚類方法時，時間復雜度為O(m×K×d×i)，其中，n和m是聚類訓練樣本數量，K為聚類的分組數，d為特征屬性維度，i表示迭代次數.由于n?m>1，總體而言，基于在線聚類的協同作弊檢測算法極大地減少了聚類的計算時間，同時，基于協同作弊特征決策圖的識別方法保證了對共謀檢測的正確性.

3 仿真實驗

本文實驗環境基于Intel I5-7300 HQ筆記本，CPU主頻為2.50 GHz，內存為8.00 GB，所有算法都運用Python編程語言，采用了PyCharm編譯工具，運行在Windows 10操作系統上.為了驗證所提出算法的可行性和有效性，本節將在不同規模的人工合成數據集、UCI真實數據集以及服務計算等真實數據集上進行了一系列的仿真實驗.

3.1 人工數據集仿真實例

本節仿真實例將在不同規模人工合成數據集上，分別從在線服務用戶聚類分析與基于改進在線聚類的協同作弊用戶識別2個方面運用可視化方法對本文方法進行分析和說明.

3.1.1 基于在線學習的服務用戶聚類分析

首先，仿真實驗對在線聚類算法進行了收斂性分析，在線聚類分析實驗過程中，采用了Scikit-learn的數據分析函數，以[1,1],[1,3],[3,3],[3,1]為中心生成了10 000個人工合成數據，對比分析了基于隨機梯度下降的在線聚類算法(SGDKMeans)、基于小批量學習的在線聚類算法(MiniKMeans)以及基于改進更新規則的在線聚類算法(MyKMeans)的收斂速度.在聚類過程中，批量規模取值為500，3種算法在給定的人工合成數據集上運行20次，并計算出算法收斂時間的平均值，實驗結果如圖2和圖3所示:

Fig.2 Convergence rate analysis of online clustering (Samples=5 000)圖2 在線聚類收斂速度分析(Samples=5 000)

Fig.3 Convergence rate analysis of online clustering (Samples=10 000)圖3 在線聚類收斂速度分析(Samples=10 000)

圖2的訓練樣本數據的數量為5 000，而圖3的樣本數目為10 000.通過觀察可知，SGDKMeans算法、MiniKMeans算法以及MyKMeans算法都能以較快的速度收斂，適用于大規模服務計算.但是，MyKMeans和MiniKMeans的聚類質量明顯好于SGDKMeans算法；并且，本文所提出的在線聚類算法MyKMeans的收斂效果更優于MiniKMeans算法.

針對KMeans聚類的分組數目的確定問題，基于改進更新規則的在線聚類算法(MyKMeans)采用了基于拐點的聚類數目確定方法，首先隨機選取訓練樣本數據中的K個點作為起始點，當K值確定后，隨機進行聚類計算n次，取得最小開銷函數值的K作為最終聚類結果，避免隨機引起的局部最優解；并通過繪制出K-開銷函數散點圖，選取有明顯拐點的開銷函數值，設為K值，如圖4所示.

在線聚類效果分析實驗主要采用了Scikit-learn的數據分析函數，同樣以[1,1],[1,3],[3,3],[3,1]為中心，生成了10 000個人工合成數據，分別應用KMeans+ +聚類算法、改進前的基于小批量學習的在線聚類算法(MiniKMeans)以及提出的基于改進更新規則的在線聚類算法(MyKMeans)進行了仿真模擬，實驗效果如圖5所示.其中ObjCost值表示誤差平方和值，KMeans+ +的誤差平方和最小，其ObjCost值為1.162 036;MiniKMeans的誤差平方和值最大，其ObjCost值為1.180 610；而MyKMeans的ObjCost值為1.165 977，幾乎和KMeans+ +接近，好于MiniKMeans算法，取得了良好的聚類效果.

Fig. 4 K value confirmation of online clustering for MyKMeans圖4 MyKMeans在線聚類K值選取分析

Fig. 5 Effective analysis of user clustering based on online learning圖5 基于在線學習的用戶聚類效果分析

Fig. 6 Silhouette coefficient analysis of online clustering圖6 基于輪廓系數的在線聚類效果分析

在線聚類效果分析實驗進一步采用輪廓系數，評估分析了KMeans+ +和MyKMeans算法的聚類效果，實驗結果如圖6所示.其中，KMeans+ +算法效果稍好于MyKMeans算法，MyKMeans算法與KMeans+ +算法的輪廓系數值幾乎相同.

在驗證所提出的基于改進更新規則的在線聚類算法(MyKMeans)的時效性時，為使得實驗結果對比反差更大，效果更明顯直觀，算法時間效率實驗生成3種規模間隔更大的人工數據[2 000,5 000,10 000]，并將KMeans+ +，MiniKMeans，以及MyKMeans算法運行在該人工數據集上，3種算法的時間性能分析實驗結果如圖7所示.其中，MyKMeans算法的時間效率與改進前的MiniKMeans算法接近，都明顯好于KMeans+ +算法，特別是隨著樣本數量的不斷增多，MyKMeans算法比KMeans+ +算法效率表現得更好.

由實驗分析可知，所提出的MyKMeans算法不僅表現出良好的算法時效性，而且具有較好的算法精度.

Fig. 7 Time efficiency analysis of clustering algorithm圖7 聚類算法的時間效率分析

3.1.2 協同作弊特征決策圖可視化分析

Fig. 8 Binary decision diagrams of collaborative collusion features圖8 協同作弊特征2維決策圖分析

協同作弊用戶分組檢測實驗采用人工合成數據方法，針對協同作弊團隊的攻擊問題，根據協同作弊惡意行為的特征定義，從聚類分組的整體性、行為異常性以及評分時間相似性3個方面進行協同作弊檢測分析.對于每一聚類分組，計算出聚類分組行為的GRC(Gi)和異常性值GRD(Gi)二元組，分別以行為整體性的取值為橫軸、行為異常性值為縱軸，從而形成了協同作弊特征決策圖，為用戶可信度評估分析提供了決策支持，如圖8所示.

通過觀察圖8可知，聚類分組3和分組6由于同時具有較大的GRC(Gi)和GRD(Gi)值，于是從其他聚類分組中脫穎而出，從而幫助管理者直觀地快速檢測出協同作弊團體.因此可見，協同作弊特征決策圖方法能夠有效地呈現出共謀團體.在此基礎上，可將攻擊時間作為輔助評價指標，進一步對聚類分組3和6進行評分時間相似性GTS(Gi)計算，以更好地識別出協同作弊團隊.

3.2 真實數據集仿真實例

本節實驗采用了真實數據集，分別從聚類精度和時間效率2個方面測試了本文提出算法MyKMeans的有效性和可行性.其中，仿真實驗從UCI機器學習數據庫[29]中選擇了Iris，Digits，20newsgroup以及在WS-DREAM數據集[30]中選取了wsdata1和wsdata2等真實數據集，相關數據集的信息如表1所示：

Table 1 Real Data Analysis表1 真實實驗數據分析

3.2.1 在線聚類算法的精度分析

在聚類精度實驗過程中，將采用聚類性能度量函數分析聚類結果的精確度，度量函數指標包括6個聚類有效性評測指標：1)類內聚合度Inertia；2)調整蘭德指標(adjusted rand index,ARI)；3)調整互信息(adjusted mutual information,AMI)；4)同質性指標(homogeneity,Homo)；5)完整性指標(completeness,Compl)；6)調和平均指標(V-measure,V-meas).其中，類內聚合度Inertia是類內聚合度的一種度量方式，當Inertia值越小時，聚類效果越好；調整蘭德指數ARI是一個外部評測指標，根據數據真實分類標簽，測試數據的聚類結果與實際分類之間的相似度；當聚類精度越高時，即聚類結果越近似于實際分類，ARI值也越高；調整互信息AMI是利用基于互信息的方法來衡量聚類效果，當聚類結果越近似于實際分類，AMI值也越高；同質性指標Homo是分析每個聚類是否只包含單個類別的成員；完整性指標Compl則是分析給定類的所有成員是否都分配給了同一聚類分組；而調和平均指標V-meas表示Homo和Compl兩者的調和平均，V-meas,Homo,Compl的值在0～1之間，值越大則表明聚類效果越佳.

首先，我們采用了UCI分類數據集Iris進行精度仿真實驗，Iris數據集包含了150個數據樣本，分為了3類，每類有50個數據，每個樣本數據包含4個屬性特征.數據集Iris的聚類精度實驗結果如表2所示：

Table 2 Clustering Accuracy Analysis of Iris Data表2 Iris實驗數據的聚類精度分析

其次，我們采用了UCI手寫數字圖像訓練集Digits進行精度仿真實驗，Digits共有1767個手寫數字的圖像矩陣，每個手寫數字圖像都儲存成為8×8的矩陣，每個像素表示一個特征.因此，Digits原始數據是64個特征.數據集Digits的聚類精度仿真實驗結果如表3所示：

Table 3 Clustering Accuracy Analysis of Digits Data表3 Digits實驗數據的聚類精度分析

最后，我們采用了UCI機器學習庫的20新聞語料數據集(20newsgroup)進行精度仿真實驗，本次實驗抽取了20newsgroup數據集中4個不同話題的新聞組信息，包含了2 034個新聞語料樣本數據，每個樣本的特征維度是4 331.在聚類處理過程中，首先采集數據并提取特征，將有噪文本轉化為向量表征；然后進行聚類模型訓練實驗.數據集20newsgroup的聚類精度實驗結果如表4所示：

Table 4 Clustering Accuracy Analysis of 20newsgroup Data表4 20newsgroup實驗數據的聚類精度分析

通過觀察表2～4，可以得出以下結論：本文提出的改進聚類算法MyKMeans，在3個真實數據集上的聚類效果均優于SGDKMeans和MiniKMeans算法，表現出了良好的算法性能.

3.2.2 在線聚類算法的時間性能分析

本次實驗將從不同規模的樣本數量和不同數量的屬性特征2方面，在真實新聞語料數據集20newsgroup上驗證分析了本文相關的聚類算法的時間效率.圖9是基于不同數據規模的聚類時間性能實驗結果，驗證了本文相關聚類算法的時間相對于不同規模樣本數量的變化情況，隨著規模增加，聚類處理時間不斷增加.圖10是基于不同維度屬性特征的聚類時間性能實驗結果，主要分析了在不同屬性特征數量的變化情況下本文相關聚類算法的時間性能.由圖10可知，隨著維度增加，聚類處理時間不斷增加.

Fig. 9 Time efficiency analysis of clustering algorithms圖9 不同數據規模的聚類算法時間效率分析

Fig. 10 Time efficiency analysis of clustering algorithms圖10 不同屬性特征規模的聚類算法時間效率分析

通過觀察聚類實驗結果圖9和圖10，可得出以下結論：在數據集20newsgroup的不同數據規模和屬性特征數的變化情況下，MyKMeans的聚類時間性能遠優于KMeans和KMeans+ +聚類算法，與MiniKMeans算法的時間性能接近.由此分析，本文所提出的在線聚類算法在真實數據集表現出良好的算法時效性，而且具有較好的算法精度，進一步驗證說明了本文提出算法的可行性和有效性.

3.2.3 協同作弊用戶分組識別算法的分析實驗

協同作弊團體識別實驗采用了真實的WS-DREAM數據集wsdata1和wsdata2，其中wsdata1和wsdata2是用于服務用戶評價和服務推薦的數據集，根據共謀作弊惡意行為的特征，我們分別對WS-DREAM的2個數據集進行了攻擊.然后，運用在線聚類算法MyKMeans對WS-DREAM數據集進行聚類分組，并在此基礎上，采用本文的在線協同作弊團體識別方法，計算出每個聚類分組的行為二元組：整體性值GRC(Gi)和異常性值GRD(Gi).其中，表5是wsdata1數據集的所有聚類分組的特征行為二元組值.

Table 5 Analysis of wsdata1 Collusion Features表5 wsdata1協同作弊檢測分析

在此基礎上，我們采用共謀特征決策圖方法，分析了每個聚類分組的行為，如圖11和圖12所示：

Fig. 11 Analysis of wsdata1 collusion features圖11 wsdata1協同作弊檢測分析

Fig. 12 Analysis of wsdata2 collusion features圖12 wsdata2協同作弊檢測分析

在圖11中，具有共謀特征的聚類分組1、分組2以及分組3都有較大的GRC(Gi)和GRD(Gi)值，并且遠離正常聚類分組，于是被識別出來；同樣，在圖12中，聚類分組1和分組3也是同時具有較大的GRC(Gi)和GRD(Gi)值，在基于作弊特征二元決策圖的可視化方法幫助下，我們有效地區分出了正常聚類分組和共謀團體.而且，通過綜合分析實驗結果表5和圖11～12可知，相對于表格分析方法，基于特征決策圖的檢測方法更容易識別出具有協同作弊特征的聚類分組.在真實數據集wsdata1和wsdata2上，基于特征決策圖的協同作弊團隊發現方法表現出了良好的識別效果，驗證分析了本文所提出的協同作弊團隊識別方法.

4 總結與展望

針對大規模服務計算的大數據特性，提出了基于改進更新規則的在線聚類算法，采取改進的基于小批量學習的在線KMeans聚類算法，并通過自動修正權重的聚類分組方差優化方法，提高了在線KMeans聚類算法的解質量，同時保證了聚類算法的時間效率；進一步，基于在線聚類分組的基礎上，充分考慮協同作弊及策略攻擊等惡意行為的特征，定義了同謀攻擊的一致性、異常性以及時間相似等檢測指標函數，設計了一個基于協同作弊特征決策圖的共謀團體識別方法，采用可視化的方式分析了聚類分組的情況.通過在線聚類和協同作弊檢測方法，實現了共謀團體的快速識別，本文主要工作包括：1)提出了基于改進更新規則的在線聚類算法；2)提出了在線協同作弊團體發現算法，為面向服務的云計算應用系統集成可信服務提供了技術支持；3)仿真實驗分析了基于在線聚類的協同作弊團體識別方法的可行性.實驗結果表明，提出的算法通過融合在線聚類與共謀欺騙檢測技術，有效地解決了大規模服務計算中協同反饋欺騙問題.

基于在線學習的協同作弊團體識別方法能夠快速檢測出共謀欺騙用戶，為可信分析提供決策支持，因此，在可信計算與服務推薦系統領域有著重要的應用前景.當前，基于在線學習的協同作弊團體識別方法面臨各種挑戰，特別是如何有效地使用分布式數據和并行計算技術，基于并行在線學習的協同作弊團體識別問題有待人們進一步深入探索和解決.

[1]Jiang Meng, Cui Peng, Faloutsos C. Suspicious behavior detection: Current trends and future directions[J]. IEEE Intelligent Systems, 2016, 31(1): 31-39

[2]Wang Haiyan, Yang Wenbin, Wang Suichang, et al. A service recommendation method based on trustworthy community[J]. Chinese Journal of Computers, 2014, 37(2): 301-311 (in Chinese)(王海艷, 楊文彬, 王隨昌, 等. 基于可信聯盟的服務推薦方法[J]. 計算機學報, 2014, 37(2): 301-311)

[3]Sun Yong, Tan Wenan. Cross-organizational workflow task allocation algorithms for socially aware collaborative computing[J]. Journal of Computer Research and Development, 2017, 54(9): 1865-1879 (in Chinese)(孫勇, 譚文安. 支持社會協同計算的跨組織工作流任務分派算法[J]. 計算機研究與發展, 2017, 54(9): 1865-1879)

[4]Bouguettaya A, Singh M, Huhns M, et al. A service computing manifesto: The next 10 years[J]. Communications of the ACM, 2016, 60(4): 64-72

[5]Meng Xiaofeng, Li Yong, Zhu Jianhua. Social computing in the era of big data: Opportunities and challenges[J]. Journal of Computer Research and Development, 2013, 50(12): 2483-2491 (in Chinese)(孟小峰, 李勇, 祝建華. 社會計算: 大數據時代的機遇與挑戰[J]. 計算機研究與發展, 2013, 50(12): 2483-2491)

[6]Wu Zhiang, Zhuang Yi, Wang Youquan, et al. Shilling attack detection based on feature selection for recommender systems[J]. Acta Electronica Sinica, 2012, 40(8): 1687-1693 (in Chinese)(伍之昂, 莊毅, 王有權, 等. 基于特征選擇的推薦系統托攻擊檢測算法[J]. 電子學報, 2012, 40(8): 1687-1693)

[7]Burke R, Mobasher B, Williams C, et al. Classification features for attack detection in collaborative recommendation systems[C]Proc of the 12th Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2006: 542-547

[8]Wu Zhiang, Wang Youquan, Cao Jie. A survey on shilling attack models and detection techniques for recommender systems[J]. China Science Bull, 2014, 59(7): 551-560 (in Chinese)(伍之昂, 王有權, 曹杰. 推薦系統托攻擊模型與檢測技術[J]. 科學通報, 2014, 59(7): 551-560)

[9]Tan Wenan, Sun Yong, Li Lingxia, et al. A trust service-oriented scheduling model for workflow applications in cloud computing[J]. IEEE Systems Journal, 2014, 8(3): 868-878

[10]Sun Yong, Tan Wenan, Li Lingxia, et al. A new method to identify collaborative partners in social service provider networks[J]. Information Systems Frontiers, 2016, 18(3): 565-578

[11]Li Baichuan, Li Ronghua, King I, et al. A topic-biased user reputation model in rating systems[J]. Knowledge and Information Systems, 2015, 44(3): 581-607

[12]Li Ronghua, Yu Xu, Huang Xin, et al. Robust reputation-based ranking on bipartite rating the networks[C]Proc of the 12th SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2012: 612-623

[13]Chandola V, Banerjee A, Kumar V. Anomaly detection: A survey[J]. ACM Computer Survey, 2009, 41(3): 1-15

[14]Vasilomanolakis E, Karuppayah S, Mühlh?user M, et al. Taxonomy and survey of collaborative intrusion detection[J]. ACM Computing Surveys, 2015, 47(4): 55:1-55:33

[15]Yang Haiqin, Lu Rongcong, Jin Guoqing. Big data oriented online learning algorithms[J]. Communications of CCF, 2014, 10(11): 36-40 (in Chinese)(楊海欽, 呂榮聰, 金國慶. 面向大數據的在線學習算法[J]. 中國計算機學會通訊, 2014, 10(11): 36-40)

[16]Yang Haiqin, Lyu M R, King I. Efficient online learning for multitask feature selection[J]. ACM Trans on Knowledge Discovery from Data, 2013, 7(2): 1-27

[17]Orabona F, Crammer K, Cesa-Bianchi N. A generalized online mirror descent with applications to classification and regression[J]. Machine Learning, 2015, 99(3): 411-435

[18]Shalev-Shwartz S. Online learning and online convex optimization[J]. Foundations & Trends in Machine Learning, 2012, 4(2): 107-194

[19]Poole D L, Mackworth A K. Artificial Intelligence: Foundations of Computational Agents[M]. Cambridge, UK: Cambridge University Press, 2010

[20]Tzortzis G, Likas A, Tzortzis G. The MinMaxk-Means clustering algorithm[J]. Pattern Recognition, 2014, 47(7): 2505-2516

[21]Miao Guangsheng, Feng Dengguo, Su Purui. A collusion detector based on fuzzy logic in P2P trust model[J]. Journal of Computer Research and Development, 2011, 48(12): 2187-2200 (in Chinese)(苗光勝, 馮登國, 蘇璞睿. P2P信任模型中基于模糊邏輯的共謀團體識別方法[J]. 計算機研究與發展, 2011, 48(12): 2187-2200)

[22]Miao Guangsheng, Feng Dengguo, Su Purui. Colluding clique detector based on activity similarity in P2P trust model[J]. Journal on Communications, 2009, 30(8): 9-20 (in Chinese)(苗光勝, 馮登國, 蘇璞睿. P2P信任模型中基于行為相似度的共謀團體識別模型[J]. 通信學報, 2009, 30(8): 9-20)

[23]Mehta B, Nejdl W. Unsupervised strategies for shilling detection and robust collaborative filtering[J]. User Modeling and User-Adapted Interaction, 2009, 19(12): 65-97

[24]Gunes I, Kaleli C, Bilge A, et al. Shilling attacks against recommender systems: A comprehensive survey[J]. Artificial Intelligence Review, 2014, 42(4): 767-799

[25]Mukherjee A, Liu Bing, Wang Junhui, et al. Detecting group review spam[C]Proc of the 20th Int Conf on World Wide Web. New York: ACM, 2011: 93-94

[26]Mukherjee A, Liu Bing, Glance N. Spotting fake reviewer groups in consumer reviews[C]Proc of the 20th Int Conf on World Wide Web. New York: ACM, 2012: 191-200

[27]Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496

[28]Kanungo T, Mount D M, Netanyahu N S, et al. An efficientk-means clustering algorithm: Analysis and implementation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2002, 24(7): 881-892

[29]University of California, School of Information and Computer Science. UCI Machine Learning Repository[EBOL]. (2007-06-25) [2013-04-04]. http:archive.ics.uci.eduml

[30]The Chinese University of Hong Kong. WS-DREAM: Towards Open Datasets and Source Code for Web Service Research[EBOL]. (2015-08-29) [2017-08-18]. https:wsdream.github.io

SunYong, born in 1977. PhD. Member of CCF. His main research interests include cooperative computing, service computing, social workflow scheduling, intelligent infor-mation systems, and software engineering.

TanWenan, born in 1965. PhD, professor, PhD supervisor. Senior member of CCF. His main research interests include software engineering, process engineering and development environment, enterprise dynamic modeling, trusted service comput-ation, and enterprise intelligent information systems.

JinTing, born in 1994. MSc candidate. Her main research interests include coo-perative computing and service computing.

ZhouLiangguang, born in 1981. MSc. His main research interests include data mining and geographic information science.