基于并行計算的空間co-location模式挖掘*

和鳳珍, 賈志洋, 張丹丹

(云南大學 旅游文化學院，云南 麗江 674100)

?

基于并行計算的空間co-location模式挖掘*

和鳳珍, 賈志洋, 張丹丹

(云南大學 旅游文化學院，云南 麗江 674100)

提出適合并行計算的空間數(shù)據(jù)分區(qū)算法，并在此基礎(chǔ)上提出基于并行計算的空間co-location挖掘算法.在三類數(shù)據(jù)集上做了大量的實驗.實驗結(jié)果表明，基于并行計算的算法在很大程度上提高了挖掘的效率，為進行空間大數(shù)據(jù)的挖掘提供了有效且快速的方法.

空間co-location模式挖掘；數(shù)據(jù)分區(qū)；并行計算；并行算法

空間co-location模式挖掘可以應(yīng)用在很多領(lǐng)域中[1-3]，它是從空間數(shù)據(jù)庫中發(fā)現(xiàn)實例頻繁關(guān)聯(lián)的模式的過程，這些模式是一組空間特征的子集.目前，空間co-location 模式挖掘算法都是串行的數(shù)據(jù)挖掘方法[4-11].本文主要研究基于并行計算[12]的空間co-location模式挖掘.

1 空間數(shù)據(jù)分區(qū)

在并行數(shù)據(jù)挖掘中，為了提高挖掘效率，數(shù)據(jù)需要合理分割，否則會因處理機等待而影響算法執(zhí)行的效率.中位數(shù)是一組數(shù)據(jù)中最中間的那一個，按照實例集橫坐標或縱坐標的中位數(shù)對數(shù)據(jù)進行分割就可以保證負載的均衡.基于距離的空間co-location模式挖掘方法就是挖掘出滿足鄰近關(guān)系R的co-location模式[5]，但在基于中位數(shù)的劃分中有些滿足鄰近關(guān)系R的模式會分割到不同的區(qū)域，從而導致結(jié)果不具備完整性.為了避免這種情況，在分割空間數(shù)據(jù)時，區(qū)與區(qū)之間劃出距離為距離閾值的一半(d/2)的交叉區(qū)域.這樣保證了模式實例的不丟失，但中位數(shù)兩邊距離閾值的一半(d/2)的距離內(nèi)的實例就會出現(xiàn)重復(fù)計算的情況，如果中位數(shù)的兩邊實例分布很稠密會浪費很多的時間.為了確保劃分的高效性，提出基于中位數(shù)的橫中軸劃分與縱中軸劃分兩種.

定義1 (橫中軸線/縱中軸線)過實例集y坐標的中位數(shù)且平行于x軸的線段稱為橫中軸線；相應(yīng)的過x軸的中位數(shù)且平行于y軸的中軸線稱為縱中軸線.

定義2 (左區(qū)/右區(qū))把空間數(shù)據(jù)分成實例數(shù)相等的左右兩個分塊.左邊由左邊界到橫中軸線向右平移d/2(d為鄰近關(guān)系R的距離閾值)的區(qū)域組成，并稱之為左區(qū)，簡記Dl；右邊由橫中軸線向左平移d/2到右邊界的區(qū)域組成，并稱之為右區(qū)，簡記Dr.

基于中軸線的劃分法：①求出空間數(shù)據(jù)集x軸坐標的中位數(shù)；②求出空間數(shù)據(jù)集y軸坐標的中位數(shù)；③求出左右距縱中軸線均為d/2的區(qū)域內(nèi)的實例數(shù)(m)；④求出上下距橫中軸線均為d/2區(qū)域內(nèi)的實例數(shù)(n)；⑤如果m大于n，則橫中軸劃分數(shù)據(jù)，否則縱中軸劃分數(shù)據(jù).

縱中軸劃分：由縱中軸線把實例空間分為左區(qū)與右區(qū)的劃分稱為縱中軸劃分，如圖1所示.橫中軸劃分：由橫中軸線把實例空間分為上區(qū)與下區(qū)的劃分稱為橫中軸劃分，如圖2所示.

圖1 縱中軸劃分圖 圖2 橫中軸劃分圖

基于以上分析，數(shù)據(jù)分區(qū)算法設(shè)計如下：

算法1：數(shù)據(jù)劃分(div_domain)算法

輸入：

空間特征集合：featureSet[n]；空間實例集合：exampleSet[m].

輸出：Dl(Dup),Dr(Ddown).

變量：

