Summary

In this chapter, we introduced the k-means algorithm, which is based on the idea of defining (randomly or according to some criteria) k centroids that represent the clusters and optimize their position so that the sum of squared distances for every point in each cluster and the centroid is minimum. As the distance is a radial function, k-means assumes clusters to be convex and cannot solve problems where the shapes have deep concavities (like the half-moon problem). In order to solve such situations, we presented two alternatives. The first one is called DBSCAN and is a simple algorithm that analyzes the difference between points surrounded by other samples and boundary samples. In this way, it can easily determine high-density areas (which become clusters) and low-density spaces among them. There are no assumptions about the shape or the number of clusters, so it's necessary to tune up the other parameters so as to generate the right number of clusters. Spectral clustering is a...