A local search approach to silhouette-based clustering

Clustering aims to split a set of objects into k groups (called clusters), in such a way each cluster contains similar objects and dissimilar objects find place in different clusters. The silhouette coefficient is a metric which is widely used to evaluate the goodness of a clustering. In this thesis are presented some methods to solve the clustering problem by optimizing the silhouette. The optimization is done by means of local search techniques. The proposed algorithms underwent an exhaustive phase of testing, in comparison with the standard ones, on both real and synthetic datasets. From the results we can see how one of the proposed algorithms can be competitive with Lloyd’s algorithm for k-means and also overcame other standard algorithms such as PAM for k-medoids.