呂成戍，王維國

（1.東北財經(jīng)大學管理科學與工程學院，遼寧 大連116025；2.東北財經(jīng)大學數(shù)學與數(shù)量經(jīng)濟學院，遼寧 大連116025）

1 引言

最近的研究表明，由于推薦系統(tǒng)的開放性以及用戶的參與性協(xié)同過濾算法很容易遭到人為攻擊［1］。攻擊者通過向推薦系統(tǒng)注入虛假用戶概貌，使其推薦結(jié)果符合自己的商業(yè)利益。這種攻擊被稱為“托攻擊（Shilling Attacks）”或“用戶概貌注入攻擊”［2，3］。托攻擊檢測技術近年來引起了學術界的廣泛關注，并已成為當前推薦系統(tǒng)領域的研究熱點之一。

支 持 向 量 機 SVM （Support Vector Machines）［4］的成功促使其被應用到推薦系統(tǒng)托攻擊檢測中［5］，使用支持向量機方法進行托攻擊檢測的效果雖然優(yōu)于決策樹、神經(jīng)網(wǎng)絡等傳統(tǒng)機器學習方法，但是在托攻擊檢測中面臨數(shù)據(jù)不均衡和代價敏感兩個難題，直接應用支持向量機方法效果仍然不夠理想。一方面由于攻擊強度不宜過大，否則易于被檢測［6］，因此訓練集中攻擊用戶樣本的數(shù)量往往遠小于正常用戶樣本的數(shù)量，即樣本集呈現(xiàn)不均衡分布特性，這會直接影響支持向量機的泛化能力；另一方面，由于推薦系統(tǒng)中用戶基數(shù)很大，推薦過程中錯誤地屏蔽一些正常用戶并不會對推薦結(jié)果產(chǎn)生顯著影響，但誤判一些攻擊用戶就有可能會改變推薦結(jié)果［7］，因此攻擊用戶和正常用戶的誤分類代價是不同的，以分類正確率作為方法的評價依據(jù)不適合處理代價敏感問題。目前，SVM在模式分類研究中已經(jīng)部分解決這兩方面問題。其中，有基于數(shù)據(jù)重采樣的方法［8，9］，對數(shù)據(jù)進行預處理，降低不均衡程度；也有基于代價敏感學習的方法［10，11］，通過在支持向量機方法中集成不同誤分類代價，使之適應代價敏感分類問題。但是，大多數(shù)研究仍集中于單純的數(shù)據(jù)集重采樣或者代價敏感學習，而忽略了實際模式分類問題，如推薦系統(tǒng)托攻擊檢測，需要同時考慮不同類別樣本在數(shù)量上的差異和誤分類代價不同這一事實。

本文將數(shù)據(jù)重采樣和代價敏感學習兩種不同類型的解決方案有機地融合在一起，提出了一種新的推薦系統(tǒng)托攻擊檢測方法。該方法首先用所提出的基于樣本重要性的欠采樣技術進行樣本空間重構，平衡正常用戶和攻擊用戶的比例，減弱不均衡數(shù)據(jù)集對支持向量機分類性能的影響。然后，對待識別的攻擊用戶賦以較大的代價，正常用戶則賦以較小的代價，利用代價敏感學習算法CS－SVM（Cost Sensitive SVM）進行分類，從而解決樣本誤分類代價不同的問題。將實現(xiàn)的軟件應用于推薦系統(tǒng)托攻擊檢測，實驗結(jié)果表明了其有效性。

2 理論基礎

2.1 單邊采樣技術

Kubat和 Matwin［12］提 出 的 單 邊 采樣技術OSS（One－Sided Selection）是一種具有代表性的欠采樣方法，其工作原理如下：設xi表示一個多數(shù)類樣本，xj表示一個少數(shù)類樣本，d（xi，xj）表示xi和xj之間的距離，判斷是否存在樣本點z，使d（xi，z）＜d（xi，xj）或d（xj，z）＜d（xi，xj）成立，如果不存在z，則 （xi，xj）是邊界點或者噪聲點，將多類樣本xi從樣本集中刪除。

2.2 代價敏感支持向量機

集成不同誤分類代價的代價敏感支持向量機本質(zhì)上是傳統(tǒng)支持向量機的代價敏感形式的擴展。對兩類問題，結(jié)合不同誤分類代價，有訓練樣本集：

最小化目標函數(shù)：

其相應的對偶形式：

相應的決策函數(shù)為：

3 混合托攻擊檢測方法

3.1 均衡訓練樣本集

重采樣是解決樣本失衡的一個有效方法。重采樣實現(xiàn)的途徑有兩種：增加少數(shù)類樣本數(shù)的過采樣技術和減少多數(shù)類樣本數(shù)的欠采樣技術。由于過采樣技術會造成訓練集規(guī)模的增大，加大計算復雜度，因此在某些需要進行快速分類和決策的場合，例如推薦系統(tǒng)托攻擊檢測，更適合使用減少多類樣本的欠采樣技術。單邊采樣技術被證明可以有效緩解數(shù)據(jù)集的不均衡程度，但是該方法簡單地將邊界點完全刪除，會造成分類信息的嚴重丟失，對分類器的性能造成不良影響。

本文針對單邊采樣技術中存在的邊界樣本處理過于簡單的問題，提出了一種基于樣本重要性的欠采樣技術SIUT（Sample Importance based Undersampling Technique）。SIUT首先使用單邊采樣方法定位多數(shù)類邊界點和噪聲點。然后，利用K近鄰法分離噪聲點和邊界點。對于噪聲點直接排除于樣本集之外，對于剩下的樣本，也就是邊界樣本，使用式（6）計算每一個樣本的重要性。

其中，TPR（True Positive Rate）是攻擊用戶的檢測率，檢測率＝正確檢測的攻擊用戶數(shù)量／總的攻擊用戶數(shù)量；FPR（False Positive Rate）是正常用戶的誤檢率，誤檢率＝被錯誤判斷為攻擊用戶的正常用戶數(shù)量／總的正常用戶數(shù)量。在推薦系統(tǒng)托攻擊檢測的實際應用中，我們希望在檢測率處于最高的前提下，盡可能地降低誤檢率。因此，I（xi）值的大小可以表明此樣本對分類支持的重要性。相應地，I（xi）值越大表明此樣本的重要性越大；反之，I（xi）值越小表明此樣本的重要性也越小。迭代刪除I（xi）值最小的多數(shù)類樣本，就可以消除對分類決策面“不重要”的多數(shù)類樣本，控制兩類數(shù)據(jù)使用比例的同時又能保留絕大多數(shù)對分類超平面有用的“重要”樣本。利用SIUT算法實現(xiàn)訓練樣本均衡的具體過程如算法1所示。

算法1 SIUT算法

輸入：原始不均衡訓練樣本集T；

輸出：均衡訓練樣本集T′。

（1）將數(shù)據(jù)集T分解為兩個子集：多數(shù)類樣本集N ＝ ｛n1，n2，…，nnnum｝和 少數(shù)類樣本 集 F ＝｛f1，f2，…，ffnum｝，其中nnum、fnum 為多數(shù)類和少數(shù)類樣本的個數(shù)。

（2）對每一個少數(shù)類F中的樣本fi（i＝1，2，…，nnum）計算它在整個樣本集T中的最近鄰樣本zi，如果zi屬于多數(shù)類，則計算zi的K 近鄰。

（3）如果zi所有的K 個最近鄰樣本都屬于少數(shù)類，則這個多數(shù)類樣本被認為是噪聲，直接刪除；否則判斷其為邊界樣本。設邊界樣本集Bordline＝｛f′1，f′2，…，f′bnum｝，其中，0≤bnum ≤fnum 。

（4）刪除Bordline中的第一個樣本f′1，形成新的邊界樣本集合Bordline′。用SVM對Bordline′和F構成的訓練集進行訓練，計算I（f′1）。

（5）對Bordline中的每一個樣本重復步驟（4），得到I（f′1），I（f′2），…，I（f′bnum）。

