基于云計算架構(gòu)的西藏生態(tài)數(shù)據(jù)聚類分析算法研究

巴桑次仁

（西藏自治區(qū)科技信息研究所，西藏 拉薩 850001）

隨著互聯(lián)網(wǎng)時代的發(fā)展，人們接觸的數(shù)據(jù)量越來越多，對空間信息的需求也呈上升趨勢。然而空間數(shù)據(jù)的類型是多樣化的，如何將這些龐大的數(shù)據(jù)量進行聚類分析，得到滿足實際應用的需求數(shù)據(jù)是人們現(xiàn)在最關(guān)注的問題[1]。而對空間數(shù)據(jù)分析獲取有效信息，關(guān)鍵一步是對空間數(shù)據(jù)進行聚類分析，得到其中隱含的有效信息。海量信息處理方面，對聚類算法的要求越來越高，速率和計算的復雜度僅僅只是其中的兩個方面，當然也是最主要的兩個方面，因此傳統(tǒng)單機的聚類算法在處理海量信息時，這兩個方面已經(jīng)達不到要求了。如果仍然要在傳統(tǒng)的分布式系統(tǒng)上實現(xiàn)算法的并行，這無疑會增加系統(tǒng)開發(fā)者的工作量。因為這種做法不僅僅要考慮到算法本身、軟硬件平臺的特性，更不能忽略實際應用當中的需求。

基于Hadoop平臺對空間聚類算法進行優(yōu)化，能夠有效的降低時間復雜度和提高空間聚類分析的精準度，還可以提取空間數(shù)據(jù)庫中的一些隱式知識，空間關(guān)系或者是一些其他有意義的模式[2]。因此空間聚類算法在城市規(guī)劃、土地利用數(shù)據(jù)、遙感等領(lǐng)域的空間數(shù)據(jù)分析中都起到了巨大作用。所以基于Hadoop框架下的空間聚類算法研究就變的十分重要。一般情況下會用一些參數(shù)來描述地理空間實體的分布規(guī)律，這些參數(shù)通常有：分布密度、離散度、分布的中心和軸線等，而地理空間實體的分布規(guī)律往往可以用來揭示空間實體的群體定位特征?？臻g聚類分析就是現(xiàn)在比較常見的，用來揭示空間實體的群體定位特征的方法之一。比如基于劃分的聚類算法，通過該算法得到的空間聚類，在一定程度上可以間接反映空間實體的分布中心和分布軸，這是因為基于劃分的聚類需要選取出聚類的中心，并使用了不同的距離度量方法。又例如，基于密度的聚類分析方法，該算法在一定程度上能把空間群體的分布密度以及離散度反映出來，這是因為基于密度的聚類分析方法在判斷空間實體是否同屬于一個聚類時，是根據(jù)空間實體間的分布密度來度量的[3]。

聚類分析主要是依據(jù)空間對象的特征，然后把描述這些個體的數(shù)據(jù)集分為相互之間有區(qū)別的組（這些組也可稱之為類）。使得組內(nèi)的相似性盡可能的大，而組間的相似性盡可能的小。一個空間對象就是特征空間中的一個點，在聚類算法中局勢用特征來表示空間對象。空間數(shù)據(jù)庫中的聚類其實就是對目標圖形進行聚類，如今，空間目標有多種類型，如：點狀、線狀、面狀，并且在大多數(shù)時候數(shù)據(jù)量非常龐大并且聚類形狀也十分復雜，這無疑使空間數(shù)據(jù)挖掘?qū)垲愑辛烁叩囊螅孩偎惴ㄋ璧膮?shù)能夠自動或者由用戶確定；②能夠處理任意形狀的聚類；③在處理大型空間數(shù)據(jù)庫時的效率能夠較高；④能夠?qū)θ我庑螤畹膶ο筮M行聚類，如點狀、線狀、面狀。

數(shù)據(jù)挖掘當中，聚類按照相似性以及距離度量在空間數(shù)據(jù)集中標識稠密分布的地區(qū)或聚類，然后從當中發(fā)現(xiàn)數(shù)據(jù)集的典型模式以及整個空間的分布規(guī)律，然而這不僅僅是知識發(fā)現(xiàn)任務的一個重要組成部分了，同時它也是數(shù)據(jù)挖掘系統(tǒng)中發(fā)現(xiàn)關(guān)聯(lián)知識、分類知識、廣義知識等共性知識的先決條件[4]。

1 研究內(nèi)容

文章選取K-means算法，基于Hadoop框架的并行化架構(gòu)對空間數(shù)據(jù)的聚類算法開展研究。研究中選取特定研究區(qū)的植被評價遙感影像數(shù)據(jù)。通過編寫程序獲取大量隨機采樣數(shù)據(jù)，每條數(shù)據(jù)是包括經(jīng)緯度、植被評價值的二元組數(shù)據(jù)。將這些數(shù)據(jù)作為聚類算法研究的原始數(shù)據(jù)，經(jīng)過去除異常點和數(shù)據(jù)歸一化等預處理手段，獲取實驗數(shù)據(jù)集?；贙-means聚類算法的原理設計空間數(shù)據(jù)聚類算法，取得的實驗結(jié)果與研究區(qū)的實際數(shù)字高程模型（DEM）進行對比分析，檢驗算法計算的植被評價值分類與高程數(shù)據(jù)的變化是否存在對應關(guān)系，最終對算法的有效性做出評估。

2 算法設計與實現(xiàn)

2.1 MMKMEANS算法思想

MMKEANS算法是基于最大最小距離原理，是相對于傳統(tǒng)的K-means算法所提出的一種改進的K-means算法。它的主要思想是先選取出初始聚心，然后在進行K-means聚類。那么對于初始聚心的選取分為以下幾個步驟[5]：

2.1.1 選第一個聚類中心。從原數(shù)據(jù)集合D當中隨機、任意的選擇一個對象。

2.1.2 選取第二個聚類中心。算出該聚類中心與剩下的各個對象之間的距離，然后將這些距離進行比較，其中距離該聚類中心最遠的那一個對象就是筆者要找的第二個聚類中心。

2.1.3 選取第三個聚類中心。與第二步不同的地方是接著要計算現(xiàn)有的兩個聚類中心與剩余的對象之間的距離，并找出距離min（d1，d2）-也就是距離這兩個聚類中心最小的那一個距離，之后找出基于這種距離當中最大的對象[6]。若該對象滿足：max（min（di1,di2））＞t｜c2-c1｜。公式說明：d1表示的是對象與聚類中心C1的距離,d2表示的是對象與聚類中心C2的距離；t則表示的是在這個聚類算法中的檢驗參數(shù)，則把該對象當作第三個聚類中心。

按照這種方法依次迭代，直到無法找到滿足條件：

2.2 MMKMEANS算法的并行設計

文章將在Hadoop平臺實現(xiàn)MMKEANS算法的MapReduce化。以前面章節(jié)中對MapReduce編程框架大致的介紹為基礎，這里筆者可以用兩個階段來表示MMKMEANS算法的并行化實現(xiàn)，在算法中的第一個階段又分了兩個MapReduce過程來實現(xiàn)對初始聚類中心的選擇。這兩個階段的實現(xiàn)則需經(jīng)過三個Ma?pReduce的過程[7]，結(jié)構(gòu)框架如圖 1 所示：

圖1 MapReduce框架圖

2.2.1 第一個過程。即MapReduce1里的map過程需要進行獨立并行抽樣，為了減少數(shù)據(jù)抽樣帶來的偏差，需要對數(shù)據(jù)進行多次抽樣。因此第一步要把原數(shù)據(jù)集合進行劃分，分成多個小片段，然后將這些數(shù)據(jù)片段復制到集群當中的每一個節(jié)點上，每一個節(jié)點都要獨立的并行執(zhí)行相關(guān)的子任務。當前MapRe?duce中reduce的任務數(shù)是由抽取出的樣本數(shù)據(jù)所決定的。例如將樣本數(shù)據(jù)任意分為m份，那么reduce的任務數(shù)則為m。當前任務中的數(shù)據(jù)并行的執(zhí)行MMKEANS聚類是reduce要負責的事情，在每一個re?duce任務當中會有若干個待選的聚類中心產(chǎn)生，而每一個reduce的輸出數(shù)據(jù)就是這些聚類中心。除此在之外，通過每一個reduce任務計算得到的各個聚類之間的平均距離：也是需要輸出的，因為在下個過程中會用到一個半徑r，在計算對象密度的時侯這個半徑需要被用到。

2.2.2 第二個過程MapReduce。簡單的來說就是要將第一個過程中reduce所輸出的鍵值對進行處理，將其轉(zhuǎn)變?yōu)椴灰粯拥妮敵鲱愋?。從全局來看，上一個過程中所輸出的聚類中心有可能是相鄰的，這是由于在上個reduce處理數(shù)據(jù)的過程中都是局部、獨立并行執(zhí)行的。然后這個reduce過程就負責將上一個reduce過程輸出的若干個聚心進行匯總，鄰近的聚類中心被歸為一個聚類中，然后在這里只需設置一個reduce任務，用于計算新的聚類中心并輸出。算法第二個階段K-means聚類過程[8]：

①K-means聚類過程將用歐式距離來進行相似度度量，這個由一個MapReduce過程來是現(xiàn)實。這個過程的初始聚類中心為第一階段中MapReduce2過程所輸出的聚類中心。其中將原數(shù)據(jù)集合中的所有對象分到與其距離最近的那一個聚類當中，這一任務由map過程負責。

②該算法結(jié)束的標志是聚類的中心不再有變化。針對各個聚類計算出新的聚類中心然后將其輸出，而下一次的迭代輸入為則為這些新的聚類中心，這一操作是由reduce過程負責的，直到算法結(jié)束為止。

2.3 MMKEANS算法的并行實現(xiàn)

2.3.1 第一階段MapReduce1過程。mapper類maxMin?Mapper實現(xiàn)：該類的功能是數(shù)據(jù)抽樣，要對數(shù)據(jù)進行抽樣，自然離不開map過程的參與，mapper類就是用來實現(xiàn)map過程的。各個map子任務的抽樣計算均是獨立并行的，第一步需要知道樣本數(shù)，也就是在計算時map子任務所需要讀取的樣本數(shù)量；第二步各個節(jié)點上存儲著輸入的數(shù)據(jù)，以＜key,value＞對的形式存在的文件，map函數(shù)則順序的讀取數(shù)據(jù)（key為對象的ID,value則是對象的空間向量模型）。在執(zhí)行當中，隨機數(shù)生成器是一個重要步驟。第一步需要對所選取的對象進行計數(shù)。在概率為1的前提下，讀取出前n個對象；然后從第n+1個對象起，要隨機的替換掉之前讀取出的n個對象之中的一個，用在n/i’概率下讀取出的第n+1個對象之后的對象（i=n+1,n+2...）。其中根據(jù)概率論的原理可以知道，其實每一個對象被選取的幾率是相等的為N/n’。map任務的對象數(shù)為N’。第二步則是需要把讀取出的n個對象當作中間數(shù)據(jù)輸出，仍然是以＜key,value＞對的形式。value仍然是對象ID和對象的空間向量模型。key是一個隨機數(shù)，取值在[1,m]之間由隨機數(shù)生成器生成的，m可以從配置文件中獲得，代表的是執(zhí)行reduce任務的數(shù)量[9]。

最終的目的是進行聚類處理，根據(jù)key把樣本數(shù)據(jù)分到不同的reduce上，這些樣本數(shù)據(jù)是在map過程中生成的，然后進行聚類處理。(docID，docVec)是doc?Vector類的數(shù)據(jù)結(jié)構(gòu)。

reducer類maxMinReducer的實現(xiàn)：該類進行re?duce處理。Reduce過程把map過程當中輸出的key以及與key有所關(guān)聯(lián)的所有對象的迭代器當作輸入數(shù)據(jù)，主要目的是為了選出若干個待選的聚類中心，這些待選的聚類中心則是從map過程中的樣本數(shù)據(jù)通過聚類得到的?？梢苑譃橐韵聨讉€步驟進行聚類中心的選取[10]：

