一、决策树
所谓决策树，就是自顶而下树形的结构，每一个节点都是一个属性。用决策树解决问题就是根据数据属性一层一层做决策的过程
好处：结构清晰，模仿人类思考的流程。
以下为某商品经过推销后，收集回来的客户信息，包括居住地区、住房类型、收入、是否老客户四种属性，最后一列代表该客户买没买。
1.用树状的结构表示上面的信息表格，我们能分析出那些规律？
① 住在农村的客户都买了；
② 住在郊区的低收入人群比高收入人群更喜欢本商品；
③ 住在城里的客户，买过一次就不会再买了。
2.换一种属性顺序来划分，决策树也可以像下面这样：
决策树不唯一。
我们可以看到根据不同属性先后划分时，树有不同的形态，所以我们的目标时选取能表现样本数据规律，且最简单的树。
3.奥卡姆的剃刀
现在有两个理论或者两个模型，性能是一样的，我们通常会选择比较简单的那个。越复杂的模型，参数和假设就会越多。
奥卡姆的剃刀认为这些多余参数设置和假设是不必要的，如果不影响做判断，剃刀就把参数、假设剃掉。
二、信息熵增益
1.信息熵
信息熵用于衡量系统的不确定性，用下面的式子表示。
14条商品信息，9条商品被买走了，5条没买，那么此时样本集S的信息熵为
当样本被分为50%和50%时信息熵最大，信息熵最大值为1，表示该样本集最不确定。
2.信息熵增益
当用一个属性A对样本进行划分时，用属性A划分样本集S后所得的信息增益为：
结合上表根据“居住地区“划分，样本集S的信息熵增益为：
根据“收入“划分，样本集S的信息熵增益：
0.247>0.152，说明属性“居住地区“对于分类提供的信息越大。
三、ID3算法
ID3算法的目的是基于已知数据建立一个最简单的决策树。
ID3的基本思想是强大的属性先分，也就是对信息熵增益大的属性优先对样本进行划分。
ID3算法流程
以如下数据为例，介绍ID3算法流程。
ID3 matlab方法：
function [ tree ] = id3( examples, attributes, activeAttributes )
examples：树杈，id3方法就是对examples分叉。
attributes：属性标签：“天气“，”是否周末”，”是否促销“，”销量“
activeAttributes：激活属性标签，该开始“天气“，”是否周末“，”是否促销“都为激活属性标签
1.对当前样本的集合，计算当前样本信息熵，计算所有属性的信息增益。
本例中，样本集中销量“高“的记录为18个，销量”低“的记录为16个。
天气属性的信息熵计算：
天气“好“中：销量”高“11条，销量”低“6条。(11,6)
天气“不好“中：销量”高“7条，销量”低“10条。(7,10)
计算“天气“属性的信息熵增量：
同理，“是否周末“、”是否促销“的信息熵增量：
2.选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划分为同一个子样本集
根据上一步计算结果知，“是否周末”属性的信息增益最大(0.139394)，所以决策树第一层用“是否周末“划分，example划分结果为
example_0（不是周末）：（销量低，销量高）（7，13）
example_1（是周末）：（销量高，销量低）（11，3）
在以后的分类中，我们就不再用“是否周末“属性进行划分。“是否周末”也就不是activeAttributes了。
3.若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上响应的符号；
叶子节点为决策树最末端的节点，本例中，如果叶子节点销量低的个体多，叶子节点value设为false，反之设为true。
否则对子样本集递归调用本算法。
决策树是按属性一层一层往下划分的，经常会用到递归的思想。
tree.left= id3(examples_0, attributes, activeAttributes);
tree.right= id3(examples_1, attributes, activeAttributes);
四、Overfitting
过学习是指：两个分类器A、B，在训练集时，A的误差小于B。在测试集时，B的误差反而小于A。那么我们就说A过学习了。
比如，在学校念书的时候A的学习成绩比B好，在社会上工作时候B的业绩反而比A好。
在决策树“生长“时，为了不让它长的太长，我们可以设置生长限制，让他长到一定层数就停下来，或者等决策树生长完毕再剪枝。
1.剪枝
决策树中剪枝并不是把数据剪掉，而是把末端的树叶往上合并，如下图
把末端的紫叶和红叶合并为一个红叶。
2.给信息增益添加惩罚项
如果某种属性把数据分的过细，虽然样本在该划分规则的信息增益很大，但对目标属性的划分的实际意义也特别差。
所以在根据属性A对样本集S划分时，我们在公式中加入一个惩罚量，来实现信息熵增益指标的改进。
A属性对样本划分的越细，惩罚量值越大，信息增益也就越小。
五、matlab实现