基于屬性組權(quán)重的分類數(shù)據(jù)離群檢測

張凱棋,宋亦靜,陳 鑫

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

0 引 言

離群數(shù)據(jù)(outlier)是指明顯偏離其他數(shù)據(jù)對象,可能是由于一種不同于其他數(shù)據(jù)對象的機(jī)理而產(chǎn)生的數(shù)據(jù)對象[1]。由于離群數(shù)據(jù)蘊(yùn)含著大量豐富的、有價值的潛在的信息,已廣泛地應(yīng)用在無線傳感器網(wǎng)絡(luò)[2]、腫瘤檢測[3]、入侵檢測[4]、欺詐檢測[5]、網(wǎng)絡(luò)安全[6]、數(shù)據(jù)清理[7]、工業(yè)系統(tǒng)[8]、地球科學(xué)[9]等領(lǐng)域。針對高維數(shù)據(jù),由于出現(xiàn)了“維度災(zāi)難”,嚴(yán)重影響了離群檢測效果。屬性分組是指根據(jù)屬性之間的相關(guān)性實(shí)現(xiàn)屬性分組,并降低了離群檢測維度,可有效地緩解“維度災(zāi)難”干擾。

屬性分組離群數(shù)據(jù)檢測作為一類高維離群檢測方法,將依據(jù)屬性之間的關(guān)聯(lián)關(guān)系,將屬性劃分為若干子集,并利用各屬性子集,識別或度量離群數(shù)據(jù)對象,從而可挖掘出全局和局部離群數(shù)據(jù)[10-12]。但現(xiàn)有的屬性分組離群檢測未能體現(xiàn)屬性組之間的差異性與屬性組的偏離程度,影響了高維離群檢測效果。該文利用信息熵累加和刻畫屬性組權(quán)重,提出了一種基于屬性組權(quán)重的分類離群數(shù)據(jù)檢測方法,有效地體現(xiàn)了屬性組之間的差異性,進(jìn)一步改善了高維離群檢測效果,并緩解了“維度災(zāi)難”干擾。其主要貢獻(xiàn):

·依據(jù)數(shù)據(jù)模式頻率和編碼長度,定義了屬性組偏離因子及計算公式;

·提出了一種基于信息熵的屬性組權(quán)重計算方法;

·提出了一種基于屬性組權(quán)重的分類離群數(shù)據(jù)檢測算法。

1 相關(guān)工作

分類數(shù)據(jù)作為一類廣泛出現(xiàn)在多種應(yīng)用領(lǐng)域中的重要數(shù)據(jù)類型,具有取值無序與不可比等特點(diǎn)。目前,分類數(shù)據(jù)離群檢測主要包括:基于距離的方法[13-15]、基于密度的方法[16-17]、基于統(tǒng)計的方法[18-19]、基于聚類的方法[20-22]、基于頻繁項集的方法[10-11,23]、基于子空間的方法[24-26]等。針對高維分類數(shù)據(jù),由于“維度災(zāi)難”,嚴(yán)重影響了分類數(shù)據(jù)離群檢測性能;而子空間方法是將數(shù)據(jù)對象從高維空間投影到低維空間,可有效緩解“維度災(zāi)難”干擾,是高維分類離群檢測的有效途徑之一。

