高平均效用co-location模式挖掘的一种有效算法

大理大学学报 ›› 2022, Vol. 7 ›› Issue (6): 9-17.

高平均效用co-location模式挖掘的一种有效算法

大理大学数学与计算机学院，云南大理　671003

收稿日期:2021-10-05 修回日期:2021-11-10 出版日期:2022-06-15 发布日期:2022-07-04
通讯作者: 李晓伟，讲师，博士，E-mail：lixiaowei_xidian@163.com。
作者简介:曾新，讲师，主要从事数据挖掘、计算机应用技术研究。
基金资助:
云南省地方本科高校（部分）基础研究联合专项资金项目（2018FH001-062；2018FH001-063）；大理大学数据安全与应用创新团队（ZKLX2020308）

An Effective Algorithm for Mining High Average-Utility Co-Location Patterns

College of Mathematics and Computer， Dali University， Dali， Yunnan 671003， China

Received:2021-10-05 Revised:2021-11-10 Online:2022-06-15 Published:2022-07-04

摘要/Abstract

摘要：

co-location模式是空间特征集合的一个子集，模式中不同特征的实例频繁出现在邻近区域内。纵观高效用co-location模式挖掘的相关研究报道，现存的高效用co-location模式挖掘方法没有考虑模式的长度对模式效用的影响。为了探索这一问题，提出一种从空间数据集中挖掘高平均效用co-location模式的算法（HAUCP），以便更好地评价co-location模式的真实效用。首先，基于空间数据集提出高平均效用co-location模式的完整定义；其次，构建了高平均效用co-location模式挖掘的基本算法，并探索了两种有效的剪枝策略以提升算法的运行效率；最后，在真实数据集和合成数据集上对算法的有效性和可扩展性进行了大量实验，实验结果表明HAUCP算法挖掘出的高效用co-location模式更加合理。

关键词: 高平均效用, co-location模式, 模式长度, 空间数据集, 数据挖掘算法

Abstract:

Co-location pattern is a subset of spatial feature set，and some instances of different features in co-location pattern frequently appear in adjacent areas. Looking at relevant research reports on high utility co-location pattern mining， the existing high utility co-location patterns mining algorithms do not consider the impact of the length of pattern on the utility of pattern. To explore this issue， we propose an effective algorithm of mining high average-utility co-location patterns （HAUCP） from spatial dataset to provide a better evaluation of the real utility of co-location pattern. First， a comprehensive definition of high average-utility co-location patterns based on spatial dataset is proposed. Secondly， the basic algorithm of high average-utility co-location pattern mining is constructed. For improving the efficiency of the basic algorithm， two pruning strategies are developed to reduce the computing costs. Finally， extensive experiments on real dataset and synthetic dataset are carried out to prove the effectiveness of the proposed algorithm. Experimental results show that high-utility co-location patterns of HAUCP are more reasonable.

Key words:

high average-utility, co-location patterns, pattern length, spatial dataset, data mining algorithm

中图分类号:

TP391

曾　新, 张晓玲, 李晓伟.

高平均效用co-location模式挖掘的一种有效算法 [J]. 大理大学学报, 2022, 7(6): 9-17.

Zeng Xin, Zhang Xiaoling, Li Xiaowei.

An Effective Algorithm for Mining High Average-Utility Co-Location Patterns [J]. Journal of Dali University, 2022, 7(6): 9-17.

参考文献

〔1〕 HUANG Y， SHEKHAR S， XIONG H. Discovering Co-Ｌocation Patterns from Spatial Data Sets： A General Approach〔J〕. IEEE Transactions on Knowledge and Data Engineering， 2004， 16（12）： 1472-1485.

〔2〕 YOO J S， SHEKHAR S， SMITH J， et al. A Partial Join Approach for Mining Co-Ｌocation Patterns〔C〕// Procee-dings of the 12th Annual ACM International Workshop on Geographic Information Systems - GIS '04. November 12-13，2004，Washington DC，USA. New York：ACM Press，2004：241-249.

〔3〕 YOO J S， SHEKHAR S. A Joinless Approach for Mining Spatial Co-Ｌocation Patterns〔J〕. IEEE Transaction on Knowledge and Data Engineering， 2006， 18（10）： 1323-1337.

〔4〕 WANG L Z， BAO Y Z， LU J， et al. A New Join-Less Approach for Co-Location Pattern Mining〔C〕//2008 8th IEEE International Conference on Computer and Information Technology， July 8-11，2008，Sydney，NSW，Australia. IEEE，2008：197-202.

〔5〕 WANG L Z， HAN J， CHEN H M， et al. Top-k Probab-ilistic Prevalent Co-Ｌocation Mining in Spatially Uncer-tain Data Sets〔J〕. Frontiers of Computer Science， 2016， 10（3）： 488-503.

〔6〕 YOO J S， VASUDEVAN H. Effectively Updating Col-ocation Patterns in Evolving Spatial Databases〔C〕//2014 the Sixth International Conferecnce on Pervasive Patterns and Applications. 2014： 96-99.

〔7〕 LU J L， WANG L Z， FANG Y， et al. Mining Strong Symbiotic Patterns Hidden in Spatial Prevalent Co-Location Patterns〔J〕. Knowledge-Based Systems， 2018， 146： 190-202.

〔8〕芦俊丽，王丽珍，赵家松，等. 从动态空间数据库中挖掘共生关系和竞争关系〔J〕. 南京大学学报（自然科学版）， 2018， 54（2）： 436-451.

〔9〕 HUANG Y， PEI J， XIONG H. Mining Co-Location Pat-terns with Rare Events from Spatial Data Sets〔J〕. GeoInformatica， 2006， 10（3）： 239-260.

〔10〕冯岭，王丽珍，高世健. 一种带稀有特征的空间co-location模式挖掘新方法〔J〕. 南京大学学报（自然科学版）， 2012， 48（1）： 99-107.

〔11〕杨世晟，王丽珍，芦俊丽，等. 空间高效用Co-location模式挖掘技术初探〔J〕. 小型微型计算机系统， 2014， 35（10）： 2302-2307.

〔12〕 WANG X X，WANG L Z，LU J L，et al. Effectively Updating High Utility Co-Location Patterns in Evolving Spatial Databases〔C〕// International Conference on Webage Information Management. Springer，Cham，2016，DOI：10.1007/978-3-319-39937-9_6.

〔13〕 WANG L Z，JIANG W G，CHEN H M，et al. Efficiently Mining High Utility Co -Location Patterns from Spatial Data Sets with Instance-Specific Utilities〔C〕// International Conference on Database Systems for Advanced Applicat-ions. Cham：Springer International Publishing，2017：458-474.

〔14〕王晓璇，王丽珍，陈红梅，等. 基于特征效用参与率的空间高效用co-location模式挖掘方法〔J〕. 计算机学报， 2019， 42（8）： 1721-1738.

〔15〕 ZENG X， YANG J， LI Z P， et al. A Method of Mining Spatial High Utility Co-Location Patterns Based on Fea-ture Actual Participation Weight〔C〕// IOP Conf. Series：Journal of Physics：Conf. Series. 2019，1168：032064.

〔16〕 HONG T P， LEE C H， WANG S L. Effective Utility Mining with the Measure of Average Utility〔J〕. Expert Systems with Application， 2011， 38（7）： 8259-8265.

〔17〕 LIN C W ， LAN G C ， HONG T P . An Incremental Mining Algorithm for High Utility Itemsets〔J〕. Expert Systems with Applications， 2012， 39（8）：7173-7180.

〔18〕 LIN J C W， LI T， FOURNIER-VIGER P， et al. An Efficient Algorithm to Mine High Average-Utility Itemsets〔J〕. Advanced Engineering Informatics， 2016， 30（2）： 233-243.

〔19〕 LIN J C W，REN S F，FOURNIER-VIGER P，et al.EHAUPM：Efficient High Average-Utility Pattern Mining with Tighter Upper Bounds〔J〕. IEEE Access，2017，5：12927-12940.

〔20〕 YUN U， KIM D. Mining of High Average-Utility Itemsets Using Novel List Structure and Pruning Strategy〔J〕. Future Generation Computer Systems， 2017， 68： 346-360.

〔21〕 LIN J C W， REN S F， FOURNIER-VIGER P， et al. Efficiently Updating the Discovered High Average-Utility Itemsets with Transaction Insertion〔J〕. Engineering Applications of Artificial Intelligence， 2018， 72： 136-149.

〔22〕 TAI W J M， WEI L J C， MATIN P， et al. TUB-HAUPM： Tighter Upper Bound for Mining High Average-Utility Patterns〔J〕. IEEE Access， 2018， 6： 18655-18669.

〔23〕 TRUONG T， DUONG H， LE B， et al. Efficient Vertical Mining of High Average-Utility Itemsets Based on Novel Upper-Bounds〔J〕. IEEE Transactions on Knowledge and Data Engineering， 2019， 31（2）： 301-314.

〔24〕 AGRAWAL R， IMIELI SKI T， SWAMI A. Mining Association Rules between Sets of Items in Large Databases〔C〕// Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. 1993：207-216.

[1]	曾　新, 李振鹏, 杨　健, 李晓伟. 含稀有特征的高平均效用co-location模式挖掘算法[J]. 大理大学学报, 2021, 6(12): 5-11.
[2]	曾新，李晓伟，杨健. 空间co-location模式挖掘表实例的计算方法[J]. , 2017, 2(12): 27-31.