模式识别课件第四章34.6多类别问题

1、u4.6.1多类问题的基本概念多类问题的基本概念 u4.6.2 决策树简介决策树简介 假设有1，2，c类模式，分为三种情况进行讨论。 每一模式类与其它模式类之间可用单个判别平面分隔 每两类模式之间都可分别用判别平面分隔开来。 0)(wgtiixwxn存在c个判别函数 ，i=1,2,c，如果x属于i类，则)(jixx)ggij 每一模式类与其它模式类之间可用每一模式类与其它模式类之间可用单个判别平面分隔单个判别平面分隔 这种情况有c个判别函数，具有下面的性质 gi(x)0，则决策xi gi(x) 0，ng2(x) 0n g3(x) 0 g2(x)0 g3(x)0，则该模式x属于1类。 相应于1类

2、的区域由 直线x1+x2=0的正边 直线x1+x25=0和x2+1=0的负边来确定，如图4.15(b)所示。4.6.1多类问题的基本概念多类问题的基本概念 图4.15多类别问题的第一种情况(b)g1(x) = -x1+x2=0g3(x) = -x2+1=0g2(x) =x1+x2-5= 0 x1x2+2ir3类的判别区域g1(x)0 g2(x)02类的判别区域g1(x)0g3(x)0 g2(x)0g3(x)0irir不确定区不确定区不确定区不确定区4.6.1多类问题的基本概念多类问题的基本概念 例： 对x=(6,5)t确定类别，可把它代入三个判别函数 g1(x) = x1+x2 g2(x)=

3、x1+x25 g3(x) = x2+1中，得 g1(x) =10 g3(x) =4 0与g13(x) 0的x值所确定，而与g23(x)无关。 4.6.1多类问题的基本概念多类问题的基本概念 相应于上述三个判别函数所确定的区域示于图4.16(b)，在确定各类函数时，使用了条件gij(x) =gji(x)。 由于g12(x) =x1x2+5，于是g21(x) =x1+x25，g12(x)=0边界的正边即为g21(x) = 0边界的负边。4.6.1多类问题的基本概念多类问题的基本概念 图 4.16 多类别问题的第二种情况说明(b)x1x2g12(x) = -g21=-x1-x2+5=0g23(x)

4、= -g32=-x1+x2=0g13(x) = -g31=-x1+3=0+g32+g31+g13+g121类的判别区域g120 g1303类的判别区域g310 g320ir+g21+g232类的判别区域g210 g2304.6.1多类问题的基本概念多类问题的基本概念 举例 假定有一模式x = (4,3)t，把它代入上述判别函数得g12(x) =2 g21(x) =2g13(x) =1 g31(x) =1g23(x) =1 g32(x) =1 由于g3j (x) 0，j=1、2，且不存在不确定的条件，该模式属于3类。 4.6.1多类问题的基本概念多类问题的基本概念 这是第二种情况的特殊状态，因为

