步步为营KDD：决策树算法

概述

算法原理

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 logimport 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