目錄

一、決策樹簡介

二、決策樹的基本流程

三. 劃分選擇，尋找最優(yōu)劃分屬性

(一)、信息增益

(二)、信息增益率

(三) 、基尼指數(shù)

四、剪枝處理

五、決策樹實現(xiàn)

（一）基于sklearn的代碼實現(xiàn)?

（二）基于Python實現(xiàn)?

實例：基于CART算法，實現(xiàn)預(yù)測貸款用戶是否具有償還貸款的能力

六、小結(jié)

一、決策樹簡介

決策樹（Decision Tree），它是一種以樹形數(shù)據(jù)結(jié)構(gòu)來展示決策規(guī)則和分類結(jié)果的模型，作為一種歸納學(xué)習(xí)算法，其重點是將看似無序、雜亂的已知數(shù)據(jù)，通過某種技術(shù)手段將它們轉(zhuǎn)化成可以預(yù)測未知數(shù)據(jù)的樹狀模型，每一條從根結(jié)點（對最終分類結(jié)果貢獻(xiàn)最大的屬性）到葉子結(jié)點（最終分類結(jié)果）的路徑都代表一條決策的規(guī)則。決策樹就是形如下圖的結(jié)構(gòu)（機(jī)器學(xué)習(xí)西瓜書的圖）：

? ? ? ? ? ? ? ? ?

二、決策樹的基本流程

決策樹是一個由根到葉的遞歸過程，在每一個中間結(jié)點尋找劃分屬性，遞歸重要的是設(shè)置停止條件：

• （1）當(dāng)前結(jié)點包含的樣本屬于同一類別，無需劃分；
• （2）當(dāng)前屬性集為空，或是所有樣本在所有屬性上取值相同無法劃分，簡單理解就是當(dāng)分到這一節(jié)點時，所有的屬性特征都用完了，沒有特征可用了，就根據(jù)label數(shù)量多的給這一節(jié)點打標(biāo)簽使其變成葉節(jié)點（其實是在用樣本出現(xiàn)的后驗概率做先驗概率）；
• （3）當(dāng)前結(jié)點包含的樣本集合為空，不能劃分。這種情況出現(xiàn)是因為該樣本數(shù)據(jù)缺少這個屬性取值，根據(jù)父結(jié)點的label情況為該結(jié)點打標(biāo)記（其實是在用父結(jié)點出現(xiàn)的后驗概率做該結(jié)點的先驗概率）。

? ? 決策樹算法的歷史

• 第一個決策算法（E.B.Hunt）：CLS
• 使決策樹受到關(guān)注，成為機(jī)器學(xué)習(xí)主流技術(shù)的算法（J.R.Quinlan）：ID3
• 最常用的決策樹算法（J.R.Quinlan）：C4.5
• 既可以分類可以用于回歸任務(wù)的決策樹算法：CART（Classfication and regression tree），從統(tǒng)計建模的角度出發(fā)考慮問題，前面都是用過信息論角度去考慮
• 基于決策樹的最強(qiáng)大算法之一：Random Forest

  ---

三. 劃分選擇，尋找最優(yōu)劃分屬性

(一)、信息增益

劃分?jǐn)?shù)據(jù)集的最大原則是：將無序的數(shù)據(jù)變得更加有序。在介紹信息增益之前，首先介紹一下信息的定義：如果待分類的事物可能劃分在多個分類中，則符號?的信息定義為：

,其中? 是選擇該分類的概率。

熵的定義如下：,這是計算所有類別所有可能值包含的信息期望，其含義是對信息的平均不確定性的度量，信息熵越大，集合D純度越低。

信息增益： ,信息熵減去條件熵，表示的含義是該屬性a能夠為分類系數(shù)帶來多少信息，信息愈多，該特征就越重要，所以當(dāng)信息增益越大時，則意味著使用屬性a來進(jìn)行劃分所獲得的純度越大。

決策樹學(xué)習(xí)中的信息增益等價于訓(xùn)練數(shù)據(jù)集中類與特征的互信息。

平均互信息：表示得知特征Y的信息從而使得對X的信息的不確定性減少程度。

(二)、信息增益率

信息增益率是為了抑制過細(xì)的屬性劃分，在西瓜書上當(dāng)我們考慮編號這一列（1-17）這17個數(shù)，顯然由此劃分信息增益最大，因為每個節(jié)點僅包含一個樣本，分支節(jié)點純度達(dá)到最大，但是這樣構(gòu)造的決策樹泛化性能太差，無法對新樣本進(jìn)行預(yù)測。所以信選擇最優(yōu)劃分屬性息增益會對某個屬性中類別數(shù)目多的屬性偏愛，但是會產(chǎn)生不利影響，為了減小這種誤差，可以使用信息增益率來。

信息增益率=Gain_ratio(D,a)?,其中：

相當(dāng)于是給定屬性a下的信息增益與特特征個數(shù)的信息熵之間的比值。

參數(shù)說明：V表示屬性a有V個可能取值 ,若使用a來對樣本集合D進(jìn)行劃分，則會產(chǎn)生V個分支結(jié)點，其中第v個分支結(jié)點包含了D中所有在樣本屬性a上取值為 的樣本，記為?

這個比僅僅是看信息增益率的大小來選擇最后劃分屬性，而是先通過信息增益從候選屬性中找出信息增益高于平均水平屬性，再從中選取增益率最高的屬性作為最優(yōu)屬性

(三) 、基尼指數(shù)

基尼值：表示從集合中隨機(jī)抽取兩個樣本，如果樣本集合越純，取到不同樣本的概率越小，這個概率就是基尼值。

首先整個數(shù)據(jù)集D的純度可用基尼值來度量:Gini(D)

其中|Y|表示標(biāo)簽類別總數(shù)。

屬性a給定情況下，屬性a的基尼指數(shù)為：Gini_inde(D,a)

其中V表示屬性a有V個可能取值 ,若使用a來對樣本集合D進(jìn)行劃分，則會產(chǎn)生V個分支結(jié)點，其中第v個分支結(jié)點包含了D中所有在樣本屬性a上取值為 a的值，記為? 。

選擇最優(yōu)劃分屬性，我們通過計算每個屬性所對應(yīng)的基尼指數(shù)然后選擇基尼指數(shù)最小的屬性為最優(yōu)屬性。

四、剪枝處理

剪枝是決策樹中的一種常用技術(shù)，用于減少過擬合并提高模型的泛化能力。剪枝分為預(yù)剪枝（Pre-pruning）和后剪枝（Post-pruning）兩種方法。

預(yù)剪枝：在決策樹構(gòu)建的過程中，通過提前停止劃分節(jié)點的方式來進(jìn)行剪枝。預(yù)剪枝方法通常根據(jù)一定的條件，在劃分節(jié)點時判斷是否停止劃分，并將該節(jié)點標(biāo)記為葉子節(jié)點。常見的預(yù)剪枝條件包括：

• 設(shè)置最大深度：限制決策樹的最大深度，避免樹過深而過擬合。
• 設(shè)置最小樣本數(shù)：當(dāng)節(jié)點的樣本數(shù)量小于某個閾值時，停止劃分。
• 設(shè)置最小信息增益或最大基尼指數(shù)：當(dāng)特征劃分后的信息增益或基尼指數(shù)低于某個閾值時，停止劃分。

后剪枝：在決策樹構(gòu)建完成后，通過自底向上的方式去除一些葉子節(jié)點，將其轉(zhuǎn)換為父節(jié)點。然后使用驗證集或交叉驗證來評估修剪前后的性能差異，如果修剪后的模型性能得到了提升，則保留修剪后的模型。常見的后剪枝方法有：?

• 單向錯誤率剪枝：計算修剪前后模型在驗證集上的錯誤率差異，如果修剪后的模型性能提升，則進(jìn)行剪枝。
• 悲觀剪枝：根據(jù)統(tǒng)計學(xué)原理計算置信區(qū)間，通過比較節(jié)點的置信區(qū)間來決定是否進(jìn)行剪枝。

預(yù)剪枝和后剪枝各有優(yōu)缺點，預(yù)剪枝速度快但可能導(dǎo)致欠擬合，后剪枝準(zhǔn)確但增加了計算復(fù)雜度。在實際應(yīng)用中，可以根據(jù)數(shù)據(jù)集的大小和特征屬性等情況選擇合適的剪枝方法以提高決策樹的泛化能力。?

五、決策樹實現(xiàn)

（一）基于sklearn的代碼實現(xiàn)?

?實例：項目采用用決策樹預(yù)測隱形眼鏡類型

# -*- coding: UTF-8 -*-
from sklearn.preprocessing import LabelEncoder, OneHotEncoder
from sklearn.externals.six import StringIO
from sklearn import tree
import pandas as pd
import numpy as np
import pydotplus
 
