Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections
Benedetto Manca
2021-01-01
Abstract
This paper investigates a mathematical programming based methodology for solving the minimum sum-of-squares clustering problem, also known as the "k-means problem", in the presence of side constraints. We propose several exact and approximate mixed-integer linear and nonlinear formulations. The approximations are based on norm inequalities and random projections, the approximation guarantees of which are based on an additive version of the Johnson-Lindenstrauss lemma. We perform computational testing (with fixed CPU time) on a range of randomly generated and real data instances of medium size, but with high dimensionality. We show that when side constraints make k-means inapplicable, our proposed methodology-which is easy and fast to implement and deploy-can obtain good solutions in limited amounts of time.File | Size | Format | |
---|---|---|---|
HAL-Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections.pdf open access
Type: versione post-print
Size 537.62 kB
Format Adobe PDF
|
537.62 kB | Adobe PDF | View/Open |
Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections.pdf Solo gestori archivio
Size 563.72 kB
Format Adobe PDF
|
563.72 kB | Adobe PDF | & nbsp; View / Open Request a copy |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.