决策树

为输入选择正确标签的流程图。叶子节点为标签，其他的节点为决策节点。决策树桩只有一个节点的决策树，基于一个特征为输入分类。要建立树桩首先应该决定哪些特征应该使用。最简单的办法是为每一个特征都建立决策树桩然后在训练集上测试选择得分最高的特征。

熵和信息增益

衡量原始集合的无序程度就需要计算他们的标签的信息熵，如果标签非常不同熵就高，如果标签相同则熵就低。熵每个标签的概率×标签的logo概率的总和.
计算标签链表的熵

import nltk
import math

#计算标签链表的熵，即标签链表的无序程度
def shang(labels):
    #构建标签链表的频率分布，方便获取概率
    fredist = nltk.FreqDist(labels)
    #构建标签的频率链表
    p_male_female = [fredist.freq(label) for label in set(labels)]
    #计算此标签链表的信息熵
    result = [p*math.log(p,2) for p in p_male_female]
    #返回求和之后的结果  result里面的是负值所以需要一个负号
    return -sum(result)

print(shang(["male","female","male","male"]))

输出: 0.8112781244591328

计算了原始输入值的标签集的信息熵,就可以判断应用了决策数之后标签会变得多么有序.为了这样做还需要计算每个决策树桩叶子的熵,利用这写叶子熵值的平均值(加权每片叶子的数量).信息增益就等于原来的熵减去新的这个熵.信息增益越高,将输入分为相关组的决策树桩就越好,越是可以选择信息增益高的树桩来建立决策数.

决策树特别适合很多层次的分类情况.但是也同样具有一些问题.首先需要为每一个节点划分训练数据,在训练节点的时候能够使用的数据量就会很小,导致较低的节点可能过拟合训练集。这个问题的解决办法是先建立一颗完整的决策树，然后去除在开发测试集上不能提高性能的节点。

第二个问题是决策树按照一定的顺序检查特征，而特征可能是相互独立的，为了提高性能需要重复大量的特征，越往下分支越多，重复的可能非常大。

一个相关的问题是决策树不善于利用对正确的标签具有较弱预测能力的特征。由于这些
特征的影响相对较小，它们往往出现在决策树非常低的地方。决策树学习的时间远远不够用
到这些特征，也不能留下足够的训练数据来可靠地确定它们应该有什么样的影响。如果我们
能够在整个训练集中看看这些特征的影响，那么我们也许能够做出一些关于它们是如何影响
标签的选择的结论。