基于子空間的離群檢測是將數(shù)據(jù)對象從高維空間投影到低維子空間,并在低維子空間中,度量與檢測離群數(shù)據(jù)對象,主要包括相關(guān)子空間和稀疏子空間兩類子空間方法。其典型研究成果:文獻(xiàn)[27]采用遺傳算法搜索稀疏子空間,但該算法受初始種群影響,離群挖掘結(jié)果的完備性和準(zhǔn)確性等無法得到保證;文獻(xiàn)[28]采用概念格作為子空間的描述工具,通過引入稠密度系數(shù),在概念格內(nèi)涵中確定稀疏子空間;文獻(xiàn)[29]在概念格的基礎(chǔ)上提出了約束概念格的方法,提高了概念格的構(gòu)造效率,進(jìn)一步提高了挖掘的效率;文獻(xiàn)[30]提出了一種基于稀疏子空間并行搜索技術(shù)的類星體光譜異常數(shù)據(jù)并行檢測算法,實(shí)現(xiàn)了對天體光譜中異常光譜的挖掘。稀疏子空間的方法的稀疏系數(shù)閾值需要人為設(shè)置,無法保證稀疏子空間劃分的準(zhǔn)確性;文獻(xiàn)[31]利用局部稀疏差異因子得到相關(guān)子空間,解決了檢測相關(guān)子空間時間復(fù)雜度較高的問題,但是維度的數(shù)據(jù)分布會使得到的相關(guān)子空間產(chǎn)生一定的誤差;文獻(xiàn)[24]提出一種軸平行子空間離群挖掘方法,該方法通過共享最近鄰居,為數(shù)據(jù)對象尋找似子集以確定子空間,但該方法采用的歐氏距離的維平均方法度量離群具有明顯不足;文獻(xiàn)[32]提出一種在相關(guān)子空間進(jìn)行離群檢測的算法,算法使用KNN方法確定數(shù)據(jù)對象的局部數(shù)據(jù)集,然后生成稀疏因子矩陣和局部稀疏因子矩陣,再確定數(shù)據(jù)對象對應(yīng)的子空間定義向量,計算數(shù)據(jù)對象的離群程度,但該方法的局部稀疏差異因子閾值的選取會影響子空間定義向量的確定和挖掘的精度。相關(guān)子空間的方法不能有效地在高維數(shù)據(jù)集中挖掘離群數(shù)據(jù),因此離群挖掘的效率和準(zhǔn)確性無法保證。

作為一種子空間離群檢測,屬性分組是將高維屬性劃分為若干不同屬性組,將相關(guān)性強(qiáng)的屬性劃分在同一個組中,相關(guān)性弱的屬性劃分在不同組中。其典型工作有:文獻(xiàn)[10]提出了一種利用特征分組的加權(quán)離群檢測的方法,該算法利用特征關(guān)系的概念對特征(即屬性)進(jìn)行分組,可以實(shí)現(xiàn)對分類數(shù)據(jù)中的全局和局部離群數(shù)據(jù)的挖掘,但是該算法組間離群數(shù)據(jù)的合并缺乏合理的解釋性;文獻(xiàn)[11]提出了一種基于壓縮數(shù)據(jù)的離群檢測算法,該算法根據(jù)最小描述長度定律最小化壓縮長度實(shí)現(xiàn)屬性的分組,但是由于建立代碼表的開銷過大,所以該算法的時間復(fù)雜度較高;文獻(xiàn)[12]采用基于二叉搜索樹的隔離算法實(shí)現(xiàn)屬性分組,在屬性組內(nèi)實(shí)現(xiàn)數(shù)據(jù)對象的聚類過程,以實(shí)現(xiàn)對離群數(shù)據(jù)的挖掘。屬性分組的方法對于分組組數(shù)的選取和分組時屬性分配存在一定的難度,同時,對于全局離群數(shù)據(jù)的挖掘的組間合并缺乏合理的解釋性。

綜上所述,子空間離群檢測可以有效地發(fā)現(xiàn)隱藏在子空間中的局部離群數(shù)據(jù),但會丟失部分有用信息,影響了離群檢測性能;屬性分組離群檢測將高維屬性分為不同的屬性組,有效地利用了全部離群信息,但現(xiàn)在的屬性分組存在著組數(shù)選取敏感,離群檢測未能有效體現(xiàn)屬性組間的差異性等,從而影響離群檢測效果。

2 屬性分組與離群檢測

在高維離群檢測中,屬性分組是緩解“維度災(zāi)難”的有效途徑之一。所謂屬性分組是依據(jù)屬性之間的關(guān)聯(lián)程度,將相關(guān)性強(qiáng)的屬性劃分在同一個組中,相關(guān)性弱的屬性劃分在不同組中。參照文獻(xiàn)[10-11],相關(guān)概念描述如下:

信息增益描述了隨機(jī)變量的概率分布的差異性,屬性分組通過標(biāo)準(zhǔn)化信息增益(Normal Information Gain,NIG)來描述屬性組間概率分布的差異性,可以有效地刻畫屬性組之間的相關(guān)性。對于任意2個屬性組(Fu和Fv),其標(biāo)準(zhǔn)化信息增益的計算公式如下:

