决策树

决策树是一种树形结构，每个叶节点代表一种类别。采用自顶向下的递归方法构建。基本思想是以信息熵为度量，构造一棵熵值下降最快的树。叶节点的熵值为0.。

信息量

设随机变量 x 的分布为 P(x)，则定义 x 信息量为：I(x)=−log2​P(x)

x 和 y 同时发生的信息量为：I(x,y)=I(x)+I(y)

事件发生的概率越小，包含的信息量越大，反之越小

熵

熵代表平均信息量，表示随机变量的不确定性。定义如下：

H(X)=−x∈X∑​p(x)log2​P(x)

P(xi​) 代表随机事件 X 为 xi​ 的概率。

条件熵

在一个条件下，随机变量的不确定性。

H(y|x) 表示在事件 x 发生的前提下 y 的熵。

H(Y∣X)=x∈X∑​p(x)H(Y∣X=x)=−x∈X∑​p(x)y∈Y∑​p(y∣x)logp(y∣x)−x∈X∑​y∈Y∑​p(x,y)logp(y∣x)

信息增益

信息增益 = 熵 - 条件熵

即信息增益代表了在一个条件下，信息不确定性减少的程度。

可参考知乎上的解释：信息增益到底怎么理解呢

ID3 决策树

算法：

grow(D):
	取信息量最大的属性at
	将 D 划分为若干个子集 Di
	对每个子集 Di：
		if Di 中所有样本属于同一个类别：
			创建一个类标记的叶节点
         else:
         	grow(Di)

ID3 的优点和缺点

令 D 为训练集， |D| 为训练集中的样本数；

Di​ 是用属性 at 划分D后的子集， ∣Di​∣ 为 Di​ 中的样本数。

Dik​ 为 Di​ 中类别为 Ck​ 的样本集合，样本数 为 ∣Dik​∣。

由相对频率估算得到的熵和条件熵称为经验熵和经验条件熵。

设有 K 个类 Ck​，∣Ck​∣ 表示类 Ck​ 的样本数，那么：∑∣Ck​∣=∣D∣

经验熵为：H(D)=−∑k=1K​pk​log2​Pk​=−∑k=1K​∣D∣∣Ck​∣​log2​∣D∣∣Ck​∣​

属性 at 对训练集 D 的经验条件熵为：

H(D∣at)=∑i=1n​pi​H(Di​)=∑i=1n​∣D∣∣Di​∣​∑k=1K​∣Di​∣∣Dik​∣​log2​∣Di​∣∣Dik​∣​

信息增益：G(D, at) = H(D) - H(D|at)

信息增益越大，事件发生的确定性越大。每次划分应选择信息增益最大的属性。

C4.5 决策树

信息增益的缺点：信息增益准则倾向于选择那些有更多可能取值的属性（属性的取值范围大），因为这样会有更多的分支，叶节点包含的样本数更少，纯度更高。但这样会使得泛化能力不高，因为有更多分支不代表就是最好的分类结果。

所以 C4.5 决策树使用 “增益率” 来选择最优化分属性。

信息增益率的定义为：

其中 IV(at) 称为属性 at 的 ”固有值“。

Di​ 是用属性 at 划分D后的子集， ∣Di​ 为 Di​ 中的样本数。

属性 at 的可能取值数目越多 (n 越大)，则 IV(a) 的值越大。由此可以看出 IV(at) 对可取值数目较