基于屬性聚類的離群數(shù)據(jù)挖掘算法

李俊麗， 張繼福

(1. 太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 山西 太原 030024； 2. 晉中學(xué)院 信息技術(shù)與工程學(xué)院， 山西 晉中 030619)

0 引 言

離群檢測是數(shù)據(jù)挖掘中的一個經(jīng)典問題， 應(yīng)用非常廣泛， 如犯罪活動[1]， 入侵檢測[2-3]， 工業(yè)控制系統(tǒng)異常檢測[4]， 以及光譜數(shù)據(jù)挖掘[5]等領(lǐng)域. 隨著科學(xué)技術(shù)的發(fā)展, 數(shù)據(jù)的收集更快也更容易， 從而導(dǎo)致高維海量數(shù)據(jù)集的產(chǎn)生. 對于處理高維海量數(shù)據(jù)集， 由于數(shù)據(jù)量大和維度高， 許多離群挖掘算法效率會降低， 可能很難發(fā)現(xiàn)僅出現(xiàn)在多維相關(guān)性空間中的一些離群數(shù)據(jù). 很多情況下， 許多高維數(shù)據(jù)集是從不同的角度觀察度量數(shù)據(jù)對象所集成的結(jié)果， 因此可以考慮從不同的角度對屬性進(jìn)行分組， 相關(guān)性高的屬性可以歸為一組. 比如在基因表達(dá)數(shù)據(jù)中， 有核血細(xì)胞的數(shù)據(jù)屬性被分成密度、 顏色和結(jié)構(gòu)等幾個組， 還比如在一個銀行客戶數(shù)據(jù)集中， 屬性可以分為客戶組、 顯示客戶賬戶信息的賬號組和描述客戶消費(fèi)行為的消費(fèi)組等， 可疑客戶可能只顯示和一些金融事務(wù)相關(guān)的消費(fèi)活動， 而客戶信息和賬號信息是正常的. 因此， 一個數(shù)據(jù)對象可能在一個屬性組中為普通數(shù)據(jù)， 但在另一個屬性組中卻是離群數(shù)據(jù). 不同屬性組代表不同的屬性信息， 因此在數(shù)據(jù)挖掘過程中應(yīng)該考慮不同屬性之間的差異性， 將屬性分成不同的組以構(gòu)成不同的屬性子空間， 這樣有助于在每個屬性子空間中挖掘數(shù)據(jù)模式的不同方面， 以便挖掘更有意義的離群數(shù)據(jù).

傳統(tǒng)的分類數(shù)據(jù)離群挖掘方法很多考慮的是在全維空間挖掘離群值， 這些方法忽略了屬性之間的關(guān)系， 因而很難檢測隱藏在屬性子集中的離群值. 本文提出一種新的離群挖掘方法來識別高維分類數(shù)據(jù)集中的離群值. 算法由兩個不同的階段組成. 在第一階段， 屬性子集是通過度量屬性之間的相關(guān)性而創(chuàng)建的， 相關(guān)性高的屬性被放置在一個屬性子集中. 第二個階段是專門的離群挖掘， 每個屬性子集的數(shù)據(jù)對象都被分配離群分?jǐn)?shù). 離群分?jǐn)?shù)高的對象被認(rèn)為是離群值. 本文將現(xiàn)有的三個分類數(shù)據(jù)離群檢測算法和本文提出的算法進(jìn)行比較， 并應(yīng)用人工合成數(shù)據(jù)集和UCI實(shí)際分類數(shù)據(jù)集來評估四個算法的性能.

1 離群挖掘技術(shù)

隨著高維數(shù)據(jù)越來越多， “維災(zāi)”影響了許多離群挖掘算法的效率. 針對高維數(shù)據(jù)集已經(jīng)提出了很多離群挖掘算法， 子空間離群檢測方法就是在相關(guān)的子空間中尋找離群點(diǎn)， 關(guān)于如何確定子空間的相關(guān)性也發(fā)展了很多技術(shù).

1.1 子空間離群挖掘

文獻(xiàn)[6]提出HOS-Miner動態(tài)子空間搜索算法， 該算法使用固定的閾值來識別離群數(shù)據(jù)， 但不同維度的子空間中離群得分無法比較. 文獻(xiàn)[7]引入新的離群得分計(jì)算方法， 通過得分函數(shù)評估分析子空間確定的數(shù)據(jù)對象的偏差， 但在此算法中離群數(shù)據(jù)是基于密度的聚類所產(chǎn)生的副產(chǎn)物. 文獻(xiàn)[8]提出一個高維特征空間變化的子空間中挖掘離群數(shù)據(jù)的原始離群檢測模式， 尤其對于數(shù)據(jù)集中的每個對象， 搜索跨越其最近鄰的軸平行子空間以確定這個子空間中對象偏離其最近鄰的程度. 文獻(xiàn)[9]在幾個子空間中同時評估每個數(shù)據(jù)對象的偏離程度， 通過計(jì)算每個數(shù)據(jù)對象的密度來確定適應(yīng)于不同維度的子空間， 單個子空間中的得分是比較對象密度和它近鄰的平均密度， 一個數(shù)據(jù)對象總得分是它在所有相關(guān)子空間的得分. 文獻(xiàn)[10]提出一個性能不受維度影響的高維數(shù)據(jù)子空間離群挖掘算法. 文獻(xiàn)[11]提出一種新的子空間搜索方法， 選擇高對比度的子空間基于密度的離群值進(jìn)行排名， 聚集局部異常因子(Local Outlier Factor, LOF)得分超過所有的“高對比度”子空間的單個數(shù)據(jù)對象， 但這種方法只適合基于密度的離群挖掘.

1.2 分類數(shù)據(jù)離群挖掘

分類數(shù)據(jù)離群挖掘方法一般分為基于規(guī)則的和基于熵的算法. 基于規(guī)則的算法受到關(guān)聯(lián)規(guī)則挖掘領(lǐng)域中頻繁項(xiàng)的概念的啟發(fā)， 提供了對數(shù)據(jù)集的頻繁或不頻繁項(xiàng)的分析. 例如， 文獻(xiàn)[12]提出一種通過發(fā)現(xiàn)頻繁項(xiàng)集來檢測離群數(shù)據(jù)的新方法. 在該算法中， 包含頻繁模式的數(shù)據(jù)對象不太可能是離群值. Otey等人設(shè)計(jì)了一種由頻繁項(xiàng)集驅(qū)動的算法[13]， 該算法為每個數(shù)據(jù)對象分配一個離群得分， 與對象的非頻繁項(xiàng)集成反比. 在對分類數(shù)據(jù)進(jìn)行離群挖掘的領(lǐng)域中， 另一類算法是基于熵的概念. 文獻(xiàn)[14-15]提出了基于熵的離群檢測方法， 并利用熵來測量數(shù)據(jù)集與離群數(shù)據(jù)之間的無序程度. 提出了離群點(diǎn)的正式定義和離群點(diǎn)檢測的優(yōu)化模型等.

雖然針對高維分類數(shù)據(jù)集已經(jīng)提出了很多離群挖掘算法， 然而這些方法忽略了屬性之間的相對依賴性， 因此可能丟失一些僅出現(xiàn)在多維相關(guān)性空間的離群數(shù)據(jù). 在本文中， 基于屬性之間的相對依賴性， 高維數(shù)據(jù)的屬性被分成不同的屬性子集. 對于高維分類屬性數(shù)據(jù)集， 本文采用屬性聚類的方法將高維屬性分成多個屬性子集， 然后在多個屬性子集上分別進(jìn)行離群數(shù)據(jù)挖掘.

2 分類數(shù)據(jù)集與離群數(shù)據(jù)

