《深入淺出決策樹分類ppt課件》由會員分享，可在線閱讀，更多相關《深入淺出決策樹分類ppt課件（22頁珍藏版）》請在裝配圖網上搜索。

決策樹分類,1,授課內容,決策樹的基本概念 如何構建一棵決策樹 ID3算法,2,小故事：女博士相親,決策樹!!,3,決策樹的基本概念,決策樹(Decision Tree):是一種樹形歸納分類算法,通過對訓練集數據的學習,挖掘出一定的規(guī)則,用于對測試集數據進行預測. 相親的例子： 分類類別：見 or 不見 訓練集：已相親人(的年齡、長相、收入等屬性) 測試集：待相親人(的年齡、長相、收入等屬性),4,決策樹的基本概念,決策樹的結構,,根節(jié)點,,,葉節(jié)點,分支,,內部節(jié)點,每個內部結點代表對某個屬性的一次測試，每條分支代表一個測試結果，葉結點代表某個類.,決策樹提供了一種展示在什么條件下會得到什么類別這種規(guī)則的方法.,5,決策樹的構建,已知： 訓練數據集D中有m個不同的類{C1,C2,C3,…,Cm}，設Ci,D是數據集D中Ci類的樣本的集合,|D|和|Ci,D|分別是D和Ci,D中的樣本個數 問題： 如何構建一棵決策樹對測試數據集進行分類？,6,決策樹的構建,ID3 最具影響和最為典型的算法 使用信息增益度選擇測試屬性 C4.5 CART,7,根據以下訓練集，使用ID3算法為電腦推銷員構建一棵決策樹,8,決策樹的構建(ID3),1.決定分類屬性集合; 2.對目前的數據表，建立一個節(jié)點N; 3.如果數據庫中的數據都屬于同一個類，N就是樹葉，在樹葉上標出所屬的類; 4.如果數據表中沒有其他屬性可以考慮，則N也是樹葉，按照少數服從多數的原則在樹葉上標出所屬類別; 5.否則，根據信息增益（GAIN值）選出一個最佳屬性作為節(jié)點N的測試屬性; 6.節(jié)點屬性選定后，對于該屬性中的每個值：從N生成一個分支，并將數據表中與該分支有關的數據收集形成分支節(jié)點的數據表，在表中刪除節(jié)點屬性那一欄; 7.如果分支數據表屬性非空，則轉1，運用以上算法從該節(jié)點建立子樹.,9,信息熵 (Entropy),如何衡量信息量的多少？比如一本50多萬字的《史記》或一套莎士比亞全集 1948年，香農(Claude Shannon)在他著名的論文“通信的數學原理”中提出了信息熵的概念，證明熵與信息內容的不確定程度有等價關系 若一個系統中存在多個事件E1,E2,…En，每個事件出現的概率是p1,p2,…pn，則這個系統的熵(平均信息量)是,10,數據集的信息熵,設數據集D中有m個不同的類C1, C2, C3, ., Cm，Ci,D是數據集D中Ci類的樣本的集合,|D|和 |Ci,D|分別是D和 Ci,D中的樣本個數 數據集D的信息熵: 其中pi是數據集D中任意樣本屬于類Ci的概率，用 估計,11,計算對下列數據集分類所需的信息熵,,|D|=14 |C1,D|=5 |C2,D|=9,,12,信息增益,選擇具有最高信息增益Gain(A) 的屬性A作為分裂屬性,按照能做“最佳分類”的屬性A劃分， 使完成樣本分類需要的信息量最小,,,13,確定第一次分裂的屬性：按年齡劃分,年齡40的有5個, 其中2個為“否”,Info年齡(D),Gain(年齡) = Info(D) - Info年齡(D) = 0.940 - 0.694 = 0.246,14,確定第一次分裂的屬性：按收入劃分,收入=高的有4個, 其中2個為“否” 收入=中的有6個, 其中2個為“否” 收入=低的有4個, 其中1個為“否”,Info收入(D),Gain(收入) = Info(D) - Info收入(D) = 0.940 - 0.911 = 0.029,15,確定第一次分裂的屬性：按學生劃分,是學生的有7個, 其中1個為“否” 不是學生的有7個, 其中4個為“否”,Info學生(D),Gain(學生) = Info(D) - Info學生(D) = 0.940 - 0.788 = 0.152,16,確定第一次分裂的屬性：按信用劃分,信用好的有6個, 其中3個為“否” 信用一般的有8個, 其中2個為“否”,Info信用(D),Gain(信用) = Info(D) - Info信用(D) = 0.940 - 0.892 = 0.048,17,確定第一次分裂的屬性,年齡,30,30-40,40,“年齡”屬性具體最高 信息增益，成為分裂屬性,,18,確定第二次分裂的屬性,Info收入(D) = 2/5 * (-2/2 * log2/2 - 0/2 * log0/2) + 2/5 * (-1/2 * log1/2 - 1/2 * log1/2) + 1/5 * (-1/1 * log1/1 - 0/1 * log0/1) = 0.400,Info學生(D) = 3/5 * (-3/3 * log3/3 - 0/3 * log0/3) + 2/5 * (-2/2 * log2/2 - 0/2 * log0/2) = 0,Info信用(D) = 3/5 * (-2/3 * log2/3 - 1/3 * log1/3) + 2/5 * (-1/2 * log1/2 - 1/2 * log1/2) = 0.951,,“學生”屬性具有最高 信息增益，成為分裂屬性,,19,決策樹的構建,年齡,30,30-40,40,學生,不買,買,不是學生,是學生,……,買,20,本堂小結,決策樹分類 概念，結構 決策樹構建 ID3算法，信息熵，信息增益 下節(jié)預告 ID3算法的不足 C4.5算法對ID3的改進,21,謝謝大家！,唐國明 國防科技大學原信息系統與管理學院,22,