Groupe d’études et de recherche en analyse des décisions


Exact Sequential Algorithms for Additive Clustering

, et

Mirkin's additive clustering (or qualitative factor analysis) algorithm explains similarities between entities by sequentially finding a cluster of entities and a weight which minimizes the residual sum of squared errors. Simple heuristics are used to find the cluster at each step. We show that this step can be solved exactly by reducing it to a series of quadratic problems in 0-1 variables with a cardinality constraint. These in turn can be reduced to unconstrained quadratic 0-1 programs. Problems with up to 40 entities can be solved exactly. Both the case where weights must be positive and the case where they are unrestricted in sign are considered.

, 30 pages