K邻近算法

生活场景

我们在日常生活中，肯定会经常碰到各种各样的选择。比如，手机买什么牌子、买什么型号? 午饭吃什么? 周末和对象去哪儿玩? 当遇到这类型问题的时候，通常都会怎么解决呢？

假如现在快到饭点，打算开始点外卖，怎么选?

• 随便选一家店？
• 问问周围同事们们都点了什么，跟风点？
• 做一份详细的报告，根据你的身体情况以及周边外卖的质量分析，选择一个更合适的店？

一、算法原理

K 近邻算法(K-Nearest Neighbor)，简称 KNN 算法。

• 是最常用来解决分类问题的一种算法
• 是一种基于有标签训练数据的模型
• 是一种有监督学习算法

1、定义

算法原理： 对于一个犹豫不决的选择，我们先参考周围最近的一些已经做出的选择，然后再做出相似的决定，即“近朱者赤，近墨者黑”。

数学解释： 对于一个未知的样本点，观察 它附近最近的已知样本点的分类结果，如果周围最近的 K 个样本点属于某一类，我们就可以把这个待测样本点归于这一类。

2、算法流程

总体来说，KNN分类算法包括以下4个步骤：

1. 准备数据，对数据进行预处理
2. 计算测试样本点（也就是待分类点）到其他每个样本点的距离
3. 对每个距离进行排序，然后选择出距离最小的K个点
4. 对K个点所属的类别进行比较，根据少数服从多数的原则，将测试样本点归入在K个点中占比最高的那一类

二、距离计算

问题一：如何定义样本间距离的远近？

• 欧式距离 (Euclidean Distance)
• 切比雪夫距离 (Chebyshev Distance)
• 曼哈顿距离(Manhattan Distance)
• 余弦距离(Cosine Distance)

问题二：K 值的选择？

• 通过验证集来选择最佳 K 值。

1、欧式距离

欧式距离，也称欧几里得距离，是最常见的距离计算公式，它衡量的是空间中两个点之间的绝对距离，或最小距离。

原理： 基于勾股定理来计算两点之间的直线距离。

计算公式如下：

2、曼哈顿距离

曼哈顿距离(Manhattan Distance)，也被称为 L1 距离，或城市街区距离。

名称来源于纽约的曼哈顿，曼哈顿的街道布局中，是一个个非常规整的正方形，要从一个十字路口开车到另一个十字路口，只能沿着直线（东西或南北）行驶，而不能直接穿越街区。这个实际驾驶距离，就是 我们从 A 走到 B（只沿着格子，水平、垂直得移动）的距离，就是“曼哈顿距离”。

计算公式如下：

欧氏距离与曼哈顿距离图解：

3、切比雪夫距离

切比雪夫距离 (Chebyshev Distance)，它的来源是国际象棋，国王不仅可以横着走，竖着走，也可以斜着走，所以国王走一步可以移动到相邻 8 个方格中的任意一个。

国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？ 这个距离就叫切比雪夫距离。

计算公式如下：

• 即将斜线看成两个点横纵（X, y）坐标轴的投影，然后加上横纵的行走距离，就是最终的切比雪夫距离。
• 计算公式就是看横纵坐标的差值的最大值。

4、余弦距离

余弦距离(Cosine Distance)，在数学的几何中，夹角余弦是用来衡量两个向量方向的差异；在机器学习中，也用这个概念来衡量样本向量之间的差异。

计算公式如下：

三、距离案例：预测用户性别案例

1、任务说明

• 根据商城里所有用户的历史行为数据（简化为两个：在美妆页面的浏览次数，在数码页面的浏览次数），以及用户 1-10 的性别数据。
• 任务：预测商城其他用户的性别。

2、数据可视化

若用户 11，在美妆页面的浏览次数是 30，在数码页面的浏览次数是 25，则如下（绿色点）所示。

四、K 值选择

K 值的选择：

• 总的来说，当 K 越小的时候，模型就越容易过拟合; 而 K 越大的时候，就越容易欠拟合。
• 利用【验证集】，找到最参数 K 值

五、算法优缺点

KNN 算法的优点：

• 简单易懂，可解释性强，实现起来非常容易
• 对噪声的敏感性非常低
  1. 由于待预测点的分类结果通常是基于其附近的 K 个邻居的投票确定的，所以，即使有一些附近的数据点是噪声或异常值，只要大部分邻居的分类是正确的，那么这个待预测点的分类应该也会是正确的。
  2. 它的结果是基于局部的信息来做出决策的，那么对一些较远的数据点异常值，KNN 就完全不会受到影响了。

KNN 算法的缺点：

• 计算复杂度高
• 不考虑数据的分布
• 如果数据分布不均匀，结果就不准确

总结

这个算法，适合那些团队中人少，甚至缺少算法同学的情况下，产品经理自己就可以根据特征的选择来使用 KNN 算法来解决问题，甚至不需要算法的介入，仅靠工程团队的同学就可以完成这个算法的实现，这就要求产品经理要注重 K 值的选择以及数据的处理。