高亞星,趙旭俊,曹栩陽

(太原科技大學 計算機科學與技術學院,山西 太原 030024)

0 引 言

離群數據是指與其他數據分布有顯著不同的數據對象[1]。離群點檢測是通過分析離群數據的特征,從海量數據中挖掘異常信息和提取興趣模式的一種方法,已廣泛地應用在欺詐檢測[2]、入侵檢測[3]、疾病檢測[4]、時間序列離群值檢測[5]等領域。

基于數據自表示的離群點檢測[6]是一種有效的方法,該方法通過構建數據點間的稀疏表示,放大了數據間的差異性,在低維離群點檢測上有較好的性能。但該方法仍存在一定的局限性,導致其在高維數據上的離群點檢測效果不佳。隨著數據量和數據維度的急速攀升,解決該問題是十分必要的。

基于數據自表示的離群點檢測方法通過研究低維數據間的關聯性與稀疏性,并構建表示關系,在低維全局離群點檢測上獲得了較好的效果。但該方法在處理高維數據時存在以下兩點問題:第一,高維數據相較于低維數據會更加離散,使得該方法更難得出較為準確的數據表示,從而影響高維離群點檢測的效果;第二,該方法并未考慮特征間的關聯性對數據相互表示過程的影響,在處理低維數據時,這種局限性對檢測結果影響并不大,然而高維數據中特征間的復雜關系不容忽視,這些特征關系對離群點的檢測有較大影響,該方法的局限性被進一步放大。

為了解決以上問題,該文提出了一種基于融合數據自表示的離群點測檢算法。首先,使用文獻[7]提出的特征分組方法對數據集按照相關特征進行分組,達到數據約簡的目的。其次,提出一種基于特征關系的數據自表示方法,在每個特征分組內,運用信息理論度量特征間的關聯性,構建了包含特征和數據雙重信息的數據自表示矩陣。然后,提出一種基于融合組間數據自表示的計算方法,將不同特征分組和組中心特征集對應的數據自表示矩陣相融合,采用矩陣點乘和均值計算得出全局自表示矩陣,其包含了豐富的全局數據特征和數據信息。最后,提出了基于融合數據自表示的離群點測檢算法,該算法在全局數據自表示矩陣上構建了有向加權圖,并通過在該圖上隨機游走來檢測離群點。在多個真實數據集和人工合成數據集上的實驗結果表明,該算法具有良好的泛化性和穩(wěn)定性。

1 相關工作

目前,傳統(tǒng)離群點檢測算法主要分為四大類,分別是基于密度的方法[8]、基于距離的方法[9]、基于近鄰的方法[10]和基于聚類的方法[11]。隨著高維數據的出現,數據變得更加稀疏[6],全局離群值的挖掘受到更多不相關特征的影響,使得傳統(tǒng)的離群點檢測算法時間復雜度較高且檢測效果不佳。

提出基于子空間的方法[12-13]的目的是降低高維數據出現帶來的影響,此類方法將所有的數據點映射到一個或多個稀疏和低維子空間中進一步檢測離群點。文獻[12]提出了一種基于特征異常值相關分析的局部離群值檢測算法,由于其刪除了不相關數據點和數據特征,雖更適用于高維數據,但難以保證精度。文獻[13]提出利用隨機哈希方法對子空間內數據點進行評分。然而隨著數據集規(guī)模的增長,它的復雜性迅速增加。由于基于子空間的方法面向數據點進行劃分,較少地考慮數據特征間的關系,仍具有不足之處?；谔卣鞣纸M的離群點檢測算法有效彌補了上述缺陷。文獻[7]提出基于互信息和信息熵的特征分組方法,細化了特征間相關性度量,但是該方法在檢測全局離群點時忽略了不同特征分組間仍存在的關系,影響了檢測效果。

近些年提出了基于數據自表示的離群點檢測算法[6],此類方法時間復雜度較低,提升了高維離群點檢測效率,但仍存在一些問題。文獻[6]提出了基于數據自表示隨機游走離群點檢測方法,構建了數據點之間的稀疏表示,得到了較好的檢測效果,但由于未考慮數據特征間的相關性,使其檢測結果會丟失許多特征信息。文獻[14]提出了一種基于數據結構信息度量的雙核參數方法,獲得了更加準確的數據表示結果,但此方法存在參數依賴。文獻[15]提出了基于超像素的張量低秩分解,將其投影到低維空間檢測離群數據。但該方法受到初始字典的約束,同時在投影過程中會丟失部分信息。文獻[16]使用核范數而不是Schatten-p范數來獲得更準確的數據低秩表示。以上幾種方法雖有效降低了時間復雜度,但均存在參數依賴問題,同時處理高維數據時都未考慮數據特征間存在的復雜關系,從而影響了離群點檢測效果。

綜上所述,基于特征分組的離群點檢測方法雖降低了檢測維度,但在全局離群點的檢測中會丟失特征分組之間的相關性信息,影響了離群點檢測性能;基于數據自表示的離群點檢測方法在保證檢測結果準確性的同時,有效地降低了時間復雜度,但現有的數據自表示方法同樣丟失高維特征包含的有效信息,離群點檢測未能更全面和深入,從而影響最終的檢測效果。

2 基于特征關系的數據自表示方法

該文提出的基于特征關系的數據自表示方法,結合互信息與條件熵理論來度量特征間的關聯性,并將其融于數據自表示過程?；バ畔⒂糜诹炕瘍蓚€隨機變量之間的依賴程度。其值越高代表兩個變量之間相關性越高,一個變量在一定程度上可以被另一個變量所取代。條件熵用于描述已知在一個隨機變量的條件下,另一個隨機變量的不確定性。

設D={d1,d2,…,dn}為任意數據集,F={f1,f2,…,fl}為該數據集中所有特征的集合,其中:dn表示第n個數據點,fl表示第l個特征,n和l分別表示數據點和數據特征的個數。G={FG1,FG2,…,FGm}為算法FG[7]得出的特征分組集合,其中FGm表示第m個特征分組,m表示總分組數。

任一特征分組對應的數據自表示矩陣記為R={r1,r2,…,rn},以n*n方陣的形式記錄了這種表示關系,其主對角線上的值(rii)為0。R由使R(ri)值最小時的ri構成,R(ri)的計算公式如下:

(1)

其中,c表示該特征分組內的特征總數,ri表示矩陣R中的第i列,FG表示該特征分組集合,FGj表示第j個特征。系數δ和ω由公式(2)和公式(5)定義。

δ用于均衡地度量特征之間的相似性與相關性,將高斯核函數用于計算特征間的距離以表示相似性,同時互信息與條件熵用于度量特征間的概率關系以表示相關性,二者結合使得特征間的復雜關系得以深入且全面的表達。δ可由如下公式得出:

(2)

其中,FGi表示第i個特征,FGj表示第j個特征,其余符號同公式(1)中定義。I(FGi,FGj)表示FGi和FGj之間的互信息,可由公式(3)得出。H(FGi|FGj)表示FGj在FGi條件下的條件熵,可由公式(4)得出。

(3)

(4)

其中,fGi和fGj表示第i和第j個特征的值。

由于具有強相關性的特征會被劃分至同一分組,出現特征冗余現象,一定程度上浪費了計算資源。ω用于度量分組內特征間的冗余程度,提升了數據自表示結果的有效性。ω可由如下公式得出:

(5)

此節(jié)提出的基于特征關系的數據自表示方法,通過度量特征間存在的復雜關系,彌補了現有算法的局限性。該方法構建了數據點之間的稀疏線性組合,正常點僅由正常點表示,而離群點可以由正常點和離群點共同表示,并通過δ,ω和范數度量特征和數據的關聯性,以達到將特征信息與數據信息相融合的效果。

