鬼佬大哥大
  • / 25
  • 下載費用:30 金幣  

一種處理大型地理柵格數據的并行聚類方法.pdf

摘要
申請專利號:

CN201510570327.7

申請日:

2015.09.09

公開號:

CN105045934A

公開日:

2015.11.11

當前法律狀態:

實審

有效性:

審中

法律詳情: 實質審查的生效IPC(主分類):G06F 17/30申請日:20150909|||公開
IPC分類號: G06F17/30 主分類號: G06F17/30
申請人: 長春工程學院
發明人: 潘欣; 趙健; 孫宏彬; 任斌; 徐宏年
地址: 吉林省長春市寬平大路395號
優先權:
專利代理機構: 哈爾濱市松花江專利商標事務所23109 代理人: 楊立超
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510570327.7

授權公告號:

|||

法律狀態公告日:

2015.12.09|||2015.11.11

法律狀態類型:

實質審查的生效|||公開

摘要

一種處理大型地理柵格數據的并行聚類方法,本發明涉及并行聚類方法。本發明要解決地理柵格十分龐大,超過了單機加載極限從而導致系統無法運行或者運行效率很低,以及在多計算機并行聚類過程中各個進程計算結果的相互交換問題。本發明是通過一、計算節點數量,為每個計算進程編號;二、將數據發送給編號為ID的計算進程;三、生成M組聚類解的初始值;四、將聚類矢量中心表發送給計算進程;五、管理進程控制迭代求解過程;六、將字段4獲得最高值的一行的內容發送給各個計算進程;七、將柵格聚類的結果寫入地理柵格數據文件中;即完成了一種處理大型地理柵格數據的并行聚類方法等步驟實現的。本發明應用于處理大型地理柵格數據的并行聚類領域。

權利要求書

