G-2000-06
Exact Sequential Algorithms for Additive Clustering
, et référence BibTeX
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.
Paru en mars 2000 , 30 pages
Axes de recherche
Applications de recherche
Document
G0006.ps (480 Ko)