模式識別第四章（3）4.6多類別問題

4.6多類別問題4.6.1多類問題的基本概念

4.6.2決策樹簡介

整理ppt4.6.1多類問題的基本概念假設有ω1，ω2，…，ωc類模式，分為三種情況進行討論。每一模式類與其它模式類之間可用單個判別平面分隔每兩類模式之間都可分別用判別平面分隔開來。存在c個判別函數(shù)，i=1,2,…,c，如果x屬于ωi類，則整理ppt⒈每一模式類與其它模式類之間可用單個判別平面分隔

這種情況有c個判別函數(shù)，具有下面的性質gi(x)>0，則決策x∈ωigi(x)<0，其它i=1，2，…，c假如模式類別的分布如圖4.15(a)所示，每一類別可用單個判別邊界與其余類別劃分開。4.6.1多類問題的基本概念

整理pptx1x2ω1ω2ω3圖4.15多類別問題的第一種情況(a)如果一模式x屬于ω1，g1(x)>0，g2(x)

<0g3(x)<0，ω1類與其它類之間的邊界由g1(x)=0確定。g1(x)=0+－g3(x)=0+－g2(x)=0+－4.6.1多類問題的基本概念

整理ppt判別邊界假設圖4.15(a)的判別函數(shù)為g1(x)=－x1+x2g2(x)=x1+x2－5g3(x)=－x2+1則三個判別邊界為－x1+x2=0x1+x2－5=0－x2+1=04.6.1多類問題的基本概念

整理ppt對于任一模式x，如果g1(x)>0g2(x)<0g3(x)<0，則該模式x屬于ω1類。相應于ω1類的區(qū)域由直線－x1+x2=0的正邊直線x1+x2－5=0和－x2+1=0的負邊來確定，如圖4.15(b)所示。4.6.1多類問題的基本概念

整理ppt圖4.15多類別問題的第一種情況(b)g1(x)=-x1+x2=0g3(x)=-x2+1=0g2(x)=x1+x2-5=0x1x2+－+－+－ω2IRω3類的判別區(qū)域g1(x)<0g2(x)<0g3(x)>0ω2類的判別區(qū)域g1(x)<0g2(x)>0g3(x)<0IRω1類的判別區(qū)域g1(x)>0g2(x)<0g3(x)<0IRIR不確定區(qū)不確定區(qū)不確定區(qū)不確定區(qū)4.6.1多類問題的基本概念

整理ppt例：對x=(6,5)T確定類別，可把它代入三個判別函數(shù)g1(x)=－x1+x2g2(x)=x1+x2－5g3(x)=－x2+1中，得

g1(x)=－1<0g2(x)=6>0g3(x)=－4<0所以模式x=(6,5)T屬于ω2類。4.6.1多類問題的基本概念

整理ppt⒉每兩類模式之間都可分別用判別平面分隔開來

對c類模式來說，有c(c－1)/2(每次從c類中取兩類的組合)個判別平面。判別函數(shù)的形式為gij(x)，如果x屬于ωi類，則而且這些函數(shù)有gij(x)=－gji(x)的性質。例如圖4.16(a)示出符合第二種情況的三類可分的模式。4.6.1多類問題的基本概念

整理pptω1ω2ω3x1x2圖4.16多類別問題的第二種情況說明(a)g23(x)=0+－g12(x)=0+－g13(x)=0+－4.6.1多類問題的基本概念

整理ppt假設判別函數(shù)為g12(x)=－x1－x2+5g13(x)=－x1+3g23(x)=－x1+x2令這些判別函數(shù)為零，可確定各判別邊界。例如ω1類的區(qū)域是由g12(x)>0與g13(x)>0的x值所確定，而與g23(x)無關。4.6.1多類問題的基本概念

整理ppt相應于上述三個判別函數(shù)所確定的區(qū)域示于圖4.16(b)，在確定各類函數(shù)時，使用了條件gij(x)=－gji(x)。由于g12(x)=－x1－x2+5，于是g21(x)=x1+x2－5，g12(x)=0邊界的正邊即為g21(x)=0邊界的負邊。4.6.1多類問題的基本概念

