Knn算法原理 大数据算法:分类算法

knn算法的分类原理是(knearestneighbor(大数据算法):分类算法KNN算法，即K近邻算法，是一种基本的分类算法。KNN算法-4-算法优化-KD树KNN算法的重要步骤是通过K近邻快速搜索所有实例点，算法流程:1，如果使用linearscan，计算输入点和每个点之间的距离是非常耗时的。

K值的选择会对算法的结果产生很大的影响。k值小意味着只有接近输入样本的训练样本才会在预测结果中发挥作用，但容易过拟合；如果k值较大，好处是可以降低学习的估计误差，但坏处是学习的近似误差增大，远离输入样本的训练样本也会在预测中起作用，使预测出错。在实际应用中，k的值一般是一个小值，通常通过交叉验证来选择k的最优值。

给定一个测试用例，基于某种距离度量在训练集中找出最近的K个实例点，然后基于这K个最近邻的信息进行预测。通常在分类任务中可以使用“投票法”，即选取这k个例子中出现频率最高的标签类别作为预测结果；在回归任务中，可以采用“平均法”，即将这k个实例的实值输出标记的平均值作为预测结果；也可以基于距离进行加权平均或加权投票，距离越近，例子的权重越大。

KNN利用各种维度数据的相关性，对数据中缺失或异常的值进行填充和修正。本文讨论的数据集来自于分布在某地的各个站点所测得的空气污染物浓度值随时间的变化记录，在某些地方或某些时刻存在数据缺失。我们知道，在这批数据中，测点的浓度值在距离和时间上是相关的，即空间距离越近，时间越近，测得的值就会越相关，所以可以用KNN算法从经度、纬度和时间三个维度对数据进行处理。上图中，我们没有得到目标点在某一时刻的测量值，但是可以得到它周围的一些测量值。

这样，我们就可以利用现有的数据来估计目标值c_x，其中权重与相邻点和目标点之间的距离成反比。比如我们可以定义实际使用中重量和距离的关系。当使用KNN算法填充数据时，我们需要找到每个样本的相邻点，因此我们需要首先计算不同样本之间的距离。在这里，我们可以使用sklearn.neighbors中的NearestNeighbors来求解NearestNeighbors(。

1简介。K KNearestNeighbor，KNN)算法:对于一个未知样本，我们可以根据最接近的K个样本的类别来判断它的类别。以下图为例。对于未知样本的绿色小圆，我们可以选取最近的样本3，其中包含2个红色三角形和1个蓝色正方形，这样就可以判断绿色小圆属于红色三角形的范畴。我们也可以选取最近的五个样本，包括三个蓝色方块和两个红色三角形，这样就可以判断绿色小圆圈属于蓝色方块的范畴。

KNN算法的重要步骤是通过K个最近邻快速搜索所有的实例点。如果使用linearscan，计算输入点和每个点之间的距离是非常耗时的。因此，kd树可以用来优化查询操作。Kd tree是Kdimensiontree的缩写，是在k维空间(如二维(x，y)，三维(x，y，z)，k维(x1，y，z)划分数据点的数据结构...).主要用于多维空间的关键数据搜索(如范围搜索、最近邻搜索)。

Kdtree是一棵二叉树，它的节点是k维的样本点，它上面的每个样本点代表一个超平面，这个超平面垂直于当前维度的坐标轴，在这个维度上把空间分成两部分，一部分在它的左子树，一部分在它的右子树。即如果当前节点的划分维数为D，则D维左子树上所有点的坐标值小于当前值，D维右子树上所有点的坐标值大于等于当前值。这个定义适用于任何子节点。

k knarestneighbor，kNN)是一种基本的分类和回归方法。它是数据挖掘技术中最简单的算法之一，其核心功能是解决监督分类问题。KNN可以快速高效地解决基于特殊数据集的预测分类问题，但它不产生模型，因此算法的精度不具有高度的普适性。K近邻法的输入是实例的特征向量，对应于特征空间中的点；输出是实例的类别，它可以包含多个类别。

算法过程:1 .计算训练样本中每个样本点与测试样本之间的距离(常见的距离度量有欧氏距离、马氏距离等。);2、对上述所有距离值进行排序；3、选择距离最小的前k个样本；4、根据K个样本的标签进行投票，得到最终的分类类别；输入:训练数据集T \\ \\ {(x _ 1，y _ 1)，(x _ 1，y _ 1)，\\ \\ cdots，(x _ n，y _ n) \\ \\ \\}其中x_i是实例的特征向量，y_i是实例的类别，i1，

KNN算法，即K近邻算法，是一种基本的分类算法。主要原理是:对于一个需要分类的数据，与一组已经分类标注的样本进行比较，得到最接近的k个样本，这k个样本最所属的类别就是需要分类的类别。下面我给你画一个KNN算法的示意图。图中红蓝绿点是样本数据，分属于三类。

KNN的算法流程也很简单，请看下面的流程图。KNN算法是一种非常简单实用的分类算法，可以用于各种分类场景，比如新闻分类、商品分类，甚至简单的文本识别。对于新闻分类，可以提前人工标注一些新闻，标注好新闻类别，计算好特征向量。对于一条未分类的新闻，在计算其特征向量后，计算其与所有已标记新闻的距离，然后进一步使用KNN算法进行自动分类。

如果特征空间中k个最相似样本的大部分属于某一类别，则该样本也属于该类别。这种方法只根据分类决策中最近的一个或几个样本的类别来确定待分类样本的类别。看下图:KNN的算法流程如下:从上图我们可以看到，图中的数据集是好数据，也就是所有的数据集都有标签，一个是蓝色的正方形，一个是红色的三角形，绿色的圆圈是我们要分类的数据。

k值的选取、距离的度量和分类决策规则。(1)k值的选择，(在应用中，k的取值一般选择一个相对较小的值，一般选择交叉验证得到k的最优值)(2)距离测量。(Lp距离:将误差的绝对值求和到p的幂，然后求p的根)，欧几里德距离:p2的Lp距离。曼哈顿距离:p1的Lp距离，当p为无穷大时，Lp距离为各维中的最大距离)(3)分类决策规则。(即如何根据k个最近邻确定待测对象的分类。