Question

决策树ID3，C4.5，CART算法中某一属性分类后，是否能运用该属性继续分类

我在看算法的时候发现ID3在使用一个属性进行分类后，它的枝叶中是把该属性剔除的也就是不能再用该属性进行分类，而在MATLAB函数fitctree中看到同一属性是可以重复使用的，而matlab使用的算法应该是cart，是不是这三种算法在这一点上不相同？各是什么情况呢？

Answer 1

决策树主要有ID3，C4.5，CART等形式。ID3选取信息增益的属性递归进行分类，C4.5改进为使用信息增益率来选取分类属性。CART是Classfication and Regression Tree的缩写。表明CART不仅可以进行分类，也可以进行回归。其中使用基尼系数选取分类属性。以下主要介绍ID3和CART算法。
ID3算法：
信息熵： H(X)=-sigma（对每一个x）（plogp） H(Y|X)=sigma(对每一个x)（pH(Y|X=xi)）
信息增益：H（D）-H(D|X) H(D)是整个数据集的熵
信息增益率：（H(D)-H(D|X)）/H(X)
算法流程：（1）对每一个属性计算信息增益，若信息增益小于阈值，则将该支置为叶节点，选择其中个数最多的类标签作为该类的类标签。否则，选择其中最大的作为分类属 性。
（2）若各个分支中都只含有同一类数据，则将这支置为叶子节点。
否则 继续进行（1）。
CART算法：
基尼系数：Gini（p）=sigma（每一个类）p(1-p)
回归树：属性值为连续实数。将整个输入空间划分为m块，每一块以其平均值作为输出。f(x)=sigma(每一块)Cm*I(x属于Rm)
回归树生成：（1）选取切分变量和切分点，将输入空间分为两份。
（2）每一份分别进行第一步，直到满足停止条件。
切分变量和切分点选取：对于每一个变量进行遍历，从中选择切分点。选择一个切分点满足分类均方误差最小。然后在选出所有变量中最小分类误差最小的变量作为切分 变量。
分类树：属性值为离散值。
分类树生成：（1）根据每一个属性的每一个取值，是否取该值将样本分成两类，计算基尼系数。选择基尼系数最小的特征和属性值，将样本分成两份。
（2）递归调用（1）直到无法分割。完成CART树生成。

决策树剪枝策略：
预剪枝（树提前停止生长）和后剪枝（完全生成以后减去一些子树提高预测准确率）
降低错误率剪枝：自下而上对每一个内部节点比较减去以其为叶节点和子树的准确率。如果减去准确率提高，则减去，依次类推知道准确率不在提高。
代价复杂度剪枝：从原始决策树T0开始生成一个子树序列{T0、T1、T2、...、Tn},其中Ti+1是从Ti总产生，Tn为根节点。每次均从Ti中 减去具有最小误差增长率的子树。然后通过 交叉验证比较序列中各子树的效果选择最优决策树。

追问

你说的很全面了，但是我的问题是每次递归调用的时候是不是用全部属性还是需要把本次用于分枝的属性给剔除掉呢？

Answer 2

cart树是不管是分类树还是回归树，都是二叉树。不管是离散属性还是连续属性。只要损失(回归树的损失是平方损失，分类树的损失是熵)能够继续减少，在从根节点开始到当前节点，即使是用过的属性是还可以继续用的。只是分裂点不一样。
c4.5离散特征多叉（离散特征在路径上只能使用1次）、连续特征二叉（连续特征在路径上能多次使用）
id3只处理离散特征，是棵多叉树

Answer 3

用过的分类属性是不能在用来分类的，假设：再用来分类的情况下，在数据很充分时，相当于把整个数据集合中的每一条信息用树结构表达出来。