资源描述
第 2章 聚类分析习题解答 2.1 设有 10个二维模式样本，如图 2.13所示。若 2 1 ，试用最大最小距离算 法对他们进行聚类分析。 解： 取 T 1 1 0 , 0 X Z 。 选离 1 Z 最远的样本作为第二聚类中心 2 Z 。 2 0 1 0 1 2 2 21 D ， 8 31 D ， 58 41 D ， 45 51 D 52 61 D ， 74 71 D ， 45 81 D ， 58 91 D ， 65 1 , 10 D 最大者为 D 71 ， T 7 2 7 , 5 X Z 74 2 1 2 1 Z Z T 计算各样本与 2 1 , Z Z 间距离，选出其中的最小距离。 74 12 D ， 52 22 D ， 34 32 D ， 13 2 , 10 D 13 , 20 , 17 , 0 , 2 , 5 , 4 , 8 , 2 , 0 ) , min( 2 1 i i D D 74 2 1 20 ) , maxmin( 92 2 1 T D D D i i , T 9 3 3 , 7 X Z 继续判断是否有新的聚类中心出现： 58 74 0 13 12 11 D D D ， 40 52 2 23 22 21 D D D ， 1 13 65 3 , 10 2 , 10 1 , 10 D D D 1 , 0 , 1 , 0 , 2 , 5 , 4 , 8 , 2 , 0 ) , , min( 3 2 1 i i i D D D 74 2 1 8 ) , , maxmin( 31 3 2 1 T D D D D i i i 寻找聚类中心的步骤结束。 按最近距离分到三个聚类中心对应的类别中： 3 2 1 1 , , : X X X ； 7 6 5 4 2 , , , : X X X X ； 10 9 8 3 , , : X X X 1 3 5 7 9 1 3 5 7 X 1 X 4 X 3 X 5 X 8 X 9 X 7 X 10 X 2 X 6 x 1 x 2 图2.13 10个二维模式样本 2.2 设有 5个二维模式样本如下： T 1 0 , 0 X ， T 2 1 , 0 X ， T 3 0 , 2 X ， T 4 3 , 3 X ， T 5 4 , 4 X 定义类间距离为最短距离，且不得小于 3。利用层次聚类法对 5个样本进行 分类。 解：(1) 将每一样本看作单独一类，得 1 1 ) 0 ( X G ， 2 2 ) 0 ( X G ， 3 3 ) 0 ( X G ， 4 4 ) 0 ( X G ， 5 5 ) 0 ( X G 计算各类间欧氏距离： 2 1 12 ) 0 ( X X D 2 1 2 22 12 2 21 11 x x x x 1 1 0 2 1 2 ) 0 ( 3 1 13 X X D 同理可求得： ) 0 ( 14 D ， ) 0 ( 15 D ； ) 0 ( 23 D ， ) 0 ( 24 D ， ) 0 ( 25 D ； ) 0 ( 34 D ， ) 0 ( 35 D ； ) 0 ( 45 D ； 得距离矩阵 D(0)为 D(0) ) 0 ( 1 G ) 0 ( 2 G ) 0 ( 3 G ) 0 ( 4 G ) 0 ( 5 G ) 0 ( 1 G 0 ) 0 ( 2 G 1 0 ) 0 ( 3 G 2 5 0 ) 0 ( 4 G 18 13 10 0 ) 0 ( 5 G 32 25 20 2 0 (2) 将最小距离 1对应的类 ) 0 ( 1 G 和 ) 0 ( 2 G 合并为一类，得到新的分类 ) 0 ( ), 0 ( ) 1 ( 2 1 12 G G G ， ) 0 ( ) 1 ( 3 3 G G ， ) 0 ( ) 1 ( 4 4 G G ， ) 0 ( ) 1 ( 5 5 G G 按最短距离法计算类间距离，由 D(0)矩阵递推得到聚类后的距离矩阵 D(1)为 D(1) ) 1 ( 12 G ) 1 ( 3 G ) 1 ( 4 G ) 1 ( 5 G ) 1 ( 12 G 0 ) 1 ( 3 G 2 0 ) 1 ( 4 G 13 10 0 ) 1 ( 5 G 25 20 2 0 (3) 将 D(1)中最小值 2 对应的类合并为一类，得 D(2)。 D(2) ) 2 ( 12 G ) 2 ( 3 G ) 2 ( 45 G ) 2 ( 12 G 0 ) 2 ( 3 G 2 0 ) 2 ( 45 G 13 10 0 (4) 将 D(2)中最小值 2对应的类合为一类，得 D(3)。 D(3) ) 3 ( 123 G ) 3 ( 45 G ) 3 ( 123 G 0 ) 3 ( 45 G 10 0 D (3)中的最小元素为 3 10 ，聚类结束，结果为： 3 2 1 1 , , X X X G ， 5 4 2 , X X G 2.3 用 K-均值算法对下列 6个模式样本进行聚类分析，设聚类中心数 K=2。 T 1 0 , 0 X ， T 2 0 , 1 X ， T 3 1 , 1 X T 4 4 , 4 X ， T 5 4 , 5 X ， T 6 5 , 5 X 解： 因 2 K ，任选两个聚类中心 T 1 1 0 , 0 ) 1 ( X Z 和 T 2 2 0 , 1 ) 1 ( X Z 。 计算距离，聚类： 1 X ： 1 1 0 0 0 | ) 1 ( | 0 | ) 1 ( | 2 2 2 1 2 1 1 1 Z X Z X D D ) 1 ( 1 1 2 1 S X D D 2 X ： 0 | ) 1 ( | 1 | ) 1 ( | 2 2 2 1 2 1 Z X Z X D D ) 1 ( 2 2 1 2 S X D D 3 X ： 1 | ) 1 ( | 2 | ) 1 ( | 2 3 2 1 3 1 Z X Z X D D ) 1 ( 2 3 1 2 S X D D 4 X ： 5 | ) 1 ( | 2 4 | ) 1 ( | 2 4 2 1 4 1 Z X Z X D D ) 1 ( 2 4 1 2 S X D D 可得到： 1 , ) 1 ( 1 1 1 N S X 5 , , , , , ) 1 ( 2 6 5 4 3 2 2 N S X X X X X 计算新的聚类中心： T 1 1 0 , 0 ) 2 ( X Z T 6 3 2 1 2 2 8 . 2 , 2 . 3 ) ( 5 1 1 ) 2 ( 2 X X X X Z X S N 判断： ) 1 ( ) 2 ( j j Z Z ， 2 , 1 j ，故返回第步。 由新的聚类中心得： 1 X ： | ) 2 ( | | ) 2 ( | 2 1 2 1 1 1 Z X Z X D D ) 2 ( 1 1 S X 2 X ： | ) 2 ( | | ) 2 ( | 2 2 2 1 2 1 Z X Z X D D ) 2 ( 1 2 S X 3 X ： | ) 2 ( | | ) 2 ( | 1 3 2 1 3 1 Z X Z X D D ) 2 ( 1 3 S X 同理有： ) 2 ( 2 4 S X ， ) 2 ( 2 5 S X ， ) 2 ( 2 6 S X 得 3 , , , ) 2 ( 1 3 2 1 1 N X X X S 3 , , , ) 2 ( 2 6 4 4 2 N X X X S 重新计算聚类中心： T 3 2 1 2 1 1 3 . 0 , 7 . 0 ) ( 3 1 1 ) 3 ( 1 X X X X Z X S N T 6 5 4 2 2 2 3 . 4 , 7 . 4 ) ( 3 1 1 ) 3 ( 2 X X X X Z X S N ) 2 ( ) 3 ( j j Z Z ， 2 , 1 j ，返回第步，以Z 1 (3)，Z 2 (3)为中心进行聚类。 按新的聚类中心分类，求得的分类结果与前一次迭代结果相同，即 ) 2 ( ) 3 ( 1 1 S S ， ) 2 ( ) 3 ( 2 2 S S 9 计算新聚类中心向量值，聚类中心与前一次结果同，即 T 1 1 3 . 0 , 7 . 0 3 ) 4 ( Z Z ， T 2 2 3 . 4 , 7 . 4 3 ) 4 ( Z Z 算法结束。聚类中心为： T 1 3 . 0 , 7 . 0 Z ， T 2 3 . 4 , 7 . 4 Z 聚类结果为： , , ) 2 ( 3 2 1 1 X X X S ， , , ) 2 ( 6 4 4 2 X X X S 2.4 用 ISODATA 算法对题 2.1中的 10个模式样本进行聚类分析。 解：10个模式样本为 T 1 0 , 0 X ， T 2 1 , 1 X ， T 3 2 , 2 X ， T 4 7 , 3 X ， T 5 6 , 3 X T 6 6 , 4 X ， T 7 7 , 5 X ， T 8 3 , 6 X ， T 9 3 , 7 X ， T 10 4 , 7 X (1)第一步：任意预选 N C =1， T 1 1 0 , 0 X Z ，K=3， 1 N ， 2 S ， 4 C ，L=0，I=5。 (2)第二步：按最近邻规则聚类。目前只有一类， 10 , , , 1 10 2 1 1 N S ， X X X 。 (3)第三步：因 N N 1 ，无聚类删除。 (4)第四步：修改聚类中心 1 1 1 1 S N X X Z 90 . 3 80 . 3 4 7 3 7 3 6 7 5 6 4 6 3 7 3 2 2 1 1 0 0 10 1 (5)第五步：计算类内平均距离 1 D 。 1 1 1 1 1 S N D X Z X 1 10 1 2 1 1 10 1 Z X Z X Z X 2 2 2 2 2 2 9 . 3 4 8 . 3 7 9 . 3 1 8 . 3 1 9 . 3 0 8 . 3 0 10 1 19 . 3 88 . 31 10 1 (6)第六步：计算总体平均距离 D。因只有一类， 19 . 3 1 D D 。 (7)第七步：不是最后一次迭代，且 2 K N C ，故进入第八步进行分裂运算。 (8)第八步：求 S 1 的标准差向量 T 12 , 11 1 。 2 11 1 , 10 2 11 21 2 11 11 11 10 1 z x z x z x 2 2 2 8 . 3 7 8 . 3 1 8 . 3 0 10 1 32 . 2 6 . 53 10 1 2 12 2 , 10 2 12 22 2 12 12 12 10 1 z x z x z x 2 2 2 9 . 3 4 9 . 3 1 9 . 3 0 10 1 39 . 2 9 . 56 10 1 得 T 39 . 2 , 32 . 2 1 。 (9)第九步： 1 的最大分量 39 . 2 max 1 。 (10)第十步：因 S max 1 且 2 K N C ，将 Z 1 分裂为两个新的聚类中心。因 max 1 是 1 的第二个分量，故在 Z 1 的 第二个分量方向上进行分裂，分裂系数 k选为 0.5，得 T T T max 1 1 10 . 5 , 80 . 3 39 . 2 5 . 0 90 . 3 , 80 . 3 5 . 0 90 . 3 , 80 . 3 Z T T T max 1 1 71 . 2 , 80 . 3 39 . 2 5 . 0 90 . 3 , 80 . 3 5 . 0 90 . 3 , 80 . 3 Z 令 1 1 Z Z ， 1 2 Z Z ，N C 加 1，迭代次数加 1（I=2） 。跳回到第二步，进行第 2次迭代运算。 (11)第二步：按最近邻规则对所有样本聚类。 78 . 21 71 . 2 0 80 . 3 0 | | 45 . 40 10 . 5 0 80 . 3 0 | | 2 2 2 1 12 2 2 1 1 11 Z X Z X D D 2 1 11 12 S D D X 76 . 10 71 . 2 1 80 . 3 1 | | 65 . 24 10 . 5 1 80 . 3 1 | | 2 2 2 2 22 2 2 1 2 21 Z X Z X D D 2 2 21 22 S D D X 2 2 2 10 2 , 10 2 2 1 10 1 , 10 71 . 2 4 80 . 3 7 | | 10 . 5 4 80 . 3 7 | | Z X Z X D D 1 10 2 , 10 1 , 10 S D D X 得到两个聚类分别为 10 7 6 5 4 1 , , , , X X X X X S ，N 1 =5 9 8 3 2 1 2 , , , , X X X X X S ，N 2 =5 (12)第三步：因 N 1 和 N 2 都大于 N ，无聚类删除。 (13)第四步：修改聚类中心，得 T 10 7 6 5 4 1 00 . 6 , 40 . 4 30 22 5 1 5 1 X X X X X Z T 9 8 3 2 1 2 80 . 1 , 20 . 3 9 16 5 1 5 1 X X X X X Z (14)第五步：计算类内平均距离 1 D 和 2 D ，得 1 10 1 7 1 6 1 5 1 4 1 5 1 Z X Z X Z X Z X Z X D 2 2 2 2 2 2 00 . 6 4 40 . 4 7 00 . 6 6 40 . 4 3 00 . 6 7 40 . 4 3 5 1 59 . 1 2 9 2 8 2 3 2 2 2 1 2 5 1 Z X Z X Z X Z X Z X D 2 2 2 2 2 2 80 . 1 3 20 . 3 7 80 . 1 1 20 . 3 1 80 . 1 0 20 . 3 0 5 1 85 . 2 (15)第六步：计算总体平均距离 D，得 22 . 2 85 . 2 5 59 . 1 5 10 1 5 5 10 1 1 2 1 2 1 j j j D D D N N D (16)第七步：因这是偶数次迭代，符合第七步的第（3）条，进入第十一步。 (17)第十一步：计算聚类中心之间的距离，得 37 . 4 2 1 12 Z Z D 。 (18)第十二步：比较 D 12 与 C ，这里 C D 12 。 (19)第十三步：根据上一步结果，聚类中心不发生合并。 (20)第十四步：不是最后一次迭代，不修改参数，迭代次数加 1（I=3） ，回到第二步。进行第 3次迭代运算。 (21)第二步到第六步：与前一次迭代计算的结果相同。 (22)第七步：不满足任何一种情况，继续执行第八步，进入分裂程序。 (23)第八步：计算 S 1 和 S 2 的标准差向量 T 12 , 11 1 和 T 22 , 21 2 。 2 11 1 , 10 2 11 71 2 11 61 2 11 51 2 11 41 11 5 1 z x z x z x z x z x 2 2 2 2 2 40 . 4 7 40 . 4 5 40 . 4 4 40 . 4 3 40 . 4 3 5 1 50 . 1 2 12 2 , 10 2 12 72 2 12 62 2 12 52 2 12 42 12 5 1 z x z x z x z x z x 2 2 2 2 2 00 . 6 4 00 . 6 7 00 . 6 6 00 . 6 6 00 . 6 7 5 1 10 . 1 2 21 1 9 2 21 81 2 21 31 2 21 21 2 21 11 21 5 1 z x z x z x z x z x 2 2 2 2 2 20 . 3 7 20 . 3 6 20 . 3 2 20 . 3 1 20 . 3 0 5 1 79 . 2 2 22 2 9 2 22 82 2 22 32 2 22 22 2 22 12 22 5 1 z x z x z x z x z x 2 2 2 2 2 80 . 1 3 80 . 1 3 80 . 1 2 80 . 1 1 80 . 1 0 5 1 17 . 1 即： T 1 10 . 1 , 50 . 1 和 T 2 17 . 1 , 79 . 2 。 (24)第九步： 5 . 1 max 1 ， 79 . 2 max 2 。 (25)第十步： S max 2 ，且满足 D D 2 和 ) 1 ( 2 2 N N ，Z 2 满足分裂条件。因 max 2 是 2 的第一个分量，故在 Z 2 的第一个分量方向上进行分裂，分裂系数 k选为 0.5，得 T T T max 1 2 71 . 2 , 20 . 5 71 . 2 , 79 . 2 5 . 0 80 . 3 71 . 2 , 5 . 0 80 . 3 Z T T T max 1 2 71 . 2 , 41 . 2 71 . 2 , 79 . 2 5 . 0 80 . 3 71 . 2 , 5 . 0 80 . 3 Z 令 2 2 Z Z ， 2 3 Z Z ，N C 加 1，迭代次数加 1（I=4） 。跳回到第二步，进行第 4次迭代运算。 (26)第二步：按最近邻规则对所有样本聚类。 15 . 13 71 . 2 0 41 . 2 0 | | 38 . 34 71 . 2 0 20 . 5 0 | | 45 . 40 10 . 5 0 80 . 3 0 | | 2 2 3 1 13 2 2 2 1 12 2 2 1 1 11 Z X Z X Z X D D D 3 1 13 S D X 最小 4.91 71 . 2 1 41 . 2 1 | | 20.56 71 . 2 1 5.2 1 | | 65 . 24 10 . 5 1 80 . 3 1 | | 2 2 3 2 3 2 2 2 2 2 22 2 2 1 2 21 Z X Z X Z X D D D 3 2 3 2 S D X 最小 22.73 71 . 2 4 41 . 2 7 | | 4.90 71 . 2 4 0 5.2 7 | | 11.45 10 . 5 4 80 . 3 7 | | 2 2 3 10 3 10 2 2 2 10 2 , 10 2 2 1 10 1 , 10 Z X Z X Z X ， D D D 2 10 2 , 10 S D X 最小 得到三个聚类分别为 7 6 5 4 1 , , , X X X X S ，N 1 =4 10 9 8 2 , , X X X S ，N 2 =3 3 2 1 3 , , X X X S ，N 3 =3 (27)第三步：因 N 1 ，N 2 ，N 3 都大于 N ，无聚类删除。 (28)第四步：修改聚类中心，得 T 7 6 5 4 1 50 . 6 , 75 . 3 26 15 4 1 4 1 X X X X Z T 10 9 8 2 33 . 3 , 67 . 6 10 20 3 1 3 1 X X X Z T 3 2 1 3 00 . 1 , 00 . 1 3 3 3 1 3 1 X X X Z (29)第五步：计算类内平均距离 1 D ， 2 D ， 2 D 得 1 7 1 6 1 5 1 4 1 4 1 Z X Z X Z X Z X D 2 2 2 2 50 . 6 6 75 . 3 3 50 . 6 7 75 . 3 3 4 1 50 . 6 7 75 . 3 5 50 . 6 6 75 . 3 4 2 2 2 2 93 . 0 2 10 2 9 2 8 2 3 1 Z X Z X Z X D 2 2 2 2 2 2 33 . 3 4 67 . 6 7 33 . 3 3 67 . 6 7 33 . 3 3 67 . 6 6 3 1 66 . 0 3 3 3 2 3 1 3 3 1 Z X Z X Z X D 2 2 2 2 2 2 1 2 1 2 1 1 1 1 1 0 1 0 3 1 94 . 0 (30)第六步：计算总体平均距离 D，得 2 1 3 2 1 3 3 4 10 1 1 j j j D D D D N N D 85 . 0 94 . 0 3 66 . 0 3 93 . 0 4 10 1 (31)第七步：因是偶数次迭代，符合第七步的第（3）条，进入第十一步。 (32)第十一步：计算所有聚类中心之间的距离。 31 . 4 33 . 3 50 . 6 67 . 6 75 . 3 2 2 2 1 12 Z Z D 15 . 6 1 50 . 6 1 75 . 3 2 2 3 1 13 Z Z D 13 . 6 1 33 . 3 1 67 . 6 2 2 3 2 23 Z Z D (33)第十二步：比较所有聚类中心间的距离与 C 的大小，这里均大于 C 。 (34)第十三步：根据上一步结果，聚类中心不发生合并。 (35)第十四步：不是最后一次迭代，不修改参数，迭代次数加 1（I=5） ，回到第二步。进行第 5次迭代运算。 (36)第二步到第六步：与前一次迭代计算的结果相同。 (37)第七步：此为最后一次迭代，置 0 C ，跳到第十一步。 (38)第十一步：计算所有聚类中心之间的距离，结果同前。 (39)第十二步：与前一次迭代结果相同。 (40)第十三步：没有合并发生。 (41)第十四步：是最后一次迭代，故算法结束。 聚类结果为： 7 6 5 4 1 , , , : X X X X ； 10 9 8 2 , , : X X X ； 3 2 1 3 , , : X X X 2.5 给出最大最小距离算法程序框图，编写程序，自选一组分别属于三类的二维 模式样本，并对它们进行聚类分析。 （略） 2.6 给出 K-均值算法的程序框图，编写程序，自选一组分别属于三类的三维模 式样本，并对它们进行聚类分析。 （略） 2.7 给出 ISODATA算法的程序框图，编写程序，利用题 2.1数据进行聚类分析， 在确认程序编写正确之后，选用附录 C数据进行聚类分析。 （略） 第 3章 判别函数及几何分类法 习题解答 3.1 在一个 10 类的模式识别问题中，有三类单独满足多类情况 1，其余的类别满足多类情况 2。问该模式识别问 题所需判别函数的最少数目为多少？ 答：满足多类情况 1的 3类问题，需要 3个判别函数， 满足多类情况 2的 7类问题，需要 21 2 ) 1 7 ( 7 个判别函数， 3+21=24 即共需 24 个判别函数。 3.2 一个三类问题，其判别函数为 4 2 2 1 1 x x d X ， 4 4 2 1 2 x x d X ， 3 1 3 x d X （1） 设这些函数是在多类情况 1条件下确定的，绘出判别界面及每一模式类别的区域。 （2） 设为多类情况 2，并使 X X 1 12 d d ， X X 2 13 d d ， X X 3 23 d d ，绘出判别界面及每一模式类别 区域。 （3） 设 X 1 d ， X 2 d 和 X 3 d 是在多类情况 3的条件下确定的，绘出其判别界面及每一模式类别的区域。 解： （1）多类情况 1时的判别界面及每一模式类别的区域如解图 3.1所示。 （2）多类情况 2时的判别界面及每一模式类别的区域如解图 3.2所示。 （3）多类情况 3： 三个判别界面方程为： 0 8 6 ) 4 4 ( ) 4 2 ( ) ( ) ( 2 2 1 2 1 2 1 x x x x x d d X X ，即 0 4 3 2 x 0 7 2 2 ) 3 ( ) 4 2 ( ) ( ) ( 2 1 1 2 1 3 1 x x x x x d d X X 0 1 4 2 ) 3 ( ) 4 4 ( ) ( ) ( 2 1 1 2 1 3 2 x x x x x d d X X 满足 0 ) ( ) ( 2 1 X d X d 且 0 ) ( ) ( 3 1 X d X d 的区域属于 1 类分布区域。 满足 0 ) ( ) ( 1 2 X d X d 且 0 ) ( ) ( 3 2 X d X d 的区域属于 2 类分布区域。 满足 0 ) ( ) ( 1 3 X d X d 且 0 ) ( ) ( 2 3 X d X d 的区域属于 3 类分布区域。 判别界面及各模式类的区域如解图 3.3所示。 0 ) ( 3 x d 1 2 1 3 2 x 1 x 0 ) ( 1 x d 0 ) ( 2 x d 2 2 3 4 0 -4 0 ) ( 23 x d 1 1 3 2 2 x 1 x 0 ) ( 12 x d 0 ) ( 13 x d 2 2 3 4 0 -4 解图 3.1 多类情况 1时的判别界面及各类别的区域 解图 3.2 多类情况 2时的判别界面及各类别的区域 3.3 有 5个良好分布的二维模式，问把它们任意线性地分为两组的概率是多少？ 解： n N n N C n N P n j j N N 1 1 1 2 ) , ( 0 1 1 2 0 2 4 1 4 0 4 4 1 5 5 1 6875 . 0 16 11 ) ( 2 1 2 ) 2 , 5 ( j j C C C C P 即所求概率为 0.6875。 3.4 设准则函数为 2 T T 2 | | ) ( | | 8 1 ) , , ( b b b J X W X W X X W 式中实数 b0，试导出两类模式的分类算法。 解：用梯度法求识别两类模式的判别函数权向量的递推式。 W X W b J J , , W X W X X W X W X b b b T T T 2 | | ) ( 2 | | 8 1 ) ( sgn | | ) ( | | 4 1 T T T 2 b b b X W X X X W X W X 其中， 0 , 1 0 , 1 sgn T T T b b b X W X W X W 若 若 当 0 T b X W 时， 0 J ； 当 0 T b X W 时， ) ( | | 2 ) ( 2 | | 4 1 T 2 T 2 b b J X W X X X X W X 。 由此得： J c k k W W 1 2 1 3 2 1 3 2 2 x 1 x 0 ) ( 2 1 X d X d 2 3 1 3 d d d d 0 ) ( 3 1 X d X d 0 ) ( 3 2 X d X d 3 2 1 2 d d d d 3 1 2 1 d d d d 0 3 4 1 4 解图 3.3 多类情况 3时的判别界面及各类别的区域 0 ), ( | | 0 , 0 T T 2 T b b c b k X W X W X X X W W 若 若 3.5 已知两类训练样本为 1 ： T T T T 0 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 2 ： T T T T 1 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 0 设 T 0 , 2 , 2 , 1 ) 1 ( W ，用感知器算法求解判别函数，并绘出判别界面。 解：感知器算法为： 0 , 0 , 1 T T i i i k c k k k k X W X W X W W W 若 若 ， c为正的校正增量。 首先，将所有样本写成增广向量的形式并编号，属于 2 的样本乘以(-1)： T 1 1 , 0 , 0 , 0 X ， T 2 1 , 0 , 0 , 1 X ， T 3 1 , 1 , 0 , 1 X ， T 4 1 , 0 , 1 , 1 X T 5 1 , 1 , 0 , 0 X ， T 6 1 , 1 , 1 , 0 X ， T 7 1 , 0 , 1 , 0 X ， T 8 1 , 1 , 1 , 1 X 取c =1开始迭代： 第一轮： 0 0 1 0 0 0 0 2 2 1 ) 1 ( 1 T X W ，故 T 1 1 , 2 , 2 , 1 ) 1 ( 2 X W W 0 0 1 0 0 1 1 2 2 1 ) 2 ( 2 T X W ，故 T 2 2 , 2 , 2 , 0 ) 2 ( 3 X W W 0 0 1 1 0 1 2 2 2 0 ) 3 ( 3 T X W ，故 T 3 3 , 1 , 2 , 1 ) 3 ( ) 4 ( X W W 0 2 1 0 1 1 3 1 2 1 ) 4 ( 4 T X W ，故 ) 4 ( ) 5 ( W W 0 2 1 1 0 0 3 1 2 1 ) 5 ( 5 T X W ，故 T 5 2 , 2 , 2 , 1 ) 5 ( ) 6 ( X W W ) 6 ( ) 7 ( 0 2 1 1 1 0 2 2 2 1 ) 6 ( 6 T W W X W ，故 T 7 7 T 1 , 2 , 3 , 1 ) 7 ( ) 8 ( 0 0 1 0 1 0 2 2 2 1 ) 7 ( X W W X W ，故 ) 8 ( ) 9 ( 0 3 1 1 1 1 1 2 3 1 ) 8 ( 8 T W W X W ，故 第二轮： ) 9 ( ) 10 ( 0 1 ) 9 ( 1 T W W X W ，故 ) 10 ( ) 11 ( 0 2 ) 10 ( 2 T W W X W ，故 T 3 3 T 2 , 1 , 3 , 2 ) 11 ( ) 12 ( 0 0 ) 11 ( X W W X W ，故 ) 12 ( ) 13 ( 0 1 ) 12 ( 4 T W W X W ，故 T 5 5 T 1 , 2 , 3 , 2 ) 13 ( ) 14 ( 0 1 ) 13 ( X W W X W ，故 ) 14 ( ) 15 ( 0 4 ) 14 ( 6 T W W X W ，故 ) 15 ( ) 16 ( 0 2 ) 15 ( 7 T W W X W ，故 ) 16 ( ) 17 ( 0 2 ) 16 ( 8 T W W X W ，故 第三轮： ) 17 ( ) 18 ( 0 1 ) 17 ( 1 T W W X W ，故 ) 18 ( ) 19 ( 0 3 ) 18 ( 2 T W W X W ，故 ) 19 ( ) 20 ( 0 1 ) 19 ( 3 T W W X W ，故 T 4 4 T 2 , 2 , 2 , 3 ) 20 ( ) 21 ( 0 0 ) 20 ( X W X W W ，故 T 5 5 T 1 , 3 , 2 , 3 ) 21 ( ) 22 ( 0 0 ) 21 ( X W W X W ，故 ) 22 ( ) 23 ( 0 4 ) 22 ( 6 T W W X W ，故 ) 23 ( ) 24 ( 0 1 ) 23 ( 7 T W W X W ，故 ) 24 ( ) 25 ( 0 1 ) 24 ( 8 T W W X W ，故 第四轮： ) 25 ( ) 26 ( 0 1 ) 25 ( 1 T W W X W ，故 ) 26 ( ) 27 ( 0 4 ) 26 ( 2 T W W X W ，故 ) 27 ( ) 28 ( 0 1 ) 27 ( 3 T W W X W ，故 ) 28 ( ) 29 ( 0 2 ) 28 ( 4 T W W X W ，故 ) 29 ( ) 30 ( 0 2 ) 29 ( 5 T W W X W ，故 ) 30 ( ) 31 ( 0 4 ) 30 ( 6 T W W X W ，故 ) 31 ( ) 32 ( 0 1 ) 31 ( 7 T W W X W ，故 ) 32 ( ) 33 ( 0 1 ) 32 ( 8 T W W X W ，故 该轮迭代分类结果全部正确，故解向量 T 1 , 3 , 2 , 3 W ，对应的判别函数为： 1 3 2 3 3 2 1 x x x d X 判别界面 0 X d 如解图3.4所示，图中虚线为判别界面与坐标面 2 1 ox x ， 3 1 ox x ， 3 2 ox x 的交线。 x 3.6 已知三类问题的训练样本为 1 ： T 1 , 1 ， 2 ： T 0 , 0 ， 3 ： T 1 , 1 试用多类感知器算法求解判别函数。 解：将训练样本写成增广形式： T 1 1 , 1 , 1 X ， T 2 1 , 0 , 0 X ， T 3 1 , 1 , 1 X 取初始值 T 3 2 1 0 , 0 , 0 1 1 1 W W W ，c=1，迭代过程如下： 第一次迭代，以 1 X 作为训练样本，计算得 0 1 1 1 T 1 1 X W d 0 1 1 1 T 2 2 X W d 0 1 1 1 T 3 3 X W d 因为 1 1 2 1 d d 且 1 1 3 1 d d 不成立，故 T 1 2 1 1 , 1 , 1 1 2 X W W T 1 2 2 1 , 1 , 1 1 2 X W W - T 1 3 3 1 , 1 , 1 1 2 X W W 第二次迭代，以 2 X 作为训练样本，计算得 1 2 2 2 T 1 1 X W d 1 2 2 2 T 2 2 X W d 1 2 2 2 T 3 3 X W d 因为 2 2 1 2 d d 且 2 2 3 2 d d 不成立，故 T 2 1 1 0 , 1 , 1 2 3 X W W T 2 2 2 0 , 1 , 1 2 3 X W W T 2 3 3 2 , 1 , 1 2 3 X W W 第三次迭代，以 3 X 作为训练样本，计算得 2 3 3 3 T 1 1 X W d 2 3 3 3 T 2 2 X W d 0 3 3 3 T 3 3 X W d 因为 3 3 1 3 d d ，但 3 3 2 3 d d 不成立，故 T 1 1 0 , 1 , 1 3 4 W W T 3 2 2 1 , 0 , 0 3 4 X W W 解图 3.4 判别界面 T 3 3 3 1 , 2 , 2 3 4 X W W 第四次迭代：以 1 X 作为训练样本，计算得： 2 4 4 1 T 1 1 X W d 1 4 4 1 T 2 2 X W d 5 4 4 1 T 3 3 X W d 因为 4 4 2 1 d d 且 4 4 3 1 d d ，故： 4 5 1 1 W W ， 4 5 2 2 W W ， 4 5 3 3 W W 第五次迭代：以 2 X 作为训练样本，计算得： 0 5 5 2 T 1 1 X W d 1 5 5 2 T 2 2 X W d 1 5 5 2 T 3 3 X W d 因为 5 5 1 2 d d 且 5 5 3 2 d d 不成立，故 T 2 1 1 1 , 1 , 1 5 6 X W W T 2 2 2 0 , 0 , 0 5 6 X W W T 2 3 3 2 , 2 , 2 5 6 X W W 第六次迭代：以 3 X 作为训练样本，计算得： 3 6 6 3 T 1 1 X W d ， 0 6 2 d ， 2 6 3 d 因为 6 6 1 3 d d 且 6 6 2 3 d d ，故： 6 7 1 1 W W ， 6 7 2 2 W W ， 6 7 3 3 W W 第七次迭代：以 1 X 作为训练样本，计算得： 1 7 7 1 T 1 1 X W d ， 0 7 2 d ， 6 7 3 d 因为 7 7 2 1 d d 且 7 7 3 1 d d ，故： 7 8 1 1 W W ， 7 8 2 2 W W ， 7 8 3 3 W W 第八次迭代：以 2 X 作为训练样本，计算得： 1 8 8 2 T 1 1 X W d 0 8 8 2 T 2 2
展开阅读全文