首页所有驱动分类下载数据挖掘与人工智能搜索引擎与SEO技术备忘录站长随笔

K邻近分类算法详解

2020-02-21 AI机器学习, 归类算法 浏览次数:69
 
其实这是一个非常简单的算法,但由于网上的资料专业术语太多,把事情弄复杂化了,为了能更好的理解这个算法,这里尽量不使用过多的专业术语,而采用更接近生活的语句来写这篇文章。

K邻近算法是一个分类算法,采用的是“物以类聚人以群分”的思想,通过统计某个未知事物周边的同类数量,然后把未知的事物归为某一类,例如:假设某个人最经常联系的朋友有10个,2个是宅男,6个是喜欢踢足球的,1个是打篮球的,1个是偶尔运动下的,那么可以猜测,这个人很有可能喜欢运动,而且运动项目可能是踢足球。

可以看出,K邻近算法实现的前提就是:必须先有已经正确分类好的数据,才可以将未知事物归类

下面有个例子,就是如何将一部电影归类:

假设已经有分类好的数据如下:

视频A是战争片,所以整部视频里,有武器和战斗的镜头是非常多的;
视频B是军事讲座,主要是介绍武器,过程中偶尔穿插了一些战斗场景;
视频C是枪战片,武器镜头不是很多,战斗场景的镜头不多也不少。
视频D是一部激烈的枪战片,武器镜头虽然很少,但是战斗场面镜头很多。
视频E是战争片,稍微比视频A打得激烈点。
视频F是一部激烈的战争片,战斗场景非常多,显然就是人狠话不多,不服就干的类型。
视频G是本例的主角,属于未知类型,需要计算机去判断并归类,这部片子的武器镜头是600次,有战斗场景的镜头500次,从直觉上来说,这有可能是一部历史题材的纪录片,也有可能是一部战争片。计算机到底会将视频G归类成什么类型的视频呢?



首先,需要将未知电影和已分类好的电影展现在一个坐标轴里,X轴是武器镜头数量,Y轴代表战斗场景的镜头数量,得出下面的图:



然后将红色G点(未知电影的点)与其他每一个点都计算距离,将这个距离看作判断准则,越近代表越相似。这个计算方法就不用我说了,其实就是计算三角形的边长,经过计算得到如下结果(小数点不要,四舍五入):



G点到A的的距离:GA=412
G点到B的的距离:GB=424
G点到C的的距离:GC=447
G点到D的的距离:GD=510
G点到E的的距离:GE=447
G点到F的的距离:GF=361

取最靠近的一个点,那么F点是最靠近G点的,那么将G归类为跟F一样的类型(战争片)。那么取最靠近的两个点F和A,G还是被归类为战争片,所以G基本上就是被归类为战争片了,这就是整个算法的工作原理。

影响最终判断结果准确率的因素:

1 取最近点的数量

取三个点?四个点?到底取多少个点?其实在现实操作中,并没有统一标准做法,是根据实际应用场景来决定的。有些在计算机算力许可前提下,取的数量尽量多,而有些取的数量是有范围限制的。

2 距离

实际操作中,并不是每一个点的权重都一样的,还有一个因素的,距离也是影响权重的因素,距离越近的点权重越大,距离越远的点权重越小。权重就相当于权威程度。打个比方:你的邻居跟你住的很近,你邻居对你的评价要比小区里其他人有较高的权威度,但是这并不代表100%正确,有时候小区里大部分人对你的评价才是正确的评价。

3 判断特征

训练样本都有一个到多个特征,每个特征也是有权重的,对于本例子来说,“有战斗场景的镜头”这个特征才是比较重要的判断因素,毕竟都是枪战题材的视频,视频里出现武器的现象是很平常的事情,它们之间区别比较大的就是战斗场面的数量和激烈程度。

4 每一类样本数据的数量

在本例中,假设有1000个已经分类好的数据,但是只有1个是战争片的样本,其他999个都是军事题材的样本,那么无论再怎么调整参数,未知视频基本上都会被判断成军事题材的视频。

总结:这个算法简单有效,容易理解,但操作起来不能太死板,必须根据实际应用场景设置各种参数,有些因素需要有权重之分,有些因素不能有权重之分,等等,当参数设置得当,得到的结果准确率是非常高的。例如本例中,距离就没有权重之分,因为视频是一个虚拟事物,它不具备有主观思维去评判未知事物的能力;但是如果是人或动物的话,那距离就有权重之分了,因为动物是带有主观性的物体。另外,特征也一样,有些样本它们的所有特征都同样重要,没有轻重之分,而有些样本的一个到几特征是比较重要的,那特征就有轻重之分,也就有权重之分。

K邻近算法每个点的距离的计算方法

可以把样本的每个特征看作所以一维向量,点与点之间的距离计算公式:一般采用欧氏距离或哈曼顿距离。

K邻近算法的实现方法

最简单的方法就是,每次判断一个未知事物,就把未知点和所有样本点的距离都计算一遍,然后再从计算结果中取距离最近的几个进行判断。

问题是,当数据量非常大的时候,每次都这样计算,实在太耗时间了,得想办法找个好的计算方法,K-D树或LSH位置敏感哈希法。

K-D树是一个二叉树的结构,它适用于多属性查找,树的每个节点就是一个样本数据,每个节点都是一个属性分割点,左边子节点里对应的特征值小于父节点的分割属性值,右边子节点里对应的特征值大于或等于父节点的分割属性值。这种分割方法有点像排序二叉树,但又不是排序二叉树,因为K-D树里面,有些特征值是相同的。K-D树的建立有很多种方法,其中一种常用方法是可以建立一个平衡的排序二叉树,但是在现实使用中,平衡二叉树并不是所有的应用场景中最优的。构建K-D树的详细步骤

LSH能高效处理海量高维数据的最近邻问题,用hash的方法把数据映射到一个新的空间中,因为有一些哈希算法会把相似的数据计算出相似的结果,利用这种特征,将计算结果映射到一个空间上面,使得相似的原始数据在新的空间中也相似的概率很大,而原始数据不相似的数据,在新的空间中相似的概率很小。

K-D树和LSH的区别是:

K-D树能算出比较准确的数据(但也有误差),LSH能准确率没那么高;
K-D树运行速度比LSH慢很多;

也没有哪种最优的说法,还是要看实际应用场景,有些应用场景要求速度快,而且允许有误差的就用LSH。
留言

有啥想说的就说吧,有啥想问的就问吧
Good good study, day day up!

名称

Email

内容

预览(只读), 点击返回编辑.

 
最新文章
 
留言
版权所有 © 2020 mypcrun.com.
桂ICP备19002156号桂公网安备 45070202000667号
这回把网站设计得那么漂亮,这下子不会被人笑了吧。