Decision Tree：ID3、C4.5

Decision Tree：ID3、C4.5

 

ID3(Iterative Dichotomiser 3)算法是判定树算法(Decision Tree Learning)的典型代表算法，由Ross Quinlan在1975年提出。ID3是作为C4.5的先驱，在Machine Learning和Natural Language Processing中使用广泛。该分类算法的核心是Entropy理论，属于数学的范畴。Entropy Theory是信息论中的名词，在上篇文章中http://isilic.iteye.com/blog/1841339有介绍，不过关于信息熵还有一些更深一些的东西。

信息熵

信息熵是指：一组数据所包含的信息量，使用概率来度量。数据包含的信息越有序，所包含的信息越低；数据包含的信息越杂，包含的信息越高。例如在极端情况下，如果数据中的信息都是0，或者都是1，那么熵值为0，因为你从这些数据中得不到任何信息，或者说这组数据给出的信息是确定的。如果数据时均匀分布，那么他的熵最大，因为你根据数据不能知晓那种情况发生的可能性比较大。

计算熵的公式为：

熵值和概率的关系如下，这个是二值情况下的概率与熵值关系，其中n=2：

实际上，信息熵表示的是信息的不确定性。当概率相同时，不确定性越大，因为所有的信息概率相同，你不能确定哪个信息出现的可能性更大；当某类别发生的概率为0或者1时，给出的结果是确定的(出现或者不出现、发生或者不发生)。这样的解释会不会更清楚点。

 

Information Gain(IG)，信息增益和信息熵描述的信息是一致的；描述的是对于数据集合S，将其按照其属性A切分后，获得的信息增益值。注意IG描述的是信息的增益值，当不确定性越大时，信息增益值应该是越小，反之亦然，是负相关的关系。信息增益的公式如下：

在ID3中，使用信息增益(IG)或者熵(Entropy)值来确定使用哪个属性进行判定属性，可以说是ID3算法的关键和精髓所在。ID3算法的伪码如下：

ID3算法的原理还是比较简单的，其理论基础是Entropy理论和Information Gain理论，只要深入理解了这个内容，ID3算法就不是问题。其实Machine Learning的基础是统计、概率、几何知识的考量，数学基础好的话，会在学习过程中感觉轻松些。

 

在Machine Learning in Action中有个章节是介绍ID3算法的，并且有完整的实现。我将代码拿过来，感兴趣的可以结合理论学习一下。 

from math import log
import operator

def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing','flippers']
    #change to discrete values
    return dataSet, labels

def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet: #the the number of unique elements and their occurance
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob,2) #log base 2
    return shannonEnt

def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]     #chop out axis used for splitting
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1      #the last column is used for the labels
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatures):        #iterate over all the features
        featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
        uniqueVals = set(featList)       #get a set of unique values
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy     #calculate the info gain; ie reduction in entropy
        if (infoGain > bestInfoGain):       #compare this to the best gain so far
            bestInfoGain = infoGain         #if better than current best, set to best
            bestFeature = i
    return bestFeature                      #returns an integer

def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if vote not in classCount.keys(): classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList):
        return classList[0]#stop splitting when all of the classes are equal
    if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]       #copy all of labels, so trees don't mess up existing labels
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree

def classify(inputTree,featLabels,testVec):
    firstStr = inputTree.keys()[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    key = testVec[featIndex]
    valueOfFeat = secondDict[key]
    if isinstance(valueOfFeat, dict):
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else: classLabel = valueOfFeat
    return classLabel

def storeTree(inputTree,filename):
    import pickle
    fw = open(filename,'w')
    pickle.dump(inputTree,fw)
    fw.close()

def grabTree(filename):
    import pickle
    fr = open(filename)
    return pickle.load(fr)

 代码还算清晰，chooseBestFeatureToSplit和calcShannonEnt这两个方法是ID3算法的核心，请仔细阅读代码，确定自己真正理解了熵理论和信息增益理论。

  

ID3算法存在的缺点： 

1：ID3算法在选择根节点和内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多是属性在有些情况下这类属性可能不会提供太多有价值的信息。 

2：ID3算法只能对描述属性为离散型属性的数据集构造决策树 

 

ID3算法的局限是它的属性只能取离散值,为了使决策树能应用于连续属性值情况，Quinlan给出了ID3的一个扩展算法：即C4.5算法。C4.5算法是ID3的改进，其中离散属性值的选择依据同ID3；它对于实值变量的处理采用多重分支。C4.5算法能实现基于规则的剪枝。因为算法生成的每个叶子都和一条规则相关联，这个规则可以从树的根节点直到叶子节点的路径上以逻辑合取式的形式读出。

 

C4.5算法之所以是最常用的决策树算法，是因为它继承了ID3算法的所有优点并对ID3算的进行了改进和补充。C4.5算法采用信息增益率作为选择分支属性的标准，并克服了ID3算法中信息增益选择属性时偏向选择取值多的属性的不足，并能够完成对连续属性离散化是处理；还能够对不完整数据进行处理。C4.5算法属于基于信息论Information Theory的方法，以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳和分类。 

C4.5算法主要做出了以下方面的改进 

1：可以处理连续数值型属性 

对于离散值，C4.5和ID3的处理方法相同，对于某个属性的值连续时，假设这这个节点上的数据集合样本为total，C4.5算法进行如下处理： 

• 将样本数据该属性A上的具体数值按照升序排列，得到属性序列值：{A1,A2,A3,...,Atotal}
• 在上一步生成的序列值中生成total-1个分割点。第i个分割点的取值为Ai和Ai+1的均值，每个分割点都将属性序列划分为两个子集。
• 计算每个分割点的信息增益(Information Gain),得到total-1个信息增益。
• 对分裂点的信息增益进行修正：减去log2(N-1)/|D|，其中N为可能的分裂点个数，D为数据集合大小。
• 选择修正后的信息增益值最大的分类点作为该属性的最佳分类点
• 计算最佳分裂点的信息增益率(Gain Ratio)作为该属性的Gain Ratio
• 选择Gain Ratio最大的属性作为分类属性。

 其中第4、5步骤Quinlan在93年的的算法中没有体现，在96年发表文章对该算法进行改进，改进的论文可以参考这里：http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/quinlan96a.pdf。 

 

2：用信息增益率(Information Gain Ratio)来选择属性 

克服了用信息增益来选择属性时偏向选择值多的属性的不足。信息增益率定义为： 

其中Gain(S,A)和ID3算法中的信息增益计算相同，而SplitInfo(S,A)代表了按照属性A分裂样本集合S的广度和均匀性。

其中Si表示根据属性A分割S而成的样本子集。 

 

3：后剪枝策略 

Decision Tree很容易产生Overfitting，剪枝能够避免树高度无限制增长，避免过度拟合数据。剪枝算法比较复杂，我自己还没有学习清楚，希望大家能提供学习这个剪枝策略方法的建议。 

 

4：缺失值处理 

对于某些采样数据，可能会缺少属性值。在这种情况下，处理缺少属性值的通常做法是赋予该属性的常见值，或者属性均值。另外一种比较好的方法是为该属性的每个可能值赋予一个概率，即将该属性以概率形式赋值。例如给定Boolean属性B，已知采样数据有12个B=0和88个B=1实例，那么在赋值过程中，B属性的缺失值被赋值为B(0)=0.12、B(1)=0.88；所以属性B的缺失值以12%概率被分到False的分支，以88%概率被分到True的分支。这种处理的目的是计算信息增益，使得这种属性值缺失的样本也能处理。

 

我们看下C4.5算法的伪码： 

Function C4.5(R:包含连续属性的无类别属性集合,C:类别属性,S:训练集)  
Begin  
   If S为空,返回一个值为Failure的单个节点;  
   If S是由相同类别属性值的记录组成,  
      返回一个带有该值的单个节点;  
   If R为空,则返回一个单节点,其值为在S的记录中找出的频率最高的类别属性值;  
   [注意未出现错误则意味着是不适合分类的记录]；  
  For 所有的属性R(Ri) Do  
        If 属性Ri为连续属性，则  
        Begin  
           sort(Ri属性值)
           将Ri的最小值赋给A1：  
        	 将Ri的最大值赋给Am；  
           For j From 1 To m-1 Do Aj=(A1+Aj+1)/2;  
           将Ri点的基于Aj(1<=j<=m-1划分的最大信息增益属性(Ri,S)赋给A；  
        End；  
  将R中属性之间具有最大信息增益的属性(D,S)赋给D;  
  将属性D的值赋给{dj/j=1,2...m}；  
  将分别由对应于D的值为dj的记录组成的S的子集赋给{sj/j=1,2...m};  
  返回一棵树，其根标记为D;树枝标记为d1,d2...dm;  
  再分别构造以下树:  
  C4.5(R-{D},C,S1),C4.5(R-{D},C,S2)...C4.5(R-{D},C,Sm);  
End C4.5

 该算法流程是我从网上移过来的，对于其中和本文描述不一致的地方做了修改。原文参考这里：http://blog.sina.com.cn/s/blog_73621a3201017g7k.html

C4.5的主要点在于对于ID3的改进，可以说上面提到的四点对于Decision Tree算法来说是非常关键的，理解了这几个改进点就算是掌握了C4.5算法的根本。

 

C4.5的缺点：

1：算法低效，在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效

2：内存受限，适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

 

在weka开源软件中有个weka.classifiers.trees.J48实现了C4.5算法，可以结合该代码学习理论知识。

 

最后提示下C5.0算法，C5.0算法是在C4.5算法基础上的改进，wiki上表示该算法应该归属于商业应用，所以没有C4.5讨论广泛。相比较于C4.5，C5.0算法的改进点在于：

1：速度，C5.0有好几个数量级别上的速度提升

2：内存使用，比C4.5使用更加有效

3：生成Decision Tree更小(Occam's Razor)，能避免过度拟合

4：支持Boosting

5：支持权重，对于不同的样本赋予不同的权重值

6：Winnowing：支持自动去除没有帮助的属性

这个是作者的声明。尤其是前两点，刚好是克服了C4.5算法的劣势，是C4.5算法的巨大提升，算法源码在http://rulequest.com/download.html这里有下载，大家可以学习下作者声称的优势都是怎么实现的。在这里http://www.rulequest.com/see5-comparison.html有C5.0和C4.5的比较，大家也可以看下，从文章来看，C5.0确实是在很多方面都超过了C4.5。

 

本文关于Decision Tree的学习到此，本文介绍了最为简单和基础的ID3算法；随后学习了C4.5相比于ID3的优势及实现思路；最后比较了C5.0的改进；对于Decision Tree算法有了基本的认识，为后面学习Decision Tree算法提供了良好的基础。