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

何云斌，劉婉旭，萬 靜

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

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

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

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

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

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

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

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

1 基本定義與說明

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

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

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

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

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

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

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

（鄰接多邊形）共享相同邊的Voronoi多邊形稱為鄰接多邊形，它們的生成點(diǎn)被稱為鄰接生成點(diǎn)。Voronoi 單元中存在幾條邊，就會(huì)有幾個(gè)鄰接多邊形。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 基本工作

2.1 聚類中心的選取

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

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

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

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

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

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

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

使用定理1 可以在已知數(shù)據(jù)點(diǎn)的第近鄰的前提下快速計(jì)算出數(shù)據(jù)點(diǎn)的第+1 近鄰，但在障礙空間中，因?yàn)檎系K物的存在會(huì)讓兩個(gè)數(shù)據(jù)點(diǎn)之間的距離變大，所以在計(jì)算距離時(shí)需要計(jì)算兩個(gè)數(shù)據(jù)點(diǎn)之間的障礙空間距離。

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

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

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

V_RkNN 算法

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

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

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

2.2 離群點(diǎn)的篩選和剪枝

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

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

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

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

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

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

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

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

outlierX 算法

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

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

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

2.3 廣義覆蓋圓

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

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

如圖7 所示，數(shù)據(jù)點(diǎn)x為聚類中心，四邊形為障礙物，其中|xF|的距離為聚類半徑。若不存在障礙物，則初始聚類包含圓中所有點(diǎn)，現(xiàn)存在障礙物，使得數(shù)據(jù)點(diǎn)集{,,…,}到聚類中心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ù)點(diǎn)作為鄰接生成點(diǎn)，生成Voronoi 圖。根據(jù)算法1 得到一個(gè)按照反向近鄰數(shù)由大到小的Hash 表。然后利用算法2 篩選和剪枝離群點(diǎn)，得到新的數(shù)據(jù)集′。將表中第一個(gè)數(shù)據(jù)點(diǎn)作為聚類中心C，根據(jù)式（2）計(jì)算聚類半徑，若在其中存在障礙物，則形成一個(gè)廣義覆蓋圓進(jìn)行聚類；反之，則形成一個(gè)覆蓋圓開始聚類。根據(jù)式（3）在聚類內(nèi)邊界找出剔除點(diǎn)并從此類簇中刪掉。在覆蓋圓內(nèi)邊界點(diǎn)的鄰近多邊形內(nèi)找到拓展點(diǎn)加入此聚類中，直到此類聚完。刪掉數(shù)據(jù)集中已聚類的數(shù)據(jù)點(diǎn)，在剩余點(diǎn)中繼續(xù)執(zhí)行以上操作，直至所有點(diǎn)聚類完成。

OBRK-means算法

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

分別對(duì)各個(gè)算法進(jìn)行100 次獨(dú)立聚類實(shí)驗(yàn)，統(tǒng)計(jì)每次實(shí)驗(yàn)的結(jié)果，然后對(duì)每種算法求100 次實(shí)驗(yàn)結(jié)果的平均值，對(duì)比算法的實(shí)驗(yàn)結(jié)果如表2 如示。

表2 算法評(píng)測有效性對(duì)比Table 2 Comparison of effectiveness of algorithms

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

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

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

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

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

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

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

5 結(jié)束語

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

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