Scalable and Adaptive KNN for Regression over Graphs

Seth Barrash, Yanning Shen, Georgios B. Giannakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

The family of k-nearest neighbor (k NN) schemes comprises simple and effective algorithms that can be used for general machine learning tasks such as classification and regression. The goal of linear k NN regression is to predict the value of an unseen datum as a linear combination of its k neighbors on a graph, which could be found via certain distance metric. Despite the simplicity and effectiveness of kmathrmNN regression, a general problem facing this approach is the proper choice of k. Most of the conventional k NN algorithms simply apply the same k for all data samples, meaning that the data samples are assumed to lie on a regular graph wherein each data sample is connected with k neighbors. However, a constant choice may not be optimal for data lying in a heterogeneous feature space. On the other hand, existing algorithms for adaptively choosing k usually incur high computational complexity, especially for large training datasets. In order to cope with this challenge, this paper introduces a novel algorithm which can adaptively choose k for each data sample; meanwhile it is capable of greatly reducing the training complexity by actively choosing training samples. Real data tests corroborate the efficiency and effectiveness of the novel algorithm.

Original languageEnglish (US)
Title of host publication2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages241-245
Number of pages5
ISBN (Electronic)9781728155494
DOIs
StatePublished - Dec 2019
Event8th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2019 - Le Gosier, Guadeloupe
Duration: Dec 15 2019Dec 18 2019

Publication series

Name2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2019 - Proceedings

Conference

Conference8th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2019
CountryGuadeloupe
CityLe Gosier
Period12/15/1912/18/19

Keywords

  • Gaussian processes
  • k-nearest neighbors
  • learning over graphs
  • regression

Fingerprint Dive into the research topics of 'Scalable and Adaptive KNN for Regression over Graphs'. Together they form a unique fingerprint.

Cite this