**本节内容：**
[TOC]
## 0.分类算法
| 算法种类 | KNN | 朴素贝叶斯 | 决策树 | 支持向量机 | 神经网络 |
| --- | --- | --- | --- | --- | --- |
| 优点 | 1.简单易用<br/>2.模型训练时间短<br/>3.预测效果好<br/>4.对异常值不敏感<br/>5.无数据输入假定 | 1.接收大量数据训练和查询时所具备的高速度，支持增量式训练<br/>2.对分类器实际学习的解释相对简单 | 1.很容易解释一个受训模型，算法将最为重要的判断因素都很好的安排在了靠近树的根部位置<br/>2.能够同时处理分类数据和数值数据<br/>3.很容易处理变量之间的相互影响<br/>4.适合小规模数据 | 1.通过将分类输入转化为数值输入，可以令支持向量同时支持分类数据和数值数据<br/>2.适合大规模数据 | 1.能够处理复杂的非线性函数，并且能发现不同输入间的依赖关系<br/>2.支持增量式训练 |
| 缺点 | 1.对内存要求较高<br/>2.预测阶段可能很慢<br/>3.对不相关的功能和数据规模敏感<br/>4.计算复杂度搞、空间复杂度高 | 1.无法处理基于特征组合所产生的变化结果 | 1.不擅长对数值数据进行预测<br/>2.不支持增量式训练 | 1.针对每个数据集的最佳核变函数及其相应的参数都是不一样的，而且每当遇到新的数据集都必须重新确定这些函数及其参数<br/>2.黑盒技术，由于存在高维空间的变换，SVM的分类过程更加难以解释 | 1.黑盒方法，无法确定推导过程<br/>2.选择训练数据的比率与问题相适应的网络规模方面，没有明确的规则可以遵循（选择过高的训练数据比率有可能导致网络对噪声数据产生过度归纳的现象，而选择过低的训练比率，则意味着除了已知数据，网络有可能不会再进一步学习了） |
## 1.KNN算法概述
* KNN是最简单的分类算法之一，也是最常见的分类算法之一
* KNN算法是<strong style="color:red">有监督学习</strong>中的分类算法
* KNN算法和<strong style="color:red">无监督学习算法K-means</strong>有些相像，但是却有本质区别
* 使用数据范围：<strong style="color:red">数值型和标称型</strong>
* 通常K是不大于20的整数
## 2.KNN算法介绍
KNN全称为 K Nearest Neighbors，意思是K个最近的邻居。从名字可知，K的取值是至关重要的。
KNN原理：当预测一个新的值x的时候，根据它距离最近的K个点是什么类别来判断x属于哪个类别。
<strong style="color:green">【敲黑板，划重点】</strong>
如图，绿色的点是我们要预测的那个点。
假设K=3，那么KNN算法就会找到与它（绿色）距离最近的三个点（为了方便查看，此处用虚线圆圈圈出来），看看哪种类别多一些，比如这个例子中是蓝色三角形多一些，所以绿色的点就被归类为蓝色三角形。
但是，当K=5时，判断结果就不一样了。
这次，圈内的红色圆更多一些，所以绿色的点就被归类为红色圆。
综上，我们知道，KNN算法中，K的取值是至关重要的。那我们该如何去选取K值，又如何计算点之间的距离呢？
### 2.1 距离计算
度量空间中点的距离，有几种常见的度量方式：
* 曼哈顿距离计算
* 欧氏距离计算
通常情况下，KNN算法种所使用的是欧式距离：
推演到多维空间，则公式变成：
有两个元素A和B，每个元素拥有n维属性，
A (x1, x2, x3, ..., xn)
B (y1, y2, y3, ..., yn)
则距离公式变为：
此时，我们知道了如何计算元素间距离。
而KNN算法的最简单粗暴的方式，就是将所有点距离进行计算，然后保存并排序，然后筛选前面K个值看看哪些类别比较多，说白了，也就是个top K的问题。
但是，通常我们也会接触一些数据结构来辅助获取top K，比如最大堆（有兴趣可以自行百度：[https://blog.csdn.net/cdnight/article/details/11650983](https://blog.csdn.net/cdnight/article/details/11650983)）
### 2.2 K值选择
K值的选择是直接影响到我们分类结果的，那么该如何去确定K值呢？
此时，我们就会采用<strong style="color:red">交叉验证</strong>（将样本数据按照一定比例，拆分出训练集和验证集，比如6：4比例），然后从选取一个较小的K值开始，不断增加K的值，然后计算验证集合的方差，最终找到一个比较合适的K值。
通常，通过交叉验证计算方差后，你会得到大致类似于下图：
* 当你增大K的时候，一般错误率会先降低，因为有周围更多的样本可以借鉴了，分类效果会变好；
* 和K-means不一样，当K值更大的时候，KNN错误率会更好
* 比如说你一共就35个样本，当你K增大到30的时候，KNN基本就没意义了。
所以选择K值的时候可以选择一个较大的临界K值，当它继续增大或者减小的时候，错误率都会上升。如图中的K=10
### 2.3特征归一化的必要性
首先举例如下，我用一个人身高(cm)与脚码（尺码）大小来作为特征值，类别为男性或者女性。我们现在如果有5个训练样本，分布如下：
A \[(179,42),男\]
B \[(178,43),男\]
C \[(165,36)女\]
D \[(177,42),男\]
E \[(160,35),女\]
通过上述训练样本，我们看出问题了吗？
很容易看到第一维身高特征是第二维脚码特征的4倍左右，那么在进行距离度量的时候，<strong style="color:red;">我们就会偏向于第一维特征。</strong>这样造成俩个特征并不是等价重要的，最终可能会导致距离计算错误，从而导致预测错误。
<br/>
口说无凭，举例如下：
现在我来了一个测试样本 F(167,43)，让我们来预测他是男性还是女性，我们采取k=3来预测。
下面我们用欧式距离分别算出F离训练样本的欧式距离，然后选取最近的3个，多数类别就是我们最终的结果，计算如下：
由计算可以得到，最近的前三个分别是C,D,E三个样本，那么由C,E为女性，D为男性，女性多于男性得到我们要预测的结果为**女性**。
<strong style="color:green">Q：</strong>这样问题就来了，一个女性的脚43码的可能性，远远小于男性脚43码的可能性，那么为什么算法还是会预测F为女性呢？
<strong style="color:green">A：</strong>那是因为由于各个特征量纲的不同，在这里导致了身高的重要性已经远远大于脚码了，这是不客观的。所以我们应该让每个特征都是同等重要的！这也是我们要归一化的原因！
<strong style="color:red;">归一化公式如下：</strong>
## 3.KNN特点
<strong style="color:green">KNN是一种非参、惰性的算法模型。</strong>
* 非参
* 并不是说该模型不需要参数，而是意味着这个模型不会对数据做出任何的假设，与之相对应的是线性回归（我们总会先假设线性回归是一条直线）。
* 也就是说KNN建立的模型结构是根据数据来决定的，这也比较符合现实的情况，毕竟在现实中的情况往往与理论上的假设是不相符的。
* 惰性
* 逻辑回归需要先对数据进行大量训练，最后才会得到一个算法模型。
* KNN算法却不需要，它没有明确的训练数据的过程，或者说这个过程很快。
## 4.优点 & 缺点？？？
### 4.1优点：
1. 简单易用，相比其他算法，KNN算是比较简洁明了的算法。即使没有很高的数学基础也能搞清楚它的原理
2. 模型训练时间快（KNN算法是惰性的）
3. 预测效果好
4. 对异常值不敏感
### 4.2缺点：
1. 对内存要求较高，因为该算法存储了所有训练数据
2. 预测阶段可能很慢
3. 对不相关的功能和数据规模敏感
## 5.何时选择KNN算法？？？
从sklearn给出的图来解释：
## 6.sklearn KNN参数介绍
`
def KNeighborsClassifier(n_neighbors = 5, weights='uniform', algorithm = '', leaf_size = '30', p = 2, metric = 'minkowski', metric_params = None, n_jobs = None )
`
* n_neighbors：KNN的K值
* weights：最普遍的KNN算法无论距离如何，权重都一样，但有时我们想要特殊化一下数据，比如距离近的点，权重设置更高一些
* 'uniform'：不管远近权重都一样，就是最普通的KNN算法形式
* 'distance'：权重和距离成反比，距离预测目标越近拥有越高的权重
* algorithm：在 sklearn 中，要构建 KNN 模型有三种构建方式。暴力法适合数据量较小的方式，否则效率会比较低。如果数据量比较大一般会选择 KD 树构建 KNN 模型，而当 KD树也比较慢的时候，则可以试试球树来构建 KNN 。依次递进关系：<strong style="color:red">暴力法 -> KD树 -> 球树</strong>
* 'brute'：蛮力实现（暴力法），直接计算距离存储比较的方式
* 'kd_tree'：采用 kd 树构建 KNN 模型
* 'ball_tree'：采用球树构建
* 'auto'：默认参数，自动选择合适的方法构建模型
不过，当数据量较小或者比较稀疏时，无论选择哪个最后都会使用 'brute'
* leaf_size：如果是选择蛮力实现，则该值可以忽略，当时用KD树或者球树，该值是停止建子树的叶子节点数量的阈值，默认30，但如果数据量增多这个参数需要增大，否则速度过慢不说，还容易过拟合。
* <strong style="color:red">p：和metric结合使用，当metric参数是 "minkowski"的时候，p=1为曼哈顿距离，p=2为欧式距离。默认p=2</strong>
* <strong style="color:red">metric：指定距离度量方法，一般都是使用欧式距离。</strong>
* 'euclidean'：欧式距离
* 'manhattan'：曼哈顿距离
* 'chebyshev'：切比雪夫距离
* 'minkowski'：闵可夫斯基距离，默认参数
* n_jobs：指定多少个CPU进行运算，默认是-1，即全部都运算。
## 7.KNN代码示例
我们直接采用sklearn自带的鸢尾花数据集进行KNN分类：
### 7.1 交叉验证确定K值
```python
from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier
#读取鸢尾花数据集
iris = load_iris()
x = iris.data
y = iris.target
k_range = range(1, 31)
k_error = []
#循环，取k=1到k=31，查看误差效果
for k in k_range:
knn = KNeighborsClassifier(n_neighbors=k)
#cv参数决定数据集划分比例，这里是按照5:1划分训练集和测试集
scores = cross_val_score(knn, x, y, cv=6, scoring='accuracy')
k_error.append(1 - scores.mean())
#画图，x轴为k值，y值为误差值
plt.plot(k_range, k_error)
plt.xlabel('Value of K for KNN')
plt.ylabel('Error')
plt.show()
```
运行结果如下：
从图中，我们可以明显看出K值取多少时误差最小，即K=11。
在实际问题中，如果数据集比较大，那为减少训练时间，K的取值范围可以缩小。
### 7.2 模型预测
```python
import matplotlib.pyplot as plt
from numpy import *
from matplotlib.colors import ListedColormap
from sklearn import neighbors, datasets
n_neighbors = 11
# 导入一些要鸢尾花数据
iris = datasets.load_iris()
# 我们只采用前两个feature,方便画图在二维平面显示
x = iris.data[:, :2]
y = iris.target
# 网格中的步长
h = .02
# 创建彩色的图
cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])
#weights是KNN模型中的一个参数，上述参数介绍中有介绍，这里绘制两种权重参数下KNN的效果图
for weights in ['uniform', 'distance']:
# 创建了一个knn分类器的实例，并拟合数据。
clf = neighbors.KNeighborsClassifier(n_neighbors, weights=weights)
clf.fit(x, y)
# 绘制决策边界。为此，我们将为每个分配一个颜色
# 来绘制网格中的点 [x_min, x_max]x[y_min, y_max].
x_min, x_max = x[:, 0].min() - 1, x[:, 0].max() + 1
y_min, y_max = x[:, 1].min() - 1, x[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
np.arange(y_min, y_max, h))
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
# 将结果放入一个彩色图中
Z = Z.reshape(xx.shape)
plt.figure()
plt.pcolormesh(xx, yy, Z, cmap=cmap_light)
# 绘制训练点
plt.scatter(x[:, 0], x[:, 1], c=y, cmap=cmap_bold)
plt.xlim(xx.min(), xx.max())
plt.ylim(yy.min(), yy.max())
plt.title("3-Class classification (k = %i, weights = '%s')"
% (n_neighbors, weights))
plt.show()
```
结果如图所示：
## 8.KNN与K-means异同？？？
* 相同点：
* K值都是重点
* 都需要计算平面中点的距离（核心都是通过计算空间中点的距离来实现目的）
* 不同点：
* 目的不同：
* KNN最终目的是分类
* K-means目的是给所有距离相近的点分配一个类别，也就是聚类
<strong style="color:green">【敲黑板，划重点】</strong>
就是画一个圈，
<strong style="color:red">KNN是让进来圈子的人变成自己人，</strong>
<strong style="color:red">K-means是让原本在圈内的人归成一类人。</strong>
## 9.KNN（k-近邻）算法的一般流程
（1）收集数据：可以使用任何方法。
（2）准备数据：距离计算所需要的的数值，最好是结构化的数据格式。
（3）分析数据：可以使用任何方法。
（4）训练算法：此步骤不适用k-近邻算法。
（5）测试算法：计算错误率。
（6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。
## 参考文献
* [一文搞懂k近邻（k-NN）算法](https://zhuanlan.zhihu.com/p/26029567)
* [《Machine Learning in Action》 美.Perter Harrington著](http://www.java1234.com/a/javabook/javabase/2018/0618/11382.html?__cf_chl_jschl_tk__=1a9fd8cd05c65e779bf06b71c939ce301af6ba6f-1612414161-0-AS1KkYGWerV7qo3F4MC63eSztes9afmW8sVm1pUj0AA3CXfq5v_PHxGsg6jMvWKM9W4mfnJSCtYBsDQCjdTCBGKfDYhHQLuGBoCBxtLUvJVspQh1LAh0Vt-3fESV6P7AnGZLz1cm4bmFVXSAUPq75GxsqqySPmykRUQ2OEG9Xl3cleceh0Errob0UWroT0YJOQMNV_d7N7EeAvfH8DqesOBHzr_ju1v-skh5JI-kku4QIhpOqxJdgT3PYbnKYjukuJq3axyb7MaX_KaIB3oHk2nRzr8h7cdtUCqQKo7XTx1KSDfYMd60S-jZnK_l363Au8zU9k9N4dXKtNrOiME1no8ElxNb1pzF7G72Gk5ceuze)
