最大模糊频繁模式挖掘算法

doi:10.11772/j.issn.1001-9081.2017.05.1424

计算机应用 ›› 2017, Vol. 37 ›› Issue (5): 1424-1429.DOI: 10.11772/j.issn.1001-9081.2017.05.1424

最大模糊频繁模式挖掘算法

张海清¹, 李代伟¹, 刘胤田¹, 龚程¹, 于曦²

1. 成都信息工程大学软件工程学院, 成都 610225;
2. 成都大学信息科学与工程学院, 成都 610106

收稿日期:2016-10-08 修回日期:2016-12-23 发布日期:2017-05-16 出版日期:2017-05-10
通讯作者: 于曦
作者简介:张海清(1986-),女,山东聊城人,讲师,博士研究生,主要研究方向:大数据分析;李代伟(1976-),男,四川达县人,副教授,硕士研究生,主要研究方向:数据集成与可视化、机器学习;刘胤田(1972-),男,四川隆昌人,教授,博士研究生,主要研究方向:数据挖掘;于曦(1973-)男,吉林长春人,副教授,博士研究生,主要研究方向:决策系统、神经网络。
基金资助:
国家自然科学基金青年基金资助项目（61602064，61502059）；成都信息工程大学科研基金资助项目（KYTZ201615）。

Mining algorithm of maximal fuzzy frequent patterns

ZHANG Haiqing¹, LI Daiwei¹, LIU Yintian¹, GONG Cheng¹, YU Xi²

1. College of Software Engineering, Chengdu University of Information Technology, Chengdu Sichuan 610225, China;
2. College of Information Science and Engineering, Chengdu University, Chengdu Sichuan 610106, China

Received:2016-10-08 Revised:2016-12-23 Online:2017-05-16 Published:2017-05-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61602064, 61502059), the Scientific Research Foundation of Chengdu University of Information Technology (KYTZ201615).

摘要/Abstract

摘要： 针对有效模式挖掘的组合爆炸及挖掘结果信息如何有效表达的问题，提出了一种基于“核心-牵引”结构的修剪候选模式和考虑项目不确定性的最大模糊模式挖掘算法（MFFP-Tree）。首先，综合分析项目的模糊性，提出模糊支持度，分析项目在事务数据集中的模糊权重，依据模糊修剪策略修剪候选项集；其次，仅扫描数据集一次，就能成功构建模糊模式挖掘树，依据模糊剪枝策略减少模式提取的开销，采用FFP-array阵列结构使得搜索方式更精简，从而进一步降低时空开销。根据基准数据集的实验结果，与最大模式挖掘算法PADS和FPMax^*对比分析，MFFP-Tree挖掘出的最大模糊模式能够更准确地反映项目与项目之间的关系；算法的时间复杂度能减半甚至低1个数量级；算法的空间复杂度降低1~2个数量级。

关键词: 高级模式挖掘, 最大模糊模式, 模糊支持度, 核心-牵引模式结构, 模糊修剪策略

Abstract: Combinatorial explosion and the effectiveness of mining results are the essential challenges of meaningful pattern extraction, a Maximal Fuzzy Frequent Pattern Tree Algorithm (MFFP-Tree) based on base-(second-order-effect) pattern structure and uncertainty consideration of items was proposed. Firstly, the fuzziness of items was analyzed comprehensively, the fuzzy support was given, and the fuzzy weight of items in the transaction data set was analyzed, the candidate item set was trimmed according to the fuzzy pruning strategy. Secondly, the database was scanned once to build FFP-Tree, and the overhead of pattern extraction was reduced based on fuzzy pruning strategy. The FFP-array structure was used to streamline the search method to further reduce the space and time complexity. The experimental results gained from the benchmark datasets reveal that the proposed MFFP-Tree has outstanding performance by comparing with PADS and FPMax^* algorithms:the time complexity of the proposed algorithm is optimized by twice to one order of magnitude for different datasets, and the spatial complexity of the proposed algorithm is optimized by one order of magnitude to two orders of magnitude, respectively.

Key words: advanced pattern mining, maximum fuzzy pattern, fuzzy support, base-(second-order-effect) pattern structure, fuzzy pruning strategy

中图分类号:

TP311.1

张海清, 李代伟, 刘胤田, 龚程, 于曦. 最大模糊频繁模式挖掘算法[J]. 计算机应用, 2017, 37(5): 1424-1429.

ZHANG Haiqing, LI Daiwei, LIU Yintian, GONG Cheng, YU Xi. Mining algorithm of maximal fuzzy frequent patterns[J]. Journal of Computer Applications, 2017, 37(5): 1424-1429.

参考文献

