决策树+编程实现

什么是决策树

构建决策树的关键问题是：

• 每个节点在哪个维度上做划分
• 某个维度在哪个值上做划分

信息熵

信息熵在信息论中代表随机变量不确定的度量。

熵越大，数据的不确定性就越高。

熵越小，数据的不确定性越低。

上图中可以看出，右边的数据比左边的数据熵小，右边数据更确定。

以二分类问题，编程实现信息熵，观察信息熵的函数曲线

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,1,200)
plt.plot(x,entropy(x))
plt.title('entropy')
plt.show()

决策树

        通过信息熵可以看到当前数据的不确定度是怎样，对于决策树来说，根节点时是拥有全部的数据。在根节点的基础上，我们要找到一个维度阈值，对根节点进行划分，划分后我们数据整体信息熵是减小的，划分出的两个节点，可以继续用这种方法划分使得整体信息熵继续变小，这样的过程递归下去，就形成了决策树。下面将用程序模拟下这种划分形式。

SKlearn:

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
#采用鸢尾花数据集
iris=datasets.load_iris()
#为了可视化方便，只采用后两个维度数据
x=iris.data[:,-2:]
y=iris.target
#导入决策树的库
from sklearn.tree import DecisionTreeClassifier
#决策树最大深度为2，用信息熵的方式进行划分
dt_clf=DecisionTreeClassifier(max_depth=2,criterion='entropy')
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)),
        np.linspace(axis[2], axis[3], int((axis[3]-axis[2])*100))
    )
    x_new=np.c_[x0.ravel(),x1.ravel()]
    #对横坐标axis[2]到axis[3]x0，纵坐标axis[0]到axis[1]x1进行组合，组合成n行两列的数据点，对这些数据点进行预测
    y_predict=model.predict(x_new).reshape(x0.shape)

    #引入ListedColormap用于生成非渐变的颜色映射
    from matplotlib.colors import ListedColormap
    # 自定义colormap
    custom_cmap=ListedColormap(['#EF9A9A','#FFF59D','#90CAF9'])
    #contourf(x, y, z)对等高线间的填充区域进行填充（使用不同的颜色）x和y为两个等长一维数组，第三个参数z为二维数组（表示平面点xi,yi映射的函数值）。
    plt.contourf(x0,x1,y_predict,linewidth=5,cmap=custom_cmap)

plot_decision_boundary(dt_clf,axis=[0.5,7.5,0,3])
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.title('DecisionTreeClassifier')
plt.show()

模拟决策树划分过程

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
#采用鸢尾花数据集
iris=datasets.load_iris()
#为了可视化方便，只采用后两个维度数据
x=iris.data[:,-2:]
y=iris.target
def split(x,y,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
def entropy(y):
    counter=Counter(y)
    res=0.0
    for num in counter.values():
        p=num/len(y)
        res+=-p*np.log(p)
    return res

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-1],d]!=x[sorted_index[i],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)
                if e<best_entropy:
                    best_entropy,best_d,best_v=e,d,v
    return best_entropy,best_d,best_v

print(try_split(x,y))
(0.69314718055994529, 0, 2.4500000000000002)

除了交叉熵，还能用基尼系数来对决策树中的每一个节点来划分，基尼系数比交叉熵的计算方式要简单很多。

当基尼系数取0时，表示100%确定，二分类情况下，基尼系数可表示为：

import  numpy as np
import matplotlib.pyplot as plt
#二分类基尼系数
def g(x):
    return -2*x*x+2*x

x=np.linspace(0.01,1,200)
plt.plot(x,g(x))
plt.title('gini')
plt.show()

SKlearn

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
#采用鸢尾花数据集
iris=datasets.load_iris()
#为了可视化方便，只采用后两个维度数据
x=iris.data[:,-2:]
y=iris.target
#导入决策树的库
from sklearn.tree import DecisionTreeClassifier
#决策树最大深度为2，用基尼系数的方式进行划分
dt_clf=DecisionTreeClassifier(max_depth=2,criterion='gini')
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)),
        np.linspace(axis[2], axis[3], int((axis[3]-axis[2])*100))
    )
    x_new=np.c_[x0.ravel(),x1.ravel()]
    #对横坐标axis[2]到axis[3]x0，纵坐标axis[0]到axis[1]x1进行组合，组合成n行两列的数据点，对这些数据点进行预测
    y_predict=model.predict(x_new).reshape(x0.shape)

    #引入ListedColormap用于生成非渐变的颜色映射
    from matplotlib.colors import ListedColormap
    # 自定义colormap
    custom_cmap=ListedColormap(['#EF9A9A','#FFF59D','#90CAF9'])
    #contourf(x, y, z)对等高线间的填充区域进行填充（使用不同的颜色）x和y为两个等长一维数组，第三个参数z为二维数组（表示平面点xi,yi映射的函数值）。
    plt.contourf(x0,x1,y_predict,linewidth=5,cmap=custom_cmap)

