機器學習算法之決策樹

rushuang3818 8年前發布 | 13K 次閱讀決策樹算法 Java開發

前言

決策樹是一種簡單高效并且具有強解釋性的模型，廣泛應用于數據分析領域。其本質是一顆由多個判斷節點組成的樹，如：

決策樹

在使用模型進行預測時，根據輸入參數依次在各個判斷節點進行判斷游走，最后到葉子節點即為預測結果。

如何構造決策樹

決策樹算法的核心是通過對數據的學習，選定判斷節點，構造一顆合適的決策樹。

假設我們從用戶行為日志中整理出如下數據：

原始數據

我們的目的是要利用這些數據，訓練決策樹模型，模型訓練好后，我們就可以通過任意給定的用戶來源網站、位置、是否閱讀過 FAQ、瀏覽網頁數信息，預測該用戶是否會進行付費以及付費類型，供運營使用。

選擇合適的拆分條件

我們知道決策樹是由一個個判斷節點組成，每經過一個判斷節點數據就會被拆分一次。上面數據中有4種屬性，每種屬性下面有多種值，我們可以按位置是否來自「浙江」進行拆分，拆分結果為：

按是否來自「浙江」拆分結果

我們「拍腦袋」進行了一次拆分，到底這么拆分合不合適，是不是最佳，我們需要量化指標來進行評價，在決策樹算法中，我們通過 基尼不純度 或者熵來對一個集合進行的有序程度進行量化，然后引入 信息增益 概念對一次拆分進行量化評價。下面依次介紹。

基尼不純度

基尼不純度是指將來自集合中的某種結果隨機應用于集合中某一數據項的預期誤差率。如何集合中的每一個數據項都屬于同一分類，那么推測的結果總會是正確的，因此誤差率是 0；如果有 4 種可能的結果均勻分布在集合內，出錯可能性是75%，基尼不純度為 0.75。該值越高，說明拆分的越不理想，如果該值為 0，說明完美拆分。java 實現代碼如下：

public static float getCiniimpurity(String[] rows){
        float total = rows.length;
        //將[a,a,b,c]轉化成[2,1,1]
        Integer[] uniqueRows = getUniqueRows(rows);
        float score = 0.0f;
        for(int k1=0;k1<uniqueRows.length;k1++){
            float p1 = uniqueRows[k1]/total;
            for(int k2=0;k2<uniqueRows.length;k2++){
                if(k2 == k1) continue;
                float p2 = uniqueRows[k2]/total;
                score += p1 * p2;
            }
        }
        return score;
    }

熵

熵是信息論中的概念，用來表示集合的無序程度，熵越大表示集合越混亂，反之則表示集合越有序。熵的計算公式為：

E = -P * log ₂ P

java 代碼實現如下：

public static double getEntropy(String[] rows){
        float total = rows.length;
        //將[a,a,b,c]轉化成[2,1,1]
        Integer[] uniqueRows = getUniqueRows(rows);
        double ent = 0.0;
        for(int i=0;i<uniqueRows.length;i++){
            float p = uniqueRows[i]/total;
            ent = ent - p * (Math.log(p)/Math.log(2));
        }
        return ent;
    }

基尼不純度與熵對比

兩者主要區別在于，熵到達峰值的過程相對慢一些。因此熵對混亂集合的「判罰」往往更重一些。通常情況下，熵的使用更加頻繁。

信息增益

假設集合 U，一次拆分后變為了兩個集合 u ₁ 和 u ₂ ，則有：

信息增益 = E(U) - (P _u1 x E(u ₁ ) + P _u2 x E(u ₂ ))

E 可以是基尼不純度或熵。

使用 P _u1 和 P _u2 是為了得到拆分后兩個集合基尼不純度或熵的加權平均，其中 :

P _u1 = Size(u1) / Size(U)
P _u2 = Size(u2) / Size(U)

信息增益越大，說明整個集合從無序到有序的速度越快，本次拆分越有效。

構造決策樹

我們已經可以通過信息增益量化一次拆分的結果好壞，下一步就是構造決策樹，主要步驟如下：

遍歷每個決策條件（如：位置、來源網站），對結果集進行拆分
計算該決策條件下，所有可能的拆分情況的信息增益，信息增益最大的拆分為本次最優拆分
遞歸執行1、2兩步，直至信息增益<=0

執行完上述步驟后，就構造出了一顆決策樹，如圖：

決策樹

決策樹剪枝

為什么要剪枝

訓練出得決策樹存在過度擬合現象——決策樹過于針對訓練的數據，專門針對訓練集創建出來的分支，其熵值可能會比真實情況有所降低。

如何剪枝

人工設置一個信息增益的閥值，自下而上遍歷決策樹，將信息增益低于該閥值的拆分進行合并

處理缺失數據

決策樹模型還有一個很大的優勢，就是可以容忍缺失數據。如果決策樹中某個條件缺失，可以按一定的權重分配繼續往以后的分支走，最終的結果可能有多個，每個結果又一定的概率，即：

最終結果=某個分支的結果 x 該分支的權重(該分支下的結果數/總結果數)

處理數值型數據

決策樹主要解決分類問題（結果是離散數據），如果結果是數字，不會考慮這樣的事實：有些數字相差很近，有些數字相差很遠。為了解決這個問題，可以用方差來代替熵或基尼不純度。

結語

本文簡單介紹了決策樹算法，該算法雖然簡單，但是在很多場景能取得非常好的效果，值得讀者一試。另外，從決策樹發展出了更為高級復雜的 隨機森林 ，如果有興趣讀者可以去深入了解。

來自：http://www.jianshu.com/p/6eecdeee5012

本文由用戶 rushuang3818 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1474254542753.html

決策樹算法 Java開發