基本概念决策树是一种分类算法。数据类型：数字和标称。数值数据必须离散化，因为构造算法仅适用于标称数据。工作原理是利用香农熵找到信息增益最大的特征，根据信息增益最大的特征对数据进行划分，重复这个过程，使无序的数据变得更加有序。使用ID3算法构建树结构。当传入一个新的数据时，根据数据找到对应的树节点，直到最后没有叶子节点，完成分类。样品可以在不浮出水面的情况下存活吗？它有脚蹼吗？是鱼吗？判断是不是鱼，是根据“不浮出水面能不能存活”和“有没有鳍状肢”这两个特征来判断的。建立一个简单的决策树，如果你得到一个新的生物，你可以用它来判断它是不是鱼。示例代码defcreateDataSet():dataSet=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]labels=['nosurfacing','flippers']returndataSet,labels香农熵公式如果待分类的交易可能分为多个类别，则符号xi的信息定义为：其中P(Xi)是选择类别的概率为了计算熵，需要计算所有类别的所有可能值所包含的信息的期望值之和，公式为：其中n是类别数ShannonentropyalgorithmdefcalcShannonEnt(dataSet):#选择类别的概率是每个类别/总数#总数，多少行数据numEntries=len(dataSet)labelCounts={}#每个类别的个数typeobtainedforfeatVecindataSet:currentLabel=featVec[-1]ifcurrentLabelnotinlabelCounts.keys():labelCounts[currentLabel]=0labelCounts[currentLabel]+=1shannonEnt=0.0forkeyinlabelCounts:#得到的概率选择这一类prob=float(labelCounts[key])/numEntries#根据公式shannonEnt-=prob*log(prob,2)#logbase2returnsshannonEnt根据香农熵划分数据不仅需要度量信息熵，还需要对数据集进行划分，对支出数据集的熵进行度量，以判断当前划分是否正确。循环计算香农熵和splitDataSet()寻找最好的特征划分方法。defsplitDataSet(dataSet,axis,value):#该算法返回轴下标外的列retDataSet=[]forfeatVecindataSet:iffeatVec[axis]==value:reducedFeatVec=featVec[:axis]#chopoutaxisusedforsplittingreducedFeatVec.extend(featVec[axis+1:])retDataSet.append(reducedFeatVec)returnretDataSetdefchooseBestFeatureToSplit(dataSet):#先取最后一列，用在标签结果中：fishornot。numFeatures=len(dataSet[0])-1#原始香农熵baseEntropy=calcShannonEnt(dataSet)bestInfoGain=0.0;bestFeature=-1#遍历所有特征foriinrange(numFeatures):#创建一个包含这个所有值的列表featurefeatList=[example[i]forexampleindataSet]#使用set去重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=infoGainbestFeature=i#returnsubscriptreturnbestFeature数据集需要满足一定的要求：数据必须是由列表元素组成的列表。（二维数组）所有列表元素的长度必须相同。***一列必须是当前实例的标签。决策树多数表决算法的递归构造如果数据集的所有属性都处理完了，但是类标签仍然不唯一，需要决定如何定义叶节点。在这种情况下，我们通常使用多数表决来确定叶节点。importoperatordefmajorityCnt(classList):#排序提取最多的类型itemgetter(1),reverse=True)returnsortedClassCount[0][0]树构建算法defcreateTree(dataSet,labels):#得到结果classList=[example[-1]forexampleindataSet]#如果结果中的*元素代表了数据个数等于结果本身，说明没有其他分类ifclassList.count(classList[0])==len(classList):returnclassList[0]#如果没有更多数据，可以多一个classifiediflen(dataSet[0])==1:#多数投票，返回出现频率最高的returnmajorityCnt(classList)#选择最适合分割类型的下标bestFeat=chooseBestFeatureToSplit(dataSet)#根据下标得到labelbestFeatLabel=labels[bestFeat]#构造树myTree={bestFeatLabel:{}}#删除标签已经被取出来避免重复计算del(labels[bestFeat])featValues=[example[bestFeat]forexampleindataSet]#使用set去重uniqueVals=set(featValues)forvalueinuniqueVals:#复制所有子标签，因为它是引用类型避免改变原始标签数据subLabels=labels[:]#递归构造树myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels)returnmyTree使用决策树点类defclassify(inputTree,featLabels,testVec):firstStr=inputTree.keys()[0]secondDict=inputTree[firstStr]featIndex=featLabels.index(firstStr)#print'featIndex%s'%(featIndex)key=testVec[featIndex]#print'key%s'%(key)valueOfFeat=secondDict[key]ifisinstance(valueOfFeat,dict):classLabel=classify(valueOfFeat,featLabels,testVec)else:classLabel=valueOfFeat返回classLabeldataSet,labels=createDataSet()mytree=createTree(dataSet,labels[:])#因为内部会删除labels中的值，所以用这个复制printmytree#{'nosurfacing':{0:'no',1:{'flippers':{0:'no',1:'yes'}}}}printclassify(mytree,labels,[0,1])no决策树的存储构造决策树是一项耗时的工作，即使数据集很小，所以我们可以使用构造决策树。defstoreTree(inputTree,filename):importpicklefw=open(filename,'w')pickle.dump(inputTree,fw)fw.close()defgrabTree(filename):importpicklefr=open(filename)returnpickle.load(fr)优势计算是复杂度不高，输出结果容易理解，对缺失中间值不敏感，可以处理不相关的特殊检测缺点，可能导致过匹配问题
