Minimum Description Length (MDL) Principle: Generators Are Preferable to Closed Patterns

Document Type

Conference Proceeding

Publication Date

2006

Find in a Library

Catalog Record

Abstract

The generators and the unique closed pattern of an equivalence class of itemsets share a common set of transactions. The generators are the minimal ones among the equivalent itemsets, while the closed pattern is the maximum one. As a generator is usually smaller than the closed pattern in cardinality, by the Minimum Description Length Principle, the generator is preferable to the closed pattern in inductive inference and classification. To efficiently discover frequent generators from a large dataset, we develop a depth-first algorithm called Gr-growth. The idea is novel in contrast to traditional breadth-first bottom-up generator-mining algorithms. Our extensive performance study shows that Gr-growth is significantly faster (an order or even two orders of magnitudes when the support thresholds are low) than the existing generator mining algorithms. It can be also faster than the state-of-the-art frequent closed itemset mining algorithms such as FPclose and CLOSET+.

Comments

This paper was presented at the 21st National Conference on Artificial Intelligence (AAAI'06), Boston, MA, USA, July 16-20, 2006.

Catalog Record

Share

COinS