障礙空間中Voronoi圖優化的反向近鄰數聚類算法

何云斌，劉婉旭，萬 靜

哈爾濱理工大學 計算機科學與技術學院，哈爾濱 150080

聚類在統計數據分析、圖像處理、模式識別等領域的應用十分廣泛，是一種常用的無監督分析方法。它根據數據樣本的相似程度將樣本劃分為若干個簇，其目的是使得同一個簇中的樣本相似性大，不同簇間的樣本相似性小。現有的聚類算法以所采用的基本思想為依據將它們分為五類，即基于劃分的聚類、基于層次的聚類、基于網格的聚類、基于模型的聚類以及基于密度的聚類方法。

選址問題在物流、生產和生活方面有著廣泛的應用，比如物流中心、垃圾廠、ATM 機的放置等。隨著互聯網的發展，越來越多的人選擇在網上購物，物流發展迅速，物流中心選址的好壞直接影響到服務質量和成本，合適的選址會給人們生活帶來便利。由于在現實世界中存在河流、山川等許多障礙，障礙物的存在增加了選址問題的困難。

事實上聚類的結果會受到障礙的影響。例如圖1中，當空間中不存在障礙物時，很明顯聚類簇數為2。而在圖2 中，由于障礙的存在，將原有的兩個聚類分成了4 個聚類。因此，障礙的存在會影響聚類結果。

圖1 空間中不存在障礙物時的聚類結果Fig.1 Clustering results in absence of obstacles in space

圖2 空間中存在障礙物時的聚類結果Fig.2 Clustering results in presence of obstacles in space

近年來，隨著障礙空間中的聚類算法在互聯網上不斷出現，障礙聚類算法的研究越來越受到人們的重視。文獻[10]首次提出了障礙空間中的聚類問題，并給出了一個帶障礙的聚類算法CODCLARANS（clustering with obstructed distance clustering algorithm based on randomized search），該算法能有效地實現帶障礙的聚類，但需占用大量的內存資源，障礙的數量和形狀對算法的執行時間影響較大。因此文獻[11]提出了一種基于網格的帶障礙的聚類算法DCellO，該算法以網格為基礎，將基于密度的聚類算法與圖形學中的種子填充著色算法相結合，削減了計算量，能夠在有障礙存在的情況下進行任意形狀的帶障礙的聚類并能更好地處理噪聲點。Voronoi 圖是由圖中各個相鄰點連線的中垂線組成的連續多邊形組成的，其臨近特性在解決計算機幾何領域的相關問題時發揮著重要作用。曹科研等人在文獻[12]中提出了一種障礙空間中的不確定數據聚類算法OBS-UK-means（obstacle uncertain K-means），并在此算法的基礎上運用R 樹、Voronoi 圖兩種剪枝方法和最短距離區域的概念相結合，減少了計算量，聚類結果與單純考慮障礙約束算法相比執行效率更好，實用價值更高。萬靜等人引入計算幾何中的Voronoi 圖對數據空間進行劃分，提出障礙空間中基于Voronoi 圖的不確定數據聚類算法。該算法根據Voronoi 圖的性質，利用KL 距離進行相似性度量，根據障礙集合是否發生變化，分別提出靜態障礙環境下和動態障礙環境下的不確定數據聚類算法。文獻[14]提出了一種基于約束的密度聚類算法，該算法將障礙物建模作為預處理步驟，結合DBSCAN（densitybased spatial clustering of applications with noise）算法，能夠檢測任意形狀和大小的聚類，對噪聲和輸入次序不敏感。這些算法雖然通過實驗驗證取得了良好的聚類效果和準確性，但需人工輸入相關參數，若參數選取不當則會造成錯誤的聚類結果。

為了解決現有的障礙空間聚類算法大多都需要人工輸入相關參數的問題，本文先引入Voronoi 圖來計算反向近鄰數，進而確定聚類中心來進行初始聚類，并針對初始聚類結果不精確的問題提出內邊界點、外邊界點、拓展點、剔除點等概念來提高聚類準確性，理論研究和實驗表明本文算法具有較高的準確性。

1 基本定義與說明

（可見點與不可見點）令二維平面上存在的兩點、與障礙物集合的交點個數為，若≤1，則稱、是相互可見的，、互為可見點；若≥2，則稱、互相不可見。

（障礙空間距離）在障礙空間中，如果對象和之間沒有障礙，即兩個對象互為可視，則障礙空間中兩個對象之間的距離為歐氏距離，記為(,)。如果對象和之間存在障礙，則兩個對象之間的距離是繞過障礙的最小距離,記為(,)。

如圖3 所示，對象和之間存在障礙物,、、、、分別為障礙物的頂點。則和之間的障礙空間距離是繞過障礙物的最短距離：

圖3 障礙空間距離Fig.3 Obstacle space distance

(,)=min((,)+(,),(,)+(,)+(,))

（反向第近鄰數(x)）對于給定數據集，數據點x作為其他點近鄰的次數記為(x)，則(x)稱為點x的反向第近鄰數。即_(x)={|x∈NN(),∈且≠，符合此條件的數據點的個數為}。

（Voronoi 圖）給定一組生成點={,,…,x}∈R，其中2 ＜＜∞，且當≠時，x≠x，其中,∈{1,2,…,}。由x所決定的區域稱為Voronoi單元VX，Voronoi 圖構成為()={(),(),…,(x)}，其中(x)表示的是x所在的Voronoi單元。

（鄰接多邊形）共享相同邊的Voronoi多邊形稱為鄰接多邊形，它們的生成點被稱為鄰接生成點。Voronoi 單元中存在幾條邊，就會有幾個鄰接多邊形。

根據Voronoi圖的結構和定義可以得出兩個基本性質。

（任意兩個多邊形不存在公共區域）Voronoi 圖將數據對象集合中的數據按照其最近鄰特性將空間進行劃分，生成互不重疊的區域。

（臨近特性）生成點x與鄰接多邊形中的鄰接生成點距離最近。

（Voronoi 圖的級鄰接生成點）給定一組生成點={,,…,x}∈R。 x的級鄰接生成點定義如下：

（1）一級鄰接生成點(x)={x|(x)和(x)有公共邊}；

（2）(≥2) 級鄰接生成點AG(x)={x|(x) 和(x)有公共邊，∈AG(x)}。

（樣本點密度）給定數據集，則其樣本點密度可以定義為：

其中，NN()為數據點的近鄰數據集，(,)為數據點和的障礙空間距離。

（聚類半徑）數據集中所有未聚類的數據點與代表點C的障礙距離均值，即為聚類半徑，聚類半徑表達式為：

其中，數據集中所有數據點集合為={,,…,x}，為C的可視點集中元素數目，為C的不可視點集中元素數目，+=。

（內邊界點、外邊界點）初始聚類后，類簇內的點且其所在的多邊形的頂點或邊與聚類邊界有交點，這樣的點定義為此類的內邊界點。內邊界點在聚類圓外的一級鄰接生成點定義為此類的外邊界點。內邊界點作為剔除點的候選集，外邊界點作為拓展點的候選集。

（剔除點）計算初始聚類內個點的平均反向近鄰數，若內邊界點的反向近鄰數小于平均反向近鄰數，則此內邊界點為剔除點。平均反向近鄰數計算公式為：

其中，為初始聚類圓中數據點的個數。

（拓展點）在聚類外邊界點中找到離內邊界點（非剔除點)的距離小于此內邊界點在聚類圓內最近的點的距離的點作為拓展點，加入到此聚類中。

如圖4 所示，為聚類中心，內邊界點集為{,,,,,}，其中假設根據式（2）計算得知又為剔除點。外邊界點集為{,,,,,,,,,,}，其中、又為拓展點。

圖4 內外邊界點、剔除點、拓展點的示例Fig.4 Example of inner and outer boundary points,culling points and extension points

2 基本工作

2.1 聚類中心的選取

初始聚類中心點選取得恰當與否直接影響最終聚類效果的好壞。正確地選取初始聚類中心點會得到較高的聚類準確率，大大縮短算法的時間；相反，中心點選取不當會出現錯誤的聚類結果，后續對錯誤的結果進行分析會得出錯誤的結論。文獻[16]提出利用反向近鄰數來確定聚類中心，雖然能夠恰當地選取聚類中心，但會有較高的時間復雜度或空間復雜度。本文根據Voronoi圖的性質對原有算法進行改進，挑選出合適的初始聚類中心，并用這些點進行聚類分析。

由反向近鄰數的定義可見，對于一個數據集中的數據點，其_值越大，則說明該點被更多的點包圍，直觀上它看起來更像數據集的質心。因此，選擇從反向近鄰數最大的數據點開始構建連通區域。

本節主要利用Voronoi 圖來計算反向近鄰數，Voronoi 圖的鄰近特性使得數據點在計算其第近鄰時只需計算幾個點的障礙距離，而不需要計算出所有點的障礙距離，這大大地減少了計算量，下面給出定理1 用于反向近鄰數的計算。

數據點的第+1 近鄰一定在的第(1 ≤≤)近鄰的鄰近單元格內。

當=1 時，的第二近鄰點一定在的鄰接多邊形或者的最近鄰的鄰接多邊形中；當＞1時，假設為的第+1 近鄰，且不在的第(≤)近鄰的鄰接多邊形中，則根據Voronoi 圖的鄰接特性，必有一點使得到的第(≤)近鄰的距離小于到的第(≤)近鄰的距離。這與題設矛盾，因此假設不成立，從而定理得證。

如圖5 所示，假設點、分別為的最近鄰和第二近鄰，則的第三近鄰一定在點、、的鄰近多邊形中，根據計算得出，點的第三近鄰為點。

圖5 定理1 的示例Fig.5 Example of theorem 1

使用定理1 可以在已知數據點的第近鄰的前提下快速計算出數據點的第+1 近鄰，但在障礙空間中，因為障礙物的存在會讓兩個數據點之間的距離變大，所以在計算距離時需要計算兩個數據點之間的障礙空間距離。

如圖6 所示，若在點和之間存在障礙物，且(,)大于(,)，則的第三近鄰為。

圖6 障礙物對計算第k 近鄰的影響Fig.6 Influence of obstacles on calculation of k nearest neighbor

根據定理1 提出基于Voronoi 圖的反向近鄰數的算法V_RkNN，其具體步驟如算法1所示。首先，初始化各個數據點的反向近鄰數_(x)=0，從=1開始，根據定理1計算各個數據點的第近鄰，若數據點的第近鄰為，則_(x)加1。當所有點計算完第近鄰后，統計此時沒有反向近鄰數的點，即_(x)=0 的點的個數，記為() 。如果從-1 近鄰到近鄰的值不變，則進一步計算每個點的+1近鄰，如果值仍不變，則說明此個點相對其他點來說比較分散，且與其他點距離較遠，則將_(x)由大到小降序保存在集合中。

V_RkNN 算法

輸入：數據集={,,…,x}，障礙物集。

輸出：聚類中心候選集合、。

算法時間復雜度和空間復雜度分析：假設數據集中數據點的個數為。步驟2 計算每個數據點的第近鄰，其時間復雜度為()，最壞情況下，數據集中每個數據點自成一類，需要計算每個數據點的第近鄰，其空間復雜度為()，但是這種情況出現概率較低。一般情況下，其空間復雜度為()，其中?。步驟6采用快速排序，時間復雜度為(lb)，其空間復雜度為(lb)。綜上所述，時間復雜度為(lb)，空間復雜度為()。

2.2 離群點的篩選和剪枝

本節討論數據集中的離群點處理。離群點是指屬性值明顯不同于其鄰近對象，偏離了大多數數據行為或數據模型的異常數據。離群點的存在使得聚類的質量和效率大大減小，因此在聚類之前去除離群點是非常有必要的一個步驟。下面給出本文離群點的判定定理和判斷規則：

_(x)=0 的點一定是離群點。

假設數據點不是離群點，則點必定是某一數據點的第近鄰，那么_()必定不為0，這與題設矛盾，因此假設不成立，從而定理得證。

根據樣本點密度的定義可知，對于一個數據集中的數據點，其樣本點密度越小，則說明該點被更少的點包圍，從直觀上來看，更可能是離群點。因此從這個角度出發，如果一個數據點的樣本點密度低于整個數據集的平均密度，那么它就可能成為離群點。因此本文的離群點還可以從那些處于平均密度以下的數據點中進行篩選和剪枝操作。為了降低算法的計算量，本文利用Voronoi 圖進行查找。下面提出規則和定理3 來進行離群點的篩選。

