董林,舒紅,李莎,2,牛宵

(1.武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,湖北武漢 430079; 2.湖北第二師范學(xué)院機(jī)械與電氣工程系,湖北武漢 430205; 3.山東省國(guó)土測(cè)繪院,山東濟(jì)南 250013)

基于頻繁項(xiàng)集挖掘的LUCC軌跡分析

董林1?,舒紅1,李莎1,2,牛宵3

(1.武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,湖北武漢 430079; 2.湖北第二師范學(xué)院機(jī)械與電氣工程系,湖北武漢 430205; 3.山東省國(guó)土測(cè)繪院,山東濟(jì)南 250013)

針對(duì)多時(shí)相、多類別情況下土地利用/覆被變化軌跡提取難與分析難的問(wèn)題,提出一種基于頻繁項(xiàng)集挖掘的土地利用/覆被變化軌跡分析方法。該方法首先使用FI-Apriori算法對(duì)土地利用/覆被數(shù)據(jù)進(jìn)行頻繁項(xiàng)集挖掘,然后將挖掘結(jié)果用于土地利用/覆被變化軌跡分析。采用美國(guó)地質(zhì)勘探局土地覆被數(shù)據(jù)的實(shí)驗(yàn)表明該方法可行且高效,其結(jié)果信息量大且能以易判讀的形式進(jìn)行表述,有利于實(shí)現(xiàn)變化規(guī)律的分析和總結(jié)。

頻繁項(xiàng)集;土地利用;土地覆被;變化軌跡

1 引 言

土地利用/覆被變化(Land Use and Land Cover Change,LUCC)與全球環(huán)境變化、可持續(xù)發(fā)展緊密相關(guān),是地理空間科學(xué)的研究熱點(diǎn)之一[1]。隨著可用的土地利用/覆被(Land Use and Land Cover,LUC)數(shù)據(jù)的不斷增多,LUCC過(guò)程監(jiān)測(cè)與分析逐漸成為研究的新熱點(diǎn)[2,3],變化軌跡分析等方法得到越來(lái)越多的應(yīng)用[4～9]。但是,已有文獻(xiàn)采用的LUCC軌跡提取方法僅適用于LUC類型數(shù)或者時(shí)相數(shù)較少的情況,難以提取全部變化軌跡;此外,軌跡分析手段也相對(duì)缺乏。為解決這些問(wèn)題,本文利用頻繁項(xiàng)集挖掘?qū)崿F(xiàn)LUCC軌跡提取,并探討了相應(yīng)的軌跡分析與表述方法。

2 LUCC軌跡分析的難點(diǎn)

假設(shè)研究區(qū)域R中LUC共有m類(分別記作c1, c2,…,cm),t1,t2,…,tn(n≥2)時(shí)刻的分類圖已知。記ti時(shí)刻類別為cj的區(qū)域?yàn)閟ij,那么該時(shí)刻的LUC狀態(tài)可以用集合Si={si1,si2,…,sim}來(lái)表示,Si中各元素在空間上的并集等于研究區(qū)域R。

狀態(tài)S1,S2,…,Sn的笛卡爾積D共包含mn個(gè)n元組,記這些元組為p1,p2,…,pl(l=mn)。對(duì)于其中任意元組pk≤s1×1,s2×2,…,sn×n＞(k≤l,x1,x2,…,xn∈{1,…,m}),其中各元素的交集等于LUC類型在t1, t2,…,tn時(shí)刻分別為cx1,cx2,…,cxm的區(qū)域,稱這個(gè)區(qū)域?yàn)閜k的對(duì)應(yīng)區(qū)域。研究區(qū)域在這n個(gè)時(shí)刻的LUCC軌跡可以用D來(lái)表示,D中各元組對(duì)應(yīng)區(qū)域的并集等于研究區(qū)域R。稱D中的一個(gè)元組為一種長(zhǎng)度為n的LUCC軌跡,或稱之為n-軌跡。如果一種軌跡對(duì)應(yīng)區(qū)域不為空,則稱之為實(shí)際存在的軌跡。

