決策樹(Decision Tree)是一種常見的機(jī)器學(xué)習(xí)算法，被廣泛應(yīng)用于分類和回歸任務(wù)中。并且再其之上的隨機(jī)森林和提升樹等算法一直是表格領(lǐng)域的最佳模型，所以本文將介紹理解其數(shù)學(xué)概念，并在Python中動(dòng)手實(shí)現(xiàn)，這可以作為了解這類算法的基礎(chǔ)知識。

在深入研究代碼之前，我們先要了解支撐決策樹的數(shù)學(xué)概念:熵和信息增益

熵：雜質(zhì)的量度

熵作為度量來量化數(shù)據(jù)集中的雜質(zhì)或無序。特別是對于決策樹，熵有助于衡量與一組標(biāo)簽相關(guān)的不確定性。數(shù)學(xué)上，數(shù)據(jù)集S的熵用以下公式計(jì)算:

Entropy(S) = -p_pos * log2(p_pos) - p_neg * log2(p_neg)

P_pos表示數(shù)據(jù)集中正標(biāo)簽的比例，P_neg表示數(shù)據(jù)集中負(fù)標(biāo)簽的比例。

更高的熵意味著更大的不確定性或雜質(zhì)，而更低的熵意味著更均勻的數(shù)據(jù)集。

信息增益：通過拆分提升知識

信息增益是評估通過基于特定屬性劃分?jǐn)?shù)據(jù)集所獲得的熵的減少。也就是說它衡量的是執(zhí)行分割后標(biāo)簽確定性的增加。

數(shù)學(xué)上，對數(shù)據(jù)集S中屬性a進(jìn)行分割的信息增益計(jì)算如下:

Information Gain(S, A) = Entropy(S) - ∑ (|S_v| / |S|) * Entropy(S_v)

S 表示原始數(shù)據(jù)集，A表示要拆分的屬性。S_v表示屬性A保存值v的S的子集。

目標(biāo)是通過選擇使信息增益最大化的屬性，在決策樹中創(chuàng)建信息量最大的分割。

在Python中實(shí)現(xiàn)決策樹算法

有了以上的基礎(chǔ)，就可以使用Python從頭開始編寫Decision Tree算法。

首先導(dǎo)入基本的numpy庫，它將有助于我們的算法實(shí)現(xiàn)。

import numpy as np

創(chuàng)建DecisionTree類

class DecisionTree:
    def __init__(self, max_depth=None):
        self.max_depth = max_depth

定義了DecisionTree類來封裝決策樹。max_depth參數(shù)是樹的最大深度，以防止過擬合。

def fit(self, X, y, depth=0):
        n_samples, n_features = X.shape
        unique_classes = np.unique(y)
         
        # Base cases
        if (self.max_depth is not None and depth >= self.max_depth) or len(unique_classes) == 1:
            self.label = unique_classes[np.argmax(np.bincount(y))]
            return

擬合方法是決策樹算法的核心。它需要訓(xùn)練數(shù)據(jù)X和相應(yīng)的標(biāo)簽，以及一個(gè)可選的深度參數(shù)來跟蹤樹的深度。我們以最簡單的方式處理樹的生長：達(dá)到最大深度或者遇到純類。

確定最佳分割屬性，循環(huán)遍歷所有屬性以找到信息增益最大化的屬性。_information_gain方法(稍后解釋)幫助計(jì)算每個(gè)屬性的信息增益。

best_attribute = None
 best_info_gain = -1
 for feature in range(n_features):
            info_gain = self._information_gain(X, y, feature)
            if info_gain > best_info_gain:
                best_info_gain = info_gain
                best_attribute = feature

處理不分割屬性，如果沒有屬性產(chǎn)生正的信息增益，則將類標(biāo)簽分配為節(jié)點(diǎn)的標(biāo)簽。

if best_attribute is None:
            self.label = unique_classes[np.argmax(np.bincount(y))]
            return

分割和遞歸調(diào)用，下面代碼確定了分割的最佳屬性，并創(chuàng)建兩個(gè)子節(jié)點(diǎn)。根據(jù)屬性的閾值將數(shù)據(jù)集劃分為左右兩個(gè)子集。

self.attribute = best_attribute
 self.threshold = np.median(X[:, best_attribute])
 
 left_indices = X[:, best_attribute] <= self.threshold
    right_indices = ~left_indices
 
    self.left = DecisionTree(max_depth=self.max_depth)
    self.right = DecisionTree(max_depth=self.max_depth)
 
    self.left.fit(X[left_indices], y[left_indices], depth + 1)
    self.right.fit(X[right_indices], y[right_indices], depth + 1)

并且通過遞歸調(diào)用左子集和右子集的fit方法來構(gòu)建子樹。

預(yù)測方法使用訓(xùn)練好的決策樹進(jìn)行預(yù)測。如果到達(dá)一個(gè)葉節(jié)點(diǎn)(帶有標(biāo)簽的節(jié)點(diǎn))，它將葉節(jié)點(diǎn)的標(biāo)簽分配給X中的所有數(shù)據(jù)點(diǎn)。

def predict(self, X):
        if hasattr(self, 'label'):
            return np.array([self.label] * X.shape[0])

當(dāng)遇到非葉節(jié)點(diǎn)時(shí)，predict方法根據(jù)屬性閾值遞歸遍歷樹的左子樹和右子樹。來自雙方的預(yù)測被連接起來形成最終的預(yù)測數(shù)組。

is_left = X[:, self.attribute] <= self.threshold
        left_predictions = self.left.predict(X[is_left])
        right_predictions = self.right.predict(X[~is_left])
         
        return np.concatenate((left_predictions, right_predictions))

下面兩個(gè)方法是決策樹的核心代碼，并且可以使用不同的算法來進(jìn)行計(jì)算，比如ID3 算法使用信息增益作為特征選擇的標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)度量了將某特征用于劃分?jǐn)?shù)據(jù)后，對分類結(jié)果的不確定性減少的程度。算法通過遞歸地選擇信息增益最大的特征來構(gòu)建決策樹，也就是我們現(xiàn)在要演示的算法。

_information_gain方法計(jì)算給定屬性的信息增益。它計(jì)算分裂后子熵的加權(quán)平均值，并從父熵中減去它。

def _information_gain(self, X, y, feature):
        parent_entropy = self._entropy(y)
         
        unique_values = np.unique(X[:, feature])
        weighted_child_entropy = 0
         
        for value in unique_values:
            is_value = X[:, feature] == value
            child_entropy = self._entropy(y[is_value])
            weighted_child_entropy += (np.sum(is_value) / len(y)) * child_entropy
         
        return parent_entropy - weighted_child_entropy

熵的計(jì)算

def _entropy(self, y):
        _, counts = np.unique(y, return_counts=True)
        probabilities = counts / len(y)
        return -np.sum(probabilities * np.log2(probabilities))

_entropy方法計(jì)算數(shù)據(jù)集y的熵，它計(jì)算每個(gè)類的概率，然后使用前面提到的公式計(jì)算熵。

常見的算法還有：

C4.5 是 ID3 的改進(jìn)版本，C4.5 算法在特征選擇時(shí)使用信息增益比，這是對信息增益的一種歸一化，用于解決信息增益在選擇特征時(shí)偏向于取值較多的特征的問題。

CART 與 ID3 和 C4.5 算法不同，CART(Classification And Regression Tree)又被稱為分類回歸樹，算法采用基尼不純度(Gini impurity)來度量節(jié)點(diǎn)的不確定性，該不純度度量了從節(jié)點(diǎn)中隨機(jī)選取兩個(gè)樣本，它們屬于不同類別的概率。

ID3、C4.5 和 CART 算法都是基于決策樹的經(jīng)典算法，像Xgboost就是使用的CART 作為基礎(chǔ)模型。

總結(jié)

以上就是使用Python中構(gòu)造了一個(gè)完整的決策樹算法的全部。決策樹的核心思想是根據(jù)數(shù)據(jù)的特征逐步進(jìn)行劃分，使得每個(gè)子集內(nèi)的數(shù)據(jù)盡量屬于同一類別或具有相似的數(shù)值。在構(gòu)建決策樹時(shí)，通常會(huì)使用一些算法來選擇最佳的特征和分割點(diǎn)，以達(dá)到更好的分類或預(yù)測效果。