决策树与随机森林笔记

1. 信息熵

信息熵

熵是随机变量不确定性的度量。设X是一个取有限个值的离散随机变量,其分布为:P(X = xi) = pi , i = 1,2,3..n

则随机变量X的熵定义为:

image-20220803164634333

表示为一种变量的期望,概率小,信息越大。

对于二项分布:H(X) = -plnp - (1-p)ln(1-p),图像如下:

当概率为1或者0时,信息熵等于0,当概率为0.5时,信息熵最大。

信息熵表达为随机变量不确定性的度量。

条件熵

条件熵H(Y|X) 表示在已知变量X的条件下,随机变量Y的不确定性。定义为:

信息增益

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

代表着特征A对信息不确定性的衡量

信息增益比

以信息增益作为划分训练集的特征,存在偏向于选择取值较多的特征的问题。这时候可以使用信息增益比。

2. 决策树

决策树模型是一种描述对实例进行分类的树形结构。

开始时,构建根结点,将所有训练数据都放在根结点;

选择一个最优特征,按照这一特征将训练数集分割成子集;

如果子集已经被能够被正确分类,则构建叶节点,如果不能,在对子集进行递归。

ID3与C4.5 决策树生成

ID3采用信息增益;C4.5采用信息增益比计算。

决策数剪枝

决策树很容易过拟合,随着树的深度变深,在训练集上的表现越好,但在测试集上越差,于是树的剪枝,主要限制树的深度。决策树剪枝通过极小化决策树整体的损失函数来实现:

叶子节点个数为|T|,t是树T的叶节点,该叶节点有Nt个样本点,Ht(T)为叶节点t上的信息熵,α>=0是系数。

这个损失函数是平衡准确性与树的复杂性(节点个数),叶子节点越多,也可以分的就越精细,信息熵就越小,但叶子节点数就会越大。

3. CART

CART(classification and regression tree)分类回归树是应用最广泛的决策树。

特征选择

CART采用基尼指数来选取最优特征:

Gini(D)表示集合D的不确定性,越平均不确定性越大;Gini(D,A)表示A = a分割后集合D的不确定性。

基尼指数与信息熵作用类似,关系如下:

用 -X +1 近似 -lnX,基尼系数是信息熵的一阶近似。

生成算法

剪枝算法

这里使用的损失函数使用的是Cα(T) = C(T) + α|T|,表示参数为α时字数T的整体损失,C(T)表示基尼指数。

之前的决策树α是固定值,CART用递归的方法对树进行剪枝。将α从小增大,分成一系列区间[a0, a1...an} ,从而对应着一系列的最优子树序列{T0, T1...Tn}

C(t)以t为单结点的基尼指数,C(Tt)是以t为根的子树的基尼指数。

4. 随机森林RF

  • 样本和特征上做随机

    多样性

  • 样本上做随机

    从样本上有放回的取数据,做成不同的数据集,再训练不同的决策树,从而形成随机森林。

    这个过程也被成为Bagging

    image-20220804123928333

    大约有 (1 - 1/m)^m ≈ 1/e 个样本不会出现在采样后的数据集中。

  • 特征随机

    随机选择一个特征子集,再做成训练集,生成不同的决策树,再组成随机森林。

  • 随机森林

    随机森林常常使用决策树作为基本分类器。可以使用SVM,逻辑回归等模型,但它们被称为强分类,效果未必好。

  • 样本不均衡问题

    1. 对大类进行降采样
    2. 对小类进行过采样
  • 应用:样本相似度

    若两样本同时出现在相同叶子节点的次数越多,则二者越相似。

    image-20220804135730552

  • 应用:计算特征重要度

    使用经过节点的数量、Gini系数等指标衡量特征的重要度。

5. 尾声

决策树是数据模型,能否将逻辑与数据结合起来,形成一种既有逻辑又有树的形式?

工作流引擎可以看成一种逻辑树,MapReduce也可以看成一种逻辑树。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×