Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-01-08T11:53:11.048Z Has data issue: false hasContentIssue false
  • English
  • Français

The Local Minima Problem in Hierarchical Classes Analysis: An Evaluation of a Simulated Annealing Algorithm and Various Multistart Procedures

Published online by Cambridge University Press:  01 January 2025

Eva Ceulemans ,
Iven Van Mechelen  and
Iwin Leenen
Eva Ceulemans*
Affiliation:
Katholieke Universiteit Leuven
Iven Van Mechelen
Affiliation:
Katholieke Universiteit Leuven
Iwin Leenen
Affiliation:
Universidad Complutense de Madrid
*
Requests for reprints should be sent to Eva Ceulemans, Department of Psychology, Tiensestraat 102, B-3000 Leuven, Belgium. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Hierarchical classes models are quasi-order retaining Boolean decomposition models for N-way N-mode binary data. To fit these models to data, rationally started alternating least squares (or, equivalently, alternating least absolute deviations) algorithms have been proposed. Extensive simulation studies showed that these algorithms succeed quite well in recovering the underlying truth but frequently end in a local minimum. In this paper we evaluate whether or not this local minimum problem can be mitigated by means of two common strategies for avoiding local minima in combinatorial data analysis: simulated annealing (SA) and use of a multistart procedure. In particular, we propose a generic SA algorithm for hierarchical classes analysis and three different types of random starts. The effectiveness of the SA algorithm and the random starts is evaluated by reanalyzing data sets of previous simulation studies. The reported results support the use of the proposed SA algorithm in combination with a random multistart procedure, regardless of the properties of the data set under study.

Keywords

hierarchical classesHICLASTucker3-HICLASmultiway clusteringsimulated annealing
Type
Theory and Methods
Information
Psychometrika , Volume 72 , Issue 3 , September 2007 , pp. 377 - 391
Copyright
Copyright © 2007 The Psychometric Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Eva Ceulemans is a post-doctoral fellow of the Fund for Scientific Research Flanders (Belgium). Iwin Leenen is a post-doctoral researcher of the Spanish Ministerio de Educación y Ciencia (programa Ramón y Cajal). The research reported in this paper was partially supported by the Research Council of K.U. Leuven (GOA/05/04).

References

Aarts, E.H., & Lenstra, J.K. (1997). Local search in combinatorial optimization. Chichester, UK: Wiley.Google Scholar
Al-Sultan, K.S., Khan, M.M. (1996). Computational experience on four algorithms for the hard clustering problem. Pattern Recognition Letters, 17, 295–308.CrossRefGoogle Scholar
Brusco, M.J. (2001). A simulated annealing heuristic for unidimensional and multidimensional (city-block) scaling of symmetric proximity matrices. Journal of Classification, 18, 3–33.CrossRefGoogle Scholar
Brusco, M.J., Stahl, S. (2000). Using quadratic assignment methods to generate initial permutations for least-squares unidimensional scaling of symmetric proximity matrices. Journal of Classification, 17, 197–223.CrossRefGoogle Scholar
Ceulemans, E., Van Mechelen, I. (2004). Tucker2 hierarchical classes analysis. Psychometrika, 69, 375–399.CrossRefGoogle Scholar
Ceulemans, E., Van Mechelen, I. (2005). Hierarchical classes models for three-way three-mode binary data: Interrelations and model selection. Psychometrika, 70, 1–20.CrossRefGoogle Scholar
Ceulemans, E., Van Mechelen, I., Leenen, I. (2003). Tucker3 hierarchical classes analysis. Psychometrika, 68, 413–433.CrossRefGoogle Scholar
De Boeck, P., Rosenberg, S. (1988). Hierarchical classes: Model and data analysis. Psychometrika, 53, 361–381.CrossRefGoogle Scholar
Gara, M., Rosenberg, S. (1990). A set-theoretical model of person perception. Behavioral Research, 25, 275–293.Google ScholarPubMed
Hand, D.J., Krzanowski, W.J. (2005). Optimising k-means clustering results with standard software packages. Computational Statistics and Data Analysis, 49, 969–973.CrossRefGoogle Scholar
Hubert, L., Arabie, P., Hesson-McInnis, M. (1992). Multidimensional-scaling in the city-block metric—a combinatorial approach. Journal of Classification, 9, 211–236.CrossRefGoogle Scholar
Klein, R.W., Dubes, R.C. (1989). Experiments in projection and clustering by simulated annealing. Pattern Recognition, 22, 213–220.CrossRefGoogle Scholar
Kuppens, P., Van Mechelen, I., Smits, D.J.M., De Boeck, P., Ceulemans, E. (2007). Individual differences in patterns of appraisal and anger experience. Cognition & Emotion, 21, 689–713.CrossRefGoogle Scholar
Leenen, I., Van Mechelen, I. (1998). A branch-and-bound algorithm for Boolean regression. In Balderjahn, I., Mathar, R., Schader, M. (Eds.), Data highways and information flooding, A challenge for classification and data analysis (pp. 164–171). Berlin: Springer.CrossRefGoogle Scholar
Leenen, I., Van Mechelen, I. (2001). An evaluation of two algorithms for hierarchical classes analysis. Journal of Classification, 18, 57–80.CrossRefGoogle Scholar
Leenen, I., Van Mechelen, I., De Boeck, P., Rosenberg, S. (1999). indclas: A three-way hierarchical classes model. Psychometrika, 64, 9–24.CrossRefGoogle Scholar
Milligan, G.W. (1980). An examination of the effect of six types of error perturbation on fifteen clustering algorithms. Psychometrika, 45, 325–342.CrossRefGoogle Scholar
Murillo, A., Vera, J.F., Heiser, W.J. (2005). A permutation-translation simulated annealing algorithm for l 1 and l 2 unidimensional scaling. Journal of Classification, 22, 119–138.CrossRefGoogle Scholar
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, 6, 81–87.CrossRefGoogle ScholarPubMed
Steinley, D. (2003). Local optima in k-means clustering: What you don’t know may hurt you. Psychological Methods, 8, 294–304.CrossRefGoogle ScholarPubMed
Van Mechelen, I., De Boeck, P. (1989). Implicit taxonomy in psychiatric diagnosis: A case study. Journal of Social and Clinical Psychology, 8, 276–287.CrossRefGoogle Scholar
Van Mechelen, I., Van Damme, G. (1994). A latent criteria model for choice data. Acta Psychologica, 87, 85–94.CrossRefGoogle Scholar
Van Mechelen, I., De Boeck, P., Rosenberg, S. (1995). The conjunctive model of hierarchical classes. Psychometrika, 60, 505–521.CrossRefGoogle Scholar
Vansteelandt, K., Van Mechelen, I. (1998). Individual differences in situation-behavior profiles: A triple typology model. Journal of Personality and Social Psychology, 75, 751–765.CrossRefGoogle Scholar
Vansteelandt, K., Van Mechelen, I. (2006). Individual differences in anger and sadness: In pursuit of active situational features and psychological processes. Journal of Personality, 74, 871–909.CrossRefGoogle ScholarPubMed