1.概念        

决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。

  2.流程

（1）收集数据

（2）准备数据，输入只能为标称型数据，所以数值型数据必须离散化

（3）分析数据，树构造完成之后，检查图像是否符合预期

（4）训练算法，构造树德数据结构

（5）测试算法，使用经验树计算错误率

（6）使用算法，适用于任何监督学习算法     

3.信息增益

     划分数据集的最大原则是：将无序的数据变得更加有序。通过计算信息增益来判定选择哪个特征。集合信息的度量方式称为香浓熵或者简称为熵。这个名字来源于信息论之父 克劳德-香农。

克劳德-香农 被公认为时二十世纪最聪明的人之一，《财富公式》中说，“贝尔实验室和MIT有很多人将香农和爱因斯坦相提并论，而其他人认为这种对比是不公平的-对香农是不公平的”。

熵：信息的期望值。

符号的定义为：，其中是选择该分类的概率。

熵的表示为：

def calcShannonEnt(dataSet) :
        numEntries = len(dataSet)
        labelCounts = {}

        for featVec in dataSet :
                currentLabel = featVec[-1]

                if currentLabel not in labelCounts.keys() :
                        labelCounts[currentLabel] = 0
                labelCounts[currentLabel] += 1
        shannonEnt = 0.0
        for key in labelCounts :
                prob = float(labelCounts[key])/numEntries
                shannonEnt -= prob * log(prob,2)

        return shannonEnt

熵越高，则混合的数据也越多，在数据集中添加更多分类，则熵的值会变大。

4