机器学习算法之KNN

出品 | 焉知

知圈 | 进“域控制器群”请加微136581676,备注域

机器学习相信大家都不陌生，它是人工智能（AI）和计算机科学的一个分支，主要是利用数据和算法来模仿人类的学习方式，逐步提高其准确性。智能驾驶这些年的迅猛发展，也得益于机器学习的发展，越来越多的机器学习算法在汽车行业得以量产应用。

今天我们来看看机器学习中一种常用的算法——KNN。KNN是K-Nearest Neighbors的缩写，有时也译作K最近邻，属于监督学习算法。本文将从核心思路开始，分析具体实现的数学方法，最后在Python下用KNN做一个关于网络入侵检测的数据实验。

KNN核心思路

KNN最擅长的就是数据分类。比如根据毫米波雷达探测物体的多普勒速度、方位角、等效的雷达散射截面等特征，可以利用KNN将物体分类为汽车、自行车、摩托车和行人等。类似地，KNN也可以用来预测前方追踪的车辆接下来是要左转还是右转。

图1：KNN分类器概念图

那么KNN的原理是什么呢？其实很简单，KNN与众多机器学习算法一样，也能从人类活动中找到类比思路。常言道：近朱者赤，近墨者黑。要快速了解一个人，一种有效的方法就是看看他身边都是什么样的朋友。假设你刚入职新公司三个月，已经对身边同事相当了解，知道他们靠不靠谱。这时候另一个刚外派半年的同事回归到本地办公室，能快速判断他靠不靠谱吗？其中一种方法就是观察这位同事身边最亲近的是哪K个同事，这K个同事是靠谱居多还是不靠谱居多？

类似地，KNN的算法思路就是当要预测一个新值的分类时，先看看离它最接近的K个已标注的学习数据偏向于哪一类。这意味着新的数据点将根据它与训练集里的数据点的匹配程度来分配一个值。

KNN算法详解

聊完抽象思路之后，我们再来看看KNN的具体实现。这具象化过程中最关键的两个点是：确定K和确定距离计算方式。

确定K的取值无疑是KNN模型中至关重要的。KNN顾名思义就是找出最近的K个邻居。同样以上面提到的观察外派回来的同事作为例子。如果K的值取小了，只通过和他最亲近的一个人来评价他，容易以偏概全。如果K的值取大了，比如取全公司人数1000人，那么就失去了“亲近”的概念。这1000个人的特质占比怎么样，和他本人已经关系不大了。

下面一张图可以直观的感受K的取值对于KNN分类模型的影响。X为我们需要预测分类的点。如果K值取1，那么离它最近的1个邻居就是三角形，就会把它分类成三角形。而如果K值取3，那么离他最近的3个邻居中，有2个圆形和1个三角形，圆形居多，就会把它分类成圆形。

图2：KNN分类的K取值示意图

算法另外一个重点是确定距离计算方式，也就是怎么衡量亲疏远近。如上图所示，我们在讨论K取值的时候，其实默认取了两个点的平面几何距离来作为邻居远近的距离。在笛卡尔坐标系下也就是：

这对应的是X和Y坐标分别是样本点的二维特征值。那么如果推广到n维，我们可以定义距离为：

这就是机器学习中常用的欧几里得距离，也称欧氏距离。当然数据点之间的距离还有很多定义方法，例如曼哈顿距离和马氏距离等，此处不展开。而KNN分类算法应用得最多的还是欧氏距离。

要实现最基本的KNN分类算法，只要如上所述确认K值和距离计算方式就可以。而在实际应用中往往针对具体的问题有可以进一步优化的地方，其中最常见的是：调整距离占比的权重和优化搜索算法。在Sklearn的KNN函数中，这两者也是其中的重要参数。

调整距离占比可以加强距离近的邻居的影响力。基本的KNN分类算法中只找出K个最近邻，然后数出其中占比最多的类比，然后分类。但这样做有时会忽略“亲疏有别”。如下图所示，测试数据点为X，K取值为3，欧氏距离最近的三个点如虚线圆圈内所示。直接数最近邻占比，那么X应该分类为正方形。但是3个最近邻中，三角形与X的距离又明显比正方形要小，如果在数数过程中加上距离权重（即距离测试点越近，权重越高），那么X就有可能被分类成三角形。这就好比一个人的亲密情侣，往往比他的几个同事更能反应他是什么类别的人。

图3：KNN分类的距离权重示意图

除了距离权重之外，另外一个常见的优化点就是搜索算法。KNN本质上是计算测试点与所有训练数据点的距离，然后搜索找出其中最近的N个近邻，这也是最耗费算力的地方。如果训练集数据量很大，而还用暴力搜索方法的话，整体的训练效率就会很低。所幸关于搜索算法，已经有丰富的研究和可用的选择，例如KD Tree和Ball Tree就是KNN过程中优化搜索的常用算法。其中KD Tree针对欧氏距离效率较高，Ball Tree可以用于高维距离。

KNN优缺点与实际应用

了解完KNN算法的实现，我们再回过来看看KNN的特点。

KNN算法的优点：

