Clustering Stability: An Overview provides a high-level overview about the existing literature on clustering stability. It reviews different protocols for how clustering stability is computed and used for model selection. The main body of the text goes on to examine theoretical results for the K-means algorithm and discuss their various relations. Finally, it looks at results for more general clustering algorithms. In addition to presenting the results in a slightly informal but accessible way, Clustering Stability: An Overview relates them to each other and discusses their different implications.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Stability Analysis of the KMeans Algorithm
actual K-means algorithm algorithm is stable argmin Assume based on clustering Ben-David Ben-Hur Carnegie Mellon University center-based clustering central limit theorem clus cluster boundaries cluster centers clustering algorithm clustering objective functions clustering results clustering stability Conclusion 3.3 Conjecture 3.4 convergence convergence in distribution correct number corresponding data points different clusterings different local optima different samples finite sample high-density region idealized K-means algorithm initial centers initialization scheme Instab(K,n instable clusterings jumping between different K-means clustering K-means objective function Kinit leads to instability Learning Theory COLT low-density regions Luxburg Machine Learning methods minimal matching distance normalized stability null distribution number of clusters objective function Q(∞)K original data set parameter preliminary centers probability distribution Rand index random initialization rescaled instability results of Theorem RInstab Section 3.2 space stability results statistical step of K-means subsamples symmetric tering Theorem 3.2 top two clusters true clusters underlying distribution unique global minimum unique global optimum