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

1、决策树算法 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 pr

2、ocess is to extract information from a data set and transform it into an understandable structure for further use.（Wikipedia）数据挖掘一般是指从大量的数据中自动搜索隐藏于其中的有着特殊关系性的信息的过程。(百度百科)分类和聚类分类(Classification)就是按照某种标准给对象贴标签，再根据标签来区分归类，类别数不变。聚类(clustering)是指根据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫做簇，并且对每一个这样的簇进行描

3、述的过程。决策树决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。ID3算法C4.5算法ID3算法介绍样本的表示方法向量表示 : 假设一个样本有n个变量(特征) = (X1,X2,Xn)T2. 矩阵表示: N个样本，n个变量(特征)ID3算法介绍3几何表示4基元（链码）表示条件属性和决策属性ID3算法介绍一个离散型属性样本实例PlayTennis数据库片段：ID3算法介绍关于PlayTennis的决策树：ID3算法介绍1986年

4、，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导致的期望熵。所谓增益，就是指在应用了某一测试之后，其对应的可能性丰富程度

5、下降，不确定性减小，这个减小的幅度就是增益，其实质上对应着分类带来的好处熵（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期望熵（Expected Entropy）属性A划分样本集S导致的期望熵E(S, A)为： 其中，Values(A)为属性A取值的集合；Sv为S中A取值为v的样本子集，Sv=sS A(s)=v；E(Sv)为将S

6、v中的样本划分为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.Ga

7、in(Outlook)=0.940-0.694=0.246，Gain(Windy)=0.940-0.892=0.048.回顾ID3算法ID3算法每一步选择具有最大信息增益的属性作为测试属性来长树。直到最大的信息增益为也零为止。（两个问题的解决）ID3算法存在的主要不足：过度拟合问题(tree prunning)决策树算法增长树的每一个分支的深度，直到恰好能对训练样例比较完美地分类。实际应用中，当数据中有噪声或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时，该策略可能会遇到困难。处理连续属性值问题(discretization)处理缺少属性值问题(replacement)属性选择的度

8、量标准问题(heuristic measure)针对这些不足， Quinlan做了一系列的改进，并于1993年形成了C4.5算法。C4.5算法介绍一个含有连续型属性样本实例PlayGolf数据库片段：C4.5算法应该解决的问题如何选择测试属性构造决策树？对于连续变量决策树中的测试是怎样的？如何选择处理连续变量（阀值）？如何终止树的增长?如何确定叶子节点的类？决策树关于PlayGolf的决策树：如何选择测试属性构造决策树？用信息增益率来选择属性这个指标实际上就等于增益/熵，之所以采用这个指标是为了克服采用增益作为衡量标准的缺点，采用增益作为衡量标准会导致分类树倾向于优先选择那些具有比较多的分支的

9、测试，也就是选择取值较多的属性，这种倾向需要被抑制其中，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算法中，连续变量的分支总是两条，分支其测试分支分别对应着，对应着分支阈值，但是这个怎么确定呢？很简单，把需要处理的样本（对应根节点）或样本子集（对应子树）按照连续变量的大小从小到大进行排序，假设该属性对应的不同

10、的属性值一共有N个，那么总共有N-1个可能的候选分割阈值点，每个候选的分割阈值点的值为上述排序后的属性值链表中两两前后连续元素的中点，那么我们的任务就是从这个N-1个候选分割阈值点中选出一个，使得前面提到的信息论标准最大。举个例子，对于Golf数据集，我们来处理温度属性，来选择合适的阈值。首先按照温度大小对对应样本进行排序如下那么可以看到有13个可能的候选阈值点，比如middle64,65, middle65,68.,middle83,85。那么最优的阈值该选多少呢？应该是middle71,72，如上图中红线所示。为什么呢？如下计算：通过上述计算方式，0.939是最大的，因此测试的增益是最小的。（测试的增益和测试后的熵是成反比的，这个从后面的公式可以很清楚的看到）。根据上面的描述，我们需要对每个候选分割阈值进行增益或熵的计算才能得到最优的阈值，我们需要算N-1次增益或熵（对应温度这个变量而言就是13次计算）。能否有所改进呢？少算几次，加快速度。答案是可以该进如何终止树的增长?前面提到树的增长实际上是一个递归过程,那么这个递归什么时候到达终止条件退出递归呢?有两种方式,第一种方式是如果某一节点的分支所覆盖的样本都属于同一类的时候,那么递归就可以终止,该分支就会产生一个叶子节点.还有一种方式就是，如果某一分支覆盖的样本的个数如果小于一个阈值，那么也