决策树分类器

Posted on

决策树DecisionTree

决策树是基于树结构来进行决策的,以二分类任务为例,我们希望从给定训练数据集学得一个模型用以对新示例进行分类,这个把样本分类的任务,可看作对“当前样本属于正类吗?”这个问题的“决策”或“判定”过程.

这恰是人类在面临决策问题时一种很自然的处理机制，著名的例子如下：

image-20240614030412182

学习决策过程中提出的每个判定问题都是对某个属性的“测试”决策过程的最终结论对应了我们所希望的判定结果

每个测试的结果或是导出最终结论，或者导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内

从根结点到每个叶结点的路径对应了一个判定测试序列

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

决策树是从有类标号的训练元组中学习决策树,适合探测式的知识发现，高维数据;

  • 自上而下地分治构造，直到构造到叶子结点，叶子结点的测试条件如下：

    • 当前结点包含的样本全部属于同一类别；

    • 当前属性集为空，或所有样本在所有属性上取值相同；

    • 当前结点包含的样本集合为空

  • 分类的启发式方法

    • 度量：信息增益/Gini系数/信息增益率
    • ID3算法
      • 选择最高信息增益的属性作为最具分类能力的属性
      • 当前样本所需信息熵为
        $H(D)=-\sum_{i} p_i log(p_i)$
      • 利用属性A来将D分为v个部分$H(D|A)=\sum_{j\le v}\frac{|D_j|}{|D|}H(D_j)$
      • 使用A分支的信息增益
        $IG(A)=H(D)-H(D|A)$
    • C4.5算法
      • 克服划分子集自由一个类的问题，使用规范化信息增益
      • 划分带来的信息（固有值）$IV_A(D)=-\sum_{j\le v}\frac{|D_j|}{|D|}log(\frac{|D_j|}{|D|})$
      • 规范化信息增益率$GainRatio(A) = IG(D|A)/IV_A(D)$
    • Cart算法

      • Gini指数反映数据量数据分区或训练元组D的不纯度

      • $Gini(D)=1-\sum_{i} p_i^2$
        $p_i$代表元组属于类$C_i$的概率

      • 对于D的基于指标A的二元分裂$D_1,D_2$，
        $Gini_A(D)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$

      • 选择使得不纯度降低的最大化的二元划分$\Delta Gini(A)=Gini(D)-Gini_A(D)$

  • 算法：

    image-20240528034907462

  • 如何解决Overfit过拟合？

    训练样本只是真实模型下的一个抽样集，导致模型泛化能力不强；

    • 增加样本集
      • 降低模型复杂度
      • Train-Validation—Test
      • 模型选择：正则项等
    • 设定决策树的最大高度来限制树的生长
    • 先剪枝：提前终止树的构造
      • 节点分裂的度量低于阈值，划分停止
    • 后剪枝：从完全生长的树剪去树枝
      • 代价比较大

  • 决策树归纳：提取分类规则

    • 可以提取决策树表示的知识，并以IF-THEN形式的分类规则表示
    • 对从根到树叶的每条路径创建一个规则
    • 沿着给定路径上的每个属性-值对形成规则前件（”IF”部分）的一个合取项
    • 叶节点包含类预测，形成规则后件（”THEN”部分）
    • IF-THEN规则易于理解，尤其树很大时
    • 评估：
      • 覆盖率：$coverage(R)=\frac{n_{cover}}{|D|}$
      • 准确率：$accuracy(R)=\frac{n_{correct}}{n_{cover}}$
      • 解决多个规则触发的冲突：
        • 规模序：按照苛刻性度量
        • 规则序：根据类的重要性度量

在sklrean中默认的划分方式就是gini指数，默认的决策树是CART树；但是gini指数的划分趋向于孤立数据集中数量多的类，将它们分到一个树叶中，而熵偏向于构建一颗平衡的树，也就是数量多的类可能分散到不同的叶子中去了。