機器學習：算法模型：決策樹

原文鏈接：https://www.cnblogs.com/wenyi1992/p/7685131.html

【基本流程】

分類決策樹的核心思想就是在一個數據集中找到一個最優特征，然后從這個特征的選值中找一個最優候選值(這段話稍后解釋)，根據這個最優候選值將數據集分為兩個子數據集，然后遞歸上述操作，直到滿足指定條件為止。

最優特征怎么找？這個問題其實就是決策樹的一個核心問題了。我們常用的方法是更具信息增益或者信息增益率來尋找最優特征，信息增益這東西怎么理解呢！搞清這個概念我們首先需要明白熵這個東西！熵簡單的講就是說我們做一件事需要的代價，代價越高肯定就越不好了。放到機器學習的數據集中來講就是我們數據的不確定性，代價越高對應的不確定就越高，我們用決策樹算法的目的就是利用數據的一些規則來盡可能的降低數據集的不確定性。好了，有了這個思想我們要做的事就很簡單了，給定一批數據集，我們可以很容易得到它的不確定性(熵)，然后呢！我們要想辦法降低這個不確定性，我們需要挖掘數據集中有用的特征，在某個特征的限制下，我們又能得到數據集的不確定性（這個其實就是書上的條件熵），一般而言給定了一個有用的特征，數據的不確定性肯定降低了(因為有一個條件約束，比沒有條件約束效果肯定會好一點，當然你的特征沒有用，那就另說了)。我們用兩次的值作差，這個結果的含義很明了，給定了這個特征，讓我們數據集的不確定性降低了多少，當然降低的越多這個特征肯定就越好了。而我們講了這么多就是要找到那一個讓數據集不確定性降低最多的特征。我們認為這個特征是當前特征中最好的一個。

我們找到了最優特征，為什么還要找最優特征的最優候選值？其實呀，找不找主要看我們面對的問題，一般的二分類問題確實沒必要找(因為總共就兩個類)，但對于多分類問題，這個還是建議找，為什么要找呢？我們來分析一下：假如我們的某個最優特征有三個類別：我們如果不找就直接分為三個子節點了。這樣會出現一個問題，就是我們的這個分類對特征值會變得敏感，為什么這么說，我們來講一個很簡答的例子：我們平時考試規定了60分及格，這個控制對于大多數學生很好把控，因為就一個條件，相當于一個二分類。但是如果我們把條件控制嚴格一些，比如超過60分，不超過80分為優秀學生(當然有點扯蛋了)。這個控制很多學霸就不好控制了，對于多分類問題也是這個道理，如果我們一下子從父節點直接分了多個子節點，那么我們的數據肯定會對這個控制很敏感，敏感就會導致出錯。出錯不是我們希望看到的，所以我們建議對多分類問題找最優候選值來轉化為二分類問題，同樣多個二分類問題其實也是一個多分類問題，只是多了幾個遞歸過程而已。

什么時候停止？停止條件是什么？這個問題其實書上也講得很簡單，基本都是一筆帶過的，我來稍微詳細說一下：我們從問題的根源出發去想一下，我們構造一顆決策樹的目的是什么？當然是為了能在數據集上取得最好的分類效果，很好這就是一個停止標準呀！當我們檢測到數據的分類效果已經夠好了，我們其實就可以停止了。當然我們常用的是控制葉節點，比如控制葉節點的樣本數目，比如當某個子節點內樣本數目小于某一個指定值，我們就決定不再分了。還有葉節點的純度，我們規定葉節點樣本必須屬于同一類才停止，這也是一個停止條件。還有最大樹的深度，比如我們規定樹的最大深度為某一個值，當樹深度到達這個值我們也要停止。還有比如：分裂次數，最大特征數等等。總之停止條件不是死的，我們可以更具自己的問題來隨意控制，開心就好！

【屬性選擇】

信息增益——ID3

ID3算法其實就是我們一般所理解的決策樹算法，其基本步驟就是我們上面所講的步驟，這個算法的核心思想就是用信息增益來選擇最優分類特征，信息增益的公式上面也給出了，這個公式我們仔細分析一下會發現一個問題：我們需要找到gain(D,A)最大的特征，對于一個數據集entropy(D)是給定的，也就是說我們需要entropy(D,A)最小，意思就是我們所選的特征是那些分完后子節點的純度最高的特征，什么樣的特征分完后子節點的特征純度比較高(熵比較小)，該特征的子類別很多，即可取值很多的這一類特征。總結一下就是信息增益偏向于去那些擁有很多子類的特征。這也是這個算法的一大致命缺點，任何帶有主觀偏向性的算法都不是一個好的算法，當然ID3算法的另一個缺點也顯而易見，它只能處理那些分類的特征，對于連續值特征毫無辦法（其實我們可以人為的把連續屬性給離散化，但是人為必然會導致可能不準確）。

增益率——C4.5

因此就有了下面的這個算法

C4.5是對ID3算法的一個改進，主要改進點就是解決了ID3的幾個缺點。首先C4.5算法用的是信息增益率來代替ID3中的信息增益。從表達式可以看出來，這么做其實就是弱化那些偏向，讓選擇最優特征時更加公平。
另外C4.5的改進就是可以處理連續值（這個方法其實和上面我提到的連續值離散化很類似，可以理解為單點逐一離散化），具體步驟如下：
1.首先對于連續值屬性的值進行排序(A1,A2......An);
2.我們可以在每兩個值之間取一個點，用這個點就可以把該組連續值分為兩部分，比如我們去一個點a1($A1<a1<A2$),則小于a1的部分（A1）大于a1的部分（A2......An）。但是這個a1好嗎？不知道呀！那我們loop一下所有這樣的a(共有n-1個)，每一個ai我們可以算出分裂前后的信息增益率，然后我們求一個max即可。很簡單吧！思路很好，但是呀很顯然有個問題，時間開銷有點大。
3.缺失值的處理，ID3不能直接處理(需要我們人工處理，比如單獨賦值或賦一個平均值)，C4.5給出了一個很優雅的方式，為什么說優雅，這樣講吧！我們每一個特征的取值都有若干個，根據訓練集每個可能的取值都有一個概率，我們用這個概率來表示這個確實值得可能取值。這樣就顯得很合理了。