K近临算法的优点

1. 实验二 K-近邻算法及应用

（1）简单，易于理解，易于实现，无需估计参数。

（2）训练时间为零。它没有显示的训练，不像其它有监督的算法会用训练集train一个模型（也就是拟合一个函数），然后验证集或测试集用该模型分类。KNN只是把样本保存起来，收到测试数据时再处理，所以KNN训练时间为零。

（3）KNN可以处理分类问题，同时天然可以处理多分类问题，适合对稀有事件进行分类。

（4）特别适合于多分类问题(multi-modal,对象具有多个类别标签)， KNN比SVM的表现要好。

（5）KNN还可以处理回归问题，也就是预测。

（6）和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感。

（1）计算量太大，尤其是特征数非常多的时候。每一个待分类文本都要计算它到全体已知样本的距离，才能得到它的第K个最近邻点。

（2）可理解性差，无法给出像决策树那样的规则。

（3）是慵懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢。

（4）样本不平衡的时候，对稀有类别的预测准确率低。当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。

（5）对训练数据依赖度特别大，对训练数据的容错性太差。如果训练数据集中，有一两个数据是错误的，刚刚好又在需要分类的数值的旁边，这样就会直接导致预测的数据的不准确。

需要一个特别容易解释的模型的时候。
比如需要向用户解释原因的推荐算法。

通过此次实验我了解了K近邻算法及其思路，该方法的思路是：如果一个样本在特征空间中的k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别。
所谓k近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例。

2. k近邻&kd树

k近邻算法是懒惰学习的代表算法。之所以说k近邻懒惰，是因为它没有显示的训练过程。它的思路很简单， 手头有一些带标签的样本，现在给定一个新的样本，找出已有样本中距离新样本最近的k个样本点，然后取这k个样本点标签的投票结果。

k近邻算法本身并不复杂，但有几个细节需要注意：

（1）距离度量

不同的距离度量可能产生不同的k近邻，从而直接影响预测结果。至于度量的选取要结合应用场景， 关键在于我们需要知道在特定场景中如何量化两样本之间的相似度。

（2）k值选择

k值的选择没有经验性的方法，一般只能通过交叉验证来选取合适的k值。

如果k值选择较小，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的训练实例才会对预测起作用，但估计误差会增大，预测结果会对近邻的实例点非常敏感，如果近邻的实例点恰巧是噪声，预测就会出错。相反如果k值选择较大，就相当于用较大的领域中的训练实例进行预测，近似误差会增大，但估计误差会减小。

对于k近邻法来说，k越大模型越简单，这一点乍一看不容易理解，但其实我们可以考虑极端情况k=N（N为样本数），此时任何新样本都会被归入当前样本集中实例最多的类别，从而丢失大量信息。反之，k越小模型越复杂，模型将面临过拟合风险。

（3）投票法

k近邻使用多数表决亮闹的投票法看起来十分自然，但我们也可以从 最小化经验误差 的角度来理解，如果分类的损失函数为0-1损失函数，则误分类概率为：

对于给定实例 ，其最近邻的k个训练实例构成集合 ，若涵盖 的区域的类别是 ，则误分类概率为：

要使误分类率最小即经验风险最小，就要使 最大，这正是投票法（多数表决）所做的事情。

kd树是一种对k维空间中的实例点进行储存以便对其进行快速检索的树形数据结构。 kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断用垂直于坐标轴的超平面将k维空间切分，构成一系列k维超矩形区域。

构造平衡kd树的流程 如下：

输入：k维空间数据集

（1）构造根结点，根结点对应于包含 的k维空间的超矩形区域。

（2）对深度为 的结点，选择 为切分的坐标轴（ ），以该结点区域中所有实例的 坐标的中位数为切分点，将该结点对应的超矩形区域划分为两个子区域，切分由通过切分点并与坐标轴 垂直的超平面实现。

（3）重复（2）直至划分得到的两个子区域中没有实例存在为止。

用kd树进行最近邻搜索的流程 如下：

输入：构造好的kd树，目标节点x

（1）在kd树中找到包含目标节点 的叶结点：从根结点出发，递归地向下访问kd树。若目标 当前维的坐标小于切分点坐标则移动敬物罩到左子结点，否则移动到右子结点，直至子结点为叶结点为止。

（2）以此叶结点为“当前最近点”。

（3）递归地向上回退：

（4）当回退到根结点，搜索结束，此时的“当前最近点”即为 的最近邻点。蚂档

以上就是利用kd树进行最近邻搜索的过程，同样的方法可以推广到k近邻。现在我们来思考一下这个算法的本质。

其实我个人理解的是， kd树的构造就是二分法在k维的应用。 但是不太相同的是，kd树算法并不是选定一个轴后不断二分直至结束，而是做一次二分换一个轴，这是因为如果我们只选定一个轴做二分得到的结果并不能反映各样本之间距离的远近，而兼顾各个轴则能一定程度上度量样本之间的距离。

我们可以想象3维的情况，kd树最终会形成一系列的小正方体，我们要想找距离一个新样本点最近的样本点，只需要找到新样本点所在的小正方体，然后check这个小正方体中的样本以及和这个小正方体 相邻 的小正方体中的样本哪个距离新样本最近即可（相邻这个概念是很重要的，为便于理解，考虑在一维的情况下，此过程为找到新样本所在区间，然后检查此区间以及左右相邻区间中的样本点即可）。而 相邻 这个概念刚好和kd树的构造过程相符，我们不断回退的过程其实就是检查 各个不同方向上 的相邻超矩形的过程。这个过程十分高效，不难看出，平衡kd树寻找最近邻的复杂度是 。

3. 机器学习中算法的优缺点之最近邻算法

机器学习中有个算法是十分重要的，那就是最近邻算法，这种算法被大家称为KNN。我们在学习机器学习知识的时候一定要学习这种算法，其实不管是什么算法都是有自己的优缺点的，KNN算法也不例外，在这篇文章中我们就详细的给大家介绍一下KNN算法的优缺点，大家一定要好好学起来哟。
说到KNN算法我们有必要说一下KNN算法的主要过程，KNN算法的主要过程有四种，第一就是计算训练样本和测试样本中每个样本点的距离，第二个步骤就是对上面所有的距离值进行排序(升序)。第三个步骤就是选前k个最小距离的样本。第四个步骤就是根据这k个样本的标签进行投票，得到最后的分类类别。
那么大家是否知道如何选择一个最佳的K值，这取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响，但会使类别之间的界限变得模糊。一般来说，一个较好的K值可通过各种启发式技术来获取，比如说交叉验证。另外噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。近邻算法具有较强的一致性结果，随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍。对于一些好的K值，K近邻保证错误率不会超过贝叶斯理论误差率。
那么KNN算法的优点是什么呢？KNN算法的优点具体体现在六点，第一就是对数据没有假设，准确度高，对outlier不敏感。第二就是KNN是一种在线技术，新数据可以直接加入数据集而不必进行重新训练。第三就是KNN理论简单，容易实现。第四就是理论成熟，思想简单，既可以用来做分类也可以用来做回归。第五就是可用于非线性分类。第六就是训练时间复杂度为O(n)。由此可见，KNN算法的优点是有很多的。
那么KNN算法的缺点是什么呢？这种算法的缺点具体体现在六点，第一就是样本不平衡时，预测偏差比较大。第二就是KNN每一次分类都会重新进行一次全局运算。第三就是k值大小的选择没有理论选择最优，往往是结合K-折交叉验证得到最优k值选择。第四就是样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）效果差。第五就是需要大量内存。第六就是对于样本容量大的数据集计算量比较大。
正是由于这些优点和缺点，KNN算法应用领域比较广泛，在文本分类、模式识别、聚类分析，多分类领域中处处有KNN算法的身影。
在这篇文章中我们给大家介绍了很多关于KNN算法的相关知识，通过对这些知识的理解相信大家已经知道该算法的特点了吧，希望这篇文章能够帮助大家更好的理解KNN算法。

4. K-近邻算法（K-NN）

给定一个训练数据集，对于新的输入实例， 根据这个实例最近的 k 个实例所属的类别来决定其属于哪一类 。所以相对于其它机器学习模型和算法，k 近邻总体上而言是一种非常简单的方法。

找到与该实例最近邻的实例，这里就涉及到如何找到，即在特征向量空间中，我们要采取 何种方式来对距离进行度量 。

距离的度量用在 k 近邻中我们也可以称之为 相似性度量 ，即特征空间中两个实例点相似程度的反映。在机器学习中，常用的距离度量方式包括欧式距离、曼哈顿距离、余弦距离以及切比雪夫距离等。 在 k 近邻算法中常用的距离度量方式是欧式距离，也即 L2 距离， L2 距离计算公式如下：

