经典机器学习算法-第五章决策树

NeighborMrSun 2023-02-27 发布于湖南

展开全文

一、决策树基本原理

决策树基于树结构，从顶往下，依次对样本的（一个或多个）属性进行判断，直到决策树的叶节点并导出最终结果。

二、损失函数

按照ID3或C4.5算法生成的决策树，可能对训练数据集有比较好的准确度，但是对未知数据的预测能力却不一定比较好，因为在训练过程中为了拟合训练数据而构造了很复杂的决策树的话，就会产生过拟合。解决这一问题的方法就是对决策树进行剪枝。

剪枝的目的是为了同时兼顾模型对训练集的拟合程度以及减少模型的复杂度来提高预测能力，那就不能仅仅使用信息增益来判别，还要加入带有模型复杂度的项对过于复杂的模型进行惩罚。

在这里定义决策树的损失函数(代价函数)：

设叶节点个数为|T|，t是T的叶节点，该叶节点有Nt个样本，其中k类的样本有Ntk个，k=1,2,3,…K，Ht(T)为叶节点上t的经验熵，α>=0为参数,则决策树学习的损失函数可以定义为：

其中经验熵为：

解释

损失函数计算的是每个叶节点的样本数和每个叶节点的经验熵的乘积的累加和最终加上以叶节点个数为基础的惩罚项。

三、特征选择方法

为了能够构建一棵分类性能良好的决策树，我们需要从训练集中不断选取具有分类能力的特征。如果用一个特征对数据集进行分类的效果与随机选取的分类效果并无差异，我们可以认为该特征对数据集的分类能力是低下的；反之，如果一个特征能够使得分类后的分支结点尽可能属于同一类别即该结点有着较高的纯度( purity)，那么该特征对数据集而言就具备较强的分类能力。决策树的特征选择就是从数据集中选择具备较强分类能力的特征来对数据集进行划分，那么什么样的特征才是具备较强分类能力的特征呢?换言之，我们应该按照什么标准来选取最优特征?

在决策树模型中，我们有三种方式来选取最优特征，包括信息增益、信息增益比和基尼指数

3.1信息增益

信息增益定义为由于得到特征X的信息而使得类Y的信息不确定性减少的程度，即信息增益是一种描述类别确定性增加的量，特征的信息增益越大，目标类的确定性越大。

举例：

X(明天下雨)是一个随机变量，X的熵1

Y(明天阴天)也是随机变量，在阴天情况下下雨的信息熵假设为0.3（此处需要知道其联合概率分布或是通过数据估计）即是条件熵。

信息增益=X的熵-Y条件下X的熵=0.7。

在获得阴天这个信息后，下雨信息不确定性减少了0.7，不确定减少了很多，所以信息增益大。也就是说，阴天（即特征）这个信息对明天下午这一推断来说非常重要。

假设训练集D的经验熵为E(D)，给定特征A的条件下D的经验条件熵为E(D|A)，那么信息增益可以定义为经验熵E(D)和经验条件熵E(D|A)之差：

g(D,A)=E(D)-E(D|A)

假设样本数据集D中第k个类比所占比例为pk,则样本数据集的经验熵E(D)为：

假设离散随机变量(X.y)的联合概率分布为：

条件熵E(YIX)表示在已知随机变量X的条件下Y的不确定性的度量，E(Y|X)可定义为在给定X的条件下Y的条件概率分布的对X的数学期望。条件可以表示为:

其中pi= P(X=xi)，i=2··,n。在利用实际数据进行计算时，熵和条件熵中的概率计算都是基于极大似然估计得到，对应的熵和条件熵也叫经验熵和经验条件熵。

信息熵的计算函数：

def entropy(ele): ''' ele:包含类别取值的列表 return 信息熵值 ''' # 计算列表中取值的概率分布 probs = [ele.count(i)/len(ele) for i in set(ele)] # 计算信息熵值 entropy = -sum([prob*log(prob, 2) for prob in probs]) return entropy

计算上述例子的信息增益：

3.2信息增益比

信息增益有时会倾向于有更多取值范围的那个特征（如，是否有工作的取值范围为“是”or“否”；信贷情况的取值范围为“一般”，“好”，“非常好”，此时 3 > 2，有可能会造成 “信贷情况” 的信息增益大于 “是否有工作” 这个特征）

使用信息增益比可以对这个问题进行校正。特征A对数据集D的信息增益比等于特征A的信息增益g(D,A)与数据集D关于A取值的熵Ea(D)的比值。

n为特征A取值的个数。

3.3基尼系数

除信息增益和信息增益比外，基尼指数 (Gini index )也是一种较好的特征选择方法。基尼指数是针对概率分布而言的。假设样本有 K个类，样本属于第类的概率为 P，则该样本类别概率分布的基尼指数可定义为:

对于给定训练集 D，Ck是属于第k类样本的集合，则该训练集的基尼指数可定义为:

如果训练集 D根据特征 A某一取值a分为D1和D2两个部分，那在特征A这个条件下训练集 D的基尼指数可定义为:

与信息熵的定义类似，训练集 D的基尼指数 Gini(D) 表示该集合的不确定性，Gini(D，A)表示训练集 D经过 A =a 划分后的不确定性。对于分类任务而言，我们希望训练集的不确定性越小越好,即Gini(D，4)越小,对应的特征对训练样本的分类能力越强。在经典的决策树算法中CART算法是基于信息增益比进行特征选择的。

### 计算基尼指数def calculate_gini(y):    # 将数组转化为列表    y = y.tolist()    probs = [y.count(i)/len(y) for i in np.unique(y)]    gini = sum([p*(1-p) for p in probs])    return gini

计算上例中天气特征下的基尼系数

四、决策树模型

基于信息增益、信息增益比和基尼指数三种特征选择方法，分别有 ID3、C.5和CART 三种经典的决策树算法。这三种算法在构造分类决策树时方法基本一致，都是通过特征选择方法递归地选择最优特征进行构造。其中 ID3 和 C4.5 算法只有决策的生成，不括决策枝部分所以这两种算法有时候容易过拟合。CART 算法除用于分类外，还可用于回归，并且该算法是包括决策树剪枝的。

4.1 ID3

ID3算法的全称为 Iterative Dichotomiser3，即 3 代迭代二叉树。其核心是基于信息增益递归地选择最优特征构造决策树。

具体方法如下:首先预设一个决策树根结点，然后对所有特征计算信息增益，选择一个信息增益最大的特征作为最优特征，根据该特征的不同取值建立子结点，接着对每个子结点递归地调用上述方法，直到信息增益很小或者没有特征可选时，即可构建最终的 ID3 决策树。

给定训练集 D、特征集合A以及信息增益阈值，ID3 算法的流程可以作如下描述：

(1) 如果 D中所有实例属于同一类别 Ck，那所构建的决策树 T为单结点树，并且类Ck即为该结点的类的标记。

(2) 如果 T不是单结点树，则计算特征集合 4 中各特征对 D的信息增益，选择信息增益最大的特征 Ag。

(3)如果 A的信息增益小于阈值，则将 T视为单结点树，并将 D中所属数量最多的类Ck作为该结点的类的标记并返回T。

(4)否则，可对Ag的每一特征取值ai，按照Ag =ai将 D划分为若干非空子集 Di，以Di中所属数量最多的类作为标记并构建子结点，由结点和子结点构成树 T并返回。

(5) 对第i个子结点，以Di为训练集，以 A- Ag为特征集，递归地调用(1)-(4)步，即可得到决策树子树Ti并返回。

下面基于以上 ID3算法流程和 7.32 节定的信息增益函数，并在新定义一些辅助函数的基础上，尝试实现ID3算法。

import numpy as npimport pandas as pdfrom math import log

df = pd.read_csv('./example_data.csv', dtype={'windy': 'str'})df

计算信息熵

def entropy(ele): probs = [ele.count(i)/len(ele) for i in set(ele)] entropy = -sum([prob*log(prob, 2) for prob in probs]) return entropy

entropy(df['play'].tolist())

根据特征值划分训练集

