(福建江夏學(xué)院 電子信息與科學(xué)學(xué)院， 福建 福州 350108)

離群點(diǎn)數(shù)據(jù)被認(rèn)為是與其他觀測值有較大差別、懷疑由不同機(jī)制產(chǎn)生的異常觀測值，這些異常數(shù)據(jù)可能來源于不同的類、自然變異，以及數(shù)據(jù)測量或收集誤差?，F(xiàn)實(shí)生活中，由于異常事例常常隱藏著有價(jià)值和出乎意料的知識，挖掘異常事例及離群數(shù)據(jù)往往比常規(guī)情況更加令人關(guān)注。離群點(diǎn)的檢測作為目前數(shù)據(jù)挖掘技術(shù)中重要的研究領(lǐng)域，廣泛應(yīng)用于包括信用卡欺詐發(fā)現(xiàn)、網(wǎng)絡(luò)安全入侵檢測、生態(tài)系統(tǒng)失調(diào)預(yù)測、犯罪行為發(fā)現(xiàn)及預(yù)防醫(yī)療檢查等眾多行業(yè)領(lǐng)域研究[1]。此外，離群點(diǎn)檢測也常用于檢測數(shù)據(jù)集中的異常樣本，剔除“臟數(shù)據(jù)”以提高如聚類和分類計(jì)算的數(shù)據(jù)分析質(zhì)量。

目前異常檢測數(shù)據(jù)挖掘主要包含基于模型、密度、聚類和距離等技術(shù)?；谀Ｐ?distribution-based)的檢測技術(shù)通過估計(jì)概率分布的參數(shù)來創(chuàng)建數(shù)據(jù)分布模型，不能很好地與模型相擬合的對象則被判別為異常數(shù)據(jù)。該技術(shù)不適用于數(shù)據(jù)的統(tǒng)計(jì)分布事先未知或沒有訓(xùn)練數(shù)據(jù)可用的情況?；诿芏?density-based)的檢測技術(shù)通過計(jì)算每個(gè)數(shù)據(jù)對象的密度評估值，將低密度區(qū)域中的數(shù)據(jù)對象檢測為離群點(diǎn)，如LOF算法[2]、MDEF[3]、COF[4]和NLOF[5]等算法，這些算法可適用于具有不同密度區(qū)域的數(shù)據(jù)集，但對初始參數(shù)的選擇非常敏感?；诰垲?clustering-based)的檢測技術(shù)通過執(zhí)行聚類操作，將遠(yuǎn)離其他簇的小簇標(biāo)識為離群對象，或使用目標(biāo)函數(shù)來評估對象屬于簇的程度，根據(jù)離群點(diǎn)評估值隔離異常數(shù)據(jù)?；诰嚯x即鄰近性度量(distance-based)的技術(shù)，不需要事先了解數(shù)據(jù)分布模式，將遠(yuǎn)離大部分其他對象的對象判定為異常數(shù)據(jù)，最常見的方法是Ramaswamy等人[6]提出的k-近鄰(k-th nearest neighber)離群挖掘算法，當(dāng)某個(gè)數(shù)據(jù)對象與其近鄰數(shù)據(jù)對象的距離很大時(shí)，則認(rèn)為該數(shù)據(jù)對象位于稀疏區(qū)域并成為離群對象。該算法通過構(gòu)造KNN圖，依據(jù)每個(gè)數(shù)據(jù)點(diǎn)到kth最近鄰數(shù)據(jù)點(diǎn)的距離進(jìn)行排序，將排序列表中距離數(shù)值較大的若干數(shù)據(jù)點(diǎn)視為離群點(diǎn)。

在眾多離群挖掘算法中，基于距離和密度的離群點(diǎn)挖掘算法是最有代表性和最有效的挖掘方法。

1 問題的提出

使用KNN算法對圖1所示數(shù)據(jù)集進(jìn)行離群點(diǎn)檢測，當(dāng)參數(shù)k取值為7時(shí)，數(shù)據(jù)點(diǎn)A和B將獲得相同的離群評估值，A、B數(shù)據(jù)點(diǎn)的k近鄰距離均為p，則被視作相同等級的離群點(diǎn)；而當(dāng)k取值為8時(shí)，該方法誤將A視作比B更強(qiáng)的離群點(diǎn)。從直觀角度上不難看出，B比A更趨向于成為離群點(diǎn)。若離群檢測算法僅從距離角度考慮離群評估，存在著明顯的缺陷。