目前， 針對數(shù)值型數(shù)據(jù)的離群挖掘研究已經(jīng)有了很多優(yōu)秀成果， 但是現(xiàn)實(shí)生活中存在很多分類數(shù)據(jù)， 由于分類數(shù)據(jù)缺乏固有的幾何特性不能直接進(jìn)行數(shù)值運(yùn)算， 相應(yīng)的離群挖掘算法的設(shè)計(jì)與數(shù)值型數(shù)據(jù)存在較大區(qū)別， 且相對來說也比較復(fù)雜.

通常， 一個分類屬性數(shù)據(jù)集可以用一個矩陣來表示， 一行代表一個數(shù)據(jù)對象， 一列代表一個屬性. 假設(shè)該數(shù)據(jù)集用矩陣D來表示， 其中數(shù)據(jù)對象xi表示第i個數(shù)據(jù)對象， 屬性維Aj表示第j個屬性維，xij(i=1,2,…,n;j=1,2,…,m)表示第i個數(shù)據(jù)對象xi在第j個屬性上的取值. 那么分類數(shù)據(jù)集可以表示為D=(X,A)， 其中，X是數(shù)據(jù)對象的集合，X={X1,…,Xn}，n代表數(shù)據(jù)對象個數(shù)；A是屬性的集合，A={A1,…,Am}，m代表維度或?qū)傩詡€數(shù).

離群數(shù)據(jù)是數(shù)據(jù)集中出現(xiàn)頻率比較低的那些數(shù)據(jù)對象. 因此， 分類數(shù)據(jù)集中理想的離群數(shù)據(jù)對象的每個屬性值都具有較低的頻率.

數(shù)據(jù)對象的離群得分定義為

(1)

式中：xi,j是數(shù)據(jù)對象i在第j個屬性上的值；n(xi,j) 是數(shù)據(jù)對象i的第j個屬性值xi,j出現(xiàn)的頻率.g(x)=(x-1)log(x-1)-xlogx為本文構(gòu)造的一個函數(shù)， 是為了使低頻率的數(shù)據(jù)對象能得到高的離群得分.

3 基于屬性聚類的離群挖掘算法

3.1 屬性聚類

對于高維分類屬性數(shù)據(jù)集， 采用屬性聚類的方法將高維屬性劃分成多個屬性子集. 屬性聚類算法是對數(shù)據(jù)集中的分類屬性采用的一種聚類算法. 不同于傳統(tǒng)的數(shù)據(jù)對象聚類方法， 屬性聚類中同一聚類簇中的屬性具有較高的相似性.

給定任意兩個屬性Ai和Aj， 屬性之間的相對依賴關(guān)系表示為FR(Ai,Aj)， 其定義為

(2)

式中：I代表兩個屬性之間的互信息；H代表兩個屬性之間的熵值.

對于任意一個屬性Ai， 它到其他屬性的關(guān)系和表示為

(3)

通過對屬性進(jìn)行聚類， 屬性被分成不同的簇， 高維屬性集被分成多個屬性子集， 然后在屬性子集上分別進(jìn)行離群挖掘.

3.2 算法描述

算法1 屬性聚類算法(Attribute Clustering)

輸入：c個任選屬性

輸出：c個屬性子集

1) for (r= 1;r≤c;r+ +) ∥c是屬性子集的個數(shù)∥

2) for(i=1;i≤m;i+ +) ∥m是數(shù)據(jù)集中屬性的個數(shù)∥

3) ComputeFR(yi∶ηr) betweenyiandηrby Eq.(2) ∥ηr是屬性子集Cr的中心屬性， 通過式(2)計(jì)算屬性yi和ηr之間的相對依賴關(guān)系∥

4) ifFR(yi∶ηr)≥FR(yi∶ηs) (s∈{1,…,c}-{r})

5) assignyitoCr

6) end if

7) end for

8) ifMR(yi)≥MR(yj) (yj∈Cr,j≠i) (Eq.(3))

9) setηr=yi

10) end if

11) end for

12) Repeatedly perform step1-11 until all the numbercof features for the groups remain unchanged ∥重復(fù)算法直到c個中心屬性不變∥

