knn算法原理与应用场景

⑴ 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 算法 是基于 距离 的一种机器学习算法，需要计算测试点与样本点之间的距离。因此，当数据量大的时候，计算量就会非常庞大，需要大量的存储空间和计算时间。

另外，如果样本数据分类不均衡，比如有些分类的样本非常少，那么该类别的分类准确率就会很低。因此，在实际应用中，要特别注意这一点。

（本节完。）

推荐阅读：

决策树算法-理论篇-如何计算信息纯度

决策树算法-实战篇-鸢尾花及波士顿房价预测

朴素贝叶斯分类-理论篇-如何通过概率解决分类问题

朴素贝叶斯分类-实战篇-如何进行文本分类

计算机如何理解事物的相关性-文档的相似度判断

⑵ 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

我们先用一个例子体会下。

假设，我们想对电影的类型进行分类，统计了电影中打斗次数、接吻次数，当然还有其他的指标也可以被统计到，如下表所示。

我们很容易理解《战狼》《红海行动》《碟中谍 6》是动作片，《前任 3》《春娇救志明》《泰坦尼克号》是爱情片，但是有没有一种方法让机器也可以掌握这个分类的规则，当有一部新电影的时候，也可以对它的类型自动分类呢？

我们可以把打斗次数看成 X 轴，接吻次数看成 Y 轴，然后在二维的坐标轴上，对这几部电影进行标记，如下图所示。对于未知的电影 A，坐标为 (x,y)，我们需要看下离电影 A 最近的都有哪些电影，这些电影中的大多数属于哪个分类，那么电影 A 就属于哪个分类。实际操作中，我们还需要确定一个 K 值，也就是我们要观察离电影 A 最近的电影有多少个。

KNN 的工作原理

“近朱者赤，近墨者黑”可以说是 KNN 的工作原理。整个计算过程分为三步：

计算待分类物体与其他物体之间的距离；

统计距离最近的 K 个邻居；

对于 K 个最近的邻居，它们属于哪个分类最多，待分类物体就属于哪一类。

K 值如何选择

你能看出整个 KNN 的分类过程，K 值的选择还是很重要的。那么问题来了，K 值选择多少是适合的呢？

如果 K 值比较小，就相当于未分类物体与它的邻居非常接近才行。这样产生的一个问题就是，如果邻居点是个噪声点，那么未分类物体的分类也会产生误差，这样 KNN 分类就会产生过拟合。

如果 K 值比较大，相当于距离过远的点也会对未知物体的分类产生影响，虽然这种情况的好处是鲁棒性强，但是不足也很明显，会产生欠拟合情况，也就是没有把未分类物体真正分类出来。

所以 K 值应该是个实践出来的结果，并不是我们事先而定的。在工程上，我们一般采用交叉验证的方式选取 K 值。

交叉验证的思路就是，把样本集中的大部分样本作为训练集，剩余的小部分样本用于预测，来验证分类模型的准确性。所以在 KNN 算法中，我们一般会把 K 值选取在较小的范围内，同时在验证集上准确率最高的那一个最终确定作为 K 值。

距离如何计算

在 KNN 算法中，还有一个重要的计算就是关于距离的度量。两个样本点之间的距离代表了这两个样本之间的相似度。距离越大，差异性越大；距离越小，相似度越大。

关于距离的计算方式有下面五种方式：

欧氏距离；

曼哈顿距离；

闵可夫斯基距离；

切比雪夫距离；

余弦距离。

其中前三种距离是 KNN 中最常用的距离，我给你分别讲解下。

欧氏距离是我们最常用的距离公式，也叫做欧几里得距离。在二维空间中，两点的欧式距离就是：

同理，我们也可以求得两点在 n 维空间中的距离：

曼哈顿距离在几何空间中用的比较多。以下图为例，绿色的直线代表两点之间的欧式距离，而红色和黄色的线为两点的曼哈顿距离。所以曼哈顿距离等于两个点在坐标系上绝对轴距总和。用公式表示就是：

闵可夫斯基距离不是一个距离，而是一组距离的定义。对于 n 维空间中的两个点 x(x1,x2,…,xn) 和 y(y1,y2,…,yn) ， x 和 y 两点之间的闵可夫斯基距离为：

其中 p 代表空间的维数，当 p=1 时，就是曼哈顿距离；当 p=2 时，就是欧氏距离；当 p→∞时，就是切比雪夫距离。