文獻(xiàn)[7]提出的算法將數(shù)據(jù)點(diǎn)與其k個(gè)最近鄰數(shù)據(jù)點(diǎn)的距離之和作為判別離群對象的評估值以實(shí)現(xiàn)KNN算法的改進(jìn)。由于數(shù)據(jù)點(diǎn)B遠(yuǎn)離于其他數(shù)據(jù)點(diǎn)，其與k近鄰距離之和即離群評估值大于數(shù)據(jù)點(diǎn)A的離群評估值，此改進(jìn)算法雖然可以解決KNN算法對于圖1所示數(shù)據(jù)集存在的離群檢測問題，然而對于圖2所示的密度差異較大的簇集，無論采用k-近鄰距離或是求距離之和的方法，都只能檢測出全局離群點(diǎn)D，而無法識別密集簇附近的局部離群點(diǎn)C，且很可能誤將稀疏簇中的大部分?jǐn)?shù)據(jù)判定為離群對象。因此，基于距離的離群檢測算法適用于密度相近的簇集，對于稀疏各異的簇集，檢測錯(cuò)誤率將大幅提高。

圖1 具有相同離群評估值的兩個(gè)數(shù)據(jù)對象A和B(k=7)Fig.1 Data A and B with equal outlier evaluation values

圖2 密度差異較大的兩個(gè)簇集Fig.2 Two clusters with great differences in density

Breaunig等人[2]提出的LOF(local outlier factor)算法通過引入局部離群因子來評估對象相對于鄰域的孤立程度，對分布密度相差較大的簇集有較好的檢測結(jié)果。該算法不從全局的角度考慮數(shù)據(jù)對象的離群特性，而是計(jì)算各數(shù)據(jù)對象與其最近的k個(gè)鄰居的局部密度比，以獲取離群系數(shù)。局部密度較大的數(shù)據(jù)對象具有較小的LOF評估值，LOF評估值較大的數(shù)據(jù)對象則被判別為離群點(diǎn)。如圖2所示的數(shù)據(jù)集中，由于離群點(diǎn)C和D都與其鄰近的數(shù)據(jù)點(diǎn)有較大的密度差異，若參數(shù)選擇得當(dāng)，使用LOF算法可以有效識別這兩個(gè)離群點(diǎn)。然而，對于數(shù)據(jù)點(diǎn)G和C來說，由于他們的最近鄰密度對象均屬于密集簇(近鄰數(shù)據(jù)點(diǎn)的密度相近)，且數(shù)據(jù)對象C比G更靠近密集簇，根據(jù)LOF算法，數(shù)據(jù)對象G將獲得比C更高的離群評估值，即算法認(rèn)為G將比C更有可能成為離群點(diǎn)，很明顯地，G只是與密集簇相近的一個(gè)稀疏簇中的正常數(shù)據(jù)對象。與基于距離的離群檢測算法對比，LOF算法雖然能夠有效檢測出局部離群點(diǎn)，但當(dāng)兩個(gè)密度各異的簇集相互靠近時(shí)，該算法很容易將稀疏簇與密集簇交界的數(shù)據(jù)對象誤判為離群點(diǎn)。

綜上所述，本文提出一種新的數(shù)據(jù)對象離群評估算法，使得在密度差異大的簇集中，也能實(shí)現(xiàn)正確的離群評估。

2 基于密度和距離相結(jié)合的新型離群檢測算法CDD算法

數(shù)據(jù)對象成為離群點(diǎn)的概率大小不僅與周圍鄰居數(shù)據(jù)點(diǎn)的密度相關(guān)，還與其偏離其它數(shù)據(jù)點(diǎn)的距離大小相關(guān)，數(shù)據(jù)對象周圍鄰居密度越小、偏離鄰居數(shù)據(jù)點(diǎn)的距離越大，則成為離群點(diǎn)的可能性就越大。綜合考慮這兩方面因素，提出一種基于密度和距離相結(jié)合的新型的離群檢測算法CDD(combination of density based and distance based outlier detection algorithm)，過程描述如下：

首先基于k-近鄰構(gòu)造有向近鄰圖，其中，對鄰域的選擇沿用傳統(tǒng)經(jīng)典k-最近鄰域理論[8]。將各數(shù)據(jù)點(diǎn)作為圖的頂點(diǎn)，指向與自己最相近的k個(gè)鄰居數(shù)據(jù)點(diǎn)，如圖3所示，然后結(jié)合該數(shù)據(jù)點(diǎn)與近鄰數(shù)據(jù)點(diǎn)的距離以及該數(shù)據(jù)點(diǎn)與周圍數(shù)據(jù)的密切關(guān)系來綜合衡量其孤立的程度，獲取離群評估值，具體描述如下：

