【学习】《算法图解》第十二章学习笔记：K近邻算法

前言

《算法图解》第十二章介绍了一种简单而强大的机器学习算法——K近邻算法（K-Nearest Neighbors，简称KNN）。这是一种基于实例的学习方法，也是机器学习领域中最基础、最直观的算法之一。本章不仅讲解了KNN的基本原理和实现方式，还探讨了特征提取、归一化等重要概念，为读者打开了机器学习的大门。本笔记将梳理KNN算法的核心思想、实现步骤以及应用场景。

一、K近邻算法概述

（一）基本思想

K近邻算法的核心思想非常简单：物以类聚，人以群分。它基于一个假设：相似的事物通常具有相似的特征，并且在特征空间中彼此靠近。

具体来说，KNN算法的基本思路是：

  1. 对于一个待分类的新实例，在训练数据集中找到与它最相似（距离最近）的K个实例
  2. 这K个实例中出现最多的类别，就作为新实例的预测类别

（二）算法特点

KNN算法具有以下特点：

  1. 非参数化方法：不对数据分布做任何假设，完全依赖于数据本身
  2. 惰性学习：没有显式的训练过程，只在需要预测时才进行计算
  3. 直观易懂：算法思想简单，容易理解和实现
  4. 计算复杂度高：预测时需要计算新实例与所有训练实例的距离

二、KNN算法步骤详解

（一）算法流程

KNN算法的基本流程如下：

  1. 收集数据：准备训练数据集，每个实例包含特征向量和类别标签
  2. 选择距离度量：确定如何计算实例之间的相似度（通常使用欧几里得距离）
  3. 对新实例进行分类：
    • 计算新实例与训练集中所有实例的距离
    • 选择距离最近的K个实例
    • 统计这K个实例中各类别的频次
    • 将出现频次最高的类别作为新实例的预测类别

（二）距离度量

KNN算法中，距离度量是衡量两个实例相似度的关键。常用的距离度量方法包括：

  1. 欧几里得距离：最常用的距离计算方法
    $$d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$$

  2. 曼哈顿距离：沿坐标轴方向的距离总和
    $$d(x, y) = \sum_{i=1}^{n}|x_i - y_i|$$

  3. 闵可夫斯基距离：欧几里得距离和曼哈顿距离的一般化形式
    $$d(x, y) = \left(\sum_{i=1}^{n}|x_i - y_i|^p\right)^{1/p}$$

  4. 余弦相似度：计算两个向量的夹角余弦值，常用于文本分析
    $$\cos(\theta) = \frac{x \cdot y}{||x|| \times ||y||}$$

在《算法图解》中，主要使用欧几里得距离作为度量标准。

（三）K值的选择

K值的选择对KNN算法的性能有重要影响：

  • K值过小（如K=1）：算法对噪声敏感，容易过拟合
  • K值过大：可能会忽略局部特征，导致欠拟合
  • 经验法则：一般选择训练样本数量的平方根作为K值的参考
  • 实践建议：通常通过交叉验证等方法从多个候选值中选择最优的K值

另外，为了避免平局情况，K值通常选择奇数。

三、特征工程与数据预处理

（一）特征提取

在应用KNN算法之前，需要将原始数据转换为特征向量。《算法图解》中提到了几种常见的特征提取方法：

  1. 数值型特征：直接使用原始数值，如身高、体重等
  2. 分类特征：通过独热编码（One-Hot Encoding）等方法转换为数值
  3. 文本特征：可以使用词袋模型（Bag of Words）或TF-IDF等方法提取特征
  4. 图像特征：可以提取颜色直方图、纹理特征等

特征提取的质量直接影响KNN算法的性能，因此需要根据具体问题选择合适的特征表示方法。

（二）特征归一化

由于KNN算法基于距离计算，不同特征的量纲（单位和范围）差异会对结果产生不公平的影响。例如，如果一个特征的取值范围是0-1，另一个特征的取值范围是0-1000，那么第二个特征将在距离计算中占据主导地位。

为了解决这个问题，需要对特征进行归一化处理，常用的方法包括：

  1. 最小-最大归一化（Min-Max Scaling）：将特征缩放到[0, 1]区间
    $$x’ = \frac{x - \min(x)}{\max(x) - \min(x)}$$

  2. Z-score标准化：将特征转换为均值为0、标准差为1的分布
    $$x’ = \frac{x - \mu}{\sigma}$$

在《算法图解》中，作者强调了归一化的重要性，并建议在实际应用中始终对特征进行适当的归一化处理。

四、Python实现KNN算法

（一）基本实现

以下是KNN算法的简单Python实现：

import numpy as np
from collections import Counter

