关键词: K-近邻算法, 基于实例的学习, 效率, 分类

Abstract: 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.

Key words: K-Nearest-Neighbor, instance-based learning, efficiency, classification