决策树

英文名字：Descision Tree

什么是决策树

举个校园相亲的例子，今天校园的小猫(女)和小狗(男)准备配对，小猫如何才能在众多的优质🐶的心仪的狗呢？于是呢？有一只特乖巧的小猫找到了你，你正在学习机器学习，刚好学习了决策树，准备给这只猫猫挑选优质狗，当然，你不仅仅是直接告诉猫哪些狗是合适你的？你更应该详细的给猫讲解决策树是如何根据它提出的标准选出的符合要求的狗呢？
猫给出如下信息：
年龄<0.5 不心仪；年龄大于>=0.5 6.5<=体重<=8.5;心仪; 年龄>=0.5 体重>8.5 长相好心仪;其余情况不心仪; 根据上述条件可以构造一颗树：
决策树的基本概念-LMLPHP
上面的图就是决策树，最终的结果是心仪或者不心仪。决策树算法以树形结构表示数据分类的结果

基本概念

决策树属于也只能非参数学习算法、可以用于解决(多)分类问题，回归问题。回归问题的结果，叶子结点的平均值是回归问题的解。
根节点：决策树具有数据结构里面的二叉树、树的全部属性
非叶子节点：（决策点）代表测试的条件，数据的属性的测试
叶子节点：分类后获得分类标记
分支：测试的结果

数学问题-熵-Gini系数

什么是熵：熵的概念源于物理学，用于度量一个热力学系统的无序程度。
信息熵：不得不提香农这个大写的人啦！信息论里面的知识。在信息论里面，信息熵衡量信息量的大小，也就是对随机变量不确定度的一个衡量。熵越大，不确定性越大；
对于某个单符号无记忆信源，发出符号($x_i$)的概率是$p_i$,概率越大，符号的信息量就越小，香农公式 $I(x_i)=-log_{p_i}$。信源所含的信息熵就是信息量的期望]
$H(x)=-\sum p_i*log_{p_i}$
Gini系数： $Gimi(p) = 1-\sum_{k=1}^{K}p_k^2$

决策树如何构建的问题

自我提问阶段：
自我提问阶段：
每个节点的位置如何确定？
特征的选择：每次选入的特征作为分裂的标准，都是使得决策树在这个节点的根据你自己选择的标准（信息熵最小、信息增益最大、gini系数最小）.
每个节点在哪个值上做划分，确定分支结构呢？
遍历划分的节点的分界值操作来解决这个问题
可以想象，我们构造的决策树足够庞大，决策树可以把每一个样本都分对，那么决策树的泛化能力就可以很差了
为了解决这个问题，就需要剪枝操作了

训练算法

基于信息熵的构造

当选择某个特征作为节点时，我们就希望这个特征的信息熵越小越好，那么不确定性越小
\[ H(x) = -p_i(x)log^{p_i(x)}= -\frac{n_j}{S}log^{\frac{n_j}{S}}\]
$n_j$: 第j个类别，在样本中出现的频数
$S$: 样本个数
对于离散属性，直接计算信息熵，连续属性，就需要划分区间，按区间计算信息熵。

基于某一层的数据集a. 遍历计算所有属性，遍历相应属性以不同值为分截点的信息熵b. 选择信息熵最小的作为节点
如果到达终止条件，返回相应信息，否则，按照分支重复步骤1
ID3算法：信息增益最大化
C:类别
\[H(C)=-\sum_{i=1}^{m}p_i log _2^{p_i}\]
按照D组划分C
\[H(C/D)=\sum_{i=1}^{v}\frac{|C_i|}{|C|}H(C_i)\]
信息增益
\[ gain(D) = gain(C)-H(C/D)\]
这里我就以网上给出的数据为例，给出根据信息熵构成决策树的计算过程。
确定特征，统计属性值和分解结果，总共四个特征，四种特征的统计结果如下图：
根据历史数据，在不知到任何情况下，计算数据本身的熵为
\[ - \frac{9}{14}log_2 \frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.940\]
计算每个特征做为节点的信息熵

以天气为例，天气三种属性，当Outlook = sunny时，H(x) = $-\frac{2}{5}log_2\frac{2}{5}-\frac{3}{5}log_2\frac{3}{5}$; 当Outlook= overcast,$H(x)=0$,当Outlook = rainy ,$H(x) = 0.971$
所以，当选天气作为节点时，此时$H(x)=\frac{5}{14}*0.971+\frac{4}{14}*0+\frac{5}{14}*0.971 = 0.693$,gain(天气) = 0.247
同理，
gain(温度) =0.029 gain(湿度)=0.152 gain(风)=0.048
因此选择天气节点，在递归实现其他节点的选择。
C4.5: 信息增益率
如果这里考虑了一列ID,每个ID出现一次，所以算出的信息增益大。
$ H(x) = 0$,信息增益最大化了，可以引入信息增益率
\[C(T) = \frac{信息增益}{H(T)}=\frac{H(C)-H(C/T)}{H(T)}\]
CART:基尼(Gini)系数
\[G = 1-\sum_{i=l_k}^{k}p_i^2\],也是对随机变量不确定性的一个衡量，gini越大，不确定性越大
连续属性的处理方法
选取分解点的问题：分成不同的区间（二分、三分....)，分别计算增益值，然后比较选择。
评价
评价函数：
\[C(T) = \sum_{releaf} N_t*H(T)\]
$ N_t$：每个叶子节点里面含有的样本个数
$H(T)$:叶子节点含有的信息熵

