模糊特征的top-k平均效用co-location模式挖掘

doi:10.3778/j.issn.1673-9418.2011003

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (5): 1053-1063.DOI: 10.3778/j.issn.1673-9418.2011003

模糊特征的top-k平均效用co-location模式挖掘

李金红, 王丽珍(), 周丽华

云南大学信息学院,昆明 650500

收稿日期:2020-11-02 修回日期:2021-01-05 出版日期:2022-05-01 发布日期:2022-05-19
通讯作者: + E-mail: lzhwang@ynu.edu.cn
作者简介:李金红（1994—）,女,云南曲靖人,硕士研究生,主要研究方向为空间数据挖掘。
王丽珍（1962—）,女,山西武乡人,博士,教授,博士生导师,CCF高级会员,主要研究方向为空间数据挖掘、交互式数据挖掘、大数据分析及其应用等。
周丽华（1968—）,女,云南华坪人,博士,教授,博士生导师,CCF会员,主要研究方向为数据挖掘、机器学习、社会网络分析。
基金资助:
国家自然科学基金(61966036);国家自然科学基金(61662086);云南省创新团队建设项目(2018HC019)

Top-k Average Utility Co-location Pattern Mining of Fuzzy Features

LI Jinhong, WANG Lizhen(), ZHOU Lihua

School of Information Science and Engineering, Yunnan University, Kunming 650500, China

Received:2020-11-02 Revised:2021-01-05 Online:2022-05-01 Published:2022-05-19
About author:LI Jinhong, born in 1994, M.S. candidate. Her research interest is spatial data mining.
WANG Lizhen, born in 1962, Ph.D., professor, Ph.D. supervisor, senior member of CCF. Her research interests include spatial data mining, interactive data mining, big data analytics and their applications, etc.
ZHOU Lihua, born in 1968, Ph.D., professor, Ph.D. supervisor, member of CCF. Her research interests include data mining, machine learning and social network analysis.
Supported by:
National Natural Science Foundation of China(61966036);National Natural Science Foundation of China(61662086);Project of Innovative Research Team of Yunnan Province(2018HC019)

摘要/Abstract

摘要：

空间并置（co-location）模式是指在空间邻域内空间特征的实例频繁地出现在一起所形成的非空特征子集。人们已经对确定数据和不确定数据的top-k空间co-location模式挖掘进行了相关研究,但是针对模糊特征的top-k平均效用co-location模式挖掘的研究还没有。提出模糊特征的top-k平均效用co-location模式挖掘。首先,定义了模糊特征的top-k平均效用co-location模式的相关概念,分析了模式的扩展模糊平均效用具有的“向下闭合”性质。其次,设计了一种基于扩展模糊平均效用值挖掘top-k平均效用co-location模式的算法,解决模糊平均效用不满足“向下闭合”性质的问题。在此基础上,又提出了一种基于局部扩展模糊平均效用的剪枝方法,有效地减小了top-k平均效用co-location模式挖掘的搜索空间,进一步提高了挖掘算法的效率。最后,在真实和合成数据集上验证了所提出算法的实用性、高效性和鲁棒性。

关键词: 空间co-location模式, 高平均效用, 模糊特征, top-k

Abstract:

The spatial co-location pattern refers to a subset of non-empty spatial features whose instances are frequently located together in a spatial neighborhood. Researchers have carried out relevant research of top-k spatial co-location pattern mining for deterministic data and uncertain data, but there is no research on top-k average utility co-location pattern mining for fuzzy features. Therefore, this paper proposes top-k average utility co-location pattern mining for fuzzy features. Firstly, the relevant concepts of top-k average utility co-location patterns of fuzzy features are defined, and the “downward close” nature of the extended fuzzy average utility of the pattern is analyzed. Secondly, an algorithm of mining top-k average utility co-location patterns based on extended fuzzy average utility value is designed,solving the problem that the fuzzy average utility does not satisfy the “downward close” nature. Thirdly, a pruning method based on a locally extended fuzzy average utility is proposed, which effectively reduces the search space for top-k average utility co-location pattern mining, and further improves the efficiency of the mining algorithm. Finally, the practicability, efficiency and robustness of the proposed algorithm are verified on real and synthetic datasets.

Key words: spatial co-location pattern, high-average utility, fuzzy feature, top-k

中图分类号:

TP391
TP311

李金红, 王丽珍, 周丽华. 模糊特征的top-k平均效用co-location模式挖掘[J]. 计算机科学与探索, 2022, 16(5): 1053-1063.

LI Jinhong, WANG Lizhen, ZHOU Lihua. Top-k Average Utility Co-location Pattern Mining of Fuzzy Features[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(5): 1053-1063.

图/表 13

图1 空间模糊特征及其实例分布示例

Fig.1 Example of spatial fuzzy features and instances

表1 图1的空间数据集的星型邻居

Table 1 Star neighborhoods of spatial dataset in Fig.1

序号	实例	邻居实例
T₁	[A1,0.2]	[B2,0.5],[E3,0.7]
T₂	[A2,0.4]	[B2,0.5],[C2,0.4],[E3,0.7]
T₃	[A3,0.5]	[B3,0.7],[C3,0.8],[C4,0.9], [D1,0.3],[E2,0.5]
T₄	[A4,0.8]	[B4,0.9],[E1,0.2]
T₅	[A5,0.7]	[C5,0.5],[D3,0.6]
T₆	[B1,0.3]	[D2,0.8]
T₇	[B2,0.5]	[C2,0.4],[D2,0.8],[E3,0.7]
T₈	[B3,0.7]	[C3,0.8],[C4,0.9]
T₉	[B4,0.9]	[E1,0.2]
T₁₀	[C3,0.8]	[D1,0.3],[E2,0.5]
T₁₁	[D1,0.3]	[E2,0.5]
T₁₂	[D2,0.8]	[E3,0.7]

图2 空间模糊特征 C及其实例分布示例

Fig.2 Example of spatial fuzzy feature C and its instances

表2 图1中5个模糊特征的外部效用

Table 2 External utility of 5 fuzzy features in Fig.1

模糊特征	外部效用
$A$	5
$B$	4
$C$	3
$D$	1
$E$	2

表2 图1中5个模糊特征的外部效用

Table 2 External utility of 5 fuzzy features in Fig.1

模糊特征	外部效用
$A$	5
$B$	4
$C$	3
$D$	1
$E$	2

表3 图1的空间数据集的星型邻居的最大模糊效用

Table 3 Maximum fuzzy utility of star neighborhood of spatial dataset in Fig.1

序号	实例	邻居实例	ftwu
T₁	[A1,0.2]	[B2,0.5],[E3,0.7]	2.0
T₂	[A2,0.4]	[B2,0.5],[C2,0.4],[E3,0.7]	2.0
T₃	[A3,0.5]	[B3,0.7],[C3,0.8],[C4,0.9],[D1,0.3],[E2,0.5]	5.1
T₄	[A4,0.8]	[B4,0.9],[E1,0.2]	4.0
T₅	[A5,0.7]	[C5,0.5],[D3,0.6]	3.5
T₆	[B1,0.3]	[D2,0.8]	1.2
T₇	[B2,0.5]	[C2,0.4],[D2,0.8],[E3,0.7]	2.0
T₈	[B3,0.7]	[C3,0.8],[C4,0.9]	5.1
T₉	[B4,0.9]	[E1,0.2]	3.6
T₁₀	[C3,0.8]	[D1,0.3],[E2,0.5]	2.4
T₁₁	[D1,0.3]	[E2,0.5]	1.0
T₁₂	[D2,0.8]	[E3,0.7]	1.4

图3 真实数据集数据分布

Fig.3 Distribution of real dataset

图4 真实数据中距离阈值d对候选模式数量的影响

Fig.4 Effect of d on the number of candidate patterns in real data

图5 真实数据中距离阈值 d对运行时间的影响

Fig.5 Effect of d on running time in real data

图6 真实数据中模式阶数对候选模式数量的影响

Fig.6 Effect of pattern size on the number of candidate patterns in real data

图7 合成数据中实例数量对候选模式数量的影响

Fig.7 Effect of the number of instances on the number of candidate patterns in synthetic data

图8 合成数据中实例数量对运行时间的影响

Fig.8 Effect of the number of instances on running time in synthetic data

图9 合成数据中特征数量对候选模式数量的影响

Fig.9 Effect of the number of features on the number of candidate patterns in synthetic data

图10 合成数据中特征数量对运行时间的影响

Fig.10 Effect of the number of features on running time in synthetic data

参考文献 21

[1]	SHEKHAR S, HUANG Y. Discovering spatial co-location patterns: a summary of results[C]// LNCS 2121: Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, Redondo Beach, Jul 12-15, 2001.Berlin, Heidelberg: Springer, 2001: 236-256.
[2]	HUANG Y, SHEKHAR S, XIONG H. Discovering coloca-tion patterns from spatial data sets: a general approach[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(12): 1472-1485. DOI URL
[3]	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 Geogra-phic Information Systems, Washington, Nov 12-13, 2004. New York: ACM, 2004: 241-249.
[4]	YOO J S, SHEKHAR S, CELIK M. A join-less approach for co-location pattern mining: a summary of results[C]// Procee-dings of the 2005 IEEE International Conference on Data Mining, Houston, Nov 27-30, 2005. Washington: IEEE Com-puter Society, 2005: 813-816.
[5]	BAO X G, WANG L Z. A clique-based approach for co-location pattern mining[J]. Information Sciences, 2019, 490: 244-264. DOI URL
[6]	WANG L Z, BAO X G, ZHOU L H, et al. Mining maximal sub-prevalent co-location patterns[J]. World Wide Web, 2019, 22(5): 1971-1997. DOI URL
[7]	YANG S S, WANG L Z, BAO X G. A framework for mining spatial high utility co-location patterns[C]// Proceedings of the 12th International Conference on Fuzzy Systems and Know-ledge Discovery, Zhangjiajie, Aug 15-17, 2015. Piscataway: IEEE, 2015: 595-601.
[8]	WANG L Z, JIANG W G, CHEN H M. Efficiently mining high utility co-location patterns from spatial data sets with instance specific utilities[C]// LNCS 10178: Proceedings of the 2017 International Conference on Database Systems for Advanced Applications, Suzhou, Mar 27-30, 2017. Cham: Springer, 2017: 458-474.
[9]	王晓璇, 王丽珍, 陈红梅, 等. 基于特征效用参与率的空间高效用co-location模式挖掘方法[J]. 计算机学报, 2019, 42(8): 1721-1738.
	WANG X X, WANG L Z, CHEN H M, et al. Mining spatial high utility co-location patterns based on feature utility ratio[J]. Chinese Journal of Computers, 2019, 42(8): 1721-1738.
[10]	YOO J S, BOW M. Mining top-k closed co-location patterns[C]// Proceedings of the 2011 IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services, Fuzhou, Jun 29-Jul 1, 2011. Piscataway: IEEE, 2011: 100-105.
[11]	WANG L Z, HAN J, CHEN H. Top-k probabilistic prevalent co-location mining in spatially uncertain data sets[J]. China Computer Science Frontier, 2016, 10(3): 488-503.
[12]	欧阳志平, 王丽珍, 陈红梅. 模糊对象的空间Co-location模式挖掘研究[J]. 计算机学报, 2011, 34(10): 1947-1955.
	OUYANG Z P, WANG L Z, CHEN H M. Mining spatial Co-location patterns for fuzzy objects[J]. Chinese Journal of Computers, 2011, 34(10): 1947-1955. DOI URL
[13]	YAO H, HAMILTON H J, BUTZ C J. A foundational app-roach to mining itemset utilities from databases[C]// Procee-dings of the 4th SIAM International Conference on Data Mining, Lake Buena Vista, Apr 22-24, 2004. Philadelphia: SIAM, 2004: 211-255.
[14]	AHMED C F, TANBEER S K, JEONG B S. Efficient tree structures for high utility pattern mining in incremental data-bases[J]. IEEE Transactions on Knowledge and Data Engin-eering, 2009, 21(12): 1708-1721.
[15]	TSENG V S, WU C, SHIE B E. UP-Growth: an efficient algorithm for high utility itemsets mining[C]// Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, Jul 25-28, 2010. New York: ACM, 2010: 253-262.
[16]	WU C, SHIE B E, TSENG V S. Mining top-k high utility itemsets[C]// Proceedings of the 18th ACM SIGKDD Con-ference on Knowledge Discovery and Data Mining, Beijing, Aug, 2012. New York: ACM, 2012: 78-86.
[17]	RYANG H, YUN U. Top-k high utility pattern mining with effective threshold raising strategies[J]. Knowledge-Based Systems, 2015, 76: 109-126. DOI URL
[18]	CHEN Y B, WANG L Z, WANG J L. Basic and optimiza-tion algorithms for mining high utility co-location patterns from fuzzy datasets[C]// Proceedings of the 4th International Conference on Fuzzy Systems and Data Mining, Bangkok, Nov 16-19, 2018. Amsterdam: IOS, 2018: 343-350.
[19]	HONG T P, LEE C H, WANG S L. Mining high average utility itemsets[C]// Proceedings of the 2009 IEEE Interna-tional Conference on Systems, Man and Cybernetics, San Antonio, Oct 11-14, 2009. Piscataway: IEEE, 2009: 2526-2530.
[20]	LIN C W, HONG T P, LU W H. Efficiently mining high average utility itemsets with a tree structure[C]// LNCS 5990: Proceedings of the 2nd International Conference on Intelligent Information and Database Systems, Hue City, Mar 24-26, 2010. Berlin, Heidelberg: Springer, 2010: 131-139.
[21]	LAN G C, HONG T P, TSENG V S. Efficiently mining high average-utility itemsets with an improved upper-bound strategy[J]. International Journal of Information Technology and Decision Making, 2012, 11(5): 1009-1030.

模糊特征的top-k平均效用co-location模式挖掘

Top-k Average Utility Co-location Pattern Mining of Fuzzy Features

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 21

相关文章 2

编辑推荐

Metrics

[1]	王光耀, 王丽珍, 杨培忠, 陈红梅. 极小负co-location模式及有效的挖掘算法[J]. 计算机科学与探索, 2021, 15(2): 366-378.
[2]	吴萍萍，王丽珍，周永恒. 带模糊属性的空间Co-Location模式挖掘研究[J]. 计算机科学与探索, 2013, 7(4): 348-358.