呂成戍，王維國(guó)

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

1 引言

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

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

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

2 理論基礎(chǔ)

2.1 單邊采樣技術(shù)

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

2.2 代價(jià)敏感支持向量機(jī)

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

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

其相應(yīng)的對(duì)偶形式：

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

3 混合托攻擊檢測(cè)方法

3.1 均衡訓(xùn)練樣本集

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

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

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

算法1 SIUT算法

輸入：原始不均衡訓(xùn)練樣本集T；

輸出：均衡訓(xùn)練樣本集T′。

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

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

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

（4）刪除Bordline中的第一個(gè)樣本f′1，形成新的邊界樣本集合Bordline′。用SVM對(duì)Bordline′和F構(gòu)成的訓(xùn)練集進(jìn)行訓(xùn)練，計(jì)算I（f′1）。

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

（6）刪除Bordline中對(duì)應(yīng)I（f′i）值最小的樣本f′i。

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

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

3.2 托攻擊檢測(cè)

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

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

對(duì)于重構(gòu)后的樣本集，利用代價(jià)敏感支持向量機(jī)進(jìn)行托攻擊檢測(cè)的具體過程如算法2所示。

算法2 托攻擊檢測(cè)算法

輸入：重構(gòu)后的訓(xùn)練樣本和測(cè)試樣本；輸出：托攻擊檢測(cè)結(jié)果。

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

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

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

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

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

3.3 混合策略分析

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

（1）αi＝0，這時(shí)對(duì)應(yīng)的xi被正確分類。

（2）0＜αi＜coiC，這時(shí)對(duì)應(yīng)的xi稱為普通支持向量，代表了大部分樣本的分類特性。

（3）αi＝coiC，這時(shí)對(duì)應(yīng)的xi稱為邊界支持向量，代表所有誤分的樣本點(diǎn)。邊界支持向量的比例在一定程度上反映了支持向量機(jī)分類的正確率。

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

由式（3）有：

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

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

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

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

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

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)準(zhǔn)備

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

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

（2）特征提取。

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

4.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

5 結(jié)束語

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

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

Figure 4 G－MEAN for detecting random attack，average attack，and bandwagon attack under attack size＝10%圖4 攻擊規(guī)模為10%時(shí)檢測(cè)隨機(jī)攻擊、均值攻擊和流行攻擊的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.

附中文參考文獻(xiàn)：

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

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