1.一種處理大型地理柵格數據的并行聚類方法,其特征在于一種處理大型地理柵格
數據的并行聚類方法具體是按照以下步驟進行的:
步驟一、在計算機集群上,利用管理節點啟動管理進程,管理進程根據大型地理柵格
數據量計算參與計算的計算節點數量,并在每個計算節點上啟動計算進程,同時為每個計
算進程編號;其中,一個計算機集群包含5~100臺通過互聯網連接的計算機,在計算機集
群中任選一臺計算機充當管理節點,計算機集群中除管理節點之外其它節點充當計算節點;
其中,大型地理柵格數據的數據量為大于1000M;
步驟二、管理進程逐行讀取大型地理柵格數據,將整個大型地理柵格數據分散加載到
N個計算進程,將每行大型地理柵格數據發送給對應編號為ID的計算進程;
步驟三、管理進程隨機生成M組聚類解的初始值,其中,每一組聚類解的初始值包含
一個類目個數和一個類目中心點矢量列表;
步驟四、管理進程根據步驟三獲得的M組類目個數和M組類目中心點矢量列表構造
具有M個條目的聚類矢量中心表,將聚類矢量中心表發送給各個計算進程;
在M個條目的聚類矢量中心表中,一共有M行記錄,每一行代表柵格數據的一個聚類
的解;每一個聚類的解包含4個字段內容:
字段1:聚類解的編號;
字段2:類目個數,對應聚類解的類目個數;
字段3:類目中心點矢量列表,對應一組聚類中心點的矢量;
字段4:聚類結果質量,用于描述聚類質量,初始化是默認置為0;
步驟五、管理進程控制迭代求解過程;
步驟五一、每次迭代過程中,各個計算進程根據聚類矢量中心表進行聚類計算,更新
步驟四得到的聚類矢量中心表的內容,并發送回管理進程;
步驟五二、管理進程根據各個計算進程的聚類矢量中心表,更新管理進程的聚類矢量
中心表,并發送回各個計算進程重復步驟五一;經過5次迭代聚類矢量中心表的字段4出
現2次相同的最高的評價值,停止迭代即得到最終的聚類矢量中心表;
其中,字段4為聚類結果質量,用于描述聚類質量,初始化是默認值為0;最高的評
價值具體為在聚類矢量中心表中,字段4獲得最高值的那一行;
步驟六、在步驟五中得到的管理進程獲得的最終的聚類矢量中心表中,字段4獲得的
最高值一行的字段2描述了類目個數和字段4獲得最高值的一行的字段3描述了每個類目
的對應的矢量中心點;將字段4獲得最高值的一行的內容發送給各個計算進程;其中,字
段4獲得最高值的一行的內容具體包括字段1、字段2、字段3和字段4;
步驟七、各個計算進程根據字段4獲得最高值的一行的內容對計算進程對應的柵格數
據進行聚類,每個柵格的類目標記為距離柵格最近的那個矢量中心點所對應的類目即為得
到柵格聚類的結果;管理進程分別從各個計算進程收集柵格聚類的結果,并將柵格聚類的
結果寫入地理柵格數據文件中;即完成了一種處理大型地理柵格數據的并行聚類方法。
2.根據權利要求1所述一種處理大型地理柵格數據的并行聚類方法,其特征在于:
步驟一中在計算機集群上,利用管理節點啟動管理進程,管理進程根據大型地理柵格數據
量計算參與計算的計算節點數量,并在每個計算節點上啟動計算進程,同時為每個計算進
程編號具體步驟如下:
(1)管理節點啟動管理進程;
(2)管理進程讀取待聚類的大型地理柵格數據的行數RowNum、列數ColNum和文件總
的大小SumSize;待聚類的大型地理柵格數據每一行大小RowSize的計算方式為:
RowSize=SumSize/ColNum;
(3)管理進程計算N個計算節點;
根據每一個計算節點的最大數據加載量為MaxMemory,每一個計算節點最大加載的柵
格數據行數MaxRowNum為:
MaxRowNum=MaxMemroy%RowSize
加載N個計算節點的計算公式為:
N=Round(RowNum/MaxRowNum+0.5)
其中,Round為四舍五入操作,%表示求余數;
(4)利用N個計算節點的每個節點啟動一個計算進程,從1到N對計算進程進行編號。
3.根據權利要求2所述一種處理大型地理柵格數據的并行聚類方法,其特征在于:步
驟二中管理進程逐行讀取大型地理柵格數據,將整個大型地理柵格數據分散加載到N個計
算進程,將每行大型地理柵格數據發送給對應編號為ID的計算進程具體步驟所示如下:
(1)設定管理進程內的變量counter=0;
(2)counter=counter+1;
(3)管理進程讀取大型地理柵格數據中第counter行的數據,將大型地理柵格數據中第
counter行的數據發送給第counter行的數據對應編號為ID的計算進程,編號為ID的計算
進程在計算進程的內存空間中存儲在大型地理柵格數據中第counter行中;
其中,將大型地理柵格數據中第counter行的數據發送給第counter行的數據對應編號
為ID的計算公式如下:
ID=counter%N+1
(4)若counter比大型地理柵格數據的行數小,那么轉到步驟(2),若counter大于等于大
型地理柵格數據的行數轉到步驟(5);
(5)管理進程通知所有計算進程數據傳輸過程結束。
4.根據權利要求3所述一種處理大型地理柵格數據的并行聚類方法,其特征在于:
步驟三中管理進程隨機生成M組聚類解的初始值包含類目個數和類目中心點矢量列表具體
為:
(1)類目個數CenterNum:CenterNum為一個大于等于2并且小于等于最大類目個數
MaxCenterNum的數值:
CenterNum=Random(MaxCenterNum-1)+2;
MaxCenterNum=Round(M/2+0.5)
其中,Random(MaxCenterNum-1)產生一個0到MaxCenterNum-1的隨機數;Round()為
四舍五入操作;
(2)類目中心點矢量列表CenterVectorList:CenterVectorList隨機生成CenterNum個類目
中心點矢量;
對于大型地理柵格數據包含FeatureNum個空間屬性,隨機生成類目中心點為一個
FeatureNum維度的矢量Vector=(F1,F2,…FfeatureNum),Vector中的每一個維度Fi表示為:
Fi=(Max(Fi)-Min(Fi))(Random(100))/100+Min(Fi)
其中,Max(Fi)表示大型地理柵格數據中第i維度的最大值,Min(Fi)表示大型地理柵格數
據中第i維度的最小值,Random(100)產生一個0~100的隨機數。
5.根據權利要求4所述一種處理大型地理柵格數據的并行聚類方法,其特征在于:步
驟五中管理進程控制迭代求解過程具體步驟如下:
(1)、管理進程向各個計算進程發送指令后,管理進程處于等待結果狀態;
(2)、計算進程遍歷聚類矢量中心表的每一行進行計算,更新每一行的字段3類目中心
點列表;對于聚類矢量中心表的一行,計算進程根據字段3類目中心點列表將計算進程中
的柵格數據進行歸類,計算一個類目的柵格的每一維度的均值,所有的維度的均值共同構
成類目對應的新的中心點,將類目對應的所有新的中心點構成新的類目中心點列表,再將
新的類目中心點列表更新到聚類矢量中心表的對應行的字段3之中;
(3)、管理進程收集步驟(2)更新后的聚類矢量中心表,更新管理進程的聚類矢量中心表;
(4)、初始化步驟(3)中更新后的聚類矢量中心表的聚類結果質量最低的一行的類目個數
與類目中心點矢量列表;
(5)、管理進程將步驟(4)初始化后的聚類矢量中心表發回給各個計算進程;
(6)、經過5次迭代后的聚類矢量中心表的字段4的最高值沒有發生變化那么轉到步驟
(7)
(7)、管理進程控制的迭代求解過程結束;即得到最終的聚類矢量中心表。
6.根據權利要求5所述一種處理大型地理柵格數據的并行聚類方法,其特征在于:計
算進程遍歷聚類矢量中心表的每一行進行計算,更新每一行的字段3類目中心點列表;對
于聚類矢量中心表的一行,計算進程根據字段3類目中心點列表將計算進程中的柵格數據
進行歸類,計算一個類目的柵格的每一維度的均值,所有的維度的均值共同構成類目對應
的新的中心點,將類目對應的所有新的中心點構成新的類目中心點列表,再將新的類目中
心點列表更新到聚類矢量中心表的對應行的字段3之中具體步驟如下:
(1)、指定迭代變量counter=1;
(2)、讀取聚類矢量中心表第counter行內容,根據類目個數的列表、類目中心點的列表
以及步驟二中分散加載到N個計算進程的大型地理柵格數據進行一次K-Means聚類,獲得
新的類目中心點的列表;
(3)、將新的類目中心點列表寫回到聚類矢量中心表第counter行的第3個字段;
(4)、通過如下公式計算聚類結果質量:

其中,
E C e n t e r N u m = Σ k = 1 C e n t e r N u m ( Σ j = 1 n | | x j - z k | | ) ]]>
D k = m a x i , j = 1 C e n t e r N u m | | z i - z j | | ]]>
E 1 = Σ j = 1 n | | x j - Σ k C e n t e r N u m Z k C e n t e r N u m | | ]]>
式中,xj為柵格數據中第j個柵格的矢量,Zk為中心點列表第k個中心的矢量,
CenterNum為聚類中心的個數,Zi為中心點列表第i個中心的矢量,Zj為中心點列表第j個
中心的矢量;
(5)、將(4)獲得的柵格聚類結果質量數值評價結果寫入到聚類矢量中心表第counter行
的第4個字段;
(6)、counter=counter+1;
(7)、如果counter大于M那么執行步驟(8),否則轉到步驟(2);
(8)、結束更新字段過程;
其中,M為對應聚類矢量中心表的行數。
7.根據權利要求6所述一種處理大型地理柵格數據的并行聚類方法,其特征在于:更
新管理進程的聚類矢量中心表的具體步驟如下:
對于聚類矢量中心表中的每一條記錄,分別更新字段3和字段4;
對于字段3,類目中心點矢量列表中的第i個中心矢量Zi′計算公式如下:
Z i = Z i + Σ P N ( Z i - Z ( P ) i ) N ]]>
其中,Z(P)i為第P個計算進程的對應類目中心點矢量列表中第i個中心矢量;Zi′為
類目中心點矢量列表中更新之后的第i個中心矢量;
對于字段4,字段4的質量計算公式如下:

其中,柵格聚類結果質量(P)為第P個計算進程的柵格聚類結果質量;N為計算節點個
數。
8.根據權利要求7所述一種處理大型地理柵格數據的并行聚類方法,其特征在于:步
驟七中各個計算進程根據字段4獲得最高值的一行的內容對計算進程對應的柵格數據進行
聚類,每個柵格的類目標記為距離柵格最近的那個矢量中心點所對應的類目即為得到柵格
聚類的結果;管理進程分別從各個計算進程收集柵格聚類的結果,并將柵格聚類的結果寫
入地理柵格數據文件中具體步驟如下:
(1)、管理進程找到聚類矢量中心表中字段4數值最高的一行,將字段4數值最高一行
的類目中心點矢量列表發送給各個計算進程;
(2)、各個計算進程將接收到的聚類矢量中心表的內容確定在計算進程內所有柵格數據
的類屬關系;
(3)、設變量counter=1;
(4)、向第counter行對應的計算進程發出收集第counte行柵格數據中每一個柵格的類
屬情況的請求;
counter行對應的計算進程的ID采用如下公式計算:
ID=counter%N+1的進程;
(5)、收集到counter行柵格數據的每一個柵格的類屬情況之后,將counter行柵格數據的
每一個柵格的類屬情況寫入到結果柵格數據文件中;
(6)、counter=counter+1;
(7)、如果counter大于大型地理柵格數據的行數RowNum,那么轉到步驟(8),否則轉到
步驟(4);
(8)、結果柵格數據文件寫入過程結束。

說明書

一種處理大型地理柵格數據的并行聚類方法

技術領域

本發明涉及并行聚類方法,特別涉及一種處理大型地理柵格數據的并行聚類方法。

背景技術

在地理信息系統技術領域,地理柵格數據是一種重要的數據類型。在地理柵格數據
中每一個柵格記錄著一塊地表區域的空間、社會、經濟及環境屬性特征,它為描述地表的
信息提供數據基礎。

地理柵格數據的聚類是一種根據柵格位置、屬性特征的數值分布情況,在不需要事先
輸入已知樣本的情況下,對柵格數據所屬類目進行自動劃分的方法。通過聚類處理,人們
可以在沒有任何額外數據輸入的情況下,將地理柵格數據上劃分出同質的或近似的區域,
獲得一個地區更具概括性的知識,進而可以進行矢量地圖繪制、專題地圖制作和數據分析。
目前主流地理信息數據處理軟件均支持K-Means、EM等聚類處理方法,目前的方法需要
將柵格數據加載到內存中并反復遍歷計算,最終獲得聚類結果。

隨著大型存儲設備、高分辨率衛星傳感器的引入,地理柵格數據的分辨率也越來越
高。分辨率的提高引起了數據量呈幾何級數增長,如:分辨率從30米提高到1米,對于
同一地區數據量將提高30×30=900倍,原先100M的地理柵格數據將增長到近90G。由
于地理柵格數據量過大,一方面單個計算機難以加載全部地理柵格數據,難以運行聚類方
法;另一方面遍歷數據將消耗較多時間,聚類耗費運行時間將十分長。

