决策树算法基础 ID3与C4.5

1. 决策树算法基础 ID3与C4.5

决策树算法基础：ID3与C4.5
设X是一个取有限个值得离散随机变量，其概率分布为P(X=xi)=pi,   i=1,2,…,n。则随机变量X的信息熵为
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。H(Y|X)的计算公式为
所以决策树分支后信息总熵H(D|A)=P1*H1+P2*H2+...+Pn*Hn,(特征A条件下D的经验条件熵)
所以信息增益ΔH=H(D)-H(D|A)
H(D|A)越小，ΔH越大，该特征A越适合作为当前的决策节点。
选取最佳特征伪代码：
计算信息总熵H(D)
遍历每一个特征下的关于D的经验条件熵H(D|A)
计算每一个特征的信息增益ΔH
将信息增益ΔH最大的特征作为最佳特征选为当前决策节点
ID3算法伪代码：
如果第一个标签的数量等于所有的标签数量，说明这是一个单节点树，返回这个标签作为该节点类
如果特征只有一个，说明这是一个单节点树，用多数表决法投票选出标签返回作为该节点类
否则，按信息增益最大的特征A作为当前决策节点，即决策树父节点
如果该特征的信息增益ΔH小于阈值，则用多数表决法投票选出标签返回作为该节点类
否则，对于该特征A的每一个可能值ai，将原空间D分割为若干个子空间Di
对于若干个非空子集Di，将每个Di中实例数最大的类作为标记，构建子节点
以Di为训练空间，递归调用上述步骤
由于信息增益存在偏向于选择取值较多的特征的问题，而C4.5算法中，将ID3算法里的信息增益换成信息增益比，较好地解决了这个问题。
决策树的优点在于计算量简单，适合有缺失属性值的样本，适合处理不相关的特征。而缺点是容易过拟合，可以通过剪枝来简化模型，另外随机森林也解决了这个问题。

2. 决策树之ID3算法及其Python实现

决策树之ID3算法及其Python实现

1. 决策树背景知识 
??决策树是数据挖掘中最重要且最常用的方法之一，主要应用于数据挖掘中的分类和预测。决策树是知识的一种呈现方式，决策树中从顶点到每个结点的路径都是一条分类规则。决策树算法最先基于信息论发展起来，经过几十年发展，目前常用的算法有：ID3、C4.5、CART算法等。
2. 决策树一般构建过程 
??构建决策树是一个自顶向下的过程。树的生长过程是一个不断把数据进行切分细分的过程，每一次切分都会产生一个数据子集对应的节点。从包含所有数据的根节点开始，根据选取分裂属性的属性值把训练集划分成不同的数据子集，生成由每个训练数据子集对应新的非叶子节点。对生成的非叶子节点再重复以上过程，直到满足特定的终止条件，停止对数据子集划分，生成数据子集对应的叶子节点，即所需类别。测试集在决策树构建完成后检验其性能。如果性能不达标，我们需要对决策树算法进行改善，直到达到预期的性能指标。 
??注：分裂属性的选取是决策树生产过程中的关键，它决定了生成的决策树的性能、结构。分裂属性选择的评判标准是决策树算法之间的根本区别。
3. ID3算法分裂属性的选择——信息增益 
??属性的选择是决策树算法中的核心。是对决策树的结构、性能起到决定性的作用。ID3算法基于信息增益的分裂属性选择。基于信息增益的属性选择是指以信息熵的下降速度作为选择属性的方法。它以的信息论为基础，选择具有最高信息增益的属性作为当前节点的分裂属性。选择该属性作为分裂属性后，使得分裂后的样本的信息量最大，不确定性最小，即熵最小。 
??信息增益的定义为变化前后熵的差值，而熵的定义为信息的期望值，因此在了解熵和信息增益之前，我们需要了解信息的定义。 
??信息：分类标签xi 在样本集 S 中出现的频率记为 p(xi)，则 xi 的信息定义为：?log2p(xi) 。 
??分裂之前样本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 为分类标签的个数。 
??通过属性A分裂之后样本集的熵：EA(S)=?∑mj=1|Sj||S|E(Sj)，其中 m 代表原始样本集通过属性A的属性值划分为 m 个子样本集，|Sj| 表示第j个子样本集中样本数量，|S| 表示分裂之前数据集中样本总数量。 
??通过属性A分裂之后样本集的信息增益：InfoGain(S,A)=E(S)?EA(S) 
??注：分裂属性的选择标准为：分裂前后信息增益越大越好，即分裂后的熵越小越好。
4. ID3算法 
??ID3算法是一种基于信息增益属性选择的决策树学习方法。核心思想是：通过计算属性的信息增益来选择决策树各级节点上的分裂属性，使得在每一个非叶子节点进行测试时，获得关于被测试样本最大的类别信息。基本方法是：计算所有的属性，选择信息增益最大的属性分裂产生决策树节点，基于该属性的不同属性值建立各分支，再对各分支的子集递归调用该方法建立子节点的分支，直到所有子集仅包括同一类别或没有可分裂的属性为止。由此得到一棵决策树，可用来对新样本数据进行分类。
ID3算法流程： 
(1) 创建一个初始节点。如果该节点中的样本都在同一类别，则算法终止，把该节点标记为叶节点，并用该类别标记。 
(2) 否则，依据算法选取信息增益最大的属性，该属性作为该节点的分裂属性。 
(3) 对该分裂属性中的每一个值，延伸相应的一个分支，并依据属性值划分样本。 
(4) 使用同样的过程，自顶向下的递归，直到满足下面三个条件中的一个时就停止递归。 
??A、待分裂节点的所有样本同属于一类。 
??B、训练样本集中所有样本均完成分类。 
??C、所有属性均被作为分裂属性执行一次。若此时，叶子结点中仍有属于不同类别的样本时，选取叶子结点中包含样本最多的类别，作为该叶子结点的分类。
ID3算法优缺点分析 
优点：构建决策树的速度比较快，算法实现简单，生成的规则容易理解。 
缺点：在属性选择时，倾向于选择那些拥有多个属性值的属性作为分裂属性，而这些属性不一定是最佳分裂属性；不能处理属性值连续的属性；无修剪过程，无法对决策树进行优化，生成的决策树可能存在过度拟合的情况。

