1. 写在前面: 

本篇属于实战部分，更注重于算法在实际项目中的应用。如需对感知机算法本身有进一步的了解，可参考以下链接，在本人学习的过程中，起到了很大的帮助：

统计学习方法 李航

决策树算法原理 https://www.cnblogs.com/pinard/p/6050306.html 等共2篇

2. 数据集：

数据集地址：https://www.kaggle.com/c/titanic

Titanic数据集是Kaggle上参与人数最多的项目之一。数据本身简单小巧，适合初学者上手，深入了解比较各个机器学习算法。

数据集包含11个变量：PassengerID、Pclass、Name、Sex、Age、SibSp、Parch、Ticket、Fare、Cabin、Embarked，通过这些数据来预测乘客在Titanic事故中是否幸存下来。

3. 算法简介：

决策树是一种i基本的分类与回归方法，亦经常被作为集成学习的基学习器。决策树本质上是要一个定义在特征空间和类空间上的条件概率。本篇主要介绍的是CART决策树（Classification And Regression Trees），其根据损失函数最小化的原则建立决策树，并对决策树进行剪枝。CART决策树是递归的构建二叉决策树，在每一步中都根据损失函数最小化选取最优解，因此，它是属于贪心算法的一种。

决策的学习通常包括3个步骤：特征选择、决策树的生成、以及决策树的修剪。下面，我们就依次从这3个方面对CART决策树方法进行简单的介绍。

3.1 特征选择：

在进行特征选择之前，我们需要对一些术语有一些了解，包括：熵、条件熵、互信息、信息增益、信息增益比、基尼指数。

 熵：熵是表示随机变量不确定性的度量，假设 $X$ 是一个取有限个值的离散随机变量，其概率分布为$P(X=x_{i}) = p_{i}, \quad i=1,2,...,n$，则随机变量 $X$ 的熵定义为 $H(x) =H(p)= -\sum_{i=1}^{n}p_{i}log(p_{i})$。

　　 当随机变量的取值只有两个(如0和1，即伯努利分布时)，熵为 $H(p) = -p\log2p - (1-p)\log_2(1-p)$i

条件熵：$H(Y|X)$ 表示随机变量X给定的条件下随机变量Y的条件熵，定义为 $H(Y|X) = \sum_{i=1}^{n}p_{i}H(Y|X=x_{i}) $

互信息(mutual information)：熵与条件熵之差称为互信息。

信息增益(information gain)：特征A对训练数据集D的信息增益$g(D,A)$，定义为D的经验熵$H(D)$与特征A给定条件下D的经验条件熵$H(D|A)$之差，即$ g(D,A) = H(D) - H(D|A) $。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益比：信息增益值的大小是相对于训练数据集而言的，没有绝对意义。在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。于是，引入信息增益比的概念，定义为：$g_{R}(D,A) = \frac{g(D,A)}{H_{A}(D)}$，这里李航老师的书中有点问题，书中分母为$H(D)$。$H(D)$是训练数据集对于类别的经验熵，而$H_{A}(D)$是训练数据集关于某个特征的经验熵。

基尼指数：假设 $X$ 是一个取有限个值的离散随机变量，其概率分布为$P(X=x_{i}) = p_{i}, \quad i=1,2,...,n$，则随机变量 $X$ 的基尼指数定义为 $\text{Gini}(x) = \text{Gini}(p) = \sum_{i=1}^{n}p_{i}(1-p_{i}) = 1 - \sum_{i=1}^{n}p_{i}^{2}$。对于二分类问题，基尼指数和$\frac{1}{2}$熵的曲线很接近，且基尼指数的计算较快，因此在CART树分类树算法中使用基尼指数。

3.1.1 CART分类树特征选择：

CART分类树使用基尼指数最小化准则选择最优特征，同时决定该特征的最优二值切分点。

CART分类树是可以处理离散变量和连续变量的。对于离散变量，假设特征A有n个取值，CART算法取相邻两样本值的平均数，一共取得n-1个划分点n。分别计算这n-1个点作为二元分类点时，该特征的基尼系数。最后选取基尼系数最小的作为该连续特征的二元离散分类点。未完全区分的离散变量（包括离散化后的连续变量），在后续的迭代过程中依然可以参与子节点的产生选择过程。

3.1.2 CART回归树特征选择：

CART回归树使用平方误差最小化准则选择最优特征：对每个划分单元$R_{m}$ 有 $\sum_{x_{i} \in R_{m}} (y_{i} - f(x_{i}))^2$，且$f(x_{i})$ 对每个单元是固定值。用过平方误差最小化可求得，$f(x_{i}) = \text{avg}(y_{i}| x_{i} \in R_{m})$

3.2 决策树生成：

3.2.1 CART分类树生成：

