中科院模式识别第二次作业参考答案.pdf

模式识别模式识别 第一题第一题 (a) 计算样本均值的计算复杂度为：)(dnO 计算样本协方差的计算复杂度为：)( 2 ndO (b) 用递归方法计算样本均值： )( 1 1 1 1 1 1 )( 1 1 1 1 11 nnn nnn nnn x n x nn xn n 用递归方法求样本协方差： t nnnnn t nnnn t nnnnn t nnnn t nnnn n k t nknk t nnnn n k t nnnknnnk t nnnn n k t nknk n k t nknkn xx n C n n xx n n xx n C n n xx n xx n xx n xx n x n xx n x n xx n xx n xx n C )( 1 11 )( ) 1( )( ) 1( 11 )( 1 0)( ) 1( 1 )( 1 )( 1 )( 1 1 )( 1 1 1 )( 1 )( 1 )( 1 11 11 2 11 2 111111 2 1 1111 1 11 1111 1 11 1 1 111 (c) 用递归公式计算样本均值，每次更新的计算复杂度为：)(dO 用递归公式计算样本协方差，每次更新的计算复杂度为：)( 2 dO (d) 当样本量非常大，或者样本是边输入边分类的时候，考虑采用递归公式，这是在线分类。 当样本量比较小，可以全部输入之后再分类的时候，考虑采用非递归公式，这是离线分类。 递归公式适合在线情况，每次有新数据增加都可以更新，但是在逐次累加过程会出现舍入误差，会与真实值有略微偏差。 非递归方式在数据更新后，需要对原数据集重复计算一遍，带来重复计算。该方式比较容易实现并行计算。 在数据集较小且给定后不经常变的情况下，两种算法复杂度相当，选择任一都可，但是非递归方式可以有更高的精度。 对于在线数据，更适合递归方式。 第二题第二题 (a) EM 算法中的 E 步，计算得： 32 0 3132 2 3 1 1 0 320 ); 2|() 11 ln( ;| );,(ln),( 11 dxxxpe DDDpEQ i x gbgx i 由)()(),( 2121 xpxpxxp可得： )4|(); 2|( 0 32 0 3132 xpxxp 于是，可得： 32121121 32 0 23213121 2 1 1121 32 0 3132 2 3 1 1 0 )2ln( 4 1 4ln2 )4|(ln)ln( ); 2|() 11 ln(),( 11 dx dxxpxx dxxxpeQ i i x i i 当4 2 时，有： 12132121 4 0 1210 6ln3)2ln( 4 1 4ln2),( dxQ 当43 2 时，有： 1 2 21 2 32121 0 1210 ) 2 4(ln) 4 2()2ln( 4 1 4ln2),( 2 dxQ 当3 2 时，有： ),( 0 Q不存在。 对分布进行归一化，有), 0()( 22 UxP，故 1)( 22 dxxP 对)( 1 xP，有1 1 )( 1 010 11 11 dxedxxp x 因此，1 1 。 (b) 当4 2 时， 1210 6ln3),(Q。 当4, 1 21 时，取得最大值：16.10),( 0 Q 当43 2 时， 1 2 21 2 0 ) 2 4(ln) 4 2(),( Q。 当3, 1 21 时，取得最大值：52 . 8 ),( 0 Q 故，当 3 1 时，),( 0 Q取得最大值。 (c) 当 4 2 时，有 otherwise xxe xxP x 0 40 , 0 8 1 ),( 21 2 21 1 则图像表示如下： 当 3 1 时，有 otherwise xxe xxP x 0 30 , 0 3 1 ),( 21 21 1 则图像表示如下： 第三题第三题 (a) 计算均值 dv v h x h h x v h v h x h dv x h vx h dvvp h vx h h xx nh xpxp n n nnn n nn nn n i n i n nn )( 2 1 exp 2 )( 2 1 exp 2 1 )(2) 11 ( 2 1 exp)( 2 1 exp 2 1 )( 2 1 exp 2 1 )( 2 1 exp 2 11 )()( 1 )( 1 )()( 2 2 2 2 2 2 2 2 2 2 2 22 2 2 2 2 2 22 1 令： 2 2 2 2 2 n n h h ，)( 22 2 n h x 。 已知：1)( 2 1 exp 2 1 2 dv v 计算得： )( 2 1 exp 1 2 1 2 )( 2 1 exp 2 2 )( 2 2 2 2 2 2 2 2 2 2 2 2 2 2 n n n n n h x h h x h xp 故指数部分有： 2 2 2 2 222 4 2 2 2 2 2 2 2 2 2 2 )( )( nnnn h x h x h x h x 故有： )( 2 1 exp 2 1 )( 2 2 2 2 2 n n n h x h xp 因此：),()( 2 2 nn hNxp (b) 计算得： 22 2 2 1 )()( 1 )( 1 )( nn n n i n i n n h vx h vx hn h xx nh VarxpVar 2/ )( 2 1 exp 2/2 2/ 2 1 )( 2 1 exp) 2/ ( 2 1 exp 2 1 2 1 )()()( 2 2 2 2 2 22 22 n n n n nn h x h h dv v h vx dvvp h vx h vx )( 2 1 2/ )( 2 1 exp 2/2 2/1 )( 1 2 2 2 2 2 2 2 2 xp nhh x h h nhh vx nh nn n n n n n 0 )( 2 1 exp 2 1 )( 2 1 exp 2 1 )( 2 1 exp 2 111 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 x nh h h x h nh h h x h h nhh vx nh n n n n n n n n n n n n 结合上面式子，可得： )( 2 1 )(xp nh xPVar n n (c) 计算得： 2 2 2 2 2 2 2 2 2 2 2 2 )( 2 1 exp )/(1 1 1)( )( 2 1 exp 2 1)( 2 1 exp 2 1 )()( n n n n n n h xh h xp h x h x xpxp 对于 n h较小时，有： 2 2 )( 2 1 1 )(1 1 n n h h 2 2 2 2 2 2 )( 2 1 1 )(2 )( exp n n n h h xh 于是，可以证得： )(1 2 1 )(2 )( 1 2 1 11)()()( 22 2 2 2 2 2 2 xp xh h xhh xpxpxp n n nn n 第五题第五题 (a) 代码如下： dim = 3; n = 10000; points = mvnrnd(0,0,0,eye(3),n); points = points; figure(1); plot3(points(1,:),points(2,:),points(3,:),.); points = unifrnd(-0.5, 0.5, dim, n); (b) 代码如下： h = 0.01:0.01:1; numh = size(h, 2); pn = zeros(1, numh); for i = 1:numh k = sum(max(abs(points) h(i)/2),2); pn(i) = (k/n)/(h(i)3); end figure(2); plot(h, pn); xlabel(h);ylabel(pn(h); (c)代码如下： pn2 = zeros(1,n); sortedDist = sort(max(abs(points); for k = 1:n h = sortedDist(k); pn2(k) = (k/n)/(8*h3); end figure(3); plot(1:n, pn2); axis(1,10000,0,0.2); xlabel(n); ylabel(pn(n); (d) 代码如下： dim = 3; n = 10000; points = mvnrnd(0 ,0 ,0 ,eye(3) ,n) ; points = points ; figure (1) ; plot3( points (1 ,:) , points (2 ,:) , points (3 ,:) , . ) ; 第六题 (a) 代码如下： k = 1;% k can be changed to 1,3 sampData = 1.36, 1.41, 1.22, 2.46, 0.68, 2.51, 0.60, 0.64, 0.85, 0.66; n = size(sampData, 2); knnDist = ; for x = 0:0.01:3 sortedDist = sort(abs(x - sampData); knnDist = knnDist, sortedDist(k); end x = 0:0.01:3; pn = repmat(k/n, 1, size(x, 2)./(2 * knnDist); plot(x, pn); xlabel(x); ylabel(pn(x); axis(0,3,0,1); 当 K=1 时，有： 当 K=3 时，有 当 K=5 时，有： (b) 程序如下： k = 5; sampData = 0.011,1.27,0.13,-0.21,-2.18,0.34,-1.38,-0.12,-1.44. ,0.26; 1.03,1.28,3.12,1.23,1.39,1.96,0.94,0.82,2.31,1.94; n = size(sampData, 2); x = -2.5:0.01:2; y = -0.5:0.01:3.5; m = size(x, 2); q = size(y, 2); knnDist = zeros(m, q); for i = 1:m for j = 1:q sortedDist = sort(sqrt(x(i)-sampData(1,:).2 + (y(j)-sampData(2,:).2); knnDist(i,j) = sortedDist(k); end end pn = repmat(k/n, m, q)./(pi*(knnDist).2+0.01); plotx1,plotx2=meshgrid(x,y); mesh(plotx1,plotx2,pn); xlabel(x1);ylabel(x2);zlabel(pn(x1,x2); axis(-2.5, 2, -0.5, 3.5, 0,); 当 K=1 时，有： 当 K=3 时，有： 当 K=5 时，有： (c) 程序如下： k = 1; w1SampData = 0.28,0.07,1.54,-0.44,-0.81,1.52,2.20,0.91,0.65,-0.26;. 1.31,0.58,2.01,1.18,0.21,3.16,2.42,1.94,1.93,0.82;. -6.2,-0.78,-1.63,-4.32,5.73,2.77,-0.19,6.21,4.38,-0.96; w2SampData = 0.011,1.27,0.13,-0.21,-2.18,0.34,-1.38,-0.12,-1.44,0.26;. 1.03,1.28,3.12,1.23,1.39,1.96,0.94,0.82,2.31,1.94;. -0.21,0.08,0.16,-0.11,-0.19,-0.16,0.45,0.17,0.14,0.08; w3SampData = 1.36,1.41,1.22,2.46,0.68,2.51,0.60,0.64,0.85,0.66;. 2.17,1.45,0.99,2.19,0.79,3.22,2.44,0.13,0.58,0.51;. 0.14,-0.38,0.69,1.31,0.87,1.35,0.92,0.97,0.99,0.88; testData = -0.41,0.14,-0.81;0.82,0.72,0.61;0.88,4.1,-0.38; nt = size(testData,2); %calculate the smoothed pn(x|w1) nw1 = size(w1SampData, 2); pnw1 = zeros(nt,1); for i = 1:nt martixTesti = repmat(testData(:,i),1,nw1); sortedDist = sort(sqrt(sum(martixTesti - w1SampData).2); v = (4*pi/3)*sortedDist(k)3; pnw1(i,1) = (k/nw1)/(v + k/nw1); end %calculate the smoothed pn(x|w2) nw2 = size(w2SampData, 2); pnw2 = zeros(nt,1); for i = 1:nt martixTesti = repmat(testData(:,i),1,nw2); sortedDist = sort(sqrt(sum(martixTesti - w2SampData).2); v = (4*pi/3)*sortedDist(k)3; pnw2(i,1) = (k/nw2)/(v + k/nw2); end %calculate the smoothed pn(x|w3) nw3 = size(w3SampData, 2); pnw3 = zeros(nt,1); for i = 1:nt martixTesti = repmat(testData(:,i),1,nw3); sortedDist = sort(sqrt(sum(martixTesti - w3SampData).2); v = (4*pi/3)*sortedDist(k)3; pnw3(i,1) = (k/nw3)/(v + k/