上篇文章介绍了K-近邻的分类方法，这篇文章介绍另外一种分类的方法：决策树。和K-近邻不同，决策树的方法包括了一个训练的过程。通过这个训练过程，我们可以构造一棵决策树。然后我们可以使用这课决策树来对输入的样本进行分类。
直观的理解
假如我们现在需要对邮件进行分类，我们收集邮件的两个特征：①邮件的域名地址是否是myEmployer.com？②邮件中是否包含“曲棍球”这个单词。同时，我们希望把邮件分成三类：①无聊时需要阅读的邮件；②需要及时处理的朋友邮件；③无需阅读的垃圾邮件。现在通过训练，我们得到了一棵决策树，其结构如下：
分类的过程非常简单，首先看收到的邮件的域名是否是myEmployer.com? 如果是，那么就把它归为“无聊时需要阅读的邮件”；如果不是，那么再看邮件中是否包含“曲棍球”这个词。如果包含，那么把她归为“需要及时处理的朋友邮件”；否则，将其归为“无需阅读的垃圾邮件”。
构造决策树
从上面的叙述，我们可以看出，决策树分类的本质在于构造成一棵树，内节点由特征组成，而叶子节点由最终的分类结果组成。那么如何使用已有的训练样本构造决策树呢？
熵 在这之前，我们先来熟悉一个概念：熵。 详细的概念理解请参考知乎。简单来说，熵代表信息的混乱程度。越混乱，熵值就会越大。在未分类之前，训练集中的数据非常混乱，我们的目的是通过将训练集以某个特征分类，使得熵值慢慢减少(减少？对，是减少)，最终我们的训练集会变得越来越有序，并且所有的训练样本都分到它们本应在的类别。
所以说，构造决策树的过程，就是一个使得熵值逐渐减少的过程。具体的思路如下：
输入：训练集
输出：决策树
repeat:
寻找使得熵值下降最大的特征；
将训练集沿着这个特征进行划分；
until：
每个分支类别完全相同 OR 遍历完所有特征
代码实现
熵的代码实现 熵的计算公式如下：
其中，p(xi)表示在样本属于xi类的概率，-log2p(xi)表示样本属于xi类的信息量。
假设我们样本的格式由(n+1)维的向量组成，其中前n维表示数据的特征，最后的维度表示数据的类别。那么计算熵值的代码如下：
from math import log
import operator
def calcShannonEnt(dataset):
numEntries = len(dataset)
labelCounts = {}
shannonEnt = 0.0
for featVec in dataset:
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob*log(prob,2)
return shannonEnt
训练集的划分 接下来我们实现训练集的划分。
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
其中axis为欲分类的特征，value为该特征取的值。
小的例子 下面举一个小的例子，来看一下特征划分前后数据的熵值变化。数据如下：
|序号|不浮出水面是否可以生存|是否有脚蹼|属于鱼类|
|-|
|1|是|是|是|
|2|是|是|是|
|3|是|否|否|
|4|否|是|否|
|5|否|是|否|
下面的代码计算以第一个特征划分前后的熵值：
def createDataSet():
dataSet = [[1,1,'yes'], [1,1,'yes'], [1,0,'no'], [0,1,'no'], [0,1,'no']]
labels = ['no surfacing', 'flippers']
dataset,labels = createDataSet()
values = [example[0] for example in dataset]
uniqueValues = set(values)
newEntropy = 0.0
for value in uniqueValues:
subDataset = splitDataSet(dataset, 0, value)
prob = len(subDataset)/float(len(dataset))
newEntropy += prob*calcShannonEnt(subDataset)
oldEntropy = calcShannonEnt(dataset)
print 'before split: %f' %oldEntropy
print 'after split: %f' %newEntropy
输出的结果为：
现在我们已经知道如何依据一个特征来划分数据集及如何计算一个数据集的熵值，现在我们可以着手构造一棵决策树了。但在构造决策树之前，我们要明白：有时候我们并不能依据特征将所有的样本分开。如果特征已经使用完，样本还没有完全分开，这时候我们取大多数的标签，作为剩下样本的标签。具体的细节，在构造决策树的时候我会再说明。
构造决策树 从决策树的结构，我们很容易想到使用递归的算法来实现递归树。在这里，我们以字典的数据结构来存储一颗树。代码如下：
def createTree(dataSet, Labels):
#获取所有的类别标签
classlist = [example[-1] for example in dataSet]
#如果所有的数据都属于同一类，则不需要使用后面的特征来构造新的节点，决策树构造完成
if classlist.count(classlist[0]) == len(classlist):
return classlist[0]
#如果数据集中的特征已用完，将剩下样本中出现次数最大的标签，作为剩下所有样本的标签
if dataSet[0] == 1:
return majorityCnt[classlist]
#选择熵值变化最大的特征
bestFeat = chooseBestFeatureToSplit(dataSet)
#取得对应特征的标签
bestFeatLabel = Labels[bestFeat]
#构造对应特征的字典
myTree = {bestFeatLabel:{}}
#将对应的标签从标签数组中删除
labels = Labels[:]
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
其中majorityCnt函数的代码如下：
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]
其中，chooseBestFeatureToSplit的代码如下：
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)
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 bestFeat
至此，决策树我们已经构造完成了。使用上面的数据构造的决策树如下：
用决策树来分类
决策树构造完成之后，我们就可以进行分类了，分类的代码如下：
def classify(inputTree, featLabels, testVec):
firstStr = inputTree.keys()[0]
secondDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr)
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 storeTree(inputTree, filename):
import pickle
fw = open(filename, 'w')
pickle.dump(inputTree, fw)
fw.close()
def grabTree(filename):
import pickle
fr = open(filename)
return pickle.load(fr)
适用范围
我们可以看到，决策树的算法只能适用于离散的数据。
今天的算法分享就到这里，咱们下次再见~
