模式识别与机器学习期末总结

11,1,2,...,()20otherwisejujdu1()NiNiNkhxx111ˆ()()NiNiNNpNVhxxx/KN19.59.59.57.5C,E()(),1cTSPwiiiiiiixμxμx1.1.样本(sample,object)：一类事物的一个具体体现，对具体的个别事物进行观测所得到的某种形式的信号。模式(pattern)：表示一类事物，如印刷体A与手写体A属同一模式。B与A则属于不同模式。样本是具体的事物，而模式是对同一类事物概念性的概括。模式类与模式联合使用时，模式表示具体的事物，而模式类则是对这一类事物的概念性描述。模式识别是从样本到类别的映射。样本模式识别类别。1.2.数据获取.测量采样-预处理.去噪复原-特征提取与选择.寻找有利于分类的本质特征-分类器设计-分类决策.做出关于样本类别的判断。1.3.先验概率:根据大量统计确定某类事物出现的比例,类条件概率密度函数:同一类事物的各个属性都有一定的变化范围，在其变化范围内的分布概率用一种函数形式表示,后验概率:一个具体事物属于某种类别的概率。2.1.最小错误率准则即最大后验准则，，计算两类后验。最小风险准则，，通过保证每个观测之下的条件风险最小，使得它的期望风险最小。2.2.多元正态分布的pdf、均值、协方差矩阵如下。等概率密度轨迹为超椭球面，主轴方向由协方差矩阵的特征向量决定，轴长度由其特征值决定。2.3.最小距离分类器，线性分类器2.4.医生判断病人是否有病：先验，似然，后验。Bayes决策的三个前提：类别数确定,各类的先验概率P(ωi)已知,各类的条件概率密度函数p(x|ωi)已知.问题的转换:基于样本估计概率密度,基于样本直接确定判别函数.3.1.一元正态分布的最大似然估计：假设样本x服从正态分布N(μ,σ2)；已获得一组样本x1,x2,…,xN。解：似然函数：l(θ)=p(K|θ)=p(x1,x2,…,xN|θ)=∏p(xk|θ)Nk=1，其对数似然函数：H(θ)=∑ln⁡p(xk|θ)Nk=1.最大似然估计ˆargmax()argmaxln(|)k1Nlpxkθθθθ。样本服从正态分布N(μ,σ2)，则p(xk;μ,σ2)=1/√2πσ2exp⁡*−(xk−μ)2/2σ2+,⁡H(μ,σ2)=∑lnp(xk;μ,σ2)=−n2ln(2π)−Nk=1n2lnσ2−12σ2∑(xi−μ)2ni=1。对μ，σ2的最大似然估计：1ln[]021nHxnii;2ln()0222222()1nnnHxii则ˆ(1/)1nnxii，22ˆ(1/)()1nnxii，对μ是无偏估计，对σ2是有偏估计。3.2.类条件概率密度函数的估计：两大类方法,参数估计：概率密度函数的形式已知，而表征函数的参数未知，需要通过训练数据来估计,(最大似然估计,Bayes估计).非参数估计：概率密度函数的形式未知，也不作假设，利用训练数据直接对概率密度进行估计(Parzen窗法和kn-近邻法,神经网络方法).3.3.估计量的评价标准：无偏性:E()=θ有效性:D()小，估计更有效;一致性：样本数趋于无穷时，依概率趋于θ.3.4.贝叶斯决策问题:样本x,决策ai,真实状态wj,状态空间A是离散空间,先验概率P(wj).贝叶斯参数估计问题：样本集K,估计量^s,真实参数s,参数空间S是连续空间,参数的先验分布p(s).3.5.Parzen窗:样本集KN=,x1,x2,…,xN-,区域RN是一个d维超立方体，棱长hN，体积VN=hNd,定义窗核函数.落入超立方体内样本数Kn，某点概率密度p(x)的估计。核函数需满足归一化条件，常用的核函数：均匀核、正态核。Hn控制窗宽，根据样本的数量选择。太大，平均化，分辨力低，太小，统计变动大。kN-近邻估计：把窗扩大到刚好覆盖kN个点。落在窗内的样本点的数目固定，窗宽是变化的。kN根据样本总数N选择。3.6.未设计好的分类器的错误率估计：需要把样本集分为训练集和测试集。C-法：利用N个样本设计，也利用这N个样本测试，得到乐观估计。U-法：把样本集分为训练集和测试集，得到保守估计。U-法可以划分成两类，样本划分法：样本数需要比较多，测试样本数越多越有效。留一法：样本较少时，N-1个样本设计，另一样本测试，遍历N个样本。假设错分样本数为K，则错误率估计为。4.1.设在三维空间中一个类别分类问题拟采用二次曲面。如欲采用广义线性方程求解，试问其广义样本向量与广义权向量的表达式，其维数是多少？二次曲面为：.广义权向量为广义样本向量为维数为10，广义线性判别函数为4.2.Fisher准则的基本原理：找到一个最合适的投影轴，使两类样本在该轴上投影之间的距离尽可能远，而每一类样本的投影尽可能紧凑，从而使分类效果为最佳。用投影后数据的统计性质(均值和离散度的函数)作为判别优劣的标准。各类样本的均值mi,i=1,2，类内离散度矩阵:总类内离散度矩阵,类间离散度矩阵4.3.Fisher准则函数的定义Fisher最佳投影方向的求解。类间分布尽可能开，类内尽可能密集。使用拉格朗日乘子法,解决,w0的确定可以有几种方法4.4.感知准则函数方法的思路是：先随意找一个初始向量a1，然后用训练样本集中的每个样本来计算。若发现一个y出现aTy0，则只要ak+1=ak+rky，rk为正(步长系数)，则必有ak+1Ty=akTy+rkyTy，就有趋势做到使ak+1Ty0。当然，修改后的ak+1还可以使某些y出现ak+1Ty0的情况，理论证明，只要训练样本集线性可分，无论a1的初值是什么，经过有限次叠代，都可收敛。感知器梯度下降算法：1.初值:任意给定一向量初始值a(1)。2.迭代:第k+1次迭代时的权向量a(k+1)等于第k次的权向量a(k)加上被错分类的所有样本之和与rk的乘积3.终止:对所有样本正确分类4.5.平方误差准则函数最小二乘近似解当N→∞，b=uN=*1,1,…,1+T时，则MSE以最小均方误差逼近Bayes判别函数(上)4.6.决策树:一种多类分类器，采用分级形式，综合用多个决策规则，逐步把复杂的多类别分类问题转化为若干个简单的分类问题来解决。分段线性判别函数的决策面是若干超平面。4.7.基于样本的直接确定判别函数方法主要包含两个步骤：确定使用的判别函数类型或决策面方程类型，如线性分类器，分段线性分类器等。在选定函数类型的条件下，确定相应的参数，从而完成整个分类器设计。线性判别函数计算简单，在一定条件下能实现最优分类，经常是一种“有限合理”的选择。分段线性分类器可以实现更复杂的分类面。5.1.按近邻法，对任意两个由不同类别的训练样本构成的样本对，如果它们有可能成为测试样本的近邻，则它们构成一组最小距离分类器，它们之间的中垂面就是分界面，因此由三个A类与四个B类训练样本可能构成的分界面最大数量为3×4＝12。实际分界面如下图所示，由9条线段构成。5.2.最小距离分类器，将各类训练样本划分成若干子类，并在每个子类中确定代表点，测试样本的类别以其与这些代表点距离最近做决策。缺点：所选择地代表点不一定能很好地代表各类，将使错误率增加。最近邻分类器是最小距离分类器中的一种极端情况，以全部训练样本为代表点，计算测试样本与所有样本的距离，并以最近邻者的类别作为决策，是非参数法。判别函数：缺点：计算量大，存储量大。近邻法的错误率高于贝叶斯错误率5.3.两类改进的方法：一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。另一种则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。5.4.剪辑近邻法：其基本思想是，利用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。剪辑的过程是：将样本集KN分成两个互相独立的子集：test集KT和reference集KR。首先对KT中每一个Xi在KR中找到其最近邻的样本Yi(Xi)。如果Yi与Xi不属于同一类别，则将Xi从KT中删除，最后得到一个剪辑的样本集KTE（剪辑样本集），以取代原样本集，对待识别样本进行分类。5.5.压缩近邻法：利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率。压缩近邻算法：定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。其算法是：1.初始化。Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一样本放入Store中作为新样本集的第一个样本。2.样本集生成。在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入Store中，若分类正确，则将该样本放回Grabbag中。3.结束过程。若Grabbag中所有样本在执行第二步时没有发生转入Store的现象，或Grabbag已成空集，则算法终止，否则转入第二步。6.1.设一样本集的协方差矩阵是：，求最优2x1特征提取器U。解答：计算特征值及特征向量[V,D]=eig(C);特征值D=[24.736,2.263]T,特征向量:。由于λ1λ2，故最优2x1特征提取器，此时的K-L变换式为：。6.2.用K-L变换降维至d维K-L变换的产生矩阵可以有多种选择：x的相关函数矩阵R=E[xxT]x的协方差矩阵C=E[(x-μ)(x-μ)T+样本总类内离散度矩阵：求出产生矩阵的特征值、特征函数，选取最大的d个特征值对应的特征向量组成变换矩阵U。7.1.有监督学习（supervisedlearning)：用已知类别的样本训练分类器，以求对训练集数据达到某种最优，并能推广到对新数据的分类，标记了两类样本的标号，需要人手工干预训练过程，。非监督学习（unsupervisedlearning)：样本数据类别未知，需要根据样本间的相似性对样本集进行分类(聚类，clustering)，依照数据的自然分布，把它们划分成两类，。监督学习方法的目的是识别事物，给待识别数据加上标号(label)。因此训练样本集必须由带标号的样本组成。而非监督学习方法只有要分析的数据集本身，没有标号。如果发现数据集呈现某种聚集性，则可按自然的聚集性分类，但不以与某种预先的分类标号对上号为目的。监督学习方法必须要有训练集与测试样本。在训练集中找规律，而对测试样本使用这种规律；而非监督学习只有一组数据，在该组数据集内寻找规律.主要的非监督学习方法:基于概率密度函数估计的直接方法：设法找到各类别在特征空间的分布参数再进行分类。直方图方法。基于样本间相似性度量的间接聚类方法：设法定出不同类别的核心或初始类核，然后依据样本与这些核心之间的相似性度量将样本聚集成不同类别。7.2.设x1=(45)T,x2=(14)T,x3=(01)T,x4=(50)T。现有下列三种划分：(1)f1={x1,x2},f2={x3,x4}.(2)f1={x1,x4},f2={x2,x3};(3)f1={x1,x2,x3},f2={x4}.证明对于平方误差和准则，第三种划分最好，而若用|Sw|准则，前两种划分好。解:f1:m1=1/2(x1+x2)=1/2(59)T,m2=1/2(x3+x4)=1/2(51)T,J1=||x1-m1||2+…+||x4-m2||2=18;f2:……..f3:m1=1/3(x1+x2+x3)=1/3(510)T,m2=(50)T,J3=52/3;J3最小,第三种划分好。|Sw|准则：()(),1,23TiiiiiSxmxmx，12wSSS7.3.使用流程图描述C-Mean