本文介绍 K 近邻（KNN）算法在机器学习中的基本原理、特点、注意事项，以及实现 KNN 模型的完整步骤。

1. K 近邻算法的基本原理

K 近邻算法（KNN）的核心思想是通过“邻居”来进行决策。它假设相似的输入具有相似的输出，因此通过计算输入数据与训练数据之间的距离，找到最近的 ( K ) 个邻居，然后根据这些邻居的类别来进行预测。

1.1 相似性原则

KNN 基于相似性原则进行预测。输入实例的类别或数值预测是基于其在特征空间中邻近的 ( K ) 个已标记实例的类别或数值。

1.2 不同的距离度量

距离度量是 KNN 算法的关键，因为它决定了哪些训练样本是测试样本的最近邻居。以下是常用的距离度量：

• 欧几里得距离：

  欧几里得距离用于度量两个点之间的“直线”距离，适用于连续型数据。其公式为：

  \[\text{Euclidean Distance}(x, y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}\]

• 曼哈顿距离：

  曼哈顿距离用于度量两个点在“网格”上的距离，适用于稀疏数据。其公式为：

  \[\text{Manhattan Distance}(x, y) = \sum_{i=1}^{n}|x_i - y_i|\]

• 闵可夫斯基距离：

  闵可夫斯基距离是欧几里得距离和曼哈顿距离的推广，其公式为：

  \[\text{Minkowski Distance}(x, y) = \left(\sum_{i=1}^{n}|x_i - y_i|^p\right)^{1/p}\]

  其中，(p = 2) 时为欧几里得距离，(p = 1) 时为曼哈顿距离。

• 余弦相似度：

  余弦相似度用于衡量两个向量的方向相似性，适用于文本数据。其公式为：

  \[\text{Cosine Similarity}(x, y) = \frac{x \cdot y}{\|x\| \|y\|}\]

  其中，(x \cdot y) 是向量的点积，(|x|) 和 (|y|) 是向量的范数。

1.3 类别选择

1.3.1 多数投票（分类）

对于分类问题，KNN 使用多数投票来决定输入实例的类别：

1. 计算距离：对于每个测试样本，计算其与所有训练样本之间的距离。

2. 选择最近的 ( K ) 个邻居：根据计算的距离选择最近的 ( K ) 个训练样本。

3. 投票决定类别：在这 ( K ) 个邻居中，选择出现次数最多的类别作为测试样本的预测类别。

例如，对于一个测试样本，如果 ( K=3 ) 且最近邻的类别为 [0, 1, 1]，则预测类别为 1。

1.3.2 平均（回归）

对于回归问题，KNN 使用邻居的平均值来预测输入实例的数值：

1. 计算距离：与分类问题类似，计算测试样本与所有训练样本之间的距离。

2. 选择最近的 ( K ) 个邻居：选择距离最近的 ( K ) 个样本。

3. 计算平均值：对这 ( K ) 个邻居的目标值取平均值，作为预测值。

例如，对于一个测试样本，如果 ( K=3 ) 且最近邻的目标值为 [2.5, 3.0, 3.5]，则预测值为 ((2.5 + 3.0 + 3.5) / 3 = 3.0)。

1.4 选择 ( K ) 值

选择合适的 ( K ) 值是 KNN 算法的关键：

• 小 ( K ) 值：较小的 ( K ) 值（如 1 或 2）使模型对噪声数据敏感，可能导致过拟合。

• 大 ( K ) 值：较大的 ( K ) 值使模型变得更平滑，但可能导致欠拟合。

• 通常做法：通过交叉验证来选择最优的 ( K ) 值，以平衡模型的复杂度和泛化能力。

通过理解 KNN 算法的核心思想、距离度量、类别选择以及如何选择 ( K ) 值，可以更好地应用和调整该算法以适应具体任务。

2. 实现步骤

我们使用 iris 数据集来进行一个简单的实现。iris 数据集常用于分类问题，包含四个特征和三种类别的鸢尾花。

2.1 数据准备

加载数据集，分割训练集和测试集，并对特征进行标准化。

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score, confusion_matrix, classification_report

# 加载iris数据集
data = load_iris()
X = data.data  # 特征数据
y = data.target  # 目标标签

# 将数据集分为训练集和测试集，80%用于训练，20%用于测试
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

scaler = StandardScaler()  # 标准化特征数据
X_train = scaler.fit_transform(X_train)
X_test = scaler.transform(X_test)

2.2 距离计算

定义欧几里得距离的计算方法。

def euclidean_distance(x1, x2):
    return np.sqrt(np.sum((x1 - x2) ** 2))

2.3 KNN 算法实现

根据计算的距离选择最近的 ( K ) 个邻居，并进行分类或回归预测。

def knn_predict(X_train, y_train, X_test, k=3):
    """
    使用KNN算法进行预测
    
    参数:
    X_train -- 训练特征矩阵
    y_train -- 训练标签向量
    X_test -- 测试特征矩阵
    k -- 邻居数量
    
    返回:
    y_pred -- 预测标签
    """
    y_pred = []
    for test_point in X_test:
        # 计算测试点与所有训练点之间的距离
        distances = [euclidean_distance(test_point, x_train) for x_train in X_train]
        # 获取距离最近的k个样本的索引
        k_indices = np.argsort(distances)[:k]
        # 获取最近邻的标签
        k_nearest_labels = [y_train[i] for i in k_indices]
        # 统计最多的类别标签
        most_common = np.bincount(k_nearest_labels).argmax()
        y_pred.append(most_common)
    return y_pred

