Python k-近邻算法的实现原理

1.KNN算法流程步骤

(1)收集数据：可以使用任何方法。包括爬虫，或者第三方提供的免费或收费数据

(2)准备数据：距离计算所需要的数值，最好是结构化的数据格式(计算测试数据与各个训练数据之间的距离)

(3)分析数据：可以使用任何方法。此处使用Python解析，预处理数据

(4)训练算法：此步骤不适用于k-近邻算法

(5)测试算法：计算错误率

(6)使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判断输入数据分别属于哪个类别，最后应用对计算出的分类执行后续的处理

比如我这里取k值为3，那么在电影例子中，按照距离依次排序的三个点分别是动作片(108,5)、动作片(115,8)、爱情片(5,89)。在这三个点中，动作片出现的频率为三分之二，爱情片出现的频率为三分之一，所以该红色圆点标记的电影为动作片。这个判别过程就是k-近邻算法

2.KNN算法——蛮力实现原理

既然我们要找到K个最近的邻居来做预测，那么我们只需要计算预测样本和所有训练集中的样本的距离，然后计算出最小的k个距离即可，接着多数表决，很容易做出预测。这个方法的确简单直接，在样本量少，样本特征少的时候有效。但是在实际运用中很多时候用不上，为什么呢?因为我们经常碰到样本的特征数有上千以上，样本量有几十万以上，如果我们这要去预测少量的测试集样本，算法的时间效率很成问题。因此，这个方法我们一般称为蛮力实现。比较适合于少量样本的简单模型的时候用。

既然蛮力实现的特征多，样本多的时候很有局限性，那么我们有没有其他的好办法呢?有!下面说两种，一个是KD树实现，一个是球树实现。

3.KNN算法——KD树实现原理

KD树算法没有一开始就尝试对测试样本分类，而是先对训练集建模，建立的模型就是KD树，建好了模型再对测试集做预测。所谓的KD树就是K个特征维度的树，注意这里的K和KNN中的K意思不同。KNN中的K代表最近的K个样本，KD树中的K代表样本特征的维数。为了防止混淆，后面我们称特征维数为n。

KD树算法包括三步，第一步是建树，第二步是搜索最近邻，最后一步是预测。

KD树的建立

我们首先来看建树的方法。KD树建树采用的是从m个样本的n维特征中，分别计算n个特征的取值的方法，用方差最大的第k维特征nk来作为根节点。对于这个特征，我们选择特征nk的取值的中位数nkv对应的样本作为划分点，对于所有第k维特征的取值小于nkv的样本，我们划入左子树，对于第k维特征的取值大于等于nkv的样本，我们划入右子树，对于左子树和右子树，我们采用和刚才同样的方法来找方差最大的特征来做根节点，递归的生成KD树。

以上内容为大家介绍了Pythonk-近邻算法的实现原理，希望对大家有所帮助，如果想要了解更多Python相关知识，请关注IT培训机构:开发教育。

鹏仔微信 15129739599 鹏仔QQ344225443 鹏仔前端 pjxi.com 共享博客 sharedbk.com