决策树概论

决策树主要是利用了二分法思想和信息论中关于信息增益的定义，并利用递归的方式来建立一颗决策树。

二分法

二分法的主要思想就是分而治之，书上有个例子举得很好，举行一个游戏，参与游戏的一方在脑海里想一个事物，其他参与者来向他提问，回答的答案也只能是对或者错，通过这种方式来不断逼近问题。

信息增益

这可以说是整个算法的关键之处，定义为： **H(X)=−∑p(x)logp(x)** 通过选取特征，来使信息增益最大，来完成对特征的划分。也就是要历遍整个特征集，找出一个没有被化走的特征，使以这个特征做二分划分时的信息增益最大。 下面给出计算信息期望值的代码 #引入必要的函数库 from math import log; import operator; #定义计算信息期望值函数 def calShannonEnt(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;

可以来测试一下，先定义创建数据集的函数

#这里0和1为特征，yes和no为标签 def creatDataSet(): dataSet = [[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]; return dataSet;

运行一下

>>> calShannonEnt(md) 0.9709505944546686

若增加最后一列的标签值的元素，会看到信息值的增加。

之前看到这里有点不解，为什么这个计算信息增益的函数仅仅与最后一列有关呢？ 后来看到后面，这整个函数是假设了每个数据集的最后一列即为当前实例的类别标签。若这里看不明白，可以继续往下看，下面讲解选取最好特征时会讲解这样划分的意义。

既然是要划分数据集，那还是要定义一个划分数据集的函数

#这个不仅是依据特征划分了数据，并且在已知数据集中去掉了该特征 def splitDataSet(dataSet, axis, value): retDataSet = []; for featVec in dataSet: if featVec[axis] == value: reducedFeatVec = featVec[:axis]; #extend是仅仅把元素复制进去 reducedFeatVec.extend(featVec[axis+1:]); #append会把对象追加进去 retDataSet.append(reducedFeatVec); return retDataSet

下面可以说是这个算法的关键了，就是选择最好的数据集的划分方式，其基本思想是：

计算不划分任何数据集的基准信息值（以最后一列为类别）选取第i列特征 以第i列特征的第j个值来划分数据集计算有第j个值的信息值（不重复计算）计算没有第j个值的信息值计算二者的加权信息值重复第一步，直到历遍完全部第j列的值计算第i列特征的信息值，并且保存其大者和其对于的index重复第二步，知道遍历完所有的列特征

以上就是这个选取最好的特征的伪代码，下面给出代码：

def chooseBestFeatureToSplit(dataSet): #获得除了最后一个特征值之外的特征总数 numFeature = len(dataSet[0]) - 1 #计算基准的熵 baseEntropy = calShannonEnt(dataSet); #最佳信息增益 bestInfoGain = 0.0; bestFeature = -1; for i in range(numFeature): 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 * calShannonEnt(subDataSet); infoGain = baseEntropy - newEntropy; if(infoGain > bestInfoGain): bestInfoGain = infoGain; bestFeature = i; return bestFeature;

讲了这么多，下面来试一试我们这个求得最有价值特征的函数作用吧

>>> my [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

这个是我们之前的数据集

>>> chooseBestFeatureToSplit(my) 0

运行完之后可以看出来，0索引位置的特征是最值得分割的，我们看看之前的数据集，若是以第一个（即索引0）位置来分割数据集，分成的两类，类别‘yes’和‘no’的一致性是最高的。

递归建立决策树

这个思路太牛，伪代码如下

递归建立决策树：

得到原始数据集若原始数据集所有的标识都是同一类的，结束函数若原始数据集除了标识没有其他特征，结束函数基于最好属性值划分数据集对于每一个划分的数据集再递归建立数据集

没想到递归还可以这么用！！ 下面给出具体代码

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] #建立一个有着dict的dict myTree = {bestFeatLabel:{}} #由于分离了特征，因此要对应的删除相应的label 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(classList)的作用是：当已经没有了特征时，但是数据集里面的标识并不是同一个，那么我们就要投票，让这个数据里面最多的标识作为这整个数据集的标识，代码如下

def majorityCnt(classList): classCount = {}; for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0; classCount[vote] += 1; sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True); return sortedClassCount[0][0];

好啦，现在我们就写完了我们的代码，来测试一下吧！

>>> mydata,label = creatDataSet(); >>> mytree = createTree(mydata,label) >>> mytree {'a': {0: 'no', 1: {'b': {0: 'no', 1: 'yes'}}}}

这个就是我们形成的决策树，我们并没有去人为的筛选特征，而是靠程序依据信息量来化为最值的特征，完美！！ 但是书上说决策树的方法会陷入过拟合的困境，目前还没有体会过所以不是很了解。