《统计学习方法》——从零实现决策树

决策树

决策树是一种树形结构,其中每个内部节点表示一个属性上的判断,每个分支代表一个判断结果的输出,最后每个叶子节点代表一种分类结果。

决策树学习的三个步骤:

  • 特征选择

通常使用信息增益最大、信息增益比最大或基尼指数最小作为特征选择的准则。

  • 树的生成

决策树的生成往往通过计算信息增益或其他指标,从根结点开始,递归地产生决策树。这相当于用信息增益或其他准则不断地选取局部最优的特征,或将训练集分割为能够基本正确分类的子集。

  • 树的剪枝

由于生成的决策树存在过拟合问题,需要对它进行剪枝,以简化学到的决策树。决策树的剪枝,往往从已生成的树上剪掉一些叶结点或叶结点以上的子树,并将其父结点或根结点作为新的叶结点,从而简化生成的决策树。

常用的特征选择准则:

(1)信息增益(ID3)

样本集合\(D\)对特征\(A\)的信息增益定义为:

\[g(D, A)=H(D)-H(D|A)
\]

\[H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}
\]

\[H(D | A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)
\]

(2)信息增益比(C4.5)

样本集合\(D\)对特征\(A\)的信息增益比定义为:

\[g_{R}(D, A)=\frac{g(D, A)}{H_A(D)}
\]

\[H_A(D)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|}log_2 \frac{\left|D_{i}\right|}{|D|}
\]

其中,\(g(D,A)\)是信息增益,\(H(D_A)\)是数据集\(D\)关于特征值A的熵,n是特征A取值的个数。

(3)基尼指数(CART)

样本集合\(D\)的基尼指数(CART)

\[\operatorname{Gini}(D)=1-\sum_{k=1}^{K}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2}
\]

特征\(A\)条件下集合\(D\)的基尼指数:

\[\operatorname{Gini}(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right)
\]

ID3、C4.5和CART的区别

(1)适用范围:

  • ID3和C4.5只能用于分类,CART还可以用于回归任务。

(2)样本数据:

  • ID3只能处理离散的特征,C4.5和CART可以处理连续变量的特征(通过对数据排序之后找到类别不同的分割线作为切分点,根据切分点把连续属性转换为布尔型, 从而将连续型变量转换多个取值区间的离散型变量)
  • ID3对特征的缺失值没有考虑,C4.5和CART增加了对缺失值的处理(主要是两个问题:样本某些特征缺失的情况下选择划分的属性;选定了划分属性,对于在该属性上缺失特征的样本的处理)
  • 从效率角度考虑,小样本C4.5,大样本CART。因为C4.5涉及到多次排序和对数运算,CART采用了简化的二叉树模型,在计算机中二叉树模型会比多叉树运算效率高,同时特征选择采用了近似的基尼系数来简化计算。

(3)节点特征选择:

  • 在每个内部节点的特征选择上,ID3选择信息增益最大的特征,C4.5选择信息增益比最大的特征,CART选择基尼指数最小的特征及其切分点作为最优特征和最优切分点。
  • ID3和C4.5节点上可以产出多叉,而CART节点上永远是二叉
  • 特征变量的使用中,对具有多个分类值的特征ID3和C4.5在层级之间只单次使用,CART可多次重复使用

(4)剪枝

  • C4.5是通过剪枝(PEP)来减小模型复杂度增加泛化能力,而CART是对所有子树中选取最优子树(CCP)

用numpy实现ID3决策树的代码如下:

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline

from collections import defaultdict
from math import log


# 生成书上的数据
def create_data():
    datasets = [['青年', '否', '否', '一般', '否'],
               ['青年', '否', '否', '好', '否'],
               ['青年', '是', '否', '好', '是'],
               ['青年', '是', '是', '一般', '是'],
               ['青年', '否', '否', '一般', '否'],
               ['中年', '否', '否', '一般', '否'],
               ['中年', '否', '否', '好', '否'],
               ['中年', '是', '是', '好', '是'],
               ['中年', '否', '是', '非常好', '是'],
               ['中年', '否', '是', '非常好', '是'],
               ['老年', '否', '是', '非常好', '是'],
               ['老年', '否', '是', '好', '是'],
               ['老年', '是', '否', '好', '是'],
               ['老年', '是', '否', '非常好', '是'],
               ['老年', '否', '否', '一般', '否'],
               ]
    df = pd.DataFrame(datasets, columns=[u'年龄', u'有工作', u'有自己的房子', u'信贷情况', u'类别'])
    return df


