决策树

• 决策树归纳的基本算法是贪心算法，它以自顶向下递归各个击破的方式构造决策树。
• 贪心算法：在每一步选择中都采取在当前状态下最好的选择。
• 在其生成过程中，分割方法即属性选择度量是关键。通过属性选择度量，选择出最好的将样本分类的属性。
• 根据分割方法的不同，决策树可以分为两类：基于信息论的方法（较有代表性的是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')