K近邻（KNN）算法

直观理解

想象你走进一家水果店，看到一个形状奇特的水果，不知道它是什么。这时，你会怎么做？你可能会观察这个水果周围最相似的几个水果，如果周围的水果大多是苹果，那这个水果很可能也是苹果。这就是K近邻算法的基本思想！

算法原理

K近邻（KNN）算法就像"物以类聚"的道理，它通过观察未知样本周围最近的K个"邻居"的类别来判断该样本属于哪个类别。比如，要判断一个人喜欢什么类型的电影，我们可以看看和他兴趣最相似的K个人喜欢什么电影。

基本概念（以电影推荐为例）

• K值：要参考的邻居数量（比如参考最相似的3个人还是5个人）
• 距离度量：计算相似程度的方法（比如看两个人的观影历史有多相似）
• 权重：邻居的影响程度（比如最相似的人的推荐更重要）

算法流程

数学原理

距离度量

1. 欧氏距离：

$d(x_i, x_j) = \sqrt{\sum_{k=1}^n (x_{ik} - x_{jk})^2}$

2. 曼哈顿距离：

$d(x_i, x_j) = \sum_{k=1}^n |x_{ik} - x_{jk}|$

3. 闵可夫斯基距离：

$d(x_i, x_j) = (\sum_{k=1}^n |x_{ik} - x_{jk}|^p)^{\frac{1}{p}}$

权重计算

距离权重：

$w_i = \frac{1}{d_i^2}$

其中$d_i$是第i个近邻的距离。

算法步骤

1. 计算测试样本与所有训练样本的距离
2. 按距离排序，选择最近的K个样本
3. 对K个样本进行投票（分类）或平均（回归）
4. 确定测试样本的类别或值

优缺点

优点

• 理论成熟，思想简单
• 无需训练过程
• 对异常值不敏感
• 适用于多分类问题

缺点

• 计算量大
• 存储开销大
• 对K值选择敏感
• 特征尺度敏感

应用场景

1. 推荐系统

   • 商品推荐
   • 电影推荐
   • 音乐推荐

2. 模式识别

   • 手写字符识别
   • 图像分类
   • 语音识别

3. 预测分析

   • 房价预测
   • 信用评分
   • 用户行为预测

代码示例

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

# 加载数据
iris = load_iris()
X = iris.data
y = iris.target

# 数据预处理
scaler = StandardScaler()
X = scaler.fit_transform(X)

# 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

# 创建KNN分类器
knn = KNeighborsClassifier(n_neighbors=5, weights='distance')

# 训练模型
knn.fit(X_train, y_train)

# 预测
y_pred = knn.predict(X_test)

# 计算准确率
accuracy = knn.score(X_test, y_test)
print(f"模型准确率: {accuracy:.2f}")

调优技巧

1. K值选择

   • 使用交叉验证
   • 考虑数据集大小
   • 平衡偏差和方差

2. 距离度量

   • 选择合适的距离函数
   • 特征归一化
   • 特征权重调整

3. 算法优化

   • 使用KD树或球树
   • 降维处理
   • 并行计算

常见问题与解决方案

1. 计算效率

   • 使用近似最近邻
   • 数据索引结构
   • 降维处理

2. 维度灾难

   • 特征选择
   • 降维技术
   • 增加样本数量

3. 不平衡数据

   • 调整K值
   • 使用距离权重
   • 采样平衡