基于融合數(shù)據(jù)自表示的離群點(diǎn)檢測(cè)算法

高亞星,趙旭俊,曹栩陽(yáng)

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,山西 太原 030024)

0 引 言

離群數(shù)據(jù)是指與其他數(shù)據(jù)分布有顯著不同的數(shù)據(jù)對(duì)象[1]。離群點(diǎn)檢測(cè)是通過(guò)分析離群數(shù)據(jù)的特征,從海量數(shù)據(jù)中挖掘異常信息和提取興趣模式的一種方法,已廣泛地應(yīng)用在欺詐檢測(cè)[2]、入侵檢測(cè)[3]、疾病檢測(cè)[4]、時(shí)間序列離群值檢測(cè)[5]等領(lǐng)域。

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

基于數(shù)據(jù)自表示的離群點(diǎn)檢測(cè)方法通過(guò)研究低維數(shù)據(jù)間的關(guān)聯(lián)性與稀疏性,并構(gòu)建表示關(guān)系,在低維全局離群點(diǎn)檢測(cè)上獲得了較好的效果。但該方法在處理高維數(shù)據(jù)時(shí)存在以下兩點(diǎn)問(wèn)題:第一,高維數(shù)據(jù)相較于低維數(shù)據(jù)會(huì)更加離散,使得該方法更難得出較為準(zhǔn)確的數(shù)據(jù)表示,從而影響高維離群點(diǎn)檢測(cè)的效果;第二,該方法并未考慮特征間的關(guān)聯(lián)性對(duì)數(shù)據(jù)相互表示過(guò)程的影響,在處理低維數(shù)據(jù)時(shí),這種局限性對(duì)檢測(cè)結(jié)果影響并不大,然而高維數(shù)據(jù)中特征間的復(fù)雜關(guān)系不容忽視,這些特征關(guān)系對(duì)離群點(diǎn)的檢測(cè)有較大影響,該方法的局限性被進(jìn)一步放大。

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

1 相關(guān)工作

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

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

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

綜上所述,基于特征分組的離群點(diǎn)檢測(cè)方法雖降低了檢測(cè)維度,但在全局離群點(diǎn)的檢測(cè)中會(huì)丟失特征分組之間的相關(guān)性信息,影響了離群點(diǎn)檢測(cè)性能;基于數(shù)據(jù)自表示的離群點(diǎn)檢測(cè)方法在保證檢測(cè)結(jié)果準(zhǔn)確性的同時(shí),有效地降低了時(shí)間復(fù)雜度,但現(xiàn)有的數(shù)據(jù)自表示方法同樣丟失高維特征包含的有效信息,離群點(diǎn)檢測(cè)未能更全面和深入,從而影響最終的檢測(cè)效果。

2 基于特征關(guān)系的數(shù)據(jù)自表示方法

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

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

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

(1)

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

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

(2)

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

(3)

(4)

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

由于具有強(qiáng)相關(guān)性的特征會(huì)被劃分至同一分組,出現(xiàn)特征冗余現(xiàn)象,一定程度上浪費(fèi)了計(jì)算資源。ω用于度量分組內(nèi)特征間的冗余程度,提升了數(shù)據(jù)自表示結(jié)果的有效性。ω可由如下公式得出:

(5)

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

3 融合組間數(shù)據(jù)自表示與離群點(diǎn)檢測(cè)

根據(jù)上一節(jié)的方法,每個(gè)特征分組生成了對(duì)應(yīng)的數(shù)據(jù)自表示矩陣,其中包含各分組的特征和數(shù)據(jù)分布信息,這種信息是局部的。由于不存在某個(gè)特征同時(shí)屬于兩個(gè)或更多分組的情況,導(dǎo)致數(shù)據(jù)自表示矩陣也是唯一對(duì)應(yīng)的,使得原始數(shù)據(jù)被簡(jiǎn)化,造成不同矩陣中包含的離群數(shù)據(jù)信息存在差異。若直接在其基礎(chǔ)上檢測(cè)離群點(diǎn)所得到的結(jié)果不足以涵蓋全局信息,又因?yàn)椴煌卣鞣纸M間仍然存在關(guān)聯(lián)性,這些信息對(duì)于準(zhǔn)確地挖掘全局離群點(diǎn)有幫助,進(jìn)一步研究融合組間關(guān)聯(lián)性將提升檢測(cè)結(jié)果有效性。

3.1 基于融合組間數(shù)據(jù)自表示的計(jì)算方法

通過(guò)融合特征組間關(guān)聯(lián)性構(gòu)建的全局?jǐn)?shù)據(jù)自表示矩陣(RT)可由如下公式得出:

(6)

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

3.2 基于融合數(shù)據(jù)自表示的離群點(diǎn)檢測(cè)算法

該文提出基于融合數(shù)據(jù)自表示的離群點(diǎn)檢測(cè)算法,通過(guò)在構(gòu)造的加權(quán)有向圖上隨機(jī)游走來(lái)篩選離群點(diǎn)。該加權(quán)有向圖(S)由全局?jǐn)?shù)據(jù)自表示矩陣(RT)構(gòu)造得出,S中有向邊為RT中數(shù)據(jù)點(diǎn)間的相互指向,邊權(quán)值表示數(shù)據(jù)點(diǎn)之間的相關(guān)性,同時(shí)也表示兩點(diǎn)之間的轉(zhuǎn)移概率。S的邊權(quán)值可由公式(7)得出:

(7)

其中,pxy表示數(shù)據(jù)點(diǎn)x到數(shù)據(jù)點(diǎn)y的轉(zhuǎn)移概率,wxy表示圖S上數(shù)據(jù)點(diǎn)x與數(shù)據(jù)點(diǎn)y之間的邊權(quán)值,與pxy值相同。rxy表示RT中第x行第y列的值。

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

(8)

其中,S(t)表示t時(shí)刻的狀態(tài)轉(zhuǎn)移分布,P表示轉(zhuǎn)移概率矩陣,O表示1*n的矩陣,n表示數(shù)據(jù)點(diǎn)個(gè)數(shù)。

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

(9)

綜上所述,基于融合數(shù)據(jù)自表示的離群點(diǎn)檢測(cè)算法基本思想為:首先在FG算法的特征分組結(jié)果基礎(chǔ)上,使用公式(1)構(gòu)建每個(gè)分組和組中心特征集對(duì)應(yīng)的數(shù)據(jù)自表示矩陣;然后,使用基于融合組間數(shù)據(jù)自表示的計(jì)算方法得出全局自表示;最后,在加權(quán)有向圖上使用馬爾可夫隨機(jī)游走檢測(cè)離群點(diǎn)。其算法描述如下:

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

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

輸出:異常因子(od)

1.根據(jù)公式(1),得出G中每個(gè)特征分組和FC對(duì)應(yīng)的數(shù)據(jù)自表示矩陣(R)

2.根據(jù)公式(6),構(gòu)建全局?jǐn)?shù)據(jù)自表示矩陣(RT)

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

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

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

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

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

4.1 實(shí)驗(yàn)設(shè)置及環(huán)境

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

表1 真實(shí)數(shù)據(jù)集

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

表2 人工數(shù)據(jù)集

4.2 人工數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

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

圖1 人工數(shù)據(jù)集上的AUC對(duì)比

表3 人工數(shù)據(jù)集上的AUC數(shù)值

從圖1和表3可見(jiàn),對(duì)于所有維度的人工數(shù)據(jù)集,MDSR算法的AUC值明顯比LOF,SOD,ROD和COPOD算法的高,較好地完成了離群點(diǎn)檢測(cè)任務(wù)。

LOF和ROD算法性能隨著數(shù)據(jù)維度的增加而大幅下降,造成這種現(xiàn)象的原因是,即使ROD算法提出了基于全維3D子空間的方法,它們?nèi)匀欢荚谌謹(jǐn)?shù)據(jù)中直接檢測(cè)離群值,當(dāng)處理高維數(shù)據(jù)時(shí),對(duì)于LOF和ROD算法將更難檢測(cè)離群值。COPOD算法AUC值則在小范圍內(nèi)浮動(dòng),是因?yàn)樗嗍艿綌?shù)據(jù)分布的影響,而非特征的數(shù)量。SOD算法構(gòu)造的子空間中包含冗余特征,數(shù)據(jù)特征越多,冗余程度越大,導(dǎo)致SOD同樣難以有效處理高維數(shù)據(jù)。提出的MDSR算法的AUC值比R-GRAPH的略高,是因?yàn)镸DSR不僅考慮了特征冗余問(wèn)題還將特征間復(fù)雜的關(guān)聯(lián)性融于數(shù)據(jù)自表示的過(guò)程中,而R-GRAPH在其數(shù)據(jù)自表示過(guò)程中并未關(guān)注這些問(wèn)題。因此MDSR算法性能不會(huì)隨著特征數(shù)的增加而顯著降低,從而保證其面對(duì)高維數(shù)據(jù)的離群點(diǎn)檢測(cè)任務(wù)時(shí),仍可以得到較準(zhǔn)確的檢測(cè)結(jié)果。

離群點(diǎn)檢測(cè)算法的運(yùn)行時(shí)間是衡量其檢測(cè)效率的一個(gè)重要評(píng)價(jià)指標(biāo)。各算法在人工數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比如表4所示。

表4 不同特征數(shù)量人工數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比 s

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

表5 不同數(shù)據(jù)量人工數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比 s

從表5可見(jiàn),實(shí)驗(yàn)中所有算法的運(yùn)行時(shí)間都隨數(shù)據(jù)量增加而線性增加,但MDSR算法的運(yùn)行時(shí)間仍保持在較低值,且遠(yuǎn)小于SOD和ROD算法的運(yùn)行時(shí)間,更直觀的對(duì)比如圖2所示。

圖2 不同數(shù)據(jù)規(guī)模下SOD,ROD和MDSR算法運(yùn)行時(shí)間對(duì)比

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

4.3 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

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

表6 真實(shí)數(shù)據(jù)集上的AUC對(duì)比

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

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

各算法在真實(shí)數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比如表7所示。

表7 真實(shí)數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比 s

從表7可見(jiàn),MDSR算法的運(yùn)行時(shí)間在所有數(shù)據(jù)集上少于SOD和ROD算法的運(yùn)行時(shí)間,而只在較低維數(shù)據(jù)集上少于LOF算法的運(yùn)行時(shí)間。SOD算法將時(shí)間消耗在尋找子空間上,ROD算法則在構(gòu)造三維子空間和旋轉(zhuǎn)檢測(cè)上花費(fèi)較多時(shí)間,導(dǎo)致其運(yùn)行時(shí)間隨著數(shù)據(jù)特征的增多大幅上升。雖然COPOD算法運(yùn)行時(shí)間較短,但該算法并不能保證離群點(diǎn)檢測(cè)效果。MDSR算法需要較多的時(shí)間用于計(jì)算特征間關(guān)聯(lián)性,但為了能在高維數(shù)據(jù)中更有效地挖掘出離群點(diǎn),可以忽略這部分時(shí)間開(kāi)銷。

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

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