孫 勇 譚文安 金 婷 周亮廣

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

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

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

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

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

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

1) 綜合考慮大規(guī)模服務(wù)計算的大數(shù)據(jù)性特征，提出一種新穎的基于改進更新規(guī)則的在線聚類算法，采用小批量學(xué)習(xí)訓(xùn)練方法，通過基于自適應(yīng)權(quán)重修正的聚類分組方差計算，并進行遞減增量優(yōu)化更新規(guī)則的動量性參數(shù)，以提高在線KMeans算法的聚類質(zhì)量.

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

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

1 基于改進更新規(guī)則的在線聚類

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

1.1 在線聚類模型分析

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

(1)

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

(2)

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

(3)

其中

(4)

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

(5)

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

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

(6)

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

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

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

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

輸出：聚類結(jié)果.

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

② 將訓(xùn)練樣本Batches劃分為多個小樣本batch；

③ REPEAT

④ FORbatchINBatchesDO

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

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

⑧ END FOR

⑨ END FOR

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

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

1.2 在線聚類算法的更新規(guī)則改進

在線KMeans聚類算法是將所有聚類分組中數(shù)據(jù)對象之間的距離之和作為最小化目標(biāo)，忽視了每個聚類分組的距離之和不平衡現(xiàn)象，聚類獲得的結(jié)果可能存在一種現(xiàn)象：一些分組內(nèi)的距離之和較大，而另外一些分組的距離之和較小，采用所有分組距離累加的方法掩蓋了某些聚類分組效果不佳的問題，導(dǎo)致在線KMeans聚類算法陷入局部最優(yōu)[20].針對局部聚類分組的距離誤差優(yōu)化不平衡問題，基于小批量學(xué)習(xí)的在線聚類算法引入了自適應(yīng)加權(quán)距離的計算方法，最小化所有聚類分組的最大距離誤差，解決各聚類分組的距離誤差不平衡問題，實現(xiàn)在線聚類的最優(yōu)化，其定義為

(7)

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

(8)

(9)

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

(10)

(11)

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

(12)

(13)

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

(14)

其中，β控制了上次權(quán)重對當(dāng)前權(quán)值的影響，保證了聚類過程的穩(wěn)定性.

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

由聚類更新公式可知：

(15)

由式(15)推導(dǎo)可得：

(16)

可得:

(17)

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

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

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

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

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

輸出：聚類結(jié)果.

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

② 將訓(xùn)練樣本Batches劃分為多個小樣本batch；

③ REPEAT

④ FORbatchinBatchesDO

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

⑧ END FOR

⑨ END FOR

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

2 協(xié)同作弊用戶識別

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

2.1 協(xié)同作弊特征分析

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

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

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

(18)

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

(19)

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

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

(20)

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

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

(21)

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

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

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

(22)

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

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

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

2.2 協(xié)同作弊團體發(fā)現(xiàn)框架與算法

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

Fig.1 Integration framework of collaborative collusion evaluation圖1 協(xié)同作弊團體發(fā)現(xiàn)算法集成框架

綜上所述，基于在線聚類的協(xié)同作弊團體發(fā)現(xiàn)算法的具體步驟如算法3所示：

算法3. 基于在線聚類的協(xié)同作弊團體發(fā)現(xiàn).

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

輸出：協(xié)同作弊團體.

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

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

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

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

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

⑦ END FOR

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

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

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

3 仿真實驗

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

3.1 人工數(shù)據(jù)集仿真實例

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

3.1.1 基于在線學(xué)習(xí)的服務(wù)用戶聚類分析

首先，仿真實驗對在線聚類算法進行了收斂性分析，在線聚類分析實驗過程中，采用了Scikit-learn的數(shù)據(jù)分析函數(shù)，以[1,1],[1,3],[3,3],[3,1]為中心生成了10 000個人工合成數(shù)據(jù)，對比分析了基于隨機梯度下降的在線聚類算法(SGDKMeans)、基于小批量學(xué)習(xí)的在線聚類算法(MiniKMeans)以及基于改進更新規(guī)則的在線聚類算法(MyKMeans)的收斂速度.在聚類過程中，批量規(guī)模取值為500，3種算法在給定的人工合成數(shù)據(jù)集上運行20次，并計算出算法收斂時間的平均值，實驗結(jié)果如圖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的訓(xùn)練樣本數(shù)據(jù)的數(shù)量為5 000，而圖3的樣本數(shù)目為10 000.通過觀察可知，SGDKMeans算法、MiniKMeans算法以及MyKMeans算法都能以較快的速度收斂，適用于大規(guī)模服務(wù)計算.但是，MyKMeans和MiniKMeans的聚類質(zhì)量明顯好于SGDKMeans算法；并且，本文所提出的在線聚類算法MyKMeans的收斂效果更優(yōu)于MiniKMeans算法.

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

在線聚類效果分析實驗主要采用了Scikit-learn的數(shù)據(jù)分析函數(shù)，同樣以[1,1],[1,3],[3,3],[3,1]為中心，生成了10 000個人工合成數(shù)據(jù)，分別應(yīng)用KMeans+ +聚類算法、改進前的基于小批量學(xué)習(xí)的在線聚類算法(MiniKMeans)以及提出的基于改進更新規(guī)則的在線聚類算法(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 基于在線學(xué)習(xí)的用戶聚類效果分析

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

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

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

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

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

3.1.2 協(xié)同作弊特征決策圖可視化分析

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

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

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

3.2 真實數(shù)據(jù)集仿真實例

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

Table 1 Real Data Analysis表1 真實實驗數(shù)據(jù)分析

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

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

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

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

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

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

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

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

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

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

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

Fig. 9 Time efficiency analysis of clustering algorithms圖9 不同數(shù)據(jù)規(guī)模的聚類算法時間效率分析

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

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

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

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

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

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

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

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

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

4 總結(jié)與展望

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

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

[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)(王海艷, 楊文彬, 王隨昌, 等. 基于可信聯(lián)盟的服務(wù)推薦方法[J]. 計算機學(xué)報, 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)(孫勇, 譚文安. 支持社會協(xié)同計算的跨組織工作流任務(wù)分派算法[J]. 計算機研究與發(fā)展, 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)(孟小峰, 李勇, 祝建華. 社會計算: 大數(shù)據(jù)時代的機遇與挑戰(zhàn)[J]. 計算機研究與發(fā)展, 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)(伍之昂, 莊毅, 王有權(quán), 等. 基于特征選擇的推薦系統(tǒng)托攻擊檢測算法[J]. 電子學(xué)報, 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)(伍之昂, 王有權(quán), 曹杰. 推薦系統(tǒng)托攻擊模型與檢測技術(shù)[J]. 科學(xué)通報, 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)(楊海欽, 呂榮聰, 金國慶. 面向大數(shù)據(jù)的在線學(xué)習(xí)算法[J]. 中國計算機學(xué)會通訊, 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]. 計算機研究與發(fā)展, 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]. 通信學(xué)報, 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.