原理：找到与给定样本最近的k个样本的类别，其中最多的类别即是分类器结果
要点：1.最近——距离度量 2.集合决策——多数选举投票 3.k的选择
补充：最近邻算法：k=1；没有显式学习步骤，由上面三个唯一决定该算法结果
问题：找到k邻近的快速方法？[[ANN（近似最近邻搜索）]] KD树 (k-dimensional tree)、局部敏感哈希(LSH)

KNN算法中k值选择指南

KNN(K-最近邻)算法中k值的选择对模型性能有重大影响。以下是关于k值选择的详细分析：

1. k值的影响

模型表现

  • 小k值：

  • 复杂度高（因为分类边界复杂)，容易过拟合

  • 对噪声敏感，决策边界不规则

  • 低偏差但高方差

  • 大k值：

  • 模型更平滑，减少噪声影响

  • 可能导致欠拟合

  • 高偏差但低方差

计算效率

  • 较大k值需要计算更多邻居，略微增加计算成本

2. 选择k值的方法

经验法则

  • 分类问题：通常从k=√n开始(n为样本数)
  • 回归问题：常用3-10之间的奇数

交叉验证

最佳实践是使用交叉验证选择k值：

  1. 将数据分为训练集和验证集
  2. 尝试不同的k值
  3. 选择在验证集上表现最好的k值

启发式方法

  • 对于类别不平衡数据，选择较小的k值
  • 数据噪声大时，选择较大的k值
  • 特征维度高时，可能需要较大的k值

3. 特殊考虑

类别不平衡

  • 在类别不平衡数据中，大k值可能导致少数类被忽略
  • 解决方案：
  • 使用加权KNN
  • 选择与少数类样本数量相当的k值

数据规模

  • 大数据集：可以使用较小的k值
  • 小数据集：需要较大的k值以避免过拟合