常見面試演算法：決策樹、隨機森林和AdaBoost

  • 2019 年 10 月 28 日
  • 筆記

決策樹 概述

決策樹（Decision Tree）演算法是一種基本的分類與回歸方法，是最經常使用的數據挖掘演算法之一。我們這章節只討論用於分類的決策樹。

決策樹模型呈樹形結構，在分類問題中，表示基於特徵對實例進行分類的過程。它可以認為是 if-then 規則的集合，也可以認為是定義在特徵空間與類空間上的條件概率分布。

決策樹學習通常包括 3 個步驟：特徵選擇、決策樹的生成和決策樹的修剪。

決策樹 場景

一個叫做 "二十個問題" 的遊戲，遊戲的規則很簡單：參與遊戲的一方在腦海中想某個事物，其他參與者向他提問，只允許提 20 個問題，問題的答案也只能用對或錯回答。問問題的人通過推斷分解，逐步縮小待猜測事物的範圍，最後得到遊戲的答案。

一個郵件分類系統，大致工作流程如下：

首先檢測發送郵件域名地址。如果地址為 myEmployer.com, 則將其放在分類  "無聊時需要閱讀的郵件"中。  如果郵件不是來自這個域名，則檢測郵件內容里是否包含單詞 "曲棍球" ,  如果包含則將郵件歸類到 "需要及時處理的朋友郵件",  如果不包含則將郵件歸類到 "無需閱讀的垃圾郵件" 。

決策樹的定義：

分類決策樹模型是一種描述對實例進行分類的樹形結構。決策樹由結點（node）和有向邊（directed edge）組成。結點有兩種類型：內部結點（internal node）和葉結點（leaf node）。內部結點表示一個特徵或屬性(features)，葉結點表示一個類(labels)。

用決策樹對需要測試的實例進行分類：從根節點開始，對實例的某一特徵進行測試，根據測試結果，將實例分配到其子結點；這時，每一個子結點對應著該特徵的一個取值。如此遞歸地對實例進行測試並分配，直至達到葉結點。最後將實例分配到葉結點的類中。

決策樹 原理

決策樹 須知概念

資訊熵 & 資訊增益

熵（entropy）： 熵指的是體系的混亂的程度，在不同的學科中也有引申出的更為具體的定義，是各領域十分重要的參量。

資訊理論（information theory）中的熵（香農熵）： 是一種資訊的度量方式，表示資訊的混亂程度，也就是說：資訊越有序，資訊熵越低。例如：火柴有序放在火柴盒裡，熵值很低，相反，熵值很高。

資訊增益（information gain）： 在劃分數據集前後資訊發生的變化稱為資訊增益。

決策樹 工作原理

如何構造一個決策樹? 我們使用 createBranch() 方法，如下所示：

決策樹 開發流程

收集數據：可以使用任何方法。

準備數據：樹構造演算法 (這裡使用的是ID3演算法，只適用於標稱型數據，這就是為什麼數值型數據必須離散化。 還有其他的樹構造演算法，比如CART)

分析數據：可以使用任何方法，構造樹完成之後，我們應該檢查圖形是否符合預期。

訓練演算法：構造樹的數據結構。

測試演算法：使用訓練好的樹計算錯誤率。

使用演算法：此步驟可以適用於任何監督學習任務，而使用決策樹可以更好地理解數據的內在含義。

決策樹 演算法特點

優點：計算複雜度不高，輸出結果易於理解，數據有缺失也能跑，可以處理不相關特徵。

缺點：容易過擬合。

適用數據類型：數值型和標稱型。

決策樹 項目案例

項目案例1: 判定魚類和非魚類

項目概述

根據以下 2 個特徵，將動物分成兩類：魚類和非魚類。

特徵：

  1. 不浮出水面是否可以生存
  2. 是否有腳蹼

開發流程

完整程式碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/ML/3.DecisionTree/DecisionTree.py

收集數據：可以使用任何方法

準備數據：樹構造演算法（這裡使用的是ID3演算法，因此數值型數據必須離散化。）

分析數據：可以使用任何方法，構造樹完成之後，我們可以將樹畫出來。

訓練演算法：構造樹結構

測試演算法：使用習得的決策樹執行分類

使用演算法：此步驟可以適用於任何監督學習任務，而使用決策樹可以更好地理解數據的內在含義

