Improved frequent itemset mining algorithm based on interval list

doi:10.11772/j.issn.1001-9081.2016.04.0997

Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (4): 997-1001.DOI: 10.11772/j.issn.1001-9081.2016.04.0997

Previous Articles Next Articles

Improved frequent itemset mining algorithm based on interval list

XU Yongxiu¹, LIU Xumin¹, XU Weixiang²

1. College of Information Engineering, Capital Normal University, Beijing 100048, China;
2. College of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China

Received:2015-09-25 Revised:2015-11-23 Online:2016-04-08 Published:2016-04-10
Supported by:
This work is supported by the National Natural Science Foundation of China (61272029).

基于间隔链表改进的频繁项集挖掘算法

徐永秀¹, 刘旭敏¹, 徐维祥²

1. 首都师范大学信息工程学院, 北京 100048;
2. 北京交通大学交通运输学院, 北京 100044

通讯作者: 徐永秀
作者简介:徐永秀(1991-),女,山东潍坊人,硕士研究生,主要研究方向:数据挖掘; 刘旭敏(1956-),女,辽宁锦州人,教授,博士,主要研究方向:计算机辅助几何设计、图形图像处理、数据挖掘; 徐维祥(1956-),男,辽宁锦州人,教授,博士,主要研究方向:数据挖掘、交通运输系统分析集成、云计算。
基金资助:
国家自然科学基金资助项目(61272029)。

Abstract

Abstract: Focusing on the problem that PrePost algorithm needs to build complex Pre-order and Post-order Code tree (PPC-tree) and Node list (N-list), an improved frequent itemset mining algorithm based on the Interval list (I-list) was proposed. Firstly, data storage structure with more compression compared to Frequent Pattern tree (FP-tree), called Interval FP-tree (IFP-tree), was adopted, which mined frequent itemsets without iteratively establishing conditional tree. Secondly, the more concise method called I-list was used to replace the complex N-list in PrePost so as to improve mining speed. Finally, in the case of single branch path, some frequent itemsets were directly obtained by the method of combination. The experimental results prove the correctness of the proposed algorithm by getting the same results for the same dataset under same minimum supports, the proposed algorithm is superior to PrePost algorithm by about 10 percent in terms of time and space which has a good application in sparse database or intensive database.

Key words: data mining, association rule, frequent itemset, Frequent Pattern tree (FP-tree), Interval list (I-list)

摘要： 针对PrePost算法中需要建立复杂的前序和后序编码树(PPC-tree)和节点链表(N-list)的问题,提出一种基于间隔链表(I-list)改进的高效频繁项集挖掘算法。首先,该算法采用了比频繁模模式树(FP-tree)更加压缩的数据存储结构间隔编码的频繁模式树(IFP-tree),无需迭代地建立条件FP-tree;其次,该算法利用更简洁的I-list代替了PrePost中复杂的N-list,从而提高了建树和挖掘速度;最后,对于单分支路径的情况,该算法通过组合的方法,直接求得某些频繁项集,以提高算法的时间性能。实验结果表明:一方面,对于同一数据集在相同支持数下挖掘的结果相同,验证了改进算法的正确性;另一方面,无论在时间还是空间上改进算法的整体性能均比PrePost算法提高约10%;且对于稀疏型数据库或密集型数据库的挖掘都有较好的应用。

关键词: 数据挖掘, 关联规则, 频繁项集, 频繁模式树, 间隔链表

CLC Number:

TP311.13

XU Yongxiu, LIU Xumin, XU Weixiang. Improved frequent itemset mining algorithm based on interval list[J]. Journal of Computer Applications, 2016, 36(4): 997-1001.

徐永秀, 刘旭敏, 徐维祥. 基于间隔链表改进的频繁项集挖掘算法[J]. 计算机应用, 2016, 36(4): 997-1001.

References

