【正文】 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 決策樹算法 第 6章 決策樹 計數(shù) 年齡 收入 學(xué)生 信譽 歸類：買計算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 1步計算決策屬性的熵 決策屬性“買計算機(jī)？”。 通常取 2，并規(guī)定當(dāng) p(ai)=0時 =0 )(1log)()(2iii apapaI ?公式 1 在決策樹分類中，假設(shè) S是訓(xùn)練樣本集合， |S|是訓(xùn)練樣本數(shù)，樣本 劃分為 n個不同的類 C1,C2,….Cn ，這些類的大小分別標(biāo)記為 |C1|， |C2|， …..,|Cn| 。事件 ai的信息量 I（ ai ）可 如下度量： 其中 p(ai)表示事件 ai發(fā)生的概率。 如果某件事情是“百年一見”則肯定比“習(xí)以為常”的事件包含的 信息量大。 當(dāng)獲取信息時，將不確定的內(nèi)容轉(zhuǎn)為確定的內(nèi)容，因此信 息伴著不確定性。是決策樹學(xué)習(xí)方法中最 具影響和最為典型的算法。 舉例加以說明，下表為調(diào)查學(xué)生膳食結(jié)構(gòu)和缺鈣情況的關(guān)系，其中 1表示包含食物， 0表示不包含 決策樹算法 第 6章 決策樹 CLS算法問題 決策樹算法 學(xué)生 雞肉 豬肉 牛肉 羊肉 魚肉 雞蛋 青菜 番茄 牛奶 健康情況 1 0 1 1 0 1 0 1 0 1 不缺鈣 2 0 0 0 0 1 1 1 1 1 不缺鈣 3 1 1 1 1 1 0 1 0 0 缺鈣 4 1 1 0 0 1 1 0 0 1 不缺鈣 5 1 0 0 1 1 1 0 0 0 缺鈣 6 1 1 1 0 0 1 0 1 0 缺鈣 7 0 1 0 0 0 1 1 1 1 不缺鈣 8 0 1 0 0 0 1 1 1 1 缺鈣 9 0 1 0 0 0 1 1 1 1 不缺鈣 10 1 0 1 1 1 1 0 1 1 不缺鈣 學(xué)生膳食結(jié)構(gòu)和缺鈣調(diào)查表 第 6章 決策樹 CLS算法問題 決策樹算法 采用不同的測試屬性及其先后順序?qū)刹煌臎Q策樹 雞肉 豬肉 豬肉 牛肉 牛肉 牛肉 不缺鈣（ 2） 缺鈣（ 3， 6） 不缺鈣（ 4） 不缺鈣（ 10） 缺鈣（ 5） 不缺鈣（ 1） 魚肉 缺鈣（ 5） 不缺鈣（ 7， 9） 是 否 是 否 否 否 否 否 否 是 是 是 是 是 第 6章 決策樹 牛奶 不缺鈣 （ 1， 2， 4， 7， 9， 10） 缺鈣 （ 3， 5， 6， 8） CLS算法問題 決策樹算法 在上例中，顯然生成的兩種決策樹的復(fù)雜性和分類意義相差 很大由此可見，選擇測試屬性是決策樹學(xué)習(xí)算法中需要研究的重 要課題。沒有規(guī)定采用何種測試屬性。 6 轉(zhuǎn)步驟 2, 對每個子集遞歸調(diào)用 CLS。否則 3 根據(jù) 某種策略 從訓(xùn)練樣本屬性表中選擇屬性 A 作為測試屬性 , 生成測試結(jié)點 A 4 若 A的取值為 v1,v2,…,vm, 則根據(jù) A 的取值的 不同 ,將 T 劃分成 m個子集 T1,T2,…,Tm。 第 6章 決策樹 人員 眼睛顏色 頭發(fā)顏色 所屬人種 1 黑色 黑色 黃種人 2 藍(lán)色 金色 白種人 3 灰色 金色 白種人 4 藍(lán)色 紅色 白種人 5 灰色 紅色 白種人 6 黑色 金色 混血 7 灰色 黑色 混血 8 藍(lán)色 黑色 混血 決策樹算法 CLS算法 第 6章 決策樹 人員 眼睛顏色 頭發(fā)顏色 所屬人種 1 黑色 黑色 黃種人 2 藍(lán)色 金色 白種人 3 灰色 金色 白種人 4 藍(lán)色 紅色 白種人 5 灰色 紅色 白種人 6 黑色 金色 混血 7 灰色 黑色 混血 8 藍(lán)色 黑色 混血 決策樹算法 CLS算法 決策樹的構(gòu)建 眼睛顏色 [1， 6] [2， 4， 8] [3， 5， 7] 黑色 蘭色 灰色 不屬于同一類，非葉結(jié)點 第 6章 決策樹 眼睛顏色 頭發(fā)顏色 頭發(fā)顏色 頭發(fā)顏色 黑色 蘭色 灰色 決策樹算法 CLS算法 黃種人 [1] 混血 [6] 白種人 [2] 白種人 [4] 混血 [8] 白種人 [3] 白種人 [5] 混血 [7] 黑色 金色 金色 紅色 黑色 金色 紅色 黑色 第 6章 決策樹 決策樹算法 CLS算法 1 生成一顆空決策樹和一張訓(xùn)練樣本屬性集 。該測試屬性對應(yīng)決策樹中的決策結(jié)點。它是許多決策樹學(xué)習(xí)算法 的基礎(chǔ)。對每個結(jié)點上問題的不同測試輸出導(dǎo)致不同的分枝，最后 會達(dá)到一個葉子結(jié)點。 每個決策結(jié)點代表一個問題或者決策 . 通常對應(yīng)待分類對象的屬性。 是整個決策樹的開始。 CLS, ID3， ， CART 第 6章 決策樹 決策樹算法 計數(shù) 年齡 收入 學(xué)生 信譽 歸類：買計算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 假定公司收集了左表數(shù)據(jù)，那么對于任意給定的客人（測試樣例），你能幫助公司將這位客人歸類嗎？ 即：你能預(yù)測這位客人是屬于“買”計算機(jī)的那一類，還是屬于“不買”計算機(jī)的那一類？ 又：你需要多少有關(guān)這位客人的信息才能回答這個問題？ 決策樹的用途 第 6章 決策樹 計數(shù) 年齡 收入 學(xué)生 信譽 歸類：買計算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 誰在買計算機(jī)？ 年齡？ 學(xué)生？ 信譽？ 買 青 中 老 否 是 優(yōu) 良 不買 買 買 不買 決策樹的用途 決策樹算法 第 6章 決策樹 計數(shù) 年齡 收入 學(xué)生 信譽 歸類：買計算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 誰在買計算機(jī)？ 年齡？ 學(xué)生？ 信譽？ 買 青 中 老 否 是 優(yōu) 良 不買 買 買 不買 決策樹的用途 決策樹算法 第 6章 決策樹 決策樹算法 決策樹的表示 決策樹的基本組成部分：決策結(jié)點、分支和葉子。 1993年， Quinlan 進(jìn)一步發(fā)展了 ID3算法，改進(jìn)成 。 Schlimmer 和 Fisher 于 1986年對 ID3進(jìn)行改造，在每個可能的決策樹節(jié)點創(chuàng)建緩沖區(qū)，使決策樹可以遞增式生成，得到 ID4算法。 })1,0{:( ?xhh第 6章 決策樹 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 4） 主要內(nèi)容 決策樹基本概念 決策樹算法 決策樹研究問題 主要參考文獻(xiàn) 第 6章 決策樹 決策樹算法 與決策樹相關(guān)的重要算法 Hunt,Marin和 Stone 于 1966年研制的 CLS學(xué)習(xí)系統(tǒng)，用于學(xué)習(xí)單個概 念。 定義 歸納學(xué)習(xí)假設(shè)：任一假設(shè)如果在足夠大的訓(xùn)練樣例中很 好地逼近目標(biāo)函數(shù)，則它也能在未見實例中很好地逼近目標(biāo)函數(shù)。由于對 c僅有的信息只是它在訓(xùn)練樣例上 的值，因此歸納學(xué)習(xí)最多只能保證輸出的假設(shè)能與訓(xùn)練樣例相擬 合。一般 H表示所有可能假設(shè)。 第 6章 決策樹 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 3） 分類模型的性能根據(jù)模型正確和錯誤預(yù)測也可以根據(jù)的檢驗記錄計數(shù) 進(jìn)行評估。它在預(yù)定義的假設(shè)空間中搜索假設(shè)，使其與 訓(xùn)練樣例有最佳的擬合度。 ??????a m p le str ain in gexbVtra inbbVbVtra inE)(,2^ ))()(( 學(xué)習(xí)是在假設(shè)空間上的一個搜索。 第 6章 決策樹 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 2） 從這些不同的變形中選擇最佳的假設(shè)（或者說權(quán)值集合）。通過 調(diào)整假設(shè)的表示，學(xué)習(xí)過程將產(chǎn)生出假設(shè)的不同變形。假設(shè)需要以某種形式表示。 學(xué)習(xí)過程將產(chǎn)生對目標(biāo)函數(shù) f的不同逼近。 第 6章 決策樹 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 1） 從特殊的訓(xùn)練樣例中歸納出一般函數(shù)是機(jī)器學(xué)習(xí)的中心問題； 從訓(xùn)練樣例中進(jìn)行學(xué)習(xí)通常被視為歸納推理。直 到最終的一般化描述。 自底向上法一次處理一個輸入對象。 第 6章 決策樹 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (3) 第 6章 決策樹 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (4) 歸納過程就是在描述空間中進(jìn)行搜索的過程。歸納學(xué)習(xí)存在一個基本的假設(shè)： 任一假設(shè)如果能夠在足夠大的訓(xùn)練樣本集中很好的逼近目標(biāo)函數(shù)，則它也能在未見樣本中很好地逼近目標(biāo)函數(shù)。這種一般性 描述能夠解釋給定的輸入數(shù)據(jù)，并可以用來預(yù)測新的數(shù)據(jù)。人類知識的增長 主要來源于歸納學(xué)習(xí)。即從特殊事實到普遍性規(guī)律的結(jié)論。歸納推理從若干個事實中表 征出的特征、特性和屬性中，通過比較、總結(jié)、概括而得出一 個規(guī)律性的結(jié)論。 第 6章 決策樹 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (1) 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是歸納算法。本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進(jìn)行分類的過程。