K 近邻算法（k-nearest neighbors, KNN）是一种很基本的机器学习方法
算法步骤：给定样本，寻找最近的 K 个样本进行（分类/回归）预测
KNN的 3 个核心要素：
- K 值的选择，较小时容易过拟合；较大时泛化性好，但训练误差大
- 距离度量方式，比如欧氏距离、曼哈顿距离（常见距离测度）
- 决策规则，分类问题常用投票法，回归问题常用平均法
KNN 的主要优点：
- 理论成熟，思想简单，既可以用来做（非线性）分类也可以用来做回归
- 训练时间复杂度比支持向量机之类的算法低，仅为 O (n)
- 和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感
- 对于类域的交叉或重叠较多的待分样本集来说，KNN 方法较其他方法更为适合
- 适用于样本量比较大的类域的自动分类，而对于样本量较小的类域容易产生误分
KNN 的主要缺点：
- 计算量大，尤其是特征数非常多的时候
- 样本不平衡的时候，对稀有类别的预测准确率低
- 使用懒散学习方法，相比逻辑回归类算法预测速度慢
- 相比决策树模型，KNN 模型可解释性不强
KNN 的效率优化：（空间换时间）
- 通过构建 KD 树/球树来提高最近样本的搜索效率
- 但是 KD 树/球树的构建需要额外消耗大量的内存
- 更多 KD 树/球树的构建细节可参阅：K近邻法(KNN)原理小结
KNN 的预测精度改善优化：
- 对于离群点，KNN 找到的最近邻样本对应的实际距离可能很远
- 考虑设定一个最大距离（又称限定半径），来避免上述问题
- 针对分类问题，考虑根据每个类的质心来寻找最近邻类（最近质心算法）