《數(shù)據(jù)挖掘?qū)д摰?章分類：基本概念、決策樹與模型評估》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)挖掘?qū)д摰?章分類：基本概念、決策樹與模型評估（91頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、Click to edit Master title style,,Click to edit Master text styles,,Second Level,,Third Level,,數(shù)據(jù)挖掘 分類：基本概念、決策樹與模型評價,第,4,章,分類：基本概念、決策樹與模型評價,,,,,,,分類的是利用一個分類函數(shù)（分類模型、分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)影射到給定類別中的一個。,,,分類,,訓(xùn)練集：數(shù)據(jù)庫中為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練集。,,訓(xùn)練集中的單個元組稱為,訓(xùn)練樣本,,,每個訓(xùn)練樣本有一個類別標(biāo)記。,,一個具體樣本的形式可為,:( v1, v2, ..., vn; c

2、);,其中,vi,表示屬性值,,c,表示類別。,,測試集：用于評估分類模型的準(zhǔn)確率,,數(shù)據(jù)分類,——,一個兩步過程,(1),第一步，建立一個模型，描述預(yù)定數(shù)據(jù)類集和概念集,,假定每個元組屬于一個預(yù)定義的類，由一個類標(biāo)號屬性確定,,學(xué)習(xí)模型可以用分類規(guī)則、決策樹或數(shù)學(xué)公式的形式提供,數(shù)據(jù)分類,——,一個兩步過程,(2),第二步，使用模型，對將來的或未知的對象進(jìn)行分類,,首先評估模型的預(yù)測準(zhǔn)確率,,對每個測試樣本，將已知的類標(biāo)號和該樣本的學(xué)習(xí)模型類預(yù)測比較,,模型在給定測試集上的準(zhǔn)確率是正確被模型分類的測試樣本的百分比,,測試集要獨(dú)立于訓(xùn)練樣本集，否則會出現(xiàn)“過分適應(yīng)數(shù)據(jù)”的情況,,如果準(zhǔn)確性能被

3、接受，則分類規(guī)則就可用來對新數(shù)據(jù)進(jìn)行分類,,有監(jiān)督的學(xué)習(xí),VS.,無監(jiān)督的學(xué)習(xí),有監(jiān)督的學(xué)習(xí)（用于分類）,,模型的學(xué)習(xí)在被告知每個訓(xùn)練樣本屬于哪個類的“監(jiān)督”下進(jìn)行,,新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類,,無監(jiān)督的學(xué)習(xí)（用于聚類）,,每個訓(xùn)練樣本的類編號是未知的，要學(xué)習(xí)的類集合或數(shù)量也可能是事先未知的,,通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號或進(jìn)行聚類,分類模型的構(gòu)造方法,1.,機(jī)器學(xué)習(xí)方法：,,決策樹法,,規(guī)則歸納,,,2.,統(tǒng)計方法：,知識表示是判別函數(shù)和原型事例,,貝葉斯法,,非參數(shù)法,(,近鄰學(xué)習(xí)或基于事例的學(xué)習(xí),),,,3.,神經(jīng)網(wǎng)絡(luò)方法,：,,BP,算法,,,模型表示是前

4、向反饋神經(jīng)網(wǎng)絡(luò)模型,,4.,粗糙集,(rough set),知識表示是產(chǎn)生式規(guī)則,,一個決策樹的例子,categorical,categorical,continuous,class,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,,Single, Divorced,< 80K,> 80K,Splitting Attributes,訓(xùn)練數(shù)據(jù),模型,:,決策樹,決策樹的另一個例子,categorical,categorical,continuous,class,MarSt,Refund,TaxInc,YES,NO,NO,NO,Yes,No,Marr

5、ied,,Single, Divorced,< 80K,> 80K,用決策樹歸納分類,什么是決策樹？,,類似于流程圖的樹結(jié)構(gòu),,每個內(nèi)部節(jié)點(diǎn)表示在一個屬性上的測試,,每個分枝代表一個測試輸出,,每個樹葉節(jié)點(diǎn)代表類或類分布,,決策樹的生成由兩個階段組成,,決策樹構(gòu)建,,開始時，所有的訓(xùn)練樣本都在根節(jié)點(diǎn),,遞歸的通過選定的屬性，來劃分樣本 （必須是離散值）,,樹剪枝,,許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點(diǎn)，樹剪枝試圖檢測和剪去這種分枝,,決策樹的使用：對未知樣本進(jìn)行分類,,通過將樣本的屬性值與決策樹相比較,為了對未知數(shù)據(jù)對象進(jìn)行分類識別，可以根據(jù)決策樹的結(jié)構(gòu)對數(shù)據(jù)集中的屬性進(jìn)行測試，從,決策樹

6、的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑,就形成了相應(yīng)對象的類別測試。決策樹可以很容易轉(zhuǎn)換為分類規(guī)則,,決策樹分類任務(wù),Decision Tree,一個決策樹的例子,categorical,categorical,continuous,class,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,,Single, Divorced,< 80K,> 80K,Splitting Attributes,訓(xùn)練數(shù)據(jù),模型,:,決策樹,應(yīng)用決策樹進(jìn)行分類,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,,Single, Div

7、orced,< 80K,> 80K,測試數(shù)據(jù),Start from the root of tree.,應(yīng)用決策樹進(jìn)行分類,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,,Single, Divorced,< 80K,> 80K,測試數(shù)據(jù),應(yīng)用決策樹進(jìn)行分類,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,,Single, Divorced,< 80K,> 80K,測試數(shù)據(jù),應(yīng)用決策樹進(jìn)行分類,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,,Sin

8、gle, Divorced,< 80K,> 80K,測試數(shù)據(jù),應(yīng)用決策樹進(jìn)行分類,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced,< 80K,> 80K,測試數(shù)據(jù),應(yīng)用決策樹進(jìn)行分類,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single, Divorced,< 80K,> 80K,測試數(shù)據(jù),Assign Cheat to “No”,決策樹分類,Decision Tree,決策樹,有許多決策樹算法,:,,Hunt,算法,,信息增益,——Information

9、gain,,（,ID3,）,,增益比率,——Gain ration,（,C4.5,）,,基尼指數(shù),——Gini index,,(SLIQ,，,SPRINT),,Hunt,算法,設(shè),D,t,,是與結(jié)點(diǎn),t,相關(guān)聯(lián)的訓(xùn)練記錄集,,算法步驟,:,,如果,D,t,,中所有記錄都屬于同一個類,y,t,,,則,t,是葉結(jié)點(diǎn)，用,y,t,標(biāo)記,,如果,D,t,,中包含屬于多個類的記錄，則,選擇一個屬性測試條件,，將記錄劃分成較小的子集。對于測試條件的每個輸出，創(chuàng)建一個子結(jié)點(diǎn)，并根據(jù)測試結(jié)果將,D,t,中的記錄分布到子結(jié)點(diǎn)中。然后，對于每個子結(jié)點(diǎn)，遞歸地調(diào)用該算法,D,t,?,Hunt,算法,Don’t,,C

10、heat,Refund,Don’t,,Cheat,Don’t,,Cheat,Yes,No,Refund,Don’t,,Cheat,Yes,No,Marital,,Status,Don’t,,Cheat,Cheat,Single,,,Divorced,Married,Taxable,,Income,Don’t,,Cheat,< 80K,>= 80K,Refund,Don’t,,Cheat,Yes,No,Marital,,Status,Don’t,,Cheat,Cheat,Single,,,Divorced,Married,決策樹,Hunt,算法采用貪心策略構(gòu)建決策樹,.,,在選擇劃分?jǐn)?shù)據(jù)的屬性時

11、，采取一系列局部最優(yōu)決策來構(gòu)造決策樹,.,,,決策樹歸納的設(shè)計問題,,如何分裂訓(xùn)練記錄,,怎樣為不同類型的屬性指定測試條件,?,,怎樣評估每種測試條件,?,,如何停止分裂過程,,決策樹,Hunt,算法采用貪心策略構(gòu)建決策樹,.,,在選擇劃分?jǐn)?shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹,.,,,決策樹歸納的設(shè)計問題,,如何分裂訓(xùn)練記錄,,怎樣為不同類型的屬性指定測試條件,?,,怎樣評估每種測試條件,?,,如何停止分裂過程,,怎樣為不同類型的屬性指定測試條件,?,依賴于屬性的類型,,標(biāo)稱,,序數(shù),,連續(xù),,,依賴于劃分的路數(shù),,2,路劃分,,多路劃分,基于標(biāo)稱屬性的分裂,多路劃分,:,,劃分?jǐn)?shù)

12、（輸出數(shù)）取決于該屬性不同屬性值的個數(shù),.,,,,,二元劃分,:,,劃分?jǐn)?shù)為,2,，這種劃分要考慮創(chuàng)建,k,個屬性值的二元劃分的所有,2,k-1,-1,種方法,.,CarType,Family,Sports,Luxury,CarType,{Family, Luxury},{Sports},CarType,{Sports, Luxury},{Family},OR,CarType,{Family,,Sports,},{,Luxury,},多路劃分,:,,劃分?jǐn)?shù)（輸出數(shù)）取決于該屬性不同屬性值的個數(shù),.,,,,,二元劃分,:,,劃分?jǐn)?shù)為,2,，需要保持序數(shù)屬性值的有序性,.,,,,基于序數(shù)屬性的劃

13、分,Size,Small,Medium,Large,Size,{Medium, Large},{Small},Size,{Small, Medium},{Large},OR,Size,{Small, Large},{Medium},基于連續(xù)屬性的劃分,,多路劃分,:,v,i,≤,A,＜,v,i+1,（,i=1,…,k),,,二元劃分,: (A < v) or (A,? v),,考慮所有的劃分點(diǎn)，選擇一個最佳劃分點(diǎn),v,基于連續(xù)屬性的劃分,決策樹,,決策樹歸納的設(shè)計問題,,如何分裂訓(xùn)練記錄,,怎樣為不同類型的屬性指定測試條件,?,,怎樣評估每種測試條件,?,,如何停止分裂過程,,怎樣選擇最佳劃

14、分？,在劃分前,: 10,個記錄,class 0, 10,個記錄,class 1,怎樣選擇最佳劃分？,選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點(diǎn)不純性的程度。不純性的程度越低，類分布就越傾斜,,結(jié)點(diǎn)不純性的度量,:,,不純性大,不純性小,怎樣找到最佳劃分？,B?,Yes,No,Node N3,Node N4,A?,Yes,No,Node N1,Node N2,劃分前,:,M0,M1,M2,M3,M4,M12,M34,Gain = M0 – M12 vs M0 – M34,結(jié)點(diǎn)不純性的測量,Gini,,,Entropy,,,classification error,不純性的測量,: GIN

15、I,給定結(jié)點(diǎn),t,的,Gini,值計算,:,,,,,(,p( j | t),是在結(jié)點(diǎn),t,中，類,j,發(fā)生的概率,).,,,當(dāng)類分布均衡時，,Gini,值達(dá)到最大值,(1 - 1/n,c,),,相反當(dāng)只有一個類時，,Gini,值達(dá)到最小值,0,計算,GINI,的例子,P(C1) = 0/6 = 0 P(C2) = 6/6 = 1,,Gini = 1 – P(C1),2,– P(C2),2,= 1 – 0 – 1 = 0,P(C1) = 1/6 P(C2) = 5/6,,Gini = 1 – (1/6),2,– (5/6),2,= 0.278,P(C1) = 2/6

