基于多變量自動(dòng)回歸的評(píng)分?jǐn)?shù)據(jù)異常檢測(cè)算法

孫連海，盧 穎

(1.成都師范學(xué)院 計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 611130；2.西安工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710021)

0 引 言

在當(dāng)今互聯(lián)網(wǎng)環(huán)境下，產(chǎn)品或者服務(wù)的評(píng)價(jià)普遍存在。這些評(píng)價(jià)可以向新的用戶提供產(chǎn)品或者服務(wù)的質(zhì)量，并且對(duì)用戶對(duì)產(chǎn)品或者服務(wù)的購(gòu)買提供決策信息[1]。隨著社會(huì)的快速發(fā)展，公司或者產(chǎn)品制造商之間的競(jìng)爭(zhēng)也日益激烈，產(chǎn)品的評(píng)價(jià)同樣也影響著產(chǎn)品的生產(chǎn)線。事實(shí)上，客戶對(duì)產(chǎn)品的評(píng)價(jià)可以作為產(chǎn)品未來(lái)銷售的基本預(yù)測(cè)指標(biāo)[2]。為了避免負(fù)面影響，公司可以通過(guò)分析產(chǎn)品的評(píng)價(jià)找出產(chǎn)品的缺陷或者功能上的不足，從而更好地改進(jìn)產(chǎn)品的設(shè)計(jì)。

本文通過(guò)對(duì)產(chǎn)品的評(píng)價(jià)值分布進(jìn)行時(shí)序分析，從而發(fā)現(xiàn)用戶評(píng)價(jià)的基本模式和異常模式。在時(shí)序的評(píng)價(jià)值分布中，本文的目標(biāo)是提取用戶的基本行為和異常行為。基本行為反應(yīng)了產(chǎn)品的質(zhì)量隨著時(shí)間的變化，異常行為是用戶對(duì)產(chǎn)品的評(píng)價(jià)值為異常模式的時(shí)間點(diǎn)。異常值的出現(xiàn)主要有兩種，第一種是通過(guò)大量的垃圾信息鼓吹產(chǎn)品的質(zhì)量[3,4]，第二種是產(chǎn)品生產(chǎn)過(guò)程的改進(jìn)[5]。基本行為表達(dá)了產(chǎn)品在時(shí)序影響下的質(zhì)量，例如隨著競(jìng)爭(zhēng)對(duì)手的技術(shù)更新產(chǎn)品的質(zhì)量逐漸下降。異常為用戶評(píng)價(jià)值的不規(guī)則性，例如觀測(cè)到的用戶評(píng)價(jià)值偏離了用戶的基本評(píng)價(jià)值。

本文應(yīng)用產(chǎn)品的時(shí)序評(píng)價(jià)值分布對(duì)產(chǎn)品的基本模式進(jìn)行分析，并對(duì)異常的行為模式進(jìn)行檢測(cè)。對(duì)于不同的數(shù)據(jù)類型，文獻(xiàn)[6]提出了不同的異常檢測(cè)方法。當(dāng)數(shù)據(jù)是獨(dú)立同分布時(shí)，流數(shù)據(jù)的時(shí)序異常檢測(cè)研究是一項(xiàng)重要的研究?jī)?nèi)容[7,8]。在時(shí)序數(shù)據(jù)的異常檢測(cè)中，時(shí)序數(shù)據(jù)中的部分?jǐn)?shù)據(jù)可能為異常數(shù)據(jù)，然而本文考慮的是單獨(dú)的多變量時(shí)序數(shù)據(jù)，其中的某些時(shí)間點(diǎn)可能為異常數(shù)據(jù)[9,10]。此外，在流數(shù)據(jù)異常檢測(cè)中，假設(shè)數(shù)據(jù)是以流的形式不斷到達(dá)，由于系統(tǒng)內(nèi)存空間的局限性僅能處理部分?jǐn)?shù)據(jù)，因而需要額外的數(shù)據(jù)處理對(duì)異常進(jìn)行分析[11]。本文假設(shè)產(chǎn)品的評(píng)價(jià)數(shù)據(jù)是時(shí)序的，并且整個(gè)評(píng)價(jià)值的歷史記錄是已知的，因此可以更好地對(duì)數(shù)據(jù)進(jìn)行分析。在傳統(tǒng)的異常檢測(cè)中，現(xiàn)有的算法往往假設(shè)數(shù)據(jù)中的異常是相互獨(dú)立的，并且是一種隨機(jī)誤差[6]，本文則認(rèn)為產(chǎn)品的評(píng)價(jià)值異常反應(yīng)了產(chǎn)品質(zhì)量的某種傾向。

