面向大規模交互數據空間劃分的Voronoi圖生成算法及應用 *

熊鵬文，周曉蕓，熊宏錦，張婷婷

(1. 南昌大學 信息工程學院， 江西 南昌 330031； 2. 海裝駐武漢地區軍事代表局， 湖北 武漢 333000；3. 陸軍工程大學 指揮控制工程學院， 江蘇 南京 210007 )

Shamos和Hoey于1975年在“最近問題”中提出了Voronoi 圖這一概念，從此拉開了計算幾何的帷幕[1]。傳統的Voronoi圖是由連接任意兩鄰點直線的中垂線連接構成的[2]。平面中的點到最近的Voronoi單元都比其他的點到該Voronoi單元的距離要近。傳統Voronoi圖研究的是單個點對單個點的空間關系，它將每個點都視為是相互獨立的。然而，在現實世界中，一個物體通常都處于和其他物體相互關聯的狀態中，我們不能僅僅把目光投向局部某個點，而應該從整體的角度去看待點與點之間的聯系。

因此，針對多核心Voronoi圖的研究受到了廣大研究人員的關注，并取得了一些成果。但是由于Voronoi單元核心的數量限制，或者點集數量的限制，抑或是計算方式的限制，多核心Voronoi圖都不能快速地對大規模數據進行空間劃分。Barequet等[3]提出了兩點核心Voronoi圖，但是Voronoi單元核心的數量限制導致該算法的應用具有局限性；Chen等[4]提出的聚類誘導 Voronoi 圖(Clustering Induced Voronoi Diagram，CIVD)，雖考慮了點與點之間的影響函數關系，但是由于算法過于煩瑣，只能生成小規模數據的Voronoi圖，因此效率較低、普適性較差。陳學森等[5]提出的基于集合影響力的Voronoi算法，雖然對Voronoi單元核心數量受到限制的問題進行了處理，但是需要人為輸入參數來調整Voronoi圖劃分的密度，實際處理起來較為復雜。盧嘉豪等[6]提出了平面相交多邊形的Voronoi圖，但是由于計算方式限制只能對少量目標進行Voronoi圖生成。萬靜等[7]提出了障礙空間中基于Voronoi圖的不確定數據聚類算法，但只考慮2級生成點以內的不確定數據和障礙情況，適用范圍窄。

對此，為了更深入地研究點集在空間的分布關系，本文將Voronoi圖的概念推廣到基于密度的聚類算法(Density-Based Spatial Clustering of Applications with Noise，DBSCAN)的Voronoi圖(Voronoi Diagram for DBSCAN，DBSCAN-VD)，不再將二維平面中的點集視作相互獨立的，而是通過聚類將點劃分成一個一個的點集，從而研究點集與點集之間的聯系。本文還提出一種自適應確定DBSCAN參數的算法，無須人為確定參數，通過利用數據集自身分布特性生成候選和參數[8]，自動尋找聚類結果的簇數變化穩定區間，并將該區間中密度閾值最少時所對應的和參數作為最優參數。DBSCAN參數的自動選取不僅可以節省計算參數的時間，而且可以有效提高聚類的準確效果。最后以顯微鏡下嗜中性粒細胞的圖像和我國地表火點分布圖作為仿真實例，驗證DBSCAN-VD算法解決大規模數據下空間劃分問題的有效性。

1 DBSCAN聚類原理

DBSCAN聚類算法是一種基于密度的聚類算法，它可以在帶有噪聲的空間數據庫中發現任意形狀的聚類。DBSCAN聚類算法具有良好的抗噪能力。關于DBSCAN聚類算法的定義[9]如下：

定義1Reps鄰域。假設存在空間中的點集D，?p∈D，以對象p為中心、以給定半徑Reps為半徑的鄰域稱為對象p的Reps鄰域。

定義2密度閾值Tminpts。假設存在空間中的點集D，?p∈D，稱滿足對象p成為核心點的值為密度閾值Tminpts。

定義3核心點。 假設存在空間中的點集D，?p∈D，?{p1,p2,…，pn}∈D，p1,p2,…，pn在對象p的Reps鄰域內，若Reps內點數大于Tminpts，表示對象p的Reps鄰域內對象個數大于密度閾值，則定義p為核心點。

定義4邊界點。假設存在空間中的點集D，?p∈D，?{p1,p2,…，pn}∈D，若Reps鄰域內點的數量小于Tminpts，且落在核心點的鄰域內，則稱以上定義點為邊界點。

定義5噪聲點。假設存在空間中的點集D，?p∈D，既不是核心點也不是邊界點，則稱p為噪聲點。

DBSCAN算法的流程首先是將所有點標記為核心點、邊界點或噪聲點[10]。DBSCAN聚類演示如圖1所示，A點為核心對象，以A點為圓心的Reps鄰域內找到其他點。然后以各自的點為圓心、Reps為半徑作圓，直到鄰域內任意一個點在以Reps為半徑作圓時，Reps鄰域不能囊括其他點，則該點稱之為邊界點B、C。N點不能被任何以核心點為圓心、Reps為半徑的圓包裹進去，所以稱之為離群點。圖中黑色箭頭的指向表示密度可達，以A點為圓心、Reps為半徑的圓構成的集合中包含了所有的密度直達樣本，集合外的均不能密度直達，在這些密度可達的樣本序列的Reps鄰域內，所有的樣本相互都是密度相連的[11]。

圖1 DBSCAN聚類演示Fig.1 DBSCAN clustering demonstration

2 基于自適應DBSCAN聚類的Voronoi圖的定義

2.1 傳統Voronoi圖的定義

Voronoi圖是對空間的最鄰近劃分[12]，在給定一些目標的情況下，將空間劃分成若干個區域，所有劃分區域內的任意一點都距離該區域內的目標最近。傳統Voronoi圖是根據平面點集繪制的分割圖像，是針對每一個點與其他點之間的位置關系進行鄰域劃分。圖2所示的是一個點集數量為8的Voronoi圖，這8個點為Voronoi圖的核心點，平面空間被任意兩點連線的中垂線劃分成若干個區域，這些區域為Voronoi單元，每個Voronoi單元中的任意一點都距離該Voronoi單元中的核心點最近。

圖2 傳統點集Voronoi圖Fig.2 Voronoi diagram of traditional point set

令P={p1,p2,…,pn}為平面上n個點的集合，其中pi表示集合中的任意一點，d(p,q)表示點p與點q之間的歐式距離，則定義：

V(pi)={x|d(x,pi)

集合V(p)={V(p1)，V(p2)，…，V(pn)}便是Voronoi圖[13]。

Voronoi圖給出了平面的空間劃分，集合中的元素為Voronoi核心點，如圖2中的8個點。V(pi)是一個域，為對應于pi的Voronoi域，也稱作Voronoi單元。劃分平面空間的線段，即Voronoi單元的邊界，為Voronoi邊。

2.2 DBSCAN-VD與傳統Voronoi圖的關系

傳統Voronoi圖是針對每一個點進行Voronoi單元劃分，Voronoi單元的數量隨著點集的數量增加而增加。在點集數量過大的情況下，Voronoi圖劃分會產生圖像分割過于密集、Voronoi單元格過多的問題。如圖3所示的點集為500的Voronoi圖，由于目標數量較多，對每一個點進行Voronoi分割產生的劃分結果過于細致，實際應用價值很小。

圖3 500個點的Voronoi圖Fig.3 Voronoi diagram of 500 points

因此，由問題出發引出基于自適應DBSCAN聚類的Voronoi圖(DBSCAN-VD)生成算法研究。DBSCAN-VD的示意如圖4所示，為了便于觀察，同一種顏色的點表示通過DBSCAN聚類歸納為一類的點集。圖中有五種顏色的小圓，分別代表五類點集，每個點集中的藍色小點則是代表點集的核心，最后再以點集的核心生成傳統Voronoi圖。DBSCAN-VD算法就是依據最近鄰關系，將這五個點集進行劃分。

圖4 DBSCAN-VD的簡化形式Fig.4 Simplified form of DBSCAN-VD

2.3 DBSCAN-VD的定義

DBSCAN-VD算法通過對生成的點集進行聚類，從而生成若干個點與點之間有密切聯系的點集的子集，再在這基礎上生成點集的子集的Voronoi圖。在通過對該Voronoi圖的定義、性質進行研究之后，得出基于DBSCAN聚類的Voronoi圖的生成算法。

定義6平面上存在一個點p和一個點集s，定義p到s的距離為p到點集s中最近一點的距離值。

d(p,s)=inf(d(x,p)|x∈s)

(1)

定義7平面上存在一個以點集為元素的集合S，S={s1,s2,…,sn}，其中si表示一個點集，Voronoi圖定義為平面上距離si最近的點的集合。

V(si)={x|d(si,x)≤d(sj,x),?si∈S，sj∈S,i≠j}

S的Voronoi圖為：

V(S)={V(s1),V(s2),…，V(sn)}

(2)

定理1給定平面上的一個集合S={s1,s2,…,sn}，其中

(3)

(4)

證明：

根據定義6，p0離si最近。再根據定義7，可以得到

p0∈V(si)

所以

另外，

然后

可以得到

所以

因此

□

定理1實際上是依據Voronoi圖的最近鄰關系，對點集與點集之間進行劃分。上述推導在數學上證明了DBSCAN-VD生成算法的合理性，接下來通過仿真實驗來證明算法的正確性。

3 DBSCAN-VD的基本生成算法

本文提出的DBSCAN-VD的基本生成算法首先采用自適應參數最優法[14]得出DBSCAN聚類所需的兩個參數值Reps和Tminpts，然后對生成的點集進行DBSCAN聚類，找出點與點之間的空間關系，從而將點集劃分為若干個點與點之間有密切聯系的點集的子集，最后生成聚類后形成的子集的Voronoi圖。

3.1 DBSCAN聚類參數的確定

DBSCAN聚類的第一步就是確定Reps和Tminpts這兩個參數的值[15]。Reps和Tminpts體現了聚類的合理性，從而決定了DBSCAN-VD生成的效果。為了確保聚類后產生的點集的子集規模不過大或過小，本文采用的自適應DBSCAN-VD算法可以自動確定參數值，提高了聚類的準確度。

基于DBSCAN算法，定義密度閾值Tdensity為Reps鄰域內存在的Tminpts個數據點，可以得到：

(5)

首先定義聚類的“距離”：本文將歐式距離作為聚類距離。計算數據集D的距離分布矩陣，即

Dn×n={Ddistance(i,j)|1≤i≤n,1≤j≤n}

(6)

其中：Dn×n為n×n的實對稱矩陣；Ddistance(i,j)為數據集D中第i個對象到第j個對象的距離。

Reps參數列表是通過K-平均最近鄰法和數學期望法產生的，通過計算數據集D中每個數據點與其第K個最近鄰數據點之間的K-最近鄰距離，并對所有數據點的K-最近鄰距離求平均值，得到數據集的K-平均最近鄰距離。第K列的元素構成所有數據點的K-最近鄰距離向量DK。對向量DK中的元素求平均，可得到向量DK的K-平均最近鄰距離，并將其作為候選Reps參數，Reps參數列表表示為：

(7)

然后采用數學期望法生成Tminpts參數列表，再依次求出每個Reps參數對應的Reps鄰域對象數量，并計算所有對象的Reps鄰域對象數量的數學期望值，作為數據集D的Tminpts參數，表示為：

(8)

其中，Pi為第i個對象的Reps鄰域對象數量，n為數據集D中的對象總數，最后求解出聚類類別數列表。

根據數據集提取出Reps候選項(按從小到大排列)，然后再提取出Tminpts候選項，隨后用這些候選項嘗試使用DBSCAN算法進行聚類，如果連續的候選項聚類的類別數目相同， 那么選擇Reps相對較大的那個作為最終參數輸入DBSCAN算法中去。

3.2 點集劃分處理

首先對需要進行空間劃分的物體提取二維平面點集，接著以每個點為圓心、Reps為半徑的圓來搜索簇，當點p的Reps鄰域包含的點數大于Tminpts時，創建一個以p為核心點的新簇。聚類算法依據Reps和Tminpts找出所有核心點，然后分別以核心點為起點，找出由其密度可達的對象生成的新簇，直到遍歷完所有點便結束。如圖5所示，虛線表示Reps鄰域，p1是核心對象，p2由p1密度直達，p3由p1密度可達,p3與p1密度相連。

圖5 點集劃分處理過程Fig.5 Point set division process

3.3 DBSCAN-VD生成算法步驟

由定理1得到生成算法的具體步驟如算法1所示。

算法1 DBSCAN-VD的生成

圖6展現了算法的過程。由圖6可以清晰地看出算法的核心思路：首先隨機生成點數為5 000的點集，然后對點集進行DBSCAN聚類生成若干個子集，最后用傳統Voronoi圖算法生成由點集的子集構建的Voronoi圖。定理1可以證明該算法思路的正確性。

(a) 聚類圖(a) Cluster diagram (b) Voronoi圖 (b) Voronoi diagram圖6 點集數量為5 000時的Voronoi圖生成結果Fig.6 Result of Voronoi diagram generation when the number of point sets is 5 000

F值是一種評價聚類結果的綜合指標。設正確率Cprecision為判斷正確的數據個數占識別出的數據個數的百分比；召回率Crecall為判斷正確的數據個數占實際的數據總數的百分比。則F值表示為：

(9)

在聚類結果簇數正確的前提下，密度閾值越小，則噪聲率越低，而且聚類結果的F值呈增大趨勢。這是由于隨著密度閾值的降低，越多的低密度數據點被劃分進簇，因此噪聲率變低，同時F值的增大則表明準確率增加，聚類結果趨于正確。聚類結果對比如表1所示。

表1 聚類結果對比

從F值評價指標來看，對不同類型的數據集進行聚類，DBSCAN-VD算法均優于對比算法，說明DBSCAN-VD算法具有較高的精確性。

4 仿真實例及分析

為了證明本文算法的有效性和可靠性，采用Python和OpenCV 2.4.11對算法進行了實現。實驗環境為Windows7操作系統，8 GB 內存Intel i5-6500, 3.20 GHz 處理器。

4.1 嗜中性粒細胞的劃分

白細胞是人體內血液中的一種細胞，醫學上往往檢測白細胞的形態和數量作為疾病診斷的依據[16]。正常情況下機體的白細胞數目為4.0×109/L～10.0×109/L。當機體發生炎癥等疾病時均會造成白細胞數目的變化, 因此檢測白細胞的形態和數量對人體檢測疾病來說具有重大意義。血常規檢測中，醫生根據各個參考值分析白細胞的各個指標，從而對機體進行初步分析[17]，具體白細胞的數值與人體機能的關系如下：

1)白細胞計數增多。當人體內的白細胞總數每微升超過10 000個時，一般被診斷為病理性白細胞升高。病理性升高最常見的原因是感染，尤其是細菌感染，感染程度越高，白細胞的數量越大，呈正比關系。

2)白細胞計數減少。當人體內的白細胞總數每微升少于4 000個時，一般會被診斷為病理性白細胞降低。病理性降低最常見的原因是病毒感染，如流行性感冒、病毒性肝炎、水痘等，均能引起病理性白細胞降低。

因此，檢測白細胞數目可以為人體疾病的診斷提供依據，白細胞數目的大小也可以反映該疾病的嚴重程度。

驗證過程為：首先從嗜中性粒細胞鏡下圖片中提取出二維平面點集，如圖7所示。

圖7 嗜中性粒細胞顯微鏡下圖片Fig.7 Microscope diagram of neutrophils

然后將采集到的點集調用DBSCAN-VD算法，得出結果如圖8所示。由圖8可知，實例產生了19個Voronoi單元格，在目標對象為大規模嗜中性粒細胞的情況下，DBSCAN-VD算法大大減少了Voronoi單元的數量，更能清晰地觀察嗜中性粒細胞群的分布情況，而不是像傳統Voronoi圖對每一個嗜中性粒細胞進行Voronoi劃分。

(a) 聚類后的圖片(a) Picture after clustering (b) DBSCAN-VD的劃分(b) Division of DBSCAN-VD圖8 嗜中性粒細胞顯微鏡下DBSCAN-VD圖Fig.8 DBSCAN-VD diagram of neutrophil under microscope

本文采用該仿真實例對基于集合影響力的多點核心Voronoi圖算法進行比較，結果如下：

MPUVD(multi-point and unique Voronoi division)算法需要代入參數ε=1.2進行計算(ε為調整點集劃分的密度參數，需要人為調整)，得出近似優結果如圖9所示。實例共計算1 038個采樣點，生成了59個多點核心單元格。

圖9 MPUVD算法Voronoi劃分圖Fig.9 Voronoi partition diagram of MPUVD algorithm

本文DBSCAN-VD算法無須輸入聚類參數，結果如圖10所示。自動生成19個Voronoi單元格，在目標對象為大規模嗜中性粒細胞的情況下，DBSCAN-VD算法大大減少了Voronoi單元的數量，更能清晰地觀察嗜中性粒細胞群的分布情況。

圖10 DBSCAN算法Voronoi劃分圖Fig.10 Voronoi partition diagram of DBSCAN algorithm

DBSCAN-VD算法的優勢有以下幾點：

1)采用DBSCAN-VD算法可以減少Voronoi單元的數量，從而提高Voronoi圖的生成效率。

2)采用DBSCAN-VD算法可以保證聚類效果的準確性和合理性。

3)DBSCAN-VD算法可以根據離散點分布情況自動生成聚類參數，而MPUVD算法的參數需要多次調試才能獲得。

4.2 地表火點的空間劃分

火是引起地球表面異常的重要因素，可以驅使自然界森林、灌木、草原等生態系統植被的演替。植被燃燒過程中的火產生出大量的氣溶膠粒子以及各種微量氣體，對大氣環境和全球碳循環有著重大的影響。如圖11所示，本文采用地表火點數據來驗證DBSCAN-VD的實際應用效果，地表火點數據來自中國科學院遙感與數字地球研究所研發的SatSee-Fire近實時地表高溫異常點查詢服務系統。

圖11 地表火點數據分布Fig.11 Distribution diagram of surface fire data

驗證過程為：首先由地表火點數據分布圖找出火點的地理位置，然后提取二維平面中點集，如圖12所示。

圖12 地表火點數據分布的二維平面點集Fig.12 Two-dimensional plane point set for the distribution of surface fire data

將采集到的點集調用DBSCAN-VD算法，得出結果如圖13所示。 由圖13可知，實例產生了23個Voronoi單元格，在目標對象為大規模地表火點的情況下，DBSCAN-VD算法大大減少了Voronoi單元的數量，可以更清晰地看出我國地表火點在空間上的劃分，由此得到精確的火點高發區域。如圖13所示，我國南部、東南亞和西亞是地表火點的高發區域，DBSCAN-VD算法可以提高地表火點的預防和監測效率、精度。

(a) 聚類后的圖片(a) Picture after clustering (b) DBSCAN-VD的劃分(b) Division of DBSCAN-VD圖13 地表火點的DBSCAN-VD圖Fig.13 DBSCAN-VD diagram of surface fire

上述嗜中性粒細胞、地表火點的仿真實例充分證明了本文提出的DBSCAN-VD算法突破了傳統Voronoi圖在劃分對象為大規模點集時, 產生圖像分割過度的問題。這不僅為Voronoi圖發展做出了貢獻，也讓Voronoi圖應用更加廣泛。

5 算法復雜度分析

對于二維數據而言，DBSCAN 算法的基本時間復雜度為O(n2)，n為數據集中數據點的數目。自適應DBSCAN算法在DBSCAN算法的基礎上進行迭代運算，迭代次數由最優參數對應的K值大小決定，在算法實際運行過程中，K遠小于n時，聚類過程即發生收斂。因此，DBSCAN-VD的時間復雜度為O(Knlnn)。Voronoi圖的基本時間復雜度為O(nlnn)，本文提出的該算法復雜度為O(Knlnn)+O(nlnn)。

綜上，本文算法的算法復雜度雖然較傳統Voronoi圖算法略高，但是提升了聚類的精確性，適用于點集數量較大時生成Voronoi圖的應用場景。

6 結論

目前，傳統單點Voronoi圖很難適用于大規模數據下的空間劃分。本文從大規模點集進行Voronoi圖劃分時產生Voronoi單元個數過多而導致分割過度的問題出發，提出了一種基于自適應DBSCAN聚類的Voronoi圖。通過對顯微鏡下嗜中性粒細胞、地表火點數據進行DBSCAN-VD仿真，結果可得DBSCAN-VD算法適用于大規模數據下的空間劃分，突破了傳統Voronoi圖單點對單點的一種劃分形式，為Voronoi圖應用于地理信息系統、生物醫學等領域拓寬了應用。在今后的工作中，將從點集的Voronoi圖推廣到多邊形集合的Voronoi圖，并且針對Voronoi圖嘗試改良其生成算法，提高算法的運算效率。