概述

算法原理

1.首先，找到能够最好地将数据集分裂的特性（feature，或叫属性），

2.然后，对分裂后的子集执行同样的操作，

3.直到没有属性能够继续分裂或子集中的实例都属于同一个类为止。

采用熵（所有列别所有可能值包含的信息的期望值）来度量数据集的信息量，信息增益等于分裂前的熵减去分裂后的熵。

数据类型

数值型和标称型，树构造算法只适用于标称型数据，因此数据值数据必须离散化。

优点

计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。

缺点

可能会产生过度匹配问题。

香农熵(Shannon entropy)

该算法最关键的一环就是如何找到最好的分裂特性。利用信息论（information theory）可获得分裂前和分裂后的信息。分裂前和分裂后信息发生的变化被称作信息增益（information gain）。通过对每个特性进行分裂测试，我们可以知道提供最大信息增益的特性。能够提供最大信息增益的分裂就是我们想要的分裂。

若要计算信息增益，我们需要知道如何量化度量分裂前和分裂后的信息。熵（entropy，拼音：shang）是由鲁道夫·克劳修斯（Rudolf Clausius）提出的度量体系混乱程度的量。香浓（Shannon）将熵的概念引入到信息论中来。

在信息论中，熵被用来衡量一个随机变量出现的期望值。假设一个随机变量X的值域是{x1, x2......, xn}，则该随机变量的熵值H定义为：

其中，E表示期望函数，I(X)表示X的信息量，也是随机变量。I(xi)是值xi的信息定义。I(xi)的公式如下：

如果用p表示X的概率质量函数（probability mass function），则熵的公式可以表示为：

b是对数的底，可以是2、e、10。当b=2时，熵的单位是bit；当b=e时，熵的单位是nat；当b=10时，熵的单位是dit。

由以上公式可知，当随机变量只含有一个值时，那么出现该值得概率就是100%，也就是p = 1，log p = 0。熵值就是0。当随机变量含有多个值时，熵值就会增大。

代码实现

以下代码采用python实现使用信息增益获取最优分裂特性的决策树算法：

#!/usr/bin/env python
# _*_ coding: utf-8 _*_

from math import log
import operator

'''
计算数据集的香浓熵

基本思想：
首先计算数据集中各个类的概率，
然后对各个类的概率计算以2为底的对数得到该类的信息量，
最后让各个类的概率乘以对应的对数并相减得到数据集的熵。
'''
def calcShannonEnt(dataSet):
    entries_count = len(dataSet)
    labelCounts={}
    for row in dataSet:
        label = row[-1]
        if(label not in labelCounts.keys()):
            labelCounts[label] = 0
        labelCounts[label] += 1
    entropy=0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/entries_count
        entropy -= prob * log(prob, 2)
    return entropy

'''
分裂数据集

基本思想：
迭代数据集的每个实例，
当实例的指定属性的值等于指定值时，获取该实例的其他属性的值构成新实例，
将新实例添加到新的数据集中。
'''
def splitDataSet(dataSet, axis, value):
    splited_dataSets = []
    for row in dataSet:
        if row[axis] == value:
            reducedRow = row[:axis]
            reducedRow.extend(row[axis+1:])
            splited_dataSets.append(reducedRow)
    return splited_dataSets

'''
选择指定数据集用于分裂的最好的特性（属性）

基本思想：
对数据集中的每个特性进行分裂，并计算分裂后的信息增益，
选择产生最大信息增益的特性作为最优特性。
'''
def chooseBestFeatureToSplit(dataSet):
    features_count = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(features_count):
        featureVals = [row[i] for row in dataSet]
        distinctVals = set(featureVals)
        newEntropy = 0.0
        for val in distinctVals:
            subDataSet = splitDataSet(dataSet, i, val)
            prob = len(subDataSet) / float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

'''
当所有属性都参与分裂，而子集的实例仍属于多个类时，则采用占比最大的类。
'''
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):
    featureLabels = labels[:]
    classList = [row[-1] for row in dataSet]
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    bestFeatureIndex = chooseBestFeatureToSplit(dataSet)
    bestFeatureLabel = featureLabels[bestFeatureIndex]
    myTree = {bestFeatureLabel:{}}
    del(featureLabels[bestFeatureIndex])
    featureVals = [row[bestFeatureIndex] for row in dataSet]
    distinctVals = set(featureVals)
    for value in distinctVals:
        subFeatureLabels = featureLabels[:]
        myTree[bestFeatureLabel][value] = createTree(splitDataSet(dataSet, bestFeatureIndex, value), subFeatureLabels)
    return myTree

'''
根据树结构对测试向量进行分类
'''
def classify(inputTree, featLabels, testVec):
    firstStr = inputTree.keys()[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    classLabel = "unknown"
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            if type(secondDict[key]).__name__ == 'dict':
                classLabel = classify(secondDict[key], featLabels, testVec)
            else:
                classLabel = secondDict[key]
    return classLabel

'''
创建测试数据集
'''
def createDataSet():
    dataSet = [
        [1,1,'yes'],
        [1,1,'yes'],
        [1,0,'no'],
        [0,1,'no'],
        [0,1,'no']
        ]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels