決策樹(Decision Tree)
定義：
決策樹（decision tree）是一個樹結(jié)構(gòu)（可以是二叉樹或非二叉樹）。其每個非葉節(jié)點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節(jié)點存放一個類別。使用決策樹進行決策的過程就是從根節(jié)點開始，測試待分類項中相應(yīng)的特征屬性，并按照其值選擇輸出分支，直到到達葉子節(jié)點，將葉子節(jié)點存放的類別作為決策結(jié)果。
-
參考示例：
女兒：多大年紀(jì)了？
母親：26。
女兒：長的帥不帥？
母親：挺帥的。
女兒：收入高不？
母親：不算很高，中等情況。
女兒：是公務(wù)員不？
母親：是，在稅務(wù)局上班呢。
女兒：那好，我去見見。
graph TD
A((年齡)) --> |<=30| C((長相))
A((年齡)) --> |>30| B((不見))
C --> |帥或中等|E((收入))
C --> |丑|D((不見))
E --> |高|F((見))
E --> |中等|G((公務(wù)員))
E --> |低|H((不見))
G --> |不是|I((不見))
G --> |是|J((見))
- 上面是一個簡單的決策樹示例，可以看出決策樹比較直觀，容易讓人理解
決策樹的構(gòu)造
不同于貝葉斯算法，決策樹的構(gòu)造過程不依賴領(lǐng)域知識，它使用屬性選擇度量來選擇將元組最好地劃分成不同的類的屬性。所謂決策樹的構(gòu)造就是進行屬性選擇度量確定各個特征屬性之間的拓?fù)浣Y(jié)構(gòu)。
構(gòu)造決策樹的關(guān)鍵步驟是分裂屬性。所謂分裂屬性就是在某個節(jié)點處按照某一特征屬性的不同劃分構(gòu)造不同的分支，其目標(biāo)是讓各個分裂子集盡可能地“純”。盡可能“純”就是盡量讓一個分裂子集中待分類項屬于同一類別。分裂屬性分為三種不同的情況：
1、屬性是離散值且不要求生成二叉決策樹。此時用屬性的每一個劃分作為一個分支。
2、屬性是離散值且要求生成二叉決策樹。此時使用屬性劃分的一個子集進行測試，按照“屬于此子集”和“不屬于此子集”分成兩個分支。
3、屬性是連續(xù)值。此時確定一個值作為分裂點split_point，按照>split_point和<=split_point生成兩個分支。
構(gòu)造決策樹的關(guān)鍵性內(nèi)容是進行屬性選擇度量，屬性選擇度量是一種選擇分裂準(zhǔn)則，是將給定的類標(biāo)記的訓(xùn)練集合的數(shù)據(jù)劃分D“最好”地分成個體類的啟發(fā)式方法，它決定了拓?fù)浣Y(jié)構(gòu)及分裂點split_point的選擇。
屬性選擇度量算法有很多，一般使用自頂向下遞歸分治法，并采用不回溯的貪心策略。這里介紹ID3和C4.5兩種常用算法。
信息增益
定義：劃分信息之前、之后發(fā)生的變化叫做信息增益
度量方式：香農(nóng)熵、熵（entropy）
公式：
$H(D)=-\sum_{i=1}^mp_ilog_2(p_i)$$p_i$表示第i個類別在整個訓(xùn)練集中出現(xiàn)的概率，可以用屬于此類別元素的數(shù)量除以訓(xùn)練元組元素總數(shù)量作為估計
ID3算法
從信息論知識中我們直到，期望信息越小，信息增益越大，從而純度越高。
以信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進行分裂。
ID4.5算法
ID3算法存在一個問題，就是偏向于多值屬性，例如，如果存在唯一標(biāo)識屬性ID，則ID3會選擇它作為分裂屬性，這樣雖然使得劃分充分純凈，但這種劃分對分類幾乎毫無用處。
ID3的后繼算法C4.5使用增益率（gain ratio）的信息增益擴充，試圖克服這個偏倚。
補充說明
- 如果屬性用完了怎么辦
在決策樹構(gòu)造過程中可能會出現(xiàn)這種情況：所有屬性都作為分裂屬性用光了，但有的子集還不是純凈集，即集合內(nèi)的元素不屬于同一類別。在這種情況下，由于沒有更多信息可以使用了，一般對這些子集進行“多數(shù)表決”，即使用此子集中出現(xiàn)次數(shù)最多的類別作為此節(jié)點類別，然后將此節(jié)點作為葉子節(jié)點。
關(guān)于剪枝
在實際構(gòu)造決策樹時，通常要進行剪枝，這時為了處理由于數(shù)據(jù)中的噪聲和離群點導(dǎo)致的過分?jǐn)M合問題。剪枝有兩種：
先剪枝——在構(gòu)造過程中，當(dāng)某個節(jié)點滿足剪枝條件，則直接停止此分支的構(gòu)造。
后剪枝——先構(gòu)造完成完整的決策樹，再通過某些條件遍歷樹進行剪枝。
關(guān)于剪枝的具體算法這里不再詳述，有興趣的可以參考相關(guān)文獻。