①選第一個聚類中心。從原數(shù)據(jù)集合D當中隨機、任意的選擇一個對象[11]。

②選取第二個聚類中心。算出該聚類中心與剩下的各個對象之間的距離，然后將這些距離進行比較，其中距離該聚類中心最遠的那一個對象就是要找的第二個聚類中心。

③選取第三個聚類中心。與第二步不同的地方是接著要計算現(xiàn)有的兩個聚類中心與剩余的對象之間的距離，并找出距離min(d1,d2)-也就是距離這兩個聚類中心最小的那一個距離,之后找出基于這種距離當中最大的對象[12]。若該對象滿足：max（min（d1，d2））＞t｜c2-c1｜。

公式說明：d1表示的是對象與聚類中心C1的距離,d2表示的是對象與聚類中心C2的距離；t則表示的是在這個聚類算法中的檢驗參數(shù)，則把該對象當作第三個聚類中心。

④按照這種方法依次迭代，直到無法找到滿足條件[13]的對象結(jié)束。

要保存聚類中心之間的距離，采用的是鍵值對的形式，鍵值對分為兩種類型：value為聚類中心的空間向量模型，key為對象ID；value為聚類間的平均距離，key=-1。為了達到使計算更便捷的目的，對象與各個聚類中心最小的距離用minDist表示的類去繼承docVector。

2.3.2 第二個階段MapReduce過程。mapper類kmeans?Mapper的實現(xiàn)：這個類主要是對map過程的實現(xiàn)，輸入的數(shù)據(jù)為原數(shù)據(jù)集合，然后其初始的聚類中心為上一個過程的輸出結(jié)果或者是上次迭代所產(chǎn)生的聚類中心[14]，valuer仍然是對象的空間向量模型，key是對象的ID。map過程主要是將對象劃分到與其距離最近的那一個聚類當中，輸出結(jié)果鍵值對中的key代表的是聚類的ID標識，valu則是clusterTool對象。為了使計算更加便捷，因此設置了兩個類，一個是cluster，另一個是clusterTool。K-means算法迭代產(chǎn)生的聚類中心的信息存儲在clusterList中，setup函數(shù)則是用來獲取這些信息的，初始聚類中心的信息可以通過第一次迭代得到，這個初始聚類中心的信息是由上一過程中產(chǎn)生[10]。

combiner類kmeansCombiner的實現(xiàn)：在本地中具有一樣的key的中間數(shù)據(jù)可以利用算法結(jié)合combine過程將它們進行合并，這樣可以使map過程中存儲在各個節(jié)點的本地磁盤中的中間數(shù)據(jù)的網(wǎng)絡通信開銷得以減小，節(jié)點之間網(wǎng)絡開銷也得到有效的減少。這個類用于combine過程的實現(xiàn)，并且將本地節(jié)點同屬與一個聚類對象clusterTool的信息進行歸并[15]。本地節(jié)點在map過程輸出的key和關(guān)聯(lián)到這個key的相關(guān)的value迭代器是它的輸入，在combine過程后所得到的鍵值對當中，value是clusterTool類的對象，而key表示的是聚類ID標識[11]。

reducer類kmeansReducer的實現(xiàn)：這個類用于reduce過程的實現(xiàn)。其中各個節(jié)點的key和與該key有所關(guān)聯(lián)的value迭代器都是這個過程接收的數(shù)據(jù)。各個節(jié)點具有相同key的數(shù)據(jù)會被歸類到一起，同時同屬于一個對象的clusterTool類的信息也會被歸并，最后決定是否要繼續(xù)迭代則需要更新各個聚類中心以及聚類半徑，以此來判斷結(jié)果是否收斂，若收斂則停止迭代，反之；這些是由reduce過程負責的。最后value為新的聚類，聚類的ID標識用key表示。