Ix：實例集x坐標的集合；Iy：實例集y坐標的集合；Xm：實例集x坐標的中位數(shù)；Ym：實例集y坐標的中位數(shù)；mx_d：x軸方向上的中位數(shù)左右d距離內(nèi)的實例數(shù)；my_d：y軸方向上的中位數(shù)上下d距離內(nèi)的實例數(shù)；Dl(Dup)：左(上)區(qū)；Dr(Ddown)：右(下)區(qū)；dis_threshold:距離閾值.

步驟：

1)Dl(Dup)=Φ;Dr(Ddown)=Φ;

Dx={exampleSet[1].x…exampleSet[m].x}；Dy={exampleSet[1].y…exampleSet[m].y}；//初始化變量

2)Xm=Gen_median(Dx);Ym=Gen_median(Dy);//求實例在x(y)軸方向上的中位數(shù)

mx_d=Count_example(Dx_d);my_d=Count_example(Dy_d);//求x(y)軸方向上距中位數(shù)左右各d/2距離內(nèi)的實例數(shù)

3)數(shù)據(jù)分區(qū)

3.1)判斷m與n的大小;

3.2)如果m大于n，則縱中軸劃分空間，否則橫中軸劃分空間;

4)輸出Dl(Dup),Dr(Ddown).

2 并行co-location模式挖掘算法

2.1 并行計算機處理機互連方式

采用TCP/IP通信協(xié)議來實現(xiàn)主機與輔機之間的通信.其中，主機采用服務(wù)器端編程方式，而輔機采用客戶端編程的方式.

2.1.1 服務(wù)器端編程

為了使用TCP/IP來實現(xiàn)各主機間的通信，使用C#編程時，引用了TCP/IP通信接口類“usingSystem.Net.Sockets”.服務(wù)器端編程包括以下步驟：定義相關(guān)變量；定義監(jiān)聽函數(shù)；啟動監(jiān)聽程序；接收并處理客戶端信息.

2.1.2 客戶端編程

在客戶端的編程中使用C#編程，同樣引用了TCP/IP通信接口“usingSystem.Net.Sockets”，客戶端編程包括以下步驟：定義相關(guān)變量；建立與服務(wù)器的連接；監(jiān)聽并接收來自服務(wù)器的信息；向服務(wù)器發(fā)送信息.

2.2 全連接算法

全連接算法中候選模式及其實例的生成都是通過連接操作而得到的，即該算法在模式及實例的生成上類似于Apriori算法[1].此算法有兩個最重要的步驟：候選模式生成和實例的生成.

生成候選模式：通過連接兩個前k-2階相同的k-1階頻繁模式來生成每一個k階模式，每個生成k階模式的k-1階子模式都是頻繁模式.

生成實例：設(shè)k階模式c3是由k-1階模式c1和c2連接得到，則模式c1和c2的表實例按照前k-2項相同進行連接.如果兩個實例滿足鄰近關(guān)系R則連接得到模式c3對應(yīng)的表實例.

算法2：全連接(Join-Base)算法

輸入：

空間特征集合：featureSet[n];空間實例集合：exampleSet[m];鄰近關(guān)系R的距離閾值：d;最小參與度閾值：min_prev;最小置信度閾值：min_cond_prob.

輸出：頻繁的空間co-location模式集合.

變量：

k:colocation的階;Ck:k階候選co-location集;Tk:Ck中的co-location表實例集;Pk:k階co-location頻繁集;T_Ck:Ck中k階co-location的粗糙表實例集.

步驟：

1)co-locationsizek=1;C1=featureSet[n];P1=featureSet[n];

2)T1=generate_able_instance(C1,xampleSet[n]);

3)if(fmul=TURE)then

4)T_C1=generate_table_instance(C1,multi_event(E));//1階粗糙表實例

5)InitiallizedatastructureCk,Tk,Pk,Rk,T_Ck,tobeemptyfor1

6)While(notemptyPkandk

7)Ck+1=gen_candidate_colocation(Ck,k);//產(chǎn)生候選k+1階co-location模式

8)if(fmul=TURE)then

9)Ck+1=multi_resolution_pruning(min_prev,T_Ck，multi_rel(R));//基于多分辨方法剪枝候選k+1階co-location模式集

10)Tk+1=gen_table_instance(min_prve,Ck+1,Tk,R);//產(chǎn)生候選表實例

11)Pk+1=select_prevalence_co-location(min_prev,Ck+1,Tk+1);//計算候選參與度，產(chǎn)生頻繁k+1階co-location

12)Rk+1=gen_co-location_rule(min_prev,Ck+1,Tk+1);//基于條件概率閾值，產(chǎn)生頻繁k+1階co-location規(guī)則

