李龍姣，程國(guó)達(dá)

(南京財(cái)經(jīng)大學(xué)信息工程學(xué)院，江蘇 南京 210046)

0 引言

一個(gè)離群點(diǎn)是這樣一個(gè)數(shù)據(jù)，它與數(shù)據(jù)集中其它數(shù)據(jù)偏離如此之多以至于讓人們懷疑它是由另外一種完全不同的機(jī)制產(chǎn)生的[1]。離群點(diǎn)檢測(cè)是數(shù)據(jù)挖掘的基本任務(wù)之一，其目的是消除噪音或發(fā)現(xiàn)潛在的、有用的知識(shí)，例如欺詐檢測(cè)、入侵檢測(cè)、故障檢測(cè)、生態(tài)系統(tǒng)失調(diào)檢測(cè)等[2]。傳統(tǒng)的離群點(diǎn)檢測(cè)方法主要分為5類:(1)基于統(tǒng)計(jì)的方法[3];(2)基于深度的方法[4];(3)基于聚類的方法[5];(4)基于密度的方法[6];(5)基于距離的方法[7]。

隨著信息技術(shù)的發(fā)展，現(xiàn)實(shí)數(shù)據(jù)集的維數(shù)和數(shù)據(jù)的數(shù)量顯著上升，幾十維甚至上百維的數(shù)據(jù)并不少見(jiàn)。在高維數(shù)據(jù)空間中，數(shù)據(jù)非常稀疏，根據(jù)數(shù)據(jù)的相似性，每個(gè)點(diǎn)都可被定義為離群點(diǎn)[8]。如何選擇合理高效的度量方法處理好高維空間數(shù)據(jù)點(diǎn)的稀疏問(wèn)題，并合理解釋高維空間離群點(diǎn)的物理意義，是高維離群點(diǎn)挖掘方法的目標(biāo)。

1 現(xiàn)有高維離群點(diǎn)挖掘方法

高維數(shù)據(jù)中的離群點(diǎn)并不是在所有維上都離群，在絕大多數(shù)情況下，離群數(shù)據(jù)往往只在少數(shù)幾個(gè)維上出現(xiàn)異常。如果在數(shù)據(jù)的所有維上進(jìn)行離群點(diǎn)挖掘，不僅有很大的時(shí)間復(fù)雜度，而且由于平均作用，使得數(shù)據(jù)之間差異變得很小[9]，為了提高挖掘效率，人們提出了投影變換[9-10]和特征選取[11-12]等基于子空間挖掘的方法。

Aggarwal等[9]提出了用遺傳算法來(lái)尋找最優(yōu)子空間的投影變換方法，這種方法將空間劃分成等邊的網(wǎng)格空間并計(jì)算每個(gè)網(wǎng)格的稀疏因子，然后利用遺傳算法來(lái)挖掘子空間中的離群點(diǎn)。在這種方法中，計(jì)算每個(gè)網(wǎng)格的稀疏因子都要掃描整個(gè)數(shù)據(jù)集，因此具有很高的計(jì)算復(fù)雜度。Sanghamitra等[13]提出了一種改進(jìn)方法，可以大大縮短計(jì)算時(shí)間。上述兩種方法采用遺傳算法雖然能有效解決數(shù)據(jù)投影問(wèn)題，但還存在問(wèn)題。首先，在初始化階段，構(gòu)成染色體的維是隨機(jī)選取的，這就給離群點(diǎn)挖掘結(jié)果帶來(lái)很大的不確定因素;其次，不同的網(wǎng)格劃分存在困難，不同的劃分會(huì)帶來(lái)不同的結(jié)果。

Angiulli等[11]提出了 HilOut算法，該方法首先利用Hilbert曲線將高維數(shù)據(jù)映射到一維線性空間，根據(jù)數(shù)據(jù)在一維空間中的前驅(qū)和后繼找出每個(gè)數(shù)據(jù)的k個(gè)最近鄰，從而計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的權(quán)值，最后根據(jù)權(quán)值排序找出離群點(diǎn)，避免了復(fù)雜的距離計(jì)算開(kāi)銷。雖然Hilbert曲線可以將復(fù)雜的高維問(wèn)題轉(zhuǎn)化為簡(jiǎn)單的一維空間計(jì)算問(wèn)題，但是該方法還是有不少缺點(diǎn)。首先，Hilbert曲線也和網(wǎng)格劃分方法一樣，要不斷將每個(gè)維2等分，這一點(diǎn)是很難做到的，因?yàn)椴皇敲總€(gè)維的長(zhǎng)度都是2的次方;其次，Hilbert曲線雖然能保證一維上相鄰的數(shù)據(jù)點(diǎn)在原高維空間中也相鄰，但是高維空間中相鄰的點(diǎn)用該曲線映射到一維空間中就不一定相鄰了，這就難以保證挖掘結(jié)果的準(zhǔn)確性。

除了上述兩種投影變換方法之外，小波變換也可以用來(lái)在子空間上挖掘離群點(diǎn)。它首先通過(guò)在數(shù)據(jù)空間強(qiáng)加一個(gè)多維網(wǎng)格結(jié)構(gòu)來(lái)匯總數(shù)據(jù)，然后進(jìn)行變換，在變換后的空間中發(fā)現(xiàn)密集區(qū)域[14]，消除密集區(qū)域后剩下的點(diǎn)就是離群點(diǎn)。Yu等[15]就利用小波變換從原始數(shù)據(jù)中消除了聚類從而得到離群點(diǎn)。當(dāng)然，該方法也有網(wǎng)格劃分的缺點(diǎn)。

Mohamed 等[16]提出了 PCKA(Projected Clustering based on the K-means Algorithm)特征選取算法。該方法把空間中的維分為兩種，一種是密集維，另一種是稀疏維，離群點(diǎn)就在稀疏維上，而聚類就要在密集維上尋找。PCKA的不足之處就是簡(jiǎn)單地把高維空間中的維劃分為密集維和稀疏維，沒(méi)有考慮有些維既有聚類數(shù)據(jù)的投影，也有離群數(shù)據(jù)的投影，這部分維在該算法中很可能被誤除從而影響挖掘結(jié)果。

此外，Tan等[17]提出的決策樹(shù)歸納方法和許龍飛等[18]提出的粗糙集方法來(lái)挖掘離群點(diǎn)，但這些方法存在和文獻(xiàn)[16]一樣的問(wèn)題。

在本文提出的方法中，計(jì)算高維數(shù)據(jù)每一維上的稀疏度，根據(jù)稀疏度形成直方圖，在直方圖上判別該維上離群點(diǎn);在得到離群點(diǎn)-離群維的對(duì)應(yīng)關(guān)系表后，用FP增長(zhǎng)方式對(duì)離群點(diǎn)-離群維關(guān)系表進(jìn)行分析，像挖掘關(guān)聯(lián)規(guī)則一樣，挖掘存在離群點(diǎn)的維之間的關(guān)系，從而解釋離群點(diǎn)不同維之間的關(guān)系。通過(guò)對(duì)實(shí)際數(shù)據(jù)集的實(shí)驗(yàn)，表明本方法是有效和有意義的。

2 原理與算法

2.1 KNN(K-Nearest Neighbors)距離的計(jì)算

假設(shè)DB是一個(gè) d維數(shù)據(jù)，A={A1，A2，…，Ad}表示數(shù)據(jù)集的維，X={x1，x2，…，xN}為數(shù)據(jù)集的 N個(gè)數(shù)據(jù)點(diǎn)，其中 xi={xi1，xi2，…，xid}，xij(i=1，…，N;j=1，…，d)對(duì)應(yīng)著數(shù)據(jù)點(diǎn)xi在維Aj上的值。數(shù)據(jù)集中任意兩點(diǎn) xu，xv在維 As上的距離為 ds(xu，xv)=|xus－xvs|，其中1≤u，v≤N，1≤s≤d。

定義1 在d維數(shù)據(jù)集DB中，給定一個(gè)參數(shù)k，一個(gè)數(shù)據(jù)點(diǎn)的KNN距離是指這個(gè)點(diǎn)與其k個(gè)最近鄰點(diǎn)的距離之和。

KNN距離顯示出了一個(gè)點(diǎn)的離群程度，KNN距離越大，這個(gè)點(diǎn)距離它的k個(gè)最鄰近點(diǎn)越遠(yuǎn)，即它是離群點(diǎn)的可能性越高。

算法1(KNN距離計(jì)算)

