You are here

Boundary compensated k-NN graphs

TitleBoundary compensated k-NN graphs
Publication TypeConference Paper
Year of Publication2010
AuthorsSricharan, K., R. Raich, and A. O. Hero, III
Conference Name2010 IEEE International Workshop on Machine Learning for Signal Processing (MLSP)
Pagination277 - 282
Date Published09/2010
Conference LocationKittila, Finland
ISBN Number978-1-4244-7875-0

The k-nearest neighbor (k-NN) graph conveys local geometry of points in a sample. This attribute has resulted in a wide variety of machine learning applications for k-NN graphs, for e.g., density estimation, manifold learning and non-parametric classification. For samples with finite support, our analysis shows that k-NN density estimators behave differently in the interior of the support as opposed to near the boundary of the support. Motivated by our analysis, we propose improving the behavior of k-NN graphs by thinning its edges near the boundary. We illustrate the advantages of such boundary corrected k-NN graphs for entropy estimation and classification.