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

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

作　　者：冯岭[1] 王丽珍[1] 高世健[1] 

机构地区：[1]云南大学信息学院计算机科学与工程系,昆明650091

出　　处：《南京大学学报（自然科学版）》2012年第1期99-107,共9页Journal of Nanjing University（Natural Science）

基　　金：国家自然科学基金(61063008);云南省教育厅研究基金(09Y0048);云南大学科学研究基金(2009F29Q)

摘　　要：Co-location模式挖掘是找出频繁出现在一起的一组空间特征的集合.在传统的方法中,一般假定每个空间特征在模式中具有平等的地位,然而,当模式中存在稀有特征时,有些模式便无法被获取.若使用现有针对含有稀有特征的挖掘方法,一些不频繁的模式也会被挖掘出来.针对以上问题,本文提出了最小加权参与率的概念,在此新概念下,不但可以挖掘出带稀有特征的频繁co-location模式,而且可以排除不频繁的模式.此外,针对算法时间复杂度高的问题,根据加权参与率排序后的部分向下闭合性提出了一种有效的剪枝方法,大大地提高了算法的执行效率.实验表明我们的方法对带稀有特征的co-location模式挖掘问题是有效的.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 are co-located.A large participation index indicates that the spatial features in a co-location pattern likely occur together.Generally,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 are 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

关 键 词：CO-LOCATION模式 稀有特征 加权参与率 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]