--- layout: default ---

从图像到数字

"介绍KNN算法"

Posted by Xz Yao on April 16, 2016

前阵子看到有童鞋问识别数字的问题,我们就来聊聊数字的识别。这个内容局限于一个已经切割好图像的单个数字。单就这个问题来说用的比较多的方法是 KNN- K Nearest Neighbor (最近邻居法)

我们都知道总统是怎么选出来的吧?有人去竞选然后选民去投票。理想状态下票数多者为胜(假设不存在选举人团制度)。在理智的状态下,选民投给的是总统候选人的一些特征(Feature)。 U.S President Election

在这个过程中,我们可以将总统候选人这个人来去人格化,把它抽取为一系列的特征向量。这个向量就包含了总统候选人的各种特质,向量的每个值都是候选人的一些政治主张、颜值(这应该是US总统选举中最最重要的因素了吧)、身价等等特征。值得注意的是,在我们的情境中,总统候选人的特征是和选民无关的(在现实生活中可能一千个选民眼中有一万个总统,这种情境以后再说)。我们拿到手的就是[X1, X2, X3, X4……, Xn]这样的一个矩阵(向量)。我们称之为特征(Feature)。

向量这个概念,可能需要一些数学上的基础知识。与向量对应的概念是标量,标量只有值没有方向,像1+1=2里的1,2都是标量。而向量如下图 vector direction 在空间里,我们可以用一组坐标来表示一个向量。例如上图中的二维坐标系,我们用终点的坐标就可以表示出这个向量:假设终点P坐标为X1, X2,原点O坐标为0, 0。那么(X1-0,X2-0)即(X1,X2)就是这个向量了,所以说一个点也可以表示出向量,一个向量也会指向一个点。两个概念是相同的。从二维往高维去,我们可以做到很高维的空间向量。稍后会给大家展示(物理学家搞的什么四维空间都弱爆了,我们上手就是好几千维……)。

在空间里我们还可以引入距离的概念,两点间的距离之类的。如果两个点的距离越大,是否就意味着两个向量之间的差异越大呢?Obviously!

回到美国总统竞选的话题上来,有两种截然相反的理论可以支持我们选总统。一种是选离自己距离最远的,这样的好处在于平衡,可以让自己不那么脑残粉理智地提出建议,捍卫彼此的对话权。另一种是选离自己距离最近的,这样的好处在于可以让自己爽一点,毕竟政见一致。(对于我这种人,谁理他什么对话权,自己爽才是王道!)但是确实有很多种决断,真实的选举中未必接近就会被选中。

所以,当有一个”总统向量(Candidate Vector)“被丢进人民的海洋时,每个选民都会做出自己的决断。我们假设这一决断与其他”总统向量”是无关的。选民会分别作出”他/她是我的真爱”,”这种辣鸡不配当总统“,”我再犹豫犹豫“这些不同的”标签”(Label)。

那么在这个过程中,你是谁?你也被提取出了和总统候选人维度相同的特征,并对”总统向量”进行了判断。

voting

为了简化这个过程,我们可以简单的在“总统向量”周围选取k个”选民向量”,这几个选民向量会有不同的判断,如果真爱最多,那么他就当选。如果辣鸡最多,那么他就是个辣鸡。这个k就是K Nearest Neighbor中的K的含义。通常k的取值还是比较小的,这样可以大大减少运算时间。

有了KNN的介绍,现在对数字的识别有没有点思路了呢?

几个问题:

  1. 数字中的”总统向量”,这一向量怎么来?这个向量会有多少维?
  2. 数字中的”选民向量”,这些向量怎么来?有哪些标签?
  3. 什么是数字中的“政见相同”?

想一想再来看答案 ***

  1. 数字里的总统向量,就是待测的样本。需要将数字转为灰度图,再转化为一个文本的文件,类似于这样 qq.jpg 之后将每一行合并到第一行中,成为一个行向量。对于一个32x32的数字图片文件来说,它就会变成一个1024x1的向量。
  2. 数字里的选民向量,来自于一定的数据集。这些数据集也需要用上述的方式进行操作,全部转化为1024*1的向量才能进行后续的操作。有0-9共10个标签。
  3. 政见相同就是这个1024维的向量在空间的距离接近。 距离的定义:distance

最后放一张超立方SuperCube的图 supercube