3. 决策树的算法

 C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；2) 在树构造过程中进行剪枝；3) 能够完成对连续属性的离散化处理；4) 能够对不完整数据进行处理。C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。具体算法步骤如下；1创建节点N2如果训练集为空，在返回节点N标记为Failure3如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N4如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；5for each 候选属性 attribute_list6if 候选属性是连续的then7对该属性进行离散化8选择候选属性attribute_list中具有最高信息增益率的属性D9标记节点N为属性D10for each 属性D的一致值d11由节点N长出一个条件为D=d的分支12设s是训练集中D=d的训练样本的集合13if s为空14加上一个树叶，标记为训练集中最普通的类15else加上一个有C4.5（R - {D},C，s）返回的点 背景：分类与回归树(CART——Classification And Regression Tree)) 是一种非常有趣并且十分有效的非参数分类和回归方法。它通过构建二叉树达到预测目的。分类与回归树CART 模型最早由Breiman 等人提出，已经在统计领域和数据挖掘技术中普遍使用。它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显著。模型的关键是预测准则的构建，准确的。定义：分类和回归首先利用已知的多变量数据构建预测准则, 进而根据其它变量值对一个变量进行预测。在分类中, 人们往往先对某一客体进行各种测量, 然后利用一定的分类准则确定该客体归属那一类。例如, 给定某一化石的鉴定特征, 预测该化石属那一科、那一属, 甚至那一种。另外一个例子是, 已知某一地区的地质和物化探信息, 预测该区是否有矿。回归则与分类不同, 它被用来预测客体的某一数值, 而不是客体的归类。例如, 给定某一地区的矿产资源特征, 预测该区的资源量。

4. 决策树算法

