Cluster differences scaling with a within-clusters loss component and a fuzzy successive approximation strategy to avoid local minima. (English) Zbl 0889.92037

Summary: Cluster differences scaling is a method for partitioning a set of objects into classes and simultaneously finding a low-dimensional spatial representation of \(K\) cluster points, to model a given square table of dissimilarities among \(n\) stimuli or objects. The least squares loss function of cluster differences scaling, originally defined only on the residuals of pairs of objects that are allocated to different clusters, is extended with a loss component for pairs that are allocated to the same cluster. It is shown that this extension makes the method equivalent to multidimensional scaling with cluster constraints on the coordinates.
A decomposition of the sum of squared dissimilarities into contributions from several sources of variation is described, including the appropriate degrees of freedom for each source. After developing a convergent algorithm for fitting the cluster differences model, it is argued that the individual objects and the cluster locations can be jointly displayed in a configuration obtained as a by-product of the optimization. Finally, the paper introduces a fuzzy version of the loss function, which can be used in a successive approximation strategy for avoiding local minima. A simulation study demonstrates that this strategy significantly outperforms two other well-known initialization strategies, and that it has a success rate of 92 out of 100 in attaining the global minimum.


91C15 One- and multidimensional scaling in the social and behavioral sciences
62P15 Applications of statistics to psychology
91C20 Clustering in the social and behavioral sciences


AS 136
Full Text: DOI


