王小林，付 山，邰偉鵬，胡 濤

(安徽工業(yè)大學(xué)a.計算機科學(xué)與技術(shù)學(xué)院；b.工程研究院，安徽馬鞍山243032)

聚類是無監(jiān)督機器學(xué)習(xí)中的代表，通過聚類可從大量數(shù)據(jù)中挖掘出有價值的信息[1]。目前聚類算法被廣泛用于生物醫(yī)學(xué)、圖像處理等領(lǐng)域中[2-3]，其大致可分為：劃分的聚類算法[4]，如K-means 等；密度的聚類算法[5]，如DBSCAN(density-based spatial clustering of applications with noise)等；網(wǎng)格的聚類算法[6-7]，如GG(grid-growing clustering algorithm for geo-spatial data)和CBSCAN(cell-based DBSCAN for location big data)等；模型的聚類算法[8]，如EM(expection-maximization algorithm)算法等。密度聚類可識別任意形狀的簇且對噪聲點不敏感，故其在數(shù)據(jù)挖掘甚至多維數(shù)據(jù)聚類中受到關(guān)注[9],以Ester 等[5]提出的DBSCAN 算法最為典型。DBSCAN算法中數(shù)據(jù)點位置對機器來說是透明的，需重復(fù)且廣泛地遍歷節(jié)點，對于大型數(shù)據(jù)集聚類效率較低，且數(shù)據(jù)量越大聚類時間越長。Wang等[10]提出了一種并行的DBSCAN算法，有效解決了理論與實踐之間的鴻溝，但并行代價較高，不具有普適性；Kumar等[11]提出了一種基于圖Group索引的DBSCAN算法，適當提高了DBSCAN 算法的聚類效率，但對大規(guī)模數(shù)據(jù)集沒有進行詳細研究；Boonchoo 等[12]通過改進DBSCAN 算法的聚類方式，提出以低密度優(yōu)先來緩解高密度數(shù)據(jù)，但缺乏大規(guī)模數(shù)據(jù)集的研究；He 等[13]、Kim等[14]、Hu等[15]使用外部工具Mapreduce平臺實現(xiàn)密度聚類算法，雖提升了聚類的效率和準確率，但需專用處理器等外部設(shè)備支持，不屬于一種低代價高效率的算法。

使用DBSCAN算法對二維點集聚類時，由于參與聚類的點集數(shù)量龐大，且DBSCAN算法是通過遍歷所有點并利用歐式距離判斷點是否屬于鄰域內(nèi)，會多次遍歷到相同的點，導(dǎo)致重復(fù)計算，耗費大量時間。針對DBSCAN算法效率低下且無法處理大規(guī)模點集數(shù)據(jù)的問題，提出一種基于劃分網(wǎng)格的密度聚類算法，且在OSM(open street map)路網(wǎng)節(jié)點數(shù)據(jù)預(yù)處理后的二維坐標點集下，采用提出的GDSCAN 算法和DBSCAN 算法進行不同規(guī)模數(shù)據(jù)的測試，驗證GDSCAN算法的聚類效率。

1 DBSCAN密度聚類算法

DBSCAN算法是一種基于密度的空間聚類算法，涉及兩個預(yù)設(shè)參數(shù):鄰域半徑reps，事先給定數(shù)據(jù)點的鄰域范圍半徑，用以限定待統(tǒng)計點的范圍；密度閾值Tminpts，在數(shù)據(jù)點reps鄰域范圍內(nèi)的點密度。

傳統(tǒng)DBSCAN算法使用圓形作為密度鄰域，并通過歐式距離判斷數(shù)據(jù)點是否在當前數(shù)據(jù)點鄰域內(nèi)，如式(1)所示以二維空間為例，通過歐式距離計算點(xi,yi)與數(shù)據(jù)點(a,b)的半徑鄰域關(guān)系。

若滿足式(1)，則表示點(xi,yi)參與點(a,b)的密度值計算，否則不予考慮。

