用cart樹回歸演算法預測女朋友給你多少零花錢
假設你有一個女朋友，你每個月都會把工資上交給她，然後她會你一些零花錢；但是令你苦惱的是，每次的零花錢金額都不等，這直接決定了你下個月的煎餅果子里能不能加個蛋的嚴重問題；
於是，你打算提前預測下個月的零花錢是多少
能不能用我們上一節介紹的《用決策樹演算法分析女朋友為什麼會生氣》中的決策樹演算法呢？我們試一下：
第一步，收集數據
圖表1
第二步，計算熵
。。。。。
有沒有發現什麼問題？
問題在於「零花錢」列的每個值都不一樣，此時再算熵已經沒有什麼意義，因為後續已經無法通過某一特徵來降熵，我們稱這種類型的變數為連續型變數；與此相對應的，上一節介紹的「是否生氣」只有少數幾個值，這種變數稱為離散型變數。
那怎麼辦呢？
我們之所以在預測離散型變數時引入「熵」，是因為「熵」可以反映不確定的程度。
可怎麼反映連續型變數的不確定程度呢？此時我們可以引入「方差」
方差是什麼？
方差是一系列數據減去均值的平方和再除以數據個數（如果不除以數據個數，我們姑且叫它「方差和」）這反映了數據的分散程度，還是舉例說話：
觀察下面兩組數據有什麼不同：
【1,2,3,4,5,6,7,8,9】
【1,4,4,5,5,5,6,6,9】
第一組數據分布很分散，第二組則比較集中在5的附近，我們說第一組數據比第二組方差大。
直覺上，如果方差越小，說明我們對數據的結果越有信心，所以應該想辦法減少方差。
前戲介紹完畢，現在我們正式介紹一個新的演算法：cart樹
Cart樹的全稱是分類回歸樹（分類指預測變數是離散的，回歸指預測變數是連續的）
與決策樹的共同點是都是建立樹結構，用葉子節點的值來進行預測。
不同點有兩個：
- 在決策樹中，一個類型變數建立多少個子樹，是根據離散值的個數決定的（比如天氣類型有三個值：晴，陰，多雲，則對應建立三個子樹）；cart樹則不管是離散型還是連續型變數，都是固定建立兩個子樹（遍歷所有特徵的所有可能取值，得到一個使方差和最小的值，小於這個值的為一個分支，大於等於這個值的為另外一個分支）
- 在決策樹中，評價不確定程度的只有一個指標：熵；在cart樹評價不確定性有兩個指標：方差（連續性）和gini指數（離散型），gini指數的形式和熵差不多，比較容易理解，本文只對方差進行展開。
下面我們就用cart樹對你下個月的生活質量情況進行預測，一共分四步
第一步、收集數據
和圖表1的內容一樣；
第二步、尋找最佳拆分點
這一步驟是最關鍵也是最麻煩的，我們先用文字大致描述一下，然後通過例子來展示該怎麼做。
步驟：對表格中每一列每一行的值，都進行如下計算：
- 將數據分為兩組，一組的該列的值都大於該值，另外一組的該列的值都小於該值；
- 分別計算兩組的「零花錢」的方差和，再求和。
- 上一步最小的和對應的值即為所求的最佳拆分點。
舉例來說，圖表1去除「零花錢」列後一共有7個不同的值（5000,8000,4000,6000,3,1,2），所有共有如下七種情況：
一、第一個月的當月工資為5000，將數據分為兩組，
1、當月工資大於5000：
此時的零花錢的均值為450，方差和為 +
=5000
2、當月工資小於等於5000：
此時的零花錢的均值為275，方差和為 +
=1200
所以總方差=5000+1200=6250
二、第二個月的當月工資為8000，將數據分為兩組:
1、當月工資大於8000，此時無記錄，相當於沒有進行劃分，跳過這種情況
三、第三個月的當月工資為4000，將數據分為兩組:
1、當月工資大於4000
此時零花錢均值為400，方差和為20000
2、當月工資小於等於4000：此時只有一條記錄，方差和為0
所以總方差為20000+0=20000
四、第四個月的當月工資為6000，將數據分為兩組:
1、當月工資大於6000時，只有一條記錄，方差和=0
2、當月工資小於等於6000：
均值為316.66，方差和為11666.66,
所以總方差=11666.66+0=11666.66
五，第一個月和第三個月的逛街次數為3，將數據分為兩組
- 逛街次數大於3，此時無記錄，跳過
六、第二個月逛街次數為1，將數據分為兩組：
1、逛街次數大於1:
均值為316.66，方差和為11666.66,
2、逛街次數小於等於1，只有一條記錄，所以方差為0
所以總方差=11666.66+0=11666.66
七、第四個月逛街次數為2，將數據分為兩組：
1、逛街次數大於2：
此時的零花錢的均值為275，方差和為1200
- 逛街次數小於等於2：
此時的零花錢的均值為450，方差和為5000
所以總方差=5000+1200=6250
總算遍歷了一遍，快累死我了。。。。
還差一點點，找最小值。
當「當月工資」為5000時和逛街次數等於2時，得到的「零花錢」方差最小，為6250，我們這裡取第一種情況，即將「當月工資」為5000元作為最佳切分點；
第三步、構建CART樹
剩下的就很簡單了，根據最佳切分點將數據分為兩個子樹後，繼續用第二步的演算法分別對兩個子樹再求得最佳切分點，然後繼續拆分子樹，直到不能繼續為止。
這裡所說的「不能繼續為止」，大概有這麼三種情況：
- 當分組時的「零花錢」類型只有一種值的時候，說明已經無需再進行切分（此時方差為0，已經無法再下降了），第二步的第二種和第五種情況就是這種類型；
- 當分組後的記錄個數小於一個閥值的時候；
- 當方差下降的幅度小於一個閥值的時候；
第一條比較好理解，第二和第三種情況是啥意思呢？是為了防止過擬合！
什麼是過擬合？這個是機器學習最常見也最頭疼的問題，以後找機會再說。。。
現在需要理解的是，此時葉子節點的「零花錢」的值不止一個，最終葉子節點的值就是這些節點「零花錢」的均值，因為本例比較簡單，沒有設置這些閥值，但當數據規模很大時，就必須要考慮過擬合問題了。
下面給出最終生成的cart樹的結構圖：
第四步，進行預測
假設你這個月工資為6500，逛街次數為4，根據cart圖，最終到達「400」的葉子節點，恭喜你！終於可以大聲宣布：老闆，多加個蛋！
Cart樹是一種建模能力很強的方法，就連在各種數據競賽中屢獲殊榮的xgboost工具，基本模型也採用了cart樹，所以重要性不言而喻，尤其要理解其運行的原理。
推薦閱讀：