整理ppt圖4.16多類別問題的第二種情況說明(b)x1x2g12(x)=-g21=-x1-x2+5=0g23(x)=-g32=-x1+x2=0g13(x)=-g31=-x1+3=0+g32+g31+g13+g12ω1類的判別區(qū)域g12>0g13>0ω3類的判別區(qū)域g31>0g32>0IR+g21+g23ω2類的判別區(qū)域g21>0g23>04.6.1多類問題的基本概念

整理ppt舉例假定有一模式x

=(4,3)T，把它代入上述判別函數(shù)得g12(x)=－2g21(x)=2g13(x)=－1g31(x)=1g23(x)=－1g32(x)=1由于g3j(x)>0，j=1、2，且不存在不確定的條件，該模式屬于ω3類。4.6.1多類問題的基本概念

整理ppt這是第二種情況的特殊狀態(tài)，因為式中wij=wi－wj。存在c個判別函數(shù)，i=1,2,…,c，如果x屬于ωi類，則⒊4.6.1多類問題的基本概念

整理ppt可以證明，對所有j≠i，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多類問題的基本概念

整理pptω1ω2ω3x1x2圖4.17多類別問題的第三種情況說明(a)g2(x)－g3(x)=0g1(x)－g2(x)=0g1(x)－g3(x)=04.6.1多類問題的基本概念

整理ppt對于ω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，j≠i的正邊。4.6.1多類問題的基本概念

整理ppt邊界的確定假設g1(x)=－x1+x2g2(x)=x1+x2－1g3(x)=－x2三類之間的邊界可由g1(x)－g2(x)=－2x1+1=0g1(x)－g3(x)=－x1+2x2=0g2(x)－g3(x)=x1+2x2－1=0確定。4.6.1多類問題的基本概念

整理ppt圖4.17多類別問題的第三種情況說明(b)g1－g2=－2x1+1=0g1－g3=－x1+2x2=0g2－g3=x1+2x2－1=0x1x2ω2類的判別函數(shù)g2(x)>g1(x)g2(x)>g3(x)ω3類的判別函數(shù)g3(x)>g1(x)g3(x)>g2(x)ω1類的判別函數(shù)g1(x)>g2(x)g1(x)>g3(x)4.6.1多類問題的基本概念

整理ppt舉例在第三種情況的條件下，除了邊界外沒有不確定區(qū)域。假定有一模式x=(1,1)T，將它代入上述的判別函數(shù)中，得g1(x)=0g2(x)=1g3(x)=－1因為g2(x)>gj(x)，j=1、3，所以模式x=(1,1)T屬于ω2類。4.6.1多類問題的基本概念

整理ppt如果某幾類模式可由以上三種情況中任一種線性判別函數(shù)來進行分類，則該幾類模式屬線性可分。一般地，可以定義c個判別函數(shù)，i=1，2，…，c如果對于一切j≠i，存在gi(x)>gj(x)，則把x歸于ωi類；如果gi(x)=gj(x)，則拒絕決策。這樣的分類器稱之為線性分類器，它把特征空間分為c個決策域R1，R2，…，Rc，當x在Ri中時，gi(x)具有最大值。4.6.1多類問題的基本概念

整理ppt如果Ri和Rj相鄰，則它們的分界面就是超平面Hij的一部分，其定義為或(wi－wj)Tx+(wi0－wj0)=0由此可知，wi－wj是Hij的法向量，從x到Hij的代數(shù)距離為

gi(x)=gj(x)4.6.1多類問題的基本概念

整理ppt對線性分類器來說，重要的是權向量的差而不是權向量本身。這時應該有c(c－1)/2個超平面。在實際中，出現(xiàn)在分界面上的超平面的個數(shù)往往少于c(c－1)/2。注意：線性分類器的決策面是凸的，決策域是單連通的。

前面關于兩類問題的準則函數(shù)和算法，一般都可以推廣到多類情況。

4.6.1多類問題的基本概念

