Validity-guided (re)clustering with applications to image segmentation

When clustering algorithms are applied to image segmentation, the goal is to solve a classification problem. However, these algorithms do not directly optimize classification quality. As a result, they are susceptible to two problems: P1) the criterion they optimize may not be a good estimator of "true" classification quality, and P2) they often admit many (suboptimal) solutions. This paper introduces an algorithm that uses cluster validity to mitigate P1 and P2. The validity-guided (re)clustering (VGC) algorithm uses cluster-validity information to guide a fuzzy (re)clustering process toward better solutions. It starts with a partition generated by a soft or fuzzy clustering algorithm. Then it iteratively alters the partition by applying (novel) split-and-merge operations to the clusters. Partition modifications that result in improved partition validity are retained. VGC is tested on both synthetic and real-world data. For magnetic resonance image (MRI) segmentation, evaluations by radiologists show that VGC outperforms the (unsupervised) fuzzy c-means algorithm, and VGC's performance approaches that of the (supervised) k-nearest-neighbors algorithm. © 1996 IEEE.