2.4 模型评估

使用测试数据集评估模型性能。

y_pred = knn_predict(X_train, y_train, X_test, k=3)
accuracy = accuracy_score(y_test, y_pred)
conf_matrix = confusion_matrix(y_test, y_pred)
class_report = classification_report(y_test, y_pred)

print("\nAccuracy:", accuracy)
print("Confusion Matrix:\n", conf_matrix)
print("Classification Report:\n", class_report)

3. 优缺点

3.1 优点

1. 简单易用：KNN 是一种非参数算法，易于理解和实现。

2. 无需训练：不需要显式的模型训练，直接对数据进行预测。

3. 适合多类别问题：可以处理多类别分类问题。

4. 易于更新：新数据可以很容易地添加到已有数据中，不需要重新训练模型。

3.2 缺点

1. 计算成本高：预测阶段需要计算每个测试样本与所有训练样本的距离，计算复杂度高。

2. 存储需求大：需要存储所有训练样本，存储需求大。

3. 对尺度敏感：特征尺度对距离计算有很大影响，需要对特征进行标准化。

4. 对噪声和异常值敏感：噪声数据和异常值可能会对结果产生较大影响。

5. 选择 ( K ) 值困难：选择合适的 ( K ) 值对模型性能有很大影响。

KNN 在处理小规模数据集和低维特征空间时表现良好，但在大规模数据集和高维特征空间中计算效率和存储需求较高。根据具体任务的需求和数据特性选择合适的 ( K ) 值和距离度量是非常重要的。

4. 交叉验证选择最优的 ( K )

通过交叉验证选择最优的 ( K ) 值是一种常见的方法，它能够帮助我们找到在特定数据集上表现最佳的 ( K ) 值，进而提高模型的泛化能力。下面是详细的步骤和代码实现：

交叉验证选择最优 ( K ) 值的步骤

1. 划分数据集：将数据集划分为多个不重叠的子集（通常为 5 或 10 个），称为“折”（folds）。

2. 模型训练和验证：对于每个可能的 ( K ) 值，进行以下步骤：
   • 对于每个折：
     • 使用该折以外的数据作为训练集，当前折作为验证集。
     • 在训练集上训练 KNN 模型，并在验证集上测试。
   • 计算模型在所有折上的平均验证准确率。

3. 选择最优 ( K ) 值：选择验证准确率最高的 ( K ) 值作为最优的 ( K ) 值。

4. 模型评估：使用最优的 ( K ) 值在整个训练集上训练模型，并在测试集上评估其性能。

Python 实现

这里使用 scikit-learn 的 KFold 和 KNeighborsClassifier 来实现上述步骤。

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import KFold
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score

# 加载iris数据集
data = load_iris()
X = data.data  # 特征数据
y = data.target  # 目标标签

# 标准化特征数据
scaler = StandardScaler()
X = scaler.fit_transform(X)

# 定义交叉验证
kf = KFold(n_splits=5, shuffle=True, random_state=42)

# 定义可能的K值范围
k_values = range(1, 31)
best_k = None
best_score = 0

# 遍历每个K值
for k in k_values:
    accuracies = []

    # 对于每个折进行训练和验证
    for train_index, val_index in kf.split(X):
        X_train, X_val = X[train_index], X[val_index]
        y_train, y_val = y[train_index], y[val_index]

        # 使用当前K值训练模型
        knn = KNeighborsClassifier(n_neighbors=k)
        knn.fit(X_train, y_train)

        # 在验证集上评估模型
        y_pred = knn.predict(X_val)
        accuracy = accuracy_score(y_val, y_pred)
        accuracies.append(accuracy)

    # 计算当前K值的平均验证准确率
    avg_accuracy = np.mean(accuracies)
    print(f"K={k}, Average Accuracy={avg_accuracy:.4f}")

    # 更新最优K值
    if avg_accuracy > best_score:
        best_score = avg_accuracy
        best_k = k

print(f"\nBest K value: {best_k}, with Average Accuracy: {best_score:.4f}")

# 使用最优K值在整个训练集上训练模型
knn_best = KNeighborsClassifier(n_neighbors=best_k)
knn_best.fit(X, y)

解释

• KFold 交叉验证：KFold(n_splits=5) 将数据集分为 5 个折，每次用 4 个折训练模型，1 个折验证模型。

• K 值范围：通常我们尝试从 1 到一个适中的上限（如 30）来测试不同的 ( K ) 值。

• 平均验证准确率：对于每个 ( K ) 值，我们计算其在所有折上的平均验证准确率，以此来评估该 ( K ) 值的性能。

• 选择最优 ( K ) 值：选择验证准确率最高的 ( K ) 值作为最优值。

通过这样的交叉验证过程，我们能够有效地选择合适的 ( K ) 值，进而提高 KNN 模型的泛化能力。

• Previous
  机器学习课程笔记（Machine Learning）
• Next
  机器学习课程笔记（Machine Learning）