張輝 韓發(fā) 鹿方凱

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

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

DOI：10. 11907/rjdk. 182134

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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)域知識(shí)的重要依據(jù)，因此迫切需要利用空間數(shù)據(jù)挖掘技術(shù)發(fā)現(xiàn)空間數(shù)據(jù)中隱含的有用知識(shí)?？臻g聚類作為空間數(shù)據(jù)挖掘的一個(gè)重要分支，是將數(shù)據(jù)對(duì)象進(jìn)行分組，使得每一個(gè)組內(nèi)對(duì)象之間相似性最小，且組間對(duì)象之間的相似性最大[1]。

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

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

1 SADBSCAN算法

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

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

定義1 K階鄰域。給定一個(gè)圖G，[pi]為G的一個(gè)頂點(diǎn)，其K階鄰域?yàn)樗械近c(diǎn)[pi]的路徑小于或等于K的點(diǎn)集，記為[NK（pi）]。

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

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

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

2 SADBSCAN算法實(shí)現(xiàn)

2.1 實(shí)現(xiàn)細(xì)節(jié)

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

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

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

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

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

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

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

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

2.2 自適應(yīng)機(jī)制

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

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

2.3 算法分析

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

3 SADBSCAN實(shí)驗(yàn)

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

3.1 實(shí)驗(yàn)數(shù)據(jù)與結(jié)果

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