K近邻算法(KNN)的理论知识和代码实现【分类系列】

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

  • 前言
  • 一、分类的定义
  • 二、评价分类器性能的指标
  • 三、统计学习方法
    • 3.1 K近邻法
    • 3.2 KNN python算法实现


前言

机器学习中有三大任务:回归分析、聚类分析、分类分析,这篇文章的重点是分类(Classification)内容中KNN算法的理论和实践【预计阅读耗时6min】;


一、分类的定义

  • 分类是监督学习的一个核心问题。在监督学习中,当输出变量Y取有限个离散值时,预测问题便成为分类问题。这时,输入变量X可以是离散的,也可以是连续的。监督学习从数据中学习一个分类模型或分类决策函数,称为分类器(classifier)。分类器对新的输入进行输出的预测(prediction),称为分类(classification)。可能的输出称为类(class)。分类的类别为多个时,称为多类分类问题。本书主要讨论二类分类问题。
  • 分类问题包括学习和分类两个过程。在学习过程中,根据已知的训练数据集利用有效的学习方法学习一个分类器;在分类过程中,利用学习的分类器对新的输入实例进行分类。分类问题可用图1.4描述。图中(x1,y1),(x2,y2),…,(xN,yN)是训练数据集,学习系统由训练数据学习一个分类器P(Y|X)或Y=f(X);分类系统通过学到的分类器P(Y|X)或Y=f(X)
    对于新的输入实例xN+1进行分类,即预测其输出的类标记yN+1。
    K近邻算法(KNN)的理论知识和代码实现【分类系列】_第1张图片

二、评价分类器性能的指标

  • 评价分类器性能的指标一般是分类准确率(accuracy),其定义是:对于给定的测试数据集,分类器正确分类的样本数与总样本数之比。也就是损失函数是0-1损失时测试数据集上的准确率(见公式(1.17))。对于二类分类问题常用的评价指标是精确率(precision)与召回率(recall)。通常以关注的类为正类,其他类为负类,分类器在测试数据集上的预测或正确或不正确,4种情况出现的总数分别记作:
  • TP——将正类预测为正类数;
  • FN——将正类预测为负类数;
  • FP——将负类预测为正类数;
  • TN——将负类预测为负类数。
    K近邻算法(KNN)的理论知识和代码实现【分类系列】_第2张图片
    精确率和召回率都高时,F1值也会高。

三、统计学习方法

3.1 K近邻法

  • k近邻法(k-nearest neighbor,k-NN)是一种基本分类与回归方法本书只讨论分类问题中的k近邻法。k近邻法的输入为实例的特征向量,对应于特征空间的点;输出为实例的类别,可以取多类。k近邻法假设给定一个训练数据集,其中的实例类别已定。分类时,对新的实例,根据其k个最近邻的训练实例的类别,通过多数表决等方式进行预测。因此,k近邻法不具有显式的学习过程。k近邻法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”。

  • k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。k近邻法1968年由Cover和Hart提出。本章首先叙述k近邻算法,然后讨论k近邻法的模型及三个基本要素,最后讲述k近邻法的一个实现方法——kd树,介绍构造kd树和搜索kd树的算法。

  • K近邻算法思想:给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的k个实例,这k个实例的多数属于某个类,就把该输入实例分为这个类。

  • K近邻模型:k近邻法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素——距离度量、k值的选择和分类决策规则决定。
    k近邻法中,当训练集、距离度量(如欧氏距离)、k值及分类决策规则(如多数表决)确定后,对于任何一个新的输入实例,它所属的类唯一地确定。这相当于根据上述要素将特征空间划分为一些子空间,确定子空间里的每个点所属的类。这一事实从最近邻算法中可以看得很清楚。特征空间中,对每个训练实例点ix,距离该点比其他点更近的所有点组成一个区域,叫作单元(cell)。每个训练实例点拥有一个单元,所有训练实例点的单元构成对特征空间的一个划分。最近邻法将实例ix的类iy作为其单元中所有点的类标记(class label)。这样,每个单元的实例点的类别是确定的。图3.1是二维特征空间划分的一个例子。
    K近邻算法(KNN)的理论知识和代码实现【分类系列】_第3张图片

  • 距离度量:特征空间中两个实例点的距离是两个实例点相似程度的反映。k近邻模型的特征空间一般是n维实数向量空间Rn。使用的距离是欧氏距离,但也可以是其他距离,如更一般的Lp距离(Lp distance)或Minkowski距离(Minkowski distance)。
    K近邻算法(KNN)的理论知识和代码实现【分类系列】_第4张图片

  • K值的选择:k值的选择会对k近邻法的结果产生重大影响。如果选择较小的k值,就相当于用较小的邻域中的训练实例进行预测,“学习”的近似误差(approximation error)会减小,只有与输入实例较近的(相似的)训练实例才会对预测结果起作用。但缺点是“学习”的估计误差(estimation error)会增大,预测结果会对近邻的实例点非常敏感[2]。如果邻近的实例点恰巧是噪声,预测就会出错。换句话说,k值的减小就意味着整体模型变得复杂,容易发生过拟合。如果选择较大的k值,就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例较远的(不相似的)训练实例也会对预测起作用,使预测发生错误。k值的增大就意味着整体的模型变得简单。如果k=N,那么无论输入实例是什么,都将简单地预测它属于在训练实例中最多的类。这时,模型过于简单,完全忽略训练实例中的大量有用信息,是不可取的。在应用中,k值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。举例K值选择不同的效果如下图所示。
    K近邻算法(KNN)的理论知识和代码实现【分类系列】_第5张图片
    在两组分类中,1NN 的分类边界明显更“崎岖”,但是对历史样本没有误判;而 15NN 的分类边界更平滑,但是对历史样本有发生误判的现象。

  • 分类决策规则:k近邻法中的分类决策规则往往是多数表决,即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

  • K近邻法的实现:算法思想简单,但是计算复杂度很高,所以有人提出一个高效算法KD树(具体的内容可以参考这篇文章kd树算法详解篇)

3.2 KNN python算法实现

  • 基于sklearn库的python算法实现如下
    1、在使用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近邻算法(KNN)的理论知识和代码实现【分类系列】_第6张图片
有了这张图,我们就能明显看出K值取多少的时候误差最小,这里明显是K=11最好。当然在实际问题中,如果数据集比较大,那为减少训练时间,K的取值范围可以缩小。

2、有了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()

结果
K近邻算法(KNN)的理论知识和代码实现【分类系列】_第7张图片
您的点赞和关注是对博主最大的支持,后续分享更多有用知识。

你可能感兴趣的