13) Outputcattribute subsets

算法2 Outlier Mining Algorithm Using Attribute Clustering (OMAC)

輸入: 數(shù)據(jù)集DS， 屬性子集個數(shù)c

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

1) Obtaincattribute subsets by algorithm 1;∥通過屬性聚類得到c個屬性子集∥

2) For (r=1;r≤c;r+ +) ∥c是屬性子集的數(shù)量∥

3) For (i=1;i≤n;i+ +) ∥n是數(shù)據(jù)對象的數(shù)量∥

4) Compute the score of objectxiby Eq.(1);∥通過式(1)計(jì)算數(shù)據(jù)對象的離群得分∥

5) End for

6) End for

7) Searching thekobjects with greatest scores ∥查找k個得分最高的離群數(shù)據(jù)∥

8) Outputkoutliers

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

本文選用UCI數(shù)據(jù)集和人工數(shù)據(jù)集對OMAC算法的性能進(jìn)行實(shí)驗(yàn)分析. 實(shí)驗(yàn)環(huán)境為： CPU Intel(R) Core(TM) i7-4713MQ， RAM 4 GB， Windows 7操作系統(tǒng)， 采用 Java 語言實(shí)現(xiàn)了OMAC以及其他三個比較算法GA[15]， AVF[16]和ITB[17].

4.1 UCI數(shù)據(jù)集

使用來自UCI的四個真實(shí)的分類數(shù)據(jù)集. 由于預(yù)先知道測試數(shù)據(jù)集中的每個對象所屬于的真正類， 所以將數(shù)據(jù)集中小類中的對象定義為異常對象. 參考文獻(xiàn)[15]的實(shí)驗(yàn)技術(shù)， 刪除了一些小類的數(shù)據(jù)對象， 使數(shù)據(jù)集中有大約2%的數(shù)據(jù)是離群數(shù)據(jù). 實(shí)驗(yàn)中使用的UCI數(shù)據(jù)集如表 1 所示.

表 1 UCI數(shù)據(jù)集描述Tab.1 Description of UCI datasets

為了對離群檢測算法的準(zhǔn)確率進(jìn)行評估， 在UCI數(shù)據(jù)集上采用不同算法進(jìn)行了實(shí)驗(yàn)， 算法對真實(shí)數(shù)據(jù)集的準(zhǔn)確率描述如表 2 所示.

表 2 UCI數(shù)據(jù)集準(zhǔn)確率比較Tab.2 Comparison of the accuracy in the UCI datasets

由表 2 可以看出， 與其他算法相比， OMAC算法在真實(shí)數(shù)據(jù)集上的準(zhǔn)確率較高. 主要原因是OMAC算法是基于屬性子集的離群挖掘算法， 而其他算法從所有屬性維度挖掘離群數(shù)據(jù)， 準(zhǔn)確性受到“維災(zāi)”的影響.

4.2 人工數(shù)據(jù)集

使用人工合成數(shù)據(jù)的優(yōu)點(diǎn)是能夠生成各種大小和維度的數(shù)據(jù)集. 本文使用GAClust軟件生成了 50維的5 000條， 10 000條， 15 000條和 20 000條的人工數(shù)據(jù)集共4個， 分別為數(shù)據(jù)集1， 2， 3和4. 每個數(shù)據(jù)集中有1%的數(shù)據(jù)是離群數(shù)據(jù).

4.2.1K值對不同算法準(zhǔn)確率和效率的影響

在數(shù)據(jù)集1中， 離群數(shù)據(jù)數(shù)目k為50， 為了測試不同算法不同k值所對應(yīng)的準(zhǔn)確率， 將數(shù)據(jù)集1的離群數(shù)據(jù)數(shù)目進(jìn)行了增減， 隨著k值的變化， 不同算法的準(zhǔn)確率如圖 1 所示.

圖 1 不同k值對應(yīng)的準(zhǔn)確率Fig.1 Accuracy of different k values

