《模式识别》（张向荣）教案全套 第1-10章 模式识别概论-半监督学习

PAGEPAGE10《模式识别》教案人工智能学院课程名称：学分/学时：3/40+16适用专业：先修课程：概率论与数理统计、线性代数后续课程：机器学习、数据挖掘开课单位：人工智能学院智能所一、课程性质和教学目标课程性质：智能科学与技术专业的专业必修课。二、课程教学内容及学时分配详见表格。三、教学方法四、考核及成绩评定方式最终成绩由平时成绩和期末成绩组合而成，所占比例如下:平时成绩：40%。其中包含出勤率、平时作业、课堂展示和上机C++或Matlab期末考试成绩：60%。主要考核对模式识别基础知识的掌握程度。五、教材及参考书目教材：张向荣冯婕焦李成刘芳，《模式识别》，西安电子科技大学出版社，2019参考书目:RichardGStork2003AndrewD.Copsey20043.吴建鑫，《模式识别》，机械工业出版社，20204.孙即祥，现代模式识别，高等教育出版社，2008课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第一讲授课教师唐旭授课章节第一章模式识别概论1.1什么是模式识别基本要求重点、难点（1）YF(x)解读：x的定义域取自特征集，Y的值域为类别的标号集，F是模式识别的判别方法。（3）鲈鱼和鲑鱼识别步骤如下：abcd.设计分类器，对鲈鱼和鲑鱼进行分类。（4）模式识别过程（5）有监督学习(Supervisedlearning)（6）无监督学习(Unsupervisedlearning)样本的类别标记和分类代价未知，由聚类器形成“聚类”(clusters)或者“自然组织(naturalgroupings)”。事先不知有多少类，有哪些类，只能根据样本间的相似性进行聚合。课外学习要求复习先验概率、条件概率、全概率公式等相关内容课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第二讲授课教师唐旭授课章节第一章模式识别概论1.5模式识别方法1.6模式识别应用领域第二章贝叶斯决策理论2.1引言2.2基于最小错误率的贝叶斯决策基本要求重点、难点a.模板匹配b.统计方法decisionboundaryc.句法方法d.神经网络（2）模式识别的应用领域广泛，例如，文字处理、生物特征识别、生物医学、遥感、文档分类、预测决策、机器人等等。（3）贝叶斯决策的两个要求：①各个类别的总体概率分布(先验概率和类条件概率密度)是已知的②要决策分类的类别数是一定的最小错误率准则最小风险准则Neyman-Pearson(黎曼皮尔逊)准则最小最大决策准则（4）几个重要概念a.先验概率Pi表示未获得观测数据之前类别的分布；b.类条件概率pxi表示在类条件下x的概率分布密度；c后验概率Pix表示在x出现条件i下类出现的概率。课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第三讲授课教师唐旭授课章节第二章贝叶斯决策理论基本要求了解基于最小错误率的贝叶斯决策和基于最小风险的贝叶斯决策重点、难点（1）采用类条件信息——类条件概率密度函数P(x|1)：鲈鱼的属性分布；P(x|2)：鲑鱼的属性分布（2）贝叶斯公式先验概率，后验概率，概率密度函数之间关系P(|x P(x|)P(i) i2P(x)P(x|)P()2i 2 j jP(x|j)P(j) jj1为x的概率密度贝叶斯公式通过类条件概率密度形式的观察值，将先验概率转化为后验概率。（3）后验概率含义P(1|x)：表示当观测向量为x值时,是鲈鱼的概率。P(2|x)：表示当观测向量为x值时,是鲑鱼的概率。（4）基于最小错误率的贝叶斯决策如下：P(1|x)P(2|x),x1P(1|x)P(2|x),x2等价形式|x)P(j|x),xi,P(x|i)P(i)P(x|j)P(j),xi,jjl(x)P(x|1)P(2),x1,P(x|)P() 2 1 2)ln(h(x)ln[l(x)]lnp(x|)lnp(x| )),x)ln(1 2 P()2 2（5）最小风险贝叶斯决策上述最小错误率决策中，使错误率达到最小是重要的。但实际上，有时候需要考虑一个比错误率更广泛的概念—风险，而风险又是和损失紧密相连的。我们对样本的分类不仅要考虑到尽可能作出正确的判断，而且还要考虑到作出错误判断时会带来什么后果。最小风险贝叶斯决策正是考虑各种错误造成损失不同而提出的一种决策规则。jj最小风险贝叶斯决策规则为：如果R(aii。实现过程：

x)min{(aj1,...,a

x)}，则①已知先验概率和类条件概率，根据贝叶斯公式计算出后验概率；②利用后验概率和决策表，计算采取每种决策的条件风险;③比较各个条件风险的值，找出条件风险最小的决策。课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第四讲授课教师唐旭授课章节第二章贝叶斯决策理论基本要求了解正态分布时的统计决策重点、难点（1）判别函数（DiscriminantFunction）用于表决策的某些数gi(x)称为别函数每个别对应一判别，gi(x),i,cgi(xkgi(x,k为正常数gi(xgi(xk,kgi(x),ln(gi(x))用f(gi(x))替换gi(x)，其中f()为单调递增函数（2）决策面对于cd维特征空间分成c判决区域Ri是特征空间中的一个子空间，判决规则将所有落入Ri的样本x分类为类别i；（超平面；（3）分类器设计gx。gixi2, cgjxi,jgixgjxgi(x)p(i|x)gi(x)p(x|i)p(i)gi(x)lnp(x|i)lnp(i)gixRix（4）两分类下的判别函数和多分类下的判别函数gxxg2x②对于多类问题，模式有1,2,...,c个类别。转换成多个两分类问题。可分三种情况：a.每一模式类与其它模式类间可用单个判别平面把一个类分开。b.每个模式类和其它模式类间可分别用判别平面分开。c.每类都有一个判别函数。课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第五讲授课教师唐旭授课章节第三章线性和非线性判别分析3.1Fisher线性判别基本要求Fisher重点、难点（1）线性判别函数的一般形式①gxwTxw0式中，x为d特征量x,x, ,xT，又称本向，1 2 dww,w, ,wTgx0w1 2 d 0数，成为阈值权或者偏置。②决策规则gxxg2x如果gx0，则决策xgx0，则决策x2gx0，可将x任意分到某一类，或拒判。（2）Fisher准则函数YFisher目标函数:S ()2J(w)b1 2 J(w)S S2S2 ， w 1 2 w其中()2表示不同类的投影点尽量分开，S2S2表示同一1 2 1 2类的投影点尽量靠近。（3）Fisher准则函数求解将J(w变成w的显函数w*经过推导，可得w*S1μμw 1 2（3）Fisher线性分类一维空间的分类面是一个点，将两类分开即是确定一个阈值w0，分类规则如下，y,x1，yw,x 0 2 NN np1p2其中1 2或11 22或1 2 2 N1N2 2 N1N22课外学习要求第一次大作业Fisher辨别分析UCIIrissonar34150Sonar260208训练和测试样本有三种方式进行划分:(三选一)1)将数据随机分训练和测试，多次平均求结果2)k折交证3)留1法(针对不同维数，画出曲线图;)仿真结果+报告。课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第六讲授课教师唐旭授课章节第三章线性和非线性判别分析3.2感知准则函数基本要求了解不同线性判别函数的算法和步骤重点、难点（1）基本概念①线性可分性假设样本集D1,x2, ,xm，为样本个数m，为n维向量，其中包含类和2。果存在个向满足如条件：aTx0,x, i i 1aTx0,x,i i 2则称样本集是线性可分的，反之是线性不可分的。②样本的规范化；对于线性可分的样本集，若令xxi,xi1,，则样本集线性i x,x, i i 2可分的条件可改写为aTx0。iixi。③解向量和解区对于线性可分的一组样本1,x2, ,xm(规范化增广样本向量)，若存在一个权向量a*满足a*Tx0，则称a*为一个解向量，在i权值空间中所有解向量组成的区域称作为解区。④对解区的限制b0xi满足axbTibxi。入余量b主要是为了避免求解权向量的算法收敛到解区边界的某点上。（2）感知器算法基本思想：采用感知器算法(PerceptionApproach)能通过对训练模式样本集的“学习”得到判别函数的系数。样本线可分足wT,i,, ,N其xi,xi1i i x,x i i 2对于权向量w，如果某个样本x被错误分类，wTx0。k i定JwwT。p kwTxk0当且仅当函数取得最小值0时，求得最优的w。可以用梯度下降法进行求解。（3）三种梯度下降优化框架批量梯度下降法BatchGradientDescent,BGD随机梯度下降法StochasticGradientDescent,SGD小批量梯度下降法Mini-batchGradientDescent,MBGD课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第七讲授课教师唐旭授课章节第三章线性和非线性判别分析3.3广义线性判别分析3.4k近邻基本要求了解多类分类问题的设计；掌握最近邻和k-近邻算法重点、难点（1）广义线性判别函数判别函数的一般形式：k1gxf1xf2x fkxfix,i1i,kfixfkx1k1gxwfx换iii1WTYgY0,x10,x 2（2）近邻法（程）近邻法则在原理上属于模板匹配。（3）最近邻法算法思想将与测试样本最近邻样本的类别作为决策的方法。对一个C类别问题每类有Ni个样本,C则第i类的判别函数：gxminxxk,k,N，i k i i其中xk表示是类的第k个样本。i i最近邻规则是次优的方法，通常的错误率比最小可能错误率（即最小贝叶斯法则的错误率）要大。补充：这里需要补充常见的距离尺度度量。（4）K-近邻法则kK在所有N个样本中找到与测试样本的k个最近邻者，其中第i个类别所占数为gix,i2, ,c，策规则：如果gjxgix，i则决策xj。K近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。（5）近邻法的快速算法剪辑最近邻方法：压缩最近邻方法：剪辑的结果只是去掉了两类边界附近的样一般称这类方法为压缩近邻法。第二次大作业分析K近邻算法的错误率推荐数据集课外学习要求数据:UCI数据库1中sonar和Iris数据；自然图像:Mnist手写体数据集2、CIFAR数据集3；遥感图像:UCM数据集4，NWPU数据集5。作业形式:程序+大报告+上机课演示1/ml/index.php2/exdb/mnist/3/~kriz/cifar.html4/datasets/landuse.html5/people/JunweiHan/NWPU-RESISC45html课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第八讲授课教师唐旭授课章节第三章线性和非线性判别分析3.5决策树基本要求了解ID3决策树构建方法及特点重点、难点（1）决策树个子节点样本（）（2）ID3ID3ID3（当的分支，重复上面的过程。PAGEPAGE20决策树节点停止分裂的一般性条件：①最小节点数②熵或者基尼值小于阀值。③决策树的深度达到指定的条件④所有特征已经使用完毕，不能继续进行分裂。ID3缺点：③不能处理缺省值④没有对决策树进行剪枝处理，很可能会出现过拟合的问题（3）C4.5C4.5是对ID3的改进算法①对连续值的处理②对未知特征值的处理④规则的派生课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第九讲授课教师唐旭授课章节无具体内容翻转课堂，前三章复习基本要求PAGEPAGE21课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第十讲授课教师唐旭授课章节第四章无监督模式识别4.1高斯混合模型（GMM）4.1.1单高斯模型4.1.2高斯混合模型基本要求了解高斯混合模型用于聚类应用的方法重点、难点（1）高斯混合模型（GMM）k（EM）（2）单高斯模型基本定义：若随机变量x服从一个数学期望为u、方差为2的高斯分布，则该分布记为Nu,2。在统计学中，u指的就是样本均值，2为标准差。一维情况下高斯分布的概率密度函数为：1 xu2Nx;u, exp 2 2 高维情况下的高斯分布模型的概率密度函数为：N;, 1 p1xuT1xu 2 其中x是duu差（3）高斯混合模型高斯混合模型假定样本数据分布服从几个高斯分布的加权和K的形式PrxkN;uk,k。k1其中的任意一个高斯分布称作这个模型的一个分量。k是混合K系数，表示每个分量的权重。需满足：k1,0k1。k1（4）将高斯混合模型用于聚类的具体步骤Step1:以k为概率随机选择K个高斯分布分量中的一个；Step2Step1Step1课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第十一讲授课教师唐旭授课章节第四章无监督模式识别4.1高斯混合模型4.1.3EM算法求解高斯混合模型4.2动态聚类算法4.2.1K-均值算法基本要求了解高斯混合模型用于聚类应用的方法；了解K均值算法。重点、难点（1）EM算法EM步计算最大化在E步上找到的期望对数似然的参数。然后用这些参数估计来确定下一步中隐含变量的分布。EM要求解问题X的一般形式是：*argmaxPr(Xx,Yy;)。 jjyY其中Y是隐含变量，如果已知数据点的分类标签Y，则可以使用最大似然估计直接求解模型参数。EM算法的基本思路是：随机初始化一组模型参数(0)，并根据后验概率更新Y的预期E(Y)，然后用E(Y)代替Y求出新的模型参数(1)。如此迭代直到趋于稳定。EM算法的具体步骤：Step1k设置kuk和k的初始值，然后计算对数似然函数；Step2:E步：假设模型参数已知，引入隐含变量，该隐变量在高斯混合模型中表示数据点由各个分量生成的概率。(i,k) kN(xn|uk,k)KNx|u,)j n j jj1Step3:M(ik就是“数据点由分量k4.1.2kuk和kNNk(i,k)i1 N1(i,k)(xu)(xu)Tk N i k i kki1 Nu1(i,k)xk N iki1 NKk NN KStep4log{kN(x;ukki1 kStep5:检查参数是否收敛或对数似然函数是否收敛，若不收敛，则返回Step2。（2）K-均值算法数据的优化过程是从“不合理”划分到“最佳”划分，是一个动态的迭代过程。K-均值(K-means算法要点：K均值准则函数：k kJJ||xm||2i ii1 i1算法流程：Step1：初始化：随机选择k个样本点，并将其视为各聚类的初始中心m1,m2,...,mk；Step2：按照最小距离法则逐个将样本x划分到以聚类中心m1,m2,...,mk为代表的k个类C1,C2,...,Ck中；Step3：计算聚类准则函数J，重新计算k个类的聚类中心m1,m2,...,mk；Step23知道聚类中心函数J不减小。优点：简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。缺点：结果与初始聚类中心有关；必须预先给出聚类的类别数k；不适合发现非凸面形状的聚类课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第十二讲授课教师唐旭授课章节第四章无监督模式识别4.2动态聚类算法4.2.2模糊聚类算法4.2.3密度聚类法基本要求了解模糊C均值(FCM)算法，DBSCAN算法重点、难点（1）模糊数学基本知识1965L.A.ZadehFuzzySets隶属度函数：表示一个对象xA常记为AxA即集A），取值范围是0,1，即0Ax1。XxA。对于限个象x2, ,xn，模糊合A可以示为：AAxi,xi。模糊集的基本运算：并集：ABxxAx,Bx，交集：ABxinAx,Bx，Ax1Bx。特征模糊化：特征的模糊化是指根据一定的规则把普通意义下的一个或几个特征变量变成多个模糊变量,用来表达原始特征的某一局部特性。模糊分类：用模糊子集代替确定子集,从而得到模糊的分类结果,即分类结果的模糊化。（2）模糊C均值(FCM)算法C均值：把N个样本{x1,x2,...,xN}划分成C个子类G1,G2,...,GCCJxm2，i jj1xiG其中mj为第j个子类Gj的聚类中心；xi表示分到Gj的所有样本,j1,2,...,C。CCj(xi是第i个样本j类GjCNJ[(x)]bxm2,f j i i jj1i1其中b1是一个可以控制聚类结果的模糊程度的常数。约束条件为一个样本属于各个聚类的隶属度之和为1,即Cj(xi)1,(i1,2,...,N)。j1利用拉格朗日乘数法来求解在条件式(2)约束下式(1)的极小值。令优化的目标函数为L[(x)]bxm2(x)，CN N Cj i i j i j i ji1 i1 j分别求L对mjj(xi0Nx)bxj i imji1 ,(j2,...,C)，Nx)bj ii11ximj 21b1j(xi)C 1b1i2N;j2C。1ximj 2j1（3）DBSCAN算法描述nMinPts①Repeat②从数据库中抽取一个未处理过的点；③If④找出所有从该点密度可达的对象，形成一个簇；⑤Else（）⑥跳出本次循环，寻找下一个点；⑦Until课外学习要求第三次大作业Kmeans和FCM算法性能比较，要求如下：1.查阅无监督聚类的评价标准有哪些，选择其中一个标准作为后续试验的验证指标。2kmeansFCM选做：利用图像分割任务验证算法。课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第十三讲授课教师唐旭授课章节第四章无监督模式识别4.3层次聚类算法基本要求了解相关的层次聚类算法重点、难点（1）层次聚类算法（2）自上而下的算法KKStepCStep2：使用K-均值算法把簇C划分成指定的K个子簇，i1,2,...,k，形成一个新的层；Step2KK（），（3）自下而上的算法K对于样本数据集D{x1,x2,...,xn}Step1：把将数据集中的每个样本单独看成一个簇，得到最底层的簇的集合C{c1,c2,...,cn}，其中每个簇只含有一个样本ci{xi}；Step2：重复以下步骤，直到所有样本被聚类到同一个簇或者满足特定的停止条件：①从C中找到两个“距离”最近的簇：minD(ci,cj)；②合并簇ci和cj，形成新的簇cij；③从C中删除簇ci和cj，添加簇cij和cj，计算D(c1c2有以①单连锁：把两个簇中相距最近的两个点之间的距离作为簇间距离。距离。课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第十四讲授课教师唐旭授课章节第五章特征选择5.1引言基本要求了解特征优化方法，类别可分离性判据及经典特征选择算法重点、难点（1）特征优化特征优化有两种方法：假设有D维特征向量空间，y{y1,y2,...,yD}y：①特征选择是指从原有的D后的dxdDxy的一个子集，因此每个分量xi必然能在原特征集中找到其对应的描述量xiyj。A:YX函数，即xWTyi j（2）类别可分离性判据①基于距离的可分性判据Fisher准则是以使类间距离尽可能大同时又保持类内距离较小这一种原理为基础的。同样在特征选择中也可以使用类似的原理，这一类被称为基于距离的可分性判据。优点：定义直观、易于实现，因此比较常用。②基于概率分布的可分性判据p(x|2p(x|端情况是对所有xp(x|p(x|2x③基于熵函数的可分性判据特征对分类的有效性也可以从后验概率角度来考虑。把类别i2c机向量x，给定x后|x)i如果根据x能完全确定，则就没有不确定性，对本身的如果x完全不能确定，则不确定性最大，对本身的观察所提供信息量最大，此时熵为最大，特征最不利于分类。（3）①最优搜索算法：分枝定界法lrl-r法)③智能优化算法：遗传算法、模拟退火法等。课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第十五讲授课教师唐旭授课章节第八章支撑向量机8.1支持向量机的引入基本要求了解间隔的概念，数据集的线性可分性、超平面、函数间隔、几何间隔等基本概念，掌握支撑矢量机学习算法。重点、难点（1）数据集的线性可分性12m位移项b，使得超平面TxbTxby1 i i Txby1i i（2）支撑矢量机学习算法根据训练数据是否线性可分，支持向量机方法可分为三种模型：线性可分支持向量机线性支持向量机非线性向量机（3）线性可分支持向量机求解相应的凸二次规划问题学习得到的分离超平面Txb为以及相应的分类决策函数f(x)signTxb)称为线性可分支持向量机。1，也即是定义离超平面最近的点的距离为1。对目标函数进行改写后，得到如下的优化问题：min12式（1）,,b2s.t.y(Txb)imi iTx1x2y2),...(xmym)}，其xRnyi2n（1）的i i约束最优化问题得到最优解，*、b*，从而得到最大间隔分离超平面和分类决策函数。输出：最大间隔划分超平面和分类决策函数。（4）线性SVM的学习T{(xyxy),...(xyxRn。若1 1 2 2 m m i（outlier），课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第十六讲授课教师唐旭授课章节第八章支撑向量机SMO基本要求了解非线性支持向量机的学习、核函数的定义、核函数有效性判定、Mercer定理及SMO算法原理重点、难点（1）非线性支持向量机的学习核技巧基本是通过个非变换将入空（式空间或者散集映射到个特（尔伯空使在输入空间 n中的面模型应于空间H中的超平型。从而通在特间H中求解先行向量机可以行分类（2）核函数的定义设是输入空间（欧式空间Rn的子集或离散集合），H是特征空间（希尔伯特空间），如果存在一个到H的映射：(x):H使得对所有的x,z，函数K(x,z)满足条件：K(x,z)(x)(z)那么K(x,z)称为核函数，(x)为映射函数。核技巧并不显式地定义映射函数，它通过在学习和预测中定义核函数K(x,z)。特征空间H的维度往往很高，甚至是无穷维的.并且对于给定的核函数，特征空间H与映射函数的取法不唯一SMOSVMSVM的对偶SMOSVMSMOSVMSMOKKTKKTSVM①非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射;SVMSVMSVMSVM课外学习要求第四次大作业SVM算法练习要求：sonar和Iris数据上分别验证SVM课程名称模式识别年级大三授课方式讲课+学生展示+上机授课学时2授课内容第十七讲授课教师唐旭授课章节第九章组合分类器基本要求了解现有的分类方法及其特点，如何评估分类法的准确性，bagging与boosting的概念以及二者之间的区别与联系重点、难点（1）分类方法①基于经典统计理论的分类法理论）②参数法直接求取分类判别函数（分类面）如SVM、BOOSTING等③从训练集中直接得出分类结果非参数，如近邻法等（2）分类法的准确性①评估分类法的准确性Holdout划分为两个独立的数据集，训练集，测试集变形：随机子选择K-倍交叉验证（k-foldcrossvalidation）Kk-1k②提高分类法的准确率“arcing”(adaptivereweightingandcombining):重新使用或选择数据，以期达到改善分类器性能的目的。Bagging、boosting（3）分类器组合评价①泛化误差E(s)sE(s)估计泛化误差实验方法有，持续法、交叉验证估计、自举