决策树（decision tree）算法

算法"/>

决策树（decision tree）算法

决策树

• • ID3
  • C4.5
  • CART

决策树是一种常用的 分类和回归方法，其规则类似于IF-THEN形式。决策树学习通常包括三个步骤：特征选择、决策树生成和决策树修剪。
代表性的算法：ID3，C4.5，CART
决策树学习本质上是从训练数据集中归纳出一组分类的规则，找到一个和训练数据矛盾较小的决策树。
决策树学习用损失函数表示目标，通常情况下其损失函数是正则化的极大似然函数，我们的目的就是将损失函数最小化。

重要概念：

熵：表示随机变量不确定性的度量。
假设X是一个取有限个值的离散随机变量，其概率分布是：
P ( X = x i ) = p i , i = 1 , 2 , , . . . , n P(X=x_i)=p_i,i=1,2,,...,n P(X=xi​)=pi​,i=1,2,,...,n
随机变量X的熵的定义：
H ( X ) = − ∑ i = 1 n p i l o g 2 p i H(X)=-\sum_{i=1}^np_ilog_2p_i H(X)=−i=1∑n​pi​log2​pi​
从熵的定义就能看出，熵只依赖于X的分布，和X的取值无关。熵越大，随机变量的不确定性越大。

条件熵： H ( Y ∣ X ) H(Y|X) H(Y∣X)表示在已知随机变量X的条件下随机变量Y的不确定性。X给定的情况下Y的条件熵H(Y|X)定义为：X给定的情况下Y的条件概率分布的熵对X的数学期望。
H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) , 其 中 p i = P ( X = x i ) H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i), 其中p_i=P(X=x_i) H(Y∣X)=i=1∑n​pi​H(Y∣X=xi​),其中pi​=P(X=xi​)

当熵和条件熵中的概率由极大似然估计得到时，所对应的熵叫做经验熵，条件熵叫做经验条件熵。

信息增益：表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。定义为经验熵和经验条件熵之差。
g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A) g(D,A)=H(D)−H(D∣A)

信息增益比：纠正利用信息增益进行划分数据集的特征所存在的偏向选择取值较多的特征的问题。定义为信息增益比上熵。
g R ( D , A ) = g ( D , A ) H A ( D ) g_R(D,A)=\frac{g(D,A)}{H_A(D)} gR​(D,A)=HA​(D)g(D,A)​

ID3

思想：在决策树各个结点上利用信息增益原则进行特征选择，递归的构建决策树。
从根节点开始，计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，根据这个特征的不同取值建立子节点；递归的对子节点继续进行选择，最后构建成决策树。
假设输入训练数据集D，特征A的阈值为 ϵ \epsilon ϵ,输出决策树T
算法描述如下：
1.如果数据集D中的所有实例都属于同一类 C k C_k Ck​，直接输出决策树T，其标记就是 C k C_k Ck​。
2.IF: A = n u l l A=null A=null,则T为单节点树，并将D中实例数最大的类 C k C_k Ck​作为该节点的类标记，返回T。
3.ELSE:计算A中各特征对D的信息增益 g ( D , A ) g(D,A) g(D,A)，选择信息增益最大的特征 A g A_g Ag​。
4.IF： A g A_g Ag​的信息增益小于 ϵ \epsilon ϵ，则返回单节点的T，将D中实例数最大的类 C k C_k Ck​作为该节点的类标记。
5.ELSE：对 A g A_g Ag​的每一个可能值 a i a_i ai​，根据 A g = a i A_g=a_i Ag​=ai​将D分为若干非空子集 D i D_i Di​, D i D_i Di​中实例数最大的类作为标记，构建子节点并通过节点和子结点构建树T，返回T。
6.对第i个子节点，以 D i D_i Di​为训练集，以 A − A g A-{A_g} A−Ag​为特征集，递归调用1-5步。

C4.5

C4.5和ID3相比，改进之处就是计算采用的是信息增益比，而不是信息增益。
算法描述如下：
1.如果数据集D中的所有实例都属于同一类 C k C_k Ck​，直接输出决策树T，其标记就是 C k C_k Ck​。
2.IF: A = n u l l A=null A=null,则T为单节点树，并将D中实例数最大的类 C k C_k Ck​作为该节点的类标记，返回T。
3.ELSE:计算A中各特征对D的信息增益比 g R ( D , A ) g_R(D,A) gR​(D,A)，选择信息增益最大的特征 A g A_g Ag​。
4.IF： A g A_g Ag​的信息增益小于 ϵ \epsilon ϵ，则返回单节点的T，将D中实例数最大的类 C k C_k Ck​作为该节点的类标记。
5.ELSE：对 A g A_g Ag​的每一个可能值 a i a_i ai​，根据 A g = a i A_g=a_i Ag​=ai​将D分为若干非空子集 D i D_i Di​, D i D_i Di​中实例数最大的类作为标记，构建子节点并通过节点和子结点构建树T，返回T。
6.对第i个子节点，以 D i D_i Di​为训练集，以 A − A g A-{A_g} A−Ag​为特征集，递归调用1-5步。

CART