一種利用半監督Fisher判別分析檢測推薦攻擊的方法

武錦霞，周全強，段亮亮

(青島理工大學 信息與控制工程學院，山東 青島 266525)

1 引 言

隨著大數據時代的到來，信息過載問題越來越嚴重.協同推薦系統(Collaborative Recommender System)能夠依據用戶概貌(User Profile)主動地為用戶推送感興趣的信息，成為解決信息過載問題的有效途徑之一，在電子商務、社交網絡、多媒體服務等領域有著廣泛的應用[1].

然而，大量研究表明，協同推薦系統易遭受推薦攻擊(Recommendation Attack)[2,3].在這種攻擊中，惡意用戶出于商業競爭等目的，通過向協同推薦系統注入大量虛假概貌來改變推薦結果.為了與真實概貌(Genuine Profile)相區分，通常將這種虛假概貌稱為攻擊概貌(Attack Profile)[4].根據不同的攻擊目的，一般將推薦攻擊分為推攻擊(Push Attack)和核攻擊(Nuke Attack)，分別用于提升和降低目標項目的推薦等級[4].為了達到攻擊的目的，惡意用戶通常使用攻擊模型(Attack Model)[4]生成攻擊概貌.除了目標項目，其他一些項目也將被評分使攻擊概貌看起來更接近真實概貌.常見的攻擊模型包括隨機攻擊、均值攻擊和流行攻擊[5].推薦攻擊的強度通常用攻擊規模和填充規模來度量[5].

為了檢測推薦攻擊，研究者提出了很多檢測方法，從機器學習的角度可以將已有方法分類3類：無監督[6-12]、有監督[13-21]及半監督檢測方法[22,23].無監督檢測方法一般不需要訓練樣本，但通常需要一定的先驗知識.有監督檢測方法通常利用有標簽的用戶概貌訓練分類器對推薦攻擊進行檢測.半監督檢測方法在利用有標簽用戶概貌訓練分類器的同時，能夠利用無標簽用戶概貌進一步提升分類器的性能，由于協同推薦系統往往存在大量無標簽用戶概貌，因此，能利用無標簽用戶概貌提升分類器性能成為半監督類檢測方法的重要優勢.然而，目前針對半監督檢測方法的研究較少，且已有半監督檢測方法的準確率不高.

為了提升半監督檢測方法的檢測性能，本文基于半監督Fisher判別分析技術提出一種推薦攻擊檢測方法RAD-SFDA.本文方法同時利用了從有標簽用戶概貌捕獲的判別結構，以及從由有標簽和無標簽用戶概貌構成的全部用戶概貌捕獲的全局結構，以獲得最優投影向量，在新的投影空間中增加了真實概貌和攻擊概貌的區分度以提升檢測性能.本文的主要貢獻如下：

1)利用FDA(Fisher Discriminant Analysis)技術捕獲了有標簽用戶概貌的判別結構；利用PCA(Principal Components Analysis)技術捕獲了全部用戶概貌的全局結構；

2)綜合上述判別結構和全局結構獲得了最佳投影向量，在新的投影空間中增加了真實概貌和攻擊概貌的區分度；

3)提出了一種基于半監督Fisher判別分析SFDA(Semi-supervised Fisher Discriminant Analysis)的檢測算法，通過訓練貝葉斯分類器對推薦攻擊進行了有效檢測；

4)在標準的MovieLens數據集上與相關工作進行了對比實驗，驗證了本文方法的有效性.

2 相關工作和背景知識

2.1 相關工作

在無監督檢測方法中，Chirita等人[6]首先提出了幾個基于統計的指標來檢測高密度的攻擊概貌.Mehta等人[7,8]利用PCA技術過濾攻擊概貌，可有效檢測多種類型的推薦攻擊，但是，該方法假設在檢測前已經知道測試集中攻擊概貌的數目，這種先驗知識在實際中不易獲得.李聰等人[9]通過定量度量攻擊概貌的群體效應構建出遺傳優化的目標函數，并在遺傳優化的過程中融入貝葉斯推斷思想來完成對攻擊概貌的檢測，有效降低了無監督方法對先驗知識的依賴程度.Yang等人[10]采用圖挖掘算法區分真實概貌和攻擊概貌，通過構造無向圖和估計相似度提出一種檢測方法，可檢測多種類型攻擊，然而，為該方法選取合適的共同評分閾值是一項有挑戰性的工作.Yang等人[11]通過分析用戶、項目和特殊評分的分布，聯合目標項目分析和非線性聚類技術提出一種檢測方法.非線性聚類技術有效提升了該方法對推薦攻擊的檢測性能，然而，從大量項目中確認目標項目并非易事.Zhang等人[12]假設測試集中同時包含真實概貌和攻擊概貌，采用聚類技術劃分真實概貌和攻擊概貌到不同的簇中以識別推薦攻擊，有效降低了無監督方法對先驗知識的要求.無監督檢測方法存在的主要問題是過度依賴先驗知識，因此，如何有效降低檢測方法對先驗知識的依賴是該類方法面臨的重要挑戰之一.

在有監督檢測方法中，Burke等人[13,14]通過訓練kNN、C4.5和SVM3個分類器檢測推薦攻擊，這些分類器有較高的召回率，但準確率不高.伍之昂等人[15]提出一種特征選擇算法，在已有特征的基礎上選取部分作為特性屬性，檢測特定類型的攻擊模型，與沒進行特征選擇之前相比，一定程度上提升了檢測性能.Zhang等人[16]利用Hilber-Huang變換提取了推薦攻擊的評分分布特征，在此基礎上訓練SVM檢測推薦攻擊，對高密度攻擊概貌具有一定檢測效果.李文濤等人[17]提出了一種基于流行度的檢測算法，該算法從評分項目的流行度角度提取分類特征，進而通過訓練決策樹生成分類器對推薦攻擊進行檢測，對包括混合攻擊在內的多類攻擊模型具有一定的檢測效果.Yang等人[18]基于重新縮放的Boosting和AdaBoost檢測推薦攻擊，提升了針對不平衡測試數據的檢測性能.Zhou等人[19]結合Borderline-SMOTE技術和目標項目分析訓練了基于SVM的分類器檢測推薦攻擊.該方法一般來說具有較好的檢測性能，然而，由于協同推薦系統通常有大量項目，有時很難準確查找目標項目，在這種情況下，該方法的檢測性能變得不穩定.Tong等人[20]提出了一種基于卷積神經網絡的推薦攻擊檢測方法，在滿足其對大量有標簽訓練樣本需求的條件下，該方法具有一定的檢測效果.Xu等人[21]提取了基于信任的用戶概貌特征，在此基礎上訓練SVM檢測推薦攻擊.該方法提升了單分類器的檢測性能，然而，該方法建立在正確識別目標項目的基礎之上，從大量項目中確定目標項目有時難以實現.有監督檢測方法雖然不需要先驗知識，但只能從有標簽的訓練樣本中學習檢測模型，無法有效利用協同推薦系統中存在的大量無標簽用戶概貌.

半監督檢測方法主要是Wu等人[22,23]的工作，他們提出了基于貝葉斯的半監督檢測方法.首先利用有標簽用戶概貌初始化一個貝葉斯分類器，然后，利用無標簽用戶概貌提升分類器的性能.該方法對某些類型的推薦攻擊具有較高的召回率，然而，該方法的準確率較低.如何有效提升準確率成為當前半監督檢測方法面臨的重要研究課題之一.

2.2 背景知識

2.2.1 Fisher判別分析FDA

FDA[24]是一種有監督的線性降維技術，利用有標簽樣本，通過尋找一個最佳投影向量，使得在投影空間中最大化不同類樣本間離散度，同時最小化同類樣本之間的離散度.

(1)

(2)

可通過優化下面的目標函數來確定FDA判別向量：

(3)

將上述優化問題轉化為求解下面的廣義特征值問題：

Sbt=λSwt

(4)

其中，λ表示廣義特征值，t表示λ對應的廣義特征向量，與FDA判別向量等價.

為便于問題描述，將Sb和Sw的定義改寫為對等表達形式：

(5)

(6)

其中，

(7)

(8)