本文將用戶對(duì)產(chǎn)品評(píng)價(jià)數(shù)據(jù)視為用戶基本行為和異常行為的組合，應(yīng)用多變量自動(dòng)回歸方法進(jìn)行用戶基本行為的發(fā)現(xiàn)和異常行為的檢測(cè)。將用戶的評(píng)價(jià)值分布表示為累積分布，并且將評(píng)價(jià)值表示為基本行為和異常行為的線性組合的生成過(guò)程。針對(duì)評(píng)價(jià)值中混入的異常行為的稀疏性，基于噪音數(shù)據(jù)的高斯分布，給出了相應(yīng)的最小化目標(biāo)函數(shù)。

1 多變量自動(dòng)回歸異常檢測(cè)模型

本文基于多變量自動(dòng)回歸方法對(duì)產(chǎn)品的評(píng)分?jǐn)?shù)據(jù)進(jìn)行挖掘，從而分析出用戶的基本行為，以及對(duì)異常行為的檢測(cè)。

1.1 數(shù)據(jù)表達(dá)

在評(píng)價(jià)分布的累計(jì)分布表示中，由于最后一項(xiàng)始終為1，故可以將其省去。此外，在累積分布中，數(shù)據(jù)項(xiàng)之間為非遞減的，后面的數(shù)據(jù)始終大于或者等于前面的數(shù)據(jù)，其具體描述見(jiàn)式(1)

CD:={x∈[0…1]D|?i:xi≤xi+1}

(1)

令X=(x(1),…,x(T))，其中x(t)的維度為D=M-1，并且x(t)∈CD。本文應(yīng)用累積分布X=(x(1),…,x(T))進(jìn)行數(shù)據(jù)分析，然而在應(yīng)用圖形對(duì)數(shù)據(jù)進(jìn)行展示時(shí)仍然應(yīng)用原始的評(píng)價(jià)數(shù)據(jù)。

1.2 產(chǎn)生過(guò)程模型

已知產(chǎn)品的時(shí)序評(píng)價(jià)數(shù)據(jù)X=(x(1),…,x(T))，本文的目的是提取出用戶的基本行為，以及異常行為及其發(fā)生時(shí)間點(diǎn)。由于X中混入了異常數(shù)據(jù)，因此不能直接應(yīng)用X估計(jì)用戶的基本行為。

本文令時(shí)序評(píng)價(jià)數(shù)據(jù)X=(x(1),…,x(T))為用戶基本行為與異常行為混合而成，將用戶的基本行為A=(a(1),…,a(T))視為潛在變量，那么可以根據(jù)X推導(dǎo)出A，并且依據(jù)A分析用戶的異常行為，其模型如圖1所示。根據(jù)圖1所示，評(píng)價(jià)數(shù)據(jù)x(t)(1≤t≤T)滿足如下隨機(jī)產(chǎn)生過(guò)程

x(t)=pt·a(t)+(1-pt)·y+εt

(2)

其中，pt為時(shí)間t的權(quán)衡系數(shù)，pt的取值越大，表明該時(shí)間下用戶基本行為的權(quán)重越大，εt為時(shí)間t的隨機(jī)噪音。為了確保模型間各個(gè)參數(shù)之間的相互預(yù)測(cè)性，用戶的基本行為和異常行為的累積分布必須是有效的，即a(t),y∈CD。在式(2)中，x(t)為觀測(cè)到的累積評(píng)價(jià)分布，a(t)為用戶的基本行為分布，y為用戶的異常行為分布。

圖1 產(chǎn)生過(guò)程的圖模型描述

假設(shè)X中用戶的基本行為a(t)是平滑的，當(dāng)X出現(xiàn)異常行為y時(shí)，X的值會(huì)發(fā)生突然變化，本文采用向量自動(dòng)回歸模型描述上述過(guò)程。在時(shí)刻t，用戶的正常行為a(t)取決于先前時(shí)刻的行為a(t-1)，并允許適當(dāng)?shù)耐蛔儯潆S機(jī)產(chǎn)生過(guò)程為

(3)

1.3 數(shù)據(jù)稀疏性

(4)

式(4)所示的先驗(yàn)分布函數(shù)具有以下優(yōu)點(diǎn)：①該先驗(yàn)分布函數(shù)易解釋。通過(guò)應(yīng)用L1范式，λ的值為異常的個(gè)數(shù)的上屆，并且當(dāng)異常發(fā)生時(shí)容易定位時(shí)間點(diǎn)。②該分布函數(shù)為考慮了異常個(gè)數(shù)上屆λ的最大熵分布。該分布函數(shù)是不提供信息的先驗(yàn)函數(shù)，并不偏好與特定的向量p。③通過(guò)該先驗(yàn)分布函數(shù)，可以應(yīng)用模型選擇方法自動(dòng)地確定參數(shù)λ。

1.4 目標(biāo)函數(shù)

(5)

(6)

(7)

其中，自變量x可以為a(0)，y，b或者w。由于式(7)中向量的取值是有界的，因此是有效的先驗(yàn)分布函數(shù)。

當(dāng)所有變量都在有效的取值范圍內(nèi)，聯(lián)合分布似然性p(X,Z)的計(jì)算公式如下

(8)

(9)

1.5 模型選擇與預(yù)測(cè)

本文通過(guò)對(duì)模型進(jìn)行選擇確定式(9)中的參數(shù)λ。λ控制著自由參數(shù)的個(gè)數(shù)，當(dāng)λ從0變?yōu)?時(shí)，自由參數(shù)增加2+D個(gè)，此外當(dāng)λ再增加1時(shí)，自由參數(shù)增加2個(gè)。當(dāng)λ=0時(shí)，沒(méi)有用到參數(shù)y，當(dāng)λ=1時(shí)，參數(shù)y出現(xiàn)，所以該步驟多了額外的D個(gè)參數(shù)。

本文應(yīng)用BIC(Bayesian information criterion)[12]來(lái)確定λ的最優(yōu)值。給定λ，BIC(λ)=-2lnLλ+kλ·ln(D·T)。通過(guò)最小化BIC(λ)，可以得到最優(yōu)的λ

(10)

其中，kλ=m+2λ+D·min(λ,1)為自由參數(shù)的個(gè)數(shù)，m為本文提出的模型中不受參數(shù)λ影響的參數(shù)，Lλ=1/f(a(0),…,a(T),b,w,y,p)D·T為數(shù)據(jù)的似然性。由于m不受λ影響，因此m的變化不會(huì)影響最優(yōu)λ的選取。

在根據(jù)時(shí)序評(píng)價(jià)數(shù)據(jù)得到用戶的基本行為和異常行為描述后，可以對(duì)未來(lái)的評(píng)價(jià)值進(jìn)行預(yù)測(cè)。由于評(píng)價(jià)數(shù)據(jù)中異常數(shù)據(jù)是稀疏的，那么可以根據(jù)T時(shí)刻的用戶基本行為預(yù)測(cè)T+1時(shí)刻的評(píng)價(jià)值

(11)

在式(11)中，噪音誤差為高斯分布的期望值0。通過(guò)將式(11)計(jì)算得到的預(yù)測(cè)結(jié)果與真實(shí)的觀測(cè)結(jié)果相對(duì)比，從而可以判斷未來(lái)時(shí)刻T+1的用戶行為是否為異常行為。

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

