We study clustering algorithms based on neighborhood graphs on a random sample of data points. The question we ask is how such a graph should be constructed in order to obtain optimal clustering results. Which type of neighborhood graph should one choose, mutual knearestneighbor or symmetric knearestneighbor? What is the optimal parameter k? In our setting, clusters are defined as connected components of the tlevel set of the underlying probability distribution. Clusters are said to be identified in the neighborhood graph if connected components in the graph correspond to the true underlying clusters. Using techniques from random geometric graph theory, we prove bounds on the probability that clusters are identified successfully, both in a noisefree and in a noisy setting. Those bounds lead to several conclusions. First, k has to be chosen surprisingly high (rather of the order n than of the order logn) to maximize the probability of cluster identification. Secondly, the major difference between the mutual and the symmetric knearestneighbor graph occurs when one attempts to detect the most significant cluster only.
Author(s):  Maier, M. and Hein, M. and von Luxburg, U. 
Journal:  Theoretical Computer Science 
Volume:  410 
Number (issue):  19 
Pages:  17491764 
Year:  2009 
Month:  April 
Day:  0 
Department(s):  Empirical Inference 
Bibtex Type:  Article (article) 
Digital:  0 
DOI:  10.1016/j.tcs.2009.01.009 
Language:  en 
Organization:  MaxPlanckGesellschaft 
School:  Biologische Kybernetik 
Links: 
PDF

BibTex @article{5681, title = {Optimal construction of knearestneighbor graphs for identifying noisy clusters}, author = {Maier, M. and Hein, M. and von Luxburg, U.}, journal = {Theoretical Computer Science}, volume = {410}, number = {19}, pages = {17491764}, organization = {MaxPlanckGesellschaft}, school = {Biologische Kybernetik}, month = apr, year = {2009}, month_numeric = {4} } 