怎麼理解決策樹、xgboost能處理缺失值？而有的模型(svm)對缺失值比較敏感呢?

01-02

如題，在網上文章介紹模型優缺點時，看到決策樹、xgboost模型對缺失值不敏感，對缺失值有處理，請問下怎麼處理的？為什麼不敏感? 而svm，線性模型對缺失值敏感？為什麼？

首先從兩個角度解釋你的困惑：

工具包自動處理數據缺失不代表具體的演算法可以處理缺失項
對於有缺失的數據：以決策樹為原型的模型優於依賴距離度量的模型

回答中也會介紹樹模型，如隨機森林(Random Forest)和xgboost如何處理缺失值。文章最後總結了在有缺失值時選擇模型的小建議。

1. 機器學習工具庫開發的「哲學」

首先你有這個困惑是因為你直接調用了工具庫，比如Python的sklearn和xgboost等，所以你認為演算法A可以自動處理缺失值而B不可以。但真實情況是...開發者在封裝工具庫的時候就已經考慮到了使用者可能導入了含有缺失值的數據，所以加了一個缺失值處理的函數。處理缺失值的不是演算法A，而是開發者額外寫的函數。

但是，模型/演算法本身不應該處理缺失值，處理缺失值的應該是用戶。然而在現實情況下，如果用戶不處理/不知道怎麼處理，我們也必須提供一個默認的缺失值處理方法。但是這種自動處理的缺失值，效果往往不好，因為數據的精髓只有用戶自己明白。

工具包提供自動數據清理的功能的好處：

防止用戶導入的數據不符合模型要求而導致失敗
節省用戶的時間，提供一站式服務

工具包提供自動數據清理的功能的風險：

簡單粗暴的處理模式會影響模型的結果，自動化的數據清理不可靠
用戶應該提供符合模型要求的數據，這不是演算法工具庫的責任。演算法工具包的默認要求就是用戶提供適合的數據，因為用戶對數據有更深刻的理解
可能會大幅度增加模型的運算時間

在軟體工程領域，我們有一個比較經典的哲學思想叫做「讓它出錯」(let it fail)。指的是如果程序在運行中出現了錯誤，應該拋出異常(raise exception)而不是默默地裝作沒看到繼續運行。放在機器學習工具包的場景下，如果發現數據有缺失，或者格式不對（比如不是數字型變數），應該報錯而不是替用戶處理。這也是為什麼sklearn會報錯，而不是替你處理。

恰好最近在開發一個機器學習開源工具包，相關的問題也想了很多。是否替使用者做了本該他自己做的事情，這需要在易用性和準確性中間找平衡。

2. 決策樹模型怎麼處理異常值？

看到這裡，我希望你理解了為什麼不是每個工具包都會自動處理缺失值。那我們分析一個具體個案 - 隨機森林(Random Forests)。隨機森林是已故統計學家Leo Breiman提出的，和gradient boosted tree一樣，它的基模型是決策樹。在介紹RF時，Breiman就提出兩種解決缺失值的方法（Random forests - classification description）：

方法1(快速簡單但效果差)：把數值型變數(numerical variables)中的缺失值用其所對應的類別中(class)的中位數(median)替換。把描述型變數(categorical variables)缺失的部分用所對應類別中出現最多的數值替代(most frequent non-missing value)。以數值型變數為例： $X_{i,j} = Median(forall X_{k,j}) quad where , k=1,2,3...n ; and ; X_{k,j} ,is, present$
方法2(耗時費力但效果好)：雖然依然是使用中位數和出現次數最多的數來進行替換，方法2引入了權重。即對需要替換的數據先和其他數據做相似度測量(proximity measurement)也就是下面公式中的Weight( $W$ )，在補全缺失點是相似的點的數據會有更高的權重W。以數值型變數為例： $X_{k,j} =frac{1}{n}sum_{i=1, e k}^{n}W_{i,k} X_{i,j} quad where , k=1,2,3...n ; and ; X_{i,j} ,is, present$

註：公式僅做參考，未仔細檢查。

Breiman說明了第二種方法的效果更好，但需要的時間更長。這也是為什麼工具包中一般不提供數據補全的功能，因為會影響到工具包的效率。

3. xgboost怎麼處理缺失值？

xgboost處理缺失值的方法和其他樹模型不同。根據作者Tianqi Chen在論文[1]中章節3.4的介紹，xgboost把缺失值當做稀疏矩陣來對待，本身的在節點分裂時不考慮的缺失值的數值。缺失值數據會被分到左子樹和右子樹分別計算損失，選擇較優的那一個。如果訓練中沒有數據缺失，預測時出現了數據缺失，那麼默認被分類到右子樹。具體的介紹可以參考[2,3]。

這樣的處理方法固然巧妙，但也有風險：即我們假設了訓練數據和預測數據的分布相同，比如缺失值的分布也相同，不過直覺上應該影響不是很大:)

4. 什麼樣的模型對缺失值更敏感？

主流的機器學習模型千千萬，很難一概而論。但有一些經驗法則(rule of thumb)供參考：

樹模型對於缺失值的敏感度較低，大部分時候可以在數據有缺失時使用。
涉及到距離度量(distance measurement)時，如計算兩個點之間的距離，缺失數據就變得比較重要。因為涉及到「距離」這個概念，那麼缺失值處理不當就會導致效果很差，如K近鄰演算法(KNN)和支持向量機(SVM)。
線性模型的代價函數(loss function)往往涉及到距離(distance)的計算，計算預測值和真實值之間的差別，這容易導致對缺失值敏感。
神經網路的魯棒性強，對於缺失數據不是非常敏感，但一般沒有那麼多數據可供使用。
貝葉斯模型對於缺失數據也比較穩定，數據量很小的時候首推貝葉斯模型。

總結來看，對於有缺失值的數據在經過缺失值處理後：

數據量很小，用樸素貝葉斯
數據量適中或者較大，用樹模型，優先 xgboost
數據量較大，也可以用神經網路
避免使用距離度量相關的模型，如KNN和SVM

當然，這只是我的經驗之談，請謹慎參考。缺失值補全(missing value imputation)是一個非常大的方向，答案中只能簡單帶過，推薦深入了解。

5. 寫在最後 - 如何優雅的調包？

不少答案中我都提到過「支持大家調包」，也就是調用現成的機器學習工具包。但「調包」最大的風險就是不知道自己用的到底是什麼，常常一知半解。

這並不可怕，可怕的是當你感到迷惑的時候卻沒有追根溯源，搞清楚到底發生了什麼。隨著工具包的封裝程度越來越高，調包的成本會越來越低。

但想要優雅的調包，最好還是知道包里裝了些什麼 ?????

[1] A Scalable Tree Boosting System

[2] What are the ways of treatng missing values in XGboost? · Issue #21 · dmlc/xgboost

[3] Frequently Asked Questions

sklearn包里的演算法代入數據不能有缺失值，而xgboost可以。不是xgboost對缺失值不敏感，而是它對缺失值有默認的處理方法。

放一張stackoverflow的截圖：xgboost: handling of missing values for split candidate search

就是把缺失值分別放到左葉子節點和右葉子節點中，計算增益。哪個增益大就放到哪個葉子節點。

我來翻譯一下上圖的解釋吧。事實上，XGBoost為缺失值設定了默認的分裂方向。XGBoost在樹的構建過程中選擇能夠最小化訓練誤差的方向作為默認的分裂方向，這個默認方向可以是左孩子方向也可以是右孩子方向。不明覺厲。。。

決策樹(Decision Tree)是機器學習中最常見的演算法，因為決策樹的結果簡單，容易理解，因此應用超級廣泛，但是機器學習的專家們在設計決策樹的時候會考慮哪些特性呢？

下面寫到的內容根據已有的決策樹來分析，一個想像中萬能的決策樹會有哪些變化？在這以前，先總結下使用決策樹的優缺點：

優點：

