Source-linked AI summary
Estimating the Optimal Number of Clusters in Categorical Data Clustering by Silhouette Coefficient
Duy-Tai Dinh, Tsutomu Fujinami, Van-Nam Huynh
TL;DR
Estimating the number of clusters is a major challenge in partitional clustering, especially for categorical data. The paper proposes k-SCC, which combines categorical-data clustering with kernel density estimation, information-theoretic dissimilarity, and silhouette-based selection of k. Experiments on synthetic and real datasets report that k-SCC outperforms three compared algorithms in determining cluster numbers.
Problem
Estimating the number of clusters is a major challenge in partitional clustering, and categorical data require suitable clustering centers and dissimilarity measures.
Method
k-SCC uses kernel density estimation for cluster centers, information-theoretic dissimilarity for object-center distances, and average silhouette maximization to select k.
Results
k-SCC outperforms the three compared algorithms on synthetic and real datasets for determining the number of clusters.
Takeaways & Limitations
The method estimates cluster numbers for categorical datasets and can be extended to mixed numeric and categorical data clustering.
Takeaways & Limitations
Average silhouette values depend strongly on the dissimilarity measure and clustering scheme, and the method has high costs on large-scale datasets.
Abstract
from arXiv · showhide
The problem of estimating the number of clusters (say k) is one of the major challenges for the partitional clustering. This paper proposes an algorithm named k-SCC to estimate the optimal k in categorical data clustering. For the clustering step, the algorithm uses the kernel density estimation approach to define cluster centers. In addition, it uses an information-theoretic based dissimilarity to measure the distance between centers and objects in each cluster. The silhouette analysis based approach is then used to evaluate the quality of different clustering obtained in the former step to choose the best k. Comparative experiments were conducted on both synthetic and real datasets to compare the performance of k-SCC with three other algorithms. Experimental results show that k-SCC outperforms the compared algorithms in determining the number of clusters for each dataset.
1 Introduction
Partitional clustering seeks groups of similar objects, but categorical data and the unknown number of clusters create important challenges. The paper proposes k-SCC to estimate the optimal cluster number using silhouette analysis.
- Clustering groups similar objects together and separates them from objects in other groups.
- K-means is widely used for partitional clustering but cannot directly handle categorical data.Transforming categorical data into a new feature space before applying k-means has proven ineffective.
- Estimating the number of clusters is vital because fixed, overestimated, or underestimated values can affect clustering quality and interpretation.
- k-SCC combines a k-means-like clustering algorithm with silhouette analysis to estimate the optimal number of clusters in categorical data.
- Experiments on synthetic and UCI real datasets evaluate clustering quality using average silhouette values and recommend an optimal cluster number for each dataset.
2 Related Work
Related work includes k-means and categorical-data variants that differ in their cluster representatives and dissimilarity measures. Silhouette analysis evaluates clustering quality and can select the cluster number by maximizing average silhouette, but prior work had not applied it to categorical data clustering.
- K-means iteratively assigns objects to nearby centroids and updates those centroids to minimize an objective function.Its standard proximity measures include Manhattan, Euclidean, and Cosine distances.
- K-means represents clusters with means and uses a squared Euclidean distance, but this numerical-data design cannot directly handle categorical data.
- K-modes adapts k-means to categorical data by using modes as cluster centers and simple matching dissimilarity.
- K-representatives defines representatives from categorical-value distributions and measures dissimilarity using relative frequencies and simple matching.The method also incorporates automatic feature weighting.
- The silhouette coefficient uses intra-cluster and nearest inter-cluster distances, with the highest average silhouette indicating the preferred cluster number.The cited passage identifies prior silhouette-based cluster-number estimation for numerical data but not categorical data.
3 Preliminaries
The preliminaries define categorical datasets, probabilistic cluster centers, information-theoretic dissimilarities, and silhouette-based selection of the cluster count. Together, these components support evaluating categorical partitions by maximizing average silhouette value.
- Categorical data: A categorical dataset is an n × m matrix whose objects contain finite-domain categorical values across m attributes.Each object is represented as a tuple of attribute values, and the dataset example contains ten objects with six categorical attributes.
- Clustering definitions: Clusters partition the dataset into k disjoint subsets whose union contains all objects.The number of objects in cluster C_l is denoted n_l.
- Cluster centers: A probabilistic center represents each categorical cluster with attribute-wise probability distributions estimated by kernel density estimation.The method uses cluster-specific smoothing bandwidths and category sets to estimate these distributions.
- Dissimilarity: The dissimilarity between categorical values is information-theoretic, and object-level dissimilarity aggregates attribute-wise dissimilarities.The resulting pairwise matrix is symmetric, assigns zero to identical objects, and has an upper bound equal to the number of attributes.
- Silhouette analysis: Silhouette values compare an object’s average within-cluster distance with its smallest average distance to another cluster.Positive values indicate well-clustered objects, negative values indicate poor clustering, and values near zero indicate overlap between clusters.
- Cluster-count selection: The optimal cluster count is the k that maximizes the dataset’s average silhouette value.This objective evaluates both within-cluster cohesion and between-cluster separation.
4 The Proposed k-SCC Algorithm
k-SCC evaluates candidate cluster counts by repeatedly partitioning categorical data, computing average silhouette values, and selecting the count with the largest value. Its iterations use assignment and center-update steps until the partition converges.
- Algorithm framework: For each k between predefined minimum and maximum values, k-SCC partitions the categorical data and computes its average silhouette value.The candidate count producing the largest average silhouette is selected as optimal.
- Initialization: The algorithm first computes a dissimilarity matrix for all categorical objects and stores candidate average silhouettes in SilSet.The default search range is kmin and kmax within [2, n − 1].
- Evaluation: After convergence, k-SCC uses the resulting clusters and proximity matrix to compute the average silhouette value for that candidate k.The computed value is added to SilSet before the next candidate count is processed.
- Iterative clustering: For each candidate k, k-SCC randomly initializes k centers, assigns objects to their nearest centers, and updates the centers iteratively.Assignment and update steps continue while the partitions are not convergent.
5 Comparative Experiment
The comparative experiments evaluate k-SCC and competing clustering methods on real and synthetic datasets using average silhouette values across candidate cluster counts. k-SCC generally achieves the strongest silhouette results, including on the Sake wine case study.
- Datasets and compared methods: The experiments compare k-SCC with k-modes, Modified-3, and k-SCC+ on real and synthetic datasets.The evaluated real datasets come from the UCI repository, while SD5K and SD10K are synthetic datasets.
- Silhouette-based evaluation: For each dataset, k was varied from 2 to 10, and the number of clusters was selected by comparing average silhouette values.The figure uses average silhouette value on the vertical axis and number of clusters on the horizontal axis.
- Results: k-SCC generally produced higher average silhouette values than k-modes, Modified-3, and k-SCC+ across the evaluated datasets.The reported results also state that k-SCC and k-SCC+ exceed k-modes in average silhouette values.
- Sake wine case study: On the Sake wine dataset, k-SCC outperformed the comparison methods in most cases, except at k = 10, where k-SCC+ had the higher average silhouette.The recommended cluster counts were three or four, corresponding to the largest and second-largest average silhouettes.
- Sake wine case study: The recommended three or four Sake wine clusters matched the classifications obtained from complete-linkage hierarchical clustering.The numeric Sake data were discretized into five linguistic grades before applying k-SCC.
6 Summary and Discussion
k-SCC estimates cluster counts for categorical data using silhouette values and outperforms three compared algorithms on synthetic and real datasets. The method can extend to mixed numeric and categorical data, but its silhouette quality depends on the dissimilarity measure and clustering scheme and can be costly for large datasets.
- k-SCC estimates the optimal number of clusters by selecting the k with the highest average silhouette value.The algorithm evaluates candidate clusterings and chooses the index producing the largest average silhouette.
- Experimental results show that k-SCC outperforms three compared algorithms on both synthetic and real datasets.
- The method can be extended to estimate clusters in mixed numeric and categorical data.
- As a partitional clustering method, k-SCC terminates at a local optimum and can be upgraded with other dissimilarity measures.
- Average silhouette values depend strongly on the dissimilarity measure and clustering scheme, while large-scale datasets impose high computational costs.The paper identifies suitable clustering frameworks and reduced computational complexity as necessary for this task.