一般而言，k 值的大小对分类结果有着重大的影响。 当选择的 k 值较小的情况下，就相当于用较小的邻域中的训练实例进行预测，只有当与输入实例较近的训练实例才会对预测结果起作用。但与此同时预测结果会对实例点非常敏感，分类器抗噪能力较差，因而容易产生过拟合 ，所以一般而言，k 值的选择不宜过小。但如果选择较大的 k 值，就相当于在用较大邻域中的闷郑握训练实例进行预测，但相应的分类误差也会增大，模型整体变得简单，会产生一定程度的欠拟合。所以一般而言，我们需要 采用交叉验证的方式来选择合适的 k 值 。

k 个实例的多数属于哪丛裤个类，明显是多数表决的归类规则。当然还可能使用其他规则，所以第三个关键就是 分类决策规则。

回归：k个实例该属性值的平均值

它是一个二叉树的数据结构，方便存储 K 维空间的数据

KNN 的计算过程是大量计算样本点之间的距离。为了减少计算距离次数，提升 KNN 的搜索效率，人们提出了 KD 树（K-Dimensional 的缩写）。KD 树是对数据点在 K 维空间中划分的一种数据结构。在 KD 树的构造中，每个节点都是 k 维数值点的二叉树。蚂庆既然是二叉树，就可以采用二叉树的增删改查操作，这样就大大提升了搜索效率。

如果是做分类，你需要引用：from sklearn.neihbors import KNeighborsClassifier
如果是回归， 需要引用：from sklearn.neighbors import KNeighborsRegressor

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=None, **kwargs)

5. k近邻算法精确度的提高有什么科学性，先进性和独特之处

