含稀有特征的高平均效用co-location模式挖掘算法

大理大学学报 ›› 2021, Vol. 6 ›› Issue (12): 5-11.

含稀有特征的高平均效用co-location模式挖掘算法

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

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

High Average-Utility Co-Location Patterns Mining Algorithm with Rare Features

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

Received:2021-04-15 Online:2021-12-15 Published:2022-01-12

摘要/Abstract

摘要： 空间高效用co-location模式挖掘以模式中所有特征的参与效用之和为衡量标准，而未考虑模式的长度和稀有特征对模式效用的影响。一般而言，模式的长度越长或存在稀有特征，模式的效用可能越大。在空间高效用co-location模式挖掘研究的基础上，同时考虑模式的长度和可能存在的稀有特征。首先，提出含稀有特征的高平均效用co-location模式挖掘的相关定义；然后，构建含稀有特征的高平均效用co-location模式挖掘算法HAUWR，并在真实和合成数据集下对HAUWR进行大量实验，实验结果表明：HAUWR能够挖掘出满足条件的co-location模式完全集，并具有较好的可扩展性；最后，针对模式长度对高效用co-location模式的影响，HAUWR与含稀有特征的高效用co-location模式挖掘算法HUWR在数据集大小、距离阈值、特征稀有度等方面进行了对比。

关键词: 空间数据挖掘, 高平均效用, co-location模式, 稀有特征, 模式长度

Abstract:

Spatial high utility co-location patterns mining uses the sum of participating utility of all features in pattern as the measurement standard， without considering the impact of pattern length and rare features. In general， the longer the pattern length or the rarer the features， the greater the utility of the pattern. This paper is based on spatial high-utility co-location pattern mining， while considering the pattern length and possible rare features of patterns. Firstly， the definitions of high average-utility co-location pattern mining with rare features is proposed； then， a high average-utility co-location pattern mining algorithm HAUWR with rare features is constructed， and a large number of experiments on HAUWR are performed on real and synthetic data sets. The experiment result shows that algorithm HAUWR can mine the complete set of co-location patterns that meet the conditions， and has good scalability. Finally， regarding the impact of pattern length of high utility co-location patterns， HAUWR is compared with high utility co-location patterns mining algorithm HUWR containing rare features in some aspects， such as dataset size， distance threshold， and feature rarity.

Key words:

, spatial data mining, high average-utility, co-location patterns, rare features, pattern length

中图分类号:

TP391

曾　新, 李振鹏, 杨　健, 李晓伟. 含稀有特征的高平均效用co-location模式挖掘算法[J]. 大理大学学报, 2021, 6(12): 5-11.

Zeng Xin, Li Zhenpeng, Yang Jian, Li Xiaowei.

High Average-Utility Co-Location Patterns Mining Algorithm with Rare Features [J]. Journal of Dali University, 2021, 6(12): 5-11.

参考文献

〔1〕 HUANG Y， SHEKHAR S， XIONG H. Discovering Colocation 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-Location Patterns〔C〕//Proceedings 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 Colocation Patterns〔J〕. IEEE Transaction on Kno-wledge and Data Engineering， 2006， 18（10）： 1323-1337.

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

〔5〕 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.

〔6〕 WANG L Z， HAN J， CHEN H M， et al. Top-k Probabilistic Prevalent Co-Location Mining in Spatially Uncertain Data Sets〔J〕. Frontiers of Computer Science， 2016， 10（3）： 488-503.

〔7〕 YOO J S， VASUDEVAN H. Effectively Updating Co-Location Patterns in Evolving Spatial Databases〔C〕//2014 the Sixth International Conferences on Pervasive Patterns and Applications， 2014： 96-99.

〔8〕 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.

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

〔10〕芦俊丽，王丽珍，肖清，等. 空间co-location模式增量挖掘及演化分析〔J〕. 软件学报， 2014， 25（2）：189-200.

〔11〕 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 Web-age Information Management. Springer， Cham， 2016， DOI：10.1007/978-3-319-39937-9_6.

〔12〕 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 Applications. Cham： Springer International Publishing， 2017： 458-474.

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

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

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

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

〔17〕 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.

〔18〕 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.

〔19〕 WU J M T， LIN J C W， PIROUZ M， et al. TUB-HAUPM： Tighter Upper Bound for Mining High Average-Utility Patterns〔J〕. IEEE Access， 2018， 6： 18655-18669.

〔20〕 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.