欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

机器学习笔记(五)---- 决策树

程序员文章站 2024-02-03 18:00:04
...

-- 基本概念

      决策树是一种非常常见的机器学习算法,采用的是自顶向下的递归方法,利用信息熵为基本度量构造一颗熵值下降最快的树,理想情况下到叶子节点的熵值为零,对应每个叶子节点的实例都属于同一类。叶子节点对应于决策结果,节点则对应一个属性测试。相比于线性模型,树形模型更接近于人的思维方式,可以产生可视化的分类规则,产生的模型具有比较强的可解释性。

      决策树的节点,也就是属性是怎么划分的呢,先要了解几个基本概念:

      信息熵:度量样本集合纯度最常用的指标,当前数据集中第k类样本所占比例为Pk,计算公式如下,Ent(D)越小,则数据纯度越高。

      机器学习笔记(五)---- 决策树

      信息增益:计算公式如下,a是离散属性,有V个可能的取值,|Dv|/|D|是第V个属性的权重。信息增益越大,意味着使用属性a来进行划分所获得的数据纯度越大。需要注意的是,对于某一类属性,如果可取值数目较多时,信息增益会越大。

      机器学习笔记(五)---- 决策树

      信息增益率:与信息增益相反,属性的可取数目较少时,信息增益率更大,其中IV(a)称为属性a的固有值,属性a的可能数目越多(V越大),则IV(a)越大,则信息增益率则越小。

      机器学习笔记(五)---- 决策树

      基尼指数:反映了从数据集中随机抽取两个样本,其类别标记不一致的概率,越小表示数据纯度越高。
      机器学习笔记(五)---- 决策树

-- 算法介绍

      信息增益、增益率、基尼指数都是决策树划分属性的纯度度量方法,根据不同的方法,就衍生出3种不同的决策树算法:

      1、ID3算法:以信息增益为准则来选择划分属性,选择划分后信息增益最大的属性进行划分,这种算法对属性可取数目较多时有偏好。

      2、C4.5算法:选择具有最大增益率的属性作为划分属性,具体做法是先从候选划分属性中找到信息增益高于平均水平的属性,再从中选择增益率最高的作为划分属性。

      3、CART算法:选择划分后基尼指数最小的属性最为最优划分属性。

      几种算法的比较:

      ID3属于比较早期的决策树算法,倾向于选择属性划分比较多的作为分裂属性,可能会导致生成一个水平节点庞大但深度浅的树;输入变量必须是离散值,并且无法处理空值。

      C4.5对ID3做了一些改进,结合信息增益和增益率来选择分裂属性,避免了ID3中倾向于选择取值较多属性的问题,并且可以处理连续值。

      CART既可以创建分类树,也可以创建回归树。分类树中,CART树是一个二叉树,所以不适合用于离散属性取值大于2的情况,对于连续值的处理和C4.5算法基本相同。

 

-- 决策树生成示例

      这个例子是西瓜书上的,比较好理解,有一份描述西瓜是好瓜还是坏瓜的数据集,共有17个样本,每条数据有6个属性,数据集如下:

机器学习笔记(五)---- 决策树

(1)以ID3算法为例生成决策树,先计算各个属性划分后的信息增益:

机器学习笔记(五)---- 决策树

(2)发现“纹理”属性的信息增益最大,则选择它作为分裂属性,得到下列图:

机器学习笔记(五)---- 决策树

 (3)接着对每个分支再进行分裂,以第一个分支为例,对属性继续计算信息增益,发现“根蒂”、“脐部”、“触感”3个属性的信息增益一样,可以随机选择一个继续分裂。

机器学习笔记(五)---- 决策树

 (4)图中{“根蒂=蜷缩”}这个节点已经全部是好瓜类型,则不需要继续分裂,递归返回

机器学习笔记(五)---- 决策树

(5)针对每一个节点递归应用上面的分裂方法,最后得到一个完整决策树:

机器学习笔记(五)---- 决策树

-- 剪枝处理

      决策树分支过多,太庞大的话容易导致过拟合,可以通过“剪枝(pruning)”的方法来降低过拟合风险。剪枝的基本策略分为“预剪枝”和“后剪枝”。

      预剪枝:在决策树生成过程中,对每个节点在分裂前进行估计,若当前节点的划分不能带来决策树泛化性能提升,则停止分裂,并将当前节点标记为叶节点并返回。下图是针对西瓜数据集的预剪枝处理,可以发现比原决策树精简了很多。

机器学习笔记(五)---- 决策树

      后剪枝:先通过算法生成一棵完整的决策树,然后自底向上的对非叶节点进行考察,若将该节点对应的子树替换为叶节点能带来决策树泛化能力的提升,则将该子树替换为叶节点。下图是针对西瓜数据集的后剪枝处理。

机器学习笔记(五)---- 决策树

      从上面预剪枝和后剪枝的例子看,一般情况下后剪枝比预剪枝保留了更多的分支,后剪枝的泛化性能一般更优,欠拟合风险更小;但由于后剪枝是自底向上对各节点进行考察,其训练时间及开销比预剪枝更大。

 

-- 特征连续值处理

      特征属性如果是连续值的话,可取值数目是无限的,不能按照离散值那样通过可取值数目来进行节点划分,最常用的办法是二分法。

      数据集D和连续值属性a,假设a在D中出现了n个不同的取值,先把这些值从小到大排序,可以考察包含n-1个候选划分点集合:

机器学习笔记(五)---- 决策树

       即把每两个取值点的中位点作为候选划分点,然后计算每个划分点之后的信息增益,选取信息增益最大的划分点进行分裂,也就是需找使Gain(D,a,t)最大的划分点。

机器学习笔记(五)---- 决策树

-- sklearn决策树可视化

      sklearn其实已经将模型封装得非常好,上面提到的很多细节都已经被屏蔽了,通过模型参数可以对其进行调节,以鸢尾花数据集为例,学习使用下决策树模型。

"criterion"参数填写“entropy”表示采用C4.5算法,“gini”表示采用CART算法

-Python 代码

from sklearn import datasets
from sklearn.cross_validation import train_test_split
from sklearn.metrics import accuracy_score
from sklearn import tree
from sklearn.externals.six import StringIO
import pydotplus

data_iris = datasets.load_iris()
x, y = data_iris.data, data_iris.target
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size = 0.3,random_state = 0)

# 通过C4.5算法决策树模型进行预测
model = tree.DecisionTreeClassifier(criterion="entropy")
model.fit(x_train, y_train)
y_pred = model.predict(x_test)
print(accuracy_score(y_test, y_pred))

# 决策树可视化
dot_data = StringIO()
tree.export_graphviz(model,out_file = dot_data,
                     feature_names=data_iris.feature_names,
                     class_names=data_iris.target_names,
                     filled=True,rounded=True,special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
graph.write_pdf("Tree.pdf")

 生成的决策树可视化图如下:

机器学习笔记(五)---- 决策树

      这个决策树可视化图信息比较完整,以顶层的3个节点为例看看决策树是怎么分生成的:

      节点1(根节点):一共有105个样本(samples=105),3种鸢尾花类别的分布情况value=[34,32,39];通过二分法找出划分点是petal width <=0.75,,信息增益为1.58;如果在此节点停止分裂,则在这个节点上的数据都会被判定为"virginica"类别(class=virginica,以当前数目最多的类别为准)。

      节点2:petal width<=0.75的样本都被分到这个节点,样本数为34,信息增益为0,说明该节点数据已经“纯净”,value=[34,0,0],该数据集所有数据都属于类别“setosa”,停止分裂。

      节点3:petal width>0.75的样本被分到这个节点,样本数为71;通过二分法找到的划分点是 petal length<=4.95,信息增益为0.993,如果在此节点停止分裂则在此节点的数据都被判定为“virginica”类别。

      节点n:...... 自顶向下,完成整个决策树的分裂。

      通过完整的决策树可以发现,所有的叶子节点的数据都是“纯净”的,但在很多时候,特别是数据量大,类别较多的情况下,如果要做到每个叶子节点数据都“纯净”的话,整个决策树非常复杂,开销太大,所以一般会对数据“纯净”相关的参数例如信息增益、基尼系数等做限制,在小于某个阈值之后就不再分裂了,在DecisionTreeClassifier分类器中是通过"min_impurity_split"参数限制的。

作者:华为云专家周捷