Computer Science ›› 2017, Vol. 44 ›› Issue (12): 194-201.doi: 10.11896/j.issn.1002-137X.2017.12.036

Previous Articles     Next Articles

Adaptive Nearest Neighbor Algorithm with Dynamic Neighborhood

FENG Ji, ZHANG Cheng and ZHU Qing-sheng   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Traditional nearest neighbor algorithm includes k-nearest neighbor (KNN) and reverse nearest neighbor (RNN),and they have been proposed in the literature,but most of them are vulnerable to their parameter choice.In this paper,a novel algorithm of nearest neighbor was proposed,named natural neighbor (NaN).In contrast to KNN and RNN,it is a scale-free nearest neighbor,and it can be used in any dataset effectually,especially data on manifold.This article discussed the theoretical model and its detailed implementation algorithm of natural neighbor in a different field,and the related questions of NaN concepts were discussed by the experimental tests.

Key words: Nearest neighbor,Natural neighbor algorithm,Dynamic neighborhood

[1] AMBERT K H,COHEN A M.k-Information gain scaled nearest neighbors:a novel approach to classifying protein-protein interaction-related documents[J].IEEE/ACM Transactions on Computational Biology & Bioinformatics,2012,9(1):305-310.
[2] BRIAN M,CAROLINA G,GERT L.Contextual Object Localization With Multiple Kernel Nearest Neighbor [J].IEEE Transactions on Image Processing,2011,20(2):570-585.
[3] SALVADOR G,JOAQUIN D,JOSE R C.Prototype Selection for Nearest Neighbor Classification:Taxonomy and Empirical Study [J].IEEE Trans.on Pattern Analysis and Machine Intelligence,2012,34(3):417-435.
[4] STEVENS S S.Mathematics,Measurement,and Psychophysics[M]∥Handbook of Experimental Psychology.1951:1-49.
[5] KORN F,MUTHUKRISHNAN S.Influence Sets Based on Reverse Nearest Neighbor Queries [J].ACM SIGMOD Recond,2000,9(2):201-212.
[6] WANG J,NESKOVIC P,COOPER L.Improving NearestNeighbor rule with a simple adaptive distance measure [J].Pattern Recognition Letter,2007,8(2):207-213.
[7] SALVADOR G,JOAQUIN D,JOSE R C.Prototype Selection for Nearest Neighbor Classification:Taxonomy and Empirical Study [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(3):417-435.
[8] GHOSH A K.On Optimum Choice of k in Nearest Neighbor classification [J].Computational Statistics & Data Analysis,2006,50(11):3113-3123.
[9] HASTIE T,TIBSHIRANI R.Discriminant Adaptive Nearest neighbor Classification [J].IEEE Transactions Pattern Analysis and Machine Intelligence,1996,18(6):607-616.
[10] GHOSH A K,ANIL K.On Nearest Neighbor Classification sing Adaptive Choice of k [J].Computational & Graphical Statistics,2007,6(2):482-502.
[11] DOMENICONI C,PENG J,GUNOPULOS D.Locally Adaptive metric Nearest-Neighbor Classification [J].IEEE Transactions Pattern Analysis and Machine Intelligence,2002,4(9):1281-1285.
[12] BHATTACHARYA G,GHOSH K,CHOWDHURY A S.An affinity-based new local distance function and similarity measure for kNN algorithm [J].Pattern Recognition Letters,2012,33(3):356-363.
[13] YIU M L,MAMOULIS N.Reverse Nearest Neighbors Search in Ad Hoc Subspaces [J].IEEE Trans.on Knowledge and Data Engineering,2007,9(3):412-426.
[14] WANG S S,CHAI S,LV Q N.A Pruning Based Continuous RkNN Query Algorithm for Large k [J].Chinese Journal of Electronics,2012,21(3):523-552.
[15] ZHANG Y.Study on Classification algorithm based on natural nearest neighbor [D].Chongqing:Chongqing University,2015.(in Chinese) 张莹.基于自然最近邻居的分类算法研究[D].重庆:重庆大学,2015.
[16] HUANG J L.Study on non-parametric clustering based on natural nearest neighborhood [D].Chongqing:Chongqing University,2014.(in Chinese) 黄金龙.基于自然最近邻的无参聚类算法研究[D].重庆:重庆大学,2014.
[17] TANG H.An outlier detection algorithm based on natural nearest neighbor [D].Chongqing:Chongqing University,2014.(in Chinese) 唐汇.基于自然最近邻居的离群检测算法研究[D].重庆:重庆大学,2014.
[18] NKAYA T,KAYALIGIL S,ZDEMIREL N E.An adaptive neighbourhood construction algorithm based on density and connectivity [J].Pattern Recognition Letters,2015,2:17-24.

No related articles found!
Full text



No Suggested Reading articles found!