A Cluster Validity Index Using Overlap and Separation Measures Between Fuzzy Clusters

Dae‐Won Kim, Kwang-H. LeeJournal of Korean Institute of Intelligent Systems 2003 · DOI

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.

Comparison of two partitions with identical cluster centers but different overlap levels.

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:

  1. 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.
Membership functions and the weighting function w(x) used to calculate overlap.
  1. 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

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. 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.
BibTeX
@article{kim2003cluster,
  author = {Dae‐Won Kim and Kwang-H. Lee},
  title = {{A Cluster Validity Index Using Overlap and Separation Measures Between Fuzzy Clusters}},
  journal = {Journal of Korean Institute of Intelligent Systems},
  year = {2003},
  doi = {10.5391/jkiis.2003.13.4.455},
}
Figure