机器学习之KNN算法

K-Nearest Neighbors (KNN) 是一种常见的机器学习算法，广泛应用于分类和回归问题。KNN是一种基于实例的学习方法，它利用训练数据集的实例来进行分类或回归预测。在KNN中，预测的结果依赖于距离度量函数计算出的最近邻实例的标签或值。下面我们将详细探讨KNN的工作原理，并通过代码和示例进一步说明其应用。

KNN算法的原理

KNN的工作流程

1. 选择K值：选择一个适当的 K 值，即选择最近邻的数量。K的值过小可能会导致过拟合，过大可能会导致欠拟合。
2. 计算距离：选择适当的距离度量方法，最常用的是 欧氏距离。
3. 预测：
   • 分类任务：通过投票选出 K 个邻居中出现最多的类别作为预测结果。
   • 回归任务：计算 K 个邻居的均值作为预测结果。

KNN的优势与劣势

优势

• 简单易懂：KNN是一种直观且简单的算法，容易实现。
• 不需要训练阶段：KNN没有显式的训练过程，直接将数据存储并用于预测。
• 能够处理多类别分类问题：KNN算法可以同时处理多个类别的数据。
• 自适应性强：由于KNN是基于实例的，不需要构建复杂的模型，可以灵活地适应不同类型的学习任务。

劣势

• 计算开销大：KNN算法在测试阶段需要计算每个测试样本与所有训练样本的距离，因此计算量较大，尤其在数据集较大的情况下。
• 内存开销大：由于KNN需要存储所有训练数据，内存消耗较高。
• 对异常值敏感：KNN对数据中的异常值较为敏感，异常值可能会严重影响模型的性能。
• 高维数据问题：KNN在高维空间中表现较差，这被称为“维度灾难”（Curse of Dimensionality）。随着维度的增加，样本之间的距离趋于相等，使得KNN的效果下降。

如何选择K值

选择K值的大小对于模型的表现至关重要。一般来说，较小的K值可能导致模型对训练数据中的噪声过于敏感，而较大的K值则可能导致模型的预测结果过于平滑，忽略了局部数据的特征。通常，可以通过交叉验证来选择最优的K值。

距离度量方法

在KNN中，选择合适的距离度量非常重要。以下是几种常见的距离度量方法：

1. 欧氏距离（Euclidean Distance）： 欧氏距离是最常见的距离度量方法，适用于连续变量。

   其中，x和 y 是两个向量，xi 和 yi是它们的第 i 个维度。

2. 曼哈顿距离（Manhattan Distance）： 曼哈顿距离计算的是两个点在所有维度上差值的绝对值之和。

3. 切比雪夫距离（Chebyshev Distance）： 切比雪夫距离计算的是两个点在各维度上差值的最大值。

KNN算法的代码实现

下面是一个简单的KNN算法实现，使用了 欧氏距离 作为度量标准。

示例：使用Python实现KNN算法

import numpy as np
from collections import Counter

# 计算欧氏距离
def euclidean_distance(x1, x2):
    return np.sqrt(np.sum((x1 - x2)**2))

# KNN算法实现
class KNN:
    def __init__(self, k=3):
        self.k = k  # 设置 K 值
    
    def fit(self, X_train, y_train):
        self.X_train = X_train
        self.y_train = y_train
    
    def predict(self, X_test):
        predictions = [self._predict(x) for x in X_test]
        return np.array(predictions)
    
    def _predict(self, x):
        # 计算测试点与训练数据的距离
        distances = [euclidean_distance(x, x_train) for x_train in self.X_train]
        # 按照距离排序并选择最近的K个点
        k_indices = np.argsort(distances)[:self.k]
        k_nearest_labels = [self.y_train[i] for i in k_indices]
        # 返回出现次数最多的标签
        most_common = Counter(k_nearest_labels).most_common(1)
        return most_common[0][0]

# 示例数据
X_train = np.array([[1, 2], [2, 3], [3, 4], [6, 7], [7, 8], [8, 9]])  # 训练数据
y_train = np.array([0, 0, 0, 1, 1, 1])  # 标签

X_test = np.array([[2, 2], [7, 7]])  # 测试数据

# 创建并训练KNN模型
knn = KNN(k=3)
knn.fit(X_train, y_train)

# 预测
predictions = knn.predict(X_test)
print(f"Predictions: {predictions}")

代码解释：

1. 欧氏距离计算：euclidean_distance() 计算两个点之间的欧氏距离。
2. KNN类：
   • fit()：用于存储训练数据。
   • predict()：对每个测试样本进行预测。
   • _predict()：对单个样本，根据最近的 K 个邻居进行预测。
3. 示例数据：X_train 和 y_train 分别是训练数据和标签，X_test 是需要预测的测试数据。

运行结果：

Predictions: [0 1]

KNN算法的应用场景

• 分类问题：KNN在文本分类、图像分类、医疗诊断等领域有广泛应用。例如，根据用户的历史行为预测用户是否会点击广告，或者根据病人的症状预测是否患有某种疾病。

• 回归问题：KNN也可用于回归问题，如房价预测、股票市场预测等。通过选择 K 个最相似的样本，计算这些样本的目标值的平均值来做出预测。

KNN的优缺点

优点：

1. 简单易理解：KNN算法非常简单，易于理解和实现。
2. 无需训练：KNN是懒惰学习算法，不需要显式的训练过程。
3. 适应性强：KNN可以轻松地适应多类别和度的数据。

缺点：

1. 计算复杂度高：在测试阶段，KNN需要计算每个测试样本与所有训练样本的距离，计算量较大，尤其是在大规模数据集上。
2. 内存消耗大：KNN算法需要存储所有的训练数据，内存消耗较大。
3. 对噪声敏感：KNN对于数据中的噪声较为敏感，特别是在高维数据中。
4. 不适合高维数据：在高维空间中，距离度量变得不再有效，KNN的效果显著下降。