13)k:=k+1;}

14)Return∪(R2,…,Rk+1);

2.3 基于并行計算的全連接算法

下面給出基于并行計算的新算法，該算法稱之為PC-join-base算法，算法主要思想是使用局域網(wǎng)內(nèi)的兩臺計算機來進行基于并行計算的全連接算法.一臺計算機(PC1)求左區(qū)Dl(Dup)的表實例，另一臺計算機(PC2)求右區(qū)Dr(Ddown)的表實例，求出每階二個區(qū)域內(nèi)的表實例后合并每階的表實例得到相應(yīng)階的表實例，進而得到co-location頻繁模式.具體挖掘過程如下：

算法3：PC-join-base算法

輸入：

空間特征集合：featureSet[n]；空間實例集合：exampleSet[m];最小參與度閾值：min_prev；最小置信度閾值：min_cond_prob

鄰近關(guān)系R的距離閾值：d.

輸出：頻繁的空間co-location模式集合

變量：

domain_width;domain_height;左(上)區(qū):Dl(Dup);右(下)區(qū):Dr(Ddown).

步驟：

1)在PC1中執(zhí)行div_domain();//求出左區(qū)(上區(qū))Dl(Dup)和右區(qū)(下區(qū))Dr(Ddown);

2)由PC1把右區(qū)(下區(qū))Dr(Ddown),發(fā)送到PC2;

3)并行執(zhí)行3.1和3.2

3.1) 在PC2中求右區(qū)(下區(qū))Dr(Ddown)的一階表實例;

waituntil(完成k+1階表實例的求解過程);

將右區(qū)(下區(qū))Dr(Ddown)的一階表實例發(fā)送給PC1;

3.2) 在PC1中求左區(qū)(上區(qū))Dl(Dup),的一階表實例;

4)在PC1上合并Dl(Dup)和Dr(Ddown)的一階表實例后得一階頻繁模式;

5)k=1;//k是階數(shù)

do

{

5.1) 在PC1上輸出k階頻繁模式;

5.2) 向PC2發(fā)一個命令，讓其繼續(xù)應(yīng)用join-base算法求右區(qū)(下區(qū))Dr(Ddown)中的k+1階表實例;

5.3) 并行執(zhí)行5.3.1和5.3.2

5.3.1) 在PC2中waituntil(完成k+1階表實例的求解過程)

{

將PC2中右區(qū)(下區(qū))Dr(Ddown)的k+1階表實例發(fā)送給PC1;}

5.3.2) 在PC1上應(yīng)用join-base算法求左區(qū)(上區(qū))Dl(Dup)中的k+1階表實例;

5.4) 在PC1上合并5.3.1和5.3.2中求出k+1階表實例(去除其中冗余的行實例);

5.5) 在PC1上求出k+1階表實例的參與度，從而生成k+1階頻繁模式;

k++;

}while(存在k階的頻繁模式)

2.4 剪枝策略

算法3在求解k+1階表實例的過程中需要合并兩臺PC上的表實例，在這個過程可以用定理1對其進行剪枝.

定理1 如果k階co-location模式P的左右兩個區(qū)參與度之和小于最小參與度閾值，則任意P的超集模式P′是非頻繁的.

證明 用算法1對數(shù)據(jù)進行分區(qū)時，左(上)區(qū)與右(下)區(qū)中間距中軸線左(上)右(下)d/2的區(qū)域是重疊的，如果k階co-location模式P的左區(qū)與右區(qū)的參與之度之和小于最小參與度閾值，則必有PI(P)

3 算法分析與討論

3.1 算法的正確性與可擴展性

定理2 基于并行計算挖掘空間co-location模式挖掘算法是正確的.

證明 (1)證明基于縱中軸線劃分的并行計算算法是正確的.

設(shè)Ei與Ej為所劃分空間內(nèi)的任意兩個實例，Xm為實例集x坐標的中位數(shù)，Ei_x為實例i的x坐標值，Ej_x為實例j的x坐標值，d為距離閾值.則在劃分中Ei與Ej分布有以下三種情況：

a)Ei_x

b)Xm-d/2≤Ei_x≤Xm且Xm≤Ej_x≤Xm+d/2;

c)Ei_xXm+d/2.

(1.1) 如果Ei_x

(1.2) 如果Xm-d/2≤Ei_x≤Xm且Xm≤Ej_x≤Xm+d/2，則Ei_x∈Dl，Ej_x∈Dl且Ei_x∈Dr，Ej_x∈Dr.此時Ei與Ej均在兩臺PC中，模式實例也不可能丟失.