(1)

其中,H(Fu),H(Fv)分別為第u屬性組的信息熵、第v屬性組的信息熵,H(Fu,Fv)為Fu和Fv之間的互信息,|Fu|和|Fv|分別表示第u屬性組和第v屬性組的屬性個數(shù)。

在公式(1)中,NIG(Fu,Fv)刻畫了Fu和Fv之間的相關(guān)程度,其值越大,表明兩組的相關(guān)性越強(qiáng),合并為同一組的概率就越大,反之亦然。

數(shù)據(jù)模式是指數(shù)據(jù)對象(xi)在屬性組(Fj)中,屬性的一個取值項集。在Fj中,xi由若干個互不相同的數(shù)據(jù)模式組成。代碼表是為描述屬性組中的數(shù)據(jù)模式和數(shù)據(jù)模式編碼構(gòu)建的一種模型結(jié)構(gòu)。數(shù)據(jù)模式編碼體現(xiàn)了數(shù)據(jù)模式在代碼表中數(shù)據(jù)模式頻率分布的差異性。在Fj中,設(shè)p為xi的任一數(shù)據(jù)模式,CT為描述數(shù)據(jù)模式和數(shù)據(jù)模式編碼的代碼表,則p的數(shù)據(jù)模式編碼定義如下:

(2)

在公式(2)中,L(code(p)|CT)刻畫了數(shù)據(jù)模式在CT下的頻率分布,其值越大,表明該數(shù)據(jù)模式在代碼表中出現(xiàn)的頻率越大,反之亦然。

數(shù)據(jù)編碼是數(shù)據(jù)集(D)中所有數(shù)據(jù)對象(xi)在CT中所有數(shù)據(jù)模式編碼的總和,數(shù)據(jù)編碼有效地刻畫了D在Fj中的壓縮效果,是評估CT模型質(zhì)量的依據(jù)。設(shè)CT為代碼表,A為xi在Fj中所有數(shù)據(jù)模式的集合,則利用公式(2),D的數(shù)據(jù)編碼描述如下:

(3)

在公式(3)中,L(D|CT)刻畫了數(shù)據(jù)集(D)在CT模型中的壓縮效果,其值越大,表明壓縮效果越差,無法適用于D,反之亦然。

為了有效地度量構(gòu)建代碼表模型(CT)的代價,利用公式(2),CT的代價定義如下:

(4)

在公式(4)中,L(CT)反映了構(gòu)建代碼表的代價,其值越大,表明構(gòu)建該代碼表所需的編碼長度越長,代價成本就越高,反之亦然。

為了刻畫屬性分組(P)的壓縮效果與體現(xiàn)屬性分組的分組效果,利用P中的各個屬性組對應(yīng)的數(shù)據(jù)編碼和代碼表代價總和作為其度量依據(jù)。利用公式(3)和(4),在D中,CT和P的壓縮消耗函數(shù)定義如下:

(5)

其中,L(P)表示描述分組情況所需要的編碼長度。

在公式(5)中,L(P,CT,D)有效地刻畫了屬性分組的質(zhì)量,其值越大,表明總的壓縮效果越差,表明屬性分組的效果越差,反之亦然。

依據(jù)上述定義,屬性分組的基本步驟如下:

(1)將每個屬性視為單獨(dú)的一組,根據(jù)公式(2),計算數(shù)據(jù)模式編碼,構(gòu)建對應(yīng)的代碼表;

(2)根據(jù)公式(1)計算兩兩屬性組的NIG,按照NIG降序的方式對屬性組排序;

(3)根據(jù)公式(3)～(5)計算壓縮消耗函數(shù),根據(jù)壓縮消耗函數(shù)的大小實(shí)現(xiàn)組間合并,更新屬性組及代碼表,若屬性組全部遍歷后,壓縮消耗函數(shù)值仍未減小,分組結(jié)束,否則返回步驟2,繼續(xù)組間合并。

在上述屬性分組的基礎(chǔ)上,為了度量數(shù)據(jù)對象在其數(shù)據(jù)集中的離群程度,利用公式(2)、公式(3),xi的離群得分計算公式定義如下:

(6)

在公式(6)中,score(xi)刻畫了xi的離群程度,其值越大,表明數(shù)據(jù)對象的偏離程度越大,成為離群數(shù)據(jù)的概率越大,反之亦然。

3 屬性組權(quán)重與分類離群檢測

在上一章節(jié)的屬性分組步驟中,NIG作為一種搜索策略,是屬性組之間合并順序依據(jù)。由公式(1)可知,計算NIG的值與初始屬性分組(P)中的屬性組個數(shù)(d)有關(guān),即:需要計算d個屬性組中的任意兩組間NIG;依據(jù)公式(5)定義的壓縮消耗函數(shù),屬性組迭代合并更新后,還需要重新計算屬性組之間的NIG。因此,屬性分組中的搜索策略效率低下。

在屬性分組中,數(shù)據(jù)模式出現(xiàn)的頻率體現(xiàn)了屬性取值項集疏密程度,數(shù)據(jù)模式編碼長度體現(xiàn)了數(shù)據(jù)模式頻率分布。數(shù)據(jù)模式編碼長度體現(xiàn)了屬性組的不確定性,可以有效地衡量屬性組的偏離程度。對于任意屬性組(Fj),設(shè)CT為Fj對應(yīng)的代碼表,Fj的偏離因子定義如下:

GDF(CT)=log(1/p(r))-log(1/p(t))

(7)

其中,r,t分別為CT中的頻次最小、頻次最大數(shù)據(jù)模式,p(r),p(t)分別表示r,t數(shù)據(jù)模式在CT中出現(xiàn)的頻率。

在公式(7)中,log(1/p(r))和log(1/p(t))分別刻畫了r,t所含的信息量,數(shù)據(jù)模式出現(xiàn)的頻次越小,包含的離群信息量越大,反之亦然。r是屬性組(Fj)中含離群信息量最大的數(shù)據(jù)模式,而t是屬性組(Fj)中含離群信息量最小的數(shù)據(jù)模式,因此,GDF(CT)刻畫了Fj的偏離程度。在屬性分組中,采用偏離因子(GDF)作為屬性組之間合并順序依據(jù),只需要利用代碼表中已有的數(shù)據(jù)模式編碼,計算d個屬性組的GDF。相較NIG而言,避免了NIG中任意兩組間的互信息計算,因此有效地提高了搜索策略的效率。

在公式(6)中,離群得分計算僅體現(xiàn)了屬性組(Fj)的數(shù)據(jù)模式編碼長度,忽略了屬性組之間所包含的離群信息量差異,影響離群檢測效果。信息熵是根據(jù)系統(tǒng)內(nèi)的分布差異,衡量系統(tǒng)所含信息量,信息熵越大表明該系統(tǒng)的不確定性或混亂程度越大[33]。因此,利用信息熵度量屬性組,可以體現(xiàn)屬性組內(nèi)包含的離群信息量,信息熵越大表明所包含的離群信息越多,即:離群檢測的重要程度也就越大,從而體現(xiàn)了屬性組之間的差異性。設(shè)Fj={fk|1≤k≤h}為任意屬性組,則Fj的權(quán)重定義如下:

(8)

其中,fk為Fj中的第k個屬性,h為Fj中的屬性個數(shù),H(fk)表示第j屬性組第k屬性的信息熵。

在公式(8)中,屬性組權(quán)重有效地度量了屬性組的混亂程度,體現(xiàn)了屬性組所包含的離群信息量,其值越大,所包含的離群信息量越大,反之亦然。屬性組權(quán)重刻畫了不同屬性組對度量離群數(shù)據(jù)對象的重要程度,充分體現(xiàn)出屬性組間的差異性。

由公式(7)和(8)可知,屬性組偏離因子(GDF)利用數(shù)據(jù)模式編碼頻率分布,有效地刻畫了屬性組對度量離群數(shù)據(jù)的重要程度,改善了搜索策略的效率;屬性組權(quán)重利用信息熵度量了屬性組包含的離群信息重要程度,有效地刻畫了屬性組之間的差異。為了有效地度量數(shù)據(jù)對象(xi)在其數(shù)據(jù)集(D)中的離群程度,參照公式(6)、公式(8),xi的離群得分重新定義如下:

(9)

在公式(9)中,離群得分值刻畫了xi的離群程度,其值越大,表明數(shù)據(jù)對象的偏離程度越大,成為離群數(shù)據(jù)的概率越大,反之亦然。由于該離群得分體現(xiàn)了屬性組權(quán)重和數(shù)據(jù)模式編碼長度,因而有效地刻畫了屬性組內(nèi)和屬性組間數(shù)據(jù)對象所包含的離群信息。

4 基于屬性組權(quán)重的分類離群檢測算法

依據(jù)上一章節(jié)描述,采用屬性組權(quán)重,分類離群檢測基本步驟描述如下:

(1)將每個屬性視為單獨(dú)的一組,根據(jù)公式(2),計算數(shù)據(jù)模式編碼,構(gòu)建對應(yīng)代碼表;

(2)根據(jù)公式(7)計算屬性組偏離因子(GDF),按照GDF降序的方式對屬性組排序;

(3)根據(jù)公式(3)～(5)計算壓縮消耗函數(shù),根據(jù)壓縮消耗函數(shù)的大小實(shí)現(xiàn)組間合并,更新屬性組及代碼表,若屬性組全部遍歷后,壓縮消耗函數(shù)值仍未減小,分組結(jié)束,否則返回步驟2,繼續(xù)組間合并;

(4)根據(jù)公式(8)計算屬性組權(quán)重,根據(jù)公式(9)計算數(shù)據(jù)對象的離群得分,從中選取離群得分最高的k個對象作為離群數(shù)據(jù)。

算法偽代碼如下:

算法:AGWODC(Attribute Group Weight Outlier Detection for Categorical data)

輸入:數(shù)據(jù)集(D)(n個數(shù)據(jù)對象×d個屬性)

輸出:k個離群數(shù)據(jù)對象

1.初始化分組:P={Fj|1≤j≤d},Fj={fj}, 1≤j≤d

2.根據(jù)公式(2)構(gòu)建代碼表:CT={CTj|1≤j≤d}

3.根據(jù)公式(7)計算每個組的偏離因子(GDF),構(gòu)成集合(OD)

4.ForFuinP:

5. forFvinP:

6.降序排序OD

7.根據(jù)公式(5),計算最小消耗函數(shù)L(P,CT,OD)

cost=L(P,CT,OD)

8.根據(jù)公式(2)計算數(shù)據(jù)模式的編碼長度,構(gòu)建新的代碼表(CTu|v)

9.P=P(Fu∪Fv)∪Fu|v

10.CT'=CT(CTu∪CTv)∪CTu|v

11. ifL(P',CT',OD)

12.P=P',CT=CT'

13. 根據(jù)公式(7)計算CT'的CDF,更新OD

14.返回步驟(4)

15. endif;

16. endfor;

17.Endfor;

18.For eachjinP:

19.根據(jù)公式(8)計算組權(quán)重ω(Fj)

20.For eachi∈(1,2,…,n) inD:

21.根據(jù)公式(9)計算數(shù)據(jù)對象的離群分?jǐn)?shù)

22.Endfor;

23.選擇離群分?jǐn)?shù)最高的k個離群數(shù)據(jù)對象

24.End AGWODC

時間復(fù)雜性分析:

在上述AGWODC算法中,主要包括屬性分組、屬性組權(quán)重與離群得分兩個階段。在屬性分組中,主要包括了組間合并時尋找新的數(shù)據(jù)模式,合并過程中插入新的數(shù)據(jù)模式時,更新其他數(shù)據(jù)模式的頻次等。組間合并時尋找新的數(shù)據(jù)模式所需時間復(fù)雜度約為O(n),更新其他數(shù)據(jù)模式的頻次所需時間復(fù)雜度約為O(n),在最壞情況下,組間合并時間復(fù)雜度為O(d2)。因此,屬性分組的時間復(fù)雜度為O(d2n),其中n為數(shù)據(jù)對象的個數(shù),d為屬性的個數(shù)。在屬性組權(quán)重與離群得分中,主要包括了屬性組權(quán)重的計算和計算數(shù)據(jù)對象離群得分,屬性組權(quán)重的計算時間復(fù)雜度約為O(d),計算數(shù)據(jù)對象離群得分的時間復(fù)雜度約為O(n),因此該過程的時間復(fù)雜度約為O(n)。總之,AGWODC算法的時間復(fù)雜度約為O(d2n+n)。

