现代模式识别-习题解答.pdf

1 第二章 习题解第二章 习题解 2 72 7 试用最大最小距离聚类算法对样本集 X 进行聚类 1234567 0 0 0 1 4 4 4 5 5 4 5 5 1 0 Xx x x x x x x 解解 Step1Step1 选第一个类心 11 0 0 zx 找距离 1 z 最远的样本 6 5 5 x 作为第二个类心 26 5 5 zx 计算 22 1212 05 05 5 2d z zzz 取参数 0 3 求距离门限 12 0 3 5 21 5 2Td z z Step2Step2 对剩余样本按最近原则聚类 2222 21212222 00 1 0 1 05 1 5 41d x zxzd x zxz 212221 min 11 5 2d x zd x zd x zT 21 x 2222 31313132 40 40 4 2 45 45 2d x zxzd x zxz 313232 min 21 5 2d x zd x zd x zT 31 x 2222 41414242 40 50 41 45 55 1d x zxzd x zxz 414242 min 11 5 2d x zd x zd x zT 42 x 2222 51515252 50 40 41 55 45 1d x zxzd x zxz 515252 min 11 5 2d x zd x zd x zT 52 x 2222 71717272 1 0 00 1 1 5 05 41d x zxzd x zxz 717271 min 11 5 2d x zd x zd x zT 71 x 所有样本均已归类 故聚类结果为 1127 x x x 23456 x x x x 2 8 2 8 对 2 7 题中的样本集 X 试用 C 均值算法进行聚类分析 解解 取类数 C 2 Step1Step1 选初始类心 0 11 0 0 zx 第一个类心 0 22 0 1 zx Step2Step2 按最近原则聚类 2 由图示可知 0 0 7172 1 2xzxz 其余样本距离 0 2 z 较近 所以第一次聚类 为 117 x x 223456 x x x x x Step3Step3 计算类心 1 117 0 11 2 1 0002 zxx 1 223456 0445518 5 1 1454519 55 zxxxxx Step4Step4 若类心发生变换 则返回 Step2 否则结束 计算过程如下 1 22 1 222 1112 0 1 2 01 4 0 18 5 0 19 5 xzxz 11 x 1 22 1 222 2122 0 1 2 15 4 0 18 5 1 19 5 104 5xzxz 21 x 1 22 1 222 7172 1 1 2 01 4 1 18 5 0 19 5 106 5xzxz 71 x 1 222 1 222 3132 4 1 2 40 28 25 4 18 5 4 19 5 0 2xzxz 32 x 1 222 1 222 4142 4 1 2 50 37 25 4 18 5 5 19 5 1 6xzxz 42 x 同理可得 562 x x 所以第二次聚类为 1127 x x x 23456 x x x x 计算新的类心 3 1127 00 11 3 1 0 1 01 33 zxxx 1 23456 44559 2 1 45459 24 zxxxx 同上 第三次聚类为 1127 x x x 23456 x x x x 各样本类别归属不变 所以类心也不变 故结束 2 102 10 已知六维样本 3 12345 0 1 3 1 3 4 3 3 3 1 2 1 1 0 0 0 1 0 1 3 3 3 1 2 1 0 0 1 0 1 0 xxxxx 试按最小距离法进行分级聚类分析 解解 计算样本点间的平方距离矩阵D 0 其元素为 0 2 ijij dxx i j 1 2 5 亦可 用 0 ijij dxx 0 023242526 230241525 2424073 25157012 26253120 D 3 x 与 5 x 的距离最小 合为一类 1 335 Gx x 用最近距离递推公式求第一层的类间平方距离矩阵D 1 1 0232425 2302415 242407 251570 D 1 335 Gx x 与 1 44 Gx 的距离最小 合为一类 2 1 1 334345 GGGx xx 2 02324 23015 23 150 D 2 22 Gx 与 2 3345 Gx xx 的距离最小 合为一类 3 2 2 2232345 GGGxx xx 聚类过程图示 1 x 2 x 3 x 4 x 5 x 1 x 2 x 1 335 Gx x 4 x 1 x 2 x 2 3345 Gx xx 1 x 3 22345 Gxx xx 由于本题每层均只有一类含多个样本 而其余均为单样本 因此各种聚类函数值均指示 第 n 层聚类结果比第 n 1 层好 n 0 1 2 一 解 1 略 4 2 S1 pattern S2 pat S3 stop D S1 S2 n1 n2 2n12 n1 n2 n12 7 3 2 3 7 3 3 4 7 D S1 S3 7 4 2 2 7 4 2 7 9 D S2 S3 3 4 2 2 3 4 2 3 5 7 9 3 5 4 7 按 T 测试由大到小排序为 pattern stop pat stop pattern pat 二 解 1 证明欧氏距离具有平移和正交旋转不变性 0 0 0 0 d x yxyxxyx d xxyy 欧氏距离具有平移不变性 正交变换距阵 A 具有性质 A A I d Ax AyAxAy AxAyAxAy xyA A xy xyxy xy d x y 欧氏距离具有正交旋转不变性 2 马氏距离对一切非奇异线性变换具有不变性 非奇异矩阵 A 存在 A 1 1 111 1 i jijij ijij ijij ij d Ax AxAxAxAVAAxAx xxA AVAA xx xxVxx d x y 马氏距离对于一切非奇异线性变换具有不变性 三 解 当聚类数目 C 2 时 存在三种可能分组 1 W1 x 2 x 0 W2 x 5 2 W1 X 2 W2 X 0 X 3 W1 X 2 X W2 X 0 利用公式 2 11 j n C j Wij ji Jxm 和欧氏距离公式得到 22 123 2 2 2 11 2 1 Www kk Jk JJ kk k 当时 Jw2 Jw1 Jw2 Jw3 最小化Jw的划分为第 2 种 k 个 x 0 和一个 x 样本分为一类 2 2 1 321 k JwJwJw 当 时 最优分组为第 1 种 将 k 个 x 2 和 k 个 x 0 的样本分为一类 四 解 1 按照 2 11 j n C j Wij ji Jxm 和欧氏距离公式 a a 1 2 12 2222 2222 4 1 45 2 5 2 5 22 05 10 2 5 0 5 22 42 5 54 5 12 5 44 5 02 5 1 0 5 52 5 00 5 18 waww m m JJJ 同理可得 wb J 18 wc J 52 3 wcwbwa JJJ 第 C 类划分最好 f 2 按照 b 6 1 42 51 2 502 552 5 42 554 5 1 2 544 5 02 51 0 5 52 500 5 54 544 51 0 500 5 16 C ii d ix m da Jxmxm J 同理 db J 16 dc J 64 3 按 d J 聚类 第 a 和 b 划分是最好的 五 解方法同第 4 题 1 按 w J 聚类 13 8 21 8 4 3 wawbwc JJJ 第 C 类划分最好 2 按 d J 聚类 1 16 1 1 3 dadbdc JJJ 第 a 类划分最好 六 解 树图如下 7 第三章第三章 习题答案习题答案 一 设一 3 类问题有如下判决函数 d1 x x1 d2 x x1 x2 1 d3 x x1 x2 1 试画出下列各种情况的判决边界及各类的区域 1 满足 3 4 2 节中的第一种情况 2 满足 3 4 2 节中的第二种情况 且令 d12 x d1 x d13 x d2 x d23 x d3 x 3 满足 3 4 2 节中的第三种情况 解 1 ii ww两分法 2 Wi Wj 两分法 8 W1 W3 W2 D23 x x1 x2 1D12 x x1D13 x x1 x2 1 IR IR 2 x 1 x 3 没有不确定区的 Wi Wj 两分法 9 232 d x 2x 1312 21dxxx 1212 21dxxx 2 x 1 x 二 证明感知器的收敛性 证明 如果模式是线性可分的 则存在判别函数的最佳权向量解 w 利用梯度下降法求解函数的 极小值点 即为 w 构造准则函数 J wk w xw x k 0 当 w x 0 w 9 w 8 k kd xx k1k 9 x x w k 1 0 w 10 w 9 k kd xx k2k 10 x x w k 2 0 w 11 w 10 k kd xx k33k 11 x x w k 0 w 12 w 11 x 2 3 1 2 k kd xx k4k 12 x x w k 1 0 w 13 w 12 k kd xx k55k 13 x x w k 10 w 15 w 14 k d x k7k 15 x x 2 0 w 16 w 15 k d x k8k 16 x x 2 0 w 17 w 16 k d x k1k 17 x x 1 0 w 18 w 17 k d x k2k 18 x x 3 0 w 19 w 18 k d x k3 k44 k55 k6 k 19 x x 1 0 w 20 w 19 k 20 x x 0 w 21 w 20 x 3 2 2 2 k 21 x x 0 w 22 w 21 x 3 2 3 1 k 22 x x 4 0 w 23 k k k k d x d x d x d x k7 k8 k1 w 22 k 23 x x 1 0 w 24 w 23 k 24 x x 1 0 w 25 w 24 k 25 x x 1 0 w 26 w 25 k k k d x d x d x k2k 26 x x 4 0 w 27 w 26 kd x 15 k3k 2 7 x x 1 0 w 2 8 w 2 7 kdx 4 k k 2 8 x x 2 0 w 2 9 w 2 8 k dx 5 k k 2 9 x x 2 0 w 3 0 w 2 9 k dx 3 由上面的结果可以看出 经过迭代w 22 能对所有训练样本正确分类 w 3 2 3 1 判别界面方程为 3x1 2x2 3x3 1 0 六 用 MSE 梯度法 算法检验下列模式的线性可分性 1 0 1 0 1 2 1 0 1 0 解 将训练样本增广及规范化后 得到 1234 0 1 1 0 1 1 1 0 1 1 0 1 xxxx 则 011 011 101 101 x 利用伪逆法 1 1 2 3 4 001 21 2 1 21 200 1 41 41 41 4 wx b x xx b b b b b 利用 H K 算法 设 0 1 1 1 1 1 b 置步数 k 0 则 0 0 0 0 0 0 wx b 0 0 0 1 1 1 1 exwb 16 0 e 的各分量均为负值 则停止迭代 无法求得方程组的解 w 所以模式线性不可分 七 已知 1 0 0 2 1 1 3 1 1 用感知器算法求该三类问题的 判别函数 并画出解区域 解 d x 9x2 7y2 5 设 y1 x 2 y 2 x 则广义线性判别函数为 12 975d yyy 它对应的正负空间如下图 第四章第四章 习题解习题解 4 2 设一维两类模式满足正态分布 它们的均值和方差分别为 设一维两类模式满足正态分布 它们的均值和方差分别为 1 1 0 0 1 1 2 2 2 2 2 2 2 2 2 p x N 2 p x N 窗函数 窗函数P P 1 1 P P 2 2 取 0 1 损失函数 试算出判决边界点 并绘出它 们的概率密度函数曲线 试确定样本 3 2 1 3 5 各属哪一类 取 0 1 损失函数 试算出判决边界点 并绘出它 们的概率密度函数曲线 试确定样本 3 2 1 3 5 各属哪一类 解解 已知 2 1 1 exp 82 2 x p x 2 2 1 2 exp 82 2 x p x 17 1 p x 2 p x 由 Bayes 最小损失判决准则 如果 122122 1212 211211 p xP lx p xP 则判 1 x 否则判 2 x 22 1212 2 1 exp exp 1 882 xxx lx 12 11 ln exp lnln10 22 xx 如果 1x 则判 1 x 否则判 2 x 3 2 属于 1 1 3 5 属于 2 4 7 在图像识别中 假定有灌木丛和坦克两种类型 分别用在图像识别中 假定有灌木丛和坦克两种类型 分别用 1 1和和 2 2表示 它们的先验 概率分别为 0 7 和 0 3 损失函数如表 3 1 所示 现在做了四次试验 获得四个样本的类概 率密度如下 表示 它们的先验 概率分别为 0 7 和 0 3 损失函数如表 3 1 所示 现在做了四次试验 获得四个样本的类概 率密度如下 1 xp 0 1 0 15 0 3 0 6 2 xp 0 8 0 7 0 55 0 3 1 试用贝叶斯最小误判概率准则判决四个样本各属于哪个类型试用贝叶斯最小误判概率准则判决四个样本各属于哪个类型 2 假定只考虑前两种判决 试用贝叶斯最小风险准则判决四个样本各属于哪个类型假定只考虑前两种判决 试用贝叶斯最小风险准则判决四个样本各属于哪个类型 3 将拒绝判决考虑在内 重新考核四次试验的结果将拒绝判决考虑在内 重新考核四次试验的结果 表 3 1 类型 损失 判决 1 2 1 判为 1 0 5 2 0 2 判为 2 4 0 1 0 3 拒绝判决 1 5 1 5 1 x x1 x2 x3 x4 x 18 解解 1 两类问题的 Bayes 最小误判概率准则为 如果 12 1212 21 p xP lx p xP 则判 1 x 否则判 2 x 由已知数据 12 0 3 0 7 3 7 样本x1 l12 x1 0 1 0 8 12 3 7 x1 2 样本x2 l12 x2 0 15 0 7 12 3 7 x3 1 样本x4 l12 x4 0 6 0 3 12 3 7 x4 1 2 不含拒绝判决的两类问题的 Bayes 最小风险判决准则为 如果 122122 1212 211211 p xP lx p xP 则判 1 x 否则判 2 x 由已知数据 12 0 3 2 1 0 7 4 0 5 3 24 5 样本x1 l12 x1 1 8 12 6 49 x1 1 样本x2 l12 x2 3 14 12 6 49 x2 1 样本x3 l12 x3 6 11 12 6 49 x3 1 样本x4 l12 x4 6 3 12 6 49 x4 1 3 含拒绝判决的两类问题的 Bayes 最小风险判决准则为 1 2 3 if min then 3 iji j RxRxxi 时为拒绝判决 其中条件风险 2 1 1 2 3 jjii i RxPxj 后验概率 2 1 iiiiiii i Pxp xPp xp xPp xP 2 1 1 1 2 3 jjiii i Rxp xPj p x 记 2 1 1 2 3 jjiii i rxp xPj 4 7 1 则 含拒绝判决的两类问题的 Bayes 最小风险判决准则为 1 2 3 if r min then 3 iji j xrxxi 时为拒绝判决 对四个样本逐一列写下表 用 4 7 1 式计算r j x 样本x1 j i 类型 损失 判决 1 p x 1 P 1 0 1 0 7 0 07 2 p x 2 P 2 0 8 0 3 0 24 r j x 1 判为 1 0 5 2 0 0 5 0 07 2 0 24 0 515 19 2 判为 2 4 0 1 0 4 0 07 1 0 24 0 52 3 拒绝判决 1 5 1 5 1 5 0 07 1 5 0 24 0 465 因为r 3 x1 0 465 最小 所以拒绝判决 样本x2 j i 类型 损失 判决 1 p x 1 P 1 0 15 0 7 0 105 2 p x 2 P 2 0 7 0 3 0 21 r j x 1 判为 1 0 5 2 0 0 5 0 105 2 0 21 0 4725 2 判为 2 4 0 1 0 4 0 105 1 0 21 0 63 3 拒绝判决 1 5 1 5 1 5 0 105 1 5 0 21 0 4725 因为r 1 x2 0 4725 最小 所以判x2 1 即灌木丛 或拒绝判决 样本x3 j i 类型 损失 判决 1 p x 1 P 1 0 3 0 7 0 21 2 p x 2 P 2 0 55 0 3 0 165 r j x 1 判为 1 0 5 2 0 0 5 0 21 2 0 165 0 435 2 判为 2 4 0 1 0 4 0 21 1 0 165 1 005 3 拒绝判决 1 5 1 5 1 5 0 21 1 5 0 165 0 5625 因为r 1 x3 0 435 最小 所以判x3 1 即灌木丛 样本x4 j i 类型 损失 判决 1 p x 1 P 1 0 6 0 7 0 42 2 p x 2 P 2 0 3 0 3 0 09 r j x 1 判为 1 0 5 2 0 0 5 0 42 2 0 09 0 39 2 判为 2 4 0 1 0 4 0 42 1 0 09 1 77 3 拒绝判决 1 5 1 5 1 5 0 42 1 5 0 09 0 765 因为r 1 x4 0 39 最小 所以判x4 1 即灌木丛 4 9 假设两类二维正态分布参数为4 9 假设两类二维正态分布参数为 1 1 1 0 1 0 2 2 1 0 先验概率相等 1 令 1 0 先验概率相等 1 令 1 1 2 2 I 试给出负对数似然比判决规则 2 令 I 试给出负对数似然比判决规则 2 令 1 11 2 1 21 2 11 2 1 21 试给出负对数似然比判决规则 试给出负对数似然比判决规则 解解 Bayes 最小误判概率似然比判决规则为 如果 12 1212 21 1 p xP lx p xP 则判 1 x 否则判 2 x 相应的负对数似然比判决规则为 如果 122112 ln ln ln lnln10lxp xp x 则判 1 x 否则 判 2 x 20 对于正态分布 1 21 2 11 exp 2 2 iiii n i p xxx 11 1212111222 1 ln ln ln 2 lxxxxx 1 由已知 22 11 12 1 22 11 1 111 exp exp 002222 xx xx p xI xx 22 11 12 2 22 11 1 111 exp exp 002222 xx xx p xI xx 22 1221111 ln ln ln 1 1 4lxp xp xxxx 故 如果 1 0 x 则判 1 x 否则判 2 x 2 1 11 2 3 4 1 21 2 11 2 3 4 1 21 1 1 1 11 211 2 4 1 211 213 2 1 1 11 211 2 4 1 211 213 1111 12 2222 111111 211 2 1414 ln 1 211 212323 xxxx lx xxxx 1212 11 11 2222 1 21 2 11 22 11 33 22 xxxx xx xx xxxx 11 1122211222 112 1 1 2 1 1 2 322 xx xxxxxxxxxx 112 4 2 3 xx x 1212 if 2 0 then else xxxx 即 121212 if 0 and 2 0 and 2 then else xxor xxxx 21 补充题 1 假设两类一维模式的概率密度函数为 补充题 1 假设两类一维模式的概率密度函数为 1 0 51 02 0 xx p x 其它 2 0 50 5 13 0 xx p x 其它 先验概率相等 1 求 Bayes 判决函数 用 0 1 损失函数 2 求总的误判概率 先验概率相等 1 求 Bayes 判决函数 用 0 1 损失函数 2 求总的误判概率 解解 1 当用 0 1 损失函数且先验概率相等时 Bayes 最小损失判决规则为 如果 122122 211211 1 p xP p xP 则判 1 x 否则判 2 x 即 12 p xp x 则判 1 x 否则判 2 x 代入本题类概率密度函数得 如果x 1 5 则判x 1 否则判x 2 故 Bayes 判决函数为d x 1 5 x 2 误判概率 21 1112 P ePp xdxPp xdx 22 21 5 1 51 111 0 51 0 50 5 228 P exdxxdx 补充题 2 在目标识别中 假定类型 1 为敌方目标 类型 2 为诱饵 假目标 已知先验概率 P 1 0 2 和 P 2 0 8 类概率密度函数如下 补充题 2 在目标识别中 假定类型 1 为敌方目标 类型 2 为诱饵 假目标 已知先验概率 P 1 0 2 和 P 2 0 8 类概率密度函数如下 1 01 2 12 0 xx p xxx 其它 1 1 12 3 23 0 xx p xxx 其它 1 求贝叶斯最小误判概率准则下的判决域 并判断样本 x 1 5 属于哪一类 2 求总错误概率 P e 3 假设正确判断的损失 11 22 0 误判损失分别为 12 和 21 若采用最小损失判决 准则 12 和 21 满足怎样的关系时 会使上述对 x 1 5 的判断相反 解 1 求贝叶斯最小误判概率准则下的判决域 并判断样本 x 1 5 属于哪一类 2 求总错误概率 P e 3 假设正确判断的损失 11 22 0 误判损失分别为 12 和 21 若采用最小损失判决 准则 12 和 21 满足怎样的关系时 会使上述对 x 1 5 的判断相反 解 1 应用贝叶斯最小误判概率准则如果 1 应用贝叶斯最小误判概率准则如果 2 1 12 xp xp xl 1 2 P P 则判 则判 2 1 x 得 得 l l1212 1 5 1 1 5 1 1 而上 式第二项的指数项比第一项的指数项下降快 且最大值 x 时 都是 1 所以 2 2 1 1 exp 2222 N NN x Var pxp x NhNh 证毕 第六章第六章 习题解习题解 6 3 有七个二维矢量 有七个二维矢量 1 1231 1 0 0 1 0 1 Xxxx 2 45672 0 0 0 2 0 2 2 0 Xxxxx 1 画出最近邻法决策面 2 求样本均值 若按离样本均值距离的大小进行分类 试画出决策面 解 1 画出最近邻法决策面 2 求样本均值 若按离样本均值距离的大小进行分类 试画出决策面 解 1 若按 1 NN 进行分类 则决策面由 1 i xX 与 2 j xX 连线的中垂面构成 2 1123 11 0 33 mxxx 24567 11 0 42 mxxxx 则按离样本均值距离的大小进行分类的决策面是 1 m 与 2 m 连线的中垂面 27 第七章第七章 习题解习题解 7 11 若有下列两类样本集 若有下列两类样本集 1234 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 Xxxxx 2 2 2 2 2 12342 0 0 1 0 1 0 0 1 1 1 1 1 Xxxxx 试用 K L 变换将特征空间维数降到 d 2 和 d 1 并用图画出样本在该特征空间中的位 置 解 试用 K L 变换将特征空间维数降到 d 2 和 d 1 并用图画出样本在该特征空间中的位 置 解 一 用 一 用Sw做从三维到二维降维 做从三维到二维降维 1 求各类均值矢量 1 1 1 1 1 01113 4 11 0001 1 4 4 00101 4 i N i mx N 2 2 2 1 2 00011 4 11 0111 3 4 4 10113 4 N i i mx N 2 求类内离差矩阵 Sw 1 1 1 111 1 1 311 11 131 16 113 ii N i Swxmxm N 2 2 2 222 1 2 311 11 131 16 113 ii N i Swxmxm N 1 0 0 5 2 2 1 2 按离均值距离的决策面 1 12 1 NN 1判决域 28 12 311 111 131 2216 113 SwSwSw 1 211 4121 112 Sw 3 求 3 求Sw的本征值与本征矢量 的本征值与本征矢量 2 3 1 161 16 16 311 1 161 16 0 16416 3 1 161 16 16 SwI 123 1 4 1 16 11 1 Swvv 11 22 33 311 11 131 164 113 vv vv vv 11 2122 33 3411010 11 134101 1 22 1134001 vv vvvu vv 由施密特正交化方法得 由施密特正交化方法得 2 2对应的与对应的与 1 v 正交的本征矢量 正交的本征矢量 21 221 11 0111 2 11111 1 0 1 1 111 2 22222 1001 u v vuv v v 归一化 归一化 2 1 1 1 6 2 v 故 变换矩阵为 故 变换矩阵为 12 1 21 6 1 21 6 02 6 Vv v 三维到二维降维变换为 三维到二维降维变换为Y XV 29 1 1 00 000 1 21 6 1 21 6 100 1 21 6 101 1 23 6 02 6 110 2 20 YX V 2 2 02 6 001 1 21 6 0101 21 6 1 21 6 011 1 21 6 02 6 111 2 22 6 YXV 二 用 二 用Sw做一维特征提取 取小的本征值 做