人工智能算法与实践-第6章 KNN算法

6.4算法案例26.1算法概述6.2算法原理6.3算法案例1目录第六章K近邻算法人工智能算法与实践—1

—

6.5算法总结01算法概述PartONE—2

—

K近邻算法K近邻算法（k-NearestNeighbor）又称KNN算法，是机器学习中的一个经典的算法。K-近邻算法原理如下：给定一个训练数据集，并且每个数据都存有一个标签。对于新输入的实例，在训练数据集中找到与该实例最为邻近的K个实例，这K个实例的多数存在哪个类中，就把新的输入实例分类到这个类中。打个比方：假设你们想了解我是个怎样的人，然后你发现我身边关系最密切的朋友是一群学霸，那么你可以推测出我也是一个学霸。假设有两类不同的样本数据，分别用三角形和正方形表示，如图所示。图正中间的五角星表示的是待分类的数据。那么，如何给这个五角星分类呢？6.1算法概述—3

—

02算法原理PartTWO—4

—

做分类找邻居算距离给定测试对象，计算它与训练集中的每个对象的距离。圈定距离最近的K个训练对象，作为测试对象的近邻。根据这K个近邻归属的主要类别，来对测试对象分类。6.2.1算法计算步骤—5

—

K折交叉验证的基本思路如下：（1）不重复地将原训练集随机分为m份；（2）挑选其中1份作为验证集，剩余K-1份作为训练集用于模型训练，在训练集上训练后得到一个模型，用这个模型在验证集上测试，保存模型的评估指标；（3）重复第二步K次（确保每个子集都有一次机会作为验证集）；（4）计算K组测试指标的平均值作为模型精度的估计，并作为当前K折交叉验证下模型的性能指标。假设K=5时，其交叉验证方法如左图所示。KNN中的K值选取对分类的结果影响至关重要。如果K值选取的太小，即选用较小的邻域中的样本进行预测，容易受到异常点的影响，波动较大，模型整体会很复杂，容易发生过拟合。6.2.2K值的选取—6

—

010203欧氏距离曼哈顿距离明考斯基距离6.2.3确定距离函数—7

—

03算法案例PartTHREE约会网站配对数据—8

—

6.3.1读取数据集—9

—

数据集介绍：海伦女士一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但她并不是喜欢每一个人。经过一番总结，她发现自己交往过的人可以进行如下分类：不喜欢，即didntlike；魅力一般，即smallDoes；极具魅力，即largeDoes。代码输出结果如下：根据数据集的第一列和第三列数据创建散点图，横轴表示特征值“每年出行的里程数”，纵轴表示特征值“每周吃冰淇淋的公升数”根据数据集的第一列和第二列数据创建散点图，横轴表示特征值“每年出行的里程数”，纵轴表示特征值“玩游戏的时间占比”根据数据集的第二列和第三列数据创建散点图，横轴表示特征值“玩游戏的时间占比”，纵轴表示特征值“每周吃冰淇淋的公升数”6.3.2创建散点图分类数据—10

—

6.3.3数据归一化处理—11

—

提取了四组样本数据，计算样本1和样本2之间的距离，这里我们选用欧氏距离，因此样本1与样本2之间的距离计算方法如下：每年出行里程数对于计算结果的影响远远大于表中其他两个特征。在处理这种数字差值范围大的特征值时，我们通常采用归一化的方法将取值范围处理为0到1或者−1到1之间，利用下面公式，可以实现将特征值转化为[0,1]区间内的值：输出结果如下所示6.3.4测试KNN分类器模型—12

—

左边为KNN模型的代码实现，这里将训练集和测试集按照7：3划分。设置k=4，遍历测试集的每一行，knn()函数会返回该行数据的分类标签结果，与实际分类标签结果进行比较，若不一致，则error加1，最后计算整个测试集的错误率。

输出结果如下所示：由此看出，KNN处理约会数据集的错误率最终为4.3%，效果还不错。6.3.5模型预测—13

—

输出结果如下所示：classifyPerson()函数的作用是输入一名用户的玩游戏时间比，一年飞行里程，消费冰淇淋数预测海伦与改名用户的匹配程度。04算法案例PartFOUR预测签到位置—14

—

预测签到位置Facebook创建了一个虚拟世界，其中包括10公里*10公里共100平方公里的约10万个地方。对于给定的坐标集，您的任务将根据用户的位置、准确性和时间戳等预测用户下一次的签到位置，从而使商家在用户签到次数多的地方更精准的投放广告，如上图所示。6.4.1项目介绍—15

—

签到事件的id用户签到位置定位准确度时间戳业务id，预测的目标值12345数据集介绍6.4.2数据集介绍—16

—

row_id

xyaccuarcy

time

place_id

6.4.3算法流程分析—17

—

首先获取数据，然后对数据进行处理，主要是处理时间特征，将时间戳成立成比较有意义的时间，还需过滤掉年和月以及签到次数少的地点。数据处理完后筛选特征值和目标值，接着进行数据集划分，使用特征工程进行标准化，接着使用KNN算法预估器进行模型训练，同时加入网格搜索与交叉验证，最后进行模型评估。6.4.4代码实现—18

—

实验代码运行后，实验结果如下：05算法总结PartFIVE—19

—

算法总结优点缺点1优点1）算法简单，易于理解，易于实现。2）不需要显示的训练过程，模型就是训练数据集本身。3）特别适用于多分类问题。2缺点1）它是一种懒惰算法，对测试样本分类时的计算量大，内存开销大，评分