sklearn.neighbors.KNeighborsClassifier(n_neighbors=5)

1. K-近邻(KNN)概念

1.1 K Nearest Neighbor算法又叫KNN算法，是机器学习比较经典的算法

定义
- 如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
距离公式
- 两个样本的距离可以通过如下公式计算，又叫欧式距离，关于距离公式会在后面进行讨论

欧式距离

1.2 KNN算法流程总结

1）计算已知类别数据集中的点与当前点之间的距离

2）按距离递增次序排序

3）选取与当前点距离最小的k个点

4）统计前k个点所在的类别出现的频率

5）返回前k个点出现频率最高的类别作为当前点的预测分类

2. 距离度量

2.1 距离公式的基本性质

在机器学习过程中，对于函数dist(.,.)，若它是一”距离度量” (distance measure)，则需满足一些基本性质:

非负性： $dist(X_i,X_j)>=0$ ；
同一性： $dist(x_i,x_j)=0$ 。当且仅当 $X_i=X_j$ ；
对称性： $dist(x_i,x_j)=dist(x_j,x_i)$ ；
直递性： $dist(x_i,x_j)<=dist(x_i,x_k)+dist(x_k,x_j)$

直递性常被直接称为“三角不等式”。

2.2 常见的距离

2.2.1 欧式距离(Euclidean Distance)

欧氏距离是最容易直观理解的距离度量方法，我们小学、初中和高中接触到的两个点在空间中的距离一般都是指欧氏距离

二维平面上点 $a(x_1, y_1)$ 和 $b(x2, y_2)$ 的距离公式 $d_{12} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
三维 $a(x_1,y_1,z_1)$ 和 $b(x_2, y_2, z_2)$ 的距离公式

d_{12} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2}

n维空间上 $a(x_{11}, x_{12}, x_{13} ..., x_{1n})$ 和 $b(x_{21}, x_{22}, x_{23} ..., x_{2n})$ 的距离公式（两个n维向量）

d_{12} = \sqrt{\sum_{k=1}^n(x_{1k} - x_{2k})^2}

Python

X=[[1,1],[2,2],[3,3],[4,4]];
经计算得:
d = 1.4142    2.8284    4.2426    1.4142    2.8284    1.4142

2.2.2 曼哈顿距离(Manhattan Distance)

在曼哈顿街区要从一个十字路口开车到另一个十字路口，驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是“曼哈顿距离”。曼哈顿距离也称为“城市街区距离”(City Block distance)

曼哈顿距离

二维平面上点 $a(x_1, y_1)$ 和 $b(x2, y_2)$ 的距离公式

d_{12} = |x_1 - x_2| + |y_1 - y_2|

n维空间上 $a(x_{11}, x_{12}, x_{13} ..., x_{1n})$ 和 $b(x_{21}, x_{22}, x_{23} ..., x_{2n})$ 的距离公式（两个n维向量）

d_{12} = \sum_{k=1}^n|x_{1k} - x_{2k}|

2.2.3 切比雪夫距离 (Chebyshev Distance)

国际象棋中，国王可以直行、横行、斜行，所以国王走一步可以移动到相邻8个方格中的任意一个。国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？这个距离就叫切比雪夫距离

切比雪夫距离

二维平面上点 $a(x_1, y_1)$ 和 $b(x2, y_2)$ 的距离公式

d_{12} = max(|x_1 - x_2|, |y_1 - y_2|)

n维空间上 $a(x_{11}, x_{12}, x_{13} ..., x_{1n})$ 和 $b(x_{21}, x_{22}, x_{23} ..., x_{2n})$ 的距离公式）

d_{12} = max(|x_{1i} - x_{2i}|)

2.2.4 闵可夫斯基距离(Minkowski Distance)

闵氏距离不是一种距离，而是一组距离的定义，是对多个距离度量公式的概括性的表述。

两个n维变量 $a(x_{11},x_{12},…,x_{1n})$ 与 $b(x_{21},x_{22},…,x_{2n})$ 间的闵可夫斯基距离定义为：

d_{12} = \sqrt[p]{\sum_{k=1}^n|x_{1k} - x_{2k}|^p}

其中p是一个变参数：

当p=1时，就是曼哈顿距离；

当p=2时，就是欧氏距离；

当p→∞时，就是切比雪夫距离。

根据p的不同，闵氏距离可以表示某一类/种的距离。

3. KNN中k值的选择

K值过小：容易受到异常点的影响 K值的减小就意味着整体模型变得复杂，容易发生过拟合；
k值过大：受到样本均衡的问题输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误 K值的增大就意味着整体的模型变得简单
实际应用中，K值一般取一个比较小的数值

误差

近似误差：
- 对现有训练集的训练误差，关注训练集，
- 如果近似误差过小可能会出现过拟合的现象，对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较大偏差的预测。
- 模型本身不是最接近最佳模型。
估计误差：
- 可以理解为对测试集的测试误差，关注测试集，
- 估计误差小说明对未知数据的预测能力好，
- 模型本身最接近最佳模型。

4. sklearn中的api

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5,algorithm='auto')

n_neighbors： int,可选（默认= 5），k_neighbors查询默认使用的邻居数
algorithm：{‘auto’，‘ball_tree’，‘kd_tree’，‘brute’}
- 快速k近邻搜索算法，默认参数为auto，可以理解为算法自己决定合适的搜索算法。除此之外，用户也可以自己指定搜索算法ball_tree、kd_tree、brute方法进行搜索，
- brute是蛮力搜索，也就是线性扫描，当训练集很大时，计算非常耗时。
- kd_tree，构造kd树存储数据以便对其进行快速检索的树形数据结构，kd树也就是数据结构中的二叉树。以中值切分构造的树，每个结点是一个超矩形，在维数小于20时效率高。
- ball tree是为了克服kd树高维失效而发明的，其构造过程是以质心C和半径r分割样本空间，每个节点是一个超球体。