張凱棋,宋亦靜,陳 鑫

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

0 引 言

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 屬性分組與離群檢測(cè)

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

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

(1)

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

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

數(shù)據(jù)模式是指數(shù)據(jù)對(duì)象(xi)在屬性組(Fj)中,屬性的一個(gè)取值項(xiàng)集。在Fj中,xi由若干個(gè)互不相同的數(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)刻畫(huà)了數(shù)據(jù)模式在CT下的頻率分布,其值越大,表明該數(shù)據(jù)模式在代碼表中出現(xiàn)的頻率越大,反之亦然。

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

(3)

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

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

(4)

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

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

(5)

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

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

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

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

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

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

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

(6)

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

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

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

在屬性分組中,數(shù)據(jù)模式出現(xiàn)的頻率體現(xiàn)了屬性取值項(xiàng)集疏密程度,數(shù)據(jù)模式編碼長(zhǎng)度體現(xiàn)了數(shù)據(jù)模式頻率分布。數(shù)據(jù)模式編碼長(zhǎng)度體現(xiàn)了屬性組的不確定性,可以有效地衡量屬性組的偏離程度。對(duì)于任意屬性組(Fj),設(shè)CT為Fj對(duì)應(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))分別刻畫(huà)了r,t所含的信息量,數(shù)據(jù)模式出現(xiàn)的頻次越小,包含的離群信息量越大,反之亦然。r是屬性組(Fj)中含離群信息量最大的數(shù)據(jù)模式,而t是屬性組(Fj)中含離群信息量最小的數(shù)據(jù)模式,因此,GDF(CT)刻畫(huà)了Fj的偏離程度。在屬性分組中,采用偏離因子(GDF)作為屬性組之間合并順序依據(jù),只需要利用代碼表中已有的數(shù)據(jù)模式編碼,計(jì)算d個(gè)屬性組的GDF。相較NIG而言,避免了NIG中任意兩組間的互信息計(jì)算,因此有效地提高了搜索策略的效率。

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

(8)

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

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

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

(9)

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

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

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

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

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

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

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

算法偽代碼如下:

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

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

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

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

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

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

4.ForFuinP:

5. forFvinP:

6.降序排序OD

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

cost=L(P,CT,OD)

8.根據(jù)公式(2)計(jì)算數(shù)據(jù)模式的編碼長(zhǎng)度,構(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)計(jì)算CT'的CDF,更新OD

14.返回步驟(4)

15. endif;

16. endfor;

17.Endfor;

18.For eachjinP:

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

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

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

22.Endfor;

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

24.End AGWODC

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

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

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

實(shí)驗(yàn)配置:Intel Core I5 6300HQ CPU,8G內(nèi)存,并采用python語(yǔ)言在pycharm平臺(tái)上,實(shí)現(xiàn)了AGWODC算法及實(shí)驗(yàn)對(duì)比算法Watch[10]和CompreX[11]。實(shí)驗(yàn)數(shù)據(jù)集包括UCI,Kaggle,UIUC公開(kāi)數(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ù)量、屬性個(gè)數(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 檢測(cè)準(zhǔn)確性

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

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

5.2 檢測(cè)效率

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

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

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

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

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

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

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

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

圖1 可擴(kuò)展性

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

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

圖2 伸縮性

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

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

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