plot_decision_boundary(dt_clf,axis=[0.5,7.5,0,3])
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.title('DecisionTreeClassifier')
plt.show()

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
#采用鸢尾花数据集
iris=datasets.load_iris()
#为了可视化方便，只采用后两个维度数据
x=iris.data[:,-2:]
y=iris.target
def split(x,y,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
def gini(y):
    counter=Counter(y)
    res=1.0
    for num in counter.values():
        p=num/len(y)
        res+=-p**2
    return res

def try_split(x,y):
    best_g=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-1],d]!=x[sorted_index[i],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)
                g=gini(y_l)+gini(y_r)
                if g<best_g:
                    best_g,best_d,best_v=g,d,v
    return best_g,best_d,best_v

#第一次划分
best_g1,best_d1,best_v1=try_split(x,y)
print('best_g1',best_g1)
print('best_d1',best_d1)
print('best_v1',best_v1)
x1_l,x1_r,y1_l,y1_r=split(x,y,best_d1,best_v1)
print(gini(y1_l))
print(gini(y1_r))
#第二次划分
best_g2,best_d2,best_v2=try_split(x1_r,y1_r)
print('best_g2',best_g2)
print('best_d2',best_d2)
print('best_v2',best_v2)
x2_l,x2_r,y2_l,y2_r=split(x,y,best_d2,best_v2)
print(gini(y2_l))
print(gini(y2_r))

信息熵vs基尼系数

• 信息熵的计算速度比基尼系数稍慢（sklearn中默认为基尼系数）
• 大多时候二者没有特别的效果优劣

CART(Classification And Regression Tree)

根据某一个维度d和某一个阈值v进行二分，sklearn中的决策树实现都是：CART

算法的预测复杂度是O（logm）,训练复杂度是O(n*m*logm)，n为特征维度，m为样本个数

决策树和其他非参数学习算法一样，非常容易产生过拟合。所以一般都要对决策树进行剪枝操作，降低复杂度，解决过拟合。

接下来，在决策树中感受一下他的超参数，第一个是树的深度

import numpy as np

import matplotlib.pyplot as plt

from sklearn import datasets

x,y=datasets.make_moons(noise=0.25,random_state=666)

plt.scatter(x[y==0,0],x[y==0,1])

plt.scatter(x[y==1,0],x[y==1,1])

plt.show()

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
x,y=datasets.make_moons(noise=0.25,random_state=666)
plt.scatter(x[y==0,0],x[y==0,1])
plt.scatter(x[y==1,0],x[y==1,1])
plt.show()

from sklearn.tree import DecisionTreeClassifier
#实例化一个决策树，构建时不传参数是，默认使用gini系数，且不停划分，直到gini系数=0,这样划分下去必将产生过拟合
dt_clf=DecisionTreeClassifier()
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)),
        np.linspace(axis[2], axis[3], int((axis[3]-axis[2])*100))
    )
    x_new=np.c_[x0.ravel(),x1.ravel()]
    #对横坐标axis[2]到axis[3]x0，纵坐标axis[0]到axis[1]x1进行组合，组合成n行两列的数据点，对这些数据点进行预测
    y_predict=model.predict(x_new).reshape(x0.shape)

    #引入ListedColormap用于生成非渐变的颜色映射
    from matplotlib.colors import ListedColormap
    # 自定义colormap
    custom_cmap=ListedColormap(['#EF9A9A','#FFF59D','#90CAF9'])
    #contourf(x, y, z)对等高线间的填充区域进行填充（使用不同的颜色）x和y为两个等长一维数组，第三个参数z为二维数组（表示平面点xi,yi映射的函数值）。
    plt.contourf(x0,x1,y_predict,linewidth=5,cmap=custom_cmap)

plot_decision_boundary(dt_clf,axis=[-1.5,2.5,-1.0,1.5])
plt.scatter(x[y==0,0],x[y==0,1])
plt.scatter(x[y==1,0],x[y==1,1])
plt.show()

dt_clf2=DecisionTreeClassifier(max_depth=2)
dt_clf2.fit(x,y)
plot_decision_boundary(dt_clf2,axis=[-1.5,2.5,-1.0,1.5])
plt.scatter(x[y==0,0],x[y==0,1])
plt.scatter(x[y==1,0],x[y==1,1])
plt.show()

#至少要有10个样本数据，才对这个节点拆分下去
dt_clf3=DecisionTreeClassifier(min_samples_split=10)
dt_clf3.fit(x,y)
plot_decision_boundary(dt_clf3,axis=[-1.5,2.5,-1.0,1.5])
plt.scatter(x[y==0,0],x[y==0,1])
plt.scatter(x[y==1,0],x[y==1,1])
plt.show()

#min_samples_leaf要求叶子节点至少要有多少个，才对这个节点拆分下去
dt_clf4=DecisionTreeClassifier(min_samples_leaf=6)
dt_clf3.fit(x,y)
plot_decision_boundary(dt_clf4,axis=[-1.5,2.5,-1.0,1.5])
plt.scatter(x[y==0,0],x[y==0,1])
plt.scatter(x[y==1,0],x[y==1,1])
plt.show()