决策树模型介绍

1、决策树模型介绍2决策树模型的介绍3决策树的基本流程目录 CONTENTS1应用案例RealRec案例演示4引 例适用情况现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话： 女儿：多大年纪了？ 母亲：26。 女儿：长的帅不帅？ 母亲：挺帅的。 女儿：收入高不？ 母亲：不算很高，中等情况。 女儿：是公务员不？ 母亲：是，在税务局上班呢。 女儿：那好，我去见见。可以用下图表示女孩的决策逻辑:4地铁大数据案例演示地铁预测人流生成过程对数据进行预处理删除空值剔除噪声采集分类每个乘客的数据对每个乘客构建一个决策树使用决策树预测统计所有进行预测站点人流情况2决策树模型的介绍3决策树的基本流程目

2、录 CONTENTS1应用案例RealRec案例演示4决策树模型起源：E.B.Hunt等人于1966年发表的论文“experiments in Induction”罗斯.昆兰在1979年提出了ID3算法，掀起了决策树研究的高潮发展：后人ID4，ID5算法的发展昆兰在1993年提出的C4.5是现在最常用的决策树算法决策树模型决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出

3、分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。优点：直观，容懂2决策树模型的介绍3决策树的基本流程目录 CONTENTS1应用案例RealRec案例演示4决策树模型构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。如何选择分裂属性？划分选择基尼指数信息增益增益率划分选择信息增益从信息论知识中我们直到，期望信息越小，信息增益越大，从而纯度越高。ID3算法的核心思想：以信息增益度量属性选择，选择分裂后信息增益最大的 属性进行分裂。下面先定义几个要用到的概念：信息熵，信息增益划分选择信息增益其中pi

4、表示第i个类别在整个训练元组中出现的概率。信息熵（information entropy） 设D为用类别对训练元组进行的划分，则D的信息熵（entropy）表示为：信息增益（information gain） 假设将训练元组D按属性A进行划分，则A对D划分的期望信息为：信息增益即为两者的差值：划分选择信息增益例子：以SNS社区中不真实账号检测为例来 说明如何使用信息增益构造决策树。其中s、m和l分别表示小、中和大。L、F、H和R表示日志密度、好友密度、是否使用真实头像和账号是否真实。划分选择信息增益第一步：计算各属性的信息增益。 L的信息增益计算过程如下： 用同样的方式算出H和F的信息增益分别

5、为0.033和0.553。划分选择信息增益第二步：第一次选择分类属性 因为F具有最大的信息增益，所以第一次分裂选择F为分裂属性，分裂后的结果如下图表示：第三步：递归计算子节点的分裂属性在上图的基础上，再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。划分选择信息增益信息增益问题对取值数目较多的属性有偏好 例如：如果存在唯一标识属性ID，则信息增益会选择它作为分裂属性，但这种划分对分类几乎毫无用处。解决方法划分选择-增益率划分选择增益率 C4.5算法选择具有最大增益率的属性作为分裂属性定义 “分裂信息” 为：定义增益率为：划分选择增益率增益率算法优点信息增益偏向于多值属性，增益率

6、调整了这种偏倚增益率算法缺点倾向于产生不平衡的划分，其中一个分区比其他分区小得多。划分选择基尼指数基尼指数度量数据分区或训练元组集D的不纯度 基尼指数定义为：属性a的基尼指数定义为：其中pi是D中元组属于Ci类的概率，对m个类计算和。划分选择基尼指数基尼指数算法的问题倾向于导致相等大小的分区和纯度基尼指数偏向于多值属性当类的数量很大时会有困难剪枝处理决策树问题节点划分过程不断重复容易导致过拟合解决方法先剪枝后剪枝剪枝处理先剪枝通过提前停止树的构建（例如，通过决定在给定的节点不再分裂或划分训练元组的子集）而对树“剪枝”。一旦停止，结点就成为树叶。后剪枝它由“完全生长”的树剪去子树。通过删除节点的

7、分枝并用树叶替换它而剪掉给定结点上的子树。该树叶的类标号用子树中最频繁的类标记。对连续值和缺失值的处理对连续值的处理连续属性离散化对特征的取值进行升序排序两个特征取值之间的中点作为可能的分裂点，将数据集分成两部分计算每个可能的分裂点的信息增益，选择最大的分裂点作为该特征的最佳分裂点对连续值和缺失值的处理对缺失值的处理对于某一属性先计算在该属性没有缺失值时候的样本子集计算无缺失样本在该划分属性上的信息增益Gain对该属性，计算无缺失值样本所占的比例 p信息增益的计算式得以推广：Gain*P26决策树模型可以生成可以理解的规则;计算量相对来说不是很大;可以处理多种数据类型;决策树可以清晰的显示哪些变量较重要。算法优点算法