机器学习-决策树
决策树是一种用于对实例进行分类的树形结构。决策树由节点（Node）和有向边（Directed Edge）组成。节点的类型有两种：内部节点和叶子节点。其中，内部节点表示一个特征或属性的测试条件（用于分开具有不同特性的记录），叶子节点表示一个分类。
决策树模型
决策树模型是一种描述对实例进行分类的树形结构。一旦决策树构建完成，那么利用决策树进行分类预测是非常简单的：首先，从根节点开始，对实例的某一特征进行对比测试，根据测试结果将该实例分配到相应的子节点上；这时，每一个子节点对应着该特征的一个取值（或取值范围）。如此递归地对实例进行测试，直至该实例被分配到叶子节点，最后将实例分配到叶子节点所代表的类中。
决策树的生成模型：
建立决策树的关键，即在当前状态下选择哪个特征属性作为分类依据。根据不同的目标函数主要有下面三种算法：
- ID3
- C4.5
- CART
1. ID3算法
信息增益：表示的知特征A的信息而使类X的信息的不确定性减少的程度。特征A对训练数据集D的信息增益g（D,A），定义为集合D的经验熵H（D）与特征A给定条件下D的经验条件熵H(D|A)之差：
g(D,A)=H(D)-H(D|A)
所以这为数据集D与特征A的互信息。
算法过程描述如下：
-
算法输入：训练数据集 D，特征集 A，最小信息增益阈值 ε。
-
算法输出： 决策树 T。
-
执行过程：
-
如果 D 中所有实例属于同一类
，那么 T就是单节点树，并且将
-
如果 A=ϕ，则 T 为单节点树，并且将 D 中实例数最大的类作为该节点的类标记，返回 T；
-
否则，计算 A 中各特征对数据集 D 的信息增益，选择信息增益最大的特征
；
-
如果
-
否则，对特征
，根据
,此时依然将
-
对第5步中，第 i 个子节点，以
并返回。
经验条件熵的计算：
2. C4.5算法
C4.5 算法和 ID3 算法基本上完全一致，只是特征选择时的选择方法从 ID3 依据的信息增益改成了信息增益比。
取值多的属性，是数据更纯，其信息增益更大，改用信息增益比更合理。
（注意：上面的信息增益比写错了，应该是：g(D|A)）=g(D,A)/H(D)
使用sklearn中决策树对iris数据分类：
import numpy as np
import pandas as pd
import matplotlib as mpl
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
from sklearn.model_selection import train_test_split
if __name__ == "__main__":
mpl.rcParams['font.sans-serif'] = [u'SimHei']
mpl.rcParams['axes.unicode_minus'] = False
iris_feature = u'花萼长度', u'花萼宽度', u'花瓣长度', u'花瓣宽度'
path = './iris.data' # 数据文件路径
data = pd.read_csv(path, header=None)
x_prime = data[range(4)]
y = pd.Categorical(data[4]).codes
x_prime_train, x_prime_test, y_train, y_test = train_test_split(x_prime, y, train_size=0.7, random_state=0)
feature_pairs = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
plt.figure(figsize=(11, 8), facecolor='#FFFFFF')
for i, pair in enumerate(feature_pairs):
# 准备数据
x_train = x_prime_train[pair]
x_test = x_prime_test[pair]
# 决策树学习
model = DecisionTreeClassifier(criterion='entropy', min_samples_leaf=3)
model.fit(x_train, y_train)
N, M = 500, 500 # 横纵各采样多少个值
x1_min, x2_min = x_train.min()
x1_max, x2_max = x_train.max()
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) # 测试点
# 训练集上的预测结果
y_train_pred = model.predict(x_train)
acc_train = accuracy_score(y_train, y_train_pred)
y_test_pred = model.predict(x_test)
acc_test = accuracy_score(y_test, y_test_pred)
print '特征：', iris_feature[pair[0]], ' + ', iris_feature[pair[1]]
print '\t训练集准确率: %.4f%%' % (100*acc_train)
print '\t测试集准确率: %.4f%%\n' % (100*acc_test)
cm_light = mpl.colors.ListedColormap(['#A0FFA0', '#FFA0A0', '#A0A0FF'])
cm_dark = mpl.colors.ListedColormap(['g', 'r', 'b'])
y_hat = model.predict(x_show)
y_hat = y_hat.reshape(x1.shape)
plt.subplot(2, 3, i+1)
plt.contour(x1, x2, y_hat, colors='k', levels=[0, 1], antialiased=True)
plt.pcolormesh(x1, x2, y_hat, cmap=cm_light) # 预测值
plt.scatter(x_train[pair[0]], x_train[pair[1]], c=y_train, s=20, edgecolors='k', cmap=cm_dark, label=u'训练集')
plt.scatter(x_test[pair[0]], x_test[pair[1]], c=y_test, s=100, marker='*', edgecolors='k', cmap=cm_dark, label=u'测试集')
plt.xlabel(iris_feature[pair[0]], fontsize=14)
plt.ylabel(iris_feature[pair[1]], fontsize=14)
# plt.legend(loc='upper right', fancybox=True, framealpha=0.3)
plt.xlim(x1_min, x1_max)
plt.ylim(x2_min, x2_max)
plt.grid(b=True)
plt.suptitle(u'决策树对鸢尾花数据两特征组合的分类结果', fontsize=18)
plt.tight_layout(1, rect=(0, 0, 1, 0.92)) # (left, bottom, right, top)
plt.show()