《模式识别与人工智能》

.模式识别与人工智能（2015—2016学年第二学期）姓名：学号：专业：控制科学与工程成绩评定：2016年5月9日引言模式识别与人工智能是60年代迅速发展起来的一门学科，属于信息，控制和系统科学的范畴。模式识别就是利用计算机对某些物理现象进行分类，在错误概率最小的条件下，使识别的结果尽量与事物相符。模式识别技术主要分为两大类：基于决策理论的统计模式识别和基于形式语言理论的句法模式识别。模式识别的原理和方法在医学、军事等众多领域应用十分广泛。模式识别与人工智能事实上是典型的多学科交叉：数学、信息科学、计算机科学、控制科学、生理学、心理学、认知科学和哲学等。正由于此，吸引了众多学科的科学家、工程技术人员致力于模式识别的研究和开发。模式识别研究模式的自动处理和判读的数学技术科学。模式识别中的最基本的问题是解决模式的分类。较全面地看，研究模式的描述、分析、分类、理解和综合。更高层次的模式识别应该还包括对模式的学习、判断、自适应、自寻优和自动发现规律等。所以模式识别在某种意义上和人工智能中的“学习”或“概念形成”相近。模式识别与机器智能的结合将开辟广阔的前景。模式识别分类主要有数据预处理，特征提取、分类器，特征预测评估等。主要研究为贝叶斯决策、线性判别函数，非线性判别函数，近邻法、特征提取、聚类分析等。模式识别的研究是确定一个样本的类别属性（模式类）的过程，即把某一样本归属于多个类型中的某个类型。是指对表征事物或现象的各种形式的(数值的、文字的和逻辑关系的)信息进行处理和分析,以对事物或现象进行描述、辨认、分类和解释的过程,是信息科学和人工智能的重要组成部分。模式识别与统计学、心理学、语言学、计算机科学、生物学、控制论等都有关系。它与人工智能、图像处理的研究有交叉关系。例如自适应或自组织的模式识别系统包含了人工智能的学习机制。又如模式识别中的预处理和特征抽取环节应用图像处理的技术；图像处理中的图像分析也应用模式识别的技术。目录引言...........................................................................................................................................2第一题K均值算法.................................................................................................................4第二题感知准则函数.............................................................................................................7第三题KPCA方法在ORL人脸数据库中实现人脸识别..................................................10程序附录.................................................................................................................................14第一题K均值算法已知数据样本为：(x1,x2,…,x20)={（0，0），（1，0），（0，1），（1，1），（2，1），（1，2），（2，2），（3，2），（6，6），（7，6），（8，6），（6，7），（7，7），（8，7），（9，7），（7，8），（8，8），（9，8），（8，9），（9，9）}，试用C（C=2）均值法进行分类，给出程序和每一次类心的变化过程，汇出动态聚类过程。1原理K均值算法使用的聚类准则函数是误差平方和准则，通过反复迭代优化聚类结果，使所有样本到各自所属类别的中心的距离平方和达到最小。2步骤第一步：K=2，选初始聚类中心为12(0)(1,0);(0)(9,9)TTZZ第二步：将待分类的模式特征集{xi}中的模式逐个按最小距离原则划分给K类中的某一类，即：()min{()}min()(1,2,...,)(1)()()()(1)(1,2,...,)ilijijjjilijijjjdrdrxzriNxGrdrxGrzrGrjK如果则判定式中表示和的聚类中心的距离,r表示迭代次数。于是产生新的聚类第三步：计算重新分类后的各聚类中心，即：(1)1(1)(1,2,...,)(1)(1)(1)jjiGrjjjrxjKnrnrGrxzx式中为类中所含模式的个数。因为这步采取平均的方法计算调整后各类的中心，且定为K类，故称为K-均值法。第四步：(1)()(1,2,...,)jjrrjKzz如果，则结束；否则，r=r+1，转至(2)。3实验结果图像显示用Matlab做仿真，图像如下：z1=1.25001.1250z2=7.66677.3333Y1=1.00001.25001.250001.12501.1250Y2=9.00007.66677.66679.00007.33337.3333G1=0101212300111222G2=Columns1through9678678978666777788Columns10through12989899第二题感知准则函数有两类样本ω1=（x1,x2）={(1,0,1)T,(0,1,1)T}，ω2=（x3,x4）={(1,1,0)T,(0,1,0)T}编写程序，用感知准则函数法求判别函数。1.原理感知器是用于线性可分的的模式分类中的一种最简单的神经网络模型，它由美国Rosenblatt于1957年提出的有监督学习(有导师学习)神经网络模型，其学习算法于1958年提出。所以这一类感知器也称为Rosenblatt感知器，它是由一个线性组合器和一个限幅器组成。其信号流图模型如下图所示：图2-1感知器模型的求和节点作用于输入与权值的线性组合同时也合并外部作用的偏置。求和节点计算的得到的结果，也就是诱导局部域，被作用于硬限幅器，相应地，当硬限幅器输入为正时，其输出为+1，反之为-1。在感知器模型中，12,,,m为感知器的权值，12,,,mxxx为感知器的输入。b为外部偏置。从而感知器的诱导局部域为1miiixb(2.1)感知器的目的是把外部作用12,,,mxxx正确地分为两类，分类的规则是如果感知器输出的y是+1则将12,,,mxxx表示的分类点分配给1L类，如果感知器输出y为-1，则将12,,,mxxx表示的分类分配给2L类。最简单的感知器中存在着被一个超平面分开的两个决策区域，此超平面的定义为10miiixb(2.2)其决策面的示意图如下图所示：1x2x1L2L图2-2在此图中，12,xx表示感知器的输入，1L和2L表示所分的类。决策面的边界即为10miiixb。2.步骤感知器能够正确地工作的前提条件是1L和2L所表示的类必须是线性可分的。而且类间间距越大越好，类内间距越小越好，即能够得到的决策面是线性的平面。为了便于计算，将图2-1中的信号流图的模型绘制成如下形式：01x1x2xmx0b12m硬限幅器输出y线性组合器图2-3等价感知器信号流图在这个信号流图中，偏置bn被当做一个等于+1的固定输入量所驱动的突触权值。因此定义11m个输入向量为121,,,,TmXnxnxnxn这里n表示使用算法迭代的步数，相应地11m个权向量定义为12,,,,TmWnb因此线性组合器的输出可以写为如下形式0mTiiinnxnWnXn(2.3)由于1L和2L是线性可分的，现在假设有121,2,XX，属于1L类，21,2,XX，属于2L类。存在一个权值向量W满足如下条件0TWX对于属于1L类的每个输入向量X0TWX对于属于2L类的每个输入向量X(2.4)下面通过迭代的方式找出能够正确分类的权值向量()Wn。在式(2.4)中，我们假设训练样本集的第n个成员()Xn根据上式算法的权值向量()Wn能够正确分类，那么权值向量的第(1)n此迭代就不用修改，即1WnWn假如0TWXn且Xn属于1L类1WnWn假如0TWXn且Xn属于2L类(2.5)如果根据式(2.4),第n个成员不能够正确分类，那么我们对权值向量做如下修改1WnWnnXn假如0TWXn且Xn属于2L类1WnWnnXn假如0TWXn且Xn属于1L类(2.6)其中n为学习效率。上式(2.4)在所给的样本是线性可分的情况下，可以证明存在一个最大的迭代次数使得()Wn收敛。具体算法步骤如下(1)将+1添加到向量x1,x2,x3,x4的首项，为权值向量赋初值，为学习效率n赋初值；(2)根据式(2.4)，判断向量是否满足式(2.5)的条件，如果满足则不更新权值向量，否则根据式(2.6)更新权值向量。3.运行结果：w=-0.29330.5619-0.39540.7749Xw=1.04350.0862-0.1268-0.6887第三题KPCA方法在ORL人脸数据库中实现人脸识别1.KPCA简介KPCA(KernelbasedPrincipleComponentAnalysis)即基于核的主成分分析，基于核函数的基本原理，通过非线性映射将输入空间投影到高维特征空间，然后在高位特征空间中对映射数据做主成分分析，具有很强的非线性处理能力。KPCA原理如下：输入空间的M个样本(1,2,,),nkkxkMxR，使10Mkkx（中心化保证均值为零），则其协方差矩阵为11MTjjjCxxM而对于一般的PCA方法，即通过求解特征方程获得贡献率最大的特征值及与之相对应的特征向量C;引入非线性映射函数，使输入空间的样本点变换成特征空间的样本点1212,,,(),(),,()MMxxxxxx并满足中心化条件1()0Mkkx则其在特征空间的协方差矩阵为11()()MTjjjCxxM则在特征空间的PCA是求解下列方程的特征值和特征向量C进而有(())()(1,2,,)kkxxCkM由于特征向量可以由数据集线性表示，则V可以由()(1,2,,)ixiM线性表示，即1()Miiivx定义MM矩阵K()()ijijKxx则有2MKK显然满足MK通过对上式的求解，可以得到要求的特征值和特征向量。2.MATLAB程序实现应用KPCA方法实现在ORL人脸数据库中实现人脸识别，要求KPCA中核函数采用多项式核函数：（1）以训练图像的个数为横坐标（训练图像为2,3,4,5,6,7,8,9个）画出识别率图像；通过测试不同数量的训练样本，可以得到相应的各种识别率。图3-1改变训练样本数时的识别率（2）(,)(())diikxxsxxc，以核函数的C（0.5~10，变化步长为0.5）为变量，画出相对应的识别率。在训练样本数为5，以核函数的C（0.5~10，变化步长为0.5）为变量，d为1时，得到的识别率是不变的总是为0.915，识别率如下所示，图3-2改变c步长识别率变化（3）(,)(())diikxxsxxc，以核函数的d（0.5~5，变化步长为0.5）为变量，画出与其对应的识别率图像。在训练样本数为5，测试样本数为5的条件下，以核函数的d（0.5~5，变化步长为0.5）为变量，c为1时，得到的其识别率的变化值为图3-3改变d步长识别率变化程序附录第一题程序%Initializationclearall;closeall;clc;x=[0101212367