遇见YI算法之决策树

Hi，手机边的你还好吗？上篇推文给大家简单介绍了下逻辑回归，大家都知道逻辑回归既可以做分类也可以做回归，也是在我们实际工作中应用比较广且模型准确的较好一个模型。今天再给大家在介绍一个应用性广且既可分类也可回归的算法：决策树。本文主要介绍分类决策树。

1、决策树

决策树基本上是每一本机器学习入门书籍必讲的东西，其决策过程和平时我们的思维很相似，所以非常好理解，同时有一堆信息论的东西在里面。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

决策树由结点（node）和 有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶节点（leaf node）。内部结点表示一个特征或属性，叶节点表示一个类。一般的，一颗决策树包含一个根结点、若干个内部结点和若干个叶结点，叶结点对应于决策结果，其他每个结点则对应于一个属性测试，每个结点包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列，决策树学习的目的是为了产生一颗泛化能力强，即处理未见示例能力强的决策树。

例如：当我们在超市买西瓜的时候如何判断一个西瓜是否好瓜？通常我们会进行一系列判断决策，比如看西瓜的色泽、根蒂、敲声等等，当我们判断西瓜色泽为青绿的时候我们会进一步看其根蒂，如果根蒂蜷缩，我们再去根据其敲声判断是否好瓜，这就是一个决策过程。生成一颗西瓜问题的决策树如下图所示，色泽、根蒂、敲声是决策树内部结点，而决策结果好瓜或坏瓜是叶子结点。

周志华老师一书中强调：

决策树的生成是一个递归过程。在决策树算法中有三种情形会导致递归返回：

（1）当前节点包含的样本全部属于同一个类别，无需划分。

（2）当前属性集为空，或是所有样本在所有属性集上取值相同，无法划分。此时，把当前节点标记为叶节点，并将其类别设定为该节点所含样本最多的类别。

（3）当前节点包含的样本集合为空，不能划分。此时，同样把当前节点标记为叶节点，但将其类别设定为其父节点所含样本最多的类别。

注意：(2)和(3)不同，(2)是后验概率，(3)是把父节点的样本分布作为当前节点的先验概率。

2、ID3（信息增益）

先看一个定义，信息熵：度量样本集合纯度最常用指标，假定当前样本集合D中第k类样本所占的比例为Pk（k=1,2，…，|y|），则D的信息熵为：

E(D)值越小，则D的纯度越高。

而对于样本离散属性，用a对样本进行划分得到样本D，所以属性a划分样本集D获得的信息增益为：

信息增益Gain(D,a)越大，则属性a来划分样本获得的纯度提升越大。

注：该部分的示例求解可参考周志华P75，简单也易懂。

3、C4.5（信息增益率）

ID3的信息增益划分法对可取数值较多的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5算法不采用信息增益，取而代之的是信息增益率来选择最优划分特征属性。信息增益率定义为：

其中：

IV(a)称为属性a的“固有值”。属性a的可能值数目越多(即V越大)，则IV(a)的值通常会越大。

4、基尼系数（CART树）

CART决策树是一棵二叉树，内部节点特征取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。CART决策树使用“基尼系数”来选择划分属性。基尼系数的定义如下：

那么对于属性a其基尼系数即为：

Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，Gini(D)越小，则数据集D的纯度越高。

以上就是决策树的一些基础原理，有讲的不明白的可以参考：

[1] 周志华. 机器学习 : Machinelearning[M]. 清华大学出版社, 2016.

[2] Peter. 机器学习实战[M]. 人民邮电出版社

[3] https://blog.csdn.net/ice_martin/article/details/63683657

5、Python实例

下面根据实例给出python代码：

（这个例子是经典案例，利用鸢尾花数据iris，对鸢尾花进行分类。）

（1）依据原理公式，直接python实现

由于该处代码较多，看起来比较枯燥这里就不给大家直接呈现了，如有想了解的小伙伴可以通过访问我的github查看，github地址：https://github.com/superzhang90/Meet-Algorithm/blob/master/DecisionTree/DecisionTree_20180603.py

（2）引入python中scikit-learn机器学习库

#通过sklearn包进行分类

from sklearn importdatasets #导入方法类

fromsklearn.cross_validation import train_test_split

from sklearn.metricsimport accuracy_score

from sklearn.treeimport DecisionTreeClassifier

import numpy as np

import matplotlib.pyplotas plt

#加载iris 数据集

iris =datasets.load_iris('E:\Python\work\iris.txt')

#特征数据

iris_feature = iris[0]

#分类数据

iris_target = iris[1]##该处sklearn已经将分类自动转成0,1,2

feature_train,feature_test, target_train, target_test = train_test_split(iris_feature,iris_target, test_size=0.33, random_state=42)

# 参数均置为默认状态

dt_model =DecisionTreeClassifier()

# 使用训练集训练模型

dt_model.fit(feature_train,target_train)

# 使用模型对测试集进行预测

predict_results =dt_model.predict(feature_test)

print(accuracy_score(predict_results, target_test))

#获取花卉两列数据集

X = feature_test

L1 = [x[0] for x inX]

print (L1)

L2 = [x[1] for x inX]

print (L2)

#画出数据分布情况

plt.scatter(L1, L2,c=predict_results, marker='x') #cmap=plt.cm.Paired

plt.title("DTC")

plt.show()

以上就是今天介绍的决策树的三种经典方法，对于决策树的剪枝问题，下次推文的时候会详细介绍下，谢谢您的阅读！

如需要原数据及源代码，可关注公众号：遇见YI算法，发送消息给小哪吒。

也可关注我的github：

https://github.com/superzhang90/Meet-Algorithm/blob/master/DecisionTree/DecisionTree_20180603.py