def split_dataframe(data, col): unique_values = data[col].unique() result_dict = {elem : pd.DataFrame for elem in unique_values} for key in result_dict.keys(): result_dict[key] = data[:][data[col] == key] return result_dict

split_example = split_dataframe(df, 'temp')

for item, value in split_example.items():    print(item, value)

根据最大信息增益选择最佳分割特征：

def choose_best_col(df, label): entropy_D = entropy(df[label].tolist()) cols = [col for col in df.columns if col not in [label]] max_value, best_col = -999, None max_splited = None for col in cols: splited_set = split_dataframe(df, col) entropy_DA = 0 for subset_col, subset in splited_set.items(): entropy_Di = entropy(subset[label].tolist()) entropy_DA += len(subset)/len(df) * entropy_Di info_gain = entropy_D - entropy_DA if info_gain > max_value: max_value, best_col = info_gain, col max_splited = splited_set return max_value, best_col, max_splited choose_best_col(df, 'play')

构建ID3决策树

class ID3Tree:    class Node:        def __init__(self, name):            self.name = name            self.connections = {}
        def connect(self, label, node):            self.connections[label] = node                def __init__(self, data, label):        self.columns = data.columns        self.data = data        self.label = label        self.root = self.Node('Root')            def print_tree(self, node, tabs):        print(tabs + node.name)        for connection, child_node in node.connections.items():            print(tabs + '\t' + '(' + connection + ')')            self.print_tree(child_node, tabs + '\t\t')
    def construct_tree(self):        self.construct(self.root, '', self.data, self.columns)            def construct(self, parent_node, parent_connection_label, input_data, columns):        max_value, best_col, max_splited = choose_best_col(input_data[columns], self.label)                if not best_col:            node = self.Node(input_data[self.label].iloc[0])            parent_node.connect(parent_connection_label, node)            return
        node = self.Node(best_col)        parent_node.connect(parent_connection_label, node)                new_columns = [col for col in columns if col != best_col]                for splited_value, splited_data in max_splited.items():            self.construct(node, splited_value, splited_data, new_columns)

4.2 C4.5

C4.5算法整体上和ID3算法极为相似，不同之处在于构造决策树时采用信息增益比作为特征选择方法。C4.5算法构造出来的决策树也称为C4.5决策树。流程和代码参考ID3.

4.3 CART决策树

CART决策树采用基尼系数进行特征选择，既可用于分类，也可用于回归。

4.3.1 CART分类树算法具体流程

　　CART分类树建立算法流程，之所以加上建立，是因为CART分类树算法有剪枝算法流程。

　　算法输入训练集D，基尼系数的阈值，样本个数阈值。

　　输出的是决策树T。

　　算法从根节点开始，用训练集递归建立CART分类树。

　　(1)、对于当前节点的数据集为D，如果样本个数小于阈值或没有特征，则返回决策子树，当前节点停止递归。

　　(2)、计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。

　　(3)、计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数，对于离散值和连续值的处理方法和基尼系数的计算见第二节。缺失值的处理方法和C4.5算法里描述的相同。

　　(4)、在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2。

　　(5)、对左右的子节点递归的调用1-4步，生成决策树。

　　对生成的决策树做预测的时候，假如测试集里的样本A落到了某个叶子节点，而节点里有多个训练样本。则对于A的类别预测采用的是这个叶子节点里概率最大的类别。

例：根据下表所给的训练集，应用CART算法生成决策树。

CART分类树算法对连续特征和离散特征的处理

　　CART分类树算法对连续值的处理，思想和C4.5相同，都是将连续的特征离散化。唯一区别在选择划分点时，C4.5是信息增益比，CART是基尼系数。

　　具体思路：m个样本的连续特征A有m个，从小到大排列a1，a2，......，am，则CART取相邻两样本值的平均数做划分点，一共取m-1个，其中第i个划分点Ti表示为：Ti = (ai + ai+1)/2。分别计算以这m-1个点作为二元分类点时的基尼系数。选择基尼系数最小的点为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为at，则小于at的值为类别1，大于at的值为类别2，这样就做到了连续特征的离散化。

　　注意的是，与ID3、C4.5处理离散属性不同的是，如果当前节点为连续属性，则该属性在后面还可以参与子节点的产生选择过程。

　　CART分类树算法对离散值的处理，采用的思路：不停的二分离散特征。

　　在ID3、C4.5，特征A被选取建立决策树节点，如果它有3个类别A1,A2,A3，我们会在决策树上建立一个三叉点，这样决策树是多叉树。

　　CART采用的是不停的二分。会考虑把特征A分成{A1}和{A2,A3}、{A2}和{A1,A3}、{A3}和{A1,A2}三种情况，找到基尼系数最小的组合，比如{A2}和{A1,A3}，然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的样本。由于这次没有把特征A的取值完全分开，后面还有机会对子节点继续选择特征A划分A1和A3。这和ID3、C4.5不同，在ID3或C4.5的一颗子树中，离散特征只会参与一次节点的建立。

4.3.2CART回归树算法具体流程

　　CART回归树和CART分类树的建立类似，这里只说不同。

　　(1)、分类树与回归树的区别在样本的输出，如果样本输出是离散值，这是分类树；样本输出是连续值，这是回归树。分类树的输出是样本的类别，回归树的输出是一个实数。

　　(2)、连续值的处理方法不同。

　　(3)、决策树建立后做预测的方式不同。

　　分类模型：采用基尼系数的大小度量特征各个划分点的优劣。

　　回归模型：采用和方差度量，度量目标是对于划分特征A，对应划分点s两边的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小。表达式为：

其中，c1为D1的样本输出均值，c2为D2的样本输出均值。

　　对于决策树建立后做预测的方式，CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。回归树输出不是类别，采用叶子节点的均值或者中位数来预测输出结果。

手动构建CART树

import numpy as npfrom sklearn.model_selection import train_test_splitfrom sklearn.metrics import accuracy_score, mean_squared_errorfrom utils import feature_split, calculate_gini

### 定义树结点class TreeNode():    def __init__(self, feature_i=None, threshold=None,                 leaf_value=None, left_branch=None, right_branch=None):        # 特征索引        self.feature_i = feature_i                  # 特征划分阈值        self.threshold = threshold         # 叶子节点取值        self.leaf_value = leaf_value           # 左子树        self.left_branch = left_branch             # 右子树        self.right_branch = right_branch

### 定义二叉决策树class BinaryDecisionTree(object): ### 决策树初始参数 def __init__(self, min_samples_split=2, min_gini_impurity=999, max_depth=float('inf'), loss=None): # 根结点 self.root = None # 节点最小分裂样本数 self.min_samples_split = min_samples_split # 节点初始化基尼不纯度 self.mini_gini_impurity = min_gini_impurity # 树最大深度 self.max_depth = max_depth # 基尼不纯度计算函数 self.gini_impurity_calculation = None # 叶子节点值预测函数 self._leaf_value_calculation = None # 损失函数 self.loss = loss

### 决策树拟合函数 def fit(self, X, y, loss=None): # 递归构建决策树 self.root = self._build_tree(X, y) self.loss=None

### 决策树构建函数 def _build_tree(self, X, y, current_depth=0): # 初始化最小基尼不纯度 init_gini_impurity = 999 # 初始化最佳特征索引和阈值 best_criteria = None # 初始化数据子集 best_sets = None

# 合并输入和标签 Xy = np.concatenate((X, y), axis=1) # 获取样本数和特征数 n_samples, n_features = X.shape # 设定决策树构建条件 # 训练样本数量大于节点最小分裂样本数且当前树深度小于最大深度 if n_samples >= self.min_samples_split and current_depth <= self.max_depth: # 遍历计算每个特征的基尼不纯度 for feature_i in range(n_features): # 获取第i特征的所有取值 feature_values = np.expand_dims(X[:, feature_i], axis=1) # 获取第i个特征的唯一取值 unique_values = np.unique(feature_values)

# 遍历取值并寻找最佳特征分裂阈值 for threshold in unique_values: # 特征节点二叉分裂 Xy1, Xy2 = feature_split(Xy, feature_i, threshold) # 如果分裂后的子集大小都不为0 if len(Xy1) > 0 and len(Xy2) > 0: # 获取两个子集的标签值 y1 = Xy1[:, n_features:] y2 = Xy2[:, n_features:]

