机器学习之决策树

信息熵:

信息熵描述信息源的不确定程度，信息熵越大、越不确定.

信息熵公式:   

信息熵公式

例子:

假设中国乒乓球队和巴西乒乓球队历史交手共64次,其中中国获胜63次,那么这次中国巴西比赛结果的信息熵多少?

第一反应，中国队赢球，是一个很确定的事情，信息熵小

中巴比赛结果有两种可能: 胜或负

根据信息熵计算公式: 

1. 共64场比赛, 中国胜63场, 负1场

       

    = = 

                                    

                                   

                                    

2.假设德国丘乓球队和法国乒乓球队比赛,双方历史交手64次,交手胜负为32:32

                                            

1>0.117，所以德国和法国比赛结果和中国巴西之间的比赛结果相比，具有更大不确定性

信息增益率:

如何选择决策树的每个节点:

信息增益率:公式 决策树

ID3算法

H(D|outlook):条件熵，给定outlook条件计算得到熵

g(D,outlook)=H(D)-H(D|outlook)

H(D|outlook=sunny,overcast,rainy)=

    sunny个数/总的个数H(D|outlook=sunny)+

    overcast个数/总的个数* H(D|outlook=overcast)+

    rainy个数/总的个数* H(D|outlook=rainy)

# 在某一特征下, 当前特征值分类所占的个数/当前特征值总数 * 当前特征值的信息熵

# 各个特征值的信息熵相加即为条件熵, 利用公式即得当前条件(特征)的信息增益率

计算每个特征的信息增益率, 值最大的特征即为当前节点, 不断重复计算过程, 直到获取所有的节点(需要将各个特征的值转为离散值)

计算流程

其他算法

其他算法 优缺点