算法模型——决策树
決策樹屬于監(jiān)督學(xué)習(xí)，是一種預(yù)測模型。
1. 概念
決策樹(Decision Tree）是在已知各種情況發(fā)生概率的基礎(chǔ)上，通過構(gòu)成決策樹來求取凈現(xiàn)值的期望值大于等于零的概率，評價(jià)項(xiàng)目風(fēng)險(xiǎn)，判斷其可行性的決策分析方法，是直觀運(yùn)用概率分析的一種圖解法。
決策樹是一種樹形結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示一個(gè)屬性上的測試，每個(gè)分支代表一個(gè)測試輸出，每個(gè)葉節(jié)點(diǎn)代表一種類別。
樹模型和線性模型有什么區(qū)別呢？最重要的是，樹形模型是一個(gè)一個(gè)特征進(jìn)行處理，線性模型是所有特征給予權(quán)重相加得到一個(gè)新的值。
決策樹與邏輯回歸的分類區(qū)別也在于此，邏輯回歸是將所有特征變換為概率后，通過大于某一概率閾值的劃分為一類，小于某一概率閾值的為另一類；而決策樹是對每一個(gè)特征做一個(gè)劃分。另外邏輯回歸只能找到線性分割（輸入特征x與logit之間是線性的，除非對x進(jìn)行多維映射），而決策樹可以找到非線性分割。
而樹形模型更加接近人的思維方式，可以產(chǎn)生可視化的分類規(guī)則，產(chǎn)生的模型具有可解釋性（可以抽取規(guī)則）。樹模型擬合出來的函數(shù)其實(shí)是分區(qū)間的階梯函數(shù)。
決策樹學(xué)習(xí)：采用自頂向下的遞歸的方法，基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹，到葉子節(jié)點(diǎn)處熵值為0（葉節(jié)點(diǎn)中的實(shí)例都屬于一類）。
2. 基礎(chǔ)理論
1. 信息熵
信息熵H(X)、聯(lián)合熵H(X,Y)、條件熵H(X|Y)、互信息I(X,Y)之間關(guān)系如圖示：
2. 算法思想
基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹，到葉子節(jié)點(diǎn)處的熵值為零，此時(shí)每個(gè)葉子節(jié)點(diǎn)中的實(shí)例都屬于同一類。例根據(jù)多個(gè)屬性來判斷瓜屬于好瓜還是壞瓜的結(jié)論，圖示如下：
3. 決策樹 ID3算法
使用信息增益作為不純度，核心思想是以信息增益度量屬性選擇，選擇分裂后的信息增益最大的，也就是熵在分裂前后差值最大的屬性進(jìn)行分裂。
根據(jù)log(x)的函數(shù)可知，p值越小，熵越大，所以當(dāng)分組完全是會出現(xiàn)p=0此時(shí)熵最大，概率為0說明已經(jīng)最純了。
表中S、M和L分別表示小、中和大。
設(shè)L、F、H和R表示日志密度、好友密度、是否使用真實(shí)頭像和賬號是否真實(shí)，試用ID3算法構(gòu)造決策樹。
解：設(shè)D為10個(gè)樣本集，其中決策屬性（真實(shí)賬戶/R）有7個(gè)YES、3個(gè)NO。決策屬性信息熵為：
如果按照日志密度來分類：計(jì)算日志密度熵值，日志密度分為3類S，L，M
其中L分類，樣本總數(shù)10，L類3，L類中假賬號0 真實(shí)賬號3
所以：
所以gain(L) = 0.876-0.603 = 0.273
同理計(jì)算好友密度信息增益：
計(jì)算真實(shí)頭像的信息增益：
因?yàn)楹糜衙芏?#xff08;F）具有最大的信息增益（好友密度信息熵最小，最易分割），所以第一次分裂選擇好友密度F為分裂屬性（實(shí)際中如果特征非常多是隨機(jī)選擇一些特征然后計(jì)算后選取的不能遍歷所有情況），分裂后的結(jié)果如下：
圖中：按好友密度（F）分割樹，水平M和L為單一水平?jīng)Q策屬性分支（樹葉），沒有必要繼續(xù)分割。水平S包含決策屬性的不同水平，應(yīng)該繼續(xù)分割。待分割決策信息表為：
此時(shí)，設(shè)D為4個(gè)樣本集，其中決策屬性（真實(shí)賬戶/R）有1個(gè)YES、3個(gè)NO。決策屬性信息熵為：
日志密度屬性期望信息熵為：
真實(shí)頭像屬性期望信息熵為：
因?yàn)槿罩久芏?#xff08;L）具有最大的信息增益，所以第二次分裂選擇日志密度（L）為分裂屬性，分裂后的結(jié)果如下圖表示：
圖中，日志密度為M時(shí)，無法做出判斷、也無法繼續(xù)進(jìn)行分裂。至此，決策樹構(gòu)建完畢。
設(shè)某人在SNS社區(qū)中的好友密度為L或M，無論其它屬性水平取值如何，均可判定為是真實(shí)賬戶；如果某人在SNS社區(qū)中的好友密度為S、日志密度也為S，可判定為是虛假賬戶；如果某人在SNS社區(qū)中的好友密度為S、日志密度為M，應(yīng)根據(jù)真實(shí)頭像信息做出判斷，由于樣本過少，無法繼續(xù)進(jìn)行。
4. 決策樹 C4.5算法
使用信息增益率作為不純度。
ID3算法是決策樹的一個(gè)經(jīng)典的構(gòu)造算法，但I(xiàn)D3算法也存在一些問題，比較突出的缺陷是信息增益的計(jì)算依賴于特征水平較多的特征，而屬性取值最多的屬性并不一定最優(yōu)。例如，投擲一枚分幣和一個(gè)色子這兩個(gè)隨機(jī)試驗(yàn)，所有可能的期望信息熵為：
通過信息熵的定義可知，在給定特征水平數(shù)條件下，各水平發(fā)生概率相等（如擲篩子6個(gè)數(shù)字發(fā)生的概率都為1/6。期望信息熵最大。所以，當(dāng)決策信息中某個(gè)變量特征水平較多時(shí)，ID3算法按信息增益指標(biāo)往往會選擇該變量或?qū)傩宰鰹榉指罟?jié)點(diǎn)。
I、“分裂信息”公式
C4.5算法首先定義了“分裂信息”，其定義可以表示成：
II、增益率
III、分裂信息和增益率計(jì)算實(shí)例
在ID3算法案例中（SNS社區(qū)中不真實(shí)賬號檢測），決策屬性信息熵為：
把決策屬性替換成其它屬性，即為各屬性分裂信息熵。
日志密度分裂信息：
好友密度分裂信息：
真實(shí)頭像分裂信息：
由前面ID3算法已知，
各屬性增益率為，
由上述計(jì)算結(jié)果可知“好友密度”在屬性中具有最大的信息增益比，取“好友密度”為分割屬性，引出一個(gè)分枝，樣本按此劃分。對引出的每一個(gè)分枝再用此分類法進(jìn)行分類，再引出分枝。
某屬性的信息增益除以分裂信息，消除了屬性水平數(shù)量多少的影響，使得分裂屬性的選擇更加合理。
5. 分類回歸樹(CART)模型
CART分類樹算法使用基尼系數(shù)函數(shù)作為不純度，基尼系數(shù)越小，則不純度越低，特征越好。
在分類問題中，假設(shè)有K個(gè)類別，第k個(gè)類別的概率為p_{k} ,則基尼系數(shù)為：
對于給定的樣本D（以下“D”處均為錯誤，應(yīng)為R），假設(shè)有K個(gè)類別，第k個(gè)類別的數(shù)量為C_{k} ，則樣本的基尼系數(shù)為:
特別的，對于樣本D,如果根據(jù)特征A的某個(gè)值a,把D分成D1和D2兩部分，則在特征A的條件下，D的基尼系數(shù)為：
回到上面的例子：
同理得：
因?yàn)長具有最小的基尼系數(shù)，所以第一次分裂選擇L為分裂屬性。
再遞歸使用這個(gè)方法計(jì)算子節(jié)點(diǎn)的分裂屬性，最終就可以得到整個(gè)決策樹。
6. 評價(jià)
1. 對比
-
決策樹與邏輯回歸
-
決策樹三種方法對比
ID3 傾向于選擇水平數(shù)量較多的變量，可能導(dǎo)致訓(xùn)練得到一個(gè)龐大且深度淺的樹；另外輸入變量必須是分類變量（連續(xù)變量必須離散化）；最后無法處理空值。
C4.5 選擇了信息增益率替代信息增益。
CART 以基尼系數(shù)替代熵,最小化不純度而不是最大化信息增益。
2. 優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
- 易于理解和實(shí)現(xiàn)
- 數(shù)據(jù)準(zhǔn)備簡單，能夠同時(shí)處理數(shù)據(jù)型和常規(guī)型屬性，在相對短的時(shí)間內(nèi)能夠?qū)Υ笮蛿?shù)據(jù)源做出可行且效果良好的結(jié)果
- 易于通過靜態(tài)測試來對模型進(jìn)行評測，可以測定模型可信度；如果給定一個(gè)觀察的模型，那么根據(jù)所產(chǎn)生的決策樹很容易推出相應(yīng)的邏輯表達(dá)式
缺點(diǎn)
- 對連續(xù)性的字段比較難預(yù)測
- 對有時(shí)間順序的數(shù)據(jù)，需要很多預(yù)處理的工作
- 當(dāng)類別太多時(shí)，錯誤可能就會增加的比較快
- 一般的算法分類的時(shí)候，只是根據(jù)一個(gè)字段來分類
參考原文鏈接
https://www.jianshu.com/p/d0a6fabd796c
https://www.jianshu.com/p/b7d71478370d
總結(jié)
- 上一篇： 广工Anyview数据结构习题
- 下一篇： 腾讯无线副总李颖：腾讯QQ游戏无线平台将