Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T15:54:30.634Z Has data issue: false hasContentIssue false

Order-Constrained Solutions in K-Means Clustering: Even Better Than Being Globally Optimal

Published online by Cambridge University Press:  01 January 2025

Douglas Steinley*
Affiliation:
University of Missouri-Columbia
Lawrence Hubert
Affiliation:
University of Illinois, Urbana-Champaign
*
Requests for reprints should be sent to Douglas Steinley, Department of Psychological Sciences, University of Missouri-Columbia, 210 McAlester Hall, Columbia, MO 65211, USA. E-mail: steinleyd@missouri.edu

Abstract

This paper proposes an order-constrained K-means cluster analysis strategy, and implements that strategy through an auxiliary quadratic assignment optimization heuristic that identifies an initial object order. A subsequent dynamic programming recursion is applied to optimally subdivide the object set subject to the order constraint. We show that although the usual K-means sum-of-squared-error criterion is not guaranteed to be minimal, a true underlying cluster structure may be more accurately recovered. Also, substantive interpretability seems generally improved when constrained solutions are considered. We illustrate the procedure with several data sets from the literature.

Information

Type
Theory and Methods
Copyright
Copyright © 2008 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.)

Article purchase

Temporarily unavailable