New algorithm to scale up efficiency of K-Nearest-Neighbor
Liu Jing · Computer Engineering and Applications Journal · 2008
The k-Nearest-Neighbor(KNN) algorithm is the most basic instance-based learning method,and is widely used in machine learning and data mining.Learning in KNN consists of simply storing the presented training data.When a new query instance is encountered,a set of similar related instances is retrieved from memory and used to classify the new query instance.One disadvantage of KNN is that the cost of classifying new instances can be high.This is due to the fact that nearly all computation takes place at classification time rather than when the training instances are first encountered.So,how to efficiently index training instances are a significant practical issue in reducing the computation required at query time.In order to set down this issue,this paper presents a new algorithm.It moves some computations taken place at classification time to the training time.The simulation experiments show that it can scale up the efficiency of KNN beyond 80%.Besides,its idea can be applied to all variants of KNN.