彭 飛，曾學文，鄧浩江，劉 磊

(1. 中國科學院大學，北京 100 190；2. 中國科學院聲學研究所國家網(wǎng)絡新媒體工程技術研究中心，北京 10019 0)

基于特征子集的推薦系統(tǒng)托攻擊無監(jiān)督檢測

彭 飛1,2，曾學文2，鄧浩江2，劉 磊2

(1. 中國科學院大學，北京 100 190；2. 中國科學院聲學研究所國家網(wǎng)絡新媒體工程技術研究中心，北京 10019 0)

針對現(xiàn)有基于協(xié)同過濾的推薦系統(tǒng)易受托攻擊影響的問題，提出一種基于特征子集的推薦系統(tǒng)托攻擊無監(jiān)督檢測算法。利用現(xiàn)有攻擊模型在項目選擇上的隨機性，給出一種描述用戶興趣集中程度的特征屬性：興趣峰度系數(shù)。將該系數(shù)與已有的推薦系統(tǒng)用戶特征屬性結合作為備選特征集，采用無監(jiān)督特征選擇方法為不同類型托攻擊選取相應的檢測特征子集。根據(jù)選擇出的特征子集計算每個用戶的離群度，以此進行排序并確定攻擊目標，在已排序的用戶序列上設置滑動窗口，通過計算窗口內(nèi)攻擊目標的平均評分偏移值對攻擊用戶進行過濾。實驗結果證明，興趣峰度系數(shù)的信息增益高于已有的特征屬性，基于特征子集的無監(jiān)督檢測算法相比于現(xiàn)有的無監(jiān)督檢測方法具有更高的穩(wěn)定性和精準度。

推薦系統(tǒng)；托攻擊；無監(jiān)督檢測；特征子集；峰度系數(shù)；滑動窗口

1 概述

隨著互聯(lián)網(wǎng)和信息技術的發(fā)展，人們逐步進入信息過載的時代。如何從海量數(shù)據(jù)中提取出用戶感興趣的內(nèi)容、克服信息不對稱是目前亟需解決的問題。推薦系統(tǒng)一方面幫助普通用戶發(fā)現(xiàn)感興趣的內(nèi)容，另一方面幫助內(nèi)容提供者將信息推送到對它感興趣的用戶面前，從而實現(xiàn)信息生產(chǎn)者和消費者的雙贏。然而，目前主流的基于協(xié)同過濾的推薦方式極易受到托攻擊[1]的影響。通過偽造用戶概貌模型，托攻擊者可以增加或減少目標對象的推薦頻率。例如，在電子商務推薦系統(tǒng)中，某些生產(chǎn)商或店主通過向系統(tǒng)注入虛假用戶評價，增加自己商品的推薦頻度，減少競爭對手商品被推薦的可能性，從而提升自己的收益。如何防范和檢測托攻擊、提升推薦系統(tǒng)的健壯性和穩(wěn)定性成為近年來推薦系統(tǒng)領域的一個研究熱點[2]。

為解決基于協(xié)同過濾的推薦系統(tǒng)易受托攻擊影響的問題，本文一方面利用現(xiàn)有攻擊模型在項目選擇上的隨機性，提出一種描述用戶興趣集中程度的特征屬性：興趣峰度系數(shù)(Kurtosis Coefficient of Interest, KCI)；另一方面，利用無監(jiān)督特征選擇方法，為不同攻擊模型選取針對性的檢測指標，并基于選擇出的指標，設計一種基于特征子集的無監(jiān)督檢測算法，針對不同的攻擊策略選擇相應的特征子集，以此對攻擊用戶進行過濾。

2 研究背景

協(xié)同過濾推薦的準確性有賴于大量用戶的參與，因而推薦系統(tǒng)無法過度限制用戶的操作。攻擊者能以極低的代價向系統(tǒng)中惡意注入虛假概貌，這些概貌的構建方式可使系統(tǒng)中大量用戶的興趣與攻擊者相近，少量的攻擊概貌就能有效操縱推薦結果[2]。托攻擊有2個目的：提高目標項的評價，稱為推攻擊；降低目標項的評價，稱為核攻擊[3]。下文首先對推薦系統(tǒng)托攻擊中的相關定義[4]進行解釋，然后對國內(nèi)外研究現(xiàn)狀進行介紹。