K近邻(k-Nearest Neighbour，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
K-近邻法就是一种基于文本特征向量空间模型表示的文本分类方法,有很多优点,算法简单,易于实现,分类精度较高。

6. K-近邻算法简介

1.K-近邻(KNearestNeighbor,KNN)算法简介 ：对于一个未知的样本，我们可以根据离它最近的k个样本的类别来判断它的类别。

以下图为例，对于一个未知样本绿色小圆，我们可以选取离它最近的3的样本，其中包含了2个红色三角形，1个蓝色正方形，那么我们可以判断绿色小圆属于红色三角形这一类。
我们也可以选取离它最近的5个样本，其中包含了3个蓝色正方形，2个红色三角形，那么我们可以判断绿色小圆属于蓝色正方形这一类。

3.API文档

下面我们来对KNN算法中的参数项做一个解释说明：

'n_neighbors'：选取的参考对象的个数（邻居个数），默认值为5，也可以自己指定数值，但不是n_neighbors的值越大分类效果越好，最佳值需要我们做一个验证。
'weights': 距离的权重参数，默认uniform。
'uniform': 均匀的权重，所有的点在每一个类别中的权重是一样的。简单的说，就是每个点的重要性都是一样的。
'distance'：权重与距离的倒数成正比，距离近的点重要性更高，对于结果的影响也更大。
'algorithm':运算方法，默认auto。
'auto'：根绝模型fit的数据自动选择最合适的运算方法。
'ball_tree'：树模型算法BallTree
'kd_tree'：树模型算法KDTree
'brute'：暴力算法
'leaf_size'：叶子的尺寸，默认30。只有当algorithm = 'ball_tree' or 'kd_tree'，这个参数需要设定。
'p'：闵可斯基距离，当p = 1时，选择曼哈顿距离；当p = 2时，选择欧式距离。
n_jobs：使用计算机处理器数目，默认为1。当n=-1时，使用所有的处理器进行运算。

4.应用案例演示
下面以Sklearn库中自带的数据集--手写数字识别数据集为例，来测试下kNN算法。上一章，我们简单的介绍了机器学习的一般步骤：加载数据集 - 训练模型 - 结果预测 - 保存模型。这一章我们还是按照这个步骤来执行。
[手写数字识别数据集] https://scikit-learn.org/stable/moles/generated/sklearn.datasets.load_digits.html#sklearn.datasets.load_digits

5.模型的方法
每一种模型都有一些它独有的属性方法（模型的技能，能做些什么事），下面我们来了解下knn算法常用的的属性方法。

6.knn算法的优缺点
优点：
简单，效果还不错，适合多分类问题
缺点：
效率低（因为要计算预测样本距离每个样本点的距离，然后排序），效率会随着样本量的增加而降低。

7. k近邻算法特征值非数字

k-近邻算法采用测量不同特征值之间的距离来进行分类。
优点：精度高，对异常值不敏感，无数据输入假定。缺点：计算复杂度高、空间复杂度高。适用数据范围：数值型和分类型。原理：首先，我们必须得有一份含有分类标签的数据集，为训练数据集。比如我们要预测用户是否会流失，那么分类标签就是流失和未流失。然后有一份新的数据集，这份数据集并没有分类标签，k-近邻算法就会将新的数据集和训练数据集进行比较，从训练数据集中选出与新数据集每个数据最相近的K个数据，查看这K个数据所属标签哪类最多，比如流失，就把新数据集中的那个数据分类为流失。怎么判断是否相近呢？K-近邻是计算不同数据的距离。k-近邻算法的原理伪代码。
对未知类别属性的数据集中的每个数据点依次执行以下操作：(1)计算已知类别数据集中的点与当前点之间的距离。(2)按照距离递增次序排序。(3)选出与当前距离最近的K个点。(4)统计出K个点所属类别的频率。(5)返回K个点出现频率最高的的类别作为当前点的预测类别

8. k近邻算法中关键的要素是

k近邻算法中关键的要素是：k值的选取、邻居距离的度量和分类决策的制订。

1.k值的选取：

k近邻算法优点很明显，简单易用，可解释性强，但也有其不足之处。例如，“多数表决”会在类别分布偏斜时浮现缺陷。也就是说，k值的选取非常重要，出现频率较多的样本将会主导测试点的预测结果。

3.分类决策的制订：

本质上，分类器就是一个由特征向量，到预测类别的映射函数。k近邻算法的分类流程大致如下三步走：（1）计算待测试样本与训练集合中每一个样本的欧式距离；（2）对每一个距离从小到大排序；（3）选择前k个距离最短的样本，分类任务采用“少数服从多数”的表决规则。回归任务则可采用k个近邻的平均值举茄作为预测值。

9. 什么叫做knn算法

在模式识别领域中，最近邻居法（KNN算法，又译K-近邻算法）是一种用于分类和回归的非参数统计方法。

在这两种情况下，输入包含特征空间（Feature Space）中的k个最接近的训练样本。

1、在k-NN分类中，输出是一个分类族群。一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k=1，则该对象的类别直接由最近的一个节点赋予。

2、在k-NN回归中，输出是该对象的属性值。该值是其k个最近邻居的值的平均值。

最近邻居法采用向量空间模型来分类，概念为相同类别的案例，彼此的相似度高，而可以借由计算与已知类别案例之相似度，来评估未知类别案例可能的分类。

K-NN是一种基于实例的学习，或者是局部近似和将所有计算推迟到分类之后的惰性学习。k-近邻算法是所有的机器学习算法中最简单的之一。

无论是分类还是回归，衡量邻居的权重都非常有用，使较近邻居的权重比较远邻居的权重大。例如，一种常见的加权方案是给每个邻居权重赋值为1/ d，其中d是到邻居的距离。

邻居都取自一组已经正确分类（在回归的情况下，指属性值正确）的对象。虽然没要求明确的训练步骤，但这也可以当作是此算法的一个训练样本集。

k-近邻算法的缺点是对数据的局部结构非常敏感。

K-均值算法也是流行的机器学习技术，其名称和k-近邻算法相近，但两者没有关系。数据标准化可以大大提高该算法的准确性。

参数选择

如何选择一个最佳的K值取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响，但会使类别之间的界限变得模糊。一个较好的K值能通过各种启发式技术（见超参数优化）来获取。

噪声和非相关性特征的存在，或特征尺度与它们的重要性不一致会使K近邻算法的准确性严重降低。对于选取和缩放特征来改善分类已经作了很多研究。一个普遍的做法是利用进化算法优化功能扩展，还有一种较普遍的方法是利用训练样本的互信息进行选择特征。

在二元（两类）分类问题中，选取k为奇数有助于避免两个分类平票的情形。在此问题下，选取最佳经验k值的方法是自助法。

10. k近邻算法是有监督还是无监督

k近邻算法是有监督。

k近邻算法的流程和优点：

k近邻算法的一般流程是：

1、收集数据。

2、计算待测数据与训练数据之间的距离（一般采用欧式距离）。

3、将计算的距离排序。

4、找出距离最小的k个值。

5、计算找出值中每个类别的频次。

6、返回最高频次的类别。

优点：精度高、对异常值不敏感缺点：计算复杂度高、空间复杂度高。K近邻最直接的利用了样本之间的关系，减少了类别特征选择不当对分类结果造成的不利影响，可以最大程度减少分类过程中的做察派误差项。