CART決策樹

一、基本概念

CART（Classification and Regression Trees）決策樹是一種典型的分類和回歸的樹形結構模型，由於其簡單、易於理解和實現，在實際應用中得到廣泛應用。 CART決策樹包含兩種類型：分類樹和回歸樹，其中分類樹用於分類問題，回歸樹用於回歸問題。

CART決策樹構建過程的核心是在每個節點上尋找最佳的分裂特徵和分裂點。節點的分裂是指根據某個特徵和對應的分裂點將節點劃分為左右兩個子節點。劃分的目的是儘可能地將同一類別的樣本放到同一子節點中，同時儘可能地將不同類別的樣本分到不同的子節點中。

在CART決策樹的構建過程中，我們需要採用一些指標來衡量節點的「純度」，這些指標主要有基尼係數和信息增益兩種。其中基尼係數是CART決策樹使用的默認指標，它的計算很簡單，公式如下：

Gini(p) = 1 - ∑(i=1～k) p(i)^2

其中k表示類別的個數，p(i)表示樣本屬於第i類的概率。當一個節點中的樣本全部屬於同一個類別時，基尼係數最小為0；當一個節點中的樣本屬於不同的類別時，基尼係數最大為1。

二、分類樹的構建

對於分類問題，CART決策樹的構建過程如下：

1、節點的初始狀態：

將所有樣本看作一個整體，將整個訓練數據集看作一個節點，在該節點上找到最佳的分裂特徵和分裂點來確定左右子節點，將數據集分為兩部分，第一部分樣本屬於某一個類別，第二部分樣本屬於其他類別。

2、節點的分裂：

根據某個特徵和對應的分裂點將節點劃分為左右兩個子節點，這個分裂點的選擇在回歸樹和分類樹中不同。在分類樹中，為了讓同一類別的樣本盡量分到同一節點中，我們需要找到最優的分裂特徵和分裂點。 在這個過程中，我們需要設計一個評價指標來衡量節點的純度。常用的指標有基尼係數和信息熵。

3、遞歸構建樹：

對於當前節點的左右兩個子節點，重複執行步驟2和步驟3，直到達到預設的停止條件，例如節點中的樣本數量達到了預設的最小值，或者節點的深度達到了預設的最大值。當無法再分裂時，節點變為葉節點。

三、回歸樹的構建

對於回歸問題，CART決策樹的構建過程如下：

1、節點的初始狀態：

將所有樣本看作一個整體，將整個訓練數據集看作一個節點，在該節點上找到最佳的分裂特徵和分裂點來確定左右子節點，將數據集分為兩部分，第一部分樣本擬合出的回歸函數與真實值的誤差儘可能小，第二部分樣本擬合出的回歸函數與真實值的誤差儘可能小。

2、節點的分裂：

根據某個特徵和對應的分裂點將節點劃分為左右兩個子節點，這個分裂點的選擇需要最小化誤差平方和，即：

min∑(y-y_hat)^2

其中y表示真實值，y_hat表示預測值。回歸樹採用的是一種自頂向下、貪心的策略，即每次選擇最優的特徵進行分裂，因此得到的樹是不穩定的，容易受到噪聲的影響。

3、遞歸構建樹：

對於當前節點的左右兩個子節點，重複執行步驟2和步驟3，直到達到預設的停止條件，例如節點中的樣本數量達到了預設的最小值，或者節點的深度達到了預設的最大值。當無法再分裂時，節點變為葉節點。

四、代碼示例

以下示例代碼展示了如何使用CART決策樹進行分類：

import numpy as np
from sklearn.tree import DecisionTreeClassifier

# 構造示例數據集
X = np.array([
    [5.1, 3.5, 1.4, 0.2],
    [4.9, 3.0, 1.4, 0.2],
    [6.2, 3.4, 5.4, 2.3],
    [5.9, 3.0, 5.1, 1.8]])
y = np.array([0, 0, 1, 1])

# 構建分類樹模型
clf = DecisionTreeClassifier()
clf.fit(X, y)

# 預測新樣本類別
x_test = np.array([5.8, 2.8, 5.1, 2.4])
y_pred = clf.predict([x_test])

print("預測類別為:", y_pred)  # 輸出預測結果