天然的可解釋性。這是決策樹最大的優點了。可解釋性有兩方面的考慮。一方面，樹結構的理解不需要機器學習專家來解讀。另一方面，很容易轉化成規則。
可以處理缺失值（missing），字元型（nominal），數值型（numeric）等數據類型。
非參數模型（non-parametric）。沒有複雜的參數設置，誰跑效果都相對一樣。
對相關（Correlation）屬性能夠比較好的處理。
運算速度相對比較快。

缺點：

最大的缺點就是很容易過擬合。導致實際預測的效果並不高。
決策樹中，重複的部分過多難以概括，譬如對於 ( F1 F2 ) || ( F3 F4 ) 的表達（如下圖，劃圈的部分重複），決策樹就有很大的重複。
不適合處理高維數據，當屬性數量過大的時候，部分決策樹就不太適用了。
對異常值（Outlier）過於敏感，很容易導致樹的結構的巨大的變換。
泛化（Generalization）能力太差，對於沒有出現過的值幾乎沒有辦法。

種樹的人們

Leo Breiman 教授

已經在2005年離世了，他UC，Berkeley的統計系教授， Breiman除了發明了CART，而且發明了Bagging和Random Forest。他對決策樹的重大貢獻包括：回歸樹， Variable Importance， Cross-Validation用作Pruning， Surrogant Splitting處理Missing變數。當然了， Bagging、Randomize來降低Overfitting的突破更不在話下。

Jerome H. Friedman 教授

是Stanford 統計系的教授，但是他本人是Berkeley物理系畢業的。他和老朋友Breiman一起發明了CART，獨自發明了MARS，同時他也是Gradient Boosting方法的發明人。他對決策樹的重大貢獻在於提出Stepwise的概念，使得回歸樹變得更為強大。

Ross Quinlan 教授

是University of Sydney的計算機系教授，也是著名的蘭德（RAND）公司的研究員，他發明了ID3， C4.5， C5.0。他對決策樹的重大貢獻在於提出了Information Gain （Ratio）的框架，引入了Entropy的思想。首次提出利用多叉樹來簡化決策樹。並且創造了Pre-pruning的思想。

James N. Morgan 教授

是University of Michigan經濟系教授，已經過世很多年了。他對決策樹的重要貢獻是，首次將Interaction Test （F-Test）引入AID決策樹。

Gordon V. Kass

來自南非的博士，他在博士論文裡面發明了CHAID演算法。他對決策樹的重大貢獻在於首次利用χ2-Test 結合F-Test來降低偏差（Bias），首次提出Unbiased的概念。

Wei-Yin Loh 教授

來自新加坡，現在是University of Wisconsin的統計系教授， Loh教授是FACT， RUISE, GUIDE, LOTUS, 和 QUEST的發明人，他廣泛的借鑒並發揚了前面幾位的貢獻。他對決策樹的主要貢獻在於，通過LDA建立了劃分的概念，並且廣泛的引入Interaction Test到決策樹框架內，另外就是引入Box-Cox Transformation預處理方式。

決策樹們

CART (Classification and Regression Trees) ：

是Breiman 提出的一個二叉樹，採用貪心的遞歸分支方法進行生長。 CART不僅可以用來分類，也可以做回歸。在CART裡面首次使用了Missing的替代劃分（surrogate splits）的技巧。 CART樹首先提出並使用了Variable Importance（VI）的概念，這是個很牛的衡量屬性特徵權重的概念。需要注意的是VI是隨著樹的變化而變化的，所以不同樹之間的VI是不能相互比較的，細節可以參考（https://www.salford-systems.com/videos/tutorials/how-to/variable-importance-in-cart）。另外CART也是最早引入Cross Validation來進行Pruning的。

.......................................................................................

# ID3 (Iterative Dichotomiser)：

是C4.5的一個早期版本，因此在後面說明中不會提及。 ID3不能處理連續值，沒有剪枝，不能處理缺失（Missing）。但是ID3提出了很好的Information Gain的框架。

C4.5：

是Quinlan提出的一系列演算法的流傳最廣的一個。前續版本有ID3，後續還有C5.0，但是C5.0是商業版本的。 C4.5在ID3的基礎上做了很多重大改進，其中一個就是ID3不能處理連續數值的情況，而C4.5通過閾值自動把連續變數分成兩部分來處理。