# 计算基尼不纯度 impurity = self.impurity_calculation(y, y1, y2)

# 获取最小基尼不纯度 # 最佳特征索引和分裂阈值 if impurity < init_gini_impurity: init_gini_impurity = impurity best_criteria = {'feature_i': feature_i, 'threshold': threshold} best_sets = { 'leftX': Xy1[:, :n_features], 'lefty': Xy1[:, n_features:], 'rightX': Xy2[:, :n_features], 'righty': Xy2[:, n_features:] } # 如果计算的最小不纯度小于设定的最小不纯度 if init_gini_impurity < self.mini_gini_impurity: # 分别构建左右子树 left_branch = self._build_tree(best_sets['leftX'], best_sets['lefty'], current_depth + 1) right_branch = self._build_tree(best_sets['rightX'], best_sets['righty'], current_depth + 1) return TreeNode(feature_i=best_criteria['feature_i'], threshold=best_criteria[ 'threshold'], left_branch=left_branch, right_branch=right_branch)

# 计算叶子计算取值 leaf_value = self._leaf_value_calculation(y)

return TreeNode(leaf_value=leaf_value)

### 定义二叉树值预测函数 def predict_value(self, x, tree=None): if tree is None: tree = self.root

# 如果叶子节点已有值，则直接返回已有值 if tree.leaf_value is not None: return tree.leaf_value

# 选择特征并获取特征值 feature_value = x[tree.feature_i]

# 判断落入左子树还是右子树 branch = tree.right_branch if isinstance(feature_value, int) or isinstance(feature_value, float): if feature_value >= tree.threshold: branch = tree.left_branch elif feature_value == tree.threshold: branch = tree.left_branch

# 测试子集 return self.predict_value(x, branch)

### 数据集预测函数 def predict(self, X): y_pred = [self.predict_value(sample) for sample in X] return y_pred

### CART回归树class RegressionTree(BinaryDecisionTree):    def _calculate_variance_reduction(self, y, y1, y2):        var_tot = np.var(y, axis=0)        var_y1 = np.var(y1, axis=0)        var_y2 = np.var(y2, axis=0)        frac_1 = len(y1) / len(y)        frac_2 = len(y2) / len(y)        # 计算方差减少量        variance_reduction = var_tot - (frac_1 * var_y1 + frac_2 * var_y2)                return sum(variance_reduction)
    # 节点值取平均    def _mean_of_y(self, y):        value = np.mean(y, axis=0)        return value if len(value) > 1 else value[0]
    def fit(self, X, y):        self.impurity_calculation = self._calculate_variance_reduction        self._leaf_value_calculation = self._mean_of_y        super(RegressionTree, self).fit(X, y)

### CART决策树class ClassificationTree(BinaryDecisionTree): ### 定义基尼不纯度计算过程 def _calculate_gini_impurity(self, y, y1, y2): p = len(y1) / len(y) gini = calculate_gini(y) gini_impurity = p * calculate_gini(y1) + (1-p) * calculate_gini(y2) return gini_impurity ### 多数投票 def _majority_vote(self, y): most_common = None max_count = 0 for label in np.unique(y): # 统计多数 count = len(y[y == label]) if count > max_count: most_common = label max_count = count return most_common # 分类树拟合 def fit(self, X, y): self.impurity_calculation = self._calculate_gini_impurity self._leaf_value_calculation = self._majority_vote super(ClassificationTree, self).fit(X, y)

测试：

from sklearn import datasetsdata = datasets.load_iris()X, y = data.data, data.targetX_train, X_test, y_train, y_test = train_test_split(X, y.reshape(-1,1), test_size=0.3)clf = ClassificationTree()clf.fit(X_train, y_train)y_pred = clf.predict(X_test)
print(accuracy_score(y_test, y_pred))

from sklearn.datasets import load_bostonX, y = load_boston(return_X_y=True)X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)model = RegressionTree()model.fit(X_train, y_train)y_pred = model.predict(X_test)mse = mean_squared_error(y_test, y_pred)

print('Mean Squared Error:', mse)

五、决策树剪枝

在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得'太好'了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合（在训练集中表现很好，但是在测试集中表现很差）。因此，可通过主动去掉一些分支来降低过拟合的风险。

决策树剪枝的基本策略有'预剪枝' (pre-pruning)和'后剪枝'(post- pruning) 。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点;后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

5.1 预剪枝

首先，基于信息增益准则，我们会选取属性'脐部'来对训练集进行划分，并产生 3 个分支，如下图所示。然而，是否应该进行这个划分呢？预剪枝要对划分前后的泛化性能进行估计。

在划分之前，所有样例集中在根结点。

*若不进行划分，该结点将被标记为叶结点，其类别标记为训练样例数最多的类别，假设我们将这个叶结点标记为'好瓜'。

*用前面表的验证集对这个单结点决策树进行评估。则编号为 {4，5，8} 的样例被分类正确。另外 4个样例分类错误，于是验证集精度为\frac{3}{7}*100% = 42.9%73∗100%=42.9%。

在用属性'脐部'划分之后，上图中的结点2、3、4分别包含编号为 {1，2，3， 14}、 {6，7， 15， 17}、 {10， 16} 的训练样例，因此这 3 个结点分别被标记为叶结点'好瓜'、 “好瓜”、 “坏瓜”。

此时，验证集中编号为 {4， 5， 8，11， 12} 的样例被分类正确，验证集精度为\frac{5}{7}*100% = 71.4% > 42.9%75∗100%=71.4%>42.9%.

于是，用'脐部'进行划分得以确定。

然后，决策树算法应该对结点2进行划分，基于信息增益准则将挑选出划分属性'色泽'。然而，在使用'色泽'划分后，编号为 {5} 的验证集样本分类结果会由正确转为错误，使得验证集精度下降为 57.1%。于是，预剪枝策略将禁止结点2被划分。

对结点3，最优划分属性为'根蒂'，划分后验证集精度仍为 71.4%. 这个划分不能提升验证集精度，于是，预剪枝策略禁止结点3被划分。

对结点4，其所含训练样例己属于同一类，不再进行划分.

于是，基于预剪枝策略从上表数据所生成的决策树如上图所示，其验证集精度为 71.4%. 这是一棵仅有一层划分的决策树，亦称'决策树桩' (decision stump).

5.2 后剪枝

后剪枝先从训练集生成一棵完整决策树，继续使用上面的案例，从前面计算，我们知前面构造的决策树的验证集精度为42.9%。

后剪枝首先考察结点6，若将其领衔的分支剪除则相当于把6替换为叶结点。替换后的叶结点包含编号为 {7， 15} 的训练样本，于是该叶结点的类别标记为'好瓜'，此时决策树的验证集精度提高至 57.1%。于是，后剪枝策略决定剪枝，如下图所示。

然后考察结点5，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号为 {6，7，15}的训练样例，叶结点类别标记为'好瓜’；此时决策树验证集精度仍为 57.1%. 于是，可以不进行剪枝.

对结点2，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号为 {1， 2， 3， 14} 的训练样例，叶结点标记为'好瓜'此时决策树的验证集精度提高至 71.4%. 于是，后剪枝策略决定剪枝.

对结点3和1，若将其领衔的子树替换为叶结点，则所得决策树的验证集精度分别为 71.4% 与 42.9%，均未得到提高，于是它们被保留。

最终，基于后剪枝策略所生成的决策树就如上图所示，其验证集精度为 71.4%。

对比两种剪枝方法，

*后剪枝决策树通常比预剪枝决策树保留了更多的分支。

*一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。

*但后剪枝过程是在生成完全决策树之后进行的。并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多.

六、scikit-learn集成方法

6.1分类树

import numpy as npfrom matplotlib import pyplot as plt
from sklearn.model_selection import train_test_splitfrom sklearn.datasets import load_irisfrom sklearn.tree import DecisionTreeClassifierfrom sklearn import tree
iris = load_iris()X = iris.datay = iris.targetX_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)
clf = DecisionTreeClassifier(max_leaf_nodes=3, random_state=0)clf.fit(X_train, y_train)data=clf.predict(X_test)print(data)

模型

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)

一、参数

（1）criterion：特征选择标准，【entropy, gini】。默认gini，即CART算法。

（2）splitter：特征划分标准，【best, random】。best在特征的所有划分点中找出最优的划分点，random随机的在部分划分点中找局部最优的划分点。默认的'best’适合样本量不大的时候，而如果样本数据量非常大，此时决策树构建推荐'random’。

（3）max_depth：决策树最大深度，【int, None】。默认值是'None’。一般数据比较少或者特征少的时候可以不用管这个值，如果模型样本数量多，特征也多时，推荐限制这个最大深度，具体取值取决于数据的分布。常用的可以取值10-100之间，常用来解决过拟合。

（4）min_samples_split：内部节点（即判断条件）再划分所需最小样本数，【int, float】。默认值为2。如果是int，则取传入值本身作为最小样本数；如果是float，则取ceil(min_samples_split*样本数量)作为最小样本数。（向上取整）

（5）min_samples_leaf：叶子节点（即分类）最少样本数。如果是int，则取传入值本身作为最小样本数；如果是float，则取ceil(min_samples_leaf*样本数量)的值作为最小样本数。这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。

（6）min_weight_fraction_leaf：叶子节点（即分类）最小的样本权重和，【float】。这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。默认是0，就是不考虑权重问题，所有样本的权重相同。一般来说如果我们有较多样本有缺失值或者分类树样本的分布类别偏差很大，就会引入样本权重，这时就要注意此值。

（7）max_features：在划分数据集时考虑的最多的特征值数量，【int值】。在每次split时最大特征数；【float值】表示百分数，即（max_features*n_features）

（8）random_state：【int, randomSate instance, None】，默认是None

（9）max_leaf_nodes：最大叶子节点数。【int, None】，通过设置最大叶子节点数，可以防止过拟合。默认值None，默认情况下不设置最大叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征多，可以加限制，具体的值可以通过交叉验证得到。

（10）min_impurity_decrease：节点划分最小不纯度，【float】。默认值为'0’。限制决策树的增长，节点的不纯度（基尼系数，信息增益，均方差，绝对差）必须大于这个阈值，否则该节点不再生成子节点。

（11）min_impurity_split（已弃用）：信息增益的阀值。决策树在创建分支时，信息增益必须大于这个阈值，否则不分裂。（从版本0.19开始不推荐使用：min_impurity_split已被弃用，以0.19版本中的min_impurity_decrease取代。min_impurity_split的默认值将在0.23版本中从1e-7变为0，并且将在0.25版本中删除。请改用min_impurity_decrease。）

（12）class_weight：类别权重，【dict, list of dicts, balanced】，默认为None。（不适用于回归树，sklearn.tree.DecisionTreeRegressor），指定样本各类别的权重，主要是为了防止训练集某些类别的样本过多，导致训练的决策树过于偏向这些类别。balanced，算法自己计算权重，样本量少的类别所对应的样本权重会更高。如果样本类别分布没有明显的偏倚，则可以不管这个参数。

（13）presort：bool，默认是False，表示在进行拟合之前，是否预分数据来加快树的构建。对于数据集非常庞大的分类，presort=true将导致整个分类变得缓慢；当数据集较小，且树的深度有限制，presort=true才会加速分类。

二、方法

（1）训练（拟合）：fit(X, y[, sample_weight])——fit(train_x, train_y)

（2）预测：predict(X)返回标签、predict_log_proba(X)、predict_proba(X)返回概率，每个点的概率和为1，一般取predict_proba(X)[:, 1]

（3）评分（返回平均准确度）：score(X, y[, sample_weight])——score(test_x, test_y)。等效于准确率accuracy_score

（4）参数类：获取分类器的参数get_params([deep])、设置分类器的参数set_params(**params)。——print(clf.get_params()) ，clf.set_params(***)

6.2 回归树

from sklearn import treeX = [[0, 0], [2, 2]]y = [0.5, 2.5]clf = tree.DecisionTreeRegressor()clf = clf.fit(X, y)data=clf.predict([[1, 1]])print(data)

模型：

class sklearn.tree.DecisionTreeRegressor(*, criterion='squared_error', 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, ccp_alpha=0.0)

参数：

criterion：{“squared_error”、“friedman_mse”、“absolute_error”、“poisson”}，默认=”squared_error”
测量分割质量的函数。支持的标准是均方误差的“squared_error”，它等于作为特征选择标准的方差减少，并使用每个终端节点的平均值来最小化 L2 损失，“friedman_mse”，它使用均方误差和弗里德曼的潜在改进分数分裂，“absolute_error” 表示平均绝对误差，它使用每个终端节点的中值最小化 L1 损失，“poisson” 使用泊松偏差的减少来找到分裂。
splitter：{“best”, “random”}，默认=”best”
用于在每个节点处选择拆分的策略。支持的策略是“best” 选择最佳分割和“random” 选择最佳随机分割。
max_depth：int 默认=无
树的最大深度。如果没有，则扩展节点直到所有叶子都是纯的或直到所有叶子包含少于min_samples_split 个样本。
min_samples_split：int 或浮点数，默认=2
拆分内部节点所需的最小样本数：
min_samples_leaf：int 或浮点数，默认=1
叶节点所需的最小样本数。只有在左右分支中的每个分支中至少留下min_samples_leaf 训练样本时，才会考虑任何深度的分割点。这可能具有平滑模型的效果，尤其是在回归中。
min_weight_fraction_leaf：浮点数，默认=0.0
需要在叶节点处的权重总和(所有输入样本的)的最小加权分数。当未提供sample_weight 时，样本具有相同的权重。
max_features：int float 或 {“auto”, “sqrt”, “log2”}，默认 = 无
寻找最佳分割时要考虑的特征数量：
注意：在找到至少一个节点样本的有效分区之前，对拆分的搜索不会停止，即使它需要有效地检查超过 max_features 的特征。
random_state：int RandomState 实例或无，默认=无
控制估计器的随机性。即使 splitter 设置为 'best' ，这些特征总是在每次拆分时随机排列。当 max_features < n_features 时，算法将在每次拆分时随机选择 max_features，然后再找到其中的最佳拆分。但是，即使 max_features=n_features ，最好的拆分可能会因不同的运行而有所不同。就是这样，如果标准的改进对于几个拆分是相同的，并且必须随机选择一个拆分。为了在拟合期间获得确定性行为，random_state 必须固定为整数。有关详细信息，请参阅词汇表。
max_leaf_nodes：int 默认=无
以best-first 方式用max_leaf_nodes 种植一棵树。最佳节点定义为杂质的相对减少。如果 None 则无限数量的叶节点。
min_impurity_decrease：浮点数，默认=0.0
如果该分裂导致杂质减少大于或等于该值，则该节点将被分裂。
加权杂质减少方程如下：
```
N_t / N * (impurity - N_t_R / N_t * right_impurity
                    - N_t_L / N_t * left_impurity)
```
其中N是样本总数，N_t是当前节点的样本数，N_t_L是左孩子的样本数，N_t_R是右孩子的样本数.
N , N_t , N_t_R 和 N_t_L 都是指加权和，如果通过了 sample_weight。
ccp_alpha：非负浮点数，默认=0.0
用于最小Cost-Complexity 修剪的复杂度参数。将选择具有最大成本复杂度且小于ccp_alpha 的子树。默认情况下，不进行剪枝。有关详细信息，请参阅最小 Cost-Complexity 修剪。

属性：

feature_importances_ndarray 形状 (n_features,)
返回特征重要性。
max_features_：int
max_features 的推断值。
n_features_int
已弃用：属性 n_features_ 在 1.0 中已弃用，并将在 1.2 中删除。
n_features_in_：int
拟合期间看到的特征数。
feature_names_in_：ndarray 形状(n_features_in_，)
拟合期间看到的特征名称。仅当 X 具有全为字符串的函数名称时才定义。
n_outputs_：int
执行fit 时的输出数。
tree_：树实例
基础树对象。请参考 help(sklearn.tree._tree.Tree) 了解 Tree 对象的属性和了解决策树结构了解这些属性的基本用法。