基于DCNDA算法的數據異常檢測

蔣 華，季 豐，王 鑫，王慧嬌

(桂林電子科技大學 計算機與信息安全學院，廣西 桂林 541000)

0 引 言

聚類分析作為數據挖掘中處理數據的重要環節之一，研究者們對聚類算法持續性、大批量的研究從未間斷，取得了豐碩的研究成果。

Marek Gagolewski等提出了一種連接標準層次聚類算法Genie[1]。Xianchao Zhang等[2]的研究中先提出了一種基于密度的算法PDBSCAN，又提出了一種基于層次密度的算法POPTICS。Singh G等提出了一種結合K均值聚類算法和分層聚類算法BIRCH特征的算法[3]。Nazari Z等提出了一種使用歐氏距離的層次聚類方法[4]。Proietti A等提出2D層次模糊聚類方法[5]。以上所提3種算法均未能有效解決層次聚類對噪音敏感問題。Kumar D等提出了一種clusiVAT算法[6]。針對自動分簇這一想法Abe R等提出了一種方法來自動估計AHC中的簇數[7]。高長元等提出了一種基于CURE聚類算法[8,9]。針對Argo浮標觀測數據數據量龐大的特點，蔣華等設計了基于MapReduce技術的Argo浮標剖面信息融合算法[10]，為利用大數據技術解決海洋數據監測問題提供了新思路。

基于上述分析，本文提出了DCNDA算法，即一種基于MeanShift核函數平移模型DBSCAN算法改進的CURE算法。MeanShift核函數平移模型自適應獲取DBSCAN參數Eps、MinPts，提高初步聚類準確率。對所有正常值數據簇進行CURE層次聚類過程中不引入收縮因子，避免收縮因子選取不當造成聚類結果偏差。不必計算代表點，進一步降低了算法時間復雜度，在篩選出的正常值簇中層次聚類，解決了CURE對異常值敏感問題，提高聚類精確度。

1 相關理論

1.1 MeanShift

MeanShift(均值位移)這一概念最早由Fukunage在1975年提出，圖1可見。MeanShift算法是一個迭代過程，首先計算出當前點的偏移均值，將該點移動到此偏移均值點處，其次以此為新的起始點，繼續移動，直至滿足最終條件。

圖1 MeanShift

圖2 MeanShift偏移過程

在給定的d維空間Rd中的n個樣本點xi,i=1,…,n，則對于x點，其MeanShift向量基本形式為

(1)

其中，指半徑為h的高維球形區域，其定義為

Sh(x)=(y|(y-x)(y-x)T≤h2)

(2)

但是，在Sh區域內，每個點對x的貢獻是一樣的。而實際上，這種貢獻與x到每個點的距離相關。對于每個樣本，其重要程度也不相同。基于這些考慮對基本MeanShift向量形式增加了核函數和樣本權重，得到改進型MeanShift向量形式

(3)

其中，G(x)是一個單位的核函數。H是一個正定的對稱矩陣，稱為帶寬矩陣。ω(xi)≥0是每個樣本的權重。Meanshift向量Mh(x)是歸一化的概率密度梯度。

1.2 核密度估計

核密度估計(kernel density estimation)是一種用于估計概率密度函數的非參數方法，在d維空間Rd中，有一組數據點x1,…,xn為獨立同分布F的n個樣本點，令其概率密度函數為f，核密度估計如下

(4)

其中，K(·)為核函數，h>0為一個平滑參數，稱為帶寬，也稱之為窗口。

核密度估計中核函數分為多種，最常用的如高斯核函數

(5)

1.3 DBSCAN算法

DBSCAN算法是一種基于密度聚類的經典算法，核心思想是一個數據點x在鄰域范圍ε內的鄰居點數量衡量該點所在空間的密度。該算法可以找出不規則形狀的cluster，事先不需要知道簇的數量。

DBSCAN算法有兩個關鍵參數Eps和MinPts，前者為定義密度時的鄰域半徑，定義核心點時的閥值，分別簡稱為ε和?。

定義1 (ε鄰域)設x∈X，X={x1,…,xn}，稱Nε(x)={y∈X:d(y,x)≤ε}為x的ε鄰域，顯然x∈Nε(x)。

定義2 (密度)設x∈X，稱ρ(x)=|Nε(x)|為x的密度。此處，密度為一個整數值，且依賴于ε鄰域。

定義3 (核心點和邊界點)設x∈X，若ρ(x)≥?，則稱x為X的核心點，由核心點構成的數據集稱之為簇Xc。非核心點但屬于核心點x在鄰域范圍內ε的對象，稱之為邊界點。

定義4 (噪音點)若x不屬于任何Xc稱之為噪音點。

DBSCAN算法適用于任何形狀的聚類，且不需要事先知道類簇數量，可以自適應的聚類出相應的類簇數量。但是該算法的兩個核心參數Eps和MinPts需要人為輸入，這組參數的組合值稍有不同便會引起聚類效果的巨大偏差，參數值的篩選嚴重影響聚類準確率。

1.4 CURE算法

CURE(clustering using representatives)算法是一種自底向上的層次聚類算法，可以對任意形狀的數據集聚類，采用計算代表點在收縮因子下的最短距離來合并簇，并重復這一過程直到聚類出最終數量的類簇。其特點是聚類步驟不可逆、分區處理和隨機取樣。

算法步驟如下：

(1)在原始數據集中隨機抽取一部分作為樣本集S；

(2)將樣本集S分區處理；

(3)對分區樣本集進行局部的聚類；

(4)隨機選取孤立點，若簇增長太慢就去掉孤立點；

(5)對局部數據簇聚類，新形成的簇的代表點根據自定義的收縮因子向中心點移動；

(6)標記類簇。

CURE算法的提出者認為，收縮因子一般取值0.2～0.7之間可以取得較好的聚類效果。但是，收縮因子的選取不當會產生聚類準確率低的問題，并且孤立點的隨機選取和根據簇增長速度來剔除孤立點，增加了人為主觀判斷，會對聚類效果造成負面影響。

2 DCNDA算法的提出

2.1 MeanShift核函數平移模型

DBSCAN聚類算法具有對異常值不敏感，事先不需要知道聚類數量，可以對不規則形狀數據樣本自適應聚類等優點，常常用于大數據庫樣本聚類。但是該算法嚴重依賴于兩個參數Eps和MinPts，這對參數的組合值需要人工確定，稍有差別聚類結果會出現明顯偏差。針對這一問題本文提出了密度函數平移模型來自適應確定Eps和MinPts的值。

MeanShift核函數平移模型原理：將樣本數據集分區，在某一分區中，選取樣本點x跟隨MeanShift向量向著該分區中密度最大點處不斷移動。MeanShift向量加入高斯核函數，在此過程中帶寬的選取根據拇指法則來指定為h，對MeanShift高斯核函數向量式求導，計算每一次偏移的極大值點，重復偏移過程直至選中樣本點移動至當前分區密度最大點處。計算所有分區MeanShift偏移結束后的帶寬均值，這個帶寬均值即為Eps；計算某分區密度最大點以帶寬h為密度半徑，當前區域內的數據點數量為s；計算出所有分區的s，其均值即為MinPts。完整步驟如下：

步驟2 在某一分區Si中的樣本點xi,i=1,…,l對于樣本點x的MeanShift向量形式如式(1)所示，加入核函數后的MeanShift向量形式如下

(6)

步驟3 對式(6)求導，令g(x)=-k`(x)得到如下結果

(7)

(8)

(9)

步驟8 若分區Si中MeanShift結束后帶寬為hi，那么Eps為所有分區帶寬的均值

(10)

計算當前分區中數據點與中心點之間的歐氏距離D(x,xi),0hi的數據點數量為ci，那么MinPts為所有分區滿足條件數據點數量的均值

(11)

2.2 DCNDA算法

本文所提的DCNDA算法是一種基于MeanShift核函數平移模型優化的DBSCAN算法改進的CURE算法。DCNDA算法基本思想：首先，輸入數據集D和聚類簇數K，通過自適應參數密度聚類算法獲得正常點數據簇和異常點簇；其次，計算所有正常點簇的質心，將質心、簇以鍵值對的形式存放在HashMap中；再次，計算所有質心之間的歐氏距離，找出距離最小的兩個質心，合并質心所在簇，生成一個新的簇，計算新生成簇的質心；最后，將新生成簇與質心的鍵值對存入HashMap，并刪除生成新簇的兩個鍵值對，重復前兩步過程，直到HashMap中鍵值對數等于K為止，將HashMap中的數據簇按序號存放在文件中。DCNDA算法執行流程如圖3所示。

圖3 DCNDA算法執行流程

假設在d維數據空間Rd中，有樣本數據集X={x1,…,xn},n為正整數，DCNDA算法完整步驟如下：

步驟1 輸入數據集以及聚類數K，MeanShift核函數平移模型處理數據集，確定參數Eps和MinPts的值(確定這兩個參數的詳細步驟見2.1)；

步驟2 執行DBSCAN算法自適應聚類出正常點簇(cluster[1],…,cluster[m])和異常點簇cluster(outlier)；

步驟3 比較步驟2中正常點簇數與輸入的K值，若正常點簇數小于或等于K，即m≤K，算法結束，輸出正常點簇和異常點簇；若m>K，繼續執行下列步驟；

步驟4 計算所有正常點數據簇(cluster[1],…,cluster[m])的質心點c

(12)

若c的取值范圍為(c1,…,cm)，則將鍵值對cl,cluster[l](1≤l≤m)存入HashMap；

步驟5 計算m個質心間的歐氏距離D(cj,ck) 1≤j,k≤m，若有兩質心點滿足D(ca,cb)=minD(cj,ck)則將質心ca,cb所代表的簇cluster[a],cluster[b]合并為一個新簇cluster[new]；

步驟6 計算新簇cluster[new]的質心cnew，將鍵值對cnew,cluster[new]存入HashMap刪除合并前的鍵值對ca,cluster[a],cb,cluster[b]；

步驟7 判斷當前HashMap中的鍵值對數H，若H>K，重復步驟5和步驟6直到H=K，輸出當前HashMap中的數據簇(cluster[1],…,cluster[K])和異常點簇cluster(outlier)，算法結束。

3 實驗及結果比較

3.1 實驗環境及數據集

實驗環境：window7操作系統、Eclipse、gnuplot4.6等。為了充分驗證本文所提算法的有效性、魯棒性，實驗數據集采用加入一定量人工數據集的二維和多維的Argo浮標數據集，實驗數據集來源于中國Argo實時資料中心，實驗數據規模見表1。

表1 實驗數據集規模

本文選取PDBSCAN算法[2]和改進分區CURE算法[9]為對比算法，以聚類準確率、異常值檢測率、算法執行時間、時間復雜度等關鍵因素做為算法評判標準，算法準確度的驗證采用有監督的F值方法實現。

3.2 聚類結果分析

在同等數據集的對比實驗中，DCNDA算法只需要輸入聚類數K1，PDBSCAN算法需要人工確定參數Eps、MinPts等。改進分區CURE算法需要人工輸入聚類數K2、分區、收縮因子等參數。如圖4、圖5、圖6所示，分別為DCNDA算法、改進分區CURE算法、PDBSCAN算法采用S2數據集的聚類效果圖。令K1=10，Eps=20，MinPts=100，K2=10，分區為100，收縮因子為0.6等。

圖4 DCNDA算法聚類效果

圖5 改進分區CURE算法聚類效果

圖6 PDBSCAN算法聚類效果

圖4～圖6中，由實心圓點、上三角形、下三角形、叉號形、空心方形等不同形狀間隔分布的數據簇代表聚類結果，聚類結果上方不同形狀的數據點表示相應數據簇的異常值點。由圖4～圖6可看出，本文所提算法DCNDA算法對高密度數據集的聚類效果最佳，異常值點描述準確。

改進分區CURE算法對異常值敏感，在初始聚類過程中受異常值影響導致聚類出現偏差。在層次聚類增長過程中，該算法排除增長緩慢的數據點這一過程，評判標準的制定受研究者主觀因素影響，難以適當的評判某一點增長速度的快慢，會造成聚類過程中異常點和正常點區分錯誤。收縮因子選取不當，也會對聚類效果造成影響。

PDBSCAN算法，Eps和MinPts這對參數需要人為設置，為了獲得良好的聚類效果只能通過多次實驗來確定參數，即便如此，仍然難以取得良好的聚類效果。PDBSCAN不需要事先知道聚類數量，依靠Eps和MinPts這對組合參數，自適應的聚類出若干數量的聚類結果。聚類數量太少或太多都是聚類精度低的表現，如圖6所示，聚類數量過多，原本屬于同一類簇的數據被分開為多個類簇，聚類效率較低。

從執行時間方面考慮，由表2可見，在二維數據集的聚類中DCNDA算法執行時間與其它兩種算法相差不大。MeanShift核函數平移模型的時間復雜度為O(Tn2),T為迭代次數，由于算法使用HashMap和KDTree等數據結構優化存儲，DCNDA算法的時間復雜度為O(mlogn)+O(Tn2),m為初始類簇數。隨著數據集中數據量的增大，數據集維度的增高，DCNDA算法的執行時間比其它兩種算法更長。在最壞情況下，改進分區CURE算法時間復雜度為O(n2logn)。PDBSCAN算法時間復雜度為O(n2)。當數據量大到一定程度后DCNDA的時間復雜度相僅當于O(n2)，與兩種對比算法時間復雜度相當。

從聚類準確率方面分析，由圖7可見DCNDA算法無論在二維數據集還是多維數據集方面的聚類準確率均高于同等數據集下的改進分區CURE算法和PDBSCAN算法。隨著數據量和數據維度的增高，DCNDA算法的聚類準確率基本保持在93.50%左右，具有較高有效性和魯棒性。改進分區CURE算法在對二維數據集聚類時，表現出了較好的穩定性和魯棒性，隨著數據集數量的進一步增大和數據維度的增長，改進分區CURE算法聚類效率有所降低，受隨機取樣和收縮因子影響，該算法對大量的高維的數據集聚類效果不穩定。PDBSCAN算法對數據量較少的二維數據集聚類效果良好，隨著數據量增大維度增高數據集簇之間存在交叉包含關系時聚類精度下降。對高維數據集聚類效果DCNDA算法明顯優于其它兩種對比算法。

表2 DCNDA、改進分區CURE、PDBSCAN聚類效率分析

圖7 聚類準確率分析

從異常值檢測率方面分析，由圖8可見，無論是二維數據集還是多維數據集，DCNDA算法的異常值檢測率維持在91%～95%之間，改進分區CURE算法主要集中在80%～85%之間，PDBSCAN算法的異常值檢測率在65%～78%范圍內。相較于其它兩種對比算法，DCNDA算法在聚類過程中對于異常值的處理更加合理，在高維數據集和數據量大的數據集聚類過程中，有明顯的優越性。

圖8 異常值檢測率分析

綜上分析，DCNDA算法對二維和多維數據集聚類具備有效性和魯棒性，為了保證聚類精確度而引入了MeanShift核函數平移模型導致時間復雜度增加，但是隨著數據量增大，時間復雜度對算法的影響程度趨于穩定。

4 結束語

本文提出了一種基于自適應參數DBSCAN算法改進的CURE算法。DCNDA算法，在初始聚類過程中，引入了MeanShift核函數平移模型來自適應確定了DBSCAN的參數，大大提高了初步密度聚類的精確度和魯棒性。初步密度聚類將異常值簇和若干正常值簇分別輸出，保證了后面層次聚類數據集的純凈性，對正常值簇的層次聚類進一步提高了聚類精確度。引用質心公式計算各簇質心，通過質心最短距離兩兩合并數據簇，避免了使用收縮因子而造成的聚類偏差，而且不需要重復計算代表點，減少了計算時間。MeanShift核函數平移模型的引入，盡管使算法聚類精度提高，但是犧牲了一定的時間復雜度，尤其是對大批量的高維數據集操作時，雖然使用了HashMap和KDTree優化算法結構，時間復雜度仍然較高。因此，如何在最大化的降低時間復雜度的前提下保證算法聚類精確度和魯棒性，將是本文下一步研究的重點。