【正文】 預(yù)測(cè)應(yīng)用（推論） 根據(jù)建立的分類(lèi)模型，對(duì)測(cè)試集合進(jìn)行測(cè)試。 分類(lèi)方法的實(shí)例包括：決策樹(shù)分類(lèi)法、基于規(guī)則的分類(lèi)法、 神經(jīng)網(wǎng)絡(luò)、支持向量級(jí)、樸素貝葉斯分類(lèi)方法等。學(xué)習(xí)算法得到的 模型不僅要很好擬合輸入數(shù)據(jù)，還要能夠正確地預(yù)測(cè)未知樣本的 類(lèi)標(biāo)號(hào)。用元組 (X,y)表示，其中， X 是屬性集合， y是一個(gè) 特殊的屬性，指出樣例的類(lèi)標(biāo)號(hào)（也稱(chēng)為分類(lèi)屬性或者目標(biāo)屬性） 第 6章 決策樹(shù) 決策樹(shù)基本概念 關(guān)于分類(lèi)問(wèn)題 名稱(chēng) 體溫 表皮覆蓋 胎生 水生動(dòng)物 飛行動(dòng)物 有腿 冬眠 類(lèi)標(biāo)號(hào) 人類(lèi) 恒溫 毛發(fā) 是 否 否 是 否 哺乳動(dòng)物 海龜 冷血 鱗片 否 半 否 是 否 爬行類(lèi) 鴿子 恒溫 羽毛 否 否 是 是 否 鳥(niǎo)類(lèi) 鯨 恒溫 毛發(fā) 是 是 否 否 否 哺乳類(lèi) X y 分類(lèi)與回歸 分類(lèi)目標(biāo)屬性 y是離散的，回歸目標(biāo)屬性 y是連續(xù)的 第 6章 決策樹(shù) 決策樹(shù)基本概念 解決分類(lèi)問(wèn)題的一般方法 分類(lèi)技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類(lèi)模型的系統(tǒng)方法。第 6 章 決策樹(shù) 主要內(nèi)容 決策樹(shù)基本概念 決策樹(shù)算法 決策樹(shù)研究問(wèn)題 主要參考文獻(xiàn) 主要內(nèi)容 決策樹(shù)基本概念 決策樹(shù)算法 決策樹(shù)研究問(wèn)題 主要參考文獻(xiàn) 第 6章 決策樹(shù) 決策樹(shù)基本概念 關(guān)于分類(lèi)問(wèn)題 分類(lèi)（ Classification）任務(wù)就是通過(guò)學(xué)習(xí)獲得一個(gè)目標(biāo)函數(shù) （ Target Function） f, 將每個(gè)屬性集 x映射到一個(gè)預(yù)先定義好的類(lèi) 標(biāo)號(hào) y。 分類(lèi)任務(wù)的輸入數(shù)據(jù)是紀(jì)錄的集合，每條記錄也稱(chēng)為實(shí)例 或者樣例。 分類(lèi)技術(shù)一般是用一種學(xué)習(xí)算法確定分類(lèi)模型，該模型可以很好 地?cái)M合輸入數(shù)據(jù)中類(lèi)標(biāo)號(hào)和屬性集之間的聯(lián)系。因此，訓(xùn)練算法的主要目標(biāo)就是要建立具有很好的泛化 能力模型，即建立能夠準(zhǔn)確地預(yù)測(cè)未知樣本類(lèi)標(biāo)號(hào)的模型。 第 6章 決策樹(shù) 決策樹(shù)基本概念 解決分類(lèi)問(wèn)題的一般方法 通過(guò)以上對(duì)分類(lèi)問(wèn)題一般方法的描述，可以看出分類(lèi)問(wèn)題 一般包括兩個(gè)步驟： 模型構(gòu)建（歸納） 通過(guò)對(duì)訓(xùn)練集合的歸納，建立分類(lèi)模型。 第 6章 決策樹(shù) 決策樹(shù)基本概念 解決分類(lèi)問(wèn)題的一般方法 TID A1 A2 A3 類(lèi) 1 Y 100 L N 2 N 125 S N 3 Y 400 L Y 4 N 415 M N 學(xué)習(xí)算法 學(xué)習(xí)模型 模型 應(yīng)用模型 TID A1 A2 A3 類(lèi) 1 Y 100 L ？ 2 N 125 S ？ 3 Y 400 L ？ 4 N 415 M ？ 訓(xùn)練集（類(lèi)標(biāo)號(hào)已知） 檢驗(yàn)集（類(lèi)標(biāo)號(hào)未知） 歸納 推論 第 6章 決策樹(shù) 決策樹(shù)基本概念 決策樹(shù) 決策樹(shù)是一種典型的分類(lèi)方法，首先對(duì)數(shù)據(jù)進(jìn)行處理，利用 歸納算法生成可讀的規(guī)則和決策樹(shù)，然后使用決策對(duì)新數(shù)據(jù)進(jìn)行 分析。 第 6章 決策樹(shù) 決策樹(shù)基本概念 決策樹(shù)的優(yōu)點(diǎn) 推理過(guò)程容易理解，決策推理過(guò)程可以表示成 If Then形式； 推理過(guò)程完全依賴(lài)于屬性變量的取值特點(diǎn)； 可自動(dòng)忽略目標(biāo)變量沒(méi)有貢獻(xiàn)的屬性變量，也為判斷屬性 變量的重要性，減少變量的數(shù)目提供參考。 歸納是從特殊到一般的過(guò)程。 歸納推理試圖從對(duì)象的一部分或整體的特定的觀(guān)察中獲得 一個(gè)完備且正確的描述。 歸納對(duì)于認(rèn)識(shí)的發(fā)展和完善具有重要的意義。 第 6章 決策樹(shù) 決策樹(shù)基本概念 關(guān)于歸納學(xué)習(xí) (2) 歸納學(xué)習(xí)的過(guò)程就是尋找一般化描述的過(guò)程。 銳角三角形內(nèi)角和等于 180度； 鈍角三角形內(nèi)角和等于 180度； 三角形內(nèi)角和 直角三角形內(nèi)角和等于 180度； 等于 180度 已知三角形 ABC， A角等于 76度， B角等于 89度，則其 C角等于 15度 歸納學(xué)習(xí)由于依賴(lài)于檢驗(yàn)數(shù)據(jù)，因此又稱(chēng)為檢驗(yàn)學(xué)習(xí)。該假定是歸納學(xué)習(xí)的有效性的前提條件。歸納可分為自 頂向下，自底向上和雙向搜索三種方式。將描述逐步一般化。 自頂向下法對(duì)可能的一般性描述集進(jìn)行搜索，試圖找到一些 滿(mǎn)足一定要求的最優(yōu)的描述。每個(gè)例子都是一個(gè) 對(duì)偶（序偶）（ x, f(x)），對(duì)每個(gè)輸入的 x，都有確定的輸出 f(x)。 F的每一個(gè)逼近都 叫做一個(gè)假設(shè)。例如， y=ax+b。在表示中 通常需要修改參數(shù)（如 a, b）。 一般方法如定義為使訓(xùn)練值與假設(shè)值 預(yù)測(cè)出的值之間的誤差平方 和 E最小為最佳。概念學(xué)習(xí)也可以看作是一 個(gè)搜索問(wèn)題的過(guò)程。多數(shù)情況下，為了高效地搜索，可以 利用假設(shè)空間中一種自然形成的結(jié)構(gòu)，即一般到特殊的偏序關(guān)系。這些計(jì)數(shù)存儲(chǔ)在混同矩陣（ Confusion Matrix）的表格中，二元 分類(lèi)問(wèn)題混淆矩陣如下： 實(shí)際 的類(lèi) 類(lèi) 1 f11 類(lèi) 0 f01 f10 f00 類(lèi) 1 類(lèi) 0 預(yù)測(cè)的類(lèi) 準(zhǔn)確率 =正確的預(yù)測(cè)數(shù) /預(yù)測(cè)總數(shù) =（ f11+f00） /(f11+f01+f10+f00) 差錯(cuò)率 =錯(cuò)誤的預(yù)測(cè)數(shù) /預(yù)測(cè)總數(shù) =（ f10+f01） /(f11+f01+f10+f00) 歸納學(xué)習(xí)假設(shè) 機(jī)器學(xué)習(xí)的任務(wù)是在整個(gè)實(shí)例集合 X上確定與目標(biāo)概念 c相同 的假設(shè) 。 H中每個(gè)假設(shè) h表 示 X上定義的布爾函數(shù)。若沒(méi)有更多的信息，只能假定對(duì)于未見(jiàn)實(shí)例最好的假設(shè)就是 訓(xùn)練數(shù)據(jù)最佳擬合的假設(shè)。 （ Function Approximation）。 1979年 , . Quinlan 給出 ID3算法，并在 1983年和 1986年對(duì) ID3 進(jìn)行了總結(jié)和簡(jiǎn)化，使其成為決策樹(shù)學(xué)習(xí)算法的典型。 1988年， Utgoff 在 ID4基礎(chǔ)上提出了 ID5學(xué)習(xí)算法，進(jìn)一步提高了效率。 另一類(lèi)決策樹(shù)算法為 CART，與 ， CART的決策樹(shù)由二元邏輯問(wèn)題生成，每個(gè)樹(shù)節(jié)點(diǎn)只有兩個(gè)分枝，分別包括學(xué)習(xí)實(shí)例的正例與反例。 年齡？ 學(xué)生？ 信譽(yù)？ 買(mǎi) 青 中 老 否 是 優(yōu) 良 不買(mǎi) 買(mǎi) 買(mǎi) 不買(mǎi) 決策樹(shù)中最上面的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)。每個(gè)分支是一 個(gè)新的決策結(jié)點(diǎn)，或者是樹(shù)的葉子。 每個(gè)葉結(jié)點(diǎn)代表一種可能的分類(lèi)結(jié)果 在沿著決策樹(shù)從上到下的遍歷過(guò)程中，在每個(gè)結(jié)點(diǎn)都有一個(gè) 測(cè)試。這一過(guò)程就是利用決策樹(shù)進(jìn)行分類(lèi)的過(guò)程， 利用若干個(gè)變量來(lái)判斷屬性的類(lèi)別 第 6章 決策樹(shù) 決策樹(shù)算法 CLS（ Concept Learning System）算法 CLS算法是早期的決策樹(shù)學(xué)習(xí)算法。 CLS基本思想 從一棵空決策樹(shù)開(kāi)始，選擇某一屬性（分類(lèi)屬性）作為測(cè)試 屬性。根據(jù)該屬性的值的 不同，可將訓(xùn)練樣本分成相應(yīng)的子集，如果該子集為空，或該子 集中的樣本屬于同一個(gè)類(lèi)，則該子集為葉結(jié)點(diǎn)，否則該子集對(duì)應(yīng) 于決策樹(shù)的內(nèi)部結(jié)點(diǎn)，即測(cè)試結(jié)點(diǎn)，需要選擇一個(gè)新的分類(lèi)屬性 對(duì)該子集進(jìn)行劃分，直到所有的子集都為空或者屬于同一類(lèi)。 2 若訓(xùn)練樣本集 T 中所有的樣本都屬于同一類(lèi) , 則生成結(jié)點(diǎn) T , 并終止學(xué)習(xí)算法 。 5 從訓(xùn)練樣本屬性表中刪除屬性 A。 第 6章 決策樹(shù) CLS算法問(wèn)題 在步驟 3中，根據(jù)某種策略從訓(xùn)練樣本屬性表中選擇屬性 A作為測(cè)試屬性。實(shí)踐表明，測(cè)試屬性集的組成以及測(cè)試屬性的先后對(duì)決策樹(shù)的學(xué)習(xí)具有舉足輕重的影響。 第 6章 決策樹(shù) ID3 決策樹(shù)算法 ID3算法主要針對(duì)屬性選擇問(wèn)題。 該方法使用信息增益度選擇測(cè)試屬性。 從直覺(jué)上講，小概率事件比大概率事件包含的信息量大。 如何度量信息量的大?。? 第 6章 決策樹(shù) ID3 –信息量大小的度量 決策樹(shù)算法 Shannon1948年提出的信息論理論。 假設(shè)有 n個(gè)互不相容的事件 a1,a2,a3,….,an, 它們中有且僅有一個(gè) 發(fā)生，則其平均的信息量可如下度量： ??????ni iiniin apapaIaaaI12121 )(1log)()(),.. .,( )(1log)()( 2iii apapaI ? 第 6章 決策樹(shù) ID3 –信息量大小的度量 決策樹(shù)算法 ??????ni iiniin apapaIaaaI12121 )(1log)()(),.. .,(上式，對(duì)數(shù)底數(shù)可以為任何數(shù)，不同的取值對(duì)應(yīng)了熵的不同單位。則任意樣本 S屬于類(lèi) Ci的概率為： ||||)(SCSp ii ?第 6章 決策樹(shù) ID3 –信息量大小的度量 決策樹(shù)算法 Entropy（ S， A） =∑（ |Sv|/|S|） * Entropy（ Sv）公式 2 ∑是屬性 A的所有可能的值 v,Sv是屬性 A有 v值的 S子集 |Sv|是 Sv 中元素的個(gè)數(shù)； |S|是 S中元素的個(gè)數(shù)。該屬性分 兩類(lèi)：買(mǎi) /不買(mǎi) S1(買(mǎi) )=641 S2（不買(mǎi)） = 383 S=S1+S2=1024 P1=641/1024= P2=383/1024= I(S1,S2)=I(641,383) =P1Log2P1P2Log2P2 =(P1Log2P1+P2Log2P2) = 決策樹(shù)算法 第 6章 決策樹(shù) 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類(lèi)：買(mǎi)計(jì)算機(jī)？ 64 青 高 否 良 不買(mǎi) 64 青 高 否 優(yōu) 不買(mǎi) 128 中 高 否 良 買(mǎi) 60 老 中 否 良 買(mǎi) 64 老 低 是 良 買(mǎi) 64 老 低 是 優(yōu) 不買(mǎi) 64 中 低 是 優(yōu) 買(mǎi) 128 青 中 否 良 不買(mǎi) 64 青 低 是 良 買(mǎi) 132 老 中 是 良 買(mǎi) 64 青 中 是 優(yōu) 買(mǎi) 32 中 中 否 優(yōu) 買(mǎi) 32 中 高 是 良 買(mǎi) 63 老 中 否 優(yōu) 不買(mǎi) 1 老 中 否 優(yōu) 買(mǎi) 第 2步計(jì)算條件屬性的熵 條件屬性共有 4個(gè)。 分別計(jì)算不同屬性的信息增益。 決策樹(shù)算法 第 6章 決策樹(shù) 決策樹(shù)的數(shù)據(jù)準(zhǔn)備 姓名 年齡 收入 學(xué)生 信譽(yù) 電話(huà) 地址 郵編 買(mǎi)計(jì)算機(jī) 張三 23 4000 是 良 2813220328 2714 Ave. M 77388 買(mǎi) 李四 34 2800 否 優(yōu) 7132397830 5606 Holly Cr 78766 買(mǎi) 王二 70 1900 否 優(yōu) 2812423222 2023 Bell Blvd. 70244 不買(mǎi) 趙五 18 900 是 良 2815500544 100 Main Street 70244 買(mǎi) 劉蘭 34 2500 否 優(yōu) 7132397430 606 Holly Ct 78566 買(mǎi) 楊俊 27 8900 否 優(yōu) 2813557990 233 Rice Blvd. 70388 不買(mǎi) 張毅 38 9500 否 優(yōu) 2815560544 399 Sugar Rd. 78244 買(mǎi) 。 。 整理后的數(shù)據(jù)表 決策樹(shù)的數(shù)據(jù)準(zhǔn)備 ? Data cleaning 刪除 /減少 noise， 補(bǔ)填 missing