一种提高K-近邻算法效率的新算法

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