收集數據：可以使用任何方法

我們利用 createDataSet() 函數輸入數據

使用演算法：此步驟可以適用於任何監督學習任務，而使用決策樹可以更好地理解數據的內在含義。

項目案例2: 使用決策樹預測隱形眼鏡類型

完整程式碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/ML/3.DecisionTree/DecisionTree.py

項目概述

隱形眼鏡類型包括硬材質、軟材質以及不適合佩戴隱形眼鏡。我們需要使用決策樹預測患者需要佩戴的隱形眼鏡類型。

開發流程

  1. 收集數據: 提供的文本文件。
  2. 解析數據: 解析 tab 鍵分隔的數據行
  3. 分析數據: 快速檢查數據，確保正確地解析數據內容，使用 createPlot() 函數繪製最終的樹形圖。
  4. 訓練演算法: 使用 createTree() 函數。
  5. 測試演算法: 編寫測試函數驗證決策樹可以正確分類給定的數據實例。
  6. 使用演算法: 存儲樹的數據結構，以便下次使用時無需重新構造樹。

收集數據：提供的文本文件

文本文件數據格式如下：

解析數據：解析 tab 鍵分隔的數據行

lecses = [inst.strip().split('t') for inst in fr.readlines()]  lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']

分析數據：快速檢查數據，確保正確地解析數據內容，使用 createPlot() 函數繪製最終的樹形圖。

>>> treePlotter.createPlot(lensesTree)

訓練演算法：使用 createTree() 函數

https://github.com/apachecn/AiLearning/blob/master/docs/3.%E5%86%B3%E7%AD%96%E6%A0%91.md

集成方法-隨機森林和AdaBoost

集成方法: ensemble method（元演算法: meta algorithm） 概述

  • 概念：是對其他演算法進行組合的一種形式。
  • 通俗來說： 當做重要決定時，大家可能都會考慮吸取多個專家而不只是一個人的意見。 機器學習處理問題時又何嘗不是如此？ 這就是集成方法背後的思想。
  • 集成方法：
    1. 投票選舉(bagging: 自舉匯聚法 bootstrap aggregating): 是基於數據隨機重抽樣分類器構造的方法
    2. 再學習(boosting): 是基於所有分類器的加權求和的方法

集成方法 場景

目前 bagging 方法最流行的版本是: 隨機森林(random forest) 選男友：美女選擇擇偶對象的時候，會問幾個閨蜜的建議，最後選擇一個綜合得分最高的一個作為男朋友

目前 boosting 方法最流行的版本是: AdaBoost 追女友：3個帥哥追同一個美女，第1個帥哥失敗->(傳授經驗：姓名、家庭情況) 第2個帥哥失敗->(傳授經驗：興趣愛好、性格特點) 第3個帥哥成功

bagging 和 boosting 區別是什麼？

  1. bagging 是一種與 boosting 很類似的技術, 所使用的多個分類器的類型（數據量和特徵量）都是一致的。
  2. bagging 是由不同的分類器（1.數據隨機化 2.特徵隨機化）經過訓練，綜合得出的出現最多分類結果；boosting 是通過調整已有分類器錯分的那些數據來獲得新的分類器，得出目前最優的結果。
  3. bagging 中的分類器權重是相等的；而 boosting 中的分類器加權求和，所以權重並不相等，每個權重代表的是其對應分類器在上一輪迭代中的成功度。

隨機森林

隨機森林 概述

  • 隨機森林指的是利用多棵樹對樣本進行訓練並預測的一種分類器。
  • 決策樹相當於一個大師，通過自己在數據集中學到的知識用於新數據的分類。但是俗話說得好，一個諸葛亮，玩不過三個臭皮匠。隨機森林就是希望構建多個臭皮匠，希望最終的分類效果能夠超過單個大師的一種演算法。

隨機森林 原理

那隨機森林具體如何構建呢？ 有兩個方面：

  1. 數據的隨機性化
  2. 待選特徵的隨機化

使得隨機森林中的決策樹都能夠彼此不同，提升系統的多樣性，從而提升分類性能。

數據的隨機化：使得隨機森林中的決策樹更普遍化一點，適合更多的場景。

