决策树的一般流程:
- 收集数据
- 准备数据:数构造方法只适用于标称型数据,因此数值型数据必须离散化
- 分析数据
- 训练算法:构造数的数据结构
- 测试算法:使用经验数计算错误率
- 使用算法
优点:计算复杂度不高,输出易于理解,对中间值的缺失不敏感,可以处理不相关特征数据
缺点:可能会产生过度匹配问题
适用数据类型:数值型和标称型
使用信息论划分数据集,然后编写代码将理论应用到具体的数据集上,最后编写代码构建决策树
伪码:
检测数据集中的每个子项是否属于同一分类:
if so return 类标签:
else
寻找划分数据集的最好特征
划分数据集
创建分支节点
for 每个划分的子集
调用函数createBranch并增加返回结果到分支节点中
return 分支节点
决策树的评价所用的定量考察方法为计算每种划分情况的信息熵增益：
如果经过某个选定的属性进行数据划分后的信息熵下降最多，则这个划分属性是最优选择
S-E越大越好
经过决策属性的划分后，数据的无序度越来越低，也就是信息熵越来越小
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]=0labelCounts[currentLabel]+=1shannonEnt=0.0for key in labelCounts:prob=float(labelCounts[key])/numEntriesshannonEnt-=prob*log(prob,2)return shannonEntdef createDataSet():dataSet=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]labels=['no surfacing','flippers']return dataSet,labelsdef splitDataSet(dataSet,axis,value):#划分数据集的特征,需要返回的特征的值retDataSet=[]for featVec in dataSet:if featVet[axis]==value: #数据集的列,即特征,reducedFeatVec=featVec[:axis]#将前后未分类的抽取出来reducedFeatVec.extend(featVec[axis+1:])retDataSet.append(reducedFeatVec) #返回未分类的数据集return retDataSet#全部分好的数据集#选择最好的数据集划分方式
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.0for 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=infoGainbestFeature=i#增益好的就是最好的分类方式,返回的是列名..归到一起了return bestFeatureimport operator#多数表决的方法定义该叶子节点的分类
def majorityCnt(classList): #值不唯一的数据字典classCount={}for vote in classList:if vote not in classCount.keys():classCount[vote]=0classCount[vote]+=1sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)#排序字典return sortedClassCount[0][0]#创建树的函数代码
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:#说明其label不唯一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