Determining the best K for clustering transactional datasets: A coverage density-based approach
Data & Knowledge EngineeringPublished 30 August 2008
Hua Yan, Keke Chen, Ling Liu, Joonsoo Bae
Citations14
SJR quartileQ2
SJR score0.68
SNIP1.41
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
This paper proposes Transactional-cluster-modes Dissimilarity based on the concept of coverage density as an intuitive transactional inter-cluster dissimilarity measure and shows that the new method often effectively estimates the number of clusters of transactional data.
Abstract
The problem of determining the optimal number of clusters is important but mysterious in cluster analysis. In this paper, we propose a novel method to find a set of candidate optimal number Ks of clusters in transactional datasets. Concretely, we propose Transactional-cluster-modes Dissimilarity based on the concept of coverage density as an intuitive transactional inter-cluster dissimilarity measure. Based on the above measure, an agglomerative hierachical clustering algorithm is developed and the Merge Dissimilarity Indexes, which are generated in hierachical cluster merging processes, are used to find the candidate optimal number Ks of clusters of transactional data. Our experimental results on both synthetic and real data show that the new method often effectively estimates the number of clusters of transactional data.
Keywords
Computer Science
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.
Fast algorithms for mining association rules
10,739 Citations1998Rakesh Agrawal, Ramakrishnan Srikant
Data Mining and Knowledge DiscoveryExtensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values
2,409 Citations1998Zhexue Huang
Two algorithms which extend the k-means algorithm to categorical domains and domains with mixed numeric and categorical values are presented and are shown to be efficient when clustering large data sets, which is critical to data mining applications.
CURE
1,909 Citations1998Sudipto Guha, Rajeev Rastogi +1 more
This work proposes a new clustering algorithm called CURE that is more robust to outliers, and identifies clusters having non-spherical shapes and wide variances in size, and demonstrates that random sampling and partitioning enable CURE to not only outperform existing algorithms but also to scale well for large databases without sacrificing clustering quality.
Information SystemsRock: A robust clustering algorithm for categorical attributes
1,482 Citations2000Sudipto Guha, Rajeev Rastogi +1 more
Bayesian classification (AutoClass): theory and results
972 Citations1996Peter Cheeseman, John Stutz
It is emphasized that no current unsupervised classi(cid:12)cation system can produce maximally useful results when operated alone, and that it is the interaction between domain experts and the machine searching over the model space, that generates new knowledge.
Data & Knowledge EngineeringA k-mean clustering algorithm for mixed numeric and categorical data
709 Citations2007Amir Ahmad, Lipika Dey
A clustering algorithm based on k-mean paradigm that works well for data with mixed numeric and categorical features is presented and a new cost function and distance measure based on co-occurrence of values is proposed.
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 RecordCluster validity methods
530 Citations2002Maria Halkidi, Yannis Batistakis +1 more
This paper presents a review of the clustering validity and methods based on external and internal criteria and discusses the cluster validity approaches based on internal and external criteria.
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.
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.
Using association rules for product assortment decisions
364 Citations1999Tom Brijs, Gilbert Swinnen +2 more
This study integrates the discovery of frequent itemsets with a (microeconomic) model for product selection (PROFSET) that enables the integration of both quantitative and qualitative criteria and demonstrates the impact of product assortment decisions on overall assortment profitability can easily be evaluated by means of sensitivity analysis.
COOLCAT
345 Citations2002Daniel Barbará, Yi Li +1 more
The connection between clustering categorical data and entropy is explored: clusters of similar poi lower entropy than those of dissimilar ones, and an incremental heuristic algorithm, COOLCAT, which is capable of efficiently clustering large data sets of records with categorical attributes, and data streams.
Lecture notes in computer scienceLIMBO: Scalable Clustering of Categorical Data
260 Citations2004Periklis Andritsos, Panayiotis Tsaparas +2 more
This work introduces LIMBO, a scalable hierarchical categorical clustering algorithm that builds on the Information Bottleneck (IB) framework for quantifying the relevant information preserved when clustering, and shows how the LIMBO algorithm can be used to cluster both tuples and values.
Fully automatic cross-associations
244 Citations2004Deepayan Chakrabarti, Spiros Papadimitriou +2 more
This work furnishes a clear, information-theoretic criterion to choose a good cross-association as well as its parameters, namely, the number of row and column groups, and provides scalable algorithms to approach the optimal.
Data & Knowledge EngineeringMMR: An algorithm for clustering categorical data using Rough Set Theory
180 Citations2007Darshit Parmar, Teresa Wu +1 more
This research proposes a new algorithm for clustering categorical data, termed Min-Min-Roughness (MMR), based on Rough Set Theory (RST), which has the ability to handle the uncertainty in the clustering process.
Entropy-based criterion in categorical clustering
178 Citations2004Tao Li, Sheng Ma +1 more
It is shown that the entropy-based criterion can be derived in the formal framework of probabilistic clustering models and the connection between the criterion and the approach based on dissimilarity co-efficients is established.
CLOPE
162 Citations2002Yiling Yang, Xudong Guan +1 more
A novel algorithm is developed -- CLOPE, which is very fast and scalable, while being quite effective in categorical data clustering, especially for transactional data characterized by high dimensionality and large volume.
IEEE Transactions on Knowledge and Data EngineeringFinding localized associations in market basket data
125 Citations2002Charų C. Aggarwal, Cecilia M. Procopiuc +1 more
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.
COOLCAT
82 Citations2002Daniel Barbará, Yi Li +1 more
Information VisualizationVISTA: Validating and Refining Clusters Via Visualization
72 Citations2004Keke Chen, Ling Liu
This paper addresses the problem of clustering and validating arbitrarily shaped clusters with a visual framework (VISTA) to capitalize on the power of visualization and interactive feedbacks to encourage domain experts to participate in the clustering revision and clustering validation process.
Data & Knowledge EngineeringCategorical data visualization and clustering using subjective factors
39 Citations2004Chia‐Hui Chang, Zhi-Kai Ding
A new clustering approach called CDCS (Categorical Data Clustering with Subjective factors) is introduced, where a visualization tool for clustered categorical data is developed such that the result of adjusting parameters is instantly reflected.
The Best K for entropy-based categorical data clustering
36 Citations2005Keke Chen, Ling Liu
This paper investigates the entropy property of the categorical data and proposes a BkPlot method for determining a set of candidate “best Ks” and shows that this approach can effectively identify the significant clustering structures.
Efficiently clustering transactional data with weighted coverage density
18 Citations2006Hua Yan, Keke Chen +1 more
The results show that the weighted coverage density approach powered by the SCALE framework can efficiently generate high quality clustering results in a fully automated manner.