2.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)采用公開(kāi)的Amazon數(shù)據(jù)集[13]，該數(shù)據(jù)集包含大約400 000個(gè)評(píng)價(jià)值以及相應(yīng)的時(shí)間戳。對(duì)于數(shù)據(jù)集中的每個(gè)評(píng)價(jià)值，均取值為1星到5星的5個(gè)離散的評(píng)價(jià)值，每條評(píng)價(jià)數(shù)據(jù)包含評(píng)價(jià)用戶的ID以及被評(píng)價(jià)產(chǎn)品的ID。此外，數(shù)據(jù)集中還包含產(chǎn)品的文本評(píng)價(jià)，實(shí)驗(yàn)應(yīng)用該文本評(píng)價(jià)作為結(jié)果判斷的準(zhǔn)確性。

2.2 算法評(píng)估

實(shí)驗(yàn)通過(guò)對(duì)Amazon數(shù)據(jù)集進(jìn)行分析，評(píng)估本文提出的算法在挖掘用戶基本行為和異常行為時(shí)的性能。首先，我們觀察評(píng)價(jià)數(shù)據(jù)集中不同時(shí)間序列點(diǎn)下評(píng)價(jià)的分布情況，如圖2所示。橫軸為不同時(shí)間戳下的數(shù)據(jù)評(píng)價(jià)值，縱軸為不同評(píng)價(jià)值所占的比例。從該圖可以看出，在Amazon數(shù)據(jù)集中，用戶對(duì)產(chǎn)品的評(píng)價(jià)分布是無(wú)規(guī)律的或者規(guī)律不明顯，這說(shuō)明用戶的基本行為和異常行為混合在一起，從而使得評(píng)價(jià)序列無(wú)明顯規(guī)律。

圖2 數(shù)據(jù)集中用戶評(píng)價(jià)的真實(shí)分布

接下來(lái)，采用本文提出的多變量自動(dòng)回歸算法對(duì)數(shù)據(jù)集進(jìn)行分析，進(jìn)而提取出評(píng)價(jià)序列中用戶的基本行為和異常行為，結(jié)果分別如圖3和圖4所示。從圖3中可以看出，用戶的基本行為從整個(gè)時(shí)間序列上看是基本穩(wěn)定的，在所有的時(shí)間序列點(diǎn)上，評(píng)價(jià)值的分布無(wú)太大的變化。然而在圖4中，異常行為卻有著較大的波動(dòng)。將圖3和圖4結(jié)合在一起，便可以得到圖2所示的評(píng)價(jià)值分布。

圖3 數(shù)據(jù)集中隱含的用戶基本行為

圖4 數(shù)據(jù)集中隱含的用戶異常行為

2.3 性能對(duì)比

為了評(píng)價(jià)算法的預(yù)測(cè)性能，將本文提出的算法與rob.VAR[7]，Kalman[8]和VAR[11]這3種算法進(jìn)行了對(duì)比，結(jié)果如圖5所示。圖中的橫坐標(biāo)表示數(shù)據(jù)集中包含的異常個(gè)數(shù)，縱坐標(biāo)表示用戶對(duì)產(chǎn)品的預(yù)測(cè)評(píng)價(jià)值與真實(shí)評(píng)價(jià)值之間的誤差的平均值。從該圖可以看出，當(dāng)數(shù)據(jù)集中包含的異常個(gè)數(shù)增加時(shí)，4種算法的預(yù)測(cè)誤差都隨之增大。然而，不論異常個(gè)數(shù)為何值，本文提出的算法的誤差都是最小的，從而可以認(rèn)為本文提出的算法在預(yù)測(cè)用戶未來(lái)的評(píng)價(jià)值時(shí)具有很高的準(zhǔn)確性。

圖5 算法的預(yù)測(cè)性能對(duì)比

