KNN针对的是分类问题

KNN针对分类问题，经过改变决议计划规矩也可用于回归问题。

分类猜测规矩：一般选用多数表决法或许加权多数表决法

回归猜测规矩：一般选用平均值法或许加权平均值法

界说

K Nearest Neighbor算法，假如一个样本在特征空间中的k个最近似（即特征空间中最附近）的样本中的大多数归于某一个类别，则该样本也归于这个类别。

留意：KNN 算法是有监督学习中的分类算法，留意与K-means算法区别
K-means为无监督学习算法，二者有本质区别，一个是分类，一个是聚类。

核心思维

KNN 的全称是 K Nearest Neighbors，意思是 K 个最近的街坊。 KNN 的原理就是当猜测一个新的值 x 的时分，依据它间隔最近的 K 个点是什么类别来判断 x 归于哪个类别。

以下图为例，绿色点为要猜测的点，不同的K取值将产生不同的成果。

机器学习笔记——KNN算法

机器学习笔记——KNN算法

间隔核算

要衡量空间中点间隔的话，有好几种衡量办法，比方常见的曼哈顿间隔核算、欧式间隔核算等等。不过通常 KNN 算法中运用的是欧式间隔。这儿仅仅简略说一下，拿二维平面为例，二维空间两个点的欧式间隔核算公式如下：

=(x2−x1)2+(y2−y1)2\rho = \sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}

拓展到多维空间，则公式变成

d(x,y):=(x1−y1)2+(x2−y2)2+⋯+(xn−yn)2=∑i=1n(xi−yi)2.d(x, y):=\sqrt{\left(x_{1}-y_{1}\right)^{2}+\left(x_{2}-y_{2}\right)^{2}+\cdots+\left(x_{n}-y_{n}\right)^{2}}=\sqrt{\sum_{i=1}^{n}\left(x_{i}-y_{i}\right)^{2}} .

KNN 算法最简略粗暴的就是将猜测点与一切点间隔进行核算，然后保存并排序，选出前面 K 个值看看哪些类别比较多。但其实也能够经过一些数据结构来辅助，比方最大堆，这儿就不多做介绍，有兴趣能够百度最大堆相关数据结构的常识。

K值挑选

  • 对于K值的挑选，一般依据样本散布挑选一个较小的值，然后经过穿插验证来挑选一个比较合适的终究值；
  • 当挑选比较小的K值的时分，表示运用较小领域中的样本进行猜测，练习差错会减小，可是会导致模型变得复杂，简略导致过拟合；
  • 当挑选较大的K值的时分，表示运用较大领域中的样本进行猜测，练习差错会增大，一起会使模型变得简略，简略导致欠拟合；

穿插验证（将样本数据依照一定份额，拆分出练习用的数据和验证用的数据，比方6：4拆分出部分练习数据和验证数据），从选取一个较小的 K 值开端，不断增加 K 的值，然后核算验证集合的方差，终究找到一个比较合适的 K 值。经过穿插验证核算方差后你大致会得到下面这样的图

机器学习笔记——KNN算法

这个图其实很好理解，当你增大 K 的时分，一般错误率会先下降，由于有周围更多的样本能够学习了，分类作用会变好。但留意，和 K-means 不相同，当 K 值更大的时分，错误率会更高。这也很好理解，比方说你总共就35个样本，当你 K 增大到30的时分，KNN 基本上就没含义了。

所以挑选 K 点的时分能够挑选一个较大的临界 K 点，当它持续增大或减小的时分，错误率都会上升，比方图中的 K=10。

算法完成

Sklearn KNN参数概述