由上式可以看出，同類中的數據對越接近，類內的離散度矩陣就越小，不同類中的數據對彼此之間越分散，類間離散度矩陣就越大.

2.2.2 主元分析PCA

PCA[25]是一種無監督的線性降維技術，目的是找到所有樣本方差變化最大的方向，能夠將原始樣本空間中的最大信息保留下來.

(9)

全局離散度矩陣St的對等形式可以表示為：

(10)

PCA的優化目標函數為：

(11)

目標函數優化問題等價于下述廣義特征值求解問題：

StL=δIdL

(12)

其中，δ為廣義特征值，L為δ對應的特征向量，Id為d維單位矩陣.

2.2.3 半監督Fisher判別分析SFDA

SFDA[26]將FDA和PCA有效的結合在一起，可同時利用從標簽樣本學習的判別結構和從全部樣本學習的全局結構，找到最佳投影向量.

Srb=(1-β)Sb+βSt

(13)

Srw=(1-β)Sw+βId

(14)

其中，β∈[0,1]表示調整參數，當β=0時，SFDA完全轉化為FDA，當β=1時，SFDA完全轉化為PCA，SFDA的優化目標函數為：

(15)

上述優化問題等價于下面求廣義特征值問題：

Srbq=λSrwq

(16)

其中，λ表示廣義特征值，q表示對應的廣義特征向量.若廣義特征值的大小排序為λ1≥λ2…≥λd，對應的廣義特征向量為q1，q2，…，qd.前r個廣義特征向量可以構成最佳投影向量q1,q2,…,qr，即SFDA判別向量，其中，r(1≤r≤d)代表降維維數，此時降維后的空間變成了r維投影空間，一旦找到了最佳投影向量，便可以將樣本投影到r維空間中，在投影空間中增加不同類樣本之間的離散度.

3 提出的檢測方法RAD-SFDA

3.1 檢測框架

圖1描述了本文方法RAD-SFDA的基本框架.

圖1 RAD-SFDA的推薦攻擊檢測框架Fig.1 Recommendation attack detection framework of RAD-SFDA

如圖1所示，RAD-SFDA方法首先利用特征提取方法對訓練集和測試集中的用戶概貌進行特征提取，本文選用主流的推薦攻擊特征提取方法，將在實驗部分進行介紹；在進行歸一化處理操作之后，利用FDA從有標簽用戶概貌獲得判別結構，利用PCA從全部用戶概貌獲得全局結構，然后，結合PCA和FDA建立SFDA模型獲得最佳投影向量；在新的投影空間中訓練貝葉斯分類器對測試集進行檢測.

3.2 檢測算法

用L=[x1，x2，…，xl]T表示訓練集中的有標簽用戶概貌，U=[xl+1,xl+2，…，xl+u]T表示訓練集中的無標簽用戶概貌，則訓練集可以表示為Ttrain=[L,U]T=[xi,x2,…,xl,xl+1,xl+2，…，xl+u]T.

用Ck表示有標簽用戶概貌的第k個類別，其中，k為1或2，C1表示真實概貌，C2表示攻擊概貌.

根據FDA[24]，利用公式(17)計算真實概貌和攻擊概貌間的離散度矩陣Sb：

(17)

利用公式(18)，計算類內離散度矩陣Sw：

(18)

根據PCA[25]，利用公式(19)計算全局離散度矩陣St：

(19)

根據SFDA[26]，利用公式(20)計算正則化類間離散度矩陣Srb：

Srb=(1-β)Sb+βSt

(20)

利用公式(21)計算正則化類內離散度矩陣Srw：

Srw=(1-β)Sw+βId

(21)

其中，β∈[0,1]表示調整參數.

計算得到Srb和Srw之后，利用公式(16)計算得到廣義特征值及其對應的廣義特征向量q.設廣義特征值由大到小排列為λ1≥λ2≥…≥λd，對應的廣義特征向量為q1,q2，…，qd，利用前r個廣義特征向量建立投影矩陣Qr=[q1,q2,…，qr]，其中，r表示降維維數，降維后的空間即是r(1≤r≤d)維投影空間，r將作為超參數在實驗中設置具體值.通過設置r確定最佳投影空間，在該空間中，減少了真實概貌之間及攻擊概貌之間的離散度，同時增大了真實概貌和攻擊概貌之間的離散度，有效增加了不同類用戶概貌的區分度，提升了檢測性能.

