基于時間序列分析的客戶項目狀態篡改識別算法

陳超凡，林書新

(1.海南大學 信息科學技術學院，海南 海口 570228;2.海南經貿職業技術學院 工程技術學院，海南 海口 571127)

基于時間序列分析的客戶項目狀態篡改識別算法

陳超凡1，林書新2

(1.海南大學 信息科學技術學院，海南 海口 570228;2.海南經貿職業技術學院 工程技術學院，海南 海口 571127)

為了解決現有客戶項目狀態篡改識別算法中不能自適應識別篡改類型和無法同時識別出多個項目狀態遭受篡改的問題，給出了基于時間序列分析的客戶項目狀態篡改識別算法，即先劃分系統內的評分時間序列區間段，運用 PCA VarSelect算法得出項目狀態篡改可疑名單，再進一步縮小識別范圍,具體方法是,根據被篡改的時間段,結合評分偏差度確定被篡改狀態的項目，在此基礎上進一步分析被篡改時間段內的評分，以確定篡改類型，最后識別出相應的被篡改狀態的項目．仿真顯示，該算法識別精度較高,不僅能識別單個項目的篡改狀態,還能同時識別多個項目的篡改狀態．

項目狀態篡改識別；時間序列分析；PCA；識別精度

隨著商業競爭的日益激烈以及推薦系統其自身存在的開放性及交互式等特點，少數客戶出于自身利益的考慮，極其容易利用這些特性對推薦系統進行篡改，破壞推薦系統的公平性．其中，客戶狀態杜撰篡改[1]或托篡改則是最常見的一種篡改方式，篡改者通過人為地杜撰虛假的客戶信息來篡改推薦系統，提高自己項目被推薦的機會或降低競爭對手項目被推薦的機會．因此，如何提高推薦系統抵御這種篡改的能力對保障系統的推薦質量至關重要．

最近幾年，關于客戶狀態篡改識別問題受到了不少國內外研究學者的關注．Chirita等[2]最早設計出了一種篡改識別算法，提出一系列識別屬性來分析少數客戶中的評分信息，并識別了這些屬性對不同篡改模型的識別性能，該算法在篡改狀態密度大的時候識別效果較好，但是當填充規模較小或者篡改狀態稀疏的情況下識別效果非常差．Lee等[3-4]進一步提出了分類識別模型，采用平均項目差異和相符權重度指標識別篡改狀態，但在實際驗證中對于篡改規模高的篡改狀態，識別效果并不理想．Mrhta等[5]提出了基于主成分分析(PCA VarSelect)的識別算法，根據篡改狀態之間的高相關性特征進行識別．該算法對于幾種基本篡改模型的識別效果較好，但由于需要預先設定參數方可確定篡改客戶的數量，顯然，在實際應用中很難準確估計參數值，自然會影響識別精度．李聰，于洪濤等[6-7]提出了一種無監督的UnRAP篡改識別算法，在為每個客戶計算Hv-score值的基礎上，測算出客戶狀態被篡改的可疑度，再設計聚類算法識別客戶狀態是否被篡改，該算法用于識別一般狀態項目是否被篡改效果明顯，但當出現有對客戶項目狀態施行了流行性篡改和核篡改的情形時,識別準確率明顯下降，且存在一定程度的誤判，還需要提前給出篡改形式，降低了算法的實用性.近幾年，融合其他領域的新方法也產生了不少篡改客戶項目狀態的識別方法，見文獻[8-12]．

本文針對目前客戶狀態杜撰、篡改客戶狀態信息的識別算法在確認精度方面存在的不足，重點針對篡改類型的識別和篡改客戶狀態信息的多個項目2方面進行了研究，首先，采用 PCA 識別算法替代Hv-score ，可以有效識別出具有篡改意圖的客戶,即可以提高對那些已經實施篡改項目的客戶的識別率；其次,結合時間序列分析,巧妙地避免了UnRAP算法中需要預知道篡改類型的不足；通過分析客戶所篡改項目的評分偏差及評分分布，采用多項目篡改客戶識別的策略，克服了UnRAP 1次只能識別1個篡改項目的弊端．

1 入侵推薦系統類型

由于推薦系統是靠在網上獲取客戶經營狀態的相關信息的，所以其設計原則具有開放性和互動性，這也給部分不良客戶以可乘之機，為達到提高自身項目評分，或者打壓降低競爭對手的同類項目評分，采用各種手段，杜撰虛假評分，以低廉的成本入侵到推薦系統中，直接導致評分結構的改變．根據入侵推薦系統的方法方式，大體可分為2類：1)以提高客戶自身項目評分為目的，稱為推篡改(push attack)，見表1中的i1；2)以降低競爭對手同類項目評分為目的，稱為核篡改(nuke attack)，見表1中的i5．

表1 客戶評分矩陣Tab.1 Customer score matrix

圖1 篡改狀態的組成結構Fig.1 tampered state of the composition of the structure

2 識別算法與改進思路

2.1 UnRAP篡改識別算法

算法的關鍵是計算客戶的Hv-score值,該值在一定程度上反映了篡改客戶項目的可疑度，然后利用聚類算法識別篡改狀態,分3個步驟完成.

1) 計算篡改客戶可疑度通常用評分矩陣中客戶的Hv-score值代替，以識別協同過濾推薦系統中的篡改客戶狀態.Hv-score值計算方法如下：

(1)

其中，客戶u對項目i的評分為ru,i，rU,j表示客戶u對所有項目評分的均分，項目i得到的平均分為ru,I，rU,I表示評分矩陣的平均分．

2) 計算客戶項目偏離度計算篡改客戶可疑度(Hv-score值)較高的客戶的各個項目評分的偏離值(deviation)，顯然，偏離值越大，被篡改的可能性越大，項目評分的偏離值計算公式為

(2)

3) 確定篡改狀態為確定項目篡改狀態，先以可疑度前若干名的客戶建立一個滑動窗口，并計算窗口中被篡改項目的偏離值，如果窗口的偏離值大于零，則屬于推篡改，于是讓窗口向后滑動一個客戶，即去掉可疑度第一的客戶，增加可疑度排名緊鄰窗口更低的客戶，構成新窗口，繼續計算新窗口的偏離值，依此類推，直到偏離值小于等于零后窗口右端的客戶為終止客戶，在所有窗口中該客戶可疑度最小.再從可疑度最高的客戶到可疑度最小的終止客戶這個窗口內，確認篡改項目的客戶，很自然,如果項目評分高于窗口平均分的對應客戶，就可被認定為篡改客戶．運用同樣的方法，從相反角度尋找核篡改客戶．

UnRAP算法識別普通篡改時效果比較好，但是識別流行篡改和核篡改時效果比較差，誤判情況比較嚴重，并且需提前獲知篡改方式，大大降低了算法的實用性．

2.2 PCA VarSelect篡改識別算法

PCA VarSelect篡改識別算法是基于主成分分析方法，把客戶作為變量，如果客戶變量間相關性低，則說明客戶正常，反之，如果客戶變量間相關性高，則說明篡改項目狀態的可能性高，因此，將客戶變量相關度高的項目篡改狀態過濾掉．

為計算客戶變量的相關性，首先對客戶評分矩陣做主成分分析，可獲得每個客戶對應的前1～3個主成分數值，以該數值作為指標，進行客戶項目狀態篡改的識別數值，再計算他們的間隔距離，取值最小的r個客戶作為客戶項目篡改狀態，r為可調．

算法流程如下：

UλVT=SVD(D)

PCA1←U(∶,1)

PCA2←U(∶,2)

for all columned user in D d

Distance(user)←PCA1(user)2+PCA2(user)2

end for

sort Distance

retum r users with smallest Distance values

不足之處在于算法需要預先知道篡改項目狀態的客戶規模r，實際應用中該規模值難以預估，預置不準將可能影響識別精度．

綜合比較上述2種算法發現各有利弊，是否可以在利用他們的優勢的基礎上，再設法克服其弊端？比如預估，預置不準將可能影響識別精度．

1)利用PCA VarSelect算法代替HV-score，提高識別精度；

2)增加時間序列分析，通過劃分推薦系統中的時間區間，初步確認客戶開始實施篡改項目狀態的時間，以此縮小識別范圍，再對該時間段內客戶的評分矩陣進行分析，進一步確定客戶篡改項目的類型.通過這個環節可以彌補UnRAP算法中需預知道客戶項目篡改類型的不足；

3)為實現對多個項目的篡改狀態同時進行識別,在分析被篡改項目評分偏差的基礎上,再分析評分的分布．

3 改進的篡改項目狀態識別算法

客戶篡改項目狀態常帶有急功近利心態，就是希望經過短時間的篡改，使得項目狀態表現的評分值直線提高.這就需要在有限時間段內，篡改量要達到一定規模，否則，對項目在推薦系統中的推薦名次與影響勢必達不到期望目標．特別是篡改客戶在篡改項目狀態的初期，或者一段時間內，沒有能改變在推薦系統中的排名，那么這段時間的努力將會隨著時間逐漸被淹沒甚至消失．因此，篡改客戶需要在一段時間加大篡改項目狀態的力度，以保持篡改后項目狀態變化處于上升態勢，并具有連續性和緊密性，這就是說，急功近利篡改項目狀態的心態會導致再短時間內項目狀態評分會有一個突變并持續上升．因此，可以通過對時間序列進行的分區，分析每個時間區域的客戶項目評分變化特征，以減小計算量并提高識別精度．