那么切比雪夫距离怎么计算呢？二个点之间的切比雪夫距离就是这两个点坐标数值差的绝对值的最大值，用数学表示就是：max(|x1-y1|,|x2-y2|)。

余弦距离实际上计算的是两个向量的夹角，是在方向上计算两者之间的差异，对绝对数值不敏感。在兴趣相关性比较上，角度关系比距离的绝对值更重要，因此余弦距离可以用于衡量用户对内容兴趣的区分度。比如我们用搜索引擎搜索某个关键词，它还会给你推荐其他的相关搜索，这些推荐的关键词就是采用余弦距离计算得出的。

KD 树

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

在这里，我们不需要对 KD 树的数学原理

了解太多，你只需要知道它是一个二叉树的数据结构，方便存储 K 维空间的数据就可以了。而且在 sklearn 中，我们直接可以调用 KD 树，很方便。

用 KNN 做回归

KNN 不仅可以做分类，还可以做回归。首先讲下什么是回归。在开头电影这个案例中，如果想要对未知电影进行类型划分，这是一个分类问题。首先看一下要分类的未知电影，离它最近的 K 部电影大多数属于哪个分类，这部电影就属于哪个分类。

如果是一部新电影，已知它是爱情片，想要知道它的打斗次数、接吻次数可能是多少，这就是一个回归问题。

那么 KNN 如何做回归呢？

对于一个新电影 X，我们要预测它的某个属性值，比如打斗次数，具体特征属性和数值如下所示。此时，我们会先计算待测点（新电影 X）到已知点的距离，选择距离最近的 K 个点。假设 K=3，此时最近的 3 个点（电影）分别是《战狼》，《红海行动》和《碟中谍 6》，那么它的打斗次数就是这 3 个点的该属性值的平均值，即 (100+95+105)/3=100 次。

总结

今天我给你讲了 KNN 的原理，以及 KNN 中的几个关键因素。比如针对 K 值的选择，我们一般采用交叉验证的方式得出。针对样本点之间的距离的定义，常用的有 5 种表达方式，你也可以自己来定义两个样本之间的距离公式。不同的定义，适用的场景不同。比如在搜索关键词推荐中，余弦距离是更为常用的。

另外你也可以用 KNN 进行回归，通过 K 个邻居对新的点的属性进行值的预测。

KNN 的理论简单直接，针对 KNN 中的搜索也有相应的 KD 树这个数据结构。KNN 的理论成熟，可以应用到线性和非线性的分类问题中，也可以用于回归分析。

不过 KNN 需要计算测试点与样本点之间的距离，当数据量大的时候，计算量是非常庞大的，需要大量的存储空间和计算时间。另外如果样本分类不均衡，比如有些分类的样本非常少，那么该类别的分类准确率就会低很多。

当然在实际工作中，我们需要考虑到各种可能存在的情况，比如针对某类样本少的情况，可以增加该类别的权重。

同样 KNN 也可以用于推荐算法，虽然现在很多推荐系统的算法会使用 TD-IDF、协同过滤、Apriori 算法，不过针对数据量不大的情况下，采用 KNN 作为推荐算法也是可行的。

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

⑸ 什么是knn算法

作为一种非参数的分类算法，K-近邻(KNN)算法是非常有效和容易实现的。它已经广泛应用于分类、回归和模式识别等。在应用KNN算法解决问题的时候，要注意两个方面的问题--样本权重和特征权重。利用SVM来确定特征的权重，提出了基于SVM的特征加权算法(FWKNN,feature
weighted
KNN)。实验表明，在一定的条件下，FWKNN能够极大地提高分类准确率。

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

⑺ R语言-KNN算法

