一种带稀有特征的空间co-location模式挖掘新方法*

南京大学学报(自然科学版) ›› 2012, Vol. 48 ›› Issue (1): 99–107.

一种带稀有特征的空间co-location模式挖掘新方法*

冯岭，王丽珍**，高世健

出版日期:2015-05-20 发布日期:2015-05-20
作者简介: (云南大学信息学院计算机科学与工程系，昆明，650091)
基金资助:
国家自然科学基金(61063008),南省教育厅研究基金(09Y0048) ,云南大学科学研究基金(2009F29Q

A new approach of mining co-location patterns in
spatial datasets with rare features

Feng Ling,Wang Li Zhen，Guo Shi一Jiun

Online:2015-05-20 Published:2015-05-20
About author: (Department of Computer Science and Engineering, School of Information and Engineering,
Yunnan Universitv. Kunming. 650091，China)

摘要/Abstract

摘要： Co-location模式挖掘是找出频繁出现在一起的一组空间特征的集合.在传统的为一法中，一般假定每个空间特征在模式中其有平等的地位，然而，当模式中存在稀有特征时，有此模式便无法被获取.
若使用现有钊一对含有稀有特征的挖掘为一法，一此不频繁的模式也会被挖掘出来.钊一对以上问题，本文提出了最小加权参与率的概念，在此新概念下，不但可以挖掘出带稀有特征的频繁co-location模式，而且
可以排除不频繁的模式.此外，钊一对算法时间复杂度高的问题，根据加权参与率排序后的部分向下闭合J降提出了一种有效的剪枝为一法，大大地提高了算法的执行效率.实验表明我们的为一法对带稀有特征的
co-location模式挖掘问题是有效的.

Abstract: Co-location pattern mining aims at finding a group of spatial features frequently located together. Participation index is proposed to measure how all the spatial features in a co-location pattern arc co-located. A large
participation index indicates that the spatial features in a co-location pattern likely occur together. Ucnerally, participation index is defined as the minimal participation ratio among all the features in a co-location pattern.
Traditional studies on co-location pattern mining use this definition which emphasizes the equal participation of each spatial feature to find frequent co-location patterns. Whereas if there arc rare features in the dataset, general
features often get a low participation index, and the co-location pattern gets a low participation index. As a result，some interesting patterns involving features with substantially different frequency can not be captured. A maximal
participation index has been proposed to resolve this problem. But if we use this existing method with rare features, some infrequent patterns may be considered as frequent patterns. On account of the case, we present a new method
of minimal weighted participation ratio. In this method，we give each feature a proper weighing in considering the amount of instances of every feature to solve the problem that general features often get a low participation ratio
value，and define the minimal weighted participation ratio as participation index as traditional studies do. Using this method we can not only find out the frequent patterns in the datasets with rare features, but also eliminate the
infrequent patterns which are frequent in the existing method. In addition, considering the high complexity of the new method，we propose an improved method using partial closure character of weighted participation ratio which is
proved right to improve the efficiency of our method. With the improved method some infrequent co-location patterns can be eliminated in advance. So the time of computing participation ratio will be reduced and the efficiency
will be improved. A lot of experiments are provided on synthetic data and real data. As onr expcnmcnts demonstrate,onr approach is effective and efficient in identifying co-location patterns in the dataset with rare features.

冯岭，王丽珍**，高世健. 一种带稀有特征的空间co-location模式挖掘新方法*[J]. 南京大学学报(自然科学版), 2012, 48(1): 99–107.

Feng Ling,Wang Li Zhen，Guo Shi一Jiun
. A new approach of mining co-location patterns in
spatial datasets with rare features
[J]. Journal of Nanjing University(Natural Sciences), 2012, 48(1): 99–107.

参考文献

[1]McNamara L, Mascolo C,Capra L. Media sha- ring based on colocation prediction in urban transport. Raghupathy S, Peter S. Proceedings of the 14^th ACM international Conference on Mobile Computing and Networking, 2008，58一69.
[2]Huang Y，Pei，Xiong H. Mining co-location patterns with rare events from spatial data sets. Geolnformatica, 2006，10(3):239一260.
[3]Wang L Z, Zhou I. H，Lu J，et al. An ordcr- clique-based approach for mining maximal co-lo- canons. information Sciences, 2009，179(19): 3370一3382.
[4]Yoo J S, Shekhar S, Celik M. A joirrlcss ap- proach for co-location pattern mining; a summa- ry of results. Han J W, Benjamin W W. Pro- cecdings of the 5^th IEEE international Confer- ence on Data Mining. Piscataway, 2005，813一816.
[5]Huang Y，Shekhar S, Xiong H. Discovering colocation patterns from spatial data sets; general approach, IEEE Transactions on Knowledge and Data Engineering, 2004，16 (12):1472一1485.
[6]Wang L Z, Yao Y Z，Lu J，et al. A new join- less approach for co-location pattern mining. Paul P W, Sungwon S. Proceedings of the IEEE 8^th International Conference on Computer and information Technology, 2008，197一202.
[7]Huang Y，Zhang P. On the relationships be- twecn clustering and spatial co-location pattern mining. Lu C T, Nikolaos G B. Proceedings of the 18^th IEEE international Conference on Tools with Artificial intelligence, 2006，513一522.
[8]Liu J Q, Wang X, Sun X Y. Effectively mining multi-dimension multi-level association rules. Journal of Nanjing University(Natural Sci- ences), 2003, 39(2); 205一210.(刘俊强，王勋，孙晓莹.多维多层关联规则挖掘的新算法.南京大学学报(自然科学)，2003 , 39 ( 2 ) ; 205一210).

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed