決策樹

習題預習

1. 決策樹在什麼場景下使用效果最好？
2. 決策樹的主要優點和缺點是什麼？
3. 如何選擇最佳的分割點？
4. 如何處理缺失的數據？
5. 如何解決決策樹容易出現過擬合現象的問題？

說明知識

決策樹是一種機器學習演算法，用於對數據進行預測和分類。它是一種可視化的算法，因為其計算過程可以被表示為一棵樹，每個節點代表一個屬性或決策，每個分支代表一個可能的結果。

以下是一個簡單的例子：假設有一組數據，其中包含了很多人的年齡、性別、收入和婚姻狀況等信息，那麼我們可以使用決策樹來分類這些人是否會買房子。首先，我們可以選擇一個屬性，例如年齡，作為根節點，然後按照年齡的不同區間（例如年齡小於30歲、30歲到50歲、大於50歲）分成三個分支。然後，對於每個分支，我們可以選擇另一個屬性，例如收入，然後按照收入的不同區間分成更小的分支。最終，我們可以得到一個包含多個節點和分支的樹，每一個葉子節點代表一個結果，例如「買房子」或「不買房子」。

通過這棵決策樹，我們可以為新的數據進行預測，只需要按照樹的分支進行選擇，最終得到該數據的預測結果。此外，我們還可以通過該樹來了解不同屬性在預測中的重要性，從而對數據進行更精確的分析和處理。

條列重點

1. 決策樹是機器學習中的一種監督式學習算法。

2. 決策樹運用樹形結構來呈現決策流程。

3. 決策樹的每個節點表示一個決策，每個邊表示一個決策的影響。

4. 決策樹遵循「分而治之」的策略，將問題拆分成多個子問題。

5. 決策樹可以處理離散和連續型變量，可以應用在分類和回歸問題上。

6. 決策樹的建構過程包括選擇最佳切割點和決定樹的深度。

7. 決策樹可能存在過擬合和欠擬合問題，在建構過程中需要適當的剪枝。

8. 決策樹的預測速度較快，且易於理解和解釋。

9. 決策樹的應用廣泛，包括金融、醫療、天氣預測等領域。

知識測驗

1. 有一個資料集包含了1000筆資料，每筆資料有4個特徵及1個二元標籤（1或0）。訓練一個二元Decision Tree來預測標籤。如果使用全部資料訓練，Decision Tree的深度最多可以設為多少？
   答案：log2(1000) = 9.97，所以Decision Tree的深度應該設為10。

2. 在一個Decision Tree中，某個節點的Gini impurity值為0.3，該節點有5個樣本，其中2個屬於正例，3個屬於負例。如果把該節點分裂為兩個子節點，如何最小化Gini impurity？
   答案：計算左右兩個子節點的加權Gini impurity，找到最小值即可。例如，將兩個樣本分配到左子節點，另外三個樣本分配到右子節點，得到左子節點的Gini impurity值為0，右子節點的Gini impurity值為0.444。因此，最好的分裂方式是將兩個樣本分配到左子節點，另外三個樣本分配到右子節點。

3. 在一個Decision Tree中，某個節點的Gini impurity值為0.4，該節點有3個樣本，其中2個屬於正例，1個屬於負例。考慮一個二元特徵x，將節點分裂為左右兩個子節點，如果x等於1則進入右子節點，否則進入左子節點。如果x等分界值t則分裂為左右兩個子節點。請問，如何計算x等分界值t？
   答案：從小到大將特徵x的值排序，用每個值當作分界值t，計算Gini impurity的下降量，找到最大的下降量對應的分界值t即可。例如，排序後的特徵值序列為(0, 0, 1)，各自對應的標籤值為(0, 1, 1)，計算t為0.5的下降量為0.067，計算t為1的下降量為0.25，因此最好的分界值是1。

4. 有一個Decision Tree訓練完畢後，其中某個節點A分裂為兩個子節點B和C，如果將子節點B進一步分裂，則Gini impurity值下降為0.1，如果將子節點C進一步分裂，則Gini impurity值下降為0.05。請問，是否可以將子節點C進一步分裂？
   答案：不能確定，因為沒有考慮到整棵Decision Tree的訓練過程。如果在子節點C之前已經有其他節點分裂了，則子節點C進一步分裂可能會導致過度擬合，並且沒有明顯的收益。如果尚未有其他節點分裂，則可以考慮將子節點C進一步分裂，以提高整個Decision Tree的泛化能力。

5. 在一個Decision Tree中，某個節點的Gini impurity值為0.4，該節點有3個樣本，其中2個屬於正例，1個屬於負例。考慮一個多元特徵(x1,x2)，將節點分裂為左右兩個子節點，如果x1等於1且x2等於0則進入左子節點，否則進入右子節點。如果x1等分界值t1，x2等分界值t2則分裂為左右兩個子節點。請問，如何計算x1和x2等分界值t1和t2？
   答案：計算每對(x1,x2)的Gini impurity下降量，找到最大的下降量對應的分界值t1和t2即可。例如，將(x1,x2)分為4個區域，各自對應的標籤值為(0, 0, 1, 1)，計算左區域的Gini impurity值為0，右區域的Gini impurity值為0.5。接著，計算x1等於0.5和x2等於0.5的下降量為0.167，計算x1等於0.5和x2等於1的下降量為0.3，計算x1等於1和x2等於0.5的下降量為0.167，計算x1等於1和x2等於1的下降量為0，因此最好的分界值是x1等於0.5，x2等於0.5。