数据挖掘——决策树巩固与 Python 实现

bigdataway 提交于 周一, 04/16/2018 - 15:15

决策树(decision tree)是一种类似于流程图的树结构(可以是二叉树也可以不是),其中,每个内部节点(非叶子结点)表示在一个属性上的测试,每个分枝代表该测试的一个输出,而每个叶子结点存放一个类标号。书的最顶层节点是根节点。

决策树是一种基本的分类与回归方法,它可以看作 if-then 规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。

更好的理解

以一个例子更好的理解决策树:

上面这个例子,就是用来决策顾客是否可能购买计算机。每个内部节点表示在一个属性上的测试(比如是否是学生),而每个叶子结点存放一个类标号也就是决策结果(比如 buys_computer = no/yes ),箭头表示一个判断条件在不同情况下的决策路程。

决策树可以运用在诸多领域。

决策树学习算法构成

主要构成有三个部分:

  • 特征选择
  • 决策树生成
  • 决策树的剪枝

决策树的路径具有一个重要的性质: 互斥且完备 ,即每一个样本均被且只能被一条路径所覆盖。

特征选择

如果利用一个特征进行分类的结果与随机分类的结果无异,则可以认为这个特征是不具备分类能力的。把这样的特征去掉,对决策树的分类精度应该影响不大。

那如何判断一个特征的分类能力呢?比如说在上面那个图中,为什么将 age 属性作为第一个分类,而不是 student 或者 credit_rating 呢?

这就需要「信息增益」这个概念,需要一些准备知识。

熵(entropy)

熵表示随机变量的不确定性,熵值越大表示随机变量含有的信息越少,变量的不确定性越大。 随机变量 X 的熵的表达式为:

P(X = xi) = pi,i = 1, 2, …, n,是 X 的概率分布。

联合熵

上面那个是一个变量 X 的熵,多个变量的联合熵,比如两个变量 X 和 Y 的联合熵表达式为:

联合熵是一集变量之间不确定性的衡量手段。

条件熵

随机变量 X 给定的条件下,随机变量 Y 的条件熵 H(Y|X) 定义为:

信息增益(information gain):

信息增益是指: 得知特征 X 的信息而使得类 Y 的信息的不确定性减少的程度

特征 A 对训练集 D 的信息增益记为 g(D, A) ,定义为集合 D 的经验熵 H(D) ,与特征 A 给定条件下 D 的熵 H(D|A) 之差,即:

根据信息增益准则进行特征选择的方法是:对训练数据集D,计算其每个特征的信息增益,并比它们的大小,从而选择 信息增益最大 的特征。

信息增益比(information gain ratio)

以信息增益作为特征选择准则,会存在偏向于选择取值较多的特征的问题。可以采用信息增益比对这一问题进行校正。

特征 A 对训练集 D 的信息增益比定义为其信息增益与训练集 D 关于特征 A 的值的熵之比,即

其中,

决策树的生成

决策树的生成算法有很多变形,这里介绍几种经典的实现算法:ID3 算法,C4.5 算法以及 CART 算法。这些算法的主要区别在于分类结点上特征选择的选取标准不同。下面详细了解一下算法及其具体实现过程。

具体例题可参考《数据挖掘概念与技术》一书。

数据

数据来源于《数据挖掘概念与技术》书中。以下实现均基于这个数据。

RID age income student credit_rating Class: buys_computer
1 youth high no fair no
2 youth high no excellent no
3 middle_aged high no fair yes
4 senior medium no fair yes
5 senior low yes fair yes
6 senior low yes excellent no
7 middle_aged low yes excellent yes
8 youth medium no fair no
9 youth low yes fair yes
10 senior medium yes fair yes
11 youth medium yes excellent yes
12 middle_aged medium no excellent yes
13 middle_aged high yes fair yes
14 senior medium no excellent no

ID3 算法及实现

ID3 算法的核心是在决策树各个结点上应用信息增益准则进行特征选择。

  • 从根节点开始,对结点计算所有可能特征的信息增益,选择信息增益最大的特征作为结点的特征,并由该特征的不同取值构建子节点;
  • 对子节点递归地调用以上方法,构建决策树;
  • 直到所有特征的信息增益均很小或者没有特征可选时为止。

Python 实现

# 待更

C4.5 算法及实现

由 ID3 算法演化而来。

C4.5 算法与 ID3 算法的区别主要在于它在生产决策树的过程中,使用信息增益比来进行特征选择。

Python 实现

# 待更

CART 算法及实现

由 ID3 算法演化而来。

CART 算法假设决策树是一颗二叉树,它通过递归地二分每一个特征,将特征区间划分为有限个单元,并在这些但愿上确定预测的概率分布。

CART 算法中,对于回归,采用的是「平方误差最小化」准则;对于分类,采用的是「基尼指数最小化」准则。

平方误差最小化

假设已将输入空间划分为 M 个单元,并且在每个单元 R1, R2, …, Rm,并且在每个 单元 Rm 上有一个固定的输出值 Cm ,于是回归树可以表示为:

当输入空间的划分确定时,可以用平方误差

来表示回归树对于训练数据的预测误差。

基尼指数

这里讲的是分类,所以先重点了解基尼指数。

基尼指数是度量数据分区和训练元组集 D 的不纯度。

假设有 m 个类别,样本点属于第 i 类的概率为 Pi,则概率分布的基尼指数定义为:

对每个属性,需要考虑每种可能的二元化分。对于 离散值 属性,选择该属性产生 最小基尼指数 的子集作为它的分裂子集。而对于 连续值 属性,必须考虑每个可能的分裂点。

对于样本 D,如果根据特征 A 的某个值 a,把 D 分成 D1 和 D2 两部分,则在特征 A的条件下,D 的基尼系数表达式为:

对于离散或连续值属性 A 的二元划分导致的不纯度降低为:

选择产生 最小基尼指数 的属性作为分裂属性。