________________________________
空间co-location 模式挖掘算法介绍及应用1
包玉珍 王丽珍 周丽华
（云南大学信息学院计算机科学与工程系 昆明650091）
摘 要 随着空间数据库的快速增长和广泛使用，如何从空间数据中自动地发现空间知识变得越来越
重要。空间co-location 模式代表了在地理空间中频繁相关的空间对象。当前挖掘空间co-location 模式所遇到的困难在于，空间对象的实例分布在连续的空间中并拥有复杂的空间关系,大部分的计算时间需要用来生成co-location 模式的表实例。本文分析了co-location 模式挖掘的实质，以及近年来提出的co-location 模式挖掘的全连接算法和无连接算法，并对这两种算法在性能上加以比较。在此基础上，结合三江并流国家基金项目，用这两种算法挖掘出了共生植被极其分布情况，为生物学家的科学研究提供了有利的帮助。
关键词 空间数据挖掘, 空间co-location 模式，全连接算法， 无连接算法
Abstract With the increase and using of spatial databases, how to gain the knowledge automatically is
getting more and more important. Spatial co-location patterns represent the subsets of features whose instances are frequently located together in geographic space. Co-location pattern discovery presents challenges since the instances of spatial features are embedded in a continuous space and share a variety of spatial relationships. A large fraction of the computation time is devoted to identifying the instances of co-location patterns. In this paper, we analyzed the co-location mining problems and discussed two algorithms of mining co-location patterns. They are full-join algorithm and join-less algorithm. We used them in a plant distributing dataset of “Three Parallel Rivers” region to mining symbiotic plant species. It shows that the mining results are interested by botanist.
Index Terms spatial data mining, spatial co-location patterns, full-join approach, join-less approach
1 引言
空间数据挖掘[3] [4]是从空间数据库中发现潜藏的、有趣模式的过程。一个空间co-location 模式是一组空间对象的集合，它们的实例在空间中频繁地相关联。挖掘空间co-location 模式是很有意义的一项工作，例如，植物学家根据共生植被的分布，发现“半湿润常绿阔叶林”生长的地方80%有“兰类”植物生长。移动服务营运商根据不同需求用户的分布，搭配相应的服务套餐，增加收入；广告运营商根据特定不同人群的聚集地段，投放相应广告。空间co-location 模式还可被
应用到地球科学、公共卫生、公共交通等方
面。在本文中，我们就是把空间co-location
模式应用到三江并流国家基金项目中，来挖
掘出共生植被的分布情况，为生物科学研究
提供帮助。 1.1 co-location 模式基本概念 设},...,,{21l f f f F =是一个空间对象集。考虑数量为l 的空间数据集合],1[,l i SD i ∈，
i SD 中包含了空间对象i f 的所有的、且仅限于i f 的全部实例。如图1所示，图中对象共
包含3个空间对象A 、B 、C 。空间对象A 的数据集包括4个实例，分别是A.1、A.2、A.3，A4， A.1代表了空间对象A 的第1个实例。 设R 是一个给定的空间邻居关系（例如，距离小于1.5米）。一个co-location 模式
是一组空间对象的集合C ，其中F C ?，C
的实例集合S I ?并且实例间满足空间关
系R 。co-location 模式中空间对象的个数
称为此co-location 模式的阶。
一个满足空间关系R 的实例集合I 是co-location C 的一个行实例，I 中必须包含了所有C 中的空间对象，并且I 里面没有
图1 空间对象和实例
任何子集能满足以上条件。例如图1中，假
设有{A.3,B.3,C.3}是co-location{A,B,C}的一个行实例。那么{A.1,A.3,B.3,C.1}就不是co-location{A,B,C}的一个行实例，因为在其中有子集{A.3,B.3,C.3}已经包含了co-location{A,B,C}的所有空间对象。co-location C 的所有行实例的集合称作co-location C 的表实例（记作
()c ance table_inst ）
。 co-location 模式中的支持度称为参与度PI(participation index )。它的取值是co-location C 的所有空间对象的PR 值中的最小值，PR 指的是参与比率（participation ratio ），它是i f 的实例在co-location C 的所有实例中不重复出现的个数与i f 总实例个数的比率。计算公式如下：
()i f C PR ,=
()()
()
i f ance table_inst C ance table_inst i f π。
其中π是关系的投影操作，如
})({instance (1C table C -π是共存模式C 的表实例在i f 上的投影。仍然以图1为例，对象A 有4个实例，对象B 有5个实例，对象C 有3个实例。假设co-location C ={}C A,，co-location C 的表实例为
{(A.1,C.1),(A.3.C.1),(A.4,C.1),(A.2,C .2)}。因为在A 的4个实例中有A.1,A.2,A.3和A.4出现表实例中，则()A ,C PR =4/4。类似的，()C ,C PR =2/3。最终
()C PR =()()()3/2,,A ,min =C C PR C PR 。
当()≥C PR min_prev 时，仍然沿用频繁项集挖掘时的称呼，称co-location C 是频繁的。
1.2空间co-location 模式挖掘的相关方法
空间co-location 模式的挖掘算法大致归结为两种：分别是基于空间统计的途径和基于数据挖掘的途径。
基于空间统计的途径使用能表现空间相关性的度量来刻画空间对象间的关系，这些度量包括结合蒙特卡罗法模拟法的cross-K 方程[6]，平均最近邻域距离，空间回归模型[7]等。
基于数据挖掘的途径可以划分为基于聚集的图层覆盖方法和基于关联规则的方法。在基于聚类的图覆盖方法中
[9，10]
，每个
空间对象被作为一层，每层上的点被聚类到一个区域中。基于关联规则的方法又可以进一步划分为基于事务的挖掘方法和基于距离的挖掘方法。基于事务的挖掘着重在于定义跨越空间的事务，所以常使用类似apriori [3]
的算法来进行挖掘。在基于距离的方法中，每个空间对象集的实例数，被用来作为兴趣度的定义。这个方法最早由S. Shekhar & Y. Huang [4]和Morimoto [12]提出，相关的co-location 模式挖掘算法可以分为三类。它们分别是：基于完全连接的co-location 模式挖掘算法[4]，基于划分连接的co-location 模式挖掘算法[5]和无连接的co-location 模式挖掘算法[8]。
2.2 对空间co-location 模式挖掘的全连接及
无连接算法的介绍
在众多的空间co-location 模式挖掘算法中，我们选择了基于完全连接的co-location 模式挖掘算法和无连接的co-location 模式挖掘算法，来实现对三江并流地区的植物共生模式的挖掘。
在S. Shekhar & Y . Huang 提出的算法中[4]，寻找频繁空间co-location 模式主要是基于表实例连接的计算过程。算法首先计算出空间实例间的关系，求出第2阶的所有co-location 模式的表实例，然后相互连接表实例生成第3阶co-location 模式。即第k+1阶co-location 模式是由第k 阶co-location 模式的实例相互连接生成。
如图2描述了连接生成co-location{A,B,C}的过程。首先直接生成第2阶的co-location 模式{A,B}、{A,C}、{B,C}及其实例。然后co-location{A,B}的行实例和co-location{A,C}的行实例按照第1个空间对象A 连接，最后检查第2、3项B ，C 的
图2 基于全连接的co-location 模式生成
邻近关系。这种类似apriori的算法能够产生完整的和正确的co-location模式集合，可是在连接高阶的co-location实例集时计算开销很大，因为伴随着co-location模式长度的增加，每个co-location模式的实例长度也增长，虽然相对实例的行数会减少，但连接计算依旧很费时。
文献[8]中使用了一种不需要连接实例来计算co-location模式的生成算法，它实际上先把实例间的关系存储到一个压缩的星形关系表中，然后通过扫描星形关系来生成新co-location模式的一个可能的实例，最后对这个可能的实例进行三次过滤操作而得到实际的表实例。随着co-location长度的增大扫描星形关系的开销也增大。
如图3是图1中的实例使用非连接co-location模式挖掘算法的计算过程。首先扫描星型关系得到所有2阶co-location 模式的实例（图中PHASE II部分），然后再一次扫描星型关系得到3阶co-location模式{A,B,C}的一个可能实例{A.1,B.1,C.1}{A.2,B.4,C.2},{A.3,B.3,C .1}。这里计算表实例的PI值进行第一次过滤，第二次过滤是检查B，C部分的的邻近关系并删除掉不符合邻近关系的行实例，最后再计算一次PI值进行第三次过滤。
3算法及具体实现
3.1算法的具体描述
输入：
（a）E={空间对象、实例id、空间位置}，E代表着空间对象的可选范围；
（b）ET={K个布尔型空间对象的集合}；
（c）空间关系R；
（d）最小支持度阈值（min_prev）
输出：
一组co-location模式的集合，每个
co-location模式的PI值≥min_prev。
限制条件：
R是有对称对象的空间关系，在本论文
中为方便起见，规定R为实例间的欧几里德
距离，距离阈值为d。
变量：
K：co-location的阶；
C k:k阶侯选co-location集；
T k: k阶co-location的表实例；
P k: k阶频繁co-location集；
{}
n
f
f
T
T
T,...,
1
=是星型邻居集；
SI k：k阶侯选co-location集的星型实例；
CI k：k阶侯选co-location集的团实
例；
Distance:存放空间实例间距离小于
给定距离的实例的集合；
1、基于全连接co-location模式挖掘
算法
1）生成distance;
2）生成频繁1项集；
3）k=1
4）while (not empty P k){
5）C k+1=生成侯选co-location模式(P k,k)；6）T k+1=生成表实例（min_prev，C k+1，T k，R）；7）P k+1 =生成频繁k+1项集（min_prev，C k+1，T k+1）；
8） k=k+1；
9） }
10）返回（P1，P2，…，P k）;
这些步骤中，值得注意的是步骤6，即
具体怎么来生成表实例。这里有两种方法，
一种是连接的方法，其计算方法可用如下查
询来描述：
Forall co-location c ∈ C k+1
Insert into Tc /* Tc is the table
instance of co-location c */ 图3 无连接算法的生成过程
Select p. instance1 ,
instance2,… , q.instance k
From c.table_instance_id1 p,
c.table_instance_id2 q
Where p.instance1=q.instance1, …, p.instance k-1=q.instance k-1,
(p.instance k，q.instance k) ∈R
end
另一种是几何的方法，即对k项和1项频繁co-location表实例，进行基于邻居关系的空间连接。在具体实现中，具体在实现的时候，生成侯选2项集的表实例时，可以从前面计算R时生成的距离集合distance 中直接求出。而2项集之后的，通过上面的连接方法来生成。
2、非连接的co-location模式挖掘算法1) 生成distance;
2）生成频繁1项集；
3）TD=产生星型邻居集（F，S，R）；
4) K=2；
5) while (not empty P k-1 ){
6) C k=生成侯选co-location模式(P k-1)；
7) For t∈T { SI k =筛选出星型实例（C k，t）； }
8) If (k=2) {CI k = SI k }
9) Else{ C k=得到初步频繁侯选集（C k，SI k，min_prev）;
10) CI k =筛选出团实例(C k，SI k);
11) }
12) P k =生成频繁k+1项集（C k，CI k，
min_prev）；
13) k=k+1；
14) }
15) 返回（P1，P2，…，P k）
无连接算法与全连接算法的主要不同之处在于表实例的生成方法上，在无连接算法中，先是生成以每个实例为中心实例的邻居集，然后按照侯选模式来生成表实例时，就直接从邻居集中查找，但因为找到的实际上并不是一个co-location模式，所以之后还要进行实例的筛选。在具体算法中，怎样存储邻居集，怎样从存储邻居集中快速组合出实例，怎样进行实例的筛选都会对算法产生很大的影响。此处我们具体实现时，是通过对distance表进行一次扫描，将每个中心实例对应的每类对象分别存储，以便与生成实例时的组合。
3.2 数据结构
在本算法中，我们的数据结构如表1所
4、实验及评价
此处是算法在模拟和实际数据上的试验结果，模拟数据是用类似与[4]中的方法合成的数据。空间对象的实例分布在100*100的空间范围内；用到的真实数据是“三江并流”区域珍惜植物数据。这个数据集中有29种珍惜植物数据，位于“三江并流”区域内，共320个分布数据。在模拟和实际数据上，我们用全连接和无连接算法，得到的结果是一样的。下面是所有实验用的电脑配置：
－硬件配置：Pentium(R) 4 CPU 2.00GHZ,512MB 内存
－操作系统：Windows XP
表1 数据结构表
－输入输出数据：数据库表格式 4.1 算法性能的比较及评价
1、全连接算法的时间复杂度，随着侯选实例的增多，时间复杂度会急剧增加。这可从两个参数的变化上来观察。一个是距离阈值d ，另一个是最小支持度。下面的数据是在100*100的空间上随机生成的233个实例，共有10个对象，每个对象平均生成20个实例。下面的图4是最小支持度为0.4时，距离从5变到25的情况。图5是最小支持度从0.1到0.7的情况，可以看出随着距离的增大或最小支持度的减小，侯选实例不断增多，致使时间复杂度急剧增大。
2、二项侯选模式的实例，主要由两个实例间的距离对来产生。而求两个实例间的距离对，是个比较耗时的过程。采用什么样的算法，减少生成距离对的时间，会降低整个算法的时间复杂度。100*100的空间中，10个对象，实例数分别为233，508，1051，2441的时候，d 取40时，
如图6可以看到随着实例的增长，计算距离的时间是急剧增长的。
3、生成侯选2项集的表实例时，怎样从距离对中抽取出相应的表实例，比较节省时间？在本文中涉及到两种方法。方法一是先生成距离对的集合，再生成模式的侯选2项集，之后从距离对的集合中，抽取各种实例。方法二是生成距离对的集合，将其按空间对象排序，之后遍历一次距离对的集合，抽取出不同模式及其实例。如图7，从实验中可以看出，方法二可以降低时间复杂度为常数。
4、下面的实验是全连接算法和无连接算法的比较。此步实验中，我们以真实数据为例，即“三江并流”区域珍惜植物数据。实验结果如下。图8是最小支持度取0.4，距离从2000米到5000米的情况。可以看到时间复杂度基本一致。图9是距离取5000时，最小支持度从0.1到0.5情况。可以看到支持度较大时，这两个算法的时间复杂度相差
不大，但支持度较小的时候，无连接算法不如全连接算法。
图4 运行时间随支持度的变化
图5运行时间随距离的变化
图7从距离对中抽取表实例的两
图9全连接算法和无连接算法按最小支持度进行比较
5、从全连接算法和无连接算法的比较中，可以看到，虽然在产生侯选模式的实例集时，没有用连接来产生，但从星型邻居集中生成实例、筛选粗糙侯选集的实例集，使粗糙侯选模式中每个对象对应的实例间，都满足距离关系，仍是很费时的一个操作。在本实验中，由于这两部分比较耗时，并没能显现出无连接算法的优势，因此可在怎样提
高这两部分的效率上，还要再进行研究。如图10所示，此图是取距离为5000，最小支持度为0.1时，侯选3项集到频繁3项集时，5个步骤运行时间的比较。图中x轴中的1表示的是用Apriori性质对侯选3项集减枝所花费的时间；2表示的是获得实例所花费的时间；3只表示无连接算法中，对粗糙候选集c3进行减枝花费的时间，这个步骤在全连接中没有；4只表示无连接算法中，除了第一个对象外的其它k-1个对象是否互相之间满足距离的关系。5是计算支持度，得到4项频繁集。从这个图中可以看出，如何从星型邻居集中筛选侯选实例，如何检验除了第一个对象外的其它k-1个对象是否互相之间满足距离的关系，这两个算法对整个无
4.2在三江并流项目中的应用及对挖掘结果的评价
云南省“三江并流”区域是世界生物多样性最丰富的地区之一，位居17个中国生物多样性保护“关键地区”的第一位；而且，“三江并流”植物数据类型复杂、与空间紧密相关，在空间数据仓库及空间数据挖掘技术的研究中具有很强的代表性。因此，借助计算机信息技术研究“三江并流”代表性植物之间的关系，其研究成果具有广泛的应用前景和意义，同时，还可以促进云南省、西部乃至国家的生态环境保护及可持续发展。在本文中，我们用co-location的全连接算法和无连接算法，在三江并流数据的真实数据集中，挖掘出了一些有意义的植被信息。当距离阈值区3500，最小支持度取0.1时，挖掘到的二项频繁模式有133项，而得到的最大频繁模式如下。
表2 五项最大频繁模式
表3 三项最大频繁模式
以上找到的结果，对植物学家是非常有用的。首先，植物学家可以尽量找一个地理空间，它能在较小的范围内，包含更多的植被，因为这样就可从时间、人力、物力上节省很多无用的消耗，投入更少的成本来进行植物的研究。其次，对于一个找到的co-location频繁模式，它的实例分布是不同的，那么植物学家也可以在具体的实例上，找那种海拔相对较低、人类更容易出入的较好环境，来进行科学研究。
5总结和展望
在本文中，我们介绍了什么是空间
co-location挖掘，及怎样把关联规则应用到空间对象之上。在实验中，我们对空间co-location挖掘的全连接算法和无连接算法，在性能上进行了详细的分析和比较，并在三江并流项目中，用这两种算法，挖掘出了一些可为植物学家提供帮助的植被共生信息。通过上面的工作，我们可以得到以后的研究方向：第一、全连接算法中，当侯选实例增多时，运算时间会积聚增加。那么能采取什么方法，可以降低时间复杂度呢？从普通的关联规则的角度来考虑，目前挖掘频繁模式的范例已经经历了一个转换，从基于产生-检查的频繁模式挖掘，转换到基于投影的频繁模式挖掘。空间co-location挖掘也可朝着这个方向进行研究。第二、无连接算法还需要改进，这个算法生成的k阶侯选模式实例，是从中心对象的邻居集中生成的，而这步的组合数会随着k的增大而越来越大。如何减少生成实例时组合的数量，也是一个研究的问题。
参考文献
[1] Jiawei Han, Micheeline Kamber著, 范明,孟小峰等译. 数据挖掘概念与技术，机
械工业出版社, 2001
[2][美]Pang-Ning Tan Michael Steinbach Vipin Kumar著, 范明,范洪建等译。数据挖掘导论，人民邮电出版社, 2006
[3] S. Shekhar and S. Chawla. Spatial Databases: A Tour. Prentice Hall, ISBN 0130174807, 2003.
[4] S. Shekhar and Y. Huang. Co-location Rules Mining: A Summary of Results. In Proc. of International Symposium on Spatio and Temporal Database(SSTD), 2001.
[5] J. S. Yoo and S. Shekhar, A partial Join Approach for Mining Co-location Patterns, In Proc. of the 12th annual ACM international workshop on Geographic information systems, 2004, pp. 241-249.
[6]．R. Agarwal and R. Srikant. Fast algorithms for Mining association rules. In Proc. of Int’l Conference on Very Large Databases(VLDB), 1994. [7]．K. Koperski and J. Han. Discovery of Spatial Association Rules in Geographic Information Databases. In Proc .of Int’l Symposium on Large Spatial Data bases, Maine.47-66, 1995.
[8] Jin Soung Yoo, Shashi Shekhar, Mete Celik: A Join-Less Approach for
Co-Location Pattern Mining: A Summary of Results. ICDM 2005: 813-816
[9]V. Estivill-Castro and I. Lee, “Data Mining Techniques for Autonomous Exploration of Large Volumes of
Geo-Referenced Crime Data,” Proc. Sixth Int’l Conf. Geocomputation, 2001.
[10] V. Estivill-Castro and A. Murray, “Discovering Associations in Spatial Data—An Efficient Medoid Based Approach,” Proc. Second Pacific-Asia Conf. Knowledge Discovery and Data Mining, 1998.
[11] D. J. DeWitt and J.M. Patel, “Partition Based Spatial-Merge Join”Proc. ACM SIGMOD Conf. Management of Data, June 1996.
[12] Y. Morimoto.Mining Frequent Neighboring Class Sets in Spatial Databases. In Proc. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001.