学习
实践
活动
工具
TVP
写文章

k近邻法篇

上回的感知机(perception)篇讨论的问题是二类分类问题,现在要介绍的k近邻法也是分类问题,不过不局限于二类问题,可以应用于多类分类问题中。

k近邻法(k-nearest neighbor, K-NN)是由Cover和Hart在1968年提出的,是一个基本的分类和回归方法,现在讨论的是在分类问题中的应用。核心思想就是在对于一个未知类别的输入,根据已知输入类别中k个最相似的输入类别,将该类别作为这个未知类别的类别。也就是俗话说的物以类聚,人以群分。想了解一个人怎么样,可以先了解下这个人最好的几个朋友,也就可以推出这个人怎么样。从这儿看出,k近邻法本质上没有学习的过程,只是对输入的特征空间进行了一个划分。自然而然地可以猜出在分类中,knn的三要素就是k值的选择+距离度量+分类决策规则。那下面的介绍就自然而然是围绕按照这三要素来了。

k值的选择

k值的选择是有依据的,k值太小,比如等于1,来一个输入,就把该输入归为和该输入距离最近的训练点的类别,这样会让模型太复杂,而且如果最近的点恰好又是噪声,预测就不正确了,也就是输入会对每个训练点敏感,这就是所谓的过拟合。

k值太大,比如等于训练集大小N,这样模型就太简单了,找出训练集中成员最多的类别,新来的输入,不管三七二十一,就分为该类别。这样会让经验风险太大,毕竟都不用学习什么参数了,那个类别成员多,以后所有输入都是这个类的。我理解这样就成了欠拟合了。

顺路说下过拟合与欠拟合,这个在机器学习模型中还是很基础的。

过拟合:也就是为了拟合每个训练数据,模型设计的特别复杂,效果就是可以将训练误差搞得非常小。可是对于未知的输入效果可能就很差了,因为如果训练数据中有噪声,那么系统将噪声也作为合理输入了,这样必然没法保证未知的输入。可以想想如果某一个地方的房价和面积是一阶线性关系,可是你却用10阶函数去拟合,能保证准确预测房价么?一句话,过拟合,就是你把模型设计的太复杂了。

欠拟合:就是你把模型设计的太简单了。不仅训练误差没法保证,期望误差也没法保证。比如还是房价,你用0阶函数来拟合,看到大家房价从0.5k到5w间变化,你不管三七二十一,房价都是2w。这样必然也是不行的。

那怎么防止过拟合或者欠拟合?

一般的套路都是来一个损失函数L=E+aJ E是经验误差,用来防止欠拟合的,J是系统复杂度,用来防止过拟合的。a是权重,可以来回调,这不就可以处理这样的极端问题了么。

那继续KNN,那怎么选取k比较合理呢?毕竟对于KNN,还不太好弄损失函数。那就选一个偏小的值,然后交叉验证看效果。据我所知没有特别科学的方法,直接告诉我们k选多少。

距离度量

要选择K个最近的点,那至少需要知道最近是用啥衡量的吧。因为距离反映到输入上,就是输入间的相似程度。在KNN中由于特征空间一般是n维的向量空间,那么用度量向量距离的方法来度量就可以了。比如有x1,x2两个输入,距离L=

(PS:用latex生成的公式只能用图片拷贝过来了,效果不太好,直接用编辑器拷贝公式可能效果更好,下来研究下)。

p>=1, 我们用的比较多的是p=2,就是欧式距离,p=1也用吧,曼哈顿距离。需要知道的是对于一个点,用不同的p,也就是距离度量方法获取到的最近邻点是不一样的。

分类决策规则

KNN的分类决策规则一般都是多数表决,K个邻近点中,那个类别点最多,那么就是那个类别。

那为什么选类别成员多的,就能保证经验误差小呢?

从数学上解释就是:

P(Y!=f(x)) = 1 - P(Y=f(x))

也就是猜中的概率越大,经验误差越小。那怎样能做能让猜中的概率最大呢?

k个邻近点,有j个类,类成员越多的,f(x)是这个类的概率也就越大。

kd树

到现在就介绍完KNN的三要素了,还有一个问题?怎样快速搜索k个最近的邻点?如果是挨个训练数据遍历的话,当训练数据很大的时候,计算会很耗时。为了提升k搜索的效率,有很多种方法,这儿介绍下其中的一种,kd树。

kd树本质上就是二叉树,普通的二叉树是针对单个数值,对于k维的数据,在各个坐标轴上循环切分,就是kd树。举一个栗子:

现在有一个训练数据集合 T=,一共是n个输入。每个输入又是k维的数据。比如x_1=(x1,x2,...xk),这儿的每个数据是对应坐标轴上的表示,这儿的k就意味着我们有k个坐标轴,也可以说成是x_1是k维空间上的点。

构造kd树的过程就是:

根节点,选择x1所在坐标轴上的所有点,选取中位数,按照中位数将训练集划分为两个区域,小于中位数的作为左子节点,大于中位数的作为右子节点,等于中位数的就放到当前节点

重复,对左右节点,选择第j个数据的中位数,j的选取就是依次循环取坐标轴上数据即可,比如父节点是第i个坐标轴,那么子节点就选取第i%k+1个坐标轴。按根节点方法划分即可。

结束,啥时候结束?划分到没数据划分就可以结束了

那怎么搜索呢? 例如来了一个输入,想找和这个输入最接近的点。

步骤是:

在kd树中找包含该输入的叶节点。

找该区域内最邻近该输入的训练点,找到后,把这个点作为最近距离点,然后以输入点为圆心,最近距离点为半径,做一个圆,如果有更近的点,那么必然在这个圆里面

看父节点的另外一个子节点区域是否和该圆相交,如果没有,那么继续往上看当前节点的父节点,重复过程3.如果有,那么看该节点对应的区域内是否有比当前最近点更近的点,如果有,那么把这个点作为当前最近的点。重复3.如果到达根节点,遍历就结束了。这时候的最近距离点就是最近的点了。

算法时间复杂度O(LOG(N)),N是训练节点个数。

那怎么找k个最邻近的点呢? 这个参考堆排序的思想即可。

总结

本篇介绍了下KNN算法,包括KNN算法的三要素,还介绍了一种快速查到最邻近点的方法,kd树。总的来说,这块不太复杂。下一篇是朴素贝叶斯篇。

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

扫码关注腾讯云开发者

领取腾讯云代金券