Optimal construction of k-nearest-neighbor graphs for identifying noisy clusters

DOI10.1016/J.TCS.2009.01.009zbMATH Open1167.68045arXiv0912.3408OpenAlexW2122218279MaRDI QIDQ1017654FDOQ1017654

Authors: Markus Maier, Matthias Hein, Ulrike Von Luxburg 

Publication date: 12 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: 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 k-nearest neighbor or symmetric k-nearest neighbor? What is the optimal parameter k? In our setting, clusters are defined as connected components of the t-level 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 noise-free 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 log n) to maximize the probability of cluster identification. Secondly, the major difference between the mutual and the symmetric k-nearest neighbor graph occurs when one attempts to detect the most significant cluster only.

Full work available at URL: https://arxiv.org/abs/0912.3408

Recommendations

• Cluster Identification in Nearest-Neighbor Graphs
• scientific article; zbMATH DE number 1982187
• How the result of graph clustering methods depends on the construction of the graph
• Optimal clustering of multipartite graphs
• Top-\(k\) and clustering with noisy comparisons
• Optimal hierarchical clustering on a graph

zbMATH Keywords

clusteringconnected componentrandom geometric graphneighborhood graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Random Geometric Graphs
• Title not available (Why is that?)
• Consistency of Single Linkage for High-Density Clusters
• Probability Inequalities for Sums of Bounded Random Variables
• A graph-based estimator of the number of clusters
• Connectivity of the mutual \(k\)-nearest-neighbor graph in clustering and outlier detection
• Percolation
• Title not available (Why is that?)
• Paths in graphs
• Combinatorial methods in density estimation
• Cluster Identification in Nearest-Neighbor Graphs
• Threshold Functions, Node Isolation, and Emergent Lacunae in Sensor Networks

Cited In (18)

• On the normalized Laplacian spectra of random geometric graphs
• A Review on Modal Clustering
• Batch edge-removal clustering based on random $k$NN graph
• On clustering procedures and nonparametric mixture estimation
• Level set tree methods
• Nearest neighbor clustering: a baseline method for consistent clustering with arbitrary objective functions
• Title not available (Why is that?)
• The coreness and H-index of random geometric graphs
• Unconstrained and curvature-constrained shortest-path distances and their approximation
• Estimation of level set trees using adaptive partitions
• A survey of neighborhood construction algorithms for clustering and classifying data points
• SELP: semi-supervised evidential label propagation algorithm for graph data clustering
• Noise-enhanced clustering and competitive learning algorithms
• Statistical analysis of a hierarchical clustering algorithm with outliers
• Fully adaptive density-based clustering
• Cluster Identification in Nearest-Neighbor Graphs
• Spectral clustering based on local linear approximations
• Improved spectral convergence rates for graph Laplacians on \(\varepsilon \)-graphs and \(k\)-NN graphs

This page was built for publication: Optimal construction of \(k\)-nearest-neighbor graphs for identifying noisy clusters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1017654)