基于密度劃分的離群點檢測算法

魏 龍，王 勇

(1.西北工業(yè)大學計算機學院，陜西 西安 710129;2.西北工業(yè)大學理學院，陜西 西安 710129)

0 引言

離群點挖掘(Outliers Mining)是數(shù)據(jù)挖掘領(lǐng)域中的一項重要技術(shù)，其目標是發(fā)現(xiàn)數(shù)據(jù)集中不同于大部分的少量數(shù)據(jù)對象，這些數(shù)據(jù)對象也被稱為異常點(Abnormal Points)或孤立點(Isolated Points)。Hawkins 最早給出離群點的本質(zhì)性定義:離群點是數(shù)據(jù)集中與眾不同的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)并非偏差，而是產(chǎn)生于完全不同的機制［1］。

離群點通常在數(shù)據(jù)預(yù)處理過程中被認為是噪聲或異常值而清理，許多挖掘算法和任務(wù)也都試圖降低離群點的影響，甚至完全排除它們。然而，由于離群點既有可能是噪聲信息也有可能是有用信息［2］，隨意刪除孤立數(shù)據(jù)可能導致有用信息的丟失，不關(guān)注孤立數(shù)據(jù)的產(chǎn)生原因可能產(chǎn)生更多的異常情況。在諸多領(lǐng)域中，人們更關(guān)注與大多數(shù)據(jù)不同的特殊數(shù)據(jù)，試圖挖掘隱含其中的知識和信息。例如飛機性能統(tǒng)計數(shù)據(jù)中的一個離群點可能意味著飛機發(fā)動機的一個設(shè)計缺陷;地理圖像上的一個離群點可能標志著一個危險對象(如埋藏生化武器);網(wǎng)絡(luò)系統(tǒng)中的一個離群點還可能是對某個惡意入侵的精確定位。隨著研究進一步深入，離群點挖掘還可應(yīng)用于信用卡欺詐、金融審計、網(wǎng)絡(luò)監(jiān)控、電子商務(wù)、故障檢測、惡劣天氣預(yù)報、醫(yī)藥研究、客戶異常行為檢測和職業(yè)運動員成績分析等［3］。所以，通過離群點檢測發(fā)現(xiàn)和利用其中有價值的信息，具有非常重要的意義。2D 密度不均勻數(shù)據(jù)點分布示意圖如圖1 所示。

圖1 2D 密度不均勻數(shù)據(jù)點分布示意圖(橫坐標為二維數(shù)據(jù)X 維的值，縱坐標為Y 維的值)

迄今為止，離群點挖掘算法的研究已經(jīng)取得了廣泛的成果，而在基于聚類的離群點挖掘算法中，DBSCAN 算法［4］因可以聚類任意形狀的簇而被廣泛研究應(yīng)用，現(xiàn)已基于這一算法的基本思路而提出了許多改進算法。第一類改進算法主要是提高算法效率:基于密度的聚類算法(CUCD)［5］，能根據(jù)數(shù)據(jù)分布計算出來虛擬的點作為核心對象，能夠較好地代表數(shù)據(jù)空間，最后通過合并鄰近核心對象產(chǎn)生聚類，但該算法對局部離群點不夠敏感。張衛(wèi)旭等人根據(jù)數(shù)據(jù)核心距離(使數(shù)據(jù)成為核心點的最小距離)進行排序，之后對這些數(shù)據(jù)簇類進行掃描，再按照LOF 算法判斷是否為離群點［6］，該算法減少了查詢的復雜度。Dongmei Ren 等人提出的算法RDF［7］，根據(jù)相對密度系數(shù)先剪枝，再進行孤立點檢測，提高了效率，但準確性降低。第二類改進算法主要是優(yōu)化聚類過程中的簇中心點選擇:基于密度算法優(yōu)化初始聚類的改進K-means 算法［8］，選擇相互距離最遠的K 個處于高密度區(qū)域的點作為初始聚類中心，減少了因初始聚類中心的不同而造成的誤差，使得聚類更加精準;汪中等人在密度敏感的相似度量基礎(chǔ)上設(shè)計出一種新的基于密度的初始化方法，并根據(jù)評價函數(shù)自動生成最優(yōu)聚類數(shù)目［9］。第三類改進算法主要是優(yōu)化混合屬性對象間的相似度量:基于密度的局部離群點檢測算法DLOF［10］，該方法通過引入信息熵用于確定各對象的離群屬性，在計算各對象之間的距離時采用加權(quán)距離，并給離群屬性較大的權(quán)重，從而提高離群點的檢測的準確度。包小兵等人提出了一種基于密度的局部離群點檢測算法ESLOM［11］，引入信息熵確定數(shù)據(jù)對象的離群屬性，并對對象距離采用加權(quán)距離，以降低屬性差異帶來的誤差。Breuning M M 用局部孤立系數(shù)LOF(數(shù)據(jù)點鄰域的平均可達密度和數(shù)據(jù)點自身的可達密度之比)表示點的孤立程度［12］，但參數(shù)不容易確定。以上幾類改進方法仍然對密度分布不均勻數(shù)據(jù)挖掘效果不理想，并且需要反復實驗來選擇合適的初始參數(shù)，算法均有一定的局限性和改進空間。