（有放回的準確率在：70% 以上， 無放回的準確率在：60% 以上）

  1. 採取有放回的抽樣方式 構造子數據集，保證不同子集之間的數量級一樣（不同子集／同一子集 之間的元素可以重複）
  2. 利用子數據集來構建子決策樹，將這個數據放到每個子決策樹中，每個子決策樹輸出一個結果。
  3. 然後統計子決策樹的投票結果，得到最終的分類 就是 隨機森林的輸出結果。
  4. 如下圖，假設隨機森林中有3棵子決策樹，2棵子樹的分類結果是A類，1棵子樹的分類結果是B類，那麼隨機森林的分類結果就是A類。

待選特徵的隨機化

  1. 子樹從所有的待選特徵中隨機選取一定的特徵。
  2. 在選取的特徵中選取最優的特徵。

下圖中，藍色的方塊代表所有可以被選擇的特徵，也就是目前的待選特徵；黃色的方塊是分裂特徵。

左邊是一棵決策樹的特徵選取過程，通過在待選特徵中選取最優的分裂特徵（別忘了前文提到的ID3演算法，C4.5演算法，CART演算法等等），完成分裂。 右邊是一個隨機森林中的子樹的特徵選取過程。

隨機森林 開發流程

收集數據：任何方法  準備數據：轉換樣本集  分析數據：任何方法  訓練演算法：通過數據隨機化和特徵隨機化，進行多實例的分類評估  測試演算法：計算錯誤率  使用演算法：輸入樣本數據，然後運行 隨機森林 演算法判斷輸入數據分類屬於哪個分類，  最後對計算出的分類執行後續處理

隨機森林 演算法特點 

優點：幾乎不需要輸入準備、可實現隱式特徵選擇、訓練速度非常快、其他模型很難超越、  很難建立一個糟糕的隨機森林模型、大量優秀、免費以及開源的實現。  缺點：劣勢在於模型大小、是個很難去解釋的黑盒子。  適用數據範圍：數值型和標稱型

項目案例: 聲納訊號分類

項目概述

這是 Gorman 和 Sejnowski 在研究使用神經網路的聲納訊號分類中使用的數據集。任務是訓練一個模型來區分聲納訊號。

開發流程

收集數據：提供的文本文件  準備數據：轉換樣本集  分析數據：手工檢查數據  訓練演算法：在數據上，利用 random_forest() 函數進行優化評估，返回模型的綜合分類結果  測試演算法：在採用自定義 n_folds 份隨機重抽樣 進行測試評估，得出綜合的預測評分  使用演算法：若你感興趣可以構建完整的應用程式，從案例進行封裝，也可以參考我們的程式碼

收集數據：提供的文本文件

樣本數據：sonar-all-data.txt

使用演算法：若你感興趣可以構建完整的應用程式，從案例進行封裝，也可以參考我們的程式碼

完整程式碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/ML/7.RandomForest/randomForest.py

AdaBoost

AdaBoost (adaptive boosting: 自適應 boosting) 概述

能否使用弱分類器和多個實例來構建一個強分類器？ 這是一個非常有趣的理論問題。

AdaBoost 原理

AdaBoost 工作原理

AdaBoost 開發流程

收集數據：可以使用任意方法  準備數據：依賴於所使用的弱分類器類型，本章使用的是單層決策樹，這種分類器可以處理任  何數據類型。     當然也可以使用任意分類器作為弱分類器，第2章到第6章中的任一分類器都可以充  當弱分類器。     作為弱分類器，簡單分類器的效果更好。  分析數據：可以使用任意方法。  訓練演算法：AdaBoost 的大部分時間都用在訓練上，分類器將多次在同一數據集上  訓練弱分類器。  測試演算法：計算分類的錯誤率。  使用演算法：通SVM一樣，AdaBoost 預測兩個類別中的一個。如果想把它應用到多個類別的  場景，那麼就要像多類 SVM 中的做法一樣對 AdaBoost 進行修改。

AdaBoost 演算法特點

* 優點：泛化（由具體的、個別的擴大為一般的）錯誤率低，易編碼，可以應用在大部分分  類器上，無參數調節。  * 缺點：對離群點敏感。  * 適用數據類型：數值型和標稱型數據。

項目案例: 馬疝病的預測

項目流程圖

基於單層決策樹構建弱分類器

  • 單層決策樹(decision stump, 也稱決策樹樁)是一種簡單的決策樹。

項目概述

