內建學習：算法理論 （三）
- 1 決策樹
- 1.1 分類樹
- 1.1.1 資訊熵
- 1.1.2 案例
- 1.1.3 基尼Gini指數
- 1.1.4 案例
- 1.2 回歸樹
- 1.2.1 回歸樹分支标準
- 1.2.2 案例
1 決策樹
1.1 分類樹
1.1.1 資訊熵
資訊熵是用來衡量資訊不确定性的名額，不确定性是一個事件出現不同結果的可能性，計算方法如下所示：
其中：為随機變量x取值為i的機率
條件熵
在給定随機變量Y的條件下，随機變量X的不确定性
資訊增益
熵-條件熵，代表了在一個條件下，資訊不确定性減少的程度
總結一下，資訊熵，條件熵，資訊增益
以相親為例來說，相親要跟居然對方外貌、身高，經濟等條件，做出是否結果對方繼續相處的選擇。是或者否
- 資訊熵：直接對選擇是或否的數量做相關的公式計算。
- 條件熵：在一定條件下選擇是或否的數量做相關公式計算，比如我們看在有房條件裡，看對方是否繼續相處的數量，做相關公式計算
- 資訊增益：類似于對每一個相親條件給出優先級，數值，有人最在意外貌，其次是身高，對方有沒有錢無所謂。與之不同的地方，是需要選擇條件，每一輪選擇一個優先級最高的條件後，要對剩下的條件，基于上一個條件下重新計算，選出最高的優先級
1.1.2 案例
假設有下圖這樣一群相親對象的人選，以及他們被對方是否接受的曆史記錄，現在我們需要通過這個資料來判斷下一位相親對象是否被接受，是以我們需要計算資訊增益
具體流程：
1.計算是否接受相親對象的資訊熵
| 是否接受對方 | 頻數 | 機率 | 資訊熵 |
| 是 | 9 | 0.64 | -0.531 |
| 否 | 5 | 0.36 | -0.410 |
| 總計 | 14 | 1 | 0.940 |
2.下一步，我們計算不同單一的條件下，每一個特征的條件熵，最後并進行求和，得出單一條件的資訊熵
單一條件，比如說學曆，特征就是：專科、大學、碩士。
學曆
X=是否接受
Y=學曆
其中i為：是和否接受
| 學曆 | 是（接受） | 否（不接受） | 頻次 | H | P |
| 專科 | 3 | 2 | 5 | 0.971 | 0.36 |
| 大學 | 2 | 3 | 4 | 0.971 | 0.36 |
| 碩士 | 4 | 5 | 0.000 | 0.29 |
學曆的資訊熵為：
婚史
| 婚史 | 是（接受） | 否（不接受） | 頻次 | H | P |
| 無婚 | 4 | 2 | 6 | 0.918 | 0.43 |
| 有婚 | 2 | 2 | 4 | 1.000 | 0.29 |
| 二婚 | 3 | 1 | 4 | 0.811 | 0.29 |
婚史的資訊熵為：
房
| 房 | 是（接受） | 否（不接受） | 頻次 | H | P |
| 有房 | 3 | 4 | 7 | 0.985 | 0.50 |
| 無房 | 6 | 1 | 7 | 0.592 | 0.50 |
房的資訊熵為：
車
| 車 | 是（接受） | 否（不接受） | 頻次 | H | P |
| 有車 | 3 | 3 | 6 | 1.000 | 0.43 |
| 無車 | 6 | 2 | 8 | 0.811 | 0.57 |
車的資訊熵為：
3.計算不同條件下的資訊增益
| 條件 | 計算 | I(X,Y) |
| 學曆 | 0.940-0.69 | 0.25 |
| 婚史 | 0.940-0.92 | 0.02 |
| 房 | 0.940-0.79 | 0.15 |
| 車 | 0.940-0.89 | 0.05 |
選擇學曆資訊增益最大的值，做為節點。
4.對新的節點，循環1、2、3的操作，直到條件分類完
基于上面的學曆，我們分出的新的三個節點，專科、大學、碩士。在這些條件下，對應着不同的資料集。
1.1.3 基尼Gini指數
基尼指數(Gini不純度)表示在樣本集合中一個随機選中的樣本被分錯的機率。
Gini指數越小表示集合中被選中的樣本被分錯的機率越小。也就是集合的純度越高。
計算公式如下：
其中，表示選中的樣本屬于第k個類别的機率。
1.1.4 案例
回到剛才的案例，流程上與計算熵流程一緻，隻是說現在不是計算熵了，是計算基尼了
1.計算是否接受相親對象的基尼
| 是否接受 | 次數 | 機率 |
| 是 | 9 | 5/14 |
| 否 | 5 | 9/14 |
2.計算不同單一的條件下，每一個特征的基尼，最後并進行權重求和，得出單一條件的基尼
學曆
| 學曆 | 是（接受） | 否（不接受） | 頻次 | P |
| 專科 | 3 | 2 | 5 | 0.36 |
| 大學 | 2 | 3 | 4 | 0.36 |
| 碩士 | 4 | 5 | 0.29 |
權重的基尼：
婚史
| 婚史 | 是（接受） | 否（不接受） | 頻次 | P |
| 無婚 | 4 | 2 | 6 | 0.43 |
| 有婚 | 2 | 2 | 4 | 0.29 |
| 二婚 | 3 | 1 | 4 | 0.29 |
權重的基尼：
房
| 房 | 是（接受） | 否（不接受） | 頻次 | P |
| 有房 | 3 | 4 | 7 | 0.50 |
| 無房 | 6 | 1 | 7 | 0.50 |
權重的基尼：
車
| 車 | 是（接受） | 否（不接受） | 頻次 | P |
| 有車 | 3 | 3 | 6 | 0.43 |
| 無車 | 6 | 2 | 8 | 0.57 |
權重的基尼：
3.計算不同條件下的Gini增益
| 條件 | 計算 | G(X,Y) |
| 學曆 | 0.459-0.342 | 0.117 |
| 婚史 | 0.459-0.4405 | 0.0185 |
| 房 | 0.459-0.3674 | 0.0916 |
| 車 | 0.459-0.4286 | 0.0304 |
選擇學曆基尼增益最大的值，做為節點，
其實我們可以不用考慮增益這個計算，隻需要記住，求熵還是求基尼就看誰小，就增益就看誰大就行了。
1.2 回歸樹
回歸樹，用決策樹的模型來實作回歸模型，每一個一個樹的葉子為最後多個下特征的預測值，隻不過這個預測值是當下特征下，預測出的所有情況的均值。
還是回到原來的案例，在原來資料集上我們增加一列年齡，現在年齡才是我們的預測Y值。
假設我們訓練集三條這樣的特征(專科、無婚、無房、無車)，其中年齡的值如下圖，
這裡就需要對三個值，求平均值，用平均值的值作為三條資料的年齡，加入到模型訓練。
1.2.1 回歸樹分支标準
标準方差是回歸樹的分支标準，回歸樹将某一特征分成多個子集，用标準方差來衡量子集之間的元素是否相近，方差越小，證明這二個子集元素越相近，就不能劃分成二個子集，需要合并，方差越大，就說明二個子集是不同的。
1.2.2 案例
流程其實跟前面求熵，求基尼都差不多🥳
1.計算年齡的标準方差：
2.計算不同單一的條件下，每一個特征的标準方差，最後并進行權重求和，
學曆、婚史、房、車分别去年齡做資料透視圖
學曆
| 學曆 | 頻次 | 标準差 | P |
| 專科 | 5 | 7.78 | 0.36 |
| 大學 | 5 | 10.87 | 0.36 |
| 碩士 | 4 | 3.49 | 0.29 |
權重的标準差：
婚史
| 婚史 | 頻次 | 标準差S | P |
| 無婚 | 6 | 7.65 | 0.43 |
| 有婚 | 4 | 8.95 | 0.29 |
| 二婚 | 4 | 10.51 | 0.29 |
權重的标準差：
房
| 房 | 頻次 | 标準差S | P |
| 有房 | 7 | 9.36 | 0.50 |
| 無房 | 7 | 8.37 | 0.50 |
權重的标準差：
車
| 車 | 頻次 | 标準差S | P |
| 有車 | 6 | 10.59 | 0.43 |
| 無車 | 8 | 7.87 | 0.57 |
權重的标準差：
3.計算不同條件下标準差增益
| 條件 | 計算 | S(X,Y) |
| 學曆 | 9.32-7.66 | 1.66 |
| 婚史 | 9.32-9.15 | 0.17 |
| 房 | 9.32-9.04 | 0.28 |
| 車 | 9.32-9.03 |