Finding localized associations in market basket data
IEEE Transactions on Knowledge and Data EngineeringPublished 1 January 2002
Charų C. Aggarwal, Cecilia M. Procopiuc, Philip S. Yu
Citations125
SJR quartileQ1
SJR score2.57
SNIP3.30
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Empirical results show that the method is indeed able to find a significantly larger number of associations than what can be discovered by analysis of the aggregate data.
Abstract
In this paper, we discuss a technique for discovering localized associations in segments of the data using clustering. Often, the aggregate behavior of a data set may be very different from localized segments. In such cases, it is desirable to design algorithms which are effective in discovering localized associations because they expose a customer pattern which is more specific than the aggregate behavior. This information may be very useful for target marketing. We present empirical results which show that the method is indeed able to find a significantly larger number of associations than what can be discovered by analysis of the aggregate data.
Keywords
Computer ScienceBusiness, Management and Accounting
A density-based algorithm for discovering clusters in large spatial Databases with Noise
19,114 Citations1996Martin Ester, Hans‐Peter Kriegel +2 more
DBSCAN, a new clustering algorithm relying on a density-based notion of clusters which is designed to discover clusters of arbitrary shape, is presented which requires only one input parameter and supports the user in determining an appropriate value for it.
Mining association rules between sets of items in large databases
14,720 Citations1993Rakesh Agrawal, Tomasz Imieliński +1 more
An efficient algorithm is presented that generates all significant association rules between items in the database of customer transactions and incorporates buffer management and novel estimation and pruning techniques.
Choice Reviews OnlineFinding groups in data: an introduction to cluster analysis
10,614 Citations1991
BIRCH
3,906 Citations1996Tian Zhang, Raghu Ramakrishnan +1 more
A data clustering method named BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) is presented, and it is demonstrated that it is especially suitable for very large databases.
Automatic subspace clustering of high dimensional data for data mining applications
2,386 Citations1998Rakesh Agrawal, Johannes Gehrke +2 more
CLIQUE is presented, a clustering algorithm that satisfies each of these requirements of data mining applications including the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records.
Efficient and Effective Clustering Methods for Spatial Data Mining
1,788 Citations1994Raymond T. Ng, Jiawei Han
The analysis and experiments show that with the assistance of CLAHANS, these two algorithms are very effective and can lead to discoveries that are difficult to find with current spatial data mining algorithms.
Information SystemsRock: A robust clustering algorithm for categorical attributes
1,482 Citations2000Sudipto Guha, Rajeev Rastogi +1 more
Beyond market baskets
1,287 Citations1997Sergey Brin, Rajeev Motwani +1 more
This work develops the notion of mining rules that identify correlations (generalizing associations), and proposes measuring significance of associations via the chi-squared test for correlation from classical statistics, enabling the mining problem to reduce to the search for a border between correlated and uncorrelated itemsets in the lattice.
OPTICS
1,269 Citations1999Mihael Ankerst, Markus Breunig +2 more
A new algorithm is introduced for the purpose of cluster analysis which does not produce a clustering of a data set explicitly; but instead creates an augmented ordering of the database representing its density-based clustering structure.
IEEE Transactions on Knowledge and Data EngineeringCLARANS: a method for clustering objects for spatial data mining
1,184 Citations2002Raymond T. Ng, Jiawei Han
A new clustering method is proposed, called CLARANS, whose aim is to identify spatial structures that may be present in the data, and two spatial data mining algorithms that aim to discover relationships between spatial and nonspatial attributes are developed.
Information SystemsCure: an efficient clustering algorithm for large databases
945 Citations2001Sudipto Guha, Rajeev Rastogi +1 more
Finding interesting rules from large sets of discovered association rules
717 Citations1994Mika Klemettinen, Heikki Mannila +3 more
It is shown how a simple formalism of rule templates makes it possible to easily describe the structure of interesting rules, and how a visualization tool interfaces with rule templates.
ACM SIGMOD RecordAutomatic subspace clustering of high dimensional data for data mining applications
663 Citations1998Rakesh Agrawal, Johannes Gehrke +2 more
ROCK: a robust clustering algorithm for categorical attributes
601 Citations1999Suvajyoti Guha, R. Rastogi +1 more
This work develops a robust hierarchical clustering algorithm, ROCK, that employs links and not distances when merging clusters, and shows that ROCK not only generates better quality clusters than traditional algorithms, but also exhibits good scalability properties.
ACM SIGMOD RecordFinding generalized projected clusters in high dimensional spaces
532 Citations2000Charų C. Aggarwal, Philip S. Yu
CACTUS—clustering categorical data using summaries
470 Citations1999Venkatesh Ganti, Johannes Gehrke +1 more
This paper introduces a novel formalization of a cluster for categorical attributes by generalizing a definition of a clusters for numerical attributes and describes a very fast summarizationbased algorithm called CACTUS that discovers exactly such clusters in the data.
Incremental Clustering for Mining in a Data Warehousing Environment
464 Citations1998Martin Ester, Hans‐Peter Kriegel +3 more
It can be proven that the incremental algorithm yields the same result as DBSCAN, which is applicable to any database containing data from a metric space, e.g., to a spatial database or to a WWW-log database.
The VLDB JournalClustering categorical data: an approach based on dynamical systems
388 Citations2000David Gibson, Jon Kleinberg +1 more
This work describes a novel approach for clustering collections of sets, and its application to the analysis and mining of categorical data, based on an iterative method for assigning and propagating weights on the categorical values in a table.
A distribution-based clustering algorithm for mining in large spatial databases
346 Citations2002Xiaowei Xu, Martin Ester +2 more
The new clustering algorithm DBCLASD (Distribution-Based Clustering of LArge Spatial Databases) is introduced to discover clusters of this type and is very attractive when considering its nonparametric nature and its good quality for clusters of arbitrary shape.
Finding generalized projected clusters in high dimensional spaces
291 Citations2000Charų C. Aggarwal, Philip S. Yu
Very general techniques for projected clustering are discussed which are able to construct clusters in arbitrarily aligned subspaces of lower dimensionality, which is substantially more general and realistic than currently available techniques.
A new framework for itemset generation
244 Citations1998Charų C. Aggarwal, Philip S. Yu
An algorithm is provided which provides very good computational efficiency, while maintaining statistical robuetneas, which implies that the method can be applied to find association rules in datasets in which items may appear in a sizeable percentage of the transactions (dense datasets), dataset in which the items have varying density, or even negative association rules.
Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces
230 Citations2000Kaushik Chakrabarti, Sharad Mehrotra
Local Dimensionality Reduction (LDR) is proposed that tries to find local correlations in the data and performs dimensionality reduction on the locally correlated clusters of data individually and an index structure is developed that exploits the correlated clusters to efficiently support point, range and k-nearest neighbor queries over high dimensional datasets.
University of Minnesota Digital Conservancy (University of Minnesota)Clustering Based on Association Rule Hypergraphs
176 Citations1997Eui-Hong Han, George Karypis +2 more
Mining Surprising Patterns Using Temporal Description Length
129 Citations1998Soumen Chakrabarti, Sunita Sarawagi +1 more
A precise characterization of surprise is proposed based on the number of bits in which a basket sequence can be encoded under a carefully chosen coding scheme, and it is inexpensive to encode sequences of itemsets that have steady, hence likely to be well-known, correlation between items.
Knowledge Discovery and Data MiningA database interface for clustering in large spatial databases
127 Citations1995Martin Ester, Hans‐Peter Kriegel +1 more
This paper presents an interface to the database management system (DBMS) based on a spatial access method, the R*-tree, which is crucial for the efficiency of KDD on large databases and proposes a method for spatial data sampling as part of the focusing component, significantly reducing the number of objects to be clustered.
Future Generation Computer SystemsA comparative study of clustering methods
119 Citations1997Mohamed Zaït, Hammou Messatfa
This paper proposes a methodology for comparing clustering methods based on the quality of the result and the performance of the execution, and applied it to several known clustering method: FastClust, Autoclass, Relational data analysis, and Kohonen nets.
Snakes and sandwiches
11 Citations1999H. V. Jagadish, Laks V. S. Lakshmanan +1 more
This paper identifies an important subclass of clustering strategies called lattice paths, and presents a dynamic programming algorithm for finding the optimal lattice path clustering, in time linear in the lattice size, and proposes a technique called snaking, which when applied to a lattICE path always reduces its cost.