K近邻算法

1. 概述

K近邻算法（K-Nearest Neighbors, KNN）是一种基于实例的学习（Instance-Based Learning）或惰性学习（Lazy Learning）算法。与前面介绍的训练过程中显式学习参数模型不同，KNN没有显式的训练过程，分类决策仅依赖于局部邻域的信息。

1.1 核心思想

“物以类聚，人以群分”

KNN的基本思想非常直观：给定一个测试样本，在特征空间中找出与它距离最近的 $K$ 个邻居，根据这些邻居的类别信息来预测该样本的类别。

1.2 算法流程

输入：训练数据集 D，测试样本 x，近邻数 K

1. 计算测试样本 x 与训练集中所有样本的距离
2. 选取距离最小的 K 个样本
3. 根据这 K 个样本的标签进行投票：
   - 分类：多数表决
   - 回归：均值/加权均值

输出：预测结果

1.3 “惰性”的意义

KNN被称为”惰性学习”，因为：

特征	惰性学习（KNN）	积极学习（如SVM、逻辑回归）
训练阶段	无计算（或仅存储数据）	显式求解参数
预测阶段	计算量大	计算量小
存储需求	需要全部训练数据	只存储模型参数

2. 距离度量

2.1 欧氏距离

最常用的距离度量，定义为：

d (x, y) = i = 1 \sum n (x_{i} - y_{i})^{2} = ∥ x - y ∥_{2}

2.2 曼哈顿距离

也称为城市街区距离：

d (x, y) = i = 1 \sum n ∣ x_{i} - y_{i} ∣ = ∥ x - y ∥_{1}

2.3 闵可夫斯基距离

欧氏距离和曼哈顿距离的推广：

d (x, y) = (i = 1 \sum n ∣ x_{i} - y_{i} ∣^{p})^{1/ p} = ∥ x - y ∥_{p}

$p$ 值	距离类型
$p = 1$	曼哈顿距离
$p = 2$	欧氏距离
$p \to \infty$	切比雪夫距离

2.4 余弦相似度

衡量两个向量方向的相似性：

cos (x, y) = \frac{x \cdot y}{∥ x ∥∥ y ∥}

适用于文本分类中高维稀疏向量。

2.5 马氏距离

考虑特征之间相关性的距离：

d_{M} (x, y) = (x - y)^{T} Σ^{- 1} (x - y)

其中 $Σ$ 是协方差矩阵。

2.6 汉明距离

用于度量离散特征（如二进制串）之间的距离：

d_{H ammin g} (x, y) = i = 1 \sum n I [x_{i} \neq = y_{i}]

3. K值的选择

3.1 K值的影响

        K=1                      K=5                      K=15
     ┌─────────┐             ┌─────────┐             ┌─────────┐
     │         │             │         │             │         │
  ○  │    ●────┼──●          │    ●────┼──●          │    ●────┼──●
     │         │              │         │              │         │
     │  ●   ○  │              │  ●   ○  │              │  ●   ○  │
     │         │              │         │              │         │
     └─────────┘              └─────────┘              └─────────┘
     K=1: 决策边界复杂          K=5: 平衡               K=15: 平滑边界
     易过拟合                   较好的泛化              可能欠拟合

3.2 K值选择策略

经验法则： $K \approx N$ ，其中 $N$ 是样本数
交叉验证：使用验证集选择最优 $K$
奇数原则：对于二分类，使用奇数 $K$ 避免平票

3.3 K值与偏差-方差的关系

K值	偏差（Bias）	方差（Variance）	特点
小K	高偏差	高方差	复杂边界，可能过拟合
大K	低偏差	低方差	简单边界，可能欠拟合

4. 加权KNN

4.1 距离加权

为距离较近的邻居赋予更大的权重：

\overset{y}{^} = \frac{\sum _{i = 1}^{K} w _{i} y _{i}}{\sum _{i = 1}^{K} w _{i}}

其中 $w_{i} = \frac{1}{d ( x , x _{i} ) ^{2}}$ （反距离平方加权）。

