機器學習算法整理(四)

語言: CN / TW / HK

機器學習算法整理(三)

決策樹

什麼是決策樹

比方説我們在招聘一個機器學習算法工程師的時候,會依照這樣的流程進行逐層的評選,從而達到一個樹形結構的決策過程。而在這棵樹中,它的深度為3.最多通過3次判斷,就能將我們的數據進行一個相應的分類。我們在這裏每一個節點都可以用yes或者no來回答的問題,實際上我們真實的數據很多內容都是一個具體的數值。對於這些具體的數值,決策樹是怎麼表徵的呢?我們先使用scikit-learn封裝的決策樹算法進行一下具體的分類。然後通過分類的結果再深入的認識一下決策樹。這裏我依然先加載鳶尾花數據集。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鳶尾花數據集的後兩個特徵
    X = iris.data[:, 2:]
    y = iris.target
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.scatter(X[y == 2, 0], X[y == 2, 1])
    plt.show()

運行結果

現在我們使用scikit-learn中的決策樹來進行分類

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鳶尾花數據集的後兩個特徵
    X = iris.data[:, 2:]
    y = iris.target
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier(max_depth=2, criterion='entropy')
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 繪製不規則決策邊界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.scatter(X[y == 2, 0], X[y == 2, 1])
    plt.show()

運行結果

這就是決策樹得到的決策邊界。通過這個圖,我們來畫一個決策樹,看看它是如何逐層決策的

這就是決策樹在面對屬性是一種數值特徵的時候是怎樣處理的。在這裏我們可以看到,在每一個節點上,它選擇某一個維度,以及和這個維度相應的閾值,比如説在根節點的時候選的是x這個維度和2.4這個閾值。看我們的數據是大於等於2.4還是小於2.4分成兩支。在右分支的子節點,選擇了y這個維度和1.8這個閾值,看數據點到了這個節點的話是小於1.8還是大於等於1.8來進行分類。

首先決策樹是一個非參數學習算法。其次決策樹可以解決分類問題,而且可以天然的解決多分類問題。不像邏輯迴歸和SVM需要使用OvR或者OvO才能解決多分類問題。同時決策樹也可以解決迴歸問題,我們可以用最終落在這個葉子節點中的所有的樣本數據的平均值來當作迴歸問題的預測值。決策樹算法也是具有非常好的可解釋性。比如説我們在給用户的信用進行評級,比如説他的信用卡超過3次拖延支付,並且他的駕照平均每年都會被扣去8分,滿足這樣的條件,他的信用評級就會評為C級。我們可以非常容易的描述出來把樣本數據分成某一個類的依據。我們現在的問題就是每個節點到底在哪個維度做劃分?我們的數據複雜起來的話可能有成百上千個維度。如果我們選好了一個維度,那麼我們要在某個維度的哪個值上做劃分?這些都是構建決策樹的關鍵問題。

信息熵

對於處理上面提到的問題——節點到底在哪個維度做劃分?某個維度的哪個值上做劃分?我們有一種方式來進行處理,那就是信息熵。

信息熵是信息論的基礎概念,熵在信息論中代表隨機變量不確定度的度量。熵越大,數據的不確定性越高;熵越小,數據的不確定性越低。熵是從物理熱力學中引申出來的概念,熵越大,在一個封閉的熱力系統中,分子無規則運動越劇烈,即不確定性越高;熵越小,封閉的熱力系統中,分子越傾向於靜止狀態,它們的狀態就越確定,即不確定性越低。我們來看一下香農提出來的信息熵公式。

其中表示一個系統中有k類的信息,每一類信息所佔的比例就叫做。比如説在我們的鳶尾花數據集中一共有3種鳶尾花,每一種鳶尾花佔的比例可能為1/3,則p1,p2,p3就分別等於1/3.由於一定是小於等於1的,log()是小於等於0的,那麼H一定是大於等於0的。

對於鳶尾花的這種各佔1/3的分類,它的信息熵就為

再比如有一種分類,其中一種分類佔1/10,第二種佔2/10,第三種佔7/10,那麼它的信息熵就為

這種分類的信息熵比鳶尾花分類的信息熵要小,意味着這種分類比鳶尾花的分類更確定。這是因為這種分類第三種分類佔了70%,所以這種分類是更確定的。而鳶尾花數據每一個類別各佔了1/3,所以這個數據整體它的不確定性就越高。我們再來看一組更極端的數據,依然是三類,其中一類佔100%。

信息熵為0,説明它的不確定性是最低的,即最確定的。在代碼上,我們以二分類為例來看一下這個公式的圖像是什麼樣子的。對於二分類來説,該公式可以轉化為

這裏x和1-x表示一類和另一類。

import numpy as np
import matplotlib.pyplot as plt

if __name__ == "__main__":

    def entropy(p):
        # 計算二分類信息熵
        return - p * np.log(p) - (1 - p) * np.log(1 - p)

    x = np.linspace(0.01, 0.99, 200)
    plt.plot(x, entropy(x))
    plt.show()

運行結果

從這個圖中,我們可以看出,當x=0.5的時候,我們的信息熵來説,如果我們的數據只有兩個類別,當每個類別各佔一半的時候,此時整個數據的信息熵就是最大的,此時我們整個數據是最不穩定的,確定性是最低的。在0.5兩邊,無論x值更小還是更大,整個信息熵都在降低,這裏因為無論x變小還是變大,我們的數據都偏向於某一類,整體的確定性變高了,所以相應的信息熵就變低了。

明白了這個概念,那麼這兩個問題就好説了——節點到底在哪個維度做劃分?某個維度的哪個值上做劃分?我們要讓我們的系統劃分後使得信息熵降低,換句話説相應的讓我們的系統變的更加確定。

比方説在極端情況下,在A、B、C這三個葉子節點的時候,每一個葉子數據都只屬於A、B、C這三類的某一類的話,那麼此時我們整個系統的信息熵就達到了0。所以我們就是要找在每一個節點上有一個維度,這個維度上有一個取值,根據這個維度和取值,對我們的數據進行劃分,劃分以後得到的信息熵是所有其他劃分方式得到的信息熵的最小值,我們稱這樣的一個劃分就是當前最好的劃分。我們只需要對所有的劃分可能性進行一次搜索就可以得到這個最好的劃分。我們只需要將這方式遞歸下去就形成了決策樹。

使用信息熵尋找最優劃分

模擬使用信息熵進行劃分

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap
from collections import Counter
from math import log

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鳶尾花數據集的後兩個特徵
    X = iris.data[:, 2:]
    y = iris.target
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier(max_depth=2, criterion='entropy')
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 繪製不規則決策邊界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()

    def split(X, y, d, value):
        '''
        劃分
        :param X: 特徵
        :param y: 輸出
        :param d: 維度
        :param value: 閾值
        :return:
        '''
        index_a = (X[:, d] <= value)
        index_b = (X[:, d] > value)
        return X[index_a], X[index_b], y[index_a], y[index_b]

    def entropy(y):
        '''
        計算信息熵
        :param y:
        :return:
        '''
        # 建立類別和數量的字典
        counter = Counter(y)
        res = 0
        for num in counter.values():
            p = num / len(y)
            res += - p * log(p)
        return res

    def try_split(X, y):
        '''
        搜索信息熵最小的維度和閾值
        :param X:
        :param y:
        :return:
        '''
        # 定義一個最好的信息熵,初始值為+∞
        best_entropy = float('inf')
        # 定義在哪個維度,哪個閾值上進行劃分,初始值都為-1
        best_d, best_v = -1, -1
        # 遍歷所有的特徵
        for d in range(X.shape[1]):
            # 對d維度上的數據進行排序
            sorted_index = np.argsort(X[:, d])
            # 遍歷所有的樣本數(不包含第一個樣本)
            for i in range(1, len(X)):
                # 拿取候選閾值,為d維的數據中每兩個數的中間值,且這兩個數不能相等
                if X[sorted_index[i - 1], d] != X[sorted_index[i], d]:
                    v = (X[sorted_index[i - 1], d] + X[sorted_index[i], d]) / 2
                    # 對候選維度和閾值嘗試劃分
                    X_l, X_r, y_l, y_r = split(X, y, d, v)
                    # 獲取對候選維度和候選閾值進行劃分後的信息熵
                    e = entropy(y_l) + entropy(y_r)
                    # 獲取信息熵最小的維度和閾值
                    if e < best_entropy:
                        best_entropy, best_d, best_v = e, d, v
        return best_entropy, best_d, best_v

    best_entropy, best_d, best_v = try_split(X, y)
    print("best_entropy =", best_entropy)
    print("best_d =", best_d)
    print("best_v =", best_v)

運行結果

best_entropy = 0.6931471805599453
best_d = 0
best_v = 2.45

根據結果,我們可以看出,我們對原始的數據進行劃分,是在第0個維度,閾值在2.45的位置進行劃分。劃分以後信息熵變成了0.693。對照這個結果,我們看一下在scikit-learn中的劃分結果

我們可以看到這個決策樹第一次劃分就是在橫軸上,也就是第0個維度,位置大概就是2.45的位置進行的劃分。現在我們將劃分後的數據進行存儲

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap
from collections import Counter
from math import log

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鳶尾花數據集的後兩個特徵
    X = iris.data[:, 2:]
    y = iris.target
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier(max_depth=2, criterion='entropy')
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 繪製不規則決策邊界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()

    def split(X, y, d, value):
        '''
        劃分
        :param X: 特徵
        :param y: 輸出
        :param d: 維度
        :param value: 閾值
        :return:
        '''
        index_a = (X[:, d] <= value)
        index_b = (X[:, d] > value)
        return X[index_a], X[index_b], y[index_a], y[index_b]

    def entropy(y):
        '''
        計算信息熵
        :param y:
        :return:
        '''
        # 建立類別和數量的字典
        counter = Counter(y)
        res = 0
        for num in counter.values():
            p = num / len(y)
            res += - p * log(p)
        return res

    def try_split(X, y):
        '''
        搜索信息熵最小的維度和閾值
        :param X:
        :param y:
        :return:
        '''
        # 定義一個最好的信息熵,初始值為+∞
        best_entropy = float('inf')
        # 定義在哪個維度,哪個閾值上進行劃分,初始值都為-1
        best_d, best_v = -1, -1
        # 遍歷所有的特徵
        for d in range(X.shape[1]):
            # 對d維度上的數據進行排序
            sorted_index = np.argsort(X[:, d])
            # 遍歷所有的樣本數(不包含第一個樣本)
            for i in range(1, len(X)):
                # 拿取候選閾值,為d維的數據中每兩個數的中間值,且這兩個數不能相等
                if X[sorted_index[i - 1], d] != X[sorted_index[i], d]:
                    v = (X[sorted_index[i - 1], d] + X[sorted_index[i], d]) / 2
                    # 對候選維度和閾值嘗試劃分
                    X_l, X_r, y_l, y_r = split(X, y, d, v)
                    # 獲取對候選維度和候選閾值進行劃分後的信息熵
                    e = entropy(y_l) + entropy(y_r)
                    # 獲取信息熵最小的維度和閾值
                    if e < best_entropy:
                        best_entropy, best_d, best_v = e, d, v
        return best_entropy, best_d, best_v

    best_entropy, best_d, best_v = try_split(X, y)
    print("best_entropy =", best_entropy)
    print("best_d =", best_d)
    print("best_v =", best_v)
    # 將第一次劃分後的數據進行存儲
    X1_l, X1_r, y1_l, y1_r = split(X, y, best_d, best_v)
    # 打印劃分後左子樹的信息熵
    print(entropy(y1_l))
    # 打印劃分後的右子樹的信息熵
    print(entropy(y1_r))

運行結果

best_entropy = 0.6931471805599453
best_d = 0
best_v = 2.45
0.0
0.6931471805599453

通過跟圖形對比,我們知道第一次劃分,我們把所有屬於第一類的數據全部劃分了進去,它沒有不確定性,所以第一次劃分的第一類的信息熵為0;而除第一類外的信息熵為0.693

對於第一類我們已經不需要劃分了,它的信息熵為0。而對於第一類之外的數據的信息熵為0.693,我們可以繼續對其進行劃分。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap
from collections import Counter
from math import log

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鳶尾花數據集的後兩個特徵
    X = iris.data[:, 2:]
    y = iris.target
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()
    dt_clf = DecisionTreeClassifier(max_depth=2, criterion='entropy')
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 繪製不規則決策邊界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()

    def split(X, y, d, value):
        '''
        劃分
        :param X: 特徵
        :param y: 輸出
        :param d: 維度
        :param value: 閾值
        :return:
        '''
        index_a = (X[:, d] <= value)
        index_b = (X[:, d] > value)
        return X[index_a], X[index_b], y[index_a], y[index_b]

    def entropy(y):
        '''
        計算信息熵
        :param y:
        :return:
        '''
        # 建立類別和數量的字典
        counter = Counter(y)
        res = 0
        for num in counter.values():
            p = num / len(y)
            res += - p * log(p)
        return res

    def try_split(X, y):
        '''
        搜索信息熵最小的維度和閾值
        :param X:
        :param y:
        :return:
        '''
        # 定義一個最好的信息熵,初始值為+∞
        best_entropy = float('inf')
        # 定義在哪個維度,哪個閾值上進行劃分,初始值都為-1
        best_d, best_v = -1, -1
        # 遍歷所有的特徵
        for d in range(X.shape[1]):
            # 對d維度上的數據進行排序
            sorted_index = np.argsort(X[:, d])
            # 遍歷所有的樣本數(不包含第一個樣本)
            for i in range(1, len(X)):
                # 拿取候選閾值,為d維的數據中每兩個數的中間值,且這兩個數不能相等
                if X[sorted_index[i - 1], d] != X[sorted_index[i], d]:
                    v = (X[sorted_index[i - 1], d] + X[sorted_index[i], d]) / 2
                    # 對候選維度和閾值嘗試劃分
                    X_l, X_r, y_l, y_r = split(X, y, d, v)
                    # 獲取對候選維度和候選閾值進行劃分後的信息熵
                    e = entropy(y_l) + entropy(y_r)
                    # 獲取信息熵最小的維度和閾值
                    if e < best_entropy:
                        best_entropy, best_d, best_v = e, d, v
        return best_entropy, best_d, best_v

    best_entropy, best_d, best_v = try_split(X, y)
    print("best_entropy =", best_entropy)
    print("best_d =", best_d)
    print("best_v =", best_v)
    # 將第一次劃分後的數據進行存儲
    X1_l, X1_r, y1_l, y1_r = split(X, y, best_d, best_v)
    # 打印劃分後左子樹的信息熵
    print(entropy(y1_l))
    # 打印劃分後的右子樹的信息熵
    print(entropy(y1_r))
    # 對右子樹繼續劃分
    best_entropy2, best_d2, best_v2 = try_split(X1_r, y1_r)
    print("best_entropy =", best_entropy2)
    print("best_d =", best_d2)
    print("best_v =", best_v2)
    X2_l, X2_r, y2_l, y2_r = split(X1_r, y1_r, best_d2, best_v2)
    # 打印第二次劃分後左子樹的信息熵
    print(entropy(y2_l))
    # 打印第二次劃分後的右子樹的信息熵
    print(entropy(y2_r))

運行結果

best_entropy = 0.6931471805599453
best_d = 0
best_v = 2.45
0.0
0.6931471805599453
best_entropy = 0.4132278899361904
best_d = 1
best_v = 1.75
0.30849545083110386
0.10473243910508653

對於第二次劃分,我們可以看信息熵降到最低是0.413,是在第1個維度,閾值在1.75的位置進行劃分。對比圖形,我們可以看到第二次劃分是在縱軸上,也就是第1個維度,位置大概就是在1.75的地方進行劃分的。並且劃分後,兩邊的信息熵都沒降為0,我們可以向更深的方向繼續劃分。

我們之前在scikit-learn中,max_depth=2,也就是深度值設為了2,也是劃分到此為止。當然我們已經知道了使用信息熵來構建決策樹,可以使用二叉樹的方式來建立這個決策樹,並打印這顆二叉樹,關於建立的方式可以參考數據結構整理 中關於二分搜索樹的內容來進行建立。

基尼係數

除了信息熵可以對決策樹的指標進行劃分,還有另外一個指標可以對決策樹進行劃分,這個指標就是基尼係數。基尼係數的公式如下

這個式子和信息熵對應的式子是有同樣的性質的,跟信息熵一樣,我們先使用幾個例子來看一下基尼係數。

通過這三個例子,我們可以看出,基尼係數和信息熵一樣可以用來作為數據不確定性的一個度量。我們同樣來看一下基尼係數的曲線是什麼樣子的。對於二分類來説,基尼係數的式子就可以化為

import numpy as np
import matplotlib.pyplot as plt

if __name__ == "__main__":

    def gini(p):
        # 計算二分類基尼係數
        return - 2 * p**2 + 2 * p

    x = np.linspace(0, 1, 200)
    plt.plot(x, gini(x))
    plt.show()

運行結果

現在我們模擬一下使用基尼係數進行劃分,看看結果是怎樣的。我們依然先使用scikit-learn來繪製一下使用基尼係數的決策樹的決策邊界。

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鳶尾花數據集的後兩個特徵
    X = iris.data[:, 2:]
    y = iris.target
    dt_clf = DecisionTreeClassifier(max_depth=2, criterion='gini', splitter='best')
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 繪製不規則決策邊界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
    plt.scatter(X[y == 0, 0], X[y == 0, 1])
    plt.scatter(X[y == 1, 0], X[y == 1, 1])
    plt.scatter(X[y == 2, 0], X[y == 2, 1])
    plt.show()

運行結果

現在我們再使用基尼係數來進行最優劃分

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from matplotlib.colors import ListedColormap
from collections import Counter

if __name__ == "__main__":

    iris = datasets.load_iris()
    # 保留鳶尾花數據集的後兩個特徵
    X = iris.data[:, 2:]
    y = iris.target
    dt_clf = DecisionTreeClassifier(max_depth=2, criterion='gini', splitter='best')
    dt_clf.fit(X, y)

    def plot_decision_boundary(model, axis):
        # 繪製不規則決策邊界
        x0, x1 = np.meshgrid(
            np.linspace(axis[0], axis[1], int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
            np.linspace(axis[2], axis[3], int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
        )
        X_new = np.c_[x0.ravel(), x1.ravel()]
        y_predict = model.predict(X_new)
        zz = y_predict.reshape(x0.shape)
        custom_cmap = ListedColormap(['#EF9A9A', '#FFF59D', '#90CAF9'])
        plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)

    # plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
    # plt.scatter(X[y == 0, 0], X[y == 0, 1])
    # plt.scatter(X[y == 1, 0], X[y == 1, 1])
    # plt.scatter(X[y == 2, 0], X[y == 2, 1])
    # plt.show()

    def split(X, y, d, value):
        '''
        劃分
        :param X: 特徵
        :param y: 輸出
        :param d: 維度
        :param value: 閾值
        :return:
        '''
        index_a = (X[:, d] <= value)
        index_b = (X[:, d] > value)
        return X[index_a], X[index_b], y[index_a], y[index_b]

    def gini(y):
        '''
        計算基尼係數
        :param y:
        :return:
        '''
        # 建立類別和數量的字典
        counter = Counter(y)
        res = 1
        for num in counter.values():
            p = num / len(y)
            res -= p**2
        return res

    def try_split(X, y):
        '''
        搜索基尼係數最小的維度和閾值
        :param X:
        :param y:
        :return:
        '''
        # 定義一個最好的基尼係數,初始值為+∞
        best_g = float('inf')
        # 定義在哪個維度,哪個閾值上進行劃分,初始值都為-1
        best_d, best_v = -1, -1
        # 遍歷所有的特徵
        for d in range(X.shape[1]):
            # 對d維度上的數據進行排序
            sorted_index = np.argsort(X[:, d])
            # 遍歷所有的樣本數(不包含第一個樣本)
            for i in range(1, len(X)):
                # 拿取候選閾值,為d維的數據中每兩個數的中間值,且這兩個數不能相等
                if X[sorted_index[i - 1], d] != X[sorted_index[i], d]:
                    v = (X[sorted_index[i - 1], d] + X[sorted_index[i], d]) / 2
                    # 對候選維度和閾值嘗試劃分
                    X_l, X_r, y_l, y_r = split(X, y, d, v)
                    # 獲取對候選維度和候選閾值進行劃分後的基尼係數
                    e = gini(y_l) + gini(y_r)
                    # 獲取基尼係數最小的維度和閾值
                    if e < best_g:
                        best_g, best_d, best_v = e, d, v
        return best_g, best_d, best_v

    best_g, best_d, best_v = try_split(X, y)
    print("best_g =", best_g)
    print("best_d =", best_d)
    print("best_v =", best_v)
    # 將第一次劃分後的數據進行存儲
    X1_l, X1_r, y1_l, y1_r = split(X, y, best_d, best_v)
    # 打印劃分後左子樹的基尼係數
    print(gini(y1_l))
    # 打印劃分後的右子樹的基尼係數
    print(gini(y1_r))
    # 對右子樹繼續劃分
    best_g2, best_d2, best_v2 = try_split(X1_r, y1_r)
    print("best_g =", best_g2)
    print("best_d =", best_d2)
    print("best_v =", best_v2)
    X2_l, X2_r, y2_l, y2_r = split(X1_r, y1_r, best_d2, best_v2)
    # 打印第二次劃分後左子樹的基尼係數
    print(gini(y2_l))
    # 打印第二次劃分後的右子樹的基尼係數
    print(gini(y2_r))

運行結果

best_g = 0.5
best_d = 0
best_v = 2.45
0.0
0.5
best_g = 0.2105714900645938
best_d = 1
best_v = 1.75
0.1680384087791495
0.04253308128544431

這裏通過第一次劃分,第一類的基尼係數為0,達到了一個最小值。除第一類的其他類的基尼係數為0.5。第一次劃分的維度為0,劃分的閾值為2.45。第二次劃分的最小基尼係數為0.21,第二次劃分的維度為1,劃分的閾值為1.75。對於剩下的兩個節點,它們的基尼係數依然沒有到0,我們可以對這兩個節點繼續向下劃分。

信息熵 vs 基尼係數

通過它們兩個的式子,我們可以看出來,信息熵的計算比基尼係數稍慢。在sikit-learn中的決策樹默認為基尼係數。在大多數時候,這二者沒有特別的效果優劣。對於決策樹有其更重要的參數,對比不必糾結這兩個參數。