圖2 不同β值對應投影向量的二維示意圖Fig.2 Two-dimensional diagram of projection vectors corresponding to different β values

在公式(20)中，Sb由有標簽用戶概貌計算得來，若有標簽用戶概貌過少則容易導致過擬合，若大量增加有標簽用戶概貌通常會增加標記代價.而St是由包含大量無標簽用戶概貌的信息計算得到，在不增加標記代價的條件下，會提高Srb檢測推薦攻擊的檢測性能.在公式(21)中，Srw中的βId可以看作為正則化項，SFDA通過添加正則化項會表現出更強的泛化能力.

公式(20)和公式(21)中的調整參數β能夠靈活調整SFDA的平滑性，當β趨于0時，SFDA傾向于FDA，當β趨于1時，SFDA傾向于PCA，將FDA和PCA巧妙的結合起來.圖2演示了二維空間中不同β值對投影向量的影響.

如圖2所示，實心圓圈表示有標簽真實概貌，空心圓圈表示無標簽真實概貌，實心方框表示有標簽攻擊概貌，空心方框表示無標簽攻擊概貌，虛線表示不同β值對應的投影向量.當β=0時，SFDA轉化為FDA，投影向量對有標簽用戶概貌進行了很好的區分，但是部分無標簽用戶概貌有一定重疊，區分度不高.當β接近于1時，SFDA的開始向PCA過度，能夠捕獲全部用戶概貌的全局結構.當β=0.5時，投影向量綜合考慮了判別結構和全局結構，有標簽和無標簽用戶概貌的區分度得到有效增強.

(22)

(23)

根據貝葉斯分類規則，按照后驗概率的大小作分類依據，利用下式給出推薦攻擊的檢測結果：

(24)

基于上述分析，本文提出的基于SFDA的檢測算法如算法1所示.

算法1.基于SFDA的推薦攻擊檢測算法

輸入：訓練集Ttrain，測試集Ttest，有標記用戶概貌的比例ratio，降維維數r，調整參數β

輸出：檢測結果集

4.利用β、Sb、Sw和St，結合公式(20)和公式(21)計算正則化類間離散度矩陣Srb和類內離散度矩陣Srw；

5.利用r、Srb和Srw，結合公式(16)計算投影矩陣Qr；

4 實驗結果與分析

4.1 實驗數據和設置

采用協同推薦領域中的標準MovieLens 10M(1)https://grouplens.org/datasets/movielens/(數據集作為實驗數據，該數據集包含71567個用戶對10681部電影的10000054個評分，評分值位于1-5之間，每個用戶至少擁有20條評分記錄.MovieLens 10M數據集中的用戶概貌全部標記為真實概貌，選取3種常見的攻擊模型隨機攻擊、均值攻擊和流行攻擊[5]生成攻擊概貌.

為了建立訓練集，從數據集中隨機選取1000個用戶概貌作為真實概貌，設置隨機攻擊、均值攻擊、流行攻擊的攻擊規模分別為1%、2%、5%和10%，對應填充規模分別為1%，3%，5%，10%.

為了建立驗證集，從剩余數據集中隨機選取1000個用戶概貌作為真實概貌，設置隨機攻擊、均值攻擊、流行攻擊的攻擊規模分別為1%，對應填充規模分別為1%.

為了建立每一個測試集，從剩余數據集中隨機選取1000個用戶概貌作為真實概貌，設置隨機攻擊、均值攻擊、流行攻擊的攻擊規模分別為1%、2%、5%和10%，對應填充規模分別為1%，3%，5%，10%，分別注入到每一個測試集中.本文實驗只檢測推攻擊，隨機選取一個項目作為目標項目，然而，本文方法可直接用于檢測核攻擊，重復10次建立不同的測試集，記錄檢測結果的平均值進行對比和分析.