在第二個階段中進行多次的迭代，聚類過程的收斂速度同樣可以是快速的，這是因為在初始聚類的時候，就會先經(jīng)過一系列的處理。在聚類收斂之后并且我們已經(jīng)獲得了各個聚類的中心，還需要為最終得到的每一個聚類分配對象，這些對象就是原數(shù)據(jù)集中的各個對象，因此這就需要再執(zhí)行一次MapReduce過程。其中第二個過程當中的map處理過程和在最后MapReduce的map過程中是一樣的；相異之處在于最后各個聚類會涵蓋所有的對象，但是reduce過程可以使用缺省的方式，而不需要在重新定義reduce函數(shù)；除此之外reduce過程也不必再次的更新各個聚類的中心。

3 實驗分析

研究中選取特定研究區(qū)(西藏那曲地區(qū))的植被評價遙感影像數(shù)據(jù)。通過編寫程序獲取大量隨機采樣數(shù)據(jù)（每次實驗5000-1000條），如圖2。

圖2 研究區(qū)空間數(shù)據(jù)采樣

通過隨機采樣點獲取的部分實驗數(shù)據(jù)如圖3所示：

圖3 原始空間數(shù)據(jù)片段

這些空間數(shù)據(jù)包括三條屬性：精度、緯度、植被評價值，經(jīng)過整理構(gòu)成D（經(jīng)緯度，評價值）的二元組數(shù)據(jù)[16]。通過編寫程序?qū)ΧM數(shù)據(jù)集中的平均值為零，以及超出評價值范圍的異常點進行清理，然后通過公式以及通過聚類算法，對所處不同經(jīng)緯度的植被評價值進行分類，可以推測研究區(qū)域的地形變化，比如文章研究數(shù)據(jù)中聚類的信息體現(xiàn)了所處區(qū)域的坡面、坡度和坡向的總體分布情況。通過聚類分析以及對每個像元進行對比分析，發(fā)現(xiàn)植被評價值的聚類結(jié)果與坡度和坡向不存在明顯的關(guān)聯(lián)度，與DEM的高程數(shù)據(jù)存在明顯的函數(shù)關(guān)系，如圖4。

圖4 聚類分析結(jié)果

4 結(jié)論

文章研究了空間數(shù)據(jù)聚類分析的一些算法，選擇MMKEANS算法在Hadoop框架上進行實驗，對實驗結(jié)果進行了分析。由于空間數(shù)據(jù)具有類型多、數(shù)據(jù)量大并且復雜的特點，這無疑加大了從空間數(shù)據(jù)當中獲得信息的難度，相較于傳統(tǒng)的關(guān)系數(shù)據(jù)庫，空間數(shù)據(jù)挖掘研究還有待完善，許多的方法和理論需要深入的研究，主要包括：對于多源空間數(shù)據(jù)的預處理。其中影像數(shù)據(jù)、數(shù)字線數(shù)據(jù)都是屬于空間數(shù)據(jù)的，并且因多源空間數(shù)據(jù)本身就十分復雜，在加上對多源空間數(shù)據(jù)的收集及其不易，因此像一些噪聲數(shù)據(jù)、空缺值以及不一致的空間數(shù)據(jù)或多或少的都會被收集到。這也就是為什么要對多源空間數(shù)據(jù)進行預處理的原因，這一過程是極其重要的；提高空間數(shù)據(jù)挖掘算法的效率以及對空間數(shù)據(jù)挖掘算法研究，其中空間數(shù)據(jù)挖掘的研究焦點之一就是空間同位算法；網(wǎng)絡環(huán)境下對空間數(shù)據(jù)的挖掘、遙感圖像數(shù)據(jù)庫的數(shù)據(jù)挖掘、多分辨率以及多層次數(shù)據(jù)挖掘等，選擇改進的K-means算法-MMKMEANS算法在Hadoop平臺進行并行化實現(xiàn)研究。實驗證明基于Hadoop平臺的最大最小K-means算法優(yōu)于傳統(tǒng)的K-means算法，其時間復雜度以及處理數(shù)據(jù)的精度都提高了，對于挖掘?qū)嶋H應用中空間數(shù)據(jù)的有效信息更有利。