2018-12-25

七天算法梳理之决策树

信息论基础

信息论的基础由香农博士于1948年奠定.下面说明关于信息论的一些基本概念.

熵

上表示一个随机变量不确定的数量.如果一个随机变量的熵越大,那么其不确定也就越大.
如果$X$为离散型变量,取值为$\mathbb R$,其概率分布为$p(x)=P(X=x),x\in \mathbb R$,那么X的熵$H(X)$定义为:

$H(X)=-\sum_{x \in R}p(x)log_2p(x)$

联合熵

联合熵其实就是描述一对随机变量平均所需要的信息量.
如果$X,Y$是一对离散型随机变量 $X,Y ~ p(x,y),X,Y$的联合熵为$H(X,Y)$为:

$H(X,Y)=-\sum_{x \in X}\sum_{y \in Y}p(x,y)logp(x,y)$

条件熵

条件熵$H(Y|X)$的意思是,在X发生的条件下,Y的不确定性有

$H(Y|X)=\sum_{x \in X}\sum_{y \in Y}p(x, y)logp(y | x)$

将联合概率进行展开后发现:

$H(X, Y)=-\sum_{x \in X}p(x)logp(x)-\sum_{x \in X}\sum_{y \in Y}p(x, y)logp(y | x) = H(X)+H(Y|X)$

信息增益

现在有属性a, 其可能有v个可能的取值,如果使用属性a来对样本D进行划分的话,易知会产生v个节点,那么所有属性为$a_v$的样本可记为$D^v$.,这时候再根据各个节点对应所占的比例$|D^v|/|D|$分配权重,就可以知道使用属性a对D进行划分的时候所获得的信息增益,也就是说使用整个样本的信息熵,减去通过属性a划分的信息熵之和就是信息增益.

现在假设样本D的信息熵为

$Ent(D)=-\sum_{k=1}^{|v|}p_klog_2p_k$

那么信息增益为:

$Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)$

基尼不纯度

基尼不纯度是CART算法划分属性所使用的度量方法,其直观上的理解是从一个数据集D中任意抽取两个样本,其类别不一致的概率.其具体的公式如下:

$Gini(D)=\sum_{k=1}{|y|}\sum_{k^{'}\neq k}(p_kp_k')$

决策树的不同分类算法

ID3算法

流程具体如下:

首先考虑样本中只有一个类或者没有属性的情况
计算各个属性的信息增益后
选择信息增益最多的属性进行节点分类,建立各个节点分支
再依次的再各个节点中进行选择计算信息增益,返回步骤2重复迭代
到达指定的退出条件,没有特征或者信息增益较小
由于ID3 算法只有生成树的过程,没有剪枝等过程,所以可能过拟合.

C4.5

首先,信息增益比的定义是信息增益G(D,a)与训练数据集熵H(D)的比

$g_R(D,a)=\frac{g(D,a)}{H(D)}$

该C4.5算法则是针对于ID3算法的改进,在生成树的过程中使用了信息增益比来选择,而不是单纯的使用信息增益
算法过程如下:
假设数据集D 特征集A 阀值ε

如果数据中均为同一个类,则返回,算法结束
如果 $A=\varnothing$, 则返回一个单节点的树,并选择实例数最多的类,为该节点的类别,算法结束
选择其中信息增益比最大的节点
再依次选择各个节点,计算当前节点的内的信息增益比,进行迭代
最终达到指定的退出条件,即信息增益比过低,或者没有更多的特征时退出算法

上面的构建的节点树都是分类树,只不过节点划分的方式不同.那么什么是回归树呢?

回归树原理

回归树对于样本的划分,通过遍历所有输入变量，找到最优的切分变量j和最优的切分点s，即选择第j个特征$x^j$和它的取值s将输入空间划分为两部分，然后重复这个操作,对于连续性的样本值非常有效.
具体算法如下

选择最优的切分变量j和最优的切分点s，求解 $min_{j,s}[min_{c_{1}}\sum_{x_{i}\in R_{1}(j,s)}(y_{i}-c_{1})^2+min_{c_{2}}\sum_{x_{i}\in R_{2}(j,s)}(y_{i}-c_{2})^2]$
遍历所有特征，对固定的特征扫描所有取值，找到使上式达到最小值的对(j,s).
用选定的对 (j,s)划分区域，并确定该区域的预测值；
继续对两个字区域调用上述步骤，直至满足停止条件；

CART分类树

CART分类树的全称是分类与回归树,主要的原理思想是将内部的节点特征取值为”是”或”否”两个值,左分支为是,右分支为否,这样整个决策树就可以在整个样本空间中求取对应的条件概率分布.
算法由特征选择和生成树以及前面两种算法所没有的剪枝构成,算法主要包括两个部分:树的生成与剪枝

CART的生成

从根节点开始，对节点计算现有特征的基尼指数，对每一个特征，例如AA，再对其每个可能的取值如aa,根据样本点对A=aA=a的结果的”是“与”否“划分为两个部分，利用

$Gini(D,A=a)=\frac{|D_{1}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})$

进行计算；在所有可能的特征AA以及该特征所有的可能取值a中，选择基尼指数最小的特征及其对应的取值作为最优特征和最优切分点。然后根据最优特征和最优切分点，将本节点的数据集二分，生成两个子节点
对两个字节点递归地调用上述步骤，直至节点中的样本个数小于阈值，或者样本集的基尼指数小于阈值，或者没有更多特征后停止；

CART的剪枝

剪枝就是对生成的树进行裁剪简化的过程,其一般是通过极小化决策树整体的损失函数或代价函数来实现.
CART的剪枝是通过两个步骤:

从树的底部不断地剪枝直到根节点,形成对应的子树序列
通过交叉验证法,对子树的序列进行测试,并从中选取最优的子树

决策树防止过拟合手段

决策树过拟合主要有两个手段,分别为early stopping与剪枝.

earlystopping:限制选取的分类节点的总数,树的深度,节点中的实例数,阈值等
剪枝,即当前节点的划分无法带来决策树泛化性能的提升,增删除对应的节点

模型评估

可以使用之前梳理的AUC ROC 交叉验证随机抽样等方法,这里就不再赘述了.

python可视化决策树与对应的函数实现

import pydotplus
from sklearn.datasets import load_iris
from sklearn import tree
import collections
# Data Collection
X = [ [180, 15,0],     
      [177, 42,0],
      [136, 35,1],
      [174, 65,0],
      [141, 28,1]]

Y = ['man', 'woman', 'woman', 'man', 'woman']    

data_feature_names = [ 'height', 'hair length', 'voice pitch' ]
# Training
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X,Y)
# Visualize data
dot_data = tree.export_graphviz(clf,
                                feature_names=data_feature_names,
                                out_file=None,
                                filled=True,
                                rounded=True)
graph = pydotplus.graph_from_dot_data(dot_data)

colors = ('turquoise', 'orange')
edges = collections.defaultdict(list)

for edge in graph.get_edge_list():
    edges[edge.get_source()].append(int(edge.get_destination()))

for edge in edges:
    edges[edge].sort()    
    for i in range(2):
        dest = graph.get_node(str(edges[edge][i]))[0]
        dest.set_fillcolor(colors[i])

graph.write_png('tree.png')

主要的函数为

参考

统计自然语言处理-宗成庆
 机器学习-周志华
 统计学习方法-李航
 决策树(分类树、回归树
 Decision tree visual example

版权声明:本文由littleji.com创作并发表,转载请注明作者及出处,欢迎关注公众号:littleji_com
本文遵守CC BY0SA 4.0
if you have any questions, please leave a message behind or give an issue

本文链接为：https://blog.littleji.com/2018/12/25/20181225MLReview3/

littleji

a blog