数据挖掘之决策树
——学自北京大学莫同老师
决策树示例
- 决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法
- 把由不同组成的总体分成较小且较具同质性的群体
- 每一个分支要么是一个新的决策节点，要么是树的叶子
- 在沿着决策树从上到下遍历的过程中，在每个节点上问题的不同回答导致了不同的分支，最后会到达一个叶子节点
- 这个过程就是利用决策树进行分类的过程，利用几个变量（问题）来判断所属的类别（每个叶子对应一个类别）
决策树优点
- 只需要很少的数据准备不用归一化
- 可以处理数值型数据和类别型数据
- 使用白盒模型输出结果容易通过模型的结构来解释。
- 可以很好的处理大规模数据
决策树缺点
- 训练一颗最优的决策树是一个完全NP问题。实际应用时，决策树的训练采用启发式搜索算法如贪心算法以达到局部最优。
- 难以解决异或等问题
决策树建立过程
决策树的建立主要有决策树生长、修剪、规则抽取等过程。
决策树生长
- 实质上就是对样本的一个不断的分类过程
- 关键问题是找到一个好的分割——也就是就是变量的排序问题
- 下一个分支是建立在上一个分支的基础上的
- 需要一个计量分类效果的量——纯度
如何计算纯度
基于基尼值（总体发散性）
计算从同一个样本中随机取两个抽样，这两个抽样属于同一种类的几率。
若一节点包含n种预测值，且每一种预测值在该几点中的出现频率为Pi，则该点的基尼值G为：
基尼值计算示例：
基尼值越大，纯度越高，纯的节点基尼值为1。
基于熵
熵是对信息的不确定性的度量。熵越低，意味着传输的信息越少，计算公式如下：
熵的计算示例
熵越小，纯度越高，纯的节点熵为0。
决策树生成算法
ID3算法
基于贪心算法，力求获得最大的信息增益度（下文有介绍）。对于有诸多属性的样本，它按每种属性进行分割，计算每种分割之后的纯度，选取分割后纯度最大的属性作为分割属性，循环直至生成树——各个节点都是纯的，或者达到终止条件，比如深度，纯度阈值等。
源码
C4.5算法
我们能够发现，并不是生成树并不是纯度越高越好，ID3算法可能导致样本集合分裂程度太大（过拟合）。
除了考虑纯度变化，我们还要考虑样本集合分裂的程度，于是提出了C4.5算法。
源码
属性选择条件
先介绍下的几个关键概念：
- 信息增益度（information gain）
该样本集S按离散属性F的V个不同的取值划分为S1,…Sv共V个子集，其中，Pvj表示Sv中第j类的概率。 - 分裂信息
- 信息增益率（information gain ratio）
C4.5算法是基于信息增益率，由公式能够发现，它的目的是获得信息增益率的最大，即实现增益度大且分裂度小。
连续值处理
在取值序列中生成一系列的分割点，然后在分割点钟选择信息增益率最大的分割点来划分数据。
缺失值处理
- 常见值替代
- 可能值概率替代：为Fi的每个可能值赋予一个概率。例如，给定一个布尔属性Fi，如果节点t包含6个已知Fi_v=1和4个Fi_v=0的实例，那么实例x有60%被分配到Fi_v=1的分支，40%被分配到另一个分支。
- 丢弃缺失值样本
决策树修剪
决策树是否需要无限生长？
生长的越多，对训练数据的分类性越好，但是不一定对校验数据分类性好。
过拟合
- 我们需要一个适应各种情况的模型
- 但是模型的生成基于一小部分抽样数据，并不一定适应所有的数据。
- 可以完美匹配（拟合）训练数据，但是无法适应其他数据集的现象称为过拟合
修剪
删除以某节点为根的子树使之称为叶子节点，该节点的类别为这个节点样例中最常见的分类
修剪方式
前期修剪——边生长边剪
后期修剪——生长完毕后修剪
前期修剪（预修剪）
- 最为简单的方法就是在决策树到达一定高度的情况下就停止树的生长；
- 到达此节点的实例个数小于某一个阈值也可停止树的生长；
- 到达此节点的实例具有相同的特征向量，而不必一定属于同一类，也可停止生长；
- 计算每次生长对系统性能的增益，如果这个增益值小于某个阈值则不进行生长。
后剪枝
它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的节点子树用叶子节点来代替，该叶子的类标号用该结点子树中最频繁的类标记。相比于先剪枝，这种方法更常用，正是因为在先剪枝方法中精确地估计何时停止树增长很困难。
分类率
随着决策树节点数的增大，对测试集的分类效果先增大后迅速减小。
剪枝算法核心思想
将各个节点作为修剪候选对象
- 删除以该节点为根的子树（该节点变为叶子节点）
- 节点重新分类
- 重新评估性能
- 性能不比原来差时才真正删除该节点
- 重复到无法提高性能为止
剪枝算法的变动空间
- 剪枝评估次序
自底向上
自顶向下 - 节点重新分类
最常见分类替代
最佳叶子节点替代
概率替代 - 性能评估
精度/错误率
深度/广度
降低错误剪枝REP（Re杜策 Error Pruning）
基本思路：对于决策树T的每棵非叶子树s，用叶子替代这棵子树。如果s被叶子替代后形成的新树关于D的误差等于或小于s关于D所产生的误差，则用叶子替代子树s
优点：计算复杂度低、对未知示例预测偏差较小
度量因子
准确率x：你说是1的，有多少真的是1
召回率y：真正是1的，有多少你说是1
关键问题是怎么综合两个指标？
综合评价：F值
规则抽取
规则产生
- 读取每个分支（深度优先）得到原始规则集
- 将规则集进行合并
- 得到最终规则集
规则合并
只需考虑后置条件相同的前置条件合并。
进一步改进
- 纯度计算
- 错误率计算
加权（成本函数）
成本函数的确定 - 多属性组合分类
链接分析
中心性
重要的或突出的参与者是链接到或涉及到大量其他参与者的参与者。
中心性度量：
度中心性：中心参与者是与其他参与者的链接最多的参与者
接近中心性：中心参与者是到其他参与者距离最短的参与者
中介中心性：中介性用来度量参与者对于其他节点对的控制能力
权威性
一个权威的参与者是被大量链接指向的参与者
PageRank
对于上面这个网页链接关系，我们假设初始看各网页概率相同，都是1/4，作为初始向量V0，不断迭代得到各个网页的重要性：
实际操作时，一般要去除终止点和陷阱点：
或者增加一个随机跳转机制：
漏斗模型
- 自顶向下
- 逐层表示流程中的各个环节
- 数量与比例
- 流失原因分析
- 转化率
关键路径
关键路径指的是设计中从输入到输出经过的延时时间最长的路径，也就是完成项目至少所需的时间，关键路径上的活动是影响工程进度的关键。
相关名词
顶点——事件
弧——活动
弧上的权值——活动持续的时间
规则
- 只有在moi顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
- 只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生；
算法
- 顺向计算活动开始的最早时间e(i)
- 逆向计算活动开始的最晚时间l(i)
- e(i) = l(i)的活动为关键活动
- 所有关键活动及相关事件组成关键路径
矩阵分析
矩阵表示两个元素之间的关联关系，行列代表不同的因素，值为关联关系。
矩阵分解法
矩阵C（mn）= 矩阵A（mk）* 矩阵B（k*n）
也就是我们可以通过引入因素k，将因素m与因素n的关系，拆分成因素m与因素k的关系以及因素与因素n的关系。
应用
如果因素m与因素k的关联关系已知，则可计算因素k与因素n的关联关系。
并行计算
Cij仅仅与A的第i行和B的第j列有关，而与Cpq（p,q != i,j）
我们可以分布式并行分别处理Cij
作者：其实是个驴
参考：课件