KNN算法原理（深入浅出）
目录
- 1. KNN算法的背景
- 2. KNN算法的基本步骤
- 步骤1：选择K值
- 步骤2：计算距离
- 步骤3：选择K个最近邻
- 步骤4：进行分类或回归
- 3. KNN算法的公式推导
- 步骤1：计算新样本与每个训练样本之间的距离
- 步骤2：找到距离最小的K个邻居
- 步骤3：进行预测
- 4. 总结
- 5. K值的选择
- **步骤1：导入必要的库**
- **步骤2：加载数据集**
- **步骤3：划分训练集和测试集**
- **步骤4：数据标准化**
- **步骤5：训练KNN模型**
- **步骤6：做出预测并评估模型**
- **步骤7：可视化结果（可选）**
- **完整代码**
- **输出**
- **总结**
1. KNN算法的背景
KNN算法是一种监督学习算法，用于解决分类问题（比如判断某个人是男是女）和回归问题（比如预测某个房子的价格）。
下面通过“距离”来判断样本的类别，认为“相似的样本通常是属于同一类的”。
KNN的基本思路就是：对于一个新的样本，计算它与所有已知样本的距离，找到距离它最近的K个样本，然后根据这K个样本的标签来推测新样本的标签。
2. KNN算法的基本步骤
下面逐步了解KNN算法的核心步骤：
步骤1：选择K值
K是一个正整数，它决定了我们在做预测时要考虑的邻居数量。比如，K=3表示我们会找到距离待预测样本最近的3个样本，看看它们的标签是什么，然后投票选出最终的标签。
步骤2：计算距离
在KNN中，距离是一个非常重要的概念。最常用的距离度量方法是欧氏距离。假设我们有两个样本：
- 样本1的特征是 x 1 = ( x 1 , 1 , x 1 , 2 , . . . , x 1 , n ) x_1 = (x_{1,1}, x_{1,2}, ..., x_{1,n}) x1=(x1,1,x1,2,...,x1,n)
- 样本2的特征是 x 2 = ( x 2 , 1 , x 2 , 2 , . . . , x 2 , n ) x_2 = (x_{2,1}, x_{2,2}, ..., x_{2,n}) x2=(x2,1,x2,2,...,x2,n)
这些特征是样本的不同属性（比如，人的身高、体重等）。计算这两个样本的欧氏距离，可以使用下面的公式：
d
(
x
1
,
x
2
)
=
(
x
1
,
1
−
x
2
,
1
)
2
+
(
x
1
,
2
−
x
2
,
2
)
2
+
⋯
+
(
x
1
,
n
−
x
2
,
n
)
2
d(x_1, x_2) = \sqrt{(x_{1,1} - x_{2,1})^2 + (x_{1,2} - x_{2,2})^2 + \dots + (x_{1,n} - x_{2,n})^2}
d(x1,x2)=(x1,1−x2,1)2+(x1,2−x2,2)2+⋯+(x1,n−x2,n)2
这个公式的意思是，首先对每个特征的差值（即
x
1
,
i
−
x
2
,
i
x_{1,i} - x_{2,i}
x1,i−x2,i）平方，然后把这些平方加起来，再开平方，得到的结果就是两个样本之间的距离。
步骤3：选择K个最近邻
计算完距离后，我们需要找到距离待预测样本最近的K个样本。这些样本就被称为邻居。我们通过这些邻居的标签来预测新样本的标签。
步骤4：进行分类或回归
-
分类：如果我们的任务是分类，比如区分“男”或“女”，我们会选择K个邻居中出现最多的类别作为新样本的预测结果。这个过程叫做“投票”。例如，如果K=3，3个邻居的标签分别是“男”，“男”，“女”，那么新样本的标签预测为“男”。
公式表示为：
y ^ = mode ( y 1 , y 2 , . . . , y K ) \hat{y} = \text{mode}(y_1, y_2, ..., y_K) y^=mode(y1,y2,...,yK)
这里的 y 1 , y 2 , . . . , y K y_1, y_2, ..., y_K y1,y2,...,yK 是K个邻居的标签，mode表示选择出现次数最多的标签。 -
回归：如果任务是预测一个数值（比如预测房价），我们会计算K个邻居标签的平均值作为新样本的预测结果。
公式表示为：
y ^ = 1 K ∑ i = 1 K y i \hat{y} = \frac{1}{K} \sum_{i=1}^{K} y_i y^=K1i=1∑Kyi
这里的 y 1 , y 2 , . . . , y K y_1, y_2, ..., y_K y1,y2,...,yK 是K个邻居的标签（在回归问题中是数值）。
3. KNN算法的公式推导
假设我们有一个训练数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } D = \{(x_1, y_1), (x_2, y_2), ..., (x_m, y_m)\} D={(x1,y1),(x2,y2),...,(xm,ym)}，每个 x i x_i xi 是样本的特征向量， y i y_i yi 是标签。
我们现在有一个新的样本 x new x_{\text{new}} xnew，需要预测它的标签。
步骤1：计算新样本与每个训练样本之间的距离
假设我们选择欧氏距离，计算新样本 x new x_{\text{new}} xnew 与每个训练样本 x i x_i xi 之间的距离：
d ( x new , x i ) = ∑ j = 1 n ( x new , j − x i , j ) 2 d(x_{\text{new}}, x_i) = \sqrt{\sum_{j=1}^{n} (x_{\text{new},j} - x_{i,j})^2} d(xnew,xi)=j=1∑n(xnew,j−xi,j)2
这就是新样本与每个训练样本的距离。
步骤2：找到距离最小的K个邻居
对所有的训练样本计算完距离之后，我们找出距离新样本最近的K个训练样本。假设这K个样本的标签是 y 1 , y 2 , . . . , y K y_1, y_2, ..., y_K y1,y2,...,yK。
步骤3：进行预测
- 分类任务：我们根据K个邻居的标签进行投票，选择最多的标签作为预测结果。假设K=3，邻居的标签是“男”，“男”，“女”，那么最终预测结果是“男”。
y ^ = mode ( y 1 , y 2 , . . . , y K ) \hat{y} = \text{mode}(y_1, y_2, ..., y_K) y^=mode(y1,y2,...,yK)
- 回归任务：我们计算K个邻居的标签的平均值，作为预测结果。
y ^ = 1 K ∑ i = 1 K y i \hat{y} = \frac{1}{K} \sum_{i=1}^{K} y_i y^=K1i=1∑Kyi
4. 总结
KNN算法的核心思想是：如果一个样本与其他样本相似，那么它的标签也应该与这些相似的样本的标签相似。通过计算距离、选择K个邻居，KNN可以非常直观地做出预测。公式推导中，我们首先计算距离，然后选择K个邻居，最后通过投票或均值来预测结果。
5. K值的选择
K的值对模型的效果影响很大。一般来说，K值较小会使模型对噪声较为敏感（可能过拟合），而K值较大则可能使模型过于平滑，导致欠拟合。通常，我们会通过交叉验证来选择一个合适的K值。
我们来通过一个具体的KNN算法应用案例，展示如何用Python实现KNN算法进行分类任务。我们将使用一个常见的机器学习库——scikit-learn，并以鸢尾花数据集（Iris dataset）为例，进行KNN分类。
步骤1：导入必要的库
首先，我们需要导入几个基本的库：
# 导入必要的库
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
numpy和pandas用于数据处理。train_test_split用于将数据集分为训练集和测试集。StandardScaler用于标准化数据，使其适应KNN的距离计算。KNeighborsClassifier是scikit-learn中KNN算法的实现。accuracy_score用于评估分类结果的准确率。load_iris是scikit-learn内置的鸢尾花数据集。
步骤2：加载数据集
我们使用scikit-learn自带的鸢尾花数据集（Iris Dataset）进行KNN分类任务。这个数据集包含150个鸢尾花的样本，每个样本有4个特征（花萼长度、花萼宽度、花瓣长度、花瓣宽度），以及每个样本的类别标签（有三个类别：Setosa, Versicolor, Virginica）。
# 加载鸢尾花数据集
iris = load_iris()
X = iris.data # 特征矩阵
y = iris.target # 类别标签
步骤3：划分训练集和测试集
我们将数据集分为训练集和测试集，通常训练集占数据集的80%，测试集占20%。
# 将数据集分为训练集和测试集（80%训练集，20%测试集）
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
步骤4：数据标准化
KNN算法非常依赖特征之间的距离，因此特征的尺度（单位）必须统一。我们通常会使用标准化来处理特征，使得每个特征的均值为0，标准差为1。
# 标准化数据
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)
步骤5：训练KNN模型
接下来，我们用训练数据训练KNN模型。假设我们选择K=3作为邻居数量，并使用欧氏距离。
# 初始化KNN分类器，设置邻居数量为3
knn = KNeighborsClassifier(n_neighbors=3)
# 使用训练集训练模型
knn.fit(X_train_scaled, y_train)
步骤6：做出预测并评估模型
训练完成后，我们可以使用测试集对模型进行评估。我们使用准确率来衡量模型的表现。
# 使用测试集进行预测
y_pred = knn.predict(X_test_scaled)
# 计算预测准确率
accuracy = accuracy_score(y_test, y_pred)
print(f"模型准确率: {accuracy * 100:.2f}%")
步骤7：可视化结果（可选）
虽然鸢尾花数据集是4维的，但我们可以选择两个特征来可视化KNN的分类效果。我们选择前两个特征（花萼长度和花萼宽度）来进行2D可视化。
# 选择前两个特征进行可视化
X_train_2d = X_train[:, :2]
X_test_2d = X_test[:, :2]
# 标准化数据
X_train_2d_scaled = scaler.fit_transform(X_train_2d)
X_test_2d_scaled = scaler.transform(X_test_2d)
# 训练KNN模型
knn.fit(X_train_2d_scaled, y_train)
# 创建网格来画出决策边界
xx, yy = np.meshgrid(np.linspace(X_train_2d_scaled[:, 0].min(), X_train_2d_scaled[:, 0].max(), 100),
np.linspace(X_train_2d_scaled[:, 1].min(), X_train_2d_scaled[:, 1].max(), 100))
# 预测网格上每个点的类别
Z = knn.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
# 绘制决策边界
plt.contourf(xx, yy, Z, alpha=0.8)
plt.scatter(X_train_2d_scaled[:, 0], X_train_2d_scaled[:, 1], c=y_train, marker='o', edgecolor='k', s=50)
plt.title("KNN Classification (Training Set)")
plt.xlabel("Feature 1: Sepal Length")
plt.ylabel("Feature 2: Sepal Width")
plt.show()
完整代码
将上述步骤整合，代码如下：
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
# 加载鸢尾花数据集
iris = load_iris()
X = iris.data
y = iris.target
# 将数据集分为训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
# 标准化数据
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)
# 训练KNN模型
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train_scaled, y_train)
# 使用测试集进行预测
y_pred = knn.predict(X_test_scaled)
# 计算准确率
accuracy = accuracy_score(y_test, y_pred)
print(f"模型准确率: {accuracy * 100:.2f}%")
# 可视化结果 (选择前两个特征进行2D可视化)
X_train_2d = X_train[:, :2]
X_test_2d = X_test[:, :2]
X_train_2d_scaled = scaler.fit_transform(X_train_2d)
X_test_2d_scaled = scaler.transform(X_test_2d)
knn.fit(X_train_2d_scaled, y_train)
# 创建网格画出决策边界
xx, yy = np.meshgrid(np.linspace(X_train_2d_scaled[:, 0].min(), X_train_2d_scaled[:, 0].max(), 100),
np.linspace(X_train_2d_scaled[:, 1].min(), X_train_2d_scaled[:, 1].max(), 100))
Z = knn.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
# 绘制决策边界
plt.contourf(xx, yy, Z, alpha=0.8)
plt.scatter(X_train_2d_scaled[:, 0], X_train_2d_scaled[:, 1], c=y_train, marker='o', edgecolor='k', s=50)
plt.title("KNN Classification (Training Set)")
plt.xlabel("Feature 1: Sepal Length")
plt.ylabel("Feature 2: Sepal Width")
plt.show()
输出
- 模型准确率：程序会输出模型在测试集上的准确率，比如：“模型准确率: 96.67%”。
- 可视化：会绘制一个2D决策边界图，显示KNN算法如何根据两个特征（花萼长度和花萼宽度）进行分类。
总结
通过这个Python应用案例，我们演示了如何使用KNN算法进行鸢尾花数据集的分类。整个过程包括了数据加载、数据划分、标准化、训练模型、预测结果和可视化等步骤。KNN是一种非常直观的算法，适合初学者使用。