（6）刪除Bordline中對應I（f′i）值最小的樣本f′i。

（7）循環(huán)（4）～（6），直到多數(shù)類邊界樣本和少數(shù)類樣本數(shù)目相對均衡為止。

（8）將修剪后的多數(shù)類邊界樣本集和少數(shù)類樣本集移入T′。

3.2 托攻擊檢測

本文設計了基于混合策略的托攻擊檢測方法，其流程如圖1所示。該方法對數(shù)據(jù)樣本的處理可分為兩個階段，首先利用本文提出的SIUT算法對原有的訓練樣本集進行均衡化處理，然后利用代價敏感支持向量機集成不同的誤分類代價對均衡后的訓練集進行分類。

Figure 1 Detecting shilling attacks method using hybrid strategies圖1 基于混合策略的托攻擊檢測方法流程圖

對于重構后的樣本集，利用代價敏感支持向量機進行托攻擊檢測的具體過程如算法2所示。

算法2 托攻擊檢測算法

輸入：重構后的訓練樣本和測試樣本；輸出：托攻擊檢測結(jié)果。

（1）初始化重構樣本集和模型參數(shù)。

（2）使用代價敏感支持向量機訓練重構后的樣本集，執(zhí)行交叉驗證操作，保存中間計算結(jié)果。

（3）判斷結(jié)果是否達到最佳的檢測性能，如果是，進入下一步；否則，返回到第（2）步。

（4）獲得訓練集上的最佳參數(shù)模型。

（5）計算式（5）中的決策閾值b，得到代價敏感支持向量機的決策函數(shù)。

3.3 混合策略分析

下面分析本文方法對推薦系統(tǒng)托攻擊檢測性能的影響。在最優(yōu)化求解式（2）過程中得到的αi可能會有三種情況：

（1）αi＝0，這時對應的xi被正確分類。

（2）0＜αi＜coiC，這時對應的xi稱為普通支持向量，代表了大部分樣本的分類特性。

（3）αi＝coiC，這時對應的xi稱為邊界支持向量，代表所有誤分的樣本點。邊界支持向量的比例在一定程度上反映了支持向量機分類的正確率。

設NBSV＋和NBSV－分別代表攻擊用戶和正常用戶中邊界支持向量的個數(shù)，NSV＋和NSV－分別代表攻擊用戶和正常用戶中支持向量的個數(shù)，N＋和N－分別代表攻擊用戶和正常用戶的數(shù)量，co＋和co－分別代表攻擊用戶和正常用戶的誤分類代價。

由式（3）有：

由式（4）可知，對于攻擊用戶αi的最大值是co＋C，因此有：

將式（8）和式（9）結(jié)合，得到：

類似地，可以得到正常用戶的不等式：

用co＋CN＋和co－CN－分別除以式（10）和式（11），并且設＝F，得：

由式（12）和式（13）可知，邊界支持向量比例的上界和支持向量比例的下界由N＋、N－、co＋和co－這幾個參數(shù)決定。當攻擊用戶和正常用戶的誤分類代價相等時，即co＋＝co－，由于攻擊用戶的數(shù)量小于正常用戶的數(shù)量，即N＋＜N－，這時攻擊用戶中邊界支持向量比例的上界將大于正常用戶邊界支持向量比例的上界。這意味著攻擊用戶被誤分的比例比正常用戶被誤分的比例大。在本文方法中，進行樣本集重構能夠減少N－，平衡兩類樣本的比例，同時代價敏感支持向量機對攻擊用戶設定較大的誤分代價co＋，綜合起來將攻擊用戶被誤分的比例上界F／co＋CN＋降低，從而提高攻擊用戶的檢測精度。

4 實驗與分析

4.1 實驗準備

（1）數(shù)據(jù)集。