由圖 1 可以看出， 隨著k值的增加， 挖掘準(zhǔn)確率有所降低. 主要原因是隨著要挖掘的離群數(shù)據(jù)數(shù)量的增加， 挖掘難度越來越大. 但OMAC算法的準(zhǔn)確性明顯高于其他算法. 這是因?yàn)镺MAC算法能夠在不同的屬性子集中挖掘不同的特征模式， 因此可以檢測到更多的離群數(shù)據(jù).

將數(shù)據(jù)集1的離群數(shù)據(jù)數(shù)目k分別設(shè)置為30， 60， 90， 120和150以測試離群數(shù)據(jù)數(shù)量對不同算法的效率的影響. 隨著離群數(shù)目的增加， 不同算法的效率如圖 2 所示.

圖 2 離群數(shù)據(jù)量大小對算法效率的影響Fig.2 Effect of outlier size on efficiency of algorithm

由圖 2 可以看出， 隨著離群數(shù)據(jù)目標(biāo)數(shù)k值的增加， 其他算法運(yùn)行時間都基本不變， 只有GA算法的運(yùn)行時間線性增加. 這是因?yàn)镚A挖掘一個離群數(shù)據(jù)需要對數(shù)據(jù)集進(jìn)行一次掃描， 所以挖掘k個離群數(shù)據(jù)需要掃描數(shù)據(jù)集k次， 因此隨著離群數(shù)據(jù)目標(biāo)數(shù)的增加， 時間消耗會增加， 而其他的算法則不會.

4.2.2 數(shù)據(jù)對象大小和維度大小對算法效率的影響

首先， 使用數(shù)據(jù)集1， 2， 3和4來進(jìn)行算法效率的測試. 隨著數(shù)據(jù)集數(shù)據(jù)對象的變化， 不同算法的效率表現(xiàn)如圖 3 所示.

圖 3 數(shù)據(jù)集大小對算法的效率影響Fig.3 Effect of data set size on efficiency of algorithm

其次， 將數(shù)據(jù)集1的維度增加到100維， 150維和200維以測試維度增加對不同算法效率的影響. 隨著屬性維數(shù)的增加， 不同算法的效率如圖 4 所示.

圖 4 數(shù)據(jù)集維度大小對算法的效率影響Fig.4 Effect of data set dimensionality on the efficiency of the algorithm

由圖 3 和圖 4 可以看出， 隨著數(shù)據(jù)對象的增加， OMAC的時間消耗有所增加， 但與其他算法相比， 增加的時間并不明顯. 與其他三種算法相比， OMAC的運(yùn)行時間增長速度比較緩慢. 這是因?yàn)镚A算法的時間復(fù)雜度比其他三種算法都要高. 對于ITB算法， 由于算法需要計(jì)算出離群值的上限， 因此， ITB算法的總體復(fù)雜度略高于OMAC和AVF.

5 結(jié) 論

本文提出了一種基于屬性聚類的離群挖掘算法， 稱為OMAC， 用于高維分類數(shù)據(jù)集. 與大多數(shù)現(xiàn)有的算法不同， 該算法可以將屬性進(jìn)行分組， 這樣可以在不同的屬性子集中挖掘數(shù)據(jù)對象的不同方面， 并從高維的分類數(shù)據(jù)中挖掘出相應(yīng)的離群數(shù)據(jù). 此外， 除了需要檢測的離群數(shù)據(jù)的目標(biāo)數(shù)， OMAC算法不需要對任何用戶給定的參數(shù)進(jìn)行設(shè)置. 為了進(jìn)行性能評價(jià)， 通過UCI數(shù)據(jù)集和人工合成數(shù)據(jù)集對OMAC算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證. 結(jié)果表明， 其在高維分類屬性數(shù)據(jù)集上， OMAC與AVF， GA， ITB算法相比， 其離群數(shù)據(jù)的能力和效率都有所提高.

參考文獻(xiàn)：

