k近邻算法（k-Nearest Neighbors，kNN）

奋斗吧

擅长邻域：未填写

标签： k近邻算法（k-Nearest Neighbors，kNN） JavaScript博客 51CTO博客

2023-07-04 18:24:30 324浏览

k近邻算法（k-Nearest Neighbors，kNN），k近邻算法（k-NearestNeighbors，kNN）前置知识：无。kNN算法步骤：收集整理好的数据，测试用的比断为...

k近邻算法（k-Nearest Neighbors，kNN）_k近邻

算法原理与思想

前置知识：无。

算法原理

kNN算法步骤：

收集数据。

如，香蕉和苹果的数据。我们可以将苹果和香蕉按俩个维度划分，长度和宽度（也可以按照别的维度，也可以是 n 维不一定是 2 维）。

k近邻算法（k-Nearest Neighbors，kNN）_数据_02

假设红色的点是苹果，绿色的点是香蕉；横坐标是长度，纵坐标是宽度。

现在新来了一个点（黑色的），机器会把这个点判断为苹果，还是判断为香蕉呢？

取一个 k 值。

我们先取一个 k 值，简单起见，k = 3 吧。

参数k的取值。这需要根据问题和数据的特点来确定。

在实现时可以考虑样本的权重，即每个样本有不同的投票权重，这称方法称为为带权重的k近邻算法。

另外还其他改进措施，如模糊k近邻算法¹。

根据 k 值，k近邻算法的过程即：在所有这些点（红色+蓝色）中，寻找离这个新点（黑色）最近的 k 个点。

我们要做的计算距离，并排序。

我们取了 k = 3，那就寻找离黑点最近的 3 个点即可。

计算距离，一般用欧拉距离。

二维空间中的欧拉距离是：

k近邻算法（k-Nearest Neighbors，kNN）_ci_03

三维空间中的欧拉距离是：

k近邻算法（k-Nearest Neighbors，kNN）_ci_04

n维空间中的欧拉距离是：

k近邻算法（k-Nearest Neighbors，kNN）_k近邻_05

让最近的 k 个点根据自己的属性来投票

比如，离黑点最近的 3 个点。其中俩个是苹果，一个是香蕉，那这个新点就是苹果。

根据算法步骤，k近邻算法实现挺简单的，但是当训练样本数大、特征向量维数很高时计算复杂度高。

因为每次预测时要计算待预测样本和每一个训练样本的距离，而且要对距离进行排序找到最近的k个样本。

我们可以使用高效的部分排序算法，只找出最小的k个数；另外一种加速手段是k-d树实现快速的近邻样本查找。

手工实现

代码实现：收集数据：

#每一个样本的特征，用向量表示
raw_data_X = [
			# [  横坐标，      纵纵标    ],
			  [3.393533211, 2.331273381],
              [3.110073483, 1.781539638],
              [1.343808831, 3.368360954],
              [3.582294042, 4.679179110],
              [2.280362439, 2.866990263],
              [7.423436942, 4.696522875],
              [5.745051997, 3.533989803],
              [9.172168622, 2.511101045],
              [7.792783481, 3.424088941],
              [7.939820817, 0.791637231]]
             
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
# 所属类别，0代表苹果，1代表香蕉

# numpy里面的数据类型适合计算，所以换成 numpy
X_train = np.array(raw_data_X)
y_train = np.array(raw_data_y)

x = np.array([8.093607318, 3.365731514])
# 新点的数据

kNN 算法实现：

import numpy as np
from math import sqrt
from collections import Counter

def kNN(k, X_train, y_train, x):
# X_train：训练数据    y_train：所属类别    x：新的待测试数据

    distances = [sqrt(np.sum((x_train - x)**2)) for x_train in X_train]
    # 列表生成式 计算二维欧拉距离
    
    nearest = np.argsort(distances)
    # argsort方法对一个列表排序，并返回列表的下标(我们要的不是距离，而是最近的点)

    topK_y = [y_train[i] for i in nearest[:k]]
    # 列表生成式 获取前 k 个元素的值(根据自己的属性来投票，就得知道自己的点是 0 还是 1)
    
    votes = Counter(topK_y)
    # Counter函数统计不同类别的点有多少个

    return votes.most_common(1)[0][0]
    # 返回最多的一个点

$k近邻算法（k-Nearest Neighbors，kNN）_数据_06$ 调包实现

一般我们不用自己手动实现，而是调用 $k近邻算法（k-Nearest Neighbors，kNN）_数据_06$

在 $k近邻算法（k-Nearest Neighbors，kNN）_数据_06$

【训练数据集】：将数据 “喂” 给机器学习算法
【拟合（fit）】：而后算法会训练出一个模型
【输入样例】：此时输入一个样例，送给模型
【预测（predict）】：模型就可以预测出结果

k近邻算法（k-Nearest Neighbors，kNN）_k近邻_09

但我们实现 kNN 算法时，并没有发现有啥模型呀。

kNN 的输入样例并不是训练出来的，而是之间在数据集之间选出来的，没有训练过程（模型）。

但为了统一标准， $k近邻算法（k-Nearest Neighbors，kNN）_数据_06$

from sklearn.neighbors import KNeighborsClassifier
# 调用 kNN 算法，需要导入 KNeighborsClassifier 类

kNN_classifier = KNeighborsClassifier(n_neighbors = 3) 
# 创建一个类的实例，参数n_neighbors是 k值

kNN_classifier.fit(X_train, y_train) 
# 数据集拟合fit

X_predict = x.reshape(1, -1)
# 创建一个矩阵，因为 scikit-learn 为了统一，预测 predict 参数，只能是矩阵

y_predict = kNN_classifier.predict(X_predict)
# 预测predict

print(y_predict[0])
# 因为我们的返回值只有一个，所以就是第一个元素

kNN总结

kNN是一个解决分类问题的算法，而是是多分类问题，不止是二分类问题（俩个选择）。

思想简单，效果强大。

除此之外，也可以解决回归问题，如预测房价、学生成绩等。

不过，kNN算法的效率比较低， $k近邻算法（k-Nearest Neighbors，kNN）_数据_11$ ，如果训练集有 $k近邻算法（k-Nearest Neighbors，kNN）_k近邻_12$ 个， $k近邻算法（k-Nearest Neighbors，kNN）_ci_13$ 个特征，则预测每一个新数据的复杂度是， $k近邻算法（k-Nearest Neighbors，kNN）_数据_11$ 。