初识KNN在线视频

在声控小恐龙中

你先要去设计

指示“跳”(jump)和“低头”(duck)的两种声音样本

然后系统会把你发出的声音

分类为“跳”或“低头”

这个分类有个字母“k”

这里我们就是用KNN进行分类的

在声控小恐龙中

我们首先用MFCC方法提取样本的13个特征

还是那句话

我们这门课程主要学习的不是编程

但我们会用它

例如MFCC具体算法是什么

不用管

会用就好了

现在的人工智能代码框架相对成熟

只要会像用手机那样去用它就好了

然后在KNN中

用欧氏距离公式计算样本之间的距离

先看看计小白对KNN的介绍吧

我们先从它的字母含义开始理解

所谓K它就是一个constant（常数）

第一个N是Nearest 最邻近的

第二个N是Neighbor

中文名是KNN邻近算法

从名字来看可以初步地认为

用中文来讲就是“物以类聚，人以群分”

此话怎讲

我们分析一个人的时候

可以观察TA最亲近的几个人

用那几个人的性格特征去判断TA的性格特征

同理

我们在判断一个未知事物的时候

我们也可以观察离它最近的几个样本

这就是KNN算法的核心要义

大家玩游戏很经常碰到一种情况

你好不容易想玩游戏

却找不到合适的队友

你要从你认识的人

就是你的朋友中

筛选几个合适的游戏伙伴

这就时候你就需要衡量一些参数

比如他们的挂机局数和胜利局数

然后这两个指标能将他们分成几类人

第一类

他们从来不打游戏

还有一类

虽然他们很厉害

但他们有可能因为各种情况

打到一半就挂机了

还有一类就比较平均

TA胜利得多 挂机得少

这种同学就是很好的游戏伙伴

我们设计一种程序

和KNN联系在一起

这是关于分类问题的算法

联系我们刚刚的思路

就可以把同学们大致的分成三类

这是一个基于实例的算法

什么意思呢

就是这些例子都是可以从生活中找到的

我觉得这非常地实在

因为没有什么虚头巴脑的东西

你给它什么例子它就是什么例子

这些同学的挂机次数、胜利次数

都是很实际的例子

那么这个算法的思想是什么样的呢

K值越大

我们框选样本的范围就越大

看这个图

当圆圈越大

K值 也就是我们包含样本的数量

也就越大

当K等于3时

我们实线小圆的范围之内

有两个红色图形和一个蓝色图形

其中绿色的小点点是我们不知道的

我们要判断它的类别

这个例子中

因为少数服从多数 基于统计的方法

我们判断它属于三角形

然而 K取不同的值时

结果可能完全不同

在这个例子中K取5

我们重新数（虚线大圆范围中）

情况就发生了转折

蓝色变成了三个而红色还是两个

基于统计的方法

判断绿色是属于蓝色正方形的同一类

一个农场里面有鹰也有鸡

他通过看别人来认清自己

那它会觉得自己是鹰还是鸡呢

那么首先看它的范围

它的这个范围里面有鸡也有鹰

然后呢 它如果看到一个非常小的范围里面的话呢

首先把它框住

框住之后呢 是有两只鸡一只鹰

那它觉得自己是什么

它觉得自己 它会首先本能认为自己这个群体中的多数

所以它会认为自己是一只鸡

那如果我们框住一个更大的呢

那里面也有五只动物

包括他自己就是六只

其中鹰占了三只 占了二分之一

那么它也会本能的认为自己是一只鹰

这个就是一个全部样本里面的k的选择的不同

这里面的话 k选择的是3 这个是5

然后呢 这个knn让我想到一个我们经常说的话

就是物以类聚 人以群分

然后是出自战国策·齐策三

就是其实在一起久了的人 都是性格啊什么的都差不多

然后呢 相似相容的原理我们也是懂得

所以说其实在一起的一部分是我们本能的认为他们有很多的相似点

他们可以它放为同一个种类

我觉得很新颖 就是我们都在从百度上找资料

他一下举了一个小鹰要知道自己是什么动物的时候

我就没听过这个例子 我觉得很新奇 然后一下就引起我兴趣了

然后我有点明白了 有点懂了 好厉害这个人

下面讲一讲k值算法的一个大概算法步骤

首先我们要构建一个模型 什么叫模型呢

简单的例子 比如说一个人的身高和体重就可以作为一个坐标轴中的x和y轴

那么每个人的身高和体重就可以归纳成一个数学的二维坐标系中的点

那么这样之后 我们就构建了一个自己的模型了

同时加上我们更多的身体数据

比如说三围啊 或者之类的话

我们就可以把我们的模型扩充成其他的维度 三维四维

或者是更多的维度 这个取决于我们信息的复杂程度

我们信息程度越复杂它的维度就越高

当然这并不影响我们在高纬度空间中计算我们的距离

因为我们有欧式空间的一个距离公式

