a3模式识别与智能计算第三章.pptVIP

模式识别与智能计算杨淑莹教授天津理工大学计算机科学与工程学院第三章模式相似性测度3.1模式相似性测度的基本概念3.2距离测度分类法3.1模式相似性测度的基本概念模式识别最基本的研究问题是样品与样品之间或类与类之间相似性测度问题。判断样品之间的相似性常采用近邻准则，即将待分类样品与标准模板进行比较，看跟哪个模板匹配程度更好些，从而确定待测试样品的分类。近邻法则在原理上属于模板匹配。原理上说近邻法是最简单的。但是近邻法有一个明显的缺点就是计算量大，存储量大，要存储的模板很多，当每个测试样品要对每个模板计算一次相似度时，所需的计算时间相对其他方法多一些。1．样品与样品之间的距离设有两个样品的特征值分别为Xi,Yi这两个样品可能在同一个类中，如图a所示，也可能在不同的类中，如图(b所示。因此可以计算同一个类内样品与样品之间的距离，也可以计算属于不同类样品与样品之间的距离。样品与样品间的距离计算有四种方法，它们是欧氏距离法、夹角余弦距离法、二值夹角余弦法和具有二值特征的Tanimoto测度，如表所示。计算距离方法样品间距离计算公式说明欧氏距离Dij越小则两个样品距离越近，就越相似。马氏距离Dij越小则两个样品距离越近，就越相似。夹角余弦距离S值越大则相似度越大。特征是二值时的夹角余弦要求Xi,Xj向量的各个特征都是以二值（0或1）表示，越大越相似。具有二值特征的Tanimoto测度要求Xi,Xj向量的各个特征都是以二值（0或1）表示，越大越相似。2．样品与类之间的距离样品与类之间的距离可以形象表示如图所示。ω是代表某类样品的集合，ω中有N个样品，X是某一个待测样品。样品与类之间的距离计算方法有两种。如下所述：(1)计算该样品到ω类内各个样品之间的距离，将这些距离求和，取平均作为样品与类之间的距离。样品与类之间的距离可描述为：(2)计算ω类的中心点M(ω)，以中的所有样品特征的平均值作为类中心，然后计算待测样品X到ω的中心点M(ω)的距离。3．类内距离类内距离指同一个类内任意样品之间距离之和的平均值。取ω内所有N个点的平均距离以表示其类内距离：4．类与类之间的距离设有两个类ωi、ωj，如图所示，计算类与类之间的距离有多种方法，如最短距离法、最长距离法、重心法和平均距离法等。如表所示。类间的距离类间的距离距离方法距离定义说明最短距离法规定两个类间相距最近的两个点之间的距离，为两类的距离。最长距离法规定两个类间相距最远的两个点之间的距离，为两类的距离。重心法求各类中所有样品的平均值作为类的重心，用两类的重心间的距离作为两类的距离。Ni、Nj分别是ωi、ωj类中样品的个数平均距离法计算两类之间所有样品的距离，求和，取距离的平均值作为两类间的距离。3.2距离测度分类法3.2.1模板匹配法1．理论基础在图像识别中，最简单的识别方法就是模板匹配。就是把未知图像和一个标准的图像相比，看它们是否相同或相似。下面讨论两类和多类的情况。（1）两类别设有两个标准手写数字，样品模板为A和B，其特征向量为n维特征：XA=(xA1,xA2,…,xAn)T和XB=(xB1,xB2,…,xBn)T。任何一个待识别的手写数字X，其特征向量为：X=(x1,x2,…,xn)T，那么，它是A，还是B呢？任意两点X,Y之间的距离：根据距离远近可作为判据，构成距离分类器，其判别法则为：（2）多类别设有个类别：ω1,ω2,…,ωM.每类由若干个向量表示，如ωi类，有：对于任意被识别的数字X计算距离d(Xi,X)，若存在某一个i，使即到某一个样品最近，则具体判别时，X,Y两点距离可以用表示，若，则。这就是多类问题的最小距离分类法。3.2.2基于PCA的模板匹配法1.理论基础在使用模板匹配法之前，先对特征进行主成分分析。按照一定贡献值，提取前m个主分量，用较低维数的特征来进行分类。2.实现步骤：（1）选取各类全体样本组成矩阵Xn*N，待测样品为Xn*1。（2）计算Xn*N的协方差矩阵Sn*n。（3）计算Sn*n的特征值λ1≥λ2≥…λn和特征向量Cn*n。（4）根据一定的贡献率，选取Cn*n的前m列，构成Cn*m。（5）计算样本库样本主成分Xm*N=CTn*mXn*N样品主成分Xm*1=CTn*