1.总概述
决策树(desicion tree)是一种树形结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一个类别。
决策树以实例为基础进行归纳学习。其采用自上而下的递归方式，基本思路是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点时熵值应该下降为零。此时每个叶节点中包含的实例都为同一类。
2.信息熵
2.1 熵
熵 (entropy) 这一概念来源于热力学，是混乱程度的度量。
而信息熵(information entropy)这一概念在1948年被引入，旨在帮助人们度量一个信息。信息量的度量就等于其不确定性的大小。信息熵的大小与这条信息的确定性成反比。
2.2 条件熵
(x,y)发生的熵减去(x)发生的熵，即为在x条件下，y发生的熵。
条件熵的推导公式如下：
若想了解更多有关机器学习中的熵、条件熵、交叉熵以及相对熵，可以跳转机器学习中的熵。
3.决策树
3.1 信息增益
信息增益表示得知特征A的信息使得使得类X的信息的不确定度减少的程度。信息增益G(D,A)定义为集合D的信息熵H(D)与给定特征条件A下的条件熵H(D,A)之差。这也被称为特征A与数据集D的互信息。
信息增益的计算方法如下：
3.2 基尼系数
基尼系数(gini coefficient/index )计算方法如下：
若想对基尼系数有更多的了解，可前往基尼系数。
3.3 信息增益率
3.4 决策树学习算法
3.4.1 ID3
使用信息增益/互信息G(D,A)来进行特征选择。
ID3算法所采用的度量标准就是我们前面所提到的“信息增益”。当属性a的信息增益最大时，则意味着用a属性划分，其所获得的“纯度”提升最大。我们所要做的，就是找到信息增益最大的属性。
3.4.2 C4.5
使用信息增益率来进行特征选择。
实际上，信息增益准则对于可取值数目较多的属性会有所偏好，为了减少这种偏好可能带来的不利影响，C4.5决策树算法不直接使用信息增益，而是使用“信息增益率”来选择最优划分属性。
需要注意的是，增益率准则对可取值数目较少的属性有所偏好。所以一般这样选取划分属性：先从候选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
3.4.3 CART
CART(classification and regression train)，使用基尼系数来进行特征选择。
一个属性的信息增益(率)/基尼系数越大，表明属性对样本的熵的减少的能力更强，这个属性使得一个数据由不确定变为确定的能力更强。
3.5 损耗函数
损耗函数的推导过程可参见损耗函数。
3.6 过拟合
决策树对于训练数据能够有很好的分类能力，但对未知的测试数据却未必能有很好的分类能力，即决策树很有可能产生过拟合的现象。
针对过拟合的现象，有以下两种解决方法。
3.6.1 剪枝
3.6.1.1 概述
三种算法的剪枝过程算法相同，区别仅仅在于对于当前树的评价标准不同。
3.6.1.2 总体思路
由完全树T0开始进行剪枝，剪枝部分结点得到T1，再次剪枝部分结点得到T2，不断重复剪枝部分结点，直至仅剩树根的树Tk。
在验证数据集上对这k个树分别评价，选择损失函数最小的数Ta。
3.6.1.3 剪枝系数的确定
叶节点越多，决策树也就越复杂，损失也就越大。
当α=0时，未剪枝的决策树损失最小。当α=+∞时，单根结点的决策树损失最小。
假设此时对以r为根的子树进行剪枝，剪枝后，只保留r本身而删掉所有的叶子。
此时剪枝后的损耗函数：
剪枝前的损耗函数：
令二者相等，可得：
此时α即为结点r的剪枝系数。
3.6.1.4 剪枝算法
对于给定的决策树T0：
计算所有内部结点的剪枝系数；
查找剪枝系数最小的结点，剪枝得到决策树Tk；
重复上述两个步骤，知道决策树只剩下一个结点；
可以得到决策树序列T0T1T2…Tk；
使用验证样本集选择最优子树，其选择标准可以选用损耗函数。
3.6.2 随机森林
随机森林具体内容见下文。
4.Bagging和随机森林
4.1 Bagging的策略
Bagging(bootstrap aggregation)的策略如下：
从样本集中有重复地选取出n个样本；
在所有属性上，对这个n个样本建立分类器(ID3、C4.5、CART、logistic回归、SVM等等)；
重复上述两步m次，即获得了m个分类器；
将数据放在这m个分类器上，最后根据这m个分类器的投票结果，决定数据属于哪一类。
4.2 随机森林
随机森林在Bagging的基础上做了一部分修改。其策略如下：
在样本集中用bootstrap采样选取n个样本；
从所有属性中随机选择k个属性，选择最佳分割属性作为节点建立CART决策树；
重复以上两步m次，即建立了m棵CART决策树；
这m棵CART决策树形成了随机森林，通过投票表决结果，来决定数据属于哪一类。
4.3 随机森林与决策树的关系
使用决策树作为基本分类器，采用Bagging的策略，所形成的总分类器为“随机森林”；但是使用SVM、logistic回归等其他分类器，采用Bagging的策略，所形成的总分类器也被叫做“随机森林”。
5.代码实践
5.1 随机森林分类
import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl
from sklearn import tree
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
def iris_type(s):#为了方便之后数据预处理
it = {b'Iris-setosa': 0, b'Iris-versicolor': 1, b'Iris-virginica': 2}
return it[s]
# 花萼长度、花萼宽度，花瓣长度，花瓣宽度
iris_feature = u'花萼长度', u'花萼宽度', u'花瓣长度', u'花瓣宽度'
if __name__ == "__main__":
mpl.rcParams['font.sans-serif'] = [u'SimHei']
mpl.rcParams['axes.unicode_minus'] = False
path = '8.iris.data' # 数据文件路径
data = np.loadtxt(path, dtype=float, delimiter=',', converters={4: iris_type})
x, y = np.split(data, (4,), axis=1)
# 为了可视化，仅使用前两列特征
x = x[:, :2]
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.3, random_state=1)
# 决策树参数估计
model = Pipeline([
('ss', StandardScaler()),
('DTC', DecisionTreeClassifier(criterion='entropy', max_depth=3))])
model = model.fit(x_train, y_train)
y_test_hat = model.predict(x_test) # 测试数据
#画决策树图
f = open('.\\iris_tree.dot', 'w')
tree.export_graphviz(model.get_params('DTC')['DTC'], out_file=f)
f.close()
N, M = 100, 100 # 横纵各采样多少个值
x1_min, x1_max = x[:, 0].min(), x[:, 0].max() # 第0列的范围
x2_min, x2_max = x[:, 1].min(), x[:, 1].max() # 第1列的范围
t1 = np.linspace(x1_min, x1_max, N)
t2 = np.linspace(x2_min, x2_max, M)
x1, x2 = np.meshgrid(t1, t2) # 生成网格采样点
x_show = np.stack((x1.flat, x2.flat), axis=1) # 测试点
cm_light = mpl.colors.ListedColormap(['#A0FFA0', '#FFA0A0', '#A0A0FF'])
cm_dark = mpl.colors.ListedColormap(['g', 'r', 'b'])
y_show_hat = model.predict(x_show) # 预测值
y_show_hat = y_show_hat.reshape(x1.shape) # 使之与输入的形状相同
plt.figure(facecolor='w')
plt.pcolormesh(x1, x2, y_show_hat, cmap=cm_light) # 预测值的显示
plt.scatter(x_test[:, 0], x_test[:, 1], c=y_test.ravel(), edgecolors='k', s=100, cmap=cm_dark, marker='o') # 测试数据
plt.scatter(x[:, 0], x[:, 1], c=y.ravel(), edgecolors='k', s=40, cmap=cm_dark) # 全部数据
plt.xlabel(iris_feature[0], fontsize=15)
plt.ylabel(iris_feature[1], fontsize=15)
plt.xlim(x1_min, x1_max)
plt.ylim(x2_min, x2_max)
plt.grid(True)
plt.title(u'鸢尾花数据的决策树分类', fontsize=17)
plt.show()
# 训练集上的预测结果
y_test = y_test.reshape(-1)
print (y_test_hat)
print (y_test)
result = (y_test_hat == y_test) # True则预测正确，False则预测错误
acc = np.mean(result)
print ('准确度: %.2f%%' % (100 * acc))
# 过拟合：错误率
depth = np.arange(1, 15)
err_list = []
for d in depth:
clf = DecisionTreeClassifier(criterion='entropy', max_depth=d)
clf = clf.fit(x_train, y_train)
y_test_hat = clf.predict(x_test) # 测试数据
result = (y_test_hat == y_test) # True则预测正确，False则预测错误
err = 1 - np.mean(result)
err_list.append(err)
print (d, ' 错误率: %.2f%%' % (100 * err))
plt.figure(facecolor='w')
plt.plot(depth, err_list, 'ro-', lw=2)
plt.xlabel(u'决策树深度', fontsize=15)
plt.ylabel(u'错误率', fontsize=15)
plt.title(u'决策树深度与过拟合', fontsize=17)
plt.grid(True)
plt.show()
5.2 随机森林回归
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor
if __name__ == "__main__":
N = 100
x = np.random.rand(N) * 6 - 3 # [-3,3)
x.sort()
y = np.sin(x) + np.random.randn(N) * 0.05
x = x.reshape(-1, 1) # 转置后，得到N个样本，每个样本都是1维的
reg = DecisionTreeRegressor(criterion='mse', max_depth=9)
dt = reg.fit(x, y)
x_test = np.linspace(-3, 3, 50).reshape(-1, 1)
y_hat = dt.predict(x_test)
plt.plot(x, y, 'r*', linewidth=2, label='Actual')
plt.plot(x_test, y_hat, 'g-', linewidth=2, label='Predict')
plt.legend(loc='upper left')
plt.grid()
plt.show()
# 比较决策树的深度影响
depth = [2, 4, 6, 8, 10]
clr = 'rgbmy'
reg = [DecisionTreeRegressor(criterion='mse', max_depth=depth[0]),
DecisionTreeRegressor(criterion='mse', max_depth=depth[1]),
DecisionTreeRegressor(criterion='mse', max_depth=depth[2]),
DecisionTreeRegressor(criterion='mse', max_depth=depth[3]),
DecisionTreeRegressor(criterion='mse', max_depth=depth[4])]
plt.plot(x, y, 'k^', linewidth=2, label='Actual')
x_test = np.linspace(-3, 3, 50).reshape(-1, 1)
for i, r in enumerate(reg):
dt = r.fit(x, y)
y_hat = dt.predict(x_test)
plt.plot(x_test, y_hat, '-', color=clr[i], linewidth=2, label='Depth=%d' % depth[i])
plt.legend(loc='upper left')
plt.grid()
plt.show()