创建自己的 KNN 可视化图

你可以使用 matplotlib 和 sklearn 来生成一个简单的 KNN 可视化图。下面是一个 Python 代码示例：

import numpy as np
from sklearn.datasets import make_classification
from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt

# 生成数据集
X, y = make_classification(n_samples=100, n_features=5, n_informative=2, random_state=42)

# 创建 KNN 分类器并进行训练
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X, y)

# 创建一个用于预测的网格（要确保特征数与训练时一致）
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1), np.arange(y_min, y_max, 0.1))

# 现在我们需要确保输入的数据有 5 个特征
# 创建一个数据集，注意这里我们需要保持与训练集相同的特征数量
grid_points = np.c_[xx.ravel(), yy.ravel(), np.zeros((xx.ravel().shape[0], 3))]

# 使用 KNN 模型进行预测
Z = knn.predict(grid_points)

# 绘制决策边界
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, alpha=0.8)
plt.scatter(X[:, 0], X[:, 1], c=y, edgecolors='k', marker='o', s=50)
plt.show()

生成图的过程是基于 KNN（K-Nearest Neighbors）分类器的决策边界可视化。

以下是整个图生成过程的详细解释：

1. 生成数据集

我们使用 make_classification 函数生成一个人工数据集，这个数据集有 100 个样本和 5 个特征，其中 2 个特征是有信息量的（即能帮助分类），其余的特征是冗余或无关的。数据集的目标是模拟实际分类任务中的数据。

X, y = make_classification(n_samples=100, n_features=5, n_informative=2, random_state=42)

• X: 是特征矩阵，包含 100 个样本，每个样本有 5 个特征。
• y: 是每个样本对应的标签（分类结果）。

2. 训练 KNN 分类器

我们用生成的数据训练一个 KNN 分类器：

knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X, y)

• KNeighborsClassifier(n_neighbors=3)：创建一个 KNN 分类器，使用 3 个邻居进行分类。
• knn.fit(X, y)：使用 X 和 y 进行模型训练。

3. 创建网格用于预测

为了展示 KNN 分类器的决策边界，我们需要生成一个包含所有可能输入点的网格。网格点的数量决定了我们图像的分辨率，网格是通过对特征空间进行划分得到的。

x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1), np.arange(y_min, y_max, 0.1))

• xx 和 yy 是通过 np.meshgrid 生成的网格的坐标。np.arange(x_min, x_max, 0.1) 会创建一个从 x_min 到 x_max 的数值序列，步长为 0.1，同理 np.arange(y_min, y_max, 0.1) 会创建从 y_min 到 y_max 的数值序列。
• xx, yy：它们的形状分别是 (height, width)，代表平面坐标的网格。

4. 确保网格输入特征一致

由于我们训练模型时使用了 5 个特征，但网格生成时只有 2 个特征，因此我们需要填充额外的 3 个特征，以确保输入特征的维度和训练时一致。

grid_points = np.c_[xx.ravel(), yy.ravel(), np.zeros((xx.ravel().shape[0], 3))]

• np.c_[] 是一个方便的功能，用于将数组按列连接。xx.ravel() 和 yy.ravel() 将网格坐标转换为一维数组，然后我们通过 np.zeros 向每个点添加额外的 3 个特征（这些特征是 0，不会影响预测的结果）。

5. 进行预测

现在，网格上的每一个点都包含了 5 个特征，我们可以将这些点输入到训练好的 KNN 模型中，进行预测：

Z = knn.predict(grid_points)

• grid_points 是形状为 (N, 5) 的数组，N 是网格点的总数（例如，3000 个点）。knn.predict(grid_points) 将输出每个点的分类标签。

6. 绘制决策边界

接下来，我们可以绘制出 KNN 分类器的决策边界。这是通过对 xx 和 yy 进行 Z.reshape(xx.shape) 转换，将预测的分类结果与网格坐标对应起来，然后用 plt.contourf() 绘制填充的等高线来展示。

Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, alpha=0.8)

• Z.reshape(xx.shape) 将 Z 的形状调整为与 xx 相同的形状，确保与网格坐标对齐。
• plt.contourf() 用于绘制决策边界的填充等高线图。alpha=0.8 设置透明度，使得决策区域的颜色更加柔和。

7. 绘制数据点

最后，我们用 plt.scatter() 绘制数据点，显示训练数据的分布。X[:, 0] 和 X[:, 1] 分别是数据的前两个特征，用于二维图中显示：

plt.scatter(X[:, 0], X[:, 1], c=y, edgecolors='k', marker='o', s=50)

• X[:, 0] 和 X[:, 1] 是数据的前两个特征（我们只用前两个特征来显示图）。
• c=y 用于根据标签 y 给每个点上色。
• edgecolors='k' 用于设置点的边缘颜色为黑色。

8. 显示图像

最终，使用 plt.show() 来显示绘制的图像：

plt.show()

总结：

• 决策边界：通过网格点进行预测，我们可以看到不同类别的决策边界。这些边界代表了分类器如何将输入空间划分为不同的类。
• 数据点分布：图中的散点表示了数据点的位置，颜色代表不同的类别。
• 分类器的影响：不同的 K 值和距离度量会影响决策边界的形状，从而影响分类的效果。

总结

KNN是一个简单但强大的机器学习算法，适用于分类和回归任务。通过选择合适的K值和距离度

量方式，可以获得很好的性能。然而，KNN的计算和内存开销较大，尤其是在数据集较大的时候，因此在实际应用中需要注意其优缺点，并根据具体问题进行调整和优化。