[1] AGRAWAL R, IMIEILNSKI T, SWAMI A. Mining association rules between sets of items in large databases[C]//Proceedings of 1993 ACM SIGMOD Conference on Management Data. New York:ACM, 1993:207-216.
[2] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules[C]//VLDB 1994:Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco:Morgan Kaufmann Publishers, 1994:487-499.
[3] LIN K C, LIAO I E, CHEN Z S. An improved frequent pattern growth method for mining association rules[J]. Expert Systems with Applications, 2011, 38(5):5154-5161.
[4] GUPTA R, SATSANGI C S. An efficient range partitioning method for finding frequent patterns from huge database[J]. International Journal of Advanced Computer Research, 2012, 2(2):62-69.
[5] 李也白, 唐辉, 贺玉明.基于改进的FP-tree的频繁模式挖掘算法[J]. 计算机应用, 2011,31(1):101-103.(LI Y B, TANG H, HE Y M. Frequent pattern mining algorithm based on improved FP-tree[J]. Journal of Computer Applications, 2011,31(1):101-103.)
[6] SUCAHYO Y G, GOPALAN R P. CT-PRO:a bottom-up non recursive frequent itemset mining algorithm using compressed FP-tree data structure[C]//FIMI 2004:Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations. Piscataway, NJ:IEEE, 2004:212-223.
[7] ZAKI M J, GOUDA K. Fast vertical mining using diffsets[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data mining. New York:ACM, 2003:326-335.
[8] LI Z F, LIU X F, CAO X. A study on improved Eclat data mining algorithm[J]. Advanced Materials Research, 2011, 328/329/330:1896-1899.
[9] DENG Z H, WANG Z H, JIANG J J. A new algorithm for fast mining frequent itemsets using N-lists[J]. Science China Information Sciences, 2012, 55(9):2008-2030.
[10] LIN K C, LIAO I E, CHANG T P. A frequent itemset mining algorithm based on the principle of inclusion-exclusion and transaction mapping[J]. Information Sciences, 2014, 276:278-289.
[11] VO B, LE T, COENEN F. Mining frequent itemsets using the n-list and subsume concepts[C]//Proceedings of the 2013 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway, NJ:IEEE, 2014:1-13.
[12] GOETHALS B, ZAKI M. Frequent itemset mining implementations repository[EB/OL].[2015-02-20] http://fimi.ua.ac.be/data/.

[1]	Huanhuan LI, Tianqiang HUANG, Xuemei DING, Haifeng LUO, Liqing HUANG. Public traffic demand prediction based on multi-scale spatial-temporal graph convolutional network [J]. Journal of Computer Applications, 2024, 44(7): 2065-2072.
[2]	Yao DONG, Yixue FU, Yongfeng DONG, Jin SHI, Chen CHEN. Survey of incomplete multi-view clustering [J]. Journal of Computer Applications, 2024, 44(6): 1673-1682.
[3]	Keshuai YANG, Youxi WU, Meng GENG, Jingyu LIU, Yan LI. Top-k high average utility sequential pattern mining algorithm under one-off condition [J]. Journal of Computer Applications, 2024, 44(2): 477-484.
[4]	Haodong ZHENG, Hua MA, Yingchao XIE, Wensheng TANG. Knowledge tracing model based on graph neural network blending with forgetting factors and memory gate [J]. Journal of Computer Applications, 2023, 43(9): 2747-2752.
[5]	Shuo HUANG, Yanhui LI, Jianqiu CAO. PrivSPM： frequent sequential pattern mining algorithm under local differential privacy [J]. Journal of Computer Applications, 2023, 43(7): 2057-2064.
[6]	Hua JIANG, Xing LI, Huijiao WANG, Jinghai WEI. Cross-level high utility itemsets mining algorithm based on data index structure [J]. Journal of Computer Applications, 2023, 43(7): 2200-2208.
[7]	Chaoshuai QI, Wensi HE, Yi JIAO, Yinghong MA, Wei CAI, Suping REN. Survey on anomaly detection algorithms for unmanned aerial vehicle flight data [J]. Journal of Computer Applications, 2023, 43(6): 1833-1841.
[8]	Yuanjiang LI, Jinsheng QUAN, Yangyi TAN, Tian YANG. Attribute reduction for high-dimensional data based on bi-view of similarity and difference [J]. Journal of Computer Applications, 2023, 43(5): 1467-1472.
[9]	Xiaomeng SHAO, Meng ZHANG. Temporal convolutional knowledge tracing model with attention mechanism [J]. Journal of Computer Applications, 2023, 43(2): 343-348.
[10]	Yaling XUN, Linqing WANG, Jianghui CAI, Haifeng YANG. Partial periodic pattern incremental mining of time series data based on multi-scale [J]. Journal of Computer Applications, 2023, 43(2): 391-397.
[11]	Wenquan LI, Yimin MAO, Xindong PENG. Agglomerative hierarchical clustering algorithm based on hesitant fuzzy set [J]. Journal of Computer Applications, 2023, 43(12): 3755-3763.
[12]	LI Xingjia, YANG Qiuhui, HONG Mei, PAN Chunxia, LIU Ruihang. Test case prioritization approach based on historical data and multi-objective optimization [J]. Journal of Computer Applications, 2023, 43(1): 221-226.
[13]	Jun WU, Aijia OUYANG, Lin ZHANG. Statistically significant sequential patterns mining algorithm under influence degree [J]. Journal of Computer Applications, 2022, 42(9): 2713-2721.
[14]	Shunkun YU, Hongxu YAN. Heuristic attribute value reduction model based on certainty factor [J]. Journal of Computer Applications, 2022, 42(2): 469-474.
[15]	LIU Shize, QIN Yanjun, WANG Chenxing, SU Lin, KE Qixue, LUO Haiyong, SUN Yi, WANG Baohui. Traffic flow prediction algorithm based on deep residual long short-term memory network [J]. Journal of Computer Applications, 2021, 41(6): 1566-1572.

Improved frequent itemset mining algorithm based on interval list

基于间隔链表改进的频繁项集挖掘算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics