We consider the k-Hyperplane Clustering problem where, given a set of m points in R^n, we have to partition the set into k subsets (clusters) and determine a hyperplane for each of them, so as to minimize the sum of the square of the Euclidean distance between each point and the hyperplane of the corresponding cluster. We give a nonconvex mixed-integer quadratically constrained quadratic programming formulation for the problem. Since even very small-size instances are challenging for state-of-the-art spatial branch-and-bound solvers like Couenne, we propose a heuristic in which many critical points are reassigned at each iteration. Such points, which are likely to be ill-assigned in the current solution, are identified using a distance-based criterion and their number is progressively decreased to zero. Our algorithm outperforms the state-of-the-art one proposed by Bradley and Mangasarian on a set of real-world and structured randomly generated instances. For the largest group of instances, we obtain an average improvement in the solution quality of 54%.

(2013). A distance-based point-reassignment heuristic for the k-hyperplane clustering problem [journal article - articolo]. In EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. Retrieved from http://hdl.handle.net/10446/229296

A distance-based point-reassignment heuristic for the k-hyperplane clustering problem

Coniglio, Stefano
2013-01-01

Abstract

We consider the k-Hyperplane Clustering problem where, given a set of m points in R^n, we have to partition the set into k subsets (clusters) and determine a hyperplane for each of them, so as to minimize the sum of the square of the Euclidean distance between each point and the hyperplane of the corresponding cluster. We give a nonconvex mixed-integer quadratically constrained quadratic programming formulation for the problem. Since even very small-size instances are challenging for state-of-the-art spatial branch-and-bound solvers like Couenne, we propose a heuristic in which many critical points are reassigned at each iteration. Such points, which are likely to be ill-assigned in the current solution, are identified using a distance-based criterion and their number is progressively decreased to zero. Our algorithm outperforms the state-of-the-art one proposed by Bradley and Mangasarian on a set of real-world and structured randomly generated instances. For the largest group of instances, we obtain an average improvement in the solution quality of 54%.
articolo
Amaldi, Edoardo; Coniglio, Stefano
(2013). A distance-based point-reassignment heuristic for the k-hyperplane clustering problem [journal article - articolo]. In EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. Retrieved from http://hdl.handle.net/10446/229296
File allegato/i alla scheda:
File Dimensione del file Formato  
k-Hyperplane-Clustering-EJOR-03.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 535.14 kB
Formato Adobe PDF
535.14 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/229296
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact