Mapclus: A mathematical programming approach to fitting the adclus model

We present a new algorithm, MAPCLUS (MAthematicalProgrammingCLUStering), for fitting the Shepard-Arabie ADCLUS (forADditiveCLUStering) model. MAPCLUS utilizes an alternating least squares method combined with a mathematical programming optimization procedure based on a penalty function approach, to impose discrete (0,1) constraints on parameters defining cluster membership. This procedure is supplemented by several other numerical techniques (notably a heuristically based combinatorial optimization procedure) to provide an efficient general-purpose computer implemented algorithm for obtaining ADCLUS representations. MAPCLUS is illustrated with an application to one of the examples given by Shepard and Arabie using the older ADCLUS procedure. The MAPCLUS solution uses half as many clusters to achieve nearly the same level of goodness-of-fit. Finally, we consider an extension of the present approach to fitting a three-way generalization of the ADCLUS model, called INDCLUS (INdividualDifferencesCLUStering).We are indebted to Scott A. Boorman, W. K. Estes, J. A. Hartigan, Lawrence J. Hubert, Carol L. Krumhansl, Joseph B. Kruskal, Sandra Pruzansky, Roger N. Shepard, Edward J. Shoben, Sigfrid D. Soli, and Amos Tversky for helpful discussions of this work, as well as the anonymous referees for their suggestions and corrections on an earlier version of this paper. We are also grateful to Pamela Baker and Dan C. Knutson for technical assistance. The research reported here was supported in part by LEAA Grant 78-NI-AX-0142 and NSF Grants SOC76-24512 and SOC76-24394.