决策树算法
一、特征选取
特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益、信息增益比、基尼指数。
1.信息增益
（1）信息熵
信息的度量方式：信息熵
假设X是一个离散型随机变量，其概率分布为:
P(X=xi) = pi, i=1, 2, 3, 4, ......, n
则其熵为：
0 ≤ H(p) ≤ log n
熵就是对所有可能性带来的信息量求平均值。
熵越大，随机变量的不确定性就越大。
示例：
当随机变量X的取值只有两个：0和1
P(x=1) = p（0 ≤ p ≤ 1）
P(x=0)= 1 - p（0 ≤ p ≤ 1）
熵为：H(p) = -p log p - (1-p) log (1-p) ，图像如下：
当p＝0或p＝1时，H(p)＝0，随机变量完全没有不确定性。
当p＝0.5时，H(p)＝1，熵取值最大，随机变量不确定性最大。
（2）条件熵
设随机变量(X,Y),其联合概率分布为：
P(X = xi,Y = yj) = pi（i = 1,2,3,…,n；j = 1,2,…,m）
条件熵H(Y|X) 表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵（conditionalentropy）H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：
（3）信息增益
信息增益（information gain）表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
特征A对训练数据集D的信息增益g(D,A)，定义为集合D的熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差：
g(D,A) = H(D) – H(D|A)
一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息（mutual information）。
根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
2.信息增益比
信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。使用信息增益比可以对这一问题进行校正。这是特征选择的另一准则。
特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D的经验熵H(D)之比：
3.基尼系数
分类问题中，假设有K个类，样本点属于第k类的概率为pk，则概率分布的基尼指数定义为：
基尼指数越大，样本集合的不确定性就越大，这一点与熵相似。
下图显示了（横坐标表示概率，纵坐标表示损失）：熵之半、分类误差率和基尼指数的关系，由此可见，熵之半和基尼指数都可以近似的代表分类误差率：
二、决策树生成算法
1.ID3算法
ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。
具体方法是：从根结点（rootnode）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。
算法
输入：训练数据集D，特征集A，阈值ε（Epsilon）
输出：决策树T。
2.C4.5生成算法
C4.5生成算法与ID3生成算法相似，只是在选取分类特征时使用信息增益比。
算法
输入：训练数据集D，特征集A，阈值ε（Epsilon）
输出：决策树T。
三、决策树剪枝算法
剪枝是决策树算法应对过拟合的主要手段，因为决策树在生成的过程中，为了尽可能的正确分类样本数据，节点的划分过程将不断重复，这样导致的结果就是过拟合。
决策树的剪枝算法大体包含两种：预剪枝和后剪枝
- 预剪枝：在决策树生成的过程中，对每个节点在划分前先进行估计，如果节点的划分不能带来决策树性能的提升，则停止划分，并将当前的节点标识为叶节点。
- 后剪枝：先从训练集生成一棵完整的决策树，然后自底向上的对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点。
- 预剪枝的优缺点：
预剪枝使决策树的很多分支都没有展开，因此不仅能显著降低过拟合的风险，并且显著减少了决策树的训练时间和测试时间。
但另一方面，有些分支的当前划分虽然不能提升决策树的泛化性能，但是在其基础熵的后继划分却能显著提高决策树的性能，预剪枝算法会禁止这样的分支展开，因此给决策树带来了欠拟合的风险。- 后剪枝的优缺点：
一般情况下，后剪枝决策树欠拟合的风险很小，泛化性能往往优于预剪枝决策树。但后剪枝决策树需要展开整棵树，并且要自底向上对所有子树进行考察，因此训练时间的开销更大。
四、sckit-learn决策树
1.数据准备
（1）导入数据
def read_dataset(filename):
# 读取数据，并且把第一列设为索引列
data = pd.read_csv('./{}.csv'.format(filename), index_col=0)
# 去除无用数据列
data.drop(['Name', 'Ticket', 'Cabin'], axis=1, inplace=True)
# 处理性别数据
data["Sex"] = (data['Sex'] == 'male').astype("int")
# 将文字编码转换为数字编码
labels = data['Embarked'].unique().tolist()
data['Embarked'] = data['Embarked'].apply(lambda n:labels.index(n))
# 处理缺失值
data = data.fillna(0)
return data
train = read_dataset("train")
（2）分割数据集
# 分割训练集测试集的特征值和标签
from sklearn.model_selection import train_test_split
def feature_label_split(dataset):
y = dataset['Survived'].values
X = dataset.drop(['Survived'], axis=1).values
return X, y
X, y = feature_label_split(train)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
2.初步训练
数据拟合
# 使用树对数据拟合
from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(criterion='entropy')
clf.fit(X_train, y_train)
train_score = clf.score(X_train, y_train)
test_score = clf.score(X_test, y_test)
print("train score:{0}; test_score:{1}".format(train_score,test_score))
3.优化模型
（1）超参数优化
①最大深度
def cv_score(depth):
clf = DecisionTreeClassifier(max_depth=depth)
clf.fit(X_train, y_train)
tr_score = clf.score(X_train, y_train)
cv_score = clf.score(X_test, y_test)
return tr_score, cv_score
depths = range(2, 15)
scores = [cv_score(depth) for depth in depths]
tr_scores = [s[0] for s in scores]
cv_scores = [s[1] for s in scores]
# 找出交叉验证评分最高的索引
best_score_index = np.argmax(cv_scores)
best_score = cv_scores[best_score_index]
best_param = depths[best_score_index]
%matplotlib inline
import matplotlib.pyplot as plt
plt.figure(figsize=(6, 4), dpi=96)
plt.grid()
plt.xlabel("decision tree max depth")
plt.ylabel("score")
plt.plot(depths, cv_scores, 'g-', label='test score')
plt.plot(depths, tr_scores, 'r--', label='train score')
plt.legend()
plt.show()
print("最好的参数：{0}，最好的分数：{1}".format(best_param, best_score))
②基尼系数
# 指定min_impurity_decrease，决定分支条件
def cv_score_gini(val):
clf = DecisionTreeClassifier(criterion='gini', min_impurity_decrease=val)
clf.fit(X_train, y_train)
tr_score = clf.score(X_train, y_train)
cv_score = clf.score(X_test, y_test)
return tr_score, cv_score
values = np.linspace(0,0.5, 1000)
scores = [cv_score_gini(val) for val in values]
tr_scores = [s[0] for s in scores]
cv_scores = [s[1] for s in scores]
# 找出交叉验证评分最高的索引
best_score_index = np.argmax(cv_scores)
best_score = cv_scores[best_score_index]
best_param = values[best_score_index]
%matplotlib inline
import matplotlib.pyplot as plt
plt.figure(figsize=(6, 4), dpi=96)
plt.grid()
plt.xlabel("threshold of entropy")
plt.ylabel("score")
plt.plot(values, cv_scores, 'g-', label='test score')
plt.plot(values, tr_scores, 'r--', label='train score')
plt.legend()
plt.show()
print("最好的参数：{0}，最好的分数：{1}".format(best_param, best_score))
（2）网格搜索
from sklearn.model_selection import GridSearchCV
entropy_thresholds = np.linspace(0, 1, 50)
gini_thresholds = np.linspace(0, 0.5, 50)
# 设置参数矩阵
param_grid = [
{"criterion":['entropy'], 'min_impurity_decrease': entropy_thresholds},
{"criterion":['gini'], 'min_impurity_decrease': entropy_thresholds},
{"max_depth": range(2, 15)},
# 每个节点最小样本数量
{"min_samples_leaf":range(2, 30, 2)}
]
clf = GridSearchCV(DecisionTreeClassifier(), param_grid, cv=5)
clf.fit(X, y)
print("最好的参数：{0}\n最好的分数：{1}".format(clf.best_params_, clf.best_score_))
（3）使用最优超参数重新训练模型
clf = DecisionTreeClassifier(criterion='entropy', max_depth=5, min_samples_leaf=8)
clf.fit(X_train, y_train)
4.保存模型
- 1.首先将决策树模型保存为dot文件：
import sklearn.tree as tree
tree.export_graphviz(decision_tree=clf, out_file="tree.dot")
- 2.然后用以下方法将dot文件转化为png、pdf等可视化文件：
（1）命令行
.../> dot -Tpng tree.dot -o tree.png
（2）Graphviz库
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple/ graphviz