5 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)配置:Intel Core I5 6300HQ CPU,8G內(nèi)存,并采用python語言在pycharm平臺上,實(shí)現(xiàn)了AGWODC算法及實(shí)驗(yàn)對比算法Watch[10]和CompreX[11]。實(shí)驗(yàn)數(shù)據(jù)集包括UCI,Kaggle,UIUC公開數(shù)據(jù)集。另外,為了驗(yàn)證算法的可擴(kuò)展性和伸縮性,采用GAClust toolkit軟件[34]生成人工數(shù)據(jù)集,將隨機(jī)數(shù)發(fā)生器種子的值設(shè)置為5,類別數(shù)設(shè)置為2,根據(jù)實(shí)驗(yàn)需要設(shè)置相應(yīng)的數(shù)據(jù)量、屬性個數(shù),分別從兩類中選取符合實(shí)驗(yàn)需求的正常數(shù)據(jù)與離群數(shù)據(jù),構(gòu)成人工數(shù)據(jù)集:其中,data1-data4為數(shù)據(jù)量相同,維數(shù)不同的人工數(shù)據(jù)集,用于驗(yàn)證算法的可擴(kuò)展性;data5-data8為維數(shù)相同,數(shù)據(jù)量不同的人工數(shù)據(jù)集,用于驗(yàn)證算法的伸縮性。其數(shù)據(jù)集詳情如表1所示。

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

5.1 檢測準(zhǔn)確性

為了實(shí)驗(yàn)驗(yàn)證AGWODC算法的離群檢測精度,采用了表1所示的UCI,Kaggle,UIUC等10個數(shù)據(jù)集,以及2個對比算法:Watch和CompreX,其AUC[35]指標(biāo)的實(shí)驗(yàn)結(jié)果如表2所示。

由表2可知,AGWODC的AUC指標(biāo)值優(yōu)于其對比算法,僅在Cowsgame數(shù)據(jù)集上略低于CompreX算法,在diabetes數(shù)據(jù)集上略低于Watch算法;盡管AGWODC的ROC曲線基本高于其他對比算法,但在Cowsgame數(shù)據(jù)集上略低于CompreX算法,diabetes數(shù)據(jù)集上略低于Watch算法。因此,表明了AGWODC具有較高的離群檢測精度。其主要原因:AGWODC利用了基于信息熵度量的屬性組權(quán)重,并在離群得分中充分體現(xiàn)出了屬性組間的差異。此外,由于Cowsgame是一種猜數(shù)字游戲的數(shù)據(jù)集,其屬性由玩家若干次猜測數(shù)字構(gòu)成,每次玩家猜測的數(shù)字形成一個屬性組,從而形成有特定含義的屬性分組,且與數(shù)據(jù)集分布無關(guān),屬性組權(quán)重會偏離了特定含義的屬性分組;由于diabetes數(shù)據(jù)集的維數(shù)較低、屬性的取值較少,信息熵?zé)o法體現(xiàn)出屬性組之間的差異。

5.2 檢測效率

為了實(shí)驗(yàn)驗(yàn)證AGWODC算法的離群檢測效率,采用了表1所示的UCI,Kaggle,UIUC等10個數(shù)據(jù)集,以及2個對比算法:Watch和CompreX,其實(shí)驗(yàn)結(jié)果如表3所示。

由表3可知,AGWODC算法的耗時明顯低于其他對比算法,因而表明AGWODC具有較高的檢測效率。其主要原因:由于Watch算法采用特征關(guān)系(FR)等,實(shí)現(xiàn)其屬性分組及離群得分,需要頻繁計算屬性之間的互信息;CompreX算法在屬性組之間合并過程中采用標(biāo)準(zhǔn)化信息增益(NIG)的搜索策略作為屬性組間合并依據(jù);AGWODC采用基于偏離因子(GDF)的搜索策略,避免了NIG中任意兩組間的互信息計算。

5.3 弗里德曼檢驗(yàn)

