3第三章決策樹-文庫(kù)吧
2025-01-15 21:06 本頁(yè)面
【正文】 23/2/13 ? 決策樹歸納的基本算法是貪心算法，它以自頂向下遞歸各個(gè)擊破的方式構(gòu)造決策樹。 ? 貪心算法：在每一步選擇中都采取在當(dāng)前狀態(tài)下最好/優(yōu)的選擇。 ? 在其生成過(guò)程中，分割方法即屬性選擇度量是關(guān)鍵。通過(guò)屬性選擇度量，選擇出最好的將樣本分類的屬性。 ? 根據(jù)分割方法的不同，決策樹可以分為兩類：基于信息論的方法（較有代表性的是 ID ）和最小 GINI指標(biāo)方法（常用的有 CART、 SLIQ及SPRINT算法等）。 二、決策 樹 (Decision Tree) （一） 決策樹的結(jié)構(gòu) 11 根部節(jié)點(diǎn) (root node) 中間節(jié)點(diǎn) (nonleaf node) (代表測(cè)試的條件 ) 分支 (branches) (代表測(cè)試的結(jié)果 ) 葉節(jié)點(diǎn) (leaf node) (代表分類后所獲得 的分類標(biāo)記 ) 2023/2/13 2023/2/13 12 （二）決策樹的形成 例： 13 ? 根部節(jié)點(diǎn) ? 中間節(jié)點(diǎn) ? 停止分支 ？ 2023/2/13 （三） ID3算法 (,) 14 2023/2/13 ? Quinlan(1979)提出，以 Shannon(1949)的信息論為依據(jù)。 ? ID3算法的屬性選擇度量就是使用信息增益，選擇最高信息增益的屬性作為當(dāng)前節(jié)點(diǎn)的測(cè)試屬性。 ? 信息論 ： 若一事件有 k種結(jié)果 ，對(duì)應(yīng)的概率為 Pi。則此事件發(fā)生后所得到 的信息量 I(視為 Entropy)為： I=(p1*log2(p1)+ p2*log2(p2)+…+ pk*log2(pk)) Example 1： ? 設(shè) k=4?p1=,p2=,p3=,p4= I=(.25*log2(.25)*4)=2 Example 2： ? 設(shè) k=4?p1=0,p2=,p3=0,p4= I=(.5*log2(.5)*2)=1 Example 3： ? 設(shè) k=4?p1=1,p2=0,p3=0,p4=0 I=(1*log2(1))=0 2023/2/13 15 2023/2/13 16 信息增益 17 Example(Gain) n=16 n1=4
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1