要运用 Sklearn KNN 算法进行分类，咱们需求先了解 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”了。前面提到过，经过调整 K 值，算法会有不同的作用。

  • weights（权重）：最普遍的 KNN 算法不论间隔怎么，权重都相同，但有时分咱们想搞点特殊化，比方间隔更近的点让它愈加重要。这时分就需求 weight 这个参数了，这个参数有三个可选参数的值，决议了怎么分配权重。参数选项如下：

      * ‘uniform’：不论远近权重都相同，就是最普通的 KNN 算法的方式。
  * ‘distance’：权重和间隔成反比，间隔猜测方针越近具有越高的权重。
  * 自界说函数：自界说一个函数，依据输入的坐标值回来对应的权重，达到自界说权重的意图。

  • algorithm：在 Sklearn 中，要构建 KNN 模型有三种构建办法：

    1. 暴力法，就是直接核算间隔存储比较的那种办法。
    2. 运用 Kd 树构建 KNN 模型。
    3. 运用球树构建。

    其间暴力法适合数据较小的办法，不然效率会比较低。假如数据量比较大一般会挑选用 Kd 树构建 KNN 模型，而当 Kd 树也比较慢的时分，则能够试试球树来构建 KNN。参数选项如下：

      * ‘brute’ ：蛮力完成。
  * ‘kd_tree’：KD 树完成 KNN。
  * ‘ball_tree’：球树完成 KNN。
  * ‘auto’： 默许参数，主动挑选合适的办法构建模型。

    不过当数据较小或比较稀少时，不论挑选哪个最终都会运用 ‘brute’。

  • leaf_size：假如是挑选蛮力完成，那么这个值是能够疏忽的。当运用 Kd 树或球树，它就是停止建子树的叶子节点数量的阈值。默许30，但假如数据量增多这个参数需求增大，不然速度过慢不说，还简略过拟合。

  • p：和 metric 结合运用，当 metric 参数是 “minkowski” 的时分，p=1 为曼哈顿间隔， p=2 为欧式间隔。默许为p=2。

  • metric：指定间隔衡量办法，一般都是运用欧式间隔。

     * ‘euclidean’ ：欧式间隔。
 * ‘manhattan’：曼哈顿间隔。
 * ‘chebyshev’：切比雪夫间隔。
 * ‘minkowski’： 闵可夫斯基间隔，默许参数。

  • n_jobs：指定多少个CPU进行运算，默许是-1，也就是全部都算。

KNN代码示例

Sklearn 鸢尾花

机器学习笔记——KNN算法

鸢尾花数据集主要包含了鸢尾花的花萼长度、花萼宽度、花瓣长度、花瓣宽度4个特色（特征），以及鸢尾花卉归于『Setosa、Versicolour、Virginica』三个品种中的哪一类。

在运用 KNN 算法之前，咱们要先决议 K 的值是多少。要选出最优的 K 值，能够运用 Sklearn 中的穿插验证办法，代码如下

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 的取值范围能够缩小。

有了 K 值能运行 KNN 算法了，具体代码如下

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()
x = iris.data[:, :2]  # 咱们只选用前两个feature,便利画图在二维平面显现
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()

算法特色

KNN是一种非参的、慵懒的算法模型。

非参的意思并不是说这个算法不需求参数，而是意味着这个模型不会对数据做出任何的假定，与之相对的是线性回归（咱们总会假定线性回归是一条直线）。也就是说 KNN 建立的模型结构是依据数据来决议的，这也比较契合实际的情况，毕竟在实际中的情况往往与理论上的假定是不相符的。

慵懒又是什么意思呢？想想看，同样是分类算法，逻辑回归需求先对数据进行很多练习（tranning），最终才会得到一个算法模型。而 KNN 算法却不需求，它没有明确的练习数据的进程，或许说这个进程很快。

算法优缺陷

长处

  1. 简略易用。相比其他算法，KNN 算是比较简洁明了的算法，即使没有很高的数学根底也能搞清楚它的原理。
  2. 模型练习时刻快，上面提到 KNN 算法是慵懒的，这儿也就不再过多叙述。
  3. 猜测作用好。
  4. 对异常值不灵敏。

缺陷

  1. 对内存要求较高，由于该算法存储了一切练习数据。
  2. 猜测阶段可能很慢。
  3. 对不相关的功能和数据规划灵敏。