Python 手写实现最简单的 kNN 算法

本文约3000字，预计阅读时间10分钟，建议收藏

摘要

从零开始学习机器学习中最简单的 kNN 算法。

今天，我打算撰写一系列关于机器学习的文章。相比爬虫，掌握机器学习更具竞争力且实用性更强。然而，目前网络上的许多教程对新手并不友好，要么直接调用 Sklearn 包，要么充斥着大量抽象的算法公式，导致新手难以入门。真正适合新手的 Python 手写代码教程非常稀缺。最近，我在慕课网上观看了 Bobo 教师的机器学习课程，深受启发。我计划以此为基础，结合自己的理解，从零开始撰写一系列机器学习教程。

第一篇文章不会涉及机器学习的基础概念，因为只有在真正了解这些概念后，才能更好地理解后续的内容。因此，我将直接从一个具体的算法实例入手，就像之前的爬虫教程一样，通过实践来激发读者的兴趣。

实战场景

在一个酒吧里，吧台上摆放着十杯几乎相同的红酒。老板提议玩个游戏：赢了可以免费喝酒，输了则需支付三倍酒钱，胜算有50%。你是个喜欢冒险的人，毫不犹豫地接受了挑战。

老板告诉你，这十杯红酒分为两类：前五杯是“赤霞珠”，后五杯是“黑皮诺”。现在，你需要根据已知的十杯酒来判断新倒的一杯酒属于哪一类。

尽管你对红酒并不熟悉，但凭借对机器学习的理解，你充满信心地接受了挑战。你询问了每杯酒的酒精浓度和颜色深度，并记录下来。很快，你判断出新倒的那杯酒应该是“赤霞珠”。

老板惊讶不已，因为你仅凭这些数据就做出了正确的判断。你自豪地解释说，这一切都归功于机器学习。

kNN 算法介绍

接下来，我们将从这个故事入手，探讨机器学习中的一个最简单算法：kNN 算法（K-Nearest Neighbor）。许多人认为机器学习很难，但我保证，只要具备高中数学基础和一点 Python 编程经验，你就能掌握这个算法。

学会 kNN 算法只需三步： 1. 理解 kNN 算法的思想 2. 掌握其背后的数学原理 3. 用简单的 Python 代码实现

在介绍 kNN 算法之前，我们需要了解两个概念：样本和特征。每一杯酒称为一个“样本”，十杯酒组成的集合称为“样本集”。酒精浓度和颜色深度等信息称为“特征”。这些样本分布在多维特征空间中。为了简化理解，我们假设只需要考虑酒精浓度和颜色深度这两个特征。

kNN 算法的应用

假设你要判断新倒的一杯酒属于哪一类。根据 kNN 算法，你需要选取一个参数 K（经验值通常取3），然后找到离新样本最近的 K 个样本，统计这些样本所属的类别，得票数最多的类别即为新样本的类别。

例如，新倒的一杯酒距离最近的三个点都是绿色的“赤霞珠”点，那么这杯酒就属于“赤霞珠”。如果最近的三个点有两个是红色的“黑皮诺”点，一个是绿色的“赤霞珠”点，那么这杯酒就属于“黑皮诺”。

数学原理

kNN 算法的核心在于计算样本间的距离。在二维坐标系中，两点间的距离可以用欧拉公式计算：

[ text{距离} = sqrt{(x2 - x1)^2 + (y2 - y1)^2} ]

在更高维度的空间中，这个公式同样适用。例如，在三维空间中，公式变为：

[ text{距离} = sqrt{(x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2} ]

在多维空间中，公式可以简化为：

[ text{距离} = sqrt{sum{i=1}^{n} (x{2i} - x_{1i})^2} ]

Python 代码实现

首先，我们需要生成一些样本数据。这里我们使用 Sklearn 中的葡萄酒数据集的一部分。

```python import numpy as np

样本数据

X_raw = [ [14.23, 5.64], [13.2, 4.38], [13.16, 5.68], [14.37, 4.80], [13.24, 4.32], [12.07, 2.76], [12.43, 3.94], [11.79, 3.00], [12.37, 2.12], [12.04, 2.60] ]

y_raw = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

新样本数据

x_test = np.array([12.8, 4.1])

转换为 numpy 数组

Xtrain = np.array(Xraw) ytrain = np.array(yraw)

绘制散点图

import matplotlib.pyplot as plt plt.style.use('ggplot') plt.figure(figsize=(10, 6))

绘制样本点

plt.scatter(Xtrain[ytrain == 1, 0], Xtrain[ytrain == 1, 1], s=100, color='green', label='赤霞珠') plt.scatter(Xtrain[ytrain == 0, 0], Xtrain[ytrain == 0, 1], s=100, color='red', label='黑皮诺') plt.scatter(xtest[0], xtest[1], s=100, color='yellow') # 新样本点

plt.xlabel('酒精浓度') plt.ylabel('颜色深度') plt.legend(loc='lower right') plt.tight_layout() plt.savefig('葡萄酒样本.png') ```

接下来，根据欧拉公式计算新样本点到每个样本点的距离：

```python from math import sqrt

计算距离

distances = [sqrt(np.sum((x - xtest) ** 2)) for x in Xtrain]

输出距离

print(distances) ```

计算出距离后，找到最近的三个点：

```python

找到最近的三个点

sort = np.argsort(distances)

获取最近的三个点的类别

K = 3 topK = [y_train[i] for i in sort[:K]] print(topK)

统计类别

from collections import Counter votes = Counter(topK) predicty = votes.mostcommon(1)[0][0] print(predict_y) ```

以上代码实现了 kNN 算法的基本步骤。如果你觉得手写代码有些复杂，也可以调用 sklearn 库中的 kNN 算法：

```python from sklearn.neighbors import KNeighborsClassifier

创建模型

kNNclassifier = KNeighborsClassifier(nneighbors=3)

训练模型

kNNclassifier.fit(Xtrain, y_train)

预测新样本

xtest = xtest.reshape(1, -1) prediction = kNNclassifier.predict(xtest)[0] print(prediction) ```

通过以上步骤，我们不仅学会了如何实现 kNN 算法，还了解了其背后的数学原理和 Python 实现方法。希望这些内容能帮助你更好地入门机器学习。