所以需要針對大型地理柵格數據設計一種并行的聚類方法,將龐大的數據的加載和計
算聚類任務分散到多臺計算機當中,進行面向大型地理柵格數據的并行聚類。

在面向大型數據的并行聚類方法方面:如一種基于MapReduce的并行聚類方法
(201210434240.3),一種基于Hadoop的并行k均值聚類方法(201310568611.1),均傾
向于通過Hadoop的MapReduce框架進行并行來加快運行并應對大數據量。此類專利都需
要利用Map步驟將計算分散在到各個計算機當中,利用Reduce整合一次迭代的聚類成果;
地理柵格數據中的地物類型并不是均勻的混雜在一起的,而是一個區域、一段連續的空間
地物類型接近;面對十分龐大的柵格數據,Map塊文件通常不大(如:默認為64M),其
包含的區域可能面積非常小僅包含少數幾種地物,此時應用聚類將會引起類目的過渡細
分,聚類算法較難獲得柵格數據整體的類目分配與數據分布情況,因此較難得到較好聚類
結果。同時柵格數據需要較多次的迭代,每次迭代Reduce也會引起集群內部的大量通訊,
相對的也會減緩聚類速度。

在柵格或者遙感影像(遙感影像是柵格數據的一種)聚類方面:一種基于模糊c均
值聚類的農田劃分方法(201210312253.3)遙感圖像的主動譜聚類方法(201410136015.0);
遙感影像的聚類方法(201210022353.2);均沒有解決在柵格或者遙感影像數據十分龐大,
超過了單機加載極限的問題,當數據過大方法將會無法運行或者運行效率很低。

發明內容

本發明的目的是為了解決地理柵格十分龐大,超過了單機加載極限從而導致系統無法
運行或者運行效率很低,以及在多計算機并行聚類過程中各個進程計算結果的相互交換問
題,而提出的一種處理大型地理柵格數據的并行聚類方法。

上述的發明目的是通過以下技術方案實現的:

步驟一、在計算機集群上,利用管理節點啟動管理進程,管理進程根據大型地理柵格
數據量計算參與計算的計算節點數量,并在每個計算節點上啟動計算進程,同時為每個計
算進程編號;其中,一個計算機集群包含5~100臺通過互聯網連接的計算機,在計算機
集群中任選一臺計算機充當管理節點,計算機集群中除管理節點之外其它節點充當計算節
點;大型地理柵格數據的數據量為大于1000M;

步驟二、管理進程逐行讀取大型地理柵格數據,將整個大型地理柵格數據分散加載到
N個計算進程,將每行大型地理柵格數據發送給對應編號為ID的計算進程;

步驟三、管理進程隨機生成M組聚類解的初始值,其中,每一組聚類解的初始值包
含類目個數和類目中心點矢量列表;

步驟四、管理進程根據步驟三獲得的M組類目個數和M組類目中心點矢量列表構造
具有M個條目的聚類矢量中心表,將聚類矢量中心表發送給各個計算進程;

在M個條目的聚類矢量中心表中,一共有M行記錄,每一行代表柵格數據的一個聚
類的解;每一個聚類的解包含4個字段內容:

字段1:聚類解的編號;

字段2:類目個數,對應聚類解的類目個數;

字段3:類目中心點矢量列表,對應一組聚類中心點的矢量;

字段4:聚類結果質量,用于描述聚類質量,初始化是默認置為0;

步驟五、管理進程控制迭代求解過程;

步驟五一、每次迭代過程中,各個計算進程根據聚類矢量中心表進行聚類計算,更新
步驟四得到的聚類矢量中心表的內容,并發送回管理進程;

步驟五二、管理進程根據各個計算進程的聚類矢量中心表,更新管理進程的聚類矢量
中心表,并發送回各個計算進程重復步驟五一;經過5次迭代聚類矢量中心表的字段4
出現2次相同的最高的評價值,停止迭代即得到最終的聚類矢量中心表;

其中,字段4為聚類結果質量,用于描述聚類質量,初始化是默認值為0;最高的評
價值具體為在聚類矢量中心表中,字段4獲得最高值的那一行;

步驟六、在步驟五中得到的管理進程獲得的最終的聚類矢量中心表中,字段4獲得的
最高值一行的字段2描述了類目個數和字段4獲得最高值的一行的字段3描述了每個類目
的對應的矢量中心點;將字段4獲得最高值的一行的內容發送給各個計算進程;其中,字
段4獲得最高值的一行的內容具體包括字段1、字段2、字段3和字段4;

步驟七、各個計算進程根據字段4獲得最高值的一行的內容對計算進程對應的柵格數
據進行聚類,每個柵格的類目標記為距離柵格最近的那個矢量中心點所對應的類目即為得
到柵格聚類的結果;管理進程分別從各個計算進程收集柵格聚類的結果,并將柵格聚類的
結果寫入地理柵格數據文件中;即完成了一種處理大型地理柵格數據的并行聚類方法。

發明效果

