Infi-chu:
http://www.cnblogs.com/Infi-chu/
一、简介
决策树思想的来源非常朴素，程序设计中的条件分支结构就是if-else结构，最早的决策树就是利用这类结构分割数据的一种分类学习方法
1.定义：
决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果，本质是一颗由多个判断节点组成的树。
二、决策树原理
1.熵
在物理学中，熵Entropy是“混乱”程度的度量
系统越有序，熵越低；系统混乱或者越分散，熵越高
信息理论：
1、从信息的完整性上进行的描述:
当系统的有序状态一致时，**数据越集中的地方熵值越小，数据越分散的地方熵值越大。
2、从信息的有序性上进行的描述:
当数据量一致时，系统越有序，熵值越低；系统越混乱或者分散，熵值越高。
1948年香农提出了信息熵（Entropy）的概念。
假如事件A的分类划分是（A1,A2,...,An），每部分发生的概率是(p1,p2,...,pn)，那信息熵定义为公式如下：（log是以2为底，lg是以10为底）
eg.
案例1：
如果一颗骰子的六个面都是1 ，投掷它不会给你带来任何新信息，因为你知道它的结果肯定是1，它的信息熵为？
答案：
- log(1) = 0 。
案例2：
假设我们没有看世界杯的比赛，但是想知道哪支球队会是冠军，
我们只能猜测某支球队是或不是冠军，然后观众用对或不对来回答，
我们想要猜测次数尽可能少，你会用什么方法？
答案：
二分法：
假如有 16 支球队，分别编号，先问是否在 1-8 之间，如果是就继续问是否在 1-4 之间，
以此类推，直到最后判断出冠军球队是哪只。
如果球队数量是 16，我们需要问 4 次来得到最后的答案。那么世界冠军这条消息的信息熵就是 4。
如果有32个球队，准确的信息量应该是：
H = -（p1 * logp1 + p2 * logp2 + ... + p32 * logp32），
其中 p1, ..., p32 分别是这 32 支球队夺冠的概率。
当每支球队夺冠概率相等都是 1/32 的时：H = -（32 * 1/32 * log1/32） = 5
每个事件概率相同时，熵最大，这件事越不确定。
案例3：
篮球比赛里，有4个球队 {A,B,C,D} ，获胜概率分别为{1/2, 1/4, 1/8, 1/8}，求H(X)
答案：
H(X) = 1\2log(2)+1\4log(4)+1\8log(8)+1\8log(8)=(1\2+1\2+3\8+3\8)log(2)=7\4bits
tips:
以2为底，记做lb,单位bit
以e为底，记做ln,单位nat
2.决策树划分依据——信息增益
定义：
信息增益：以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。
信息增益 = entroy(前) - entroy(后)
公式：
特征A对训练数据集D的信息增益g(D,A),定义为集合D的信息熵H(D)与特征A给定条件下D的信息条件熵H(D|A)之差，即公式为：
公式详解：
【注】
信息增益表示得知特征X的信息，使得类Y的信息熵减少的程度。
eg.
如图，第一列为论坛号码，第二列为性别，第三列为活跃度，最后一列用户是否流失。
我们要解决一个问题：性别和活跃度两个特征，哪个对用户流失影响更大？
通过计算信息增益可以解决这个问题，统计上右表信息
其中Positive为正样本（已流失），Negative为负样本（未流失），下面的数值为不同划分下对应的人数。
可得到三个熵：
整体熵：
性别熵
性别信息熵
活跃度熵
活跃度信息熵
【注】
活跃度的信息增益比性别的信息增益大，也就是说，活跃度对用户流失的影响比性别大。
在做特征选择或者数据分析的时候，我们应该重点考察活跃度这个指标。
3.决策树划分依据——信息增益率
增益率：增益比率度量是用前面的增益度量Gain(S，A)和所分离信息度量SplitInformation(如上例的性别，活跃度等)的比值来共同定义的。
4.决策树划分依据——基尼值和基尼指数
基尼值Gini（D）：从数据集D中随机抽取两个样本，其类别标记不一致的概率。故，Gini（D）值越小，数据集D的纯度越高。
基尼指数Gini_index（D）：一般，选择使划分后基尼系数最小的属性作为最优化分属性。
eg.
根据下图列表，按照基尼指数的划分依据，做出决策树。
1，对数据集非类标号属性{是否有房，婚姻状况，年收入}分别计算它们的Gini系数增益，取Gini系数增益值最大的属性作为决策树的根节点属性。
2，根节点的Gini系数为：
3，当根据是否有房来进行划分时，Gini系数增益计算过程为：
4，若按婚姻状况属性来划分，属性婚姻状况有三个可能的取值{married，single，divorced}，分别计算划分后的Gini系数增益。
? {married} | {single,divorced}
? {single} | {married,divorced}
? {divorced} | {single,married}
当分组为{married} | {single,divorced}时：
当分组为{single} | {married,divorced}时：
当分组为{divorced} | {single,married}时：
对比计算结果，根据婚姻状况属性来划分根节点时取Gini系数增益最大的分组作为划分结果，即:{married} | {single,divorced}
5，同理可得年收入Gini：
对于年收入属性为数值型属性，首先需要对数据按升序排序，然后从小到大依次用相邻值的中间值作为分隔将样本划分为两组。例如当面对年收入为60和70这两个值时，我们算得其中间值为65。以中间值65作为分割点求出Gini系数增益。
最大化增益等价于最小化子女结点的不纯性度量（Gini系数）的加权平均值，现在我们希望最大化Gini系数的增益。根据计算知道，三个属性划分根节点的增益最大的有两个：年收入属性和婚姻状况，他们的增益都为0.12。此时，选取首先出现的属性作为第一次划分。
6，接下来，采用同样的方法，分别计算剩下属性，其中根节点的Gini系数为（此时是否拖欠贷款的各有3个records）
7，对于是否有房属性，可得：
8，对于年收入属性则有：
5.总结
决策树构建的基本步骤如下：
-
开始将所有记录看作一个节点
-
遍历每个变量的每一种分割方式，找到最好的分