资源描述：
《大数据经典算法c4.5讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、决策树算法C4.5组长：赵庆杰报告人：赵庆杰成员：潘志舟朱鹏刘纯汪光炼漆学志提纲必备概念知识算法背景简介算法描述必备概念知识数据挖掘分类和聚类决策树ID3算法C4.5算法数据挖掘Dataminingisthecomputationalprocessofdiscoveringpatternsinlargedatasetsinvolvingmethodsattheintersectionofartificialintelligence,machinelearning,statistics,anddata
2、basesystems.Theoverallgoalofthedataminingprocessistoextractinformationfromadatasetandtransformitintoanunderstandablestructureforfurtheruse.（Wikipedia）数据挖掘一般是指从大量的数据中自动搜索隐藏于其中的有着特殊关系性的信息的过程。(百度百科)分类和聚类分类(Classification)就是按照某种标准给对象贴标签，再根据标签来区分归类，类别数不变。聚类
3、(clustering)是指根据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫做簇，并且对每一个这样的簇进行描述的过程。决策树决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。ID3算法C4.5算法ID3算法介绍样本的表示方法向量表示:假设一个样本有n个变量(特征)Ⅹ=(X1,X2,…,Xn)T2.
4、矩阵表示:N个样本，n个变量(特征)ID3算法介绍3几何表示4基元（链码）表示条件属性和决策属性ID3算法介绍一个离散型属性样本实例——PlayTennis数据库片段：ID3算法介绍关于PlayTennis的决策树：ID3算法介绍1986年，Quinlan提出了著名的ID3算法。用ID3算法长树的基本思想：分类能力最好的属性被测试并创建树的根结点测试属性每个可能的值产生一个分支训练样本划分到适当的分支形成儿子结点重复上面的过程，直到所有的结点都是叶子结点两个问题：什么属性最好？什么结点才是叶子结点？
5、优先选择哪些属性测试什么时候结束树的增长信息增益（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的概率
6、，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={sSA(s)=v}；E(Sv)为将Sv中的样本划分为c个类的信息熵。
7、Sv
8、/
9、S
10、为Sv和S中的样本个数之比。条件属性outlo
11、ok共有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….
12、Gain(Outlook)=0.940-0.694=0.246，Gain(Windy)=0.940-0.892=0.048….回顾ID3算法ID3算法每一步选择具有最大信息增益的属性作为测试属性来长树。直到最大的信息增益为也零为止。（两个问题的解决）ID3算法存在的主要不足：过度拟合问题(treeprunning)决策树算法增长树的每一个分支的深度，直到恰好能对训练样例比较完美地分类。实际应用中，当数据中有噪声或训练样例的数量太少以至于不能产生目标函数的有代表性的采样
