TL;DR
This paper introduces two novel clustering algorithms based on Minimum Spanning Trees (MSTs): a k-constrained algorithm (HEMST) that partitions data into a specified number of clusters, and an unconstrained algorithm (MSDR) that automatically determines the optimal number of clusters. Both algorithms outperform existing methods like k-means and standard MST-based approaches on various challenging datasets, particularly in scenarios with irregular cluster shapes and varying densities.
What Problem Does This Paper Address?
Traditional clustering algorithms often struggle with datasets exhibiting irregular cluster shapes, non-uniform densities, or when the number of clusters is unknown beforehand. Many existing methods assume spherical clusters or require users to pre-specify the number of clusters, which can be impractical. The paper aims to address these limitations by leveraging the power of Minimum Spanning Trees (MSTs) to discover underlying cluster structures, even in complex, non-spherical arrangements, and to provide methods for both pre-defined and automatically determined cluster counts.
Methods
The paper proposes two main algorithms:
- Hierarchical EMST-based Algorithm (HEMST): This is a k-constrained algorithm. It starts by constructing an MST and iteratively identifies "representative points" for clusters. Edges are removed based on a criterion involving the average weight and standard deviation of edges. The process is recursive, refining the set of representative points until the desired number of clusters, k, is achieved. The final clusters are formed by assigning original points to these representative points.
- Maximum Standard Deviation Reduction Algorithm (MSDR): This is an unconstrained algorithm. It also begins with an MST and iteratively removes edges. The key innovation here is the objective function: it aims to maximize the reduction in the average standard deviation of edge weights across the resulting subtrees. This process continues until the rate of reduction stabilizes, and then a polynomial regression is used to automatically determine the optimal number of clusters.
Datasets
The paper evaluates its algorithms on:
- Artificial Datasets: Several synthetic datasets are used to demonstrate performance on challenging cluster shapes and densities (Figures 4, 5, and 6).
- Image Color Clustering: The algorithms are applied to color clustering in JPEG and GIF images.
- UCI Repository Datasets: The algorithms are tested on benchmark datasets including:
- Iris Plants
- Pima-Indians Diabetes
- Thyroid
- Image Segmentation
Key Insights and Ideas
- MSTs for Irregular Clusters: The core idea is that MSTs naturally capture connectivity and can be pruned to reveal clusters with arbitrary shapes, overcoming limitations of methods assuming spherical clusters.
- Representative Points as "Attractors": HEMST uses representative points that act as anchors for their respective clusters, effectively guiding the clustering process.
- Standard Deviation as a Cluster Quality Metric: MSDR's novel approach of maximizing the reduction in standard deviation of edge weights provides a robust way to identify inter-cluster edges, leading to automatic cluster number determination.
- Parameter-Free Unconstrained Clustering: MSDR's ability to automatically determine the number of clusters without requiring user-defined parameters is a significant advantage over many existing methods, including other MST-based approaches like ZEMST.
Key Results
- HEMST vs. k-means/EM: On artificial datasets with irregular shapes and varying densities (Figures 4, 5, 6), HEMST generally outperformed k-means and EM, successfully identifying clusters that other methods fragmented or merged incorrectly.
- Image Color Clustering: HEMST was shown to be more effective than the standard SEMST algorithm in color clustering, capturing more details and objects in images with fewer clusters. MSDR also showed promise in unconstrained color clustering, producing fewer clusters than ZEMST while preserving image objects.
- UCI Datasets:
- On the Iris Plants dataset, MSDR produced the lowest average entropy, indicating purer clusters, and was particularly good at separating versicolor from virginica.
- On the Thyroid dataset, MSDR achieved significantly lower average entropy than other MST-based algorithms and successfully identified Hypo instances, which other MST methods struggled with.
- On the Pima Indians Diabetes dataset, MSDR produced clusters with significantly lower average entropy compared to other algorithms.
- On the Image Segmentation dataset, MSDR successfully separated "sky" instances and identified more "path" instances than k-means, with comparable or better average entropy.
- Computational Complexity: HEMST has a complexity of O(n² log n), and MSDR has a complexity of O(n² log n + nk).
Limitations and Future Work
- Runtime Efficiency of MSDR: The authors acknowledge that runtime efficiency is a challenge for MSDR, although they have implemented optimizations. Further improvements are likely needed for very large datasets.
- Parameter Tuning for ZEMST: The paper highlights that Zahn's algorithm (ZEMST) heavily relies on user-defined parameters (neighborhood size, standard deviation factors), making it difficult to obtain optimal results across different datasets.
- Future Work: The authors intend to explore MST-based clustering in domains with inherently irregular cluster boundaries and to identify new challenges in applying these techniques in practice. They also suggest further investigation into the potential of MST-based algorithms for various data mining tasks.
Summary updated