1. 实现简单。与很多其他机器学习算法动辄复杂的微积分和概率论等数学原理相比，KNN的数学原理和具体实现都简单直接，大概只需初中数学就能搞清楚。

2. 鲁棒性好。KNN对训练数据中的异常值并不敏感，对噪声明显的数据具有较好的鲁棒性。

3. 对非线性数据效果好，因为在这个算法中没有关于数据的假设，不需要做线性回归。

4. 预测效果好。如果训练数据非常大，它可以更有效。

KNN算法的缺点或局限：

1. 总是需要确定K的值，这可能是一个复杂和反复调试的过程。

2. 计算成本高。因为要计算所有训练样本的数据点之间的距离，所以预测过程中需要存储所有训练数据，对内存的要求很高。

3. 随着训练数据量的增大，其预测速度也明显变慢。

4. 对数据的规模和不相关的特征非常敏感。

那么在实际工程应用中，哪里有KNN的身影呢？

1. 银行信用评级。KNN可用于银行系统，预测一个人是否适合贷款审批？这个人是否具有与违约者相似的特征？

2. 语音识别。在KNN算法的帮助下，我们可以将输入的语音数据进行分类，预测说话人的意图。

3. 手写检测。KNN也常用来识别手写字体的图像，尤其是阿拉伯数字。

4. 车辆行为预测。KNN可以通过前车的实时运动数据，预测其下一步的可能动作。

5. 网络入侵检测。KNN可以根据网络特征数据，来判断当前网络是否被攻击。

KNN的Python实例

Sklearn中就有KNN分类器的函数“KNeighborsClassifier”，官方的说明材料很详尽。这里为了更加细致地理解KNN算法，我们重新手写一下代码，做一个Python下的数据实验。

如上文所述，KNN常用与网络入侵检测（IDS）。这个数据实验我们就用NSL-KDD数据集。这是网络安全领域相对权威的一个入侵检测数据集，可以根据网络特征数据，检测是否有入侵发生，属于哪种类型的攻击入侵。IDS越来越多地在车载网络上普及，包括AUTOSAR Adaptive中也加入了该模块。总体思路是车端域控制器或者计算平台收集特征的网络数据，并通过车联网上传云端分析，检测车辆网络有没有被攻击或者入侵。

NSL-KDD数据集细分了很多攻击类型，在这个实验中，我们将其合并成5大类，如下表所示。

表1：NSL-KDD数据集概况

NSL-KDD原始数据集数据不平衡，也含有文本特征，所以需要作预处理，包括重采样、文本特征独热编码和归一化等，这里不详细展开。预处理后的数据集概况如下表2所示。

表2：数据实验所用数据集概况

而这个数据实验的大致流程如下图所示，先利用训练集a、b通过粗调和细调确定K值，然后再预测测试集并评价：

图4：数据实验基本流程

其中找出K个欧氏距离最近的数据的代码如下：

然后在K个近邻中找出类别占比最多的函数：

之后是KNN分类器的主函数：

基于训练数据a, 让K在1到1000的范围内以步长20取值，预测训练数据b，并和数据b的标签信息比对，得出K与准确率的关系如下图。

图5：粗调下K取值与准确率的关系

由此按照550到650的范围内以步长1取值，得出如下的K与准确率关系。由此，我们确定K取值582。

图6：细调下K取值与准确率的关系

基于确定的K值，代入测试数据集的数据，并预测结果。将预测结果和测试集的标注对比得到如下的模型评价指标：

图7：KNN分类器模型评价

从评价指标看，总体准确率还有提升的空间，不同的攻击类型的准确率和召回率也各有不同。例如Dos攻击目的是耗尽资源，数据流量异常相对明显，其分类准确率也较高。而远程入侵r2l相对隐蔽，分类难度也高些。当然亦正因为不同分类器对不同攻击类型的识别各有长短，实际上入侵检测系统（IDS）往往部署在云端，也会采用大算力下多种模型冗余校核的手段来提高网络信息安全性。

写在最后

本文抛砖引玉，简述了KNN的原理，并以KNN在网络入侵检测的应用作为例子，完成了数据实验。近年来智能汽车的快速发展，背后是人工智能的支撑。而人工智能也有望在汽车产业上进一步落地。像KNN等机器学习算法相信今后也会更多地应用在汽车产业上，不管是单车智能、车联网下的云端数据处理、车载网络信息安全乃至汽车企业文档管理工具等，都是人工智能展现的舞台。在这样的时代下，我们大家都学一点人工智能的知识，会不会就像90年代末大家都学一点电脑知识一样重要呢？谨以此与大家共勉。

参考来源：

1.https://www.javatpoint.com/k-nearest-neighbor-algorithm-for-machine-learning

2.https://www.researchgate.net/figure/Illustration-example-of-KNN-algorithm_fig1_282448172

3.https://www.tutorialspoint.com/machine_learning_with_python/machine_learning_with_python_knn_algorithm_finding_nearest_neighbors.htm

4. NSL-KDD | Datasets | Research | Canadian Institute for Cybersecurity | UNB