基于上述的考慮，本文提出基于密度劃分的離群點檢測算法DD-DBSCAN。

1 DD-DBSCAN 算法

1.1 離群點定義

離群點挖掘可以被形式化地描述:給出n 個數(shù)據(jù)點或?qū)ο蟮募?，及預(yù)期的離群點數(shù)目k，發(fā)現(xiàn)與剩余的數(shù)據(jù)相比差異是顯著的、異常的或不一致的前k個對象［13］。在DD-DBSCAN 算法中，有2 類數(shù)據(jù)是離群點:第一類是全局離群點，即點最小距離(如1.2節(jié)定義7 所示)最大的前N 個點為離群點;第二類是局部離群點，即在其所在簇中Eps 鄰域內(nèi)，點的個數(shù)小于MinPts 這個閾值或者Eps 鄰域內(nèi)沒有核心點的點為離群點。

1.2 相關(guān)概念

本節(jié)對本文所提算法用到的概念進行描述。假設(shè)P、Q 為m 維空間的任意2 個對象，有:

那么，P、Q 之間的歐幾里德距離(以下簡稱距離)表示為:

圖2 DD-DBSCAN 算法相關(guān)概念示意圖

以二維數(shù)據(jù)為例說明相關(guān)定義，如圖2 所示。其中M、N 表示整個數(shù)據(jù)集中2 個不同的簇，其中分別包含m、n 個點。則:

任意一點Mi 表示為:

圖2 中任意2 點Mi、Mj 間的距離為:

定義1 核心對象。點的Eps 鄰域內(nèi)的點的個數(shù)大于等于MinPts 這個閾值。

定義2 邊界對象。點本身不是核心對象，但其Eps 鄰域內(nèi)包含至少一個核心對象。

定義3 直接密度可達。P 是核心點，Q 在P 的Eps 鄰域內(nèi)，那么Q 由點P 直接密度可達。

定義4 密度可達。在給定數(shù)據(jù)集中存在一個對象鏈P(1)、P(2)、...、P(n)，P(1)=Q，P(n)=P，如果P(i +1)由P(i)直接密度可達，則稱P 從Q 密度可達，密度可達是非對稱的。

定義5 簇。由任意一個核心點對象開始，從該對象密度可達的所有對象構(gòu)成一個簇。

定義6 離群點。不能被劃分到任意一個簇中的點(不是核心對象，也不由任一點直接密度可達的對象)。

定義7 點最小距離。點P 距離其在同一個集合中的各個點間距離的最小值，記為MinDp。

在圖2 中，點M2 在簇M 中的最小距離為:

定義8 簇間距離。2 個簇S、T 中距離最近的點之間的距離，記為ClusterD(S，T)。

在圖2 中，簇M 和N 的簇間距離為:

圖3 DD-DBSCAN 算法中“定義9-簇密度”概念示意圖

定義9 簇密度。簇S 中各個點MinD 的平均值，記為ClusterDensity(S)(如圖3 所示，圖中簇M 的簇密度即為以該簇各對象Mi 為頂點，以各對象之間的距離為邊組成無向完全圖G，然后以該圖生成最小生成樹T 的各邊加權(quán)平均值)。