選取13個廣泛使用特征提取方法[14]將上述數據集映射到特征空間，這些特征包括：WDMA，RDMA，WDA，Length Variance，DegSim，DegSim′，FMD(random attack)，FAC(random attack)，FMV(average attack)，FMD(average attack)，PV(average attack)，FMD(bandwagon attack，push)，和 FAC(bandwagon attack).

利用標準的召回率Recall和準確率Precision[28]評價方法在測試集上的檢測性能.F-measure[28]是對召回率和準確率的調和均值，利用F-measure評價檢測方法在驗證集上的檢測性能.

4.2 參數設置

在算法1中有3個關鍵的參數需要設置，分別是有標簽用戶概貌比例ratio、降維數目r和調整參數β.為了設定這3個參數，我們固定其中兩個參數，讓第3個參數在合理的范圍內進行變化，觀察本文方法在驗證集上的檢測性能.

圖3 驗證集上的檢測性能隨ratio的變化Fig.3 Changes of detection performance on validation set with ratio

設置β=0.5，r=11，本文方法在驗證集上的檢測性能隨ratio的變化情況如圖3所示.

如圖3所示，曲線反映了有標簽用戶概貌所占比例ratio對本文方法檢測性能的影響.隨著ratio的不斷增加，對應的F-measure值不斷增大，這是因為隨著有標簽用戶概貌的增加，從有標簽用戶概貌學習到的分類方向會更加準確，因而從全部用戶概貌學習到的最大方差方向調整利用從有標簽用戶概貌學習到的分類方向后，便能找到最佳的投影向量，達到最好的檢測性能.當ratio的值增加到15%時，F-measure達到最大值，之后便趨于穩定，說明該方法在此點找到最佳投影向量.該曲線圖表明，有標簽用戶概貌的加入能夠增加該方法的檢測性能，并且即使在有標簽用戶概貌比例很小的情況下，該方法也能取得很好的檢測性能.綜上，在算法1中，設置ratio=15%.

設置β=0.5，ratio=15%，本文方法在驗證集上的檢測性能隨r的變化情況如圖4所示.

圖4 驗證集上的檢測性能隨r的變化Fig.4 Changes of detection performance on validation set with r

如圖4所示，曲線反映了不同維度的投影向量對本文方法檢測性能的影響.隨著r值不斷增加，本文方法檢測性能不斷上升，這是因為最佳投影向量是由r個廣義特征向量構成的，廣義特征向量的個數越多，包含的信息也就越多，通常越有利于提升檢測性能.當r=11時，F-measure增加到最大，之后便不再增加，表明在此點便找到了最佳投影向量，用戶概貌經過最佳投影向量的投影后，在r維空間中能夠增加不同類用戶概貌之間的離散度，使得檢測性能達到最大.綜上，在算法1中，設置r=11.

設置ratio=15%，r=11，本文方法在驗證集上的檢測性能隨β的變化情況如圖5所示.

圖5 驗證集上的檢測性能隨β的變化Fig.5 Changes of detection performance on validation set with β

如圖5所示，曲線反映了調整參數β對本文方法檢測性能的影響，β能夠調整本文方法的靈活性，將FDA和PCA巧妙的結合起來，當β趨于0.1時，本文方法接近于FDA方法，當β趨于0.9時，本文方法接近于PCA方法.從曲線的變化幅度可以看出β值的變化對檢測性能影響波動不大，這主要是因為不論β的取值情況如何，文本方法都有效利用了訓練集中全部用戶概貌信息.如圖5所示，當β取0.5時，F-measure值最大，說明本文方法在此點處能最大限度的發揮出FDA和PCA結合后的優勢，充分利用判別結構和全局結構找到最佳投影向量，因而檢測性能最佳.因此在算法1中，設置β=0.5.

4.3 對比方法

為了驗證本文方法的有效性，我們將其與下面有代表性的工作進行實驗對比：

-PCA-VarSelect[6]：一種基于PCA的無監督檢測方法，通過計算協方差檢測攻擊概貌，該方法假設攻擊規模已知.

-SVM-TIA[19]：一種基于SVM的有監督檢測方法，用Borderline-SMOTE方法平衡用戶概貌樣本，利用目標分析方法降低誤判率.

-HySAD[23]：一種基于貝葉斯分類器的半監督檢測方法，首次將半監督技術應用于推薦攻擊檢測.