實驗數(shù)據(jù)來自明尼蘇達大學GroupLens研究小 組 通 過 MovieLens 網(wǎng) 站 （http：／／movielens.umn.edu）收集的 MovieLens100K 數(shù)據(jù)集［13］，該數(shù)據(jù)集包含了943位用戶對1 682部電影的100 000條1～5的評分數(shù)據(jù)，每位用戶至少對20部電影進行了評分。數(shù)據(jù)集被轉(zhuǎn)換成一個用戶－項目評分矩陣R，并假設MovieLens數(shù)據(jù)集中不存在攻擊用戶評價行為。整個實驗分為訓練和測試兩個階段，按照80%～20%的比例拆分數(shù)據(jù)集構造訓練－測試數(shù)據(jù)。

（2）特征提取。

特征提取是托攻擊檢測的基礎，托攻擊檢測常用的特征信息包括［14］：用戶的預測變化值、用戶評價值背離程度、與其他用戶相適度、鄰居用戶相似程度和背離平均度等指標。本文根據(jù)以上反映用戶評分信息異常度的統(tǒng)計屬性，對用戶－項目評分矩陣R中每個用戶的評分數(shù)據(jù)進行統(tǒng)計整理，得到5個檢測屬性，加上用戶編號（userID）和分類屬性（class）構成一條關于某個用戶評分數(shù)據(jù)的檢測數(shù)據(jù)。

4.2 實驗結(jié)果分析

實驗采取3×3×5的設計模式，攻擊類型（隨機攻擊、均值攻擊、流行攻擊），攻擊強度（3%、5%、10%），填充率（3%、5%、10%、15%、20%）。每組實驗配置下，分別獨立地向數(shù)據(jù)集注入10次攻擊，最終實驗數(shù)據(jù)是10次攻擊檢測的均值。使用SVM方法、CS－SVM方法、OSS和SVM相結(jié)合的方法、SIUT和SVM相結(jié)合的方法這四種方法和本文提出的方法做比較，選取G－MEAN值作為評價指標。實驗中SVM方法采用高斯核函數(shù)，寬度為1，CS－SVM方法的誤分類代價co＋＝3，co－＝100，SIUT方法的K近鄰取值為6。實驗結(jié)果如圖2～圖4所示。

從圖2～圖4可以發(fā)現(xiàn)，無論是面對隨機攻擊、均值攻擊還是流行攻擊，本文方法的G－MEAN值都是所比較的五種方法中最優(yōu)的，并且隨著攻擊強度的增加，其G－MEAN值逐漸提高，幾乎可以檢測出全部攻擊用戶，提高了對攻擊用戶的檢測能力，進而能夠很好地幫助推薦系統(tǒng)得到準確的用戶評分數(shù)據(jù)，以確保系統(tǒng)的安全。具體分析如下：CS－SVM方法的G－MEAN值和SVM 方法的GMEAN值相比提高不明顯，這是由于攻擊用戶和正常用戶的誤分類代價通常只能根據(jù)樣本數(shù)目的比例進行選取，這種單純靠調(diào)整懲罰因子的方法不能有效地提高SVM方法在類別不均衡和代價敏感情況下的分類性能。另外，從實驗中可以看出，OSS和SVM相結(jié)合的方法大幅提高了SVM方法的分類性能，說明通過OSS方法進行預處理，能有效提高SVM方法的分類能力。但是，從實驗結(jié)果可以看出，本文提出的SIUT方法對改善SVM方法處理不均衡數(shù)據(jù)分類問題的效果更加明顯，這是由于SIUT在消除大量噪聲信息的同時，又能保留絕大多數(shù)對分類學習有用的樣本點，保證了信息損失最小，從而增大了后續(xù)分類方法對攻擊用戶的決策空間，因此分類性能較OSS方法更優(yōu)。最后，值得一提的是，SIUT ＋CS－SVM 方法的G－MEAN值和SIUT＋SVM方法的G－MEAN值相比有較大幅度的提高，說明通過對SVM方法進行代價敏感的改善能進一步提高算法的性能。

Figure 2 G－MEAN for detecting random attack，average attack，and bandwagon attack under attack size＝3%圖2 攻擊規(guī)模為3%時檢測隨機攻擊、均值攻擊和流行攻擊的G－MEAN值

5 結(jié)束語

