决策树算法

冷不防 2021-12-14 05:59 282阅读 0赞

### 决策树是怎么回事？ ###

其实就是对实例进行分类的**树形结构**。决策树由**节点**（node）和**有向边**（directed edge）组成。节点包括内部节点（internal node）和叶节点（leaf node）。内部节点表示一个属性或特征，叶结点表示一个类。  
这是一个非常简单的分类器，关于它更细致的描述这里就不再赘述，我们谈论几个要点：熵（entropy）、条件熵、Gini系数、预剪枝和后剪枝，连续值属性的处理等。

### 熵（entropy） ###

熵就是描述一个系统或一系列事件的混乱程度或者不确定程度，熵值越大，不确定性越大；熵值越小，不确定性越小。  
在机器学习中，描述事件的不确定性我们利用的是统计学知识中的概率，概率能描述一件事情发生的可能性大小，但是却描述不了事件的混乱程度，而熵就这样应运而生了。

设 X X X是一个取有限个值的离散随机变量，其概率分布（不要和分布函数混淆）为  
 P ( X = x i ) = p i , i = 1 , 2 , ⋯ &ThinSpace; , n P(X=x\_i)=p\_i,\\quad i=1,2,\\cdots,n P(X=xi)=pi,i=1,2,⋯,n则随机变量 X X X的熵定义为  
 H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X)=-\\sum^n\_\{i=1\}p\_i\\log p\_i H(X)=−i=1∑npilogpi  
若 p i = 0 p\_i=0 pi=0，则定义 0 log ⁡ 0 = 0 0\\log 0=0 0log0=0，这是显然的，因为根据极限的理论  
 lim ⁡ x → 0 + x ln ⁡ x = lim ⁡ x → 0 + ln ⁡ x 1 x = 洛 必 达 lim ⁡ x → 0 + 1 x − 1 x 2 = 0 \\underset\{x\\to0^+\}\{\\lim\}x\\ln x=\\underset\{x\\to0^+\}\{\\lim\}\\frac\{\\ln x\}\{\\frac\{1\}\{x\}\}\\xlongequal\{洛必达\}\\underset\{x\\to0^+\}\{\\lim\}\\frac\{\\frac\{1\}\{x\}\}\{-\\frac\{1\}\{x^2\}\}=0 x→0\+limxlnx=x→0\+limx1lnx洛必达x→0\+lim−x21x1=0

可以发现，熵的取值范围如下： 0 ≤ H ( X ) ≤ log ⁡ n 0\\leq H(X)\\leq \\log n 0≤H(X)≤logn  
如果在一个随机事件中，各个事件 X = x i X=x\_i X=xi的可能性都一样，即等可能发生，则此时随机事件达到了熵值的最大值。

### 条件熵（conditional entropy） ###

条件熵 H ( Y ∣ X ) H(Y|X) H(Y∣X)表示在已知随机变量 X X X的条件下随机变量 Y Y Y的不确定性或混乱程度，定义为 X X X给定条件下 Y Y Y的条件概率分布的熵对 X X X的数学期望 H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) H(Y|X)=\\sum^n\_\{i=1\}p\_iH(Y|X=x\_i) H(Y∣X)=i=1∑npiH(Y∣X=xi)这里， p i = P ( X = x i ) , i = 1 , 2 , ⋯ &ThinSpace; , n . p\_i=P(X=x\_i),i=1,2,\\cdots,n. pi=P(X=xi),i=1,2,⋯,n.

当熵和条件熵中的**概率**由数据估计（特别是极大似然估计）得到时，所得到的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）.我们在算法中经常是以**频率**估**概率**。

### 信息增益 ###

#### 信息增益定义 ####

信息增益是构建决策树时选定属性或特征的绝对指标。  
信息增益从字面意思猜测，应该是我们从中获取了多少有用信息。  
特征 A A A对训练数据集 D D D的信息增益 g ( D , A ) g(D,A) g(D,A)，定义为 g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A) g(D,A)=H(D)−H(D∣A)可见，信息增益**表征**由于特征 A A A而使得对数据集 D D D的分类的不确定性减小的程度。不同的特征，往往具有不同的信息增益，信息增益大的特征具有更强的分类能力。信息增益一般也称为互信息（mutual information）。

#### 基本记号 ####

*  设训练数据集为 D D D， ∣ D ∣ |D| ∣D∣表示样本的个数.
 *  设数据集 D D D有 K K K个类 C k ， k = 1 , 2 , ⋯ &ThinSpace; , K ， ∣ C k ∣ C\_k，k=1,2,\\cdots,K，|C\_k| Ck，k=1,2,⋯,K，∣Ck∣为属于类 C k C\_k Ck的样本个数， ∑ k = 1 K ∣ C k ∣ = ∣ D ∣ \\sum^K\_\{k=1\}|C\_k|=|D| ∑k=1K∣Ck∣=∣D∣.
 *  设特征 A A A有 n n n个不同的取值 \{ a 1 , a 2 , ⋯ &ThinSpace; , a n \} \\\{a\_1,a\_2,\\cdots,a\_n\\\} \{ a1,a2,⋯,an\}，根据特征 A A A的取值将 D D D划分为 n n n个不同的子集 D 1 , D 2 , ⋯ &ThinSpace; , D n D\_1,D\_2,\\cdots,D\_n D1,D2,⋯,Dn， ∣ D i ∣ |D\_i| ∣Di∣为 D i D\_i Di的样本个数，有 ∑ i ∣ D i ∣ = ∣ D ∣ \\sum\_i|D\_i|=|D| ∑i∣Di∣=∣D∣.
 *  记子集 D i D\_i Di中属于类 C k C\_k Ck的样本的集合为 D i k ， ∣ D i k ∣ D\_\{ik\}，|D\_\{ik\}| Dik，∣Dik∣的 D i k D\_\{ik\} Dik的样本个数.

1.  数据集 D D D的**经验熵** H ( D ) H(D) H(D)  
     H ( D ) = − ∑ k = 1 K ∣ C k ∣ ∣ D ∣ log ⁡ 2 ∣ C k ∣ ∣ D ∣ H(D)=-\\sum^K\_\{k=1\}\\frac\{|C\_k|\}\{|D|\}\\log\_2\\frac\{|C\_k|\}\{|D|\} H(D)=−k=1∑K∣D∣∣Ck∣log2∣D∣∣Ck∣
