决策树

算法概述：将原始数据集根据决定性特征划分为几个数据子集，这些数据子集会分布在第一个决策点的所有分支上，如果某个分支下的数据属于同一类型，则表示到达终止模块，可以得到结论，无需进一步对数据集进行分割；如果子集内的数据不属于同一类型，则需重复划分数据子集，直到所有具有相同类型的数据均在一个数据子集内。但是应该怎样划分数据呢，显然是根据决定性特征，这里引进一个度量标准--信息增益（划分数据集之前之后信息发生的变化），我们可以计算每个特征值划分划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

3.1.1计算熵

熵定义为信息的期望。

如果待分类的事务可能划分在多个分类之中，则符号xi的信息定义为l(x_i)=-log₂p(x_i),p(x_i)是选择该分类的概率。计算出所有类别所有可能值包含的信息期望值就可以得到熵：H=-∑ⁿ_i=1 p(x_i)log₂p(x_i),n是分类的数目。

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

代码很简单，是书上的，这里不一一赘述。

3.1.2按照给定特征划分数据集

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

同样很简单，reducedFeatVec=featVec[:axis]指定特征之前的数据，reducedFeatVec.extend(featVec[axis+1:])指定特征之后的数据。（featVec[axis]已经作为分类的特征了嘛，需要去除）

3.1.3选择最好的数据集划分方式

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]#获取第i个特征所有的可能取值
　　　　uniqueVals=set(featList)
　　　　newEntropy=0.0
　　　　for value in uniqueVals:#根据第i个特征划分数据并计算划分后的熵
　　　　　　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个特征划分数据集最佳！

3.1.3递归构建决策树

好了，好了，做了这么多准备工作，现在终于要开始构建决策树了！

得到原始数据集，然后基于最好的属性值划分数据，由于特征值可能多于2个，因此可能存在大于2个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上在此划分数据。递归结束条件：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果

所有实例具有相同的分类，则得到一个叶子节点或终止块，任何到达叶子节点的数据必然属于叶子节点的分类。

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

返回出现次数最多的类别

好，我去学习matplotlib了，这样就可以将其可视化了！

决策树,布布扣,bubuko.com

决策树

原文：http://www.cnblogs.com/woshikafeidouha/p/3573730.html