決策樹(Decision Tree)是一種基于規(guī)則的基礎而又經典的分類與回歸方法，其模型結構呈現樹形結構件缸，可認為是一組if-then規(guī)則的集合。

決策樹主要包含三個步驟：特征選擇叔遂、決策樹構建和決策樹剪枝他炊。

典型的決策樹有ID3、C4.5和CART(Classification And Regression)已艰，它們的主要區(qū)別在于樹的結構與構造算法痊末。其中ID3和C4.5只支持分類，而CART支持分類和回歸哩掺。

1.決策樹簡介

1.1. ID3決策樹

ID3決策樹根據信息增益來構建決策樹凿叠；
對訓練集(或子集) D，計算其每個特征的信息增益嚼吞，并比較大小盒件，選擇信息增益最大的特征作為該節(jié)點的特征，由該節(jié)點的不同取值建立子節(jié)點舱禽。再對子節(jié)點遞歸以上步驟履恩，構建決策樹；直到所有特征的信息增益均小于預設閾值或沒有特征為止呢蔫。

缺點： 信息增益偏向取值較多的特征

舉個例子切心，如果以身份證號作為一個屬性去劃分數據集，則數據集中有多少個人就會有多少個子類別片吊，而每個子類別中只有一個樣本绽昏，故 則信息增益，此時信息增益最大俏脊，選擇該特征(身份證號)劃分數據全谤，然而這種劃分毫無意義，但是從信息增益準則來講爷贫，這就是最好的劃分屬性认然。

信息增益(information gain)表示得知特征 X 的信息而使得類 Y的信息的不確定性減少的程度。

1.2. C4.5決策樹

C4.5決策樹根據信息增益比來構建決策樹漫萄；
C4.5算法與ID3算法只是將ID3中利用信息增益選擇特征換成了利用信息增益比選擇特征卷员。

1.3. CART決策樹

CART決策樹根據基尼系數來構建決策樹。

CART決策樹生成步驟

算法的終止條件：節(jié)點中樣本個數小于預定閾值腾务，或者樣本中基尼系數小于預定閾值(樣本基本屬于同一類)毕骡，或者沒有更多特征。

ID3、C4.5和CART算法對比

2. 決策樹的sklearn實現

決策樹的sklearn實現主要是DecisionTreeClassifier函數(分類，回歸函數DecisionTreeRegressor)叙凡。

class sklearn.tree.DecisionTreeClassifier(
    criterion=’gini’,               # 該函數用于衡量分割的依據劈伴。常見的有"gini"用來計算基尼系數和"entropy"用來計算信息增益
    splitter=’best’, 
    max_depth=None,                 # 樹的最大深度
    min_samples_split=2,            # 分割內部節(jié)點所需的最小樣本數
    min_samples_leaf=1,             # 葉節(jié)點上所需的最小樣本數
    min_weight_fraction_leaf=0.0, 
    max_features=None, 
    random_state=None, 
    max_leaf_nodes=None, 
    min_impurity_decrease=0.0, 
    min_impurity_split=None, 
    class_weight=None, 
    presort=False
)

具體實現如下，完整代碼可參考Github

import pickle
import random
import time

import numpy as np
from sklearn.feature_extraction.text import TfidfVectorizer, TfidfTransformer
from sklearn.tree import DecisionTreeClassifier
from sklearn import metrics
from tqdm import tqdm


def train_model(train_data, test_data):
    # 打亂樣本握爷，以免同類別樣本集中
    train_xy = [(cls, d) for cls, data in train_data.items() for d in data]
    random.shuffle(train_xy)
    train_x = [d for _, d in train_xy]
    train_y = [cls for cls, _ in train_xy]
    # train_x, train_y = [], []
    # for cls, data in train_data.items():
    #     train_x += data
    #     train_y += [cls] * len(data)

    t1 = time.time()
    # 將得到的詞語轉換為詞頻矩陣
    vectorizer = TfidfVectorizer(min_df=1)
    # 統計每個詞語的tf-idf權值
    transformer = TfidfTransformer()
    # 訓練tfidf模型
    train_tfidf = transformer.fit_transform(vectorizer.fit_transform(np.array(train_x)))
    # 訓練決策樹模型
    dt_cls = DecisionTreeClassifier(random_state=0).fit(train_tfidf, train_y)
    t2 = time.time()
    pickle.dump((vectorizer, transformer, dt_cls), open("./model.pickle", "wb"))
    print('train model over. it took {0}ms'.format((t2 - t1)))

    # 預測測試數據
    y_true, y_pred = [], []
    for cls, data in tqdm(test_data.items()):
        for d in data:
            test_tfidf = transformer.transform(vectorizer.transform([d]))
            prediction = dt_cls.predict(test_tfidf)[0]
            y_pred.append(prediction)
            y_true.append(cls)
    # 輸出各類別測試測試參數
    classify_report = metrics.classification_report(y_true, y_pred)
    print(classify_report)


if __name__ == '__main__':
    train = pickle.load(open("./train_data.pickle", "rb"))
    test = pickle.load(open("./test_data.pickle", "rb"))
    train_model(train_data=train, test_data=test)

3. 決策樹的python實現

ID3和C4.5算法只是特征選擇方式不同跛璧，其他創(chuàng)建過程一致。完整代碼可參考Github

def create_tree_by_id3_and_c45(self, x, y, feature_list=None):
    """
    創(chuàng)建決策樹
    :param x:
    :param y:
    :param feature_list:
    :return:
    """
    # the type is the same, so stop classify
    if len(set(y)) <= 1:
        return y[0]
    # traversal all the features and choose the most frequent feature
    if len(x[0]) == 1:
        return Counter(y).most_common(1)

    feature_list = [i for i in range(len(y))] if not feature_list else feature_list
    if self.decision_tree_type == 'ID3':
        best_feature_idx = self.dataset_split_by_id3(x, y)
    elif self.decision_tree_type == 'C45':
        best_feature_idx = self.dataset_split_by_c45(x, y)
    else:
        raise KeyError
    decision_tree = {best_feature_idx: {}}
    feature_list = feature_list[:best_feature_idx] + feature_list[best_feature_idx + 1:]
    # get the list which attain the whole properties
    best_feature_values = set([sample[best_feature_idx] for sample in x])
    for value in best_feature_values:
        sub_dataset, sub_labels = [], []
        for featVec, label in zip(x, y):
            if featVec[best_feature_idx] == value:
                sub_dataset.append(list(featVec[:best_feature_idx]) + list(featVec[best_feature_idx + 1:]))
                sub_labels.append(label)

        decision_tree[best_feature_idx][value] = self.create_tree_by_id3_and_c45(sub_dataset, sub_labels, feature_list)

    return decision_tree

CART根據基尼系數進行特征選擇饼拍。完整代碼可參考Github

def create_tree_by_cart(self, x, y, feature_list=None):
    """
    輸入：訓練數據集D赡模，特征集A田炭，閾值ε
    輸出：決策樹T
    """
    y_lables = np.unique(y)

    # 1师抄、如果數據集D中的所有實例都屬于同一類label（Ck），則T為單節(jié)點樹教硫，并將類label（Ck）作為該結點的類標記叨吮，返回T
    if len(set(y_lables)) == 1:
        return y_lables[0]

    # 2、若特征集A=空瞬矩，則T為單節(jié)點茶鉴，并將數據集D中實例樹最大的類label（Ck）作為該節(jié)點的類標記，返回T
    if len(x[0]) == 0:
        labelCount = dict(Counter(y_lables))
        return max(labelCount, key=labelCount.get)

    # 3景用、否則涵叮，按CART算法就計算特征集A中各特征對數據集D的Gini，選擇Gini指數最小的特征bestFeature（Ag）進行劃分
    best_feature_and_idx, _ = self.dataset_split_by_cart(x, y)

    feature_list = [i for i in range(len(x[0]))] if not feature_list else feature_list
    best_feature_idx = feature_list[int(best_feature_and_idx[0])]  # 最佳特征

    decision_tree = {best_feature_idx: {}}  # 構建樹伞插，以Gini指數最小的特征bestFeature為子節(jié)點
    # feature_list = feature_list[:best_feature_idx] + feature_list[best_feature_idx + 1:]
    feature_list.pop(int(best_feature_and_idx[0]))

    # 使用beatFeature進行劃分割粮，劃分產生2個節(jié)點，成樹T媚污，返回T
    y_lables_split = y[list(x[:, int(best_feature_and_idx[0])] == best_feature_and_idx[1])]  # 獲取按此劃分后y數據列表
    y_lables_grp = Counter(y_lables_split)  # 統計最優(yōu)劃分應該屬于哪個i葉子節(jié)點“是”舀瓢、“否”
    y_leaf = y_lables_grp.most_common(1)[0][0]  # 獲得劃分后出現概率最大的y分類
    decision_tree[best_feature_idx][best_feature_and_idx[1]] = y_leaf  # 設定左枝葉子值

    # 4、刪除此最優(yōu)劃分數據x列耗美，使用其他x列數據京髓，遞歸地調用步1-3，得到子樹Ti商架，返回Ti
    sub_x = np.delete(x, int(best_feature_and_idx[0]), axis=1)  # 刪除此最優(yōu)劃分x列堰怨，使用剩余的x列進行數據劃分
    # 判斷右枝類型，劃分后的左右枝“是”蛇摸、“否”是不一定的诚些，所以這里進行判斷
    y1 = y_lables[0]  # CART樹y只能有2個分類
    y2 = y_lables[1]
    if y_leaf == y1:
        decision_tree[best_feature_idx][y2] = self.create_tree_by_cart(sub_x, y, feature_list)
    elif y_leaf == y2:
        decision_tree[best_feature_idx][y1] = self.create_tree_by_cart(sub_x, y, feature_list)

    return decision_tree

利用《統計學習方法》中P59例子數據

X = [
        ["青年", "否", "否", "一般"],
        ["青年", "否", "否", "好"],
        ["青年", "是", "否", "好"],
        ["青年", "是", "是", "一般"],
        ["青年", "否", "否", "一般"],
        ["中年", "否", "否", "一般"],
        ["中年", "否", "否", "好"],
        ["中年", "是", "是", "好"],
        ["中年", "否", "是", "非常好"],
        ["中年", "否", "是", "非常好"],
        ["老年", "否", "是", "非常好"],
        ["老年", "否", "是", "好"],
        ["老年", "是", "否", "好"],
        ["老年", "是", "否", "非常好"],
        ["老年", "否", "否", "一般"]
    ]
    Y = ["否", "否", "是", "是", "否", "否", "否", "是", "是", "是", "是", "是", "是", "是", "否"]

生成決策樹，可視化代碼可參考Github

ID3和C4.5算法生成的決策樹

CART算法生成的決策樹

參考

1. 機器學習基礎之一文讀懂決策樹
   
2. 機器學習之-常見決策樹算法(ID3诬烹、C4.5砸烦、CART)
   
3. Python實現決策樹2(CART分類樹及CART回歸樹)