在圖3 中，簇M 的簇密度為:

定義10 簇內(nèi)最大(最小)距離。簇S 內(nèi)各個點MinD 的最大值(最小值)，記為MaxDCS(MinDCS)。

在圖3 中，簇M 內(nèi)最大、最小距離分別為:

1.3 算法思路

如圖4 所示，就像地圖上的等高線一樣，等高線之間距離大小即不同的疏密程度代表了地形地貌的陡緩程度。一般情況下，離群點就是指“遠離”大部分數(shù)據(jù)的點，換句話就是指“鄰居”數(shù)量較少的點，圖4 中點a 至e 相對于簇X、Y、Z 內(nèi)的點來說就是離群點。一個數(shù)據(jù)集經(jīng)過聚類挖掘后，簇核心點(即核心對象)的鄰域必然是數(shù)據(jù)分布相對密集的區(qū)域，而邊界點(即邊界對象)所在區(qū)域數(shù)據(jù)分布相對稀疏;在數(shù)據(jù)稠密的簇內(nèi)，數(shù)據(jù)點距離其最近點的距離(即點MinD 值)的平均值(即簇ClusterDensity 值)較小，反之較大。由此易知，在圖4 中，Y 區(qū)域所構(gòu)成的簇與Z 區(qū)域所構(gòu)成的簇相比，其ClusterDensity 值明顯較大。

圖4 DD-DBSCAN 算法思路示意圖

在一個數(shù)據(jù)集中如果有N 個全局離群點，那么這些數(shù)據(jù)必然也是其MinD 值最大的點。圖4 中，與點a 至e 最近點的距離明顯要大于其它的點。在去除了全局離群點的一組數(shù)據(jù)中，如果在各個簇內(nèi)，一個點在各個點平均最小距離和的μ 倍鄰域內(nèi)，點的個數(shù)達不到MinPts 這個閾值，那么這個點為離群點，這部分點主要集中在簇的邊緣區(qū)域。

基于密度劃分的離群點檢測算法DD-DBSCAN就是根據(jù)以上思路設(shè)計，其實現(xiàn)步驟為:1)計算各個點之間的距離(如式(3)所示采用歐氏距離)，并且按照從小到大的順序排列，然后依這個順序?qū)?shù)據(jù)點分別合并到一個個簇中，直到剩余N 個未劃分數(shù)據(jù)為止，并且把這些未劃分的數(shù)據(jù)記為離群點;2)對第一步處理后簇密度和簇距離達到合并條件的簇進行合并，合并之后分別在各個簇中運用基于密度的聚類算法DBSCAN，分別檢測出局部離群點。

以二維數(shù)據(jù)為例，核心對象和簇的數(shù)據(jù)結(jié)構(gòu)設(shè)計如表1 所示。

表1 核心對象和簇的數(shù)據(jù)結(jié)構(gòu)

DD-DBSCAN 算法過程如下所示。

DD-DBSCAN 算法中基于密度聚類的離群點挖掘函數(shù)DBSCAN 運算過程，如下所示。

1.4 算法說明

1)數(shù)據(jù)次序?qū)z測結(jié)果的影響:本文算法在數(shù)據(jù)讀入后，首先要將數(shù)據(jù)按照點的MinD 值大小進行一次排序，在此基礎(chǔ)上進行下一步實驗。因此，檢測結(jié)果不受數(shù)據(jù)讀入次序影響，使得算法適應(yīng)性增強。

2)全局離群點的檢測:如1.3 節(jié)所述，全局離群點是其MinD 值相對比較大的點。因此，在第一步進行合并的時候，按照已經(jīng)排好的次序，將沒有被合并到任何一個簇的最后N 個點劃為離群點，這幾個離群點就是全局離群點。

3)初始簇合并的條件:經(jīng)過第一步，數(shù)據(jù)集分離了全局離群點，并且將其余MinD 值大小相近的點分別連接成了一個個簇，這些簇需要進一步合并。合并的原則是，2 個簇的ClusterD 值小于2 個簇MaxDC 值中較小的一個，并且2 個簇的ClusterDensity 相比不超過2 倍。通過這一步將數(shù)據(jù)按照密度不同，劃分成了若干個簇，使得DD-DBSCAN 算法能處理密度分布不均勻的數(shù)據(jù)。

