English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

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

Maier, M., Hein, M., & von Luxburg, U. (2009). Optimal construction of k-nearest-neighbor graphs for identifying noisy clusters. Theoretical computer science, 410(19), 1749-1764. doi:10.1016/j.tcs.2009.01.009.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0013-C529-5 Version Permalink: http://hdl.handle.net/21.11116/0000-0002-C813-7
Genre: Journal Article

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Maier, M1, 2, Author              
Hein, M, Author
von Luxburg, U1, 2, Author              
Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795              
2Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794              

Content

show
hide
Free keywords: -
 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 logn) 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.

Details

show
hide
Language(s):
 Dates: 2009-04
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1016/j.tcs.2009.01.009
BibTex Citekey: 5681
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Theoretical computer science
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: Amsterdam : Elsevier
Pages: - Volume / Issue: 410 (19) Sequence Number: - Start / End Page: 1749 - 1764 Identifier: ISSN: 0304-3975
CoNE: https://pure.mpg.de/cone/journals/resource/954925512450