kNN算法¶
参考文献：
- 机器学习实战——人邮版
- 统计学习方法（第二版）——李航
1、基本概念¶
又称 k-近邻算法
思路：选择训练数据集（类别已定）中前 k 个最相似的数据
输入输出¶
输入：某个实例的特征向量
输出：实例的类别
三要素¶
- k 值选择
- k 值减小，模型变复杂，容易过拟合，而且如果临近的是噪声，预测就错了
- k 值增大，模型变简单了。估计误差减小了，但是近似误差增大了
- 可以使用交叉验证法选取最优的 k 值
- 距离度量
- 一般是欧式距离，还有更一般的 $ L_{p} $ 距离：$ L_{p}\left(x_{i}, x_{j}\right)=\left(\sum_{l=1}{n}\left|x_{i}{l}-x_{j}{l}\right|{p}\right)^{\frac{1}{p}} $
- 分类决策规则（一般是多数表决）
如果上述三要素确定之后，对于给定的实例，它的类别就被唯一确定了。
2、优缺点¶
特点：不具有显式的学习过程，对近邻的点非常敏感
优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型，布尔型（也称标称型）
参考：机器学习实战——人邮版
3、一般流程¶
1、收集数据
2、准备数据（将原始数据结构化最好，期间可能对数据进行归一化）
3、分析数据
4、训练算法（不用训练）
5、测试算法（计算错误率）
6、使用算法
4、实现时考虑的问题¶
如何对训练数据进行快速 k 近邻搜索
最简单的方法：线性扫描
如何提高效率？¶
使用特殊的结构存储数据（如 kd 树），从而减少计算次数