机器学习-决策树

74 阅读 0 评论 49 点赞

我是靠谱客的博主寒冷诺言，最近开发中收集的这篇文章主要介绍机器学习-决策树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

决策树是一种用于对实例进行分类的树形结构。决策树由节点（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 中所有实例属于同一类 $c_{k}$ ，那么 T就是单节点树，并且将 $c_{k}$ 作为该节点所表示的类别，返回 T；
如果 A=ϕ，则 T 为单节点树，并且将 D 中实例数最大的类作为该节点的类标记，返回 T；
否则，计算 A 中各特征对数据集 D 的信息增益，选择信息增益最大的特征 $a_{g}$ ；
如果 $a_{g}$ 的信息增益小于 ε，此时 T 设置为单节点数，同时也选择将 D 中实例数最大的类作为该节点的类标记，返回 T；
否则，对特征 $a_{g}$ 的每一个可能的取值 $a_{i}$ ，根据 $a_{g}$ = $a_{i}$ 将数据集 D 分割为互不相交的子集 $d_{i}$ ,此时依然将 $d_{i}$ 中实例数最大的类作为标记，构建子节点。由子节点和子节点构成树 T，返回 T；
对第5步中，第 i 个子节点，以 $d_{i}$ 为训练集，以 A−{ $a_{g}$ } 为新的特征集递归的调用1~5步得到子树 $t_{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()