K Nearest Neighbor算法
2020-02-29 本文已影响0人
老姚记事本
顾名思义通过最近的邻居们判断目标的属性。
算法思想
选取目标距离最近的k个节点，通过统计他们类型，选取最多数量的类型作为目标判断。
TODO kNN支持
实现细节
- 保存k、点的集合、分类的集合；
- 输入目标点，遍历上面的集合计算距离，得到距离集合；
- 对距离集合排序，获取nearest k个的索引；
- 依据索引，统计neighbor的分类；
- 根据统计结果，得到目标点的分类。
可以使用kd树进行优化（类似二分的思想，减少运算量）
实际运用
scikit-learn库，Nearest Neighbors
优缺点
-
优点
简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；可用于数值型数据和离散型数据；训练时间复杂度为O(n)；无数据输入假定；对异常值不敏感。 -
缺点：
计算复杂性高；空间复杂性高；样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分。最大的缺点是无法给出数据的内在含义。
思考
-
距离计算，一般欧式距离，为什么不是曼哈顿？
欧式距离相同，曼哈顿距离不一定相同，违反现实中“距离”概念
image.png
-
k选取策略
过小噪音更高，过大模型太简单不适用。一般将标记好的数据，一部分做训练资料，一部分做参数计算，最后统计正确率。 - 算法复杂度
O(nd)，n训练点数，d维度 -
特征归一化
降低维度特征的偏向