4)參數(shù)Eps 的選擇問題:本文算法的核心是基于密度聚類的檢測算法，在第二步要分別對各個簇進行基于密度聚類算法的挖掘，需要輸入?yún)?shù)Eps。由于在經(jīng)過合并簇的步驟后，整個數(shù)據(jù)集已經(jīng)按照密度不同而被劃分成不同的簇，可分別求得各個簇的簇密度ClusterDensity，Eps 的值便以各個簇的ClusterDensity值為基數(shù)自適應(yīng)設(shè)定。實驗證明，當Eps 取值為μ倍的簇ClusterDensity 取值時，實驗結(jié)果較為理想，(在本文第2 節(jié)實驗中調(diào)整系數(shù)μ=1.25)。由于DD-DBSCAN 算法根據(jù)各個簇的簇密度，適時調(diào)整了密度聚類過程所需參數(shù)大小，無需反復輸入任何參數(shù)試驗，不需要先驗知識做支撐，提高了算法的檢測效率。

2 實驗結(jié)果與分析

為驗證本文算法的有效性，將通過實驗來比較DD-DBSCAN 算法、DBSCAN 算法各自的覆蓋率和準確率。實驗的硬件環(huán)境是:CPU Inter Core Duo 1.66 GHz，主存2 G，微軟Windows XP 操作系統(tǒng)，算法使用Java 語言編程實現(xiàn)。實驗采用了一個2D 模擬數(shù)據(jù)集和一個真實數(shù)據(jù)集Iris Plants Database［14］。

2.1 數(shù)據(jù)準備

2.1.1 2D 模擬數(shù)據(jù)集

用一組二維數(shù)據(jù)模擬密度分布不均勻的數(shù)據(jù)集，共有80 條(通過人工控制分布區(qū)域和數(shù)量，以Java編程語言產(chǎn)生隨機數(shù)的函數(shù)實現(xiàn))，其中加入了20 條記錄作為離群記錄。數(shù)據(jù)基本分布情況如圖5 所示。

圖5 2D Simulated Database 分布示意圖(圖中“□”標識的為離群點，“* ”為其余點)

2.1.2 Iris Plants Database

Iris Plants Database 來自UCI 網(wǎng)站，是美國加州大學信息與計算機科學系的Iris 數(shù)據(jù)集，夏魯寧等人也用此數(shù)據(jù)做對比實驗來驗證聚類算法的效率［15］。它以鳶尾花的特征作為數(shù)據(jù)來源，來自美國UCI 標準數(shù)據(jù)集，該數(shù)據(jù)被廣泛應(yīng)用于聚類分析和分類分析實驗中。數(shù)據(jù)集包含150 條記錄，分為setosa、versicolor、virginica 3 個類，每類50 個數(shù)據(jù)，每個數(shù)據(jù)包含4 個獨立的屬性，它們分別是花萼和花瓣的長度和寬度，這些屬性變量測量植物的花朵，比如萼片和花瓣的長度等。本實驗在原始數(shù)據(jù)集的基礎(chǔ)上，隨機刪除其中70 條，再加入20 條記錄作為離群點，使得數(shù)據(jù)總計為100 條記錄。

2.2 性能指標

根據(jù)給定數(shù)據(jù)集和實驗結(jié)果，計算由此方法所挖掘出的離群點個數(shù)占數(shù)據(jù)集中離群點數(shù)的比例，比例越接近1，則表明此算法精度越高，性能越好;計算算法檢測出的真正的離群點個數(shù)占所檢測出的全部離群點數(shù)的比例，比例越高，則表明算法準確度越高，性能越好。2 個指標同時偏高的算法，為性能較好的算法。本實驗采用以下2 個指標對算法進行評價，具體算法如下。其中，OA是算法檢測到的離群點集合，OB是數(shù)據(jù)集中所有真實離群點數(shù)目的集合［16］。

2.2.1 覆蓋率(Coverage)

覆蓋率C 是指檢測到真實離群點的數(shù)目與所有真實離群點數(shù)目的比值。

