【机器学习】机器学习创建算法第2篇：K-近邻算法【附代码文档】

机器学习（算法篇）完整教程（附代码资料）主要内容讲述：机器学习算法课程定位、目标，K-近邻算法，1.1 K-近邻算法简介，1.2 k近邻算法api初步使用定位,目标,学习目标,1 什么是K-近邻算法,1 Scikit-learn工具介绍,2 K-近邻算法API,3 案例,4 小结。K-近邻算法，1.3 距离度量学习目标,1 欧式距离,2 ,3 切比雪夫距离 (Chebyshev Distance)：,4 闵可夫斯基距离(Minkowski Distance)：,5 标准化欧氏距离 (Standardized EuclideanDistance)：,6 余弦距离(Cosine Distance),7 汉明距离(Hamming Distance)【了解】：,9 马氏距离(Mahalanobis Distance)【了解】。K-近邻算法，1.4 k值的选择学习目标。K-近邻算法，1.5 kd树学习目标,1 kd树简介,2 构造方法,3 案例分析,4 总结。K-近邻算法，1.6 案例：鸢尾花种类预测--数据集介绍，1.7 特征工程-特征预处理学习目标,1 案例：鸢尾花种类预测,2 scikit-learn中数据集介绍,1 什么是特征预处理,2 归一化,3 标准化。K-近邻算法，1.8 案例：鸢尾花种类预测—流程实现，1.9 练一练，1.10 交叉验证，网格搜索，1.11 案例2：预测facebook签到位置学习目标,1 再识K-近邻算法API,2 案例：鸢尾花种类预测,总结,1 什么是交叉验证(cross validation),2 什么是网格搜索(Grid Search),3 交叉验证，网格搜索（模型选择与调优）API：,4 鸢尾花案例增加K值调优,1 数据集介绍,2 步骤分析,3 代码过程。线性回归，2.1 线性回归简介，2.2 线性回归api初步使用，2.3 数学:求导学习目标,1 线性回归应用场景,2 什么是线性回归,1 线性回归API,2 举例,1 常见函数的导数,2 导数的四则运算,3 练习,4 矩阵（向量）求导 [了解]。线性回归，2.4 线性回归的损失和优化学习目标,1 损失函数,2 优化算法。线性回归，2.6 梯度下降法介绍，2.5 线性回归api再介绍学习目标,1 全梯度下降算法（FG）,2 随机梯度下降算法（SG）,3 小批量梯度下降算法（mini-bantch）,4 随机平均梯度下降算法（SAG）,5 算法比较,6 梯度下降优化算法(拓展)。线性回归，2.7 案例：波士顿房价预测学习目标,1 分析,2 回归性能评估,3 代码。线性回归，2.8 欠拟合和过拟合学习目标,1 定义,2 原因以及解决办法,3 正则化,4 维灾难【拓展知识】。线性回归，2.9 正则化线性模型，2.10 线性回归的改进-岭回归，2.11 模型的保存和加载，逻辑回归，3.1 逻辑回归介绍，3.2 逻辑回归api介绍，3.3 案例：癌症分类预测-良／恶性乳腺癌肿瘤预测学习目标,1 Ridge Regression (岭回归，又名 Tikhonov regularization),2 Lasso Regression(Lasso 回归),3 Elastic Net (弹性网络),4 Early Stopping [了解],1 API,2 观察正则化程度的变化，对结果的影响？,3 波士顿房价预测,1 sklearn模型的保存和加载API,2 线性回归的模型保存加载案例,学习目标,1 逻辑回归的应用场景,2 逻辑回归的原理,3 损失以及优化,1 分析,2 代码。逻辑回归，3.4 分类评估方法，3.5 ROC曲线的绘制，决策树算法，4.1 决策树算法简介学习目标,1.分类评估方法,2 ROC曲线与AUC指标,3 总结,1 曲线绘制,2 意义解释,学习目标。决策树算法，4.2 决策树分类原理学习目标,1 熵,2 决策树的划分依据一------信息增益,3 决策树的划分依据二----信息增益率,4 决策树的划分依据三——基尼值和基尼指数。决策树算法，4.3 cart剪枝学习目标,1 为什么要剪枝,2 常用的减枝方法。决策树算法，4.4 特征工程-特征提取学习目标,1 特征提取,2 字典特征提取,3 文本特征提取。决策树算法，4.5 决策树算法api，4.6 案例：泰坦尼克号乘客生存预测，集成学习，5.1 集成学习算法简介，5.2 Bagging学习目标,1 泰坦尼克号数据,2 步骤分析,3 代码过程,3 决策树可视化,学习目标,1 什么是集成学习,2 ,3 集成学习中boosting和Bagging,1 Bagging集成原理,2 随机森林构造过程,3 随机森林api介绍,4 随机森林预测案例,5 bagging集成优点。集成学习，5.3 Boosting，聚类算法，6.1 聚类算法简介，6.2 聚类算法api初步使用，6.3 聚类算法实现流程学习目标,1.boosting集成原理,2 GBDT(了解),3.XGBoost【了解】,4 什么是泰勒展开式【拓展】,学习目标,1 认识聚类算法,1 api介绍,2 案例,1 k-means聚类步骤,2 案例练习,3 小结。聚类算法，6.4 模型评估，6.5 算法优化学习目标,1 误差平方和(SSE \The sum of squares due to error)：,2 , — K值确定,3 轮廓系数法（Silhouette Coefficient）,4 CH系数（Calinski-Harabasz Index）,5 总结,1 Canopy算法配合初始聚类,2 K-means++,3 二分k-means,4 k-medoids（k-中心聚类算法）,5 Kernel k-means（了解）,6 ISODATA（了解）,7 Mini Batch K-Means（了解）,8 总结。聚类算法，6.6 特征降维，6.7 案例：探究用户对物品类别的喜好细分降维，6.8 算法选择指导学习目标,1 降维,2 特征选择,3 主成分分析,1 需求,2 分析,3 完整代码。

全套笔记资料代码移步： 前往gitee仓库查看

感兴趣的小伙伴可以自取哦，欢迎大家点赞转发~

---

K-近邻算法

学习目标

• 掌握K-近邻算法实现过程
• 知道K-近邻算法的距离公式
• 知道K-近邻算法的超参数K值以及取值问题
• 知道kd树实现搜索的过程
• 应用KNeighborsClassifier实现分类
• 知道K-近邻算法的优缺点
• 知道交叉验证实现过程
• 知道超参数搜索过程
• 应用GridSearchCV实现算法参数的调优

1.4 k值的选择

举例说明：

K值过小：

​ 容易受到异常点的影响

k值过大：

​ 受到样本均衡的问题

---

K值选择问题，李航博士的一书「统计学习方法」上所说：

1) 选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；

2) 选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。

3) K=N（N为训练样本个数），则完全不足取，因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中大量有用信息。

在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是把训练数据在分成两组:训练集和验证集）来选择最优的K值。对这个简单的分类器进行泛化，用核方法把这个线性模型扩展到非线性的情况，具体方法是把低维数据集映射到高维特征空间。

---

近似误差：对现有训练集的训练误差，关注训练集，如果近似误差过小可能会出现过拟合的现象，对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。

估计误差：可以理解为对测试集的测试误差，关注测试集，估计误差小说明对未知数据的预测能力好，模型本身最接近最佳模型。

K-近邻算法

学习目标

• 掌握K-近邻算法实现过程
• 知道K-近邻算法的距离公式
• 知道K-近邻算法的超参数K值以及取值问题
• 知道kd树实现搜索的过程
• 应用KNeighborsClassifier实现分类
• 知道K-近邻算法的优缺点
• 知道交叉验证实现过程
• 知道超参数搜索过程
• 应用GridSearchCV实现算法参数的调优

1.5 kd树

问题导入：

实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索。

这在特征空间的维数大及训练数据容量大时尤其必要。

