決策樹(shù):分類(lèi)決策樹(shù)模型使一種對(duì)實(shí)例進(jìn)行分類(lèi)的樹(shù)形結(jié)構(gòu)。決策樹(shù)由節(jié)點(diǎn)和有向邊組成，節(jié)點(diǎn)有兩種類(lèi)型：內(nèi)部節(jié)點(diǎn)和葉節(jié)點(diǎn)。內(nèi)部節(jié)點(diǎn)表示一個(gè)特征和屬性，葉節(jié)點(diǎn)表示一個(gè)類(lèi)。
特征選擇:特征選擇在于選取對(duì)訓(xùn)練數(shù)據(jù)具有分類(lèi)能力的特征。通常特征選擇的準(zhǔn)則是信息增益或信息增益比。
信息熵:熵是表示隨機(jī)變量不確定性的度量。由定義可知，熵只依賴(lài)于X的分布，而與X的取值無(wú)關(guān)。熵越大，隨機(jī)變量的不確定性越大。
信息熵.png
條件熵:條件熵H(Y|X)表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性。
條件熵.png
信息增益:
信息增益.png
信息增益比:信息增益值的大小是相對(duì)于訓(xùn)練數(shù)據(jù)集而言的，沒(méi)有絕對(duì)意義。在分類(lèi)問(wèn)題困難時(shí)，也就是說(shuō)訓(xùn)練數(shù)據(jù)集的經(jīng)驗(yàn)熵大的時(shí)候，信息增益值就會(huì)偏大。反之，則偏小。使用信息增益比，可以對(duì)這一問(wèn)題進(jìn)行校正。
信息增益比.png
決策樹(shù)的生成
- ID3算法：在決策樹(shù)各個(gè)節(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則選擇特征，遞歸構(gòu)建決策樹(shù)。該算法只有決策樹(shù)的生成，所以該算法生成的樹(shù)容易產(chǎn)生過(guò)擬合。
- C4.5算法：與ID3相似，在生成決策數(shù)的過(guò)程中，用信息增益比來(lái)選擇特征。
