文章目录

• 什么是决策树
• 熵、条件熵
• ID3、C4.5
• CART

什么是决策树

      决策树可以简单理解为是一种根据特征信息不断分裂，直至达到某一阈值（可以是max_depth、min_node_leafs等）分裂结束，就是一串的if…then…结构。那么谁作为第一个if判断的特征呢？这就需要熵、条件熵、信息增益登场了。

熵、条件熵

      熵是表示随机变量Y不确定的度量，熵越大则越混乱越无法确定；越小则越肯定，例如拜登是男的，entropy=0。下面是熵的计算公式：
e n t r o p y = H ( D ) = ∑ i = 1 n p i ∗ l o g ( p i ) entropy=H(D)=\displaystyle\sum_{i=1}^{n} p_i*log(p_i) entropy=H(D)=i=1∑n​pi​∗log(pi​)
      条件熵是表示在已知随机变量X的条件下，随机变量Y的不确定性。有钻研精神的小伙伴可以去了解KL散度等相关知识（我不会…)
H ( Y ∣ X ) = ∑ i = 1 n p i ∗ H ( Y ∣ X = x i ) H(Y|X)=\displaystyle\sum_{i=1}^{n} p_i*H(Y|X=x_i) H(Y∣X)=i=1∑n​pi​∗H(Y∣X=xi​)
当熵和条件熵中的概率由数据估计（特别是由极大似然估计），所对应的熵和条件熵分别被称为经验熵(empirical entropy)和经验条件熵(conditional empirical entropy)，此外定义当p=0是，熵为0.
      信息增益（infomation gain)表示知道特征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)

举一个例子，贷款申请样本数据

年龄	有工作	有房子	信誉	是否放贷
青年	否	否	一般	否
青年	否	否	好	否
青年	是	否	好	是
青年	是	是	一般	是
青年	否	否	一般	否
中年	否	否	一般	否
中年	否	否	好	否
中年	是	是	好	是
中年	否	是	非常好	是
中年	否	是	非常好	是
老年	否	是	非常好	是
老年	否	是	好	是
老年	是	否	好	是
老年	是	否	非常好	是
老年	否	否	一般	否

ID3、C4.5

     ID3算法就是算每一个特征的信息增益，把信息增益最大的作为根节点，当确定好该特征，之后该特征将不再参与。上代码

from math import log2
def e(p):
    # calculate entropy
    return -p * log2(p) if p != 0 else 0
    
totalE = e(9 / 15) + e(6 / 15)
# conditional entropy of age
e1 = 1 / 3 * (e(2 / 5) + e(3 / 5)) * 2 + 1 / 3 * (e(4 / 5) + e(1 / 5))
# conditional entropy of job
e2 = 1 / 3 * e(0) + 2 / 3 * (e(4 / 10) + e(6 / 10))
# conditional entropy of house
e3 = 6 / 15 * e(0) + 9 / 15 * (e(3 / 9) + e(6 / 9))
# conditional entropy of credit
e4 = 5 / 15 * (e(1 / 5) + e(4 / 5)) + 6 / 15 * (e(2 / 6) + e(4 / 6))

计算后第三个特征的信息增益最大，也就是把是否有房子作为根节点。那下面怎么分呢？


上图对应了没有房子的人，6个不贷款，3个放贷。然后按照前面的方法重复选择信息增益最大的特征作为下一个节点作为分裂依据。

e_nohouse = e(3 / 9) + e(6 / 9)
e21 = 4 / 9 * (e(1 / 4) + e(3 / 4)) + 2 / 9 * e(1) + 3 / 9 * (e(2 / 3) + e(1 / 3))
e22 = 7 / 9 * (e(1 / 7) + e(6 / 7)) + 2 / 9 * e(1)
e23 = 4 / 9 * (e(2 / 4) * 2)  # 找贷款
a = {'age': -e21, 'job': -e22, 'loan': -e23}
print('下一个分裂特征是：%s' % max(a, key=a.get))

循环的判断，这样一颗树就构成了，通常可以事先定义好停止分裂的条件。

