面向不确定数据模式指标的通用界值估算方法

doi:10.11772/j.issn.1001-9081.2017061582

计算机应用 ›› 2018, Vol. 38 ›› Issue (1): 165-170.DOI: 10.11772/j.issn.1001-9081.2017061582

面向不确定数据模式指标的通用界值估算方法

王菊¹, 刘付显¹, 靳春杰²

1. 空军工程大学防空反导学院, 西安 710051;
2. 93527部队, 河北张家口 075000

收稿日期:2017-06-26 修回日期:2017-08-21 出版日期:2018-01-10 发布日期:2018-01-22
通讯作者: 王菊
作者简介:王菊(1991-),女,内蒙古临河人,博士研究生,主要研究方向:数据挖掘、模式识别;刘付显(1962-),男,山东菏泽人,教授,博士,主要研究方向:作战仿真、数据挖掘;靳春杰(1989-),男,天津北辰人,助理工程师,主要研究方向:数据挖掘、模式识别。

General bound estimation method for pattern measures over uncertain datasets

WANG Ju¹, LIU Fuxian¹, JIN Chunjie²

1. College of Air and Missile Defense, Air Force Engineering University, Xi'an Shaanxi 710051, China;
2. Unit 93527, Zhangjiakou Hebei 075000, China

Received:2017-06-26 Revised:2017-08-21 Online:2018-01-10 Published:2018-01-22

摘要/Abstract

摘要： 针对约束模式挖掘中模式指标的界值估算问题，提出了一种面向不确定数据模式指标的通用界值估算方法。根据带有权值的不确定型事务数据库的特点，首先设计了面向常用模式指标的通用界值估算框架，其次给出了在该框架下对模式指标上界值的快速估算方法，最后估计了两种典型模式指标的上界值以说明其可行性。实验中对比了PHUI-UP算法分别结合事务加权效用值、所提方法估算所得的上界值和实际上界值后的运行时间和内存占用情况，实验结果表明所提方法可以通过占用较小内存和运行时间来实现模式效用上界值的估算。

关键词: 不确定数据库, 模式指标, 界值估算, 约束模式挖掘, 通用估算框架

Abstract: Concerning the problem of bound estimation for pattern measures in constraint-based pattern mining, a general bound estimation method for pattern measures over uncertain datasets was proposed. According to the characteristics of uncertain transaction datasets with weight, firstly, a general estimation framework for common pattern measures was designed. Secondly, a fast estimation method for the upper bound of pattern measures under the designed framework was provided. Finally, two commonly used pattern measures were introduced to verify the feasibility of the proposed method. In the experiment, the runtime and memory usage of the Potential High-Utility Itemsets UPper-bound-based mining (PHUI-UP) algorithm with transaction weighted utilization, the proposed upper bound and the actual upper bound were compared. The experimental results show that the proposed method can take less memory usage and runtime to realize the estimation of the upper bound of pattern utilization.

Key words: uncertain dataset, pattern measure, bound estimation, constraint-based pattern mining, general estimation framework

中图分类号:

王菊, 刘付显, 靳春杰. 面向不确定数据模式指标的通用界值估算方法[J]. 计算机应用, 2018, 38(1): 165-170.

WANG Ju, LIU Fuxian, JIN Chunjie. General bound estimation method for pattern measures over uncertain datasets[J]. Journal of Computer Applications, 2018, 38(1): 165-170.

参考文献

[1] ZHU F, ZHANG Z, QU Q. A direct mining approach to efficient constrained graph pattern discovery[C]//SIGMOD 2013:Proceedings of the 2013 Special Interest Group on Management of Data. New York:ACM, 2013:821-832.
[2] GUNS T, NIJSSEN S, RAEDT L. K-pattern set mining under constraints[J]. IEEE Transaction on Knowledge and Data Engineering, 2013, 25(2):402-418.
[3] ZENG X, PEI J, WANG K, et al. PADS:a simple yet effective pattern-aware dynamic search method for fast maximal frequent pattern mining[J]. Knowledge and Information Systems, 2009, 20(3):243-252.
[4] GAO L. Domain-driven data mining:challenges and prospects[J]. IEEE Transaction on Knowledge and Data Engineering, 2010, 22(6):755-769.
[5] AGRAWAL R, IMIELINSKI T, SWAMI A. Mining association rules between sets of items in large databases[C]//SIGMOD' 93:Proceedings of the 1993 ACM Special Interest Group on Management of Data. New York:ACM, 1993:207-216.
[6] BONCHIA F, GIANNOTTIB F, LUCCHESB C, et al. A constraint-based querying system for exploratory pattern discovery[J]. Information Systems, 2009, 34(1):3-27.
[7] YAO H, HAMMILTON H J, BUTZ C J. A foundational approach to mining itemset utilities from databases[C]//SDM 2004:Proceedings of the 2004 Siam International Conference on Data mining. New York:ACM, 2004:482-486.
[8] WU C, SHIE B, TSENG V, et al. Mining top-K high utility itemsets[C]//KDD 2012:Proceedings of the 2012 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2012:78-86.
[9] TANG L, ZHANG L, LUO P, et al. Incorporating occupancy into frequent pattern mining for high quality pattern recommendation[C]//Proceedings of the 2013 ACM International Conference on Information and Knowledge Management. New York:ACM, 2013:75-84.
[10] YUN U. Efficient mining of weighted interesting patterns with a strong weight and/or support affinity[J]. Information Sciences, 2007, 177(17):213-241.
[11] 张磊.基于约束的频繁模式挖掘方法[D].合肥:中国科学技术大学,2014:73-116.(ZHANG L. Constraint-based frequent pattern mining:novel applications and new techniques[D]. Hefei:University of Science and Technology of China, 2014:73-116.)
[12] GREEN T, TANNEN V. Models for incomplete and probabilistic information[C]//Proceedings of the 2006 IEEE International Conference on Extending Database Technology. Piscataway, NJ:IEEE, 2006:278-296.
[13] LIN C W, HONG T P, LU W H. An effective tree structure for mining high utility itemsets[J]. Expert Systems with Applications, 2011, 38(6):7419-7424.
[14] LIU M, QU J. Mining high utility itemsets without candidate generation[C]//KDD 2012:Proceedings of the 2012 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2012:78-86.
[15] LIU Y, LIAO W, CHOUDHARY A. A two-phase algorithm for fast discovery of high utility itemsets[C]//Proceedings of the 2005 Pacific-Asia Conference on Knowledge Discovery and Data Mining. New York:ACM, 2005:689-695. WANG Ju, born in 1991, Ph. D. candidate. Her research interests include data mining, pattern recognition.LUI Fuxian, born in 1962, Ph. D., professor. His research interests include simulation of warfare, data mining.JIN Chunjie, born in 1989, assistant engineer. His research interests include data mining, pattern recognition.

面向不确定数据模式指标的通用界值估算方法

General bound estimation method for pattern measures over uncertain datasets

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics