机器学习-K近邻算法(KNN)

什么是KNN算法

图解KNN基本算法

（1）k近邻算法中k的选取

（2）距离函数

（3）归一化处理

（4）概率kNN

KNN算法的优缺点

优势

缺点

KNN算法总结

什么是KNN算法

k近邻算法，也称为 KNN 或 k-NN，是一种非参数、有监督的学习分类器，KNN 使用邻近度对单个数据点的分组进行分类或预测。虽然 k近邻算法 (KNN) 可以用于回归或分类问题，但它通常用作分类算法，假设可以在彼此附近找到相似点。

表示 K 最近邻算法图的插图

        回归问题使用与分类问题类似的概念，但在这种情况下，取 k 个最近邻的平均值来对分类进行预测。这里的主要区别是分类用于离散值，而回归用于连续值。但是，在进行分类之前，必须定义距离。最常用的是欧几里得距离，我们将在下面深入研究。
        还值得注意的是，k近邻算法 (KNN) 也是"惰性学习"模型家族的一部分，这意味着它只是存储训练数据集，而不是经历训练阶段。这也意味着所有计算都发生在进行分类或预测时。由于 k近邻算法 (KNN) 严重依赖内存来存储其所有训练数据，因此也称为基于实例或基于内存的学习方法。
        Evelyn Fix 和 Joseph Hodges 在 1951 年的这篇论文中提出了围绕 k近邻算法 (KNN) 模型的最初想法，而 Thomas Cover 在他的研究中扩展了他们的概念：“最近邻模式分类”。虽然这种算法不再像以前那样受欢迎，但由于其简单性和准确性，仍然是人们在数据科学中学习的首选算法之一。然而，随着数据集的增长，k近邻算法 (KNN) 变得越来越低效，影响了整体模型的性能。 k近邻算法 (KNN) 通常用于简单的推荐系统、模式识别、数据挖掘、金融市场预测、入侵检测等。

图解KNN基本算法

假设有三种兔子，第一种兔子叫作绿兔（Green），它们的平均身高是 50厘米，平均体重 5公斤。选取100个样本，分别测量它们的身高和体重，画在坐标图上，用绿色方块表示。

第二种兔子叫蓝兔（blue），它们体型比较小，平均身高是 30厘米，平均体重是 4公斤。同样，选取100个样本，分别测量它们的身高和体重，并将它们画在同一个坐标图上，用蓝色三角表示。

最后一种兔子叫黄兔（yellow），它们的平均身高45厘米，但体重较轻，平均只有2.5公斤。100只黄兔的数据用黄色圆圈表示。

在这些数据中，（身高，体重）的二元组叫做特征（features），兔子的品种则是分类标签（class label）。我们想解决的问题是，给定一个未知分类的新样本的所有特征，通过已知数据来判断它的类别。

现在假设有一只兔子R，想要确定它属于绿兔、蓝兔和黄兔中的哪一类，应该怎么做呢？按照最普通的直觉，应该在已知数据里找出几个和我们想探究的兔子最相似的几个点，然后看看那些兔子都是什么个情况；如果它们当中大多数都属于某一类别，那么兔子R大概率也就是那个类别了。

为了确定兔子R属于哪一类，首先测量出其身长为 40 厘米，体重 2.7 公斤，为了直观展示，将其画在上述同一坐标系中，用红色五角星表示。

现在预设一个整数k，寻找距离兔子R最近的k个数据样本进行分析。kNN 算法如何对这次观测进行分类要取决于k的大小。直觉告诉我们兔子R像是一只黄兔，因为除了最近的蓝色三角外，附近其他都是黄色圆圈。的确，如果设 k = 15，算法会判断这只兔子是一只黄兔。但是如果设 k = 1，那么由于距离最近的是蓝色三角，会判断兔子R是一只蓝兔。

如果按照15NN和1NN的方法对这个二维空间上的每一个点进行分类，会形成以下的分割：

在两组分类中，1NN 的分类边界明显更“崎岖”，但是对历史样本没有误判；而 15NN 的分类边界更平滑，但是对历史样本有发生误判的现象。选择k的大小取决于对偏差和方差之间的权衡。

（1）k近邻算法中k的选取

对于K值的选择，一般根据样本分布选择一个较小的值，然后通过交叉验证来选择一个比较合适的最终值；
当选择比较小的K值的时候，表示使用较小领域中的样本进行预测，训练误差会减小，但是会导致模型变得复杂，容易导致过拟合；
当选择较大的K值的时候，表示使用较大领域中的样本进行预测，训练误差会增大，同时会使模型变得简单，容易导致欠拟合；

如果我们选取较小的k值，那么就会意味着我们的整体模型会变得复杂，容易发生过拟合。假设我们选取k=1这个极端情况，并且有训练数据和待分类点如下图：

上图中有俩类，一个是黑色的圆点，一个是蓝色的长方形，现在我们的待分类点是红色的五边形。根据我们的k近邻算法步骤来决定待分类点应该归为哪一类。我们由图中可以得到，五边形离黑色的圆点最近，k又等于1，因此，我们最终判定待分类点是黑色的圆点。

由这个处理过程我们很容易能够感觉出问题了，如果k太小了，比如等于1，那么模型很容易学习到噪声，也就非常容易判定为噪声类别。而在上图，如果，k大一点，k等于8，把长方形都包括进来，我们很容易得到我们正确的分类应该是蓝色的长方形！如下图：

所谓的过拟合就是在训练集上准确率非常高，而在测试集上准确率低，经过上例，我们可以得到k太小会导致过拟合，很容易将一些噪声（如上图离五边形很近的黑色圆点）学习到模型中，而忽略了数据真实的分布。

如果我们选取较大的k值，就相当于用较大邻域中的训练数据进行预测，这时与输入实例较远的（不相似）训练实例也会对预测起作用，使预测发生错误，k值的增大意味着整体模型变得简单。

我们想，如果k=N（N为训练样本的个数）,那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类。这时，模型压根就没有训练，只是直接拿训练数据统计了一下各个数据的类别，找最大的而已。这好像下图所示：

我们统计了黑色圆形是8个，长方形个数是7个，那么，如果k=N，我就得出结论了，红色五边形是属于黑色圆形的。这个时候，模型过于简单，完全忽略训练数据实例中的大量有用信息，是不可取的。

综上分析，k值既不能过大，也不能过小，在我举的这个例子中，我们k值的选择，在下图红色圆边界之间这个范围是最好的，如下图：

注：这里只是为了更好让大家理解，真实例子中不可能只有两维特征。

（2）距离函数

为了确定哪些数据点最接近给定查询点，需要计算查询点与其他数据点之间的距离。这些距离度量有助于形成决策边界，而决策边界可将查询点划分为不同的区域。你通常会看到使用 Voronoi 图可视化的决策边界。

可以选择多种距离度量，但本文仅涵盖以下几种：

欧几里得距离（p=2） ：又叫欧式距离，这是最常用的距离度量，仅限于实值向量。使用下面的公式，可以测量查询点和被测量的另一个点之间的直线。

欧几里得距离公式

曼哈顿距离（p=1）：这也是另一种流行的距离指标，它测量两点之间的绝对值。也称为出租车距离或城市街区距离，因为它通常用网格可视化，说明人们如何通过城市街道从一个地址导航到另一个地址。

曼哈顿距离公式

闵可夫斯基距离：闵氏距离不是一种距离，而是一组距离的定义，是对多个距离度量公式的概括性的表述。无论是欧式距离还是曼哈顿距离，都可视为闵可夫斯基距离的一种特例。

闵可夫斯基距离公式

其中p是一个变参数：

当p=1时，就是曼哈顿距离；

当p=2时，就是欧氏距离；

当p→∞时，就是切比雪夫距离。

因此，根据变参数的不同，闵氏距离可以表示某一类 / 种的距离。

闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。

e.g. 二维样本（身高[单位:cm],体重[单位:kg]）, 现有三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c的闵氏距离。但实际上身高的10cm并不能和体重的10kg划等号。

闵氏距离的缺点：
(1）将各个分量的量纲（scale），也就是"单位"相同的看待了;
(2）未考虑各个分量的分布（期望，方差等）可能是不同的。

（3）归一化处理

使用 kNN 时需要根据特征数据的取值区间来调整坐标轴的比例，这个做法叫作标准化或者归一化。为什么要这么做呢？拿上面的例子来说，一只兔子的身长（cm）数值平均是它的体重（kg）的 10倍左右，如果我们在这组数值上直接使用闵科夫斯基距离函数的话就会导致横轴的距离比重明显放大，分类结果也不合理，如下图所示：

如果把坐标轴成其他的单位，比如毫米和吨，并用相应的新数值来计算距离，又会得到完全不同的分类标准。甚至，在极端情况下，如果身高用纳米并且体重用吨计量，那么相比之下身高的数值会奇高无比，以至于两点之间的距离是完全由身高决定的，体重则没有任何权重。为了解决这个问题，我们应该在计算距离时把所有坐标轴进行归一化。
在之前的例子中，由于横轴数值大约是竖轴的 10 倍左右，所以我们将横轴（身高）的数值压缩 10倍，即计算距离时使用：

（4）概率kNN

上面的kNN算法返回的是对一组特征的绝对分类，告诉我们这只兔子被判断为哪一个类别。可有时我们并不想知道一个确切地分类，而想知道它属于某个分类的概率是多大。比如我们发现一只身长 37厘米，体重 4.84公斤的小兔兔，在下图五角星的位置。

这只兔子的特征数据在绿兔和蓝兔的分界处，机器不论判断它属于哪个类别都很有可能是错的。这时，类似“它有一半可能性是绿兔，一半可能性是蓝兔”的反馈会更有意义。
为了这个目的，我们同样找出距离问题特征最近的k kk个样本，但与其寻找数量最多的分类，我们统计其中每个类别的分别有多少个，再除以k kk得到一个属于每一个类别概率值。比如在上面的图里，距离五角星最近的 15个样本中，有 8只绿兔和 7 只蓝兔，由此判断：它有 53% 的可能性是绿兔，47% 的可能性是蓝兔，0%的可能性是黄兔。
在整个二维空间中的每一个点上进行概率 kNN 算法，可以得到每个特征点是属于某个类别的概率热力图，图中颜色越深代表概率越大。

15NN 绿兔的概率
15NN 黄兔的概率

15NN 蓝兔的概率

相比于绝对的分类，这些概率的计算会给我们更有效的表述以及更多的应用空间。

KNN算法的优缺点

就像任何机器学习算法一样，k近邻算法 (KNN) 也有其优点和缺点。根据项目和应用，它可能是也可能不是正确的选择。

优势

易于实现：鉴于算法的简单性和准确性，它是新数据科学家将学习的首批分类器之一。
轻松适应：随着新训练样本的增加，算法会根据任何新数据进行调整，因为所有训练数据都存储在内存中。
很少的超参数：k近邻算法 (KNN) 只需要 a k 值和距离度量，与其他机器学习算法相比，所需的超参数很少。

缺点

不能很好地扩展：由于 k近邻算法 (KNN) 是一种惰性算法，因此与其他分类器相比，它占用了更多的内存和数据存储。从时间和金钱的角度来看，这可能是昂贵的。更多的内存和存储将增加业务开支，而更多的数据可能需要更长的时间来计算。虽然已经创建了不同的数据结构（例如 Ball-Tree）来解决计算效率低下的问题，但分类器是否理想可能取决于业务问题。
维度的诅咒：k近邻算法 (KNN) 容易成为维度诅咒的受害者，这意味着它在高维数据输入时表现不佳。这有时也称为峰值现象，在算法达到最佳特征数量后，额外的特征会增加分类错误的数量，尤其是当样本尺寸较小时。
容易过拟合：由于"维度的诅咒"，k近邻算法 (KNN) 也更容易过拟合。虽然利用特征选择和降维技术来防止这种情况发生，但 k 的值也会影响模型的行为。较小的 k 值可能会过度拟合数据，而较大的 k 值往往会"平滑"预测值，因为它是对更大区域或邻域的值进行平均。但是，如果 k 的值太高，那么可能会欠拟合数。

KNN算法作为一种较简单的算法，它的不足之处也明显，由于上述的不足，为了提高kNN搜索的速度，可以利用特殊的数据存储形式来减少计算距离的次数。kd树就是一种以二叉树的形式存储数据的方法。kd树就是对k维空间的一个划分。构造kd树相当于不断用垂直于坐标轴的超平面将k维空间切分，构成一系列k维超矩阵区域。kd树的每一个节点对应一个超矩阵区域。(深入了解请参看李航老师的《统计机器学习》P41页)