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就了解到这里吧,下回见。

关注请扫码:

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180608G0XP6I00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券