聚类分析之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 作为推荐算法也是可行的。

距离计算在自然语言处理中得到广泛使用，不同距离计算方式应用与不同的环境，其中也产生了很多不同的效果。

1 余弦距离

余弦夹角也可以叫余弦相似度。集合中夹角可以用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。

余弦取值范围为[-1,1]。求得两个向量的夹角，并得出夹角对应的余弦值，词余弦值就可以用来表示这两个向量的相似性。夹角越小，趋近于0度，余弦值越接近于1，它们的方向就更加吻合，即更加相似。当两个向量的方向完全相反时，夹角的余弦取最小值-1。当余弦值为0时，两向量正交，夹角为90度。因此可以看出，余弦相似度于向量的幅值无关，于向量的方向相关。

公式描述：

Python代码实现：

2 欧氏距离

欧几里得距离即欧几里得空间中两点间的直线距离。

Python实现：

3 曼哈顿距离

曼哈顿距离也成为城市街区距离。用来表示两个点在标准坐标系上的绝对轴距之和，即从一个路口到另外一个路口，驾驶距离不是两点之间的直线距离。

Python实现

4 明可夫斯基距离

明氏距离又叫明可夫斯基距离，是欧氏空间中的一种测度，被看作欧氏距离和曼哈顿距离的一种推广。

python实现

可参照之前代码

5 切比雪夫距离

python实现

6 杰卡德距离

杰卡德（Jaccard）相似系数：两个集合A和B的交集在元素在A、B的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号J(A,B)表示。杰卡德距离：在占比中所取的是两个集合中不同元素。

Python实现：

7 汉明距离

在信息论中，两个登场字符串之间的汉明距离对应位置上的不同字符的个数。也就是说，将一个字符串变换成另一个字符串所需要替换的字符个数。

例如：“toned”与“roses”之间的汉明距离就是3

python实现：

切比雪夫不等式：

P{|X-EX|>=ε}<=DX/ε^2

描述的是：随机变量X与他的均值EX的距离比较大的概率；

切比雪夫不等式给出这个概率的估计值

这个估计值比较“粗”,不够精确,

但是,在无法计算这个概率的准确值时,如果知道方差,用这个不等式给出事件概率的估计值也是一个不错的方法

切比雪夫不等式在大数律中有不错的应用

见的距离算法 11欧几里得距离（Euclidean Distance）以及欧式距离的标准化（Standardized Euclidean distance）

12马哈拉诺比斯距离（Mahalanobis Distance）

13曼哈顿距离（Manhattan Distance） 

14切比雪夫距离（Chebyshev Distance）

15明可夫斯基距离（Minkowski Distance）