决策树算法的算法理论和应用场景
  
 算法理论：
  
 我了解的决策树算法，主要有三种，最早期的ID3，再到后来的C4.5和CART这三种算法。
  
 这三种算法的大致框架近似。
  
 决策树的学习过程
  
 1.特征选择
  
 在训练数据中 众多X中选择一个特征作为当前节点分裂的标准。如何选择特征有着很多不同量化评估标准，从而衍生出不同的决策树算法。
  
 2.决策树生成
  
 根据选择的特征评估标准，从上至下递归生成子节点，直到数据集不可分或者最小节点满足阈值，此时决策树停止生长。
  
 3.剪枝
  
 决策树极其容易过拟合，一般需要通过剪枝，缩小树结构规模、缓解过拟合。剪枝技术有前剪枝和后剪枝两种。
  
 有些算法用剪枝过程，有些没有，如ID3。
  
 预剪枝：对每个结点划分前先进行估计，若当前结点的划分不能带来决策树的泛化性能的提升，则停止划分，并标记为叶结点。
  
 后剪枝：现从训练集生成一棵完整的决策树，然后自底向上对非叶子结点进行考察，若该结点对应的子树用叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。
  
 但不管是预剪枝还是后剪枝都是用验证集的数据进行评估。
  
 ID3算法是最早成型的决策树算法。ID3的算法核心是在决策树各个节点上应用信息增益准则来选择特征，递归构建决策树。缺点是，在选择分裂变量时容易选择分类多的特征，如ID值【值越多、分叉越多，子节点的不纯度就越小，信息增益就越大】。
  
 ID3之所以无法 处理缺失值、无法处理连续值、不剪纸等情况，主要是当时的重点并不是这些。
  
 C4.5算法与ID3近似，只是分裂标准从 信息增益 转变成  信息增益率。可以处理连续值，含剪枝，可以处理缺失值，这里的做法多是 概率权重。
  
 CART：1.可以处理连续值 2.可以进行缺失值处理 3.支持剪枝 4.可以分类可以回归。
  
 缺失值的处理是 作为一个单独的类别进行分类。
  
 建立CART树
  
 我们的算法从根节点开始，用训练集递归的建立CART树。
  
 1) 对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。
  
 2) 计算样本集D的基尼系数， 如果基尼系数小于阈值 （说明已经很纯了！！不需要再分了！！），则返回决策树子树，当前节点停止递归。
  
 3) 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数。
  
 4) 在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择 基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2。 (注：注意是二叉树，故这里的D1和D2是有集合关系的，D2=D-D1)
  
 5) 对左右的子节点递归的调用1-4步，生成决策树。
  
 CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。
  
 
  
                                          
 
  
                                                                                  
 应用场景
  
 比如欺诈问题中，通过决策树算法简单分类，默认是CART的分类树，默认不剪枝。然后在出图后，自行选择合适的叶节点进行拒绝操作。
  
 这个不剪枝是因为欺诈问题的特殊性，欺诈问题一般而言较少，如数据的万几水平，即正样本少，而整个欺诈问题需要解决的速度较快。此时只能根据业务要求，迅速针对已有的正样本情况，在控制准确率的前提下，尽可能提高召回率。这种情况下，可以使用决策树来简单应用，这个可以替代原本手工选择特征及特征阈值的情况。

5. （2）决策树算法及其应用

判定树是一个类似于流程图的树结构：其中，每个内部结点表示一个属性上的测试，每个分支代表一个属性输出，而每个树叶节点代表类或类分布。树的最顶层是根节点。
                                          
 一条信息的信息量大小和它的不确定性有直接的关系，信息量的度量就等于不确定性的多少。信息量的计算公式如下所示：
   ** 变量的不确定性越大，熵越大 **
                                          
 选择属性判断结点
   信息获取量（Information Gain):Gain(A)= Info(D) - Infor_A(D)通过A作为节点分类获取了多少信息。
   实例，以下是对是否购买计算机的群体的一项数据调查:
                                          
 已知从结果上来看的信息量是:
                                                                                                                          
 依次类推，当将age作为第一个结点之后，会得到新生成的三个结点，然后再次重复计算，将三个结点按照决策树原理再次进行分类，知道分类结果唯一。
                                                                                                                          
 优点:
   直观 便于理解 小规模数据集有效
   缺点:
   处理连续性变量不好 错误增加的比较快 不适用于大规模数据集
  
 分类（classfication）、回归（regression）、聚类（clustering），降维（dimensionality）
   模型选择（model selection）、预处理（preprocessing）
  
 使用的数据文件
                                          
 得到的dot文件
                                          
 使用graphviz将dot文件转为png，pdf

6. 如何实现并应用决策树算法

决策树的典型算法有ID3，C4.5，CART等。
国际权威的学术组织，数据挖掘国际会议ICDM （the IEEE International Conference on Data Mining）在2006年12月评选出了数据挖掘领域的十大经典算法中，C4.5算法排名第一。C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。C4.5算法产生的分类规则易于理解，准确率较高。不过在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，在实际应用中因而会导致算法的低效。
决策树算法的优点如下：
（1）分类精度高；
（2）生成的模式简单；
（3）对噪声数据有很好的健壮性。
因而是目前应用最为广泛的归纳推理算法之一，在数据挖掘中受到研究者的广泛关注。

7. 决策树算法的典型算法

决策树的典型算法有ID3，C4.5，CART等。国际权威的学术组织，数据挖掘国际会议ICDM （the IEEE International Conference on Data Mining）在2006年12月评选出了数据挖掘领域的十大经典算法中，C4.5算法排名第一。C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法。C4.5算法产生的分类规则易于理解，准确率较高。不过在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，在实际应用中因而会导致算法的低效。决策树算法的优点如下：（1）分类精度高；（2）生成的模式简单；（3）对噪声数据有很好的健壮性。因而是目前应用最为广泛的归纳推理算法之一，在数据挖掘中受到研究者的广泛关注。

8. 决策树算法的介绍

决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树方法最早产生于上世纪60年代，到70年代末。由J Ross Quinlan提出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数据集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除。