PCT - a technique to probe cluster terrain

Abstract

We present a novel technique called probing cluster terrain (PCT) useful for exploring the terrain (shape and size) of individual clusters contained in input X = {x(i), i = 1,...,n}, even if X was not previously partitioned. A covariance matrix C-t(v(j)) is employed as an explorer to probe the terrain of the cluster centered at v(j). Associated with C-t(v(j)) is a ring formed with the formula for Mahalanobis distance. The kernel of PCT is an alternating process that minimizes a well-defined objective function J. The most intriguing behavior of PCT is that the ring actually expands to discover data points of the cluster in the course of minimizing J. Stability of PCT is analyzed, and promising applications of PCT are described. We show that PCT can be incorporated with other clustering algorithms to improve clustering accuracy, or it can be used to perform cluster validation. (C) 2002 Elsevier Science B.V. All rights reserved.