本發明針對大型地理柵格數據,提供了一種可以將這些數據分散加載到多個計算機的
進程當中,并通過多臺計算機并行計算聯合求解最終獲得大型地理柵格數據的聚類結果。
利用本發明提出的方法,可以應對遠超過一臺計算機內存極限大小的地理柵格數據的聚類
工作,并快速獲得聚類結果。

本發明將整個柵格數據按照行逐個的分配給各個計算節點計算機,將整個大型柵格
數據分散加載到多臺計算機中;計算節點按照一定的間隔加載柵格數據,一方面限制了單
個計算節點加載的數據量,另一方面可以保證每個節點具備整個柵格數據類目與數據分布
的全局視角,更利于獲得聚類結果;

本發明在迭代計算的過程中構造了聚類矢量中心表,利用該表實現了多個計算機之間
聚類結果的同步和綜合,由于該表較小通訊量較低,所以每次聚類迭代可以較小通訊代價
完成;同時,聚類矢量中心表同時包含多組聚類中心與類目個數,在迭代過程中可以不斷
優選獲得更優化的聚類結果如圖7所示。

附圖說明

圖1為具體實施方式一提出的一種處理大型地理柵格數據的并行聚類方法流程圖;

圖2為具體實施方式二提出的根據柵格數據大小啟動管理進程和計算進程的步驟流
程圖;

圖3為具體實施方式三提出的將整個大型柵格數據分散加載到N個計算進程的步驟
流程圖;

圖4為具體實施方式一提出的聚類矢量中心表的結構示意圖;

圖5為具體實施方式五提出的管理進程控制的迭代求解過程示意圖;

圖6為具體實施方式八提出的管理進程逐行的分別從各個計算進程收集結果寫入到結
果柵格數據文件中的流程示意圖;

圖7為具體實施方式一提出的多個計算節點的計算機分散加載與處理大型地理柵格
數據示意圖;

圖8(a)為實施例提出的柵格數據的空間屬性1的灰度圖;

圖8(b)為實施例提出的柵格數據的空間屬性2的灰度圖;

圖8(c)為實施例提出的柵格數據的空間屬性3的灰度圖;

圖8(d)為實施例提出的柵格數據的空間屬性4的灰度圖;

圖8(e)為實施例提出的柵格數據的空間屬性5的灰度圖

圖9(a)為實施例提出的各個計算節點加載數據的示意圖;

圖9(b)為實施例提出的各個計算節點加載數據的示意圖;

圖9(c)為實施例提出的各個計算節點加載數據的示意圖;

圖9(d)為實施例提出的各個計算節點加載數據的示意圖;

圖9(e)為實施例提出的各個計算節點加載數據的示意圖;

圖9(f)為實施例提出的各個計算節點加載數據的示意圖;

圖10為實施例提出的柵格聚類結果對應的灰度圖。

具體實施方式

具體實施方式一:結合圖1本實施方式的一種處理大型地理柵格數據的并行聚類方
法,具體是按照以下步驟制備的:

步驟一、在計算機集群上,利用管理節點啟動管理進程,管理進程根據大型地理柵格
數據量計算參與計算的計算節點數量,并在每個計算節點上啟動計算進程,同時為每個計
算進程編號;其中,一個計算機集群包含5~100臺通過互聯網連接的計算機,在計算機
集群中任選一臺計算機充當管理節點,計算機集群中除管理節點之外其它節點充當計算節
點;大型地理柵格數據的數據量為大于1000M;

步驟二、管理進程逐行讀取大型地理柵格數據,將整個大型地理柵格數據分散加載到
N個計算進程,將每行大型地理柵格數據發送給對應編號為ID的計算進程;

步驟三、管理進程隨機生成M組聚類解的初始值,其中,每一組聚類解的初始值包
含類目個數和類目中心點矢量列表;

步驟四、管理進程根據步驟三獲得的M組類目個數和M組類目中心點矢量列表構造
具有M個條目的聚類矢量中心表,將聚類矢量中心表發送給各個計算進程;

管理進程隨機生成M組聚類初始值,M的大小根據聚類目標的復雜程度而定;

對于城市等人工建筑較多的結構復雜地區:M取30;

對于市郊、城鄉結合地區:M取20;

對于鄉村和大面積自然景觀地區:M取20;

其中,聚類矢量中心表由管理進程構造,聚類矢量中心表如圖4所示,在M個條目
的聚類矢量中心表中,一共有M行記錄,每一行代表柵格數據的一個聚類的解(即每一
行對應一個聚類的解);每一個聚類的解包含4個字段內容:

字段1:聚類解的編號;

字段2:類目個數,對應聚類解的類目個數;

字段3:類目中心點矢量列表,對應一組聚類中心點的矢量;

字段4:聚類結果質量(聚類矢量中心表有很多行,每一行都是柵格數據可能的聚類
解,每個聚類解都由字段4來描述聚類質量),用于描述聚類質量,初始化是默認置為0;

步驟五、管理進程控制迭代求解過程;

步驟五一、每次迭代過程中,各個計算進程根據聚類矢量中心表進行聚類計算,更新
步驟四得到的聚類矢量中心表的內容,并發送回管理進程;