[1] Anderson, E. (1935). The Irises of the Gaspe peninsula.Bulletin of the American Iris Society, 59, 2–5.
[2] Ball, G. H., & Hall, D. J. (1967). A clustering technique for summarizing multivariate data.Behavioral Science, 12, 153–155.
[3] Banfield, C. F., & Bassill, L. C. (1977). Algorithm AS113. A transfer algorithm for non-hierarchical classification.Applied Statistics, 26, 206–210.
[4] Bezdek, J. C. (1973).Fuzzy mathematics in pattern classification. Unpublished doctoral dissertation, Cornell University, Ithaca.
[5] Bezdek, J. C. (1981).Pattern recognition with fuzzy objective function algorithms. New York: Plenum. · Zbl 0503.68069
[6] Bezdek, J. C., & Dunn, J. C. (1975). Optimal fuzzy partitions: A heuristic for estimating the parameters in a mixture of normal distributions.IEEE Transactions on Computers, Series C, 24, 835–838. · Zbl 0308.68078
[7] Bock, H.-H. (1979). Fuzzy clustering procedures. In R. Tomassone (Ed.),Analyse des Donneés et Informatique [Data analysis and informatics] (pp. 205–218). Le Chesnay, France: INRIA.
[8] Bock, H.-H. (1986). Multidimensional scaling in the framework of cluster analysis. In P. O. Degens, H.-J. Hermes & O. Opitz (Eds.),Studien zur Klassifikation: Vol. 17 [Classification and its environment] (pp. 247–258). Frankfurt: INDEKS-Verlag.
[9] Bock, H.-H. (1987). On the interface between cluster analysis, principal component analysis, and multidimensional scaling. In H. Bozdogan & A. K. Gupta (Eds.),Multivariate statistical modeling and data analysis (pp. 17–34). New York: Reidel. · Zbl 0627.62068
[10] de Leeuw, J. (1992).Fitting distances by least squares. Unpublished manuscript.
[11] de Leeuw, J., & Heiser, W. J. (1980). Multidimensional scaling with restrictions on the configuration. In P. R. Krishnaiah (Ed.),Multivariate analysis, Vol. V (pp. 501–522). Amsterdam: North-Holland. · Zbl 0468.62054
[12] Draper, N. R., & Smith, H. (1966).Applied regression analysis. New York: Wiley. · Zbl 0158.17101
[13] Dunn, J. C. (1974). A fuzzy relative of the ISODATA process and its use in detecting compact well separated clusters.Journal of Cybernetics, 3, 32–57. · Zbl 0291.68033
[14] Fisher, R. A. (1936). The use of multiple measurements in taxonomic problems.Annals of Eugenics, 7, 179–188.
[15] Fisher, W. D. (1958). On grouping for maximum homogeneity.Journal of the American Statistical Association, 53, 789–798. · Zbl 0084.35904
[16] Gordon, A. D. (1981).Classification: Methods for the explorator analysis of multivariate data. London: Chapman and Hall. · Zbl 0507.62057
[17] Gordon, A. D., & Henderson, J. T. (1977). An algorithm for Euclidean sum of squares classification.Biometrics, 33, 355–362. · Zbl 0357.62038
[18] Gower, J. C. (1989). Generalised canonical analysis. In R. Coppi & S. Bolasco (Eds.),Multiway data analysis (pp. 221–232). Amsterdam: North-Holland.
[19] Groenen, P. J. F. (1993).The majorization approach to multidimensional scaling: Some problems and extensions. Doctoral Dissertation. Leiden: DSWO Press. · Zbl 0898.62080
[20] Guttman, L. (1968). A general nonmetric technique for finding the smallest coordinate space for a configuration of points.Psychometrika, 33, 469–506. · Zbl 0205.49302
[21] Hartigan, J. A., & Wong, M. A. (1979). Algorithm AS 136: AK-means clustering algorithm.Applied Statistics, 28, 100–108. · Zbl 0447.62062
[22] Heiser, W. J. (1993). Clustering in low-dimensional space. In O. Opitz, B. Lausen, & R. Klar (Eds.),Information and classification: Concepts, methods and applications (pp. 162–173). Heidelberg: Springer Verlag.
[23] Heiser, W. J., & Groenen, P. J. F. (1993, June).Stress decomposition and use of fuzzy memberships in cluster differences scaling. Paper presented at the annual meeting of the Psychometric Society, Berkeley, California.
[24] Kernighan, B. W., & Lin, S. (1970). An efficient heuristic procedure for partitioning graphs.Bell Systems Technical Journal, 49, 291–307. · Zbl 0333.05001
[25] Kruskal, J. B. (1977). The relationship between multidimensional scaling and clustering. In J. Van Ryzin (Ed.),Classification and clustering (pp. 17–44). New York: Academic Press.
[26] Rao, C. R. (1955). Analysis of dispersion for multiple classified data with unequal numbers in cells.Sankhyā, 15, 253–280. · Zbl 0067.12004
[27] Rao, C. R. (1973).Linear statistical inference and its applications (2nd ed.). New York: Wiley. · Zbl 0256.62002
[28] Ruspini, E. (1970). Numerical methods for fuzzy clustering.Information Science, 2, 319–350. · Zbl 0205.21301
[29] Selim, S. Z., & Ismail, M. A. (1984).K-means-type algorithms: A generalized convergence theorem and characterization of local optimality.IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6, 81–87. · Zbl 0546.62037
[30] Shepard, R. N. (1962). The analysis of proximities: multidimensional scaling with an unknown distance function I & II.Psychometrika, 27, 125–140 & 219–246. · Zbl 0129.12103
[31] Sokal, R. R., & Michener, C. D. (1958). A statistical method for evaluating systematic relationships.The University of Kansas Science Bulletin, 38, 1409–1438.
[32] Späth, H. (1985).Cluster dissection and analysis. Chichester: Ellis Horwood. · Zbl 0584.62094
[33] Tijssen, R. J. W. (1992).Cartography of science: Scientometric mapping with multidimensional scaling methods. Doctoral dissertation. Leiden: DSWO Press.
[34] Tobler, W. (1976). Spatial interaction patterns.Journal of Environmental Systems, 6, 271–301.
[35] Wedel, M. (1990).Clusterwise regression and market segmentation: Developments and applications. Unpublished doctoral dissertation, University of Wageningen.
[36] Zadeh, L. A. (1977). Fuzzy sets and their application to pattern classification and clustering analysis. In J. Van Ryzin (Ed.),Classification and clustering (pp. 251–299). New York: Academic Press.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.