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 |

1) Download Document PDF |

2) Download Document PDF |

Open access Restricted Private