决策树

决策树

定义：对实例进行分类的树形结构，通过多层判断区别所属目标

本质：通过多层判断，从训练数据集中归纳出一组分类规则

优点

  • 计算量小， 运算速度快
  • 易于理解，可清晰查看各个属性的重要性

缺点

  • 忽略属性间的相关行
  • 样本类别分布不均匀时，容易影响模型表现

**ID3:**利用信息熵原理选择信息增益最大的属性进行分类属性，递归的拓展决策树的分支，完成决策树的构造

信息熵：度量随机变量不确定的指标，熵越大，变量的不确定性就越大。假定当前样本集合D中第k类样本所占的比例为: p_x,则D的信息熵为：
$$
Ent(D)= -\sum_{k=1}^{|y|}p_k\log_2p_k
$$
根据信息熵可以计算以属性a进行样本划分带来的信息增益：
$$
Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{D^v}{D}Ent(D^v)
$$
V为根据属性a划分出的类别数，D为当前样本总数，D^v为类别v样本数

image-20210317205321739

目标：划分后样本分布不确定性尽可能小，即划分后信息熵小，信息增益大

例子：image-20210317210017020

image-20210317210143861