2.1 相關定義

定義1(攻擊概貌) 假定集合I包含系統(tǒng)中所有的項目，集合U包含所有的用戶。一個攻擊概貌[2]由目標項目it∈I、選擇項目集合IS?I、填充項目集合IF?I和未評分的項目集合Iφ4個部分組成。根據(jù)不同的攻擊模型，函數(shù)δ，σ和γ分別設定IS，IF及it的評分值。圖1給出了一個攻擊概貌的一般形式。

圖1 攻擊概貌的一般形式

定義2(攻擊規(guī)模) 攻擊規(guī)模是指向系統(tǒng)中注入的攻擊概貌的數(shù)目與系統(tǒng)中用戶概貌總數(shù)的比值。

定義3(填充規(guī)模) 填充規(guī)模是指在一個攻擊概貌中，被評分的項目數(shù)目與系統(tǒng)中項目總數(shù)的比值。

定義4(攻擊模型) 攻擊模型是一個四元組：

(1)隨機攻擊：該方法對目標項目評最高分，對填充項目按與系統(tǒng)平均分、方差相等的高斯分布隨機評分；

(2)平均攻擊：該方法對目標項目評最高分，對填充項目取其系統(tǒng)平均分；

(3)流行攻擊：該方法對目標項目評最高分，對選擇出的流行項目取其系統(tǒng)平均分，對填充項目按與系統(tǒng)平均分、方差相等的高斯分布隨機評分。

通常使用攻擊規(guī)模和填充規(guī)模來確定攻擊的強度，不同攻擊規(guī)模、填充規(guī)模、攻擊模型對系統(tǒng)會產(chǎn)生不同的影響[5]。

2.2 國內(nèi)外研究現(xiàn)狀

針對推薦系統(tǒng)托攻擊的研究主要包括攻擊檢測以及魯棒性推薦算法兩方面，本文主要對托攻擊的檢測算法進行分析，托攻擊的檢測算法主要有基于監(jiān)督學習和基于無監(jiān)督學習2種思路。

早期的工作大都集中于有監(jiān)督檢測算法。文獻[6]提出了基于用戶概貌統(tǒng)計特征的方法，通過提取正常用戶概貌與攻擊概貌的特征屬性，利用特征值之間的差異檢測攻擊概貌。文獻[7]對攻擊概貌的統(tǒng)計特征進行分析，設計了更多更有效的特征屬性提取方法。文獻[8]則提出了基于特征選擇的檢測方法，進一步提高了有監(jiān)督檢測算法的精準度。

鑒于有監(jiān)督檢測算法固有的局限性，目前的研究更多集中于無監(jiān)督檢測算法。文獻[9]利用奈曼-皮爾遜準則來檢測托攻擊，并分別提出監(jiān)督學習算法和無監(jiān)督學習算法。文獻[10]提出了PLSA(Probabilistic Latent Semantic Analysis)檢測算法與PCA VarSelect(Variable-selection using Principal Component Analysis)檢測算法[11]。PLSA算法利用攻擊用戶間極端相似的特點對其進行聚類識別。PCA VarSelect算法對評分矩陣做主成分分析，并以每個用戶對應的前1至3個主成分系數(shù)的大小作為攻擊檢測的指標。文獻[12]通過計算Hv-score值來尋找攻擊概貌，并以此設計了UnRAP(Unsupervised Retrival of Attack Profiles)算法。

此外，文獻[13]提出了基于信任的不實評價過濾方法，利用用戶的聲譽以及用戶間的信任程度來減輕攻擊用戶對系統(tǒng)的影響。文獻[14]在特征選擇的基礎上，對樸素貝葉斯分類器進行擴展，設計了能夠應對混合攻擊的半監(jiān)督檢測方法。

通過對上述研究分析可以發(fā)現(xiàn)，現(xiàn)有的無監(jiān)督算法都只依賴于某一固定特征，并以此作為攻擊概貌檢測的指標，這種單一的檢測標準在面對不同攻擊場景時，很難保證精準度，并且隨著新的攻擊策略的出現(xiàn)，現(xiàn)有的無監(jiān)督檢測方法也都難以進行調(diào)整和應對。為此，下文將提出興趣峰度系數(shù)(KCI)和基于特征子集的無監(jiān)督檢測方法。