圖3 數(shù)據(jù)對象指向最鄰近的k個(gè)鄰居(k=3)Fig.3 Data pointing to k nearest neighbors (k=3)

1.2.2 觀察組 在上述服藥基礎(chǔ)下，給予患者自擬補(bǔ)腎活血方。方劑成分如下：熟地黃15 g，山茱萸15 g，山藥（炒）15 g，茯苓 15 g，薏以仁 12 g，車前草 10 g，續(xù)斷 12 g，菟絲子 15 g， 杜仲（鹽炒）20 g，黨參 15 g，玉米須 15 g，生黃芪 20 g，紅花 12 g，紫丹參 12 g，白術(shù)（炒）20 g，陳皮10 g，白茅根 20 g，川芎（酒炙）8 g。 1 劑/d，分早晚服用。共服用2個(gè)月。

k_Dist(xi)}.

當(dāng)k=3時(shí)，圖3顯示出數(shù)據(jù)集X中各數(shù)據(jù)對象與其k-最近鄰居的關(guān)系。其中，每個(gè)頂點(diǎn)xi代表一個(gè)數(shù)據(jù)矢量，每條邊都指向該對象最近的k個(gè)鄰居，即Groupk(xi)中包含的k個(gè)數(shù)據(jù)對象。

定義2令Neighk(xi)為數(shù)據(jù)集X中所有指向xi(xi∈X)的矢量對象的數(shù)量。對于?xi∈X，若xi∈Groupk(xp)(p∈[1,n])，則Neighk(xi)=Neighk(xi)+1。

Neighk(xi)從全局角度考慮數(shù)據(jù)對象xi的鄰域關(guān)系，從很大程度上評估出數(shù)據(jù)點(diǎn)xi與鄰近對象關(guān)系的密切程度。其數(shù)值越大，xi數(shù)據(jù)對象成為其它數(shù)據(jù)對象的k-近鄰的情況越多，則表示數(shù)據(jù)對象xi存在于高密度區(qū)域的概率越大，其成為離群點(diǎn)的可能性則越低；反之，對于某數(shù)據(jù)對象來說，若沒有或者極少其他數(shù)據(jù)對象的k-近鄰指向它，那么該數(shù)據(jù)對象很可能是離群點(diǎn)。如圖3所示的數(shù)據(jù)集中，對于周圍數(shù)據(jù)點(diǎn)密集的F點(diǎn)來說，其Neighk(F)值為6，而H點(diǎn)遠(yuǎn)離大部分?jǐn)?shù)據(jù)點(diǎn)使其不屬于任何對象的k-近鄰集合，Neighk(H)值為0。

定義3|Groupk(xi)|表示包含數(shù)據(jù)對象xi的k-近鄰的集合的大小，那么數(shù)據(jù)點(diǎn)xi與其k個(gè)最近鄰數(shù)據(jù)對象的平均距離為：

定義4對于給定對象的數(shù)據(jù)集X={x1,x2，…,xn}，則每個(gè)數(shù)據(jù)對象的離群評估得分可表示為：

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

3.1 模擬數(shù)據(jù)的離群檢測對比

為了較好地展現(xiàn)新算法的優(yōu)點(diǎn)，實(shí)驗(yàn)生成如圖4所示的一組模擬數(shù)據(jù)，在3個(gè)不同密度的簇集(方點(diǎn))中加入若干離群數(shù)據(jù)(圓點(diǎn))，采用KNN、LOF和CDD 3種算法實(shí)現(xiàn)離群數(shù)據(jù)的挖掘計(jì)算，最近鄰個(gè)數(shù)k取值范圍為2～8，數(shù)據(jù)挖掘的結(jié)果如圖5-圖7所示，分別顯示了在不同的k近鄰取值情況下3種算法獲得的離群評估值。圖5-圖7按離群評估值從高到低顯示出前8個(gè)數(shù)據(jù)對象，其中，橫坐標(biāo)表示k的取值，縱坐標(biāo)表示相應(yīng)的離群評估值。

圖4 仿真數(shù)據(jù)集Fig.4 Simulation dataset

圖5 KNN算法離群計(jì)算結(jié)果Fig.5 Outlier detection results of KNN algorithm

圖6 LOF算法的離群計(jì)算結(jié)果Fig.6 Outlier detection results of LOF algorithm

圖7 CDD算法離群計(jì)算結(jié)果Fig.7 Outlier detection results of CDD algorithm

