kNN算法
kNN算法
kNN（k-Nearst Neighbors）也叫k近邻算法是一种监督学习模型，其定义很简单，如果一个样本特征空间中的个最邻近的样本中大多数属于某个类别，则该样本也属于这个类别，也就是“近朱者赤，近墨者黑”。
这是ML中最基本的算法之一，但是模型并不需要从样本特征空间中学习到什么东西，而是直接计算样本的相似度来确定待预测样本应该与哪些训练样本标签保持一致。
三要素
k值
一般根据样本分布选择一个较小的值，然后通过交叉验证来选择一个比较合适的最终值。使用较小值会让模型变得更加复杂，容易过拟合。使用较大值误差会增大，容易欠拟合。
同时为了方便投票，一般将设置为奇数。
这里我们举两个例子来看k值对预测的影响
很明显我们发现取时，待预测样本将为蓝色类，而时又将变成红色类。
距离度量
- 因为需要计算样本间的相似度，所以需要选择一种计算样本距离的方式，常用欧几里得距离，有时也会使用欧式距离、曼哈顿距离等。
决策规则
kNN既可以用于回归也可以用于分类，但是在不同的任务上处理稍有不同，对于分类预测，一般使用多数表决法，而回归预测中常用平均值法。
用于分类时，可以通过多数表决或者加权多数表决来确定一个待预测样本的类别。 用于回归时，可以使用平均值或加权平均值来确定一个待预测样本的预测值。
实现
暴力
- 计算预测样本到所有训练集样本的距离，然后选择最小的k个距离得到k个邻近点。当特征数较多时，效率低。
KD树
先对训练数据进行建模构建KD树，再根据建好的模型获取邻近样本数据。后续还有基于KD树的修改方案，例如BBF树、MVP树等
关于KD树，后续应该会用单独的篇章讲解实现todo
优化
分簇
为了缓解每次预测需要查询所有距离，我们可以将样本分为多个样本簇，并计算簇的中心点，每次预测时先确定样本与哪个簇中心最近，再在这个簇中心找邻居，当然分簇又涉及到聚类的问题，此处不详细展开。
例如对于10,000条数据，分为50个簇，每个簇包含200个样本，则每次预测从10,000次对比下降到50+200次。
归一化
计算距离时，如果某些特征（指标）值比较大，会使得其他特征的贡献变得忽略不急，此时除了使用不同权重外，还可以进行归一化，例如对于欧式距离
显然最后一个维度的距离产生的贡献使得前两个维度的贡献约等于0。设最后维度取值范围是，则将数据300归一化后变为
优缺点
优点：简单，无须训练
缺点：
惰性算法（lazy）
计算量大，内存开销大。
必须指定k值，k值选择不当分类精度不能保证。