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

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

0 引 言

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

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中的簇數(shù)[7]。高長元等提出了一種基于CURE聚類算法[8,9]。針對Argo浮標觀測數(shù)據(jù)數(shù)據(jù)量龐大的特點，蔣華等設計了基于MapReduce技術的Argo浮標剖面信息融合算法[10]，為利用大數(shù)據(jù)技術解決海洋數(shù)據(jù)監(jiān)測問題提供了新思路。

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

1 相關理論

1.1 MeanShift

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

圖1 MeanShift

圖2 MeanShift偏移過程

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

(1)

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

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

(2)

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

(3)

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

1.2 核密度估計

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

(4)

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

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

(5)

1.3 DBSCAN算法

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

DBSCAN算法有兩個關鍵參數(shù)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的密度。此處，密度為一個整數(shù)值，且依賴于ε鄰域。

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

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

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

1.4 CURE算法

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

算法步驟如下：

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

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

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

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

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

(6)標記類簇。

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

2 DCNDA算法的提出

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

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

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

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

(6)

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

(7)

(8)

(9)

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

(10)

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

(11)

2.2 DCNDA算法

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

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

假設在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ù)的詳細步驟見2.1)；

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

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

步驟4 計算所有正常點數(shù)據(jù)簇(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中的鍵值對數(shù)H，若H>K，重復步驟5和步驟6直到H=K，輸出當前HashMap中的數(shù)據(jù)簇(cluster[1],…,cluster[K])和異常點簇cluster(outlier)，算法結束。

3 實驗及結果比較

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

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

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

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

3.2 聚類結果分析

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

圖4 DCNDA算法聚類效果

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

圖6 PDBSCAN算法聚類效果

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

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

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

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

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

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

圖7 聚類準確率分析

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

圖8 異常值檢測率分析

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

4 結束語

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