Ascending frequency ordered prefix-tree: efficient mining of frequent patterns
Ascending frequency ordered prefix-tree: efficient mining of frequent patterns
复制标题
DOI：
10.1109/dasfaa.2003.1192369
复制
发表时间：
2003-03
期刊：
影响因子：
--
通讯作者：
Guimei Liu;Hongjun Lu;Yabo Xu;J. Yu
中科院分区：
文献类型：
--
作者：
Guimei Liu;Hongjun Lu;Yabo Xu;J. Yu
挖掘频繁模式是许多数据挖掘应用中一个基本而重要的问题。许多算法采用模式增长方法，该方法明显优于候选生成-测试方法。我们确定了影响模式增长方法性能的关键因素，并对其进行了优化，以进一步提高性能。我们的算法使用一种简单而紧凑的数据结构-升序频率前缀树（AFOPT）来组织条件数据库，其中我们使用数组来存储单个分支以进一步节省空间。我们使用自顶向下的策略遍历前缀树结构。实验结果表明，将自顶向下的遍历策略与升频项排序方法相结合，取得了显著的性能提升。
Mining frequent patterns is a fundamental and important problem in many data mining applications. Many of the algorithms adopt the pattern growth approach, which is shown to be superior to the candidate generate-and-test approach significantly. We identify the key factors that influence the performance of the pattern growth approach, and optimize them to further improve the performance. Our algorithm uses a simple while compact data structure-ascending frequency ordered prefixtree (AFOPT) to organize the conditional databases, in which we use arrays to store single branches to further save space. We traverse our prefix-tree structure using a top-down strategy. Our experiment results show that the combination of the top-down traversal strategy and the ascending frequency item ordering method achieves significant performance improvement over previous works.