KNN算法就是K邻近算法,是最简单的机器学习算法之一,主要用于将对象划分到已知的类当中。本节深入浅出地了解一下该算法。

例如,研究生面试时,导师如何确定一个学生适合当研究生呢?往往会根据一些特征或者指标来确定,例如有探索精神、动手能力强、有学术写作能力、能够抗压等一系列条件。他们会觉得这样的学生更有科研创新的潜质,或者说这些学生未来更有可能做出成就。

做个热爱学习的科研人

理论基础

例如一段运动视频,需要判断是打乒乓球还是踢足球。

为了确定分类,定义两个特征,分别是挥手踢脚。当然,挥手和踢脚不能一锤定音,不能说挥手就是打乒乓球,踢脚就是踢足球。

可以统计在比赛的一段时间内,视频里的挥手踢脚的次数。如下表所示:

视频编号 视频类型 挥手次数 踢脚次数
A 乒乓球视频 4801 198
B 乒乓球视频 4603 254
C 足球视频 123 3855
D 足球视频 177 8876
E 足球视频 341 4553
F 乒乓球视频 5649 120
J 乒乓球视频 5310 230
H 足球视频 100 5620
I 乒乓球视频 4320 210

将上面表格里的数据转化为散点图,横坐标为挥手次数,纵坐标为踢脚次数:

视频数据散点图

数据点明显出现聚集特征:

  • 乒乓球:挥手次数[4000,6000],踢脚次数[100,300]
  • 足球:挥手次数[100,400],踢脚次数[4000,9000]

这是一个极端的例子,只有两个特征,非黑即白。

在实际使用中往往是复杂的,参数会比较多,为了提高算法的可靠性,在实施的时候会取K个临近点,这K个点中属于哪一类的较多,将会把待识别的点划分到该类中。为了方便统计,K值通常取奇数。

计算过程

KNN在获取各个样本的特征值之后,计算待识别样本的特征值以及各个已知分类的样本特征值之间的距离,然后找出K个最邻近的样本,根据k个最邻近样本中占比最高的样本所属的分类,来确定待识别样本的分类。

归一化

归一化的目的是为了防止量纲的不统一导致判断错误。

例如,在犯罪电影中,警察通过技术手段获知犯罪嫌疑人的身高为180cm,缺一根手指头;受害人身高173cm,手指健全。目前,投案人甲、乙都宣称自己是受害人。

勾引我犯罪

当有多个参数时,一般将参数构成列表(数组)进行综合判断。本案例中,以(身高,手指数)作为特征,因此犯罪嫌疑人的特征值为(180,9),受害人特征为(173,10)。

于是,对甲乙两人进行判断:

  • 甲身高175cm,缺一根手指,甲的特征值为(175,9)

    • 甲与嫌疑人的特征值距离=(180—175)+(9—9)=5
    • 甲与受害人的特征值距离=(175—173)+(10—9)=3
  • 乙身高178cm,十指健全,甲的特征值为(178,10)

    • 乙与嫌疑人的特征值距离=(180—178)+(10—9)=3
    • 乙与受害人的特征值距离=(178—173)+(10—10)=5

此时,甲的特征值与受害人更接近,断定甲为受害人。乙的特征值与嫌疑人更接近,断定甲为嫌疑人。

显然这个结果是错误的。因为手指和身高有不同的量纲(权值),数字上增加1在手指和身高两个特征是天差地别。

由于参数量纲的原因,需要对参数进行归一化处理,让所有参数有相等的权值。做归一化时,一般使用特征值除以所有特征值的最大值(或者最大值与最小值的差)。在上面的案例中,计算方式为:
$$
归一化特征 = (身高/最大身高180,手指数量/10)
$$
经过归一化之后进行计算:

犯罪嫌疑人的特征值为(180/180,9/10)=(1,0.9),受害人特征为(173/180,10/10)=(0.96,1)。

于是,对甲乙两人进行判断:

  • 甲身高175cm,缺一根手指,甲的特征值为(175/180,9/10)=(0.97,0.9)

    • 甲与嫌疑人的特征值距离=(1-0.97)+(0.9—0.9)=0.03
    • 甲与受害人的特征值距离=(0.97—0.96)+(1—0.9)=0.11
  • 乙身高178cm,十指健全,甲的特征值为(178/180,10/10)=(0.99,1)

    • 乙与嫌疑人的特征值距离=(1-0.99)+(1-0.9)=0.11
    • 乙与受害人的特征值距离=(0.99-0.96)+(1—1)=0.03

此时,甲的特征值与嫌疑人更接近,乙的特征值与受害人更接近。

距离计算

  • 直接相减。不推荐,可能会出现正负抵消的情况
  • 绝对值和,称为曼哈顿距离,基本满足要求。
  • 平方和的平方根,成为欧式距离,更加广泛。

欧式距离

K值的选择

我们一般选取一个较小的数值,通常采取 交叉验证法来选取最优的k值。(也就是说,选取k值很重要的关键是实验调参,类似于神经网络选取多少层这种,通过调整超参数来得到一个较好的结果


博主个人公众号
版权声明 ▶ 本网站名称:陶小桃Blog
▶ 本文链接:https://www.52txr.cn/2022/CVKNN1.html
▶ 本网站的文章部分内容可能来源于网络,仅供大家学习与参考,如有侵权,请联系站长进行核实删除。
▶ 转载本站文章需要遵守:商业转载请联系站长,非商业转载请注明出处!!

最后修改:2022 年 05 月 25 日
如果觉得我的文章对你有用,请随意赞赏