6.线性支持向量机（线性SVM① 总结：两类问题的线性判别函数 口总结 名称 准则 算法 ■目标：求对特征空间划分的最优超平面； Fisher wSW Jr(w)= w*=S(m1-m2) ■核心思想：最大化分类边界距离； S+5:wS,w ■支持向量：SVM的训练结果，在SVM分类决策 感知器 J(a)=∑(-a'y) ak+)=a(k)+r∑y 中起决定性作用。 veYe 口计算的复杂性取决于支持向量的数目，而不是样 最小错 本空间的维数，这在某种意义上避免了“维数灾难” 分样本 J(a)=(Ya-b)-Ya-b 共轭梯度法 口具有较好的“鲁棒”性：增、删非支持向量样本对模 MSE J,(a)=Ya-b a'=Y'b 型没有彩响；支持向量样本集具有一定的鲁棒性。 ■可保证解的全局最优性，不存在陷入局部极小解 SVM f+c() 二次规划 的问题。 st.constraints 2 7.多类问题（简介) 7.多类问题（简介) 口思路一：两类别问题可以推广到多类别问题 口思路二：多类线性判别函数(Linear Machine) ■0：/@法：将c类别问题化为(c-1)个两类（第i ■将特征空间确实划分为c个决策域，共有c个判 类与所有非类)问题，按两类问题确定其判别函 别函数 数与决策面方程。 8(x)=w,x+0o,i=1,,C ■ω：/0；法：将c类中的每两类别单独设计其线 ■决策规则： 性判别函数，总共有c(c1)2个线性判别函数. j=argmax g(x),i=1,....c; 阴影区域中的 ■决策域的边界由相邻决策域的判别函数共同决 点无法判定其 类别 定，此时应有g)厂gx: ■线性分类器的决策面是凸的，决策区域单连通： 非 ■多类分类器的分界面是分段线性的： 24 7.多类问题（简介） 7.多类问题（简介） 口多类线性决策面图例 口决策树：一种多级分类器，它采用分级的形式， 综合用多个决策规则，逐步把复杂的多类别分类 91>9 92>91 R 问题转化为若干个简单的分类问题来解决。 root Colo? level0 91>93 R R level I 9391 92>93 93>92 R19 6. 线性支持向量机 (线性SVM)  总结  目标：求对特征空间划分的最优超平面；  核心思想：最大化分类边界距离；  支持向量：SVM 的训练结果，在 SVM 分类决策 中起决定性作用。 计算的复杂性取决于支持向量的数目，而不是样 本空间的维数，这在某种意义上避免了“维数灾难”。 具有较好的“鲁棒”性：增、删非支持向量样本对模 型没有影响；支持向量样本集具有一定的鲁棒性。  可保证解的全局最优性，不存在陷入局部极小解 的问题。 20 总结：两类问题的线性判别函数 MSE 共轭梯度法 最小错 分样本 SVM 二次规划 感知器 Fisher 名称 准则 算法 1 2 ( ) T b b F T w S S J S S S    w w w w w    1 1 2 ( ) w S  w mm   () ( ) k T P Y J    y a a y ( 1) ( ) k k Y k kr    y a a y 2 ( ) s J Y a ab   * Y  a b  J () ( ) a Ya b Ya b      2 1 1 2 . . constraints k N i i C s t  w   21 7. 多类问题（简介）  思路一：两类别问题可以推广到多类别问题  ωi/~ωi法：将 c 类别问题化为 (c-1) 个两类（第i 类与所有非i类）问题，按两类问题确定其判别函 数与决策面方程。  ωi/ωj 法：将 c 类中的每两类别单独设计其线 性判别函数，总共有 c(c-1)/2 个线性判别函数。 R1 R3 ω1 R2 非 ω1 非ω2 ω2 R1 R3 R2 ω1 ω2 ω1 ω3 ω3 ω2 阴影区域中的 点无法判定其 类别 22 7. 多类问题（简介）  思路二：多类线性判别函数 (Linear Machine)  将特征空间确实划分为 c 个决策域，共有 c 个判 别函数  决策规则：  决策域的边界由相邻决策域的判别函数共同决 定，此时应有 gi (x)=gj (x)；  线性分类器的决策面是凸的，决策区域单连通；  多类分类器的分界面是分段线性的； 0 ( ) , 1,..., ; T i ii g ic x wx    argmax ( ), 1,..., ; i i j gi c   x 23 7. 多类问题（简介）  多类线性决策面图例 R1 R3 R2 g1>g2 g1>g3 g3>g1 g3>g2 g2>g3 g2>g1 R1 R3 R2 R5 R4 24 7. 多类问题（简介）  决策树：一种多级分类器，它采用分级的形式， 综合用多个决策规则，逐步把复杂的多类别分类 问题转化为若干个简单的分类问题来解决