LUCC軌跡分析就是要從已知的n個(gè)LUC狀態(tài)中發(fā)現(xiàn)實(shí)際存在的LUCC軌跡,并分析它們?cè)诳臻g和時(shí)間上的分布與變化規(guī)律,為驅(qū)動(dòng)力和效應(yīng)分析提供支撐。

LUCC分析通常分兩步進(jìn)行:首先從LUC序列數(shù)據(jù)中提取出所有可能感興趣的軌跡,然后對(duì)這些軌跡中的規(guī)律進(jìn)行分析及歸納。不過(guò),這兩步都存在待解決的問(wèn)題,當(dāng)LUC種類和時(shí)相數(shù)較多時(shí)尤為突出。

(1)難以完整、高效地提取軌跡

進(jìn)行LUCC軌跡分析需要找出實(shí)際存在的2～n-軌跡。k-軌跡有C(n,k)·mk種(2≤k≤n),因此2～n-軌跡的總數(shù)為C(n,2)·m2+…+C(n,n)·mn。通常n的小幅度增加就會(huì)帶來(lái)軌跡總數(shù)的快速增長(zhǎng),例如m=9的情況下,n=2時(shí)軌跡總共有81種,n=5時(shí)就增長(zhǎng)至99 954種。顯然,在沒(méi)有高可伸縮性算法的情況下對(duì)m和n的大小加以限制是有必要的。

(2)缺乏軌跡表述與分析方法

完成軌跡提取后,還要以簡(jiǎn)明的形式對(duì)其進(jìn)行表述并加以分析,以便得到LUCC在時(shí)間和空間上的規(guī)律。傳統(tǒng)的覆被狀態(tài)統(tǒng)計(jì)圖表、轉(zhuǎn)移矩陣等方法僅適用于較簡(jiǎn)單的1、2-軌跡,已有復(fù)雜軌跡的表述與分析方法仍需進(jìn)一步完善,新方法也有待提出。

此外,已有LUCC軌跡提取方法使用的都是同分辨率的柵格數(shù)據(jù),如何有效利用不同分辨率的柵格數(shù)據(jù)以及矢量數(shù)據(jù)也尚待研究。

3 利用頻繁項(xiàng)集挖掘?qū)崿F(xiàn)LUCC軌跡提取

逐一檢測(cè)所有軌跡是找出實(shí)際存在的LUCC軌跡最簡(jiǎn)單的方法,但在LUC類別數(shù)m和時(shí)刻數(shù)n較大的情況下可行性較差?？梢岳萌缦滦再|(zhì)來(lái)優(yōu)化該過(guò)程:

性質(zhì)1:如果在ti時(shí)刻cj類型面積為a,那么任何包含sij的軌跡對(duì)應(yīng)區(qū)域面積不超過(guò)a。

性質(zhì)2:如果k階軌跡p≤si1j1,si2j2,…,sikjk＞對(duì)應(yīng)區(qū)域面積為a,那么任何同時(shí)包含si1j1,si2j2,…,sikjk的軌跡對(duì)應(yīng)區(qū)域面積不超過(guò)a。

性質(zhì)3:相同時(shí)刻不存在兩種覆被狀態(tài)。

利用以上性質(zhì)就可以減小軌跡提取的工作量,再選擇適宜的算法就可以較高效地找出實(shí)際存在或面積大于指定值的LUCC軌跡。

從數(shù)據(jù)挖掘的視角出發(fā),性質(zhì)1和性質(zhì)2就是關(guān)聯(lián)規(guī)則挖掘中的Apriori性質(zhì)在LUCC軌跡提取中的具體表現(xiàn)形式。如果將一個(gè)時(shí)刻的一種LUC類型看作一項(xiàng)(item),那么一種軌跡就對(duì)應(yīng)于一個(gè)由不同時(shí)刻的項(xiàng)組成的項(xiàng)集。這樣,提取對(duì)應(yīng)區(qū)域面積大于a的軌跡就與挖掘支持度大于a/A的頻繁項(xiàng)集對(duì)應(yīng)起來(lái)(A為研究區(qū)域總面積);挖掘支持度大于0的項(xiàng)集相當(dāng)于提取所有實(shí)際存在的軌跡;因此可以利用頻繁項(xiàng)集挖掘?qū)崿F(xiàn)LUCC軌跡提取。此外,性質(zhì)3可以看作項(xiàng)的約束條件,將其輸入挖掘算法可以進(jìn)一步提高軌跡提取速度。

LUCC軌跡提取所使用的分類圖可能是不同分辨率的柵格圖像,也可能是矢量圖像。本文將分類圖統(tǒng)一轉(zhuǎn)至矢量格式,使用文獻(xiàn)[10]提出的FI-Apriori算法進(jìn)行頻繁項(xiàng)集挖掘(軌跡提取)。該算法可以直接對(duì)矢量多邊形圖層進(jìn)行挖掘來(lái)提取空間頻繁項(xiàng)集,并且具備較好的可伸縮性,能夠?qū)Χ鄷r(shí)相、多類別的覆被數(shù)據(jù)進(jìn)行高效挖掘。此外,該算法還可以將頻繁項(xiàng)集的對(duì)應(yīng)圖層保存下來(lái),有利于軌跡的可視化。

4 根據(jù)頻繁項(xiàng)集分析LUCC軌跡

對(duì)覆被序列數(shù)據(jù)進(jìn)行挖掘可以得到一組對(duì)應(yīng)于LUCC軌跡的頻繁項(xiàng)集,下面說(shuō)明如何將這些項(xiàng)集用于軌跡分析。

(1)1-項(xiàng)集可用于統(tǒng)計(jì)各時(shí)刻的LUC狀態(tài)

一個(gè)1-項(xiàng)集只包含一個(gè)項(xiàng),其支持度等于該項(xiàng)代表的LUC類型在對(duì)應(yīng)時(shí)刻占總面積的比例。例如,項(xiàng)ticj的支持度為0.1表明在ti時(shí)刻cj所占比例為10%。如果已提取出所有實(shí)際存在的1-軌跡(即支持度大于0的1-項(xiàng)集),則可以直接根據(jù)它們統(tǒng)計(jì)在這些時(shí)刻上各LUC類型所占比例。

(2)2-項(xiàng)集可用于生成轉(zhuǎn)移矩陣

一個(gè)2-項(xiàng)集代表一種覆被轉(zhuǎn)移模式。例如,項(xiàng)集{t1c1,t2c2}對(duì)應(yīng)于t1時(shí)刻LUC類型為c1并且在t2時(shí)刻類別為c2的區(qū)域,其支持度等于研究區(qū)域中發(fā)生了這種轉(zhuǎn)變的區(qū)域所占比例。因此,根據(jù)2-項(xiàng)集可以計(jì)算出任意年份之間的LUC類型轉(zhuǎn)移矩陣。

(3)2-項(xiàng)集可用于繪制轉(zhuǎn)移模式圖

狀態(tài)統(tǒng)計(jì)和轉(zhuǎn)移矩陣是傳統(tǒng)的LUCC分析方法,它們的缺點(diǎn)在于不夠直觀?？梢岳?-項(xiàng)集繪制既能體現(xiàn)各時(shí)刻的覆被狀態(tài),也能展示出覆被轉(zhuǎn)移的類別及強(qiáng)度的轉(zhuǎn)移模式圖。方法為:為每一項(xiàng)繪制一個(gè)結(jié)點(diǎn),對(duì)于任意(或時(shí)刻相鄰的)兩項(xiàng)A、B用正比于項(xiàng)集{A,B}支持度的線段連結(jié)其對(duì)應(yīng)結(jié)點(diǎn)。

(4)項(xiàng)集可用于軌跡的表述及可視化

項(xiàng)集是LUCC軌跡的一種表述形式,其內(nèi)容是組成該軌跡的LUC狀態(tài)序列,其支持度是該軌跡對(duì)應(yīng)區(qū)域所占比例。

可以利用頻繁項(xiàng)集對(duì)應(yīng)圖層實(shí)現(xiàn)軌跡的空間可視化,以便直觀地展示軌跡的位置與面積等信息、揭示其中的空間規(guī)律。

5 實(shí) 驗(yàn)

5.1 數(shù)據(jù)準(zhǔn)備

實(shí)驗(yàn)所使用的數(shù)據(jù)來(lái)自美國(guó)地質(zhì)勘探局(USGS)土地覆被變化趨勢(shì)項(xiàng)目。該項(xiàng)目對(duì)美國(guó)威拉米特谷生態(tài)區(qū)(Willamette Valley Ecoregion)內(nèi)32個(gè)樣本區(qū)1972年～2000年的土地覆被狀況進(jìn)行了跟蹤調(diào)查。選取編號(hào)為samp03_0003的樣本區(qū)作為研究區(qū)域(地理位置如圖1所示),對(duì)該區(qū)域1972年、1979年、1985年、1992年和2000年的覆被分類圖進(jìn)行挖掘與分析實(shí)驗(yàn)(實(shí)驗(yàn)數(shù)據(jù)、程序等可以在作者網(wǎng)站http://www.c2001.net/downloads.html下載)。

圖1 研究區(qū)域地理位置

研究區(qū)域的覆被分類圖均為柵格格式,分辨率為60 m,各種像素值代表的覆被類型及出現(xiàn)情況如表1所示。

像素值與覆被類型 表1

根據(jù)前文的計(jì)算,當(dāng)m=9、n=5時(shí)LUCC軌跡共有99 954種,本文采用FI-Apriori算法僅對(duì)958個(gè)候選項(xiàng)集進(jìn)行檢驗(yàn)就提取出了所有實(shí)際存在的LUCC軌跡(該過(guò)程中依據(jù)限制條件排除了254個(gè)2階軌跡)。挖掘共得到510個(gè)頻繁項(xiàng)集,如圖2所示。

FI-Apriori算法輸入為矢量多邊形圖層,故對(duì)覆被數(shù)據(jù)進(jìn)行了分割與矢量化。1972年的分類圖中共有7種像素值,經(jīng)處理得到7個(gè)矢量多邊形圖層,每個(gè)對(duì)應(yīng)于一種覆被類型。其余年份的數(shù)據(jù)處理方式類似,最終得到38個(gè)多邊形圖層,以年份加覆被類型縮寫(xiě)命名(例如1972WT)。

5.2 軌跡提取與分析

數(shù)據(jù)準(zhǔn)備完畢后,使用FI-Apriori算法進(jìn)行了LUCC軌跡(即頻繁項(xiàng)集)提取。根據(jù)性質(zhì)3故向算法添加了“任何項(xiàng)集不得包含對(duì)應(yīng)于同一時(shí)間不同土地覆被類型的兩項(xiàng)”這一約束條件。支持度和置信度閾值設(shè)定為0.000003(略小于原圖中一個(gè)像素所占比例),因此最細(xì)微的變化也能被檢測(cè)出來(lái)。

圖2 挖掘得到的頻繁項(xiàng)集

挖掘結(jié)果中頻繁1-項(xiàng)集共有38個(gè),2-項(xiàng)集140個(gè),3-項(xiàng)集189個(gè),4-項(xiàng)集116個(gè),5-項(xiàng)集有27個(gè)。下面利用這些頻繁項(xiàng)集進(jìn)行LUCC軌跡分析。

(1)根據(jù)1-項(xiàng)集的支持度可以計(jì)算出5個(gè)年份中不同覆被類型所占比例及對(duì)應(yīng)的面積,如表2所示。

1972年～2000年各類覆被比例及面積 表2

根據(jù)表2可以得知研究區(qū)域覆被類型以AG、WL、WT、DU和FW為主,這幾種類型面積總和始終大于研究區(qū)域總面積的77%。

(2)根據(jù)頻繁2-項(xiàng)集生成了1972年～2000年的轉(zhuǎn)移矩陣(如表3所示)。

1972年～2000年土地覆被類型轉(zhuǎn)移矩陣(單位/km2) 表3

續(xù)表3

由表3可知1972年～2000年最主要的覆被變化就是2.57 km2的AG轉(zhuǎn)入DU以及MD和GS的出現(xiàn)。其余大部分區(qū)域覆被類型維持不變。

(3)利用時(shí)間上相鄰接的頻繁2-項(xiàng)集(共49個(gè))繪制了覆被轉(zhuǎn)移模式圖,如圖3所示。

圖3 相鄰時(shí)間的覆被轉(zhuǎn)移模式

由圖3可知,從1972年～2000年研究區(qū)域覆被始終是以AG、WL、WT、DU和FW為主,1985年～1992年間開(kāi)始出現(xiàn)MD,1992年～2000年間開(kāi)始出現(xiàn)GS。各種覆被類型中,WL、FW、NB只有轉(zhuǎn)出沒(méi)有轉(zhuǎn)入, WT、DU和GS只有轉(zhuǎn)入沒(méi)有轉(zhuǎn)出,其余3類既有轉(zhuǎn)入也有轉(zhuǎn)出。實(shí)際存在的覆被轉(zhuǎn)移模式共12種(不考慮時(shí)段的不同),其中WL和FW到AG、AG和FW到DU、AG到WT的轉(zhuǎn)化最頻繁,表明AG、DU以及WT的擴(kuò)張是該區(qū)域最常見(jiàn)的覆被變化。

利用所有的頻繁2-項(xiàng)集(共140個(gè))繪制了全部轉(zhuǎn)移模式,如圖4所示。

圖4 全部覆被轉(zhuǎn)移模式

相對(duì)于圖3,圖4可以揭示更多的變化細(xì)節(jié)信息。例如根據(jù)圖3僅能得知2000年的AG全部由1992年的AG轉(zhuǎn)入,根據(jù)圖4中的橙色連線可以發(fā)現(xiàn)2000年AG中的部分區(qū)域曾經(jīng)是WL或FW。

(4)利用項(xiàng)集和它們的對(duì)應(yīng)圖層進(jìn)行了軌跡表述與可視化,下面以5-項(xiàng)集為例進(jìn)行說(shuō)明。挖掘共得到27個(gè)頻繁5-項(xiàng)集,對(duì)應(yīng)于研究區(qū)域在1972年～2000年間的27種5-軌跡。其中,始終未發(fā)生改變的有7種,占總面積的96%左右;其余的是發(fā)生過(guò)改變的模式,有20種,占總面積的4%左右。這些軌跡中支持度最高的10種如表4所示。

挖掘得到的5-軌跡 表4

由表4可知,1972年～2000年間AG、WL、WT、DU、FW、MN、NB這7種覆被類型對(duì)應(yīng)區(qū)域始終未發(fā)生大面積變化;在此期間最主要的變化是AG向DU的三次轉(zhuǎn)變,分別發(fā)生于1979年～1985年、1985年～1992年和1992年～2000年間,相應(yīng)軌跡的支持度分別為0.584%,1.276%和0.645%。

利用{1972AG}、{1972AG,1979AG}等5個(gè)項(xiàng)集對(duì)應(yīng)的圖層實(shí)現(xiàn)了軌跡＜1972AG,1979AG,1985AG, 1992AG,2000DU＞的可視化,如圖5所示。

其中,圖5(a)對(duì)應(yīng)于項(xiàng)集{1972AG},圖5(b)對(duì)應(yīng)于{1972AG,1979AG},圖5(c)對(duì)應(yīng)于{1972AG,1979AG, 1985AG},圖5(d)對(duì)應(yīng)于{1972AG,1979AG,1985AG, 1992AG},圖5(e)對(duì)應(yīng)于{1972AG,1979AG,1985AG, 1992AG,2000UD},圖5(f)是圖5(a)到圖5(e)的疊加。

由圖5可知,1972年覆被類型為AG的區(qū)域在不斷地轉(zhuǎn)為其他類型(例如DU),這種變化主要發(fā)生于研究區(qū)域的西北部,通常是與其他覆被類型鄰接的小塊區(qū)域。

圖5 LUCC軌跡的可視化

6 結(jié) 語(yǔ)

本文對(duì)多時(shí)相、多類別LUCC軌跡提取與分析方法進(jìn)行了研究,將軌跡提取問(wèn)題轉(zhuǎn)化為頻繁項(xiàng)集挖掘問(wèn)題,并討論了利用頻繁項(xiàng)集進(jìn)行軌跡分析的方法。不過(guò),本文還未考慮相似軌跡合并問(wèn)題,所使用的結(jié)果表述及分析方法也有待進(jìn)一步豐富和完善。此外,軌跡的增量式提取也是未來(lái)需要研究的內(nèi)容。

[1] 李秀彬.全球環(huán)境變化研究的核心領(lǐng)域——土地利用/土地覆被變化的國(guó)際研究動(dòng)向[J].地理學(xué)報(bào),1996,51 (6):553～558.

[2] 韋素瓊,陳健飛.土地利用變化區(qū)域?qū)Ρ妊芯俊蚤}臺(tái)為例[M].北京:科學(xué)出版社,2006.

[3] 羅格平,周成虎,陳曦.干旱區(qū)綠洲土地利用與覆被變化過(guò)程[J].地理學(xué)報(bào),2003,58(1):63～72.

[4] Lambin E F,Strahler A H.Change-vector Analysis in Multitemporal Space:A Tool to Detect and Categorize Land-cover Change Processes Using High Temporalresolution Satellite Data [J].Remote Sensing of the Environment,1994,48:231～244.

[5] Petit C,Scudder T,Lambin E.Quantifying Processes of Landcover Change by Remote Sensing:Resettlement and Rapid Land -cover Changes in South-eastern Zambia[J].International Journal of Remote Sensing,2001,22(17):3435～3456.

[6] Zhou Q,Li B,Kurban A.Trajectory Analysis of Land Cover Change in Arid Environment of China[J].International Journal of Remote Sensing.29(4):1093～1107.

[7] Zhou Q,Li B,Zhou C.Studying spatio-temporal pattern of landuse change in arid environment of China.Li Z,Zhou Q, Kainz W.Advances in Spatial Analysis and Decision Making [C].Lisse,Swets&Zeitlinger,2004:1～6.

[8] Wang D,Gong J,Zhang L,Song Y.Spatiotemporal analysis of land use/cover change patterns in the new coastal district of Tianjin,China[C].The 18th International Conference on Geoinformatics,Beijing.Piscataway:IEEE Press,2010:1～6.

