K近邻算法基本原理:
存在一个样本数据集合,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据项与所属分类的对应关系;
输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据的分类标签;
一般来说我们只选择样本数据集中前K个最相似的数据,这就是K近邻算法中K的出处,通常K是不大于20的整数;
最后前K个最相似数据中出现次数最多的分类,即为新数据的分类。
举例来说:
有人曾统计过很多电影的打斗和接吻镜头,然后以此为分类依据,数据如下:
电影名称 | 打斗镜头 | 接吻镜头 | 电影类型 |
---|---|---|---|
California Man | 3 | 104 | 爱情片 |
He is Not Really into Dudes | 2 | 100 | 爱情片 |
Beautiful Woman | 1 | 81 | 爱情片 |
Kevin Longblade | 101 | 10 | 动作片 |
Robo Slayer 300 | 99 | 5 | 动作片 |
Amped II | 98 | 2 | 动作片 |
? | 18 | 90 | ? |
现在有部未知分类的电影,统计出其打斗镜头为18,接吻镜头为90,根据K近邻算法,目前已有5个样本数据,需要计算新数据和样本集中所有数据的距离;
我们以打斗镜头数为横坐标、接吻镜头数为纵坐标构建一个二维坐标系,然后把所有数据放入其中即可计算距离了,如下:

电影名称 | 与未知电影的距离 |
---|---|
California Man | 20.5 |
He is Not Really into Dudes | 18.7 |
Beautiful Woman | 19.2 |
Kevin Longblade | 115.3 |
Robo Slayer 300 | 117.4 |
Amped II | 118.9 |
根据K近邻算法,如果K=4,则前四个最靠近的电影依次为He is Not Really into Dudes、Beautiful Woman、California Man、Kevin Longblade;这四部电影中有3部爱情片、1部动作片;因此新电影的类型为爱情片。
另外再说一下在电影分类的例子里边,可不能简单的认为接吻镜头比打斗镜头多的为爱情片,打斗镜头比接吻镜头多的为动作片哈,要不然如果未知电影的接吻镜头和打斗镜头相同的话,你就只能把这部电影归类为爱情动作片了…
到此《机器学习实战》中的内容复制完毕,接来下聊聊自己的实践所得。
K近邻算法很简单也很容易理解,我们用它来进行手写数字的识别,完整例子如下:
https://newbieyoung.github.io/machinelearninginaction-js/Ch02/demo0.html

在白色画布中用鼠标写一个数字,然后点击识别,即可在console
中看到识别结果;
需要注意的是识别之前,需要先加载并解析样本集;

样本集中包含0-9的数字图片,尺寸为32x32
,每个数字均有5个不同样本,console
中的404
是由于加载机制导致的,因为加载方法考虑了样本数量不确定的情况,因此加载时如果报错则说明当前数字样本已经加载完毕,开始加载下一个数字;
等到输出load end
和parse end
时则说明例子可以正常运行了。
手绘功能使用的是signature_pad,这个组件的原理应该很简单,监听鼠标事件,获得移动点,然后连线即可;难点在于移动速度控制笔画粗细的函数不好确定,容易出现不同速度之间的笔画不平滑导致笔迹凹凸不平。
另外样本图片尺寸之所以为32x32
,则涉及到图片相似度算法。
计算图片相似度的算法有很多,出于简单易实现以及精度方面的考虑,我采用了感知哈希
中的pHash
算法;
主要过程以及实现如下:
1、缩小尺寸,一般缩小为32x32,这也是样本图片尺寸为32x32的主要原因,因为可以省去算法的第一步;

2、简化色彩,将图片转化为灰度图片,进一步简化计算量;

3、对灰度图片的像素值进行离散余弦变换

这时就有疑惑了,离散余弦变换
是什么鬼?
查查维基百科:

刚看第一句,傅里叶变换
又是什么鬼?
一般遇到这种尴尬的情况,会选择放弃治疗,不管了直接看公式:

最常用
!OJBK!搞定!

当然,如果对某个概念并不是很理解的话,至少得知道这个东西有什么用吧!
请看测试离散余弦变换
例子:
https://newbieyoung.github.io/machinelearninginaction-js/test/test0.html

分别是原图、灰度图以及灰度之后进行离散余弦变换
然后再把变换后的值当成像素值的新图;
离散变换值转换为像素值我采用的方法是取的最小值和最大值,然后获得差值,最后把所有的值减去最小值除以差值获得对应比例,最后把该比例换算到0-255的区间即可。
粗略看新图只会发现原图的内容不存在了,仔细看则会发现新图左上角有一块很小的图案,放大后会稍微明显一点;

因此可以简单的理解离散余弦变换
会把图片内容转换为左上角这种类似指纹一样的图案,这也就不难理解第四步了。
4、缩小DCT,虽然DCT的结果是32x32矩阵,但是我们只保留左上角8x8的部分,这部分呈现了图片中的最低频率;

5、计算缩小DCT的平均值;

6、计算hash值,在缩小的DCT矩阵中,如果某一位的值大于或等于平均值则设置为1,小于则设置为0,按照某一顺序得到一个由0、1组成的64位的字符串。

至此就是pHash
算法的全部了。
最后我们把不同图片之间pHash
算法得到的64位指纹
数据的不同位数的个数当成距离
即可(这个距离也被称为汉明距离
)。
另外K近邻算法还有几点需要注意:
上述K近邻算法实现采用的是
暴力计算
的方式,这种方式在样本集很小的时候效果很好;但当样本集增大之后就会很低效,为了解决这个问题,诞生了大量基于树结构的改进算法,比如:K-D树
、球树
等。错误率;
虽然我并没有做这部分工作,但是实际应用时需要对错误率进行测试。
放到这个例子中,你在运行时会有较大概率发现识别错误,这和样本数量太少有一定关系;
识别错误时,你可以在console
中看到:

距离最小的也超过了10
,在pHash
算法中如果不同数据位不超过5
则说明两张图片类似;如果超过10
,就说明差别很大!
同时也说明pHash
算法得到哈希值只是内容特征值,并没有反应结构特征,毕竟我们人识别数字并不是根据图片中某些位置的像素值是多少来判断的。
例子中实现的离散余弦变换是完全按公式实现的,计算量较大;其实是有优化版本的;
样本数据特征如果单位不一致,还需要进行归一化处理,防止计算距离时某些值比重过高;
K近邻算法是分类数据最简单最有效的算法,但也存在着很多缺点,比如计算复杂度高、空间复杂度高、无法给出数据的内在含义等。