(1.3)如果Ej_x>Xm+d/2且Ei_x

綜上，基于縱中軸線劃分的算法是正確的.

(2)同理可證基于橫中軸線劃分的并行算法是正確的.

基于并行計算挖掘空間co-location模式挖掘算法可繼續(xù)按一分為二的形式擴展.由基于中位線的劃分法可知，為了確保負載的均衡應(yīng)該把實例空間分為實例數(shù)目相等的區(qū)域.那么可以把實例空間首先一分為二，再在兩部分中分別使用基于中軸線的劃分方法，依次在把每個部分一分為二.這樣，經(jīng)過n次就可以把實例空間分成2n個分塊.可以分別把這2n個分塊交給2n臺處理機來計算.

3.2 算法的復(fù)雜度分析

3.2.1 算法2的時間復(fù)雜度分析

定理3 若含有m個特征的集合F中各特征的實例數(shù)基本相等，l為各個特征的平均實例數(shù).這時全連接算法從i-1階生成i階模式的最壞時間復(fù)雜度為P′.其中i≥2.

證明 挖掘1階模式的時間消耗為mL；生成i階模式時，由于i-1階表實例的最大長度為li-1，生成i階表實例的前i-2階(列)需比較O((li-1)2)次，對于前i-2階的每一次連接，最后兩列所需連接次數(shù)為li，這時i階的時間消耗最大值約為：

3.2.2 算法3的時間復(fù)雜度分析

4 實驗分析

實驗所用的兩臺PC的配置為Intel(R)Core(TM)i3-2100CPU3.10GHz,4G內(nèi)存；操作系統(tǒng)為Windows7；開發(fā)平臺為MicrosoftVisualStudio2008；開發(fā)語言為C#.實驗所用的數(shù)據(jù)為三江并流區(qū)域老君山地帶的真實植被數(shù)據(jù).實驗分析了距離閾值、參與度閾值和實例數(shù)目等對算法的影響，驗證了基于并行計算的co-location模式挖掘算法的正確性以及高效性.

4.1 參與度閾值對算法的影響

考察參與度閾值的變化對算法執(zhí)行時間的影響.特征個數(shù)為11，實例個數(shù)為65 535.距離閾值為30.

圖3中可以看出：基于并行計算的co-location模式挖掘算法優(yōu)于全連接算法.其他參數(shù)相同的情況下，空間co-location模式挖掘的運算量是隨參與度閾值的增大而減小的.因此，當參與度閾值比較大的時候，基于并行計算的算法相對于全連接的優(yōu)勢不是特別明顯.但參與度閾值比較小的時候連接操作很多算法運算量就很大，基于并行計算的算法明顯優(yōu)于全連接算法.

圖3 參與度閾值對算法執(zhí)行時間的影響 圖4 距離閾值對算法執(zhí)行時間的影響

4.2 距離閾值對算法的影響

考察距離閾值的變化對算法執(zhí)行時間的影響.特征個數(shù)為10，實例總數(shù)為8 000，參與度閾值為0.7.

圖4中可以看出：當距離閾值比較小的時候，由于計算量小，基于并行計算的co-location模式挖掘算法相對于基于全連接的算法優(yōu)勢不是很明顯.但隨著距離閾值增大運算量也增大，基于并行計算的算法明顯優(yōu)于全連接算法.

4.3 實例數(shù)目對算法的影響

考察實例數(shù)目的變化對算法執(zhí)行時間的影響，距離閾值為30，參與度閾值為0.7.圖5中可以看出：當實例數(shù)目較小時，基于并行計算的co-location模式挖掘算法的優(yōu)勢不太明顯.但隨著實例數(shù)目的增多，基于并行計算的算法的優(yōu)勢越來越明顯.

圖5 實例數(shù)目對算法執(zhí)行時間的影響 圖6 不同PC數(shù)目對算法執(zhí)行時間的影響

4.4 PC數(shù)目對算法的影響

考察PC數(shù)目的變化對算法執(zhí)行時間的影響.特征個數(shù)為11，實例個數(shù)為65 535，距離閾值為30.

圖6中可以看出：隨著PC臺數(shù)的增加算法所用的時間也相應(yīng)地減少.由于合并實例時花費了一小部分的時間，4臺PC并行計算的時間略大于2臺PC并行計算所花的時間的一半.同樣的，8臺PC并行計算的時間略大于4臺PC并行計算所花的時間的一半.

5 總 結(jié)

