模式识别复习题

1、1、模式识别系统的基本构成单元，并对各单元简要解释?数据获取：用计算机可以运算的符号来表示所研究的对象-二维图像：文字、指纹、地图、照片等-一维波形：脑电图、心电图、季节震动波形等-物理参量和逻辑值：体温、化验数据、参量正常与否的描述?预处理单元：去噪声，提取有用信息，并对输入测量仪器或其它因素所造 成的退化现象进行复原?特征提取和选择：对原始数据进行变换，得到最能反映分类本质的特征-测量空间：原始数据组成的空间-特征空间：分类识别赖以进行的空间-模式表示：维数较高的测量空间-维数较低的特征空间?分类决策：在特征空间中用模式识别方法把被识别对象归为某一类别-基本做法：在样本训练集基础上确定某个

2、判决规则，使得按这种规则对被识别对象进行分类所造成的错误识别率最小或引起的损失 最小2、写出K-均值聚类算法的基本步骤,例子见布置的作业题.算法：第一步：选K个初始聚类中心，Z1(1), Z2(1)，ZK(1)，其中括号内的序号为 寻找聚类中心的迭代运算的次序号。聚类中心的向量值可任意设 定，例如可选开始的K个模式样本的向量值作为初始聚类中心。第二步：逐个将需分类的模式样本X按最小距离准则分配给 K个聚类中心中 的某一个Z(1)。假设 i=j 时，Dj(k) min x 乙(k) ,i 1,2, K，则 x Sj(k)，其中k为迭代运算的次序号，第一次迭代 k=l，S 表示第j个聚类，其聚类中

3、心为z。第三步：计算各个聚类中心的新的向量值，Z(k+1), j=1,2，K1Zj(k 1) x, j 1,2,L ,KNj x Sj(k)求各聚类域中所包含样本的均值向量：Jj|x Zj（k 1）2, j 1,2,L ,Kx Sj（k）其中Nj为第j个聚类域S中所包含的样本个数。以均值向量作为新的聚类中心，可使如下聚类准则函数最小：在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K均值算法。第四步：若Zj（k 1） Zj（k）, j=i,2,；K,则返回第二步，将模式样本逐个重新 分类，重复迭代运算；若Zj（k 1） Zj（k），j=i,2-；K，贝U算法收敛，计算结束。例子:已知x

4、1（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-均值算法进行聚类分析解：选 k 2，乙（1）“ Z2（1） X10，第一步：选取z,（1） n00 ,Z2(1)第二步：根据聚类中心进行聚类，得到S(1) X1,X2,X3,(4,X5,X6,X7

5、,X8S2(1)x),Xo,X11,X12 ,L X20第三步:计算新的聚类中心111.2500乙X-(X1 X2 LX8)N1 X S(1)81.1250117.6667ZJ2)X(X9X10L X20 )N2 X S2 (1)127.3333第四步:因 Zj(2)Zj(1),j1,2，故回到第二步第二步：根据新的聚类中心重新进行聚类，得到S3)X,X2,X3,X4,X5,X6,X7,X8S2(2)X9,*0,X11,XI2 ,L X20第三步:计算新的聚类中心11 ,1.2500Z1(3)X(X1 X2 LX8)N1 x S(2)81.1250117.6667Z2)X(X9 X10L X2

6、0)N2 x S2(2)127.3333第四步：Zj （3） Zj （2）, j 1,2，所以算法收敛，得聚类中心为迭代结束1.25007.6667N 1.1250 ,Z27.33333、最、剪辑、压缩近邻法的基本思想。最近邻法的基本思想：以全部训练样本作为“代表点”，计算测试样本与这些“代 表点”，即所有样本的距离，并以最近邻者的类别作为决策。剪辑近邻法基本思想是，利用现有样本集对其自身进行剪辑， 将不同类别交界处 的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。 压缩近邻法：利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最 少量样本的条件下，仍能对原有样本的

7、全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率。4、设有6个5维模式样本如下，按最小/大距离准则进行聚类分析(直到分成 三个类别为止，距离度量采用欧氏距离)xi：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步：将每一样本看成单独一类，得G 幼上20)X2,G3(0)X3g40) X4, g50) X5, g60) X6计算各类之间的欧式距离，可得距离矩阵 D(0)G；0)g20)g30)c(0)G4g5

8、0)g60)G；0)0g20)0g30)0g40)0g50)恵0g60)42714V80第2步：矩阵D(0)中最大元素为.21，它是G1(0)和G60)之间的距离，将他们合并为一个新类为G1(1) G1(0),G60),Gr G20),Gr G30),Gr G40),Gr G5(0)计算聚类后的距离矩阵DGiG21)G31)G41)G51)Gi0Gj0Gj0Gf亦Vl30G51)Hi0第3步：由于D(1)中距离最大者为.15，它是Gi与之间的距离，于是合并Gi和G31)，得新的分类为g；2) g1(1),g31),g22) g,g32) g,g42) g同样，按最大距离准则计算距离矩阵 D，得

