機(jī)器人課件3決策樹(shù)學(xué)習(xí)

1、2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬1機(jī)器學(xué)習(xí)第3章 決策樹(shù)學(xué)習(xí)2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬2概論 決策樹(shù)學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一 是一種逼近離散值函數(shù)的方法 很好的健壯性 能夠?qū)W習(xí)析取表達(dá)式 ID3, Assistant, C4.5 搜索一個(gè)完整表示的假設(shè)空間 歸納偏置是優(yōu)先選擇較小的樹(shù) 決策樹(shù)表示了多個(gè)if-then規(guī)則2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬3提綱 決策樹(shù)定義 適用問(wèn)題特征 基本ID3算法

2、 決策樹(shù)學(xué)習(xí)的歸納偏置 訓(xùn)練數(shù)據(jù)的過(guò)度擬合 更深入的話題2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬4決策樹(shù)表示法 決策樹(shù) 通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類實(shí)例。 葉子節(jié)點(diǎn)即為實(shí)例所屬的分類 樹(shù)上每個(gè)節(jié)點(diǎn)說(shuō)明了對(duì)實(shí)例的某個(gè)屬性的測(cè)試 節(jié)點(diǎn)的每個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值 圖3-1 決策樹(shù)代表實(shí)例屬性值約束的合取的析取式。從樹(shù)根到樹(shù)葉的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合取，樹(shù)本身對(duì)應(yīng)這些合取的析取。2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬5決策樹(shù)學(xué)習(xí)的適用問(wèn)題 適用問(wèn)題的特征 實(shí)例

3、由“屬性-值”對(duì)表示 目標(biāo)函數(shù)具有離散的輸出值 可能需要析取的描述 訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤 訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例 問(wèn)題舉例 根據(jù)疾病分類患者 根據(jù)起因分類設(shè)備故障 根據(jù)拖欠支付的可能性分類貸款申請(qǐng) 分類問(wèn)題 核心任務(wù)是把樣例分類到各可能的離散值對(duì)應(yīng)的類別2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬6基本的決策樹(shù)學(xué)習(xí)算法 大多數(shù)決策樹(shù)學(xué)習(xí)算法是一種核心算法的變體 采用自頂向下的貪婪搜索遍歷可能的決策樹(shù)空間 ID3是這種算法的代表2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬7基本的決策樹(shù)學(xué)

4、習(xí)算法（2） ID3的思想 自頂向下構(gòu)造決策樹(shù) 從“哪一個(gè)屬性將在樹(shù)的根節(jié)點(diǎn)被測(cè)試”開(kāi)始 使用統(tǒng)計(jì)測(cè)試來(lái)確定每一個(gè)實(shí)例屬性單獨(dú)分類訓(xùn)練樣例的能力 ID3的過(guò)程 分類能力最好的屬性被選作樹(shù)的根節(jié)點(diǎn) 根節(jié)點(diǎn)的每個(gè)可能值產(chǎn)生一個(gè)分支 訓(xùn)練樣例排列到適當(dāng)?shù)姆种?重復(fù)上面的過(guò)程2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬8表3-1 用于學(xué)習(xí)布爾函數(shù)的ID3算法概要ID3(Examples, Target_attribute, Attributes)創(chuàng)建樹(shù)的root節(jié)點(diǎn)如果Examples都為正,返回label=+的單節(jié)點(diǎn)樹(shù)root如果Examples都為

5、反,返回label=-的單節(jié)點(diǎn)樹(shù)root如果Attributes為空，那么返回單節(jié)點(diǎn)root，label=Examples中最普遍的Target_attribute值否則開(kāi)始AAttributes中分類examples能力最好的屬性root的決策屬性A對(duì)于A的每個(gè)可能值vi在root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空 在這個(gè)新分支下加一個(gè)葉子節(jié)點(diǎn)，節(jié)點(diǎn)的label=Examples中最普遍的Target_attribute值 否則在新分支下加一個(gè)子樹(shù)ID3（ Examplesvi,Target_attr

6、ibute,Attributes-A）結(jié)束返回root2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬9最佳分類屬性信息增益 用來(lái)衡量給定的屬性區(qū)分訓(xùn)練樣例的能力 ID3算法在增長(zhǎng)樹(shù)的每一步使用信息增益從候選屬性中選擇屬性用熵度量樣例的均一性 熵刻畫了任意樣例集的純度 給定包含關(guān)于某個(gè)目標(biāo)概念的正反樣例的樣例集S，那么S相對(duì)這個(gè)布爾型分類的熵為Entropy(S)=-p+log2p+ - p-log2p- 信息論中對(duì)熵的一種解釋，熵確定了要編碼集合S中任意成員的分類所需要的最少二進(jìn)制位數(shù) 更一般地，如果目標(biāo)屬性具有c個(gè)不同的值，那么S相對(duì)于c個(gè)狀態(tài)

7、的分類的熵定義為 Entropy(S)=ciiipp12log2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬10最佳分類屬性（2） 用信息增益度量期望的熵降低 屬性的信息增益，由于使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低 Gain(S,A)是在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù) 例子)()(|)(),(AValuesvvvSEntropySSSEntropyASGain2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬11ID3算法舉例 表3-2 繼續(xù)這個(gè)過(guò)程，直到滿足以下兩個(gè)條件中的一個(gè) 所有的屬性已

8、經(jīng)被這條路經(jīng)包括 與這個(gè)節(jié)點(diǎn)關(guān)聯(lián)的所有訓(xùn)練樣例都具有相同的目標(biāo)屬性值2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬12決策樹(shù)學(xué)習(xí)中的假設(shè)空間搜索 觀察ID3的搜索空間和搜索策略，認(rèn)識(shí)到這個(gè)算法的優(yōu)勢(shì)和不足 假設(shè)空間包含所有的決策樹(shù)，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間 維護(hù)單一的當(dāng)前假設(shè)（不同于第二章的變型空間候選消除算法） 不進(jìn)行回溯，可能收斂到局部最優(yōu) 每一步使用所有的訓(xùn)練樣例，不同于基于單獨(dú)的訓(xùn)練樣例遞增作出決定，容錯(cuò)性增強(qiáng)2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬13決策樹(shù)學(xué)習(xí)

9、的歸納偏置 ID3的搜索策略 優(yōu)先選擇較短的樹(shù) 選擇那些信息增益高的屬性離根節(jié)點(diǎn)較近的樹(shù) 很難準(zhǔn)確刻畫ID3的歸納偏置 近似的ID3的歸納偏置 較短的樹(shù)比較長(zhǎng)的樹(shù)優(yōu)先 近似在于ID3得到局部最優(yōu)，而不一定是全局最優(yōu) 一個(gè)精確具有這個(gè)歸納偏置的算法，BFS-ID3 更貼切近似的歸納偏置 較短的樹(shù)比較長(zhǎng)的樹(shù)優(yōu)先，信息增益高的屬性更靠近根節(jié)點(diǎn)的樹(shù)優(yōu)先2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬14限定偏置和優(yōu)選偏置 ID3和候選消除算法的比較 ID3的搜索范圍是一個(gè)完整的假設(shè)空間，但不徹底地搜索這個(gè)空間 候選消除算法的搜索范圍是不完整的假設(shè)空間，但徹

10、底地搜索這個(gè)空間 ID3的歸納偏置完全是搜索策略排序假設(shè)的結(jié)果，來(lái)自搜索策略 候選消除算法完全是假設(shè)表示的表達(dá)能力的結(jié)果，來(lái)自對(duì)搜索空間的定義2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬15限定偏置和優(yōu)選偏置 優(yōu)選偏置 ID3的歸納偏置是對(duì)某種假設(shè)勝過(guò)其他假設(shè)的一種優(yōu)選，對(duì)最終可列舉的假設(shè)沒(méi)有硬性限制 限定偏置 候選消除算法的偏置是對(duì)待考慮假設(shè)的一種限定 通常優(yōu)選偏置比限定偏置更符合歸納學(xué)習(xí)的需要 優(yōu)選偏置和限定偏置的結(jié)合 考慮第1章的例子2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬16為什么短

11、的假設(shè)優(yōu)先 ID3的歸納偏置的哲學(xué)基礎(chǔ) 奧坎姆剃刀 優(yōu)先選擇擬合數(shù)據(jù)的最簡(jiǎn)單的假設(shè) 科學(xué)上的例子 物理學(xué)家優(yōu)先選擇行星運(yùn)動(dòng)的簡(jiǎn)單假設(shè) 簡(jiǎn)單假設(shè)的數(shù)量遠(yuǎn)比復(fù)雜假設(shè)的數(shù)量少 簡(jiǎn)單假設(shè)對(duì)訓(xùn)練樣例的針對(duì)性更小，更像是泛化的規(guī)律，而不是訓(xùn)練樣例的另一種描述2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬17為什么短的假設(shè)優(yōu)先 奧坎姆剃刀的困難 我們反問(wèn)，使用上頁(yè)的推理，應(yīng)該優(yōu)先選擇包含恰好17個(gè)葉子節(jié)點(diǎn)和11個(gè)非葉子節(jié)點(diǎn)的決策樹(shù)？ 假設(shè)的規(guī)模由學(xué)習(xí)器內(nèi)部使用的特定表示決定 從生物進(jìn)化的觀點(diǎn)看內(nèi)部表示和奧坎姆剃刀原則2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯

12、者：曾華軍等 作者：Mitchell 講者：陶曉鵬18決策樹(shù)學(xué)習(xí)的常見(jiàn)問(wèn)題 決策樹(shù)學(xué)習(xí)的實(shí)際問(wèn)題 確定決策樹(shù)增長(zhǎng)的深度 處理連續(xù)值的屬性 選擇一個(gè)適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn) 處理屬性值不完整的訓(xùn)練數(shù)據(jù) 處理不同代價(jià)的屬性 提高計(jì)算效率 針對(duì)這些問(wèn)題，ID3被擴(kuò)展成C4.52003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬19避免過(guò)度擬合數(shù)據(jù) 過(guò)度擬合 對(duì)于一個(gè)假設(shè)，當(dāng)存在其他的假設(shè)對(duì)訓(xùn)練樣例的擬合比它差，但事實(shí)上在實(shí)例的整個(gè)分布上表現(xiàn)得卻更好時(shí)，我們說(shuō)這個(gè)假設(shè)過(guò)度擬合訓(xùn)練樣例 定義：給定一個(gè)假設(shè)空間H，一個(gè)假設(shè)hH，如果存在其他的假設(shè)hH，使得在訓(xùn)練樣例

13、上h的錯(cuò)誤率比h小，但在整個(gè)實(shí)例分布上h的錯(cuò)誤率比h小，那么就說(shuō)假設(shè)h過(guò)度擬合訓(xùn)練數(shù)據(jù)。 圖3-6的例子 2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬20避免過(guò)度擬合數(shù)據(jù)（2） 導(dǎo)致過(guò)度擬合的原因 一種可能原因是訓(xùn)練樣例含有隨機(jī)錯(cuò)誤或噪聲 當(dāng)訓(xùn)練數(shù)據(jù)沒(méi)有噪聲時(shí)，過(guò)度擬合也有可能發(fā)生，特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點(diǎn)時(shí)，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實(shí)際的目標(biāo)函數(shù)并無(wú)關(guān)系。2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬21避免過(guò)度擬合數(shù)據(jù)（3） 避免過(guò)度擬合的方

14、法 及早停止樹(shù)增長(zhǎng) 后修剪法 兩種方法的特點(diǎn) 第一種方法更直觀 第一種方法中，精確地估計(jì)何時(shí)停止樹(shù)增長(zhǎng)很困難 第二種方法被證明在實(shí)踐中更成功2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬22避免過(guò)度擬合數(shù)據(jù)（4） 避免過(guò)度擬合的關(guān)鍵 使用什么樣的準(zhǔn)則來(lái)確定最終正確樹(shù)的規(guī)模 解決方法 使用與訓(xùn)練樣例截然不同的一套分離的樣例，來(lái)評(píng)估通過(guò)后修剪方法從樹(shù)上修建節(jié)點(diǎn)的效用。 使用所有可用數(shù)據(jù)進(jìn)行訓(xùn)練，但進(jìn)行統(tǒng)計(jì)測(cè)試來(lái)估計(jì)擴(kuò)展（或修剪）一個(gè)特定的節(jié)點(diǎn)是否有可能改善在訓(xùn)練集合外的實(shí)例上的性能。 使用一個(gè)明確的標(biāo)準(zhǔn)來(lái)衡量訓(xùn)練樣例和決策樹(shù)的復(fù)雜度，當(dāng)這個(gè)編碼的長(zhǎng)度

15、最小時(shí)停止樹(shù)增長(zhǎng)。2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬23避免過(guò)度擬合數(shù)據(jù)（5） 方法評(píng)述 第一種方法是最普通的，常被稱為訓(xùn)練和驗(yàn)證集法。 可用數(shù)據(jù)分成兩個(gè)樣例集合： 訓(xùn)練集合，形成學(xué)習(xí)到的假設(shè) 驗(yàn)證集合，評(píng)估這個(gè)假設(shè)在后續(xù)數(shù)據(jù)上的精度 方法的動(dòng)機(jī)：即使學(xué)習(xí)器可能會(huì)被訓(xùn)練集合誤導(dǎo)，但驗(yàn)證集合不大可能表現(xiàn)出同樣的隨機(jī)波動(dòng) 驗(yàn)證集合應(yīng)該足夠大，以便它本身可提供具有統(tǒng)計(jì)意義的實(shí)例樣本。 常見(jiàn)的做法是，樣例的三分之二作訓(xùn)練集合，三分之一作驗(yàn)證集合。2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬24

16、錯(cuò)誤率降低修剪 將樹(shù)上的每一個(gè)節(jié)點(diǎn)作為修剪得候選對(duì)象 修剪步驟 刪除以此節(jié)點(diǎn)為根的子樹(shù)，使它成為葉結(jié)點(diǎn) 把和該節(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例的最常見(jiàn)分類賦給它 反復(fù)修剪節(jié)點(diǎn)，每次總是選取那些刪除后可以最大提高決策樹(shù)在驗(yàn)證集合上的精度的節(jié)點(diǎn) 繼續(xù)修剪，直到進(jìn)一步的修剪是有害的為止 數(shù)據(jù)分成3個(gè)子集 訓(xùn)練樣例，形成決策樹(shù) 驗(yàn)證樣例，修剪決策樹(shù) 測(cè)試樣例，精度的無(wú)偏估計(jì) 如果有大量的數(shù)據(jù)可供使用，那么使用分離的數(shù)據(jù)集合來(lái)引導(dǎo)修剪2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬25規(guī)則后修剪 從訓(xùn)練集合推導(dǎo)出決策樹(shù)，增長(zhǎng)決策樹(shù)直到盡可能好地?cái)M合訓(xùn)練數(shù)據(jù)，允許過(guò)度擬合發(fā)

17、生 將決策樹(shù)轉(zhuǎn)化為等價(jià)的規(guī)則集合，方法是為從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑創(chuàng)建一條規(guī)則 通過(guò)刪除任何能導(dǎo)致估計(jì)精度提高的前件來(lái)修剪每一條規(guī)則 按照修剪過(guò)的規(guī)則的估計(jì)精度對(duì)它們進(jìn)行排序，并按這樣的順序應(yīng)用這些規(guī)則來(lái)分類后來(lái)的實(shí)例2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬26規(guī)則后修剪（2） 例子 圖3-1的最左一條路徑 if (outlook=sunny)(Humidity=High) then PlayTennis=No 考慮刪除先行詞(outlook=sunny)和(Humidity=High) 選擇使估計(jì)精度有最大提升的步驟 考慮修剪第二個(gè)前

18、件2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬27規(guī)則后修剪（3） 規(guī)則精度估計(jì)方法 使用與訓(xùn)練集不相交的驗(yàn)證集 基于訓(xùn)練集合本身 被C4.5使用，使用一種保守估計(jì)來(lái)彌補(bǔ)訓(xùn)練數(shù)據(jù)有利于當(dāng)前規(guī)則的估計(jì)偏置 過(guò)程 先計(jì)算規(guī)則在它應(yīng)用的訓(xùn)練樣例上的精度 然后假定此估計(jì)精度為二項(xiàng)式分布，并計(jì)算它的標(biāo)準(zhǔn)差 對(duì)于一個(gè)給定的置信區(qū)間，采用下界估計(jì)作為規(guī)則性能的度量 評(píng)論 對(duì)于大的數(shù)據(jù)集，保守預(yù)測(cè)非常接近觀察精度，隨著數(shù)據(jù)集合的減小，離觀察精度越來(lái)越遠(yuǎn) 不是統(tǒng)計(jì)有效（此概念第5章介紹），但是實(shí)踐中發(fā)現(xiàn)有效2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等

19、 作者：Mitchell 講者：陶曉鵬28規(guī)則后修剪（4） 把決策樹(shù)轉(zhuǎn)化成規(guī)則集的好處 可以區(qū)分決策節(jié)點(diǎn)使用的不同上下文 消除了根節(jié)點(diǎn)附近的屬性測(cè)試和葉節(jié)點(diǎn)附近的屬性測(cè)試的區(qū)別 提高了可讀性2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬29合并連續(xù)值屬性 ID3被限制為取離散值的屬性 學(xué)習(xí)到的決策樹(shù)要預(yù)測(cè)的目標(biāo)屬性必須是離散的 樹(shù)的決策節(jié)點(diǎn)的屬性也必須是離散的 簡(jiǎn)單刪除上面第2個(gè)限制的方法 通過(guò)動(dòng)態(tài)地定義新的離散值屬性來(lái)實(shí)現(xiàn)，即先把連續(xù)值屬性的值域分割為離散的區(qū)間集合2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell

20、 講者：陶曉鵬30合并連續(xù)值屬性（2） 例子，Temperature應(yīng)該定義什么樣的基于閾值的布爾屬性 選擇產(chǎn)生最大信息增益的閾值 按照連續(xù)屬性排列樣例，確定目標(biāo)分類不同的相鄰實(shí)例 產(chǎn)生一組候選閾值，它們的值是相應(yīng)的A值之間的中間值 可以證明產(chǎn)生最大信息增益的c值位于這樣的邊界中（Fayyad1991） 通過(guò)計(jì)算與每個(gè)候選閾值關(guān)聯(lián)的信息增益評(píng)估這些候選值 方法的擴(kuò)展 連續(xù)的屬性分割成多個(gè)區(qū)間，而不是單一閾值的兩個(gè)空間2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬31屬性選擇的其他度量標(biāo)準(zhǔn) 信息增益度量存在一個(gè)內(nèi)在偏置，偏向具有較多值的屬性 避免方

21、法，其他度量，比如增益比率 增益比率通過(guò)加入一個(gè)被稱作分裂信息的項(xiàng)來(lái)懲罰多值屬性，分裂信息用來(lái)衡量屬性分裂數(shù)據(jù)的廣度和均勻性SplitInformation(S,A)=GainRatio(S,A)= 分裂信息項(xiàng)阻礙選擇值為均勻分布的屬性 問(wèn)題，當(dāng)某個(gè)SiS。解決方法：采用一些啟發(fā)式規(guī)則， 比如僅對(duì)增益高過(guò)平均值的屬性應(yīng)用增益比率測(cè)試ciiiSSSS12|log|),(),(ASmationSplitInforASGain2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬32屬性選擇的其他度量標(biāo)準(zhǔn)（2） 基于距離的度量 定義了數(shù)據(jù)劃分間的一種距離尺度

22、計(jì)算每個(gè)屬性產(chǎn)生的劃分與理想劃分間的距離 選擇最接近完美劃分的屬性 Lopez de Mantaras定義了這個(gè)距離度量，證明了它不偏向有大量值的屬性 此外 Mingers實(shí)驗(yàn)，不同的屬性選擇度量對(duì)最終精度的影響小于后修剪得程度和方法的影響2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬33缺少屬性值的訓(xùn)練樣例 例子，醫(yī)學(xué)領(lǐng)域 經(jīng)常需要根據(jù)此屬性值已知的實(shí)例來(lái)估計(jì)這個(gè)缺少的屬性值 為了評(píng)估屬性A是否是決策節(jié)點(diǎn)n的最佳測(cè)試屬性，要計(jì)算決策樹(shù)在該節(jié)點(diǎn)的信息增益Gain(S,A)。假定是S中的一個(gè)訓(xùn)練樣例，并且其屬性A的值A(chǔ)(x)未知2003.11.18

23、機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬34缺少屬性值的訓(xùn)練樣例（2） 處理缺少屬性值的 一種策略是賦給它節(jié)點(diǎn)n的訓(xùn)練樣例中該屬性的最常見(jiàn)值 另一種策略是賦給它節(jié)點(diǎn)n的被分類為c(x)的訓(xùn)練樣例中該屬性的最常見(jiàn)值 更復(fù)雜的策略，為A的每個(gè)可能值賦予一個(gè)概率，而不是簡(jiǎn)單地將最常見(jiàn)的值賦給A(x)2003.11.18機(jī)器學(xué)習(xí)-決策樹(shù)學(xué)習(xí) 譯者：曾華軍等 作者：Mitchell 講者：陶曉鵬35處理不同代價(jià)的屬性 實(shí)例的屬性可能與代價(jià)相關(guān) 優(yōu)先選擇盡可能使用低代價(jià)屬性的決策樹(shù)，僅當(dāng)需要產(chǎn)生可靠的分類時(shí)才依賴高代價(jià)屬性 通過(guò)引入一個(gè)代價(jià)項(xiàng)到屬性選擇度量中，可以使ID3算法考慮屬性代價(jià) Tan和Schlim