輸入:DB:數(shù)據(jù)集;k:近鄰數(shù)據(jù)點(diǎn)數(shù)目;Aj:需要計(jì)算的維j;N:每一維的數(shù)據(jù)數(shù)目。

輸出:每個(gè)數(shù)據(jù)點(diǎn)在Ai上的KNN距離yij(i=1，…，N;j=1，…，d)(規(guī)范化至[0，1])。

步驟1 將DB中Ai對(duì)應(yīng)的N個(gè)值存儲(chǔ)到一維數(shù)組 a[N]，b[N];

步驟2 將數(shù)組b中元素升序排列，取每個(gè)元素b[i](i=0，…，N-1)的前驅(qū)和后繼元素共2k 個(gè);

步驟3 計(jì)算b[i](i=0，…，N-1)與其2k個(gè)前驅(qū)后繼的直線距離，并將這2k個(gè)距離從小到大排序;

步驟4 從排序的距離中取前k個(gè)距離相加即為KNN距離;

步驟5 將Aj上數(shù)值的KNN距離規(guī)范化至[0，1];

步驟6 從數(shù)組a中獲取b中元素在DB中對(duì)應(yīng)的索引號(hào)以便將其在Aj上的KNN距離yij保存到相應(yīng)位置。

2.2 通過(guò)直方圖判別離群點(diǎn)

Knorr等在文獻(xiàn)[19]中這樣定義離群點(diǎn):如果數(shù)據(jù)集DB中對(duì)象至少有pct部分與對(duì)象o的距離大于dmin，則稱對(duì)象o是以pct和dmin為參數(shù)的基于距離的離群點(diǎn)。

上述基于距離的離群點(diǎn)定義是全局離群點(diǎn)的定義，除此之外，還有另外的一種離群點(diǎn)，如果一個(gè)對(duì)象相對(duì)于它的局部鄰域，特別是關(guān)于鄰域密度，它是遠(yuǎn)離的，那它就是局部離群點(diǎn)[20]。

除了上述定義的全局離群點(diǎn)和局部離群點(diǎn)，本文提出一種隱形離群點(diǎn)。

定義2 數(shù)據(jù)集DB的對(duì)象，如果其綜合屬性分析結(jié)果屬于某個(gè)聚類C，但是在某些維上卻不屬于任何聚類在這些維上的投影區(qū)域，這種對(duì)象為隱形離群點(diǎn)。

隱形離群點(diǎn)一般處于所屬聚類的邊緣，以全局的眼光來(lái)看并不離群，使用投影變換或者特征選取方法挖掘離群點(diǎn)時(shí)也容易被忽略，本文在數(shù)據(jù)的每一維上進(jìn)行分析后才能保證將其辨別，并準(zhǔn)確判斷其離群維。

如某個(gè)數(shù)據(jù)點(diǎn)在任何一維上離群，則把它當(dāng)作是離群點(diǎn)并記下它離群的維以便后續(xù)分析。根據(jù)直方圖找出全局離群點(diǎn)、局部離群點(diǎn)以及隱形離群點(diǎn)，其中隱形的離群點(diǎn)并不屬于預(yù)先設(shè)定的離群點(diǎn)集，但也會(huì)隨著離群點(diǎn)一起檢測(cè)出，經(jīng)過(guò)FP增長(zhǎng)分析后方可確定是否離群，這些離群點(diǎn)是很有分析價(jià)值的，提取這些隱形離群點(diǎn)和明顯的離群點(diǎn)一起進(jìn)行后續(xù)的離群屬性關(guān)系分析，將得到很多有用的信息。

KNN 距離規(guī)范至區(qū)間[0，1]，將[0，1]區(qū)間分成s份，每份長(zhǎng)度為1/s，然后計(jì)算 Ai(i=1，…，d)上屬于每個(gè)區(qū)間的數(shù)據(jù)個(gè)數(shù)，從而生成KNN直方圖。

假設(shè)離群點(diǎn)在數(shù)據(jù)集中所占比例為α(0＜α≤5%)，數(shù)據(jù)總數(shù)為N，則離群點(diǎn)數(shù)目為αN。在直方圖中，S1，…，Sm為 s個(gè) KNN 距離區(qū)間，|Si|(i=1，…，s)為第i個(gè)區(qū)間包含的數(shù)據(jù)點(diǎn)數(shù)目。

定義3 在某一維的KNN直方圖中，將前m(0＜m≤s)個(gè)KNN距離區(qū)間所包含的數(shù)據(jù)點(diǎn)數(shù)目相加得直至且≥(1－α/2)N，如果|Sm+1|≤αN，則N，如果|Sm+1|≥αN，則，定義直方圖中右邊β部分的數(shù)據(jù)點(diǎn)為這一維上的全局離群點(diǎn)。

定義3給出了在直方圖中區(qū)分全局離群點(diǎn)的規(guī)則，其中αN為離群點(diǎn)總數(shù)，離群點(diǎn)包含全局離群點(diǎn)、局部離群點(diǎn)和隱形離群點(diǎn)，故定義中將αN/2作為全局離群點(diǎn)的最大值，在直方圖中進(jìn)行具體的計(jì)算后，確定β為判定全局離群點(diǎn)的邊界值，即把直方圖右部β部分?jǐn)?shù)據(jù)點(diǎn)判定為全局離群點(diǎn)。

定義4 在某一維的KNN直方圖中，從S1至SS取第一個(gè)包含數(shù)據(jù)點(diǎn)小于αN的距離區(qū)間Sn(1＜n＜s)，令γ=，則這一維上的局部離群點(diǎn)和隱形離群點(diǎn)存在于γ和β部分?jǐn)?shù)據(jù)點(diǎn)之間。

定義4給出了局部離群點(diǎn)和隱形離群點(diǎn)在直方圖中存在范圍。由于聚類的密度不同，故不同的聚類包含的數(shù)據(jù)點(diǎn)所處的KNN距離區(qū)間不同，本方法定義處于直方圖左邊γ部分的數(shù)據(jù)點(diǎn)為該維上密度最大聚類中的數(shù)據(jù)點(diǎn)，而Sn為該聚類與其余聚類之間的分隔，γ至β部分?jǐn)?shù)據(jù)就包含了小密度聚類以及局部離群點(diǎn)和隱形離群點(diǎn)。由于局部離群點(diǎn)存在于不同的聚類之間，隱形離群點(diǎn)處于聚類的邊緣，局部離群點(diǎn)和隱形離群點(diǎn)的KNN距離大于聚類中數(shù)據(jù)點(diǎn)的KNN距離。

定義5 取直方圖左邊γ部分?jǐn)?shù)據(jù)所在KNN區(qū)間包含的平均數(shù)據(jù)點(diǎn)數(shù)目為c，即c=|Si|/(n－1)，將εc(0＜ε≤1)作為聚類包含數(shù)據(jù)點(diǎn)數(shù)目的最小值。

定義6 在某一維的直方圖中，對(duì)于[γ，β]部分?jǐn)?shù)據(jù)所在的KNN距離區(qū)間，如果連續(xù)3個(gè)區(qū)間內(nèi)數(shù)據(jù)點(diǎn)的數(shù)目之和小于εc，則這些區(qū)間內(nèi)的數(shù)據(jù)點(diǎn)為這一維上的局部離群點(diǎn)或者隱形離群點(diǎn)。

定義5和定義6給出了在直方圖中判別局部離群點(diǎn)和隱形離群點(diǎn)的規(guī)則。實(shí)驗(yàn)表明，處于直方圖中[γ，β]部分?jǐn)?shù)據(jù)中的聚類，其包含數(shù)據(jù)點(diǎn)的KNN距離最多分布與3個(gè)連續(xù)的區(qū)間，故如果連續(xù)3個(gè)連續(xù)區(qū)間的數(shù)據(jù)數(shù)目之和小于εc，則這些區(qū)間內(nèi)的數(shù)據(jù)就是疑似局部離群點(diǎn)或者隱形離群點(diǎn)。

算法2 (根據(jù)KNN直方圖判別離群點(diǎn))

輸入:d維數(shù)據(jù)集DB;每一維數(shù)據(jù)在s個(gè)KNN距離區(qū)間內(nèi)的數(shù)據(jù)點(diǎn)數(shù)目;離群點(diǎn)在數(shù)據(jù)集中所占比例α，數(shù)據(jù)總數(shù) N，ε(0 ＜ ε≤1))。

輸出:每一維上的全局離群點(diǎn)所在距離區(qū)間集合outlier_Interval以及局部離群點(diǎn)和隱形離群點(diǎn)所在的距離區(qū)間集合local_Interval。

