摘要：k近邻（k nearest neighbor,kNN）分类作为数据挖掘中最典型的算法之一,以较高的泛化性能以及充足的理论基础被广泛应用。然而kNN在测试时需要计算待识别实例与所有训练实例之间的距离,以至于在面对大规模数据时需要大量的时间。为此,提出一种基于分层抽样的kNN加速算法（KNN based on stratified sampling,SS-kNN）。首先将训练实例所在的空间划分为若干个实例个数相等的区域,然后从每个区域内抽取实例,最后判定待识别实例落入划分区域中的哪一个,并从此区域以及相邻区域抽取的实例中寻找其k个近邻。与原始kNN算法以及基于随机抽样的kNN算法相比,SSkNN算法可以获得与其相近分类精度,但将其运行速度分别提高大约399倍和16倍。

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社