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

发布时间:2022-04-29 09:41:16 人气:67 作者:多测师

  1. KNN 算法流程步骤

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

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

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

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

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

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

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

Python 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树。

  以上内容为大家介绍了Python k-近邻算法的实现原理,希望对大家有所帮助,如果想要了解更多Python相关知识,请关注多测师。https://www.e70w.com/xwzx/


返回列表
在线客服
联系方式

热线电话

17727591462

上班时间

周一到周五

二维码
线