3 融合組間數據自表示與離群點檢測

根據上一節(jié)的方法,每個特征分組生成了對應的數據自表示矩陣,其中包含各分組的特征和數據分布信息,這種信息是局部的。由于不存在某個特征同時屬于兩個或更多分組的情況,導致數據自表示矩陣也是唯一對應的,使得原始數據被簡化,造成不同矩陣中包含的離群數據信息存在差異。若直接在其基礎上檢測離群點所得到的結果不足以涵蓋全局信息,又因為不同特征分組間仍然存在關聯性,這些信息對于準確地挖掘全局離群點有幫助,進一步研究融合組間關聯性將提升檢測結果有效性。

3.1 基于融合組間數據自表示的計算方法

通過融合特征組間關聯性構建的全局數據自表示矩陣(RT)可由如下公式得出:

(6)

其中,FG算法依據其定義的相關性度量方式,得到各組中心特征,具有與組內其余特征均強相關的特點。FG算法得出的組中心特征集表示為FC={FC1,FC2,…,FCm},RC表示FC上的數據自表示矩陣,R1·R2·…·Rm分別表示m個特征分組對應的數據自表示矩陣。公式(6)中,通過構建中心特征分組對應的數據自表示矩陣(RC),將不同組中心融合為一體,使得每個特征分組的主要信息被集中表達,均衡了組間差異性。R1·R2·…·Rm表示通過點乘各自表示矩陣,使得正常點與離群程度較大的點相互表示值與其他表示關系之間的差值增大,某些可能是離群點的數據與正常點之間的關系更弱。該文提出的基于融合組間數據自表示的計算方法,通過融合各特征分組的數據自表示矩陣,加入組間特征信息,構建全局矩陣,為后續(xù)離群點檢測提供了良好的基礎。

3.2 基于融合數據自表示的離群點檢測算法

該文提出基于融合數據自表示的離群點檢測算法,通過在構造的加權有向圖上隨機游走來篩選離群點。該加權有向圖(S)由全局數據自表示矩陣(RT)構造得出,S中有向邊為RT中數據點間的相互指向,邊權值表示數據點之間的相關性,同時也表示兩點之間的轉移概率。S的邊權值可由公式(7)得出:

(7)

其中,pxy表示數據點x到數據點y的轉移概率,wxy表示圖S上數據點x與數據點y之間的邊權值,與pxy值相同。rxy表示RT中第x行第y列的值。

阻尼因子(η)在文獻[14]中被用于馬爾可夫轉移概率的計算。公式(8)描述了S上不同時間的狀態(tài)轉移分布,隨機選取初始點。

(8)

其中,S(t)表示t時刻的狀態(tài)轉移分布,P表示轉移概率矩陣,O表示1*n的矩陣,n表示數據點個數。

基于穩(wěn)定后的狀態(tài)轉移分布,通過公式(9)得出每個數據點的異常因子(od),其用于描述數據點的離群程度。正常點被轉移到的概率較高,而離群點被轉移到的概率較低,取異常因子最小的h個點作為最終的全局離群點。

(9)

綜上所述,基于融合數據自表示的離群點檢測算法基本思想為:首先在FG算法的特征分組結果基礎上,使用公式(1)構建每個分組和組中心特征集對應的數據自表示矩陣;然后,使用基于融合組間數據自表示的計算方法得出全局自表示;最后,在加權有向圖上使用馬爾可夫隨機游走檢測離群點。其算法描述如下:

算法1:MDSR(An outlier detection algorithm based on mergence data self-representation)

輸入:FG算法得出的特征分組:G={FG1,FG2,…,FGm},組中心特征集為FC={FC1,FC2,…,FCm}

輸出:異常因子(od)

1.根據公式(1),得出G中每個特征分組和FC對應的數據自表示矩陣(R)

2.根據公式(6),構建全局數據自表示矩陣(RT)