2.2.2 準確率(Precision)

準確率P 是指檢測到真實離群點的數(shù)目與檢測到的離群點數(shù)據(jù)數(shù)目的比值。

2.3 性能分析

文獻［4］DBSCAN 算法描述中給出的參數(shù)選擇方法是設(shè)定minPts=4，通過觀察法來判斷Eps。本節(jié)對于DD-DBSCAN 算法和DBSCAN 算法的對比實驗中，對于基于密度聚類的部分，均設(shè)定minPts=4，分別通過自適應(yīng)變化和人工變更參數(shù)Eps 來驗證2個算法的差別。

2.3.1 2D 模擬數(shù)據(jù)上的實驗結(jié)果

因為二維模擬數(shù)據(jù)集方便在圖上顯示，分別運用2 種算法挖掘后，其結(jié)果顯示如圖6～圖10 所示，結(jié)果的具體數(shù)據(jù)如表2 所示。其中，圖6～圖9 所示的為運用DBSCAN 算法挖掘結(jié)果示意圖，圖10 為運用DD-DBSCAN 算法挖掘結(jié)果示意圖，圖中符號“□”表示檢測出的離群點，其余符號“* ”為非離群點。

圖6 在2D 模擬數(shù)據(jù)集上實驗1(MinPts=4，Eps=10，離群點數(shù)=55)

圖7 在2D 模擬數(shù)據(jù)集上實驗2(MinPts=4，Eps=20，離群點數(shù)=38)

圖8 在2D 模擬數(shù)據(jù)集上實驗3(MinPts=4，Eps=25，離群點數(shù)=20)

通過圖6～圖10 可以看到，運用DBSCAN 算法對數(shù)據(jù)進行挖掘時，在參數(shù)MinPts 固定的情況下，當Eps 取值越小時:由于能夠符合核心點和與核心點密

圖9 在2D 模擬數(shù)據(jù)集上實驗4(MinPts=4，Eps=30，離群點數(shù)=10)

圖10 DD-DBSCAN 算法挖掘結(jié)果示意

度相連的點越來越少，使得檢測出的離群點越來越多，如圖6 所示，這些離群點中包括數(shù)據(jù)集中實際存在的全局離群點、一些遠離簇核心點的局部離群點以及數(shù)據(jù)密度較稀疏的區(qū)域，也就是說該算法能夠檢測出離群點，但卻存在過多的誤判，即把本不是離群點的稀疏區(qū)域也判定為離群點。因此，根據(jù)第2.2 節(jié)定義，覆蓋率C 較高，但是準確率P 較低。當Eps 取值越大時，DBSCAN 算法檢測到的離群點越來越少，如圖9 所示，此時只能檢測到部分全局離群點，而無法準確檢測到局部離群點，因此，覆蓋率C 下降，而準確率P 上升。從實驗看出，無論2 個參數(shù)怎么調(diào)節(jié)，DBSCAN 算法始終無法有效處理數(shù)據(jù)密度差異較大的數(shù)據(jù)。而如圖10 所示，由于DD-DBSCAN 算法通過密度稀疏將數(shù)據(jù)集“分而治之”，能夠在各個簇中分別自適應(yīng)地調(diào)整參數(shù)，使得算法的檢測結(jié)果較為理想，能夠有效檢測出局部和全局離群點。

2.3.2 Iris 數(shù)據(jù)集上的實驗結(jié)果

在超過二維的數(shù)據(jù)集Iris 上的實驗結(jié)果，如表2所示。

表2 DD-DBSCAN 算法與DBSCAN 算法在2 種數(shù)據(jù)上的挖掘結(jié)果對比