4.2 核函数加权

使用核函数根据距离分配权重：

核函数	权重公式
均匀核	$w_{i} = 1/ K$ （等权重）
距离反比	$w_{i} = 1/ d_{i}$
高斯核	$w_{i} = exp (- d_{i}^{2} /2 σ^{2})$

5. KD树与Ball树

5.1 暴力搜索的复杂度

KNN的朴素实现需要计算测试样本与所有训练样本的距离，时间复杂度为 $O (N D)$ ，其中 $N$ 是样本数， $D$ 是特征维度。对于大规模数据集，这会成为瓶颈。

5.2 KD树

KD树是一种对 $K$ 维空间进行二进制划分的数据结构。

构建过程：

1. 选择当前维度的方差最大的特征
2. 选择该特征的中位数作为切分点
3. 递归地对左右子空间进行划分

搜索过程：

def knn_search_kd-tree(point, kdtree, k):
    # 1. 从根节点开始，找到包含目标点的叶节点
    # 2. 在路径上回溯，检查是否有更近的点
    # 3. 使用"回溯"策略，只在必要时访问其他分支

复杂度：

构建： $O (N lo g N)$
搜索：平均 $O (lo g N)$ ，最坏 $O (N)$

5.3 Ball树

当数据在高维空间或特征尺度不同时，Ball树比KD树更高效。

6. 代码实现

6.1 朴素实现

import numpy as np
from collections import Counter
 
class KNN:
    """K近邻分类器"""
    
    def __init__(self, k: int = 5, p: float = 2.0):
        """
        参数:
            k: 近邻数
            p: 距离度量 (p=2为欧氏距离, p=1为曼哈顿距离)
        """
        self.k = k
        self.p = p
        self.X_train = None
        self.y_train = None
    
    def fit(self, X, y):
        """KNN是惰性学习，这里只是存储数据"""
        self.X_train = np.array(X)
        self.y_train = np.array(y)
        return self
    
    def _compute_distance(self, x1, x2):
        """计算距离"""
        return np.sum(np.abs(x1 - x2) ** self.p) ** (1/self.p)
    
    def _predict_single(self, x):
        """对单个样本预测"""
        # 计算与所有训练样本的距离
        distances = [self._compute_distance(x, x_train) 
                    for x_train in self.X_train]
        
        # 找到K个最近邻的索引
        k_indices = np.argsort(distances)[:self.k]
        
        # 获取K个近邻的标签
        k_labels = self.y_train[k_indices]
        
        # 投票（多数表决）
        most_common = Counter(k_labels).most_common(1)
        return most_common[0][0]
    
    def predict(self, X):
        """预测多个样本"""
        X = np.array(X)
        return np.array([self._predict_single(x) for x in X])
 
 
# 示例使用
if __name__ == "__main__":
    from sklearn.datasets import load_iris
    from sklearn.model_selection import train_test_split
    
    iris = load_iris()
    X, y = iris.data, iris.target
    
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
    
    # 使用sklearn
    from sklearn.neighbors import KNeighborsClassifier
    from sklearn.preprocessing import StandardScaler
    
    # KNN对特征缩放敏感，需要标准化
    scaler = StandardScaler()
    X_train_scaled = scaler.fit_transform(X_train)
    X_test_scaled = scaler.transform(X_test)
    
    knn = KNeighborsClassifier(n_neighbors=5, p=2)
    knn.fit(X_train_scaled, y_train)
    
    accuracy = knn.score(X_test_scaled, y_test)
    print(f"Test Accuracy: {accuracy:.4f}")

6.2 带距离加权的实现

