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

摘要

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