机器学习: KNN

2019-02-23 本文已影响25人写代码的海怪

KNN (K Nearest Neighbor) 是比较常见的种监督算法。它的主要思想是看这个数据距离最近的 K 个节点中，这些节点哪个类占最多，那么这个数据就属于哪个类，算是比较容易理解的算法。

问题描述

给定如下数据集

如何判定目标数据是属于哪个类，0 或者 1。

就像前面所说的要看最近的 K 个节点的各类，所以现在的问题转变成求该点的最近 K 个点。求距离使用的就是 Euclidean Distance，也就是求两点间距离公式。

$d(x, x^\prime) = \sqrt{\sum_{i=0}^k{{(x_i-x_i^ \prime)}^2}}$

是不是这样求就收工了呢？嗯。。。差不多是的，不过这里最好还要加一个权重，因为有些特征值比较重要，所以不能真的像求距离那样，还要对特征值给个优先级。

$d(x, x^\prime) = \sqrt{\sum_{i=0}^k{w^i{(x_i-x_i^ \prime)}^2}}$

图示如下

如果 K 很小会出现过拟合问题，因为这时候每个点只看最靠近自己的那个点，所以对于训练数据来做预测是 100% 正确的，但是用测试数据做预测错误就会很多。

而如果 K 太大（甚至等于数据集本身），那么就会欠拟合，边界变得十分“平滑”。