A distance-based point-reassignment heuristic for the k-hyperplane clustering problem. Amaldi, E. & Coniglio, S. European Journal of Operational Research, 227(1):22-29, Elsevier B.V., 5, 2013.
![A distance-based point-reassignment heuristic for the k-hyperplane clustering problem [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper ![A distance-based point-reassignment heuristic for the k-hyperplane clustering problem [link]](https://bibbase.org/img/filetypes/link.svg "link")
Website abstract bibtex
Paper Website abstract bibtex We consider the k-Hyperplane Clustering problem where, given a set of m points in Rn, 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 squares of the Euclidean distances between the points and the hyperplane of the corresponding clusters. 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 best available one proposed by Bradley and Mangasarian on a set of real-world and structured randomly generated instances. For the largest instances, we obtain an average improvement in the solution quality of 54%. © 2012 Elsevier B.V. All rights reserved.
@article{
title = {A distance-based point-reassignment heuristic for the k-hyperplane clustering problem},
type = {article},
year = {2013},
identifiers = {[object Object]},
keywords = {Data mining,Heuristics,Nonlinear programming},
pages = {22-29},
volume = {227},
websites = {http://linkinghub.elsevier.com/retrieve/pii/S037722171200690X},
month = {5},
publisher = {Elsevier B.V.},
id = {df1b8ccd-d8af-3f9f-9bb2-da7bee15c9b6},
created = {2015-03-23T18:50:22.000Z},
accessed = {2014-10-31},
file_attached = {true},
profile_id = {756a70ce-605d-3e50-9cbb-a99c29afcbe8},
group_id = {1f5b486a-d8ac-3a35-9104-56111360dab7},
last_modified = {2017-03-14T11:36:44.206Z},
read = {true},
starred = {false},
authored = {false},
confirmed = {true},
hidden = {false},
citation_key = {Amaldi2013},
private_publication = {false},
abstract = {We consider the k-Hyperplane Clustering problem where, given a set of m points in Rn, 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 squares of the Euclidean distances between the points and the hyperplane of the corresponding clusters. 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 best available one proposed by Bradley and Mangasarian on a set of real-world and structured randomly generated instances. For the largest instances, we obtain an average improvement in the solution quality of 54%. © 2012 Elsevier B.V. All rights reserved.},
bibtype = {article},
author = {Amaldi, Edoardo and Coniglio, Stefano},
journal = {European Journal of Operational Research},
number = {1}
}Downloads: 0
{"_id":"jMe3KA9Mby52hM8kM","bibbaseid":"amaldi-coniglio-adistancebasedpointreassignmentheuristicforthekhyperplaneclusteringproblem-2013","downloads":0,"creationDate":"2018-03-26T07:07:40.602Z","title":"A distance-based point-reassignment heuristic for the k-hyperplane clustering problem","author_short":["Amaldi, E.","Coniglio, S."],"year":2013,"bibtype":"article","biburl":null,"bibdata":{"title":"A distance-based point-reassignment heuristic for the k-hyperplane clustering problem","type":"article","year":"2013","identifiers":"[object Object]","keywords":"Data mining,Heuristics,Nonlinear programming","pages":"22-29","volume":"227","websites":"http://linkinghub.elsevier.com/retrieve/pii/S037722171200690X","month":"5","publisher":"Elsevier B.V.","id":"df1b8ccd-d8af-3f9f-9bb2-da7bee15c9b6","created":"2015-03-23T18:50:22.000Z","accessed":"2014-10-31","file_attached":"true","profile_id":"756a70ce-605d-3e50-9cbb-a99c29afcbe8","group_id":"1f5b486a-d8ac-3a35-9104-56111360dab7","last_modified":"2017-03-14T11:36:44.206Z","read":"true","starred":false,"authored":false,"confirmed":"true","hidden":false,"citation_key":"Amaldi2013","private_publication":false,"abstract":"We consider the k-Hyperplane Clustering problem where, given a set of m points in Rn, 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 squares of the Euclidean distances between the points and the hyperplane of the corresponding clusters. 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 best available one proposed by Bradley and Mangasarian on a set of real-world and structured randomly generated instances. For the largest instances, we obtain an average improvement in the solution quality of 54%. © 2012 Elsevier B.V. All rights reserved.","bibtype":"article","author":"Amaldi, Edoardo and Coniglio, Stefano","journal":"European Journal of Operational Research","number":"1","bibtex":"@article{\n title = {A distance-based point-reassignment heuristic for the k-hyperplane clustering problem},\n type = {article},\n year = {2013},\n identifiers = {[object Object]},\n keywords = {Data mining,Heuristics,Nonlinear programming},\n pages = {22-29},\n volume = {227},\n websites = {http://linkinghub.elsevier.com/retrieve/pii/S037722171200690X},\n month = {5},\n publisher = {Elsevier B.V.},\n id = {df1b8ccd-d8af-3f9f-9bb2-da7bee15c9b6},\n created = {2015-03-23T18:50:22.000Z},\n accessed = {2014-10-31},\n file_attached = {true},\n profile_id = {756a70ce-605d-3e50-9cbb-a99c29afcbe8},\n group_id = {1f5b486a-d8ac-3a35-9104-56111360dab7},\n last_modified = {2017-03-14T11:36:44.206Z},\n read = {true},\n starred = {false},\n authored = {false},\n confirmed = {true},\n hidden = {false},\n citation_key = {Amaldi2013},\n private_publication = {false},\n abstract = {We consider the k-Hyperplane Clustering problem where, given a set of m points in Rn, 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 squares of the Euclidean distances between the points and the hyperplane of the corresponding clusters. 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 best available one proposed by Bradley and Mangasarian on a set of real-world and structured randomly generated instances. For the largest instances, we obtain an average improvement in the solution quality of 54%. © 2012 Elsevier B.V. All rights reserved.},\n bibtype = {article},\n author = {Amaldi, Edoardo and Coniglio, Stefano},\n journal = {European Journal of Operational Research},\n number = {1}\n}","author_short":["Amaldi, E.","Coniglio, S."],"urls":{"Paper":"https://bibbase.org/service/mendeley/756a70ce-605d-3e50-9cbb-a99c29afcbe8/file/5c17adc1-6100-cc3d-6f0d-12032819bdb8/2013-A_distance-based_point-reassignment_heuristic_for_the_k-hyperplane_clustering_problem.pdf.pdf","Website":"http://linkinghub.elsevier.com/retrieve/pii/S037722171200690X"},"bibbaseid":"amaldi-coniglio-adistancebasedpointreassignmentheuristicforthekhyperplaneclusteringproblem-2013","role":"author","keyword":["Data mining","Heuristics","Nonlinear programming"],"downloads":0},"search_terms":["distance","based","point","reassignment","heuristic","hyperplane","clustering","problem","amaldi","coniglio"],"keywords":["data mining","heuristics","nonlinear programming"],"authorIDs":[]}