基于特征效用参与率的空间高效用co-location模式挖掘方法

Mining Spatial High Utility Co-location Patterns Based on Feature Utility Ratio

空间co-location模式是指其实例在空间邻域内频繁一起出现的空间特征子集.与传统的空间co-location模式挖掘不同,在空间高效用co-location模式挖掘中,不再将参与度(PI)作为有趣模式的度量指标,而是将效用值作为挖掘有趣模式的兴趣度量指标.现有的空间高效用co-location模式挖掘方法分为特征带效用和实例带效用两类.特征带效用的现有方法没有考虑不同特征效用之间的差异,挖掘的结果往往包含了许多不尽合理的"高效用"模式;而实例带效用的现有方法,则考虑了不同特征对模式效用的影响,但没有客观地度量这种影响.该文提出了一种确定特征在模式中的效用权重ω(fi,c)的方法,定义了更为合理的空间高效用co-location模式概念,设计了一个有效的挖掘算法.大量的实验表明提出的高效用co-location模式度量方法和相应的挖掘算法能够处理特征效用差异性和特征间的相互影响问题,能更有效地挖掘到空间高效用co-location模式.

A spatial co-location pattern is a subset of spatial features which shows frequent association relationships based on the spatial neighborhood.Different from the participation index(PI)which is regarded as a measure of interests in traditional spatial co-location pattern mining,the utility of co-location pattern is considered as the measure of interests in the spatial high utility co-location pattern mining.The purpose of the spatial high utility co-location pattern mining is to compensate for the knowledge omission in traditional co-location pattern mining,and the high utility co-location can reflect the interactions between different spatial features or different spatial instances.It is noteworthy that there are lots of differences between the traditional high utility pattern mining and the spatial high utility co-location pattern mining.Firstly,due to the specificity of different spatial features,it is irrational to measure the utilities of different spatial instances using a unified standard.Second,although the high utility pattern mining technology in traditional databases is very mature,these techniques cannot be directly applied to spatial high utility co-location pattern mining,because the prevalence of spatial co-location patterns,which is completely different from the itemsets in transaction database,is measured by the cluster relations formed by the proximity relationships.So far,the existing methods of the spatial high utility co-location pattern mining can be classified into two classes:spatial features with utilities and spatial instances with utilities.The spatial features with utilities method considers the utilities of different features,which will weaken the value of the features that are highly participated but relatively low-valued in the co-location pattern.The interactions of the features in a co-location pattern are very important to evaluate a co-location,but the method of spatial features with utilities has not considered this important factor.Moreover,this method has also not considered the different utility measure standards of different spatial features,the utilities of spatial features are added directly.In the method of spatial instances with utilities,the utility participation ratio(UPR)is calculated and used to evaluate the features’ utility value in a co-location pattern.At the same time,it considers the influences between the different features.However,the method requires that the UPR of all features in a co-location pattern is greater than a specified utility threshold,which leads to some high utility co-location patterns are missed,so the method can not measure the spatial high utility co-location patterns objectively.In summary,the former does not consider the difference of different features’ utilities which lead to mine some unreasonable patterns,and the latter considers the influence of different features,but the different influence has not been measured objectively.This paper proposes an efficient method to measure the utility weightω(fi,c)of different features in a spatial co-location pattern,which can reflect the interaction of features in the co-location pattern more correctly,and define a more reasonable concept of spatial high utility co-location pattern.A basic mining algorithm and two efficient pruning algorithms are designed.Experimental results show that the method proposed in this paper can help users to mine the useful,reasonable and interesting spatial high utility co-location patterns.