模式识别复习题

数据获取特征提取和选择数据获取特征提取和选择预处理分类决策分类器设计数据获取：用计算机可以运算的符号来表示所研究的对象二维图像：文字、指纹、地图、照片等一维波形：脑电图、心电图、季节震动波形等物理参量和逻辑值：体温、化验数据、参量正常与否的描述预处理单元：去噪声，提取有用信息，并对输入测量仪器或其它因素所造成的退化现象进行复原特征提取和选择：对原始数据进行变换，得到最能反映分类本质的特征测量空间：原始数据组成的空间特征空间：分类识别赖以进行的空间模式表示：维数较高的测量空间->维数较低的特征空间分类决策：在特征空间中用模式识别方法把被识别对象归为某一类别基本做法：在样本训练集基础上确定某个判决规则，使得按这种规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小写出K-均值聚类算法的基本步骤,例子见布置的作业题.算法：第一步：选K个初始聚类中心，z1(1)，z2(1)，…，zK(1)，其中括号内的序号为寻找聚类中心的迭代运算的次序号。聚类中心的向量值可任意设定，例如可选开始的K个模式样本的向量值作为初始聚类中心。第二步：逐个将需分类的模式样本{x}按最小距离准则分配给K个聚类中心中的某一个zj(1)。假设i=j时，，则，其中k为迭代运算的次序号，第一次迭代k=1，Sj表示第j个聚类，其聚类中心为zj。第三步：计算各个聚类中心的新的向量值，zj(k+1)，j=1,2,…,K求各聚类域中所包含样本的均值向量：其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心，可使如下聚类准则函数最小：在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K-均值算法。第四步：若，j=1,2,…,K，则返回第二步，将模式样本逐个重新分类，重复迭代运算；若，j=1,2,…,K，则算法收敛，计算结束。例子：已知{x1(0,0),x2(1,0),x3(0,1),x4(1,1),x5(2,1),x6(1,2),x7(2,2),x8(3,2),x9(6,6),x10(7,6),x11(8,6),x12(6,7),x13(7,7),x14(8,7),x15(9,7),x16(7,8),x17(8,8),x18(9,8),x19(8,9),x20(9,9)}，用K-均值算法进行聚类分析解：选，，第一步：选取第二步：根据聚类中心进行聚类，得到第三步：计算新的聚类中心第四步：因，故回到第二步第二步：根据新的聚类中心重新进行聚类，得到第三步：计算新的聚类中心第四步：，所以算法收敛，得聚类中心为迭代结束。3、最、剪辑、压缩近邻法的基本思想。 最近邻法的基本思想：以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。剪辑近邻法基本思想是，利用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。压缩近邻法：利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率。4、设有6个5维模式样本如下，按最小/大距离准则进行聚类分析（直到分成三个类别为止，距离度量采用欧氏距离）x1:0,3,1,2,0x2:1,3,0,1,0x3:3,3,0,0,1x4:1,1,0,2,0x5:3,2,1,2,1x6:4,1,1,1,0按最大距离准则进行聚类分析：第1步：将每一样本看成单独一类，得计算各类之间的欧式距离，可得距离矩阵000000第2步：矩阵中最大元素为，它是和之间的距离，将他们合并为一个新类为计算聚类后的距离矩阵00000第3步：由于中距离最大者为，它是与之间的距离，于是合并和，得新的分类为同样，按最大距离准则计算距离矩阵，得0000第4步：：由于中距离最大者为，它是与之间的距离，于是合并得新的分类为满足聚类要求，如聚为3类，聚类完毕。5、设有5个6维模式样本如下，按最小/大距离准则进行聚类分析（距离度量采用欧氏距离）x1:0,1,3,1,3,4x2:3,3,3,1,2,1x3:1,0,0,0,1,1x4:2,1,0,2,2,1x5:0,0,1,0,1,0用最小聚类准则进行系统聚类分析：第1步：将每一样本看成单独一类，得计算各类之间的欧式距离，可得距离矩阵00000第2步：矩阵中最小元素为，它是和之间的距离，将他们合并为一类，得新的分类为计算聚类后的距离矩阵0000第3步：由于中距离最小者为，它是与之间的距离，于是合并和，得新的分类为同样，按最小距离准则计算距离矩阵，得000第4步：同理得满足聚类要求，如聚为2类，聚类完毕。6、一个三类问题，其判别函数如下：d1(x)=-x1,d2(x)=x1+x2-1,d3(x)=x1-x2-1设这些函数是在多类情况1条件下确定的。1)绘出其判别界面和每一个模式类别的区域。2)对如下三个样本所属模式作出判决：A=(45)T,B=(-25)T,C=(2-5)T例子：一个三类问题，其判别函数如下： d1(x)=-x1,d2(x)=x1+x2-1,d3(x)=x1-x2-11、设这些函数是在多类情况1条件下确定的，绘出其判别界面和每一个模式类别的区域。2、设为多类情况2，并使：d12(x)=d1(x),d13(x)=d2(x),d23(x)=d3(x)。绘出其判别界面和多类情况2的区域。3、设d1(x),d2(x)和d3(x)是在多类情况3的条件下确定的，绘出其判别界面和每类的区域解：（1）其判别界面和每一个模式类别的区域如图中所示：A=(45)T属于ω1,B=(-25)T属于不确定区域,C=(2-5)T属于ω3.（2）其判别界面和每一个模式类别的区域如图中所示：（3）其判别界面和每一个模式类别的区域如图中所示：7、已知：ω1:{x1,x2}={(101)T,(011)T}，ω2:{x3,x4}={(110)T,(010)T}。给定初始增广权向量w1=(1111)T，C=1。要求：1)用感知器算法求模式分类的解向量w。2)写出判别函数和决策面方程。解：先求四个样本的增值模式x1=(1,0,1,1)Tx2=(0,1,1,1)Tx3=(1,1,0,1)Tx4=(0,1,0,1)T假设初始权向量w1=(1,1,1,1)TC=1第一次迭代：w1Tx1=(1,1,1,1)T(1,0,1,1)=3>0所以不修正w1Tx2=(1,1,1,1)T(0,1,1,1)=3>0所以不修正w1Tx3=(1,1,1,1)T(1,1,0,1)=3>0所以修正w1w2=w1-x3=(0,0,1,0)Tw2Tx4=(0,0,1,0)T(0,1,0,1)=0所以修正w2w3=w2-x4=(0,-1,1,-1)T第一次迭代后,权向量w3=(0,-1,1,-1)T,再进行第2,3,…次迭代如下表：直到在一个迭代过程中权向量相同，训练结束。w6=w=(0,-1,3,0)判别函数决策面方程：即8、已知：ω1:X1=(0,2)T,X3=(2,0)T,X5=(-1,-1)Tω2:X2=(1,1)T,X4=(0,-2)T,X6=(-2,0)T给定初始增广权向量w1=(111)T，C=1。要求：用感知器算法求模式分类的解向量w。解：此为线性不可分问题，利用感知器法求权向量权向量产生循环(1,1,1)T,(0,0,0)T,(2,0,1)T,(2,2,0)T,(1,1,1)T因此算法不收敛，我们可以取循环中任一权值，例如取W=(2,2,0)T则判别函数为：g(x)=2x1+2x2判别面方程为：g(x)=2x1+2x2＝0所以：x1+x2＝0由图看出判别面H把二类分开，但其中x2错分到ω1类，而x1错分到ω2类，但大部分分类还是正确的。9、对一大批人进行癌症普查，患癌者以ω1类代表，正常人以ω2类代表。已知P(ω1，当然P(ω2)=1-0.005=0.995.设有一种诊断癌症的试验，其结果为“阳性”和“阴性”两种反应。假设根据临床记录发现这种方法有以下统计结果:患有癌症的人试验反应为阳性的概率，即p(x=阳|ω1患有癌症的人试验反应为阴性的概率，即p(x=阴|ω1正常人试验反应为阳性的概率，即p(x=阳|ω2正常人试验反应为阴性的概率，即p(x=阴|ω2问：若被化验的人具有阳性反应，他患癌症的概率为多少？解：因为，P(w2|x=阳)=1-P(w1P(w1|x=阳)<P(w2|x=阳)故判决：正常。10、已知P(ω1，P(ω2)=0.1，p(x|ω1)=0.2，p(x|ω2)=0.4。且有如下决策表：损失状态决策ω1ω2α106α210请按最小风险贝叶斯决策进行分类。解：已知条件为P(ω1，P(ω2)=0.1，p(x|ω1)=0.2，p(x|ω2)=0.4。利用贝叶斯公式分别计算出ω1及ω2的后验概率再计算条件风险:由于即决策为ω2的条件风险小于决策为ω1的条件风险，因此我们采取决策行动，即判断待识别的细胞x为ω2类——异常细胞。11、设有如下三类模式样本集ω1，ω2和ω3，其先验概率相等，求Sw和Sbω1：{(10)T,(20)T,(11)T}ω2：{(-10)T,(01)T,(-11)T}ω3：{(-1-1)T,(0-1)T,(0-2)T}解：由于本题中有三类模式，因此我们利用下面的公式：=,即:为第i类样本样本均值12试用感知器算法实现逻辑“与”、“或”功能。（初始加权值、阈值和训练速率系数自己设定）一、用感知器算法实现逻辑“与”功能真值表：x1x2T00-1(0)01-1(0)10-1(0)111设，，，，转移函数为符号函数则有，则有，则有则有，重复上述（1）～（4），则有，则有，则有，则有，最后所得加权值为，用感知器算法实现逻辑“或”功能真值表：x1x2T00-1(0)011101111仍设，，，，转移函数为符号函数(1)则有，(2)则有(3)则有，(4)则有，重复上述（1）～（4），(5)则有，则有，则有，则有，最后所得加权值为，13.掌握BP算法.前馈与反馈网络结构与训练过程.BP训练算法实现步骤准备：训练数据组。设网络具有m层，表示第m层中第j个结点的输出，（零层输出）等于xj，即第j个输入。表示从到的连接加权。这里，m代表层号，而不是向量的类号。将各加权随机置为小的随机数。可用均匀分布的随机数，以保证网络不被大的加权值所饱和。从训练数据组中选一数据对(xk,Tk)，将输入向量加到输入层（m=0），使得对所有端点i：，k表示向量类号信号通过网络向前传播，即利用关系式：计算从第一层开始的各层内每个结点i的输出，直到输出层的每个结点的输出计算完为止。计算输出层每个结点的误差值（利用公式(1)）（对Sigmod函数）它是由实际输出和要求目标值之差获得。计算前面各层各结点的误差值（利用公式(2)）这里逐层计算反传误差，直到将每层内每个结点的误差值算出为止。利用加权修正公式和关系修正所有连接权。一般η=0.01~1，称为训练速率系数。返回第2步，为下一个输入向量重复上述步骤，直至网络收敛。（2）前馈网络通过许多具有简单处理能力的神经元的复合作用，使整个网络具有复杂的非线性映射能力。反馈网络通过网络神经元状态的变迁，最终稳定于某一状态，得到联想存储或神经计算的结果。感知器训练算法准备：收集一组训练对，即一组输入向量，其中每个都有一个对应的目标向量。输入：二进制值或连续值（-1~+1）输出：目标向量（二进制值）训练步骤：将所有网络加权随机置为较小的值（均匀分布随机数）加入一个输入量)，计算各结点的输入加权和：将信号通过符号函数，得：计算每个结点的输出误差值：调节各加权值：重复步骤2~5，直到所有误差达到所要求的最小值（如零值）为止。Hopfield网络学习过程假设共有p个模式，即网络面临的学习任务为集合{x1,x2,…,xp}，其中。先考虑Hopfield网络对一个模式学习和回忆的情况。对一个模式的学习，此时p=1，即学习任务集合只有一个模式x1。设网络权矩阵为W，对于初始模式x1，若网络稳定，则应有：x1=sgn(x1W)，x1为网络的不动点上式展开可写成：，其中 (1)式(1)可用于神经网络状态的任何更新方式。由sgn函数的性质，若条件（即式(1)左右两边同号）满足，则式(1)成立，从而有：因，则由He