决策树学习笔记

决策树

1. 信息熵：

   解释：当前集合D中第k类样本所占的比例为p_k(k = 1, 2, ...,|y|)， Ent(D)越小，数据纯度越高

2. 离散属性a有V个可能的值{a1, a2, ..av}, 用a对样本进行划分可得到V个分支

​ 信息增益：Gain(D, a) = Ent(D)-\sum ^{V}_{k=1} \frac{|D_v|}{|D|} Ent(D^v)

​ 该值越大，则信息纯度提升也越大。划分时，选择使得纯度增加最大的属性进行划分（ID3)

1. 增益率: Gain_ratio(D, a) = Gain(D, a)/IV(a)

   其中：IV(a) = -\sum^{V}_{v=1} |D_v|/|D|*log_2(|D_v|/|D|)

   a可取的数目越多，则IV(a)的值就会越大，称为属性的固有值。一个属性种类越多，则增益率会比相同信息增益量的属性要小。相当于一个对属性分类数量的加权操作，毕竟有同一个属性的项目越多，则这个分类带来的结果会相对更准确。

2. 基尼指数

   Gini(D)反应了数据集中随机取出两个样本类别标记不一样的概率

   计算方法：

   Gini(D)=\sum^{y}_{k=1} \sum_{k'!=k} p_k*p_k' = 1-\sum^{y}_{k=1}(p_k)^2

   基尼系数越小，数据纯度越高。

   对于一个属性a的基尼指数：

   Gini_index(D, a)= \sum^V_{v=1} |D_v|/|D| Gini(D^v)

   相当于划分后每个具有属性a_v的子数据集的基尼指数的加权平均