Brett Lantz在R中使用C5.0算法實現(xiàn)決策樹
- 來源 | 愿碼(ChainDesk.CN)內容編輯
- 愿碼Slogan | 連接每個程序員的故事
- 網(wǎng)站 | http://chaindesk.cn
- 愿碼愿景 | 打造全學科IT系統(tǒng)免費課程村刨，助力小白用戶告抄、初級工程師0成本免費系統(tǒng)學習、低成本進階嵌牺，幫助BAT一線資深工程師成長并利用自身優(yōu)勢創(chuàng)造睡后收入打洼。
- 官方公眾號 | 愿碼 | 愿碼服務號 | 區(qū)塊鏈部落
- 免費加入愿碼全思維工程師社群 | 任一公眾號回復“愿碼”兩個字獲取入群二維碼
本文閱讀時長：9min
決策樹學習者是強大的分類器，它利用樹結構來模擬特征和潛在結果之間的關系逆粹。這種結構之所以得名募疮，是因為它反映了文字樹在寬闊的樹干上開始的方式，并且當它向上延伸時分裂成更窄的樹枝僻弹。以同樣的方式阿浓，決策樹分類器使用分支決策的結構，其將示例引導到最終預測的類值蹋绽。
決策樹有很多實現(xiàn)芭毙，但最著名的是C5.0算法。該算法由計算機科學家J. Ross Quinlan開發(fā)卸耘，作為其先前算法C4.5的改進版本（C4.5本身是對其迭代二分法3（ID3）算法的改進）退敦。雖然Quinlan向商業(yè)客戶銷售C5.0，但該算法的單線程版本的源代碼已公開蚣抗，因此已被納入諸如R等程序中侈百。
C5.0決策樹算法
C5.0算法已經(jīng)成為生成決策樹的行業(yè)標準，因為它可以直接開箱即用地解決大多數(shù)類型的問題翰铡。與其他高級機器學習模型相比 设哗，C5.0構建的決策樹通常表現(xiàn)得差不多但更容易理解和部署。此外两蟀，如下表所示网梢，算法的弱點相對較小，可以在很大程度上避免赂毯。
優(yōu)勢
- 一種通用分類器战虏，可以很好地解決許多類型的問題。
- 高度自動化的學習過程党涕，可以處理數(shù)字或名義特征烦感，以及缺少數(shù)據(jù)。
- 不包括不重要的功能膛堤。
- 可以在小型和大型數(shù)據(jù)集上使用手趣。
- 在沒有數(shù)學背景的情況下可以解釋的模型中的結果（對于相對較小的樹）。
- 比其他復雜模型更有效。
弱點
- 決策樹模型通常偏向于具有大量級別的特征的分裂绿渣。
- 很容易過度裝配或不適合模型朝群。
- 由于依賴于軸并行分割，可能無法對某些關系建模中符。
- 訓練數(shù)據(jù)的微小變化可能導致決策邏輯發(fā)生很大變化姜胖。
- 大樹很難解釋，他們做出的決定似乎違反直覺淀散。
為了簡單起見右莱，我們早期的決策樹示例忽略了機器如何采用分而治之策略所涉及的數(shù)學問題。讓我們更詳細地探討這一點档插，以研究這種啟發(fā)式方法在實踐中如何運作慢蜓。
選擇最佳分割
決策樹將面臨的第一個挑戰(zhàn)是確定要拆分的特征。在前面的示例中郭膛，我們尋找一種分割數(shù)據(jù)的方法胀瞪，使得生成的分區(qū)包含主要包含單個類的示例。示例子集僅包含單個類的程度稱為純度饲鄙，而僅由單個類組成的任何子集稱為純凄诞。
可以使用各種純度測量來識別最佳決策樹分裂候選者。C5.0使用熵忍级，這是一種借鑒信息理論的概念帆谍，用于量化一組類值中的隨機性或無序性。具有高熵的集合非常多樣化轴咱，并且提供關于可能也屬于集合的其他項目的很少信息汛蝙，因為沒有明顯的共性。決策樹希望找到減少熵的分裂朴肺，最終增加組內的同質性窖剑。
通常，熵以比特來度量戈稿。如果只有兩個可能的類西土，則熵值的范圍可以從0到1.對于n個類，熵范圍從0到log 2 （n）鞍盗。在每種情況下需了，最小值表示樣本是完全同質的，而最大值表示數(shù)據(jù)盡可能多樣化般甲，并且沒有組具有甚至小的多個肋乍。
在數(shù)學概念中，熵被指定為：
在該公式中敷存，對于給定的數(shù)據(jù)段（S）墓造，術語c指的是類級別的數(shù)量，并且p i 指的是落入級別級別i的值的比例。例如觅闽，假設我們有兩個類的數(shù)據(jù)分區(qū)：紅色（60％）和白色（40％）帝雇。我們可以將熵計算為：
> -0.60 * log2(0.60) - 0.40 * log2(0.40)
[1] 0.9709506
我們可以想象所有可能的兩級安排的熵。如果我們知道一個類中的例子的比例是x谱煤，那么另一個類中的比例是（1-x）摊求。使用curve（）函數(shù)禽拔，我們可以繪制x的所有可能值的熵：
> curve(-x * log2(x) - (1 - x) * log2(1 - x),
col = "red", xlab = "x", ylab = "Entropy", lwd = 4)
如下圖：
如在x = 0.50處的熵峰值所示刘离，50-50分裂導致最大熵。隨著一個類越來越主導另一個類睹栖，熵減少到零硫惕。
為了使用熵來確定要分割的最佳特征，該算法計算由于對每個可能特征的分割而導致的同質性變化野来，該度量被稱為信息增益恼除。特征F的信息增益被計算為分割（S 1）之前的片段中的熵與分割（S 2）產生的分區(qū)之間的差異：
一個復雜的問題是，在拆分之后曼氛，數(shù)據(jù)被分成多個分區(qū)豁辉。因此，計算熵（S 2 ）的函數(shù)需要考慮所有分區(qū)的總熵舀患。它通過根據(jù)落入該分區(qū)的所有記錄的比例對每個分區(qū)的熵進行加權來實現(xiàn)此目的徽级。這可以在公式中說明如下：
簡單來說，由分割產生的總熵是n個分區(qū)中的每一個的熵的總和聊浅，其由落入分區(qū)（w i）中的示例的比例加權餐抢。
信息增益越高，在對該特征進行拆分后創(chuàng)建同類組的功能就越好低匙。如果信息增益為零旷痕，則不會減少用于分割此特征的熵。另一方面顽冶，最大信息增益等于分割之前的熵欺抗。這意味著拆分后的熵為零，這意味著拆分產生完全同質的組强重。
以前的公式假設名義特征佩迟，但決策樹也使用信息增益來分割數(shù)字特征。為此竿屹，通常的做法是測試將值劃分為大于或小于閾值的組的各種拆分报强。這會將數(shù)字特征縮減為兩級分類功能，以便像往常一樣計算信息增益拱燃。為分割選擇產生最大信息增益的數(shù)字切割點秉溉。
注意：盡管它被C5.0使用，但信息增益并不是可用于構建決策樹的唯一分裂標準。其他常用標準是基尼指數(shù)召嘶，卡方統(tǒng)計量和增益比父晶。
修剪決策樹
如前所述，決策樹可以繼續(xù)無限增長弄跌，選擇拆分功能并劃分為更小和更小的分區(qū)甲喝，直到每個示例完全分類或算法耗盡要分離的功能。但是铛只，如果樹長得過大埠胖，那么它做出的許多決定將過于具體，模型將過度擬合到訓練數(shù)據(jù)中淳玩。修剪決策樹的過程涉及減小其大小直撤，以便更好地概括為看不見的數(shù)據(jù)。
該問題的一個解決方案是在樹達到一定數(shù)量的決策時或當決策節(jié)點僅包含少量示例時阻止樹增長蜕着。這稱為提前停止或預先確定決策樹谋竖。由于樹避免做不必要的工作，這是一個吸引人的策略承匣。然而蓖乘，這種方法的一個缺點是，無法知道樹是否會錯過細微但重要的模式韧骗，如果它變得更大嘉抒，它將會學到它。
另一種稱為后修剪的方法涉及種植有意過大的樹并修剪葉節(jié)點以將樹的大小減小到更合適的水平宽闲。這通常是比預執(zhí)行更有效的方法众眨，因為在不首先增加決策樹的情況下確定決策樹的最佳深度是相當困難的。稍后修剪樹允許算法確定發(fā)現(xiàn)了所有重要的數(shù)據(jù)結構容诬。
C5.0算法的一個好處是娩梨，它是關于修剪的看法 - 它使用相當合理的默認值自動處理許多決策。它的總體策略是對樹進行后修剪览徒。它首先會生成一個超級訓練數(shù)據(jù)的大樹狈定。之后，刪除對分類錯誤影響很小的節(jié)點和分支习蓬。在某些情況下纽什，整個分支在樹上向上移動或由更簡單的決策取代。這些移植分支的過程分別稱為子樹提升和子樹替換躲叼。
在過度擬合和欠擬合之間取得適當?shù)钠胶馐且患囆g芦缰，但如果模型準確性至關重要，那么可能需要花一些時間使用各種修剪選項來查看它是否能提高測試數(shù)據(jù)集的性能枫慷。
總而言之让蕾，決策樹由于其高準確性和用簡單語言制定統(tǒng)計模型的能力而被廣泛使用浪规。在這里，我們研究了一種非常流行且易于配置的決策樹算法C5.0探孝。與其他決策樹實現(xiàn)相比笋婿，C5.0算法的主要優(yōu)勢在于可以非常輕松地調整訓練選項。
