k近邻算法与局部回归

A. 实验二 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个实例。

B. 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)

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

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

1.k值的选取：

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

3.分类决策的制订：

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

D. 机器学习一般常用的算法有哪些

机器学习是人工智能的核心技术，是学习人工智能必不可少的环节。机器学习中有很多算法，能够解决很多以前难以企的问题，机器学习中涉及到的算法有不少，下面小编就给大家普及一下这些算法。

一、线性回归

一般来说，线性回归是统计学和机器学习中最知名和最易理解的算法之一。这一算法中我们可以用来预测建模，而预测建模主要关注最小化模型误差或者尽可能作出最准确的预测，以可解释性为代价。我们将借用、重用包括统计学在内的很多不同领域的算法，并将其用于这些目的。当然我们可以使用不同的技术从数据中学习线性回归模型，例如用于普通最小二乘法和梯度下降优化的线性代数解。就目前而言，线性回归已经存在了200多年，并得到了广泛研究。使用这种技术的一些经验是尽可能去除非常相似（相关）的变量，并去除噪音。这是一种快速、简单的技术。

二、Logistic 回归

它是解决二分类问题的首选方法。Logistic 回归与线性回归相似，目标都是找到每个输入变量的权重，即系数值。与线性回归不同的是，Logistic 回归对输出的预测使用被称为 logistic 函数的非线性函数进行变换。logistic 函数看起来像一个大的S，并且可以将任何值转换到0到1的区间内。这非常实用，因为我们可以规定logistic函数的输出值是0和1并预测类别值。像线性回归一样，Logistic 回归在删除与输出变量无关的属性以及非常相似的属性时效果更好。它是一个快速的学习模型，并且对于二分类问题非常有效。

三、线性判别分析（LDA）

在前面我们介绍的Logistic 回归是一种分类算法，传统上，它仅限于只有两类的分类问题。而LDA的表示非常简单直接。它由数据的统计属性构成，对每个类别进行计算。单个输入变量的 LDA包括两个，第一就是每个类别的平均值，第二就是所有类别的方差。而在线性判别分析，进行预测的方法是计算每个类别的判别值并对具备最大值的类别进行预测。该技术假设数据呈高斯分布，因此最好预先从数据中删除异常值。这是处理分类预测建模问题的一种简单而强大的方法。

四、决策树

决策树是预测建模机器学习的一种重要算法。决策树模型的表示是一个二叉树。这是算法和数据结构中的二叉树，没什么特别的。每个节点代表一个单独的输入变量x和该变量上的一个分割点。而决策树的叶节点包含一个用于预测的输出变量y。通过遍历该树的分割点，直到到达一个叶节点并输出该节点的类别值就可以作出预测。当然决策树的有点就是决策树学习速度和预测速度都很快。它们还可以解决大量问题，并且不需要对数据做特别准备。

五、朴素贝叶斯

其实朴素贝叶斯是一个简单但是很强大的预测建模算法。而这个模型由两种概率组成，这两种概率都可以直接从训练数据中计算出来。第一种就是每个类别的概率，第二种就是给定每个 x 的值，每个类别的条件概率。一旦计算出来，概率模型可用于使用贝叶斯定理对新数据进行预测。当我们的数据是实值时，通常假设一个高斯分布，这样我们可以简单的估计这些概率。而朴素贝叶斯之所以是朴素的，是因为它假设每个输入变量是独立的。这是一个强大的假设，真实的数据并非如此，但是，该技术在大量复杂问题上非常有用。所以说，朴素贝叶斯是一个十分实用的功能。

六、K近邻算法

K近邻算法简称KNN算法，KNN 算法非常简单且有效。KNN的模型表示是整个训练数据集。KNN算法在整个训练集中搜索K个最相似实例（近邻）并汇总这K个实例的输出变量，以预测新数据点。对于回归问题，这可能是平均输出变量，对于分类问题，这可能是众数类别值。而其中的诀窍在于如何确定数据实例间的相似性。如果属性的度量单位相同，那么最简单的技术是使用欧几里得距离，我们可以根据每个输入变量之间的差值直接计算出来其数值。当然，KNN需要大量内存或空间来存储所有数据，但是只有在需要预测时才执行计算。我们还可以随时更新和管理训练实例，以保持预测的准确性。

七、Boosting 和 AdaBoost

首先，Boosting 是一种集成技术，它试图集成一些弱分类器来创建一个强分类器。这通过从训练数据中构建一个模型，然后创建第二个模型来尝试纠正第一个模型的错误来完成。一直添加模型直到能够完美预测训练集，或添加的模型数量已经达到最大数量。而AdaBoost 是第一个为二分类开发的真正成功的 boosting 算法。这是理解 boosting 的最佳起点。现代 boosting 方法建立在 AdaBoost 之上，最显着的是随机梯度提升。当然，AdaBoost 与短决策树一起使用。在第一个决策树创建之后，利用每个训练实例上树的性能来衡量下一个决策树应该对每个训练实例付出多少注意力。难以预测的训练数据被分配更多权重，而容易预测的数据分配的权重较少。依次创建模型，每一个模型在训练实例上更新权重，影响序列中下一个决策树的学习。在所有决策树建立之后，对新数据进行预测，并且通过每个决策树在训练数据上的精确度评估其性能。所以说，由于在纠正算法错误上投入了太多注意力，所以具备已删除异常值的干净数据十分重要。

八、学习向量量化算法（简称 LVQ）

学习向量量化也是机器学习其中的一个算法。可能大家不知道的是，K近邻算法的一个缺点是我们需要遍历整个训练数据集。学习向量量化算法（简称 LVQ）是一种人工神经网络算法，它允许你选择训练实例的数量，并精确地学习这些实例应该是什么样的。而学习向量量化的表示是码本向量的集合。这些是在开始时随机选择的，并逐渐调整以在学习算法的多次迭代中最好地总结训练数据集。在学习之后，码本向量可用于预测。最相似的近邻通过计算每个码本向量和新数据实例之间的距离找到。然后返回最佳匹配单元的类别值或作为预测。如果大家重新调整数据，使其具有相同的范围，就可以获得最佳结果。当然，如果大家发现KNN在大家数据集上达到很好的结果，请尝试用LVQ减少存储整个训练数据集的内存要求

E. k近邻算法如何做回归分析

有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在， 我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。我们常说，物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手，所谓观其友，而识其人。我们不是要判别上图中那个绿色的圆是属于哪一类数据么，好说，从它的邻居下手。但一次性看多少个邻居呢？从上图中，你还能看到：
如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。 于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。
KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
KNN 算法本身简单有效，它是一种 lazy-learning 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为 n，那么 KNN 的分类时间复杂度为O(n)。
KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
K 近邻算法使用的模型实际上对应于对特征空间的划分。K 值的选择，距离度量和分类决策规则是该算法的三个基本要素： K 值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，是预测发生错误。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。 该算法中的分类决策规则往往是多数表决，即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别 距离度量一般采用 Lp 距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。 KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
实现 K 近邻算法时，主要考虑的问题是如何对训练数据进行快速 K 近邻搜索，这在特征空间维数大及训练数据容量大时非常必要。

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

G. 什么叫做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值的方法是自助法。

H. 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树比蛮力实现要少检索多少数据。