if __name__ == '__main__':
    with open('lenses.txt', 'r') as fr:                                        #加載文件
        lenses = [inst.strip().split('\t') for inst in fr.readlines()]        #處理文件
    lenses_target = []                                                        #提取每組數(shù)據(jù)的類別，保存在列表里
    for each in lenses:
        lenses_target.append(each[-1])
    print(lenses_target)
 
    lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']            #特征標(biāo)簽       
    lenses_list = []                                                        #保存lenses數(shù)據(jù)的臨時列表
    lenses_dict = {}                                                        #保存lenses數(shù)據(jù)的字典，用于生成pandas
    for each_label in lensesLabels:                                            #提取信息，生成字典
        for each in lenses:
            lenses_list.append(each[lensesLabels.index(each_label)])
        lenses_dict[each_label] = lenses_list
        lenses_list = []
    # print(lenses_dict)                                                        #打印字典信息
    lenses_pd = pd.DataFrame(lenses_dict)                                    #生成pandas.DataFrame
    # print(lenses_pd)                                                        #打印pandas.DataFrame
    le = LabelEncoder()                                                        #創(chuàng)建LabelEncoder()對象，用于序列化           
    for col in lenses_pd.columns:                                            #序列化
        lenses_pd[col] = le.fit_transform(lenses_pd[col])
    # print(lenses_pd)                                                        #打印編碼信息
 
    clf = tree.DecisionTreeClassifier(max_depth = 4)                        #創(chuàng)建DecisionTreeClassifier()類
    clf = clf.fit(lenses_pd.values.tolist(), lenses_target)                    #使用數(shù)據(jù)，構(gòu)建決策樹
    dot_data = StringIO()
    tree.export_graphviz(clf, out_file = dot_data,                            #繪制決策樹
                        feature_names = lenses_pd.keys(),
                        class_names = clf.classes_,
                        filled=True, rounded=True,
                        special_characters=True)
    graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
    graph.write_pdf("tree.pdf")                                                #保存繪制好的決策樹，以PDF的形式存儲。

（二）基于Python實現(xiàn)?

實例：基于CART算法，實現(xiàn)預(yù)測貸款用戶是否具有償還貸款的能力

