KNN

• 最近邻法 (​k=1)

  • ​理论基础

    • ​训练样本足够多的情况下，测试样本与其最相近的训练样本应具有相同的类别

  • ​决策规则

    •  $g_i(x)=\mathop{min}\limits_{k}||x-x^k_i||\\ if\quad g_j(x)=\mathop{min}\limits_{i}g_i(x)\quad then:x\in\omega_j$ 

  • ​错误率

    • ​错误率随训练样本数量增大而减少

    • ​错误率小于贝叶斯分类错误率的两倍

  • ​不足

    • ​计算量大、存储量大

    • ​训练样本数量有限，单个训练样本对结果可能产生较大影响

• ​KNN

  • ​优点

    • ​简单、易于实现

    • ​重新训练的代价低

    • ​计算时间和空间与训练集成线性关系

  • ​不足

    • 在训练集规模和特征维数较大时，​分类速度慢

    • ​各属性具有相同权重，影响准确率

    • ​当样本不平衡时影响准确率

    • ​样本库容量依赖性强

    • ​K值不好确定

  • ​K值的确定

    • ​k过小

      • ​近邻数少，会降低分类精度、放大噪声数据的干扰

    • ​k过大

      • ​并不相似的数据也被包含进来，噪声增加而导致分类效果下降

  • ​改进策略

    • ​降低计算复杂度

      • ​约减样本属性

      • ​缩小训练样本

      • ​聚类，将聚类的中心点作为新的训练样本

    • ​优化相似度度量方法

      • ​背景：基于欧几里得距离计算相似度，对噪声特征敏感

      • ​改进：给特征赋予不同权重

    • ​优化判决策略

      • ​均匀化样本分布密度

    • ​选取恰当k值

      • ​反复实验调整，当k增大到一定程度时，正确度下降