class WeightedKNN:
    """带距离加权的KNN"""
    
    def __init__(self, k: int = 5, use_distance_weight: bool = True):
        self.k = k
        self.use_distance_weight = use_distance_weight
    
    def fit(self, X, y):
        self.X_train = np.array(X)
        self.y_train = np.array(y)
        return self
    
    def predict(self, X):
        X = np.array(X)
        predictions = []
        
        for x in X:
            distances = np.linalg.norm(self.X_train - x, axis=1)
            
            # 找到K个最近邻
            k_indices = np.argsort(distances)[:self.k]
            k_distances = distances[k_indices]
            k_labels = self.y_train[k_indices]
            
            if self.use_distance_weight:
                # 距离加权（避免除零）
                k_distances = np.maximum(k_distances, 1e-10)
                weights = 1 / k_distances
                # 按权重投票
                unique_labels = np.unique(k_labels)
                scores = {}
                for label in unique_labels:
                    mask = k_labels == label
                    scores[label] = np.sum(weights[mask])
                prediction = max(scores, key=scores.get)
            else:
                # 简单多数表决
                prediction = Counter(k_labels).most_common(1)[0][0]
            
            predictions.append(prediction)
        
        return np.array(predictions)

7. 特征缩放的重要性

KNN使用距离度量，因此特征缩放至关重要。

7.1 标准化 vs 归一化

方法	公式	适用场景
Z-score标准化	$x^{'} = \frac{x - μ}{σ}$	特征近似正态分布
Min-Max归一化	$x^{'} = \frac{x - x _{min}}{x _{ma x} - x _{min}}$	有明确边界
Robust缩放	$x^{'} = \frac{x - m e d ian}{I QR}$	有异常值

7.2 为什么重要？

    特征A: 取值范围 [0, 1]          特征B: 取值范围 [0, 1000]
    
    标准化前：                       标准化后：
    距离 ≈ 特征B的差异               距离 ≈ 特征A的差异 + 特征B的差异
    （特征B主导）                    （两特征同等重要）

8. 维数灾难

8.1 问题描述

在高维空间中，“距离集中”现象（Distance Concentration）会导致KNN性能下降。随着维度增加，所有样本之间的距离趋向于相等。

8.2 解决方案

降维：使用 PCA、t-SNE等方法
特征选择：选择最相关的特征
距离度量学习：学习适合数据的距离度量

9. 优缺点分析

优点

优点	说明
简单直观	算法思想易于理解
无需训练	没有显式的训练过程
对数据分布无假设	非参数方法
可处理多分类	自然扩展
可用于回归和分类	通用性强

缺点

缺点	说明
预测时间长	需要计算与所有样本的距离
存储需求大	需要存储全部训练数据
对特征缩放敏感	需要标准化
维数灾难	高维性能下降
对噪声敏感	K值小时易受噪声影响

10. 应用场景

10.1 推荐系统

协同过滤中，使用KNN找到相似用户或物品：

from sklearn.neighbors import NearestNeighbors
 
# 找到与目标用户最相似的K个用户
user_ratings = user_item_matrix[target_user]
neighbors = NearestNeighbors(n_neighbors=K, metric='cosine')
neighbors.fit(user_item_matrix)
distances, indices = neighbors.kneighbors([user_ratings])

10.2 异常检测

将远离大多数样本的点视为异常：

def knn_anomaly_detection(X, k=5, threshold=0.95):
    knn = NearestNeighbors(n_neighbors=k)
    knn.fit(X)
    
    # 计算每个点到第K个最近邻的距离
    distances, _ = knn.kneighbors(X)
    k_distances = distances[:, -1]
    
    # 距离大于阈值的点为异常
    threshold_value = np.percentile(k_distances, threshold * 100)
    return k_distances > threshold_value

10.3 图像分类

KNN曾用于手写数字识别（MNIST），虽然深度学习方法后来居上，但KNN仍然是一个有效的基线。

11. 与其他算法的关系

11.1 KNN vs 决策树

特征	KNN	决策树
学习方式	惰性	积极
边界形状	非线性	轴平行
对噪声	敏感	相对鲁棒
可解释性	低	高

11.2 KNN vs SVM

特征	KNN	SVM
复杂度	预测时高	预测时低
边界形状	自适应	核决定
参数	K、距离度量	C、核

Metaphor

探索