3.根據公式(7),使用RT計算出狀態(tài)轉移矩陣(P)

4.η?0.1,S(0)?{1/n,1/n,…,1/n}

5.根據公式(8),得出穩(wěn)定的狀態(tài)轉移分布(S(t))

6.根據公式(9),計算出每個數據點的異常因子(od),并取其值最小的h個點作為最終的全局離群點。

4 實驗分析

4.1 實驗設置及環(huán)境

為了驗證MDSR算法的有效性,在人工數據集和真實數據集上共同實驗,使用LOF[17],SOD[18],ROD[19],COPOD[20]和R-GRAPH[6]作為對比算法,采用ROC曲線下面積(AUC)和運行時間作為評價指標。真實數據集包含3個UCI Machine Learning Repository(UCI)數據集和6個Outlier Detection DataSets(ODDS)數據集,詳見表1。

表1 真實數據集

人工數據集來源于文獻[21],使用文獻[8]中對人工數據集的處理方法,得到本實驗中的28個數據集,分別為:18個數據規(guī)模一定的數據集,其中特征數量包含20,30,40,50,75和100,每個特征數量中包含3個不同的數據集;與10個特征數量一定的數據集,其中特征數為20,數據量從1 000到10 000,詳見表2。該文基于Matlab平臺,AMD Ryzen 7 4800H 2.90 GHz CPU和RTX 2060 GPU實現了MDSR算法。

表2 人工數據集

4.2 人工數據集實驗結果分析

6種算法在6個不同維度人工數據集上的AUC如圖1所示,具體AUC數值如表3所示,取每維度中的3個數據集上最大的AUC作為實驗結果。依據參考文獻[8,22],LOF和SOD算法中參數n_neighbors的值取5時其算法模型達到最優(yōu)。

圖1 人工數據集上的AUC對比

表3 人工數據集上的AUC數值

從圖1和表3可見,對于所有維度的人工數據集,MDSR算法的AUC值明顯比LOF,SOD,ROD和COPOD算法的高,較好地完成了離群點檢測任務。

LOF和ROD算法性能隨著數據維度的增加而大幅下降,造成這種現象的原因是,即使ROD算法提出了基于全維3D子空間的方法,它們仍然都在全局數據中直接檢測離群值,當處理高維數據時,對于LOF和ROD算法將更難檢測離群值。COPOD算法AUC值則在小范圍內浮動,是因為它更多受到數據分布的影響,而非特征的數量。SOD算法構造的子空間中包含冗余特征,數據特征越多,冗余程度越大,導致SOD同樣難以有效處理高維數據。提出的MDSR算法的AUC值比R-GRAPH的略高,是因為MDSR不僅考慮了特征冗余問題還將特征間復雜的關聯性融于數據自表示的過程中,而R-GRAPH在其數據自表示過程中并未關注這些問題。因此MDSR算法性能不會隨著特征數的增加而顯著降低,從而保證其面對高維數據的離群點檢測任務時,仍可以得到較準確的檢測結果。

離群點檢測算法的運行時間是衡量其檢測效率的一個重要評價指標。各算法在人工數據集上的運行時間對比如表4所示。

表4 不同特征數量人工數據集上的運行時間對比 s

從表4可見,MDSR算法在前3個數據集上的運行時間比SOD算法的少,在全部數據集上的運行時間比ROD算法的少。對于SOD算法,選擇相關子空間的過程占用了運行時間。對于ROD算法,構建全局三維子空間的過程有較大的時間開銷。由于COPOD算法是基于連接的,在數據集規(guī)模為1 000的前提下,其運行時間浮動較小。提出的MDSR算法深入挖掘特征關系,隨著數據特征的增加,這種復雜關系更加難以計算,導致該方法在運行時間上略有增加。為分析數據規(guī)模對MDSR算法運行時間的影響,在數據集D20_1,D20_2,…,D20_10上進一步對比,結果如表5所示。