步驟五二、管理進程根據各個計算進程的聚類矢量中心表,更新管理進程的聚類矢量
中心表,并發送回各個計算進程重復步驟五一;經過5次迭代聚類矢量中心表的字段4
出現2次相同的最高的評價值(評價是一個數值,值越大就越高),停止迭代即得到最終
的聚類矢量中心表(這個表示最終的聚類在矢量上的表達);

其中,字段4為聚類結果質量(聚類矢量中心表有很多行,每一行都是柵格數據可能
的聚類解,每個聚類解都由字段4來描述聚類質量),用于描述聚類質量,初始化是默認
值為0;最高的評價值具體為在聚類矢量中心表中,字段4獲得最高值的那一行;

步驟六、在步驟五中得到的管理進程獲得的最終的聚類矢量中心表中,字段4獲得的
最高值一行的字段2描述了類目個數和字段4獲得最高值的一行的字段3描述了每個類目
的對應的矢量中心點;將字段4獲得最高值的一行的內容發送給各個計算進程;其中,字
段4獲得最高值的一行的內容具體包括字段1、字段2、字段3和字段4;

步驟七、各個計算進程根據字段4獲得最高值的一行的內容對計算進程對應的柵格數
據進行聚類,每個柵格的類目標記為距離柵格最近的那個矢量中心點所對應的類目即為得
到柵格聚類的結果;管理進程分別從各個計算進程收集柵格聚類的結果,并將柵格聚類的
結果寫入地理柵格數據文件中;即完成了一種處理大型地理柵格數據的并行聚類方法。

本實施方式效果:

本實施方式針對大型地理柵格數據,提供了一種可以將這些數據分散加載到多個計算
機的進程當中,并通過多臺計算機并行計算聯合求解最終獲得大型地理柵格數據的聚類結
果。利用本實施方式提出的方法,可以應對遠超過一臺計算機內存極限大小的地理柵格數
據的聚類工作,并快速獲得聚類結果。

本實施方式將整個柵格數據按照行逐個的分配給各個計算節點計算機,將整個大型
柵格數據分散加載到多臺計算機中;計算節點按照一定的間隔加載柵格數據,一方面限制
了單個計算節點加載的數據量,另一方面可以保證每個節點具備整個柵格數據類目與數據
分布的全局視角,更利于獲得聚類結果;

本實施方式在迭代計算的過程中構造了聚類矢量中心表,利用該表實現了多個計算
機之間聚類結果的同步和綜合,由于該表較小通訊量較低,所以每次聚類迭代可以較小通
訊代價完成;同時,聚類矢量中心表同時包含多組聚類中心與類目個數,在迭代過程中可
以不斷優選獲得更優化的聚類結果如圖7所示。

具體實施方式二:本實施方式與具體實施方式一不同的是:步驟一中在計算機集群
上,利用管理節點啟動管理進程,管理進程根據大型地理柵格數據量計算參與計算的計算
節點數量,并在每個計算節點上啟動計算進程,同時為每個計算進程編號具體步驟(該步
驟的處理流程如圖2所示)如下:

(1)管理節點啟動管理進程;

(2)管理進程讀取待聚類的大型地理柵格數據的行數RowNum、列數ColNum和文件總
的大小SumSize;待聚類的大型地理柵格數據每一行大小RowSize的計算方式為:

RowSize=SumSize/ColNum;

(3)管理進程計算N個計算節點;

根據每一個計算節點的最大數據加載量為MaxMemory,每一個計算節點最大加載的
柵格數據行數MaxRowNum為:

MaxRowNum=MaxMemroy%RowSize

加載N個計算節點的計算公式為:

N=Round(RowNum/MaxRowNum+0.5)

其中,Round為四舍五入操作,%表示求余數;

(4)利用N個計算節點的每個節點啟動一個計算進程,從1到N對計算進程進行編號。
其它步驟及參數與具體實施方式一相同。

具體實施方式三:本實施方式與具體實施方式一或二不同的是:步驟二中管理進程逐
行讀取大型地理柵格數據,將整個大型地理柵格數據分散加載到N個計算進程,將每行
大型地理柵格數據發送給對應編號為ID的計算進程具體步驟所示如下(如圖3):

(1)設定管理進程內的變量counter=0;

(2)counter=counter+1;

(3)管理進程讀取大型地理柵格數據中第counter行的數據,將大型地理柵格數據中第
counter行的數據發送給第counter行的數據對應編號為ID的計算進程,編號為ID的計算
進程在計算進程的內存空間中存儲在大型地理柵格數據中第counter行中;

其中,將大型地理柵格數據中第counter行的數據發送給第counter行的數據對應編號
為ID的計算公式如下:

ID=counter%N+1

(4)若counter比大型地理柵格數據的行數小,那么轉到步驟(2),若counter大于等于
大型地理柵格數據的行數轉到步驟(5);

(5)管理進程通知所有計算進程數據傳輸過程結束。其它步驟及參數與具體實施方式
一或二相同。

具體實施方式四:本實施方式與具體實施方式一至三之一不同的是:步驟三中管理
進程隨機生成M組聚類解的初始值包含類目個數和類目中心點矢量列表具體為:

(1)類目個數CenterNum:CenterNum為一個大于等于2并且小于等于最大類目個數
MaxCenterNum的數值:

CenterNum=Random(MaxCenterNum-1)+2;

MaxCenterNum=Round(M/2+0.5)

其中,Random(MaxCenterNum-1)產生一個0到MaxCenterNum-1的隨機數;
MaxCenterNum可以根據用戶的需要進行輸入,也可以指定一個默認值:Round()為四舍
五入操作;

(2)類目中心點矢量列表CenterVectorList:CenterVectorList隨機生成CenterNum個類
目中心點矢量;

對于大型地理柵格數據包含FeatureNum個空間屬性,隨機生成類目中心點為一個
FeatureNum維度的矢量Vector=(F1,F2,…FfeatureNum),Vector中的每一個維度Fi表示為:

Fi=(Max(Fi)-Min(Fi))(Random(100))/100+Min(Fi)

其中,Max(Fi)表示大型地理柵格數據中第i維度的最大值,Min(Fi)表示大型地理柵
格數據中第i維度的最小值,Random(100)產生一個0~100的隨機數。其它步驟及參數與
具體實施方式一至三之一相同。

具體實施方式五:本實施方式與具體實施方式一至四之一不同的是:步驟五中管理進
程控制迭代求解過程具體步驟如下(如圖5所示):

(1)、管理進程向各個計算進程發送指令后,管理進程處于等待結果狀態;

(2)、各個計算進程接收指令后進行計算,各個計算進程都有相應的聚類矢量中心表,
各個計算節點的計算進程中互不干擾進行聚類計算;計算進程遍歷聚類矢量中心表的每一
行進行計算,更新每一行的字段3類目中心點列表;對于聚類矢量中心表的一行,計算進
程根據字段3類目中心點列表將計算進程中的柵格數據進行歸類,計算一個類目的柵格的
每一維度的均值,所有的維度的均值共同構成類目對應的新的中心點,將類目對應的所有
新的中心點構成新的類目中心點列表,再將新的類目中心點列表更新到聚類矢量中心表的
對應行的字段3之中;

(3)、管理進程收集步驟(2)更新后的聚類矢量中心表,更新管理進程的聚類矢量中心
表;

(4)、初始化步驟(3)中更新后的聚類矢量中心表的聚類結果質量最低的一行的類目個
數與類目中心點矢量列表;

(5)、管理進程將步驟(4)初始化后的聚類矢量中心表發回給各個計算進程;

(6)、經過5次迭代后(重復5次步驟(1)~(6)后)的聚類矢量中心表的字段4的最高
值沒有發生變化;

(7)、管理進程控制的迭代求解過程結束;即得到最終的聚類矢量中心表;

管理進程將數據發送給計算進程,計算進程每次迭代的時候更新聚類矢量中心表,并
將最終的聚類矢量中心表發送給管理進程。其它步驟及參數與具體實施方式一至四之一相
同。

具體實施方式六:本實施方式與具體實施方式一至五之一不同的是:計算進程遍歷聚
類矢量中心表的每一行進行計算,更新每一行的字段3類目中心點列表;對于聚類矢量中
心表的一行,計算進程根據字段3類目中心點列表將計算進程中的柵格數據進行歸類,計
算一個類目的柵格的每一維度的均值,所有的維度的均值共同構成類目對應的新的中心
點,將類目對應的所有新的中心點構成新的類目中心點列表,再將新的類目中心點列表更
新到聚類矢量中心表的對應行的字段3之中具體步驟如下:

(1)、指定變量counter=1;

(2)、讀取聚類矢量中心表第counter行內容,根據類目個數的列表、類目中心點的列
表以及步驟二中分散加載到N個計算進程的大型地理柵格數據進行一次K-Means聚類,
獲得新的類目中心點的列表;

(3)、將新的類目中心點列表寫回到聚類矢量中心表第counter行的第3個字段;

(4)、通過如下公式計算聚類結果質量:


其中,

E C e n t e r N u m = Σ k = 1 C e n t e r N u m ( Σ j = 1 n | | x j - z k | | ) ]]>

D k = m a x i , j = 1 C e n t e r N u m | | z i - z j | | ]]>

E 1 = Σ j = 1 n | | x j - Σ k C e n t e r N u m Z k C e n t e r N u m | | ]]>

式中,xj為柵格數據中第j個柵格的矢量,Zk為中心點列表第k個中心的矢量,通過
柵格聚類結果質量公式獲得一個柵格聚類結果質量數值評價,柵格聚類結果質量數值越高
柵格聚類的質量就越好;CenterNum為聚類中心的個數,Zi為中心點列表第i個中心的矢
量,Zj為中心點列表第j個中心的矢量;

(5)、將(4)獲得的柵格聚類結果質量數值評價結果(即對柵格聚類結果質量的效果進
行打分)寫入到聚類矢量中心表第counter行的第4個字段;

(6)、counter=counter+1;

(7)、如果counter大于M那么執行步驟(8),否則(如果counter≤M)轉到步驟(2);

(8)、結束更新字段過程;

其中,M為對應聚類矢量中心表的行數。其它步驟及參數與具體實施方式一至五之
一相同。

具體實施方式七:本實施方式與具體實施方式一至六之一不同的是:更新管理進程的
聚類矢量中心表的具體步驟如下:

對于聚類矢量中心表中的每一條記錄,分別更新字段3和字段4;

對于字段3,類目中心點矢量列表中的第i個中心矢量Zi′計算公式如下:

Z i = Z i + Σ P N ( Z i - Z ( P ) i ) N ]]>

其中,Z(P)i為第P個計算進程的對應類目中心點矢量列表中第i個中心矢量;Zi′為
類目中心點矢量列表中更新之后的第i個中心矢量;

對于字段4,其計算公式如下:


其中,柵格聚類結果質量(P)為第P個計算進程的聚類結果質量;N為計算節點個數。
其它步驟及參數與具體實施方式一至六之一相同。

具體實施方式八:本實施方式與具體實施方式一至七之一不同的是:步驟七中各個計
算進程根據字段4獲得最高值的一行的內容對計算進程對應的柵格數據進行聚類,每個柵
格的類目標記為距離柵格最近的那個矢量中心點所對應的類目即為得到柵格聚類的結果;
管理進程分別從各個計算進程收集柵格聚類的結果,并將柵格聚類的結果寫入地理柵格數
據文件中具體步驟如下(如圖6所示):

(1)、管理進程找到聚類矢量中心表中字段4數值最高的一行,將字段4數值最高一
行的類目中心點矢量列表發送給各個計算進程;

(2)、各個計算進程將接收到的聚類矢量中心表的內容確定在計算進程內所有柵格數
據的類屬關系;

(3)、設變量counter=1;

(4)、向第counter行對應的計算進程發出收集第counte行柵格數據中每一個柵格的類
屬情況的請求;

counter行對應的計算進程的ID采用如下公式計算:

ID=counter%N+1個進程

對應的計算進程的ID可以由ID=counter%N+1的公式計算出來,比如第1001行對
應的是3號進程,那么管理進程應該向3號進程索要該行聚類的結果;

(5)、收集到counter行柵格數據的每一個柵格的類屬情況之后,將counter行柵格數據
的每一個柵格的類屬情況寫入到結果柵格數據文件中;

(6)、counter=counter+1;

(7)、如果counter大于大型地理柵格數據的行數RowNum,那么轉到步驟(8),否則轉
到步驟(4);

(8)、結果柵格數據文件寫入過程結束。其它步驟及參數與具體實施方式一至七之一相
同。

采用以下實施例驗證本發明的有益效果:

實施例一:

本實施例一種處理大型地理柵格數據的并行聚類方法,具體是按照以下步驟制備的:
為了驗證和測試本專利提出方法,引入我國沿海地區的一部分地理柵格數據,該數據每個
柵格的分辨率為1米×1米,包含5個空間屬性,柵格數目為3萬×3萬,其數據文件大
小為35G。將每個柵格的空間屬性映射為256級灰度圖,圖8(a)~圖8(e)為地理柵格數據
的5個空間屬性,將看到每一個空間屬性所示的效果:

測試用計算機集群環境為1臺8G內存的服務器充當管理節點,40臺包含8G內存
計算機充當計算節點,每個計算節點內存最大加載的數據量為6G(計算節點需要預留出一
部分內存給操作系統和其他程序使用),通過千兆局域網連接在一起。顯然任何一臺計算
機的內存都無法加載35G數據,傳統的加載之后在運行的方法無法正常運行。

利用本發明提出的方法,對改柵格數據進行聚類。

1、通過步驟一計算出共需要6個計算節點。

2、通過步驟二將整個數據分散加載到6個計算節點之中,管理節點負責分配數據,
每個計算節點加載了5.83G的數據,實現的所有數據在集群內部的加載;加載結果如圖
9(a)~圖9(f)所示,每個計算節點均加載了部分柵格數據:

3、通過步驟三、步驟四和步驟五獲得聚類矢量中心表,通過步驟六獲得最終的聚類
效果,將原有的擁有5個空間屬性,每個屬性包含多種數值可能的大型柵格數據分為了4
個類目。圖10為輸出柵格的類屬結果轉換為灰度圖像的結果,對于屬于類目1的柵格標
記為白色,對于該類目的柵格其對應的地表類型大多屬于旱地和干旱的草地;屬于類目2
的柵格標記為淺灰色,對于該類目的柵格其對應的地表類型大多屬于沼澤;屬于類目3
的柵格標記為深灰色,對于該類目的柵格其對應的地表類型大多屬于草地;屬于類目4
的柵格標記為深黑色,對于該類目的柵格其對應的地表類型大多屬于水田;

本發明還可有其它多種實施例,在不背離本發明精神及其實質的情況下,本領域技術
人員當可根據本發明作出各種相應的改變和變形,但這些相應的改變和變形都應屬于本發
明所附的權利要求的保護范圍。

關 鍵 詞:
一種 處理 大型 地理 柵格 數據 并行 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:一種處理大型地理柵格數據的并行聚類方法.pdf
鏈接地址:http://www.wwszu.club/p-6401475.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大