從圖5可以看出，離群點(diǎn)W和R并未被KNN算法檢測出來，由于稀疏簇中的正常數(shù)據(jù)點(diǎn)(如O、T和N)的離群評估值均大于距離密集簇較近的離群點(diǎn)W和R，KNN算法并不能很好對密度差異較大的簇集進(jìn)行離群點(diǎn)的識別，實(shí)驗(yàn)結(jié)果表明稀疏簇中的所有數(shù)據(jù)的離群值都高于離群點(diǎn)W和R，僅考慮距離因素的KNN算法，錯(cuò)檢率較高。圖6中，由于數(shù)據(jù)點(diǎn)R和S的鄰近簇相同，而數(shù)據(jù)點(diǎn)R比S更靠近鄰近簇，LOF算法則作出了錯(cuò)誤的判斷，認(rèn)為正常數(shù)據(jù)點(diǎn)S的離群程度高于獨(dú)立數(shù)據(jù)點(diǎn)R。當(dāng)疏密差距較大的兩個(gè)簇集相近時(shí)，稀疏簇邊界上的數(shù)據(jù)點(diǎn)通常會被LOF算法誤判為離群數(shù)據(jù)，而新算法CDD則解決了由于互相靠近的簇集密度不均衡所帶來的邊緣數(shù)據(jù)點(diǎn)離群值錯(cuò)誤評估的問題，圖7的檢測結(jié)果顯示，由CDD算法獲得的前7位數(shù)據(jù)對象已準(zhǔn)確涵蓋本實(shí)驗(yàn)所有離群點(diǎn)，且它們的離群評估值也客觀地體現(xiàn)出了各數(shù)據(jù)點(diǎn)的離群程度。

另一方面，k-近鄰算法、LOF算法對參數(shù)k的取值具有較大的依賴性，為了獲取高質(zhì)量的離群檢測結(jié)果，需要多次調(diào)整參數(shù)k的取值，并根據(jù)現(xiàn)實(shí)經(jīng)驗(yàn)來判斷最佳的離群檢測結(jié)果。如圖6所示，隨著k值的變化，LOF算法下的各數(shù)據(jù)點(diǎn)的離群評估值也有較大的波動(dòng)，k值的選定在一定程度上影響了離群檢測結(jié)果的準(zhǔn)確性和穩(wěn)定性，而CDD算法得出的各數(shù)據(jù)點(diǎn)的離群評估值的大小排序則相對穩(wěn)定(見圖7)，離群值走勢不隨k值的變化劇烈波動(dòng)，說明CDD算法有效弱化了參數(shù)k對離群檢測結(jié)果的影響，提高離了群點(diǎn)檢測的穩(wěn)定性和準(zhǔn)確率。

3.2 真實(shí)數(shù)據(jù)集離群檢測對比

3.2.1 Lymphography數(shù)據(jù)集

Lymphography數(shù)據(jù)集包含了來源于前南斯拉夫腫瘤學(xué)研究所的148條淋巴系造影術(shù)數(shù)據(jù)，每個(gè)數(shù)據(jù)包含18個(gè)分類屬性。數(shù)據(jù)被劃分為4個(gè)簇，其中兩個(gè)簇分別包含了81和61個(gè)數(shù)據(jù)對象，而另外兩個(gè)小簇分別包含2個(gè)和4個(gè)數(shù)據(jù)對象，本實(shí)驗(yàn)將占比較小的兩個(gè)小簇中的6個(gè)數(shù)據(jù)對象作為歧異值進(jìn)行離群檢測，使用KNN、LOF和CDD 3種算法分別對該數(shù)據(jù)集實(shí)現(xiàn)數(shù)據(jù)挖掘并進(jìn)行離群檢測結(jié)果對比。各算法檢測出的離群點(diǎn)中，正確的離群點(diǎn)所占比率越高，則表示該算法性能越好[9]。

表1列出了當(dāng)最近鄰居個(gè)數(shù)k取值為5～10時(shí)，3種算法獲取的離群評估平均值排名前n位的離群數(shù)據(jù)的檢測率對比，其中，檢測率指檢測到正確的離群數(shù)據(jù)量與離群數(shù)據(jù)總量的比值。從表1可以看出，CDD算法檢測獲取的前6個(gè)離群數(shù)據(jù)對象中已包含5個(gè)正確的離群對象，檢測獲取的前8個(gè)數(shù)據(jù)對象即涵蓋了出所有離群對象，而KNN算法和LOF算法獲取的前8個(gè)離群對象中，離群檢測率僅為66.7%和88.3%；LOF算法須提取前10個(gè)離群數(shù)據(jù)才能找出所有離群點(diǎn)，KNN算法離群檢測率更低，需要提取前12個(gè)離群數(shù)據(jù)。由此可見，在Lymphography數(shù)據(jù)集上，CDD算法在離群檢測率方面明顯優(yōu)于其他兩種算法。