表5 不同數據量人工數據集上的運行時間對比 s

從表5可見,實驗中所有算法的運行時間都隨數據量增加而線性增加,但MDSR算法的運行時間仍保持在較低值,且遠小于SOD和ROD算法的運行時間,更直觀的對比如圖2所示。

圖2 不同數據規(guī)模下SOD,ROD和MDSR算法運行時間對比

由于MDSR算法考慮了特征間關聯性,使其運行時間比COPOD和R-GRAPH算法的較長。但是結合表3中AUC數值和表4、表5中運行時間可以得出,該文提出的算法運行時間雖不是最短,但仍取得了最好的檢測結果,同時結合數據量大小和數據維度對MDSR算法性能的影響,表明該算法適合用于高維離群點檢測任務且總體優(yōu)于對比算法。

4.3 真實數據集實驗結果分析

為進一步驗證MDSR算法的有效性,將其與LOF,SOD,ROD,COPOD和R-GRAPH在9個真實數據集上進行了對比實驗,且設置了3種離群點占比,分別為2%,5%和10%。由于Pendigits,Optdigits,Musk和Speech數據集中離群點占比不足5%,故只以2%的離群值作為實驗設置。3種離群點占比下不同算法在真實數據集上的AUC對比如表6所示。

表6 真實數據集上的AUC對比

從表6可見,MDSR算法具有較好的檢測結果。結合表1,MDSR算法無論在較低維數據集Breast Cancer和Ionosphere上,還是在較高維數據集Musk,Arrhythmia和Speech上,AUC值都明顯比LOF,SOD和ROD算法的高。由于LOF算法原理較為直接和單一,導致其在高維數據集上無法保證檢測效果。MDSR算法考慮了特征間關系和數據信息的融合,優(yōu)于僅研究特征信息的SOD算法,使得MDSR算法的檢測結果更突出。對于ROD算法,從表6可見其AUC值大于0.7,只出現在低維數據集Breast-Cancer(Diagnostic)和Ionosphere上。由于ROD在檢測過程中旋轉其構建的3D子空間,此過程需要占用的內存隨數據維度增加而變大,而本設備不足以支撐ROD算法檢測高維數據集Arrhythmia和Speech。MDSR算法的AUC值相比R-GRAPH的略優(yōu),原因是R-GRAPH只通過研究數據間相互表示關系檢測離群點,存在一定的局限性。對于基于數據連接的離群點檢測算法(COPOD),當數據量小于1 000時,它的檢測AUC可以達到0.9以上,但數據量一旦超過3 000,其檢測AUC下降幅度超過了0.3。

結合以上分析可以得出,MDSR算法更加全面和深入地挖掘了數據和特征信息,具有較好的穩(wěn)定性和泛化性。

各算法在真實數據集上的運行時間對比如表7所示。

表7 真實數據集上的運行時間對比 s

從表7可見,MDSR算法的運行時間在所有數據集上少于SOD和ROD算法的運行時間,而只在較低維數據集上少于LOF算法的運行時間。SOD算法將時間消耗在尋找子空間上,ROD算法則在構造三維子空間和旋轉檢測上花費較多時間,導致其運行時間隨著數據特征的增多大幅上升。雖然COPOD算法運行時間較短,但該算法并不能保證離群點檢測效果。MDSR算法需要較多的時間用于計算特征間關聯性,但為了能在高維數據中更有效地挖掘出離群點,可以忽略這部分時間開銷。

5 結束語

通過均衡地度量特征與數據關聯,該文提出一種基于融合數據自表示的離群點檢測算法,充分挖掘并體現了數據特征間和數據間的復雜關系,有效改善了高維離群點檢測性能,適用于高維數據的離群點檢測任務。算法度量特征間相關性的過程較為費時,下一步主要研究工作是采取一些方法來優(yōu)化該過程,已在保證檢測有效性的基礎上降低其時間消耗。