过拟合

如果决策树过于庞大，分支太多，可能造成过拟合。对应训练样本都尽可能的分对，也许样本本身就存在异常点呢？

指定深度d
节点的min_sample
节点熵值或者gini值小于阙值
熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度数，节点停止分裂。
当所以特征都用完了
指定节点个数
当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。

II. 后剪枝：构建好后，然后才开始裁剪
\[ C_\alpha(T) = C(T)+\alpha|T_{leaf}|\]
在构造含一棵树后，选一些节点做计算，看是否需要剪枝

随机森林

Bootstraping: 有放回采样
Bagging:有放回采样n个样本，建立分类器
一次采样一颗树，多次采样多棵树，构成一片森林，多个分类器共同决定。当有一个test时，代入所以的决策树，共同决策。
随机性的解释：
1. 数据的随机性
为每个树选取训练数据，随机按照比列有放回选择数据集
2. 特征的随机性
按照比列选取特征的个数

决策树单个节点选择的代码实现

简单实现了单个节点决策构造过程

def split(X,y,d,value):
'''
在d纬度上，按照value进行划分
'''
    index_a =(X[:,d]<=value)
    index_b =(X[:,d]>value)
    return X[index_a],X[index_b],y[index_a],y[index_b]
from collections import Counter
from math import log
from numpy as np
def entropy(y):
    counter = Counter(y) # 字典
    res = 0.0
    for num in counter.values():
        p = num/len(y)
        res+=-p*log(p)
    return res
def gain(X,y,d,v):
    X_l,X_r,y_l,y_r = split(X,y,d,v)
    e = len(y_l)/len(y)*entropy(y_l)+len(y_r)/len(y)*entropy(y_r)
    return (entropy(y)-e)
def gainratio(X,y,d,v):
    X_l,X_r,y_l,y_r = split(X,y,d,v)
    gain =entropy(y) - len(y_l)/len(y)*entropy(y_l)+len(y_r)/len(y)*entropy(y_r)
    return gain/(entropy(y_l)+entropy(y_r))
def gini(y):
    counter = Counter(y)
    res = 1.0
    for num in counter.values():
        p = num / len(y)
        res += -p**2
    return res
    #X_l,X_r,y_l,y_r = split(X,y,d,v)
    #return 1-(len(y_l)/len(y))**2-(len(y_r)/len(y))**2
def try_split(X,y):
    best_entropy = float('inf')
    best_d,best_v=-1,-1
    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]):
                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)
                #gini
                e = gini(y_l) + gini(y_r)
                # 信息增益
                e = -gain(X,y,d,v)

                if e < best_entropy:
                    best_entropy, best_d,best_v = e,d,v
    return best_entropy, best_d, best_v

# 手动来划分

data =np.array([[   0.3 ,   5   ,   2   ,   0   ],
[   0.4 ,   6   ,   0   ,   0   ],
[   0.5 ,   6.5 ,   1   ,   1   ],
[   0.6 ,   6   ,   0   ,   0   ],
[   0.7 ,   9   ,   2   ,   1   ],
[   0.5 ,   7   ,   1   ,   0   ],
[   0.4 ,   6   ,   0   ,   0   ],
[   0.6 ,   8.5 ,   0   ,   1   ],
[   0.3 ,   5.5 ,   2   ,   0   ],
[   0.9 ,   10  ,   0   ,   1   ],
[   1   ,   12  ,   1   ,   0   ],
[   0.6 ,   9   ,   1   ,   0   ],
])
X =data[:,0:3]
y = data[:,-1]
# 手动来划分
best_entropy, best_d, best_v = try_split(X, y)
print(best_entropy, best_d, best_v)
X1_l, X1_r, y1_l, y1_r = split(X,y,best_d,best_v)
print(X1_l, X1_r, y1_l, y1_r)


best_entropy2, best_d2, best_v2 = try_split(X1_r, y1_r)
X2_l, X2_r, y2_l, y2_r = split(X1_r,y1_r,best_d2,best_v2)
entropy(y2_l)

Python sklean里面tree模块里面的DecisionTreeClassifier

from sklearn import tree
clf =tree.DecisionTreeClassifier(max_depth=1,criterion ='gini') # criterion='entropy|gini'

clf = clf.fit(X,y)

训练好一颗决策树之后，我们可以使用export_graphviz导出器以Graphviz格式导出树。

import graphviz
dot_data = tree.export_graphviz(clf, out_file=None,)
graph = graphviz.Source(dot_data)
graph.render("data")

在运行时可以出错：
ExecutableNotFound: failed to execute ['dot', '-Tpdf', '-O', 'data'], make sure the Graphviz executables are on your systems' PATH
原因：graphviz本身是一个软件，需要额外下载，并将其bin加入环境变量之中。下载

cherryxiemay

决策树的基本概念

决策树

什么是决策树

基本概念

数学问题-熵-Gini系数

决策树如何构建的问题

训练算法

基于信息熵的构造

ID3算法： 信息增益最大化

C4.5: 信息增益率

CART:基尼(Gini)系数

连续属性的处理方法

评价

过拟合

随机森林

决策树单个节点选择的代码实现

简单实现了单个节点决策构造过程

Python sklean里面tree模块里面的DecisionTreeClassifier

ID3算法：信息增益最大化