决策树算法解析

设样本有$m$个类别，$v$是属性中不同值的数量

ID3算法-信息熵

信息量

分类所期望的信息量: $I=-\sum_{i=1}^{m}\frac{s_{i}}{s}log_{2}(\frac{s_{i}}{s})$

信息熵（加权）

为了得到准确的分类还需要多少期望信息量，即让划分的每种属性都有相同的类别。值越小分类就越准确

$$E(属性A)=\sum_{j=1}^{v}\frac{s_{1j}+\dotsb+s_{mj}}{s}I(s_{1j},\dotsc,s_{mj})$$

可理解为将该属性划分的每个节点的信息熵加权平均得到的$E(属性)$

信息增益

信息增益=原来的信息期望量-基于属性划分后的信息需求。基于属性划分后的信息需求即信息熵越小，信息增益就越大。故应选择这样的划分。

$$Gain(属性A)=I-E(属性A)$$

C4.5算法-信息增益率

为了解决与每个划分相关联的记录太少，以致预测不可靠。把属性测试条件产生的输出也考虑进去。

分裂信息（Split Info）

$$SplitInfo=-\sum_{i=1}^{k}P(v_{i})log_{2}P(v_{i}),k是划分总数，v_{i}是子女节点样本数占比$$

信息增益率（Gain Ratio）

$$GainRatio=\frac{\Delta_{info}}{SplitInfo}$$

增益率可以说明：大量的划分会导致信息增益率很小

$$k是属性的划分总数，若每个属性值有着相同的样本数n，则父节点有kn个样本。\\ 则P(v_{i})=\frac{n}{kn}=\frac{1}{k},SplitInfo=-\sum_{i=1}^{k}\frac{1}{k}log_{2}\frac{1}{k}=log_{2}k$$

属性划分$k$越大，会导致$SplitInfo$越大，则$GainRatio$越小

CART算法-Gini不纯度

Gini不纯度（指数）

$p(i|t)-节点t中属于类i的记录占比$

$$Gini(t)=1-\sum_{i=0}^{c-1}[p(i|t)]^2,c是类别数量$$

Gini指标的加权平均

不纯性度量的总结

不纯性度量的意义：不纯性度量的值越大，说明划分效果越差。当所有样本属于同一个类时，不纯性度量的值最小。

• $Entropy(t)=-\sum_{i=0}^{c-1}p(i|t)log_{2}p(i|t)$
• $Gini(t)=1-\sum_{i=0}^{c-1}[p(i|t)]^2$
• $ClassificationError(t)=1-\max_{i}[p(i|t)]$

最大化增益$\Delta$:

$$\Delta=I(parent)-\sum_{j=1}^{k}\frac{N(v_{j})}{N}I(v_{j})$$

（其中$I(\cdot)$是节点的不纯性度量，$N$是父节点上的样本总数，$k$是不同属性值的个数，$N(v_{j})$是与子女节点$v_{j}$关联的节点数。）