def knn_classify(training_data, training_labels, new_instance, k=3, distance_fn=None):
    """
    使用KNN算法对新实例进行分类
    
    参数:
    training_data -- 训练数据集，每行是一个实例的特征向量
    training_labels -- 训练数据的类别标签
    new_instance -- 待分类的新实例
    k -- 近邻数量
    distance_fn -- 距离计算函数，默认为欧几里得距离
    
    返回:
    predicted_label -- 预测的类别标签
    """
    # 如果没有提供距离函数，使用欧几里得距离
    if distance_fn is None:
        distance_fn = lambda x, y: np.sqrt(np.sum((x - y) ** 2))
    
    # 计算新实例与所有训练实例的距离
    distances = []
    for i, instance in enumerate(training_data):
        dist = distance_fn(instance, new_instance)
        distances.append((dist, training_labels[i]))
    
    # 按距离排序并选择前k个
    distances.sort(key=lambda x: x[0])
    k_nearest = distances[:k]
    
    # 统计这k个近邻中各类别的频次
    k_nearest_labels = [label for _, label in k_nearest]
    most_common = Counter(k_nearest_labels).most_common(1)
    
    return most_common[0][0]

（二）示例应用

以《算法图解》中的电影分类例子为例，我们可以使用KNN算法对电影进行分类：

# 电影数据：[动作场景数, 浪漫场景数]
movies = np.array([
    [3, 104],  # "爱情片"
    [2, 100],  # "爱情片"
    [1, 81],   # "爱情片"
    [101, 10], # "动作片"
    [99, 5],   # "动作片"
    [98, 2]    # "动作片"
])

# 电影类别标签
labels = ["爱情片", "爱情片", "爱情片", "动作片", "动作片", "动作片"]

# 对特征进行归一化
def normalize(data):
    min_vals = np.min(data, axis=0)
    max_vals = np.max(data, axis=0)
    ranges = max_vals - min_vals
    normalized_data = np.zeros(np.shape(data))
    m = data.shape[0]
    normalized_data = (data - np.tile(min_vals, (m, 1))) / np.tile(ranges, (m, 1))
    return normalized_data

# 归一化后的电影数据
normalized_movies = normalize(movies)

# 待分类的新电影：[动作场景数, 浪漫场景数]
new_movie = np.array([18, 90])
normalized_new_movie = (new_movie - np.min(movies, axis=0)) / (np.max(movies, axis=0) - np.min(movies, axis=0))

# 使用KNN算法进行分类
predicted_category = knn_classify(normalized_movies, labels, normalized_new_movie, k=3)
print(f"这部新电影可能是: {predicted_category}")

五、KNN算法的优缺点

（一）优点

  1. 简单直观：算法思想容易理解，实现简单
  2. 无需训练：不需要构建模型，可以直接用于分类
  3. 适用性广：可用于分类和回归问题
  4. 理论成熟：有完善的数学理论支持
  5. 对数据分布无假设：不需要对数据分布做任何假设

（二）缺点

  1. 计算复杂度高：预测时需要计算与所有训练实例的距离，时间复杂度为O(n)，其中n是训练集大小
  2. 存储开销大：需要存储全部训练数据
  3. 对特征缩放敏感：不同特征的量纲差异会影响结果
  4. 维度灾难：在高维空间中，距离度量的区分能力下降
  5. 对噪声敏感：异常值可能对结果产生较大影响

六、KNN的实际应用

（一）应用场景

KNN算法在许多领域都有广泛应用：

  1. 推荐系统：基于用户相似度推荐商品、电影等
  2. 图像识别：通过图像特征进行分类
  3. 文本分类：对文档进行主题分类
  4. 医疗诊断：基于病人症状和历史病例进行疾病诊断
  5. 金融风控：信用评分和风险评估

（二）KNN的改进

为了解决KNN算法的一些缺点，研究人员提出了多种改进方法：

  1. KD树：使用KD树等数据结构加速近邻搜索
  2. 加权KNN：根据距离对近邻的投票进行加权
  3. 局部加权回归：在回归问题中使用加权平均
  4. 降维技术：使用PCA等方法降低特征维度
  5. 特征选择：选择最相关的特征子集

七、总结

K近邻算法是一种简单而强大的机器学习方法，它通过比较新实例与已知实例的相似度来进行分类或回归。尽管KNN算法有计算复杂度高、存储开销大等缺点，但其简单直观的特性使其成为机器学习入门的理想算法，也是实际应用中的重要工具之一。

在实践中，特征工程（特别是特征提取和归一化）对KNN算法的性能至关重要。此外，K值的选择也需要根据具体问题进行调整，通常通过交叉验证等方法确定最优值。

《算法图解》通过生动的例子和清晰的解释，帮助读者理解了KNN算法的基本原理和应用方法，为进一步学习更复杂的机器学习算法奠定了基础。

八、参考资料