import numpy as np
import math
from sklearn.model_selection import train_test_split
 
 
# 創(chuàng)建測試數(shù)據(jù)集
def createDataSet():
    dataSet = [[0, 0, 0, 0, 'no'],  # 數(shù)據(jù)集
               [0, 0, 0, 1, 'no'],
               [0, 1, 0, 1, 'yes'],
               [0, 1, 1, 0, 'yes'],
               [0, 0, 0, 0, 'no'],
               [1, 0, 0, 0, 'no'],
               [1, 0, 0, 1, 'no'],
               [1, 1, 1, 1, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [2, 0, 1, 2, 'yes'],
               [2, 0, 1, 1, 'yes'],
               [2, 1, 0, 1, 'yes'],
               [2, 1, 0, 2, 'yes'],
               [2, 0, 0, 0, 'no']]
    labels = ['年齡', '有工作', '有自己的房子', '信貸情況']  # 分類屬性
    return dataSet, labels  # 返回數(shù)據(jù)集和分類屬性
 
 
 
# 計算基尼指數(shù)
def cal_gini(data_vector):
    nums_data = len(data_vector)  # 數(shù)據(jù)集樣本數(shù)
    counts_by_labels = {}  # 用來保存每個label下的樣本數(shù)
    gini = 0      #基尼指數(shù)
    p_sum=0       #每個類別的樣本數(shù)
 
    for vector in data_vector:
        if vector[-1] not in counts_by_labels:  # vector[-1]為label值
            counts_by_labels[vector[-1]] = 0
        counts_by_labels[vector[-1]] += 1  # 統(tǒng)計label出現(xiàn)的次數(shù)
    for key in counts_by_labels:
        p = float(counts_by_labels[key] / nums_data)  # 計算每個標(biāo)簽出現(xiàn)的概率
        p_sum+= p**2
    gini=1-p_sum               # 公式5.24
    return gini
 
# 返回類列表中出現(xiàn)次數(shù)最多的類標(biāo)簽
def max_class(label_list):
    count_label = {}
    for label in label_list:
        if label not in count_label:
            count_label[label] = 0
        count_label[label] += 1
    #     選擇字典value最大的所對應(yīng)的key值
    return max(count_label, key=count_label.get)
 
 
"""
根據(jù)每個特征劃分?jǐn)?shù)據(jù)集
data_vector
index_feature：特征的索引位置i
value：用來劃分的特征取值
返回劃分后的子數(shù)據(jù)及樣本數(shù)，和子數(shù)據(jù)集（子數(shù)據(jù)集剔除了第i列特征）
"""
# 根據(jù)cart算法劃分?jǐn)?shù)據(jù)集，cart算法生成的是二叉數(shù)，因此分割之后也就只有兩個子數(shù)據(jù)集。返回分割后的D1和D2數(shù)據(jù)集
def split_datatset_cart(data_vector, index_feature, value):
    split_set_yes = []   #判別為“是”的子數(shù)據(jù)集
    split_set_no=[]       #判別為“否”的子數(shù)據(jù)集
    for vector in data_vector:
        if vector[index_feature] == value:
            # 去掉第i列特征
            split_1 = vector[:index_feature]
            split_1.extend(vector[index_feature + 1:])
            split_set_yes.append(split_1)
        else:
            split_2 = vector[:index_feature]
            split_2.extend(vector[index_feature + 1:])
            split_set_no.append(split_2)
    #         分別輸出D1和D2數(shù)據(jù)集以及對應(yīng)的數(shù)據(jù)集樣本數(shù)
    return len(split_set_yes),split_set_yes,len(split_set_no),split_set_no
 
 
# 選擇最優(yōu)分類特征
# 生成決策樹的方法：cart算法
def choose_bestfeture_cart(data_vector):
    nums_data = len(data_vector)
    nums_feature = len(data_vector[0]) - 1  # 每個樣本所包含的特征個數(shù)
    min_gini = float('inf')  # 表示最小的基尼指數(shù)
    best_index_feature = 0  # 表示最優(yōu)特征的索引位置index
    best_split_point=None  #表示最優(yōu)的切分點
    for i in range(nums_feature):  # 遍歷所有的特征
        features_i_set = [vector[i] for vector in data_vector]  # 提取第i個特征中所包含的可能取值
        features_i_set = list(set(features_i_set))  # 對特征值去重
        feature_gini = 0  #每個特征中每個特征值所對應(yīng)的基尼指數(shù)
        # 如果第i個特征向量包含的特征取值個數(shù)小于2，則只有一個切分點。參考P71例5.4
        if len(features_i_set)<=2:
            # 同時選取features_i_set中數(shù)值最大特征取值為切分點。當(dāng)然選取最小取值也有一樣的結(jié)果，這只是設(shè)定的一個規(guī)矩。
            # fea為切分點
            fea=max(features_i_set)
            # 根據(jù)切分點進(jìn)行劃分子數(shù)據(jù)集
            nums_di_yes, di_set_yes, nums_di_no, di_set_no = split_datatset_cart(data_vector, i, fea)  #
            p_di_yes = nums_di_yes / nums_data  # 計算|Di|/|D|
            gini_yes_di = cal_gini(di_set_yes)  # 計算yes子類的gini指數(shù)
            feature_gini += p_di_yes * gini_yes_di
            p_di_no = nums_di_no / nums_data
            gini_yes_no = cal_gini(di_set_no)     # 計算no子類的gini指數(shù)
            feature_gini += p_di_no * gini_yes_no
 
            # 選取最優(yōu)的分類特征和最優(yōu)切分點
            if feature_gini < min_gini:
                min_gini = feature_gini
                best_index_feature = i
                best_split_point = fea
        # 如果第i個特征向量包含的特征取值個數(shù)小于2，則有多個切分點
        else:
            for fea in features_i_set:  # 遍歷第i個特征的所有vlaue
                nums_di_yes, di_set_yes,nums_di_no, di_set_no = split_datatset_cart(data_vector, i, fea)  #
                p_di_yes = nums_di_yes / nums_data  # 計算|Di|/|D|
                gini_yes_di = cal_gini(di_set_yes)  # 計算yes子類的gini指數(shù)
                feature_gini += p_di_yes * gini_yes_di
                p_di_no=nums_di_no/nums_data
                gini_yes_no=cal_gini(di_set_no)
                feature_gini += p_di_no*gini_yes_no
 
                # 選取最優(yōu)的分類特征和最優(yōu)切分點
                if feature_gini<min_gini:
                    min_gini=feature_gini
                    best_index_feature=i
                    best_split_point=fea
    # print(best_index_feature,best_split_point)
    return best_index_feature,best_split_point  # 返回最優(yōu)分類特征的索引位置和最優(yōu)切分點
 
 
# 決策樹的生成
class Decision_tree(object):
    def __init__(self, data_vector, labels):
        # 數(shù)據(jù)集
        self.data_vector = data_vector
        # 特征標(biāo)簽
        self.labels = labels
        # 用于保存最優(yōu)特征的索引信息，列表形式輸出
        self.best_feature_index_list=[]
 
    # 生成決策樹，返回決策樹tree，字典形式
    def tree_main(self):
        tree = self.create_decision_tree(self.data_vector, self.labels)
        return tree
 
    """
    遞歸函數(shù)，用于生成每一個子樹,并返回。
    《統(tǒng)計學(xué)習(xí)方法》CART算法
    data_vector：每一個待分類數(shù)據(jù)集
    labels：待分類特征標(biāo)簽 
    """
 
    def create_decision_tree(self,data_vector, labels):
        nums_label = [vector[-1] for vector in data_vector]
        # 如果數(shù)據(jù)集中所有實例屬于同一個類，則停止劃分。返回該類 標(biāo)簽。
        if len(set(nums_label)) == 1:
            return nums_label[0]
        # 如果特征集只有一類時，即已經(jīng)遍歷完了所有特征，則停止劃分。返回出現(xiàn)次數(shù)最多的類標(biāo)簽
        if len(data_vector[0]) == 1:
            return max_class(nums_label)
        best_index_feature,best_split_point = choose_bestfeture_cart(data_vector)  # 選擇最優(yōu)特征
        # best_feature_index_list存放每一個最優(yōu)分類特征的索引值和對應(yīng)的切分點，以兩者的元組形式存放。
        self.best_feature_index_list.append((best_index_feature,best_split_point))
        best_feature_label = labels[best_index_feature]  # 最優(yōu)特征的標(biāo)簽
        myTree = {best_feature_label: {}}  # 子決策樹，key為最優(yōu)特征的標(biāo)簽，value為子決策樹
        del (labels[best_index_feature])  # 刪除已經(jīng)使用過的最優(yōu)特征標(biāo)簽
 
        # 規(guī)定左子樹為A=a的樣本，右子樹為A！=a的樣本，并規(guī)定右子樹的標(biāo)簽為“-best_split_point”?。。∵@樣可以便于在進(jìn)行predict時方便分類。
        nums_di_yes, di_set_yes, nums_di_no, di_set_no = split_datatset_cart(data_vector,best_index_feature,best_split_point)
        # 左子樹
        myTree[best_feature_label][best_split_point] = self.create_decision_tree(di_set_yes, labels)
        # 右子樹
        myTree[best_feature_label][-best_split_point] = self.create_decision_tree(di_set_no, labels)
 
        return myTree
 
 
 
if __name__ == '__main__':
    dataSet, labels = createDataSet()
    # best_index,point_split=choose_bestfeture_cart(dataSet)
    # print(labels[best_index],point_split)
 
    # 劃分訓(xùn)練集和測試集
    x_train, x_test = train_test_split(dataSet, test_size=0.3, random_state=0)
 
    #
    tree= Decision_tree(dataSet, labels)
    decision_tree=tree.tree_main()
    print(decision_tree)
    print(tree.best_feature_index_list)
    # test_vector=[2, 1, 0, 0]
 
    # 由于數(shù)據(jù)集
    # score=0
    # for test_vector in x_test:
    #     predict_result=tree.predict(decision_tree,test_vector)
    #     print(test_vector,predict_result)
    #     if predict_result == test_vector[-1]:
    #         score+=1
    # print("測試準(zhǔn)確率：%f%%"%(score/len(x_test)*100))
 

六、小結(jié)

決策樹是一種基礎(chǔ)的機(jī)器學(xué)習(xí)算法，能夠用于分類和回歸等問題。決策樹模型的核心思想是通過劃分訓(xùn)練數(shù)據(jù)，構(gòu)建一個基于特征屬性的樹形結(jié)構(gòu)，使得每個葉子節(jié)點對應(yīng)于一個類別或數(shù)值輸出。在預(yù)測時，將新樣本從根節(jié)點開始依據(jù)屬性進(jìn)行判斷，直到達(dá)到葉子節(jié)點并返回該節(jié)點的類別或數(shù)值。

決策樹的實現(xiàn)可以使用多種方法，例如使用Python中的scikit-learn庫，Java中的Weka庫或R語言中的rpart包等。在實驗中需要選擇合適的數(shù)據(jù)集和特征屬性，并進(jìn)行訓(xùn)練、評估和可視化等操作。下面是一份決策樹實現(xiàn)實驗報告小結(jié)的示例：

實驗?zāi)康?/strong>：了解決策樹算法的原理，學(xué)習(xí)使用決策樹算法來解決分類或回歸問題。