9、CG1g22)g32)g42)Gi(2)0g22)屁0g32)V50g42)佑0第4步：由于D中距离最大者为 皿，它是Gi与G22)之间的距离，于是合并 得新的分类为GiGi(2),g22),g23) g32),g33) g42)满足聚类要求，如聚为3类，聚类完毕。5、设有5个6维模式样本如下，按最小/大距离准则进行聚类分析(距离度量 采用欧氏距离)xi:0, 1,3, 1, 3, 4X2：3, 3, 3, i,2,iX3：i, 0, 0, 0, i,iX4：2,1,0, 2, 2,1X5：0, 0, 1, 0, 1,0用最小聚类准则进行系统聚类分析：第1步：将每一样本看成单独一类，得G(0)

10、xj,g20)X2, G30) X3g40)X4, g50) 5计算各类之间的欧式距离，可得距离矩阵D(0)G；0)g20)g30)g40)g50)G；0)0g20)V230g30)725屈0g40)屈0g50)726725屁0第2步：矩阵D(0)中最小元素为，它是g30)和g50)之间的距离，将他们合并为 一类，得新的分类为G1GW 澎耐gH G40)计算聚类后的距离矩阵Dc(1)G1CG2CG3GfG107230725V240GJ420第3步：由于D中距离最小者为 5，它是g31)与G41)之间的距离，于是合并G31)和G41)，得新的分类为Gi(2)澎上22) G22),G32)澎创 同

11、样，按最小距离准则计算距离矩阵D，得CG1CG2g32)G1(2)0g22)0g32)VT50第4步：同理得Gig；2), g23) g22),g32)满足聚类要求，如聚为2类，聚类完毕6、一个三类问题，其判别函数如下:di(x)=-xi, d2(x)=xi +X2-1, d3(X)=X1-X2-1d2(x)0 d3(x)0所以不修正W1 T X2=(1,1,1,1)t (0,1,1,1)=30所以不修正W1 T X3=(1,1,1,1)t (1,1,0,1)=30所以修正 W1W2=W1-X3=(0,0,1,0)Tw2 T x4=(0,0,1,0)T (0,1,0,1) =0所以修正 w2w

12、3=w2-x4=(0,-1,1,-1)T第一次迭代后，权向量W3=(0,-1,1,-1)t,再进行第2,3，次迭代如下表:直到在一个迭代过程中权向量相同，训练结束。 w6=w=(0,-1,3,0)判别函数 g xx2 3x3决策面方程: g xx2 3x3=0 即 x2-3x3=08、已知：3 1： Xi =(0,2)t , X3 =(2,0)t ,X5 =(-1,-1)t3 2： X2 =(1,1)t , X4 =(0,-2)t,X6 =(-2,0)t给定初始增广权向量w1=(1 1 1)T ， C=1。要求：用感知器算法求模式分类的解向量 w。 解：此为线性不可分问题，利用感知器法求权向量

13、 权向量产生循环 (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)= 2x+2x?= 0所以：X1+X2 = 0由图看出判别面H把二类分开，但其中X2错分到3 1类， 而X1错分到3 2类，但大部分分类还是正确的。9、对一大批人进行癌症普查，患癌者以3 1类代表，正常人以3 2类代表。已知P(3 1)=，当然 P(3 2)=.设有一种诊断癌症的试验，其结果为“阳性”和“阴性” 两种反应。假设

14、根据临床记录发现这种方法有以下统计结果 ：患有癌症的人试验反应为阳性的概率 =，即p(x=m | 31)=患有癌症的人试验反应为阴性的概率=，即P(X=K | 3 1)=正常人试验反应为阳性的概率=，即P(X=阳| 3 2)=正常人试验反应为阴性的概率=，即P(X=阴| 3 2)=问：若被化验的人具有阳性反应，他患癌症的概率为多少解：P 1 |x 二阳P x=阳 I J PP X二阳P X=阳 I J P 1P X=阳 | 1 P 1 P X=阳 | 2 P 20.3230.95 0.0050.95 0.005 0.01 0.995因为，P(w?|x=阳)=1-P(w|x二阳)=P(wi |x=阳) 0为常数，一般可取a = 1或a = 1/N , N为模式向量的 11维数。这里，Wj与XiXj成正比才能保证不等式一定成立，即网络为稳定状态。 此式称为Hebb调节规则：若神经元 M与Nj的状态相同(同时兴奋或抑制)，则 Ni与Nj间的联系强度增