k近邻法最简单的实现是线性扫描（穷举搜索），即要计算输入实例与每一个训练实例的距离。计算并存储好以后，再查找K近邻。当训练集很大时，计算非常耗时。

为了提高kNN搜索的效率，可以考虑使用特殊的结构存储训练数据，以减小计算距离的次数。

---

1 kd树简介

1.1 什么是kd树

根据KNN每次需要预测一个点时，我们都需要计算训练数据集里每个点到这个点的距离，然后选出距离最近的k个点进行投票。当数据集很大时，这个计算成本非常高，针对N个样本，D个特征的数据集，其算法复杂度为O（DN^2）。

kd树：为了避免每次都重新计算一遍距离，算法会把距离信息保存在一棵树里，这样在计算之前从树里查询距离信息，尽量避免重新计算。其基本原理是，如果A和B距离很远，B和C距离很近，那么A和C的距离也很远。有了这个信息，就可以在合适的时候跳过距离远的点。

这样优化后的算法复杂度可降低到O（DNlog（N））。感兴趣的读者可参阅论文：Bentley，J.L.，Communications of the ACM（1975）。

1989年，另外一种称为Ball Tree的算法，在kd Tree的基础上对性能进一步进行了优化。感兴趣的读者可以搜索Five balltree construction algorithms来了解详细的算法信息。

1.2 原理

黄色的点作为根节点，上面的点归左子树，下面的点归右子树，接下来再不断地划分，分割的那条线叫做分割超平面（splitting hyperplane），在一维中是一个点，二维中是线，三维的是面。

黄色节点就是Root节点，下一层是红色，再下一层是绿色，再下一层是蓝色。

1.树的建立；

2.最近邻域搜索（Nearest-Neighbor Lookup）

kd树(K-dimension tree)是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是一种二叉树，表示对k维空间的一个划分，构造kd树相当于不断地用垂直于坐标轴的超平面将K维空间切分，构成一系列的K维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

类比“二分查找”：给出一组数据：[9 1 4 7 2 5 0 3 8]，要查找8。如果挨个查找（线性扫描），那么将会把数据集都遍历一遍。而如果排一下序那数据集就变成了：[0 1 2 3 4 5 6 7 8 9]，按前一种方式我们进行了很多没有必要的查找，现在如果我们以5为分界点，那么数据集就被划分为了左右两个“簇” [0 1 2 3 4]和[6 7 8 9]。

因此，根本就没有必要进入第一个簇，可以直接进入第二个簇进行查找。把二分查找中的数据点换成k维数据点，这样的划分就变成了用超平面对k维空间的划分。空间划分就是对数据点进行分类，“挨得近”的数据点就在一个空间里面。

2 构造方法

（1）构造根结点，使根结点对应于K维空间中包含所有实例点的超矩形区域；

（2）通过递归的方法，不断地对k维空间进行切分，生成子结点。在超矩形区域上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（子结点）；这时，实例被分到两个子区域。

（3）上述过程直到子区域内没有实例时终止（终止时的结点为叶结点）。在此过程中，将实例保存在相应的结点上。

（4）通常，循环的选择坐标轴对空间切分，选择训练实例点在坐标轴上的中位数为切分点，这样得到的kd树是平衡的（平衡二叉树：它是一棵空树，或其左子树和右子树的深度之差的绝对值不超过1，且它的左子树和右子树都是平衡二叉树）。

KD树中每个节点是一个向量，和二叉树按照数的大小划分不同的是，KD树每层需要选定向量中的某一维，然后根据这一维按左小右大的方式划分数据。在构建KD树时，关键需要解决2个问题：

（1）选择向量的哪一维进行划分；

（2）如何划分数据；

第一个问题简单的解决方法可以是随机选择某一维或按顺序选择，但是更好的方法应该是在数据比较分散的那一维进行划分（分散的程度可以根据方差来衡量）。好的划分方法可以使构建的树比较平衡，可以每次选择中位数来进行划分，这样问题2也得到了解决。

3 案例分析

