大数据经典算法c4.5讲解幻灯片.ppt

决策树算法C4 5 组长 赵庆杰报告人 赵庆杰成员 潘志舟朱鹏刘纯汪光炼漆学志 提纲 必备概念知识算法背景简介算法描述 必备概念知识 数据挖掘分类和聚类决策树ID3算法C4 5算法 数据挖掘Dataminingisthecomputationalprocessofdiscoveringpatternsinlargedatasetsinvolvingmethodsattheintersectionofartificialintelligence machinelearning statistics anddatabasesystems Theoverallgoalofthedataminingprocessistoextractinformationfromadatasetandtransformitintoanunderstandablestructureforfurtheruse Wikipedia 数据挖掘一般是指从大量的数据中自动搜索隐藏于其中的有着特殊关系性的信息的过程 百度百科 分类和聚类分类 Classification 就是按照某种标准给对象贴标签 再根据标签来区分归类 类别数不变 聚类 clustering 是指根据 物以类聚 的原理 将本身没有类别的样本聚集成不同的组 这样的一组数据对象的集合叫做簇 并且对每一个这样的簇进行描述的过程 决策树决策树是一种典型的分类方法 首先对数据进行处理 利用归纳算法生成可读的规则和决策树 然后使用决策对新数据进行分析 本质上决策树是通过一系列规则对数据进行分类的过程 由于这种决策分支画成图形很像一棵树的枝干 故称决策树 ID3算法C4 5算法 ID3算法介绍 样本的表示方法向量表示 假设一个样本有n个变量 特征 X1 X2 Xn T2 矩阵表示 N个样本 n个变量 特征 ID3算法介绍 3几何表示4基元 链码 表示条件属性和决策属性 ID3算法介绍 一个离散型属性样本实例 PlayTennis数据库片段 ID3算法介绍 关于PlayTennis的决策树 ID3算法介绍 1986年 Quinlan提出了著名的ID3算法 用ID3算法长树的基本思想 分类能力最好的属性被测试并创建树的根结点测试属性每个可能的值产生一个分支训练样本划分到适当的分支形成儿子结点重复上面的过程 直到所有的结点都是叶子结点两个问题 什么属性最好 什么结点才是叶子结点 优先选择哪些属性测试 什么时候结束树的增长 信息增益 InformationGain 属性A划分样本集S的信息增益Gain S A 为 Gain S A E S E S A 其中 E S 为划分样本集S为c个类的熵 E S A 为属性A划分样本集S导致的期望熵 所谓增益 就是指在应用了某一测试之后 其对应的可能性丰富程度下降 不确定性减小 这个减小的幅度就是增益 其实质上对应着分类带来的好处 熵 Entropy 划分样本集S为c个类的熵E S 为 其中 pi ni n 为S中的样本属于第i类Ci的概率 n为S中样本的个数 决策属性分为YES NO两类 S1 YES 9 S2 NO 5 S S1 S2 14E S 9 14 log2 9 14 5 14 log2 5 14 0 940 期望熵 ExpectedEntropy 属性A划分样本集S导致的期望熵E S A 为 其中 Values A 为属性A取值的集合 Sv为S中A取值为v的样本子集 Sv s S A s v E Sv 为将Sv中的样本划分为c个类的信息熵 Sv S 为Sv和S中的样本个数之比 条件属性outlook共有sunny overcast rain三个取值sunny的取值为5个 其中YES和NO的比例是2 3 I sunny 2 5 log2 2 5 3 5 log2 3 5 0 976I overcast 4 4 log2 4 4 0 000I rain 3 5 log2 3 5 2 5 log2 2 5 0 976E S outlook 5 14 0 976 4 14 0 000 5 14 0 976 0 694E S windy 0 892 Gain Outlook 0 940 0 694 0 246 Gain Windy 0 940 0 892 0 048 回顾ID3算法 ID3算法每一步选择具有最大信息增益的属性作为测试属性来长树 直到最大的信息增益为也零为止 两个问题的解决 ID3算法存在的主要不足 过度拟合问题 treeprunning 决策树算法增长树的每一个分支的深度 直到恰好能对训练样例比较完美地分类 实际应用中 当数据中有噪声或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时 该策略可能会遇到困难 处理连续属性值问题 discretization 处理缺少属性值问题 replacement 属性选择的度量标准问题 heuristicmeasure 针对这些不足 Quinlan做了一系列的改进 并于1993年形成了C4 5算法 C4 5算法介绍 一个含有连续型属性样本实例 PlayGolf数据库片段 C4 5算法应该解决的问题 如何选择测试属性构造决策树 对于连续变量决策树中的测试是怎样的 如何选择处理连续变量 阀值 如何终止树的增长 如何确定叶子节点的类 决策树 关于PlayGolf的决策树 如何选择测试属性构造决策树 用信息增益率来选择属性这个指标实际上就等于增益 熵 之所以采用这个指标是为了克服采用增益作为衡量标准的缺点 采用增益作为衡量标准会导致分类树倾向于优先选择那些具有比较多的分支的测试 也就是选择取值较多的属性 这种倾向需要被抑制其中 S1到Sc是c个不同值的属性A分割S而形成的c个样本子集 如按照属性A把S集 含30个用例 分成了10个用例和20个用例两个集合则SplitInfo S A 1 3 log 1 3 2 3 log 2 3 对于连续变量决策树中的测试是怎样的 很明显 我们看到这个例子中对于连续变量 所有连续变量的测试分支都是2条 因此在C4 5算法中 连续变量的分支总是两条 分支其测试分支分别对应着 对应着分支阈值 但是这个 怎么确定呢 很简单 把需要处理的样本 对应根节点 或样本子集 对应子树 按照连续变量的大小从小到大进行排序 假设该属性对应的不同的属性值一共有N个 那么总共有N 1个可能的候选分割阈值点 每个候选的分割阈值点的值为上述排序后的属性值链表中两两前后连续元素的中点 那么我们的任务就是从这个N 1个候选分割阈值点中选出一个 使得前面提到的信息论标准最大 举个例子 对于Golf数据集 我们来处理温度属性 来选择合适的阈值 首先按照温度大小对对应样本进行排序如下 那么可以看到有13个可能的候选阈值点 比如middle 64 65 middle 65 68 middle 83 85 那么最优的阈值该选多少呢 应该是middle 71 72 如上图中红线所示 为什么呢 如下计算 通过上述计算方式 0 939是最大的 因此测试的增益是最小的 测试的增益和测试后的熵是成反比的 这个从后面的公式可以很清楚的看到 根据上面的描述 我们需要对每个候选分割阈值进行增益或熵的计算才能得到最优的阈值 我们需要算N 1次增益或熵 对应温度这个变量而言就是13次计算 能否有所改进呢 少算几次 加快速度 答案是可以该进 如何终止树的增长 前面提到树的增长实际上是一个递归过程 那么这个递归什么时候到达终止条件退出递归呢 有两种方式 第一种方式是如果某一节点的分支所覆盖的样本都属于同一类的时候 那么递归就可以终止 该分支就会产生一个叶子节点 还有一种方式就是 如果某一分支覆盖的样本的个数如果小于一个阈值 那么也可产生叶子