首页 > 编程笔记

KNN算法(K最近邻算法)详解

K 最近邻的核心数学知识是距离的计算和权重的计算。我们把需要预测的点作为中心点,然后计算其周围一定半径内的已知点距其的距离,挑选前 k 个点,进行投票,这 k 个点中,哪个类别的点多,该预测点就被判定属于哪一类。

1. 两点间距离公式

已知坐标系中有两个点,三角形坐标 (3,4) 和圆坐标 (7,7),如图 1 所示,它们的距离应该如何计算呢?

我们一般使用欧式距离,即高中学到的两点间的距离公式,如图 2 所示,它的本质就是勾股定理:

a2+b2=c2

根据勾股定理,我们可计算两点之间的距离为 5。

已知直角坐标系中有两个点(3,4),(7,7)
图1:已知直角坐标系中有两个点(3,4),(7,7)
 
使用勾股定理计算两点之间的距离为5
图2:使用勾股定理计算两点之间的距离为5

2. 权重

权重是指某一个因素相对于整个事物的重要程度,它既体现了各个因素所占的百分比,同时也强调了因素的相对重要程度和贡献度。

例如,成绩评分分为平时成绩和考试成绩,平时成绩占总成绩的 30%,而考试成绩占 70%。也就是说,如果平时成绩是 90 分,考试成绩是 80 分,则总成绩是90×0.3+80×0.7=83分。

从这个权重配比来看,相比平时成绩,学校更看重的是考试成绩。

3. K 最近邻算法原理

现在给出一个点 (2,5),很容易判别该点属于三角形的类别,因为它的周围全部都是三角形,如图 3 所示。

坐标系中分布着若干个点
图3:坐标系中分布着若干个点
 
新出现一个点(2,5)
图4:新出现一个点(2,5)
 
同样的道理,给出点 (8,5),也很容易判别这一点属于圆形的类别,如图 5 所示。

新出现一个点(8,5)
图5:新出现一个点(8,5)
 
但如果一点出现在 (5,5) 位置时,如图 6 所示,它应该属于哪一个类别呢?似乎并不好判别,因为它的周围既有三角形,又有圆形。

新出现一个点(5,5)
图6:新出现一个点(5,5)

让我们看一看K最近邻算法是如何解决这个问题的。如图 7 所示,K 最近邻算法首先会计算图像中每个样本点到该观测点的距离。

计算所有点到该点的距离
图7:计算所有点到该点的距离

然后将距离从小到大排序,取出前 k 个值,这里我们假设 k=5,也就是说取离观测值最近的 5 个点,如图 8 所示:

取k=5个点
图8:取k=5个点

然后在这 5 个值中计算各个类别的个数,个数最多的类别,就是该观测值的类别。例如,这里三角形有 3 个,圆形有 2 个,三角形的个数大于圆形的个数,所以该观测值会被判定为三角形。

回想本节开头所给出的两个图,图 4 和图 5。当 k=5 时,点 (2,5) 周围最近的 5 个点全部都是三角形,所以该点被判定为三角形,如图 9 所示。

当周围都是三角形的时候就被判定为三角形
图9:当周围都是三角形的时候就被判定为三角形
 
k=5 时,点 (8,5) 周围最近的 5 个点全部都是圆形,所以该点被判定为圆形,如图 10 所示。

当周围都是圆形的时候就被判定为圆形
图10:当周围都是圆形的时候就被判定为圆形

优秀文章