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

摘要： K-近邻（K-Nearest-Neighbor，KNN）算法是一种最基本的基于实例的学习方法，被广泛应用于机器学习与数据挖掘。其学习过程只是简单地存储已知的训练数据。当遇到新的查询实例时，一系列相似的实例被从存储器中取出，并用来分类新的查询实例。KNN的一个不足是分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时，而不是在第一次遇到训练实例时。所以，如何有效地索引训练实例，以减少查询时所需计算是一个重要的实践问题。为解决这个问题，提出了一种新的算法。该算法把部分原本发生在分类阶段的计算移到训练阶段来完成。实验表明，算法能够提高KNN效率80%以上。此外，算法的思想还可以应用于KNN的所有变体中。

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