决策树构建的基本步骤如下：
1. 开始，所有记录看作⼀个节点
2. 遍历每个特征的每⼀种分裂⽅式，找到最好的分裂特征（分裂点）
3. 分裂成两个或多个节点
4. 对分裂后的节点分别继续执⾏2-3步，直到每个节点⾜够“纯”为⽌
如何评估分裂点的好坏？如果⼀个分裂点可以将当前的所有节点分为两类，使得每⼀类都很“纯”，也就是同⼀类的记录较多，那么就是⼀
个好分裂点。
具体实践中，到底选择哪个特征作为当前分裂特征，常⽤的有下⾯三种算法：
ID3：使⽤信息增益g(D,A)进⾏特征选择
C4.5：信息增益率 =g(D,A)/H(A)
CART：基尼系数
⼀个特征的信息增益(或信息增益率，或基尼系数)越⼤，表明特征对样本的熵的减少能⼒更强，这个特征使得数据由不确定性到确定性的能
⼒越强。
下⾯就以⼀个经典的打⽹球的例⼦来说明如何构建决策树。我们今天是否去打⽹球（play）主要由天⽓（outlook）、温度
（temperature）、湿度（humidity）、是否有风（windy）来确定。样本中共14条数据。
NO. Outlook temperature humidity windy play
1 sunny hot high FALSE no
2 sunny hot high TRUE no
3 overcast hot high FALSE yes
4 rainy mild high FALSE yes
5 rainy cool normal FALSE yes
6 rainy cool normal TRUE no
7 overcast cool normal TRUE yes
8 sunny mild high FALSE no
9 sunny cool normal FALSE yes
10 rainy mild normal FALSE yes
11 sunny mild normal TRUE yes
12 overcast mild high TRUE yes
13 overcast hot normal FALSE yes
14 rainy mild high TRUE no
其中|D|是数据集中所有样本个数,k是⽬标变量的类别数，|Ck |是该分类下的样本个数。
2、遍历所有特征，对于特征A：
计算特征A对数据集D的经验条件熵H(D|A)
计算特征A的信息增益g(D,A)=H(D)-H(D|A)
选择信息增益最⼤的特征作为当前分裂特征。
