- 决策树归纳的基本算法是贪心算法，它以自顶向下递归各个击破的方式构造决策树。
- 贪心算法：在每一步选择中都采取在当前状态下最好的选择。
- 在其生成过程中，分割方法即属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性。
- 根据分割方法的不同，决策树可以分为两类：基于信息论的方法（较有代表性的是ID3、C4.5算法等）和最小GINI指标方法（常用的有CART，SLIQ及SPRINT算法等）。
前面已经学习了预备知识信息量与Gini index
ID3算法
ID3的属性选择度量就是使用信息增益，选择最高信息增益的属性作为当前节点的测试属性。
p是parent node首字母，
IG表示信息增益，
f表示特征，
D_p代表父节点数据集，
D_j表示子节点j的数据集，
N_p表示父节点样本个数
N_j表示子节点j样本个数
下面举个例子
| Outlook | Temperature | Humidity | Windy | Play |
|---|---|---|---|---|
| sunny | hot | high | false | no |
| sunny | hot | high | true | no |
| overcast | hot | high | false | yes |
| rain | mild | high | false | yes |
| rain | cool | normal | false | yes |
| rain | cool | normal | true | no |
| overcast | cool | normal | true | yes |
| sunny | mild | high | false | no |
| sunny | cool | normal | false | yes |
| rain | mild | normal | false | yes |
| sunny | mild | normal | true | yes |
| overcast | mild | high | true | yes |
| overcast | hot | normal | false | yes |
| rain | mild | high | true | no |
可以把上面数据存入excel，然后使用pandas读出来，pandas可以无缝对接excel，简直太方便了
import pandas as pd
import numpy as np
df = pd.read_excel("decision.xlsx")
print df
输出就是下面这样子
现在来计算‘Outlook’特征信息增益
import pandas as pd
import numpy as np
from collections import defaultdict
df = pd.read_excel("decision.xlsx")
#print df.dtypes
#print df.columns
#print df[df.columns[0]]
print df.index,df.shape
def I(future,label):
df.columns
d = defaultdict(lambda:[0,0])
for f,l in zip(df[future], df[label]):
if l == 'yes':
d[f][0] += 1
else:
d[f][1] += 1
return d
I('Outlook', 'Play')