根据训练数据集D，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

第一步：设结点的训练数据集为D，计算现有所有特征对该数据集的基尼指数。对每一个特征A，对其可能取的每个值a(对连续特征，a即其划分点)，计算A=a时的基尼系数

第二步：在所有可能的特征A以及它们所有可能的切分点a中，选择基尼系数最小的特征及其对应的切分点作为最优特征与最优切分点。并照此切分，由现结点生成两个子结点，将训练集数据分配到两个子结点中

第三步：对两个子节点递归地重复前两步，直到满足停止条件

3.2.1 CART回归树生成：

整体流程和CART分类树一致。

根据训练数据集D所在的输入空间，递归地将每个区域划分成两个子区域并决定每个子区域上的输出值，构建二叉决策树：

第一步：选择最优切分变量 $j$ 与切分点 $s$：

$$ \min_{j,s}\left [ \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 \right ] $$

第二步：用选定的$(j,s)$对划分区域$R_{1}$和$R_{2}$，并决定相应的输出值，输出值为每个单元上的所有实例对应的输出的均值

第三步：继续对两个子区域递归地重复前两步，直到满足停止条件

3.3 决策树剪枝：

决策树剪枝过程，参考李航老师的原文：

这里简要解释一下，其中的 $g(t) = \frac{C(t) - C(T_{t})}{|T_{t}| - 1}$ 是如何推导出来的：

首先，我们定义子树的损失函数为：

$$ C_{\alpha}(T) = C(T) + \alpha |T| $$

其中，$T$为任意子树，$C(T)$ 为对训练数据的预测误差即损失函数（分类树为基尼指数、回归树为平方误差），$|T|$ 为子树的叶结点个数，$\alpha \geq0$ 为参数，类似于正则化系数。$C_{\alpha}(T)$ 为参数是 $\alpha$ 时的子树 $T$ 的整体损失。参数 $\alpha$ 权衡训练数据的拟合程度与模型的复杂度。

接下来，对于整体树$T_{0}$的任意内部结点$t$：

以$t$为单结点树的损失函数是：$C_{\alpha}(t) = C(t) + \alpha$

以$t$为根结点的子树$T_{t}$的损失函数是：$ C_{\alpha}(T_{t}) = C(T_{t}) + \alpha|T_{t}| $ 

当$\alpha$极小时，$C_{\alpha}(T_{t}) < C_{\alpha}(t)$，当$\alpha$增大到一定程度时，$C_{\alpha}(T_{t}) = C_{\alpha}(t)$，此时，单结点树$t$的损失函数和根节点树$T_{t}$相同且结点更少，便对$T_{t}$进行剪枝。而此时满足等式的$\alpha$为 $\alpha= \frac{C(t) - C(T_{t})}{|T_{t}| - 1}$。

4. 实战：

sklearn中，分类树主要使用 sklearn.tree.DecisionTreeClassifier，回归树主要使用 sklearn.tree.DecisionTreeRegressor。Titanic 数据集是分类问题，所以使用 sklearn.tree.DecisionTreeClassifier。

下面，对DecisionTreeClassifier中一些比较重要的参数进行一下说明：

1. criterion：‘gini’，‘entropy‘ 损失函数的选取基尼指数或者是熵

2. splitter：‘best’，‘random’ 每个结点进行二叉树分类时，如何选取最优划分点。‘best’是指特征所有划分点中的最优划分点，‘random‘是指随机选取的划分点中的最优划分点。数据量较大时，建议使用‘random‘。

3. max_depth：树的深度，数据量较大时，可以给定一个限制，一般根据数据分布在10~100之间。

4. min_samples_split：每个可以被再次分类的结点中所需要的最少的样本数。默认为2

5. min_samples_leaf：每个叶结点中所需要的最少的样本数，若不满足，将和它对应的另一个叶结点一起被剪枝，退回上一节点。默认为1

6. max_features：划分是考虑的最大特征数。当特征数特别大时，可以用‘sqrt‘，‘log2’等降级特征数，加快树的生成时间‘

7. max_leaf_nodes：最大的叶结点数，防止过拟合

8. ccp_alpha：即上一节决策树剪枝中提到的$\alpha$参数，小于$\alpha$的子树将会被剪枝。但需要注意的是，sklearn中不会在所有子树中进行交叉验证，然后选取最优子树。

以下是简单的代码，供参考：

 1 import pandas as pd
 2 import numpy as np
 3 import matplotlib.pyplot as plt
 4 from sklearn.preprocessing import MinMaxScaler, StandardScaler, OneHotEncoder, OrdinalEncoder
 5 from sklearn.impute import SimpleImputer
 6 from sklearn.model_selection import StratifiedKFold, GridSearchCV
 7 from sklearn.pipeline import Pipeline, FeatureUnion
 8 from sklearn.tree import DecisionTreeClassifier
 9 from sklearn.metrics import accuracy_score, precision_score, recall_score