通過表2 可以看到，運用DBSCAN 算法進行檢測時，當聚類半徑Eps 值逐漸增大時，檢測出的離群點數(shù)不斷減少，算法不能有效地檢測出所有的離群點，覆蓋率C 呈下降趨勢;當聚類半徑Eps 值逐漸減小時，檢測出的離群點數(shù)量不斷增多，算法誤判的數(shù)量也不斷增多，導致準確率P 呈下降趨勢。因此，DBSCAN 需要多次輸入?yún)?shù)才能得到一個較為理想的結(jié)果，而且參數(shù)依賴人工輸入，無法自動適應(yīng)數(shù)據(jù)變化，使得算法的效率比較低，局限性較大。而本文提出的DD-DBSCAN 算法優(yōu)點明顯，能夠在一次輸入數(shù)據(jù)和參數(shù)后，得到理想的檢測結(jié)果，無需反復輸入?yún)?shù)進行試驗，算法能夠有效處理密度不均勻的數(shù)據(jù)集。在超過二維的數(shù)據(jù)上的實驗結(jié)果表明，DD-DBSCAN 能夠獲得較高的覆蓋率和準確率，具有較好的魯棒性。

3 結(jié)束語

本文提出了一種基于密度劃分的離群點檢測算法DD-DBSCAN，并在2D 模擬數(shù)據(jù)集和Iris Plants 數(shù)據(jù)集上進行了檢驗。實驗結(jié)果表明，本文算法相比DBSCAN 算法能夠有效處理密度不均勻的數(shù)據(jù)，不需要用戶設(shè)置參數(shù)MinPts 和Eps，通過自適應(yīng)的方法自動確定參數(shù)，算法的精確度和正確率都比較高。下一步的研究方向為:基于DD-DBSCAN 算法，進行不確定數(shù)據(jù)流上的離群點檢測算法研究，并且改進對象之間的相似性度量方法以適應(yīng)高維混合屬性數(shù)據(jù)特征，使得算法能夠處理動態(tài)變化的大規(guī)模數(shù)據(jù)集。

［1］Hawkins D.Identification of Outliers［M］.London:Chapman and Hall，1980.

［2］Knorr M E，Ng R T，Tucakov V.Distance-based outliers:Algorithms and applications［J］.The VLDB Journal，2000，8(3-4):237-253.

［3］范潔.數(shù)據(jù)挖掘中孤立點檢測算法的研究［D］.長沙:中南大學，2009.

［4］Ester M，Kriegel H，Sander J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise［C］// Proceeding of the 2nd Internatioanal Conference on Knowledge Discovery and Data Mining.1996:226-231.

［5］王桂紅.基于密度的聚類算法研究［J］.泉州師范學院學報(自然科學版)，2009，27(2):44-49.

［6］張衛(wèi)旭，尉宇.基于密度的局部離群點檢測算法［J］.計算機數(shù)字工程，2010，38(10):11-14.

［7］Ren Dongmei，Wang Baoying，Pcrrizo W.RDF:A density-based outlier detection method using vertical data representation［C］// Proceedings of the 4th IEEE International Conference on Data Mining.2004:503-506.

［8］傅德勝，周辰.基于密度的改進K 均值算法及實現(xiàn)［J］.計算機應(yīng)用，2011，31(2):432-434.

［9］汪中，劉貴全，陳恩紅.一種優(yōu)化初始中心點的K-means算法［J］.模式識別與人工智能，2009，22(2):299-304.

［10］胡彩平，秦小麟.一種基于密度的局部離群點檢測算法DLOF［J］.計算機研究與發(fā)展，2010，47(12):2110-2116.

［11］包小兵，翟素蘭，程蘭蘭.基于信息熵加權(quán)的局部離群點檢測算法［J］.計算機技術(shù)與發(fā)展，2012，22(9):59-65.

［12］Breuning M M，Kriegel H P，Ng R T，et al.LOF:Identifying sensity-based local outliers［C］// Proceedings of ACMSIGMOD International Conference on Management of Data，2000.2000:93-104.

［13］王晶，夏魯寧，荊繼武.一種基于密度最大值的聚類算法［J］.中國科學院研究生院學報，2009，26(4):539-548.

［14］MacQueen J B.Some methods for classification and analysis of multivariate observations［C］// Proceedings of the 5th Berkeley Symposium on Mathematics，Statistics and Probabilty.1967:281-297.

［15］夏魯寧，荊繼武.SA-DBSCAN:一種自適應(yīng)基于密度聚類算法［J］.中國科學院研究生院學報，2009，26(4):530-538.

［16］唐向紅，李國徽，楊觀賜.快速挖掘數(shù)據(jù)流中離群點［J］.小型微型計算機系統(tǒng)，2011，32(1):9-16.