转载请标明出处http://www.cnblogs.com/haozhengfei/p/d65ab6ccff684db729f44a947ac9e7da.html
决策树
1.什么是决策树
决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。
使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶节点存放的类别作为决策结果。
我们的决策树是一个分类的决策树，将我们的数据离散到各个不同的分类。
构建决策树的两个要求：
1.选择需要的属性以及怎么给属性做分支（分裂属性），
2.属性的前后（属性选择度量算法）。
决策树的构造关键是分裂属性
所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。
分裂属性分为三种不同的情况：
– 1、属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。
– 2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。
– 3、属性是连续值。此时确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支。
2.决策树中属性的选择顺序
属性的选择度量算法--决定哪一个属性应该排在前面（属性的选择顺序）
ID3（原始的算法），C4.5（ID3衍生的算法）
ID3（原始的算法）
ID3算法的核心思想：以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。
熵：给了一个条件后，判断这个条件的信息增益，信息增益越大，表明熵锐减的越多，那么这个条件应该越往前排。
Demo1：扔筛子的信息熵怎么求？
（-1/6 * log1/6 + -1/6 * log1/6 + ...）
Demo2：
分别算出各个条件的信息增益，哪一个信息增益越大，则选择该特征属性的排序越靠前
C4.5（衍生的算法）
为什么会出现C4.5？
ID3算法有一些弊端，比如某个属性下有10个分类，这10个分类每个分类都对应一个值，那么最后求得这一属性的熵为0，信息增益最大，就排在了其他属性的前面，这对于其他属性是不公平的，所以引入了C4.5，可以看做是ID3的升级版，C4.5比较的信息增益。
比较信息增益率（每一属性的信息/这一属性下的类别），按照信息增益率的高低进行属性的排序。
3.决策树应用时需要注意的一些问题
决策树本身是一个弱分类器的算法，优点是可以做到多分类，但是应用时要考虑到"剪枝"
1.树太高，容易造成计算量太大
2.容易过拟合（准确率超过90%可能就过拟合了，小于70%拟合度不够），就是一个节点上面只有少数的样本，所以使用决策树经常需要降低深度，也就是"剪枝“
4.决策树升级版-->GBDT和随机森林
随机森林：每次在全量样本中采取有放回的可以构建多棵决策树，随机森林的本质是采取一种投票的机制（比如随机森林中有15棵树，7棵树投票见面，8棵树投票不见面，那么最后的结果就是不见面）