1、K最近邻(k-NearestNeighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

2、KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

3、KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。

简言之，就是将未标记的案例归类为与它们最近相似的、带有标记的案例所在的类 。

原理及举例

工作原理：我们知道样本集中每一个数据与所属分类的对应关系，输入没有标签的新数据后，将新数据与训练集的数据对应特征进行比较，找出“距离”最近的k（通常k<20）数据，选择这k个数据中出现最多的分类作为新数据的分类。

算法描述

1、计算已知数据集中的点与当前点的距离

2、按距离递增次序排序

3、选取与当前数据点距离最近的K个点

4、确定前K个点所在类别出现的频率

5、返回频率最高的类别作为当前类别的预测

距离计算方法有"euclidean"（欧氏距离）,”minkowski”（明科夫斯基距离）, "maximum"（切比雪夫距离）, "manhattan"（绝对值距离）,"canberra"（兰式距离）, 或 "minkowski"（马氏距离）等

Usage

knn(train, test, cl, k = 1, l = 0, prob =FALSE, use.all = TRUE)

Arguments

train

matrix or data frame of training set cases.

test

matrix or data frame of test set cases. A vector will  be interpreted as a row vector for a single case.

cl

factor of true classifications of training set

k

number of neighbours considered.

l

minimum vote for definite decision, otherwisedoubt. (More precisely, less thank-ldissenting votes are allowed, even

ifkis  increased by ties.)

prob

If this is true, the proportion of the votes for the

winning class are returned as attributeprob.

use.all

controls handling of ties. If true, all distances equal

to thekth largest are

included. If false, a random selection of distances equal to thekth is chosen to use exactlykneighbours.

kknn(formula = formula(train), train, test, na.action = na.omit(), k = 7, distance = 2, kernel = "optimal", ykernel = NULL, scale=TRUE, contrasts = c('unordered' = "contr.mmy", ordered = "contr.ordinal"))

参数：

formula                            A formula object.

train                                 Matrix or data frame of training set cases.

test                                   Matrix or data frame of test set cases.

na.action                         A function which indicates what should happen when the data contain ’NA’s.

k                                       Number of neighbors considered.

distance                          Parameter of Minkowski distance.

kernel                              Kernel to use. Possible choices are "rectangular" (which is standard unweighted knn), "triangular", "epanechnikov" (or beta(2,2)), "biweight" (or beta(3,3)), "triweight" (or beta(4,4)), "cos", "inv", "gaussian", "rank" and "optimal".

ykernel                            Window width of an y-kernel, especially for prediction of ordinal classes.

scale                                Logical, scale variable to have equal sd.

contrasts                         A vector containing the ’unordered’ and ’ordered’ contrasts to use

kknn的返回值如下：

fitted.values              Vector of predictions.

CL                              Matrix of classes of the k nearest neighbors.

W                                Matrix of weights of the k nearest neighbors.

D                                 Matrix of distances of the k nearest neighbors.

C                                 Matrix of indices of the k nearest neighbors.

prob                            Matrix of predicted class probabilities.

response                   Type of response variable, one of continuous, nominal or ordinal.

distance                     Parameter of Minkowski distance.

call                              The matched call.

terms                          The ’terms’ object used.

iris%>%ggvis(~Length,~Sepal.Width,fill=~Species)

library（kknn）
data（iris）

dim(iris)

m<-(dim(iris))[1]
val<-sample(1:m,size=round(m/3）,replace=FALSE,prob=rep(1/m,m))

建立训练数据集

data.train<-iris[-val,]

建立测试数据集

data.test<-iris[val,]

调用kknn  之前首先定义公式

formula ： Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width

iris.kknn<-kknn(Species~.,iris.train,iris.test,distance=1,kernel="triangular")

summary(iris.kknn)

# 获取fitted.values

fit <- fitted(iris.kknn)

# 建立表格检验判类准确性

table(iris.valid$Species, fit)
# 绘画散点图，k-nearest neighbor用红色高亮显示

pcol <- as.character(as.numeric(iris.valid$Species))

pairs(iris.valid[1:4], pch = pcol, col = c("green3", "red")[(iris.valid$Species != fit)+1]

二、R语言knn算法

install.packages("class")

library(class)

对于新的测试样例基于距离相似度的法则，确定其K个最近的邻居，在K个邻居中少数服从多数

确定新测试样例的类别

1、获得数据

2、理解数据

对数据进行探索性分析，散点图

如上例

3、确定问题类型，分类数据分析

4、机器学习算法knn

5、数据处理，归一化数据处理

normalize <- function(x){

num <- x - min(x)

denom <- max(x) - min(x)

return(num/denom)

}

iris_norm <-as.data.frame(lapply(iris[,1:4], normalize))

summary(iris_norm)

6、训练集与测试集选取

一般按照3:1的比例选取

方法一、set.seed(1234)

ind <- sample(2,nrow(iris), replace=TRUE, prob=c(0.67, 0.33))

iris_train <-iris[ind==1, 1:4]

iris_test <-iris[ind==2, 1:4]

train_label <-iris[ind==1, 5]

test_label <-iris[ind==2, 5]

方法二、

ind<-sample(1:150,50)

iris_train<-iris[-ind,]

iris_test<-iris[ind,1:4]

iris_train<-iris[-ind,1:4]

train_label<-iris[-ind,5]

test_label<-iris[ind,5]

7、构建KNN模型

iris_pred<-knn(train=iris_train,test=iris_test,cl=train_label,k=3)

8、模型评价

交叉列联表法

table（test_label,iris_pred)

实例二

数据集

http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data

导入数据

dir <-'http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data'wdbc.data <-read.csv(dir,header = F)

names(wdbc.data) <- c('ID','Diagnosis','radius_mean','texture_mean','perimeter_mean','area_mean','smoothness_mean','compactness_mean','concavity_mean','concave points_mean','symmetry_mean','fractal dimension_mean','radius_sd','texture_sd','perimeter_sd','area_sd','smoothness_sd','compactness_sd','concavity_sd','concave points_sd','symmetry_sd','fractal dimension_sd','radius_max_mean','texture_max_mean','perimeter_max_mean','area_max_mean','smoothness_max_mean','compactness_max_mean','concavity_max_mean','concave points_max_mean','symmetry_max_mean','fractal dimension_max_mean')

table(wdbc.data$Diagnosis)## M = malignant, B = benign

wdbc.data$Diagnosis <- factor(wdbc.data$Diagnosis,levels =c('B','M'),labels = c(B ='benign',M ='malignant'))

⑻ 大数据算法：分类算法

KNN算法，即K近邻（K Nearest Neighbour）算法，是一种基本的分类算法。其主要原理是：对于一个需要分类的数据，将其和一组已经分类标注好的样本集合进行比较，得到距离最近的K个样本，K个样本最多归属的类别，就是这个需要分类数据的类别。下面我给你画了一个KNN算法的原理图。

图中，红蓝绿三种颜色的点为样本数据，分属三种类别 、 、 。对于待分类点 ，计算和它距离最近的5个点（即K为5），这5个点最多归属的类别为 （4个点归属 ，1个点归属 ），那么 的类别被分类为 。

KNN的算法流程也非常简单，请看下面的流程图。

KNN算法是一种非常简单实用的分类算法，可用于各种分类的场景，比如新闻分类、商品分类等，甚至可用于简单的文字识别。对于新闻分类，可以提前对若干新闻进行人工标注，标好新闻类别，计算好特征向量。对于一篇未分类的新闻，计算其特征向量后，跟所有已标注新闻进行距离计算，然后进一步利用KNN算法进行自动分类。

读到这你肯定会问，如何计算数据的距离呢？如何获得新闻的特征向量呢？

KNN算法的关键是要比较需要分类的数据与样本数据之间的距离，这在机器学习中通常的做法是：提取数据的特征值，根据特征值组成一个n维实数向量空间（这个空间也被称作特征空间），然后计算向量之间的空间距离。空间之间的距离计算方法有很多种，常用的有欧氏距离、余弦距离等。

对于数据 和 ，若其特征空间为n维实数向量空间 ，即 ， ，则其欧氏距离计算公式为

这个欧式距离公式其实我们在初中的时候就学过，平面几何和立体几何里两个点之间的距离，也是用这个公式计算出来的，只是平面几何（二维几何）里的n=2，立体几何（三维几何）里的n=3，而机器学习需要面对的每个数据都可能有n维的维度，即每个数据有n个特征值。但是不管特征值n是多少，两个数据之间的空间距离的计算公式还是这个欧氏计算公式。大多数机器学习算法都需要计算数据之间的距离，因此掌握数据的距离计算公式是掌握机器学习算法的基础。

欧氏距离是最常用的数据计算公式，但是在文本数据以及用户评价数据的机器学习中，更常用的距离计算方法是余弦相似度。

余弦相似度的值越接近1表示其越相似，越接近0表示其差异越大，使用余弦相似度可以消除数据的某些冗余信息，某些情况下更贴近数据的本质。我举个简单的例子，比如两篇文章的特征值都是：“大数据”“机器学习”和“极客时间”，A文章的特征向量为（3, 3, 3），即这三个词出现次数都是3；B文章的特征向量为（6, 6, 6），即这三个词出现次数都是6。如果光看特征向量，这两个向量差别很大，如果用欧氏距离计算确实也很大，但是这两篇文章其实非常相似，只是篇幅不同而已，它们的余弦相似度为1，表示非常相似。

余弦相似度其实是计算向量的夹角，而欧氏距离公式是计算空间距离。余弦相似度更关注数据的相似性，比如两个用户给两件商品的打分分别是（3, 3）和（4, 4），那么两个用户对两件商品的喜好是相似的，这种情况下，余弦相似度比欧氏距离更合理。

我们知道了机器学习的算法需要计算距离，而计算距离需要还知道数据的特征向量，因此提取数据的特征向量是机器学习工程师们的重要工作，有时候甚至是最重要的工作。不同的数据以及不同的应用场景需要提取不同的特征值，我们以比较常见的文本数据为例，看看如何提取文本特征向量。

文本数据的特征值就是提取文本关键词，TF-IDF算法是比较常用且直观的一种文本关键词提取算法。这种算法是由TF和IDF两部分构成。

TF是词频（Term Frequency），表示某个单词在文档中出现的频率，一个单词在一个文档中出现的越频繁，TF值越高。

词频：

IDF是逆文档频率（Inverse Document Frequency），表示这个单词在所有文档中的稀缺程度，越少文档出现这个词，IDF值越高。

逆文档频率：

TF与IDF的乘积就是TF-IDF。

所以如果一个词在某一个文档中频繁出现，但在所有文档中却很少出现，那么这个词很可能就是这个文档的关键词。比如一篇关于原子能的技术文章，“核裂变”“放射性”“半衰期”等词汇会在这篇文档中频繁出现，即TF很高；但是在所有文档中出现的频率却比较低，即IDF也比较高。因此这几个词的TF-IDF值就会很高，就可能是这篇文档的关键词。如果这是一篇关于中国原子能的文章，也许“中国”这个词也会频繁出现，即TF也很高，但是“中国”也在很多文档中出现，那么IDF就会比较低，最后“中国”这个词的TF-IDF就很低，不会成为这个文档的关键词。

提取出关键词以后，就可以利用关键词的词频构造特征向量，比如上面例子关于原子能的文章，“核裂变”“放射性”“半衰期”这三个词是特征值，分别出现次数为12、9、4。那么这篇文章的特征向量就是（12, 9, 4），再利用前面提到的空间距离计算公式计算与其他文档的距离，结合KNN算法就可以实现文档的自动分类。

贝叶斯公式是一种基于条件概率的分类算法，如果我们已经知道A和B的发生概率，并且知道了B发生情况下A发生的概率，可以用贝叶斯公式计算A发生的情况下B发生的概率。事实上，我们可以根据A的情况，即输入数据，判断B的概率，即B的可能性，进而进行分类。

举个例子：假设一所学校里男生占60%，女生占40%。男生总是穿长裤，女生则一半穿长裤一半穿裙子。假设你走在校园中，迎面走来一个穿长裤的学生，你能够推断出这个穿长裤学生是男生的概率是多少吗？

答案是75%，具体算法是：

这个算法就利用了贝叶斯公式，贝叶斯公式的写法是：

意思是A发生的条件下B发生的概率，等于B发生的条件下A发生的概率，乘以B发生的概率，除以A发生的概率。还是上面这个例子，如果我问你迎面走来穿裙子的学生是女生的概率是多少。同样带入贝叶斯公式，可以计算出是女生的概率为100%。其实这个结果我们根据常识也能推断出来，但是很多时候，常识受各种因素的干扰，会出现偏差。比如有人看到一篇博士生给初中学历老板打工的新闻，就感叹读书无用。事实上，只是少见多怪，样本量太少而已。而大量数据的统计规律则能准确反映事物的分类概率。

贝叶斯分类的一个典型的应用场合是垃圾邮件分类，通过对样本邮件的统计，我们知道每个词在邮件中出现的概率 ，我们也知道正常邮件概率 和垃圾邮件的概率 ，还可以统计出垃圾邮件中各个词的出现概率 ，那么现在一封新邮件到来，我们就可以根据邮件中出现的词，计算 ，即得到这些词出现情况下，邮件为垃圾邮件的概率，进而判断邮件是否为垃圾邮件。

现实中，贝叶斯公式等号右边的概率，我们可以通过对大数据的统计获得，当有新的数据到来的时候，我们就可以带入上面的贝叶斯公式计算其概率。而如果我们设定概率超过某个值就认为其会发生，那么我们就对这个数据进行了分类和预测，具体过程如下图所示。

训练样本就是我们的原始数据，有时候原始数据并不包含我们想要计算的维度数据，比如我们想用贝叶斯公式自动分类垃圾邮件，那么首先要对原始邮件进行标注，需要标注哪些邮件是正常邮件、哪些邮件是垃圾邮件。这一类需要对数据进行标注才能进行的机器学习训练也叫作有监督的机器学习。