[9] Wang D,Gong J,Chen L,Zhang L,Song L,Yue Y.Spatiotemporal pattern analysis of land use/cover change trajectories in Xihe Watershed[J].International Journal of Applied Earth Observation and Geoinformation,2012,14(1):12～21.

[10] 董林,舒紅,牛宵.利用疊置分析和面積計(jì)算實(shí)現(xiàn)空間關(guān)聯(lián)規(guī)則挖掘[J].武漢大學(xué)學(xué)報(bào)·信息科學(xué)版,2013, 38(1):95～99.

Frequent Itemset Mining Based LUCC Trajectory Analysis

Dong Lin1,Shu Hong1,Li Sha1,2,Niu Xiao3
(1.State Key Lab for Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,Wuhan 430079,China; 2.Department of Mechanical and Electrical Engineering,Hubei University of Education,Wuhan 430205,China; 3.Land Surveying and Mapping Institute of Shandong Province,Jinan 250013,China)

A novel land use and land cover change trajectory extract and analysis method based on frequent itemsets mining is proposed in this paper.This method use FI-Apriori,a spatial data mining algorithm designed by us,to mine spatial frequent itemsets from multi-temporal and multi-type land use and land cover data efficiently;with these frequent itemsets,area statistics,transfer patterns and change trajectories of land use and land cover types can be easily fetched and analyzed.Experiment using data fetched by USGS shows this method is valid and efficient in land use and land cover trajectory analysis;results of the analysis contain much information,and can be expressed in highly interpretable forms.

frequent itemset;land use;land cover;change trajectory

1672-8262(2014)06-5-05

P237

A

2014—06—01

董林(1984—),男,博士研究生,主要研究方向?yàn)榭臻g數(shù)據(jù)挖掘。

國(guó)家自然科學(xué)基金項(xiàng)目(41171313)