決策樹

定義

從根節點開始，也就是擁有全部的數據，找一個維度對根節點開始劃分，

劃分后希望數據整體的信息熵是最小的，

針對劃分出來的兩個節點，我們繼續重復剛才的劃分方式尋找信息熵最小的維度和閾值。

遞歸這個過程就形成了決策樹。

特點

非參數學習算法

可以解決分類問題

天然可以解決多分類問題

非常好的可解釋性

代碼實現

sklearn封裝的方式

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
# 學習使用數據集，去后兩個維度，便于可視化
iris = datasets.load_iris()
X = iris.data[:, 2:]
y = iris.targetdt_clf = DecisionTreeClassifier(max_depth=2, criterion="entropy", random_state=42)
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)from matplotlib.colors import ListedColormapcustom_cmap = ListedColormap(["#EF9A9A", "#FFF59D", "#90CAF9"])plt.contourf(x0, x1, zz, cmap=custom_cmap)plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
# X[y==0,0]表示樣本target為0的，第一個維度，其余類推
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()

信息熵（重要知識）

熵在信息論中代表：隨機變量不確定度的度量。

熵越大，數據的不確定性越高；熵越小，數據的不確定性越低，公式如下：
$$\begin{gathered} H=?\sum _{i?1}^k{p}_i\log (p_i) \\ {p}_i類別i的概率 \end{gathered}$$
如以下兩組數據的隨機分布如下：
{ 1 3 , 1 3 , 1 3 } H = ? 1 3 log ? 1 3 ? 1 3 log ? 1 3 ? 1 3 log ? 1 3 = 1.0986 { 1 10 , 2 10 , 7 10 } H = ? 1 10 log ? 1 10 ? 2 10 log ? 2 10 ? 7 10 log ? 7 10 = 0.8018 \{\frac{1}{3},\frac{1}{3},\frac{1}{3}\} \\ H = -\frac{1}{3}\log{\frac{1}{3}}-\frac{1}{3}\log{\frac{1}{3}}-\frac{1}{3}\log{\frac{1}{3}} = 1.0986 \\ \\ \{\frac{1}{10},\frac{2}{10},\frac{7}{10}\} \\ H = -\frac{1}{10}\log{\frac{1}{10}}-\frac{2}{10}\log{\frac{2}{10}}-\frac{7}{10}\log{\frac{7}{10}} = 0.8018 \\ {31?,31?,31?}H=?31?log31??31?log31??31?log31?=1.0986{101?,102?,107?}H=?101?log101??102?log102??107?log107?=0.8018

二分類問題信息熵的公式可化簡為：
$$H=?x\log ?(x)?(1?x)\log (1?x)$$

import numpy as np
import matplotlib.pyplot as plt
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()

最小化信息熵劃分數據維度和閾值，模擬sklearn中的封裝方法

import numpy as np
from collections import Counter
from math import log
from sklearn import datasetsiris = datasets.load_iris()
X = iris.data[:, 2:]
y = iris.targetdef split(X, y, d, value):"""函數功能：根據給定的特征維度d和閾值value，將數據集進行劃分X、y分別是數據樣本和標簽d是數據的某一個維度value是d維度上的一個閾值"""# 尋找所有數據集中維度為d且小于等于value的bool向量index_a = X[:, d] <= valueindex_b = X[:, d] > valuereturn X[index_a], X[index_b], y[index_a], y[index_b]def entropy(y):"""計算信息熵y:類別標簽, 類似[0,0,1,1,2,2,2,2]"""counter = Counter(y)res = 0.0for num in counter.values():p_i = num / len(y)  # 計算每個類別的概率res += -p_i * log(p_i)return resdef try_split(X, y):"""尋找傳入數據的最優劃分方案（信息熵最小）最優的維度和劃分閾值"""# 最優信息熵best_entropy = float("inf")best_d, best_v = -1, -1# 搜索過程：從d=0以及d這個維度升序后的相鄰樣本的均值開始for d in range(X.shape[1]):# 返回排序(升序)后索引sorted_index = np.argsort(X[:, d])for i in range(1, len(X)):if X[sorted_index[i], d] != X[sorted_index[i - 1], d]:# 候選閾值value的確認方式，且相鄰的兩個值不相等(剪枝)v = (X[sorted_index[i], d] + X[sorted_index[i - 1], d]) / 2X_l, X_r, y_l, y_r = split(X, y, d, v)p_l, p_r = len(X_l) / len(X), len(X_r) / len(X)  # 可以刪除占比e = p_l * entropy(y_l) + p_r * entropy(y_r)if e < best_entropy:  # 更新最小熵、最優維度d以及該維度上的最優閾值vbest_entropy, best_d, best_v = e, d, vreturn best_entropy, best_d, best_vbest_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.46209812037329684
# best_d = 0
# best_v = 2.45
# 解釋：第一次劃分在第0個維度上，閾值為2.45，信息熵最優# 根據第一次的最優劃分條件，對數據集進行劃分
X1_l, X1_r, y1_l, y1_r = split(X, y, best_d, best_v)
entropy(y1_l)  # 0.0 y1_l信息熵為0，對應X1_l節點無需再劃分
entropy(y1_r)  # y1_r信息熵0.6931471805599453，繼續劃分X1_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)
# best_entropy = 0.2147644654371359
# best_d = 1
# best_v = 1.75X2_l, X2_r, y2_l, y2_r = split(X1_r, y1_r, best_d2, best_v2)
entropy(y2_l) # 0.30849545083110386
entropy(y2_r)  # 0.10473243910508653
# 信息熵不為0還可以繼續劃分，此時深度為2

基尼系數

基尼系數公式如下：
$$G=1?\sum _{i=1}^k{p}_i^2$$
基尼系數和信息熵擁有同樣的性質。

基尼系數代碼實現

from collections import Counterdef gini(y):counter = Counter(y)res = 1.0for num in counter.values():p = num / len(y)res -= p**2return res

CART

決策樹又稱：Classification And Regression Tree

復雜度分析：

預測：$O(logm)$

預測：$O(n?m?logm)$

$n、m$ 分別是樣本數量和數據維度。

決策樹的局限性

1、決策數是在某一個維度上進行劃分，所以產生的決策邊界都是和數據維度平行的，并不會產生傾斜的邊界，有時真實數據可能并非如此。

2、決策樹會對個別的樣本點是非常敏感的，某一個特殊的樣本點可能都會改變決策樹的決策邊界。