5、xwxwwxxxtijjijiij)()()()(tgggn式中wij=wiwj。0)(wgtiixwx存在c个判别函数 ，i=1,2,c，如果x属于i类，则)()(xxjiggij 4.6.1多类问题的基本概念多类问题的基本概念 可以证明，对所有ji， gi(x) gj(x)，gij(x) 0， 即如果各类别在第三种情况下的条件下可分，在第二种情况下也是可分的，反之却不然。 如图4.17(a)示例，其中c=3。 i类与j类之间的边界可由gi(x) = gj(x)或gi(x)gj(x) = 0确定。4.6.1多类问题的基本概念多类问题的基本概念 123x1x2图 4.17多类别问题的第三种情况

6、说明(a)g2(x)g3(x)=0g1(x)g2(x)=0g1(x)g3(x)=04.6.1多类问题的基本概念多类问题的基本概念 对于1类的模式，要求g1(x) g2(x)和g1(x) g3(x)，就是说，该类模式处于g1(x)g2(x) = 0g1(x)g3(x) = 0直线的正边。 一般的形式i类模式处于gi(x)gj(x) = 0，j =1,2,c，ji的正边。4.6.1多类问题的基本概念多类问题的基本概念 边界的确定 假设g1(x) =x1+x2g2(x) =x1+x21g3(x) =x2 三类之间的边界可由g1(x)g2(x)=2x1+1=0g1(x)g3(x)=x1+2x2=0g2

7、(x)g3(x)=x1+2x21=0确定。4.6.1多类问题的基本概念多类问题的基本概念 图 4.17多类别问题的第三种情况说明(b)g1g2=2x1+1=0g1g3=x1+2x2=0g2g3=x1+2x21=0 x1x22类的判别函数g2(x)g1(x) g2(x)g3(x)3类的判别函数g3(x)g1(x) g3(x)g2(x)1类的判别函数g1(x)g2(x) g1(x)g3(x)4.6.1多类问题的基本概念多类问题的基本概念 举例举例 在第三种情况的条件下，除了边界外没有不确定区域。 假定有一模式x=(1,1)t，将它代入上述的判别函数中，得g1(x)=0 g2(x)=1 g3(x)=

8、1 因为g2(x) gj(x)，j=1、3，所以模式x=(1,1)t属于2类。4.6.1多类问题的基本概念多类问题的基本概念 如果某几类模式可由以上三种情况中任一种线性判别函数来进行分类，则该几类模式属线性可分。 一般地，可以定义c个判别函数，i=1，2，c0)(itiiwgxwxn如果对于一切ji，存在gi(x) gj(x)，则把x归于i类；如果gi(x) = gj(x)，则拒绝决策。这样的分类器称之为线性分类器，它把特征空间分为c个决策域r1，r2，rc，当x在ri中时，gi(x)具有最大值。4.6.1多类问题的基本概念多类问题的基本概念 如果ri和rj相邻，则它们的分界面就是超平面hij

9、的一部分，其定义为 或 (wiwj)tx+(wi0wj0) = 0 由此可知，wiwj是hij的法向量，从x到hij的代数距离为 gi(x) = gj(x)|)()(jijiggrwwxx4.6.1多类问题的基本概念多类问题的基本概念 对线性分类器来说，重要的是权向量的差而不是权向量本身。这时应该有c(c1)/2个超平面。在实际中，出现在分界面上的超平面的个数往往少于c(c1)/2。 注意：线性分类器的决策面是凸的，决策域是单连通的。 前面关于两类问题的准则函数和算法，一般都可以推广到多类情况。 4.6.1多类问题的基本概念多类问题的基本概念 例：给出一组三类问题的判别函数：例：给出一组三类问

10、题的判别函数： g1(x) =-x1，g2(x) = x1+ x2-1，g3(x) = x1-x2-1 假设每一模式类与其它模式类之间可用单个判别平面分隔； 每两类模式之间都可分别用判别平面分隔开，且g12(x) = g1(x)，g13(x) = g2(x)，g23(x) = g3(x)n存在c个判别函数， ，i =1，2，c，对 ，有gi(x)gj(x)，则xi。xwxtiig)(ij 4.6.1多类问题的基本概念多类问题的基本概念 对于以上三种情况，分别作出每类的判别边界和区域。解：此时，有c = 3个判别函数，其具有下面的性质：，其它，0, 2 , 10)(cigitixxwx三个判别边

11、界分别为：x1 = 0 x2轴 x1+x21 = 0 x1x21 = 04.6.1多类问题的基本概念多类问题的基本概念 02-22-2x1x2g1(x) = x1 = 0g2(x) = x1+x21 = 0g3(x) = x1x21= 0+-12131-1iriririririr图 4.18-1判别区域如图4.18所示。4.6.1多类问题的基本概念多类问题的基本概念 对c类别，有 个判别函数，且gij(x)0，则xi，且gij(x)=gji(x)。2) 1( ccij 其判别区域如图4.19所示。此时 g12(x) = g1(x) = x1， g13(x) = g2(x) = x1+ x21，

12、 g23(x) = g3(x) = x1x214.6.1多类问题的基本概念多类问题的基本概念 0-22-2x1x2g23(x) = x1x21= 0g13(x) = x1+x21= 0g12(x) = x1 = 0-11213-121ir图 4.194.6.1多类问题的基本概念多类问题的基本概念 此时 ，gij(x) = gigjcigtii, 2 , 1)(，xwxijiijggxxx，则，)()(得判别平面g12(x) = g1(x)g2(x) = 2x1x2+1 = 0g13(x) = g1(x)g3(x) = 2x1+x2+1 = 0g23(x) = g2(x)g3(x) = 2x2

13、= 0判别区域如图4.20所示。4.6.1多类问题的基本概念多类问题的基本概念 -1-22-2x1x223g2(x)g3(x)g1(x)g3(x)g1(x)g2(x)101/21-11图 4.204.6.1多类问题的基本概念多类问题的基本概念 树分类器 决策树及决策表 在多类判别中，经常遇到这样的问题：要保证得到的分类器性能足够好就必须使用大量的特征。要求在有大量样本的训练集上进行分类器设计。而这个数目比我们能够得到的样本数大很多。而且，特征集中对于某一类的判别能力很强的特征可能对于其他类的判别能力却很弱。树分类器 为了克服上述困难，提出了一种“分隔解决(divide and conquer)

14、”的多层分类器方法，即决策树方法。对于某个位置样本，通过一系列的决策函数最终将它判为某一个具体的类别。4.6.2 决策树简介决策树简介树分类器 在树分类器的每一步中，需要解决的问题都只涉及一个数目小得多的特征集。 对于多类判别问题，很难保证每个类别的分布都是正态的（甚至很难保证每个分布式对称的）并且具有相似的协方差矩阵。但利用层次化分析的方法就能期望上述条件被近似满足，这样，在每一步中得到的分类器都可以看成是最优的。4.6.2 决策树简介决策树简介树分类器 图中给出一个简单决策树的例子。分类水平l1上：类别数为4，=1,2,3,4(l1)=3,(l2)分类水平l2上：具体决定x为(l2)中的哪

15、个具体类别， (l2) =1,2, 4(l1)3(l2)124l1l2x4.6.2 决策树简介决策树简介决策树的性能 依据kulkarni(1978)所做的工作进行研究。 假设为了达到某一个结点，沿着树的一个路径所使用的特征是相互独立的，这样对于类别k的概率密度为：djkjkxpp1)|()|(xxj表示沿着决策树的一条路径，是为判别k类所使用的相互独立的某个特征向量中的分量。4.6.2 决策树简介决策树简介决策树的性能 设第k类的正确分类概率为pc(k)，用于分类的特征之间是相互独立的，则pc(k|lj)表示在通向k的一条路径(t(k)上每个搜索过的结点上正确分类的概率。根据先验概率对这些p

16、c(k)计算加权平均，得到决策树的正确识别率：)()|()(kitlikckclpp4.6.2 决策树简介决策树简介决策树的性能 同时，对于每一个结点li，对从它能达到的那些类别计算平均值，得到结点上的正确识别率：)(1)|()()(kitlikcckkclpptp)()()()|()()(iilkkikclkkicplpplp4.6.2 决策树简介决策树简介决策树的性能 上面这些公式表明，在每一个结点上的正确识别率是一个线性函数，而公式)(1)|()()(kitlikcckkclpptpn表示的总体正确识别率是一个非线性函数。因此，在决策树的每一级水平上使决策性能最优并不能保证整个决策树的总

17、体性能达到最优。4.6.2 决策树简介决策树简介决策树的性能 如何确定一个总体最优的决策树是另外一个复杂的问题。因此，设计一个最优决策树并不是一件容易的工作，通常情况下，它需要搜索树的整个结构空间以及所有可能的特征组合方式。 一些搜索技巧己经被应用到这个领域中，例如动态搜索法和分枝定界法等等。4.6.2 决策树简介决策树简介决策树的性能 最优化各个结点的分类性能并不能保证决策树整体分类性能最优。 在实际应用中，般采用一种“手动”的方法进行决策树设计，它是根据各个特征的可分性属性来选择决策树的结构以及各个结点的分类方式。)()|()(kitlikckclppn从公式中 可以看到，为了得到一个比不

18、进行层次化判别的分类器性能更好的结果，必须保证每一个结点处的分类性能都相当好。 4.6.2 决策树简介决策树简介决策树的性能 例如，对于前面图中所示的决策树，两个概率pc(l2)|l1) 和pc(2|l2)都具有相同的值0.94，那么有pc(2)=0.942=0.88。 而对于一个更大一些的树，值0.94将会自乘4次从而使得错误率达到22%!因此，沿着一条路径，错误率会很快变坏。 4.6.2 决策树简介决策树简介决策树的例子 胸部组织(breast tissue)数据集(数据为刚刚切开的胸部组织测量得到的电阻)上应用决策树的例子。 数据集一共被分成了6个类别，分别记为car(癌症状，carci

19、noma)，fad(纤维性瘤，fibro-adenoma)，gla(腺状，glandular)，mas(乳脉病，mastopathy)，con(连接性，connective)以及adi(脂肪性，adipose)。 这些数据的一些特征的分布和正态分布模型符合得很好，例如i0，areada以及ipmax。4.6.2 决策树简介决策树简介决策树的例子 进行一个kruskal-wallis分析，可以明显地看出，所有的特征都具有判别能力。而且实际上想要将gla，fad和mas分开是不可能的。由于这个数据集上各个类的维数比率很小(例如对于类别con仅仅有14个样本)，这就表明必须使用决策树方法，因为它可以

20、将一些类聚集起来并且可以在每一个结点上极大地减少所用特征的数目。4.6.2 决策树简介决策树简介决策树的性能 利用i0和pa500作为分类特征后，我们有必要看一下图4-39中所示的分布图。4.6.2 决策树简介决策树简介决策树的性能 从直观上看，形成了两个大的聚类，一个是con，adi，另一个是mas，gla，fad，car。利用因子分析法也可以看出，一个因子和特征pa500密切联系，而另一个因子和特征i0密切联系。 数据的结构以及对于特征分析的图像使人们首先将数据集分成上面提到的这两个大类。单独便用特征i0并设定分类阈值为i0=600时得到了最好的分类结果，错误率为0。4.6.2 决策树简介

21、决策树简介决策树的性能 在第二步判别中，从医学的角度得到最有利的分类指导：类别car以及(mas，gla，fad)。n利用判别分析法可知，利用这种方法在整个训练集上得到的错误率大约为8%，所用的特征为aerada以及ipmax。4.6.2 决策树简介决策树简介决策树的性能 应用样本划分法(对半的形式，即一半数目的样本归入训练集，一半数目的样本归入测试集)随机地进行两次错误率估计，在测试集上得到的平均错误率为8.6%，和训练集上得到的错误率估计值很相近。 在第二级水平上，对于con类和adi类也利用特征i0进行判别，结果对于adi类错误率为0，而对于con类错误率为14%。4.6.2 决策树简介

22、决策树简介决策树的性能 利用上面这些结果就可以建立一棵如图4-41所示的决策树。n在决策树的每一级水平上都使用了一个决策函数，具体如图4-41中所示，作为必须满足的一个决策规则。 yesno4.6.2 决策树简介决策树简介决策树的性能 由于在每一级水平上都只使用了少量数目的特征，对于第一级和第二级来讲分别是l和2，在两个水平上都得到了一个比较高的维数比率，这样得到的置信区间为95%的错误率估计的可信度就比较高 (对于第一级水平低于2%而对于car和mas，gla，fad水平大约在3%)。4.6.2 决策树简介决策树简介分类器 前面对于胸部组织数据集采用的决策树是一个二叉树：在每一个结点上，所作

23、的是一个“二中选一”的决策。这种二叉树是最普遍的一种决策树类型，即在每一个结点上对于单个的特征得到一个线性判别，这个判别平行于特征轴，并且对于专家来讲很容易解释其具体含义。它允许分类特征任意组合，通过对一个问题 这个样本是否属于一个类别集的回答结果yes或者no在每个结点上将样本分类。4.6.2 决策树简介决策树简介分类器 例如，这种类型的决策树经常被应用到医学领域，经常是对一个给定的人群统计各个影响健康的因素的单独作用，然后据此建立一棵树。 设计这种决策树可以自动地采用很多方式，关键在于每个结点上采用什么样的“分离规则(split criterion)”，以及为了找到最优的组合而采用的搜索算

24、法。4.6.2 决策树简介决策树简介分类器 一个“分离规则”具有如下形式： d(x) 式中，d(x)是对于特征向量x的决策函数，而是一个阈值。 通常使用的都是线性决策函数。在很多应用领域里，使用的分离规则是基于单个特征的表达式(于是被称为单变量分离)。 4.6.2 决策树简介决策树简介数据挖掘中的统计分类器 在一个大的机构(例如企业、医院、信用卡公司等)应用某些数据库技术时存在着一个趋势，它包含着“数据仓库”的概念，其中一个经典的数据搜索技术被称为“数据挖掘”。 一个数据仓库就是一个包含着很多数据表的数据库系统，数据表中的内容会周期性的更新，它们包含着很多细节的历史信息，支持对于更高级数据的描

25、述，还有很多的总结性工具，比如元数据等，也就是说，一些对于系统元素(例如名称、定义、结构等)的定位和描述的数据。4.6.2 决策树简介决策树简介数据挖掘中的统计分类器 数据挖掘技巧被用来从数据仓库中提取相关的信息，它被应用于各种不同的领域，例如： 工程领域，例如设备故障预测，网络上的搜索引擎等。 经济领域，例如对于某个投资的利润预测，检测一个消费线，评价一个贷款风险等。 生物及医学领域，例如染色体中的蛋白质序列匹配，对于怀孕的几率的估计等。4.6.2 决策树简介决策树简介数据挖掘中的统计分类器 这些技术都用到了模式识别中的一些方法，例如聚类分析、统计分类以及神经网络等。 此外还应用了人工智能领域中的一些方法，例如知识表达、因果模型以及规则演绎等。4.6.2 决策树简介决策树简介数据挖掘中的统计分类器 在应用模式识别中的一些技巧进行数据挖掘时需要考虑下面这几个重要的问题： 需要在一个大的数据库上进行，并