机器学习算法之决策树详解

决策树：决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy(熵) = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法得出熵，这一度量是基于信息学理论中熵的概念。决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。决策树是一种十分常用的分类方法，是一种监督学习。

判断是否适合外出的决策树

决策树的构造

在构造决策树时，我们需要解决的第一个问题就是，当前数据集上那个特征在划分数据分类时起决定性的作用。为了找到决定性的特征，划分出最好的结果，我们必须评估每个特征。完成测试之后，原始数据集就会被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型，则已正确划分数据类型，如过不同，则需重复划分数据子集。划分数据子集的算法和原始数据相同，直到所有的节点都是同一类型为止。

---

信息增益

上面说到我们需要找到决定性的特征来划分出最好的结果，这也是决策树核心问题所在，那怎么确定这个最优特征呢？我们常用的方法就是用信息论中的信息增益来确定这个特征。

在划分数据集之前之后信息发生的变化叫做信息增益，知道如何计算信息增益，获得计算增益最高的特征就是最好的选择。

在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越有序，信息熵就越低，反之一个系统越混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

熵定义为信息的期望值，既然是要算期望，就得先知道信息的定义。如果待分类的事件可能划分在多个分类之中，则事件(X_i)的信息定义为：

info(x_i) = -log₂p(x_i)

其中p(x_i)是选择该类别的概率。
为了计算熵，需要计算出信息的期望，即：(这里要吐槽一下简书，不支持MathJax，所以只能找图片替代公式)

信息期望

接下来以气象数据为例子，来说明决策树的构建过程：

outlook	temperature	humidity	windy	play
sunny	hot	high	FALSE	no
sunny	hot	high	TRUE	no
overcast	hot	high	FALSE	yes
rainy	mild	high	FALSE	yes
rainy	cool	normal	FALSE	yes
rainy	cool	normal	TRUE	no
overcast	cool	normal	TRUE	yes
sunny	mild	high	FALSE	no
sunny	cool	normal	FALSE	yes
rainy	mild	normal	FALSE	yes
sunny	mild	normal	TRUE	yes
overcast	mild	high	TRUE	yes
overcast	hot	normal	FALSE	yes
rainy	mild	high	TRUE	no

在没有使用特征划分类别的情况下，有9个yes和5个no，当前的熵为：

计算熵

假设我们以 outlook 特征划分数据集，对该特征每项指标分别统计：在不同的取值下 play 和 no play 的次数：

outlook	yes	no
sunny	2	3
overcast	4	0
rainy	3	2

此时各分支的熵计算如下：

各分支的熵
因此如果用特征outlook来划分数据集的话，总的熵为：
outlook划分后的总熵
那么最终得到特征属性outlook带来的信息增益为：IG(outlook)=0.940−0.694=0.246，然后用同样的方法，可以分别求出temperature，humidity，windy的信息增益。IG(temperature)=0.029，IG(humidity)=0.152，IG(windy)=0.048。可以得出使用outlook特征所带来的信息增益最大，所以应该首先选择outlook来划分数据集。然后继续划分各个分支的数据集，知道每个分支下的所有实例都具有相同的分类。最终构造出决策树：
最终的决策树(图片源自网络)

---

决策树代码实现

1. 计算香农熵

# 计算香农熵
def calShannonEntropy(dataSet):
    numEntries = len(dataSet)   # 数据总数
    labelCounts = {}
    for featureVect in dataSet:
        currentLabel = featureVect[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        probability = float(labelCounts[key]) / numEntries
        shannonEnt -= probability * log(probability, 2)
    return shannonEnt

2. 按照给定的特征划分数据集

# 划分数据集
def splitDataSet(dataSet, featureIndex, featureValue):
    newDataSet = []
    for featVec in dataSet:
        if featVec[featureIndex] == featureValue:
            reducedFeatVec = featVec[:featureIndex]
            reducedFeatVec.extend(featVec[featureIndex+1:])
            newDataSet.append(reducedFeatVec)
    return newDataSet

3. 选择最佳特征值划分数据集

def chooseBestFeatureToSplit(dataSet):
    numFeature = len(dataSet[0]) - 1
    baseEntropy = calShannonEntropy(dataSet)
    bestFeature = -1; bestInfoGain = 0
    for i in range(numFeature):
        featList = [entry[i] for entry in dataSet]  # 取出每一种属性
        uniqueValue = set(featList)  # 得到该属性有哪些值(用集合的方法去掉重复值)
        newEntropy = 0.0
        for value in uniqueValue:
            subDataSet = splitDataSet(dataSet, i, value)
            probility = len(subDataSet) / float(len(dataSet))
            newEntropy += probility * calShannonEntropy(subDataSet)
        infoGain = baseEntropy - newEntropy
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

4. 投票决定不确定结果
如果数据集已经处理了所有属性，但是类标签依然不是唯一的，通常我们才有多数表决的方法决定该叶子节点的分类。

# 找出票数最多的标签
def majorityVote(classList):
    classCount = {}
    for vote in classList:
        if vote not in classList.keys():
            classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reversed=True)
    return sortedClassCount[0][0]

5. 创建决策树

def createTree(dataset, labels):
    # 取出位于最后一列的类别标签
    classList = [label[-1] for label in dataset]
    if classList.count(classList[0]) == len(classList):  # 类别完全相同时，停止划分
        return classList[0]  # 返回唯一特征值
    if len(dataset[0]) == 1:  # 已经遍历完所有特征，只剩最后一列类别标签
        return majorityVote(classList)  # 返回票数最多的类标签

    # 开始划分
    # 先选取最好的划分特征值
    bestFeature = chooseBestFeatureToSplit(dataset)
    bestFeatureLabel = labels[bestFeature]

    # 初始化树
    myTree = {bestFeatureLabel: {}}
    subLabels = labels[:]
    del subLabels[bestFeature]
    
    # 递归构建决策树
    featList = [entry[bestFeature] for entry in dataset]
    uniqueValues = set(featList)
    for value in uniqueValues:
        myTree[bestFeatureLabel][value] = createTree(splitDataSet(dataset, bestFeature, value), subLabels)
    return myTree

6. 使用决策树执行分类

# 使用决策树执行分类
def classify(inputTree, featLabels, testVec):
    # 取出根节点,python2直接写成inputTree.keys()[0]
    firstStr = list(inputTree.keys())[0]
    # 找到根节点下面的分支(该分类特征的分支)
    childDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)

    # 遍历分类特征的所有取值
    for key in childDict.keys():
        # 如果测试向量的该类值等于分类特征的第key个节点
        if testVec[featIndex] == key:
            # 判断该节点是否为字典类型
            if type(childDict[key]).__name__ == 'dict':
                # 是字典类型，继续遍历
                classLabel = classify(childDict[key], featLabels, testVec)
            else:
                # 不是字典，返回最终结果
                classLabel = childDict[key]
    return classLabel

7. 存储决策树
构建决策树是非常耗时的任务，即使很小的数据集，也要花费几秒的时间来构建决策树，这样显然耗费计算时间。所以，我们可以将构建好的决策树保存在磁盘中，这样当我们需要的时候，再从磁盘中读取出来使用即可。为了解决这个问题，可以使用pickle序列化对象，任何对象都可以执行序列化操作，字典对象也不例外。