机器学习——KNN（K近邻）_机器学习knn

一、机器学习种类

1.1 有监督学习 与 无监督学习

• （1）无监督学习是在寻找数据集中的规律性，这种规律性并不一定要达到划分数据集的目的，也就是说不一定要“分类”。
  这一点是比有监督学习方法的用途要广。譬如分析一堆数据的主分量，或分析数据集有什么特点都可以归于
  非监督学习方法的范畴。

• （2）用非监督学习方法分析数据集的主分量与用K-L变换计算数据集的主分量又有区别。后者从方法上讲不是学习方法。
  因此用K-L变换找主分量不属于无监督学习方法，即方法上不是。而通过学习逐渐找到规律性这体现了学习方法这一点。
  在人工神经元网络中寻找主分量的方法属于无监督学习方法。

1.2 监督学习 与 强化学习

二、K近邻（KNN）K Nearest Neighbors

2.1 什么是K近邻

思想：只要知道你朋友（邻居）是什么人，就能知道你是什么人
K近邻是一种 懒惰的学习方法：（基于实例学习）

Lazy learners（懒惰学习）： instance-based learning

新数据来时，才开始学习给出分类

2.2 K近邻的距离度量公式

距离（distance）–衡量样本之间的相相识度

1. 欧式距离（平面几何之间的距离）
2. 曼哈顿距离（两点之间X的距离+Y的距离：类似楼梯铺红毯，红毯的长度）

通用距离公式 ( 闵可夫斯基距离 )
$$D(X,Y)=\sqrt[p]{\sum _{i=1}^n|X_i-Y_i{|}^p}$$
当 $p=1$ 为曼哈顿距离：$D(X,Y)={\sum }_{i=1}^n|X_i-Y_i|$
当 $p=2$ 为欧式距离：$D(X,Y)=\sqrt[]{{\sum }_{i=1}^n(X_i-Y_i{)}^2}$

---

2.3 K值选择–近似误差（训练集误差）与 估计误差（测试集误差）

近似误差

对现有训练集的训练误差，关注训练集，如果近似误差过小可能会出现过拟合的现象，
对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较大偏差的预测。
模型本身不是最接近最佳模型

估计误差

可以理解为对测试集的测试误差，关注测试集，估计误差小说明对未知数据的预测能力好，模型本身最接近最佳模型。

K值确定标准：

K值过小：特征空间被划分为更多子空间（模型的项越多），整体模型变复杂，容易过拟合，
选择的范围就比较小，训练的时候命中率较高，近似误差小，
用 test_dataset 测试时的时候就容易出错，估计误差大，容易过拟合。

K值=N： 无论输入实例是什么，都将简单的预测他属于训练实例中最多的类

k值较大，就相当于用较大领域中的训练实例进行预测，泛化误差小（方差小），但缺点是近似误差大（偏差大），换句话说，K值较大就意味着整体模型变得简单，容易发生欠拟合；一个极端是k等于样本数m，则完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。

K近邻算法基本流程

开始
指定K值
计算输入样本与训练样本之间的距离
按距离排序
筛选K个最近邻居
投票判断分类
结束

---

2.4 kd-tree （k-dimensional树）

原理：一种分割k维数据空间的数据结构。应用于多维空间关键数据搜索（如：范围和最近邻搜索）。
kd树是是一种二叉树，表示对k维空间的一个划分，构造kd树相当于不断地用垂直于坐标轴的超平面
将K维空间切分，构成一系列的K维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

2.5 构造方法

1. 构造根结点，使根结点对应于K维空间中包含所有实例点的超矩形区域；

2. 通过递归的方法，不断地对k维空间进行切分，生成子结点。在超矩形区域上选择一个坐标轴和
   在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，
   将当前超矩形区域切分为左右两个子区域（子结点）；这时，实例被分到两个子区域

3. 上述过程直到子区域内没有实例时终止（终止时的结点为叶结点）。在此过程中，将实例保存在相应的结点上。

4. 通常，循环的选择坐标轴对空间切分，选择训练实例点在坐标轴上的中位数为切分点，
   这样得到的kd树是平衡的（平衡二叉树：它是一棵空树，或其左子树和右子树的深度之差的绝对值不超过1，且它的左子树和右子树都是平衡二叉树）。

注意：平衡的kd树搜索时的效率未必是最低的。特殊情况有时在稀疏点切

2.6 K近邻算法代码

在scikit-learn 中，K近邻类库sklearn.neighbors: 【代码演示】

• KNN 分类树 的类 KNeighborsClassifier
  KNN 回归树 的类 KNeighborsRegressor

• KNN的扩展类
  限定半径最近邻分类树的类RadiusNeighborsClassifier
  限定半径最近邻回归树的类RadiusNeighborsRegressor
  最近质心分类算法NearestCentroid。

在这些算法中，KNN分类和回归的类参数完全一样。具体参数如下：

sklearn.neighbors.KNeighborsClassifier(
　　　　n_neighbors=5,
　　　　weights=’uniform’,
　　　　algorithm=’auto’,
　　　　leaf_size=30,
　　　　p=2,
　　　　metric=’minkowski’,
　　　　metric_params=None,
　　　　n_jobs=None,
　　　　**kwargs
　　　　)

• n_neighbors：KNN中的k值，默认为5（对于k值的选择，前面已经给出解释）；

• weights：用于标识每个样本的近邻样本的权重，可选择"uniform",“distance” 或自定义权重。默认 “uniform”，所有最近邻样本权重都一样。如果是 “distance”，则权重和距离成反比例；如果样本的分布是比较成簇的，即各类样本都在相对分开的簇中时，我们用默认的"uniform"就可以了，如果样本的分布比较乱，规律不好寻找，选择"distance"是一个比较好的选择；

• algorithm：限定半径最近邻法使用的算法，可选‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’。

  • ‘brute’对应第一种线性扫描；
  • ‘kd_tree’对应第二种kd树实现；
  • ‘ball_tree’对应第三种的球树实现；
  • ‘auto’则会在上面三种算法中做权衡，选择一个拟合最好的最优算法。

• leaf_size：这个值控制了使用kd树或者球树时， 停止建子树的叶子节点数量的阈值。这个值越小，则生成的kc树或者球树就越大，层数越深，建树时间越长，反之，则生成的kd树或者球树会小，层数较浅，建树时间较短。默认是30。
  这个值一般依赖于样本的数量，随着样本数量的增加，这个值必须要增加，否则不光建树预测的时间长，还容易过拟合。可以通过交叉验证来选择一个适中的值。当然，如果使用的算法是蛮力实现，则这个参数可以忽略；

• metric，p：距离度量（前面介绍过），默认闵可夫斯基距离 “minkowski”（p=1为曼哈顿距离， p=2为欧式距离）；

• metric_params：距离度量其他附属参数（具体我也不知道，一般用得少）；

• n_jobs：并行处理任务数，主要用于多核CPU时的并行处理，加快建立KNN树和预测搜索的速度。n_jobs= -1，即所有的CPU核都参与计算。

限定半径最近邻法分类和回归的类的主要参数也和KNN基本一样。具体参数如下：

sklearn.neighbors.RadiusNeighborsClassifier(
　　　　radius=1.0,
　　　　weights=’uniform’,
　　　　algorithm=’auto’,
　　　　 leaf_size=30,
　　　　 p=2,
　　　　 metric=’minkowski’,
　　　　 outlier_label=None,
　　　　metric_params=None,
　　　　n_jobs=None,
　　　　**kwargs
　　　　)

• radius：限定半径，默认为1。半径的选择与样本分布有关，可以通过交叉验证来选择一个较小的半径，尽量保证每类训练样本其他类别样本的距离较远；
• outlier_labe：int类型，主要用于预测时，如果目标点半径内没有任何训练集的样本点时，应该标记的类别，不建议选择默认值 None,因为这样遇到异常点会报错。一般设置为训练集里最多样本的类别。

2.7 K近邻模型优化-- K值

K过小（理论最小=1）也就是邻居数为1，会受到噪声数据影响，降低分类精度
K过大（理论=训练样本数）会受到不相关数据影响，降低分类精度
使用交叉验证寻找最好的K值
经验值 k = sqr(n)/2, n时训练样本数
用强大的 Gridsearch（网格搜索）寻找最优参数

parameters = {
　　　　‘n_neighbors’:[5,10,15,20,30],
　　　　‘weights’:[‘uniform’,‘distance’],
　　　　‘p’:[1,2]
　　　　}
　　　　
knn = KNeighborsClassifier()
grid_search = GridSearchCV(lnn,parameters,scoring = ‘accuracy’,cv = 5)
grid_search.fit(x,y)

参考：
https://www.cnblogs.com/pinard/p/6061661.html