理論

什么是決策樹写隶？

決策樹內(nèi)部節(jié)點表示一個特征或?qū)傩裕~節(jié)點表示一個類讲仰，進行分類時慕趴，從根節(jié)點開始，對實例的某一特征進行測試鄙陡，根據(jù)測試結(jié)果冕房，將實例分配到其子節(jié)點，這時每一個子節(jié)點對應(yīng)著該特征的一個取值趁矾，如此遞歸地對實例進行測試并分配耙册，直至到達葉節(jié)點，最后將實例分到葉節(jié)點地類中毫捣。
可以將決策樹看成一個if-then規(guī)則的集合详拙，每一個實例都被一條路徑或一條規(guī)則所覆蓋，而且只被一條路徑或一條規(guī)則所覆蓋蔓同，互斥并且完備溪厘。同時，決策樹還表示給定特征條件下類的條件概率分布牌柄，定義了特征空間的一個劃分，分為互不相交的幾個單元侧甫，決策樹的一條路徑就對應(yīng)劃分中的一個單元珊佣，決策樹分類時將實例分到條件概率大的一類去。

決策樹學(xué)習(xí)

決策樹學(xué)習(xí)通常包括3個步驟：特征選擇披粟、決策樹的生成和決策樹的剪枝咒锻。決策樹學(xué)習(xí)的算法通常是一個遞歸地選擇最優(yōu)特征，并根據(jù)該特征對訓(xùn)練數(shù)據(jù)進行分割守屉，使得對各個子數(shù)據(jù)集有一個最好的分類的過程惑艇，這一過程對應(yīng)著特征空間的劃分，也對應(yīng)著決策樹的構(gòu)建拇泛。為了防止過擬合滨巴，我們需要對生成的決策樹自下而上進行剪枝，去掉過于細分的葉節(jié)點俺叭，使其回退到父節(jié)點恭取，甚至更高的節(jié)點，然后將父節(jié)點或更高的節(jié)點改為新的葉節(jié)點熄守。

前提知識

設(shè) 是一個取有限值的離散隨機變量蜈垮，其概率分布為

隨機變量耗跛，其聯(lián)合概率分布為

我們使用熵來衡量事件所包含的信息量，事件發(fā)生的不確定性越大攒发，包含的信息量就越多调塌，因此熵是事件發(fā)生概率的函數(shù)。對于兩個獨立（不相關(guān)）事件 x 和 y惠猿，有羔砾，同時有 ，這也符合對數(shù)函數(shù)的性質(zhì)紊扬。
隨機變量 的熵是隨機變量 中包含的平均信息量蜒茄，因此隨機變量的熵定義為

條件熵表示在已知的條件下隨機變量的不確定性，定義為在給定的條件下餐屎，的條件概率分布的熵對的數(shù)學(xué)期望

這里檀葛，
當熵和條件熵的概率由數(shù)據(jù)估計得到時，稱為經(jīng)驗熵和經(jīng)驗條件熵腹缩，如果有概率屿聋，則令

特征選擇

特征選擇在于選取對訓(xùn)練數(shù)據(jù)具有分類能力的特征，準則是信息增益或信息增益比藏鹊。

信息增益表示得知特征的信息而使得類的信息的不確定性減少的程度润讥，將熵與條件熵之差稱為互信息，決策樹學(xué)習(xí)中的信息增益等價于訓(xùn)練數(shù)據(jù)集中類與特征的互信息盘寡。

給定訓(xùn)練數(shù)據(jù)集和特征楚殿，經(jīng)驗熵表示對數(shù)據(jù)集進行分類的不確定性，經(jīng)驗條件熵表示在特征給定的條件下對數(shù)據(jù)集進行分類的不確定性竿痰，它們的差脆粥，即信息增益，表示由于特征而使得對數(shù)據(jù)集的分類的不確定性減少的程度影涉。在進行特征選擇的時候变隔。我們選擇信息增益最大的特征，因為信息增益大的特征具有更強的分類能力蟹倾。
信息增益定義為

設(shè)訓(xùn)練數(shù)據(jù)集為匣缘，表示其樣本容量。設(shè)有個類鲜棠，, 為屬于類的樣本個數(shù)肌厨，。設(shè)特征有個不同的取值豁陆，根據(jù)特征的取值將劃分為個子集夏哭，為的樣本個數(shù)，献联。記子集中屬于類的樣本的集合為竖配，即何址，為的樣本個數(shù)。
計算信息增益的算法如下：

