论文部分内容阅读
摘 要：空间Co-location模式挖掘是空间数据挖掘的一个重要领域，其目标是发现空间中在一起频繁出现的空间特征。Joinless算法沿用了Joinbase的度量标准，定义了星型邻近关系，并利用它的性质，将Joinbase算法中的连接操作替换成了更快速的查找操作。本文基于Java HashMap实现了上述两种算法，并通过实验考察了参数设置对挖掘算法效率的影响、Joinbase算法和Joinless算法的剪枝策略的效率，同时，从时间、空间两方面比较了这两种算法的异同，以期为学生学习、老师教学以及实际应用研究提供参考。
关键词：空间数据挖掘；Co-location模式；Joinbase算法；Joinless算法
中图分类号：TP3-0 文献标识码：B 收稿日期：2015-12-09
一、引言
现实世界中的物体都占据一定的物理空间，并且与周围的其他物体存在诸多联系。本文首先介绍了Joinbase算法和Joinless算法，并详细阐述了其中的剪枝策略以及一些可能的优化方法；其次，分析了使用Java编程语言实现的两种算法，并进行了相关实验，考察了参数设置对算法的影响，探究了剪枝策略的效率以及比较两种算法。
二、空间Co-location模式挖掘
空间特征（spatial feature）是一系列特征的集合，它们用来表示空间中事物的不同属性，记为F= {f1，f2，…，fn}。它们的实例（instance）就是指空间中体现这些特征（可以是一种或多种）的具体事物，记为I={i1，i2，…，in}，其中每个实例in∈I都可以表示为“实例ID、所属特征、空间位置”。以植被数据为例，某种植被可以看作是空间特征，而这种植被的某一个个体则称之为实例。
Co-location规则的条件概率表示由模式c1推出模式c2的可信度，计算方法为：
三、算法实现
Java HashMap是Java中最常用的容器类之一，它是基于哈希表的Map接口的非同步实现，能够快速地存取键值对。在很多情况下，哈希表的效率都要优于搜索树和其他查找结构，因此哈希表在很多领域尤其是在关联数组、数据库索引、缓存等方面得到了广泛应用。
HashMap中的Map.Entry包含了键、值、哈希码以及一个指向下个Map.Entry的引用，值得注意的是Java容器中都是存放对象的引用，所以，HashMap中键值也都是引用。因为空间效率与具体的实现有关，而目前JVM有很多不同的实现方法，数组的长度等于容量除以负载因子，为了保持一致，本文讨论空间效率时，是假设在64位机器上，并且每个引用占用8个字节的条件下进行。
笔者通过实验比较Joinbase和Joinless算法，并探究两种算法中的一些剪枝策略的效率以及参数设置对挖掘算法的影响。首先计算hashCode时需要对所有的关键域使用乘法进行操作——即使编译器优化为位移操作，这样，使用现有的HashMap还不如“直接比较”高效。
四、小结
本文使用Java HashMap实现了Joinless算法和Joinbase算法，并使用数据测试了算法的效率以及参数对算法的影响。通过比较Joinbase算法和Joinless算法，我们发现Joinless算法的效率与实现方式有很大的关系，虽然理论上说Joinless的查找操作要比Joinbase的连接操作高效，但是由于Java HashMap本身的机制影响，导致Joinless实际的运行效率反而不如Joinbase。
参考文献：
[1]王丽珍，周丽华，陈红梅.数据仓库与数据挖掘原理及应用（第二版）[M].北京：科学出版社，2009.
[2]Huang Yan，Shashi Shekhar and Hui Xiong.Discovering Colocation patterns from Spatial Data Sets： A Heneral Approach[J].IEEE Transactions on Knowledge and Data Engineering，2004，16（12）.
[3]Yoo，Jin Soung，and Shashi Shekhar.A joinless approach for mining spatial colocation patterns[J].IEEE Transactions on Knowledge and Data Engineering，2006，18（10）.
[4]冯 岭，王丽珍，高世健.一种带稀有特征的空间co-location模式挖掘新方法[J].南京大学学报（自然科学版），2012，48（1）：99-107.
[5]熊国华，周 俊，童小华，等.空间数据线要素综合的经典算法及其实现[J].水利科技与经济，2006，12（6）.
[6]王 新，肖 涛，芦俊丽，等.空间Co-Location模式增量挖掘及演化分析[J].软件学报，2014，（S2）.
关键词：空间数据挖掘；Co-location模式；Joinbase算法；Joinless算法
中图分类号：TP3-0 文献标识码：B 收稿日期：2015-12-09
一、引言
现实世界中的物体都占据一定的物理空间，并且与周围的其他物体存在诸多联系。本文首先介绍了Joinbase算法和Joinless算法，并详细阐述了其中的剪枝策略以及一些可能的优化方法；其次，分析了使用Java编程语言实现的两种算法，并进行了相关实验，考察了参数设置对算法的影响，探究了剪枝策略的效率以及比较两种算法。
二、空间Co-location模式挖掘
空间特征（spatial feature）是一系列特征的集合，它们用来表示空间中事物的不同属性，记为F= {f1，f2，…，fn}。它们的实例（instance）就是指空间中体现这些特征（可以是一种或多种）的具体事物，记为I={i1，i2，…，in}，其中每个实例in∈I都可以表示为“实例ID、所属特征、空间位置”。以植被数据为例，某种植被可以看作是空间特征，而这种植被的某一个个体则称之为实例。
Co-location规则的条件概率表示由模式c1推出模式c2的可信度，计算方法为：
三、算法实现
Java HashMap是Java中最常用的容器类之一，它是基于哈希表的Map接口的非同步实现，能够快速地存取键值对。在很多情况下，哈希表的效率都要优于搜索树和其他查找结构，因此哈希表在很多领域尤其是在关联数组、数据库索引、缓存等方面得到了广泛应用。
HashMap中的Map.Entry包含了键、值、哈希码以及一个指向下个Map.Entry的引用，值得注意的是Java容器中都是存放对象的引用，所以，HashMap中键值也都是引用。因为空间效率与具体的实现有关，而目前JVM有很多不同的实现方法，数组的长度等于容量除以负载因子，为了保持一致，本文讨论空间效率时，是假设在64位机器上，并且每个引用占用8个字节的条件下进行。
笔者通过实验比较Joinbase和Joinless算法，并探究两种算法中的一些剪枝策略的效率以及参数设置对挖掘算法的影响。首先计算hashCode时需要对所有的关键域使用乘法进行操作——即使编译器优化为位移操作，这样，使用现有的HashMap还不如“直接比较”高效。
四、小结
本文使用Java HashMap实现了Joinless算法和Joinbase算法，并使用数据测试了算法的效率以及参数对算法的影响。通过比较Joinbase算法和Joinless算法，我们发现Joinless算法的效率与实现方式有很大的关系，虽然理论上说Joinless的查找操作要比Joinbase的连接操作高效，但是由于Java HashMap本身的机制影响，导致Joinless实际的运行效率反而不如Joinbase。
参考文献：
[1]王丽珍，周丽华，陈红梅.数据仓库与数据挖掘原理及应用（第二版）[M].北京：科学出版社，2009.
[2]Huang Yan，Shashi Shekhar and Hui Xiong.Discovering Colocation patterns from Spatial Data Sets： A Heneral Approach[J].IEEE Transactions on Knowledge and Data Engineering，2004，16（12）.
[3]Yoo，Jin Soung，and Shashi Shekhar.A joinless approach for mining spatial colocation patterns[J].IEEE Transactions on Knowledge and Data Engineering，2006，18（10）.
[4]冯 岭，王丽珍，高世健.一种带稀有特征的空间co-location模式挖掘新方法[J].南京大学学报（自然科学版），2012，48（1）：99-107.
[5]熊国华，周 俊，童小华，等.空间数据线要素综合的经典算法及其实现[J].水利科技与经济，2006，12（6）.
[6]王 新，肖 涛，芦俊丽，等.空间Co-Location模式增量挖掘及演化分析[J].软件学报，2014，（S2）.