16、 P(C2) = 4/6,,Gini = 1 – (2/6),2,– (4/6),2,= 0.444,基于,GINI,的劃分,當(dāng)一個結(jié)點(diǎn),p,分割成,k,個部分,(,孩子,),,劃分的質(zhì)量可由下面公式計算,,,,,,,n,i,=,孩子結(jié)點(diǎn),i,的記錄數(shù),,,,n,,=,父結(jié)點(diǎn),p,的記錄數(shù),.,二元屬性,:,計算,GINI,對于二元屬性，結(jié)點(diǎn)被劃分成兩個部分,,得到的,GINI,值越小，這種劃分越可行,.,B?,Yes,No,Node N1,Node N2,Gini(N1) = 1 – (5/6),2,– (2/6),2,= 0.194,,Gini(N2) = 1 – (1/

17、6),2,– (4/6),2,= 0.528,Gini,split,= 7/12 * 0.194 +  5/12 * 0.528= 0.333,標(biāo)稱屬性,:,計算,Gini,多路劃分,,二元劃分,,一般多路劃分的,Gini,值比二元劃分小，這一結(jié)果并不奇怪，因?yàn)槎獎澐謱?shí)際上合并了多路劃分的某些輸出，自然降低了子集的純度,Multi-way split,Two-way split,,(find best partition of values),連續(xù)屬性,:,計算,Gini,使用二元劃分,,劃分點(diǎn),v,選擇,,N,個記錄中所有屬性值作為劃分點(diǎn),,對每個劃分進(jìn)行類計數(shù),, A < v a

18、nd A,?,v,,計算每個候選點(diǎn),v,的,Gini,指標(biāo)，并從中選擇具有最小值的候選劃分點(diǎn),,時間復(fù)雜度為,(n,2,),連續(xù)屬性,:,計算,Gini...,降低計算復(fù)雜性的方法,,,,將記錄進(jìn)行排序,,從兩個相鄰的排過序的屬性值之間選擇中間值作為劃分點(diǎn),,計算每個候選點(diǎn)的,Gini,值,,時間復(fù)雜度為,nlogn,劃分點(diǎn),排序后的值,,定義：給定一個概率空間 事件,的自信息定義為,,因,,自信息反映了事件 發(fā)生所需要的信息量。,,值越大說明需要越多的信息才能確定事件 的發(fā)生，其隨機(jī)性也越大，而當(dāng) 發(fā)生時所攜帶的信息量也越大。反

19、過來， 值越小，需要較少信息量就能確定 的發(fā)生，即事件 隨機(jī)性較小。當(dāng)其發(fā)生時所攜信息量就少。 是對不確定性大小的一種刻畫,熵,---,定義,熵,---,定義,1.,定義：在概率空間 上定義的隨機(jī)變量,I( X),的數(shù)學(xué)期望,,,稱為隨機(jī)變量,X,的平均自信息，又稱,X,的信息熵或熵記為,H(x),,,非負(fù)性：,H,大于等于,0,,連續(xù)性：,H,對任意,q,連續(xù),,極值性：當(dāng),q,都等于,1\K,時,H,達(dá)到最大值,logK,熵,---,定義,基于,Information Gain,的劃分,給定結(jié)點(diǎn),t,的,Entr

20、opy,值計算,:,,,,(,p( j | t),是在結(jié)點(diǎn),t,中，類,j,發(fā)生的概率,).,,當(dāng)類分布均衡時，,Entropy,值達(dá)到最大值,(log n,c,),,相反當(dāng)只有一個類時，,Gini,值達(dá)到最小值,0,,Entropy,與,GINI,相似,計算,Entropy,的例子,P(C1) = 0/6 = 0 P(C2) = 6/6 = 1,,Entropy = – 0 log 0,,– 1 log 1 = – 0 – 0 = 0,P(C1) = 1/6 P(C2) = 5/6,,Entropy = – (1/6) log,2,(1/6),,– (5/6) lo

21、g,2,(1/6) = 0.65,P(C1) = 2/6 P(C2) = 4/6,,Entropy = – (2/6) log,2,(2/6),,– (4/6) log,2,(4/6) = 0.92,基于,Information Gain,的劃分,...,Information Gain:,,,,,,,n,i,=,孩子結(jié)點(diǎn),i,的記錄數(shù),,,,n,,=,結(jié)點(diǎn),p,的記錄數(shù),.,,在,ID3 and C4.5,中使用,,基于,Information Gain,的劃分,...,增益率（,Gain Ratio,）,:,,,,,,,熵和,Gini,指標(biāo)等不純性趨向于有利于具有大量不同

22、值的屬性,!,如：利用雇員,id,產(chǎn)生更純的劃分，但它卻毫無用處,,每個劃分相關(guān)聯(lián)的記錄數(shù)太少，將不能做出可靠的預(yù)測,,解決該問題的策略有兩種：,,限制測試條件只能是二元劃分,,使用增益率。,K,越大,Split Info,越大增益率越小,基于,Classification Error,的劃分,給定結(jié)點(diǎn),t,的,Classification Error,值計算,,:,,,,,當(dāng)類分布均衡時，,error,值達(dá)到最大值,(1 - 1/n,c,),,相反當(dāng)只有一個類時，,error,值達(dá)到最小值,0,例子,P(C1) = 0/6 = 0 P(C2) = 6/6 = 1,,Error = 1

23、 – max (0, 1) = 1 – 1 = 0,P(C1) = 1/6 P(C2) = 5/6,,Error = 1 – max (1/6, 5/6) = 1 – 5/6 = 1/6,P(C1) = 2/6 P(C2) = 4/6,,Error = 1 – max (2/6, 4/6) = 1 – 4/6 = 1/3,不純性度量之間的比較,二元分類問題,:,決策樹,Hunt,算法采用貪心策略構(gòu)建決策樹,.,,在選擇劃分?jǐn)?shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構(gòu)造決策樹,.,,,決策樹歸納的設(shè)計問題,,如何分裂訓(xùn)練記錄,,怎樣為不同類型的屬性指定測試條件,?

24、,,怎樣評估每種測試條件,?,,如何停止分裂過程,,停止分裂過程,當(dāng)所有的記錄屬于同一類時，停止分裂,,,當(dāng)所有的記錄都有相同的屬性時，停止分裂,,,提前終止樹的生長,,,三種著名的決策樹,Cart,：基本的決策樹算法,,Id3,：利用增益比不純性，樹采用二叉樹，停止準(zhǔn)則為當(dāng)所有的記錄屬于同一類時，停止分裂，或當(dāng)所有的記錄都有相同的屬性時，停止分裂,,C4.5,：,id3,的改進(jìn)版本，也是最流行的分類數(shù)算法。采用多重分支和剪枝技術(shù)。,,,決策樹,特點(diǎn),:,,決策樹是一種構(gòu)建分類模型的非參數(shù)方法,,不需要昂貴的的計算代價,,決策樹相對容易解釋,,決策樹是學(xué)習(xí)離散值函數(shù)的典型代表,,決策數(shù)對于噪聲

25、的干擾具有相當(dāng)好的魯棒性,,冗余屬性不會對決策樹的準(zhǔn)確率造成不利影響,,數(shù)據(jù)碎片問題。隨著數(shù)的生長，可能導(dǎo)致葉結(jié)點(diǎn)記錄數(shù)太少，對于葉結(jié)點(diǎn)代表的類，不能做出具有統(tǒng)計意義的判決,,子樹可能在決策樹中重復(fù)多次。使決策樹過于復(fù)雜,,子樹重復(fù)問題,,Same,subtree,appears in multiple branches,決策邊界,,斜決策樹,x + y < 1,Class =,+,,Class =,模型過分?jǐn)M合和擬合不足,分類模型的誤差大致分為兩種：,,訓(xùn)練誤差：是在訓(xùn)練記錄上誤分類樣本比例,,泛化誤差：是模型在未知記錄上的期望誤差,,一個好的分類模型不僅要能夠很好的擬合訓(xùn)練數(shù)據(jù)，而且對未知

26、樣本也要能準(zhǔn)確分類。,,換句話說，一個好的分類模型必須具有低訓(xùn)練誤差和低泛化誤差。,,當(dāng)訓(xùn)練數(shù)據(jù)擬合太好的模型，其泛化誤差可能比具有較高訓(xùn)練誤差的模型高，這種情況成為模型,過分?jǐn)M合,模型過分?jǐn)M合和擬合不足,當(dāng)決策樹很小時，訓(xùn)練和檢驗(yàn)誤差都很大，這種情況稱為,模型擬合不足,。出現(xiàn)擬合不足的原因是模型尚未學(xué)習(xí)到數(shù)據(jù)的真實(shí)結(jié)構(gòu)。,,隨著決策樹中結(jié)點(diǎn)數(shù)的增加，模型的訓(xùn)練誤差和檢驗(yàn)誤差都會隨之下降。,,當(dāng)樹的規(guī)模變得太大時，即使訓(xùn)練誤差還在繼續(xù)降低，但是檢驗(yàn)誤差開始增大，導(dǎo)致,模型過分?jǐn)M合,模型模型過分?jǐn)M合和擬合不足,過分?jǐn)M合,導(dǎo)致過分?jǐn)M合的原因,導(dǎo)致過分?jǐn)M合的原因,噪聲導(dǎo)致的過分?jǐn)M合,,例子：哺乳動物

27、的分類問題,,十個訓(xùn)練記錄中有兩個被錯誤標(biāo)記：蝙蝠和鯨,,如果完全擬合訓(xùn)練數(shù)據(jù)，決策樹,1,的訓(xùn)練誤差為,0,，但它在檢驗(yàn)數(shù)據(jù)上的誤差達(dá),30%.,人和海豚，針鼴誤分為非哺乳動物,,相反，一個更簡單的決策樹,2,，具有較低的檢驗(yàn)誤差（,10%,），盡管它的訓(xùn)練誤差較高，為,20%,,決策樹,1,過分?jǐn)M合了訓(xùn)練數(shù)據(jù)。因?yàn)閷傩詼y試條件,4,條腿具有欺騙性，它擬合了誤標(biāo)記的訓(xùn)練紀(jì)錄，導(dǎo)致了對檢驗(yàn)集中記錄的誤分類,,噪聲導(dǎo)致的過分?jǐn)M合（例子）,噪聲導(dǎo)致決策邊界的改變,缺乏代表性樣本導(dǎo)致的過分?jǐn)M合,根據(jù)少量訓(xùn)練記錄做出分類決策的模型也容易受過分?jǐn)M合的影響。,,由于訓(xùn)練數(shù)據(jù)缺乏具有代表性的樣本，在沒有多少

28、訓(xùn)練記錄的情況下，學(xué)習(xí)算法仍然細(xì)化模型就會產(chǎn)生過分?jǐn)M合。,,,,例子：五個訓(xùn)練記錄，所有的記錄都是正確標(biāo)記的，對應(yīng)的決策樹盡管訓(xùn)練誤差為,0,，但檢驗(yàn)誤差高達(dá),30%,,人、大象和海豚被誤分類，因?yàn)闆Q策樹把恒溫但不冬眠的動物分為非哺乳動物。決策樹做出這樣的分類決策是因?yàn)橹挥幸粋€訓(xùn)練記錄（鷹）具有這些特征。,,這個例子清楚的表明，當(dāng)決策樹的葉結(jié)點(diǎn)沒有足夠的代表性樣本時，很可能做出錯誤的預(yù)測。,,過分?jǐn)M合與多重比較,模型的過分?jǐn)M合可能出現(xiàn)在使用多重比較過程的算法中,,多重比較的例子：考慮未來十個交易日股市是升還是降,,一個人十次猜測至少正確預(yù)測八次的概率是：,0.0547,,假設(shè)從,50,個股票分

29、析家中選擇一個投資顧問，策略是選擇在未來的十個交易日做出最多正確預(yù)測的分析家。,,該策略的缺點(diǎn)是，即使所有的分析家都用隨機(jī)猜測做出預(yù)測，至少有一個分析家做出八次正確預(yù)測的概率是：,1-,（,1-0.0547,）,50,=0.9399,，這一結(jié)果相當(dāng)高。,,,多重比較過程與模型過分?jǐn)M合有什么關(guān)系？,,在決策樹增長過程中，可以進(jìn)行多種測試，以確定哪個屬性能夠最好的劃分訓(xùn)練數(shù)據(jù)。,,在這種情況下，算法實(shí)際上是使用多重比較過程來決定是否需要擴(kuò)展決策樹。,,當(dāng)候選屬性多，訓(xùn)練記錄數(shù)少時，這種影響就變得更加明顯。,泛化誤差估計,過分?jǐn)M合的主要原因一直是個爭辯的話題，但大家還是普遍同意模型的復(fù)雜度對模型的過

30、分?jǐn)M合有影響。,,如何確定正確的模型復(fù)雜度？理想的復(fù)雜度是能產(chǎn)生最低泛化誤差的模型的復(fù)雜度。,,估計泛化誤差的方法,,使用再代入估計。用訓(xùn)練誤差提供對泛化誤差的樂觀估計,,結(jié)合模型復(fù)雜度,,估計統(tǒng)計上界,,使用確定集,,,,結(jié)合模型復(fù)雜度,奧卡姆剃刀 （,Occam's Razor,）：給定兩個具有相同泛化誤差的模型，較簡單的模型比復(fù)雜的模型更可取,,,,因?yàn)閺?fù)雜模型中的附加成分很大程度上是偶然的擬合。因此，分類模型評估應(yīng)把模型復(fù)雜度考慮進(jìn)去,,方法：悲觀誤差估計、最小描述長度原則（,MDL,）,悲觀誤差評估,,悲觀誤差估計公式：,,,,,,,,Q(ti),為每個結(jié)點(diǎn),ti,的罰分，,e(T)

31、,為訓(xùn)練樣本集的錯分樣本數(shù)，,N,t,為訓(xùn)練樣本總數(shù)，,k,為葉結(jié)點(diǎn)數(shù)。,,,,,例子,1,：如果罰分等于,0.5,，訓(xùn)練樣本集中樣本數(shù)為,24,個，我們構(gòu)建了,7,個葉結(jié)點(diǎn)的決策樹，訓(xùn)練樣本集的錯分樣本數(shù)為,4,,根據(jù)公式我們得,e’(T)=(4+7*0.5)/24=0.3125,,例子,2,：如果罰分等于,0.5,，訓(xùn)練樣本集中樣本數(shù)為,24,個，我們構(gòu)建了,4,個葉結(jié)點(diǎn)的決策樹，訓(xùn)練樣本集的錯分樣本數(shù)為,6,,根據(jù)公式我們得,e’(T)=(6+4*0.5)/24=0.3333,,當(dāng)罰分等于,1,時，例,1,，,2,為,0.458,，,0.417,,0.5,的罰分項(xiàng)表示只要至少能夠改進(jìn)一個

32、訓(xùn)練記錄的分類，結(jié)點(diǎn)就應(yīng)當(dāng)擴(kuò)充，因?yàn)閿U(kuò)展一個結(jié)點(diǎn)等價于總誤差增加,0.5,，代價比犯一個訓(xùn)練錯誤小,,最小描述長度,(MDL),Cost(Model,Data) = Cost(Data|Model) + Cost(Model),,Cost,是傳輸總代價,.,,最小化,cost,值,.,,Cost(Data|Model),是誤分類記錄編碼的開銷,.,,Cost(Model),是模型編碼的開銷,.,使用確認(rèn)集,該方法中，不是用訓(xùn)練集估計泛化誤差，而是把原始的訓(xùn)練數(shù)據(jù)集分為兩個較小的子集，一個子集用于訓(xùn)練，而另一個稱為確認(rèn)集，用于估計泛化誤差。,,該方法為評估模型在未知樣本上的性能提供了較好辦法。,

33、處理決策樹中的過分?jǐn)M合,先剪枝,(Early Stopping Rule),,樹增長算法在產(chǎn)生完全擬合整個訓(xùn)練數(shù)據(jù)集的之前就停止決策樹的生長,,為了做到這一點(diǎn)，需要采用更具限制性的結(jié)束條件,:,,,當(dāng)結(jié)點(diǎn)的記錄數(shù)少于一定閾值，則停止生長,,當(dāng)不純性度量的增益低于某個確定的閾值時，則停止生長,(e.g., information gain).,,缺點(diǎn)：很難為提前終止選取正確的閾值,:,,,閾值太高，導(dǎo)致擬合不足,,閾值太低，導(dǎo)致不能充分解決過分?jǐn)M合的問題。,處理決策樹中的過分?jǐn)M合,…,后剪枝,,在該方法中，初始決策樹按照最大規(guī)模生長，然后進(jìn)行剪枝的步驟，按照自底向上的方式修剪完全增長的決策樹。,

34、,修剪有兩種做法,:,,,用新的葉結(jié)點(diǎn)替換子樹，該葉結(jié)點(diǎn)的類標(biāo)號由子樹下記錄中的多數(shù)類確定,,用子樹中最常用的分支代替子樹,,處理決策樹中的過分?jǐn)M合,…,,與先剪枝相比，后剪枝技術(shù)傾向于產(chǎn)生更好的結(jié)果。,,因?yàn)椴幌裣燃糁?，后剪枝是根?jù)完全增長的決策樹作出的剪枝決策，先剪枝則可能過早終止決策樹的生長。,,然而，對于后剪枝，當(dāng)子樹被剪掉后，生長完全決策樹的額外開銷就被浪費(fèi)了。,不平衡類問題,,,,,,,,PREDICTED CLASS,,,,,ACTUALCLASS,,Class=Yes,Class=No,,Class=Yes,a,(TP),b,(FN),,Class=No,c,(FP),d,(

35、TN),準(zhǔn)確率的缺點(diǎn),考慮,2,類問題,,類,0,的樣本數(shù),= 9990,,類,1,的樣本數(shù),= 10,,,如果模型預(yù)測所有的樣本為類,0,,,準(zhǔn)確率為,9990/10000 = 99.9 %,,準(zhǔn)確率的值具有欺騙性,,模型并沒有分對類,1,的任何樣本,,,度量,,精度確定在分類器斷言為正類的那部分記錄中實(shí)際為正類的記錄所占的比例。精度越高，分類器的假正類錯誤率就越低。,,召回率度量被分類器正確預(yù)測的正樣本的比例。具有高召回率的分類器很少將正樣本誤分為負(fù)樣本。,ROC (Receiver Operating Characteristic),ROC,曲線是顯示分類器真正率（,TPR,）和假正率（,FPR,）之間折中的一種圖形化方法。,,ROC,曲線上有幾個關(guān)鍵點(diǎn)，它們有公認(rèn)的解釋：,,（,TPR=0,，,FPR=0,）：把每個實(shí)例都預(yù)測為負(fù)類的模型,,（,TPR=1,，,FPR=1,）：把每個實(shí)例都預(yù)測為正類的模型,,（,TPR=1,，,FPR=0,）：理想模型,,使用,ROC,曲線比較模型,沒有哪個模型能夠壓倒對方,,FRR<0.36,M,1,,較好,,FRR>0.36, M,2,較好,,,ROC,曲線下方的面積,,理想情況,:,,,面積,= 1,,隨機(jī)猜測,:,,,面積,= 0.5,怎樣產(chǎn)生,ROC,曲線,Threshold >=,ROC,曲線,:,