[1] 凌晨添. 進(jìn)化神經(jīng)網(wǎng)絡(luò)在信用卡欺詐檢測中的應(yīng)用[J]. 微電子學(xué)與計(jì)算機(jī), 2011, 28(10)： 14-17.

Ling Chentian. Evolutionary neural network for credit card frand detection[J]. Microelectronics and Computer, 2011, 28(10)： 14-17. (in Chinese)

[2] 梅孝輝. 基于聚類的離群點(diǎn)挖掘在入侵檢測中的應(yīng)用研究[D]. 重慶： 重慶大學(xué), 2015.

[3] 歐陽根平. Hadoop云平臺下基于離群點(diǎn)挖掘的入侵檢測技術(shù)研究[D]. 成都： 電子科技大學(xué), 2015.

[4] 陳莊, 黃勇, 鄒航. 基于離群點(diǎn)挖掘的工業(yè)控制系統(tǒng)異常檢測[J]. 計(jì)算機(jī)科學(xué), 2014, 41(5)： 178-181.

Chen Zhuang, Huang Yong, Zou Hang. Anomaly detection of industrial control system based on outlier mining[J]. Computer Science, 2014, 41(5)： 178-181. (in Chinese)

[5] 張繼福, 李永紅, 秦嘯, 等. 基于MapReduce 與相關(guān)子空間的局部離群數(shù)據(jù)挖掘算法[J]. 軟件學(xué)報(bào), 2015 26(5)： 1079-1095.

Zhang Jifu, Li Yonghong, Qin Xiao, et al. Related-subspace-based local outlier detection algorithm using map reduce[J]. Journal of Software, 2015, 26(5)： 1079-1095. (in Chinese)

[6] Zhang J, Lou M, Ling T W, et al. HOS-miner： a system for detecting outlying subspaces of high-dimensional data[C]. Thirtieth International Conference on Very Large Data Bases. VLDB Endowment, 2004： 1265-1268.

[7] Müller E, Assent I, Steinhausen U, et al. OutRank： ranking outliers in high dimensional data[C]. Proceedings of the 24th International Conference on Data Engineering (ICDE) Workshop on Ranking in Databases (DBRank), Cancun, Mexico, 2008： 600-603.

[8] Fayyad U M, Piatetsky-Shapiro G, Smyth P. Advances in Knowledge Discovery and Data Mining[M]. Massachusetts: MIT Press, 1996.

[9] Müller E, Schiffer M, Seidl T. Adaptive outlierness for subspace outlier ranking[C]. International Conference on Information and Knowledge Management, 2010： 1629-1632.

[10] Nguyen H V, Gopalkrishnan V, Assent I. An unbiased distance-based outlier detection approach for high-dimensional data[C]. International Coference on Database Systems for Advanced Application, 2011(6587)： 138-152.

[11] Keller F, Muller E, Bohm K. HiCS： high contrast subspaces for density-based outlier ranking[J]. IEEE, 2012, 41(4)： 1037-1048.

[12] He Z, Xu X, Huang Z J, et al. FP-outlier： frequent pattern based outlier detection[J]. Computer Science and Information Systems, 2005(2): 103-118.

[13] Otey M E, Ghoting A, Parthasarathy S. Fast distributed outlier detection in mixed-attribute data sets[J]. Data Mining and Knowledge Discovery, 2006(12): 203-228.

[14] He Z, Deng S, Xu X. An optimization model for outlier detection in categorical data[J]. Lecture Notes in Computer Science, 2005, 3644(1): 400-409.

[15] He Z, Xu X, Deng S, et al. A fast greedy algorithm for outlier mining[C]. Proceedings of 10th Pacific-Asia Conference on Knowledge and Data Discovery, 2006: 567-576.

[16] Koufakou A. Scalable and efficient outlier detection in large distributed data sets with mixed-type attributes[D]. Orlando: University of Central Florida, 2009.

[17] Wu S, Wang S. Information-theoretic outlier detection for large-scale categorical data[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(3): 589-602.