KNN算法

本篇大纲：

1、KNN算法

2、sklearn中KNN的API分析以及代码示例

上期回顾

1、首先我们由sigmoid函数出发，将线性拟合函数转换成分类型函数。

2、通过对拟合函数求极大似然，根据梯度的含义，我们进而得到theta的迭代公式，发现Logistic回归的迭代公式与线性回归的迭代公式形式一致。

故而也有SGD，MBGD以及L1正则和L2正则。

3、我们先手动实现了Logistic的三个核心函数。然后对Sklearn中逻辑回归的API做了详细的参数分析。

正题

闲话不絮，直接正题。

首先要知道什么是KNN，KNN全称K-nearest neighbors，即K临近。

所谓K临近，就是找K个最相邻的邻居来代表自己，也就是物以类聚，人以群分的意思。故而，从某种角度上来说，KNN其实都算不上是机器学习的一种，因为这个算法并不存在迭代学习的过程。

示例一：

以绿色的圆为例，以它为圆心，不同的半径我们可以画出两个圆。

假定以第一个小圆作为界限，则绿圆的邻居有三，两个红三角，一个蓝方块。

物以类聚，人以群分，多数战胜少数，此时判别绿圆属于红三角类别。

假定以第二个大圆作为界限，则绿圆的邻居有五，三个蓝方块，两个红三角。

又不是灭霸，所以人多就是拳头大，绿圆此时属于蓝方块类别。

示例二：

以红色圆点为例，知道它所在位置周围临近的若干邻居的值，要估测它的值，则依然框一个小框，当然，也可以是画一个小圆，身边有六个数值，加和求平均则基本可用来估计它的数值。

方法简单，过程直白。

KNN虽然简单，但是既可以做分类预测，也可以做回归预测。

从上述例子中我们可以看到，

对于分类问题，我们使用了多数表决法来判断目标对象的类别。

对于回归问题，我们使用了平均值法来判断目标对象的数值。

当然，多数表决法和平均值法看起来过于简单粗暴，并且容易不准确。

试想，一个公司的平均工资如何能够完美代表一个公司清洁工的工资呢，故而我们需要加权。让老总的工资比重占到微乎其微，让同属清洁工的工资权重占到尽可能高，毕竟，人均收入指标并不能衡量所有人的收入情况。

正由于多数表决法和平均值法看起来过于简单粗暴

故而也就有了加权多数表决法和加权平均值法。

换而言之，虽然邻居众多，但是离得越近，话语权才越重，即给予的权重才越大，这样才能更好地进行预测。

那么基本原理也就清楚了，问题来了？

1、K邻居，K怎么选择？

2、什么叫邻居，多近算邻居，距离怎么度量？

1、多少个邻居可以作为标准？

清洁工可以以身边最近3个人作为邻居来评判，当然也可以以本公司总人数2000人作为邻居来估测。

很显然，k值越小，训练误差越小，但会导致模型更复杂，容易出现过拟合现象。相反，k值越大，则训练误差越大，也会使模型变得过于简单，容易出现欠拟合现象。

因此对于k值的调整上，我们可以通过多组参数的调试，因为KNN没有带CV的API，故而我们可以使用GridSearchCV来进行最优参数选择。

2、距离该如何度量？

通常我们会使用欧式距离。

从闵可夫斯基距离出发，p为1时即为曼哈顿距离，p为2时即为欧式距离，p为无穷时即为切比雪夫距离，故而对于KNN，我们默认使用闵可夫斯基距离公式作为基础距离公式。

KNN中最核心的问题：该如何寻找出K个最邻近的样本点呢？

方式一：暴力法(brute)

所谓暴力法，也就是每来一个样本，都对已有的训练样本进行一次全遍历，获取到测试点到所有训练样本点的距离，然后再选择出k个最临近的点。

无论我们在选TopK时是使用平衡二叉树还是利用堆栈存储，前面的计算距离O(n)时间已经是必不可少了。故而这种方式会比较慢。

方式二：KD Tree法

很犀利的一种方式，简单来说，即先栽树，后乘凉。

先使用训练集数据进行KD-Tree的创建。

对于新来的测试集，则充分利用之前创建的树结构来寻找临近点，避免遍历毫无可能属于邻居的结点。

KD-Tree

既然KD-Tree是一种树形结构，故而主要分两大步骤。

一为创建树，二为遍历树，来寻找测试样本的临近结点。

关于创建树，主要步骤如下：

1、选择根节点，寻找特征变量中方差最大的那个特征变量，以该特征变量对应的中位数所对应的点作为根节点。以该特征变量作为判断依据，大于其中位数，作为右子树，小于其中位数，作为左子树。

2、对左子树和右子树重新按照步骤1进行进一步子树构建，迭代构建，直到结点分无可分。

干巴巴说步骤似乎不形象，来示例：

到这里，树的创建也就结束了。

那么来了一个新的测试结点，怎么去获取邻居呢？

假定来了新的测试样本（3,8）

因为我们已经有树了，故而从根开始，由于8大于7，故而落到右子树，然后由于8大于6，故而就落在右边叶子节点上。

故而初步我们可以判断与它相关的主要是根节点的右边子树结点。

假定我们设置的邻居数为2

我们以其兄弟节点（8,1）以及一路追根的直接父节点（9,6），（7,2），一般会找邻居数大小的父辈节点们来与兄弟节点一起判断距离。

这里的距离我们即以欧式距离进行计算，

故而我们可以知道距离（9,6）最近，即选出第一个邻居。

由于和（7,2）次近，则又选出第二个邻居，故而邻居选择结束。

这里，对于这个新来的测试结点而言，我们总共计算了三次，对于基本没有可能是邻居的左子树则完全省略了计算过程，从而也提升了效率。

回过头来看，这里又有个问题，为何每次都以方差最大的作为根节点呢？

因为一般而言，整体方差越大的特征变量其对于因变量的影响就越大，方差越小的特征变量其对于因变量的影响则越小。

比如无论y取值如何，某列特征变量x属性值始终为一个固定值1，那么我们基本可以判断，这列x对于y而言，基本上没有什么太大的作用。

故而我们更愿意将更为关键一点的影响因素放置树的头部，也就是为何每次都选取方差最大的特征变量作为参考指标了。

API分析

原理基本理清之后，接下来就是API的分析了，首先，贴上官网的API，这里我们以分类器示例：

比较重要的几个参数：

n_neighbors：表示邻居的数目，由上面我们知道，邻居数过大容易欠拟合，过小，容易过拟合，故而这是本模型中非常重要，并且需要不断调整的参数。

Weights：表示样本权重，默认为uniform即等权重，也可选择distance，以及自定义的距离度量方式。前面分析我们知道，等权重的情况下容易导致数据的不平衡性，故而一般而言，我们可以选择使用distance，即距离与权重成反比，越近权重越高，越远权重越小。

Algorithm：主要可选参数有“brute”和“kd_tree”，前者是暴力解决法，后者即上面所说的Kd树。故而一般而言，我们会选择Kd树。

Leaf_size：代表叶子数目，叶子数目太小，容易导致树过深，因而效率会慢，故而一般不要设太小。

Metric：即对应的距离度量方式，默认为闵可夫斯基距离公式，由于闵可夫斯基距离公式通过对p的调整，可以切换至曼哈顿距离，欧式距离以及切比雪夫距离，故而这里又涉及到参数p。

P代表的即为闵可夫斯基距离公式中的p，默认为2，即代表欧式距离。

简单代码示例，以官方示例为例：

这里共四个数，即四个样本，特征变量X只有一维

当x=0或x=1时，对应的Y都为0.

当x=2或x=3时，对应的Y都为1

给定测试样本x=1.1，使用KNN来进行分类预测，则将其预测结果为属于0类别。

同时也能获取到预测为0类别和1类别的概率估计值分别为0.67和0.33。

有了模型结果之后，一般而言，我们需要看看可以直观感受的优劣性指标，因为是分类型结果，故而这里我们就可以选择看准确率，F值或者AUC值等来观看其结果情况。

关于分类型和数值型的常见指标我们在

人工智能初入门之机器学习整体流程

已大概列举过，这里就不再赘述。

直接贴上代码示例和注解：

虽然KNN原理简单，但是由于其物以类聚的特性，对于某些分类场景也不失为一种可以尝试的模型，尤其是当预测场景中具有相似类别具有相近属性时，则尤为适合。

比如人群类别的划分，客户流失的预测，简单的面部识别等等。

好了，KNN就了解到这里吧，下回见。

关注请扫码：