空間聚類分析概念與算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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