A tree-based approach for efficiently mining Approximate Frequent Itemsets

Jia-Ling Koh, Vi Lang Tu

研究成果: 書貢獻/報告類型會議貢獻

2 引文 斯高帕斯(Scopus)

摘要

The strategies for mining frequent itemsets, which is the essential part of discovering association rules, have been widely studied over the last decade. In real-world datasets, it is possible to discover multiple fragmented patterns but miss the longer true patterns due to random noise and errors in the data. Therefore, a number of methods have been proposed recently to discover approximate frequent itemsets. However, a challenge of providing an efficient algorithm for solving this problem is how to avoid costly candidate generation and test. In this paper, an algorithm, named FP-AFI (FP-tree based Approximate Frequent Itemsets mining algorithm), is developed to discover approximate frequent itemsets from a FP-tree-Iike structure. We define a recursive function for getting the set of transactions which faulttolerant contain an itemset P. The patterns in the fault-tolerant supporting transactions of P are represented by the conditional AFP-trees of P. Moreover, to avoid re-constructing the tree structure in the mining process, two pseudo-projection operations on AFP-trees are provided to obtain the conditional AFP-trees of a candidate itemset systematically. Consequently, the approximate support of a candidate itemset and the item supports of each item in the candidate are obtained easily from the conditional AFP-trees. Hence, the constrain test of a candidate itemset is performed efficiently without additional database scan. The experimental results show that the FP-AFI algorithm performs much better than the FP-Apriori and the AFI algorithms in efficiency especially when the size of data set is large and the minimum threshold of approximate support is small. Moreover, the execution time of FP-AFI is scalable even when the error threshold parameters become large.

原文英語
主出版物標題2010 4th International Conference on Research Challenges in Information Science - Proceedings, RCIS 2010
頁面25-36
頁數12
出版狀態已發佈 - 2010 十月 7
事件2010 4th International Conference on Research Challenges in Information Science, RCIS 2010 - Nice, 法国
持續時間: 2010 五月 192010 五月 21

出版系列

名字2010 4th International Conference on Research Challenges in Information Science - Proceedings, RCIS 2010

其他

其他2010 4th International Conference on Research Challenges in Information Science, RCIS 2010
國家法国
城市Nice
期間10/5/1910/5/21

    指紋

ASJC Scopus subject areas

  • Information Systems
  • Information Systems and Management

引用此

Koh, J-L., & Tu, V. L. (2010). A tree-based approach for efficiently mining Approximate Frequent Itemsets. 於 2010 4th International Conference on Research Challenges in Information Science - Proceedings, RCIS 2010 (頁 25-36). [5507360] (2010 4th International Conference on Research Challenges in Information Science - Proceedings, RCIS 2010).