我们未知样本和其他训练样本的距离计算出来之后

我们就可以根据我们的k值选出最大的一个距离

最大的距离是隔的最远的一个极限值

比如说我们k值取到5 离它第5远的一个值数 它的距离是3

那么当距离小于3的我就把它框选进去 距离大于3的我们就不要了

我们重复着2 3 4步直到我们所有的训练样本距离都算完之后

我们框选中的距离样本之中

我们要去统计不同样本每个类别出现的次数是多少

然后第七步 我们选择出频数最大的类别作为未知样本的类别

这就是knn算法的基本步骤

然后呢 讲一下knn算法的三个要素

第一个是k值的选择 第二个是距离度量 第三个是分类决策的规则

K值取值不能太大也不能太小

最好在20以内

然后距离度量

knn算法可以用来度量两个样本间是相似度

有三个 一个是欧氏距离 第二个是曼哈顿距离 第三个是闵可夫斯基距离

然后分类决策的规则 它一般都是多数表决方法

就是输入实例的k个邻近的多数类决定输入实例的类

这是三个基本要素 当三个要素确定之后

对于一个新的输入实例 它所属的y值也确定了

这个范围之内的选取就没有涉及到很多数学知识

就直接取一个半径圈一圈然后来判断

第三点 讲它的劣势缺点

这个范围里面的数据越多就需要去判断更多的这些数据去推测中间这个图形是什么图形

所以对计算机的能力要求会比较高

谢谢小白陈泳翰同学的现场演绎

刚才有2个大大的问号 你知道原因吗

看看计小白对KNN的介绍吧

来认识下KNN（k-NearestNeighbor）这个新朋友吧

KNN 我们先分解为K-NN

先来说说NN原理

即“就近原则”

K-NN中的NN是为了按特征分类

物以类聚 人以群分

计小白的宿舍有4个小伙伴

小A 小B 小C 还有小D

休息活动时 小A和小C喜欢玩篮球

而小B和小D就喜欢玩跳绳

计小白也喜欢玩篮球

他就会去小A和小C那边

可到了聚餐时刻

小A和小D却是无辣不欢的主

而计小白一吃辣就

计小白就会和小B和小C一起吃饭

也就是说 物以类聚 人以群分

在不同场合 人以群分的分类标准是不同的

不同的分类标准 也就是定义不同的距离 即相似度

例如两人间的饮食爱好间的距离 运动兴趣间的距离等等

在刚才的NN中 计小白是需要被分类的样本

而四个小伙伴小A 小B 小C和小D是已经被分类的样本

换一个说法 NN有两种样本

一种是还没有类别的样本

另一种是已经有类别的样本

没有类别的样本

会根据与已经有类别的样本之间的某种距离

选择最邻近的样本的类别作为自己的类别

我们再来说说K-NN的K

在物以类聚 人以群分时

分类要考虑K个最邻近的样本

如果我们要给计小白分类

就要选择在某个标准下与计小白最邻近的前K个样本

然后少数服从多数

这K个样本属于哪个类别的多

计小白就属于哪个类别

那电脑要怎么帮忙呢

电脑先记录下了土豆们 鼠标们的长度和宽度

然后把长度和宽度 作为坐标轴的X轴和Y轴

那土豆们 鼠标们在坐标轴的表示就是这样的

电脑同时记录下了计小白的长度和宽度

计小白在坐标轴的表示又是这样的

在这个坐标轴上 点与点的距离就是相似度的距离

距离越短 则越相似 这是NN

K的取值不同 计小白的分类结果就不同

如果K设为3 和计小白最相似的是这三张照片

有2个土豆 1个鼠标

那按照少数服从多数 计小白就长得像土豆

如果K设为5 就有了五张照片

依旧有2个土豆 但另外3个都是鼠标

如果继续按照少数服从多数 那计小白就会更像鼠标了

好了 恭喜你 又认识了KNN这个新朋友

还不止呢 在刚才 电脑用长度加宽度来区分了土豆和鼠标

这个长度加宽度在人工智能中就称为特征

长度加宽度的坐标轴称为特征空间

我们再来对KNN做一个小结

把已经分类或需要分类的样本在定义的特征空间上表征

需要分类的样本选择特征空间上和自己最邻近的K个样本

需要分类的样本的类别就是这K个样本中最多的那个类别

特征 特征空间 KNN 我们理解了

继续加油吧

谢谢计小白

计小白的介绍已经解释了刚才那两个大大问号

对第一个问号的解释

需要分类的样本选择特征空间上和自己最邻近的K个样本

与圆 与半径其实没有关系

直接根据距离选择距离最小的

也就是最邻近的k个样本

对第二个问号的解释

计算量与k的取值没啥关系

是与已经分类的样本多少有关

不管k取值多少

都需要预先计算出需要分类的样本和所有已经分类的样本之间的距离