×

Optimal construction of \(k\)-nearest-neighbor graphs for identifying noisy clusters. (English) Zbl 1167.68045

Summary: 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.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C80 Random graphs (graph-theoretic aspects)
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bettstetter, C., On the minimum node degree and connectivity of a wireless multihop network, (MobiHoc’02: Proceedings of the 3rd ACM International Symposium on Mobile ad hoc Networking & Computing (2002), ACM: ACM New York, NY, USA), 80-91
[2] Biau, G.; Cadre, B.; Pelletier, B., A graph-based estimator of the number of clusters, ESIAM Probab. Statist., 11, 272-280 (2007) · Zbl 1187.62114
[3] Bollobas, B., Random Graphs (2001), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0997.05049
[4] Bollobas, B.; Riordan, O., Percolation (2006), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1118.60001
[5] Brito, M.; Chavez, E.; Quiroz, A.; Yukich, J., Connectivity of the mutual \(k\)-nearest-neighbor graph in clustering and outlier detection, Statist. Probab. Lett., 35, 33-42 (1997) · Zbl 0898.62077
[6] Devroye, L.; Lugosi, G., Combinatorial Methods in Density Estimation (2001), Springer: Springer New York · Zbl 0964.62025
[7] Federer, H., (Geometric Measure Theory. Geometric Measure Theory, Die Grundlehren der mathematischen Wissenschaften, vol. 153 (1969), Springer-Verlag)
[8] Hartigan, J., Consistency of single linkage for high-density clusters, J. Amer. Statist. Assoc., 76, 388-394 (1981) · Zbl 0468.62053
[9] Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58, 13-30 (1963) · Zbl 0127.10602
[10] Kunniyur, S. S.; Venkatesh, S. S., Threshold functions, node isolation, and emergent lacunae in sensor networks, IEEE Trans. Inform. Theory, 52, 12, 5352-5372 (2006) · Zbl 1309.94050
[11] Maier, M.; Hein, M.; von Luxburg, U., Cluster identification in nearest-neighbor graphs, (Hutter, M.; Servedio, R.; Takimoto, E., Proc. of the 18th Conf. on Algorithmic Learning Theory. Proc. of the 18th Conf. on Algorithmic Learning Theory, ALT (2007), Springer: Springer Berlin), 196-210 · Zbl 1142.68401
[12] Penrose, M., Random Geometric Graphs (2003), Oxford University Press: Oxford University Press Oxford · Zbl 1029.60007
[13] Rao, B. L.S. P., Nonparametric Functional Estimation (1983), Academic Press: Academic Press New York · Zbl 0542.62025
[14] Santi, P.; Blough, D., The critical transmitting range for connectivity in sparse wireless ad hoc networks, IEEE Trans. Mobile Computing, 02, 1, 25-39 (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.