Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters

TLDR

A family of graph‑theoretical algorithms based on the minimal spanning tree can detect various cluster structures in arbitrary point sets and extend to higher‑dimensional and general metric spaces. The authors developed these clustering algorithms to emulate human perception of gestalts in two‑dimensional space and discuss applications to taxonomy and feature‑space selection for pattern recognition. The methods are illustrated through detailed analyses of planar cluster detection problems, with implementations in PL/1. These methods offer determinacy, easy cluster interpretation, conformity to gestalt principles, invariance under monotone distance transformations, and have been successfully applied to Fisher iris data and implemented in debugged PL/1 programs.

Abstract

A family of graph-theoretical algorithms based on the minimal spanning tree are capable of detecting several kinds of cluster structure in arbitrary point sets; description of the detected clusters is possible in some cases by extensions of the method. Development of these clustering algorithms was based on examples from two-dimensional space because we wanted to copy the human perception of gestalts or point groupings. On the other hand, all the methods considered apply to higher dimensional spaces and even to general metric spaces. Advantages of these methods include determinacy, easy interpretation of the resulting clusters, conformity to gestalt principles of perceptual organization, and invariance of results under monotone transformations of interpoint distance. Brief discussion is made of the application of cluster detection to taxonomy and the selection of good feature spaces for pattern recognition. Detailed analyses of several planar cluster detection problems are illustrated by text and figures. The well-known Fisher iris data, in four-dimensional space, have been analyzed by these methods also. PL/1 programs to implement the minimal spanning tree methods have been fully debugged.