多分辨剪枝局部聚类算法挖掘空间co-location模式

摘要/Abstract

摘要： 传统的co-location模式挖掘算法采取对各个特征实例进行逐一连接的挖掘方式,其结果是,常常消耗大量的时间和空间资源,甚至由于内存资源被过度消耗而无法挖掘出最终结果,特别是在数据量大的情况下更是如此。因此,提出了一种高效的多分辨剪枝局部聚类算法(MP_LC)。MP_LC算法首先对数据区域划分网格,再对各个网格中每一特征的实例进行聚类,求出每一类所包含实例的质心,用质心代替相应的实例集,并进行后续的挖掘。大量实验结果表明,MP_LC算法具有较高的效率、较高的准确率以及较好的实际应用价值。

关键词: co-location模式,多分辨剪枝,聚类,质心,实例收缩率

Abstract: The traditional co-location pattern mining algorithms take the mining method that connects each furture instance one by one.As a result,they often consume a large amount of time and space resources,even they are unable to dig out the final results because memory resources are over consumed,especially in the face of a large quantity of data case.Therefore,an efficient multiresolution pruning and local clustering algorithm (MP_LC) was proposed.The MP_LC algorithm firstly divides the data region into grids,then clusteres the instances of each feature in each grid,and calculates the centroid of the instances contained by each cluster,replaces the instance set by the centroid,and finally continues to subsequent mining work.A large number of experimental results indicate that the MP_LC algorithm has high efficiency,high accuracy,and good practical application value.

Key words: Co-location pattern,Multiresolution pruning,Cluster,Centroid,Instance shrinkage rate

吕诚. 多分辨剪枝局部聚类算法挖掘空间co-location模式[J]. 计算机科学, 2014, 41(Z11): 327-332. https://doi.org/

LV Cheng. Mining Spatial Co-location Pattern with Multiresolution Pruning and Local Clustering Algorithm[J]. Computer Science, 2014, 41(Z11): 327-332. https://doi.org/

参考文献

[1] Gao Yun-jun,Zheng Bai-hua.Continuous Obstructed NearestNeighbor Queries in Spatial Databases[C]∥ACM SIGMOD.NY,USA,2009:577-590
[2] Ruggieri S.Frequent regular itemset mining [C]∥KDD.ACM,Washington DC,USA,2010:263-272
[3] Shekhar S,Huang Yan.Discovering Spatial Co-location Pat-terns:A Summary of Results [C]∥Proc.of the 7th International Symposium on Advances in Spatial and Temporal Databases.CA,USA,2001:236-240
[4] Al-Naymat G.Enumeration of maximal clique for mining spatial Co-Location Patterns [C]∥6^th ACS/IEEE International Confe-rence on Computer Systems and Applications.Doha,Qatar,2008:126-133
[5] Celik M,Kang J M,Shekhar S.Zonal Co-Location Patterns Discovery with Dynamic Parameters[C]∥7th IEEE International Conference on Data Mining.Omaha NE,USA,2007:433-438
[6] Huang Yan,Xiong Hui,Shekhar S,et al.Mining confident Co-Location rules without a support threshold[C]∥ACM Symposium on Applied Computing.Florida,USA,2003:497-418
[7] Huang Yan,Shekhar S,Xiong H.Discovering Co-location Pat-terns from Spatial Data Sets:A General Approach [J].IEEE Transactions on Knowledge and Data Engineering,2004,16(12):1472-1485
[8] Koperski K,Han J.Discovery of Spatial Association Rules in Geographic Information Databases[C]∥Proc.of the 4th International Symposium on Spatial Databases.Portland,Maine,1995:47-66
[9] Yoo J S,Shekhar S.A partial Join Approach for Mining Co-location Patterns [C]∥the 12th Annual ACM International Workshop on Geographic Information Systems.NY,USA,2004:241-249
[10] Yoo J S,Shekhar S,Celik M.A Join-Less Approach for Co-Location Pattern Mining:A Summary of Results [C]∥The 5th IEEE International Conference on Data Mining.NY,USA,2005:813-816
[11] Wang L,Bao Y,Lu J,et al.A New Join-less Approach for Co-lo-cation Pattern Mining [C]∥The 8th IEEE International Conference on Computer and Information Technology.Sydney,Australia,2008:197-202
[12] Wang Li-zhen,Bao Yu-zhen,Lu Zhong-yu.Efficient Discovery of spatial co-location patterns using the iCPI-tree [J].The Open Information Systems Journal,2009,3 (1):69-80
[13] Wang Li-zhen,Zhou Li-hua,Joan L.An order-clique-based ap-proach for mining maximal co-locations[J].Information Sciences,2009,179 (19):3370-3382
[14] Xiao X,Xie X,Luo Q.Density-based co-location pattern discovery[C]∥Proc.of the 16th ACM International Conference on Advances in Geographic Information Systems.Irvine,California,2008:11-20
[15] Huang Yan,Pei J,Xiong H.Mining Co-location Patterns withRare Events from Spatial Data Sets[J].Geoinformatica,2006,10(3):239-260
[16] Xiao X,Xie X,Luo Q.Density-based co-location pattern discovery[C]∥Proc.of the 16th ACM International Conference on Advances in Geographic Information Systems.Irvine,California,2008:11-20
[17] Huang Yan,Pei J,Xiong H.Mining Co-location Patterns withRare Events from Spatial Data Sets [J].Geoinformatica,2006,10(3):239-260
[18] Wang Li-zhen,Wu Ping-ping, Chen Hong-mei.Finding Probabilistic Prevalent Co-locations in Spatially Uncertain Data Sets [J].IEEE Transactions on Knowledge and Data Engineering (TKDE),2011,25(4):790-804
[19] Sheng C,Hsu W,Lee M.Discovering Spatial Interaction Patterns [M].Berlin:Springer,2008:95-109
[20] 欧阳志平,王丽珍,陈红梅.模糊对象的空间Co-Location模式挖掘研究[J].计算机学报,2012(10):1947-1956
[21] Wang Li-zhen,Chen Hong-mei,Zhao Li-hong,et al.Efficiently Mining Co-Location Rules on Interval Data [C]∥ADMA 2010,Part I.LNCS 6440,2010:477-488

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed