决策树_决策树算法 - CSDN
决策树 订阅
决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干,故称决策树。在机器学习中,决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度,使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类别。分类树(决策树)是一种十分常用的分类方法。他是一种监督学习,所谓监督学习就是给定一堆样本,每个样本都有一组属性和一个类别,这些类别是事先确定的,那么通过学习得到一个分类器,这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。 展开全文
决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干,故称决策树。在机器学习中,决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度,使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类别。分类树(决策树)是一种十分常用的分类方法。他是一种监督学习,所谓监督学习就是给定一堆样本,每个样本都有一组属性和一个类别,这些类别是事先确定的,那么通过学习得到一个分类器,这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。
信息
外文名
Decision Tree
中文名
决策树
决策树组成
□——决策点,是对几种可能方案的选择,即最后选择的最佳方案。如果决策属于多级决策,则决策树的中间可以有多个决策点,以决策树根部的决策点为最终决策方案。 [1]  ○——状态节点,代表备选方案的经济效果(期望值),通过各状态节点的经济效果的对比,按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝,概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。 [1]  △——结果节点,将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。 [1]  【概述来源】 [2] 
收起全文
精华内容
参与话题
  • 决策树

    万次阅读 多人点赞 2018-08-14 21:07:39
    这篇博客用来简要介绍决策树算法(DecisionTree) 决策树是机器学习中常用的一种算法,它即可用于解决分类问题,也可用于解决回归问题,在这篇博客我们只介绍分类决策树决策树顾名思义是一种树形结构,而我们的...

    这篇博客用来简要介绍决策树算法(DecisionTree)

    决策树是机器学习中常用的一种算法,它即可用于解决分类问题,也可用于解决回归问题,在这篇博客我们只介绍分类决策树。

    决策树顾名思义是一种树形结构,而我们的任务就是想办法构建出这样一颗树用它来进行分类。

    在开始介绍决策树的构建之前,首先介绍几个相关概念,信息熵条件熵以及信息增益

    信息熵

    我个人的理解,信息熵就是用来衡量一个随机变量取值的不确定性的一个指标,信息熵越大则不确定性越大,信息熵越小则不确定性也就越小。

    假设一个随机变量X的概率分布如下:

    X

    v_1

    v_2 .... v_n
    p p_1 p_2 .... p_n

    则随机变量X的信息熵的计算公式如下:

    H(X)=\sum _{i=1}^{n}-p_ilogp_i

    通常情况下对数以2为底或以e(自然对数)为底,并且我们规定如果p_i=0则定义0log0=0

    一个服从两点分布的随机变量的信息熵图像如下图所示:

    可以看出当概率p=0.5时,信息熵最大,随机变量的不确定性也就最大,从直观的角度这也很容易理解,即如果随机变量属于两个值的概率都相等,那我们很难确定它属于哪一个值,反之如果不相等,则我们将猜测随机变量属于概率大的哪一个值。

    条件熵

    设二维随机变量(X, Y)的概率分布为:

    p(X=x_i, Y=y_i)=p_{ij}, \;\;i=1, 2, 3, ..., n;\;\;j=1, 2, 3, ..., m

    p_i=p(X=x_i)

    我们将随机变量X给定条件下随机变量Y的条件熵表示为H(Y|X),表示在已知随机变量X的情况下随机变量Y的不确定性,其定义如下:

    H(Y|X)=\sum _{i=1}^{n}p_iH(Y|X=x_i)

    实际上就是给定X的条件下随机变量Y的熵对于X的期望值。

    信息增益

    信息增益表示为g(Y, X),其含义为给定X的能够使随机变量Y的确定性增加的程度。

    计算方式如下:

    g(Y, X) = H(Y) - H(Y|X)

    这个很好理解,当我们知道某些信息时肯定是要比什么都不知道的时候更能确定某个随机变量的取值,除非这些信息是无效信息,否则肯定会带来确定性的增加,即信息增益。

    接下来我们就来探究决策树构建过程

    决策树由节点和有向边所构成,节点分为叶子节点和内部节点两部分,通常情况下,节点分支都为二叉的,如下图所示:

    图中圆形为内部节点,方块为叶子节点。

    我们以案例驱动的方式来解释决策树是如何构建出来的,其过程分为两步,特征选择以及决策树的生成

    首先我们给定一张数据表,数据表中记录的是一些贷款信息,如下图所示:

    贷款申请样本数据表
    ID 年龄 有工作 有房子 信贷情况 类别
    1 青年 一般
    2 青年
    3 青年
    4 青年 一般
    5 青年 一般
    6 中年 一般
    7 中年
    8 中年
    9 中年 非常好
    10 中年 非常好
    11 老年 非常好
    12 老年
    13 老年
    14 老年 非常好
    15 老年 一般

    我们的任务就是构建一颗决策树来进行判断是否同意某个人的贷款申请。

    我们用随机变量Y来表示类别(0表示否,1表示是), A表示年龄(0表示青年,1表示中年,2表示老年),W是否有工作(0表示否,1表示是),R表示是否有房子(0表示否,1表示是),C表示信贷情况(0表示一般,1表示好,2表示非常好)

    根节点包含的样本:所有样本

    根节点信息熵:

    H(Y) =- \frac{6}{15}log\frac{6}{15} - \frac{9}{15}log\frac{9}{15}\approx 0.97

    根节点各个特征的条件熵:

    H(Y|A)=p(A=0)H(Y|A=0)+p(A=1)H(Y|A=1)+p(A=2)H(Y|A=2)=\frac{1}{3}(-\frac{2}{5}log\frac{2}{5}-\frac{3}{5}log\frac{3}{5})+\frac{1}{3}(-\frac{2}{5}log\frac{2}{5}-\frac{3}{5}log\frac{3}{5})+\frac{1}{3}(-\frac{1}{5}log\frac{1}{5}-\frac{4}{5}log\frac{4}{5})\approx 0.89

    H(Y|W)=p(W=0)H(Y|W=0)+p(W=1)H(Y|W=1)=\frac{10}{15}(-\frac{6}{10}log\frac{6}{10}-\frac{4}{10}log\frac{4}{10})+\frac{5}{15}(-1log1 - 0log0)\approx 0.65

    H(Y|R)=p(R=0)H(Y|R=0)+p(R=1)H(Y|R=1)=\frac{9}{15}(-\frac{6}{9}log\frac{6}{9}-\frac{3}{9}log\frac{3}{9})+\frac{6}{15}*0\approx 0.55

    H(Y|C)=p(C=0)H(Y|C=0)+p(C=1)H(Y|C=1)+p(C=2)H(Y|C=2)\approx 0.61

    计算信息增益:

    g(Y, A)=H(Y) - H(Y|A)=0.08

    g(Y, W)=H(Y) - H(Y|W)=0.32

    g(Y, R)=H(Y) - H(Y|R)=0.42

    g(Y, C)=H(Y) - H(Y|C)=0.36

    因此可以确定,当分支特征为R(是否有房子)时带来的信息增益越大,因此根节点的分支特征选择为是否有房子,分为左右两支,左子节点中的数据集为没有房子的样本,右子节点的数据集为有房子,之后以此类推便构建出了决策树模型。

    综上,每个节点的分支过程可以分为以下几步:

    1.确定当前节点的信息熵以及各个特征的条件熵

    2.计算各个特征的信息增益

    3.确定当前节点的分支特征

    那么,我们如何决定什么时候停止分支呢?我们可以这样设置,当某个节点的信息熵小于某个阈值时我们就停止对这个节点的分支操作,那么此节点也就成为了叶子节点。

    最终我们需要确定每个叶子结点的类别,即叶子结点中的样本集中,占比最大的那一个类别便是当前叶子节点的类别,当新来一个样本我们只需要按照决策树从顶层向下逐步判断,看样本最终落入那个叶子结点,所落入的叶子结点的类别便是当前样本的预测类别。

    至此决策树的基本原理已经介绍完毕,要说明的是,以上介绍的只是决策树当中的ID3算法,在ID3算法提出之后,相继又提出了C4.5算法和CART,与ID3算法不同的是,C4.5算法采用的特征选择指标是信息增益率而不是信息增益,其他原理同ID3相同。实际上信息增益率的计算方法也相当简单,就是信息增益与特征的熵的比值;而CART(Class and Regression Tree)从名字看出来即可做分类又可做回归,与ID3不同的是,作为分类树时,其选择划分节点的特征的依据是基尼系数,选择使得划分后数据集基尼系数最小的那个特征作为节点的划分的特征。如果是构建回归树,则划分节点的特征的选择是依据划分后子节点的方差,我们尽可能选择使得方差最小的划分特征,我们往往使用启发式的方式来搜索划分特征以及划分特征的值,即依次遍历各个维度的特征,当遍历到当前维度特征时,依次遍历当前特征的所有值作为划分值从而选出使得子节点方差最小的划分特征以及特征的值。

    以下为本人使用Python编写的决策树的相关程序:

    from sklearn.datasets import load_iris
    from sklearn.model_selection import train_test_split
    import numpy as np
    from sklearn.metrics import accuracy_score
    
    
    class DecesionTree(object):
    
        def __init__(self, stop_entropy, deepth):
            """
    
            :param stop_entropy: 终止分裂的最小熵值
            :param deepth: 决策树最大深度
            """
            self.stop_entropy = stop_entropy
            self.deepth = deepth
            data = load_iris()
            x = data["data"]
            y = data["target"]
            self.x_train, self.x_test, self.y_train, self.y_test = train_test_split(x, y, random_state=2, test_size=0.3)
            self.tree = {}
            for layer in range(deepth):
                self.tree[layer] = [None] * 2 ** layer
            attr_max_values = np.max(self.x_train, axis=0)
            attr_min_values = np.min(self.x_train, axis=0)
            # self.split_values用来记录每一维特征的所有可能的分割值, self.split[i]表示第i维特征的所有可能的分割值
            self.split_values = []
            for min_value, max_value in zip(attr_min_values, attr_max_values):
                self.split_values.append(np.linspace(min_value, max_value, 102, endpoint=True)[1:-1])
    
        def generate_tree(self):
            for layer in range(self.deepth):
                # 遍历是第几层节点
                # node_num用于标记当前层节点的个数
                node_num = 2 ** layer
                for node_index in range(1, node_num + 1):
                    # 先确定当前节点的数据集,标记
                    node = Node()
                    if layer == 0:
                        # 如果是第0层,则当前节点node的数据集就是训练集
                        node.data_set = self.x_train
                        node.labels = self.y_train
                    else:
                        # 如果不是0层,则需要根据父节点来获取当前节点的数据集
                        # previous_index为生成当前节点的上一层父节点的索引
                        previous_index = int(np.ceil(node_index / 2)) - 1
                        previous_node = self.tree[layer - 1][previous_index]
                        if (previous_node is None) or (previous_node.attr_split is None):
                            # 判断如果父节点为叶子节点则跳过当前节点的构造
                            continue
                        attr_split = previous_node.attr_split
                        split_value = previous_node.split_value
                        data_set = previous_node.data_set
                        labels = previous_node.labels
                        if node_index % 2 != 0:
                            # 上一层节点的左分支(小于分割值)
                            data_index = data_set[:, attr_split] < split_value
                            node.data_set = data_set[data_index]
                            node.labels = labels[data_index]
                        else:
                            # 上一层节点的右分支(大于等于分割值)
                            data_index = data_set[:, attr_split] >= split_value
                            node.data_set = data_set[data_index]
                            node.labels = labels[data_index]
                    # 确定当前节点数据集后,计算当前节点信息熵,确定是否进行分割,如果小于停止分割信息熵,则不分割,否则分割
                    current_node_entropy = self.calc_entropy(node.labels)
                    if current_node_entropy < self.stop_entropy:
                        # 小于停止分割信息熵则不对当前节点的attr_split以及split_value赋值,当前节点成为叶子节点
                        self.tree[layer][node_index - 1] = node
                        continue
                    else:
                        # 确定当前节点的分割特征以及分割特征的值
                        courrent_entropy_gain = 0
                        current_attr_split = None
                        current_split_value = None
                        for attr_split_index in range(4):
                            # 遍历四个维度的特征
                            for split_value in self.split_values[attr_split_index]:
                                entropy_gain = self.calc_entropy_gain(attr_split_index, split_value, node.data_set, node.labels)
                                if entropy_gain >= courrent_entropy_gain:
                                    courrent_entropy_gain = entropy_gain
                                    current_attr_split = attr_split_index
                                    current_split_value = split_value
                        node.attr_split = current_attr_split
                        node.split_value = current_split_value
                    self.tree[layer][node_index - 1] = node
            values = list(self.tree.values())
            for value in values:
                if np.all(np.logical_not(np.array(value, np.bool))):
                    index_ = values.index(value)
                    break
            else:
                index_ = self.deepth
            nodes = self.tree[index_ - 1]
            for node in nodes:
                if isinstance(node, Node):
                    node.attr_split = None
                    node.split_value = None
    
        def calc_entropy(self, labels):
            """
    
            :param labels: 要计算熵值的数据集的标记
            :return: 数据集的熵值
            """
            # 计算信息熵
            label_unique = np.unique(labels)
            labels_list = list(labels)
            p_list = []
            for label in label_unique:
                p_list.append(labels_list.count(label) / len(labels_list))
            entropy = 0
            for p in p_list:
                entropy -= p * np.log2(p)
            return entropy
    
        def calc_condition_entropy(self, attr_split, split_value, data_set, labels):
            """
    
            :param attr_split: 用来分割数据集的特征
            :param split_value: 用来分割数据集的特征的值
            :param data_set: 被分割的数据集
            :param labels: 被分割的数据集标记
            :return: 条件熵, 大于分割特征特征值的数据集和标记以及小于分割特征特征值的数据集和标记
            """
            # 计算小于分割值的数据集的熵
            smaller_index = data_set[:, attr_split] < split_value
            smaller_data_set = data_set[smaller_index]
            smaller_label = labels[smaller_index]
            smaller_entropy = self.calc_entropy(smaller_label)
            # 计算大于分割值的数据集的熵
            bigger_index = data_set[:, attr_split] >= split_value
            bigger_data_set = data_set[bigger_index]
            bigger_label = labels[bigger_index]
            bigger_entropy = self.calc_entropy(bigger_label)
            # 两部分熵加权求和得到条件熵
            p_smaller = len(smaller_label) / len(labels)
            p_bigger = len(bigger_label) / len(labels)
            condition_entropy = p_smaller * smaller_entropy + p_bigger * bigger_entropy
            return condition_entropy, bigger_data_set, bigger_label, smaller_data_set, smaller_label
    
        def calc_entropy_gain(self, attr_split, split_value, data_set, labels):
            entropy = self.calc_entropy(labels)
            condition_entropy = self.calc_condition_entropy(attr_split, split_value, data_set, labels)[0]
            entropy_gain = entropy - condition_entropy
            return entropy_gain
    
        def leaf_node_label(self):
            # 确定叶子节点的类别
            nodes = []
            nodes_list = self.tree.values()
            for nd in nodes_list:
                nodes.extend(nd)
            while True:
                if None in nodes:
                    nodes.remove(None)
                else:
                    break
            for node in nodes:
                if not node.split_value:
                    labels = np.unique(node.labels)
                    p = []
                    for label in labels:
                        p.append(list(node.labels).count(label) / len(node.labels))
                    node.predict_label = labels[p.index(max(p))]
    
        def test(self):
            self.y_test_pred = []
            for test_sample in self.x_test:
                current_nodes = [self.tree[0][0]]
                for layer in range(1, self.deepth):
                    current_attr_split = current_nodes[-1].attr_split
                    current_split_value = current_nodes[-1].split_value
                    # 寻找下一个子节点
                    if test_sample[current_attr_split] < current_split_value:
                        current_node = self.tree[layer][self.tree[layer - 1].index(current_nodes[-1]) * 2]
                    else:
                        current_node = self.tree[layer][self.tree[layer - 1].index(current_nodes[-1]) * 2 + 1]
                    current_nodes.append(current_node)
                    if not current_node.split_value:
                        # 如果已经到叶节点就不在继续
                        break
                y_pred = current_nodes[-1].predict_label
                self.y_test_pred.append(y_pred)
            print("鸢尾花数据测试集预测结果:")
            print("测试集预测类别:", self.y_test_pred)
            print("测试集真实类别:", list(self.y_test))
            print("预测准确率:%.2f%s" % (100 * accuracy_score(self.y_test, self.y_test_pred), "%"))
    
    
    class Node(object):
    
        def __init__(self):
            # self.data_set为当前节点的样本
            self.data_set = None
            # self.labels为当前节点的样本对应的标记
            self.labels = None
            # self.attr_split为用来分割当前节点的特征是哪一维
            self.attr_split = None
            # self.split_value为分割当前节点特征的分割值是多少
            self.split_value = None
            # 如果当前节点为叶子节点,则self.predict_label代表当前叶节点的类别
            self.predict_label = None
    
    
    def main():
        tree = DecesionTree(0.2, 3)
        tree.generate_tree()
        tree.leaf_node_label()
        tree.test()
    
    
    if __name__ == "__main__":
        main()

     

    展开全文
  • 决策树(Decision Tree)是一种基本的分类与回归方法。本文会讨论决策树中的分类树与回归树,后续文章会继续讨论决策树的Boosting和Bagging的相关方法。决策树由结点和有向边组成。结点有两种类型:内部结点和叶结点...

    分类目录:《深入理解机器学习》总目录
    相关文章:
    基于决策树的模型(一)分类树和回归树
    基于树的模型(二):集成学习之Bagging和Random Forest
    基于树的模型(三):集成学习之GBDT和XGBoost
    基于树的模型(四):随机森林的延伸——深度森林(gcForest)
    基于树的模型(五):从零开始用Python实现ID3决策树
    基于树的模型(六):Python实现CART决策树并利用Tkinter构建GUI对决策树进行调优
    基于树的模型(七):RF/XGBoost等算法实践与决策树Scala实践等(材料准备中)


    决策树(Decision Tree)是一种基本的分类与回归方法,当决策树用于分类时称为分类树,用于回归时称为回归树。本文主要讨论决策树中的分类树与回归树的一些基本理论,后续文章会继续讨论决策树的BoostingBagging相关方法。

    决策树由结点和有向边组成。结点有两种类型:内部结点和叶结点,其中内部结点表示一个特征或属性,叶结点表示一个类。一般的,一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于决策结果,其他每个结点则对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中,根结点包含样本全集,从根结点到每个叶结点的路径对应了一个判定测试序列。在下图中,圆和方框分别表示内部结点和叶结点。决策树学习的目的是为了产生一棵泛化能力强,即处理未见示例能力强的决策树。
    j决策树图示

    分类树

    分类树是一种描述对实例进行分类的树形结构。在使用分类树进行分类时,从根结点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点。这时,每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配,直至达到叶结点。最后将实例分到叶结点的类中。

    假设给定训练数据集:
    D={(x1,y1),(x2,y2),...,(xN,yN)}D=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}其中,xi=(xi(1),xi(2),...,xi(n))T,x_i=(x_i^{(1)}, x_i^{(2)}, ..., x_i^{(n)})^T,为输入实例,即特征向量,nn为特征个数,i=12Ni=1,2…,NNN为样本容量,yi{1,2,...,K}y_i \in \{ 1, 2, ..., K\}为类标。分类树学习的目标是根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。

    决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个,也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树,同时具有很好的泛化能力。从另一个角度看,决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个,我们选择的条件概率模型应该不仅对训练数据有很好的拟合,而且对未知数据有很好的预测。

    决策树学习用损失函数表示这一目标,其损失函数通常是正则化的极大似然函数,决策树学习的策略是以损失函数为目标函数的最小化。当损失函数确定以后,学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题,所以现实中决策树学习算法通常采用启发式方法,近似求解这一最优化问题。这样得到的决策树是次最优的。

    决策树分类算法
    输入:
    \qquad 训练集:D=(x1,y1),(x2,y2),&ThinSpace;,(xN,yN)D = {(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)}
    \qquad 属性集:A=a1,a2,&ThinSpace;,anA = {a_1, a_2, \cdots, a_n}
    过程:
    \qquad 函数TreeGenerate(D,A)TreeGenerate(D, A)
    输出:
    \qquad 以node为根节点的决策树
    算法:
    ( 1 ) 生成结点根node
    ( 2 ) if DD中样本全属于同一类别CkC_k then
    ( 3 ) \quad 将node标记为CkC_k类叶结点
    ( 4 ) \quad return
    ( 5 ) end if
    ( 6 ) if A=A = \varnothing OR DD中样本在AA上取值相同 then
    ( 7 ) \quad 将node标记为叶结点,其类别标记为DD中样本数最多的类
    ( 8 ) \quad return
    ( 9 )end if
    (10)从AA中选择最优划分属性aa_*
    (11)for aa_* 的每一个值ava_*^v do
    (12)\quad 为node生成一个分支:令DvD_v表示DD中在aa_*上取值为ava_*^v的样本子集
    (13)\quad if DvD_v为空 then
    (14)\qquad 将分支结点标记为叶结点,其类别标记为DD中样本最多的类
    (15)\qquad return
    (16)\quad else
    (17)\qquadTreeGenerate(Dv,A{a})TreeGenerate(D_v, A - \{a_*\})为分支结点
    (18)\quad end if
    (19)end for

    决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。开始,构建根结点,将所有训练数据都放在根结点。选择一个最优特征,按照这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类,那么构建叶结点,并将这些子集分到所对应的叶结点中去,如果还有子集不能被基本正确分类,那么就对这些子集选择新的最优特征,继续对其进行分割,构建相应的结点。如此递归地进行下去,直至所有训练数据子集被基本正确分类,或者没有合适的特征为止。最后每个子集都被分到叶结点上,即都有了明确的类。这就生成了一棵决策树。

    从上述过程中就可以看出,决策树的生成是一个递归过程。在决策树基本算法中,有三种情形会导致递归返回

    1. 当前结点包含的样本全属于同一类别,无需划分
    2. 当前属性集为空,或是所有样本在所有属性上取值相同,无法划分
    3. 当前结点包含的样本集合为空,不能划分

    在第二种情形下,我们把当前结点标记为叶结点,并将其类别设定为该结点所含样本最多的类别。在第三种情形下,同样把当前结点标记为叶结点,但将其类别设定为其父结点所含样本最多的类别。这两种情形的处理实质不同:第二种情况是在利用当前结点的后验分布,而第三种情况则是把父结点的样本分布作为当前结点的先验分布

    以上方法生成的决策树可能对训练数据有很好的分类能力,但对未知的测试数据却未必有很好的分类能力,即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝,将树变得更简单,从而使它具有更好的泛化能力。具体地,就是去掉过于细分的叶结点,使其回退到父结点,甚至更高的结点,然后将父结点或更高的结点改为新的叶结点。如果特征数量很多,也可以在决策树学习开始的时候,对特征进行选择,只留下对训练数据有足够分类能力的特征。

    可以看出,决策树学习算法包含特征选择决策树的生成决策树的剪枝过程。由于决策树表示一个条件概率分布,所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择,决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优,相对地,决策树的剪枝则考虑全局最优。

    决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。分类树具有良好的可读性与分类速度快的优点。分类树在学习时,利用训练数据,根据损失函数最小化的原则建立分类树模型,在预测时,对新的数据,利用分类树模型进行分类。决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的修剪。

    决策树与if-then规则

    可以将决策树看成一个if-then规则的集合:由决策树的根结点到叶结点的每一条路径构建一条规则,路径上内部结点的特征对应着规则的条件,而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质——互斥并且完备。这就是说,每一个实例都被一条路径或一条规则所覆盖,而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

    决策树与条件概率分布

    决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域,并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设XX为表示特征的随机变量,YY为表示类的随机变量,那么这个条件概率分布可以表示为PYXP(Y|X)XX取值于给定划分下单元的集合,YY取值于类的集合。各叶结点(单元)上的条件概率往往偏向某一个类,即属于某一类的概率较大。决策树分类时将该结点的实例强行分到条件概率大的那一类去。

    决策树的优缺点
    • 计算复杂度不高
    • 对中间缺失值不敏感
    • 解释性强,在解释性方面甚至比线性回归更强
    • 与传统的回归和分类方法相比,决策树更接近人的决策模式
    • 可以用图形表示,非专业人士也可以轻松理解
    • 可以直接处理定性的预测变量而不需创建哑变量
    • 决策树的预测准确性一般比回归和分类方法弱,但可以通过用集成学习方法组合大量决策树,显著提升树的预测效果

    特征选择

    特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。比如,我们希望构建一棵决策树来根据不同人的各种属性来预测每个人性别,那么对于属性“头发的长度”可能就要比属性“头发的颜色”所能包含的信息更多。因为一般来说,男生的头发要比女生的头发短,所以我们希望“头发的长度”这个属性处于决策树的上部。随着划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”(purity)越来越高。

    信息增益

    为了便于说明信息增益,先给出熵与条件熵的定义。在信息论与概率统计中,熵(entropy)是表示随机变量不确定性的度量。设XX是一个取有限个值的离散随机变量,其概率分布为:
    P(X=xi)=pi,i=1,2,&ThinSpace;,nP(X = x_i) = p_i, i = 1, 2, \cdots, n
    则随机变量XX的熵定义为:
    H(X)=i=1npilogpiH(X) = -\sum_{i = 1}^n p_i \log p_i
    在上式中,若pi=0p_i = 0,则定义pilogpi=0p_i \log p_i = 0。通常,上式中的对数以22为底或以ee为底(自然对数),这时熵的单位分别称作比特(bit)或纳特(nat).由定义可知,熵只依赖于XX的分布,而与XX的取值无关,所以也可将XX的熵记作H(p)H(p),即:
    H(p)=i=1npilogpiH(p) = -\sum_{i = 1}^n p_i \log p_i
    由此可见,熵越大,随机变量的不确定性就越大。从熵的定义可验证
    0H(p)logn0 \leq H(p) \leq \log n
    当随机变量只取两个值,例如1,0时,即XX的分布为:
    P(X=1)=p,P(X=0)=1p,0p1P(X = 1) = p,\quad P(X = 0) = 1-p, \quad 0≤p≤1
    其熵为:
    H(p)=plog2p(1p)log2(1p)H(p) = -p \log_2 p - (1 - p)\log_2 (1 - p)
    这时,熵H(p)H(p)随概率pp变化的曲线如下图所示(单位为比特):
    熵的变化曲线
    p=0p = 0p=1p = 1H(p)=0H(p) = 0,随机变量完全没有不确定,当p=0.5p = 0.5时,H(p)=1H(p) = 1,熵取值最大,随机变量不确定性最大。

    设有随机变量(X,Y)(X, Y),其联合概率分布为:

    P(X=xi,Y=yi)=pij{i=1,2,&ThinSpace;,nj=1,2,&ThinSpace;,m P(X = x_i, Y = y_i) = p_{ij} \quad \begin{cases} i = 1, 2, \cdots, n \\ j = 1, 2, \cdots, m \end{cases}

    条件熵H(YX)H(Y|X)表示在已知随机变量XX的条件下随机变量YY的不确定性。随机变量XX给定的条件下随机变量YY的条件熵(conditional entropy)H(YX)H(Y|X),定义为XX给定条件下YY的条件概率分布的熵对XX的数学期望:
    H(YX)=i=1npiH(YX=xi)H(Y|X) = \sum_{i = 1}^n p_iH(Y|X = x_i)

    其中,pi=P(X=xi),i=1,2,&ThinSpace;,np_i = P(X = x_i), i = 1, 2, \cdots, n

    当熵和条件熵中的概率由数据估计(如极大似然估计)得到时,所对应的熵与条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。此时,如果有0概率,令0log0=00\log0 = 0

    信息增益(information gain)表示得知特征XX的信息而使得类YY的信息的不确定性减少的程度。特征aa_*对训练数据集DD的信息增益g(D,a)g(D, a_*),定义为集合DD的经验熵H(D)H(D)与特征aa_*给定条件下DD的经验条件熵H(Da)H(D|a_*)之差,即:
    g(D,a)=H(D)H(Da)g(D, a_*) = H(D) - H(D|a_*)
    一般地,熵H(Y)H(Y)与条件熵H(YX)H(Y|X)之差称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

    决策树学习应用信息增益准则选择特征。给定训练数据集DD和特征aa_*,经验熵H(D)H(D)表示对数据集DD进行分类的不确定性。而经验条件熵H(Da)H(D|a_*)表示在特征aa_*给定的条件下对数据集DD进行分类的不确定性。那么它们的差,即信息增益,就表示由于特征aa_*而使得对数据集DD的分类的不确定性减少的程度。显然,对于数据集DD而言,信息增益依赖于特征,不同的特征往往具有不同的信息增益,信息增益大的特征具有更强的分类能力。

    根据信息增益准则的特征选择方法:对训练数据集(或子集)DD,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。

    设训练数据集为DDD|D|表示其样本容量,即样本个数。设有KK个类CkC_kk=1,2,&ThinSpace;,Kk=1, 2, \cdots, KCk|C_k|为属于类CkC_k的样本个数,k=1KCk=D\sum_{k=1}^K |C_k| = |D|。设特征aa_*VV个不同的取值{a1,a2,&ThinSpace;,aV}\{ a_*^1, a_*^2, \cdots, a_*^V\},根据特征aa_*的取值将DD划分为VV个子集D1,D2,&ThinSpace;,DVD_1, D_2, \cdots, D_VDt|D_t|DtD_t的样本个数,i=1nDt=D\sum_{i=1}^n|D_t|=|D|。记子集DiD_i中属于类CkC_k的样本的集合为DikD_{ik}。即Dik=DiCkD_{ik} = D_i \cap C_kDik|D_{ik}|DikD_{ik}的样本个数。于是计算信息增益的方法如下:

    信息增益
    输入:训练数据集DD和特征aa_*
    输出:特征aa_*对训练数据集DD的信息增益g(D,a)g(D, a_*)
    1.计算数据集DD的经验熵H(D)H(D)H(D)=k=1KCkDlog2CkDH(D) = -\sum_{k=1}^K \frac{C_k}{D}\log_2\frac{C_k}{D}
    2.计算特征AA对数据集DD的经验条件熵H(DA)H(D|A)H(DA)=i=1nDiDH(Di)=i=1nDiDk=1KDikDilog2DikDiH(D|A) = \sum_{i=1}^n\frac{|D_i|}{D}H(D_i)=-\sum_{i=1}^n\frac{|D_i|}{D}\sum_{k=1}^K\frac{D_{ik}}{D_i}\log_2\frac{D_{ik}}{D_i}
    3.计算信息增益:g(D,a)=H(D)H(Da)g(D, a_*) = H(D) - H(D|a_*)

    一般而言,信息增益越大,则意味着使用特征aa_*来进行划分所获得的“纯度提升”越大。因此,我们可用信息增益来进行决策树的划分属性选择,即在上述决策树分类算法第10行使用a=arg maxaAg(D,a)a_* = \text{arg}\ \max_{a \in A}g(D, a)选择最优划分属性。著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。

    ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归地构建决策树。具体方法是:从根结点开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子结点。之后,再对子结点递归地调用以上方法,构建决策树,直到所有特征的信息增益均很小或没有特征可以选择为止,最终得到一个决策树。ID3相当于用极大似然法进行概率模型的选择

    ID3算法
    输入:训练数据集DD,特征集AA,阀值ϵ\epsilon
    输出:决策树TT
    1.若DD中所有实例属于同一类CkC_k,则TT为单结点树,并将类CkC_k作为该结点的类标记,返回决策树TT
    2.若A=A = \varnothing,则TT为单结点树,并将DD中实例数最大的类CkC_k,作为该结点的类标记,返回决策树TT
    3.否则,计算AA中各特征对DD的信息增益,选择信息增益最大的特征aa_*
    4.如果aa_*的信息增益小于阀值ϵ\epsilon,则置TT为单结点树,并将DD中实例数最大的类CkC_k作为该结点的类标记,返回决策树TT
    5.否则,对aa_*的每一可能值ava_*^v,依a=ava_* = a_*^vDD分割为若干非空子集DvD_v,将DvD_v中实例数最大的类作为标记,构建子结点,由结点及其子结点构成决策树TT,返回决策树TT
    6.对第vv个子结点,以DvD_v为训练集,以A{a}A - \{a_*\}为特征集,递归地调用第(1)步~第(5)步,得到子树TvT_v,并返回子树TvT_v

    信息增益率

    信息增益值的大小是相对于训练数据集而言的,并没有绝对意义。在训练数据集的经验熵大的时候,信息增益值会偏大。反之,信息增益值会偏小。使用信息增益率(information gain ratio)可以对这一问题进行校正。这是特征选择的另一准则。特征aa_*对训练数据集DD的信息增益率gg(D,a)g_g(D, a_*)定义为其信息增益g(D,a)g(D, a_*)与训练数据集DD的经验熵H(D)H(D)之比:
    gg(D,a)=g(D,a)H(D)g_g(D, a_*) = \frac{g(D, a_*)}{H(D)}

    如前文所说,信息增益准则对可取值数目较多的属性有所偏好,为减少这种偏好可能带来的不利影响,著名的C4.5决策树算法不直接使用信息增益来选择划分属性,而是使用信息增益率来选择最优划分属性。

    C4.5算法
    输入:训练数据集DD,特征集AA,信息增益率阀值ϵ\epsilon,信息增益阈值α\alpha
    输出:决策树TT
    1.若DD中所有实例属于同一类CkC_k,则TT为单结点树,并将类CkC_k作为该结点的类标记,返回决策树TT
    2.若A=A = \varnothing,则TT为单结点树,并将DD中实例数最大的类CkC_k,作为该结点的类标记,返回决策树TT
    3.否则,计算AA中各特征对DD的信息增益和信息增益率,在信息增益大于α\alpha的特征中选择信息增益率最大的特征aa_*
    4.如果aa_*的信息增益率小于阀值ϵ\epsilon,则置TT为单结点树,并将DD中实例数最大的类CkC_k作为该结点的类标记,返回决策树TT
    5.否则,对aa_*的每一可能值ava_*^v,依a=ava_* = a_*^vDD分割为若干非空子集DvD_v,将DvD_v中实例数最大的类作为标记,构建子结点,由结点及其子结点构成决策树TT,返回决策树TT
    6.对第vv个子结点,以DvD_v为训练集,以A{a}A - \{a_*\}为特征集,递归地调用第(1)步~第(5)步,得到子树TvT_v,并返回子树TvT_v

    需注意的是,信息增益率准则对可取值数目较少的属性有所偏好,因此,C4.5算法并不是直接选择增益率最大的候选划分属性,而是使用了一个启发式的方法选择最优划分属性:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的.。

    连续值处理

    实际的任务中常会遇到连续属性,对于全部为连续属性的样本来说,我们一般使用回归决策树来处理。C4.5算法则采用了二分法对连续属性进行处理。由于连续属性的可取值数目不再有限,因此,不能直接根据连续属性的可取值来对结点进行划分。此时,连续属性离散化技术可派上用场。最简单的策略是采用二分法对连续属性进行处理。

    给定样本集DD和连续属性aa,假定aaDD上出现了nn个不同的取值,将这些值从小到大进行排序,记为{a1,a2,a3,&ThinSpace;,an}\{a_1, a_2, a_3, \cdots, a_n\}。基于划分点tt可将DD分为子集Dt+D_t^+DtD_t^-,其中Dt+D_t^+包含那些在属性aa上取值大于tt的样本,而DtD_t^-则包含那些在属性aa上取值不大于tt的样本。显然,对相邻的属性取值aia^iai+1a^{i + 1}来说,tt在区间[ai,ai+1)[a^i, a^{i + 1})中取任意值所产生的划分结果相同.因此,对连续属性aa,我们可考察包含n1n-1个元素的候选划分点集合:
    Ta={ai+ai+12  1in1}T_a = \{\frac{a^i + a^{i + 1}}{2} \ | \ 1 \leq i \leq n - 1\}

    即把区间[ai,ai+1)[a^i, a^{i + 1})的中位点ai+ai+12\frac{a^i + a^{i + 1}}{2}作为候选划分点。然后,我们就可像离散属性值一样来考察这些划分点,选取最优的划分点进行样本集合的划分:
    Gain(D,a)=maxtTaGain(D,a,t)=maxtTaEnt(D)λ{,+}DtλDEnt(Dtλ) \begin{aligned} Gain(D, a) &amp;= \max_{t \in T_a} Gain(D, a, t)\\ &amp; = \max_{t \in T_a} Ent(D) - \sum_{\lambda \in \{-, +\}} \frac{D^\lambda _t}{D}Ent(D^\lambda _t) \end{aligned}

    其中Gain(D,a,t)Gain(D, a, t)是样本集DD基于划分点tt二分后的信息增益。于是,我们就可选择使Gain(D,a,t)Gain(D, a, t)最大化的划分点。

    缺失值处理

    现实任务中常会遇到不完整样本,即样本的某些属性值缺失。且在属性数目较多的情况下,有时会有大量样本出现缺失值。如果简单地放弃不完整样本,仅使用无缺失值的样本来进行学习,显然是对数据信息极大的浪费。显然,有必要考虑利用有缺失属性值的训练样例来进行学习。

    划分属性的选择

    给定训练集DD和属性aa,令D~\tilde{D}表示DD中在属性aa上没有缺失值的样本子集。显然,我们仅可根据D~\tilde{D}来判断属性aa的优劣。假定属性aaVV个可取值{a1,a2,a3,&ThinSpace;,aV}\{a^1, a^2, a^3, \cdots, a^V\},令D~v\tilde{D}^v表示D~\tilde{D}中在属性aa上取值为ava^v的样本子集,D~k\tilde{D}_k表示D~\tilde{D}中属于第kk(k=1,2,3,&ThinSpace;,K)(k = 1, 2, 3, \cdots, K)的样本子集,则显然有D~=k=1KD~k\tilde{D} = \bigcup^K_{k = 1}\tilde{D}_kD~=v=1VD~v\tilde{D} = \bigcup^V_{v = 1}\tilde{D}^v。假定我们为每个样本xx赋予一个权重ωx\omega_x,并定义:
    ρ=xD~ωxxDωxp~k=xD~kωxxD~ωxr~v=xD~vωxxD~ωx \begin{aligned} \rho &amp; = \frac{\sum_{x \in \tilde{D}}\omega_x}{\sum_{x \in D}\omega_x}\\ \tilde{p}_k &amp; = \frac{\sum_{x \in \tilde{D}_k}\omega_x}{\sum_{x \in \tilde{D}}\omega_x}\\ \tilde{r}_v &amp; = \frac{\sum_{x \in \tilde{D}^v}\omega_x}{\sum_{x \in \tilde{D}}\omega_x} \end{aligned}

    直观地看,对于属性aaρ\rho表示无缺失值样本所占的比例,p~k\tilde{p}_k表示无缺失值样本中第kk类所占的比例,r~v\tilde{r}_v则表示无缺失值样本中在属性aa上取值ava^v的样本所占的比例。基于上述定义,我们可将信息增益的计算式推广为:
    Gain(D,a)=ρ×Gain(D~,a)=ρ×(Ent(D~)x=1Vr~vEnt((D~v)) \begin{aligned} Gain(D, a) &amp;= \rho \times Gain(\tilde{D}, a)\\ &amp; = \rho \times (Ent(\tilde{D}) - \sum_{x = 1}^V \tilde{r}_v Ent((\tilde{D}^v)) \end{aligned}

    对样本进行划分

    根据上面的定义,若样本xx在划分属性aa上的取值已知,则将xx划入与其取值对应的子结点,且样本权值在子结点中保持为ωx\omega_x。若样本xx在划分属性aa上的取值未知,则将xx同时划入所有子结点,且样本权值在与属性值ava^v对应的子结点中调整为r~v×ωx\tilde{r}_v \times \omega_x。直观地看,这就是让同一个样本以不同的概率划入到不同的子结点中去。

    基尼指数

    数据集DD的纯度还可用基尼值来度量:
    Gini(D)=k=1Kpk(1pk)=1k=1Kpk2Gini(D) = \sum^K_{k=1}p_k(1 - p_k) = 1 - \sum^K_{k=1}p_k^2

    其中,KK为类别数,pkp_k为样本点属于第kk类的概率。对于二类分类问题,若样本点属于第1个类的概率是pp,则概率分布的基尼指数为:
    Gini(D)=2p(1p)Gini(D) = 2p(1 - p)

    直观来说,Gini(D)Gini(D)反映了从数据集DD中随机抽取两个样本,其类别标记不一致的概率。因此,$Gini(D) 越小,则数据集D的纯度越高。对于属性a$的基尼指数定义为:
    Gini_index(D,a)=v=1VDvDGini(Dv)Gini\_index(D, a) = \sum^V_{v = 1}\frac{D^v}{D}Gini(D^v)

    CART算法中,我们在候选属性集合AA中,选择那个使得划分后基尼指数最小的属性作为最优划分属性,即:a=argminaAGini_index(D,a)a_* = \text{arg}\min_{a \in A}Gini\_index(D, a)

    在二类分类问题中,基尼指数Gini(D)Gini(D)、熵H(p)H(p)的一半,和分类误差率的关系:
    特征选择方法对比
    其中,横坐标表示概率pp,纵坐标表示损失。可以看出基尼指数和熵的一半的曲线很接近,都可以近似地代表分类误差率。

    分类树的剪枝

    剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段。在决策树学习中,为了尽可能正确分类训练样本,结点划分过程将不断重复,有时会造成决策树分支过多,这时就可能因为对训练样本学习得“太好”了,以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此,可通过主动去掉一些分支来降低过拟合的风险。决策树剪枝的基本策略有预剪枝后剪枝

    预剪枝

    预剪枝是指在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点。停止决策树生长常用方法:

    1. 定义一个高度,当决策树达到该高度时就停止决策树的生长
    2. 达到某个节点的实例具有相同的特征向量,即使这些实例不属于同一类,也可以停止决策树的生长。这个方法对于处理数据的数据冲突问题比较有效。
    3. 定义一个阈值,当达到某个节点的实例个数小于阈值时就可以停止决策树的生长
    4. 定义一个阈值,通过计算每次扩张对系统性能的增益,并比较增益值与该阈值大小来决定是否停止决策树的生长。

    后剪枝

    后剪枝则是先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升,则将该子树替换为叶结点。相比于预剪枝,后剪枝更常用,因为在预剪枝中精确地估计何时停止树增长很困难。

    错误率降低剪枝(REP,Reduced-Error Pruning)

    错误率降低剪枝方法是一种比较简单的后剪枝的方法。在该方法中,可用的数据被分成两个样例集合:首先是训练集,它被用来形成学习到的决策树,另一个是与训练集分离的验证集,它被用来评估这个决策树在后续数据上的精度,确切地说是用来评估修剪这个决策树的影响。学习器可能会被训练集中的随机错误和巧合规律所误导,但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。

    错误率降低剪枝方法考将树上的每个节点作为修剪的候选对象,再决定是对该节点进行剪枝:

    1. 删除以此结点为根的子树
    2. 使其成为叶子结点
    3. 当修剪后的树对于验证集合的性能不比修剪前的树的性能差时,则确认删除该结点,否则恢复该节点

    因为训练集合的过拟合,使得验证集合数据能够对其进行修正,反复进行上面的操作,从底向上的处理结点,删除那些能够提高验证集合的精度的结点,直到进一步修剪会降低验证集合的精度为止。

    错误率降低剪枝方法是最简单的后剪枝方法之一,不过由于使用独立的测试集,原始决策树相比,修改后的决策树可能偏向于过度修剪。这是因为一些不会再次在测试集中出现的很稀少的训练集实例所对应的分枝在剪枝过程中往往会被剪枝。尽管错误率降低剪枝方法有这个缺点,不过错误率降低剪枝方法仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了一个很好的学习思路。由于验证集合没有参与决策树的构建,所以用错误率降低剪枝方法剪枝后的决策树对于测试样例的偏差要好很多,能够解决一定程度的过拟合问题。

    悲观错误剪枝(PEP,Pesimistic-Error Pruning)

    悲观错误剪枝方法是根据剪枝前后的错误率来判定子树的修剪。它不需要像错误率降低修剪方法那样,需要使用部分样本作为测试数据,而是完全使用训练数据来生成决策树,并进行剪枝,即决策树生成和剪枝都使用训练集

    该方法引入了统计学中连续修正的概念弥补错误率降低剪枝方法中的缺陷,在评价子树的训练错误公式中添加了一个常数,即假定每个叶子结点都自动对实例的某个部分进行错误的分类。

    把一颗具有多个叶子节点的子树的分类用一个叶子节点来替代的话,在训练集上的误判率肯定是上升的,但是在新数据上不一定。于是我们把子树的误判计算加上一个经验性的惩罚因子来做是否剪枝的考量指标。对于一个叶子节点,它覆盖了NN个样本,其中有EE个错误,那么该叶子节点的错误率为E+0.5N\frac{E + 0.5}{N}。这个0.50.5就是惩罚因子,那么一颗子树,它有LL个叶子节点,那么该子树的误判率估计为:
    Ei+0.5LNi\frac{\sum E_i +0.5 * L}{\sum N_i}

    这样的话,我们可以看到一棵子树虽然具有多个子节点,但由于加上了惩罚因子,所以子树的误判率计算未必占到便宜。剪枝后内部节点变成了叶子节点,其误判个数EE也需要加上一个惩罚因子,变成E+0.5E+0.5,那么子树是否可以被剪枝就取决于剪枝后的错误E+0.5E+0.5在的标准误差内。对于样本的误差率ee,我们可以根据经验把它估计成各种各样的分布模型,比如二项式分布、正态分布等。如果E+0.5&lt;Ei+SE(Ei)E+0.5 &lt; E_i + SE(E_i)则对ii进行剪枝。

    代价复杂度剪枝(CCP,Cost-Complexity Pruning)

    代价复杂度剪枝算法为子树TtT_t定义了代价和复杂度,以及一个可由用户设置的衡量代价与复杂度之间关系的参数αα。其中,代价指在剪枝过程中因子树TtT_t被叶节点替代而增加的错分样本,复杂度表示剪枝后子树TtT_t减少的叶结点数,αα则表示剪枝后树的复杂度降低程度与代价间的关系,定义为:
    α=R(t)R(Tt)N11\alpha = \frac{R(t) - R(T_t)}{|N_1| - 1}

    其中,N1|N_1|是子树TtT_t中的叶节点数,R(t)=r(t)p(t)R(t) = r(t) * p(t)为结点tt的错误代价,r(t)r(t)为结点tt的错分样本率,p(t)p(t)为落入结点tt的样本占所有样本的比例,R(Tt)=R(i)R(T_t) = \sum R(i)是子树TtT_t错误代价,ii为子树TtT_t的叶节点。

    1. 对于完全决策树TT的每个非叶结点计算αα值,循环剪掉具有最小αα值的子树,直到剩下根节点,得到一系列的剪枝树{T0,T1,T2,&ThinSpace;,Tm}\{ T_0, T_`1, T_2, \cdots, T_m \},其中T0T_0为原有的完全决策树,TmT_m为根结点,Ti+1T_{i +1}为对TiT_i进行剪枝的结果
    2. 从子树序列中,根据真实的误差估计选择最佳决策树
    REP PEP CCP
    剪枝方式 自底向上 自顶向下 自底向上
    计算复杂度 O(n)O(n) O(n)O(n) O(n2)O(n^2)
    误差估计 测试集上误差估计 使用连续纠正 标准误差

    回归树

    建立回归树的过程大致可以分为两步:

    1. 将预测变量空间(X1,X2,X3,&ThinSpace;,XpX_1, X_2, X_3, \cdots, X_p)的可能取值构成的集合分割成JJ个互不重叠的区域{R1,R2,R3,&ThinSpace;,RJ}\{ R_1, R_2, R_3, \cdots, R_J\}
    2. 对落入区域RjR_j的每个观测值作同样的预测,预测值等于RjR_j上训练集的各个样本取值的算术平均数。

    比如,在第一步中得到两个区域R1R_1R2R_2R1R_1中训练集的各个样本取值的算术平均数为10,R2R_2中训练集的各个样本取值的算术平均数为20。则对给定的观测值X=xX = x,若xR1x \in R_1,给出的预测值为10,若xR2x \in R_2,则预测值为20。

    所以,类似于上述决策树分类算法的第(10)步,关键在于如何构建区域划分{R1,R2,R3,&ThinSpace;,RJ}\{ R_1, R_2, R_3, \cdots, R_J\}。事实上,区域的形状是可以为任意形状的,但出于模型简化和增强可解释性的考虑,这里将预测变量空间划分成高维矩形,我们称这些区域为称盒子。划分区域的目标是找到使模型的残差平方和RSSRSS最小的矩形区域{R1,R2,R3,&ThinSpace;,RJ}\{ R_1, R_2, R_3, \cdots, R_J\}RSSRSS的定义为:
    RSS=j=1JiRj(yiy^Rj)2RSS = \sum^J_{j=1} \sum_{i \in R_j}(y_i - \hat{y}_{R_j})^2

    其中,y^Rj\hat{y}_{R_j}是第jj个矩形区域中训练集中各个样本取值的算术平均数。但是,要想考虑将特征空间划分为JJ个矩形区域的所有可能性,在计算上是不可行的。因此一般采用一种自上而下的贪婪法:递归二又分裂。“自上而下”指的是它从树顶端开始依次分裂预测变量空间,每个分裂点都产生两个新的分支。“贪婪”意指在建立树的每一步中,最优分裂确定仅限于某一步进程,而不是针对全局去选择那些能够在未来进程中构建出更好的树的分裂点。

    在执行递归二又分裂时,先选择预测变量XjX_j和分割点ss,将预测变量空间分为两个区域{XXj&lt;s}\{ X|X_j &lt;s \}{XXjs}\{ X|X_j \geq s \},使RSSRSS尽可能地减小。也就是说,考虑所有预测变量X1,X2,X3,&ThinSpace;,XpX_1, X_2, X_3, \cdots, X_p和与每个预测变量对应的ss的取值,然后选择预测变量和分割点,使构造出的树具有最小的RSSRSS。更详细地,对jjss,定义一对半平面:
    R1(j,s)={XXj&lt;s}R2(j,s)={XXjs}R_1(j, s) = \{ X|X_j &lt;s \} \quad \text{和} \quad R_2(j, s) = \{ X|X_j \geq s \}

    寻找jjss,使得下式最小:
    xiR1(j,s)(yiy^R1)2+xiR2(j,s)(yiy^R2)2\sum_{x_i \in R_1(j, s)}(y_i - \hat{y}_{R_1})^2 + \sum_{x_i \in R_2(j, s)}(y_i - \hat{y}_{R_2})^2

    重复上述步骤,寻找继续分割数据集的最优预测变量和最优分割点,使随之产生的区域中的RSSRSS达到最小。此时被分割的不再是整个预测变量空间,而是之前确定的两个区域之一。如此一来就能得到3个区域。接着进一步分割3个区域之一以最小化RSSRSS。这一过程不断持续,直到符合某个停止准则,如我们在分类决策树中讨论到的前剪枝中的停止准则。

    区域{R1,R2,R3,&ThinSpace;,RJ}\{ R_1, R_2, R_3, \cdots, R_J\}产生后,就可以确定某一给定的测试数据所属的区域,并用这一区域训练集的各个样本取值的算术平均数作为与测试进行预测。

    f回归树实例

    回归树的剪枝

    上述方法生成的回归树会在训练集中取得良好的预测效果,却很有可能造成数据的过拟合,导致在测试集上效果不佳。原因在于这种方法产生的树可能过于复杂。一棵分裂点更少、规模更小(区域{R1,R2,R3,&ThinSpace;,RJ}\{ R_1, R_2, R_3, \cdots, R_J\}的个数更少)的树会有更小的方差和更好的可解释性(以增加微小偏差为代价)。针对上述问题,一种可能的解决办法是:仅当分裂使残差平方和RSSRSS的减小量超过某阀值时,才分裂树结点。这种策略能生成较小的树,但可能产生过于短视的问题,一些起初看来不值得的分裂却可能之后产生非常好的分裂。也就是说在下一步中,RSSRSS会大幅减小。

    因此,更好的策略是生成一棵很大的树T0T_0,然后通过后剪枝得到子树。直观上看,剪枝的目的是选出使测试集预测误差最小的子树。子树的测试误差可以通过交叉验证或验证集来估计。但由于可能的子树数量极其庞大,对每一棵子树都用交叉验证来估计误差太过复杂。因此需要从所有可能的子树中选出一小部分再进行考虑。在回归树中,我们一般使用代价复杂度剪枝(CCP,Cost-Complexity Pruning),也称最弱联系剪枝(Weakest Link Pruning)。这种方法不是考虑每一棵可能的子树,而是考虑以非负调整参数α\alpha标记的一系列子树。每一个α\alpha的取值对应一棵子树TT0T \in T_0,当α\alpha一定时,其对应的子树使下式最小:
    m=1TxiRm(yiy^Rm)2+αT\sum_{m=1}^{|T|} \sum_{x_i \in R_m}(y_i - \hat{y}_{R_m})^2 + \alpha |T|

    这里的T|T|表示树TT的结点数,RmR_m是第mm个终端结点对应的矩形(预测向量空间的一个子集),y^Rm\hat{y}_{R_m}是与RmR_m对应的预测值,也就是RmR_m中训练集的平均值。调整系数α\alpha在子树的复杂性和与训练数据的契合度之间控制权衡。当α=0\alpha = 0时,子树TT等于原树T0T_0,因为此时上式只衡量了训练误差。而当α\alpha增大时,终端结点数多的树将为它的复杂付出代价,所以使上式取到最小值的子树会变得更小。

    α\alpha从0开始逐渐增加时,树枝以一种嵌套的、可预测的模式被修剪,因此获得与α\alpha对应的所有子树序列是很容易的。可以用交又验证或验证集确定α\alpha,然后在整个数据集中找到与之对应的子树:

    回归决策树算法
    1.利用递归二叉分裂在训练集中生成一额大树,只有当终端结点包含的观测值个数低于某个最小值时才停止。
    2.对大树进行代价复杂性剪枝,得到一系列最优子树,子树是α\alpha的函数。
    3.利用KK折交叉验诞选择α\alpha。具体做法是将训练集分为KK折。对所有k=1,2,3,&ThinSpace;,Kk=1, 2, 3, \cdots, K,对训练集上所有不属于第kk折的数据重复第(1)步~第(2)步得到与α\alpha对应的子树,并求出上述子树在第kk折上的均方预测误差。
    4.每个α\alpha会有相应的KK个均方预测误差,对这KK个值求平均,选出使平均误差最小的α\alpha
    5.找出选定的α\alpha在第(2)步中对应的子树。

    决策树的基础即是上文所述的分类决策树与回归决策树,其预测准确性一般比回归和分类方法弱,但可以通过用集成学习方法组合大量决策树,显著提升树的预测效果,这些方法我将会在接下来的文章中继续阐述,欢迎关注学习讨论!

    展开全文
  • 机器学习实战(三)——决策树

    万次阅读 多人点赞 2018-11-03 11:59:49
    决策树 3.1 决策树的构造 3.1.1 信息增益 3.1.2 编写代码计算经验熵 3.1.4利用代码计算信息增益 3.2 决策树的生成和修剪 3.2.1 决策树的构建 1. ID3算法 2. C4.5的生成算法 3. 决策树的剪枝 3.2.2 ...

    决策树

    (声明:本文内容来自机器学习实战和统计学习方法,是两者的整合,并非来自单个书籍)

    决策树(decision tree):是一种基本的分类与回归方法,此处主要讨论分类的决策树。

    在分类问题中,表示基于特征对实例进行分类的过程,可以认为是if-then的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。

    决策树通常有三个步骤:特征选择、决策树的生成、决策树的修剪。

    用决策树分类:从根节点开始,对实例的某一特征进行测试,根据测试结果将实例分配到其子节点,此时每个子节点对应着该特征的一个取值,如此递归的对实例进行测试并分配,直到到达叶节点,最后将实例分到叶节点的类中。

    下图为决策树示意图,圆点——内部节点,方框——叶节点

    这里写图片描述

    • 决策树学习的目标:根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。

    • 决策树学习的本质:从训练集中归纳出一组分类规则,或者说是由训练数据集估计条件概率模型。

    • 决策树学习的损失函数:正则化的极大似然函数

    • 决策树学习的测试:最小化损失函数

    • 决策树学习的目标:在损失函数的意义下,选择最优决策树的问题。

    • 决策树原理和问答猜测结果游戏相似,根据一系列数据,然后给出游戏的答案。
      在这里插入图片描述

    上图为一个决策树流程图,正方形代表判断模块,椭圆代表终止模块,表示已经得出结论,可以终止运行,左右箭头叫做分支。

    上节介绍的k-近邻算法可以完成很多分类任务,但是其最大的缺点是无法给出数据的内在含义,决策树的优势在于数据形式非常容易理解。

    3.1 决策树的构造

    决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。

    1) 开始:构建根节点,将所有训练数据都放在根节点,选择一个最优特征,按着这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。

    2) 如果这些子集已经能够被基本正确分类,那么构建叶节点,并将这些子集分到所对应的叶节点去。

    3)如果还有子集不能够被正确的分类,那么就对这些子集选择新的最优特征,继续对其进行分割,构建相应的节点,如果递归进行,直至所有训练数据子集被基本正确的分类,或者没有合适的特征为止。

    4)每个子集都被分到叶节点上,即都有了明确的类,这样就生成了一颗决策树。

    决策树的特点:

    • 优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。
    • 缺点:可能会产生过度匹配的问题
    • 适用数据类型:数值型和标称型

    首先:确定当前数据集上的决定性特征,为了得到该决定性特征,必须评估每个特征,完成测试之后,原始数据集就被划分为几个数据子集,这些数据子集会分布在第一个决策点的所有分支上,如果某个分支下的数据属于同一类型,则当前无序阅读的垃圾邮件已经正确的划分数据分类,无需进一步对数据集进行分割,如果不属于同一类,则要重复划分数据子集,直到所有相同类型的数据均在一个数据子集内。

    创建分支的伪代码createBranch()如下图所示:

    检测数据集中每个子项是否属于同一类:

    If so return 类标签:
    Else
         寻找划分数据集的最好特征
         划分数据集
         创建分支节点
             for 每个划分的子集
                 调用函数createBranch()并增加返回结果到分支节点中
             return 分支节点
    

    使用决策树做预测需要以下过程:

    • 收集数据:可以使用任何方法。比如想构建一个相亲系统,我们可以从媒婆那里,或者通过参访相亲对象获取数据。根据他们考虑的因素和最终的选择结果,就可以得到一些供我们利用的数据了。
    • 准备数据:收集完的数据,我们要进行整理,将这些所有收集的信息按照一定规则整理出来,并排版,方便我们进行后续处理。
    • 分析数据:可以使用任何方法,决策树构造完成之后,我们可以检查决策树图形是否符合预期。
    • 训练算法:这个过程也就是构造决策树,同样也可以说是决策树学习,就是构造一个决策树的数据结构。
    • 测试算法:使用经验树计算错误率。当错误率达到了可接收范围,这个决策树就可以投放使用了。
    • 使用算法:此步骤可以使用适用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义。

    本节使用ID3算法来划分数据集,该算法处理如何划分数据集,何时停止划分数据集。

    3.1.1 信息增益

    划分数据集的大原则是:将无序数据变得更加有序,但是各种方法都有各自的优缺点,信息论是量化处理信息的分支科学,在划分数据集前后信息发生的变化称为信息增益,获得信息增益最高的特征就是最好的选择,所以必须先学习如何计算信息增益,集合信息的度量方式称为香农熵,或者简称熵。

    希望通过所给的训练数据学习一个贷款申请的决策树,用以对未来的贷款申请进行分类,即当新的客户提出贷款申请时,根据申请人的特征利用决策树决定是否批准贷款申请。

    特征选择就是决定用哪个特征来划分特征空间。比如,我们通过上述数据表得到两个可能的决策树,分别由两个不同特征的根结点构成。

    这里写图片描述
    图(a)所示的根结点的特征是年龄,有3个取值,对应于不同的取值有不同的子结点。图(b)所示的根节点的特征是工作,有2个取值,对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。问题是:究竟选择哪个特征更好些?这就要求确定选择特征的准则。直观上,如果一个特征具有更好的分类能力,或者说,按照这一特征将训练数据集分割成子集,使得各个子集在当前条件下有最好的分类,那么就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。

    什么是信息增益呢?在划分数据集之前之后信息发生的变化成为信息增益,知道如何计算信息增益,我们就可以计算每个特征值划分数据集获得的信息增益,获得信息增益最高的特征就是最好的选择。

    熵定义为信息的期望值,如果待分类的事物可能划分在多个类之中,则符号xix_i的信息定义为:
    l(xi)=log2p(xi)l(x_i)=-log_2 p(x_i)
    其中,p(xi)p(x_i)是选择该分类的概率。

    为了计算熵,我们需要计算所有类别所有可能值所包含的信息期望值,通过下式得到:
    H=Σi=1np(xi)log2p(xi)H=-\Sigma_{i=1}^n p(x_i)log_2 p(x_i)
    其中,nn为分类数目,熵越大,随机变量的不确定性就越大。

    当熵中的概率由数据估计(特别是最大似然估计)得到时,所对应的熵称为经验熵(empirical entropy)。什么叫由数据估计?比如有10个数据,一共有两个类别,A类和B类。其中有7个数据属于A类,则该A类的概率即为十分之七。其中有3个数据属于B类,则该B类的概率即为十分之三。浅显的解释就是,这概率是我们根据数据数出来的。我们定义贷款申请样本数据表中的数据为训练数据集D,则训练数据集D的经验熵为H(D),|D|表示其样本容量,及样本个数。设有K个类Ck,k = 1,2,3,···,K,|Ck|为属于类Ck的样本个数,这经验熵公式可以写为:
    H(D)=ΣckDlog2ckDH(D)=-\Sigma \frac{|c_k|}{|D|}log_2\frac{|c_k|}{|D|}

    根据此公式计算经验熵H(D),分析贷款申请样本数据表中的数据。最终分类结果只有两类,即放贷和不放贷。根据表中的数据统计可知,在15个数据中,9个数据的结果为放贷,6个数据的结果为不放贷。所以数据集D的经验熵H(D)为:
    H(D)=915log2915615log2615=0.971H(D)=-\frac{9}{15} log_2\frac{9}{15}-\frac{6}{15} log_2\frac{6}{15}=0.971
    经过计算可知,数据集D的经验熵H(D)的值为0.971。

    在理解信息增益之前,要明确——条件熵

    信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。

    条件熵H(YX)H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性,随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X),定义X给定条件下Y的条件概率分布的熵对X的数学期望:
    H(YX)=i=1npiH(YX=xi)H(Y|X)=\sum_{i=1}^n p_iH(Y|X=x_i)
    其中,pi=P(X=xi)p_i=P(X=x_i)

    当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的分别为经验熵和经验条件熵,此时如果有0概率,令0log0=00log0=0

    信息增益:信息增益是相对于特征而言的。所以,特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即:

    g(D,A)=H(D)H(DA)g(D,A)=H(D)-H(D|A)

    一般地,熵H(D)与条件熵H(D|A)之差成为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

    信息增益值的大小相对于训练数据集而言的,并没有绝对意义,在分类问题困难时,也就是说在训练数据集经验熵大的时候,信息增益值会偏大,反之信息增益值会偏小,使用信息增益比可以对这个问题进行校正,这是特征选择的另一个标准。

    信息增益比:特征AA对训练数据集D的信息增益比gR(D,A)g_R(D,A)定义为其信息增益g(D,A)g(D,A)与训练数据集DD的经验熵之比:

    gR(D,A)=g(D,A)H(D)g_R(D,A)=\frac{g(D,A)}{H(D)}

    3.1.2 编写代码计算经验熵

    在这里插入图片描述
    在编写代码之前,我们先对数据集进行属性标注。

    • 年龄:0代表青年,1代表中年,2代表老年;
    • 有工作:0代表否,1代表是;
    • 有自己的房子:0代表否,1代表是;
    • 信贷情况:0代表一般,1代表好,2代表非常好;
    • 类别(是否给贷款):no代表否,yes代表是。

    创建数据集,计算经验熵的代码如下:

    from math import log
    
    """
    函数说明:创建测试数据集
    Parameters:无
    Returns:
        dataSet:数据集
        labels:分类属性
    Modify:
        2018-03-12
    
    """
    def creatDataSet():
        # 数据集
        dataSet=[[0, 0, 0, 0, 'no'],
                [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
    
    """
    函数说明:计算给定数据集的经验熵(香农熵)
    Parameters:
        dataSet:数据集
    Returns:
        shannonEnt:经验熵
    Modify:
        2018-03-12
    
    """
    def calcShannonEnt(dataSet):
        #返回数据集行数
        numEntries=len(dataSet)
        #保存每个标签(label)出现次数的字典
        labelCounts={}
        #对每组特征向量进行统计
        for featVec in dataSet:
            currentLabel=featVec[-1]                     #提取标签信息
            if currentLabel not in labelCounts.keys():   #如果标签没有放入统计次数的字典,添加进去
                labelCounts[currentLabel]=0
            labelCounts[currentLabel]+=1                 #label计数
    
        shannonEnt=0.0                                   #经验熵
        #计算经验熵
        for key in labelCounts:
            prob=float(labelCounts[key])/numEntries      #选择该标签的概率
            shannonEnt-=prob*log(prob,2)                 #利用公式计算
        return shannonEnt                                #返回经验熵
    
    #main函数
    if __name__=='__main__':
        dataSet,features=creatDataSet()
        print(dataSet)
        print(calcShannonEnt(dataSet))
    

    结果:

    0个特征的增益为0.0831个特征的增益为0.3242个特征的增益为0.4203个特征的增益为0.3630个特征的增益为0.2521个特征的增益为0.9182个特征的增益为0.474
    {'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
    
    

    3.1.4利用代码计算信息增益

    
    from math import log
    
    """
    函数说明:创建测试数据集
    Parameters:无
    Returns:
        dataSet:数据集
        labels:分类属性
    Modify:
        2018-03-12
    
    """
    def creatDataSet():
        # 数据集
        dataSet=[[0, 0, 0, 0, 'no'],
                [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
    
    
    """
    函数说明:计算给定数据集的经验熵(香农熵)
    Parameters:
        dataSet:数据集
    Returns:
        shannonEnt:经验熵
    Modify:
        2018-03-12
    
    """
    def calcShannonEnt(dataSet):
        #返回数据集行数
        numEntries=len(dataSet)
        #保存每个标签(label)出现次数的字典
        labelCounts={}
        #对每组特征向量进行统计
        for featVec in dataSet:
            currentLabel=featVec[-1]                     #提取标签信息
            if currentLabel not in labelCounts.keys():   #如果标签没有放入统计次数的字典,添加进去
                labelCounts[currentLabel]=0
            labelCounts[currentLabel]+=1                 #label计数
    
        shannonEnt=0.0                                   #经验熵
        #计算经验熵
        for key in labelCounts:
            prob=float(labelCounts[key])/numEntries      #选择该标签的概率
            shannonEnt-=prob*log(prob,2)                 #利用公式计算
        return shannonEnt                                #返回经验熵
    
    
    """
    函数说明:计算给定数据集的经验熵(香农熵)
    Parameters:
        dataSet:数据集
    Returns:
        shannonEnt:信息增益最大特征的索引值
    Modify:
        2018-03-12
    
    """
    
    
    def chooseBestFeatureToSplit(dataSet):
        #特征数量
        numFeatures = len(dataSet[0]) - 1
        #计数数据集的香农熵
        baseEntropy = calcShannonEnt(dataSet)
        #信息增益
        bestInfoGain = 0.0
        #最优特征的索引值
        bestFeature = -1
        #遍历所有特征
        for i in range(numFeatures):
            # 获取dataSet的第i个所有特征
            featList = [example[i] for example in dataSet]
            #创建set集合{},元素不可重复
            uniqueVals = set(featList)
            #经验条件熵
            newEntropy = 0.0
            #计算信息增益
            for value in uniqueVals:
                #subDataSet划分后的子集
                subDataSet = splitDataSet(dataSet, i, value)
                #计算子集的概率
                prob = len(subDataSet) / float(len(dataSet))
                #根据公式计算经验条件熵
                newEntropy += prob * calcShannonEnt((subDataSet))
            #信息增益
            infoGain = baseEntropy - newEntropy
            #打印每个特征的信息增益
            print("第%d个特征的增益为%.3f" % (i, infoGain))
            #计算信息增益
            if (infoGain > bestInfoGain):
                #更新信息增益,找到最大的信息增益
                bestInfoGain = infoGain
                #记录信息增益最大的特征的索引值
                bestFeature = i
                #返回信息增益最大特征的索引值
        return bestFeature
    
    """
    函数说明:按照给定特征划分数据集
    Parameters:
        dataSet:待划分的数据集
        axis:划分数据集的特征
        value:需要返回的特征的值
    Returns:
        shannonEnt:经验熵
    Modify:
        2018-03-12
    
    """
    def splitDataSet(dataSet,axis,value):
        retDataSet=[]
        for featVec in dataSet:
            if featVec[axis]==value:
                reducedFeatVec=featVec[:axis]
                reducedFeatVec.extend(featVec[axis+1:])
                retDataSet.append(reducedFeatVec)
        return retDataSet
    
    
    #main函数
    if __name__=='__main__':
        dataSet,features=creatDataSet()
        # print(dataSet)
        # print(calcShannonEnt(dataSet))
        print("最优索引值:"+str(chooseBestFeatureToSplit(dataSet)))
    
    

    结果:

    0个特征的增益为0.0831个特征的增益为0.3242个特征的增益为0.4203个特征的增益为0.363
    最优索引值:2
    
    

    对比我们自己计算的结果,发现结果完全正确!最优特征的索引值为2,也就是特征A3(有自己的房子)。

    3.2 决策树的生成和修剪

    我们已经学习了从数据集构造决策树算法所需要的子功能模块,包括经验熵的计算和最优特征的选择,其工作原理如下:得到原始数据集,然后基于最好的属性值划分数据集,由于特征值可能多于两个,因此可能存在大于两个分支的数据集划分。第一次划分之后,数据集被向下传递到树的分支的下一个结点。在这个结点上,我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。

    构建决策树的算法有很多,比如C4.5、ID3和CART,这些算法在运行时并不总是在每次划分数据分组时都会消耗特征。由于特征数目并不是每次划分数据分组时都减少,因此这些算法在实际使用时可能引起一定的问题。目前我们并不需要考虑这个问题,只需要在算法开始运行前计算列的数目,查看算法是否使用了所有属性即可。

    决策树生成算法递归地产生决策树,直到不能继续下去未为止。这样产生的树往往对训练数据的分类很准确,但对未知的测试数据的分类却没有那么准确,即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度,对已生成的决策树进行简化。

    3.2.1 决策树的构建

    1. ID3算法

    ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征,递归地构建决策树。

    具体方法是:

    1)从根结点(root node)开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征。

    2)由该特征的不同取值建立子节点,再对子结点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止;

    3)最后得到一个决策树。

    ID3相当于用极大似然法进行概率模型的选择

    算法步骤:

    这里写图片描述
    这里写图片描述

    分析数据:

    上面已经求得,特征A3(有自己的房子)的信息增益最大,所以选择A3为根节点的特征,它将训练集D划分为两个子集D1(A3取值为“是”)D2(A3取值为“否”)。由于D1只有同一类的样本点,所以它成为一个叶结点,结点的类标记为“是”。

    对D2则需要从特征A1(年龄),A2(有工作)和A4(信贷情况)中选择新的特征,计算各个特征的信息增益:

    g(D2,A1)=H(D2)H(D2A1)=0.251g(D2,A1)=H(D2)-H(D2|A1)=0.251
    g(D2,A2)=H(D2)H(D2A2)=0.918g(D2,A2)=H(D2)-H(D2|A2)=0.918
    g(D2,A3)=H(D2)H(D2A3)=0.474g(D2,A3)=H(D2)-H(D2|A3)=0.474

    根据计算,选择信息增益最大的A2作为节点的特征,由于其有两个取值可能,所以引出两个子节点:

    ①对应“是”(有工作),包含三个样本,属于同一类,所以是一个叶子节点,类标记为“是”

    ②对应“否”(无工作),包含六个样本,输入同一类,所以是一个叶子节点,类标记为“否”

    这样就生成一个决策树,该树只用了两个特征(有两个内部节点),生成的决策树如下图所示:

    在这里插入图片描述

    2. C4.5的生成算法

    与ID3算法相似,但是做了改进,将信息增益比作为选择特征的标准。

    这里写图片描述

    递归构建决策树:

    从数据集构造决策树算法所需的子功能模块工作原理如下:得到原始数据集,然后基于最好的属性值划分数据集,由于特征值可能多于两个,因此可能存在大于两个分支的数据集划分,第一次划分之后,数据将被向下传递到树分支的下一个节点,在此节点在此划分数据,因此可以使用递归的原则处理数据集。

    递归结束的条件是:

    程序完全遍历所有划分数据集的属性,或者每个分支下的所有实例都具有相同的分类,如果所有实例具有相同的分类,则得到一个叶子节点或者终止块,任何到达叶子节点的数据必然属于叶子节点的分类。

    编写ID3算法的代码

    from math import log
    import operator
    
    """
    函数说明:计算给定数据集的经验熵(香农熵)
    Parameters:
        dataSet:数据集
    Returns:
        shannonEnt:经验熵
    Modify:
        2018-03-12
    
    """
    def calcShannonEnt(dataSet):
        #返回数据集行数
        numEntries=len(dataSet)
        #保存每个标签(label)出现次数的字典
        labelCounts={}
        #对每组特征向量进行统计
        for featVec in dataSet:
            currentLabel=featVec[-1]                     #提取标签信息
            if currentLabel not in labelCounts.keys():   #如果标签没有放入统计次数的字典,添加进去
                labelCounts[currentLabel]=0
            labelCounts[currentLabel]+=1                 #label计数
    
        shannonEnt=0.0                                   #经验熵
        #计算经验熵
        for key in labelCounts:
            prob=float(labelCounts[key])/numEntries      #选择该标签的概率
            shannonEnt-=prob*log(prob,2)                 #利用公式计算
        return shannonEnt                                #返回经验熵
    
    """
    函数说明:创建测试数据集
    Parameters:无
    Returns:
        dataSet:数据集
        labels:分类属性
    Modify:
        2018-03-13
    
    """
    def createDataSet():
        # 数据集
        dataSet=[[0, 0, 0, 0, 'no'],
                [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
    
    """
    函数说明:按照给定特征划分数据集
    
    Parameters:
        dataSet:待划分的数据集
        axis:划分数据集的特征
        value:需要返回的特征值
    Returns:
        无
    Modify:
        2018-03-13
    
    """
    def splitDataSet(dataSet,axis,value):
        #创建返回的数据集列表
        retDataSet=[]
        #遍历数据集
        for featVec in dataSet:
            if featVec[axis]==value:
                #去掉axis特征
                reduceFeatVec=featVec[:axis]
                #将符合条件的添加到返回的数据集
                reduceFeatVec.extend(featVec[axis+1:])
                retDataSet.append(reduceFeatVec)
        #返回划分后的数据集
        return retDataSet
    
    """
    函数说明:计算给定数据集的经验熵(香农熵)
    Parameters:
        dataSet:数据集
    Returns:
        shannonEnt:信息增益最大特征的索引值
    Modify:
        2018-03-13
    
    """
    
    
    def chooseBestFeatureToSplit(dataSet):
        #特征数量
        numFeatures = len(dataSet[0]) - 1
        #计数数据集的香农熵
        baseEntropy = calcShannonEnt(dataSet)
        #信息增益
        bestInfoGain = 0.0
        #最优特征的索引值
        bestFeature = -1
        #遍历所有特征
        for i in range(numFeatures):
            # 获取dataSet的第i个所有特征
            featList = [example[i] for example in dataSet]
            #创建set集合{},元素不可重复
            uniqueVals = set(featList)
            #经验条件熵
            newEntropy = 0.0
            #计算信息增益
            for value in uniqueVals:
                #subDataSet划分后的子集
                subDataSet = splitDataSet(dataSet, i, value)
                #计算子集的概率
                prob = len(subDataSet) / float(len(dataSet))
                #根据公式计算经验条件熵
                newEntropy += prob * calcShannonEnt((subDataSet))
            #信息增益
            infoGain = baseEntropy - newEntropy
            #打印每个特征的信息增益
            print("第%d个特征的增益为%.3f" % (i, infoGain))
            #计算信息增益
            if (infoGain > bestInfoGain):
                #更新信息增益,找到最大的信息增益
                bestInfoGain = infoGain
                #记录信息增益最大的特征的索引值
                bestFeature = i
                #返回信息增益最大特征的索引值
        return bestFeature
    
    """
    函数说明:统计classList中出现次数最多的元素(类标签)
    Parameters:
        classList:类标签列表
    Returns:
        sortedClassCount[0][0]:出现次数最多的元素(类标签)
    Modify:
        2018-03-13
    
    """
    def majorityCnt(classList):
        classCount={}
        #统计classList中每个元素出现的次数
        for vote in classList:
            if vote not in classCount.keys():
                classCount[vote]=0
                classCount[vote]+=1
            #根据字典的值降序排列
            sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
            return sortedClassCount[0][0]
    
    """
    函数说明:创建决策树
    
    Parameters:
        dataSet:训练数据集
        labels:分类属性标签
        featLabels:存储选择的最优特征标签
    Returns:
        myTree:决策树
    Modify:
        2018-03-13
    
    """
    def createTree(dataSet,labels,featLabels):
        #取分类标签(是否放贷:yes or no)
        classList=[example[-1] for example in dataSet]
        #如果类别完全相同,则停止继续划分
        if classList.count(classList[0])==len(classList):
            return classList[0]
        #遍历完所有特征时返回出现次数最多的类标签
        if len(dataSet[0])==1:
            return majorityCnt(classList)
        #选择最优特征
        bestFeat=chooseBestFeatureToSplit(dataSet)
        #最优特征的标签
        bestFeatLabel=labels[bestFeat]
        featLabels.append(bestFeatLabel)
        #根据最优特征的标签生成树
        myTree={bestFeatLabel:{}}
        #删除已经使用的特征标签
        del(labels[bestFeat])
        #得到训练集中所有最优特征的属性值
        featValues=[example[bestFeat] for example in dataSet]
        #去掉重复的属性值
        uniqueVls=set(featValues)
        #遍历特征,创建决策树
        for value in uniqueVls:
            myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),
                                                   labels,featLabels)
        return myTree
    
    if __name__=='__main__':
        dataSet,labels=createDataSet()
        featLabels=[]
        myTree=createTree(dataSet,labels,featLabels)
        print(myTree)
    
    
    
    

    结果:

    0个特征的增益为0.0831个特征的增益为0.3242个特征的增益为0.4203个特征的增益为0.3630个特征的增益为0.2521个特征的增益为0.9182个特征的增益为0.474
    {'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
    

    3. 决策树的剪枝

    决策树生成算法递归的产生决策树,直到不能继续下去为止,这样产生的树往往对训练数据的分类很准确,但对未知测试数据的分类缺没有那么精确,即会出现过拟合现象。过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树,解决方法是考虑决策树的复杂度,对已经生成的树进行简化。

    剪枝(pruning):从已经生成的树上裁掉一些子树或叶节点,并将其根节点或父节点作为新的叶子节点,从而简化分类树模型。

    实现方式:极小化决策树整体的损失函数或代价函数来实现

    决策树学习的损失函数定义为:

    Cα(T)=t=1TNtHt(T)+αTC_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|

    其中:

    参数 意义
    TT 表示这棵子树的叶子节点,
    Ht(T)H_t(T) 表示第tt个叶子的熵,这里写图片描述
    NtN_t 表示该叶子所含的训练样例的个数,
    α\alpha 惩罚系数,
    $ T

    因为:
    这里写图片描述
    所以有:Cα(T)=C(T)+αTC_\alpha(T)=C(T)+\alpha|T|

    其中:

    参数 意义
    C(T)C(T) 表示模型对训练数据的预测误差,即模型与训练数据的拟合程度;
    $ T
    α\alpha 参数α&gt;=0\alpha&gt;=0控制两者之间的影响,较大的α\alpha促使选择较简单的模型(树),较小的α\alpha促使选择较复杂的模型(树),α=0\alpha=0意味着只考虑模型与训练数据的拟合程度,不考虑模型的复杂度。

    剪枝就是当α\alpha确定时,选择损失函数最小的模型,即损失函数最小的子树。

    • α\alpha值确定时,子树越大,往往与训练数据的拟合越好,但是模型的复杂度越高;
    • 子树越小,模型的复杂度就越低,但是往往与训练数据的拟合不好
    • 损失函数正好表示了对两者的平衡。

    损失函数认为对于每个分类终点(叶子节点)的不确定性程度就是分类的损失因子,而叶子节点的个数是模型的复杂程度,作为惩罚项,损失函数的第一项是样本的训练误差,第二项是模型的复杂度。如果一棵子树的损失函数值越大,说明这棵子树越差,因此我们希望让每一棵子树的损失函数值尽可能得小,损失函数最小化就是用正则化的极大似然估计进行模型选择的过程。

    决策树的剪枝过程(泛化过程)就是从叶子节点开始递归,记其父节点将所有子节点回缩后的子树为Tb(分类值取类别比例最大的特征值),未回缩的子树为TaTa,如果Cα(Ta)Cα(Tb)C_α(T_a)≥C_α(T_b)说明回缩后使得损失函数减小了,那么应该使这棵子树回缩,递归直到无法回缩为止,这样使用“贪心”的思想进行剪枝可以降低损失函数值,也使决策树得到泛化。

    可以看出,决策树的生成只是考虑通过提高信息增益对训练数据进行更好的拟合,而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。

    公式Cα(T)=C(T)+αTC_\alpha(T)=C(T)+\alpha|T|定义的损失函数的极小化等价于正则化的极大似然估计,剪枝过程示意图:
    这里写图片描述

    这里写图片描述
    这里写图片描述
    这里写图片描述

    决策树算法很容易过拟合(overfitting),剪枝算法就是用来防止决策树过拟合,提高泛华性能的方法。

    剪枝分为预剪枝与后剪枝。

    预剪枝是指在决策树的生成过程中,对每个节点在划分前先进行评估,若当前的划分不能带来泛化性能的提升,则停止划分,并将当前节点标记为叶节点。

    后剪枝是指先从训练集生成一颗完整的决策树,然后自底向上对非叶节点进行考察,若将该节点对应的子树替换为叶节点,能带来泛化性能的提升,则将该子树替换为叶节点。

    那么怎么来判断是否带来泛化性能的提升那?最简单的就是留出法,即预留一部分数据作为验证集来进行性能评估。

    3.2.2 决策树可视化

    这里代码都是关于Matplotlib的,如果对于Matplotlib不了解的,可以先学习下,Matplotlib的内容这里就不再累述。可视化需要用到的函数:

    getNumLeafs:获取决策树叶子结点的数目

    getTreeDepth:获取决策树的层数

    plotNode:绘制结点

    plotMidText:标注有向边属性值

    plotTree:绘制决策树

    createPlot:创建绘制面板

    from math import log
    import operator
    from matplotlib.font_manager import FontProperties
    import matplotlib.pyplot as plt
    """
    函数说明:计算给定数据集的经验熵(香农熵)
    Parameters:
        dataSet:数据集
    Returns:
        shannonEnt:经验熵
    Modify:
        2018-03-12
    
    """
    def calcShannonEnt(dataSet):
        #返回数据集行数
        numEntries=len(dataSet)
        #保存每个标签(label)出现次数的字典
        labelCounts={}
        #对每组特征向量进行统计
        for featVec in dataSet:
            currentLabel=featVec[-1]                     #提取标签信息
            if currentLabel not in labelCounts.keys():   #如果标签没有放入统计次数的字典,添加进去
                labelCounts[currentLabel]=0
            labelCounts[currentLabel]+=1                 #label计数
    
        shannonEnt=0.0                                   #经验熵
        #计算经验熵
        for key in labelCounts:
            prob=float(labelCounts[key])/numEntries      #选择该标签的概率
            shannonEnt-=prob*log(prob,2)                 #利用公式计算
        return shannonEnt                                #返回经验熵
    
    """
    函数说明:创建测试数据集
    Parameters:无
    Returns:
        dataSet:数据集
        labels:分类属性
    Modify:
        2018-03-13
    
    """
    def createDataSet():
        # 数据集
        dataSet=[[0, 0, 0, 0, 'no'],
                [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
    
    """
    函数说明:按照给定特征划分数据集
    
    Parameters:
        dataSet:待划分的数据集
        axis:划分数据集的特征
        value:需要返回的特征值
    Returns:
        无
    Modify:
        2018-03-13
    
    """
    def splitDataSet(dataSet,axis,value):
        #创建返回的数据集列表
        retDataSet=[]
        #遍历数据集
        for featVec in dataSet:
            if featVec[axis]==value:
                #去掉axis特征
                reduceFeatVec=featVec[:axis]
                #将符合条件的添加到返回的数据集
                reduceFeatVec.extend(featVec[axis+1:])
                retDataSet.append(reduceFeatVec)
        #返回划分后的数据集
        return retDataSet
    
    """
    函数说明:计算给定数据集的经验熵(香农熵)
    Parameters:
        dataSet:数据集
    Returns:
        shannonEnt:信息增益最大特征的索引值
    Modify:
        2018-03-13
    
    """
    
    
    def chooseBestFeatureToSplit(dataSet):
        #特征数量
        numFeatures = len(dataSet[0]) - 1
        #计数数据集的香农熵
        baseEntropy = calcShannonEnt(dataSet)
        #信息增益
        bestInfoGain = 0.0
        #最优特征的索引值
        bestFeature = -1
        #遍历所有特征
        for i in range(numFeatures):
            # 获取dataSet的第i个所有特征
            featList = [example[i] for example in dataSet]
            #创建set集合{},元素不可重复
            uniqueVals = set(featList)
            #经验条件熵
            newEntropy = 0.0
            #计算信息增益
            for value in uniqueVals:
                #subDataSet划分后的子集
                subDataSet = splitDataSet(dataSet, i, value)
                #计算子集的概率
                prob = len(subDataSet) / float(len(dataSet))
                #根据公式计算经验条件熵
                newEntropy += prob * calcShannonEnt((subDataSet))
            #信息增益
            infoGain = baseEntropy - newEntropy
            #打印每个特征的信息增益
            print("第%d个特征的增益为%.3f" % (i, infoGain))
            #计算信息增益
            if (infoGain > bestInfoGain):
                #更新信息增益,找到最大的信息增益
                bestInfoGain = infoGain
                #记录信息增益最大的特征的索引值
                bestFeature = i
                #返回信息增益最大特征的索引值
        return bestFeature
    
    """
    函数说明:统计classList中出现次数最多的元素(类标签)
    Parameters:
        classList:类标签列表
    Returns:
        sortedClassCount[0][0]:出现次数最多的元素(类标签)
    Modify:
        2018-03-13
    
    """
    def majorityCnt(classList):
        classCount={}
        #统计classList中每个元素出现的次数
        for vote in classList:
            if vote not in classCount.keys():
                classCount[vote]=0
                classCount[vote]+=1
            #根据字典的值降序排列
            sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
            return sortedClassCount[0][0]
    
    """
    函数说明:创建决策树
    
    Parameters:
        dataSet:训练数据集
        labels:分类属性标签
        featLabels:存储选择的最优特征标签
    Returns:
        myTree:决策树
    Modify:
        2018-03-13
    
    """
    def createTree(dataSet,labels,featLabels):
        #取分类标签(是否放贷:yes or no)
        classList=[example[-1] for example in dataSet]
        #如果类别完全相同,则停止继续划分
        if classList.count(classList[0])==len(classList):
            return classList[0]
        #遍历完所有特征时返回出现次数最多的类标签
        if len(dataSet[0])==1:
            return majorityCnt(classList)
        #选择最优特征
        bestFeat=chooseBestFeatureToSplit(dataSet)
        #最优特征的标签
        bestFeatLabel=labels[bestFeat]
        featLabels.append(bestFeatLabel)
        #根据最优特征的标签生成树
        myTree={bestFeatLabel:{}}
        #删除已经使用的特征标签
        del(labels[bestFeat])
        #得到训练集中所有最优特征的属性值
        featValues=[example[bestFeat] for example in dataSet]
        #去掉重复的属性值
        uniqueVls=set(featValues)
        #遍历特征,创建决策树
        for value in uniqueVls:
            myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),
                                                   labels,featLabels)
        return myTree
    
    """
    函数说明:获取决策树叶子节点的数目
    
    Parameters:
        myTree:决策树
    Returns:
        numLeafs:决策树的叶子节点的数目
    Modify:
        2018-03-13
    
    """
    
    def getNumLeafs(myTree):
        numLeafs=0
        firstStr=next(iter(myTree))
        secondDict=myTree[firstStr]
        for key in secondDict.keys():
            if type(secondDict[key]).__name__=='dict':
                numLeafs+=getNumLeafs(secondDict[key])
            else: numLeafs+=1
        return numLeafs
    
    """
    函数说明:获取决策树的层数
    
    Parameters:
        myTree:决策树
    Returns:
        maxDepth:决策树的层数
    
    Modify:
        2018-03-13
    """
    def getTreeDepth(myTree):
        maxDepth = 0                                                #初始化决策树深度
        firstStr = next(iter(myTree))                                #python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性,可以使用list(myTree.keys())[0]
        secondDict = myTree[firstStr]                                #获取下一个字典
        for key in secondDict.keys():
            if type(secondDict[key]).__name__=='dict':                #测试该结点是否为字典,如果不是字典,代表此结点为叶子结点
                thisDepth = 1 + getTreeDepth(secondDict[key])
            else:   thisDepth = 1
            if thisDepth > maxDepth: maxDepth = thisDepth            #更新层数
        return maxDepth
    
    """
    函数说明:绘制结点
    
    Parameters:
        nodeTxt - 结点名
        centerPt - 文本位置
        parentPt - 标注的箭头位置
        nodeType - 结点格式
    Returns:
        无
    Modify:
        2018-03-13
    """
    def plotNode(nodeTxt, centerPt, parentPt, nodeType):
        arrow_args = dict(arrowstyle="<-")                                            #定义箭头格式
        font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)        #设置中文字体
        createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',    #绘制结点
            xytext=centerPt, textcoords='axes fraction',
            va="center", ha="center", bbox=nodeType, arrowprops=arrow_args, FontProperties=font)
    
    """
    函数说明:标注有向边属性值
    
    Parameters:
        cntrPt、parentPt - 用于计算标注位置
        txtString - 标注的内容
    Returns:
        无
    Modify:
        2018-03-13
    """
    def plotMidText(cntrPt, parentPt, txtString):
        xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]                                            #计算标注位置
        yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
        createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)
    
    """
    函数说明:绘制决策树
    
    Parameters:
        myTree - 决策树(字典)
        parentPt - 标注的内容
        nodeTxt - 结点名
    Returns:
        无
    Modify:
        2018-03-13
    """
    def plotTree(myTree, parentPt, nodeTxt):
        decisionNode = dict(boxstyle="sawtooth", fc="0.8")                                        #设置结点格式
        leafNode = dict(boxstyle="round4", fc="0.8")                                            #设置叶结点格式
        numLeafs = getNumLeafs(myTree)                                                          #获取决策树叶结点数目,决定了树的宽度
        depth = getTreeDepth(myTree)                                                            #获取决策树层数
        firstStr = next(iter(myTree))                                                            #下个字典
        cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)    #中心位置
        plotMidText(cntrPt, parentPt, nodeTxt)                                                    #标注有向边属性值
        plotNode(firstStr, cntrPt, parentPt, decisionNode)                                        #绘制结点
        secondDict = myTree[firstStr]                                                            #下一个字典,也就是继续绘制子结点
        plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD                                        #y偏移
        for key in secondDict.keys():
            if type(secondDict[key]).__name__=='dict':                                            #测试该结点是否为字典,如果不是字典,代表此结点为叶子结点
                plotTree(secondDict[key],cntrPt,str(key))                                        #不是叶结点,递归调用继续绘制
            else:                                                                                #如果是叶结点,绘制叶结点,并标注有向边属性值
                plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
                plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
                plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
        plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD
    
    """
    函数说明:创建绘制面板
    
    Parameters:
        inTree - 决策树(字典)
    Returns:
        无
    Modify:
        2018-03-13
    """
    def createPlot(inTree):
        fig = plt.figure(1, facecolor='white')#创建fig
        fig.clf()#清空fig
        axprops = dict(xticks=[], yticks=[])
        createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)#去掉x、y轴
        plotTree.totalW = float(getNumLeafs(inTree))#获取决策树叶结点数目
        plotTree.totalD = float(getTreeDepth(inTree))#获取决策树层数
        plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0#x偏移
        plotTree(inTree, (0.5,1.0), '')#绘制决策树
        plt.show()#显示绘制结果
    
    if __name__ == '__main__':
        dataSet, labels = createDataSet()
        featLabels = []
        myTree = createTree(dataSet, labels, featLabels)
        print(myTree)
        createPlot(myTree)
    
    if __name__=='__main__':
        dataSet,labels=createDataSet()
        featLabels=[]
        myTree=createTree(dataSet,labels,featLabels)
        print(myTree)
    
    

    这里写图片描述

    3.2.3 ID3、C4.5、CART的区别

    这三个是非常著名的决策树算法。简单粗暴来说,ID3 使用信息增益作为选择特征的准则;C4.5 使用信息增益比作为选择特征的准则;CART 使用 Gini 指数作为选择特征的准则。

    一、ID3
    熵表示的是数据中包含的信息量大小。熵越小,数据的纯度越高,也就是说数据越趋于一致,这是我们希望的划分之后每个子节点的样子。

    信息增益 = 划分前熵 - 划分后熵。信息增益越大,则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 **。也就是说,用属性 a 来划分训练集,得到的结果中纯度比较高。

    ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。

    二、C4.5

    C4.5 克服了 ID3 仅仅能够处理离散属性的问题,以及信息增益偏向选择取值较多特征的问题,使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。

    C4.5 处理连续特征是先将特征取值排序,以连续两个值中间值作为划分标准。尝试每一种划分,并计算修正后的信息增益,选择信息增益最大的分裂点作为该属性的分裂点。

    三、CART

    CART 与 ID3,C4.5 不同之处在于 CART 生成的树必须是二叉树。也就是说,无论是回归还是分类问题,无论特征是离散的还是连续的,无论属性取值有多个还是两个,内部节点只能根据属性值进行二分。

    CART 的全称是分类与回归树。从这个名字中就应该知道,CART 既可以用于分类问题,也可以用于回归问题。

    回归树中,使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值,是划分到该叶子节点的所有样本目标值的均值,这样只是在给定划分的情况下最小化了平方误差。

    要确定最优化分,还需要遍历所有属性,以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差,选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则,所以又叫做最小二乘回归树。

    分类树种,使用 Gini 指数最小化准则来选择特征并进行划分;

    Gini 指数表示集合的不确定性,或者是不纯度。基尼指数越大,集合不确定性越高,不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是,基尼指数是为了最小化误分类的概率。

    信息增益 vs 信息增益比

    之所以引入了信息增益比,是由于信息增益的一个缺点。那就是:信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项,解决了这个问题。

    Gini 指数 vs 熵

    既然这两个都可以表示数据的不确定性,不纯度。那么这两个有什么区别那?

    • Gini 指数的计算不需要对数运算,更加高效;
    • Gini 指数更偏向于连续属性,熵更偏向于离散属性。

    3.3 使用决策树进行分类

    依靠训练数据构造了决策树之后,我们可以将它用于实际数据的分类。在执行数据分类时,需要决策树以及用于构造树的标签向量。然后,程序比较测试数据与决策树上的数值,递归执行该过程直到进入叶子结点;最后将测试数据定义为叶子结点所属的类型。在构建决策树的代码,可以看到,有个featLabels参数。它是用来干什么的?它就是用来记录各个分类结点的,在用决策树做预测的时候,我们按顺序输入需要的分类结点的属性值即可。举个例子,比如我用上述已经训练好的决策树做分类,那么我只需要提供这个人是否有房子,是否有工作这两个信息即可,无需提供冗余的信息。

    from math import log
    import operator
    
    """
    函数说明:计算给定数据集的经验熵(香农熵)
    Parameters:
        dataSet:数据集
    Returns:
        shannonEnt:经验熵
    Modify:
        2018-03-12
    
    """
    def calcShannonEnt(dataSet):
        #返回数据集行数
        numEntries=len(dataSet)
        #保存每个标签(label)出现次数的字典
        labelCounts={}
        #对每组特征向量进行统计
        for featVec in dataSet:
            currentLabel=featVec[-1]                     #提取标签信息
            if currentLabel not in labelCounts.keys():   #如果标签没有放入统计次数的字典,添加进去
                labelCounts[currentLabel]=0
            labelCounts[currentLabel]+=1                 #label计数
    
        shannonEnt=0.0                                   #经验熵
        #计算经验熵
        for key in labelCounts:
            prob=float(labelCounts[key])/numEntries      #选择该标签的概率
            shannonEnt-=prob*log(prob,2)                 #利用公式计算
        return shannonEnt                                #返回经验熵
    
    """
    函数说明:创建测试数据集
    Parameters:无
    Returns:
        dataSet:数据集
        labels:分类属性
    Modify:
        2018-03-13
    
    """
    def createDataSet():
        # 数据集
        dataSet=[[0, 0, 0, 0, 'no'],
                [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
    
    """
    函数说明:按照给定特征划分数据集
    
    Parameters:
        dataSet:待划分的数据集
        axis:划分数据集的特征
        value:需要返回的特征值
    Returns:
        无
    Modify:
        2018-03-13
    
    """
    def splitDataSet(dataSet,axis,value):
        #创建返回的数据集列表
        retDataSet=[]
        #遍历数据集
        for featVec in dataSet:
            if featVec[axis]==value:
                #去掉axis特征
                reduceFeatVec=featVec[:axis]
                #将符合条件的添加到返回的数据集
                reduceFeatVec.extend(featVec[axis+1:])
                retDataSet.append(reduceFeatVec)
        #返回划分后的数据集
        return retDataSet
    
    """
    函数说明:计算给定数据集的经验熵(香农熵)
    Parameters:
        dataSet:数据集
    Returns:
        shannonEnt:信息增益最大特征的索引值
    Modify:
        2018-03-13
    
    """
    
    
    def chooseBestFeatureToSplit(dataSet):
        #特征数量
        numFeatures = len(dataSet[0]) - 1
        #计数数据集的香农熵
        baseEntropy = calcShannonEnt(dataSet)
        #信息增益
        bestInfoGain = 0.0
        #最优特征的索引值
        bestFeature = -1
        #遍历所有特征
        for i in range(numFeatures):
            # 获取dataSet的第i个所有特征
            featList = [example[i] for example in dataSet]
            #创建set集合{},元素不可重复
            uniqueVals = set(featList)
            #经验条件熵
            newEntropy = 0.0
            #计算信息增益
            for value in uniqueVals:
                #subDataSet划分后的子集
                subDataSet = splitDataSet(dataSet, i, value)
                #计算子集的概率
                prob = len(subDataSet) / float(len(dataSet))
                #根据公式计算经验条件熵
                newEntropy += prob * calcShannonEnt((subDataSet))
            #信息增益
            infoGain = baseEntropy - newEntropy
            #打印每个特征的信息增益
            print("第%d个特征的增益为%.3f" % (i, infoGain))
            #计算信息增益
            if (infoGain > bestInfoGain):
                #更新信息增益,找到最大的信息增益
                bestInfoGain = infoGain
                #记录信息增益最大的特征的索引值
                bestFeature = i
                #返回信息增益最大特征的索引值
        return bestFeature
    
    """
    函数说明:统计classList中出现次数最多的元素(类标签)
    Parameters:
        classList:类标签列表
    Returns:
        sortedClassCount[0][0]:出现次数最多的元素(类标签)
    Modify:
        2018-03-13
    
    """
    def majorityCnt(classList):
        classCount={}
        #统计classList中每个元素出现的次数
        for vote in classList:
            if vote not in classCount.keys():
                classCount[vote]=0
                classCount[vote]+=1
            #根据字典的值降序排列
            sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
            return sortedClassCount[0][0]
    
    """
    函数说明:创建决策树
    
    Parameters:
        dataSet:训练数据集
        labels:分类属性标签
        featLabels:存储选择的最优特征标签
    Returns:
        myTree:决策树
    Modify:
        2018-03-13
    
    """
    def createTree(dataSet,labels,featLabels):
        #取分类标签(是否放贷:yes or no)
        classList=[example[-1] for example in dataSet]
        #如果类别完全相同,则停止继续划分
        if classList.count(classList[0])==len(classList):
            return classList[0]
        #遍历完所有特征时返回出现次数最多的类标签
        if len(dataSet[0])==1:
            return majorityCnt(classList)
        #选择最优特征
        bestFeat=chooseBestFeatureToSplit(dataSet)
        #最优特征的标签
        bestFeatLabel=labels[bestFeat]
        featLabels.append(bestFeatLabel)
        #根据最优特征的标签生成树
        myTree={bestFeatLabel:{}}
        #删除已经使用的特征标签
        del(labels[bestFeat])
        #得到训练集中所有最优特征的属性值
        featValues=[example[bestFeat] for example in dataSet]
        #去掉重复的属性值
        uniqueVls=set(featValues)
        #遍历特征,创建决策树
        for value in uniqueVls:
            myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),
                                                   labels,featLabels)
        return myTree
    
    
    
    """
    使用决策树进行分类
    Parameters:
        inputTree;已经生成的决策树
        featLabels:存储选择的最优特征标签
        testVec:测试数据列表,顺序对应最优特征标签
    Returns:
        classLabel:分类结果
    Modify:2018-03-13
    
    """
    def classify(inputTree,featLabels,testVec):
        #获取决策树节点
        firstStr=next(iter(inputTree))
        #下一个字典
        secondDict=inputTree[firstStr]
        featIndex=featLabels.index(firstStr)
    
        for key in secondDict.keys():
            if testVec[featIndex]==key:
                if type(secondDict[key]).__name__=='dict':
                    classLabel=classify(secondDict[key],featLabels,testVec)
                else: classLabel=secondDict[key]
        return classLabel
    
    if __name__=='__main__':
        dataSet,labels=createDataSet()
        featLabels=[]
        myTree=createTree(dataSet,labels,featLabels)
        #测试数据
        testVec=[0,1]
        result=classify(myTree,featLabels,testVec)
    
        if result=='yes':
            print('放贷')
        if result=='no':
            print('不放贷')
    
    

    结果:

    0个特征的增益为0.0831个特征的增益为0.3242个特征的增益为0.4203个特征的增益为0.3630个特征的增益为0.2521个特征的增益为0.9182个特征的增益为0.474
    放贷
    

    3.4 决策树的存储

    构造决策树是很耗时的任务,即使处理很小的数据集,如前面的样本数据,也要花费几秒的时间,如果数据集很大,将会耗费很多计算时间。然而用创建好的决策树解决分类问题,则可以很快完成。因此,为了节省计算时间,最好能够在每次执行分类时调用已经构造好的决策树。为了解决这个问题,需要使用Python模块pickle序列化对象。序列化对象可以在磁盘上保存对象,并在需要的时候读取出来。

    假设我们已经得到决策树{'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}},使用pickle.dump存储决策树。

    import pickle
    """
    函数说明:存储决策树
    Parameters:
        inputTree:已经生成的决策树
        filename:决策树的存储文件名
    Returns:
        无
    Modify:
        2018-03-13
    
    """
    def storeTree(inputTree,filename):
        with open(filename,'wb') as fw:
            pickle.dump(inputTree,fw)
    
    if __name__=='__main__':
        myTree={'有自己的房子':{0:{'有工作':{0:'no',1:'yes'}},1:'yes'}}
        storeTree(myTree,'classifierStorage.txt')
    
    
    
    

    运行代码,在该Python文件的相同目录下,会生成一个名为classifierStorage.txt的txt文件,这个文件二进制存储着我们的决策树。

    很简单使用pickle.load进行载入即可,编写代码如下:

    import pickle
    
    """
    函数说明:读取决策树
    
    Parameters:
        filename:决策树的存储文件名
    Returns:
        pickle.load(fr):决策树字典
    Modify:
        2018-03-13
    """
    def grabTree(filename):
        fr = open(filename, 'rb')
        return pickle.load(fr)
    
    if __name__ == '__main__':
        myTree = grabTree('classifierStorage.txt')
        print(myTree)
    

    3.5 sklearn——使用决策树预测隐形眼镜类型

    数据集下载

    步骤:

    收集数据:使用书中提供的小型数据集

    准备数据:对文本中的数据进行预处理,如解析数据行

    分析数据:快速检查数据,并使用createPlot()函数绘制最终的树形图

    训练决策树:使用createTree()函数训练

    测试决策树:编写简单的测试函数验证决策树的输出结果&绘图结果

    使用决策树:这部分可选择将训练好的决策树进行存储,以便随时使用

    这里写图片描述

    3.5.1 使用sklearn构建决策树

    官方网站

    sklearn.tree——提供了决策树模型,用于解决分类和回归问题

    class sklearn.tree.DecisionTreeClassifier(criterion=’gini’, splitter=’best’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)[source]
    

    参数说明如下:

    criterion:特征选择标准,可选参数,默认是gini,可以设置为entropy。gini是基尼不纯度,是将来自集合的某种结果随机应用于某一数据项的预期误差率,是一种基于统计的思想。entropy是香农熵,也就是上篇文章讲过的内容,是一种基于信息论的思想。Sklearn把gini设为默认参数,应该也是做了相应的斟酌的,精度也许更高些?ID3算法使用的是entropy,CART算法使用的则是gini。

    splitter:特征划分点选择标准,可选参数,默认是best,可以设置为random。每个结点的选择策略。best参数是根据算法选择最佳的切分特征,例如gini、entropy。random随机的在部分划分点中找局部最优的划分点。默认的”best”适合样本量不大的时候,而如果样本数据量非常大,此时决策树构建推荐”random”。

    max_features:划分时考虑的最大特征数,可选参数,默认是None。寻找最佳切分时考虑的最大特征数(n_features为总共的特征数),有如下6种情况:
    如果max_features是整型的数,则考虑max_features个特征;
    如果max_features是浮点型的数,则考虑int(max_features * n_features)个特征;
    如果max_features设为auto,那么max_features = sqrt(n_features);
    如果max_features设为sqrt,那么max_featrues = sqrt(n_features),跟auto一样;
    如果max_features设为log2,那么max_features = log2(n_features);
    如果max_features设为None,那么max_features = n_features,也就是所有特征都用。
    一般来说,如果样本特征数不多,比如小于50,我们用默认的”None”就可以了,如果特征数非常多,我们可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数,以控制决策树的生成时间。

    max_depth:决策树最大深,可选参数,默认是None。这个参数是这是树的层数的。层数的概念就是,比如在贷款的例子中,决策树的层数是2层。如果这个参数设置为None,那么决策树在建立子树的时候不会限制子树的深度。一般来说,数据少或者特征少的时候可以不管这个值。或者如果设置了min_samples_slipt参数,那么直到少于min_smaples_split个样本为止。如果模型样本量多,特征也多的情况下,推荐限制这个最大深度,具体的取值取决于数据的分布。常用的可以取值10-100之间。

    min_samples_split:内部节点再划分所需最小样本数,可选参数,默认是2。这个值限制了子树继续划分的条件。如果min_samples_split为整数,那么在切分内部结点的时候,min_samples_split作为最小的样本数,也就是说,如果样本已经少于min_samples_split个样本,则停止继续切分。如果min_samples_split为浮点数,那么min_samples_split就是一个百分比,ceil(min_samples_split * n_samples),数是向上取整的。如果样本量不大,不需要管这个值。如果样本量数量级非常大,则推荐增大这个值。
    min_weight_fraction_leaf:叶子节点最小的样本权重和,可选参数,默认是0。这个值限制了叶子节点所有样本权重和的最小值,如果小于这个值,则会和兄弟节点一起被剪枝。一般来说,如果我们有较多样本有缺失值,或者分类树样本的分布类别偏差很大,就会引入样本权重,这时我们就要注意这个值了。

    max_leaf_nodes:最大叶子节点数,可选参数,默认是None。通过限制最大叶子节点数,可以防止过拟合。如果加了限制,算法会建立在最大叶子节点数内最优的决策树。如果特征不多,可以不考虑这个值,但是如果特征分成多的话,可以加以限制,具体的值可以通过交叉验证得到。

    class_weight:类别权重,可选参数,默认是None,也可以字典、字典列表、balanced。指定样本各类别的的权重,主要是为了防止训练集某些类别的样本过多,导致训练的决策树过于偏向这些类别。类别的权重可以通过{class_label:weight}这样的格式给出,这里可以自己指定各个样本的权重,或者用balanced,如果使用balanced,则算法会自己计算权重,样本量少的类别所对应的样本权重会高。当然,如果你的样本类别分布没有明显的偏倚,则可以不管这个参数,选择默认的None。

    random_state:可选参数,默认是None。随机数种子。如果是证书,那么random_state会作为随机数生成器的随机数种子。随机数种子,如果没有设置随机数,随机出来的数与当前系统时间有关,每个时刻都是不同的。如果设置了随机数种子,那么相同随机数种子,不同时刻产生的随机数也是相同的。如果是RandomState instance,那么random_state是随机数生成器。如果为None,则随机数生成器使用np.random。

    min_impurity_split:节点划分最小不纯度,可选参数,默认是1e-7。这是个阈值,这个值限制了决策树的增长,如果某节点的不纯度(基尼系数,信息增益,均方差,绝对差)小于这个阈值,则该节点不再生成子节点。即为叶子节点 。

    presort:数据是否预排序,可选参数,默认为False,这个值是布尔值,默认是False不排序。一般来说,如果样本量少或者限制了一个深度很小的决策树,设置为true可以让划分点选择更加快,决策树建立的更加快。如果样本量太大的话,反而没有什么好处。问题是样本量少的时候,我速度本来就不慢。所以这个值一般懒得理它就可以了。
    除了这些参数要注意以外,其他在调参时的注意点有:

    当样本数量少但是样本特征非常多的时候,决策树很容易过拟合,一般来说,样本数比特征数多一些会比较容易建立健壮的模型
    如果样本数量少但是样本特征非常多,在拟合决策树模型前,推荐先做维度规约,比如主成分分析(PCA),特征选择(Losso)或者独立成分分析(ICA)。这样特征的维度会大大减小。再来拟合决策树模型效果会好。
    推荐多用决策树的可视化,同时先限制决策树的深度,这样可以先观察下生成的决策树里数据的初步拟合情况,然后再决定是否要增加深度。
    在训练模型时,注意观察样本的类别情况(主要指分类树),如果类别分布非常不均匀,就要考虑用class_weight来限制模型过于偏向样本多的类别。
    决策树的数组使用的是numpy的float32类型,如果训练数据不是这样的格式,算法会先做copy再运行。
    如果输入的样本矩阵是稀疏的,推荐在拟合前调用csc_matrix稀疏化,在预测前调用csr_matrix稀疏化。
    sklearn.tree.DecisionTreeClassifier()提供了一些方法供我们使用,如下图所示:
    这里写图片描述

    数据预处理:将string类型的数据集进行编码:
    1)LabelEncoder:将字符串转换为增量值
    2)OneHotEncoder:使用One-of-K算法将字符串转换为整数

    为了对string类型的数据序列化,需要先生成pandas数据,这样方便我们的序列化工作。这里我使用的方法是,原始数据->字典->pandas数据,编写代码如下:

    import pandas as pd
    from sklearn.preprocessing import LabelEncoder
    
    # import pydotplus
    # from sklearn.externals.six import StringIO
    
    if __name__ == '__main__':
        # 加载文件
        with open('lenses.txt', 'r') as fr:
            # 处理文件
            lenses = [inst.strip().split('\t') for inst in fr.readlines()]
        # 提取每组数据的类别,保存在列表里
        lenses_target = []
        for each in lenses:
            lenses_target.append(each[-1])
        # 特征标签
        lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
        # 保存lenses数据的临时列表
        lenses_list = []
        # 保存lenses数据的字典,用于生成pandas
        lenses_dict = {}
        # 提取信息,生成字典
        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)
        #生成pandas.DataFrame
        lenses_pd = pd.DataFrame(lenses_dict)
        # print(lenses_pd)
        # 生成pandas.DataFrame
        lenses_pd = pd.DataFrame(lenses_dict)
        # 打印pandas.DataFrame
        print(lenses_pd)
        # 创建LabelEncoder()对象,用于序列化
        le = LabelEncoder()
        # 为每一列序列化
        for col in lenses_pd.columns:
            lenses_pd[col] = le.fit_transform(lenses_pd[col])
        print(lenses_pd)
    

    <img src="//img-blog.csdn.net/20180313202656991?watermark/2/text/Ly9ibG9nLmNzZG4ubmV0L2ppYW95YW5nd20=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70"width=60%alt=""/><img src="//img-blog.csdn.net/20180313202846875?watermark/2/text/Ly9ibG9nLmNzZG4ubmV0L2ppYW95YW5nd20=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70"width=60%alt=""/>

    3.5.2 使用Graphviz可视化决策树

    1)pydotplus安装

    直接在anaconda prompt下输入:

    pip install pydotplus
    

    2)Graphviz下载

    安装步骤安装,之后win+R->sysdm.cpl
    这里写图片描述
    在“环境变量”中的“系统变量”中找到“PATH”,之后将路径C:\Anaconda\pkgs\graphviz-2.38.0-4\Library\bin添加到后面,重启Pycharm即可。

    3.6 总结

    优点:

    • 易于理解和解释,决策树可以可视化。
    • 几乎不需要数据预处理。其他方法经常需要数据标准化,创建虚拟变量和删除缺失值。决策树还不支持缺失值。
    • 使用树的花费(例如预测数据)是训练数据点(data points)数量的对数。
    • 可以同时处理数值变量和分类变量。其他方法大都适用于分析一种变量的集合。
    • 可以处理多值输出变量问题。
    • 使用白盒模型。如果一个情况被观察到,使用逻辑判断容易表示这种规则。相反,如果是黑盒模型(例如人工神经网络),结果会非常难解释。
    • 即使对真实模型来说,假设无效的情况下,也可以较好的适用。

    缺点:

    • 决策树学习可能创建一个过于复杂的树,并不能很好的预测数据。也就是过拟合。修剪机制(现在不支持),设置一个叶子节点需要的最小样本数量,或者数的最大深度,可以避免过拟合。
    • 决策树可能是不稳定的,因为即使非常小的变异,可能会产生一颗完全不同的树。这个问题通过decision trees with an ensemble来缓解。
    • 学习一颗最优的决策树是一个NP-完全问题under several aspects of optimality and even for simple concepts。因此,传统决策树算法基于启发式算法,例如贪婪算法,即每个节点创建最优决策。这些算法不能产生一个全家最优的决策树。对样本和特征随机抽样可以降低整体效果偏差。
    • 概念难以学习,因为决策树没有很好的解释他们,例如,XOR, parity or multiplexer problems.
    • 如果某些分类占优势,决策树将会创建一棵有偏差的树。因此,建议在训练之前,先抽样使样本均衡。

    决策树算法主要包括三个部分:特征选择、树的生成、树的剪枝。常用算法有 ID3、C4.5、CART。

    • 特征选择。特征选择的目的是选取能够对训练集分类的特征。特征选择的关键是准则:信息增益、信息增益比、Gini 指数;

    • 决策树的生成。通常是利用信息增益最大、信息增益比最大、Gini 指数最小作为特征选择的准则。从根节点开始,递归的生成决策树。相当于是不断选取局部最优特征,或将训练集分割为基本能够正确分类的子集;

    • 决策树的剪枝。决策树的剪枝是为了防止树的过拟合,增强其泛化能力。包括预剪枝和后剪枝。

    3.7 梯度提升决策树(GBDT)

    3.7.1 GBDT概述

    梯度提升决策树GBDT(Gradient Boosting Decision Tree)也被称为是MART(Multiple Additive Regression Tree))或者是GBRT(Gradient Boosting Regression Tree),也是一种基于集成思想的决策树模型,但是它和Random Forest有着本质上的区别。不得不提的是,GBDT是目前竞赛中最为常用的一种机器学习算法,因为它不仅可以适用于多种场景,更难能可贵的是,GBDT有着出众的准确率。这也是为什么很多人称GBDT为机器学习领域的“屠龙刀”。

    “Boosting,迭代,即通过迭代多棵树来共同决策。这怎么实现呢?难道是每棵树独立训练一遍,比如A这个人,第一棵树认为是10岁,第二棵树认为是0岁,第三棵树认为是20岁,我们就取平均值10岁做最终结论?当然不是!且不说这是投票方法并不是GBDT,只要训练集不变,独立训练三次的三棵树必定完全相同,这样做完全没有意义。之前说过,GBDT是把所有树的结论累加起来做最终结论的,所以可以想到每棵树的结论并不是年龄本身,而是年龄的一个累加量。

    GBDT的核心就在于:每一棵树学的是之前所有树结论和的残差,这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁,但第一棵树的预测年龄是12岁,差了6岁,即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习,如果第二棵树真的能把A分到6岁的叶子节点,那累加两棵树的结论就是A的真实年龄;如果第二棵树的结论是5岁,则A仍然存在1岁的残差,第三棵树里A的年龄就变成1岁,继续学,如果我们的迭代轮数还没有完,可以继续迭代下面,每一轮迭代,拟合的岁数误差都会减小。这就是Gradient Boosting在GBDT中的意义。

    其实从这里我们可以看出GBDT与Random Forest的本质区别,GBDT不仅仅是简单地运用集成思想,而且它是基于对残差的学习的。我们在这里利用一个GBDT的经典实例进行解释。

    在GBDT的迭代中,假设我们前一轮迭代得到的强学习器是ft1(x)f_{t−1}(x), 损失函数是L(y,ft1(x))L(y,ft1(x))L(y,f_{t−1}(x))L(y,f_{t−1}(x)), 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器ht(x)h_t(x),让本轮的损失损失L(y,ft(x)=L(y,ft1(x)+ht(x))L(y,ft(x)=L(y,f_{t−1}(x)+h_t(x))最小。也就是说,本轮迭代找到决策树,要让样本的损失尽量变得更小。

    GBDT主要的优点有:

    1. 可以灵活处理各种类型的数据,包括连续值和离散值。

    2. 在相对少的调参时间情况下,预测的准备率也可以比较高。这个是相对SVM来说的。

    3)使用一些健壮的损失函数,对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

    GBDT的主要缺点有:

    1)由于弱学习器之间存在依赖关系,难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。

    参考于梯度提升树(GBDT)原理小结
    这篇博客也很好机器学习算法GBDT

    展开全文
  • 决策树详解

    万次阅读 多人点赞 2018-07-18 20:43:20
    决策树是一种常见的机器学习算法,它的思想十分朴素,类似于我们平时利用选择做决策的过程。 例如有人给我们介绍新的对象的时候,我们就要一个个特点去判断,于是这种判断的过程就可以画成一棵树,例如根据特点...

    定义

    决策树是一种常见的机器学习算法,它的思想十分朴素,类似于我们平时利用选择做决策的过程。

    例如有人给我们介绍新的对象的时候,我们就要一个个特点去判断,于是这种判断的过程就可以画成一棵树,例如根据特点依次判断:
    这里写图片描述

    如上,决策的形式以树的形式进行示意和编码,就形成了决策树。

    结构

    显然,决策树在逻辑上以树的形式存在,包含根节点、内部结点和叶节点
    - 根节点:包含数据集中的所有数据的集合
    - 内部节点:每个内部节点为一个判断条件,并且包含数据集中满足从根节点到该节点所有条件的数据的集合。根据内部结点的判断条件测试结果,内部节点对应的数据的集合别分到两个或多个子节点中。
    - 叶节点:叶节点为最终的类别,被包含在该叶节点的数据属于该类别。

    简而言之,决策树是一个利用树的模型进行决策的多分类模型,简单有效,易于理解。

    伪代码

    决策树算法的伪代码(参照了python语法)如下图所示:

    # D = {(x1,y1)、(x2,y2)......(xm,yn)} 是数据集
    # A = {a1、a2、a3.} 是划分节点的属性集
    # 节点node有两个主要属性:content代表该节点需要分类的训练集,type代表叶节点的决策类型
    def generateTree(D,A):
        newNode = 空 #生成新的节点
        # 如果当前数据集都为一个种类,则设为一个叶节点并返回
        if D 中数据皆属于类别 C:
            newNode.content = D
            newNode.type = C
            return  
        # 如果已经没有属性了或者数据集在剩余属性中表现相同(属性无法区分)
        if A = 空集 or D中数据在A中取值相同:
            newNode.content = D
            newNode.type = D中最多的类
            return
        #从A中选取最优的属性a
        a=selectBestPorperty(A)
        #为a的每一个取值生成一个节点,递归进行处理
        for a的每一个取值 res[i]:
            生成新的分支节点 node[i]
            D[i] = D中取值为res[i]的数据
            node[i].content = D[i]
            if node[i].content == null:
                node[i].type = D中最多的类
            else:
                generateTree(D[i],A - {a})
        return        

    划分选择

    可以看到,在伪代码中,大部分步骤都是简单而明确的,而最重要的步骤在于从A中选取最优的属性a,可以说,属性选择的质量,决定了决策树的预测准确度。这很容易理解,例如我们看一个学生聪明与否可以看他的成绩,但是如果依靠他的身高预测他是否聪明,显然得不到好的结果。

    一般的原则是,希望通过不断划分节点,使得一个分支节点包含的数据尽可能的属于同一个类别,即“纯度“越来越高。

    这里列出三种常用的准则。

    信息增益准则

    我们先对一个节点的纯度进行定义,我们将其称之为信息熵

    Ent(D)=k=1|γ|pklog(pk)

    其中pk代表当前节点D的数据中第k类样本所占的比例。

    观察该信息熵的定义,有以下几个特点:

    • 由于pk都属于[0,1],Ent(D)必定为正值,值越大说明纯度越低
    • Ent(D)在k=1,p1=1时取值最小值0,在k=|γ| pk=1|γ|时取值最大值log2|γ|
    • 信息熵是一个节点的固有性质,和该节点选取什么属性进行下一步的划分无关

    在定义了信息熵之后,对信息增益进行定义,假设选取属性a有V个取值,{a1a2......aV},按照决策树的规则,D将被划分为V个不同的节点数据集,Dv代表其中第v个节点:

    Gain(D,a)=Ent(D)v=1V|Dv||D|Ent(Dv)

    观察该式,有以下几点说明:

    • 第一线Ent(D)是确定的,和选取的属性a无关,我们可以将之看为定值
    • |Dv||D|表示分支节点所占的比例大小,显然数据集越大的分支节点权重越高
    • 分支节点整体纯度越大,则后一项越小,信息增益Gain变得越大,所以我们的目标是如何最大化信息增益

    由此,我们得到了一种选择划分属性的方法,计算以每个属性进行划分子节点得到的信息增益,选择其中最大的作为选择的属性。

    信息增益率准则

    信息增益原则对于每个分支节点,都会乘以其权重,也就是说,由于权重之和为1,所以分支节点分的越多,即每个节点数据越小,纯度可能越高。这样会导致信息熵准则偏爱那些取值数目较多的属性

    为了解决该问题,这里引入了信息增益率,定义如下:

    Gainratio(D,a)=Gain(D,a)IV(a)

    IV(a)=v=1V|Dv||D|log2|Dv||D|

    相当于引入了修正项IV(a),它是对于属性a的固有值。

    需要注意的是,信息增益率原则可能对取值数目较少的属性更加偏爱,为了解决这个问题,可以先找出信息增益在平均值以上的属性,在从中选择信息增益率最高的

    基尼指数准则

    在CART决策树中,使用基尼指数来选择属性,首先定义数据集D的基尼值:

    Gini(D)=k=1|γ|k1!=kpkpk1=1k=1|γ|pk2

    形象的说,基尼值代表了从D中随机选择两个样本,其类别不一致的概率。

    有了基尼值后,可以在此基础上定义基尼指数:

    Giniindex(D,a)=v=1V|Dv||D|Gini(Dv)

    其中Dv的含义和之前相同,可以看出基尼指数越小,说明纯度越高,我们可以通过选择基尼指数小的属性来划分子节点。

    剪枝

    剪枝是应该决策树过拟合的一种重要方法,主要分为以下两种:

    • 预剪枝:该策略就是在对一个节点进行划分前进行估计,如果不能提升决策树泛化精度,就停止划分,将当前节点设置为叶节点。那么怎么测量泛化精度,就是留出一部分训练数据当做测试集,每次划分前比较划分前后的测试集预测精度。
      • 优点:降低了过拟合风险,降低了训练所需的时间。
      • 缺点:预剪枝是一种贪心操作,可能有些划分暂时无法提升精度,但是后续划分可以提升精度。故产生了欠拟合的风险。
    • 后剪枝:该策略是首先正常建立一个决策树,然后对整个决策树进行剪枝。按照决策树的广度优先搜索的反序,依次对内部节点进行剪枝,如果将某以内部节点为根的子树换成一个叶节点,可以提高泛化性能,就进行剪枝。
      • 优先:降低过拟合风险,降低欠拟合风险,决策树效果提升比预剪枝强
      • 缺点:时间开销大得多

    特殊值处理

    连续值处理

    在之前进行选择属性的时候,我们仅仅讨论了属性值为离散值的情况,例如身高分为“极高、高、较高、中等、较矮”五个选项,但是如果数据集中身高为连续值,例如140-210cm,我们该如何处理呢?

    这里可以采用二分的思想,将连续值化为离散值。由于我们的数据集是有限的,即使是连续值,属性a在数据集中也只出现了有限个确定的值,记为(a1,a2,a3......an),且a1<a2<a3......<an

    取n个值的中点,令

    t1=a1+a22,t2=a2+a32......tn1=an1+an2

    我们得到了n-1个中点,(t1t2......tn1),任取一个值ti可以将数据集D分为两个,D+表示D中大于ti的数据,D表示D中小于ti的数据集合,这样,我们便可以同离散值一样进行处理了

    接下来的问题是,选取哪一个t呢?显然在信息增益准则下,应该选择使得信息增益最大的t:

    Gain(D,a)=maxtGain(D,a,t)=maxtEnt(D)λ{+,}|Dλ||D|Ent(Dtλ)

    经过稍加改造的信息增益公式就可以选择最好的t来进行划分。

    缺失值处理

    缺失值处理较为复杂,设计到较多的公式,在这里给出链接,读者可以参考阅读

    缺失值处理详解

    其主要思想是

    • 在选择属性时,仅使用不缺失该属性的数据来计算信息增益,最后乘以一个代表缺失数据比例的比例系数
    • 在对某个属性进行划分子节点时,对于不缺失该属性的数据正常划分,对于缺失该属性的数据,按不同的权重划分进行每个子节点

    多变量决策树

    实际上大部分机器学习的分类算法,都是将一个具有n个属性的数据,看成一个在n维空间的一个点,分类的过程就是在n维空间或者更高维度空间中找到超平面,将这些点进行划分

    而普通的决策树算法有一个特点,由于它每个节点的划分条件都是单独的,明确的,所以决策树的决策边界是平行于空间的坐标轴的。如下图所示:

    这里写图片描述
    这对其拟合特性有一定的影响,当数据比较复杂时,需要较多的属性才能得到较好的划分,而多变量决策树就可以解决该问题。

    在多变量决策树的学习过程中,不是为每个非叶结点寻找一个最优划分属性,而是试图建立一个合适的线性分类器。 如下图所示:

    这里写图片描述

    多变量决策树较复杂,如果想进一步了解,可以阅读这个领域的论文。

    查看更多

    所有的文章都会在我的博客和我的知乎专栏同步进行更