# 计算数据集的熵,需D的最后一列为标签
def entropy(D):
    total_num = len(D)
    label_cnt = defaultdict(int)
    for i in range(total_num):
        label = D[i][-1]
        label_cnt[label] += 1
    ent = -sum([(cnt/total_num) * log(cnt/total_num, 2) for cnt in label_cnt.values()])
    return ent


# 计算列索引为index的属性对集合D的条件熵
def cond_entropy(D, index):
    total_num = len(D)
    feature_sets = defaultdict(list)
    for i in range(total_num):
        feature = D[i][index]
        feature_sets[feature].append(D[i])
    cond_ent = sum([(len(d)/total_num) * entropy(d) for d in feature_sets.values()])
    return cond_ent
# 决策树节点类
class Node:
    def __init__(self, is_leaf, label=None, feature_idx=None, feature_name=None):
        self.is_leaf = is_leaf
        self.label = label  # 仅针对于叶子节点
        self.feature_idx = feature_idx  # 该节点特征对应的列索引,仅针对于非叶子节点
        self.feature_name = feature_name  # 该节点特征名,仅针对于非叶子节点
        self.sons = {}
        
    def add_son(self, feature_value, node):
        self.sons[feature_value] = node
        
    def predict(self, x):
        if self.is_leaf:
            return self.label
        return self.sons[x[self.feature_idx]].predict(x)
    
    def __repr__(self):
        s = {
            'feature:': self.feature_name,
            'label:': self.label,
            'sons:': self.sons
            }
        return '{}'.format(s)


# ID3决策树
class ID3DTree:
    def __init__(self, epsilon=0.1):
        """
        epsilon: 决策树停止生长的信息增益阈值
        """
        self.epsilon = epsilon
        self.decision_tree = None
        
    def fit(self, data):
        """data为dataframe格式"""
        self.decision_tree = self._train(data)
        return self.decision_tree
        
    def predict(self, x):
        if self.decision_tree:
            return self.decision_tree.predict(x)
        
    def _get_max_gain_feature(self, D):
        num_features = len(D[0]) - 1
        ent_D = entropy(D)
        index, max_gain = 0, 0
        for i in range(num_features):
            cond_ent = cond_entropy(D, i)
            gain = ent_D - cond_ent  # 信息增益 = H(D) - H(D|A)
            if gain > max_gain:
                max_gain = gain
                index = i
        return index, max_gain
            
    def _train(self, data):
        """递归构建决策树,data为dataframe格式"""
        y, feature_names = data.iloc[:, -1], data.columns[:-1]
        # 1.数据集中所有样本均属于同一类别,则停止生长
        if len(y.value_counts()) == 1:
            return Node(is_leaf=True, label=y.iloc[0])
        
        # 2.数据集中特征数量为空,则将包含实例数量最多的类作为该叶子节点的标签
        if len(feature_names) == 0:
            label = y.value_counts().sort_values(ascending=False).index[0]
            return Node(is_leaf=True, label=label)
        
        # 计算信息增益最大的特征
        idx, max_gain = self._get_max_gain_feature(np.array(data))
        # 3. 如果最大的信息增益小于设置的阈值,则停止生长
        if max_gain < self.epsilon:
            label = y.value_counts().sort_values(ascending=False).index[0]
            return Node(is_leaf=True, label=label)
        
        target_feature = feature_names[idx]  # 当前节点特征
        curr_node = Node(is_leaf=False, feature_idx=idx, feature_name=target_feature)
        value_sets = data[target_feature].value_counts().index  # 该特征取值集合
        for value in value_sets:
            sub_data = data.loc[data[target_feature]==value].drop([target_feature], axis=1)
            # 4.递归生成子树
            sub_tree = self._train(sub_data)
            curr_node.add_son(value, sub_tree)
            
        return curr_node

测试代码:

df_data = create_data()
dt = ID3DTree()
tree = dt.fit(df_data)
print('决策树:{}'.format(tree))

y_test = dt.predict(['老年', '否', '是', '非常好'])
print('样本 [老年, 否, 是, 非常好] 的预测结果:{}'.format(y_test))

输出为:

决策树:{'feature:': '有自己的房子', 'label:': None, 'sons:': {'否': {'feature:': '有工作', 'label:': None, 'sons:': {'否': {'feature:': None, 'label:': '否', 'sons:': {}}, '是': {'feature:': None, 'label:': '是', 'sons:': {}}}}, '是': {'feature:': None, 'label:': '是', 'sons:': {}}}}
样本 [老年, 否, 是, 非常好] 的预测结果:是