設(shè)原始數(shù)據(jù)集為D，對于任意數(shù)據(jù)點p，記以點p 為圓心、reps為半徑鄰域內(nèi)的鄰居點集為Np，用|Np|表示點集包含的點數(shù)量。對于數(shù)據(jù)集D 中的每個點，傳統(tǒng)DBSCAN算法將其分為3類。

1)核心點對任意數(shù)據(jù)點p，若p 的reps鄰域內(nèi)鄰居點數(shù)量 ||Np≥Tminpts，則稱點p 為核心點。

2) 邊界點 對任意數(shù)據(jù)點p，若p 的reps鄰域內(nèi)鄰居點數(shù)量 ||Np＜Tminpts，但存在一個鄰居點q(q∈Np)，且|≥Tminpts，即q是核心點，則稱p 為邊界點。

3)噪聲點 若任意點p 的reps鄰域 ||Np＜Tminpts，且不存在任意點r ∈Np為核心點，則點p 為噪聲點。即若p 既不是核心點也不是邊界點，則其為噪聲點。點類型的決策過程如圖1。

給定數(shù)據(jù)集D，對于D中的任意兩個位置點，他們之間存在3種密度關(guān)系:直接密度可達、密度可達和密度相連。若點p 在q 的reps鄰域內(nèi)，且q 為核心對象點，則稱p 是q 發(fā)出的直接密度可達；對于位置點集合{ }p1,p2,p3,…,pb?D，若pi+1(i=1,2,3,…,n-1)是pi發(fā)出的直接密度可達，則稱p1直接密度可達pn；若存在對象點o ∈D，且p 到o為密度可達，且q 到o為密度可達，則稱p 到q 為密度相連。

圖1 點類型決策流程Fig.1 Decision process for point type

DBSCAN 聚類算法過程為:首先，隨機選取一點記為p，通過遍歷點的reps鄰域來搜索簇，如果點p 的reps鄰域包含多于Tminpts個點，則創(chuàng)建一個以p為核心點的簇；然后，通過迭代的方法從核心對象點到直接密度可達對象逐步擴張、聚集，當無核心對象點添加到簇中，整個迭代過程結(jié)束，同時得到若干劃分的簇。點只提供坐標信息，在確定鄰域內(nèi)包含的點個數(shù)是否大于Tminpts時，需計算出鄰域中心點和其他點的位置關(guān)系，通常使用歐氏距離來判斷任一點是否被包含在reps鄰域內(nèi)。點數(shù)量較少時，其判斷位置需要的計算量也較少；面對大量點數(shù)據(jù)時，計算點之間的距離會造成大量的等待時延，且這個時延隨著數(shù)據(jù)點的增多呈指數(shù)增長，造成時間和內(nèi)存的浪費。

2 基于劃分網(wǎng)格的DBSCAN算法

圖2 Grid dividing-based DBSCAN算法流程圖Fig.2 Algorithm flowchart of grid dividing-based DBSCAN

針對傳統(tǒng)DBSCAN 算法不能較好適應(yīng)大規(guī)模數(shù)據(jù)的聚類情況，提出基于劃分網(wǎng)格的密度聚類算法GDSCAN。對于二維坐標點集，取其最小及最大的坐標(xmin,ymin)，(xmax,ymax)，并以此確定其最小外包矩形；綜合最小外包矩形大小和原始數(shù)據(jù)的特性確定鄰域半徑reps，以reps作為網(wǎng)格邊長將最小外包矩形劃分成若干網(wǎng)格，網(wǎng)格邊長≥reps。計算開始時隨機選取一個未遍歷的點作為起點，通過給定reps及Tminpts逐步迭代擴張，填充核心對象點集。在填充和聚類過程中，計算reps鄰域點集個數(shù)時，點必定存在于某一網(wǎng)格中任意位置，其鄰域范圍不可能超出以該網(wǎng)格為中心的所有直接相連網(wǎng)格（直接可達網(wǎng)格）。因此，只需考慮中心網(wǎng)格和直接可達網(wǎng)格內(nèi)的點進行距離計算，直接過濾大量較遠的點，以實現(xiàn)對核心對象集合的填充或?qū)c的聚類。算法流程框圖如圖2。

點的直接可達網(wǎng)格示意如圖3。由圖3可看出:當網(wǎng)格劃分為正方形時，記9 個網(wǎng)格的范圍為RRec。以點p 為例，p 所在的正方形網(wǎng)格5為中心網(wǎng)格，則1，2，3，4，6，7，8，9為其直接可達網(wǎng)格。網(wǎng)格邊長為r(r ≥reps)，為使中間網(wǎng)格內(nèi)任意點的鄰域圓位于其直接可達網(wǎng)格內(nèi)，網(wǎng)格邊長最小r=reps。若點p 位于中心網(wǎng)格的非邊框部分，則其reps鄰域位于中間的圓內(nèi)。記鄰域內(nèi)的點集為N，則N 的分布范圍RN?RRec。若點p 位于中心網(wǎng)格的頂點處，分別以中心網(wǎng)格四角為圓心的圓，由于圓的半徑等于網(wǎng)格邊長，所以4 個圓的范圍不會超過9 個網(wǎng)格。若取網(wǎng)格邊長大于reps，則圓處于被包含的狀態(tài)，同樣無法超過9個網(wǎng)格的范圍。同理，若點p 位于中心網(wǎng)格除頂點的邊上，以p 為圓心，reps為半徑的圓Op，當且僅當r=reps時，Op與最外層的網(wǎng)格相切，當r ＞reps時，Op永遠被包含在9個網(wǎng)格內(nèi)。這樣，對于點p，其reps鄰域內(nèi)的點只存在于9個網(wǎng)格內(nèi)，且不包含4個角不與圓相交的區(qū)域。對于游離在9個網(wǎng)格外的點，由于其不被包含在點p 的reps鄰域內(nèi)，其完全不用參與距離的計算。記 ||Np點p 的reps鄰域內(nèi)包含的點個數(shù)，若 ||Np≥Tminpts，在下一步判斷核心對象點時再次構(gòu)建其直接可達網(wǎng)格計算鄰域內(nèi)點數(shù)量。

圖3 點的直接可達網(wǎng)格示意圖Fig.3 Schematic diagram for direct reachable grid of points

受原始數(shù)據(jù)離散情況等外部因素影響，往往點分布的圖不可能正好劃分為若干正方形，但同樣可等分為若干相同大小的長方形。將原始點分布圖劃分成若干等大小的長方形，取長方形最短邊l 為劃分標準，滿足長方形最短邊l ≥鄰域半徑r，其鄰域范圍示意圖如圖4。由圖4 可看出:當且僅當l=r時，點在中心網(wǎng)格上下邊(包括端點)時，其生成的鄰域圓與網(wǎng)格形成相切的關(guān)系；當l ＞r 時，同正方形網(wǎng)格一樣，中心網(wǎng)格中任意一點，其鄰域包含在中心網(wǎng)格的直接可達網(wǎng)格范圍內(nèi)，這種情況同樣適用。

若取長方形最長邊為劃分標準，其鄰域范圍示意圖如圖5。由圖5可看出，以中心網(wǎng)格頂點為圓心作鄰域圓，點的鄰域范圍超出中心網(wǎng)格及其直接可達網(wǎng)格范圍，需擴大網(wǎng)格范圍以及數(shù)量。因此，不考慮使用長方形網(wǎng)格最長邊為劃分標準。

對點p 的鄰域密度值判斷后，對下一點重新選取中心網(wǎng)格和直接可達網(wǎng)格，從而只計算網(wǎng)格內(nèi)的點，這樣在迭代過程中可大大減少點距離的判斷，直接減少計算量，極大提高算法效率。算法步驟流程圖如圖6。

圖4 以長方形網(wǎng)格最短邊為標準的鄰域范圍示意圖Fig.4 Schematic diagram of neighborhood range with the shortest edge of rectangular grid as standard

圖5 以長方形網(wǎng)格最長邊為標準的鄰域范圍示意圖Fig.5 Schematic diagram of neighborhood range with the longest edge of rectangular grid as standard

圖6 GDSCAN算法流程圖Fig.6 Algorithm flowchart of GDSCAN

3 實驗結(jié)果及分析

3.1 實驗環(huán)境及條件

實驗測試設(shè)備為1臺PC 機，Windows10系統(tǒng)，配置為i5-8400 六核CPU，主頻為2.80 GHz，16 GB 內(nèi)存，1 T機械硬盤。使用Visual Studio 2012開發(fā)軟件以及C++語言實現(xiàn)DBSCAN和GDSCAN算法。

實驗數(shù)據(jù)取自O(shè)SM 官網(wǎng)，為美國東北部區(qū)域的路網(wǎng)數(shù)據(jù)，大小約16 GB，是一個XML格式文件。使用Python中Numba庫中特定的XML結(jié)構(gòu)解析包xml.etree.cEl-ementTree分析原始文件，同時使用jit裝飾部分函數(shù)加速程序運行，最終得到兩個目標文件，node.txt，way.txt。node文件中保存了路網(wǎng)中節(jié)點和節(jié)點的鄰接點信息，按行保存，每行結(jié)構(gòu)為{'Nd':node_id,'X':x,'Y':y,'Nn':Nn}。其中:Nd為節(jié)點在路網(wǎng)中的唯一標識；x，y為節(jié)點在路網(wǎng)中的橫軸和縱軸坐標；Nn為node_id的鄰接點集合。way文件中的數(shù)據(jù)按行保存，每行數(shù)據(jù)結(jié)構(gòu)為{'Wd':way_id,'Wn':Wn}，其中:Wd為路在路網(wǎng)中的唯一標識；Wn為路在路網(wǎng)中包含的節(jié)點集合，節(jié)點只保存id。這兩個文件主要保存鄰接點信息，故可以通過文件進一步處理出叉路口點，叉路口點的定義如下。

定義1(一叉路口點)路網(wǎng)中存在一條路L(a，b)∈S，a，b分別為該條路的端點，a，b∈N，且a，b∈L，則稱a，b稱為一叉路口點。

定義2(二叉路口點)路網(wǎng)中存在一條路L(L∈S，S為路網(wǎng)中所有路的集合)，若存在一點c∈L且c只在L一條路上，則稱c為二叉路口點。

定義3(三叉路口點)若路網(wǎng)中存在一點c∈N，當且僅當有3條路L1，L2，L3∈S，L1∩L2∩L3=c，且c為3條路的端點，則稱點c為三叉路口點。

以此類推可得到m叉路口點的定義，最終得到的二維坐標形式的叉路口點即為經(jīng)過處理的聚類原始數(shù)據(jù)集。其中只有坐標(x，y)在聚類算法中起作用，其余附加信息用于構(gòu)建索引、查詢信息等環(huán)節(jié)。

3.2 聚類結(jié)果分析

對原始數(shù)據(jù)集預(yù)處理后，使用密度分布特征明顯的四叉路口點進行聚類，同時使用外包多邊形包裹區(qū)分不同簇。算法參數(shù)需人為確定，在OSM路網(wǎng)數(shù)據(jù)中，點之間的距離以點坐標單位為衡量標準時彼此相距較遠，選取Tminpts=10，reps=100 時，符合本實驗數(shù)據(jù)密度分布。網(wǎng)格依據(jù)點的最小外包矩形圖平均劃分，單個網(wǎng)格長為578、寬為519。原始四叉路口散點圖如圖7，GDSCAN 算法聚類結(jié)果如圖8，對圖8進行局部放大，結(jié)果如圖9。

圖7 四叉路口散點圖Fig.7 Scatter plot of four-forked intersection

圖8 四叉路口聚類結(jié)果Fig.8 Clustering results of four-forked intersection

圖9 聚類結(jié)果局部放大圖Fig.9 Partially enlarged view of clustering results

比較圖7～9 可看出，點的密度分布呈東密西疏的特點，符合實際情況，即美國東北部的西南地區(qū)較為繁華，其余區(qū)域欠佳，因此西南方的叉路口數(shù)相對多。由此表明，聚類較好地保留了四叉路口的密度特性，可清晰區(qū)分出不同的簇，GDSCAN 算法的聚類效果較為理想。

為了進一步測試GDSCAN算法的運行效率，從實驗數(shù)據(jù)點集中抽取部分點進行GDSCAN 和DBSCAN 算法的速率測試實驗。在保證實驗參數(shù)與上文相同的情況下，對不同數(shù)量級的數(shù)據(jù)均進行10 次測試，并取平均耗時，對小于10 000 個點的的結(jié)果使用折線圖展示，結(jié)果如圖10。

圖10 兩種算法在不同數(shù)據(jù)集下的聚類耗時Fig.10 Clustering time of two algorithms underdifferent data sets

從圖10 可看出:數(shù)據(jù)點在2 000 個以下時，GDSCAN 和DBSCAN 算法的聚類耗時無顯著差距，GDSCAN耗時稍短；隨數(shù)據(jù)點增加，DBSCAN耗時極速增長，數(shù)據(jù)點達到10 000 個時，DBSCAN 需20 s才能將點聚類成功；而GDSCAN隨著數(shù)據(jù)集中點的增加，耗時平穩(wěn)線性增長，當數(shù)據(jù)集內(nèi)點達到10 000 個時，聚類耗時仍低于5 s，此時DBSCAN 耗時為GDSCAN的4倍多。

表1為數(shù)據(jù)點達到200 000個時，兩種算法的聚類耗時。由表1可看出，數(shù)據(jù)點達到200 000個時，DBSCAN 的聚類耗時是GDSCAN 的44 242 倍；數(shù)據(jù)點達到400 000 個時，DBSCAN 的聚類耗時是GDSCAN的94 293倍；對于500 000～700 000個數(shù)據(jù)點的大規(guī)模數(shù)據(jù)集，GDSCAN算法聚類耗時仍保持平穩(wěn)增長(DBSCAN耗時巨大，故僅記錄GDSCAN算法的聚類耗時)。

上述結(jié)果表明:DBSCAN算法聚類耗時依賴原始數(shù)據(jù)集的大小，數(shù)據(jù)集較小時處理時間在承受范圍內(nèi)，數(shù)據(jù)集增加時處理時間過長；而基于網(wǎng)格的DBSCAN算法在聚類過程中對原始數(shù)據(jù)集大小的依賴性低，在不同等級的數(shù)據(jù)集中都具較好表現(xiàn)；就本次北美路網(wǎng)數(shù)據(jù)的聚類處理而言，使用網(wǎng)格密度聚類算法具有較高的時間效率和較好的聚類結(jié)果。

表1 兩種算法的聚類耗時Tab.1 Clustering time of two algorithms

4 結(jié) 論

針對DBSCAN 算法對大規(guī)模數(shù)據(jù)聚類效率低下的問題，使用劃分網(wǎng)格的方法對DBSCAN 算法進行改進，提出一種基于劃分網(wǎng)格的密度聚類算法GDSCAN。以美國東北部區(qū)域的路網(wǎng)為實驗數(shù)據(jù)，采用GDSCAN算法對其進行聚類，并與DBSCAN算法的聚類耗時進行比較。結(jié)果表明，GDSCAN算法對大規(guī)模數(shù)據(jù)的處理較為理想，聚類效率有較大提升。但在合適的網(wǎng)格邊長和半徑的選取上GDSCAN算法還有進一步優(yōu)化的空間，后續(xù)研究將從鄰域半徑、網(wǎng)格邊長與數(shù)據(jù)點的關(guān)系考慮更高效合適的參數(shù)。