模式识别算法
1. K-Nearest Neighbor
K-NN可以说是一种最直接的用来分类未知数据的方法。简单来说,K-NN可以看成:有那么一堆你已经知道分类的数据,然后当一个新数据进入的时候,就开始跟训练数据里的每个点求距离,然后挑离这个训练数据最近的K个点看看这几个点属于什么类型,然后用少数服从多数的原则,给新数据归类。
实际上K-NN本身的运算量是相当大的,因为数据的维数往往不止2维,而且训练数据库越大,所求的样本间距离就越多。就拿我们course project的人脸检测来说,输入向量的维数是1024维(32x32的图,当然我觉得这种方法比较silly),训练数据有上千个,所以每次求距离(这里用的是欧式距离,就是我们最常用的平方和开根号求距法) 这样每个点的归类都要花上上百万次的计算。所以现在比较常用的一种方法就是kd-tree。也就是把整个输入空间划分成很多很多小子区域,然后根据临近的原则把它们组织为树形结构。然后搜索最近K个点的时候就不用全盘比较而只要比较临近几个子区域的训练数据就行了。
当然,kd-tree有一个问题就是当输入维数跟训练数据数量很接近时就很难优化了。所以用PCA(稍后会介绍)降维大多数情况下是很有必要的
Principle Component AnalysisPCA
译为主元分析或者主成份分析,是一种很好的简化数据的方法,也是PR中常见到不能再常见的算法之一。CSDN上有一篇很不错的中文博客介绍PCA,《主元分析(PCA)理论分析及应用》,主元分析比较大的意义就是让我明白了线性代数中特征值跟特征向量究竟代表什么,从而让我进一步感受到了线性代数的博大精深魅力无穷。
PCA简而言之就是根据输入数据的分布给输入数据重新找到更能描述这组数据的正交的坐标轴,比如下面一幅图,对于那个椭圆状的分布,非常方便表示这个分布的坐标轴肯定是椭圆的长轴短轴而不是原来的x y。
那么如何求出这个长轴和短轴呢?于是线性代数就来了:我们求出这堆数据的协方差矩阵(关于什么是协方差矩阵,详见本节最后附的链接),然后再求出这个协方差矩阵的特征值和特征向量,对应特大特征值的那个特征向量的方向就是长轴(也就是主元)的方向,次大特征值的就是第二主元的方向,以此类推。
模式识别(英语:Pattern Recognition),就是通过计算机用数学技术方法来研究模式的自动处理和判读。我们把环境与客体统称为'模式'。随着计算机技术的发展,人类有可能研究复杂的信息处理过程。信息处理过程的一个重要形式是生命体对环境及客体的识别。对人类来说,特别重要的是对光学信息(通过视觉来获得)和声学信息(通过听觉来获得)的识别。这是模式识别的两个重要方面。市场上可见到的代表性产品有光学字符识别、语音识别系统。
模式识别是人类的一项基本智能,在日常生活中,人们经常在进行'模式识别'。随着20世纪40年代计算机的出现以及50年代人工智能的兴起,人们当然也希望能用计算机来代替或扩展人类的部分脑力劳动。(计算机)模式识别在20世纪60年代初迅速发展并成为一门新学科。
模式识别是指对表征事物或现象的各种形式的(数值的、文字的和逻辑关系的)信息进行处理和分析,以对事物或现象进行描述、辨认、分类和解释的过程,是信息科学和人工智能的重要组成部分。