將并行計算與空間co-location模式挖掘方法相結(jié)合，提出了一種基于并行計算的空間co-location模式挖掘算法.該算法基于中軸線來分割數(shù)據(jù)，因中軸線的性質(zhì)確保了負載的均衡.在此基礎(chǔ)上，統(tǒng)計x軸與y軸區(qū)與區(qū)之間重復(fù)部分的實例數(shù)而后選擇實例數(shù)少的中軸線來分區(qū)使得在實例分布相對稀疏的區(qū)域分區(qū)，以此確保算法的高效性.實驗分析表明，三類真實數(shù)據(jù)集上基于并行計算的空間co-location模式挖掘算法都優(yōu)于基于全連接的空間co-location模式挖掘算法.基于并行計算挖掘空間co-location模式挖掘算法可繼續(xù)按一分為二的形式擴展，為以后研究大規(guī)模的空間co-location數(shù)據(jù)提供了有效且快速的方法.

[1]HUANGYAN,SHEKHARS,XIONGHUI.Discoveringco-locationpatternsfromspatialdatasets:ageneralapproach[J].IEEETransactionsonKnowledgeandDataEngineering,2004,16(12):1472-1485.

[2] 王麗珍，陳紅梅.空間模式控制理論與方法[M].北京：科學出版社，2004.

[3]XIONGHUI,SHEKHARS,HUANGYAN,etal.Aframeworkfordiscoveringco-locationpatternsindatasetswithextendedspatialobjects[C].Proceedingsofthe12thAnnualACMInternationalConferenceonDataMining(SDM′04),LakeBuenaVista,USA,2004:1-12.

[4]HUANGY,SHEKHARS,XIONGH.Discoveringco-locationpatternsfromspatialdatasets:ageneralapproach[J].IEEETransactionsonKnowledgeandDataEngineering，2004，16(12)：1472-1485.

[5]YOOJS,SHEKHARS.Apartialjoinapproachforminingco-locationpatterns[C].Proc.ofthe12thannualACMinternationalworkshoponGeographicinformationsystems,WashingtonDC,USA,2004:241-249.

[6]HUANGY,ZHANG,LYUP.Canweapplyprojectionbasedfrequentpatternminingparadigmtospatialco-locationmining?[C].Proc.ofthe9thPacific-AsiaConferenceonKnowledgeDiscoveryandDataMining(PAKDD),Hanoi,Vietnam,2005:719-725.

[7]YOOJS,SHEKHARS,CELIKM.Ajoin-lessapproachforco-locationpatternmining:asummaryofresults[C].Proc.ofthe5thIEEEInt.Conf.onDataMining(ICDM2005),Houston,USA,2006：813-816.

[8]WANGL,BAOY,LUJ,etal.Anewjoin-lessapproachforco-locationpatternmining[C].InThe8thIEEEInternationalConferenceonComputerandInformationTechnology,Sydney,Australia,2008：197-202.

[9]WANGLIZHEN,BAOYUZHEN,LUZHONGYU.Efficientdiscoveryofspatialco-locationpatternsusingtheiCPI-tree[J].TheOpenInformationSystemsJournal,2011,3(1):69-80.

[10]WANGLIZHEN,ZHOULIHUA,LUJOAN.Anorder-clique-basedapproachforminingmaximalco-locations[J].InformationSciences,2009,179(19):3370-3382.

[11]WUPINGPING,WANGLIZHEN,ZHOUYONGHENG.Discoveringco-Locationfromspatialdatasetswithfuzzyattributes[J].JournalofFrontiersofComputerScienceandTechnology,2013,7(4)：348-358.

[12]SHEKHARS,CHAWLAS.Spatialdatabases:atour[M].UpperSaddleRiver,USA:PrenticeHall,2003.

Mining Spatial Co-location Patterns Based on Parallel Computing

HE Feng-zhen， JIA Zhi-yang， ZHANG Dan-dan

(Tourism and Culture College，Yunnan University，Lijiang 74100，China)

This article studies spatial co-location pattern mining on the basis of parallel computing. We proposed a novel co-location pattern mining algorithm based on parallel computing. We did lots of experiments on three data sets. Experiments showed that the novel algorithm based on parallel computing can greatly improve the efficiency of spatial data mining and provide a new method to mine mass spatial data in a fast and effective way.

Spatial co-location pattern mining; Data partition; Parallel computing; Parallel algorithms

2014-11-24

國家自然科學基金資助項目(F020508)；云南省教育廳科學研究基金重點資助項目(2012Z143C).

和鳳珍(1988-)，女，云南麗江人，碩士研究生，助教，主要從事空間數(shù)據(jù)挖掘與分析方面研究.

和鳳珍.

TP311.13

A

1007-9793(2015)04-0056-07