最近研究树模型，从最简单的决策树开始研究，扼要的说下最简单的ID3算法。
对于机器学习的数据: train_x, train_y, test_x, test_y。当然test_y通常是被预测的值。对于决策树而言，就是事先利用train_x与train_y建立一颗泛化性能足够好的树，以供后期分类test_x。
1.ID3算法的特征只能是标称属性；对于数值属性，则必须做离散化处理。如下图（这是一个已经被训练好的树，因为叶子节点已经给出了明确的分类，有贷款意向和无贷款意向），数据总共包含四个属性：职业，年龄，收入，学历。每一个属性下面的类别都是有限的，例如职业下面只有*职业，工人，白领。而年龄这个属性应当是做了离散化处理，包含6类。如
2. 决策树的分类就是在每一个属性上进行分支，比如对于职业这个属性，划分为*职业，工人，白领。图中为什么一定要先对职业这个属性先分支呢？事实上决策树分支的原则是：从当前节点所包含的的所有属性中选择信息增益最大或者基尼指数最小的一个属性来优先进行分支。
2.1假设按照属性A对数据集D进行划分，划分之后生成N个数据集D1，D2...，则属性A的信息增益公式为：
其中|D|代表数据集D总样本的个数。En(Di)代表数据集的熵。熵的计算是以train_y来计算的，比如数据集Di中有贷款意向的x人，无贷款意向的y人，En(Di) = -(xlogx + ylogy)，其中log以2为底。可以看出，信息增益就是两个熵之差：划分前数据集D的熵 - 按照属性A划分之后的多个数据集的熵的样本比例加和。增加的越多，则说明，当前属性带来的纯度提升越大。
2.2 假设按照属性A对数据集D进行划分，划分之后生成N个数据集D1，D2...，则属性A的基尼指数为对数据集D按照A划分之后多个数据集的基尼指数的样本比例加和。其公式为：
gini(D)代表数据集D的基尼指数，其计算相比信息增益更为简单。基尼指数也是按照train_y来计算的，比如数据集Di中有贷款意向的x人，无贷款意向的y人，则gini(Di) = 1 - {[x / (x+y)]^2 + [y / (x+y)]^2} ，gini指数与熵恰好相反，代表数据集的纯净程度，因此划分节点时选择基尼指数最小的属性进行划分。
3. 决策树叶子节点的投票
上图中是一个已经训练好的树，因为其根节点的值已经被确定了，要么有贷款意向，要么没有，这个结果是训练出来的。那么在训练的时候，如工人年龄大于40岁的叶子节点总共包含100个样本，其中90个在训练集中都被标定为没有贷款意向，10个被标定为有贷款意向。那么最终的结果投票就是没有贷款意向。注意，很多时候，由于特征太少，或者算法参数设置错误，导致树的深度不够，就会出现即使用完了所有属性，也可能出现90个在训练集中都被标定为没有贷款意向，10个被标定为有贷款意向的情况。这种情况算是好的，假设出现了60个有贷款意向，40个无贷款意向，而属性已经用完，则当前模型就很有可能欠拟合了。因此，特征较少时，设定参数，树应该较深，防止欠拟合；而特征很多的时候，树应该较浅，防止过拟合。
4. 决策树的剪枝。
如果数据集较少，或者说每个特征的属性分布不均匀。那么如果你一直对属性进行分支，直到所有属性全部耗尽，最终结果就很可能导致过拟合。因此需要对树进行剪枝：比如生成的某些节点样本极少，那么就应该和邻近节点合并，提高泛化性能。
5. 算法总结
ID3算法的核心就是在决策树的各个节点（非叶子节点）上应用信息增益选择特征划分当前数据集，递归的构建决策树。
从根节点开始，对非叶子节点计算所有特征的信息增益（计算时，使用一个特征将数据划分开，使用目标值train_y作为混乱程度熵的刻画指标，来计算信息增益），选择信息增益最大的特征作为当前节点特征，由该特征的不同取值建立子节点；再对子节点递归的调用上述方法，构建其他节点，直到所有特征的信息增益均很小或者没有特征可以选择为止。