模式识别复习题

1、模式识别系统的基本构成单元，并对各单元简要解释数据获取特征提取和选择预处理分类决策分类器设计•数据获取：用计算机可以运算的符号来表示所研究的对象–二维图像：文字、指纹、地图、照片等–一维波形：脑电图、心电图、季节震动波形等–物理参量和逻辑值：体温、化验数据、参量正常与否的描述•预处理单元：去噪声，提取有用信息，并对输入测量仪器或其它因素所造成的退化现象进行复原•特征提取和选择：对原始数据进行变换，得到最能反映分类本质的特征–测量空间：原始数据组成的空间–特征空间：分类识别赖以进行的空间–模式表示：维数较高的测量空间-维数较低的特征空间•分类决策：在特征空间中用模式识别方法把被识别对象归为某一类别–基本做法：在样本训练集基础上确定某个判决规则，使得按这种规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小2、写出K-均值聚类算法的基本步骤,例子见布置的作业题.算法：第一步：选K个初始聚类中心，z1(1)，z2(1)，…，zK(1)，其中括号内的序号为寻找聚类中心的迭代运算的次序号。聚类中心的向量值可任意设定，例如可选开始的K个模式样本的向量值作为初始聚类中心。第二步：逐个将需分类的模式样本{x}按最小距离准则分配给K个聚类中心中的某一个zj(1)。假设i=j时，}K,2,1i,)k(zxmin{)k(Dij，则)k(Sxj，其中k为迭代运算的次序号，第一次迭代k=1，Sj表示第j个聚类，其聚类中心为zj。第三步：计算各个聚类中心的新的向量值，zj(k+1)，j=1,2,…,K求各聚类域中所包含样本的均值向量：其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心，()1(1),1,2,,jjxSkjzkxjKN可使如下聚类准则函数最小：在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K-均值算法。第四步：若)k(z)1k(zjj，j=1,2,…,K，则返回第二步，将模式样本逐个重新分类，重复迭代运算；若)k(z)1k(zjj，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-均值算法进行聚类分析解：选2k，11210(1),(1)zxzx，第一步：选取1121007(1),(1)06zxzx第二步：根据聚类中心进行聚类，得到1123456782910111220(1){,,,,,,,}(1){,,,,}SxxxxxxxxSxxxxx第三步：计算新的聚类中心121128(1)1291020(1)21.250011(2)()1.125087.666711(2)()7.333312xSxSzxxxxNzxxxxN第四步：因(2)(1),1,2jjzzj，故回到第二步第二步：根据新的聚类中心重新进行聚类，得到1123456782910111220(2){,,,,,,,}(2){,,,,}SxxxxxxxxSxxxxx第三步：计算新的聚类中心121128(2)1291020(2)21.250011(3)()1.125087.666711(3)()7.333312xSxSzxxxxNzxxxxN第四步：(3)(2),1,2jjzzj，所以算法收敛，得聚类中心为121.25007.6667,1.12507.3333zz迭代结束。3、最、剪辑、压缩近邻法的基本思想。2()(1),1,2,,jjjxSkJxzkjK最近邻法的基本思想：以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。剪辑近邻法基本思想是，利用现有样本集对其自身进行剪辑，将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。压缩近邻法：利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率。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步：将每一样本看成单独一类，得(0)(0)(0)112233(0)(0)(0)445566{},{},{}{},{},{}GxGxGxGxGxGx计算各类之间的欧式距离，可得距离矩阵(0)D(0)1G(0)2G(0)3G(0)4G(0)5G(0)6G(0)1G0(0)2G30(0)3G1560(0)4G65130(0)5G118670(0)6G211481140第2步：矩阵(0)D中最大元素为21，它是(0)1G和(0)6G之间的距离，将他们合并为一个新类为(1)(0)(0)(1)(0)(1)(0)(1)(0)(1)(0)11622334455{,},{},{},{},{}GGGGGGGGGGG计算聚类后的距离矩阵(1)D(1)1G(1)2G(1)3G(1)4G(1)5G(1)1G0(1)2G140(1)3G1560(1)4G115130(1)5G118670第3步：由于(1)D中距离最大者为15，它是(1)1G与(1)3G之间的距离，于是合并(1)1G和(1)3G，得新的分类为(2)(1)(1)(2)(1)(2)(1)(2)(1)113223445{,},{},{},{}GGGGGGGGG同样，按最大距离准则计算距离矩阵(2)D，得(2)1G(2)2G(2)3G(2)4G(2)1G0(2)2G140(2)3G1350(2)4G11870第4步：：由于(2)D中距离最大者为14，它是(2)1G与(2)2G之间的距离，于是合并得新的分类为(3)(2)(2)(3)(2)(3)(2)1122334{,},{},{}GGGGGGG满足聚类要求，如聚为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步：将每一样本看成单独一类，得(0)(0)(0)112233(0)(0)4455{},{},{}{},{}GxGxGxGxGx计算各类之间的欧式距离，可得距离矩阵(0)D(0)1G(0)2G(0)3G(0)4G(0)5G(0)1G0(0)2G230(0)3G25240(0)4G241570(0)5G26253120第2步：矩阵(0)D中最小元素为3，它是(0)3G和(0)5G之间的距离，将他们合并为一类，得新的分类为(1)(0)(1)(0)(1)(0)(0)(1)(0)112233544{},{},{,},{}GGGGGGGGG计算聚类后的距离矩阵(1)D(1)1G(1)2G(1)3G(1)4G(1)1G0(1)2G230(1)3G25240(1)4G241570第3步：由于(1)D中距离最小者为7，它是(1)3G与(1)4G之间的距离，于是合并(1)3G和(1)4G，得新的分类为(2)(1)(2)(2)(2)(1)(1)1122334{},{},{,}GGGGGGG同样，按最小距离准则计算距离矩阵(2)D，得(2)1G(2)2G(2)3G(2)1G0(2)2G230(2)3G24150第4步：同理得(3)(2)(3)(2)(2)11223{},{,}GGGGG满足聚类要求，如聚为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)=30所以不修正w1Tx2=(1,1,1,1)T(0,1,1,1)=30所以不修正w1Tx3=(1,1,1,1)T(1,1,0,1)=30所以修正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)判别函数233gxxx决策面方程：233=0gxxx即23-3=0xx8、已知：ω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)=0.005，当然P(ω2)=1-0.005=0.995.设有一种诊断癌症的试验，其结果为“阳性”和“阴性”两种反应。假设根据临床记录发现这种方法有以下统计结果:患有癌症的人试验反应为阳性的概率=0.95，即p(x=阳|ω1)=0.95患有癌症的人试验反应为阴性的概率=0.05，即p(x=阴|ω1)=0.05正常人试验反应为阳性的概率=0.01，即p(x=阳|ω2)=0.