[1] AGRAWAL R, IMIELINSKI T, SWAMI A. Mining association rules between sets of items in large databases[J].ACM SIGMOD Record, 1993, 22(2):207-216.
[2] HAN J, PEI J, YIN Y, et al. Mining frequent patterns without candidate generation:a frequent-pattern tree approach[J]. Data Mining and Knowledge Discovery, 2004, 8(1):53-87.
[3] TSENG V S, SHIE B E, WU C W, et al. Efficient algorithms for mining high utility itemsets from transactional databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(8):1772-1786.
[4] GRAHNE G, ZHU J. Fast algorithms for frequent itemset mining using FP-trees[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(10):1347-1362.
[5] 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):375-391.
[6] MUZAMMAL M, RAMAN R. Mining sequential patterns from probabilistic databases[C]//Proceedings of the 2011 Pacific-Asia Conference on Knowledge Discovery and Data Mining. Berlin:Springer, 2011:210-221.
[7] AGGARWAL C, HAN J. Frequent Pattern Mining[M]. Berlin:Springer, 2014:19-61.
[8] ZHANG X, ZHANG Y. Sliding-window top-k pattern mining on uncertain streams[J]. Journal of Computational Information Systems, 2011, 7(3):984-992.
[9] 杨皓, 段磊, 胡斌, 等. 带间隔约束的Top-k 对比序列模式挖掘[J]. 软件学报, 2015, 26(11):2994-3009.(YANG H, DUAN L, HU B, et al. Mining Top-k distinguishing sequential patterns with gap constraint[J]. Journal of Software, 2015, 26(11):2994-3009.)
[10] CHEN H. Mining top-k frequent patterns over data streams sliding window[J]. Journal of Intelligent Information Systems, 2014, 42(1):111-131.
[11] ZIHAYAT M, AN A. Mining top-k high utility patterns over data streams[J]. Information Sciences, 2014, 285(1):138-161.
[12] YUN U, LEE G. Sliding window based weighted erasable stream pattern mining for stream data applications[J]. Future Generation Computer Systems, 2016, 59(C):1-20.
[13] LI T. Fuzziness in systems modelling[J]. International Journal of General Systems, 2013, 42(1):1-2.
[14] CHEN H, LI T, LUO C, et al. A decision-theoretic rough set approach for dynamic data mining[J]. IEEE Transactions on Fuzzy Systems, 2015, 23(6):1958-1970.
[15] 牛新征, 余堃. 基于FPMAX的最大频繁项目集挖掘改进算法[J]. 计算机科学, 2013, 40(12): 223-228.(NIU X Z, SHE K. Mining maximal frequent item sets with improved algorithm of FPMAX [J]. Computer Science, 2013, 40(12): 223-228.)

最大模糊频繁模式挖掘算法

Mining algorithm of maximal fuzzy frequent patterns

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	高威刘丽华和斌涛邓方安. 区块链共识机制与改进算法研究进展[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	翟社平朱鹏举杨锐刘佳一腾. 基于区块链的物联网身份管理系统[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[3]	李博, 黄建强, 黄东强, 王晓英. 基于异构平台的稀疏矩阵向量乘自适应计算优化[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3867-3875.
[4]	陈姿芊, 牛科迪, 姚中原, 斯雪明. 适用于物联网的区块链轻量化技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3688-3698.
[5]	高婷婷, 姚中原, 贾淼, 斯雪明. 链上链下一致性保护技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3658-3668.
[6]	贾淼, 姚中原, 祝卫华, 高婷婷, 斯雪明, 邓翔. 零知识证明赋能区块链的进展与展望[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3669-3677.
[7]	牛科迪, 李敏, 姚中原, 斯雪明. 面向物联网的区块链共识算法综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3678-3687.
[8]	杨巍白璐宁俊义董建军单春海信俊昌. 异构环境感知的幂律图流划分方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[9]	秦学程刘春颜李宝赵蕴龙. 面向工业场景的云边协同数据存储与检索架构[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	涂进兴, 李志雄, 黄建强. 基于GPU对角稀疏矩阵向量乘法的动态划分算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3521-3529.
[11]	孙鉴, 马宝全, 吴隹伟, 杨晓焕, 武涛, 陈攀. 地震场景下无人机群路径规划与任务分配均衡联合优化[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3232-3239.
[12]	蒋辉, 闫秋艳, 姜竹郡. 面向多元时间序列异常检测的对称正定自编码器方法[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3294-3299.
[13]	李源, 林秋兰, 陈安之, 杨国利, 宋威, 王国仁. 基于树分解的时序最短路径计数查询算法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2446-2454.
[14]	田润泽, 周宇龙, 朱洪, 薛岗. 基于局部信息的服务迁移路径选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2168-2174.
[15]	宋洪涛, 于江生, 韩启龙. 工业多元时序数据质量评估方法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1743-1750.