[1] Zhang Liang, Ren Yonggong, Fu Yu,. New algorithm of mining frequent closed itemsets [J]. Journal of Southeast University (English Edition), 2008, 24 (3): 335-338. [doi:10.3969/j.issn.1003-7985.2008.03.020]
Copy
New algorithm of mining frequent closed itemsets(
)
一种新的频繁闭项目集挖掘算法
)Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]
- Volumn:
- 24
- Issue:
- 2008 3
- Page:
- 335-338
- Research Field:
- Computer Science and Engineering
- Publishing date:
- 2008-09-30
Info
- Title:
- New algorithm of mining frequent closed itemsets
- 一种新的频繁闭项目集挖掘算法
- Author(s):
- Zhang Liang; Ren Yonggong; Fu Yu
- School of Computer and Information Technology, Liaoning Normal University, Dalian 116029, China
- Keywords:
- frequent itemsets; frequent closed itemsets; minimum frequent closed itemsets; maximal frequent closed itemsets; frequent closed pattern tree
- PACS:
- TP311.13
- DOI:
- 10.3969/j.issn.1003-7985.2008.03.020
- Abstract:
- A new algorithm based on an FC-tree(frequent closed pattern tree)and a max-FCIA(maximal frequent closed itemsets algorithm)is presented, which is used to mine the frequent closed itemsets for solving memory and time consuming problems. This algorithm maps the transaction database by using a Hash table, gets the support of all frequent itemsets through operating the Hash table and forms a lexicographic subset tree including the frequent itemsets.Efficient pruning methods are used to get the FC-tree including all the minimum frequent closed itemsets through processing the lexicographic subset tree.Finally, frequent closed itemsets are generated from minimum frequent closed itemsets.The experimental results show that the mapping transaction database is introduced in the algorithm to reduce time consumption and to improve the efficiency of the program.Furthermore, the effective pruning strategy restrains the number of candidates, which saves space.The results show that the algorithm is effective.
- 为了解决频繁闭项目集挖掘中时间和存储开销大的问题, 提出了一种基于FC-tree(频繁闭模式树)的频繁闭项目集挖掘算法max-FCIA(最大频繁闭项目集挖掘算法).该算法利用哈希表映射事务数据库, 通过对哈希表进行操作从而得到所有频繁项目集的支持度, 进而生成包含所有频繁项目的有序树.经过剪枝处理的有序树就是包含所有最小频繁闭项目集的FC-tree, 最后用最小频繁闭项目集生成频繁闭项目集.实验结果表明, 该算法通过映射事务数据库, 减少了扫描数据库所浪费的时间, 提高程序执行效率.另外, 运用有效的剪枝策略, 避免了不必要候选项目集的生成, 节省了存储空间, 实验证明该算法是有效的.
References:
[1] Pasquier N, Bastide Y, Taouil R, et al.Discovering frequent closed itemsets for association rules[C]//Proc of the 7th Intl Conf on Database Theory.Springer-Verlag, 1999:398-416.
[2] Burdick D, Calimlim M, Gehrke J.MAFIA:a maximal frequent itemset algorithm[J].IEEE Transactions on Knowledge and Data Engineering, 2005, 17(11):1490-1504.
[3] Zaki M J, Hsiao C J.CHARM:an efficient algorithm for closed itemset mining[C]//Proc of the 2nd SIAM Intl Conf on Data Mining.Arlington:SIAM, 2002:12-28.
[4] Wang Jianyong, Han Jiawei, Pei Jian.Closet+:searching for the best strategies for mining frequent closed itemsets[C]//Proc of ACM SIGKDD’03.Washington, DC, 2003:236-245.
[5] Grahne G, Zhu J.Efficiently using prefix-trees in mining frequent itemsets [C]//Proc of the IEEE ICDM Workshop on Frequent Itemset Mining Implementation (FIMI’03).Melbourne, Florida, USA, 2003.
[6] Yahia S B, Hamrouni T, Nguifo E M.Frequent closed itemset based algorithms:a thorough structural and analytical survey[J].SIGKDD Explorations, 2006, 8(1):93-104.
[7] Zhu Yuquan, Song Yuqing.Research on an algorithm for mining frequent closed itemsets[J].Journal of Computer Research and Development, 2007, 44(7):1177-1183.(in Chinese)
[8] Liu Junqiang, Sun Xiaoying, Zhuang Yueting, et al.Mining frequent closed patterns by adaptive pruning[J].Journal of Software, 2004, 15(1):94-102.(in Chinese)
[9] Lü Cheng, Hao Ying, Zhang Hantao.Algorithm of mining frequent patterns based on the vertical bitmap[J].Journal of Shandong University, 2007, 42(5):24-29.(in Chinese)
[10] Zhu Yuquan, Yang Hebiao, Sun Lei.Data mining techniques[M].Nanjing:Southeast University Press, 2006:27-77.(in Chinese)
Memo
- Memo:
-
Biographies: Zhang Liang(1982—), female, graduate;Ren Yonggong(corresponding author), male, doctor, professor, renyonggong@gmail.com.
Foundation items: The National Natural Science Foundation of China(No.60603047), the Natural Science Foundation of Liaoning Province, Liaoning Higher Education Research Foundation(No.2008341).
Citation: Zhang Liang, Ren Yonggong, Fu Yu.New algorithm of mining frequent closed itemsets[J].Journal of Southeast University(English Edition), 2008, 24(3):335-338.