如果一個數據點的一級鄰接生成點均為離群點，那么這個數據點是一個離群點。

假設、為兩個均低于平均密度的數據點，且數據點的樣本點密度大于數據點的樣本點密度。如果數據點是離群點，則數據點也一定是離群點。

假設數據點的樣本點密度大于數據點的樣本點密度，根據樣本點密度的定義可知，數據點的樣本點密度與其周圍的數據點分布有關，如果一個數據點是離群點，那么該數據點則處于一個相對稀疏的區域。由此可知，若數據點是離群點，那么數據點處于稀疏區域，而數據點的樣本點密度大于數據點的樣本點密度，那么數據點一定處于一個更為稀疏的區域，那么數據點肯定為離群點，從而定理得證。

通過以上論述和分析以及提出的定理和規則，下面給出關于離群點篩選剪枝算法outlierX的主要思想：給定數據集，首先根據算法1對所有_(x)=0的數據點進行剪枝。再計算數據集中的數據點的樣本點密度，進而算出平均密度并篩選出所有低于平均密度的數據點，按樣本點密度遞減順序進行排序，并存入中。然后，將所有數據點作為生成點，生成Voronoi 圖，將集合中的數據點根據樣本點密度大小從大到小進行逐個判斷是否為離群點，如果數據點是離群點，則從數據集中刪除數據點以及中所有位于之后的數據點，并停止判斷，離群點篩選剪枝算法過程結束。下面給出具體的離群點篩選剪枝算法outlierX，如算法2所示。

outlierX 算法

輸入：數據集={x|=1,2,…,}。

輸出：過濾后的數據集′。

算法時間復雜度和空間復雜度分析：假設數據集的大小為，篩選過后的數據集的大小為。算法有三個循環，步驟3～5 的時間復雜度為()，空間復雜度為()。步驟7～11 為第二個循環，遍歷了整個數據集，因此時間復雜度為()。第12步使用快速排序的方法對數據集進行降序排序，的大小為，因此時間復雜度為(lb)，空間復雜度為(lb)。第13～18 步為第三個循環，由于遍歷的是篩選后的數據集，且遇到數據點是離群點時停止遍歷，時間復雜度不大于()。綜上所述，該算法的時間復雜度為(lb)，空間復雜度為()。

2.3 廣義覆蓋圓

在帶有障礙物的空間內聚類，由于平面內的距離不能簡單地由兩點的直線距離來刻畫，一般的覆蓋圓則失去了效果。本文根據文獻[17]，引入廣義覆蓋圓來解決有障礙物的聚類問題。

在障礙物存在的情況下，定義平面內到聚類中心x的障礙距離等于聚類半徑的點的集合叫作x的廣義覆蓋圓，圓內的所有點即為同屬于聚類中心x的類簇的點。

如圖7 所示，數據點x為聚類中心，四邊形為障礙物，其中|xF|的距離為聚類半徑。若不存在障礙物，則初始聚類包含圓中所有點，現存在障礙物，使得數據點集{,,…,}到聚類中心x的距離大于聚類半徑，故不在以x為聚類中心、以為聚類半徑的初始類簇中。

圖7 廣義覆蓋圓的示例Fig.7 Example of generalized covering circle

3 OBRK-means數據聚類算法

基于以上分析和討論，下面給出障礙空間中的聚類算法（obstacle based on nearest-means，OBRKmeans）的主要思想：首先將數據集中的數據點作為鄰接生成點，生成Voronoi 圖。根據算法1 得到一個按照反向近鄰數由大到小的Hash 表。然后利用算法2 篩選和剪枝離群點，得到新的數據集′。將表中第一個數據點作為聚類中心C，根據式（2）計算聚類半徑，若在其中存在障礙物，則形成一個廣義覆蓋圓進行聚類；反之，則形成一個覆蓋圓開始聚類。根據式（3）在聚類內邊界找出剔除點并從此類簇中刪掉。在覆蓋圓內邊界點的鄰近多邊形內找到拓展點加入此聚類中，直到此類聚完。刪掉數據集中已聚類的數據點，在剩余點中繼續執行以上操作，直至所有點聚類完成。

