Python机器学习最邻近规则分类(KNN)算法理论

2017年6月18日19:14:27 发表评论 908

Python机器学习最邻近规则分类(KNN)算法理论

1、概述

KNN(K-Nearest Neighbor)算法也叫K近邻算法,是Cover和Hart在1968年提出的。它是分类算法的一种。在Pthon机器学习中长用来做简单的分类器。它是基于实例的学习也叫做懒惰学习,什么意思呢?就是说,这个算法每次应用都要依赖基础的数据集。

2、例子

看下面这个判断电影类型的例子。

Python机器学习最邻近规则分类(KNN)算法理论

例子中有七个实例,每个实例有打斗次数和训练次数两个特征值,我们就根据打斗次数和接吻次数来建立KNN模型判断下面的未知电影属于哪一类型的。我们就把打斗次数当做是X坐标,接吻次数当做是Y左边,然后每一个实例都会有一个坐标表示,如下表。

Python机器学习最邻近规则分类(KNN)算法理论

这样就会得到一个坐标系。然后接下来判断G点的类型,怎么判断呢?是这样的,我们就找出离G点最近的几个点,具体找几个点需要自己确定出最好的个数(K)。然后以少数服从多数来确定出G点属于的类型。是不是非常简单,我个人觉得这个是一个非常容易理解的算法。在日常生活中我们经常干这样的是事情。

3、算法详述

基本步骤如下:

1、为了判断未知实例的类别,以所有已知类别的实例作为参照。

2、选择参数K(邻近点的个数)。

3、计算未知实例与已知实例的距离。

4、选择最近K个已知实例。

5、根据少数服从多数的投票法则(majority-voting),让未知实例归类为K个最邻近样本中最多数的类别。

 

亮点之间的距离的计算方法:

Python机器学习最邻近规则分类(KNN)算法理论

就是亮点之间的距离计算公式。初中学过的。当然,距离的计算还有好多种方式,可以利用余弦值,相关度,曼哈顿距离等衡量距离的方法。

4、KNN算法的优缺点

优点想必大家都可以看得出来,就是简单,利于理解,在算法实现方面上也比较简单。但缺点还是需要注意一下的,看下面的图:

Python机器学习最邻近规则分类(KNN)算法理论

现在我们对图中的Y标记进行分类,很明显,现在X在红色的圈内,附近都是红色的圆点,我们可以看出来它应该是属于红色的。但是,如果使用KNN算法来分的话,如果K的个数掐还在黑色圈的范围,可以数一下,三角形的个数要比红色圈的个数要多,所以KNN算法会把它分到三角形的种类里面。也就是说,K的取值是非常重要的,太大了不好,太小了也不行。这个数值需要大量的测试最终选出最优K。

因为这个算发每次计算都要依赖大量的已知实例,所以需要大量的空间来存储这个实例,是比较浪费内存的。算法的复杂度也是比较大的。

另外,如果样例的个数是不均匀的,比如其中一类样本过大(实例数量过多)占主导的时候,新的未知实例容易被归类为这个主导样本,因为这类样本实例的数量过大,但这个新的未知实例实际并木接近目标样本。想必这一点大家都能想到。

5、算法改进

上面的缺点说到,K的取值是非常影响准确率的,所以我们最好在每个边上面加上权重(比如1/距离),然后以最终的权重之和来判断最近的几个点是谁,然后判断出未知实例的种类。

PS:以上所有图片引用来自互联网。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: