自適應局部密度變化空間聚類算法研究

張輝 韓發(fā) 鹿方凱

摘 要：針對空間局部密度變化和需要用戶輸入?yún)?shù)的空間聚類問題，提出自適應局部密度變化的空間聚類方法。借助 Delaunay三角網(wǎng)構(gòu)建空間鄰近關(guān)系的優(yōu)勢，首先給出點密度的度量標準，即與點直接相連的邊長度均值。將核點定義為一階鄰域中至少存在一個密度相似點，在此基礎上應用廣度優(yōu)先搜索算法對一階鄰域進行搜索，對密度相似的核點進行擴展，將密度遠小于核點密度的點作為簇的邊界點。在判斷點密度是否相似時，根據(jù)已加入核點的平均密度和密度變化率自動調(diào)整參數(shù)值。通過模擬實驗，對比DBSCAN算法實驗結(jié)果，對提出的算法進行驗證。實驗結(jié)果表明，該算法不僅能夠自動適應局部密度變化和識別出離散點，而且能適應不同形態(tài)的空間簇。

關(guān)鍵詞：空間聚類;自適應;局部密度不同;點密度;Delaunay三角網(wǎng)

DOI：10. 11907/rjdk. 182134

中圖分類號：TP312文獻標識碼：A文章編號：1672-7800（2019）001-0095-04

Abstract：In order to solve the problems of spatial clustering with local density changes and requiring parameters given by the user， this paper proposes a spatial clustering method with self-adaptive local density variation. In this paper， the Delaunay triangulation is used to construct the spatial proximity relationship. The metric of the point density and the mean value of the first-order neighbors side-length are firstly given. The core point is defined as that there is at least one point with similar density in the first-order neighborhood. On this basis， the breadth-first search algorithm is used to perform search on the first-order neighborhood， and the core points with similar density are extended， and points far less than the density of the core is considered as the boundary points of the cluster. When judging whether the density of points is similar， the parameter values are automatically adjusted according to the average density and the rate of the density change of the core points that have been added. Through simulation experiments and comparison of experimental results of DBSCAN algorithm， the proposed algorithm is verified. Experimental results show that the algorithm can automatically adapt to local density changes and different forms of spatial clusters and identify discrete points.

0 引言

隨著數(shù)據(jù)獲取技術(shù)快速發(fā)展，空間數(shù)據(jù)量變得龐大，并且成為探索空間領(lǐng)域知識的重要依據(jù)，因此迫切需要利用空間數(shù)據(jù)挖掘技術(shù)發(fā)現(xiàn)空間數(shù)據(jù)中隱含的有用知識。空間聚類作為空間數(shù)據(jù)挖掘的一個重要分支，是將數(shù)據(jù)對象進行分組，使得每一個組內(nèi)對象之間相似性最小，且組間對象之間的相似性最大[1]。

