k-NN graph construction based on markov random walk

Cao, Jiangzhong, Ling, Bingo Wing-Kuen, Woo, Wai Lok and Yang, Zhijing (2015) k-NN graph construction based on markov random walk. In: 2015 IEEE International Conference on Digital Signal Processing (DSP). IEEE, pp. 343-346. ISBN 978-1-4799-8058-1

Full text not available from this repository.

Abstract

k-nearest-neighbors (k-NN) graphs are widely used in image retrieval, machine learning and other research fields. Selecting its neighbors is a core for constructing the k-NN graph. However, existing selection methods usually encounter some unreliable neighbors in the k-NN graph. This paper proposes an efficient Markov random walk (MRW) based method for selecting more reliable neighbors for constructing the k-NN graph. The MRW model is defined on the raw k-NN graph. The k-NN of a sample is determined by the probability of the MRW. Since the high order transition probabilities reflects complex relationships among data, the neighbors in the graph obtained by our proposed method are more reliable than those of existing methods. Also, our proposed method can improve the performances of some applications with k-NN graph. Experiments are performed on the synthetic and real datasets for comparison. The results show that the graph obtained by our proposed method better correspond to the structure of the data compared to those of the state-of-the-art methods.

Item Type:	Book Section
Uncontrolled Keywords:	k-NN graph, Markov random walk, spectral clustering
Subjects:	G900 Others in Mathematical and Computing Sciences
Department:	Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User:	Becky Skoyles
Date Deposited:	11 Apr 2019 08:46
Last Modified:	10 Oct 2019 20:15
URI:	http://nrl.northumbria.ac.uk/id/eprint/38924

Downloads