决策树算法总结

决策树算法总结优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。缺点：可能会产生过度匹配问题。适用数据类型：数值型和标称型。算法工作原理：为了找到决定性特征值，划分出最好的结果，我们必须评估每个特征。完成测试后，原始数据集被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个数据分支下的数据属于同一类型，则当前无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。如果划分数据子集的算法和划分原始数据集的方法相同，直到所有具有相同类型的数据均在一个数据子集内。伪代码（函数createBrabch（））： Ifsoreturn类标签； else 寻找划分数据集的最好特征 划分数据集 创建分支节点 for每个划分的子集 调用函数createBrabch并增加返回结果到分支节点中 return分支节点构建过程（使用Python语言）：一．在构造决策树时，我们需要解决的第一个问题： 当前数据集上哪个特征在划分数据分类时起决定性作用为了解决这个问题，我们先引入几个概念：信息：如果待分类的事务可能划分在多个分类之中，则符号的信息定义为其中是选择该分类的概率。香农熵（简称为熵）：信息的期望值。为了计算熵，我们需要计算所有类别所有可能的值包含的信息期望值，通过下面公式可以得到其中n是分类的数目。信息增益：数据集划分前后信息发生的变化。程序清单1： 计算给定数据的香农熵defcalcShannonEnt(dataSet): numEntries=len(dataSet) labelCounts={} forfeatVecindataSet: currentLabel=featVec[-1] ifcurrentLabelnotinlabelCounts.keys(): labelCounts[currentLabel]=0 labelCounts[currentLabel]+=1 shannonEnt=0.0 forkeyinlabelCounts: prob=float(labelCounts[key])/numEntries shannonEnt-=prob*log(prob,2) returnshannonEnt二．在学习了如何度量数据集的无序程度后，还要划分数据集，度量划分数据集的熵，以便确定当前是否正确地划分了数据集。我们将对每个特征划分数据集的结果计算一次信息熵，然后判断哪个特征划分数据集是最好的划分方式。程序清单2: 按照给定特征划分数据集defsplitDataSet(dataSet,axis,value): retDataSet=[] forfeatVecindataSet: iffeatVec[axis]==value: reducedFeatVec=featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) returnretDataSet三个输入参数分别为：待划分数据集，划分数据集的特征，特征的返回值。注意：extend()和append()方法的使用。程序清单3： 选择最好的数据集划分方式defchooseBestFeatureToSplit(dataSet): numFeatures=len(dataSet[0])-1 baseEntropy=calcShannonEnt(dataSet) bestInfoGain=0.0 bestFeature=-1 foriinrange(numFeatures): featList=[example[i]forexampleindataSet] uniqueVals=set(featList) newEntropy=0.0 forvalueinuniqueVals: 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 returnbestFeature遍历整个数据集，循环计算香农熵和splitDataSet()函数，找到最好的特征划分方式。三．学习了从数据集构造决策树算法所需的子功能模块后，开始构建决策递归树，其工作原理如下：得到原始数据，然后基于最好的属性值划分数据集，由于特征值可能有多余两个，因此可能存在大于两个分支的数据集划分。第一次划分后，数据将被传递到树分支下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。 递归结束的条件是：遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。程序清单4： 选择出现次数最多的分类defmajorityCnt(classList): classCount={} forvoteinclassList: ifvotenotinclassCount.keys(): classCount[vote]=0 classCount[vote]+=1 sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True) returnsortedClassCount[0][0]程序清单5： 创建决策树defcreateTree(dataSet,labels): classList=[example[-1]forexampleindataSet] ifclassList.count(classList[0])==len(classList): print'classListaresame' returnclassList[0] iflen(dataSet[0])==1: print'nofeature' returnmajorityCnt(classList) bestFeat=chooseBestFeatureToSplit(dataSet) bestFeatLabel=labels[bestFeat] myTree={bestFeatLabel:{}} del(labels[bestFeat]) featValues=[example[bestFeat]forexampleindataSet] uniqueVals=set(featValues) forvalueinuniqueVals: subLabels=labels[:] myTree[bestFeatL