基于劃分的聚類方法和基于層次的聚類方法，是較早提出的較為有效的基本聚類方法，旨在發(fā)現(xiàn)球狀簇，卻很難發(fā)現(xiàn)任意形狀的簇[2-4]。為了發(fā)現(xiàn)任意形狀的簇，基于密度的聚類方法能夠過濾低密度區(qū)域，發(fā)現(xiàn)稠密樣本點組成的類簇，并能識別噪聲數(shù)據(jù)[5-8];基于格網(wǎng)的聚類方法[9]，在某種程度上類似于基于密度的方法，采用基于格網(wǎng)的數(shù)據(jù)結(jié)構(gòu)對數(shù)據(jù)集進行聚類。但基于密度和基于格網(wǎng)的聚類方法不能較好處理局部密度變化的簇，且需要人為設置參數(shù)。基于圖論的聚類方法是將所有實體構(gòu)建的圖分割成一系列子圖，每個子圖視為一個空間簇，對局部密度變化的簇具有很好的聚類效果，但仍沒有解決基于密度方法中需要人為設置參數(shù)的問題[10-11]。混合聚類方法一般會對幾種聚類算法的優(yōu)點進行組合[12]。綜上，算法大都具有不適用于局部密度變化的數(shù)據(jù)集，或需要人為設置參數(shù)的缺點。基于密度的聚類方法在這兩方面最為突出，算法也大都以基于密度的聚類方法為基礎進行改進。在基于密度的聚類方法中，DBSCAN（Density Based Spatial Clustering of Applications with Noise）算法作為應用最廣泛的密度聚類算法，具有發(fā)現(xiàn)任意簇、自動排除噪聲點、無需指定類別數(shù)的優(yōu)點[13];但是當數(shù)據(jù)集密度差異較大時，由于DBSCAN方法設定了全局密度參數(shù)，無法正確識別局部密度不同的空間數(shù)據(jù)簇，算法的兩個參數(shù)也不易設置[5]。OPTICS（Ordering Points to Identify the Clustering Structure）[6]算法通過對基于密度的聚類排序，即表示出數(shù)據(jù)的密度結(jié)構(gòu)，解決了空間數(shù)據(jù)局部密度分布不均問題，但也受DBSCAN算法自身局限的影響，不能對周圍稀疏樣本點區(qū)域有較好處理效果，且計算量大。SNN（Shared Nearest Neighbor）[7]和VDBSCAN（Varied Density Based Spatial Clustering of Application with Noise）[8]算法也是針對變化密度進行改進的，雖然可以發(fā)現(xiàn)不同密度的簇，但在某些情況下無法產(chǎn)生正確結(jié)果，選擇合適的參數(shù)也十分困難。

為了解決空間局部密度不同和參數(shù)不易選擇的問題，本文對DBSCAN算法進行改進，提出一種適應局部密度變化的空間聚類方法——SADBSCAN（Self-adaptive Density Based? Spatial Clustering of Applications with Noise）。該方法利用Delaunay三角網(wǎng)構(gòu)建空間鄰近關(guān)系的優(yōu)勢，對直接相連且密度相等的數(shù)據(jù)點進行擴展聚類[14-15];在自適應方面，算法進行核點擴展時，首先由用戶給出一個閾值，然后根據(jù)數(shù)據(jù)點的分布情況，自動調(diào)整參數(shù)，得到一個更合適的值。

1 SADBSCAN算法

在介紹算法之前，先引出算法的一些相關(guān)概念。

D={[p1]，…，[pn]}表示一個包含n個實體的數(shù)據(jù)集，G表示D中實體構(gòu)成的Delaunay剖分圖。每個空間實體[pi]表示Delaunay剖分后三角網(wǎng)中的一個頂點，進而可以給出如下定義：

定義1 K階鄰域。給定一個圖G，[pi]為G的一個頂點，其K階鄰域為所有到點[pi]的路徑小于或等于K的點集，記為[NK（pi）]。

定義2 點密度。給定一個圖G，[pi]為G的一個頂點，[pi]的密度用統(tǒng)計量為其一階鄰域內(nèi)各點與[pi]邊長均值的倒數(shù)構(gòu)造，記為[densitypi]，表達式如式（1）。

式（2）為一階鄰域內(nèi)各點與[pi]邊長的均值，[dist（pi，pj）]表示點[pi]、[pj]的歐氏距離。如圖1所示，對數(shù)據(jù)集Delaunay三角形剖分后可以發(fā)現(xiàn)，左邊的簇比較密集，與點直接相連的邊長度均值[meanpi]較小，則[densitypi]就較大;右邊的簇比較稀疏，與點直接相連的邊長度均值[meanpi]較大，則[densitypi]就較小。因此，本文給出的點密度度量標準能夠準確度量各類簇的局部密度，最大程度地反映類間差異性。

聚類過程與DBSCAN算法類似，也是從某個核點開始聚類，遍歷其一階鄰域，只要存在核點就繼續(xù)聚類，并將遠小于核點密度且兩點距離小于α的點判定為邊界點，直至再無核點可擴展，則一個簇聚類完成。然后另選一個未訪問的新核點重復上述過程，直到所有點聚類完成。上述聚類過程也可以表述為將所有密度直達、密度相連和密度可達的點聚為一類。

2 SADBSCAN算法實現(xiàn)

2.1 實現(xiàn)細節(jié)

為了更好地描述和實現(xiàn)算法，先給出數(shù)據(jù)點的數(shù)據(jù)結(jié)構(gòu)：

算法還需要設置一個變量CID和一個隊列corequeue，用來記錄當前使用的ClusterID編號（初始值為0）和存儲當前聚類簇中發(fā)現(xiàn)的核點。算法步驟如下：

（1）對數(shù)據(jù)集進行Delaunay剖分，得到三角網(wǎng)集合DT（D）。

（2）遍歷DT（D）尋找每個點的一階鄰域[pi]·N[]，根據(jù)一階鄰域計算點密度[pi]。density。

（3）任取一點[pi]，遍歷[pi]·N[]，若存在與[pi]。density相似的點，則判斷[pi]為核點，令ClusterID+1，并將其賦給[pi]。ClusterID， 令[pi]· isCore=1。

（4）遍歷[pi]·N[]中的點[pj]，若[Dvp（pi，pj）<α]，則[pj]為核點，存入corequeue，令[pj]·isCore=1;若[densitypi>>][densitypj]且[dist（pi，pj）<α]，則[pj]為邊界點，令[pi]·ClusterID=CID，[pj]· isCore=0。

（5）若corequeue不為空，則取出頭元素，令其為[pi]·ClusterID=CID，重復步驟（4）、步驟（5）。

（6）若空間數(shù)據(jù)點全部被訪問過，則算法結(jié)束，否則轉(zhuǎn)步驟（3）。

2.2 自適應機制

密度波動在一定范圍內(nèi)，即高斯分布的方差在[0，α）區(qū)間內(nèi)，密度波動范圍的上界限為[α]。首先用戶設定一個上限閾值[α]，然后在算法運行過程中根據(jù)每次彈出的核點密度偏離中心的程度動態(tài)更新[α]值。具體分為以下兩個過程：由式（6）計算從corequeue中彈出的核點偏離中心的程度d;由式（7）計算新值[α]。

式（6）中，[cdensityp]表示已被擴展核點（包括核點p）的密度均值。由式（7）對[α]進行自適應，由于偏離中心程度的上限為[α]，根據(jù)高斯分布特征，在中心值周圍有很大一部分數(shù)據(jù)集，若縮減過快，[α]就會由于該值影響減小到一個較小值，從而不能發(fā)現(xiàn)那些d較大并且滿足密度相似的點。因此當[d <α2]時，[α]需要縮減;當[d≥α2]時，[α]需要增大。增加比例大于縮減比例，縮減比例值是經(jīng)過大量實驗之后確定的一個相對較優(yōu)值。

2.3 算法分析

從上述聚類過程分析可知，對于給定含有n個點的數(shù)據(jù)集，構(gòu)建Delaunay三角網(wǎng)的時間復雜度為O（nlogn）[16];找到一個點的鄰域需掃描一遍所有剖分后的三角形，所需時間為O（n），而n個點的時間約為O（n2）;核隊列上的循環(huán)和處理當前核點的鄰域與數(shù)據(jù)點數(shù)n無關(guān)，時間復雜度分別為O（1），所以 SADBSCAN 的時間復雜度為O（n2）。由此可知，本文算法SADBSCAN的時間復雜度與算法DBSCAN相同。

3 SADBSCAN實驗

為了驗證SADBSCAN算法的可行性與優(yōu)越性，使用具有不同形狀、局部密度和噪聲點的標準數(shù)據(jù)集直觀展示聚類效果，并與經(jīng)典的基于密度的算法DBSCAN進行比較。

3.1 實驗數(shù)據(jù)與結(jié)果

使用數(shù)據(jù)集是在聚類分析中廣為應用的標準數(shù)據(jù)集，均為二維數(shù)據(jù)，同時具有局部密度不同、簇形各異以及有離散點干擾等各自不同特點。各數(shù)據(jù)集參數(shù)如表1所示，將兩種算法分別應用于各數(shù)據(jù)集上。