模式识别复习资料

.,复习,1模式和模式识别的概念1）模式：对某些感兴趣的客体的定量的或结构的描述。模式类是具有某些共同特性的模式的集合。2）模式识别：研究一种自动技术，依靠这种技术，计算机将自动地（或人尽量少地干涉）把待别识模式分配到各自的模式类中去。,.,复习,2模式识别系统组成,.,复习,1）监督分类：需要依靠已知类别的训练样本集，按照他们特征向量的分布来确定判别函数，然后利用判别函数对未知模式进行分类。需要足够的先验知识。判别。需要有足够的先验知识。2）非监督分类：用于没有先验知识的情况，通常采用聚类分析的方法。,3监督分类和无监督分类,.,复习,4模式识别整体知识结构,.,5最大最小距离算法（小中取大距离算法）,算法描述,选任意一模式样本做为第一聚类中心Z1。,选择离Z1距离最远的样本作为第二聚类中心Z2。,逐个计算各模式样本与已确定的所有聚类中心之间的距离，并选出其中的最小距离。例当聚类中心数k=2时，计算,复习,.,将样本按最近距离划分到相应聚类中心对应的类别中。,重复步骤，直到没有新的聚类中心出现为止。,在所有最小距离中选出最大距离，如该最大值达到的一定分数比值(阈值T)以上，则相应的样本点取为新的聚类中心，返回；否则，寻找聚类中心的工作结束。,例k=2时,复习,.,例2.1对图示模式样本用最大最小距离算法进行聚类分析。,选Z1=X1,距Z1最远，选为Z2。计算T。,对应最小距离中的最大值，且T，选作Z3。,结果：Z1=X1；Z2=X6；Z3=X7。,用全体模式对三个聚类中心计算最小距离中的最大值，无T情况，停止寻找中心。,聚类,.,算法描述,1）N个初始模式样本自成一类，即建立N类：计算各类之间（即各样本间）的距离，得一NN维距离矩阵D(0)。“0”表示初始状态。,(G_Group),6层次聚类法,2）假设已求得距离矩阵D(n)（n为逐次聚类合并的次数），找出D(n)中的最小元素，将其对应的两类合并为一类。由此建立新的分类：,3）计算合并后新类别之间的距离，得D(n+1)。,4）跳至第2步，重复计算及合并。,复习,.,结束条件：1）取距离阈值T，当D(n)的最小分量超过给定值T时，算法停止。所得即为聚类结果。2）或不设阈值T，一直将全部样本聚成一类为止，输出聚类的分级树。,复习,.,例：给出6个五维模式样本如下，按最短距离准则进行系统聚类分类。,计算各类间欧氏距离：,解：（1）将每一样本看作单独一类，得：,，；,；,.,（2）将最小距离对应的类和合并为1类，得新的分类。,计算聚类后的距离矩阵D(1)：由D(0)递推出D(1)。,得距离矩阵D(0)：,.,（3）将D(1)中最小值对应的类合为一类，得D(2)。,.,（4）将D(2)中最小值对应的类合为一类，得D(3)。,若给定的阈值为，D(3)中的最小元素，聚类结束。,若无阈值，继续分下去，最终全部样本归为一类。可给出聚类过程的树状表示图。,.,层次聚类法的树状表示,类间距离阈值增大，分类变粗。,.,7K-均值算法,算法描述,（1）任选K个初始聚类中心：Z1(1)，Z2(1)，ZK(1),（2）按最小距离原则将其余样品分配到K个聚类中心中的某一个。,Nj：第j类的样本数。,（3）计算各个聚类中心的新向量值：,（4）如果，则回到（2），将模式样本逐个重新分类，重复迭代计算。,，算法收敛，计算完毕。,如果,复习,.,例2.3：已知20个模式样本如下，试用K-均值算法分类。,解：取K=2，并选：,计算距离，聚类：,：,.,：,：,，可得到：,计算新的聚类中：,.,从新的聚类中心得：,：,：,有：,计算聚类中心：,.,返回第步，以Z1(3)，Z2(3)为中心进行聚类。,以新的聚类中心分类，求得的分类结果与前一次迭代结果相同：,计算新聚类中心向量值，聚类中心与前一次结果相同，即：,，故算法收敛，得聚类中心为,结果图示：,.,图2.10K-均值算法聚类结果,.,上述K-均值算法，其类型数目假定已知为K个。当K未知时，可以令K逐渐增加，此时Jj会单调减少。最初减小速度快，但当K增加到一定数值时，减小速度会减慢，直到K=总样本数N时，Jj=0。JjK关系曲线如下图：,8聚类准则函数Jj与K的关系曲线,曲线的拐点A对应着接近最优的K值（J值减小量、计算量以及分类效果的权衡）。并非所有的情况都容易找到关系曲线的拐点。迭代自组织的数据分析算法可以确定模式类的个数K。,.,用线性判别函数将属于i类的模式与其余不属于i类的模式分开。,识别分类时：,9线性判别函数,复习,.,对某一模式区，di(X)0的条件超过一个，或全部的di(X)0，分类失效。相当于不确定区(indefiniteregion，IR)。,此法将M个多类问题分成M个两类问题，识别每一类均需M个判别函数。识别出所有的M类仍是这M个函数。,.,例3.1设有一个三类问题，其判别式为：,现有一模式，X=7,5T，试判定应属于哪类？并画出三类模式的分布区域。,解：将X=7,5T代入上三式，有：,三个判别界面分别为：,图示如下：,.,步骤：,a)画出界面直线。,b)判别界面正负侧：找特殊点带入。,c)找交集。,.,感知器算法步骤：,（1）选择N个分属于1和2类的模式样本构成训练样本集X1,XN构成增广向量形式，并进行规范化处理。任取权向量初始值W(1)，开始迭代。迭代次数k=1。,（2）用全部训练样本进行一轮迭代，计算WT(k)Xi的值，并修正权向量。,分两种情况，更新权向量的值：,9感知器算法,复习,.,c：正的校正增量。,分类器对第i个模式做了错误分类，,权向量校正为：,统一写为：,（3）分析分类结果：只要有一个错误分类，回到（2），直至对所有样本正确分类。,分类正确时，对权向量“赏”这里用“不罚”，即权向量不变；分类错误时，对权向量“罚”对其修改，向正确的方向转换。,感知器算法是一种赏罚过程：,.,例3.8已知两类训练样本,解：所有样本写成增广向量形式；进行规范化处理，属于2的样本乘以(1)。,用感知器算法求出将模式分为两类的权向量解和判别函数。,.,任取W(1)=0，取c=1，迭代过程为：,第一轮：,有两个WT(k)Xi0的情况（错判），进行第二轮迭代。,.,第二轮：,第三轮：,第四轮：,.,该轮迭代的分类结果全部正确，故解向量,相应的判别函数为：,当c、W(1)取其他值时，结果可能不一样，所以感知器算法的解不是单值的。,判别界面d(X)=0如图示。,.,10最小错误率贝叶斯决策,对两类问题,可改写为：,统计学中称l12(X)为似然比，为似然比阈值。,.,例4.1假定在细胞识别中，病变细胞的先验概率和正常细胞的先验概率分别为。现有一待识别细胞，其观察值为X，从类条件概率密度发布曲线上查得：,试对细胞X进行分类。,解：方法1通过后验概率计算。,.,方法2：利用先验概率和类概率密度计算。,，是正常细胞。,.,11最小风险贝叶斯决策,.,2）两类情况：对样本X,当X被判为1类时：,当X被判为2类时：,（4-15）,（4-16）,由（4-15）式：,决策规则：,.,，为阈值。,计算。,计算。,定义损失函数Lij。,判别步骤：,类概率密度函数p(X|i)也称i的似然函数,.,解：计算和得：,例4.2在细胞识别中，病变细胞和正常细胞的先验概率分别为,现有一待识别细胞，观察值为X，从类概率密度分布曲线上查得,损失函数分别为L11=0，L21=10，L22=0，L12=1。按最小风险贝叶斯决策分类。,为病变细胞。,.,经过选择或变换，组成识别特征，尽可能保留分类信息，在保证一定分类精度的前提下，减少特征维数，使分类器的工作即快又准确。,12特征选择和提取的目的,13特征选择和特征提取的异同,（1）特征选择：从L个度量值集合中按一定准则选出供分类用的子集，作为降维（m维，mL）的分类特征。,（2）特征提取：使一组度量值通过某种变换产生新的m个特征，作为降维的分类特征，其中。,复习,.,14特征提取的方法,其中，,第二步：计算C的特征值，对特征值从小到大进行排队，选择前m个。,.,第四步：利用A对样本集X进行变换。,则m维（mn）模式向量X*就是作为分类用的模式向量。,解：1)求样本均值向量和协方差矩阵。,.,由,