机器学习之决策树

2019-05-24 本文已影响0人长亭远望夜色微凉

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

信息熵公式: $H(X)=-P_i\log_2P_i$

信息熵公式

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

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

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

根据信息熵计算公式:

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

$H_1 = -63/64*log_263/64$ $H_2 = -1/64*log_21/64$

$H$ = $H_1 + H_2$ = $-(63/64*log_263/64+1/64*log_21/64)$

$H(中巴比赛结果)=-(63/64*log_263/64+1/64*log_21/64)$

$=-(0.984*log_20.984+0.0156*log_20.0156)$

$= (0.0233*0.984+ 6.00231*0.0156)$

$=0.117$

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

$H(德国法国比赛结果)=-（0.5*log_20.5+0.5*log_20.5）$

$=(0.5+0.5)=1$

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)

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

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

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

计算流程

优缺点