3 興趣峰度系數(shù)

現(xiàn)有的托攻擊檢測特征屬性都是用于衡量攻擊用戶評分的異常程度，而本文提出的KCI還可以對攻擊用戶在項目選擇上的異常信息進行提取。系統(tǒng)中每個項目都具有一些主題關鍵詞來標識該項目的特征，用戶對項目的選擇在一定程度上反映了自己的興趣取向。以MovieLens數(shù)據(jù)集(http://grouplens.com)為例，每個電影都包含幾個反映電影類型的關鍵詞，如cartoon、music、comedy、action等，用戶對電影的選擇反映了用戶對相應電影類型的偏好，例如，兒童會更多地選擇cartoon類型的電影，而年輕人則更可能選擇action類型的電影。因此，一個正常的用戶在選擇電影時會體現(xiàn)出自身對某些特定類型電影的喜好。然而，在現(xiàn)有攻擊策略下，一個托攻擊用戶在選取填充項目時，是隨機選擇的，沒有考慮到用戶對某些電影類型的關注。

為此，本文提出一種描述用戶興趣集中程度的特征屬性：興趣峰度系數(shù)(KCI)。下文以MovieLens數(shù)據(jù)集為例，描述該屬性的計算方法。

矩陣A表示用戶的觀影記錄，是一個m× n大小的矩陣(m表示用戶數(shù)，n表示電影數(shù))，矩陣各項的取值定義如式(1)所示，其中，Rui表示用戶u對電影i的評分，下同。

矩陣M表示電影的類型信息，是一個n× l大小的矩陣(l表示電影類型的數(shù)目)，矩陣各項的取值定義如式(2)所示。

利用上述2個矩陣可以得到用戶對各種電影類型的偏好矩陣T，T的計算方法如式(3)所示，T中的矩陣元素Tus表示了用戶u觀看類型s的電影次數(shù)。

進一步地，采用數(shù)理統(tǒng)計中的峰度系數(shù)來評估用戶對各類電影興趣分布的集中程度。公式如下：

對MovieLens 100K數(shù)據(jù)集進行攻擊規(guī)模為5%、填充規(guī)模為10%的隨機攻擊時，攻擊用戶與真實用戶概貌的KCI分布如圖2所示，KCI值已經(jīng)過歸一化處理。圖中橫軸0表示真實用戶，1表示攻擊用戶。

圖2 興趣峰度系數(shù)分布對比

可以看出，真實用戶的KCI取值集中于0.4～0.6之間，而攻擊用戶KCI取值趨近于0，以此作為分類屬性，對攻擊用戶具有較好的辨識度。

4 基于特征子集的無監(jiān)督檢測算法

在上節(jié)介紹的興趣峰度系數(shù)基礎上，本文引用文獻[7]中定義的10個指標，包括RDMA、WDMA、WDA、Degsim、LengthVar、FMV、FMD、PV、FMTD、TMF以及文獻[12]提出的Hv-score。

本文2.1節(jié)介紹了一些主流的攻擊手段，隨著推薦系統(tǒng)的日益成熟，新的攻擊手段也將逐漸涌現(xiàn)。直接利用上述所有的特征屬性進行托攻擊檢測會有如下問題：有些特征是冗余的甚至是不相關的，冗余特征的存在會降低學習算法的效率，而不相關特征(噪音特征)的存在會有損學習算法的性能。因此，在進行無監(jiān)督檢測之前，有必要對數(shù)據(jù)進行預處理以去除冗余特征和噪音，即進行無監(jiān)督特征選擇。特征選擇的目標可認為是從原始特征子集中選取包含全部或絕大部分信息的特征子集。由于被丟棄的特征幾乎是無信息量的，因此學習算法的性能將會很少降低，甚至由于去掉帶有干擾信息的特征而導致算法性能提高。

為此，本文利用無監(jiān)督特征選擇方法，針對不同攻擊策略，篩選出對于當前場景下最有效的特征子集，選擇方法遵循“最小冗余-最大相關”標準[15]，無監(jiān)督特征選擇方法本身不是本文討論的重點，在文獻[16]中有詳細描述。

在無監(jiān)督特征選擇的基礎上，本文提出一種基于特征子集的推薦系統(tǒng)托攻擊無監(jiān)督檢測算法UnDSA-FS，具體步驟如下：

步驟1為每個用戶計算特征子集中各特征值

針對不同的攻擊策略選擇不同的特征子集，利用上述無監(jiān)督特征子集選擇方法，本文確定3種主流的攻擊策略下，特征子集選擇結果如表1所示。

表1 特征子集選擇結果

計算每個用戶對應特征子集中的各特征值，除了本文提出的興趣峰度系數(shù)外，其他特征屬性的計算方法可參考文獻[7-12]。

步驟2計算每個用戶在特征子集上的離群度

根據(jù)攻擊用戶與真實用戶特征屬性分布的特點，本文采用基于距離和離群點的檢測方法。離群度計算方法如式(7)所示，其中，d( u)表示用戶u的特征子集與其他用戶的距離和；fu和fv表示用戶u和用戶v對于特征f的特征值，F(xiàn)sub即步驟1中選擇出來的特征子集。

步驟3確定攻擊目標項

在步驟2計算出各用戶距離和的基礎上，按降序排列生成用戶排序列表。取前10的用戶，并計算各個項目在前10個用戶中的平均評分偏移。具有最大評分偏移絕對值的項目被視為攻擊目標it。平均評分偏移計算方法如式(8)所示，其中，b( i)表示項目i的平均評分偏移；Ri表示項目i的平均分；U為用戶集合；LN(U)表示用戶排序列表的前N個用戶。同時，根據(jù)目標項的評分偏移b( i)判斷攻擊目的：如果b( i)為正，則為推攻擊；為負值，則為核攻擊。

步驟4確定攻擊用戶

在確定目標項目之后，通過一個滑動窗口(大小設為10)滑過步驟3所得的用戶排序列表，每次滑過一個用戶，計算當前窗口中目標項目的平均評分偏移，當窗口由攻擊用戶富集的部分滑動到正常用戶的范圍時，目標項目的平均評分偏移值就會發(fā)生跳變，返回當前窗口起始位置作為停止點。

然后對停止點之前的排序列表進行分析檢索攻擊用戶，如果沒有對目標項目評分或者對其評分跟攻擊的目的是相反的，則認為是正常用戶，否則視為攻擊用戶。

5 實驗與結果分析

在Movielens 100 K數(shù)據(jù)集上對本文提出的興趣峰度系數(shù)以及基于特征子集的無監(jiān)督檢測算法進行實驗分析。該數(shù)據(jù)集包含943個用戶對1 682部電影的100 000個評分記錄。

5.1 信息增益對比

信息增益是用來度量特征屬性對訓練樣例區(qū)分能力的指標，即系統(tǒng)在有無該屬性時熵的差值。文獻[7]對通用的托攻擊檢測特征屬性的信息增益進行了實驗評估，并發(fā)現(xiàn)RDMA、WDMA、WDA以及LengthVar是最具有辨識度的通用特征屬性。本文將KCI與這些特征進行對比，測試并分析各特征屬性在數(shù)據(jù)集上的信息增益情況。

計算出數(shù)據(jù)集中所有的用戶概貌的各特征值。然后，針對攻擊用戶和真實用戶計算信息增益。圖3～圖5所示結果是100次隨機選取攻擊目標攻擊條件下的各特征屬性的信息增益平均值。圖中展示了隨機攻擊、平均攻擊和流行攻擊在攻擊規(guī)模為3%條件下，不同填充規(guī)模下的信息增益對比?？梢钥闯?，KCI在大多數(shù)填充規(guī)模下的信息增益都優(yōu)于RDMA、WDMA、WDA和LengthVar屬性。只有在填充規(guī)模為1%時，KCI的信息增益不理想，這是由于過少的填充項目無法體現(xiàn)出用戶興趣的分布。上述測試結果充分說明了用戶興趣峰度系數(shù)的作用。

圖3 隨機推攻擊檢測的信息增益對比

圖4 平均推攻擊檢測的信息增益對比

圖5 流行推攻擊檢測的信息增益對比

5.2 Un DSA-FS算法檢測效果對比

托攻擊檢測算法效果的評價采用準確率p、召回率r或兩者的綜合指標F值[17]。計算方法如下：

本文2.2節(jié)介紹了目前已有的一些無監(jiān)督檢測算法，包括PCA VarSelect和UnRAP等。圖6～圖8展示了3種攻擊模型在攻擊規(guī)模為3%時，隨著填充規(guī)模的變化，PCA VarSelect、UnRAP以及UnDSA-FS算法的F值。從中可以看出，在不同填充規(guī)模下，UnRAP算法的穩(wěn)定性和精準度都較差，PCA VarSelect精準度一般，而本文基于特征子集的檢測方法穩(wěn)定性和精準度都較好。

圖6 隨機推攻擊檢測的精準度對比

圖7 平均推攻擊檢測的精準度對比

圖8 流行推攻擊檢測的精準度對比

5.3 Un DSA-FS在不同攻擊場景下的測試

為對UnDSA-FS算法進行全面的評估，本文采取3× 4× 6的設計模式[3]，攻擊模型(隨機攻擊，均值攻擊，流行攻擊)，攻擊規(guī)模(3%, 5%, 10%, 15%)和填充規(guī)模(1%, 3%, 5%, 10%, 15%, 20%)的不同組合對應一組實驗配置。每組實驗配置下，獨立地向數(shù)據(jù)集注入10次推攻擊，最終實驗數(shù)據(jù)是這10次攻擊檢測的均值。

表2～表4展示了UnDSA-FS算法的檢測效果。從中可以看出，本文算法取得了較好的檢測性能，大部分召回率都在90%以上。隨著攻擊規(guī)模和填充率的增大，攻擊概貌的異常程度愈加顯著，可見，本文算法的檢測效果有增強的趨勢。

表2 隨機推攻擊檢測的準確率和召回率

表3 平均推攻擊檢測的準確率和召回率

表4 流行推攻擊檢測的準確率和召回率

6 結束語

本文一方面利用現(xiàn)有攻擊模型在項目選擇上的隨機性，提出一種描述用戶興趣集中程度的特征屬性——興趣峰度系數(shù)。另一方面，利用無監(jiān)督特征選擇方法，為不同類型托攻擊選取有效的檢測指標，并基于選擇出的指標，設計一種基于特征子集的無監(jiān)督檢測算法。該算法在不同攻擊規(guī)模、攻擊模型、填充規(guī)模下都能較好地對攻擊概貌進行檢測。本文提出的是一種對于各種類型推薦系統(tǒng)都適用的通用方法，下一步的工作重點是研究在服務推薦、電子商務等特定領域中托攻擊者的異常特征，進一步提升檢測效果。

[1] Burke R, O’Mahony M P, Hurley N J. Rob ust Collaborative Recommendation[M]. New York, USA: Springer, 2011.

[2] Seminario C E, W ilson D C. Robustness and Accuracy Tradeoffs for Recommender Systems Under Attack[C]//Proc. of the 25th International Florida A rtificial Intelligence Research So ciety Conference. Mar co Island, US A: AAAI Press, 2012: 86-91.

[3] 李 聰, 駱志剛, 石金龍. 一種探測推薦系統(tǒng)托攻擊的無監(jiān)督算法[J]. 自動化學報, 2011, 37(2): 160-167.

[4] 魏 莎. 協(xié)同過濾推薦系統(tǒng)中攻擊概貌檢測算法研究[D].秦皇島: 燕山大學, 2012.

[5] Lee J S, Zhu Dan. Shilling Attack Detection——A N ew Approach for a Trustworthy Recommender System[J]. INFORMS Journal on Computing, 2012, 24(1): 117-131.

[6] Chirita P A, Nejdl W, Zamfir C. Preventing Shilling Attacks in Online Recomm ender Systems[C]//Proc. of ACM International Workshop on Web Information and Data Management. New York, USA: ACM Press, 2005: 67-74.

[7] Burke R, Mobasher B, Williams C, et al. Classification Features for A ttack Detection in Co llaborative Reco mmendation Systems[C]//Proc. of the 12th ACM SI GKDD In ternational Conference on Knowledge Discovery and Data Mining. Philadelphia, USA: ACM Press, 2006: 542-547.

[8] 伍之昂, 莊 毅, 王有權, 等. 基于特征選擇的推薦系統(tǒng)托攻擊檢測算法[J]. 電子學報, 2012, 40(8): 1687-1693.

[9] Hurley N, Cheng Z, Zhang M. Statistical Attack Detection[C]// Proc. of ACM Conferenc e o n Recommen der Systems. New York, USA: ACM Press, 2009: 149-156.

[10] Mehta B, Nejdl W. Unsupervised S trategies for Shilling

Detection and Robust Collaborative Filterin g[J]. User

Modeling and User-adapted Interaction, 2009, 19(1/2): 65-97. [11] Mehta B, Hofmann T, F ankauser P. Lies a nd Propaga nda: Detection Spam Users in Collaborative Filtering[C]//Proc. of the 12th International C onference on Intelligent User Interfaces. New York, USA: ACM Press, 2007: 14-21.

[12] Bryan K, O’Mahony M P, Cun ningham P. Uns upervised Retrieval of A ttack Profiles in C ollaborative R ecommender Systems[C]//Proc. of 2008 ACM Conference on Recommender Systems. New York, USA: ACM Press, 2008: 155-162.

[13] 單明輝, 貢佳煒, 牛爾力, 等. R ulerRep: 一種基于偏離度的過濾不實評價新方法[J]. 計算機學報, 2010, 33(7): 1226-1235.

[14] W u Zhiang, W u Junjie, Cao Jie, et al. HySAD: A Semisupervised H ybrid Shilling A ttack D etector for Trustworthy Product Re commendation[C]//Proc. of the 18th ACM SIGKDD International C onference on Knowledge Discovery and Data Mining. [S. l.]: ACM Press, 2012: 985-993.

[15] Peng Hanchuan, Long Fuhui, Ding C. Feature Selection Based on Mutual Infor mation: Criteria of Max-depend ency, Maxrelevance, and Min-redundancy[J]. IEEE T ransactions on Pattern Analysis and Machine Intelligence, 2005, 27(8): 1226-1238.

[16] 徐峻嶺, 周毓明, 陳 林, 等. 基于互信息的無監(jiān)督特征選擇[J]. 計算機研究與發(fā)展, 2012, 49(2): 372-382.

[17] Lewis D D. A Sequential Algorithm for Training Text Classifiers[C]//Proc. of the 17th Annual International ACM SIGI R Conference on Research a nd Development in I nformation Retrieval. New York, USA: ACM Press, 1994: 3-12.

編輯 金胡考

Unsupervised Detection of Shilling Attack for Recommender System Based on Feature Subset

PENG Fei1,2, ZENG Xue-wen2, DENG Hao-jiang2, LIU Lei2

(1. University of Chinese Academy of Sciences, Beijing 100190, China; 2. National Network New Media Engineering Research Center, Institute of Acoustics, Chinese Academy of Sciences, Beijing 100190, China)

To solve the problem that existing recommender systems based on collaborative filtering are vulnerable to the shilling attac k, this paper proposes an Unsupervised Detection Algorithm of Shilling Attack B ased on Feature Subset(U nDSA-FS). A feature named Kurtosis Coefficient of Interest(KCI) is proposed to describe the intensity degree of user’s interest. Taking the KCI and other existed features as candi date feature set, this algorithm uses unsuperv ised feature selection method to ch oose proper feature su bset for different attack strategies. It computes the distan ce sum of each user, sorts t he users by the distance sum and identifies the atta ck target. It sets a sliding window on the sorted us er sequence, and filters the at tack users by calcu lating the mean rating deviation of attack target. Experimental result verifies that the info rmation gain of KCI is higher than existing features’, and the proposed UnDSA-FS has a better performance in stability and precision compared with existing unsupervised detection methods.

recommender system; shilling attack; unsupervised detection; feature subset; kurtosis coefficient; sliding window

10.3969/j.issn.1000-3428.2014.05.023

國家“863”計劃基金資助項目“融合網(wǎng)絡業(yè)務體系開發(fā)”(2011AA01A102)；國家科技支撐計劃基金資助項目“ACR創(chuàng)新應用示范”(2011BAH19B04)；中國科學院重點部署基金資助項目“NGB有線無線融合開放業(yè)務平臺關鍵技術研究與驗證”(KGZDEW-103-2)。

彭 飛(1988－)，男，博士研究生，主研方向：網(wǎng)絡安全，個性化服務推薦；曾學文、鄧浩江，研究員、博士、博士生導師；劉 磊，副研究員、博士。

2013-03-25

2013-05-27E-mail：pengf@dsp.ac.cn

1000-3428(2014)05-0109-06

A

TP309