决策树算法 -- ID3

ID3 算法是决策树算法中最简单的一种,它使用信息增益作为判断指标。

决策树分类法是一种简单但却广泛使用的分类技术。它相较于kNN算法,能够展示给我们更多关于平均实例样本和典型实力样本的特征。决策树是一种使用概率测量方法处理分类问题的算法。

如何建立决策树

在原则上,对于一个给定的数据集,我们所可以构造的决策树的数目达到了指数级。因此,找到一个最佳决策树在计算上是不可行的。但尽管如此,人们还是找到了一些方法,去寻找具有一定的准确率的次最优决策树。我们采取贪心的策略,在每一次选择划分数据的属性时,选择局部最优的属性来构造决策。这就是Hunt算法。Hunt算法是一种通过将训练集划分成子集的一种以递归方法建立决策树的算法。

ID3算法的概述

对于一个决策树算法最关键的一点,就是如何选择特征作为划分数据集的标准。ID3算法就是一个选择信息增益作为其划分依据的算法。它选择信息增益最大的特征来对数据集进行划分。 还有一点ID3算法需要解决的就是如何判定划分的结束。这有两种情况,一种是划分出来的所有类属于同一个类。第二种情况,便是没有属性可以用来划分。

划分数据的依据

ID3算法是依靠信息增益作为衡量标准的决策树算法。

信息熵(Entropy)

熵的概念主要是指信息的混乱程度,变量的不确定性越大,熵的值也就越大,熵的公式可以表示为:

$$Entropy(t): -\sum_{i=0}^{c-1} p(i|t) log_2p(i|t)$$

信息增益(Information gain)

信息增益指的是划分前后熵的变化,可以用下面的公式表示:

$$ InfoGain: I(parent) - \sum_{j =1}^{k} \frac{N(v_j)}{N} I(v_j)$$

其中k表示划分后所具有的特征数目,N表示条目数量。I是熵。

ID3算法实现

计算熵

首先统计出有多少个特征,然后计算出每个特征的概率,并按照计算熵的公式计算。

def calcEnt(dataSet):
    numEntries: len(dataSet)
    labelsCount: {} 
    #计算每个label对应的条目数量
    for featureVec in dataSet:
        currentLable: featureVec[-1]
        labelsCount[currentLable]: labelsCount.get(currentLable, 0) + 1
    ent: 0.0
    # 计算熵
    for key in labelsCount:
        prob: labelsCount.get(key) / float(numEntries)
        ent -= prob * log(prob, 2)
    return ent

划分数据集

根据输入的特征类别和该特征的值从数据集划分出一个子数据集。

def splitDataSet(dataSet, axis, value):
    retDataSet: []
    for data in dataSet:
        if data[axis] == value:
            # 将符合值且去除axis的特征加入到返回的List中
            reducedFeature: data[:axis]
            reducedFeature.extend(data[axis + 1:])
            retDataSet.append(reducedFeature)
    return retDataSet

选择信息增益最大的划分特征

从数据集中选择出当前最优的划分特征。根据信息增益的计算公式。

def chooseBestFeatureToSplit(dataSet):
'''
return the index of the best feature
'''
numFeatures: len(dataSet[0]) - 1
numDataSet: len(dataSet)
# 计算未划分时的熵
baseEntropy: calcEnt(dataSet)
bestInoGain: 0.0
bestFeature: 0.0
for i in range(numFeatures):
    # 得到第i个特征对应的值们
    valsList: [data[i] for data in dataSet]
    uniqueVals: set(valsList)
    newEntropy: 0.0
    # 计算每个值情况下的熵以及该情况发生的概率
    for val in uniqueVals:
        subDataSet: splitDataSet(dataSet, i, val)
        prob: len(subDataSet) / float(numDataSet)
        newEntropy += prob * calcEnt(subDataSet)
    infoGain: float(baseEntropy - newEntropy)
    if(infoGain > bestInoGain):
        bestInoGain: infoGain
        bestFeature: i
return bestFeatur

选择最多的类别

如上文所述,我们有两种不同的结束判定情况。 这里我们介绍的是当数据集中没有可划分的特征,但是留下来了不同的类。我们为了输出方便,从中选择数目最多的类输出

def majorityCnt(classList):
    classCount: {}
    for vec in classList:
        classCount[vec]: classCount.get(vec, 0) + 1
    sortedClassCount: sorted(
        classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

构造树

当我们完成前面那些构造树的函数后,我们便可以正式构造我们的函数。这是一个递归算法。

def createTree(dataSet, labels):
'''
label 用于辅助构造树,提供特征的名字
'''
    # 每个数据对应的类别
    classList: [subData[-1] for subData in dataSet]
    # 结束情况一 只有同一类的数据
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 结束情况二 没有可以划分的特征
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    # 选择最佳的划分特征
    bestFeature: chooseBestFeatureToSplit(dataSet)
    bestFeatureLabel: labels[bestFeature]
    myTree: {bestFeatureLabel: {}}
    # 删除已被选择的特征
    del(labels[bestFeature])
    # 得到用于划分的特征对应的值们
    featureVals: [example[bestFeature] for example in dataSet]
    uniqueVals: set(featureVals)
    # 对每一个值 递归调用createTree,来继续划分数据集
    for values in uniqueVals:
        # 赋值给subLabels,而不是引用
        subLabels: labels[:]
        myTree[bestFeatureLabel][values]: createTree(
            splitDataSet(dataSet, bestFeature, values), subLabels)
    return myTree

分类

当构造完树后,我们就能用树来进行分类。这里的inputree参数便是我们前面构造的树。

def classify(inputTree, featureLabels, testVec):
    firstLabel: list(inputTree.keys())[0]
    secondTree: inputTree.get(firstLabel)   # seconTree 就是firstLabel对应的value
    featureIndex: featureLabels.index(firstLabel)
    classLabel: ''
    for key in secondTree:

        if testVec[featureIndex] == key:
            if type(secondTree[key]).__name__ == 'dict':
                classLabel: classify(secondTree[key], featureLabels, testVec)
            else:
                classLabel: secondTree[key]
    return classLabel