CLUSTERING WITH NEURAL NETWORKS

Partitioning a set of N patterns in a d-dimensional metric space into K clusters - in a way that those in a given cluster are more similar to each other than the rest - is a problem of interest in many fields, such as, image analysis, taxonomy, astrophysics, etc. As there are approximately KN/K! possible ways of partitioning the patterns among K clusters, finding the best solution is beyond exhaustive search when N is large. We show that this problem, in spite of its exponential complexity, can be formulated as an optimization problem for which very good, but not necessarily optimal, solutions can be found by using a Hopfield model of neural networks. To obtain a very good solution, the network must start from many randomly selected initial states. The network is simulated on the MPP, a 128 × 128 SIMD array machine, where we use the massive parallelism not only in solving the differential equations that govern the evolution of the network, but also in starting the network from many initial states at once thus obtaining many solutions in one run. We achieve speedups of two to three orders of magnitude over serial implementations and the promise through Analog VLSI implementations of further speedups of three to six orders of magnitude. © 1990 Springer-Verlag.