障礙空間中Voronoi圖優(yōu)化的反向近鄰數(shù)聚類算法

何云斌，劉婉旭，萬 靜

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

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

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

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

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

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

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

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

1 基本定義與說明

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

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

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

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

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

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

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

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

根據(jù)Voronoi圖的結(jié)構(gòu)和定義可以得出兩個基本性質(zhì)。

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

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

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

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

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

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

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

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

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

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

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

其中，為初始聚類圓中數(shù)據(jù)點的個數(shù)。

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

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

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

2 基本工作

2.1 聚類中心的選取

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

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

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

數(shù)據(jù)點的第+1 近鄰一定在的第(1 ≤≤)近鄰的鄰近單元格內(nèi)。

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

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

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

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

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

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

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

V_RkNN 算法

輸入：數(shù)據(jù)集={,,…,x}，障礙物集。

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

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

2.2 離群點的篩選和剪枝

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

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

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

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

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

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

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

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

outlierX 算法

輸入：數(shù)據(jù)集={x|=1,2,…,}。

輸出：過濾后的數(shù)據(jù)集′。

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

2.3 廣義覆蓋圓

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

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

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

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

3 OBRK-means數(shù)據(jù)聚類算法

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

OBRK-means算法

輸入：數(shù)據(jù)集，障礙集。

輸出：障礙空間下的數(shù)據(jù)聚類結(jié)果。

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

4 實驗結(jié)果與分析

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

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

表1 UCI實驗室數(shù)據(jù)集Table 1 UCI laboratory datasets

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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