k近邻法（K-Nearest Neighbor）

KNN 的工作原理

  • 计算待分类物体与其他物体之间的距离；
  • 统计距离最近的 K 个邻居；
  • 对于 K 个最近的邻居，它们属于哪个分类最多，待分类物体就属于哪一类。

K值如何选择

  • 如果 K 值比较小，就相当于未分类物体与它的邻居非常接近才行。分类就会产生过拟合。

  • 如果 K 值比较大，相当于距离过远的点也会对未知物体的分类产生影响，分类产生欠拟合情况.

鲁棒性:在异常和危险情况下系统生存的能力

在工程上，我们一般采用交叉验证的方式选取 K 值。

交叉验证的思路就是，把样本集中的大部分样本作为训练集，剩余的小部分样本用于预测，来验证分类模型的准确性。所以在 KNN 算法中，我们一般会把 K 值选取在较小的范围内，同时在验证集上准确率最高的那一个最终确定作为 K 值。

距离的计算：

  • 欧氏距离；
  • 曼哈顿距离；
  • 闵可夫斯基距离；
  • 切比雪夫距离；

K D 树

KNN 的计算过程是大量计算样本点之间的距离。

  • 为了减少计算距离次数
  • 提升 KNN 的搜索效率

KD 树（K-Dimensional ）

  • 对数据点在 K 维空间中划分的一种数据结构。
  • 在 KD 树的构造中，每个节点都是 k 维数值点的二叉树。
  • 既然是二叉树，就可以采用二叉树的增删改查操作，这样就大大提升了搜索效率。

sklearn实现

KNN 既可以做分类器，也可以做回归。

  • 做分类，你需要引用：from sklearn.neighbors import KNeighborsClassifier
  • 做回归，你需要引用：from sklearn.neighbors import KNeighborsRegressor
  1. KNeighborsClassifier(n_neighbors=5, weights=‘uniform’, algorithm=‘auto’, leaf_size=30)

1.n_neighbors：即 KNN 中的 K 值，代表的是邻居的数量。K 值如果比较小，会造成过拟合。如果 K 值比较大，无法将未知物体分类出来。一般我们使用默认值 5。

2.weights：是用来确定邻居的权重，有三种方式：weights=uniform，代表所有邻居的权重相同；weights=distance，代表权重是距离的倒数，即与距离成反比；自定义函数，你可以自定义不同距离所对应的权重。大部分情况下不需要自己定义函数。

3.algorithm：用来规定计算邻居的方法，它有四种方式：algorithm=auto，根据数据的情况自动选择适合的算法，默认情况选择 auto；

  • algorithm=kd_tree，也叫作 KD 树，是多维空间的数据结构，方便对关键数据进行检索，不过 KD 树适用于维度少的情况，一般维数不超过 20，如果维数大于 20 之后，效率反而会下降；
  • algorithm=ball_tree，也叫作球树，它和 KD 树一样都是多维空间的数据结果，不同于 KD 树，球树更适用于维度大的情况；
  • algorithm=brute，也叫作暴力搜索，它和 KD 树不同的地方是在于采用的是线性扫描，而不是通过构造树结构进行快速检索。当训练集大的时候，效率很低。

4.leaf_size：代表构造 KD 树或球树时的叶子数，默认是 30，调整 leaf_size 会影响到树的构造和搜索速度。