PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Grossi V., Monreale A., Nanni M., Pedreschi D., Turini F. Clustering formulation using constraint optimization. Domenico Bianculli, Radu Calinescu, Bernhard Rumpe (eds.). (Lecture Notes in Computer Science, vol. 9509). Berlin: Springer, 2015.
 
 
Abstract
(English)
The problem of clustering a set of data is a textbook machine learning problem, but at the same time, at heart, a typical optimization problem. Given an objective function, such as minimizing the intra-cluster distances or maximizing the inter-cluster distances, the task is to find an assignment of data points to clusters that achieves this objective. In this paper, we present a constraint programming model for a centroid based clustering and one for a density based clustering. In particular, as a key contribution, we show how the expressivity introduced by the formulation of the problem by constraint programming makes the standard problem easy to be extended with other constraints that permit to generate interesting variants of the problem. We show this important aspect in two different ways: first, we show how the formulation of the density-based clustering by constraint programming makes it very similar to the label propagation problem and then, we propose a variant of the standard label propagation approach.
URL: http://link.springer.com/chapter/10.1007%2F978-3-662-49224-6_9
DOI: 10.1007/978-3-662-49224-6_9
Subject Clustering
Constraint Programming
G.1.6 Optimization, Constrained optimization
H.3.3 Information Search and Retrieval, Clustering
90C27 Combinatorial optimization
91C20 Clustering


Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional