ID决策树的构造原理_数据结构

前言

学习目标

了解决策树算法的基本思想
掌握 id3 决策树的构建原理

1.决策树介绍

1.1案例引入

有的同学可能在大学学习过一门课程叫《数据结构》，里面有一个重要的结构就是“树”，和现实生活中的树一样，树的主要由四部分树根、树干、树枝、树叶组成，今天的决策树也是一种树结构，大家学习的时候可以想象现实生活中的树来来理解。

决策树算法是一种监督学习算法，英文是decision tree。

决策树思想的来源非常朴素，试想每个人的大脑都有类似于if-else这样的逻辑判断，这其中的if表示的是条件，if之后的then就是一种选择或决策。程序设计中的条件分支结构就是if-then结构，最早的决策树就是利用这类结构分割数据的一种分类学习方法。

比如：你母亲要给你介绍男朋友，是这么来对话的：

女儿：多大年纪了？

母亲：26。

女儿：长的帅不帅？

母亲：挺帅的。

女儿：收入高不？

母亲：不算很高，中等情况。

女儿：是公务员不？

母亲：是，在税务局上班呢。

女儿：那好，我去见见。

于是你在脑袋里面就有了下面这张图

作为女孩的你在决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。

1.2构建决策树的三个步骤

特征选择：选取有较强分类能力的特征（定性分析问题还是定量分析问题等等）
决策树生成
决策树剪枝（让决策树更加简洁高效，对于一些特征不重要，或根据权值大小，对决策树的分类进行筛选）

决策树api：

from sklearn.tree import decisiontreeclassifier
from sklearn.tree import plot_tree

2.id3决策树

2.1信息熵

id3 树是基于信息增益构建的决策树.

定义

熵在信息论中代表随机变量不确定度的度量
熵越大，数据的不确定性度越高
熵越小，数据的不确定性越低

公式：

$\large h = -\sum_{i=1}^{k}p_i\log(p_i)$

公式的转换，当数据类别只有两类的情况下，公式可以做如下转换：

代码角度理解信息熵的概念

import numpy as np
import matplotlib.pyplot as plt

def entropy(p):
    return -p*np.log(p)-(1-p)*np.log(1-p)

x = np.linspace(0.01,0.99,200)
plt.plot(x,entropy(x))
plt.show()

2.2 信息增益

2.2.1定义

特征 $a$ 对训练数据集d的信息增益 $g(d,a)$ ，定义为集合 $d$ 的经验熵 $h(d)$ 与特征a给定条件下d的经验熵 $h(d|a)$ 之差。即 $\large g(d,a)=h(d)-h(d|a)$

根据信息增益选择特征方法是：对训练数据集d，计算其每个特征的信息增益，并比较它们的大小，并选择信息增益最大的特征进行划分。表示由于特征$a$而使得对数据d的分类不确定性减少的程度。

2.2.2算法

设训练数据集为d， $\mid d\mid$ 表示其样本个数。设有 $k$ 个类 $c_k$ ， $k=1,2,\cdots,k$ ， $\mid c_k\mid$ 为属于类 $c_k$ 的样本个数， $\sum\limits{k=1}^{k}=\mid{d}\mid$ 。设特征a有个不同取值 ${a_1, a_2, \cdots,a_n}$ ，根据特征a的取值将d划分为个子集 $d_1, d_2, \cdots,d_n$ ， $\mid d_i\mid$ 为样本个数， $\sum\limits{i=1}^n\mid d_i\mid=\mid d\mid$ 。子集中属于类 $c_k$ 的样本集合为 $d{ik}$ ，即 $d{ik}=d_i\bigcap c_k$ ， $\mid d{ik}\mid$ 为的样本个数。信息增益算法如下：

输入：训练数据集d和特征a；
输出：特征a对训练数据集d的信息增益

(1) 计算数据集d的经验熵 $h(d)$

$h(d)=-\sum\limits_{k=1}^{k}\frac{\mid c_k\mid}{\mid d\mid}\log_2\frac{\mid c_k\mid}{\mid d\mid}$

(2) 计算特征a对数据集d的经验条件熵 $h(d\mid a)$

$h(d\mid a)=\sum\limits{i=1}^{n}\frac{\mid d_i\mid}{\mid d\mid}h(d_i)=-\sum\limits{i=1}^{n}\frac{\mid d_i\mid}{\mid d\mid}\sum\limits{k=1}^{k}\frac{\mid d{ik}\mid}{\mid d_i\mid}\log_2\frac{\mid d_{ik}\mid}{\mid d_i\mid}$