空間聚類分析概念與算法

1、空間聚類概念空間聚類作為聚類分析的一個(gè)研究方向，是指將空間數(shù)據(jù)集中的對(duì)象分成由相似對(duì)象組成的類。同類中的對(duì)象間具有較高的相似度，而不同類中的對(duì)象間差異較大。作為一種無監(jiān)督的學(xué)習(xí)方法，空間聚類不需要任何先驗(yàn)知識(shí)，比如預(yù)先定義的類或帶類的標(biāo)號(hào)等。由于空間聚類方法能根據(jù)空間對(duì)象的屬性對(duì)空間對(duì)象進(jìn)行分類劃分，其已經(jīng)被廣泛應(yīng)用在城市規(guī)劃、環(huán)境監(jiān)測(cè)、地震預(yù)報(bào)等領(lǐng)域，發(fā)揮著較大的作用。同時(shí)，空間聚類也一直都是空間數(shù)據(jù)挖掘研究領(lǐng)域中的一個(gè)重要研究分支。目前，己有許多文獻(xiàn)資料提出了針對(duì)不同數(shù)據(jù)類型的多種空間聚類算法，一些著名的軟件，如WEAK、SPSS、SAS等軟件中已經(jīng)集成了各種聚類分析軟件包?？臻g數(shù)據(jù)的復(fù)雜

2、性空間聚類分析的對(duì)象是空間數(shù)據(jù)。由于空間數(shù)據(jù)具有空間實(shí)體的位置、大小、形狀、方位及幾何拓?fù)潢P(guān)系等信息，使得空間數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和表現(xiàn)形式比傳統(tǒng)事務(wù)型數(shù)據(jù)更為復(fù)雜，空間數(shù)據(jù)的復(fù)雜特性表現(xiàn)：空間屬性間的非線性關(guān)系。由于空問數(shù)據(jù)中蘊(yùn)含著復(fù)雜的拓?fù)潢P(guān)系，因此，空間屬性間呈現(xiàn)出一種非線性關(guān)系。這種非線性關(guān)系不僅是空間數(shù)據(jù)挖掘中需要進(jìn)一步研究的問題，也是空問聚類所面臨的難點(diǎn)之一。空間數(shù)據(jù)的尺度特征。空間數(shù)據(jù)的尺度特征足指在不同的層次上，空間數(shù)據(jù)所表現(xiàn)出來的特征和規(guī)律都不盡相同。雖然在空間信息的概化和細(xì)化過程中可以利用此特征發(fā)現(xiàn)整體和局部的不同特點(diǎn)，但對(duì)空間聚類任務(wù)來說，實(shí)際上是增加了空間聚類的難度。間信息的

3、模糊性。空間信息的模糊性足指各種類型的窄問信息中，包含大量的模糊信息，如空問位置、間關(guān)系的模糊性，這種特性最終會(huì)導(dǎo)致空間聚類結(jié)果的不確定性。空間數(shù)據(jù)的高維度。空問數(shù)據(jù)的高維度性是指空間數(shù)據(jù)的屬性(包括空間屬性和非空間屬性)個(gè)數(shù)迅速增加，比如在遙感領(lǐng)域，獲取的空間數(shù)據(jù)的維度已經(jīng)快速增加到幾十甚至上百個(gè)，這會(huì)給空間聚類的研究增加很大的困難?？臻g聚類算法目前，研究人員已經(jīng)對(duì)空間聚類問題進(jìn)行了較為深入的研究，提出了多種算法。根據(jù)空間聚類采用的不同思想，空間聚類算法主要可歸納為以下幾種：基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法、基于網(wǎng)格的聚類算法、基于模型的聚類算法以及其它形式的聚類算

4、法，如圖1所示。(1)基于劃分的聚類基于劃分的聚類方法是最早出現(xiàn)并被經(jīng)常使用的經(jīng)典聚類算法。其基本思想是：在給定的數(shù)據(jù)集隨機(jī)抽取n個(gè)元組作為n個(gè)聚類的初始中心點(diǎn)，然后通過不斷計(jì)算其它數(shù)據(jù)與這幾個(gè)中心點(diǎn)的距離(比如歐幾里得距離)，將每個(gè)元組劃分到其距離最近的分組中，從而完成聚類的劃分。由于基于劃分的聚類方法比較容易理解，且易實(shí)現(xiàn)，目前其已被廣泛的弓1入到空間聚類中，用于空間數(shù)據(jù)的分類。其中最為常用的幾種算法是：k一平均(k-means)算法、kl中心點(diǎn)(k一medoids)算法和EM(expectationmaximization)算法。k一平均算法使用每個(gè)聚類中所有對(duì)象的平均值作為該聚類的中心

5、；k一中心點(diǎn)算法I貝0選用簇中位置最中心的對(duì)象作為聚類中心；而EM算法“則采用一個(gè)平均概率分布和一個(gè)dXd協(xié)方差矩陣來表示一個(gè)聚類。除上述3種算法外，也出現(xiàn)了眾多的基于上述算法的變異算法，如基于選擇的方法(CLARA)、基于隨機(jī)搜索的方法(cLARANs)等。基于層次的聚類基于層次的聚類方法就是將數(shù)據(jù)對(duì)象組成一棵聚類的樹。根據(jù)層次的分解方向，分為凝聚法和分裂法。凝聚法最初假定數(shù)據(jù)集中的每個(gè)對(duì)象都為一個(gè)單獨(dú)的類，然后通過不斷合并相近的對(duì)象，直到滿足條件為止；分裂法同凝聚法的分解方向相反，其開始假設(shè)所有的對(duì)象都在一個(gè)類中，之后不斷進(jìn)行分裂，直到滿足條件為止。由于一個(gè)類一旦分裂或凝聚就不能撤消，因此

6、基于層次的算法的靈活性較差，故很少有純粹的層次算法，層次方法往往和其它方法相結(jié)合進(jìn)行聚類。代表性算法有：CURE算法、CHAMELEON算法。CURE(clusteringusingrepresentatives)算法是-一種新穎的層次算法，它采取隨機(jī)取樣和劃分相結(jié)合的方法：一個(gè)隨機(jī)樣本首先被劃分，每個(gè)劃分被局部聚類，最后把每個(gè)劃分中產(chǎn)生的聚類結(jié)果用層次聚類的方法進(jìn)行聚類。較好的解決了偏好球形和相似大小的問題，在處理孤立點(diǎn)時(shí)也更加健壯。CHAMELEON(hierarchicalclusteringusingdynamicmodeling)算法的主要思想是首先使用圖劃分算法將數(shù)據(jù)對(duì)象聚類為大量

7、相對(duì)較小的子類，其次使用凝聚的層次聚類算法反復(fù)地合并子類來找到真正的結(jié)果類。CHAMELEON算法是在CURE等算法的基礎(chǔ)上改進(jìn)而來，能夠有效的解決CURE等算法的問題?；诿芏鹊木垲惢诿芏鹊木垲愃惴ㄖ饕攸c(diǎn)在于其使用區(qū)域密度作為劃分聚類的依據(jù)，其認(rèn)為只要數(shù)據(jù)空間區(qū)域的密度超過了預(yù)先定義的閥值，就將其添加到相近的聚類中。這種方法不同于各種各樣基于距離的聚類算法，其優(yōu)點(diǎn)在于能夠發(fā)現(xiàn)任意形狀的聚類，從而克服基于距離的方法只能發(fā)現(xiàn)類圓形聚類的缺點(diǎn)。代表性算法有：DBSCAN算法、OPTICS算法、DE一NCLUE算法等。DBSCAN(densitybasedspatialclusteringofa

8、pplicationswithnoise算法將聚類定義為基于密度可達(dá)性最大的密度相連對(duì)象的集合。聚類分析時(shí)，它必須輸入?yún)?shù)、MinPts，其中，是給定對(duì)象的半徑，MinPts是一個(gè)對(duì)象的鄰域內(nèi)包含的最少對(duì)象數(shù)目。檢查一個(gè)對(duì)象的鄰域的密度是否較大，即一定距離內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù)是否超過MinPts來確定是否建立一個(gè)以該對(duì)象為核心對(duì)象的新類，再合并密度可達(dá)類。盡管DBSCAN算法能對(duì)任意形狀的數(shù)據(jù)集進(jìn)行聚類。但它仍需要用戶輸入?yún)?shù)和MinPts，而聚類結(jié)果對(duì)這兩個(gè)參數(shù)的值又非常敏感。這事實(shí)上是將選擇參數(shù)的任務(wù)留給了用戶，而在實(shí)際中，用戶很難準(zhǔn)確確定合適的參數(shù)值，這往往導(dǎo)致聚類結(jié)果的偏差。因此，為了克服上