方法:對(duì)每一維數(shù)據(jù)Ai(i≤i≤d)。

(1)全局離群點(diǎn)判別。

(2)確定γ。

(3)確定局部離群點(diǎn)。

2.3 離群點(diǎn)-離群維關(guān)系表

找出數(shù)據(jù)集中的離群點(diǎn)只是本文的目的之一，更為重要的目的是分析存在離群點(diǎn)的屬性之間的關(guān)系，為此首先要生成離群點(diǎn)-離群維關(guān)系表。

算法3 (離群點(diǎn)-離群維關(guān)系表生成)

輸入:d維數(shù)據(jù)集DB;每一維上的全局離群點(diǎn)以及局部離群點(diǎn)和隱形離群點(diǎn)所在的距離區(qū)間集合。

輸出:每個(gè)離群點(diǎn)的離群屬性集;將維Ai對(duì)應(yīng)的數(shù)據(jù)存入一維數(shù)組pointValue[N];將維Ai數(shù)據(jù)對(duì)應(yīng)的KNN距離值存入一維數(shù)組pointWeight[N];所有的離群點(diǎn)在pointValue的對(duì)應(yīng)的索引號(hào)存入一位數(shù)組 Outlier[N]。

方法:

在數(shù)組pointWeight中找到屬于這些KNN距離區(qū)間的KNN距離并把這些距離對(duì)應(yīng)的索引號(hào)存入一位數(shù)組pointIndex

for j=0 to pointIndex.Count do

if(Outlier中存在 pointIndex[j])

取得pointIndex[j]在Outlier中的索引號(hào)index;

將這一維的維數(shù)i加入pointIndex[j]對(duì)應(yīng)的數(shù)組Att[index];

else

將 pointIndex[j]加入 Outlier

將這一維的位數(shù) i加入 pointIndex[j]對(duì)應(yīng)的數(shù)組 Att[Outlier.Count-1];

end for

end for

2.4 離群維的頻繁項(xiàng)集分析

頻繁地同時(shí)出現(xiàn)離群屬性組合就是頻繁項(xiàng)集，這些離群維之間必然存在某些關(guān)聯(lián)規(guī)則，發(fā)現(xiàn)這些規(guī)則可以發(fā)現(xiàn)離群點(diǎn)的離群原因，從而解釋離群點(diǎn)的物理意義。為了避免產(chǎn)生大量候選項(xiàng)集合重復(fù)掃描數(shù)據(jù)庫(kù)，本文選擇頻繁模式增長(zhǎng)(Frequent-Pattern Growth，F(xiàn)P增長(zhǎng))[14]方法對(duì)離群屬性集進(jìn)行頻繁項(xiàng)集挖掘，找出頻繁出現(xiàn)的離群屬性組合。

3 實(shí)驗(yàn)結(jié)果與結(jié)論

Aggarwal[9]認(rèn)為評(píng)價(jià)一個(gè)離群點(diǎn)檢測(cè)方法的好壞，可以通過(guò)在給定的數(shù)據(jù)集上來(lái)運(yùn)行該方法，并且計(jì)算在由該方法所找出的離群點(diǎn)中，真正的離群點(diǎn)所占據(jù)的比例，比例越高，則表明該方法的性能越好。本文使用兩個(gè)數(shù)據(jù)集對(duì)所提出的方法進(jìn)行測(cè)試分析，并分別用該評(píng)價(jià)方法對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)。

數(shù)據(jù)1 使用UCI網(wǎng)站的Abalone數(shù)據(jù)，該數(shù)據(jù)包含4177個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)有9個(gè)屬性，分別為性別、長(zhǎng)度、直徑、高度、全重、肉重、可食部分重量、殼重和年輪數(shù)。本文將該數(shù)據(jù)集中年輪數(shù)為10圈的成年雄性鮑魚(yú)以及幼齡鮑魚(yú)數(shù)據(jù)取出作為測(cè)試數(shù)據(jù)集，即數(shù)據(jù)包含兩個(gè)類，一類是成年雄性鮑魚(yú)，另一類維幼齡鮑魚(yú)，其中幼齡鮑魚(yú)數(shù)據(jù)即為離群點(diǎn)。根據(jù)找出的離群點(diǎn)數(shù)據(jù)來(lái)分析區(qū)分相同年輪數(shù)的鮑魚(yú)中成年雄性和幼仔鮑魚(yú)的屬性。

本實(shí)驗(yàn)設(shè) s=25，α =4‰，ε =0.6，通過(guò)對(duì)數(shù)據(jù)第二維至第八維(第一維是預(yù)測(cè)維，第九維年輪數(shù)都為10，故不用計(jì)算KNN距離)KNN距離的計(jì)算，得到KNN直方圖，以長(zhǎng)度屬性為例，如圖1所示。

圖1 長(zhǎng)度屬性KNN直方圖

通過(guò)直方圖以及算法分析得到每個(gè)離群點(diǎn)以及離群維的對(duì)應(yīng)關(guān)系表，如表1所示。

表1 離群點(diǎn)以及離群維的對(duì)應(yīng)關(guān)系表

對(duì)該離群點(diǎn)-離群維關(guān)系對(duì)應(yīng)表進(jìn)行FP分析以發(fā)現(xiàn)離群維之間的關(guān)系如表2所示。

表2 Abalone數(shù)據(jù)結(jié)果分析表

其中屬性2為長(zhǎng)度，屬性3為直徑，屬性5為毛重，屬性8為殼重，經(jīng)查詢可得索引號(hào)為295-297的離群點(diǎn)為幼齡鮑魚(yú)，其離群屬性主要為長(zhǎng)度和直徑，由此可知相同年輪的成年鮑魚(yú)和幼齡鮑魚(yú)仔長(zhǎng)度和直徑上相差較大;其它離群數(shù)據(jù)點(diǎn)為相同年輪數(shù)的成年雄性鮑魚(yú)中的離群鮑魚(yú)，它們主要的離群屬性為毛重和殼重，由此可知這些離群的成年鮑魚(yú)是因?yàn)椤绑w重超標(biāo)”才被“孤立”。

實(shí)驗(yàn)結(jié)果評(píng)價(jià)如表3所示。

表3 Abalone數(shù)據(jù)實(shí)驗(yàn)結(jié)果評(píng)價(jià)表

數(shù)據(jù)2 使用UCI網(wǎng)站的SPECTF Heart Data Set，該數(shù)據(jù)包含265個(gè)數(shù)據(jù)，45個(gè)維，每個(gè)數(shù)據(jù)描述一個(gè)病人的心臟診斷數(shù)據(jù)，其中第一維是綜合診斷結(jié)果，由一個(gè)二進(jìn)制數(shù)0或者1表示，其中0表示不正常，1表示正常，即本數(shù)據(jù)集包含兩個(gè)類，一類數(shù)據(jù)為“心臟正?！?，另一類為“心臟不正?！?，數(shù)據(jù)中不正常數(shù)據(jù)即為離群點(diǎn)。實(shí)驗(yàn)找出這些離群點(diǎn)并分析病人的哪些屬性不正常則可判定心臟不正常。

本實(shí)驗(yàn)設(shè) s=25，α=2%，ε=0.6，以第 26維KNN直方圖為例，如圖2所示。

圖2 第26維KNN直方圖

通過(guò)直方圖以及算法分析得到每個(gè)離群點(diǎn)以及離群維的對(duì)應(yīng)關(guān)系表，如表4所示。

表4 離群點(diǎn)-離群維對(duì)應(yīng)關(guān)系表

對(duì)該離群點(diǎn)-離群維關(guān)系對(duì)應(yīng)表進(jìn)行FP分析以發(fā)現(xiàn)離群維之間的關(guān)系如表5所示。

表5 SPECTF Heart Data Set數(shù)據(jù)實(shí)驗(yàn)結(jié)果分析表

經(jīng)數(shù)據(jù)分析，實(shí)驗(yàn)結(jié)果中索引號(hào)174-177對(duì)應(yīng)的數(shù)據(jù)為心臟不正常的病人數(shù)據(jù)，主要在F7R、F16R、F16S、F17R、F17S以及F22R屬性出現(xiàn)異常從而被診斷為心臟病;其余數(shù)據(jù)顯示出這些病人雖在某些指標(biāo)上數(shù)據(jù)異常，但是對(duì)心臟健康影響不大，其中F3R、F11R、F10R、F13R以及F2S屬性上出現(xiàn)問(wèn)題的較多。

