共计 3960 个字符，预计需要花费 10 分钟才能阅读完成。
本系列文章 md 笔记（已分享）次要探讨机器学习算法相干常识。机器学习算法文章笔记以算法、案例为驱动的学习，随同浅显易懂的数学知识，让大家把握机器学习常见算法原理，利用 Scikit-learn 实现机器学习算法的利用，联合场景解决理论问题。包含 K - 近邻算法，线性回归，逻辑回归，决策树算法，集成学习，聚类算法。K- 近邻算法的间隔公式，利用 LinearRegression 或 SGDRegressor 实现回归预测，利用 LogisticRegression 实现逻辑回归预测，利用 DecisionTreeClassifier 实现决策树分类，利用 RandomForestClassifie 实现随机森林算法，利用 Kmeans 实现聚类工作。
全套笔记和代码自取移步 gitee 仓库：gitee 仓库获取残缺文档和代码
感兴趣的小伙伴能够自取哦，欢送大家点赞转发~
共 7 章，44 子模块
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 总结
首先 通过二叉树搜寻 （比拟待查问节点和决裂节点的决裂维的值，小于等于就进入左子树分支，大于就进入右子树分支直到叶子结点）， 顺着“搜寻门路”很快能找到最近邻的近似点，也就是与待查问点处于同一个子空间的叶子结点；
而后再回溯搜寻门路，并判断搜寻门路上的结点的其余子结点空间中是否可能有间隔查问点更近的数据点，如果有可能，则须要跳到其余子结点空间中去搜寻（将其余子结点退出到搜寻门路）。
反复这个过程直到搜寻门路为空。
