首页 / 知识
Python k-近邻算法的实现原理
2023-11-12 13:31:00
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相关知识，请关注我们
最新内容
相关内容
Python网络编程调用接收数据的三种
Python网络编程调用接收数据的三种方法，数据，代码，基础，通用，通讯，服务，网络，培训，方法，报文，最近在使用python进行网络编程开发一个通用的tc
Python变量数据类型的转换
Python变量数据类型的转换，代码，数据，培训，信息，字符串，类型，变量，整数，浮点，函数，虽然Python是弱类型编程语言，不需要像Java或C语言那样还要
Python元类之通过元类实现数据库OR
Python元类之通过元类实现数据库ORM框架，数据，名称，信息，代码，主体，当中，字段，分析，一致，投入，ORM框架是什么如果是没有做过后端的小伙伴上来
Python性能分析
Python性能分析，代码，分析，对比，时间，工具，标准，注释，跨行，通用，报告，python标准库提供两个代码性能分析相关的模块，即timeit和cProfile/profi
Python算法定义
Python算法定义，有限，时间，数据，算法，情况，培训，系统，策略，复杂度，步骤，算法(Algorithm)是指解题方案的准确而完整的描述，是一系列解决问题的
基于 Python K-近邻算法的手写识别
基于 Python K-近邻算法的手写识别系统，数据，数字，分析，培训，系统，算法，近邻，测试，样本，图形，这里我们一步步的构造使用k-近邻分类器的手写识
Python k-近邻算法常见问题
Python k-近邻算法常见问题，加权，技术，系统，培训，样本，近邻，距离，变量，算法，权重，1，K值设定为多大?K太小，分类结果易受噪声点影响;K太大，近邻中
python如何导入txt数据库?
python如何导入txt数据库?，数据，时间，代码，培训，数据库，函数，读数，数据表，以上，方法，python将TXT数据导入数据库的方法代码如下：#!/usr/bin/py
python获取当前时间日期有哪些方法
python获取当前时间日期有哪些方法?，时间，标准，星期六，培训，日期，微秒，结果，模块，星期，格式，获取到时间也是我们在学习python遇到的常见问题，
python怎样获取json数据类型?
python怎样获取json数据类型?，培训，数据类型，类型，正则，火狐，以上，方法，更多，内容，列表，python中获取json不同数据类型的方法：1、获取"key"：v
python数据怎么添加列?
python数据怎么添加列?，数据，位置，培训，方法，属性，结果，示例，函数，前面，以上，python在DataFrame数据中添加列的方法：1、使用concat方法在数据
python如何获取列表里的数据类型?
python如何获取列表里的数据类型?，代码，信息，培训，类型，数据类型，表里，元素，语句，函数，对象，1、Python可以通过tpye()方法来判断list里的元知