ID3算法缺点：
     1）无法处理缺失值
     2）偏爱特征取值多的特征
     3）无法处理连续值
     4）无法剪枝，容易过拟合

      信息增益率 是表示特征A对训练集D的信息增益率 g R ( D , A ) g_R(D,A) gR​(D,A)定义为其信息增益g(D，A)与训练数据集D的经验熵H(D)之比：
g R ( D , A ) = g ( D , A ) / H ( D ) g_R(D,A)=g(D,A)/H(D) gR​(D,A)=g(D,A)/H(D)

CART

     全名叫分类回归树。既可以分类，又可以回归，它的二叉树。它采用基尼系数来判断不纯度。，在分类问题中，假设有K个类别，第k个类别的概率为pk, 则基尼系数的表达式为
g i n i ( p ) = ∑ k = 1 k p k ∗ ( 1 − p k ) = 1 − ∑ k = 1 k p k 2 gini(p)=\displaystyle\sum_{k=1}^{k} p_k*(1-p_k)=1-\displaystyle\sum_{k=1}^{k} p_k^2 gini(p)=k=1∑k​pk​∗(1−pk​)=1−k=1∑k​pk2​
如果是二类分类问题，假设属于第一个样本输出的概率是p，则基尼系数的表达式为：
g i n i ( p ) = 2 p ∗ ( 1 − p ) gini(p) = 2p*(1-p) gini(p)=2p∗(1−p)
对于个给定的样本D,假设有K个类别, 第k个类别的数量为Ck,则样本D的基尼系数表达式为：
g i n i ( D ) = 1 − ∑ k = 1 k ( C k ∣ D ∣ ) 2 gini(D) = 1-\displaystyle\sum_{k=1}^{k}(\frac {C_k}{|D|})^2 gini(D)=1−k=1∑k​(∣D∣Ck​​)2
对于样本D,如果根据特征A的某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼系数表达式为：
g i n i ( D , A ) = ∣ C 1 ∣ ∣ D ∣ ∗ g i n i ( D 1 ) + ∣ C 2 ∣ ∣ D ∣ ∗ g i n i ( D 2 ) gini(D,A)=\frac {|C_1|}{|D|}*gini(D1) + \frac {|C_2|}{|D|}*gini(D2) gini(D,A)=∣D∣∣C1​∣​∗gini(D1)+∣D∣∣C2​∣​∗gini(D2)
计算代码如下：

gini_age_young = 1/3 * (2 * 2/5 * 3/5) + 2/3 * (2 * 3/10 * 7/10)
gini_age_median = 1/3 * (2 * 2/5 * 3/5) + 2/3 * (2 * 4/10 * 6/10)
gini_age_old = 1/3 * (2 * 1/5 * 4/5) + 2/3 * (2 * 5/10 * 5/10)
gini_job = 1/3*0 + 2/3*(2 * 4/10 * (1-4/10))
gini_house = 6/15*0 + 9/15 * (2 * 3/9 * (1 - 3/9))
gini_loan_good = 5/15 * (2 * 2/5 * 3/5) + 10/15 * (2 * 6/10 * 4/10)
gini_loan_very_good = 4/15 * 0 + 11/15 * (2 * 6/10 * 4/10)
gini_loan_common = 5/15 * (2 * 2/5 * 3/5) + 11/15 * (2 * 6/10 * 4/10)
result = {'gini_age_young': gini_age_young, 'gini_age_median': gini_age_median, 'gini_age_old':gini_age_old,
       'gini_job': gini_job, 'gini_house': gini_house,
       'gini_loan_good': gini_loan_good, 'gini_loan_very_good':gini_loan_very_good, 'gini_loan_common': gini_loan_common}

print('按照特征%s二叉分类，基尼系数最小, 值为：%f' % (min(result, key=result.get), result[min(result, key=result.get)]))

接下来就是循环判断，和ID3差不多。
本文主要简单记录算法原理，更多更详细优质内容可以查阅参考链接。

李航—统计学习方法
刘建平—决策树算法原理(上)
Python3《机器学习实战》学习笔记（三）：决策树实战篇之为自己配个隐形眼镜