預測患有疝氣病的馬的存活問題，這裡的數據包括368個樣本和28個特徵，疝氣病是描述馬胃腸痛的術語，然而，這種病並不一定源自馬的胃腸問題，其他問題也可能引發疝氣病，該數據集中包含了醫院檢測馬疝氣病的一些指標，有的指標比較主觀，有的指標難以測量，例如馬的疼痛級別。另外，除了部分指標主觀和難以測量之外，該數據還存在一個問題，數據集中有30%的值是缺失的。

完整程式碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/ML/7.AdaBoost/adaboost.py

開發流程 

收集數據：提供的文本文件  準備數據：確保類別標籤是+1和-1，而非1和0  分析數據：統計分析  訓練演算法：在數據上，利用 adaBoostTrainDS() 函數訓練出一系列的分類器  測試演算法：我們擁有兩個數據集。在不採用隨機抽樣的方法下，我們就會對 AdaBoost 和  Logistic 回歸的結果進行完全對等的比較  使用演算法：觀察該例子上的錯誤率。不過，也可以構建一個 Web 網站，讓馴馬師輸入馬的  癥狀然後預測馬是否會死去

收集數據：提供的文本文件

訓練數據：horseColicTraining.txt 測試數據：horseColicTest.txt

分析數據：統計分析

過擬合(overfitting, 也稱為過學習)

  • 發現測試錯誤率在達到一個最小值之後有開始上升，這種現象稱為過擬合。

通俗來說：就是把一些噪音數據也擬合進去的，如下圖。

訓練演算法：在數據上，利用 adaBoostTrainDS() 函數訓練出一系列的分類器。

要點補充

非均衡現象：

在分類器訓練時，正例數目和反例數目不相等（相差很大）。或者發生在正負例分類錯誤的成本不同的時候。

  • 判斷馬是否能繼續生存(不可誤殺)
  • 過濾垃圾郵件(不可漏判)
  • 不能放過傳染病的人
  • 不能隨便認為別人犯罪

我們有多種方法來處理這個問題： 具體可參考此鏈接

8 Tactics to Combat Imbalanced Classes in Your Machine Learning Dataset

再結合書中的方法，可以歸為八大類：

1.能否收集到更多的數據？

這個措施往往被人們所忽略，被認為很蠢。但是更大的數據集更能體現樣本的分布，多樣性。

2.嘗試使用其他的評價指標

Accuracy 或者error rate 不能用於非均衡的數據集。這會誤導人。這時候可以嘗試其他的評價指標。

Confusion Matrix 混淆矩陣：使用一個表格對分類器所預測的類別與其真實的類別的樣本統計，分別為：TP、FN、FP與TN。

Precision：精確度

Recall： 召回率

F1 Score (or F-Score)： 精確度和召回率的加權平均

或者使用