.......................................................................................

# AID (Automatic Interaction Detection) ：

是CHAID的早期版本，或者說一個更一般的方法，因此在後面說明中不會提及。 AID首次提出利用F-Test來進行選擇和劃分，進而引入Interaction的概念。

CAID (Chi-Squared Automatic Interaction Detection) ：

是AID的後續版本，在認識的AID的偏差性後，利用χ2-Test和F-Test結合的方式來選擇屬性，來降低偏差。同時CHAID也意識到二叉樹的複雜性，運行多叉樹合併產生更小的決策樹。

.....................................................................................

# FACT (Fast Algorithm for Classification Trees)：

是QUEST的一個早期版本，因此在後面說明中不會提及。FACT講符號的屬性全部轉換成數值型的，然後，利用LDA（linear discriminant analysis）來將屬性進行分割的。它進行特徵選擇的時候，利用ANOVA (analysis of variance)的F-Test，優先選擇最大的F Ratio的屬性進行劃分。

QUEST (Quick, Unbiased, Efficient, Statistical Tree)：

是FACT的後續版本，並且將FACT的基於LDA（linear discriminant analysis）的劃分，修改成了基於QDA（quadratic discrimination analysis）的劃分。並且在特徵選擇的時候，連續特徵和FACT一樣基於F-Test，但是離散特徵是基於χ2-Test的。在QUEST中Missing處理比較簡單，就是用插值（Imputation）。

CRUISE (Classification Rule with Unbiased Interaction Selection and Estimation)：

是QUEST的後續演算法，除了繼承了QUEST的F-Test（連續值）和χ2-Test（離散值）的劃分，還引入了叫2D的特徵劃分方式。 2D的劃分中，兩兩屬性之間都要進行5次測試（2次marginal tests和3次interaction tests）

並且劃分也有改變，先進行Box-Cox Transformation預處理，再進行LDA劃分。另外還有一個重大改變是CRUISE經過Box-Cox變換後，可以將一個屬性劃分成多個分支（多叉樹）。 CRUISE採用了CART樹處理Missing的Surrogate Splitting辦法。

GUIDE （Generalized, Unbiased, Interaction Detection and Estimation）：

GUIDE更像一個QUEST 和CART樹的一個綜合體的Bagging升級版。它繼承了QUEST和CRUISE的特徵劃分方式，但是加入了Variable Importance的排序和按閾值選擇部分特徵集。並且GUIDE和CART類似也可以用作Regression。由於受到Random Forest成功的影響， GUIDE自帶了Bagging的兩種機制（Random Forest 和Extremely Randomized Trees）。但是GUIDE裡面Missing沒有採用CART的方式，而是把Missing看成一類特殊值，但是同時根據數據類型，具有插值的mean（連續型），或者是常量（符號型）。

.................................................................................

# MARS（Multivariate Adaptive Regression Splines）：

是Frieman提出的一個多變數回歸的線性樣板。基於多個Hinge Function把不同變數的回歸部分拼接起來。因此來說， MARS與傳統的樹還是差異蠻大的，因此在後面說明中不會提及。但是這個過程中Friedman應用了Stepwise Regression的思想。這或許是他後來提出Gradient Boosting方法的一個基礎。

結構特徵

既然是樹，樹是二叉還是多叉的呢？

二叉：CART， QUEST， GUIDE

二叉或者多叉：C4.5，CHAID， CRUISE

是一顆樹還是多棵樹？

多顆樹：GUIDE (兩種Bagging方式)

生長特徵

在樹長過程中要判斷按屬性來分，在這個過程有幾個指標會帶來變化。

參考一個屬性還是多個屬性進行劃分？只支持一個屬性還是支持多個屬性？

一個屬性： CART C4.5 CHAID QUEST CRUISE

多個屬性： CART QUEST CRUISE

計算屬性的什麼值？信息增益（Information Gain）的計算方式？

Gini ： CART

Entropy： C4.5

Misclassification Error ： CART