10 from sklearn.base import BaseEstimator, TransformerMixin
11 
12 
13 class DataFrameSelector(BaseEstimator, TransformerMixin):
14     def __init__(self, attribute_name):
15         self.attribute_name = attribute_name
16 
17     def fit(self, x, y=None):
18         return self
19 
20     def transform(self, x):
21         return x[self.attribute_name].values
22 
23 
24 # Load data
25 data_train = pd.read_csv(‘train.csv‘)
26 
27 train_x = data_train.drop(‘Survived‘, axis=1)
28 train_y = data_train[‘Survived‘]
29 
30 # Data cleaning
31 cat_attribs = [‘Pclass‘, ‘Sex‘, ‘Embarked‘]
32 dis_attribs = [‘SibSp‘, ‘Parch‘]
33 con_attribs = [‘Age‘, ‘Fare‘]
34 
35 # encoder: OneHotEncoder()、OrdinalEncoder()
36 cat_pipeline = Pipeline([
37     (‘selector‘, DataFrameSelector(cat_attribs)),
38     (‘imputer‘, SimpleImputer(strategy=‘most_frequent‘)),
39     (‘encoder‘, OneHotEncoder()),
40 ])
41 
42 dis_pipeline = Pipeline([
43     (‘selector‘, DataFrameSelector(dis_attribs)),
44     (‘scaler‘, StandardScaler()),
45     (‘imputer‘, SimpleImputer(strategy=‘most_frequent‘)),
46 ])
47 
48 con_pipeline = Pipeline([
49     (‘selector‘, DataFrameSelector(con_attribs)),
50     (‘scaler‘, StandardScaler()),
51     (‘imputer‘, SimpleImputer(strategy=‘mean‘)),
52 ])
53 
54 full_pipeline = FeatureUnion(
55     transformer_list=[
56         (‘con_pipeline‘, con_pipeline),
57         (‘dis_pipeline‘, dis_pipeline),
58         (‘cat_pipeline‘, cat_pipeline),
59     ]
60 )
61 
62 train_x_cleaned = full_pipeline.fit_transform(train_x)
63 
64 cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=2)
65 
66 clf1 = DecisionTreeClassifier(random_state=1992)
67 
68 param_grid = [{
69     ‘criterion‘: [‘gini‘, ‘entropy‘],
70     ‘min_samples_split‘:[2, 4, 8, 16, 32],
71     ‘class_weight‘: [None, ‘balanced‘],
72     ‘ccp_alpha‘:[0, 1e-1, 1e-2, 1e-3],
73                 }]
74 
75 grid_search = GridSearchCV(clf1, param_grid=param_grid, cv=cv, scoring=‘accuracy‘, n_jobs=-1, return_train_score=True)
76 
77 grid_search.fit(train_x_cleaned, train_y)
78 predicted_y = grid_search.predict(train_x_cleaned)
79 
80 df_cv_results = pd.DataFrame(grid_search.cv_results_).sort_values(by=‘rank_test_score‘)
81 print(‘-------Result of DecisionTreeClassifier-------‘)
82 print(grid_search.best_params_)
83 print(accuracy_score(train_y, predicted_y))
84 print(precision_score(train_y, predicted_y))
85 print(recall_score(train_y, predicted_y))
86 
87 # 导入预测数据，预测结果，并生成csv文件
88 data_test = pd.read_csv(‘test.csv‘)
89 submission = pd.DataFrame(columns=[‘PassengerId‘, ‘Survived‘])
90 submission[‘PassengerId‘] = data_test[‘PassengerId‘]
91 
92 test_x_cleaned = full_pipeline.fit_transform(data_test)
93 
94 submission_DecisionTree = pd.DataFrame(submission, copy=True)
95 submission_DecisionTree[‘Survived‘] = pd.Series(grid_search.predict(test_x_cleaned))
96 
97 submission_DecisionTree.to_csv(‘submission_DecisionTree.csv‘, index=False)

4.1 结果分析：

如果大家仔细查看交叉验证的结果 grid_serch.cv_results_。可以发现，部分参数下决策树的 train_test_score 远远好于 train_test_score。这是明显的过拟合现象，因此在参数中加入 ‘min_sample_split‘ 和 ’ccp_alpha‘ 防止过拟合。

和前几篇一样，将交叉验证后的最优参数" ccp_alpha = 0.01, class_weight=None, criterion=‘entropy‘, min_samples_split=2 "用于预测集，并将结果上传kaggle，结果如下：

【机器学习实战】-- Titanic 数据集（5）-- 决策树

原文：https://www.cnblogs.com/guduzhen/p/14258686.html