决策树(Decision Tree)是一种基本的分类与回归方法，是最经常使用的数据挖掘算法之一。
决策树模型呈树型结构，在分类问题中，表示基于特征对实例进行分类的过程。

决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。

基础概念

  • 信息熵&信息增益
    • 熵(entropy):熵指的是体系对混乱程度。
    • 信息论(information theory)中的熵(香农熵):是一种信息的度量方式，表示信息的混乱程度。
    • 信息增益(information gain):在划分数据集前后发生的变化称为信息增益。
  • 决策树的基本概念
    • 节点(Node):树中的每个点称为节点。根节点是树的起点，内部节点是决策点，叶节点是最终的决策结果。
    • 分支(Branch):从一个节点到另一个节点到路径称为分支。
    • 分裂(Split):根据某个特征将数据集分成多个子集的过程。
    • 纯度(Purity):衡量一个子集中样本的类别是否一致。纯度越高，说明子集中的样本越相似。

工作原理

  • 选择最佳特征：根据某种标准(如信息增益、基尼指数等)选择最佳特征进行分割。
  • 分割数据集：根据选定的特征将数据集分成多个子集。
  • 递归构建子树：对每个子集重复上述过程，直到满足停止条件(如所有样本属于同一类别、达到最大深度)。
  • 生成叶节点：当满足停止条件时，生成叶节点并赋予类别或值。

构建标注

  • 1.信息增益(Information Gain) ID3 C4.5
    • 用于分类问题，衡量选择某一特征后数据集的纯度提升。 Entropy是数据集的熵，用来衡量数据的不确定性。
    • alt text
  • 2.基尼指数(Gini Index) CART
    • 其中pi是类别i的样本占比。基尼指数越小，表示数据集越纯净
    • alt text
  • 3.均方误差(MSE)
    • 用于回归问题，衡量预测值和真实值的差异
    • MSE越小，表示回归树的预测效果越好

算法特点

  • 计算复杂度不高，输出结果易于理解，数据有缺失也能跑，可以处理不相关特征
  • 容易过拟合