基于频繁项集挖掘的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)