決策樹(shù)學(xué)習(xí)
決策樹(shù)學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一，它是一種逼近離散值函數(shù)的方法，對(duì)噪聲數(shù)據(jù)又很好地健壯性且能夠?qū)W習(xí)析取表達(dá)式屑宠。
下圖是一顆典型的學(xué)習(xí)決策樹(shù)
所謂能夠?qū)W習(xí)析取表達(dá)式是指阱表，根據(jù)這顆決策樹(shù)我們可以寫(xiě)出與之對(duì)應(yīng)的表達(dá)式：
(Outlook=Sunny ^ Humidity=Normal) V (Outlook=Overcast) V (Outlook=Rain ^ Wind=Weak)
決策樹(shù)學(xué)習(xí)最適合具有以下特征的問(wèn)題：
- 實(shí)例是由“屬性-值”對(duì)（pair）表示饺窿；（例如溫度Temperatue用值Hot鸿捧、Mild嗤军、Cold表示而不是連續(xù)的數(shù)值）
- 目標(biāo)函數(shù)具有離散的輸出值靶瘸；（例如給每一個(gè)實(shí)例賦予一個(gè)bool類(lèi)型的分類(lèi)寝优，如yes和no）
- 可能需要析取的描述条舔；（上文已描述）
- 訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤；（決策樹(shù)學(xué)習(xí)對(duì)錯(cuò)誤有很好的健壯性）
- 訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例乏矾。
ID3算法
如圖一所示孟抗，該決策樹(shù)把屬性O(shè)utlook作為樹(shù)的根節(jié)點(diǎn)被第一個(gè)測(cè)試，而之后是Humidity和Wind屬性钻心，為什么凄硼？測(cè)試屬性的先后順序有什么關(guān)系和標(biāo)準(zhǔn)？決策樹(shù)算法的核心就是要解決這個(gè)問(wèn)題捷沸。
ID3是一種自頂向下增長(zhǎng)樹(shù)的貪婪算法摊沉，在每個(gè)結(jié)點(diǎn)選取能最好地分類(lèi)樣例的屬性。繼續(xù)這個(gè)過(guò)程指導(dǎo)這棵樹(shù)能完美分類(lèi)訓(xùn)練樣例痒给，或所有的屬性都已被使用過(guò)说墨。
ID3算法概要：
該算法描述并沒(méi)有解決其核心問(wèn)題：在選取樹(shù)的每個(gè)結(jié)點(diǎn)時(shí)，哪個(gè)屬性是最佳的分類(lèi)屬性苍柏？
衡量屬性?xún)r(jià)值的一個(gè)好的定量標(biāo)準(zhǔn)是什么呢尼斧？這里定義一個(gè)統(tǒng)計(jì)屬性，稱(chēng)為“信息增益”（information gain）试吁，用來(lái)衡量給定的屬性區(qū)分訓(xùn)練樣例的能力棺棵。ID3算法在增長(zhǎng)樹(shù)的每一步使用這個(gè)信息增益標(biāo)準(zhǔn)從候選屬性中選擇屬性。
信息增益
在學(xué)習(xí)信息增益之前熄捍，先來(lái)了解一個(gè)信息論中的一個(gè)名詞：熵（entropy）烛恤。
熵刻畫(huà)了任意樣例集的純度，它的取值為0-1余耽。舉個(gè)例子缚柏，一個(gè)箱子里有10個(gè)水果，或蘋(píng)果或梨子宾添，如果10個(gè)水果都是蘋(píng)果或都是梨子船惨，那說(shuō)明水果的純度最高，用熵來(lái)描述就是熵最低（0）缕陕，如果5個(gè)蘋(píng)果5個(gè)梨子粱锐，那么純度最低，用熵來(lái)描述就是熵最高（1）扛邑。
信息論中熵的另一種解釋更有利于理解：熵確定了要編碼集合S中任意成員（即以均勻地概率隨機(jī)抽出的一個(gè)成員）的分類(lèi)所需要的最少二進(jìn)制位數(shù)怜浅。
需要進(jìn)一步了解可移步[百度百科-信息熵]
給定樣例集S，計(jì)算對(duì)S進(jìn)行布爾分類(lèi)的熵的公式為：
我們定義0log0為0。
其中恶座，p+是在S中正例的比例搀暑，p-是在S中反例的比例，參考上述水果的例子跨琳，假設(shè)蘋(píng)果為正例自点，蘋(píng)果個(gè)數(shù)為10，梨子個(gè)數(shù)為0時(shí)脉让，1log1=0, 0log0=0桂敛，所以熵為0。如果蘋(píng)果梨子各5個(gè)溅潜，那么p+ = 0.5, p- = 0.5术唬，代入公式，熵為1滚澜。
一般的粗仓，如果目標(biāo)屬性具有c個(gè)不同的值，那么S相對(duì)于c個(gè)狀態(tài)的分類(lèi)的熵定義為：
那么设捐，信息增益是什么意思呢借浊？簡(jiǎn)單地說(shuō)，一個(gè)屬性的信息增益就是由于這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低挡育。
舉例來(lái)說(shuō)巴碗，一個(gè)水果是一個(gè)樣例朴爬，如果要驗(yàn)證該水果是蘋(píng)果還是梨子即寒，最準(zhǔn)確地方法是通過(guò)驗(yàn)證該水果的基因。但是水果本身的顏色召噩、形狀母赵、口味等幾個(gè)屬性可以幫助我們對(duì)該水果進(jìn)行分類(lèi)，那么具滴，哪個(gè)屬性最有助于判斷這個(gè)水果是蘋(píng)果還是梨子呢凹嘲？如果因?yàn)檫@個(gè)屬性可以將水果進(jìn)行蘋(píng)果/梨子分類(lèi)的熵降低，那么降低的熵的量就是信息增益构韵，當(dāng)然周蹭，如果信息增益越大（即降低的熵越多），那么這個(gè)屬性就是最佳屬性疲恢。
更精確的講凶朗，一個(gè)屬性A相對(duì)樣例集合S的信息增益Gain(S, A)被定義為：
對(duì)水果的幾個(gè)屬性（顏色、形狀显拳、口味..）依次根據(jù)此公式計(jì)算信息增益棚愤，然后再互相比較，選擇信息增益最大的屬性為最佳屬性。
所以宛畦，信息增益正是ID3算法增長(zhǎng)樹(shù)的每一步中選取最佳屬性的度量標(biāo)準(zhǔn)瘸洛。
