4.1基本流程 决策树学习基本算法：大概思想就是通过信息增益来递归构建决策树，返回条件： （1）当前节点属于同一类别 （2）当前属性集为空，或者当前所有属性相同（返回值为样本数量最多的类） （3）当前节点包含的样本集为空集 算法流程如下图： 4.2 划分选择 我们希望每个节点包含的样本“纯度”高，即差异性不大，此时可以用信息熵作为判定标准。 信息熵是用来度量样本集合纯度的指标，简单来说，信息熵越大，样本越“混乱”，信息熵越小，样本纯度越高，信息熵公式下： 4.2.1 信息增益 ID3决策树是以信息增益为准则来划分属性的,信息增益和信息熵的关系 算法C4.5和CART决策树与ID3的不同点就在于划分属性的判定标准。 C4.5判定标准是增益率： CART决策树的判定标准是基尼指数： 4.3 剪枝处理 剪枝是决策树算法对付“过拟合”的主要手段，主要有两种，“预剪枝”和“后剪枝” 4.3.1预剪枝 预剪枝基于贪心策略，减少了决策树的分支，预剪枝虽然会降低过拟合的风险，并且还显著减少了决策树的训练时间开销和测试时间开销，但是降低了决策树的泛化性能。 4.3.2后剪枝 后剪枝是在决策树生成之后，判定每个节点被替换成叶节点之后的精度，来决定是否进行剪枝，后剪枝决策树比预剪枝决策树保留了更多的分支，欠拟合风险小，但是训练时间开销比未剪枝决策树和预剪枝决策树都要大的多。
4.4连续值和缺省值 4.4.1连续值 对连续值来说最简单的处理方式就是二分法，划分候选的点的集合如下： 同时，我们可以对前面的信息增益的公式稍稍改变： 当信息增益最大时，得到的属性划分点就是我们要的点. 4.4.2缺失值 样本缺失之后，有两个重要的问题（1）如何在属性值缺失的情况下进行划分样本属性的选择（2）给定划分属性，若样本在该属性上的值缺失了，如何对样本进行划分。 4.5多变量决策树 决策树的特点之一就是分类边界的每一段都是与坐标轴平行的，但是在这种情况下当分类边界比较复杂是，要使用很多段划分才能获得较好的近似效果例如： 在多变量决策树中使用了斜的划分边界，不是为每个结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器，例如： 下面是创建决策树的代码，代码来源是《机器学习实战》
from typing import List, Union import operator def calcShannonEnt(dataSet): numEntries=len(dataSet) labelCounts={} for featVec in dataSet: currentLabel=featVec[-1] if currentLabel not in labelCounts: 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 def creatDataSet(): dataSet=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']] labels=['no surfacing','flippers'] return dataSet,labels def splitDataSet(dataSet,axis,value): retDataSet=[] for featVec in dataSet: if featVec[axis]==value: reducedFeatVec=featVec[:axis] reducedFeatVec.extend(featVec[axis,:]) 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]#取一列dataSet uniqueVals=set(featList) newEntropy=0.0 #当以第i个元素划分时，信息增益的值 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 bestFeature def majorityCnt(classList): calssCount={} 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)#iteritems()将字典以列表的形式返回 operator.itemgetter return sortedClassCount[0][0] def createTree(dataSet,labels): classList=[example[-1] for example in dateSet] 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] uniqueaVals=set(featvalues) for value in uniqueaVals: subLabels=labels[:] myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels) return myTree def classify(inputTree,featLabels,testVec): firstStr=inputTree.keys()[0] secondDic=inputTree[firstStr] featIndex=featLabels.index(firstStr) for key in secondDic.keys(): if testVec[featIndex]==key: if type(secondDic[key]).__name__=='dict': classLabel=classify(secondDic[key],featLabels,testVec) else: classLabel=secondDict[key] return classLabel