Efficient mining of emerging patterns
Guozhu Dong, Jinyan Li · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · 1999
We introduce a new kind of patterns, called emerging patterns (EPs), for knowledge discovery from databases. EPs are defined as itemsets whose supports increase significantly from one dataset to another. EPs can capture emerging trends in timestamped databases, or useful contrasts between data classes. EPs have been proven useful: we have used them to build very powerful classifiers, which are more accurate than C4.5 and CBA, for many datasets. We believe that EPs with low to medium support, such as 1%-20%, can give useful new insights and guidance to experts, in even “well understood” applications. The efficient mining of EPs is a challenging problem, since (i) the Apriori property no longer holds for EPs, and (ii) there are usually too many candidates for high dimensional databases or for small support thresholds such as 0.5%. Naive algorithms are too costly. To solve this problem, (a) we promote the description of large collections of itemsets using their concise borders (the pair of sets of the minimal and of the maximal itemsets in the collections). (b) We design EP mining algorithms which manipulate only borders of collections (especially using our multiborder- differential algorithm), and which represent discovered EPs using borders. All EPs satisfying a constraint can be efficiently discovered by our border-based algorithms, which take the borders, derived by Max-Miner, of large itemsets as inputs. In our experiments on large and high dimensional datasets including the US census and Mushroom datasets, many EPs, including some with large cardinality, are found quickly. We also give other algorithms for discovering general or special types of EPs.
Cited by 1,018 works. doi:10.1145/312129.312191
Authors
References
- Fast Algorithms for Mining Association Rules in Large Databases
- Fast algorithms for mining association rules
- Mining sequential patterns
- Advances in knowledge discovery and data mining
- Efficiently mining long patterns from databases
- Discovery of Frequent Episodes in Event Sequences
- Discovering Frequent Episodes in Sequences.
- Integrating classification and association rule mining
- Efficient mining of partial periodic patterns in time series database
- Levelwise Search and Borders of Theories in Knowledge Discovery