F-Test / χ2-Test : QUEST CRUISE

是否對屬性按重要性排序(Variable Importance)？

有重要性排序：CART GUIDE

沒有重要性排序： C4.5 CHAID QUEST CRUISE

連續值如何劃分？

Information Gain （Ratio） based Threshold： C4.5

Twoing Criteria （類似Information Gain）：CART

LDA/QDA based Threshold：QUEST CRUISE

Adjusted p value：CHAID

數據特徵

是否能夠處理Missing值？如果能，是如何處理的？

不能處理: --

插值法（Imputation）： QUEST, CRUISE

替代法（Alternate/Surrogate Splits）：CART， CRUISE

缺失值單獨分支（Missing value branch）：CHAID， GUIDE

概率權重（Probability weights）： C4.5

數值型和符號型（類別型）屬性值是如何計算的？

閾值來劃分連續型：CART， C4.5， CHAID

符號型變換成數值型：QUEST, CRUISE

連續型通過Box-Cox變換：GUIDE

正則化特徵

剪枝（Pruning）是決策樹正則化的最重要辦法。

一個剪枝的方法是？

（Stopping rule）：CHAID

（Pre-pruning）：C4.5

（Cross-validation pruning）：CART QUEST CRUISE

剪枝參考值得計算方式？

Cost-Complexity Minimization　（standard misclassification cost vs number of leaves ）：　CART

Error-Based Pruning　（Wilson』s confidence intervals）：　C4.5

Maximum Depth: CHAID

Gini， Entropy，和Misclassification Error的異同

這些都可以作為信息增益框架下的信息計算公式。信息增益的框架如下：

Information Gain：

他們的公式和曲線不一樣：

Gini：

Entropy：

Missclassification Error：

根據公式衍生有如下不同：

Gini更適合連續數值變數，而Entropy更適合符號型變數。

Gini降低最小誤分率，而Entropy具有更好的概率解釋性。

Gini運算要比Entropy運算快。

但是根據實際運行情況：

Gini， Entropy，和Misclassification Error 基本一致，一般不超過2%的區別。

參考：

http://www.stat.wisc.edu/~loh/

http://www.geniqmodel.com/res/Reference-Pithy-History-of-CHAID-and-Offspring.html

https://datajobs.com/data-science-repo/Decision-Trees-[Rokach-and-Maimon].pdf

http://www.stat.wisc.edu/~loh/cruise.html

http://www.stat.wisc.edu/~loh/guide.html

http://www.stat.wisc.edu/~loh/compareclass.pdf

https://www.ibm.com/support/knowledgecenter/en/SSLVMB_20.0.0/com.ibm.spss.statistics.help/alg_tree-cart.htm

http://www.lib.umich.edu/faculty-history/faculty/james-n-morgan

James N. Morgan Fund for New Directions in Analysis of Complex Interactions

http://sebastianraschka.com/faq/docs/decision-tree-binary.html

談談我的理解，與上面朋友的見解略有出入。一句話解釋是：

基於特徵採樣的統計分布的方法對缺失值有更高的抗性。
決策樹能將缺失值盡量解釋為其它特徵，從而最適用於應對缺失值。其它基於統計分布的方法（如廣義加性模型和KNN）能在盡量保證「缺失值是隨機的」的前提下降低缺失值造成的負面影響，機理是預先填充缺失值並在訓練中視其有值。
基於數據的值來定位邊界的方法（如支持向量）對缺失值的抗性不好，不恰當的非隨機缺失值可能導致模型出現意外。

在聊各個模型之前，我們先聊聊缺失值是什麼樣子的。我們定義

${f X}$ ： $N imes p$ 的 input matrix（其中有些值是missing）；
${f X}_{obs}$ ： ${f X}$ 中可觀測到的 entries；
${f y}$ ： $N imes 1$ 的 response vector；
${f R}$ ：一個 Indicator Matrix， ${f R}_{ij}=1$ 表示 $x_{ij}$ 缺失，否則表示未缺失；
${f Z}=({f y},{f X})$ ； ${f Z}_{obs}=({f y},{f X}_{obs})$ 。

則在一般定義下，「缺失值是隨機的」（missing at random，MAR）表示造成數據缺失的原因僅與可見的那些變數有關：

${ m Pr}({f R}|{f Z}, heta) = { m Pr}({f R}|{f Z}_{obs}, heta).$

其中， $heta$ 表示 ${f R}$ 分布的參數。

更進一步地，「缺失值是完全隨機的」（missing completely at random，MCAR）表示 ${f R}$ 的分布與觀測到還是沒有觀測到數據沒有關係：

${ m Pr}({f R}|{f Z}, heta) = { m Pr}({f R}| heta).$

舉個例子：如果一個病人的體溫測量值是有時缺失的，其原因是醫生覺得病得太重的病人不需要量體溫，那這個缺失顯然不是MAR或者MCAR的。對於離散型特徵，如果將特徵中的缺失值單獨編碼成一個獨立的類別（比如missing），而這個missing類別訓練出來後對response有預測作用，那麼這個特徵中的缺失行為基本不是MAR或者MCAR的。

實際應用中的缺失值一般很少是MAR或者MCAR的。例如在推薦演算法中，用戶的網路特徵有時無法取到，但這種事情在各種條件下發生的概率顯然並不相同，並且這些條件很難用已有的特徵加以完全描述。

下面來看下通常用來處理缺失值的兩種方式：

讓訓練演算法在訓練階段自行處理缺失值；
在訓練開始前處理掉缺失值。

決策樹類演算法用來處理缺失值的方式是第一種方式。對於隨機森林，基於的是所謂「代理變數」思想。我們知道，隨機森林關注的是各個特徵之間的相關性。缺失值與其它變數間相關性越高，意味著用已有的變數來「模擬」缺失值時損失的信息越少。仍然用用戶的網路特徵為例，隨機森林會在網路特徵缺失的情況下轉而使用其它存在的稍弱的高相關特徵（如頁面響應時間）的值進行所謂的second split，從而保證了信息量的最大程度保留。

對於additive model，常用來處理缺失值的方式是第二種。對additive model而言，在訓練中將missing單獨視為一個值處理和在訓練前將缺失值填充為mean是等價的，相當於在迭代的時候對目標函數不作為。GBDT作為generalized additive model的一種，它能處理缺失值其實意思是「缺失值雖然會降低信息量，但不會對最終結果（尤其是其它特徵的結果）造成主動性的負面影響」。但由於普通的填充方法相當於假設缺失特徵的分布是MCAR的，它能帶來的信息量也僅限於用均值或其它值填充時逼近的信息量，且本身會帶來uncertainty。

至於SVM為何不擅長處理缺失值，是因為SVM不是基於特徵在樣本上的總體分布的，而是基於邊界點而做的結論。我們看到，只有缺失值是MCAR的才能保證統計量上與觀測數據無偏，那麼非MCAR的缺失很容易導致分割面的錯誤移動。做個推論，神經網路也不能很好地處理缺失值，因為邊界點上的值的非MCAR缺失會造成梯度判斷的方向性錯誤。相對地，雖然KNN是一個基於距離的模型，但它仍然是一個基於統計的模型，對缺失值仍然是比較robust的。對於樣本較為充分的特徵，KNN可以接受在訓練開始前處理缺失值，並且導致意外的損失的概率較低。

順便一提，一個理論上比較有效的第二種處理缺失值的技術實現是：當一個特徵出現缺失值的時候，用其它特徵來預測它的值進行填充。不過考慮到工程複雜度，一般還是使用均值或中值（連續變數）或者單獨開一個missing類別（離散變數）來實現，或者使用一些trick。經典的一個故事是性別缺失，當一維的性別特徵可能missing時，擴展成兩維{not男，not女}來進行編碼。不過這些trick仍然只有一個目的：儘可能保留信息量並使用存在的特徵對缺失的特徵進行解釋。

拋磚引玉，歡迎探討。

缺失值也能分到樹的left /right branch 或者停止生長。。。所以缺失值並不影響樹的生成，形成和分裂(以是否能收斂來看)