3.1 树的建立

给定一个二维空间数据集：T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}，构造一个平衡kd树。

（1）思路引导：

根结点对应包含数据集T的矩形，选择x(1)轴，6个数据点的x(1)坐标中位数是6，这里选最接近的(7,2)点，以平面x(1)=7将空间分为左、右两个子矩形（子结点）；接着左矩形以x(2)=4分为两个子矩形（左矩形中{(2,3),(5,4),(4,7)}点的x(2)坐标中位数正好为4），右矩形以x(2)=6分为两个子矩形，如此递归，最后得到如下图所示的特征空间划分和kd树。

3.2 最近领域的搜索

假设标记为星星的点是 test point， 绿色的点是找到的近似点，在回溯过程中，需要用到一个队列，存储需要回溯的点，在判断其他子节点空间中是否有可能有距离查询点更近的数据点时，做法是以查询点为圆心，以当前的最近距离为半径画圆，这个圆称为候选超球（candidate hypersphere），如果圆与回溯点的轴相交，则需要将轴另一边的节点都放到回溯队列里面来。

样本集{(2,3),(5,4), (9,6), (4,7), (8,1), (7,2)}

3.2.1 查找点(2.1,3.1)

在(7,2)点测试到达(5,4)，在(5,4)点测试到达(2,3)，然后search_path中的结点为<(7,2),(5,4), (2,3)>，从search_path中取出(2,3)作为当前最佳结点nearest, dist为0.141；

然后回溯至(5,4)，以(2.1,3.1)为圆心，以dist=0.141为半径画一个圆，并不和超平面y=4相交，如上图，所以不必跳到结点(5,4)的右子空间去搜索，因为右子空间中不可能有更近样本点了。

于是再回溯至(7,2)，同理，以(2.1,3.1)为圆心，以dist=0.141为半径画一个圆并不和超平面x=7相交，所以也不用跳到结点(7,2)的右子空间去搜索。

至此，search_path为空，结束整个搜索，返回nearest(2,3)作为(2.1,3.1)的最近邻点，最近距离为0.141。

3.2.2 查找点(2,4.5)

在(7,2)处测试到达(5,4)，在(5,4)处测试到达(4,7)【优先选择在本域搜索】，然后search_path中的结点为<(7,2),(5,4), (4,7)>，从search_path中取出(4,7)作为当前最佳结点nearest, dist为3.202；

然后回溯至(5,4)，以(2,4.5)为圆心，以dist=3.202为半径画一个圆与超平面y=4相交，所以需要跳到(5,4)的左子空间去搜索。所以要将(2,3)加入到search_path中，现在search_path中的结点为<(7,2),(2, 3)>；另外，(5,4)与(2,4.5)的距离为3.04 < dist = 3.202，所以将(5,4)赋给nearest，并且dist=3.04。

回溯至(2,3)，(2,3)是叶子节点，直接平判断(2,3)是否离(2,4.5)更近，计算得到距离为1.5，所以nearest更新为(2,3)，dist更新为(1.5)

回溯至(7,2)，同理，以(2,4.5)为圆心，以dist=1.5为半径画一个圆并不和超平面x=7相交, 所以不用跳到结点(7,2)的右子空间去搜索。

至此，search_path为空，结束整个搜索，返回nearest(2,3)作为(2,4.5)的最近邻点，最近距离为1.5。

4 总结

首先通过二叉树搜索（比较待查询节点和分裂节点的分裂维的值，小于等于就进入左子树分支，大于就进入右子树分支直到叶子结点），顺着“搜索路径”很快能找到最近邻的近似点，也就是与待查询点处于同一个子空间的叶子结点；

然后再回溯搜索路径，并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点，如果有可能，则需要跳到其他子结点空间中去搜索（将其他子结点加入到搜索路径）。

重复这个过程直到搜索路径为空。

未完待续， 同学们请等待下一期

全套笔记资料代码移步： 前往gitee仓库查看

感兴趣的小伙伴可以自取哦，欢迎大家点赞转发~