KNN针对的是分类问题

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

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

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

界说

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

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

核心思维

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

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

间隔核算

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

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

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

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 值。经过穿插验证核算方差后你大致会得到下面这样的图

这个图其实很好理解，当你增大 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 鸢尾花

鸢尾花数据集主要包含了鸢尾花的花萼长度、花萼宽度、花瓣长度、花瓣宽度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 算法却不需求，它没有明确的练习数据的进程，或许说这个进程很快。

算法优缺陷

长处

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

缺陷

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

机器学习笔记——KNN算法

KNN针对的是分类问题

界说

核心思维

间隔核算

K值挑选

算法完成

Sklearn KNN参数概述

KNN代码示例

Sklearn 鸢尾花

算法特色

算法优缺陷

长处

缺陷

作者信息

机器学习笔记——KNN算法

KNN针对的是分类问题

界说

核心思维

间隔核算

K值挑选

算法完成

Sklearn KNN参数概述

KNN代码示例

Sklearn 鸢尾花

算法特色

算法优缺陷

长处

缺陷

相关文章

【面试】数据结构与算法(十三)

Redis缓存方案设计

深度学习数学基础-概率与信息论

iOS17适配指南之SwiftData(二)

作者信息