3.2.2 Wisconsin breast Cancer數(shù)據(jù)集

Wisconsin breastCancer乳腺癌數(shù)據(jù)集包含569組數(shù)據(jù)，每個(gè)數(shù)據(jù)對象包含32個(gè)分類屬性，其中良性腫瘤細(xì)胞特征有357例，惡性腫瘤細(xì)胞特征有212例，本實(shí)驗(yàn)將選取357個(gè)數(shù)據(jù)對象良性腫瘤細(xì)胞和部分惡性腫瘤細(xì)胞(32個(gè)數(shù)據(jù)對象)，共389個(gè)數(shù)據(jù)對象作為檢測樣本，使用3種算法分別對其進(jìn)行離群數(shù)據(jù)對象(惡性腫瘤特征數(shù)據(jù))的檢測，算法選取k值為10～15，測試對比結(jié)果如表2所示。

表1 3種算法在Lymphography數(shù)據(jù)集中的運(yùn)行結(jié)果對比Tab.1 Comparison of results of three algorithms in Lymphography dataset

表2 3種算法在Wisconsin breast Cancer數(shù)據(jù)集中的運(yùn)行結(jié)果對比Tab.1 Comparison of results of three algorithms in Wisconsin breast cancer dataset

分析實(shí)驗(yàn)結(jié)果可以看出，KNN算法和LOF算法分別需要檢測出前57個(gè)和63個(gè)離群評估值較大的數(shù)據(jù)對象，才能找到所有惡性腫瘤離群數(shù)據(jù)。算法CDD檢測出的前46個(gè)數(shù)據(jù)對象中已經(jīng)包含所有32個(gè)離群數(shù)據(jù)，而KNN和LOF算法檢測到的前46個(gè)數(shù)據(jù)中，僅分別包含27個(gè)和24個(gè)正確離群數(shù)據(jù)。因此，對于Wisconsin breast Cancer數(shù)據(jù)集，CDD算法的離群檢測有效性還是優(yōu)于KNN和LOF算法。

4 結(jié)語

本文提出的改進(jìn)算法CDD通過構(gòu)造有向鄰近圖，從簇中各數(shù)據(jù)對象的近鄰密度疏密以及分布距離大小兩方面進(jìn)行綜合考量，有效量化各數(shù)據(jù)對象的離群強(qiáng)弱程度并獲得離群對象隊(duì)列。通過在不同的數(shù)據(jù)集上的實(shí)驗(yàn)對比，結(jié)果表明新型算法的離群點(diǎn)檢測準(zhǔn)確度明顯高于k-近鄰算法及LOF算法，且有效弱化了離群算法對初始參數(shù)k取值的依賴性。

在此改進(jìn)基礎(chǔ)上，針對不同數(shù)據(jù)集的特征，進(jìn)一步研究算法以降低時(shí)間復(fù)雜度、提高算法運(yùn)行的效率，是今后要繼續(xù)研究的方向。

[1] He Zengyou， Xu Xiaofei， Deng Shengchun． Discovering cluster-based local outliers[J]． Pattern Recognition Letters，2003，24(9)：1641-1650．

[2] Breunig M， Kriegel H P， Ng R， et a1． LOF：Identilying densityhased local outliers[C]∥. Proc of the ACM SIGMOD International Conference on Management of Data，2000：93-104．

[3] Papadimitrious S， Kitawaga H， Gibbons P B， et al． LOCI： Fast outlier detection using the local correlation integral[C]∥. Proc of the 19thInternational Conference on Data Engineering，2002：315-326．

[4] Tang J， Chen Z， Fu A， et al. Enhancing effectiveness of outlier detections for low-density pattern[J]． Proceedings of the 6thPAKDD，2002,2236:535-548．

[5] 王敬華，趙新想，張國燕，等．NLOF：一種新的基于密度的局部離群點(diǎn)檢測算法[J]．計(jì)算機(jī)科學(xué)，2013，40(8)：181-185．

[6] Ramaswamy S， Rastogi R， Kyuseok S． Efficient algorithms for mining outliers from large data sets[C]∥. Proc of the ACM SIGMOD International Conference on Management of Data，2000：427-438．

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

[8] 范小剛，朱慶生，萬家強(qiáng)．基于K-近鄰樹的離群檢測算法[J]．計(jì)算機(jī)應(yīng)用研究，2015，32(3)：669-673．

[9] 周世波，徐維祥．一種基于偏離的局部離群點(diǎn)檢測算法[J]．儀器儀表學(xué)報(bào)，2014，35(10)： 2293-2297.