具體按照以下步驟操作.

1)確定客戶項目篡改時間段

首先是確定時間序列，時間序列的起始時間自然定為推薦系統開始獲取客戶數據的某個時間，然后按照給定的時間長度分割時間序列，技巧在于使得時間分割點的間距盡可能的小，再運用UnRAP算法篩選出被篡改項目的可疑客戶，最后選取被篡改項目的前10%的可疑客戶，依次計算出這些客戶在每個時間段篡改項目的評分與正常評分的偏離值，把評分偏離值最大的時間段對應的區間作為項目狀態篡改的區間段.這樣明顯縮小了可疑篡改項目狀態客戶的范圍．計算方法如下：

(3)

2)確定項目篡改類型與對應的篡改客戶集

運用前述方法選定的項目篡改時間段有一個顯著的特征，就是在該時間段內，推薦系統中存在較多的項目狀態篡改評分，所以該時間段內的客戶項目狀態評分與其他時間段內的客戶項目狀態評分會有較大的偏差，利用這個時間段客戶評分偏差的特征，可進一步確定項目狀態篡改類型．在項目篡改時間段內如果某客戶項目狀態的評分，大于所有客戶項目狀態評分的平均值3分及以上的，則可認定該項目狀態可能被推篡改，反之則可認為是遭到核篡改．

篡改類型確定了之后，可以通過所有客戶項目狀態評分的平均值確定篡改可疑客戶集合．對于被推篡改類型，該時間段內，凡是項目評分大于或等于所有客戶項目狀態均評分的客戶，均可認定為被推篡改客戶；反之，項目評分值小于所有客戶項目狀態均評分的客戶，可被認定為核篡改客戶．

3)對項目狀態篡改客戶進行進一步篩選確認

通過前述2個步驟獲得了篡改可疑客戶集合，對于被推篡改類型，可疑客戶集合中每個項目的評分均大于或等于所有客戶項目狀態評分的平均值，以此均作為可疑篡改客戶難免會出錯，為此，為了進一步提高識別精度，求可疑篡改客戶集與識別到的篡改客戶集的交集，篩選一部分被誤判的正常客戶

C=A∩B，

(4)

其中，A表示運用時間序列分析算法篩選出來的全部篡改客戶集，B為基于時間段區間篩選出的可疑篡改客戶集．C為給定時間段對應區間內項目狀態篡改客戶集．

4 多個項目狀態篡改的識別

客戶項目狀態篡改識別算法是針對單一同類項目的，但客戶經營項目往往是多個，此時，客戶篡改項目狀態也必定是多個項目同時進行篡改.但是，到目前為止，針對多個項目狀態同時受到篡改的問題還未見有相關成果．雖然UnRAP算法通過分析可疑篡改客戶對項目狀態的評分分布，但由于該方法是將最大評分偏離值作為狀態篡改項目，即1次只能篩選出1個被篡改的項目，如果有多個項目被篡改，則需在去掉篩選出的項目后，再重復前面的算法，顯然，計算量明顯增加.

為此，考慮設置一個閾值，將最大評分偏離值，改為評分偏離值超過給定閾值，則對應考察的項目就可以是多個.

多個項目狀態篡改的識別想法并不復雜，這里不詳細描述.

考慮同時篡改3個項目狀態的篡改模型，如圖2所示，利用公式(2)可求得項目偏離值的分布圖，仔細觀察不難發現，正常項目狀態變化不是很大，與平均值的差距處在較低的區間，而項目狀態受到篡改的基本上都與正常項目具有較大的偏離值．

不過，因為涉及的項目多，超過設定閾值的偏離度也不一樣，為便于統一比較，需要利用下式(5)對偏離值進行歸一化處理：

(5)

其中D集合為項目的偏離值，D(i)則表示項目i的偏離值，HE則為歸一化后的偏離值集合．

項目ID/103圖2 項目偏離值分布Fig.2 Project deviation value map

隨后，設置一個適當的閾值，以確定項目狀態被篡改的客戶名單和數量，仍運用基于時間序列分析的項目狀態篡改識別算法，計算每個客戶對應的篡改項目狀態，最后對每個相應篡改項目狀態的篡改客戶取交集，篩選掉重復的客戶，最終確定篡改客戶狀態，如圖3所示.

