基于頻繁項集挖掘的LUCC軌跡分析

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

(1.武漢大學測繪遙感信息工程國家重點實驗室,湖北武漢 430079; 2.湖北第二師范學院機械與電氣工程系,湖北武漢 430205; 3.山東省國土測繪院,山東濟南 250013)

基于頻繁項集挖掘的LUCC軌跡分析

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

(1.武漢大學測繪遙感信息工程國家重點實驗室,湖北武漢 430079; 2.湖北第二師范學院機械與電氣工程系,湖北武漢 430205; 3.山東省國土測繪院,山東濟南 250013)

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

頻繁項集;土地利用;土地覆被;變化軌跡

1 引 言

土地利用/覆被變化(Land Use and Land Cover Change,LUCC)與全球環境變化、可持續發展緊密相關,是地理空間科學的研究熱點之一[1]。隨著可用的土地利用/覆被(Land Use and Land Cover,LUC)數據的不斷增多,LUCC過程監測與分析逐漸成為研究的新熱點[2,3],變化軌跡分析等方法得到越來越多的應用[4～9]。但是,已有文獻采用的LUCC軌跡提取方法僅適用于LUC類型數或者時相數較少的情況,難以提取全部變化軌跡;此外,軌跡分析手段也相對缺乏。為解決這些問題,本文利用頻繁項集挖掘實現LUCC軌跡提取,并探討了相應的軌跡分析與表述方法。

2 LUCC軌跡分析的難點

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

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

LUCC軌跡分析就是要從已知的n個LUC狀態中發現實際存在的LUCC軌跡,并分析它們在空間和時間上的分布與變化規律,為驅動力和效應分析提供支撐。

LUCC分析通常分兩步進行:首先從LUC序列數據中提取出所有可能感興趣的軌跡,然后對這些軌跡中的規律進行分析及歸納。不過,這兩步都存在待解決的問題,當LUC種類和時相數較多時尤為突出。

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

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

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

完成軌跡提取后,還要以簡明的形式對其進行表述并加以分析,以便得到LUCC在時間和空間上的規律。傳統的覆被狀態統計圖表、轉移矩陣等方法僅適用于較簡單的1、2-軌跡,已有復雜軌跡的表述與分析方法仍需進一步完善,新方法也有待提出。

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

3 利用頻繁項集挖掘實現LUCC軌跡提取

逐一檢測所有軌跡是找出實際存在的LUCC軌跡最簡單的方法,但在LUC類別數m和時刻數n較大的情況下可行性較差。可以利用如下性質來優化該過程:

性質1:如果在ti時刻cj類型面積為a,那么任何包含sij的軌跡對應區域面積不超過a。

性質2:如果k階軌跡p≤si1j1,si2j2,…,sikjk＞對應區域面積為a,那么任何同時包含si1j1,si2j2,…,sikjk的軌跡對應區域面積不超過a。

性質3:相同時刻不存在兩種覆被狀態。

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

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

LUCC軌跡提取所使用的分類圖可能是不同分辨率的柵格圖像,也可能是矢量圖像。本文將分類圖統一轉至矢量格式,使用文獻[10]提出的FI-Apriori算法進行頻繁項集挖掘(軌跡提取)。該算法可以直接對矢量多邊形圖層進行挖掘來提取空間頻繁項集,并且具備較好的可伸縮性,能夠對多時相、多類別的覆被數據進行高效挖掘。此外,該算法還可以將頻繁項集的對應圖層保存下來,有利于軌跡的可視化。

4 根據頻繁項集分析LUCC軌跡

對覆被序列數據進行挖掘可以得到一組對應于LUCC軌跡的頻繁項集,下面說明如何將這些項集用于軌跡分析。

(1)1-項集可用于統計各時刻的LUC狀態

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

(2)2-項集可用于生成轉移矩陣

一個2-項集代表一種覆被轉移模式。例如,項集{t1c1,t2c2}對應于t1時刻LUC類型為c1并且在t2時刻類別為c2的區域,其支持度等于研究區域中發生了這種轉變的區域所占比例。因此,根據2-項集可以計算出任意年份之間的LUC類型轉移矩陣。

(3)2-項集可用于繪制轉移模式圖

狀態統計和轉移矩陣是傳統的LUCC分析方法,它們的缺點在于不夠直觀。可以利用2-項集繪制既能體現各時刻的覆被狀態,也能展示出覆被轉移的類別及強度的轉移模式圖。方法為:為每一項繪制一個結點,對于任意(或時刻相鄰的)兩項A、B用正比于項集{A,B}支持度的線段連結其對應結點。

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

項集是LUCC軌跡的一種表述形式,其內容是組成該軌跡的LUC狀態序列,其支持度是該軌跡對應區域所占比例。

可以利用頻繁項集對應圖層實現軌跡的空間可視化,以便直觀地展示軌跡的位置與面積等信息、揭示其中的空間規律。

5 實 驗

5.1 數據準備

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

圖1 研究區域地理位置

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

像素值與覆被類型 表1

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

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

5.2 軌跡提取與分析

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

圖2 挖掘得到的頻繁項集

挖掘結果中頻繁1-項集共有38個,2-項集140個,3-項集189個,4-項集116個,5-項集有27個。下面利用這些頻繁項集進行LUCC軌跡分析。

(1)根據1-項集的支持度可以計算出5個年份中不同覆被類型所占比例及對應的面積,如表2所示。

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

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

(2)根據頻繁2-項集生成了1972年～2000年的轉移矩陣(如表3所示)。

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

續表3

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

(3)利用時間上相鄰接的頻繁2-項集(共49個)繪制了覆被轉移模式圖,如圖3所示。

圖3 相鄰時間的覆被轉移模式

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

利用所有的頻繁2-項集(共140個)繪制了全部轉移模式,如圖4所示。

圖4 全部覆被轉移模式

相對于圖3,圖4可以揭示更多的變化細節信息。例如根據圖3僅能得知2000年的AG全部由1992年的AG轉入,根據圖4中的橙色連線可以發現2000年AG中的部分區域曾經是WL或FW。

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

挖掘得到的5-軌跡 表4

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

利用{1972AG}、{1972AG,1979AG}等5個項集對應的圖層實現了軌跡＜1972AG,1979AG,1985AG, 1992AG,2000DU＞的可視化,如圖5所示。

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

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

圖5 LUCC軌跡的可視化

6 結 語

本文對多時相、多類別LUCC軌跡提取與分析方法進行了研究,將軌跡提取問題轉化為頻繁項集挖掘問題,并討論了利用頻繁項集進行軌跡分析的方法。不過,本文還未考慮相似軌跡合并問題,所使用的結果表述及分析方法也有待進一步豐富和完善。此外,軌跡的增量式提取也是未來需要研究的內容。

[1] 李秀彬.全球環境變化研究的核心領域——土地利用/土地覆被變化的國際研究動向[J].地理學報,1996,51 (6):553～558.

[2] 韋素瓊,陳健飛.土地利用變化區域對比研究——以閩臺為例[M].北京:科學出版社,2006.

[3] 羅格平,周成虎,陳曦.干旱區綠洲土地利用與覆被變化過程[J].地理學報,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].武漢大學學報·信息科學版,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—),男,博士研究生,主要研究方向為空間數據挖掘。

國家自然科學基金項目(41171313)