K Nearest Neighbor算法

顾名思义通过最近的邻居们判断目标的属性。

算法思想

选取目标距离最近的k个节点，通过统计他们类型，选取最多数量的类型作为目标判断。
TODO kNN支持

实现细节

1. 保存k、点的集合、分类的集合；
2. 输入目标点，遍历上面的集合计算距离，得到距离集合；
3. 对距离集合排序，获取nearest k个的索引；
4. 依据索引，统计neighbor的分类；
5. 根据统计结果，得到目标点的分类。

可以使用kd树进行优化（类似二分的思想，减少运算量）

实际运用

scikit-learn库，Nearest Neighbors

优缺点

• 优点
  简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；可用于数值型数据和离散型数据；训练时间复杂度为O(n)；无数据输入假定；对异常值不敏感。

• 缺点：
  计算复杂性高；空间复杂性高；样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分。最大的缺点是无法给出数据的内在含义。

思考

1. 距离计算，一般欧式距离，为什么不是曼哈顿？
   欧式距离相同，曼哈顿距离不一定相同，违反现实中“距离”概念
   image.png
2. k选取策略
   过小噪音更高，过大模型太简单不适用。一般将标记好的数据，一部分做训练资料，一部分做参数计算，最后统计正确率。
3. 算法复杂度
   O(nd)，n训练点数，d维度
4. 特征归一化
   降低维度特征的偏向

参考资料

一文搞懂k近邻（k-NN）算法（一）
一文搞懂k近邻（k-NN）算法（二）
kd 树算法之详细篇