基于數(shù)學(xué)形態(tài)學(xué)的帶障礙約束的空間聚類算法研究

摘要：該文提出了一種基于數(shù)學(xué)形態(tài)學(xué)的帶障礙約束的聚類算法。通過數(shù)學(xué)形態(tài)學(xué)的膨脹運(yùn)算，進(jìn)行連通區(qū)域的尋找，同時(shí)借助于進(jìn)行膨脹運(yùn)算的結(jié)構(gòu)元素，確定障礙物與連通區(qū)域是否相交。算法與DBCluC算法不同的是：通過結(jié)構(gòu)元素，大大減少了需要進(jìn)行相交判斷的點(diǎn)的數(shù)量，具有較高的時(shí)間效率。

關(guān)鍵詞：聚類算法；障礙約束；數(shù)學(xué)形態(tài)學(xué)

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044(2008)36-2923-03

Clustering Algorithm Based on Mathematical Morphology in the Presence of Obstacles

KONG Juan1，XU Tian-fu2，XUE Qin-feng3

(1.Shandong Normal University College of Information Science and Engineering，Jinan 250014，China;2.Local Taxation in Shandong ，Department Information Center，Jinan 250002，China;3.Shandong Institute of Science and Technology Building，Jinan 250002，China)

Abstract: In this paper，we introduce a clustering algorithm based on Mathematical Morphology in the presence of obstacles.In this algorithm，we search for the regional connectivity through the expansion operations of Mathematical morphology.At the same time，with the help of the structural elements， whether the obstacles cross the regional connectivity can be determined.The algorithm is different from the DBCluC: the adoption of structural elements， greatly reducing the number of points need to judge and the efficiency of the algorithm is very high.

Key words:clustering algorithm; obstacle; mathematical morphology

1 概論

由于雷達(dá)、紅外、光電、衛(wèi)星、電視攝像、電子顯微成像、CT成像等各種宏觀與微觀傳感器的使用，空間數(shù)據(jù)的數(shù)量、大小和復(fù)雜性都在飛快地增長，己經(jīng)遠(yuǎn)遠(yuǎn)超出了人們的解譯能力。終端用戶不可能詳細(xì)地分析所有數(shù)據(jù)，并提取感興趣的空間知識(shí)，致使“空間數(shù)據(jù)爆炸但知識(shí)貧乏”。 因此，利用空間數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)(SDMKD，spatial data mining and knowledge discovery)從空間數(shù)據(jù)庫中自動(dòng)或半自動(dòng)地挖掘事先未知卻潛在有用的空間模式變得十分必要[1]。

空間聚類指將空間對(duì)象劃分為不同的群，使群內(nèi)數(shù)據(jù)具有高相似性而不同群數(shù)據(jù)具有較大的相異性，而在實(shí)際應(yīng)用中，河流、湖泊等障礙物的存在破壞了空間的連續(xù)性。如果在聚類過程中對(duì)障礙物不加考慮，勢必會(huì)影響聚類結(jié)果的準(zhǔn)確性。因此，在聚類過程中對(duì)空間障礙物進(jìn)行處理就是帶障礙約束的空間聚類。

2 相關(guān)研究工作

2.1 帶障礙約束的聚類算法

為了提高聚類聚類結(jié)果的精確性，使聚類結(jié)果能對(duì)用戶進(jìn)行正確的引導(dǎo)，研究者紛紛在已有的各種空間聚類算法的基礎(chǔ)上，加入了對(duì)障礙物的處理思想。目前，已經(jīng)有很多比較成熟的算法[2]。

在本節(jié)中，我們將對(duì)COD_CLARANS， AUTOCLUST+以及DBCLuC算法進(jìn)行簡要介紹，并分析各個(gè)算法的優(yōu)缺點(diǎn)及存在的問題。

COD_CLARANS是第一個(gè)基于劃分思想的帶障礙約束的聚類算法，是對(duì)CLARANS算法加入障礙約束后的改進(jìn)。算法引入了障礙距離這一概念，即兩對(duì)象間不與任何障礙物相交的最短距離。若兩對(duì)象之間的直線距離不與障礙物相交，兩對(duì)象間的障礙距離仍等于歐氏距離。COD_CLARANS算法的缺點(diǎn)是只能處理一些小的數(shù)據(jù)集，并且預(yù)處理的代價(jià)昂貴，不能處理任意形狀的聚類。若聚類間密度差別比較大，微聚類技術(shù)將無法實(shí)現(xiàn)。

AUTOCLUST+將Delaunay圖引入到聚類算法當(dāng)中。它是在AUTOCUST基礎(chǔ)上進(jìn)行改進(jìn)，將障礙物模型化為一系列分割線段，生成約束下的Delaunay圖，再根據(jù)AUTOCUST核心算法進(jìn)行處理，得到最終的聚類結(jié)果。因此，算法繼承了AUTOCUST算法的特點(diǎn)，即對(duì)數(shù)據(jù)點(diǎn)采取了Delaunay結(jié)構(gòu)，聚類結(jié)果比較好，但相對(duì)而言，算法空間復(fù)雜度較高，在處理多維數(shù)據(jù)時(shí)尤甚，不適用于較大的多維數(shù)據(jù)庫。

DBCluC是一個(gè)處理障礙物的基于密度的聚類算法，它是在傳統(tǒng)的密度聚類算法DBSCAN的基礎(chǔ)上引入了障礙模型。該算法中，如果任意兩個(gè)數(shù)據(jù)點(diǎn)的連線和任一障礙物相交，則這兩個(gè)數(shù)據(jù)點(diǎn)視為不可見，它們之間的距離為無窮大。但是，這種判斷兩點(diǎn)間距離的方法不夠精確。如果障礙物上有一點(diǎn)可以連接障礙物兩邊的數(shù)據(jù)點(diǎn)，該算法不能處理這種情況。

2.2 基于數(shù)學(xué)形態(tài)學(xué)的聚類算法

2.2.1 數(shù)學(xué)形態(tài)學(xué)概述

數(shù)學(xué)形態(tài)學(xué)（Mathematical Morphology），是法國科學(xué)家在研究巖石結(jié)構(gòu)時(shí)建立的一門學(xué)科，是90年代新興的圖像處理技術(shù)[2-6]，其基本思想是利用一個(gè)稱作“結(jié)構(gòu)元素”的探針收集圖像信息，當(dāng)探針在圖像中不斷移動(dòng)時(shí)便可以考察圖像各部分間的相互關(guān)系，從而了解圖像結(jié)構(gòu)特征。結(jié)構(gòu)元素可直接攜帶知識(shí)（形態(tài)、大小、灰度和色度信息），來探測研究圖像結(jié)構(gòu)的特點(diǎn)。形態(tài)學(xué)的用途主要是獲取物體拓?fù)浜徒Y(jié)果信息，它通過物體和結(jié)構(gòu)元素相互作用的某些運(yùn)算，得到物體更本質(zhì)的形態(tài)[3]。

基于數(shù)學(xué)形態(tài)學(xué)的聚類算法（下稱MMC算法）能識(shí)別任意形狀的聚類，有效確定聚類數(shù)，而不是用戶輸入聚類數(shù)，還能有效利用各種先驗(yàn)知識(shí)，是一種比較簡單的聚類方法。

2.2.2 相關(guān)概念及定義

1) 腐蝕運(yùn)算[4]

把結(jié)構(gòu)元素B平移a后得到Ba，若Ba包含于X，我們記下這個(gè)a點(diǎn)，所有滿足上述條件的a點(diǎn)組成的集合稱做X被B腐蝕的結(jié)果。用公式表示為：E(X)={a|Ba?奐X}=X?專B。X被B腐蝕的結(jié)果就象X被剝掉了一層似的，這就是為什么叫腐蝕的原因。

2) 膨脹運(yùn)算[4]

膨脹可以看做是腐蝕的對(duì)偶運(yùn)算，其定義是：把結(jié)構(gòu)元素B平移a后得到Ba，若Ba擊中X，我們記下這個(gè)a點(diǎn)，所有滿足上述條件的a點(diǎn)組成的集合稱做X被B膨脹的結(jié)果。B擊中X（hit）是設(shè)有兩幅圖象B，X。若存在這樣一個(gè)點(diǎn)，它既是B的元素，又是X的元素，則稱B擊中X，記作B↑X。膨脹運(yùn)算用公式表示為： D(X)={a|Ba↑X}=X?茌B。X被B膨脹的結(jié)果就象X膨脹了一圈似的，這就是為什么叫膨脹的原因。

3 基于MMC的帶障礙約束的聚類算法

我們的算法是在數(shù)學(xué)形態(tài)學(xué)聚類算法的基礎(chǔ)上，引入了障礙約束和對(duì)障礙約束的處理思想。它既具有數(shù)學(xué)形態(tài)學(xué)聚類算法的優(yōu)點(diǎn)，算法復(fù)雜性低，可以發(fā)現(xiàn)任意形狀的聚類，又可以有效的將障礙物兩邊的數(shù)據(jù)分為不同的類。算法涉及二維空間中的線狀障礙物，對(duì)面狀障礙物將其考慮成由多個(gè)線性障礙物圍成的多邊形。

3.1 算法思想

算法對(duì)障礙物的處理思想是采用空間連續(xù)性原理，即障礙物的不可穿越性破壞了原空間的連續(xù)性，使原本屬于同一個(gè)類的對(duì)象被障礙物劃分到不同的類。如何將位于障礙物兩邊的距離很近的對(duì)象區(qū)分成不同的類呢？在DBCluC算法中，通過兩對(duì)象的連線與障礙物相交與否計(jì)算兩對(duì)象之間的障礙距離或直接距離。然而，這種算法需要判斷任意兩個(gè)對(duì)象之間的連線是否與障礙物相交，并計(jì)算它們之間的距離，算法的復(fù)雜性很高。為了提高算法的效率，我們提出了基于數(shù)學(xué)形態(tài)學(xué)的帶障礙約束的聚類算法——MMOC。

在MMOC算法中，借助進(jìn)行膨脹運(yùn)算的結(jié)構(gòu)元素對(duì)對(duì)象之間的距離進(jìn)行判斷。根據(jù)基于數(shù)學(xué)形態(tài)學(xué)聚類的原理，如果兩對(duì)象之間的距離dist（A，B）大于進(jìn)行膨脹運(yùn)算的結(jié)構(gòu)元素的半徑r，當(dāng)結(jié)構(gòu)元素的圓心在A點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行膨脹運(yùn)算時(shí)，B點(diǎn)不能被包含進(jìn)A點(diǎn)膨脹后所得到的數(shù)據(jù)子集中，則A，B將屬于不同的聚類。根據(jù)這一思想，我們可以在尋找連通區(qū)域的過程中，將位于障礙物另一端的對(duì)象進(jìn)行相應(yīng)的標(biāo)識(shí)。

與DBCluC算法不同的是，MMOC算法在尋找連通區(qū)域時(shí)，并不是計(jì)算每兩個(gè)對(duì)象是否與障礙物相交，而是計(jì)算進(jìn)行膨脹運(yùn)算的結(jié)構(gòu)元素是否與障礙物相交，這大大減少了需要進(jìn)行判斷的工作量。當(dāng)結(jié)構(gòu)元素與障礙物相交時(shí)，進(jìn)一步計(jì)算位于結(jié)構(gòu)元素圓心點(diǎn)的數(shù)據(jù)A與其圓形區(qū)域內(nèi)的每一點(diǎn)的連線是否與障礙物相交，如果相交，將該點(diǎn)進(jìn)行標(biāo)記；如果不相交，該點(diǎn)與點(diǎn)A位于同一個(gè)連通區(qū)域內(nèi)。當(dāng)在尋找同一個(gè)連通區(qū)域的過程中對(duì)下一個(gè)點(diǎn)進(jìn)行膨脹運(yùn)算時(shí)，對(duì)已有標(biāo)記的對(duì)象可以直接將它排除在本類之外，而不再需要判斷。

該算法的優(yōu)點(diǎn)有以下兩點(diǎn)：

1) 這種方法在尋找連通區(qū)域的過程中，只需要對(duì)少量的位于障礙物周圍的點(diǎn)進(jìn)行判斷，對(duì)遠(yuǎn)離障礙物的點(diǎn)只需要按照正常的聚類過程進(jìn)行聚類；

2) 當(dāng)一個(gè)點(diǎn)B與連通區(qū)域S1有障礙物相隔時(shí)，對(duì)點(diǎn)B進(jìn)行標(biāo)記，在后續(xù)的聚類過程中，只要同一個(gè)連通區(qū)域的尋找還未結(jié)束，則不再需要對(duì)B進(jìn)行判斷，而直接排除在本類之外。

3.2 算法分析

假設(shè)原始數(shù)據(jù)集的數(shù)據(jù)量為n，根據(jù)數(shù)學(xué)形態(tài)學(xué)的空間聚類算法可知，用結(jié)構(gòu)元素進(jìn)行膨脹運(yùn)算獲取連通區(qū)域的時(shí)間復(fù)雜度是 O(n)。假設(shè)障礙物兩端附近的點(diǎn)共有m個(gè)，根據(jù)障礙物的多少、大小不同，m的個(gè)數(shù)將差別很大，但m一定小于n。當(dāng)結(jié)構(gòu)元素膨脹運(yùn)算進(jìn)行到障礙物附近時(shí)，需要對(duì)這m個(gè)數(shù)據(jù)點(diǎn)判斷其位于障礙物的哪一側(cè)，并進(jìn)行標(biāo)識(shí)，其時(shí)間復(fù)雜度是O(m) 。因此，整個(gè)算法的時(shí)間復(fù)雜度是O(m+n)，即O(n)。由此可知，采用基于數(shù)學(xué)形態(tài)學(xué)的帶障礙約束的聚類算法，其時(shí)間復(fù)雜度非常低，是對(duì)DBCluC算法的一種改進(jìn)。

圖1表達(dá)了MMOC算法的聚類過程。圖1（a）是經(jīng)過“噪聲”處理的原始數(shù)據(jù)集的，為了更好的展現(xiàn)聚類的過程，我們僅選用障礙物附近的幾個(gè)代表點(diǎn)。圖1（b）是連通區(qū)域?qū)ふ疫^程中使用結(jié)構(gòu)元素B對(duì)數(shù)據(jù)點(diǎn)1、5和7分別進(jìn)行膨脹運(yùn)算的示意圖。綠色的結(jié)構(gòu)元素與障礙物不相交，透明的兩個(gè)結(jié)構(gòu)元素都與障礙物相交。如圖所示，當(dāng)對(duì)數(shù)據(jù)點(diǎn)1進(jìn)行膨脹時(shí)，數(shù)據(jù)點(diǎn)2，3，4被包含進(jìn)數(shù)據(jù)子集中，結(jié)構(gòu)元素與線性障礙物不相交，無需對(duì)2，3，4進(jìn)行判斷，它們屬于數(shù)據(jù)點(diǎn)1所在的聚類，賦予與1同樣的聚類標(biāo)識(shí)。當(dāng)膨脹運(yùn)算進(jìn)行到數(shù)據(jù)點(diǎn)5時(shí)，數(shù)據(jù)點(diǎn)3，6，10被包含進(jìn)數(shù)據(jù)子集中，此時(shí)結(jié)構(gòu)元素與障礙物相交。則數(shù)據(jù)點(diǎn)3，6，10分別與數(shù)據(jù)點(diǎn)5相連，3與5的連線沒有與障礙物相交，則3與5屬于同一個(gè)類，賦予同樣的聚類標(biāo)識(shí)。6與10的flag值置為true。此時(shí)，再對(duì)這個(gè)聚類中的其他元素進(jìn)行膨脹時(shí)，連通區(qū)域不再增加，此連通區(qū)域的尋找結(jié)束。將6，10的flag值重新置為flase。任選一個(gè)沒有聚類標(biāo)識(shí)的點(diǎn)7進(jìn)行下一個(gè)連通區(qū)域的尋找。對(duì)點(diǎn)7進(jìn)行膨脹的結(jié)構(gòu)元素雖然與障礙物相交，但其與點(diǎn)6，8，10的連線都沒有與障礙物相交，它們屬于點(diǎn)7所在的連通區(qū)域，賦聚類標(biāo)識(shí)。如此進(jìn)行下去，直到所有的點(diǎn)都有聚類標(biāo)識(shí)為止。

4 結(jié)束語

本文重點(diǎn)提出了一種帶障礙約束的空間聚類算法，分析了已有的基于障礙約束的空間聚類算法的優(yōu)缺點(diǎn)，并結(jié)合基于數(shù)學(xué)形態(tài)學(xué)空間聚類思想提出了用結(jié)構(gòu)元素判斷障礙物穿越與否的思想。新算法與原有的帶障礙約束的空間聚類算法相比，最重要的一點(diǎn)是時(shí)間復(fù)雜性大大降低，而且易于理解， 具有較大的優(yōu)越性。

參考文獻(xiàn):

[1] 李新運(yùn).城市空間數(shù)據(jù)挖掘方法與應(yīng)用研究[M].山東:山東科技大學(xué)，2004.

[2] XIN WANG， HOWARD J. HAMILTON，Clustering spatial data in the presence of obstacles，International Journal on Artificial Intelligence Tools，2005.

[3] 李德仁，王樹良，李德毅.空間數(shù)據(jù)挖掘理論與應(yīng)用[M].北京：科學(xué)出版社，2006.

[4] 唐常青.數(shù)學(xué)形態(tài)學(xué)方法及其應(yīng)用[M]，1990.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”