2.  计算特征 A A A对训练数据集 D D D的经验条件熵 H ( D ∣ A ) H(D|A) H(D∣A)  
     H ( D ∣ A ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ H ( D i ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ ∑ k = 1 K ∣ D i k ∣ ∣ D i ∣ log ⁡ 2 ∣ D i k ∣ ∣ D i ∣ H(D|A)=\\sum^n\_\{i=1\}\\frac\{|D\_i|\}\{|D|\}H(D\_i)=-\\sum^n\_\{i=1\}\\frac\{|D\_i|\}\{|D|\}\\sum^K\_\{k=1\}\\frac\{|D\_\{ik\}|\}\{|D\_i|\}\\log\_2\\frac\{|D\_\{ik\}|\}\{|D\_i|\} H(D∣A)=i=1∑n∣D∣∣Di∣H(Di)=−i=1∑n∣D∣∣Di∣k=1∑K∣Di∣∣Dik∣log2∣Di∣∣Dik∣
3.  计算信息增益  
     g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A) g(D,A)=H(D)−H(D∣A)

#### 信息增益比 ####

*  以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题.
 *  使用**信息增益比**可以对这一问题进行**校正**，这是特征选择的**另一准则**.

其实很简单，如果特征 A A A的**取值**比较多，不仅说明特征 A A A对数据集 D D D的分类能力比较好，同时也说明特征 A A A本身的不确定性比较大，即特征 A A A自身的熵值 H A ( D ) H\_A(D) HA(D)比较大，那么如果特征 A A A自身的熵值有多大，就对关于特征 A A A的信息增益进行相应大小的惩罚，就可以纠正这一问题。

信息增益比的数学定义：  
 g R ( D , A ) = g ( D , A ) H A ( D ) g\_R(D,A)=\\frac\{g(D,A)\}\{H\_A(D)\} gR(D,A)=HA(D)g(D,A)其中， H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ log ⁡ 2 ∣ D i ∣ ∣ D ∣ H\_A(D)=-\\sum^n\_\{i=1\}\\frac\{|D\_i|\}\{|D|\}\\log\_2\\frac\{|D\_i|\}\{|D|\} HA(D)=−i=1∑n∣D∣∣Di∣log2∣D∣∣Di∣  
 n n n是特征 A A A取值的个数， H A ( D ) H\_A(D) HA(D)是计算属性本身的熵值，不要**搞混**了.

*  ID3算法的核心是在决策树各个结点上应用**信息增益**准则选择特征，递归的构建决策树；
 *  C4.5算法与ID3算法相似，但是应用了**信息增益比**选择特征。

### CART算法 ###

CART即Classification And Regression Tree.  
决策树的生成就是递归的构建二叉决策树的过程，对**回归树**用**平方误差最小化**准则，对于**分类树**用**基尼指数**（Gini index）最小化的准则，进行特征选择，生成二叉树。

#### 回归树生成算法（参考李航） ####

在训练数据集所在的空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建**二叉**决策树。  
具体的算法查看《统计学习方法》5.5节及《西瓜书》4.4节，这里我主要描述下怎么在特定切分变量 j j j上寻找最优切分点  t t t.  
这里其实可以用**试点发**不断逼近最优的切分点 t t t，但是在这里边的步长可以放大，最优切分点已经变成最优切分区间了，具体又是怎么做呢？

给定样本集合 D D D和连续属性 a a a，假定  a a a 在 D D D上出现了  n n n 个不同的取值，则将这些值从小到大排列，记为 \{ a 1 , a 2 , ⋯ &ThinSpace; , a n \} \\\{a^1,a^2,\\cdots,a^n\\\} \{ a1,a2,⋯,an\}，基于划分点  t t t 可将 D D D分为子集 D + − 和 D + − D^-\_+和D^-\_+ D\+−和D\+−，对于相邻的属性取值 a i 与 a i + 1 a^i与a^\{i+1\} ai与ai\+1来说， t t t 在区间 \[ a i , a i + 1 ) \[a^i,a^\{i+1\}) \[ai,ai\+1)中取任意值所产生的划分结果都相同，因此对于连输属性 a a a，我们可考察包含 n − 1 n-1 n−1个元素的候选划分点集合：  
 T a = \{ a i + a i + 1 2 ∣ 1 ≤ i ≤ n − 1 \} T\_a=\\left\\\{\\frac\{a^i+a^\{i+1\}\}\{2\}|1\\leq i\\leq n-1\\right\\\} Ta=\{ 2ai\+ai\+1∣1≤i≤n−1\}然后我们可以像离散属性值一样来考察这些划分点，选择最优的划分点进行样本集合的划分。

《统计学习方法》是利用**平方误差最小化**准则，《西瓜书》是利用**信息增益最大化**的准则，二者其实并不矛盾，是一致的。这里参考西瓜书的方法，  
 g ( D , a ) = max ⁡ t ∈ T a   g ( D , a , t ) = max ⁡ t ∈ T a   g ( D ) − ∑ λ ∈ \{ − , + \} ∣ D t λ ∣ ∣ D ∣ g ( D t λ ) \\begin\{aligned\}g(D,a)&=\\underset\{t\\in T\_a\}\{\\max\} \\ g(D,a,t)\\\\ &=\\underset\{t\\in T\_a\}\{\\max\} \\ g(D)-\\sum\_\{\\lambda\\in\\\{-,+\\\}\}\\frac\{|D\_t^\\lambda|\}\{|D|\}g(D^\\lambda\_t) \\end\{aligned\} g(D,a)=t∈Tamax g(D,a,t)=t∈Tamax g(D)−λ∈\{ −,\+\}∑∣D∣∣Dtλ∣g(Dtλ)  
其中， g ( D , a , t ) g(D,a,t) g(D,a,t)是**样本集** D D D基于划分点  t t t 二分后的信息增益，于是我们就可以使 g ( D , a , t ) g(D,a,t) g(D,a,t)最大化从而得到在属性 a a a上的最优划分点。

#### CART分类树的生成 ####

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点.

CART分类树的生成机制和ID3算法、C4.5算法生成决策树的机制一样，只是CART算法利用了Gini指数衡量某一特征给数据集分类带来的**不确定性减小的程度**，对应于ID3和C4.5中的信息增益。

下面我们仅描述Gini指数。

##### Gini指数 #####

基尼指数和熵都是针对随机事件的不确定性进行衡量，二者殊途同归；同时也可以把**基尼指数**近似看成是**熵**的**一阶泰勒展开**。

*  **基尼指数**的定义  
    分类问题中，假设有 K K K个类，样本点属于第 k k k类的概率为 p k p\_k pk，则概率分布的基尼指数定义为： G i n i ( p ) = ∑ k = 1 K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 \{\\rm Gini\}(p)=\\sum^K\_\{k=1\}p\_k(1-p\_k)=1-\\sum^K\_\{k=1\}p\_k^2 Gini(p)=k=1∑Kpk(1−pk)=1−k=1∑Kpk2  
    对于给定的样本集合 D D D，其基尼指数为： G i n i ( p ) = 1 − ∑ k = 1 K ( ∣ C k ∣ ∣ D ∣ ) 2 \{\\rm Gini\}(p)=1-\\sum^K\_\{k=1\}\\left(\\frac\{|C\_k|\}\{|D|\}\\right)^2 Gini(p)=1−k=1∑K(∣D∣∣Ck∣)2这里， C k C\_k Ck是 D D D中属于第 k k k类的样本子集， K K K是类的个数。

如果样本集合 D D D根据特征 A A A是否取**某一可能值** a a a被分割成 D 1 D\_1 D1和 D 2 D\_2 D2两部分，即  
 D 1 = \{ ( x , y ) ∈ D ∣ A ( x ) = a \} , D 2 = D − D 1 D\_1=\\\{(x,y)\\in D|A(x)=a\\\},\\quad D\_2=D-D\_1 D1=\{ (x,y)∈D∣A(x)=a\},D2=D−D1

则特征 A A A的条件下，集合 D D D的基尼指数定义为  
 G i n i ( D , A ) = ∣ D 1 ∣ ∣ D ∣ G i n i ∣ D 1 ∣ ∣ D ∣ + ∣ D 2 ∣ ∣ D ∣ G i n i ∣ D 2 ∣ ∣ D ∣ \{\\rm Gini\}(D,A)=\\frac\{|D\_1|\}\{|D|\}\{\\rm Gini\}\\frac\{|D\_1|\}\{|D|\}+\\frac\{|D\_2|\}\{|D|\}\{\\rm Gini\}\\frac\{|D\_2|\}\{|D|\} Gini(D,A)=∣D∣∣D1∣Gini∣D∣∣D1∣\+∣D∣∣D2∣Gini∣D∣∣D2∣从以上的表述不难看出，在基于某一属性生成决策树时，不管该属性有多少不同的取值，都是按照二分法处理，即生成的是**二叉树**。

### 剪枝处理（pruning） ###

剪枝是决策树学习算法对付“过拟合”的主要手段。

*  《西瓜书》的剪枝策略：决策树剪枝的基本策略有“**预剪枝**”和\*\*“后剪枝\*\*”。具体描述请参考《西瓜书》4.3节，总之就是利用“**验证集**”样本考察**非叶结点**，如果将该结点对应的子树替换为**叶结点**能带来决策树泛化性能的提升，则将该子树替换为叶结点。

#### 《统计学习方法》的剪枝策略 ####

这里引进了决策树学习的损失函数、参数 α \\alpha α，模型对训练数据的也测误差 C ( T ) C(T) C(T)，以及模型的复杂度 ∣ T ∣ |T| ∣T∣，比较细碎，但是理解不难，不再繁述。