9、述問題，人們提出了一種基于DBSCAN的改進(jìn)算法OPTICS(orderingpointstoidentifytheclusteringstructure)。OPTICS算法為自動(dòng)和交互的聚類分析計(jì)算一個(gè)聚類次序，這個(gè)次序反映了數(shù)據(jù)基于密度的聚類結(jié)構(gòu)，并且能夠使用圖形或其它可視化的方法表示。DENCLUE(density一basedclustering)算法也是一種基于密度分布的聚類方法，概括了包括劃分法、層次法等多種聚類方法，能夠處理包含大量噪音的聚類，并且其執(zhí)行效率要遠(yuǎn)遠(yuǎn)高于DBSCAN算法。(4)基于網(wǎng)格的聚類基于網(wǎng)格的聚類主要思想是將空間區(qū)域劃分若干個(gè)具有層次結(jié)構(gòu)的矩形單元，不同層次的

10、單元對(duì)應(yīng)于不同的分辨率網(wǎng)格，把數(shù)據(jù)集中的所有數(shù)據(jù)都映射到不同的單元網(wǎng)格中，算法所有的處理都是以單個(gè)單元網(wǎng)格為對(duì)象，其處理速度要遠(yuǎn)比以元組為處理對(duì)象的效率要高的多。代表性算法有：STING算法、CLIQUE算法、WAVE.CLUSTER算法等。STING(statisticalinformationgnd)算法“首先將空間區(qū)域劃分為若干矩形單元，這些單元形成一個(gè)層次結(jié)構(gòu)，每個(gè)高層單元被劃分為多個(gè)低一層的單元。單元中預(yù)先計(jì)算并存儲(chǔ)屬性的統(tǒng)計(jì)信息，高層單元的統(tǒng)計(jì)信息可以通過底層單元計(jì)算獲得。這種算法的優(yōu)點(diǎn)是效率很高，而且層次結(jié)構(gòu)有利于并行處理和增量更新；其缺點(diǎn)是聚類的邊界全部是垂直或是水平的，與實(shí)際

11、情況可能有比較大的差別，影響聚類的質(zhì)量。WaveCluster(clusteringusingwavelettransformation)算法“是-一種采用小波變換的聚類方法。其首先使用多維數(shù)據(jù)網(wǎng)格結(jié)構(gòu)匯總區(qū)域空間數(shù)據(jù)，用多維向量空間表示多維空間中的數(shù)據(jù)對(duì)象，然后使用小波變換方法對(duì)特征空間進(jìn)行處理，發(fā)現(xiàn)特征空間中的稠密區(qū)域。最終通過多次小波變換，獲得多分辨率的聚類。CLIQuE(clustefinginquest)算法“綜合了基于密度和基于網(wǎng)格的聚類方法。其主要思想是將多維數(shù)據(jù)空間劃分為多個(gè)矩形單元，通過計(jì)算每一個(gè)單元中數(shù)據(jù)點(diǎn)中全部數(shù)據(jù)點(diǎn)的比例的方法確定聚類。其優(yōu)點(diǎn)是能夠有效處理高維度的數(shù)據(jù)集

12、，缺點(diǎn)是聚類的精度有可能會(huì)降低?；谀Ｐ偷木垲惢谀Ｐ偷木垲愔饕枷胧羌僭O(shè)數(shù)據(jù)集中的數(shù)據(jù)分布符合特定的數(shù)學(xué)模型，通過數(shù)學(xué)模型來發(fā)現(xiàn)聚類。主要有兩種基于模型的方法：一種是統(tǒng)計(jì)學(xué)的方法，代表性算法是COBWEB算法：另一種是神經(jīng)網(wǎng)絡(luò)的方法，代表性的算法是競(jìng)爭(zhēng)學(xué)習(xí)算法。COBWEB算法m是一種增量概念聚類算法。這種算法不同于傳統(tǒng)的聚類方法，它的聚類過程分為兩步：首先進(jìn)行聚類，然后給出特征描述。因此，分類質(zhì)量不再是單個(gè)對(duì)象的函數(shù)，而且也加入了對(duì)聚類結(jié)果的特征性描述。競(jìng)爭(zhēng)學(xué)習(xí)算法”屬于神經(jīng)網(wǎng)絡(luò)聚類。它采用若干個(gè)單元的層次結(jié)構(gòu)，以一種“勝者全取”的方式對(duì)系統(tǒng)當(dāng)前所處理的對(duì)象進(jìn)行競(jìng)爭(zhēng)。其它方法的聚類除了上述

