目标
给一份人员购买手机的历史数据，要求通过决策树预测未来一段时候的不同人员属性的购买趋势
概念
决策树是一个类似于流程图的树结构，可用于数据预测，其中每个内部节点表示在一个属性上的测试，每个分枝代表一个属性输出，而每个树叶节点代表类或类分布。树的最顶层为根结点，结构图如下：
其中某一个数据实例包含特征[A,B,C,Boolean],以A为根结点判断A特征取值（A-1,A-2,A-3）,在特征A-2中只存在一种情况，因此不需要在分枝决策；在特征A-1,A-3中还存在一种以上的可能性，因此在以B,C特征为节点继续进行判断，知道判断特征的结果只剩下一种。
熵（entropy）
1948年，香农提出了 ”信息熵(entropy)“的概念一条信息的信息量大小和它的不确定性有直接的关系，要搞清楚一件非常非常不确定的事情，或者是我们一无所知的事情，需要了解大量信息==>信息量的度量就等于不确定性的多少。
比特(bit)来衡量信息的多少
-(p1log(p1)+p2log(p2)+……+p10*log(p10))
可写成函数
变量的不确定性越大（也就是X值越小），信息熵也就越大。
如例子：现在有如下数据（根据不同的情况买iphoneX的人进行统计），特征有“年龄”=[youth,middle_aged,senior]，“收入=[high,medium,low]”，“是否学生=[yes,no]”，“信用度=[bad,good]”
其基本结构图如下：
决策树ID3归纳算法
在1970-1980， J.Ross. Quinlan, 提出ID3算法。
如何选择属性判断节点（节点到底以哪个为标准？为什么以“年龄”，“收入”，“信用度”作为结点）：
信息获取量(Information Gain)
Gain(A)=info(D)-info_A(D)
计算通过A特征来作为节点分类获取了多少信息
根据以上表格数据，和以上Gain公式可知：
info(D)表示对于目标“买iphoneX”信息熵，“-6/10log2[(6/10)]”表示买iphoneX的概率，“-4/10log2[(4/10)]”表示不买iphonX概率
对于关于年龄的信息熵：
备注：
5/10(-3/5log2[3/5],-2/10log2[2/5])=年轻人在整体实例集占比 x ( -在年轻人中买手机概率 -不买手机概率) 3/10(-3/3log2[3/3]-0/3log2[0/3])=中年人在整体实例集占比 x( -在中年人中买手机概率 -不买手机概率) 2/10(-0/2log2[0/2]-2/2log2[(2/2)])=老年人在整体实例集占比 x ( -在老年人中买手机概率 -不买手机概率)
由上可知 Gain(年龄)=0.940-0.694=0.246 (以年龄分类的信息获取量)。
因此以Gain(收入)=0.151，Gain(是否学生)=0.029，Gain(信用度)=0.048可以按照以上分别求出值。
在以上4个特征中值排序为：Gain(年龄) >Gain(收入)>Gain(信用度)>Gain(是否学生),因此该节点以 “年龄”为标准。
总结归纳
1 .树代表训练样本的单个节点开始.
2 如果样本在同一个类，则该节点称为树叶。
3 如果样本不在同一个类，则算法使用信息增益熵的度量作为评判信息，选择能够最好将样本分类的属性
4 所有属性都是分类的，即是离散值。如果是连续的值必须离散化先（如年龄为具体数字，着需要对数字离散化1-10为一个段，10-100位一个段…）。
5 对测试属性的每个已知的值，创建一个分枝，并据此划分样本。
6 算法使用同样过程，递归形成每个划分上的样本判定。如果以恶属性出现在一个节点上就不需要在该节点的任何后代考虑（意思是如年龄已经成为一个节点，那么子节点中不需要考虑“年龄”特征）
7 递归划分步骤，当只剩下一下条件成立即停止：
7-1 给定节点所有样本属于同一类；7-2 没有剩余属性可以用来进一步划分（使用多数表决）
决策树优点：
直观，便于理解，小规模数据有效。
决策树缺点：
处理连续变量不好，类别较多时错误增加快，可规模性一般。