基于屬性組權重的分類數據離群檢測

張凱棋,宋亦靜,陳 鑫

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

0 引 言

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

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

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

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

·提出了一種基于屬性組權重的分類離群數據檢測算法。

1 相關工作

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

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

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

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

2 屬性分組與離群檢測

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

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

(1)

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

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

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

(2)

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

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

(3)

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

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

(4)

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

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

(5)

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

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

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

(1)將每個屬性視為單獨的一組,根據公式(2),計算數據模式編碼,構建對應的代碼表;

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

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

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

(6)

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

3 屬性組權重與分類離群檢測

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

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

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

(7)

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

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

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

(8)

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

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

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

(9)

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

4 基于屬性組權重的分類離群檢測算法

依據上一章節描述,采用屬性組權重,分類離群檢測基本步驟描述如下:

(1)將每個屬性視為單獨的一組,根據公式(2),計算數據模式編碼,構建對應代碼表;

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

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

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

算法偽代碼如下:

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

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

輸出:k個離群數據對象

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

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

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

4.ForFuinP:

5. forFvinP:

6.降序排序OD

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

cost=L(P,CT,OD)

8.根據公式(2)計算數據模式的編碼長度,構建新的代碼表(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. 根據公式(7)計算CT'的CDF,更新OD

14.返回步驟(4)

15. endif;

16. endfor;

17.Endfor;

18.For eachjinP:

19.根據公式(8)計算組權重ω(Fj)

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

21.根據公式(9)計算數據對象的離群分數

22.Endfor;

23.選擇離群分數最高的k個離群數據對象

24.End AGWODC

時間復雜性分析:

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

5 實驗結果

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

表1 實驗數據集

5.1 檢測準確性

為了實驗驗證AGWODC算法的離群檢測精度,采用了表1所示的UCI,Kaggle,UIUC等10個數據集,以及2個對比算法:Watch和CompreX,其AUC[35]指標的實驗結果如表2所示。

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

5.2 檢測效率

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

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

5.3 弗里德曼檢驗

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

表4 AUC與運行時間的弗里德曼檢驗

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

5.4 可擴展性與伸縮性

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

圖1 可擴展性

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

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

圖2 伸縮性

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

6 結束語

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