大数据十大经典算法c4.5讲解.ppt

决策树算法￿C4.5提纲•必备概念知识•算法背景简介•算法描述必备概念知识•数据挖掘•分类和聚类•决策树•ID3算法•C4.5算法•数据挖掘•Data￿mining￿is￿the￿computational￿process￿of￿discovering￿patterns￿in￿large￿data￿sets￿involving￿methods￿at￿the￿intersection￿of￿artificial￿intelligence,￿machine￿learning,￿statistics,￿and￿database￿systems.The￿overall￿goal￿of￿the￿data￿mining￿process￿is￿to￿extract￿information￿from￿a￿data￿set￿and￿transform￿it￿into￿an￿understandable￿structure￿for￿further￿use.（Wikipedia）•数据挖掘一般是指从大量的数据中自动搜索隐藏于其中的有着特殊关系性的信息的过程百度百科)•分类和聚类•分类(Classification)就是按照某种标准给对象贴标签，再根据标签来区分归类，类别数不变。

•聚类(clustering)是指根据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫做簇，并且对每一个这样的簇进行描述的过程•决策树决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析本质上决策树是通过一系列规则对数据进行分类的过程由于这种决策分支画成图形很像一棵树的枝干，故称决策树•ID3算法•C4.5算法ID3算法介绍•样本的表示方法1.向量表示￿:￿￿假设一个样本有n个变量(特征)￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿Ⅹ=￿(X1,X2,…,Xn)T2.￿矩阵表示:￿￿￿￿N个样本，n个变量(特征)ID3算法介绍•3几何表示•4基元（链码）表示•条件属性和决策属性ID3算法介绍•一个离散型属性样本实例——PlayTennis数据库片段：ID3算法介绍•关于PlayTennis的决策树：ID3算法介绍•1986年，Quinlan提出了著名的ID3算法•用ID3算法长树的基本思想：–分类能力最好的属性被测试并创建树的根结点–测试属性每个可能的值产生一个分支–训练样本划分到适当的分支形成儿子结点–重复上面的过程，直到所有的结点都是叶子结点两个问题：什么属性最好？什么结点才是叶子结点？优先选择哪些属性测试什么时候结束树的增长信息增益（Information￿Gain）•属性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=14•E（S）=-(9/14)log2(9/14)-(5/14)log2(5/14)=0.940期望熵（Expected￿Entropy）•属性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.976 E(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算法存在的主要不足：–过度拟合问题(tree￿prunning)决策树算法增长树的每一个分支的深度，直到恰好能对训练样例比较完美地分类实际应用中，当数据中有噪声或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时，该策略可能会遇到困难–处理连续属性值问题(discretization)–处理缺少属性值问题(replacement)–属性选择的度量标准问题(heuristic￿measure)•针对这些不足，￿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次计算）能否有所改进呢？少算几次，加快速度答案是可以该进如何终止树的增长?•前面提到树的增长实际上是一个递归过程,那么这个递归什么时候到达终止条件退出递归呢?有两种方式,第一种方式是如果某一节点的分支所覆盖的样本都属于同一类的时候,那么递归就可以终止,该分支就会产生一个叶子节点.还有一种方式就是，如果某一分支覆盖的样本的个数如果小于一个阈值，那么也可产生叶子节点，从而终止树的增长如何确定叶子节点的类？•Tree-Growth终止的方式有2种，对于第一种方式，叶子节点覆盖的样本都属于同一类，那么这种情况下叶子节点的类自然不必多言对于第二种方式，叶子节点覆盖的样本未必属于同一类，直接一点的方法就是，该叶子节点所覆盖的样本哪个类占大多数，那么该叶子节点的类别就是那个占大多数的类致谢欢迎提问。