从样例构建决策树
对于原始样例集，我们选取一个最好的属性将其分裂，这样我们会产生多个样例子集，同时我们会把该属性从属性集去掉，并且继续对各个样例子集进行分裂操作，直到样例集中的所有样例具有相同的分类。显然，这是一个递归分裂的问题，在这个分裂过程中我们会遇到以下四种情况：
- 样例集合为空集说明测试样例中并没有这样的属性组合，因此返回其父节点得票最多的分类。
- 属性集合为空集属性用完了，样例集合仍然有多种分类，说明拥有相同属性组合的样例有着不同的分类，这种情况的发生是因为数据存在了噪声，此时我们返回样例集合得票最多的分类。
- 样例集合分类一致返回一个“决策”。
- 样例集合分类不一致选择一个最好的属性继续分裂。
对于这四种情况，我们采取不同的举措，从而最终构建出一棵决策树。
确定最优属性
在分裂时，我们希望能找到一个最优属性，那么到底什么样的属性是最优的呢？直观上看，我们希望能找到这样一个属性，它可以将混乱的集合分裂成不那么混乱的子集。
我们首先定义熵来度量集合的混乱程度： H(V) = -ΣP(Vk)log2P(Vk)
P(Vk) = 出现Vk的概率，因此∈(0, 1)
我们研究y = -P(Vk)log2P(Vk)的单调性会发现，P(Vk)→0时，y→0; P(Vk)→1, y→0;
因此当集合中的所有分类个数一致时（集合最混乱），熵最大；相反，当集合中只有一个分类的时候，熵最小。现在假设A属性将样例集合分为E1,E2...Ed,其中Ek有nk个样例。对各个子集的熵进行加权求平均后获得子集的剩余期望熵:Remainder(A) = Σnk/nHk(V)
定义信息增益来描述分裂前后熵减少了多少：
Gain(A) = HA(V) - Remainder(A)
因此使得Gain（A）最大的属性值A为最优属性。
伪代码
function DecisionTree(examples, attributes) returns a tree if examples is empty return parent's majority if attributes is empty return the majority of examples if all examples have the same classification return the classification A = the best attribute tree = a new tree for each value vk of A do newexamples = {e: e.A=vk} subtree = DecisionTree(newexamples, attributes-A) add subtree to tree return tree 随机森林
随机森林是决策树的一种优化方案，其主要思想是有放回的随机抽取多个与原始样例集大小一样的集合，然后根据这些样例集合构建多棵树，形成一个随机森林。在做决策的时候我们选取票数最高的决策作为最终的结果。
function RandomForest(examples, attributes) returns a decision forest = a empty set for i = 1 to k do exs = RandomSelectFrom(examples) tree = DecisionTree(exs, attributes) forest.append(tree)
过度拟合
当我们把噪声作为了分类属性，那么可能会出现过度拟合的问题，表现在样例集上泛化的非常好，但在实际测试样例中却表现平平。对于这种问题，我们可以对决策树进行χ2剪枝。考查只有叶节点作为后代的测试节点，对其进行统计重要性测试。若发现该节点不相关，则将其剪枝。
那么为什么我们不在构造时就进行重要性测试，从而提前避免分裂呢？原因是可能不存在好的属性，却存在好的属性组合。例如XOR：a b y
0 0 10 1 01 0 01 1 1
不管我们选择属性a还是b进行分裂，都会发现分裂后的集合仍有一半是1，一半是0，如果这时进行剪枝的话，我们就没办法构建一棵有效的决策树。反之，如果我们先用a进行分裂，然后再用b进行分裂，我们会发现样例被很好的归类。因此单个属性a，b都不能很好的对样例进行分类，但是组合a、b却能对对样例进行分类，后剪枝正是为了解决这样一个问题。