Kappa (Cohen's kappa)

ROC Curves

ROC 評估方法

  • ROC 曲線: 最佳的分類器應該儘可能地處於左上角
  • 對不同的 ROC 曲線進行比較的一個指標是曲線下的面積(Area Unser the Curve, AUC).
  • AUC 給出的是分類器的平均性能值，當然它並不能完全代替對整條曲線的觀察。
  • 一個完美分類器的 AUC 為1，而隨機猜測的 AUC 則為0.5。

3.嘗試對樣本重抽樣

欠抽樣(undersampling)或者過抽樣(oversampling)

- 欠抽樣: 意味著刪除樣例  - 過抽樣: 意味著複製樣例(重複使用)

對大類進行欠抽樣

對小類進行過抽樣

或者結合上述兩種方法進行抽樣

一些經驗法則：

  • 考慮樣本（超過1萬、十萬甚至更多）進行欠取樣，即刪除部分樣本；
  • 考慮樣本（不足1為甚至更少）進行過取樣，即添加部分樣本的副本；
  • 考慮嘗試隨機取樣與非隨機取樣兩種取樣方法；
  • 考慮對各類別嘗試不同的取樣比例，不一定是1:1
  • 考慮同時使用過取樣與欠取樣

4.嘗試產生人工生成的樣本

一種簡單的方法就是隨機抽樣小類樣本的屬性（特徵）來組成新的樣本即屬性值隨機取樣。你可以根據經驗進行抽樣，可以使用其他方式比如樸素貝葉斯方法假設各屬性之間互相獨立進行取樣，這樣便可得到更多的數據，但是無法保證屬性之間的非線性關係。

當然也有系統性的演算法。最常用的SMOTE(Synthetic Minority Over-Sampling Technique)。 顧名思義，這是一種over sampling（過抽樣）的方式。它是產生人為的樣本而不是製造樣本副本。這個演算法是選取2個或者2個以上相似的樣本（根據距離度量 distance measure），然後每次選擇其中一個樣本，並隨機選擇一定數量的鄰居樣本對選擇的那個樣本的一個屬性增加雜訊(每次只處理一個屬性)。這樣就構造了更多的新生數據。具體可以參見原始論文。

http://www.jair.org/papers/paper953.html

python實現可以查閱UnbalancedDataset

https://github.com/scikit-learn-contrib/imbalanced-learn

5.嘗試不同的演算法

強烈建議不要在每個問題上使用你最喜歡的演算法。雖然這個演算法帶來較好的效果，但是它也會蒙蔽你觀察數據內蘊含的其他的資訊。至少你得在同一個問題上試試各種演算法。具體可以參閱Why you should be Spot-Checking Algorithms on your Machine Learning Problems

Why you should be Spot-Checking Algorithms on your Machine Learning Problems

比如說，決策樹經常在非均衡數據集上表現良好。創建分類樹時候使用基於類變數的劃分規則強制使類別表達出來。如果有疑惑，可以嘗試一些流行的決策樹，比如, C4.5, C5.0, CART 和 Random Forrest。

6.嘗試使用懲罰的模型

你可以使用同種演算法但是以不同的角度對待這個問題。

懲罰的模型就是對於不同的分類錯誤給予不同的代價（懲罰）。比如對於錯分的小類給予更高的代價。這種方式會使模型偏差，更加關注小類。

通常來說這種代價/懲罰或者比重在學習中演算法是特定的。比如使用代價函數來實現：

代價函數

  • 基於代價函數的分類器決策控制：TP*(-5)+FN*1+FP*50+TN*0

這種方式叫做 cost sensitive learning，Weka 中相應的框架可以實現叫CostSensitiveClassifier

http://weka.sourceforge.net/doc.dev/weka/classifiers/meta/CostSensitiveClassifier.html

如果當你只能使用特定演算法而且無法重抽樣，或者模型效果不行，這時候使用懲罰（penalization）是可行的方法。這提供另外一種方式來「平衡」類別。但是設定懲罰函數/代價函數是比較複雜的。最好還是嘗試不同的代價函數組合來得到最優效果。

7.嘗試使用不同的角度

其實有很多研究關於非均衡數據。他們有自己的演算法，度量，術語。

從它們的角度看看你的問題，思考你的問題，說不定會有新的想法。

兩個領域您可以考慮： anomaly detection(異常值檢測) 和 change detection（變化趨勢檢測）。

Anomaly dectection 就是檢測稀有事件。 比如通過機器震動來識別機器谷中或者根據一系列系統的調用來檢測惡意操作。與常規操作相比，這些事件是罕見的。

把小類想成異常類這種轉變可能會幫助你想到新辦法來分類數據樣本。

change detection 變化趨勢檢測類似於異常值檢測。但是他不是尋找異常值而是尋找變化或區別。比如通過使用模式或者銀行交易記錄來觀察用戶行為轉變。

這些兩種轉變可能會給你新的方式去思考你的問題和新的技術去嘗試。

8.嘗試去創新

仔細思考你的問題然後想想看如何將這問題細分為幾個更切實際的小問題。

比如：

將你的大類分解成多個較小的類；

使用One Class分類器（看待成異常點檢測）；

對數據集進行抽樣成多個數據集，使用集成方式，訓練多個分類器，然後聯合這些分類器進行分類；

這只是一個例子。更多的可以參閱In classification, how do you handle an unbalanced training set? 和Classification when 80% of my training set is of one class

http://www.quora.com/In-classification-how-do-you-handle-an-unbalanced-training-set

https://github.com/apachecn/AiLearning/blob/master/docs/7.%E9%9B%86%E6%88%90%E6%96%B9%E6%B3%95-%E9%9A%8F%E6%9C%BA%E6%A3%AE%E6%9E%97%E5%92%8CAdaBoost.md

VirMach 便宜 VPS

QNews

QNews