輸入：訓(xùn)練數(shù)據(jù)和特征进胯；
輸出：特征對訓(xùn)練數(shù)據(jù)集的信息增益用爪。

1. 計算數(shù)據(jù)集的經(jīng)驗熵
   
2. 計算特征對數(shù)據(jù)集的經(jīng)驗條件熵
   
3. 計算信息增益
   

使用信息增益作為劃分訓(xùn)練數(shù)據(jù)集的特征，存在偏向于選擇取值較多的特征的問題胁镐，使用信息增益比可以進行校正偎血。
信息增益比定義為其信息增益與訓(xùn)練數(shù)據(jù)集關(guān)于特征的值的熵之比，即

其中盯漂， 颇玷。

決策樹生成

ID3算法

應(yīng)用信息增益準則選擇特征，遞歸地構(gòu)建決策樹就缆。從根節(jié)點開始帖渠，對結(jié)點計算所有可能的特征的信息增益，選擇信息增益最大的特征作為結(jié)點的特征竭宰，由該特征的不同取值建立子結(jié)點空郊；再對子結(jié)點遞歸地調(diào)用以上方法，構(gòu)建決策樹切揭；直到所有特征的信息增益均很小或沒有特征可以選擇為止狞甚。

輸入：訓(xùn)練數(shù)據(jù)集，特征集廓旬，閾值哼审；
輸出：決策樹。

1. 若中所有實例屬于同一類孕豹，則為單結(jié)點樹棺蛛，并將類作為該結(jié)點的類標記，返回巩步；
2. 若 ，則為單結(jié)點樹桦踊，并將中實例數(shù)最大的類作為該結(jié)點的類標記椅野，返回；
3. 否則籍胯，計算中各特征對的信息增益竟闪，選擇信息增益最大的特征；
4. 如果的信息增益小于閾值杖狼，則置為單結(jié)點樹炼蛤，并將中實例數(shù)最大的類作為該結(jié)點的類標記，返回蝶涩；
5. 否則理朋，對的每一可能值絮识，依將分割為若干非空子集，將中實例數(shù)最大的類作為標記嗽上，構(gòu)建子結(jié)點次舌，由結(jié)點及其子結(jié)點構(gòu)成樹，返回;
6. 對第個子結(jié)點兽愤，以為訓(xùn)練集彼念，以為特征集，遞歸地調(diào)用1-5步浅萧，得到子樹逐沙，返回。

C4.5算法

使用信息增益比來選擇特征洼畅，其他與ID3類似吩案。

實現(xiàn)

例：有一個由15個樣本組成的貸款申請訓(xùn)練數(shù)據(jù)，數(shù)據(jù)包括4個特征：年齡土思，是否有工作务热，是否有房子，信貸情況己儒，最后一列是類別崎岂，是否同意貸款。
數(shù)據(jù)train_data.csv如下：

ID,age,hasWork,hasOwnHouse,credit,clazz
1,青年,否,否,一般,否
2,青年,否,否,好,否
3,青年,是,否,好,是
4,青年,是,是,一般,是
5,青年,否,否,一般,否
6,中年,否,否,一般,否
7,中年,否,否,好,否
8,中年,是,是,好,是
9,中年,否,是,非常好,是
10,中年,否,是,非常好,是
11,老年,否,是,非常好,是
12,老年,否,是,好,是
13,老年,是,否,好,是
14,老年,是,否,非常好,是
15,老年,否,否,一般,否

決策樹實現(xiàn)代碼decisionTree.py如下：

# -*- coding: utf-8 -*-
import pandas as pd
import numpy as np
import queue

class Node:
    def __init__(self, label):
        self.label = label
        self.attribute = None
        self.children = None
        self.x = None
        self.y = None

    def setAttribute(self, attribute):
        self.attribute = attribute

    def setChildren(self, children):
        self.children = children

def entropy(datas, clazz):
    C = datas[clazz].value_counts().values
    D = float(datas.index.size)
    H = -np.sum(C/D * np.log2(C/D))
    return H