整理ppt例：給出一組三類問題的判別函數(shù)：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)③存在c個判別函數(shù)，，i=1，2，…，c，對，有gi(x)＞gj(x)，則x∈ωi。4.6.1多類問題的基本概念

整理ppt對于以上三種情況，分別作出每類的判別邊界和區(qū)域。解：①此時，有c=3個判別函數(shù)，其具有下面的性質：三個判別邊界分別為：－x1=0→x2軸

x1+x2－1=0x1－x2－1=04.6.1多類問題的基本概念

整理ppt02-22-2x1x2g1(x)=－x1=0g2(x)=x1+x2－1

=0g3(x)=x1－x2－1=0+++---ω1ω21ω31-1IRIRIRIRIRIR圖4.18-1判別區(qū)域如圖4.18所示。4.6.1多類問題的基本概念

整理ppt②對c類別，有個判別函數(shù)，且gij(x)>0，，則x∈ωi，且gij(x)=gji(x)。其判別區(qū)域如圖4.19所示。此時

g12(x)=g1(x)=－x1，g13(x)=g2(x)=x1+x2－1，g23(x)=g3(x)=x1－x2－14.6.1多類問題的基本概念

整理ppt0-22-2x1x2g23(x)=x1－x2－1=0g13(x)=x1+x2－1=0g12(x)=－x1=0-1ω1ω21ω3-121IR圖4.194.6.1多類問題的基本概念

整理ppt③此時，gij(x)=gi－gj得判別平面g12(x)=g1(x)－g2(x)=－2x1－x2+1=0g13(x)=g1(x)－g3(x)=－2x1+x2+1=0g23(x)=g2(x)－g3(x)=2x2=0判別區(qū)域如圖4.20所示。4.6.1多類問題的基本概念

整理ppt-1-22-2x1x2ω2ω3g2(x)－g3(x)g1(x)－g3(x)g1(x)－g2(x)ω101/21-11圖4.204.6.1多類問題的基本概念

整理ppt樹分類器決策樹及決策表在多類判別中，經常遇到這樣的問題：要保證得到的分類器性能足夠好就必須使用大量的特征。要求在有大量樣本的訓練集上進行分類器設計。而這個數(shù)目比我們能夠得到的樣本數(shù)大很多。而且，特征集中對于某一類的判別能力很強的特征可能對于其他類的判別能力卻很弱。4.6.2決策樹簡介整理ppt樹分類器為了克服上述困難，提出了一種“分隔解決(divideandconquer)”的多層分類器方法，即決策樹方法。對于某個位置樣本，通過一系列的決策函數(shù)最終將它判為某一個具體的類別。4.6.2決策樹簡介

整理ppt樹分類器在樹分類器的每一步中，需要解決的問題都只涉及一個數(shù)目小得多的特征集。對于多類判別問題，很難保證每個類別的分布都是正態(tài)的（甚至很難保證每個分布式對稱的）并且具有相似的協(xié)方差矩陣。但利用層次化分析的方法就能期望上述條件被近似滿足，這樣，在每一步中得到的分類器都可以看成是最優(yōu)的。4.6.2決策樹簡介

整理ppt樹分類器圖中給出一個簡單決策樹的例子。分類水平l1上：類別數(shù)為4，Ω={ω1,ω2,ω3,ω4}Ω(l1)={ω3,Ω(l2)}分類水平l2上：具體決定x為Ω(l2)中的哪個具體類別，Ω(l2)={ω1,ω2,ω4}Ω(l1)ω3Ω(l2)ω1ω2ω4l1l2x4.6.2決策樹簡介

整理ppt決策樹的性能依據(jù)Kulkarni(1978)所做的工作進行研究。假設為了達到某一個結點，沿著樹的一個路徑所使用的特征是相互獨立的，這樣對于類別ωk的概率密度為：xj表示沿著決策樹的一條路徑，是為判別ωk類所使用的相互獨立的某個特征向量中的分量。4.6.2決策樹簡介

整理ppt決策樹的性能設第ωk類的正確分類概率為Pc(ωk)，用于分類的特征之間是相互獨立的，則Pc(ωk|lj)表示在通向ωk的一條路徑(T(ωk))上每個搜索過的結點上正確分類的概率。根據(jù)先驗概率對這些Pc(ωk)計算加權平均，得到決策樹的正確識別率：4.6.2決策樹簡介

整理ppt決策樹的性能同時，對于每一個結點li，對從它能達到的那些類別計算平均值，得到結點上的正確識別率：4.6.2決策樹簡介

整理ppt決策樹的性能上面這些公式表明，在每一個結點上的正確識別率是一個線性函數(shù)，而公式表示的總體正確識別率是一個非線性函數(shù)。因此，在決策樹的每一級水平上使決策性能最優(yōu)并不能保證整個決策樹的總體性能達到最優(yōu)。4.6.2決策樹簡介

整理ppt決策樹的性能如何確定一個總體最優(yōu)的決策樹是另外一個復雜的問題。因此，設計一個最優(yōu)決策樹并不是一件容易的工作，通常情況下，它需要搜索樹的整個結構空間以及所有可能的特征組合方式。一些搜索技巧己經被應用到這個領域中，例如動態(tài)搜索法和分枝定界法等等。4.6.2決策樹簡介

整理ppt決策樹的性能最優(yōu)化各個結點的分類性能并不能保證決策樹整體分類性能最優(yōu)。在實際應用中，般采用一種“手動”的方法進行決策樹設計，它是根據(jù)各個特征的可分性屬性來選擇決策樹的結構以及各個結點的分類方式。從公式中可以看到，為了得到一個比不進行層次化判別的分類器性能更好的結果，必須保證每一個結點處的分類性能都相當好。4.6.2決策樹簡介

整理ppt決策樹的性能例如，對于前面圖中所示的決策樹，兩個概率Pc(Ω(l2)|l1)和Pc(ω2|l2)都具有相同的值0.94，那么有Pc(ω2)=0.942=0.88。而對于一個更大一些的樹，值0.94將會自乘4次從而使得錯誤率達到22%!因此，沿著一條路徑，錯誤率會很快變壞。

4.6.2決策樹簡介

整理ppt決策樹的例子胸部組織(BreastTissue)數(shù)據(jù)集(數(shù)據(jù)為剛剛切開的胸部組織測量得到的電阻)上應用決策樹的例子。數(shù)據(jù)集一共被分成了6個類別，分別記為car(癌癥狀，carcinoma)，fad(纖維性瘤，fibro-adenoma)，gla(腺狀，glandular)，mas(乳脈病，mastopathy)，con(連接性，connective)以及adi(脂肪性，adipose)。這些數(shù)據(jù)的一些特征的分布和正態(tài)分布模型符合得很好，例如I0，AREA＿DA以及IPMAX。4.6.2決策樹簡介

整理ppt決策樹的例子進行一個Kruskal-Wallis分析，可以明顯地看出，所有的特征都具有判別能力。而且實際上想要將gla，fad和mas分開是不可能的。由于這個數(shù)據(jù)集上各個類的維數(shù)比率很小(例如對于類別con僅僅有14個樣本)，這就表明必須使用決策樹方法，因為它可以將一些類聚集起來并且可以在每一個結點上極大地減少所用特征的數(shù)目。4.6.2決策樹簡介

整理ppt決策樹的性能利用I0和PA500作為分類特征后，我們有必要看一下圖4-39中所示的分布圖。4.6.2決策樹簡介

整理ppt決策樹的性能從直觀上看，形成了兩個大的聚類，一個是{con，adi}，另一個是{mas，gla，fad，car}。利用因子分析法也可以看出，一個因子和特征PA500密切聯(lián)系，而另一個因子和特征I0密切聯(lián)系。數(shù)據(jù)的結構以及對于特征分析的圖像使人們首先將數(shù)據(jù)集分成上面提到的這兩個大類。單獨便用特征I0并設定分類閾值為I0=600時得到了最好的分類結果，錯誤率為0。4.6.2決策樹簡介

整理ppt決策樹的性能在第二步判別中，從醫(yī)學的角度得到最有利的分類指導：類別car以及(mas，gla，fad)。利用判別分析法可知，利用這種方法在整個訓練集上得到的錯誤率大約為8%，所用的特征為AERA＿DA以及IPMAX。4.6.2決策樹簡介

整理ppt決策樹的性能應用樣本劃分法(對半的形式，即一半數(shù)目的樣本歸入訓練集，一半數(shù)目的樣本歸入測試集)隨機地進行兩次錯誤率估計，在測試集上得到的平均錯誤率為8.6%，和訓練集上得到的錯誤率估計值很相近。在第二級水平上，對于con類和adi類也利用特征I0進行判別，結果對于adi類錯誤率為0，而對于con類錯誤率為14%。4.6.2決策樹簡介

整理ppt決策樹的性能利用上面這些結果就可以建立一棵如圖4-41所示的決策樹。在決策樹的每一級水平上都使用了一個決策函數(shù)，具體如圖4-41中所示，作為必須滿足的一個決策規(guī)則。

yesno4.6.2決策樹簡介

整理ppt決策樹的性能由于在每一級水平上都只使用了少量數(shù)目的特征，對于第一級和第二級來講分別是l和2，在兩個水平上都得到了一個比較高的維數(shù)比率，這樣得到的置信區(qū)間為95%的錯誤率估計的可信度就比較高(對于第一級水平低于2%而對于car和{mas，gla，fad}水平大約在±3%)。4.6.2決策樹簡介

整理ppt分類器

前面對于胸部組織數(shù)據(jù)集采用的決策樹是一個二叉樹：在每一個結點上，所作的是一個“二中選一”的決策。這種二叉樹是最普遍的一種決策樹類型，即在每一個結點上對于單個的特征得到一個線性判別，這個判別平行于特征軸，并且對于專家來講很容易解釋其具體含義。它允許分類特征任意組合，通過對一個問題——這個樣本是否屬于一個類別集的回答結果"yes"或者"no"在每個結點上將樣本分類。4.6.2決策樹簡介

整理ppt分類器

例如，這種類型的決策樹經常被應用到醫(yī)學領域，經常是對一個給定的人群統(tǒng)計各個影響健康的因素的單獨作用，然后據(jù)此建立一棵樹。設計這種決策樹可以自動地采用很多方式，關鍵在于每個結點上采用什么樣的“分離規(guī)則(splitcriterion)”，以及為了找到最優(yōu)的組合而采用的搜索算法。4.6.2決策樹簡介

整理ppt分類器

一個“分離規(guī)則”具有如下形式：d(x)≥Δ式中，d(x)是對于特征向量x的決策函數(shù)，而Δ是一個閾值。通常使用的都是線性決策函數(shù)。在很多應用領域里，使用的"分離規(guī)則"是基于單個特征的表達式(于是被稱為單變量分離)。

4.6.2決策樹簡介

整理ppt數(shù)據(jù)挖掘中的統(tǒng)計分類器在一個大的機構(例如企業(yè)、醫(yī)院、信用卡公司等)應用某些數(shù)據(jù)庫技術時存在著一個趨勢，它包含著“數(shù)據(jù)倉庫”的概念，其中一個經典的數(shù)據(jù)搜索技術被稱為“數(shù)據(jù)挖掘”。一個數(shù)據(jù)倉庫就是一個包含著很多數(shù)據(jù)表的數(shù)據(jù)庫系統(tǒng)，數(shù)據(jù)表中的內容會周期性的更新，它們包含著很多細節(jié)的歷史信息，支持對于更高級數(shù)據(jù)的描述，還有很多的總結性工具，比如元數(shù)據(jù)等，也就是說，一些對于系統(tǒng)元素(例如名稱、定義、結構等)的定位和描述的數(shù)據(jù)。4.6.2決策樹簡介

整理ppt數(shù)據(jù)挖掘中的統(tǒng)計分類器數(shù)據(jù)挖掘技巧被用來從數(shù)據(jù)倉庫中提取相關的信息，它被應用于各種不同