齐 晴，沈正飞，曹 健，应 俊，赵 龙

1.上海交通大学计算机科学与工程系，上海2002402.上海海勃物流软件有限公司，上海200080

近年来，随着数据的积累，如何利用机器学习算法从大量的数据中学习知识已经成为一个人们普遍关心的问题.对于一个机器学习算法，除了需要有较好的预测性能和良好的泛化能力外，还应该具备如下几个特点：1）快速训练；2）快速预测；3）可以应对大规模在线数据以及流数据.想要设计一个算法同时满足上述条件是比较困难的，而在诸如计算机视觉、推荐系统、广告预测等领域，巨大的数据量对机器学习算法的计算效率优化提出了更大的挑战.

K-近邻算法（K-nearest neighbor,KNN）是一种非监督式算法，它针对待分类样本寻找最相似的k个样本，利用它们的标签判定待分类样本的类别.作为一种经典的机器学习算法，KNN 因效果较好而得到了普遍的应用.研究者们也不断深化KNN 算法的模型，例如文献[1]提出了利用D-S 证据理论对近邻的标签进行聚合形成最后的分类结果的方法.

在KNN 算法中，需要为待分类样本与每个历史样本计算距离并进行比较，从而能够找到最相近的k个历史样本.随着历史案例库的不断扩大，KNN 算法的运行效率将急剧下降.特别是在面向多用户进行实时决策的系统中，具有较大的日活跃用户数量（daily active user，DAU）与每秒查询率（queries-per-second，QpS），对系统的吞吐量和算法的效率都有较高的要求，此时KNN 的效率可能会成为系统的制约因素.文献[2]提出的边界树与边界森……