2019-02-14决策树学习通常包括三个步骤：
1. 特征选择。选取最优特征来划分特征空间，用信息增益或者信息增益比来选择
2. 决策树的生成。ID3、C4.5、CART
3. 剪枝
总结优缺点：
ID3:
优点：算法简单，通俗易懂
缺陷：1. 无法处理缺失值
2. 只能处理离散值，无法处理连续值
3. 用信息增益作为划分规则，存在偏向于选择取值较多的特征。因为特征取值越多，说明划分的
越细，不确定性越低，信息增益则越高
4. 容易出现过拟合
C4.5:
优点：1. 能够处理缺省值
2. 能对连续值做离散处理
3. 使用信息增益比，能够避免偏向于选择取值较多的特征。因为信息增益比=信息增益/属性
熵，属性熵是根据属性的取值来计算的，一相除就会抵消掉
4. 在构造树的过程中，会剪枝，减少过拟合
缺点：构造决策树，需要对数据进行多次扫描和排序，效率低
学习的时候发现了这两点错误：
1. Gain(D , 天气)=0 ---> 1
Gain(D , 湿度)=0 ----> 1
Gain(D , 刮风)=0.0615
2. 针对将属性选择为温度的信息增益率为：
Gain(D′, 温度)=Ent(D′)-0.792=1.0-0.792=-0.208
这里算出来的还是信息增益，不是信息增益率，没有除以属性熵
属性熵=-3/6log3/6 - 1/6log1/6 - 2/6log2/6
作业：
经验熵 H(D) = -1/2log1/2 - 1/2log1/2 = 1
属性 红的信息增益：
g(D, A1) = H(D) - H(D|A1)
= 1 - 1/2*0 - 1/2 * 0
= 1
属性 大的信息增益：
g(D,A2) = 1 - 1/2*(-1/2log1/2-1/2log1/2)*2
= 0
属性熵都是1，所以信息增益比跟信息增益一样
特征选择 红作为最优特征，红的就是好苹果，不红的就是坏苹果展开作者回复: Good Job
39
2019-01-22「红」的信息增益为：1
「大」的信息增益为：0
因此选择「红」的作为根节点，「大」作为子节点。接着再通过计算得出「大」作为子节点效果更差，故进行剪枝。因此最终的完整决策树就只有「红」一个节点：
红（是）---好苹果（是）
红（否）---好苹果（否）
通过使用sklearn来验证一下：
from sklearn import tree
import sys
import os
import graphviz
import numpy as np
os.environ["PATH"] += os.pathsep + 'D:/Program Files/Anaconda3/Library/bin/graphviz'
#创建数据[红，大]，1==是，0==否
data = np.array([[1,1],[1,0],[0,1],[0,0]])
#数据标注为，1==好苹果，0==坏苹果
target = np.array([1,1,0,0])
clf = tree.DecisionTreeClassifier() #创建决策树分类器模型
clf = clf.fit(data, target) #拟合数据
#最后利用graphviz库打印出决策树图
dot_data = tree.export_graphviz(clf,out_file=None)
graph = graphviz.Source(dot_data)
graph展开 1 26- 2019-01-21今天去面试一个金融分析师职位
问：算法知道吗？
我答：还在学习中，但我会python 爬虫，Numpy/Pandas~还有标准化(心想为嘛早上不认真看看今天的课程，起码说的出来C4.5是啥)😂😂
以后要好好做作业~及时看课程展开作者回复: 加油 有进步收获就好
1 14 
2019-01-23step1：将红作为属性来划分，有两个叶子节点D1，D2，分别对应是和否。用+代表是好苹果，-代表不是好苹果。
故 D1 = {红=是}={1+，2+}，D2={红=否}={3-，4-};
先分别计算2个叶子结点的信息熵：
Ent（D1）=0，Ent（D2）=0，作为子节点的归一化信息熵为：1/2*0+1/2*0=0
并且：训练集中有4条数据，2个是好苹果，2个不是，故根节点的信息熵为：Ent（D）=-（2/4*LOG2(2/4）+2/4*LOG2(2/4))=1
step2：计算每个节点的信息增益
Gain（D,红）=Ent（D）-0=1
同理可得，大属性作为根节点的信息增益Gain（D，大）=0
所以红作为属性的信息增益更大，选择红作为根节点。
Step3：构造决策树
红
是 否
{1+，2+} {3-，4-}
可以看到上面的决策树纯度已经很高，不需要进一步划分。所以最终的决策树即为下所示，只有红一个节点：
红
是 否
好苹果（是） 好苹果（否）展开 12
2019-01-22算法一点听不懂咋整作者回复: 慢慢来，先理解概念，然后掌握工具使用
1 10
2019-01-21老师在计算ID3父节点为天气时信息熵的时候，每一项的系数是3/6,这里是不是错了，不应该是4/7和3/7吗？ 9
2019-01-24老师，C4.5的例子，属性熵是多少？如何计算的？ 7
2019-03-25Gain(D , 天气)=0, Gain(D , 湿度)=0, Gain(D , 刮风)=0.0615
这个三个值计算错了吧？
我计算的结果: Gain(D, 天气) = 1， Gain(D, 湿度) = 1， Gain(D, 刮风) = 0.3115,
请老师指正 1 6
2019-04-18脑瓜疼作者回复: 慢慢来 我整理的时候也是，现在头发都掉了一些，主要是公式计算比较多啊
1 5
2019-01-24> 如果你将天气作为属性的划分，会有三个叶子节点 D1、D2 和 D3，分别对应的是晴天、阴天和小雨。我们用 + 代表去打篮球，- 代表不去打篮球。那么第一条记录，晴天不去打篮球，可以记为 1-，于是我们可以用下面的方式来记录 D1，D2，D3：
D1(天气 = 晴天)={1-,2-,6+}
D2(天气 = 阴天)={3+,7-}
D3(天气 = 小雨)={4+,5-}
----------------------
建议例子举两个， 2-指的是第二天是不打篮球。 跳着看，看了好一会，才明白1-2-6+啥意思。 = =
是==+ 否==-
ENT(D)= -(1/2log1/2+1/2log1/2)=1
D1(红=是)={1+,2+}
D2(红=否)={3-,4-}
ENT(D1)=0
ENT(D2)=1
Gain(D , 红)=1
Gain(D , 大)=0
红 作为父节点，大 没有作用，剪掉
代码就不放了，抄了大伙的。
同学们的代码少了一行，运行半天都没树出来。原来要打印出来的(；′⌒`)(Ｔ▽Ｔ)
graph.render("tree")#在同目录下生成tree.pdf
问一下老师，那个树我看不懂额。。要不解释一下gini和value展开 2 5
2019-04-17根集合D = {2个好苹果，2个不是号苹果}，求得Ent(D) = 1。
按红作为属性划分可得$D_1、D_2$两个子集
$D_1$ (红 = 是) = {2个好苹果}
$D_2$ (红= 否) = {2个不是好苹果}
可得Ent( $D_1$ ) = 0 、Ent( $D_2$ ) = 0
可得归一化信息熵为$\dfrac{1}{2} \times 0 + \dfrac{1}{2} \times 0 $ = 0
则G(D,红) = 1-0 = 1
按大作为属性，同样可得 $D_1、D_2$两个子集
$D_1$ (大 = 是) = {1个好苹果，1个不是好苹果}
$D_2$ (大 = 否) = {1个好苹果，1个不是好苹果}
可得Ent( $D_1$ ) = 1 、Ent( $D_2$ ) = 1
归一化信息熵 = $\dfrac{2}{4}\times1 + \dfrac{2}{4}\times1$ = 0.5
则G（D，大）= 1- 0.5 = 0.5
由此可得按红作为属性的信息增益大于按大作为属性的信息增益，所以选择红作为根节点。
接着在红为是的基础上，分析按大作为属性的信息增益。在红为是的集合里共有两个苹果集合D = {2个好苹果} Ent(D) = 0
$D_1$ (大 = 否) = {1个好苹果}
$D_2$ (大 = 是) = {1个好苹果}
Ent( $D_1$ ) = 0 、Ent( $D_2$ ) = 0
G(D，大) = 0
因为大是与否在红决定的前提下对好苹果的决定没有影响，所以剪去该分支。展开作者回复: 整理的不错 很认真啊 滢
4
2019-06-17决策树算法，根据判别属性建立二叉树、多叉树，从根节点属性值开始，不断向下分支，根据中间子节点属性值判断，最终到达叶子节点实现分类目标。纯度和信息熵来判断属性值的不确定性，分类过程中，本质上是个算法收敛过程，如果算法收敛快，运算少，达到相同效果，肯定选择它。构建决策树，是确定跟节点、子节点、叶子节点过程，为了兼顾收敛和效果，通过信息增益计算值，判断某个节点作为根节点，信息熵最小，不确定性小，就是信息增益最大，收敛快。依靠此方法，逐步确定中间的子节点，最终的叶子节点就是分类结果。ID3算法缺点在于倾向测试集数值出现次数多，概率大，会造成错误分类，因为测试数据是抽象数据，不是全量数据，不能反应真是数据的全貌，从而出现过拟合现象。过拟合或者欠拟合问题，有点像评判好学生一样，如果数据样本都是清华北大学生，各方面都突出，维度多且高，预测好学生结果少，且都是985学生，收敛性强，最终区间少，过拟合；如果训练样本是单方面突出的学生，维度少，要求中等，模型预测结果是好学生的数据多，收敛性差，最终区间多，过拟合。为了避免抽象样本特殊性，不能代表真是数据情况，采用信息增益率方式，以百分比判断，算法c4.5就是这样一种方式。展开 3
2019-02-14在ID3算法那个例子中，当用“温度”作为根节点的时候，在温度为高的情况下，我计算的天气、湿度的信息增益都是1，而刮风为0.3115，所以这个子节点应该从天气或者湿度中选一个，我不明白为什么课程上写的结果是0、0、0.0615。望解答，谢谢。 1 3
2019-03-27老师，我这里有个问题：在说C4.5算法的时候，您的例子是：D’的样本个数为6， D的样本个数为7， 那么利用D‘计算出来的信息增益率所占权重比例是6/7,所以 Gain(D, 温度) = 6/7*0.208 = 0.178。这样不对吧，应该是D’所占比例是6/7，所以Gain(D, 温度) = 0.208 / (7/6) 才对吧 2 2
2019-01-22红的信息增益为：1
大的信息增益为：0
红比大更纯，红放决策树上面作为父节点，大放下面作为子节点 2
2019-01-21苹果-大的信息熵：5/3
苹果-红的信息熵：1
归一化的信息熵：1
苹果-大信息增益更大，作为根节点，红作为子节点。
决策树：
大（是）-红(是）-好苹果（是）
大（是）-红(否）-好苹果（否）
大（否）-红(是）-好苹果（是）
大（否）-红（否）-好苹果（否）展开作者回复: Good Job
2
2019-01-21老师看完有两个疑问：
1、D：5个打篮球，5个不打篮球。为什么计算ent(D)概率是3/6呢？不应该是5/10吗？
2、在介绍C4.5算法那部分，在计算ent(D1')的时候，两个概率都是3/6，不是1/3和2/3吗？难道我对信息熵的理解有误？ 1 2
2019-05-11“然后我们要将上图中第一个叶节点，也就是 D1={1-,2-,3+,4+}进一步进行分裂，往下划分，计算其不同属性（天气、湿度、刮风）作为节点的信息增益”
这里为什么父节点已经是温度了，子节点还要再计算温度属性呢？ 1
2019-03-021.根结点的信息熵是 -（1/2*log（1/2）+1/2*log（1/2） = 1
2.假如以红来作为根结点，那么有两个叶子 红和不红，
红的信息熵是 -（1*log（1））= 0
不红的信息熵是 -(1*log(1)) = 0
所以 以红作为根结点的信息增益是 1-0 = 1
3.假如以大来作为根结点，那么有两个叶子节点： 大和不大
大的信息熵是 -(1/2*log(1/2)+1/2*log(1/2)) = 1
不大的信息熵是 -(1/2*log(1/2)+1/2*log(1/2)) = 1
以大作为根结点的信息增益是 1- (1/2*1 +1/2*1) = 0;
因为 以红作为根结点的信息增益大于以 大来作为根结点的信息增益，所以选择红来作为根结点。
4.第一个叶子节点 的节点是大 ，第二个叶子节点的节点也是大。展开作者回复: Good Job
1
2019-02-161、计算案例中的下一个节点的信息增益有疑惑：
算得Gain(D , 天气)=1，与文章提到的Gain(D , 天气)=0矛盾，不知道哪里理解有误。
2、作业
苹果训练集中有4条数据，2个是好苹果，2个不是好苹果。
根结点的信息熵是：1
1）将“是为红”作为属性进行划分，有2个叶子结点D1和D2，分别对应‘是’红苹果，‘不是’红苹果。
用+代表‘是’好苹果，-代表‘不是’好苹果。
D1（红苹果->是）=【1+，2+】
D2（红苹果->否）=【3-，4-】
2个叶子节点的信息熵：
Ent（D1）=0
Ent（D2）=0
子节点归一化信息熵=0
所以，‘是红苹果’作为属性节点的信息增益为，Gain（D，是红苹果）=1
2）将‘是大苹果’作为属性进行划分，2个叶子节点D1，D2对应‘是大苹果’，‘不是大苹果’。
D1（大苹果->是）=【1+，3-】
D2（大苹果->否）=【2+，4-】
2个叶子节点的信息熵：
Ent（D1）=1
Ent（D2）=1
子节点归一化信息熵=1
所以，‘是大苹果’作为属性节点的信息增益为，Gain（D，是大苹果）=0.
综上，‘是红苹果’作为属性的信息增益最大，所以将‘是红苹果’作为根节点。
3）将D1（红苹果->是）=【1+，2+】进一步分裂，往下划分。
得到Gain（D，大苹果）=0
所以无需进一步划分。
最终决策树。
红苹果（是）-》好苹果（是）
红苹果（否）-〉好苹果（否）展开作者回复: Good Job
1