13、5種空間聚類算法外，研究人員根據(jù)空間聚類的要求，提出了多種結(jié)合其它思想的空間聚類方法。影響較大的有遺傳空間聚類和帶約束的空間聚類算法。其中，遺傳空間聚類是模仿生物進(jìn)化過程中的自然選擇和進(jìn)化機(jī)制，通過基因編碼、遺傳、變異和交叉等操作，來實(shí)現(xiàn)空間聚類的一種算法，是一種基于群體的全局隨機(jī)優(yōu)化算法：而帶約束的空間聚類算法則是為了解決空間聚類中所面臨的空間障礙問題而產(chǎn)生的，如城市中的河流、湖泊等障礙，各居民點(diǎn)并非沿直線，而是沿著一定的道路或網(wǎng)絡(luò)到達(dá)簇中心等情況，如果在實(shí)際分析中不考慮這些障礙，獲得的聚類結(jié)果必然與實(shí)際情況有較大的誤差，而帶約束的空間聚類正是解決上述問題的有效算法。空間聚類質(zhì)量評(píng)價(jià)方法空間

14、聚類作為聚類的一個(gè)研究分支，其過程是一個(gè)尋找最優(yōu)劃分的過程，即根據(jù)聚類終止條件不斷對(duì)劃分進(jìn)行優(yōu)化，最終得到最優(yōu)解。由于空間聚類是一種無監(jiān)督的學(xué)習(xí)方法，事先沒有任何先驗(yàn)知識(shí)，因此，需要一定的措施或方法對(duì)的空間聚類結(jié)果進(jìn)行有效性驗(yàn)證和質(zhì)量評(píng)價(jià)。本文主要從內(nèi)部度量和外部度量?jī)蓚€(gè)方面對(duì)空間聚類質(zhì)量進(jìn)行評(píng)價(jià)。31內(nèi)部度量空間聚類的內(nèi)部度量原則主要有兩個(gè)：聚類內(nèi)部距離和聚類間的距離。聚類內(nèi)部距離是指聚類內(nèi)部問對(duì)象的平均距離，它反映了聚類的緊湊性和聚類算法的有效性；而聚類間的距離是指兩個(gè)聚類間所有會(huì)話的平均距離。對(duì)于良好的聚類算法來說，聚類內(nèi)部距離應(yīng)較小，聚類問的距離應(yīng)較遠(yuǎn)。(1)聚類間距離假設(shè)n個(gè)空間對(duì)象

15、被聚類為WK)個(gè)簇，定義聚類間距離為所有分中心(每個(gè)簇的均值)到全域中心(所有空間對(duì)象均值)的距離之和_L=Im一聊I式中，L聚類間距離，m全部空間對(duì)象的均值，mi簇C。所含空間對(duì)象的均值，聚類的個(gè)數(shù)，l(fGK,K聚類區(qū)間。(2)聚類內(nèi)部距離假設(shè)n個(gè)空間對(duì)象被聚類為I(r個(gè)簇，定義聚類內(nèi)部距離為所有聚類內(nèi)部距離的總和(其中每個(gè)聚類的內(nèi)部距離為該聚類所有空間對(duì)象到其中心的距離之和)D=工工Ipm1其中，D類內(nèi)距離；P任空間研究對(duì)象，m.簇C。所含空間對(duì)象的均值。32外部度量“對(duì)聚類質(zhì)量的評(píng)價(jià)，除了內(nèi)部度量方法外，還有外部度量方法。外部度量方法不同于內(nèi)部度量方法，其主要從當(dāng)前分類是正確的分類的角度出發(fā)，衡量聚類質(zhì)量的好壞。外部度量有兩種方法：純凈度和F.measure熵。純凈度純凈度定義為已知正確類符號(hào)fG標(biāo)識(shí)為該類的數(shù)據(jù)占整個(gè)簇的比例，即Purity(Ck)=max其中，中類標(biāo)識(shí)的數(shù)目，簇N該簇中標(biāo)識(shí)為t的數(shù)目。而整個(gè)聚類結(jié)果的純凈度為所有簇的純凈度的均