3 結(jié)束語(yǔ)

異常檢測(cè)在推薦系統(tǒng)，入侵檢測(cè)和流數(shù)據(jù)分析等領(lǐng)域都有著廣泛的應(yīng)用前景。為了從用戶對(duì)產(chǎn)品的評(píng)價(jià)數(shù)據(jù)中分析出用戶的基本行為以及異常行為，本文提出了一種基于多變量自動(dòng)回歸的評(píng)分?jǐn)?shù)據(jù)異常檢測(cè)算法。本文將用戶對(duì)產(chǎn)品評(píng)價(jià)數(shù)據(jù)視為用戶基本行為和異常行為的組合，應(yīng)用多變量自動(dòng)回歸方法進(jìn)行用戶基本行為的發(fā)現(xiàn)和異常行為的檢測(cè)。將用戶的評(píng)價(jià)值分布表示為累積分布，并且將評(píng)價(jià)值表示為基本行為和異常行為的線性組合的生成過(guò)程。針對(duì)評(píng)價(jià)值中混入的異常行為的稀疏性，基于噪音數(shù)據(jù)的高斯分布，給出了相應(yīng)的最小化目標(biāo)函數(shù)。實(shí)驗(yàn)結(jié)果表明，本文提出的算法能很好的描述時(shí)序評(píng)價(jià)序列中用戶的基本行為和異常行為，并且與相關(guān)算法相比較能更好的對(duì)未來(lái)的評(píng)價(jià)值進(jìn)行預(yù)測(cè)。

參考文獻(xiàn)：

[1]Melnyk I,Matthews B,Valizadegan H,et al.Vector autoregressive model-based anomaly detection in aviation systems[J].Journal of Aerospace Information Systems,2016,13(4):1-13.

[2]Günnemann N,Günnemann S,Faloutsos C.Robust multivariate autoregression for anomaly detection in dynamic product ratings[C]//International Conference on World Wide Web,2014:361-372.

[3]Bhaumik R,Williams C,Mobasher B,et al.Securing colla-borative filtering against malicious attacks through anomaly detection[C]//Proceedings of the 4th Workshop on Intelligent Techniques for Web Personalization,2016:112-118.

[4]Samejima M,Ohno H,Akiyoshi M,et al.An anomaly detection method on web-based system by trend analysis with autoregressive model[J].IEEJ Transactions on Electronics Information & Systems,2014,134(6):814-820.

[5]Malekzadeh M,Gul M,Catbas F N.Application of multivariate statistically based algorithms for civil structures anomaly detection[C]//Society for Experimental Mechanics Series,2013:289-298.

[6]Aggarwal C C.Outlier analysis[M].USA:Springer,2013.

[7]Tan S C,Ting K M,Liu T F.Fast anomaly detection for streaming data[C]//International Joint Conference on Artificial Intelligence,2013:1511-1516.

[8]Sanchez H,Bustos B.Anomaly detection in streaming time series based on bounding boxes[M].USA:Similarity Search and Applications.Springer International Publishing,2014:201-213.

[9]Marat I Kusainov,Vyacheslav A Vasiliev.On optimal adaptive prediction of multivariate autoregression[J].Sequential Analysis,2015,34(2):211-234.

[10]Sallam A,Fadolalkarim D,Bertino E,et al.Data and syntax centric anomaly detection for relational databases[J].Wiley Interdisciplinary Reviews Data Mining & Knowledge Discovery,2016,6(6):231-239.

[11]Sallam A,Xiao Q,Bertino E,et al.Anomaly detection techniques for database protection against insider threats (invited paper)[C]//International Conference on Information Reuse and Integration.IEEE,2016:20-29.

[12]Abramson N,Braverman D,Sebestyen G.Pattern recognition and machine learning[J].IEEE Transactions on Information Theory,2017,9(4):257-261.

[13]Mason W,Suri S.Conducting behavioral research on ama-zon’s mechanical Turk[J].Behavior Research Methods,2012,44(1):1-23.