Figure 3 G－MEAN for detecting random attack，average attack，and bandwagon attack under attack size＝5%圖3 攻擊規(guī)模為5%時檢測隨機攻擊、均值攻擊和流行攻擊的G－MEAN值

本文結(jié)合數(shù)據(jù)重采樣和代價敏感學習兩類解決方案的優(yōu)點提出了一個新的托攻擊檢測方法。利用所提出的基于樣本重要性的欠采樣技術——SIUT對數(shù)據(jù)集進行重采樣，在消除噪聲樣本減少數(shù)據(jù)不均衡程度的同時又保證信息損失最小。結(jié)合代價敏感支持向量機算法對重構后的訓練樣本進行檢測。實驗結(jié)果表明，本文方法在不同的攻擊強度下對不同的攻擊模型均獲得了良好的檢測效果，檢測性能較傳統(tǒng)SVM算法有顯著提高。同時，不均衡數(shù)據(jù)和不同誤分類代價的分類問題在現(xiàn)實世界中廣泛存在，因此本文提出的方法還可以推廣到其他應用領域。

Figure 4 G－MEAN for detecting random attack，average attack，and bandwagon attack under attack size＝10%圖4 攻擊規(guī)模為10%時檢測隨機攻擊、均值攻擊和流行攻擊的G－MEAN值

［1］ Mehta B，Hofmann T.A survey of attack－resistant collabora－tive filtering algorithms［J］.Data Engineering Bulletin，2008，31（2）：14－22.

［2］ Lam S K，Riedl J.Shilling recommender systems for fun and profit［C］∥Proc of the 13th International Conference on World Wide Web，2004：393－402.

［3］ O’Mahony M，Hurley N J，Kushmerick N，et al.Collaborative recommendation：A robustness analysis［J］.ACM Transactions on Internet Technology，2004，4（4）：344－377.

［4］ Vapnik V N.Statistical learning theory［M］.USA：Wiley，1998.

［5］ Williams C A，Mobasher B，Burke R.Defending recommender systems：Detection of profile injection attacks［J］.Service Oriented Computing and Applications，2007，1（3）：157－170.

［6］ Li Cong，Luo Zhi－gang，Shi Jin－long.An unsupervised algorithm for detecting shilling attacks on recommender systems［J］.ACTA Automatica SINICA，2011，37（2）：160－167.（in Chinese）

［7］ Bhaumik R，Williams C，Mobasher B，et al.Securing collaborative filtering against malicious attacks through anomaly detection［C］∥Proc of the 4th Workshop on Intelligent Techniques for Web Personalization（ITWP’06），2006：1.

［8］ Weiss G M.Mining with rarity：A unifying framework［J］.ACM SIGKDD Explorations Newsletter，2004，6（1）：7－19.

［9］ Liao T W.Classification of weld flaws with imbalanced class data［J］.Expert Systems with Applications，2008，35（3）：1041－1052.

［10］ Zheng En－h(huán)ui，Li Ping，Song Zhi－h(huán)uan.Cost sensitive support vector machines［J］.Control and Decision，2006，21（4）：473－476.（in Chinese）

［11］ Hong X，Chen S，Harris C J.A kernel－based two－class classifier for imbalanced data sets［J］.IEEE Transactions on Neural Networks，2007，18（1）：28－41.

［12］ Kubat M，Matwin S.Addressing the curse of imbalanced training sets：One－sided selection［C］∥Proc of the 14th International Conference on Machine Learning，1997：217－225.

［13］ http：／／www.grouplens.org／node／73.

［14］ O’Mahony M，Hurley N，Kushmerick N，et al.Collaborative recommendation：A robustness analysis［J］.ACM Transactions on Internet Technology，2004，4（4）：344－377.

附中文參考文獻：

［6］ 李聰，駱志剛，石金龍.一種探測推薦系統(tǒng)托攻擊的無監(jiān)督算法［J］.自動化學報，2011，37（2）：160－167.

［10］ 鄭恩輝，李平，宋執(zhí)環(huán).代價敏感支持向量機［J］.控制與決策，2006，21（4）：473－476.