决策树算法

一、基本原理

  决策树类似于二叉树结构，按照数据集中的特征依次对其分类，直到所有的数据分类完毕。
  首先在已知数据集上确定哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征，划分出最好的结果，必须要评估每个特征。此时，原始数据集就会被划分为几个子数据集分支。如果某个分支下的数据都属于同一类型，即该子集中的所有数据的特性均相同，则无需进一步对数据集进行划分。否则需要重复划分数据子集，直到所有具有相同类型的数据均在一个数据子集内。
  构造决策树最关键的是如何找到决定性的特征。是否划分的原则为子数据集中的所有数据是否均具有相同的特征。

二、算法实现

  伪代码函数decisionTree()：
  检测数据集中每个子项是否属于同一类：
  IF so
   return 类标签
  Else
   寻找划分数据集的最好特性
   划分数据集
   创建分支节点
    for 每个划分的子集
     调用函数decisionTree()并将结果增加到分支节点中
   return 分支节点

信息增益

  在划分数据集之前之后信息发生的变化称为信息增益。获得信息增益最高的特征就是最好的分类选择。计算信息增益常用的是香农熵(熵)。熵的定义为信息的期望值，表示数据的无序性。其计算公式为：

python程序：

from math import log
def calcShannonEnt(dataSet):
    numEntries = len(dataSet)  # 计算总数
    labelCounts = {}
    for featVec in dataSet:
        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)   # 带入公式求和
    return shannonEnt

程序说明：
  函数的输入为原始数据集，其中最后一列为分类标签。首先计算数据集的总个数，其次将数据集按照分类标签分类，并统计每个子类的总数。最后根据熵的计算公式，依次对每类的信息增益进行求和。

例：有一组已知分类标签的数据集，计算其香农熵。

  利用python创建数据集：

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

  根据公式其香农熵为：

  数据集一共有5组数据，其中分类标签为’yes’的有3个，分类标签为’no’的有2个。熵越高，则混合的数据也越多。

划分数据集

  除了计算整体数据的信息熵，还需要计算划分数据集的熵。对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。其计算公式为：

  首先按照每个特征划分数据集：
python程序：

def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]  # 截取之前的数据到该特征
            reducedFeatVec.extend(featVec[axis + 1:]) # 将该特征后的数据加入到列表中
            retDataSet.append(reducedFeatVec)
    return retDataSet

程序说明：
  函数的三个输入分别为：待划分的数据集，数据集中的某个特征，该特征对应的特征值。例如splitDataSet(dataSet, 0, 1)表示划分出数据集dataSet中第0个特征为1的数据，即第1个特征为1的数据，python的列表索引从0开始。(dataSet即createDataSet()函数生成的数据集)
  首先利用for循环遍历整个数据集，当对应的特征等于给定的值后，先将该特征之前的数据添加到列表中，然后将之后的数据添加到列表中。
  splitDataSet(dataSet, 0, 1)的返回值为：[[1,’yes’], [1, ‘yes’], [0, ‘no’]]

  对每个特征划分完成后，需要计算每个数据子集的熵，从而选择最好的数据集划分方式。
python程序：

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1  # 减去数据集中的标签
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]  # 获得数据集中某一列的值
        uniqueVals = set(featList)  # set():使数据为不重复的序列
        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
        # 计算最大的熵，作为划分数据集的方式
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

程序说明：
  函数首先计算总的数据集的熵，然后将最好的熵和特征初始化为0和-1。然后需要将划分数据集，计算每个子集的熵，但首先要知道数据集中每个特征有多少特征值。函数首先获得每一个特征的所有特征值，然后利用set()将重复的值去掉。featList返回的就是每个特征对的所有特征值。createDataSet()生成的数据集的featList为：[1, 1, 1, 0, 0]和[1, 1, 0, 1, 1]。最后，对于划分好的每个数据集依次计算熵，并选择最大的熵作为最好的划分方式。

  H(1)、H(2)分别表示第1，2种分类结果，数据集中特征0，即第1个特征的分类结果为1和0。其中结果为1的数据集为：[[1,’yes’], [1, ‘yes’], [0, ‘no’]]，’yes’有2个，’no’有1个；结果为0的数据集为：[[1, ‘no’],[1, ‘no’]],’yes’有0个，’no’有2个。特征1的计算类似。

构建决策树

  划分好一次数据集之后，数据将被向下传递到下一个节点，然后在此节点上做进一步的划分。因此可用递归的原则处理原始数据集。
  递归的结束条件为：遍历完原始数据集的所有数据或者每个子集的数据特征均相同。

python程序实现：

def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    # 第一种终止条件
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 第二种终止条件
    if len(dataSet[0]) == 1:
        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[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
        # 列表的值为划分后的数据集
    return myTree

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]

程序说明：
  函数的输入参数为原始数据集和分类标签。首先判断该数据集是否能进行划分。其递归结束的条件有2个，一个是划分后的数据子集的所有特征属性均相同。即数据集中第一个特征的个数即该数据集的总特征个数。另一个是当遍历完所有的原始数据集的特征之后，仍然存在没有划分成包含唯一类别的子类，这时候采用出现出现次数最多的类别作为其返回值。然后计算数据集中的熵并选择最好的分类特征，再将此特征删除，得到数据子集，再依次对子集进行递归处理，直到分类完成。
  该程序最终的结果为：{‘no surfacing’: {0: ‘no’, 1: {‘flippers’: {0: ‘no’, 1: ‘yes’}}}}。即首先根据“不浮在水面是否可以生存”的特征分成“0”(否)和“1”(是)两类。其中“0”这一类的子数据集的特征均相同，不需要在划分。而“1”这一类再按照“是否有脚蹼”继续分类。

三、感悟

3.1 python知识

(1)extend和append的区别：
extend:将一个序列添加到列表中；
append：将一个对象添加到列表中；
即append是将要添加的数据作为一个新的对象添加到列表中，不属于原来的列表，而extend添加后的数据仍然属于原来的列表。
例:a = [1, 2], b = [3]
a.extend(b) : [1, 2, 3]
a.append(b) : [1, 3, [3]]
(2)set():使数据为不重复的序列

3.2 算法

(1)决策树属于有监督的算法。因为其原始数据集的分类标签是已知的。
(2)决策树类似于二叉数，将原始数据集按照每个特征的标签依次划分，直到所有的数据划分完成。
(3)构建决策树主要分为两步，首先选择最好的划分类别，将原始数据集分成子数据集，其次判断递归的结束条件是否满足，即需不需要继续往下划分。
(4)选择最好的划分类别时，常用的判断依据是计算每个特征的子数据集的熵，熵代表的是数据集的混乱程度，数据越混乱，熵越高，其分类标准也越好。