基于DCNDA算法的數(shù)據(jù)異常檢測

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

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

0 引 言

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

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

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

1 相關(guān)理論

1.1 MeanShift

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

圖1 MeanShift

圖2 MeanShift偏移過程

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

(1)

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

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

(2)

但是，在Sh區(qū)域內(nèi)，每個點(diǎn)對x的貢獻(xiàn)是一樣的。而實(shí)際上，這種貢獻(xiàn)與x到每個點(diǎn)的距離相關(guān)。對于每個樣本，其重要程度也不相同。基于這些考慮對基本MeanShift向量形式增加了核函數(shù)和樣本權(quán)重，得到改進(jìn)型MeanShift向量形式

(3)

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

1.2 核密度估計(jì)

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

(4)

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

核密度估計(jì)中核函數(shù)分為多種，最常用的如高斯核函數(shù)

(5)

1.3 DBSCAN算法

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

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

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

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

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

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

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

1.4 CURE算法

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

算法步驟如下：

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

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

(3)對分區(qū)樣本集進(jìn)行局部的聚類；

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

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

(6)標(biāo)記類簇。

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

2 DCNDA算法的提出

2.1 MeanShift核函數(shù)平移模型

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

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

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

(6)

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

(7)

(8)

(9)

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

(10)

計(jì)算當(dāng)前分區(qū)中數(shù)據(jù)點(diǎn)與中心點(diǎn)之間的歐氏距離D(x,xi),0hi的數(shù)據(jù)點(diǎn)數(shù)量為ci，那么MinPts為所有分區(qū)滿足條件數(shù)據(jù)點(diǎn)數(shù)量的均值

(11)

2.2 DCNDA算法

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

圖3 DCNDA算法執(zhí)行流程

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

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

步驟2 執(zhí)行DBSCAN算法自適應(yīng)聚類出正常點(diǎn)簇(cluster[1],…,cluster[m])和異常點(diǎn)簇cluster(outlier)；

步驟3 比較步驟2中正常點(diǎn)簇?cái)?shù)與輸入的K值，若正常點(diǎn)簇?cái)?shù)小于或等于K，即m≤K，算法結(jié)束，輸出正常點(diǎn)簇和異常點(diǎn)簇；若m>K，繼續(xù)執(zhí)行下列步驟；

步驟4 計(jì)算所有正常點(diǎn)數(shù)據(jù)簇(cluster[1],…,cluster[m])的質(zhì)心點(diǎn)c

(12)

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

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

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

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

3 實(shí)驗(yàn)及結(jié)果比較

3.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

實(shí)驗(yàn)環(huán)境：window7操作系統(tǒng)、Eclipse、gnuplot4.6等。為了充分驗(yàn)證本文所提算法的有效性、魯棒性，實(shí)驗(yàn)數(shù)據(jù)集采用加入一定量人工數(shù)據(jù)集的二維和多維的Argo浮標(biāo)數(shù)據(jù)集，實(shí)驗(yàn)數(shù)據(jù)集來源于中國Argo實(shí)時資料中心，實(shí)驗(yàn)數(shù)據(jù)規(guī)模見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集規(guī)模

本文選取PDBSCAN算法[2]和改進(jìn)分區(qū)CURE算法[9]為對比算法，以聚類準(zhǔn)確率、異常值檢測率、算法執(zhí)行時間、時間復(fù)雜度等關(guān)鍵因素做為算法評判標(biāo)準(zhǔn)，算法準(zhǔn)確度的驗(yàn)證采用有監(jiān)督的F值方法實(shí)現(xiàn)。

3.2 聚類結(jié)果分析

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

圖4 DCNDA算法聚類效果

圖5 改進(jìn)分區(qū)CURE算法聚類效果

圖6 PDBSCAN算法聚類效果

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

改進(jìn)分區(qū)CURE算法對異常值敏感，在初始聚類過程中受異常值影響導(dǎo)致聚類出現(xiàn)偏差。在層次聚類增長過程中，該算法排除增長緩慢的數(shù)據(jù)點(diǎn)這一過程，評判標(biāo)準(zhǔn)的制定受研究者主觀因素影響，難以適當(dāng)?shù)脑u判某一點(diǎn)增長速度的快慢，會造成聚類過程中異常點(diǎn)和正常點(diǎn)區(qū)分錯誤。收縮因子選取不當(dāng)，也會對聚類效果造成影響。

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

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

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

表2 DCNDA、改進(jìn)分區(qū)CURE、PDBSCAN聚類效率分析

圖7 聚類準(zhǔn)確率分析

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

圖8 異常值檢測率分析

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

4 結(jié)束語

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