實(shí)驗(yàn)結(jié)果評(píng)價(jià)表如表6所示。

表6 SPECTF Heart Data Set數(shù)據(jù)實(shí)驗(yàn)結(jié)果評(píng)價(jià)表

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

實(shí)驗(yàn)表明，本文提出的離群點(diǎn)挖掘方法能有效地挖掘出數(shù)據(jù)集中的稀有類即離群點(diǎn)，并且除了全局離群點(diǎn)之外，也能找出隱形離群點(diǎn)，用FP增長(zhǎng)算法對(duì)離群點(diǎn)的離群維進(jìn)行分析，得出離群維之間的關(guān)聯(lián)規(guī)則，從而合理地解釋了離群點(diǎn)的物理意義;實(shí)驗(yàn)結(jié)果的準(zhǔn)確度分析說(shuō)明挖掘結(jié)果準(zhǔn)確有效，本方法具有很好的應(yīng)用價(jià)值。

[1]Hawkins D.Identifications of Outliers[M].London:Chapmanand Hall，1980.

[2]薛安榮，姚琳，鞠時(shí)光，等.離群點(diǎn)挖掘方法綜述[J].計(jì)算機(jī)科學(xué)，2008，35(11):13-18，27.

[3]Rousseeuw P J，Leroy A M.Robust Regression and Outlier Detection[M].New York:John Wiley＆Sons，1987.

[4]Johnson T，Kwok I，Ng R T.Fast computation of 2-dimensional depth contours[C]//Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining.New York:AAAI Press，1998:224-228.

[5]Jain A K，Murty M N，F(xiàn)lynn P J.Data clustering:A review[J].ACM Computing Surveys，1999，31(3):264-323.

[6]Breunig M M，Kriegel H P，Ng R T，et al.LOF:Identif-ying density-based local outliers[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data.Dallas:ACM Press，2000:93-104.

[7]Knorr E，Ng R.Algorithms for mining distance based outliers in large datasets[C]//Proceedings of the 24th VLDB Conference.New York:Morgan Kaufmann，1998:392-403.

[8]Beyer K，Goldstein J，Ramakrishnan R.When is nearest neighbours meaningful?[C]//Proceedings of the 7th International Conference on Data Theory.1999:217-235.

[9]Aggarwal C C，Yu P.Outlier detection for high dimensional data[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data.Santa Barbara，2001:37-47.

[10]Aggarwal C C.Redesigning distance functions and distance based applications for high dimensional data[J].SIGMOD Record Date，2001，30(1):13-18.

[11]Angiulli F，Pizzuti C.Outlier mining in large high-dimensional data sets[J].IEEE Trans.Knowledge and Data Eng.，2005，17(2):203-215.

[12]Angiulli F，Basta S，Pizzuti C.Distance based detection and prediction of outlier[J].IEEE Trans.Knowledge and Data Eng.，2006，18(2):145-160.

[13]Sanghamitra B，Santanu S.A genetic approach for efficientoutlier detection in projected space[J].Pattern Recognition，2008，41(4):1338-1349.

[14]Jiawei Han，Micheline Kamber.Data Mining:Concepts and Techniques，Second Edition[M].Beijing:China Machine Press，2009.

[15]Yu Dantong，Gholamhosein S，Zhang Aidong.FindOut:Finding outliers in very large data sets[J].Knowledge and Information Systems，2002，4(4):387-412.

[16]Mohamed Bouguessa，Shengrui Wang.Mining projected clusters in high-dimensional spaces[J].IEEE Trans.Knowledge and Data Eng.，2009，21(4)507-522.

[17]Tan Pangning，Michael S，Vipin K.Introduction to Data Mining[M].New York:Addison Wesley，2006.

[18]許龍飛，熊君麗.基于粗糙集的高維空間離群點(diǎn)發(fā)現(xiàn)算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2004，40(7):58-60.

[19]Knorr E M，Ng RT.Algorithms for mining distance-based outliers in large datasets[C]//Proceedings of the 24th International Conference on Very Large Bases.New York，NY，1998.

[20]Markus MBreunig，Hans-Peter Kriegel.LOF:Identifying density-based local outliers[C]//Proceedings of ACM SIGMOD 2000 International Conference on Management of Data.Dalles，TX，2000:93-104.