為了驗證在本文方法中，無標簽用戶概貌有效提升了檢測性能，我們增加了一種對比方法如下：

-SFDA-Labeled：只使用訓練集中有標簽的用戶概貌進行訓練，不使用無標簽用戶概貌提升性能，其余設置與本文方法RAD-SFDA中的設置相同.

4.4 實驗結果與分析

4種檢測方法PCA-VarSelect、SVM-TIA、HySAD和RAD-SFDA對測試集中隨機攻擊、均值攻擊和流行攻擊的檢測結果如表1、表2和表3所示.

PCA-VarSelect方法對隨機攻擊和均值攻擊的檢測效果較高，準確率和召回率保持在較高水平，該方法在檢測流行攻擊時性能有所下降，特別是檢測小規模的流行攻擊時，準確率不高.

表1 隨機攻擊的檢測結果對比Table 1 Comparison of detection results for random attack

表2 均值攻擊的檢測結果對比Table 2 Comparison of detection results for average attack

表3 流行攻擊的檢測結果對比Table 3 Comparison of detection results for bandwagon attack

SVM-TIA方法在大多數情況下表現出了很好的檢測性能，然而，在個別點處檢測性能不穩定，這主要是因為SVM-TIA方法建立在準確識別目標項目的基礎之上，當該方法準確定位到目標項目時，檢測性能很高，否則，檢測性能下降.

HySAD方法在檢測3類推薦攻擊時，具備一定的召回率，然而，從表中可以看出，該方法的檢測準確率需要進一步提升.RAD-SFDA方法在大多數情況下表現出了較好的檢測性能，召回率和準確率保持在了較高的水平，實驗結果充分驗證了本文方法的有效性.

兩種檢測方法SFDA-Labeled和RAD-SFDA對測試集中隨機攻擊、均值攻擊和流行攻擊檢測結果的平均性能指標如表4所示.

表4 檢測結果對比Table 4 Comparison of test results

如表4所示，在檢測各類攻擊時，RAD-SFDA方法比SFDA-Labeled方法在性能上均有所提升，平均召回率累計提升0.48，平均準確率累計提升0.08.實驗結果表明，本文提出的檢測方法充分發揮了半監督檢測方法的優勢，能夠利用無標簽用戶概貌有效提升推薦攻擊的檢測性能.

4.5 討 論

本文提出的RAD-SFDA方法同時利用了從有標簽用戶概貌捕獲的判別結構，以及從由有標簽和無標簽用戶概貌構成的全部用戶概貌捕獲的全局結構，以獲得最佳投影向量，有效提升了半監督檢測方法的準確率，這是本文方法與多數已有方法主要不同之處，也是本文方法能夠有效提升檢測性能的重要原因，實驗結果充分驗證了本文方法的有效性.

需要指出的是，雖然在多數實驗結果中，本文方法都取得了較好的檢測結果，但是，在檢測高填充規模、高攻擊規模的隨機攻擊和流行攻擊時，本文方法的檢測性能不高.導致這種現象的原因可能與本文選擇的特征提取方法有關，本文所用的特征提取方法整體上是有效的，但對個別的攻擊情況如高填充規模、高攻擊規模的攻擊，特征提取能力較弱.未來的工作中，選擇更多、更有效的推薦攻擊特征提取方法有望進一步提升半監督檢測方法的檢測性能.

5 總 結

本文提出了一種基于半監督Fisher判別分析的推薦攻擊檢測方法，有效提升了半監督檢測方法的檢測性能.利用Fisher判別分析技術捕獲了有標簽用戶概貌的判別結構，利用主元分析技術捕獲了所有有標簽和無標簽用戶概貌的全局結構.利用SFDA技術實現判別結構和全局結構的有機結合，得到了最佳投影向量，增加了不同類用戶概貌之間的離散度.在新的投影空間中，利用貝葉斯分類器完成了對推薦攻擊的有效檢測.在標準的MovieLens數據集上進行了對比實驗，驗證了本文方法的有效性.未來工作中，將考慮引入更多的推薦攻擊特征提取方法，以期進一步提升檢測方法的穩定性.