本系列文章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 总结
首先通过二叉树搜寻（比拟待查问节点和决裂节点的决裂维的值，小于等于就进入左子树分支，大于就进入右子树分支直到叶子结点），顺着“搜寻门路”很快能找到最近邻的近似点，也就是与待查问点处于同一个子空间的叶子结点；
而后再回溯搜寻门路，并判断搜寻门路上的结点的其余子结点空间中是否可能有间隔查问点更近的数据点，如果有可能，则须要跳到其余子结点空间中去搜寻（将其余子结点退出到搜寻门路）。
反复这个过程直到搜寻门路为空。