决策树

决策树模型与学习
特征选择
决策树的生成
决策树的剪枝
CART 算法

决策树模型实现

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

决策树模型与学习

决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性，叶结点表示一个类。
决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。
决策树学习本质上是从训练数据集中归纳出一组分类规则。
决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。
开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。
我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。
如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。
决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。

特征选择

如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。
在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设 $X$ 是一个取有限个值的离散随机变量，其概率分布为
$p(X=x_i)=p_i, \ \ \ \ \ i=1,2,...,n$
则随机变量 $X$ 的熵定义为
$H(X) = -\sum_{i=1}^np_i\log p_i$
$H(X)$ 也常用 $H(p)$ 表示，式中的对数以2为底或以e为底，这时熵的单位分别称作比特（bit）或纳特（nat）。熵越大，随机变量的不确定性就越大。
条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性。随机变量 $X$ 给定的条件下随机变量 $Y$ 的条件熵（conditional entropy） $H(Y|X)$ ，定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望
$P(X=x_i,Y=y_j) = p_{ij}, \ \ \ \ \ i=1,2,...,n; \ \ \ \ \ j=1,2,...,m \\ H(Y|X) = \sum_{i=1}^np_iH(Y\mid X=x_i)$
其中 $p_i=P(X=x_i), \ \ \ \ \ i=1,2,...,n$ 。
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。
信息增益（information gain）表示得知特征 $X$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。
特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$ ，定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差
$g(D,A) = H(D) - H(D\mid A)$
一般地，熵 $H(Y)$ 与条件熵 $H(Y|X)$ 之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益大的特征具有更强的分类能力。
信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在分类问题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。
信息增益比 $g_R(D,A)$ 定义为特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$ 与训练数据集 $D$ 经验熵 $H(D)$ 之比：
$g_R(D,A) = \frac{g(D,A)}{H(D)}$

决策树的生成

ID3 算法
输入：训练数据集 $D$ ，特征集 $A$ ，阈值 $\xi$ ；
输出：决策树 $T$
1>> 若 $D$ 中所有实例属于同一类 $C_k$ ，则 $T$ 为单结点树，并将类 $C_k$ 作为该结点的类标记，返回 $T$ ；
2>> 若 $A＝\emptyset$ ，则 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；
3>> 否则，计算 $A$ 中各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A_g$ ；
4>> 如果 $A_g$ 的信息增益小于阈值 $\xi$ ，则置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；
5>> 否则，对 $A_g$ 的每一可能值 $a_i$ ，依 $A_g＝a_i$ 将 $D$ 分割为若干非空子集 $D_i$ ，将 $D_i$ 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 $T$ ，返回 $T$ ；
6>> 对第 $i$ 个子结点，以 $D_i$ 为训练集，以 $A{A_g}$ 为特征集，递归地调用 1>>~5>>，得到子树 $T_i$ ，返回 $T_i$ 。
C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成的过程中，用信息增益比来选择特征。

决策树的剪枝

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。
在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning）。具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。
设树 $T$ 的叶结点个数为 $\mid T \mid$ ， $t$ 是树 $T$ 的叶结点，该叶结点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个， $k=1,2,...,K$ ， $H_t(T)$ 为叶结点 $t$ 上的经验熵， $\alpha \ge 0$ 为参数，则决策树学习的损失函数可定义为
$C_\alpha(T) = \sum_{t=1}^{\mid T \mid} N_tH_t(T) + \alpha \mid T \mid$
其中经验熵为
$H_t(T) = -\sum_k\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}$
我们将
$C(T) = \sum_{t=1}^{\mid T \mid} N_tH_t(T) = -\sum_{t=1}^{\mid T \mid} \sum_{k=1}^KN_{tk} \log \frac{N_{tk}}{N_t}$
这时有
$C_\alpha(T) = C(T) + \alpha \mid T \mid$
式中， $C(T)$ 表示模型对训练数据的预测误差，即模型与训练数据的拟合程度， $\mid T \mid$ 表示模型复杂度，参数 $\alpha \ge 0$ 控制两者之间的影响。
树的剪枝算法
输入：生成算法产生这个树 $T$ ，参数 $\alpha$
输出：修剪后的子树 $T_a$
1>> 计算每个结点的经验熵。
2>> 递归地从树的叶结点向上回缩。设一组叶结点回缩到其父结点之前与之后的整体树分别为 $T_B$ 与 $T_A$ ，其对应的损失函数值分别是 $C_a(T_B)$ 与 $C_a(T_A)$ ，如果 $C_a(T_A) \le C_a(T_B)$ ，则进行剪枝，即将父结点变为新的叶结点。
3>> 返回 2>>，直到不能继续为止，得到损失函数最小的子树 $T_a$ 。

CART 算法

分类与回归树（classification and regression tree，CART）是在给定输入随机变量 $X$ 条件下输出随机变量 $Y$ 的条件概率分布的学习方法。
CART 算法由以下两步组成：
1>> 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
2>> 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
CART 的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。
假设已将输入空间划分为 $M$ 个单元 $R_1,R_2,...,R_M$ ，并且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$ ，于是回归树模型可表示为
$f(x) = \sum_{m=1}^M c_m I(x \in R_m)$
当输入空间划分确定时，可以用平方误差 $\sum_{x_i \in R_m} (y_i - f(x_i))^2$ 来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。
单元 $R_m$ 上的 $c_m$ 的最优值 $\hat{c}_m$ 是 $R_m$ 上的所有输入实例 $x_i$ 对应的输出 $y_i$ 的均值，即
$\hat{c}_m = ave(y_i \mid x_i \in R_m)$
最小二乘回归树生成算法
输入：训练数据集 $D$
输出：回归树 $f(x)$
1>> 遍历变量 $j$ ，对固定的切分变量 $j$ 扫描切分点，求解
$min_{j,s} \ \ \ [\ \ \ min_{c_1} \sum_{x_i \in R_1(j,s)}(y_i - c_1)^2 \ \ \ + \ \ \ min_{c_2} \sum_{x_i \in R_2(j,s)}(y_i - c_2)^2 \ \ \ ]$
得到最优切分变量 $j$ 与切分点 $s$ 。
2>> 用选定的 $(j,s)$ 划分区域并决定响应的输出值
$R_1(j,s) = \{x\mid x^{(j)} \le s \}, \ \ \ \ \ R_2(j,s) = \{x\mid x^{(j)} \gt s \} \\ \hat{c}_m = \frac{1}{N_m} \sum_{x_i \in R_m(j,s)} y_i, \ \ \ \ \ x \in R_m, \ \ \ \ \ m=1,2$
3>> 继续对两个子区域调用步骤 1>> 和 2>>，直至满足停止条件。
4>> 将输入空间划分 $M$ 个区域 $R_1,R_2,...,R_m$ ，生成决策树：
$f(x) = \sum_{m=1}^M \hat{c}_m I( x \in R_m)$
分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$ ，则概率分布的基尼指数定义为
$Gini(p) = \sum_{k=1}^Kp_k(1-p_k) = 1- \sum_{k=1}^Kp_k^2$
对于给定的样本集合 $D$ ，其基尼指数为
$Gini(D) = 1-\sum_{k=1}^K(\frac{\mid C_k \mid}{ \mid D \mid })^2$
这里， $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集， $K$ 是类的个数。
如果样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分，则在特征 $A$ 的条件下，集合 $D$ 的基尼指数定义为
$Gini(D,A)=\frac{\mid D_1 \mid}{\mid D \mid}Gini(D_1) + \frac{ \mid D_2 \mid}{\mid D \mid}Gini(D_2)$
基尼指数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼指数 $Gini(D,A)$ 表示经 $A＝a$ 分割后集合 $D$ 的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似。直观来说， $Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此， $Gini(D)$ 越小，则数据集 $D$ 的纯度越高。
分类树生成算法
输入：训练数据集 $D$ ，停止计算的条件；
输出：CART 决策树。
1>> 设结点的训练数据集为 $D$ ，计算现有特征对该数据集的基尼指数。此时，对每一个特征 $A$ ，对其可能取的每个值 $a$ ，根据样本点对 $A＝a$ 的测试为“是”或“否”将 $D$ 分割成 $D_1$ 和 $D_2$ 两部分，计算 $A＝a$ 时的基尼指数。
2>> 在所有可能的特征 $A$ 以及它们所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
3>> 对两个子结点递归地调用 1>> 和 2>>，直至满足停止条件。
4>> 生成 CART 决策树。
算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。
对固定的 $\alpha$ ，一定存在使损失函数 $C_\alpha(T)$ 最小的子树，将其表示为 $T_a$ 。 $T_a$ 在损失函数 $C_\alpha(T)$ 最小的意义下是最优的。容易验证这样的最优子树是唯一的。当 $\alpha$ 大的时候，最优子树 $T_a$ 偏小；当 $\alpha$ 小的时候，最优子树 $T_a$ 偏大。极端情况，当 $\alpha＝0$ 时，整体树是最优的。当 $a\rightarrow \infty$ 时，根结点组成的单结点树是最优的。
将 $\alpha$ 从小增大， $0＝\alpha_0<\alpha_1<…<\alpha_n<+\infty$ ，产生一系列的区间 $[\alpha_i,\alpha_{i+1}), \ i＝0,1,…,n$ ；剪枝得到的子树序列对应着区间 $\alpha \in [\alpha_i,\alpha_{i+1}), \ i＝0,1,…,n$ 的最优子树序列 ${T_0，T_1,…,T_n}$ ，序列中的子树是嵌套的。然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
从整体树 $T_0$ 开始剪枝，对 $T_0$ 的任意内部结点 $t$ , 以 $t$ 为单结点树的损失函数是
$C_\alpha(t) = C(t) + \alpha$
以 $t$ 为根节点的子树 $T_t$ 的损失函数是
$C_\alpha(T_t) = C(T_t) + \alpha\mid T_t \mid$
当 $\alpha = 0$ 或者 $\alpha$ 充分小时，有不等式
$C_\alpha(T_t) \lt C_\alpha(t)$
当 $\alpha$ 增大时，在某一 $\alpha$ 有
$C_\alpha(T_t) = C_\alpha(t)$
所以只要 $\alpha = \frac{C(t)-C(T_t)}{\mid T_t \mid -1}$ ， $T_t$ 与 $t$ 有相同的损失函数值，而 $t$ 的结点少，因此 $t$ 比 $T_t$ 更可取，对 $T_t$ 进行剪枝。
因此，对 $T_0$ 中的每个内部结点 $t$ ，计算
$g(t) = \frac{C(t)-C(T_t)}{\mid T_t \mid -1}$
它表示剪枝后整体损失函数减少的程度。在 $T_0$ 中剪去 $g(t)$ 最小的 $T_t$ ，将得到的子树作为 $T_1$ ，同时将最小的 $g(t)$ 设为 $\alpha_1$ 。 $T_1$ 为区间 $[\alpha_1,\alpha_2)$ 的最优子树。
如此剪枝下去，直至得到根结点。在这一过程中，不断地增加 $\alpha$ 的值，产生新的区间。
CART 剪枝算法
输入： CART 算法生成的决策树 $T_0$ ；
输出：最优决策树 $T_\alpha$
1>> 设 $k=0, T=T_0$ 。
2>> 设 $\alpha=+\infty$ 。
3>> 自下而上地对各内部结点 $t$ 计算 $C(T_t)$ ， $\mid T_t \mid$ 以及 $g(t)$ ，并令 $\alpha = min(\alpha, g(t))$ 。
4>> 自上而下地访问内部结点t，如果有 $g(t)＝\alpha$ ，进行剪枝，并对叶结点 $t$ 以多数表决法决定其类，得到树 $T$ 。
5>> 设 $k=k+1, \alpha_k=\alpha, T_k=T$ 。
6>> 如果 $T$ 不是由根结点单独构成的树，则回到步骤 4>>。
7>> 采用交叉验证法在子树序列 $T_0,T_1,…,T_n$ 中选取最优子树 $T_\alpha$

决策树模型实现

import json
import numpy as np
import pandas as pd
from collections import Counter
from math import log


class Node(object):
    def __init__(self, leaf=False, value=None):
        self.leaf = leaf # 是否为叶节点
        self.value = value # 经最大信息增益特征划分后的特征值
        self.label = None # 当前节点所属类
        self.feature = None # 当前节点数据最大信息增益特征
        self.feature_name = None # 当前节点数据最大信息增益特征名称
        self.alllabels = None # 当前节点包含的所有实例的标签数据
        self.childs = [] # 子节点
    
    # 添加子节点
    def append(self, node):
        self.childs.append(node)
    
    # 预测数据所属类别
    def predict(self, features):
        if self.leaf: return self.label
        for child in self.childs:
            if child.value == features[self.feature]:
                return child.predict(features)
    
    def printf(self, idepth=0):
        string = "节点值:%s, 类标签:%s, 特征名称:%s" % (
            self.value, self.label, self.feature_name)
        if not self.childs:
            return string
        else:
            idepth += 1
            for child in self.childs:
                string += '\n'
                string += '\t' * idepth
                string += child.printf(idepth)
        return string


class DecisonTree(object):
    def __init__(self, epsilon=0.1, alpha=0.1):
        self.epsilon = epsilon
        self.alpha = alpha
        self.tree = Node()

    # 计算熵
    def calc_entropy(self, datasets):
        length = len(datasets)
        counter = Counter(d[-1] for d in datasets)
        return -sum([(c / length) * log(c / length, 2) for c in counter.values()])
    
    # 计算条件熵
    def calc_conditional_entropy(self, datasets, axis=0):
        length = len(datasets)
        features = {}
        for d in datasets:
            features.setdefault(d[axis], []).append(d)
        return sum([(len(f) / length) * self.calc_entropy(f) for f in features.values()])
    
    # 计算信息增益
    def calc_information_gain(self, entropy, conditional_entropy):
        return entropy - conditional_entropy
    
    # 计算最大信息增益及其特征
    def calc_max_information_gain(self, datasets):
        count = len(datasets[0]) - 1
        entropy = self.calc_entropy(datasets)
        features = []
        for i in range(count):
            information_gain = self.calc_information_gain(entropy, self.calc_conditional_entropy(datasets, axis=i))
            features.append((i, information_gain))
        return max(features, key=lambda x: x[-1])
    
    def train(self, train_data, node):
        y_train, features = train_data.iloc[:, -1], train_data.columns[:-1]
        
        # 若训练数据属于同一类别 CK， 则决策树 T 为单节点树，并将类 CK 作为节点的类标记
        if len(y_train.value_counts()) == 1:
            node.leaf = True
            node.label = y_train.iloc[0]
            node.alllabels = y_train
            return
        
        # 特征为空，则 T 为单节点树，将训练数据中，最大实例数的类 CK 作为该节点的类标记
        if len(features) == 0:
            node.leaf = True
            node.label = y_train.value_counts().sort_values(ascending=False).index[0]
            node.alllabels = y_train
            return
        
        # 计算信息增益最大的特征
        max_feature_index, max_information_gain = self.calc_max_information_gain(np.array(train_data))
        max_feature_name = features[max_feature_index]
        
        # 最大的信息增益小于阈值，则置 T 为单节点树，将训练数据中，最大实例数的类 CK 作为该节点的类标记
        if max_information_gain < self.epsilon:
            node.leaf = True
            node.label = y_train.value_counts().sort_values(ascending=False).index[0]
            node.alllabels = y_train
            return
        
        feature_values = train_data[max_feature_name].value_counts().index
        # 递归生成树
        for fv in feature_values:
            node.feature = max_feature_index
            node.feature_name = max_feature_name
            sub_node = Node(leaf=False, value=fv)
            sub_train_data = train_data.loc[train_data[max_feature_name] == fv].drop([max_feature_name], axis=1)
            node.append(sub_node)
            self.train(sub_train_data, sub_node)

    def fit(self, datasets):
        self.train(datasets, self.tree)
    
    # 找到所有叶节点
    def leafs(self, node, leafs):
        for child in node.childs:
            if child.leaf:
                leafs.append(child.alllabels)
            else:
                self.leafs(child)
    
    # 计算预测误差 C(T)
    def calc_predict_error(self):
        leafs = []
        self.leafs(self.tree, leafs)
        leafnum = [len(leaf) for leaf in leafs]
        entropy = [self.calc_entropy(leaf) for leaf in leafs]
        error = self.alpha * len(leafs)
        return sum(l * e for l, e in zip(leafnum, entropy)) + error
    
    # 剪枝
    def cut(self, alpha):
        if alpha: self.alpha = alpha
        minerror = self.calc_predict_error()
        self._cutting(self.tree, minerror)
    
    def _cutting(self, node, minerror):
        if node.feature is not None:
            childs_label = [child.label for child in node.childs]
            # 如果子节点全部为叶节点
            if None not in childs_label:
                childs_alllabels = []
                for child in node.childs:
                    childs_alllabels.extend(child.alllabels)
                childs_counter = Counter(childs_alllabels)
                
                # 剪枝前备份一下数据
                _leaf = node.leaf
                _feature = node.feature
                _label = node.label
                _alllabels = node.alllabels
                _childs = node.childs
                
                #剪枝
                node.leaf = True
                node.feature = None
                node.label = childs_counter.most_common(1)[0][0]
                node.alllabels = childs_alllabels
                node.childs = []
                
                # 剪枝前后进行误差比较
                predict_error = self.calc_predict_error()
                if predict_error <= minerror:
                    minerror = predict_error
                    return 1
                else:
                    node.leaf = _leaf
                    node.feature = _feature
                    node.label = _label
                    node.alllabels = _alllabels
                    node.childs = _childs
            else:
                retry = 0
                i = 0
                while i < len(node.childs):
                    # 剪枝之后，父节点需要重新检测，循环回退一步
                    if_retry = self._cutting(node.childs[i], minerror)
                    if if_retry == 1:
                        retry = 1
                    elif if_retry == 2:
                        i -= 1
                    i += 1
                if retry:
                    return 2


if __name__ == '__main__':
    datasets = np.array([['青年', '否', '否', '一般', '否'],
                   ['青年', '否', '否', '好', '否'],
                   ['青年', '是', '否', '好', '是'],
                   ['青年', '是', '是', '一般', '是'],
                   ['青年', '否', '否', '一般', '否'],
                   ['中年', '否', '否', '一般', '否'],
                   ['中年', '否', '否', '好', '否'],
                   ['中年', '是', '是', '好', '是'],
                   ['中年', '否', '是', '非常好', '是'],
                   ['中年', '否', '是', '非常好', '是'],
                   ['老年', '否', '是', '非常好', '是'],
                   ['老年', '否', '是', '好', '是'],
                   ['老年', '是', '否', '好', '是'],
                   ['老年', '是', '否', '非常好', '是'],
                   ['老年', '否', '否', '一般', '否'],
                   ['青年', '否', '否', '一般', '是']])

    datalabels = np.array(['年龄', '有工作', '有自己的房子', '信贷情况', '类别'])
    train_data = pd.DataFrame(datasets, columns=datalabels)
    test_data = ['老年', '否', '否', '一般']

    dt = DecisonTree()
    dt.fit(train_data)
    print('剪枝前:')
    print(dt.tree.printf())

    y = dt.tree.predict(test_data)
    print('预测结果:', y)

    dt.cut(alpha=0.5)
    print('剪枝后:')
    print(dt.tree.printf())
    y = dt.tree.predict(test_data)
    print('预测结果:', y)

运行结果

也可以使用 sklearn 实现决策树模型

from sklearn.tree import DecisionTreeClassifier
dtc = DecisionTreeClassifier()
dtc.fit(x_train, y_train,)
"""
DecisionTreeClassifier(class_weight=None, criterion='gini', max_depth=None,
            max_features=None, max_leaf_nodes=None,
            min_impurity_decrease=0.0, min_impurity_split=None,
            min_samples_leaf=1, min_samples_split=2,
            min_weight_fraction_leaf=0.0, presort=False, random_state=None,
            splitter='best')
"""
score(x_test, y_test)

最后编辑于：2019.02.19 11:34:42

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,088评论 5赞 459
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,715评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,361评论 0赞 319
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,099评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 60,987评论 4赞 355
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,063评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,486评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,175评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,440评论 1赞 290
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,518评论 2赞 309
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,305评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,190评论 3赞 312
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,550评论 3赞 298
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,880评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,152评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,451评论 2赞 341
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,637评论 2赞 335

决策树

决策树模型与学习

特征选择

决策树的生成

决策树的剪枝

CART 算法

决策树模型实现

推荐阅读更多精彩内容