【正文】 Y 4 N 415 M N 學(xué)習(xí)算法 學(xué)習(xí)模型 模型 應(yīng)用模型 TID A1 A2 A3 類 1 Y 100 L ？ 2 N 125 S ？ 3 Y 400 L ？ 4 N 415 M ？ 訓(xùn)練集（類標(biāo)號(hào)已知） 檢驗(yàn)集（類標(biāo)號(hào)未知） 歸納 推論 第 6章 決策樹 決策樹基本概念 決策樹 決策樹是一種典型的分類方法，首先對(duì)數(shù)據(jù)進(jìn)行處理，利用 歸納算法生成可讀的規(guī)則和決策樹，然后使用決策對(duì)新數(shù)據(jù)進(jìn)行 分析。因此，訓(xùn)練算法的主要目標(biāo)就是要建立具有很好的泛化 能力模型，即建立能夠準(zhǔn)確地預(yù)測(cè)未知樣本類標(biāo)號(hào)的模型。 分類任務(wù)的輸入數(shù)據(jù)是紀(jì)錄的集合，每條記錄也稱為實(shí)例 或者樣例。用元組 (X,y)表示，其中， X 是屬性集合， y是一個(gè) 特殊的屬性，指出樣例的類標(biāo)號(hào)（也稱為分類屬性或者目標(biāo)屬性） 第 6章 決策樹 決策樹基本概念 關(guān)于分類問題 名稱 體溫 表皮覆蓋 胎生 水生動(dòng)物 飛行動(dòng)物 有腿 冬眠 類標(biāo)號(hào) 人類 恒溫 毛發(fā) 是 否 否 是 否 哺乳動(dòng)物 海龜 冷血 鱗片 否 半 否 是 否 爬行類 鴿子 恒溫 羽毛 否 否 是 是 否 鳥類 鯨 恒溫 毛發(fā) 是 是 否 否 否 哺乳類 X y 分類與回歸 分類目標(biāo)屬性 y是離散的，回歸目標(biāo)屬性 y是連續(xù)的 第 6章 決策樹 決策樹基本概念 解決分類問題的一般方法 分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。 分類方法的實(shí)例包括：決策樹分類法、基于規(guī)則的分類法、 神經(jīng)網(wǎng)絡(luò)、支持向量級(jí)、樸素貝葉斯分類方法等。本質(zhì)上決策樹是通過一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類的過程。歸納推理從若干個(gè)事實(shí)中表 征出的特征、特性和屬性中，通過比較、總結(jié)、概括而得出一 個(gè)規(guī)律性的結(jié)論。人類知識(shí)的增長(zhǎng) 主要來源于歸納學(xué)習(xí)。歸納學(xué)習(xí)存在一個(gè)基本的假設(shè)： 任一假設(shè)如果能夠在足夠大的訓(xùn)練樣本集中很好的逼近目標(biāo)函數(shù)，則它也能在未見樣本中很好地逼近目標(biāo)函數(shù)。 自底向上法一次處理一個(gè)輸入對(duì)象。 第 6章 決策樹 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 1） 從特殊的訓(xùn)練樣例中歸納出一般函數(shù)是機(jī)器學(xué)習(xí)的中心問題； 從訓(xùn)練樣例中進(jìn)行學(xué)習(xí)通常被視為歸納推理。假設(shè)需要以某種形式表示。 第 6章 決策樹 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 2） 從這些不同的變形中選擇最佳的假設(shè)（或者說權(quán)值集合）。它在預(yù)定義的假設(shè)空間中搜索假設(shè)，使其與 訓(xùn)練樣例有最佳的擬合度。一般 H表示所有可能假設(shè)。 定義 歸納學(xué)習(xí)假設(shè)：任一假設(shè)如果在足夠大的訓(xùn)練樣例中很 好地逼近目標(biāo)函數(shù)，則它也能在未見實(shí)例中很好地逼近目標(biāo)函數(shù)。 Schlimmer 和 Fisher 于 1986年對(duì) ID3進(jìn)行改造，在每個(gè)可能的決策樹節(jié)點(diǎn)創(chuàng)建緩沖區(qū)，使決策樹可以遞增式生成，得到 ID4算法。 CLS, ID3， ， CART 第 6章 決策樹 決策樹算法 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(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ù)，那么對(duì)于任意給定的客人（測(cè)試樣例），你能幫助公司將這位客人歸類嗎？ 即：你能預(yù)測(cè)這位客人是屬于“買”計(jì)算機(jī)的那一類，還是屬于“不買”計(jì)算機(jī)的那一類？ 又：你需要多少有關(guān)這位客人的信息才能回答這個(gè)問題？ 決策樹的用途 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(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ì)算機(jī)？ 年齡？ 學(xué)生？ 信譽(yù)？ 買 青 中 老 否 是 優(yōu) 良 不買 買 買 不買 決策樹的用途 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(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ì)算機(jī)？ 年齡？ 學(xué)生？ 信譽(yù)？ 買 青 中 老 否 是 優(yōu) 良 不買 買 買 不買 決策樹的用途 決策樹算法 第 6章 決策樹 決策樹算法 決策樹的表示 決策樹的基本組成部分：決策結(jié)點(diǎn)、分支和葉子。 每個(gè)決策結(jié)點(diǎn)代表一個(gè)問題或者決策 . 通常對(duì)應(yīng)待分類對(duì)象的屬性。它是許多決策樹學(xué)習(xí)算法 的基礎(chǔ)。 第 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é)點(diǎn) 第 6章 決策樹 眼睛顏色 頭發(fā)顏色 頭發(fā)顏色 頭發(fā)顏色 黑色 蘭色 灰色 決策樹算法 CLS算法 黃種人 [1] 混血 [6] 白種人 [2] 白種人 [4] 混血 [8] 白種人 [3] 白種人 [5] 混血 [7] 黑色 金色 金色 紅色 黑色 金色 紅色 黑色 第 6章 決策樹 決策樹算法 CLS算法 1 生成一顆空決策樹和一張訓(xùn)練樣本屬性集 。 6 轉(zhuǎn)步驟 2, 對(duì)每個(gè)子集遞歸調(diào)用 CLS。 舉例加以說明，下表為調(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算法問題 決策樹算法 采用不同的測(cè)試屬性及其先后順序?qū)?huì)生成不同的決策樹 雞肉 豬肉 豬肉 牛肉 牛肉 牛肉 不缺鈣（ 2） 缺鈣（ 3， 6） 不缺鈣（ 4） 不缺鈣（ 10） 缺鈣（ 5） 不缺鈣（ 1） 魚肉 缺鈣（ 5） 不缺鈣（ 7， 9） 是 否 是 否 否 否 否 否 否 是 是 是 是 是 第 6章 決策樹 牛奶 不缺鈣 （ 1， 2， 4， 7， 9， 10） 缺鈣 （ 3， 5， 6， 8） CLS算法問題 決策樹算法 在上例中，顯然生成的兩種決策樹的復(fù)雜性和分類意義相差 很大由此可見，選擇測(cè)試屬性是決策樹學(xué)習(xí)算法中需要研究的重 要課題。 當(dāng)獲取信息時(shí)，將不確定的內(nèi)容轉(zhuǎn)為確定的內(nèi)容，因此信 息伴著不確定性。事件 ai的信息量 I（ ai ）可 如下度量： 其中 p(ai)表示事件 ai發(fā)生的概率。 第 6章 決策樹 ID3 –信息量大小的度量 決策樹算法 Gain（ S， A）是屬性 A在集合 S上的信息增益 Gain（ S， A） = Entropy（ S） Entropy（ S， A） 公式 3 Gain（ S， A）越大，說明選擇測(cè)試屬性對(duì)分類提供的信息越多 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(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) 買 決策樹算法 第 6章 決策樹 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(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ì)算決策屬性的熵