項目ID/103圖3 變換后的偏離值分布Fig.3 Transformed deviation value map

算法流程見圖4.

5 實驗分析

5.1 數據集

采用Movie lens網站(http://movilens.umn.edu/)提供的一組客戶評價項目狀態的數據，數據涉及到900多個客戶，1 600多個項目，評分數據更是高達10萬條，數據顯示，客戶對項目狀態評價的活躍度也較高．通常客戶評分采用五級制，分別記為1、2、3、4、5分，分值越大表示客戶對項目的評價越高．

5.2 評判標準

為便于統一比較，采用如下評判標準：

1)對于篡改項目項的識別，采用識別率Ti和誤判率Fi作為評價指標．其計算公式為

其中，TPi表示正確識別的項目總數，FNi表示未被識別的項目總數.

2)采用準確率Pu與召回率Ru作為識別項目狀態是否被篡改的評價指標

其中，TPu表準確篩選出被篡改狀態的總數，FGu表本屬正常客戶，卻被篩選為篡改狀態的客戶數，FPu表沒有被篩選出的篡改狀態客戶數．

5.3 實驗比較

為比較算法的性能，使得實驗具有一定的真實性，采用3種篡改模型生成不同的篡改項目狀態，3種項目狀態篡改模型分別用均值篡改、隨機篡改、流行篡改方法獲得．

5.3.1 1個項目狀態的篡改篩選分析

僅選取1個項目的狀態作為篡改對象，分別按照1%、2%、5%、7%、9%、10%的項目狀態篡改規模生成篡改項目狀態．

具體實驗過程中，先隨機抽取20個項目作為篡改狀態的項目，對每個項目重復10次實驗，10次實驗的平均值作為項目狀態的篡改識別結果．

從3種篡改模型識別精確度比較圖5可以看出，T-UnRAP算法識別精度比UnRAP算法要高，特別地，當項目狀態是受到核篡改，或流行篡改時，篩選準確率也較高，不僅如此，算法還具有一定的自適應能力，即可以自動識別篡改項目狀態的類型．

5.3.2 多項目的篡改狀態識別

選取篡改項目群的項目個數分別為1、3、5、10，填充規模為1%，篡改規模為1%、2%、5%、10%．識別率為對項目的識別度的識別結果評價，精確度和召回率是對相應的篡改狀態的識別結果評價．仍然采用先隨機抽取若干項目作為篡改狀態的項目，對每個項目重復10次實驗，10次實驗的平均值作為項目狀態的篡改識別結果．

從表2、表3、表4可以看出，無論項目狀態的篡改模型，篡改類型，和篡改規模如何改變，對項目狀態是否被篡的識別率均較高，且準確度都在90%以上，召回率有時甚至達到99%．

圖5 3種篡改模型識別精確度比較Fig.5 Comparison of three tampering model recognition accuracy

表2 不同項目個數和篡改規模的隨機篡改模型的篩選準確率Tab.2 Number of different projects and tampering the size of the random tampering model of the screening accuracy

續表2Continued Tab.2

表3 不同項目個數和篡改規模的均值篡改模型的篩選準確率Tab.3 Number of different projects and tampering the scale of the mean tampering model of the screening accuracy

表4 不同項目個數和篡改規模的流行篡改模型的篩選準確率Tab.4 Number of different projects and tampering the scale of the popular tampering model screening accuracy

6 結論

準確識別客戶項目狀態是否被篡改是推薦系統安全性的一個熱點研究方向．本文在流行篡改客戶項目狀態識別算法的基礎之上，融入時間序列分析方法，利用客戶評分分布的差異性與時間序列的關聯關系，實現自動識別項目狀態篡改類型，改進后的項目狀態篡改算法不僅識別準確率和召回率都有明顯提高，且對多項目及其所對應的項目狀態篡改也可以進行有效的識別．

[1] BURKE R,MOBASHER B,WILLIAMs C,et al.Classification features for attack detection in collaborative recommender Systems[C]//Proceedings of the 12th ACM SIGKDD International Conference,ACM Press,2006:542-547.

[2] CHIRITA P A,NEJDL W,ZAMFIR C.Preventing shilling attacks in online recommender systems[C]//Proceedings of The 7th annual ACM international workshop on Web information and data management,ACM Press,2005:67-74.

[3] LEE J S,ZHU D.Shilling attack detection-A new approach for a trustworthy recommender system[J].Informs Journal on Computing,2011,3(10): 1-15.

[4] SHI Z W,YANG S,JIANG Z G,et al.Hyperspectral target detection using regularized high-order matched filter[J].Optical Engineering,2011,50(5):057201-1-057201-10.

[5] MRHTA B,HOFMANN T,FANKHAUSER P.Lies and propaganda: detecting spam users in collaborative filtering[C]//Proceedings of The 12th international Conference on Intelligentuer Interfaces,ACM Press,2007:14-21.

[6] 李聰,駱志剛,石金龍.一種探測推薦系統托篡改的無監督算法[J].自動化學報,2013.39(10):1681-1690.DOI:10.3724/sp.J.1004.2013.01681.

LI C,LUO Z G,SHI J L.Detecting shilling attacks in recommender systems based on Non-random-missing Mechanism [J].ACTA AUTOAMTICA SINICA,2013.39(10):1681-1690.DOI:10.3724/sp.J..1004.2013.01681.

[7] 于洪濤,魏莎,張付志，等.基于多項目項目檢索的無監督客戶狀態篡改識別算法[J].小型微型計算機系統,2013,34(9):2120-2124.DOI:10.3969/j.issn.1000-1220.2013.09.031.

YU H T,WEI S,ZHANG F Z ,et al.An unsupervised algorithm for detecting user profile attack based on multi-target items retrieval[J].Journal of Chinese Computer Systems,2013,34(9):2120-2124.DOI:10.3969/j.issn.1000-1220.2013.09.031.

[8] TAN Z,JAMDAGNI A，HE X,et al.A system for denial-of-service attack detection based on multivariate correlation analysis[J].Parallel and Distributed Systems IEEE Transactions on,2014,25(2):447-456.

[9] DACER M C,KARGL F,KONIGH,et al.Network attack detection and defense:securing industrial control systems for critical infrastructures(Dagstuhl Seminar 14292)[J].Dagstuhl Report,2014,4(7):62-79.

[10] 于洪濤,李鵬,張付志.基于多維風險因子的推薦篡改識別方法[J].小型微型計算機系統,2015,36(5):971-975.

YU H T,LI P,ZHANG F Z.Method for detecting recommendation attack based on multiple risk factors [J].Journal of Chinese Computer Systems,2015,36(5):971-975.

[11] 郝志峰,牛曉龍,蔡瑞初,等.融合信息熵與信任機制的防篡改推薦算法研究[J].計算機應用與軟件,2015,32(3):284-288.DOI:3969/j.issn.1000-386x.2015.03.067.

HAO Z F,NIU X L,CAI R C,et al.Research compiter applications and sortware anti-attack recommendation algorithm with fusion of information entropy and trust mechanism[J].Computer Application and Software,2015,32(3):284-288.DOI:3969/j.issn.1000-386x.2015.03.067.

[12] 岳猛,吳志軍,姜軍.云計算中基于可用帶寬歐式距離的LDoS篡改識別方法[J].山東大學學報(理學版),2016,51(9):92-100.DOI:10.6040/j.issn.1671-9352.3.20.090.

YUE M,WU Z J,JIANG J.An approach of detecting LDOS attacks based on the euclidean distance of available bandwidth in cloud computing[J].Journal of Shandong Universty(Natural Science),2016,51(9):92-100.DOI:10.6040/j.issn.1671-9352.3.20.090.

(責任編輯：孟素蘭)

Customerprojectstatustamperingalgorithmbasedontimeseriesanalysis

CHENChaofan1,LINShuxin2

(1.College of Information Science and Technology,Hainan University,Haikou 570228,China;2.Collegeof Engineering and Technology,Hainan College of Economics and Business,Haikou 571127,China)

The existing customer project status recognition algorithm can not adaptively identify the tampering type and can not simultaneously identify the tampering of multiple project states,the algorithm of tampering recognition based on time series analysis is given.The PCA VarSelect algorithm is used to derive the suspicious list of project status and further reduce the recognition range.The method is to determine the tampering state according to the tampering time period and the score deviation degree.On this basis，this method can further analyze the tampering period of time to determine the type of tampering and finally identify the corresponding tampered state of the project.Simulation shows that the algorithm has high recognition accuracy.It not only can identify the tampering state of a single project,but also can identify the tampering state of multiple projects at the same time.

project status tampering algorithm；time series analysis；PCA；recognition accuracy

TP391

A

1000-1565(2017)05-0545-10

10.3969/j.issn.1000-1565.2017.05.015

2016-12-01

國家自然科學基金資助項目(71361008)

陳超凡 (1993—)，男，江蘇南京人，海南大學在讀碩士研究生，主要從事算法理論與軟件工程研究.E-mail:75181146@qq.com

林書新(1973—)，男，海南海口人，海南經貿職業技術學院副教授，主要從事算法理論與計算機應用研究.E-mail：38860058@qq.com