弗里德曼檢驗(yàn)是一種無參數(shù)檢驗(yàn)方法,用于檢測3組或者3組以上數(shù)據(jù)是否存在顯著差異性。為了評價AGWODC與其他相關(guān)算法在AUC值和檢測效率的優(yōu)越性,采用統(tǒng)計檢驗(yàn)中弗里德曼檢驗(yàn)對3種算法在10個數(shù)據(jù)集上的AUC值和運(yùn)行時間進(jìn)行檢驗(yàn),比較3種算法是否存在差異性。根據(jù)表2和表3中的實(shí)驗(yàn)數(shù)據(jù),弗里德曼檢驗(yàn)統(tǒng)計結(jié)果如表4所示。

表4 AUC與運(yùn)行時間的弗里德曼檢驗(yàn)

由表4可知,在顯著性水平α=0.05時,卡方值為12.000,漸近顯著性為0.002,表明AUC值的秩平均值具有顯著統(tǒng)計學(xué)差異,秩平均值越大,AUC值越大;在顯著性水平α=0.05時,卡方值為20.000,漸近顯著性為0.000 045,表明運(yùn)行時間的秩平均值具有顯著統(tǒng)計學(xué)差異,秩平均值越小,運(yùn)行時間越短。由表4可知,AGWODC的AUC值算法秩平均值最大,運(yùn)行時間秩平均值最小,因此,從統(tǒng)計檢驗(yàn)的角度而言,AGWODC算法優(yōu)于其他算法。

5.4 可擴(kuò)展性與伸縮性

可擴(kuò)展性與伸縮性是衡量離群檢測算法的重要指標(biāo),可擴(kuò)展性是當(dāng)數(shù)據(jù)對象個數(shù)相同,維數(shù)變化對離群檢測算法效率的影響;伸縮性是當(dāng)維數(shù)相同,數(shù)據(jù)對象個數(shù)變化對算法效率的影響。為了驗(yàn)證AGWODC算法的可擴(kuò)展性,采用了表1所示的4個人工數(shù)據(jù)集(data1～data4),以及2個對比算法:Watch和CompreX,其實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 可擴(kuò)展性

由圖1可知,隨著數(shù)據(jù)集的維數(shù)增加,3個算法的耗時呈現(xiàn)了非線性增長,且AGWODC明顯優(yōu)于其他2個對比算法,表明AGWODC具有良好的可擴(kuò)展性。其主要原因:隨著維數(shù)的增加,在屬性分組過程中,屬性組偏離因子(GDF)的計算隨之增多,屬性組代碼表建立和屬性組間合并隨之增多,但避免了CompreX中NIG搜索策略與Watch中FR中屬性之間的互信息計算,有效降低了算法的運(yùn)行時間。

為了驗(yàn)證AGWODC算法的伸縮性,采用了表1所示的4個人工數(shù)據(jù)集(data5～data8),以及2個對比算法:Watch和CompreX,其實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 伸縮性

由圖2可知,隨著數(shù)據(jù)集的數(shù)據(jù)對象增加,3個算法的耗時呈現(xiàn)了非線性增長,且AGWODC明顯優(yōu)于其他2個對比算法,表明AGWODC具有良好的伸縮性。其主要原因:隨著數(shù)據(jù)對象的增加,屬性組間合并時尋找新的數(shù)據(jù)模式、更新數(shù)據(jù)模式頻次和數(shù)據(jù)對象離群得分的計算量也隨之增加,但避免了CompreX中NIG搜索策略與Watch中特征關(guān)系(FR)中屬性之間的互信息計算,大大縮短了算法的運(yùn)行時間。

6 結(jié)束語

該文采用信息熵累加和刻畫屬性組權(quán)重,提出了一種基于屬性組權(quán)重的分類離群數(shù)據(jù)檢測方法,充分體現(xiàn)和刻畫了屬性組之間的差異性以及屬性組的偏離程度,有效地改善了高維離群檢測性能,并緩解了“維度災(zāi)難”干擾,可適用于海量高維分類數(shù)據(jù)離群檢測任務(wù)。下一步研究工作是基于屬性組權(quán)重的分類離群數(shù)據(jù)檢測并行化,以及混合數(shù)據(jù)的高維離群檢測等。