[数据结构与算法]datawhale吃瓜打卡Task03

第四章 决策树

• 算法原理
  将样本划分得“纯”，纯用信息熵度量。
• ID3决策树：以信息增益为准则来选择划分属性的决策树
  信息熵度量随机变量X的不确定性，信息熵越大越不确定。
  
  条件熵
  
  
  信息增益：已知属性后纯度的提升，信息熵-条件熵
  
• C4.5决策树：先选出信息增益高于平均水平的属性，然后再从中选择增益率最高的。
  信息增益准则偏好取值数目较多的属性。
  增益率对可能取值数目较少的属性有偏好。
  
• CART决策树：选择基尼指数最小的属性作为最优划分属性
  基尼值
  
  基尼指数
  
  实际划分方法
  对每个属性a的每个可能取值v，将数据集分为a=v，和a!=v。