Abstract
A new cluster validity index is proposed that determines the optimal partition and optimal number of clusters for fuzzy partitions obtained from the fuzzy c-means algorithm. The proposed validity index exploits an overlap measure and a separation measure between clusters. The overlap measure is obtained by computing an inter-cluster overlap, while the separation measure is obtained by computing a distance between fuzzy clusters. A good fuzzy partition is expected to have a low degree of overlap and a larger separation distance. Testing of the proposed index and nine previously formulated indexes on well-known data sets showed the superior effectiveness and reliability of the proposed index in comparison to other indexes.
Introduction
In Fuzzy C-Means (FCM) clustering, data points are assigned membership degrees across multiple clusters rather than being restricted to a single group. A critical challenge in this domain is determining the optimal number of clusters ($c$) for a given dataset. Existing validity indices often rely on Euclidean distances between cluster centers to model "compactness" and "separation." However, this geometric approach can be misleading.
As illustrated in Figure 2, two very different partitions can have identical center-to-center distances but vastly different levels of fuzzy overlap. Traditional indices frequently struggle when clusters have varying densities or complex shapes, often leading to inaccurate estimates of the true cluster count.
Methods
To address these limitations, we propose the $v_{os}$ index, which is defined as the ratio of a normalized overlap measure to a normalized separation measure:
$$v_{os}(c, U) = \frac{Overlap^N(c, U)}{Sep^N(c, U)}$$
The goal is to minimize this value, identifying partitions with minimal overlap and maximal separation. The index is built upon two core components:
- Overlap Measure ($Overlap$): Instead of physical spatial distance, this measure analyzes membership values ($\mu$). High overlap occurs when many points have high membership in two different clusters simultaneously. A weighting function $w(x_i)$, shown in Figure 3, is employed to focus specifically on points in "ambiguous" regions between clusters, ignoring points clearly within a single cluster.
- Separation Measure ($Sep$): This uses a fuzzy set similarity measure to calculate the degree to which two fuzzy clusters are distinct based on the intersection of their membership functions, rather than simple point-to-point distances.
Results
The $v_{os}$ index was evaluated against nine well-known CVIs (including $v_{PC}$, $v_{PE}$, and $v_{XB}$) using five benchmark datasets: X30, BENSAID, STARFIELD, IRIS, and BUTTERFLY.
The $v_{os}$ index demonstrated superior performance, achieving perfect accuracy by correctly identifying the optimal number of clusters for all five test datasets. It was particularly effective on the STARFIELD dataset, which is notoriously difficult for center-based metrics. While other indices like $v_{FS}$ worked for IRIS but failed for STARFIELD, $v_{os}$ showed high reliability across diverse data distributions.
Conclusion
The $v_{os}$ index represents a shift from purely geometric cluster validation to a membership-based approach. By leveraging the information in the membership matrix and focusing on ambiguous boundary regions, it provides a more robust measure of cluster quality. Future research should explore its computational scalability for large datasets and its performance in high-dimensional feature spaces where traditional Euclidean distances become less meaningful.
Summary updated