An Efficient Algorithm for Enumerating Closed Patterns in Transaction Databases
An Efficient Algorithm for Enumerating Closed Patterns in Transaction Databases
复制标题
DOI：
10.1007/978-3-540-30214-8_2
复制
发表时间：
2004-10
期刊：
影响因子：
--
通讯作者：
T. Uno;Tatsuya Asai;Y. Uchida;Hiroki Arimura
中科院分区：
文献类型：
--
作者：
T. Uno;Tatsuya Asai;Y. Uchida;Hiroki Arimura
闭模式类是频繁模式的一种压缩表示，近年来引起了人们极大的兴趣。本文提出了一种从大型事务数据库中挖掘频繁闭合模式的高效算法LCM（Linear time Closed Pattern Miner）。主要的理论贡献是我们提出的闭合模式的前缀保留闭合扩展，这使我们能够以深度优先的方式在频繁闭合模式数量的线性时间内搜索所有频繁闭合模式。我们的算法不需要任何存储空间，以前获得的模式，而现有的算法需要它。LCM与直接算法的性能比较表明，我们的前缀保持闭包扩展的优势。
The class of closed patterns is a well known condensed representations of frequent patterns, and have recently attracted considerable interest. In this paper, we propose an efficient algorithm LCM (Linear time Closed pattern Miner) for mining frequent closed patterns from large transaction databases. The main theoretical contribution is our proposedprefix-preserving closure extensionof closed patterns, which enables us to search all frequent closed patterns in a depth-first manner, in linear time for the number of frequent closed patterns. Our algorithm do not need any storage space for the previously obtained patterns, while the existing algorithms needs it. Performance comparisons of LCM with straightforward algorithms demonstrate the advantages of our prefix-preserving closure extension.