在机器学习的世界里打怪升级——KNN算法篇

“全文约2000字，阅读时间约6分钟”

来自机器学习世界里的勇士，你刚走出新手村，还没完全武装自己，就碰到了旅途中第一个小boss——KNN算法。

不过也别害怕，这是入门机器学习zui简单、也zui容易理解的一个算法。

boss技能综述

先来看看该boss的整体技能（原理）综述：

要想预测一个新数据，只需把它放到训练数据集中（“旧数据”），看它离哪些数据近，就把它预测为这些数据的类别（分类）；或者把它预测为这些数据的均值（回归）。

所以k近邻算法既可以做分类，又可以做回归（限于篇幅，本文只介绍分类）。

我们说，机器学习可以看做是一个函数，输入训练数据集，输出预测值。在k近邻算法中，给定一个数据集D：

其中，x为n维向量，代表每一个样本的特征数量；y代表有p个类别；右上角的角标从1到N，代表有N个样本。

我们的目标是：

当给定一个新的实例x，模型通过学习数据集D，输出实例x对应的类别y。

boss详细攻略

该算法的步骤很简单，主要有以下两步：

1.找到与x距离最近（如何衡量最近？下文会有介绍）的k个点，k近邻算法中的k就是这个含义。

2.根据“少数服从多数”的原则，决定x的类别y。换句话说，这k个点中最多的那个类别，就是新的实例x的类别。用公式表示为：

那这公式是啥意思呢？

我们从括号内部开始看起。

首先，y[i]表示k个点所对应的类别，a[j]就表示数据集D中的所有类别，j的取值为1到p（上文介绍过，一共有p个类别）。

其次，I()叫做指示函数。

它的含义是，当括号内的条件为真（True）时，函数返回的值是1；当括号内的条件为假（False）时，函数返回0。

在公式（1）中，当y[i]=a[j]时，返回1。

我们来看下公式（1）运行的过程：

首先取第1个类别a[1]，让k个点对应的y[i]都跟a[1]比较，计算指示函数并求和。

接下来从第2个类别a[2]开始循环上面的步骤，直到第p个类别a[p]。

由于每次循环返回一个值，我们需要找出其中的最大值，那么这个最大值对应的类别，就是我们要求的实例x对应的类别y。

距离的衡量

k近邻算法中，向量和向量之间的距离，我们一般用L2范数来衡量。即

a[i]就表示a中的第i个维度（特征），总共有n个维度（特征）。

分类的规则

最后我们来看下为什么“少数服从多数”的规则是可行的。

我们做一个分类问题的目标是什么？

当然是分错的数量越少越好了。

假设我们预测的类别为y'，实际的类别为y，显然，我们分错的概率为

当我们找到离x最近的k个点之后，分错的概率就是

我们希望分错的概率越小越好，那么就意味着（3）式中的

越大越好，而这正是我们公式（1）所表示的内容。

因此，多数“投票”的规则就等价于分错概率最小化。

boss技能介绍

Python在机器学习领域有着得天独厚的优势，下面我们就来看看KNN算法在Python中是如何被调用的（调包侠）。

分类

我们来看下它的参数。

1.algorithm

该参数指在寻找最近邻时所采用的算法，默认为auto，意为自动进行选择。可供选择的算法主要有下面三种：kd_tree，ball_tree，brute。

2.leaf_size

指叶子节点的数目，默认为30。

3.metric

指采用何种方式进行距离度量，默认为minkowski（闵可夫斯基距离），也就是我们之前介绍过的范数。

4.metric_params

指距离度量的相关参数，一般无需进行设置。

5.n_neighbors

指最近邻点的个数，默认为5个。

6.p

当p=1时，即L1范数，采用曼哈顿距离；当p=2时，意为L2范数，采用欧氏距离。

7.weights

指分类时的权重类型，默认是uniform，即k个近邻点的权重相等；还可以选择distance，意为近邻点的权重与预测点之间的距离有关，一般是反比的关系。

回归

在scikit-learn中可以按如下方式实现：

可以看到，回归模型的参数与分类模型的一模一样，大家可以进行参考，这里就不再赘述了。

boss战

终于，我们要直面KNN算法这个小boss了。

Python的scikit-learn库中自带了很多公开的数据集，这里用乳腺癌数据集来说明k近邻算法。

首先，加载该数据集

然后，把该数据集分成两部分。一部分用来训练我们的模型，另一部分用来测试模型的精度。

其中，train_test_split可以将数据按25%的比例分成训练集和测试集。X_train、y_train为训练样本和标签，占75%；X_test、y_test为测试样本和标签，占比25%。

接着，加载我们的模型

这里的n_neighbors和k的含义一样，都是指邻居的个数。也就是说，我们要找到最近的3个邻居，来对预测做出判断。

然后，把数据“喂”给我们的模型，让模型得到训练。

训练完成后，我们测试一下模型的精度

也就是说，模型的精度达到了91.6%。

呼，boss终于倒下了，但刚才的过程有点惊险，我们还需要做一些任务来补充实力。

任务1：模型的泛化能力

我们用数据训练模型的目的，就是希望它在未知的新数据集中有很好的表现，我们把这种能力就叫做泛化。

我们总是希望泛化精度尽可能高，但有时候，你对旧数据进行过度训练，模型在训练集中表现的非常好，以至于将一些无关的噪声点都拟合了进来。

这时，模型的泛化能力反而会降低，我们称之为过拟合。

与此同时，假如你没有对数据进行有效的训练，产生的模型也比较粗糙，那么对于新的数据集，模型同样不会有好的结果。我们称之为欠拟合。

在模型训练过程中，既不能训练过少，也不能过度训练。过拟合和欠拟合都是需要我们避免的。

任务2：模型的优缺点

优点：模型易于理解，不需要什么数学基础。参数也不多，调参很容易。

缺点：如果训练数据的特征很多，而且样本也很大，那么k近邻算法的预测速度和精度都会有大幅下降。

恭喜你，勇士！经过这一场战斗，你获得了以下属性提升：

武力+1%，技能熟练度+1%，智慧+1%

前方还有更多未知的冒险在等着你，继续前进吧，勇士！