K-近邻算法（K-Nearest Neighbors, KNN）原理与实现

K-近邻算法是一种基本且直观的监督学习算法，常用于分类和回归任务。它的核心思想是：一个样本的类别或数值可以由其邻近的K个样本的多数投票或平均值来决定。

算法原理详解

1. 基本概念

   • 假设我们有一个带标签的训练数据集，每个样本都有特征向量和对应的标签
   • 当需要预测新样本的类别时，KNN会找到训练集中与该样本最相似的K个邻居
   • 通过这K个邻居的标签来决定新样本的标签

2. 相似度度量

   • 欧几里得距离：最常用的距离度量方法

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

• 曼哈顿距离：在网格状路径中更适用

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

• 余弦相似度：更适合文本等稀疏数据

KNN分类算法实现步骤

1. 数据预处理

   # 特征标准化（重要步骤）
   from sklearn.preprocessing import StandardScaler
   scaler = StandardScaler()
   X_train_scaled = scaler.fit_transform(X_train)
   X_test_scaled = scaler.transform(X_test)
   

2. 距离计算

   import numpy as np
   
   def euclidean_distance(x1, x2):
       """计算两个向量之间的欧几里得距离"""
       return np.sqrt(np.sum((x1 - x2) ** 2))
   

3. 寻找K个最近邻

   def find_k_neighbors(X_train, y_train, x_test, k=5):
       """找到测试样本的K个最近邻居"""
       distances = []
   
       # 计算测试样本与所有训练样本的距离
       for i in range(len(X_train)):
           dist = euclidean_distance(x_test, X_train[i])
           distances.append((dist, y_train[i]))
   
       # 按距离排序并取前K个
       distances.sort(key=lambda x: x[0])
       neighbors = distances[:k]
   
       return neighbors
   

4. 多数投票决策

   from collections import Counter
   
   def predict_class(neighbors):
       """根据邻居进行多数投票"""
       class_votes = []
       for neighbor in neighbors:
           class_votes.append(neighbor[1])
   
       # 统计每个类别的票数
       vote_count = Counter(class_votes)
   
       # 返回票数最多的类别
       return vote_count.most_common(1)[0][0]
   

5. 完整的KNN分类器实现

   class KNNClassifier:
       def __init__(self, k=5):
           self.k = k
   
       def fit(self, X, y):
           self.X_train = X
           self.y_train = y
   
       def predict(self, X_test):
           predictions = []
           for x in X_test:
               neighbors = find_k_neighbors(self.X_train, self.y_train, x, self.k)
               prediction = predict_class(neighbors)
               predictions.append(prediction)
           return predictions
   

K值选择的影响分析

1. K值过小（如K=1）

   • 优点：对局部模式敏感，决策边界复杂
   • 缺点：容易过拟合，对噪声敏感

2. K值过大

   • 优点：决策边界平滑，减少噪声影响
   • 缺点：可能忽略局部特征，增加计算量

3. K值选择方法

   • 使用交叉验证选择最优K值
   • 通常选择奇数值避免平票情况
   • 经验法则：K ≈ √n（n为训练样本数）

算法复杂度分析

1. 训练阶段

   • 时间复杂度：O(1) - 只是存储数据
   • 空间复杂度：O(n) - 存储所有训练数据

2. 预测阶段

   • 时间复杂度：O(n×d) - 需要计算与所有训练样本的距离
   • 其中n是训练样本数，d是特征维度

优化策略

1. 使用KD树加速搜索

   from sklearn.neighbors import KDTree
   
   # 构建KD树
   kd_tree = KDTree(X_train)
   
   # 快速搜索K近邻
   distances, indices = kd_tree.query(X_test, k=5)
   

2. 使用球树（Ball Tree）

   • 适用于高维数据
   • 比KD树在某些情况下更高效

实际应用考虑

1. 特征选择的重要性

   • 无关特征会降低算法性能
   • 需要进行特征工程和特征选择

2. 数据标准化

   • KNN对特征尺度敏感
   • 必须进行标准化处理

3. 处理类别不平衡

   • 使用加权投票：根据距离给近邻分配不同权重
   • 距离越近的邻居投票权重越大

KNN算法虽然简单，但在很多实际应用中表现优秀，特别是在数据分布不明显的情况下。理解其原理和实现细节对于掌握机器学习基础至关重要。