Java教程

K近邻(KNN)算法是基于实例的算法,如果训练样本数量庞大,预测的时候挨个计算距离效率会很低下,如何破解?

本文主要是介绍K近邻(KNN)算法是基于实例的算法,如果训练样本数量庞大,预测的时候挨个计算距离效率会很低下,如何破解?,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

K近邻(KNN)算法是基于实例的算法,如果训练样本数量庞大,预测的时候挨个计算距离效率会很低下,如何破解?

K近邻(KNN)是最简单的算法之一,它计算预测样本与训练数据集中每个数据点之间的距离,并找到K个最近的样本数据。

当我们使用最近邻搜索算法时,它将所有的数据点与上述的查询点进行比较,找到最近的K个点。

有很多方法可以求出两个数据点之间的距离。最常用的距离度量是“欧氏距离”和“汉明距离”。

设想这样一种情况:你的任务有数千万个训练样本,每次算法都会将预测数据与所有训练数据进行比对。它不是计算量很大吗?

此外,数据点越大,所需的计算量也就越大。很明显!

KNN搜索计算每个距离的时间复杂度为O(N)。对于有K个邻居搜索的KNN,只有当我们保持一个优先队列返回最近的K个观测值时,时间复杂度才为O(log(K)*N)。因此,对于大数据或者互联网场景下的数据集,KNN似乎对计算得要求要求很高。那么,有没有其他方法可以替代KNN模型的最近距离计算的算法,它使用类似的方法,但也可以是有效的时间?

令人开心的是,KD树和Ball树就是用来解决这个问题的。

这篇关于K近邻(KNN)算法是基于实例的算法,如果训练样本数量庞大,预测的时候挨个计算距离效率会很低下,如何破解?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!