OBRK-means算法

輸入：數據集，障礙集。

輸出：障礙空間下的數據聚類結果。

算法時間復雜度和空間復雜度分析：假設數據集的大小為。經過上一章的分析可知第1 步和第2 步的時間復雜度均為(lb)，空間復雜度分別為()和()。步驟3～15 主要是計算聚類半徑需要耗費時間，計算聚類半徑的時間復雜度為()，并未占用額外的空間。綜上所述，總時間復雜度為(lb)，總空間復雜度為()。

4 實驗結果與分析

本章主要通過實驗對所提出的OBRK-means 算法和文獻[12]中提出的DBCCOM 算法進行性能分析與比較。實驗硬件環境為8 GB 內存，IntelCorei5處理器，Windows10 操作系統，程序用Java編寫。

UCI數據集是公認、公開的機器學習數據集，許多聚類算法都使用其驗證聚類算法準確率和有效性。因此本文選擇UCI 數據集中的數據作為本文實驗的真實數據集，實驗所需數據集的詳細情況如表1所示。

表1 UCI實驗室數據集Table 1 UCI laboratory datasets

實驗主要考慮四方面因素：數據基數、障礙物數量、CPU 運行時間、聚類質量。利用以上四方面作為衡量算法的指標。

常用的聚類有效性評測有內部評價法、外部評價法和相關性測試評價。它們能對聚類結果進行評價，得出聚類結果是否最優。實驗采用F-measure 熵作為聚類外部評測標準，簡寫為F 值。用輪廓系數（Silhouette coefficient）作為評價聚類內部有效性的指標，簡寫為S 值。

分別對各個算法進行100 次獨立聚類實驗，統計每次實驗的結果，然后對每種算法求100 次實驗結果的平均值，對比算法的實驗結果如表2 如示。

表2 算法評測有效性對比Table 2 Comparison of effectiveness of algorithms

結果顯示，對于以上4 組數據集，OBRK-means算法的F-measure 指標平均值和S 指標平均值均高于DBCCOM 算法的評測指標。通過實驗可看出，OBRK-means算法表現出更好的聚類效果。

接下來從樣本數目和障礙物對聚類結果的準確率和CPU 響應時間的影響進行分析。具體情況為：對于聚類算法的準確率來說，無論是增加樣本數目還是障礙物的數目，OBRK-means 算法的性能更優。OBRK-means 算法和DBCCOM 算法的CPU 響應時間均隨著樣本數目和障礙物數量的增加而增加，但本文提出的OBRK-means算法因使用Voronoi圖進行距離度量更高效，其時間復雜度為(lb)，而DBCCOM的時間復雜度為()，因而相比之下本文算法的CPU 響應時間更少。

由圖8 到圖11 的折線趨勢圖可知，與聚類算法DBCCOM 相比，本文提出的OBRK-means 算法在處理障礙空間中的數據集時所得聚類結果的準確率和精度更高，這說明使用OBRK-means 算法聚類出的數據，類內緊密度更高，類間相似度更小。因此本文提出的OBRK-means 算法在處理障礙空間中的數據時，所得聚類結果更好。

圖8 樣本數目對準確率的影響Fig.8 Effect of sample size on accuracy

圖9 障礙物數目對準確率的影響Fig.9 Effect of obstacles on accuracy

圖10 樣本數目對CPU 響應時間的影響Fig.10 Effect of sample size on CPU response time

圖11 障礙物數目對CPU 響應時間的影響Fig.11 Effect of the number of obstacles on CPU response time

5 結束語

障礙空間的聚類算法在現實生活中有著非常廣泛的應用，本文提出的OBRK-means 算法首先引入Voronoi 圖計算反向近鄰數來確定聚類中心，再利用Voronoi 圖和樣本點密度進行離群點的篩選，最后針對初始聚類結果不精確的問題提出內邊界點、外邊界點、拓展點、剔除點等概念來提高聚類準確性，達到了理想的聚類效果。

障礙空間中的聚類算法有著廣泛的實際應用，接下來，將對不同障礙物情況下的聚類問題進行研究，并對移動對象在障礙物約束下的聚類問題進行研究，使聚類結果更能反映真實地理情況，更有實用價值。