❶ KNN算法，结果报错，帮忙怎么改
knn算法(k-Nearest Neighbor algorithm).是一种经典的分类算法.
注意,不是聚类算法.所以这种分类算法必然包括了训练过程.
然而和一般性的分类算法不同,knn算法是一种 懒惰算法 .它并非
像其他的分类算法先通过训练建立分类模型.,而是一种被动的分类
过程.它是边测试边训练建立分类模型.
算法的一般描述过程如下:
1.首先计算每个测试样本点到其他每个点的距离.
这个距离可以是欧氏距离,余弦距离等.
❷ 01 KNN算法 - 概述
KNN算法 全称是K近邻算法 （K-nearst neighbors，KNN）
KNN是一种基本的机器学习算法，所谓K近邻，就是k个最近的邻居。即每个样本都可以用和它 最接近的k个邻近位置的样本 来代替。
KNN是个相对比较简单的算法，比起之前提过的回归算法和分类算法更容易。如果一个人从来没有接触过机器学习的算法，拿到数据后最容易想到的分类方式就是K近邻。打个比方：你们想了解我是个怎样的人，然后你们发现我的身边关系最密切的朋友是一群逗逼，所以你们可以默认我也是一个逗逼。
KNN算法即可以应用于 分类算法 中，也可以应用于 回归算法 中。
KNN在做回归和分类的主要区别，在于最后做预测时候的决策不同。在分类预测时，一般采用 多数表决法 。在做回归预测时，一般使用 平均值法 。
多数表决法： 分类时，哪些样本离我的目标样本比较近，即目标样本离哪个分类的样本更接近。
平均值法： 预测一个样本的平均身高，观察目标样本周围的其他样本的平均身高，我们认为平均身高是目标样本的身高。
再举个例子：
分别根据甜度和脆度两个特征来判断食物的种类。
根据样本我们普遍发现：
比较甜，比较脆的食物都是水果。
不甜，不太脆的食物是蛋白质。
不甜，比较脆的食物是蔬菜。
于是根据目标的样本甜度和脆度两个特征，我们可以对其进行分类了。
k值的选择:
先选一个较小的值，然后通过交叉验证选择一个合适的最终值。
k越小，即使用较小的领域中的样本进行预测，训练误差会减小，但模型会很复杂，以至于过拟合。
k越大，即使用交大的领域中的样本进行预测，训练误差会增大，模型会变得简单，容易导致欠拟合。
距离的度量:
使用欧几里得距离：欧几里得度量（euclidean metric）（也称欧氏距离）是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。
决策规划:
分类：多数表决法、加权多数表决法。
回归：平均值法、加权平均值法。
加权多数表决法：
平均值法和加权平均值法：
同样看上面的图，上方的三个样本值为3，下面两个样本值为2，预测？的值。
如果不考虑加权，直接计算平均值：
(3 * 3 + 2 * 2) / 5 = 2.6
加权平均值：权重分别为1/7和2/7。计算加权平均值：
(3 * 3* 1/7 + 2 * 2 * 2/7) / 5 = 2.43
1、蛮力实现(brute)：
计算预测样本到所有训练集样本的距离，然后选择最小的k个距离，即可得到k个最邻近点。
缺点：当特征数多、样本数多时，算法的效率比较低。
2、KD树 (kd_tree)：
首先对训练数据进行建模，构建KD树，然后根据建好的模型来获取邻近样本数据。
后续内容会介绍KD树搜索最小值的方式，让大家直观感受到KD树比蛮力实现要少检索多少数据。
❸ KNN算法常见问题总结
给定测试实例，基于某种距离度量找出训练集中与其最靠近的k个实例点，然后基于这k个最近邻的信息来进行预测。
通常，在分类任务中可使用“投票法”，即选择这k个实例中出现最多的标记类别作为预测结果；在回归任务中可使用“平均法”，即将这k个实例的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的实例权重越大。
k近邻法不具有显式的学习过程，事实上，它是懒惰学习（lazy learning）的着名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。
KNN一般采用欧氏距离，也可采用其他距离度量，一般的Lp距离：
KNN中的K值选取对K近邻算法的结果会产生重大影响。如果选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差（近似误差：可以理解为对现有训练集的训练误差）会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法来选择最优的K值。经验规则：k一般低于训练样本数的平方根
1、计算测试对象到训练集中每个对象的距离
2、按照距离的远近排序
3、选取与当前测试对象最近的k的训练对象，作为该测试对象的邻居
4、统计这k个邻居的类别频率
5、k个邻居里频率最高的类别，即为测试对象的类别
输入X可以采用BallTree或KDTree两种数据结构，优化计算效率，可以在实例化KNeighborsClassifier的时候指定。
KDTree
基本思想是，若A点距离B点非常远，B点距离C点非常近， 可知A点与C点很遥远，不需要明确计算它们的距离。 通过这样的方式，近邻搜索的计算成本可以降低为O[DNlog(N)]或更低。 这是对于暴力搜索在大样本数N中表现的显着改善。KD 树的构造非常快，对于低维度 (D<20) 近邻搜索也非常快, 当D增长到很大时，效率变低： 这就是所谓的 “维度灾难” 的一种体现。
KD 树是一个二叉树结构，它沿着数据轴递归地划分参数空间，将其划分为嵌入数据点的嵌套的各向异性区域。 KD 树的构造非常快：因为只需沿数据轴执行分区, 无需计算D-dimensional 距离。 一旦构建完成, 查询点的最近邻距离计算复杂度仅为O[log(N)]。 虽然 KD 树的方法对于低维度 (D<20) 近邻搜索非常快, 当D增长到很大时, 效率变低。
KD树的特性适合使用欧氏距离。
BallTree
BallTree解决了KDTree在高维上效率低下的问题，这种方法构建的树要比 KD 树消耗更多的时间，但是这种数据结构对于高结构化的数据是非常有效的， 即使在高维度上也是一样。
KD树是依次对K维坐标轴，以中值切分构造的树；ball tree 是以质心C和半径r分割样本空间，每一个节点是一个超球体。换句简单的话来说，对于目标空间(q, r)，所有被该超球体截断的子超球体内的所有子空间都将被遍历搜索。
BallTree通过使用三角不等式减少近邻搜索的候选点数:|x+y|<=|x|+|y|通过这种设置, 测试点和质心之间的单一距离计算足以确定距节点内所有点的距离的下限和上限. 由于 ball 树节点的球形几何, 它在高维度上的性能超出 KD-tree, 尽管实际的性能高度依赖于训练数据的结构。
BallTree适用于更一般的距离。
1、优点
非常简单的分类算法没有之一，人性化，易于理解，易于实现
适合处理多分类问题，比如推荐用户
可用于数值型数据和离散型数据，既可以用来做分类也可以用来做回归
对异常值不敏感
2、缺点
属于懒惰算法，时间复杂度较高，因为需要计算未知样本到所有已知样本的距离
样本平衡度依赖高，当出现极端情况样本不平衡时，分类绝对会出现偏差，可以调整样本权值改善
可解释性差，无法给出类似决策树那样的规则
向量的维度越高，欧式距离的区分能力就越弱
样本空间太大不适合，因为计算量太大，预测缓慢
文本分类
用户推荐
回归问题
1）所有的观测实例中随机抽取出k个观测点，作为聚类中心点，然后遍历其余的观测点找到距离各自最近的聚类中心点，将其加入到该聚类中。这样，我们就有了一个初始的聚类结果，这是一次迭代的过程。
2）我们每个聚类中心都至少有一个观测实例，这样，我们可以求出每个聚类的中心点（means），作为新的聚类中心，然后再遍历所有的观测点，找到距离其最近的中心点，加入到该聚类中。然后继续运行2）。
3）如此往复2），直到前后两次迭代得到的聚类中心点一模一样。
本算法的时间复杂度：O(tkmn)，其中，t为迭代次数，k为簇的数目，m为记录数，n为维数；
空间复杂度：O((m+k)n)，其中，k为簇的数目，m为记录数，n为维数。
适用范围：
K-menas算法试图找到使平凡误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tkmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。
1）首先，算法只能找到局部最优的聚类，而不是全局最优的聚类。而且算法的结果非常依赖于初始随机选择的聚类中心的位置。我们通过多次运行算法，使用不同的随机生成的聚类中心点运行算法，然后对各自结果C通过evaluate(C)函数进行评估，选择多次结果中evaluate(C)值最小的那一个。k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远
2）关于初始k值选择的问题。首先的想法是，从一个起始值开始，到一个最大值，每一个值运行k-means算法聚类，通过一个评价函数计算出最好的一次聚类结果，这个k就是最优的k。我们首先想到了上面用到的evaluate(C)。然而，k越大，聚类中心越多，显然每个观测点距离其中心的距离的平方和会越小，这在实践中也得到了验证。第四节中的实验结果分析中将详细讨论这个问题。
3）关于性能问题。原始的算法，每一次迭代都要计算每一个观测点与所有聚类中心的距离。有没有方法能够提高效率呢？是有的，可以使用k-d tree或者ball tree这种数据结构来提高算法的效率。特定条件下，对于一定区域内的观测点，无需遍历每一个观测点，就可以把这个区域内所有的点放到距离最近的一个聚类中去。这将在第三节中详细地介绍。
相似点：都包含这样的过程，给定一个点，在数据集中找离它最近的点。即二者都用到了NN(Nears Neighbor)算法，一般用KD树来实现NN。
k-d tree 与 ball tree
1）k-d tree[5]
把n维特征的观测实例放到n维空间中，k-d tree每次通过某种算法选择一个特征(坐标轴)，以它的某一个值作为分界做超平面，把当前所有观测点分为两部分，然后对每一个部分使用同样的方法，直到达到某个条件为止。
上面的表述中，有几个地方下面将会详细说明：（1）选择特征（坐标轴）的方法 （2）以该特征的哪一个为界 （3）达到什么条件算法结束。
(1)选择特征的方法
计算当前观测点集合中每个特征的方差，选择方差最大的一个特征，然后画一个垂直于这个特征的超平面将所有观测点分为两个集合。
（2)以该特征的哪一个值为界 即垂直选择坐标轴的超平面的具体位置。
第一种是以各个点的方差的中值（median）为界。这样会使建好的树非常地平衡，会均匀地分开一个集合。这样做的问题是，如果点的分布非常不好地偏斜的，选择中值会造成连续相同方向的分割，形成细长的超矩形(hyperrectangles)。
替代的方法是计算这些点该坐标轴的平均值，选择距离这个平均值最近的点作为超平面与这个坐标轴的交点。这样这个树不会完美地平衡，但区域会倾向于正方地被划分，连续的分割更有可能在不同方向上发生。
（3）达到什么条件算法结束
实际中，不用指导叶子结点只包含两个点时才结束算法。你可以设定一个预先设定的最小值，当这个最小值达到时结束算法。
图6中，星号标注的是目标点，我们在k-d tree中找到这个点所处的区域后，依次计算此区域包含的点的距离，找出最近的一个点（黑色点），如果在其他region中还包含更近的点则一定在以这两个点为半径的圆中。假设这个圆如图中所示包含其他区域。先看这个区域兄弟结点对应区域，与圆不重叠；再看其双亲结点的兄弟结点对应区域。从它的子结点对应区域中寻找（图中确实与这个双亲结点的兄弟结点的子结点对应区域重叠了）。在其中找是否有更近的结点。
k-d tree的优势是可以递增更新。新的观测点可以不断地加入进来。找到新观测点应该在的区域，如果它是空的，就把它添加进去，否则，沿着最长的边分割这个区域来保持接近正方形的性质。这样会破坏树的平衡性，同时让区域不利于找最近邻。我们可以当树的深度到达一定值时重建这棵树。
然而，k-d tree也有问题。矩形并不是用到这里最好的方式。偏斜的数据集会造成我们想要保持树的平衡与保持区域的正方形特性的冲突。另外，矩形甚至是正方形并不是用在这里最完美的形状，由于它的角。如果图6中的圆再大一些，即黑点距离目标点点再远一些，圆就会与左上角的矩形相交，需要多检查一个区域的点，而且那个区域是当前区域双亲结点的兄弟结点的子结点。
为了解决上面的问题，我们引入了ball tree。
2）ball tree[4]
解决上面问题的方案就是使用超球面而不是超矩形划分区域。使用球面可能会造成球面间的重叠，但却没有关系。ball tree就是一个k维超球面来覆盖这些观测点，把它们放到树里面。图7（a)显示了一个2维平面包含16个观测实例的图,图7（b）是其对应的ball tree，其中结点中的数字表示包含的观测点数。
不同层次的圆被用不同的风格画出。树中的每个结点对应一个圆，结点的数字表示该区域保含的观测点数，但不一定就是图中该区域囊括的点数，因为有重叠的情况，并且一个观测点只能属于一个区域。实际的ball tree的结点保存圆心和半径。叶子结点保存它包含的观测点。
使用ball tree时，先自上而下找到包含target的叶子结点，从此结点中找到离它最近的观测点。这个距离就是最近邻的距离的上界。检查它的兄弟结点中是否包含比这个上界更小的观测点。方法是：如果目标点距离兄弟结点的圆心的距离大于这个圆的圆心加上前面的上界的值，则这个兄弟结点不可能包含所要的观测点。（如图8）否则，检查这个兄弟结点是否包含符合条件的观测点。
那么，ball tree的分割算法是什么呢？
选择一个距离当前圆心最远的观测点i1，和距离i1最远的观测点 i2，将圆中所有离这两个点最近的观测点都赋给这两个簇的中心，然后计算每一个簇的中心点和包含所有其所属观测点的最小半径。对包含n个观测点的超圆进行分割，只需要线性的时间。
与k-d tree一样，如果结点包含的观测点到达了预先设定的最小值，这个顶点就可以不再分割了。
❹ KNN-分类算法
KNN，K-NearestNeighbor，即K个最近的邻居的意思。对于一个输入样本，用特征上最接近它的K个临近值大多数属于的标签来对它进行分类。KNN是最简单的机器学习算法之一，可以用于分类和回归，是一种监督学习算法。
具体实现过程如下：
①准备数据，对数据进行预处理
在已经分好类的情况下，我们需要对没有分类的物品进行分类 。
②计算测试样本点（也就是待分类点）到其他每个样本点的距离。
其实就是计算（x1,y1）和（x2,y2）的距离。拓展到多维空间，则公式变成这样：
k值是KNN算法的一个参数，K的含义即参考”邻居“标签值的个数。
如果当K的取值过小时，一旦有噪声得成分存在们将会对预测产生比较大影响，例如取K值为1时，一旦最近的一个点是噪声，那么就会出现偏差，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
如果K的值取的过大时，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大。这时与输入目标点较远实例也会对预测起作用，使预测发生错误。K值的增大就意味着整体的模型变得简单；
如果K==N的时候，那么就是取全部的实例，即为取实例中某分类下最多的点，就对预测没有什么实际的意义了
在划分好数据集后，我们可以通过交叉验证法来得到最佳的K值
优点：
1.无数据输入假定，在分类完的情况下进行测试
2.预测精度高
3.对异常值不敏感
缺点：
1.时间复杂度和空间复杂度高，计算到每一个点的距离，计算量较大
2.当样本不平衡的时候，比如一个类的样本容量大，另一个类的样本容量很小，对于测试识别的样本来说，投票结果更容易靠近样本容量大的类，从而导致分类错误
❺ KNN 算法-理论篇-如何给电影进行分类
KNN 算法 的全称是 K-Nearest Neighbor ，中文为 K 近邻 算法，它是基于 距离 的一种算法，简单有效。
KNN 算法 即可用于分类问题，也可用于回归问题。
假如我们统计了一些 电影数据，包括电影名称，打斗次数，接吻次数，电影类型 ，如下：
可以看到，电影分成了两类，分别是动作片和爱情片。
如果现在有一部新的电影A，它的打斗和接吻次数分别是80 和7，那如何用KNN 算法对齐进行分类呢？
我们可以将打斗次数作为 X 轴 ，接吻次数作为 Y 轴 ，将上述电影数据画在一个坐标系中，如下：
通过上图可以直观的看出，动作电影与爱情电影的分布范围是不同的。
KNN 算法 基于距离，它的原理是： 选择与待分类数据最近的K 个点，这K 个点属于哪个分类最多，那么待分类数据就属于哪个分类 。
所以，要判断电影A 属于哪一类电影，就要从已知的电影样本中，选出距离电影A 最近的K 个点：
比如，我们从样本中选出三个点（即 K 为 3），那么距离电影A 最近的三个点是《功夫》，《黑客帝国》和《战狼》，而这三部电影都是动作电影。因此，可以判断电影A 也是动作电影。
另外，我们还要处理两个问题：
关于点之间的距离判断，可以参考文章 《计算机如何理解事物的相关性》 。
至于K 值的选择，K 值较大或者较小都会对模型的训练造成负面影响，K 值较小会造成 过拟合 ，K 值较大 欠拟合 。
因此，K 值的选择，一般采用 交叉验证 的方式。
交叉验证的思路是，把样本集中的大部分样本作为训练集，剩余部分用于预测，来验证分类模型的准确度。一般会把 K 值选取在较小范围内，逐一尝试K 的值，当模型准确度最高时，就是最合适的K 值。
可以总结出， KNN 算法 用于分类问题时，一般的步骤是：
如果，我们现在有一部电影B，知道该电影属于动作电影，并且知道该电影的接吻次数是 7 ，现在想预测该电影的打斗次数是多少？
这个问题就属于 回归问题 。
首先看下，根据已知数据，如何判断出距离电影B 最近的K 个点。
我们依然设置K 为3，已知数据为：
根据已知数据可以画出下图：
图中我画出了一条水平线，这条线代表所有接吻次数是7 的电影，接下来就是要找到距离 这条线 最近的三部（K 为 3）动作电影。
可以看到，距离这条水平线最近的三部动作电影是《功夫》，《黑客帝国》和《战狼》，那么这三部电影的打斗次数的平均值，就是我们预测的电影B 的打斗次数。
所以，电影B 的打斗次数是：
本篇文章主要介绍了 KNN 算法 的基本原理，它简单易懂，即可处理分类问题，又可处理回归问题。
KNN 算法 是基于 距离 的一种机器学习算法，需要计算测试点与样本点之间的距离。因此，当数据量大的时候，计算量就会非常庞大，需要大量的存储空间和计算时间。
另外，如果样本数据分类不均衡，比如有些分类的样本非常少，那么该类别的分类准确率就会很低。因此，在实际应用中，要特别注意这一点。
（本节完。）
推荐阅读：
决策树算法-理论篇-如何计算信息纯度
决策树算法-实战篇-鸢尾花及波士顿房价预测
朴素贝叶斯分类-理论篇-如何通过概率解决分类问题
朴素贝叶斯分类-实战篇-如何进行文本分类
计算机如何理解事物的相关性-文档的相似度判断
❻ knn算法如何选择一个最佳k值
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
❼ 02 KNN算法 - KD Tree
KD Tree 是KNN算法中用于计算最近邻的快速简便的构建方式。
当样本量少的时候，用 brute 直接搜索最近邻的方式是可行的。即计算到所有样本的距离。但当样本量庞大时，直接计算所有样本距离的工作量很大，这种情况使用 KD Tree 可以节约大量时间成本。
KD树采用从m个样本的n维特征中，分别计算n个特征取值的方差，用 方差最大 的第k维特征n k 作为 根节点 。对于这个特征，选择取值中的 中位数 n kv 作为样本的划分点，对于小于该值的样本划分到 左子树 ，对于大于等于该值的样本划分到 右子树 ，对左右子树采用同样的方式找 方差最大的特征 作为 根节点 ，递归产生KD Tree。
为什么要选择方差最大的进行划分？
构建树的目的是加快我的搜索过程。
既然我想加快我的搜索过程，要就意味着我最终的数据落在某个叶子节点上。我希望只需搜索整个二叉树的某一些列即可，那么最好的划分方式，就是让我的每个分支上数据的差异性最大化。
那么衡量数据差异性的最基础的数学指标是什么？
是方差。方差越大，意味着数据的离散程度就越大，我将离散程度由大到小的数据一分为二，方差小意味着数据更集中到了一起。
现在有一个二维样本: {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
1、计算x1和x2每一列对应的方差
a、通过pandas计算出的是 样本方差:
/ (n-1)
0| 6.966667
1| 5.366667
dtype: float64
b、通过numpy计算出的是 总体方差:
/ n
[[2 3]
[5 4]
[9 6]
[4 7]
[8 1]
[7 2]]
[ 5.80555556 4.47222222]
[ 5.80555556 4.47222222]
第一个树的划分：基于x 1 进行划分
[2,4,5,7,8,9]的中位数是5和7的平均值6。
虽然严格意义上说中位数是6，但是在计算机中我们人为得定义x 1 的中位数是7。
左侧：（2,3）（5,4）（4,7） （7,2）
右侧: （9,6）（8,1）
第二个树的划分：根据右侧（9,6）（8,1）的x 2 进行划分
下侧：x 2 ≤ 6；上侧x 2 ＞6
第二个树的划分：根据左侧（2,3）（5,4）（4,7） （7,2）的x 2 进行划分
寻找2、3、4、7的中位数 4 进行划分
....
注意：每次生成的划分都是一个矩形。当叶子节点无法被继续划分的时候，KD树的构建完成，递归结束。
我们生成了KD Tree后，现在就可以去预测测试集里面的样本目标点了。
1、对于一个目标点，先在KD树里找到包含目标点的叶子节点。
2、以目标点为圆心，以 目标点 到 叶子节点样本实例 的距离为半径，得到一个超球体，最近邻的点一定在这个超球体内部。
3、然后返回叶子节点的父节点，检查另一个子节点包含的超矩形体是否和超球体相交。
4、如果相交就倒这个子节点寻找着是否有更加近的近邻，有的话就更新最近邻。
5、如果不相交，直接返回父节点中的父节点，在另一个子树继续搜索最近邻。当回溯到根节点时，算法结束。
6、此时保存的最近邻节点就是最终的最近邻。
如果现在想找(2,4.5)这点的最近邻，该如何操作？
1、画出二叉树：
2、寻找(2,4.5)这点：
一个比较好的理解方式：首先找到第一个最近邻，然后画出一个圆。然后逐渐收缩圆的半径，查看每次缩小后的圆是否能够和矩形相交于一个更小的最近邻点，如果有则更新。直到回到根节点。
❽ 为什么k临近算法不能处理特征很多的数据集
机器学习中常常要用到分类算法，在诸多的分类算法中有一种算法名为k-近邻算法，也称为kNN算法。
一、kNN算法的工作原理
二、适用情况
三、算法实例及讲解
---1.收集数据
---2.准备数据
---3.设计算法分析数据
---4.测试算法
一、kNN算法的工作原理
官方解释：存在一个样本数据集，也称作训练样本集，并且样本中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系，输入没有标签的新数据后，将新数据的每个特征与样本集中的数据对应的特征进行比较，然后算法提取样本集中特征最相似的数据（最近邻）的分类标签。一般来说，我们只选择样本集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数，最后，选择k个最相似的数据中出现次数最多的分类，作为新数据的分类。
我的理解：k-近邻算法就是根据“新数据的分类取决于它的邻居”进行的，比如邻居中大多数都是退伍军人，那么这个人也极有可能是退伍军人。而算法的目的就是先找出它的邻居，然后分析这几位邻居大多数的分类，极有可能就是它本省的分类。
二、适用情况
优点：精度高，对异常数据不敏感（你的类别是由邻居中的大多数决定的，一个异常邻居并不能影响太大），无数据输入假定；
缺点：计算发杂度高（需要计算新的数据点与样本集中每个数据的“距离”，以判断是否是前k个邻居），空间复杂度高（巨大的矩阵）；
适用数据范围：数值型（目标变量可以从无限的数值集合中取值）和标称型（目标变量只有在有限目标集中取值）。
❾ 模型效果评价
目录：
数据拆分：训练数据集&测试数据集
分类模型评价指标：精准度、混淆矩阵、精准率、召回率、F1 Score、ROC曲线等
回归模型评价指标：MSE、RMSE、MAE、R Squared
聚类模型评价指标：兰德指数、互信息、轮廓系数
数据拆分
目的：训练数据和测试数据分别用来训练模型和测试模型预测效果。
拆分原则：一般按照8:2的比例进行拆分，80%的数据用于训练，20%的数据用来预测；
将规则排列的数据先shuffle打散之后再分割；
超参数：在机器学习算法模型执行之前需要指定的参数。（调参调的就是超参数） 如kNN算法中的k。
模型参数：算法过程中学习的属于这个模型的参数（kNN中没有模型参数，回归算法有很多模型参数）。
如何选择最佳的超参数，这是机器学习中的一个永恒的问题。在实际业务场景中，调参的难度大很多，一般我们会业务领域知识、经验数值、实验搜索等方面获得最佳参数。
评价分类结果：精准度、混淆矩阵、精准率、召回率、F1 Score、ROC曲线、AUC、PR曲线。
1、混淆矩阵
混淆矩阵是监督学习中的一种可视化工具，主要用于比较分类结果和实例的真实信息。矩阵中的每一行代表实例的预测类别，每一列代表实例的真实类别。
真正(True Positive , TP)：被模型预测为正的正样本。
假正(False Positive , FP)：被模型预测为正的负样本。
假负(False Negative , FN)：被模型预测为负的正样本。
真负(True Negative , TN)：被模型预测为负的负样本。
真正率(True Positive Rate,TPR)：TPR=TP/(TP+FN)，即被预测为正的正样本数 /正样本实际数。
假正率(False Positive Rate,FPR) ：FPR=FP/(FP+TN)，即被预测为正的负样本数 /负样本实际数。
假负率(False Negative Rate,FNR) ：FNR=FN/(TP+FN)，即被预测为负的正样本数 /正样本实际数。
真负率(True Negative Rate,TNR)：TNR=TN/(TN+FP)，即被预测为负的负样本数 /负样本实际数/2
2、准确率（Accuracy）
准确率是最常用的分类性能指标。
Accuracy = (TP+TN)/(TP+FN+FP+TN)
即正确预测的正反例数 /总数
3、精确率（Precision）
精确率容易和准确率被混为一谈。其实，精确率只是针对预测正确的正样本而不是所有预测正确的样本。表现为预测出是正的里面有多少真正是正的。可理解为查准率。
Precision = TP/(TP+FP)
即正确预测的正例数 /预测正例总数
4、召回率（Recall）
召回率表现出在实际正样本中，分类器能预测出多少。与真正率相等，可理解为查全率。
Recall = TP/(TP+FN)，即正确预测的正例数 /实际正例总数
5、F1 score
F值是精确率和召回率的调和值，更接近于两个数较小的那个，所以精确率和召回率接近时，F值最大。很多推荐系统的评测指标就是用F值的。
2/F1 = 1/Precision + 1/Recall
6、ROC曲线
逻辑回归里面，对于正负例的界定，通常会设一个阈值，大于阈值的为正类，小于阈值为负类。如果我们减小这个阀值，更多的样本会被识别为正类，提高正类的识别率，但同时也会使得更多的负类被错误识别为正类。为了直观表示这一现象，引入ROC。根据分类结果计算得到ROC空间中相应的点，连接这些点就形成ROC curve，横坐标为False Positive Rate(FPR假正率)，纵坐标为True Positive Rate(TPR真正率)。一般情况下，这个曲线都应该处于(0,0)和(1,1)连线的上方
ROC曲线中的四个点和一条线:
点(0,1)：即FPR=0, TPR=1，意味着FN＝0且FP＝0，将所有的样本都正确分类。
点(1,0)：即FPR=1，TPR=0，最差分类器，避开了所有正确答案。
点(0,0)：即FPR=TPR=0，FP＝TP＝0，分类器把每个实例都预测为负类。
点(1,1)：分类器把每个实例都预测为正类。
总之：ROC曲线越接近左上角，该分类器的性能越好。而且一般来说，如果ROC是光滑的，那么基本可以判断没有太大的overfitting
7、AUC
AUC（Area Under Curve）被定义为ROC曲线下的面积(ROC的积分)，通常大于0.5小于1。随机挑选一个正样本以及一个负样本，分类器判定正样本的值高于负样本的概率就是 AUC 值。AUC值(面积)越大的分类器，性能越好。
8、PR曲线
PR曲线的横坐标是精确率P，纵坐标是召回率R。评价标准和ROC一样，先看平滑不平滑（蓝线明显好些）。一般来说，在同一测试集，上面的比下面的好（绿线比红线好）。当P和R的值接近时，F1值最大，此时画连接(0,0)和(1,1)的线，线和PRC重合的地方的F1是这条线最大的F1（光滑的情况下），此时的F1对于PRC就好像AUC对于ROC一样。一个数字比一条线更方便调型。
有时候模型没有单纯的谁比谁好（比如图二的蓝线和青线），所以选择模型还是要结合具体的使用场景。下面是两个场景：1，地震的预测 对于地震的预测，我们希望的是RECALL非常高，也就是说每次地震我们都希望预测出来。这个时候我们可以牺牲PRECISION。情愿发出1000次警报，把10次地震都预测正确了，也不要预测100次对了8次漏了两次。2，嫌疑人定罪 基于不错怪一个好人的原则，对于嫌疑人的定罪我们希望是非常准确的。即时有时候放过了一些罪犯（recall低），但也是值得的。
对于分类器来说，本质上是给一个概率，此时，我们再选择一个CUTOFF点（阀值），高于这个点的判正，低于的判负。那么这个点的选择就需要结合你的具体场景去选择。反过来，场景会决定训练模型时的标准，比如第一个场景中，我们就只看RECALL=99.9999%（地震全中）时的PRECISION，其他指标就变得没有了意义。
当正负样本数量差距不大的情况下，ROC和PR的趋势是差不多的，但是在正负样本分布极不均衡的情况下，PRC比ROC更能真实的反映出实际情况，因为此时ROC曲线看起来似乎很好，但是却在PR上效果一般。
评价回归结果：MSE、RMSE、MAE、R Squared。
回归问题用到的衡量指标相对直观。假设yiyi是第ii个样本的真实值，ŷiy^i是对第ii个样本的预测值。
1. 平均绝对误差（MAE）
平均绝对误差MAE（Mean Absolute Error）又被称为l1范数损失（l1-norm loss）：
2. 平均平方误差（MSE）
平均平方误差MSE（Mean Squared Error）又被称为l2范数损失（l2-norm loss）：
3、均方根误差（RMSE）
RMSE虽然广为使用，但是其存在一些缺点，因为它是使用平均误差，而平均值对异常点（outliers）较敏感，如果回归器对某个点的回归值很不理性，那么它的误差则较大，从而会对RMSE的值有较大影响，即平均值是非鲁棒的。
4、解释变异
解释变异（ Explained variance）是根据误差的方差计算得到的：
5、决定系数
决定系数（Coefficient of determination）又被称为R2分数：
三、聚类模型评价
1 . 兰德指数
兰德指数（Rand index）需要给定实际类别信息C，假设K是聚类结果，a表示在C与K中都是同类别的元素对数，b表示在C与K中都是不同类别的元素对数，则兰德指数为：
其中数据集中可以组成的总元素对数，RI取值范围为[0,1]，值越大意味着聚类结果与真实情况越吻合。
对于随机结果，RI并不能保证分数接近零。为了实现“在聚类结果随机产生的情况下，指标应该接近零”，调整兰德系数（Adjusted rand index）被提出，它具有更高的区分度：
ARI取值范围为[−1,1]，值越大意味着聚类结果与真实情况越吻合。从广义的角度来讲，ARI衡量的是两个数据分布的吻合程度。
2. 互信息
互信息（Mutual Information）也是用来衡量两个数据分布的吻合程度。假设UU与VV是对NN个样本标签的分配情况，则两种分布的熵（熵表示的是不确定程度）分别为：
利用基于互信息的方法来衡量聚类效果需要实际类别信息，MI与NMI取值范围为[0,1]，AMI取值范围为[−1,1]，它们都是值越大意味着聚类结果与真实情况越吻合。
3. 轮廓系数
轮廓系数（Silhouette coefficient）适用于实际类别信息未知的情况。对于单个样本，设aa是与它同类别中其他样本的平均距离，bb是与它距离最近不同类别中样本的平均距离，轮廓系数为：
对于一个样本集合，它的轮廓系数是所有样本轮廓系数的平均值。
轮廓系数取值范围是[−1,1]
❿ python网格搜索支持向量回归得分低，为0.003，偶尔还会出现负数，该怎么处理
使用Python编程可以快速迁移代码并进行改动，无须花费过多的精力在修改代码与代码规范上。开发者在Python中封装了很多优秀的依赖库，可以直接拿来使用，常见的机器学习库如下：1、Scikit-LearnScikit-Learn基于Numpy和Scipy，是专门为机器学习建造的一个Python模块，提供了大量用于数据挖掘和分析的工具，包括数据预处理、交叉验证、算法与可视化算法等一系列接口。Scikit-Learn基本功能可分为六个部分：分类、回归、聚类、数据降维、模型选择、数据预处理。其中集成了大量分类、回归、聚类功能，包括支持向量机、逻辑回归、随机森林、朴素贝叶斯等。2、Orange3Orange3是一个基于组件的数据挖掘和机器学习软件套装，支持Python进行脚本开发。它包含一系列的数据可视化、检索、预处理和建模技术，具有一个良好的用户界面，同时也可以作为Python的一个模块使用。用户可通过数据可视化进行数据分析，包含统计分布图、柱状图、散点图，以及更深层次的决策树、分层聚簇、热点图、MDS等，并可使用它自带的各类附加功能组件进行NLP、文本挖掘、构建网络分析等。3、XGBoostXGBoost是专注于梯度提升算法的机器学习函数库，因其优良的学习效果及高效的训练速度而获得广泛的关注。XGBoost支持并行处理，比起同样实现了梯度提升算法的Scikit-Learn库，其性能提升10倍以上。XGBoost可以处理回归、分类和排序等多种任务。4、NuPICNuPIC是专注于时间序列的一个机器学习平台，其核心算法为HTM算法，相比于深度学习，其更为接近人类大脑的运行结构。HTM算法的理论依据主要是人脑中处理高级认知功能的新皮质部分的运行原理。NuPIC可用于预测以及异常检测，使用面非常广，仅要求输入时间序列即可。5、MilkMilk是Python中的一个机器学习工具包。Milk注重提升运行速度与降低内存占用，因此大部分对性能敏感的代码都是使用C++编写的，为了便利性在此基础上提供Python接口。重点提供监督分类方法，如SVMs、KNN、随机森林和决策树等。