Efficient discovery of error-tolerant frequent itemsets in high dimensions
Authors:
Open Access
- 26 August 2001
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 194-203
Abstract
We present a generalization of frequent itemsets allowing for the notion of errors in the itemset definition. We motivate the problem and present an efficient algorithm that identifies error-tolerant frequent clusters of items in transactional data (customer-purchase data, web browsing data, text, etc.). The algorithm exploits sparseness of the underlying data to find large groups of items that are correlated over database records (rows). The notion of transaction coverage allows us to extend the algorithm and view it as a fast clustering algorithm for discovering segments of similar transactions in binary sparse data. We evaluate the new algorithm on three real-world applications: clustering high-dimensional data, query selectivity estimation and collaborative filtering. Results show that the algorithm consistently uncovers structure in large sparse databases that other traditional clustering algorithms fail to find.Keywords
This publication has 12 references indexed in Scilit:
- Density-based indexing for approximate nearest-neighbor queries1999
- Compressed data cubes for OLAP aggregate query approximation on continuous dimensions1999
- Efficiently mining long patterns from databases1998
- Automatic subspace clustering of high dimensional data for data mining applications1998
- CURE1998
- Recommender systemsCommunications of the ACM, 1997
- BIRCH1996
- Mining quantitative association rules in large relational tables1996
- GroupLens1994
- Mining association rules between sets of items in large databases1993