Frequent Pattern Mining and Knowledge Indexing Based on Zero-Suppressed BDDs
Frequent Pattern Mining and Knowledge Indexing Based on Zero-Suppressed BDDs
复制标题
DOI：
10.1007/978-3-540-75549-4_10
复制
发表时间：
2006-09
期刊：
影响因子：
--
通讯作者：
S. Minato;Hiroki Arimura
中科院分区：
文献类型：
--
作者：
S. Minato;Hiroki Arimura
频繁模式挖掘是知识发现和数据挖掘的基本技术之一。在过去的十年里，已经提出了几种高效的频繁模式挖掘算法，但大多数算法都集中在枚举满足给定条件的模式上，而将模式结果的存储和索引视为单独的问题，以便进行有效的归纳分析。本文提出了一种从事务数据库中提取所有/最大频繁模式的快速算法，并使用零抑制二叉决策图(ZBDDS)同时索引大量的模式。我们的方法与现有的最先进的算法相比速度相当快，不仅列举/列出了模式，而且还在主存储器中紧凑地索引输出数据。挖掘后的模式结果可以通过代数运算得到有效的分析结果。基于BDD的数据结构已经成功地应用于VLSI逻辑设计中，但我们的方法是基于BDD的技术在数据挖掘领域的第一次实际应用。
Frequent pattern mining is one of the fundamental techniques for knowledge discovery and data mining. During the last decade, several efficient algorithms for frequent pattern mining have been presented, but most algorithms have focused on enumerating the patterns that satisfy the given conditions, considering the storage and indexing of the pattern results for efficient inductive analysis to be a separate issue. In this paper, we propose a fast algorithm for extracting all/maximal frequent patterns from transaction databases and simultaneously indexing a huge number of patterns using Zero-suppressed Binary Decision Diagrams (ZBDDs). Our method is comparably fast as existing state-of-the-art algorithms and not only enumerates/lists the patterns but also compactly indexes the output data in main memory. After mining, the pattern results can be analyzed efficiently by using algebraic operations. BDD-based data structures have previously been used successfully in VLSI logic design, but our method is the first practical application of BDD-based techniques in the data mining area.