def conditional_entropy(datas, clazz, attr):
    sub_d = datas[attr].value_counts()
    label = sub_d.index
    Di = sub_d.values
    D = float(datas.index.size)
    H = []
    for i in range(label.size):
        H.append(entropy(datas[datas[attr]==label[i]], clazz))
    CH = np.sum(Di * H / D)
    return CH

def info_gain(datas, clazz, attr):
    H = entropy(datas, clazz)
    CH = conditional_entropy(datas, clazz, attr)
    G = H - CH
    return G

def info_gain_ratio(datas, clazz, attr):
    G = info_gain(datas, clazz, attr)
    Di = datas[attr].value_counts().values
    D = float(datas.index.size)
    HA = -np.sum(Di / D * np.log2(Di / D))
    GR = G / HA
    return GR


def decisionTree(datas, attrs, clazz, threshold, method = 'ID3'):
    clazz_value_cnts = datas[clazz].value_counts()
    label = clazz_value_cnts.index[0]
    node = Node(label)
    if clazz_value_cnts.size == 1 or attrs.size == 0:
        return node

    IG = np.zeros(attrs.size)
    for i in range(attrs.size):
        if method == 'ID3':
            IG[i] = info_gain(datas, clazz, attrs[i])
        if method == 'C4.5':
            IG[i] = info_gain_ratio(datas, clazz, attrs[i])
    index = IG.argmax()
    attr = attrs[index]
    node.setAttribute(attr)

    if IG.max() < threshold:
        return node

    attrs_value_cnts = datas[attr].value_counts()
    attrs = attrs.drop(attr)
    children = dict()

    for i in range(attrs_value_cnts.size):
        children[attrs_value_cnts.index[i]] = decisionTree(datas[datas[attr]==attrs_value_cnts.index[i]], attrs, clazz, threshold, method)

    node.setChildren(children)
    return node

"""
return tree depth
"""
def getTreeDepth(tree):
    if tree.children == None:
        return 1

    ds = [None] * len(tree.children)
    i = 0
    for node in tree.children.values():
        ds[i] = getTreeDepth(node)
        i = i + 1

    return max(ds) + 1


"""
return the tree's leaves's number
"""

def getLeavesNum(tree):
    if tree.children == None:
        return 1

    num = 0
    for node in tree.children.values():
        num += getLeavesNum(node)

    return num

df = pd.read_csv('train_data.csv', encoding='utf-8')
tree = decisionTree(df, df.columns.drop('clazz').drop('ID'), 'clazz', 0, 'ID3')
printTree(tree)

進行可視化代碼plotTree.py如下：

import matplotlib.pyplot as plt
import pandas as pd
import decisionTree as dt


def xy(tree, y):
    global n
    tree.y = y

    if tree.x != None:
        return tree.x

    if tree.children == None:
        x = n * x0
        n += 1
    else:
        xSum = 0
        k = len(tree.children)
        for node in tree.children.values():
            xSum += xy(node, y - y0)
        x = float(xSum) / k

    tree.x = x
    return x


xx = 0.05
yy = 0.08


def pp(tree, ax):
    if tree == None:
        return

    if tree.children != None:
        for key in tree.children.keys():
            ax.annotate(tree.attribute,
                        xy=(tree.children[key].x + xx, tree.children[key].y + yy),
                        xytext=(tree.x, tree.y),
                        xycoords='figure fraction',
                        textcoords='figure fraction',
                        arrowprops=dict(arrowstyle='->')
                        )
            ax.text((tree.children[key].x + tree.x) / 2, (tree.children[key].y + tree.y) / 2, key,
                    transform=ax.transAxes)
            pp(tree.children[key], ax)
    else:
        ax.text(tree.x, tree.y, tree.label, transform=ax.transAxes)


df = pd.read_csv('train_data.csv', encoding='utf-8')
tree = dt.decisionTree(df, df.columns.drop('clazz').drop('ID'), 'clazz', 0, 'ID3')

fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)

h = dt.getTreeDepth(tree)
w = dt.getLeavesNum(tree)

y0 = float(1) / (h + 1)
x0 = float(1) / (w + 1)

n = 1

xy(tree, 1 - y0)
pp(tree, ax)

plt.show()

結(jié)果展示如下：

plotTree.png