python决策树算法的实现

python决策树算法的实现'''数据集：Mnist训练集数量：60000测试集数量：10000------------------------------运⾏结果：ID3(未剪枝)正确率：85.9%运⾏时长：356s'''importtimeimportnumpyasnpdefloadData(fileName):'''加载⽂件:paramfileName:要加载的⽂件路径:return:数据集和标签集'''#存放数据及标记dataArr=[];labelArr=[]#读取⽂件fr=open(fileName)#遍历⽂件中的每⼀⾏forlineinfr.readlines():#获取当前⾏，并按“，”切割成字段放⼊列表中#strip：去掉每⾏字符串⾸尾指定的字符（默认空格或换⾏符）#split：按照指定的字符将字符串切割成每个字段，返回列表形式curLine=line.strip().split(',')#将每⾏中除标记外的数据放⼊数据集中（curLine[0]为标记信息）#在放⼊的同时将原先字符串形式的数据转换为整型#此外将数据进⾏了⼆值化处理，⼤于128的转换成1，⼩于的转换成0，⽅便后续计算dataArr.append([int(int(num)>128)fornumincurLine[1:]])#将标记信息放⼊标记集中#放⼊的同时将标记转换为整型labelArr.append(int(curLine[0]))#返回数据集和标记returndataArr,labelArrdefmajorClass(labelArr):'''找到当前标签集中占数⽬最⼤的标签:paramlabelArr:标签集:return:最⼤的标签'''#建⽴字典，⽤于不同类别的标签技术classDict={}#遍历所有标签foriinrange(len(labelArr)):#当第⼀次遇到A标签时，字典内还没有A标签，这时候直接幅值加1是错误的，#所以需要判断字典中是否有该键，没有则创建，有就直接⾃增iflabelArr[i]inclassDict.keys():#若在字典中存在该标签，则直接加1classDict[labelArr[i]]+=1else:#若⽆该标签，设初值为1，表⽰出现了1次了classDict[labelArr[i]]=1#对字典依据值进⾏降序排序classSort=sorted(classDict.items(),key=lambdax:x[1],reverse=True)#返回最⼤⼀项的标签，即占数⽬最多的标签returnclassSort[0][0]defcalc_H_D(trainLabelArr):'''计算数据集D的经验熵，参考公式5.7经验熵的计算:paramtrainLabelArr:当前数据集的标签集:return:经验熵'''#初始化为0H_D=0#将当前所有标签放⼊集合中，这样只要有的标签都会在集合中出现，且出现⼀次。#遍历该集合就可以遍历所有出现过的标记并计算其Ck#这么做有⼀个很重要的原因：⾸先假设⼀个背景，当前标签集中有⼀些标记已经没有了，⽐如说标签集中#没有0（这是很正常的，说明当前分⽀不存在这个标签）。式5.7中有⼀项Ck，那按照式中的针对不同标签k#计算Cl和D并求和时，由于没有0，那么C0=0，此时C0/D0=0,log2(C0/D0)=log2(0)，事实上0并不在log的#定义区间内，出现了问题#所以使⽤集合的⽅式先知道当前标签中都出现了那些标签，随后对每个标签进⾏计算，如果没出现的标签那⼀项就#不在经验熵中出现（未参与，对经验熵⽆影响），保证log的计算能⼀直有定义trainLabelSet=set([labelforlabelintrainLabelArr])#遍历每⼀个出现过的标签foriintrainLabelSet:#计算|Ck|/|D|#trainLabelArr==i：当前标签集中为该标签的的位置#例如a=[1,0,0,1],c=(a==1):c==[True,false,false,True]#trainLabelArr[trainLabelArr==i]：获得为指定标签的样本#trainLabelArr[trainLabelArr==i].size：获得为指定标签的样本的⼤⼩，即标签为i的样本#数量，就是|Ck|#trainLabelArr.size：整个标签集的数量（也就是样本集的数量），即|D|p=trainLabelArr[trainLabelArr==i].size/trainLabelArr.size#对经验熵的每⼀项累加求和H_D+=-1*p*np.log2(p)#返回经验熵returnH_DdefcalcH_D_A(trainDataArr_DevFeature,trainLabelArr):'''计算经验条件熵:paramtrainDataArr_DevFeature:切割后只有feature那列数据的数组:paramtrainLabelArr:标签集数组:return:经验条件熵'''#初始为0H_D_A=0#在featue那列放⼊集合中，是为了根据集合中的数⽬知道该feature⽬前可取值数⽬是多少trainDataSet=set([labelforlabelintrainDataArr_DevFeature])#对于每⼀个特征取值遍历计算条件经验熵的每⼀项foriintrainDataSet:#计算H(D|A)#trainDataArr_DevFeature[trainDataArr_DevFeature==i].size/trainDataArr_DevFeature.size:|Di|/|D|#calc_H_D(trainLabelArr[trainDataArr_DevFeature==i]):H(Di)H_D_A+=trainDataArr_DevFeature[trainDataArr_DevFeature==i].size/trainDataArr_DevFeature.size\*calc_H_D(trainLabelArr[trainDataArr_DevFeature==i])#返回得出的条件经验熵returnH_D_AdefcalcBestFeature(trainDataList,trainLabelList):'''计算信息增益最⼤的特征:paramtrainDataList:当前数据集:paramtrainLabelList:当前标签集:return:信息增益最⼤的特征及最⼤信息增益值'''#将数据集和标签集转换为数组形式#trainLabelArr转换后需要转置，这样在取数时⽅便#例如a=np.array([1,2,3]);b=np.array([1,2,3]).T#若不转置，a[0]=[1,2,3]，转置后b[0]=1,b[1]=2#对于标签集来说，能够很⽅便地取到每⼀位是很重要的trainDataArr=np.array(trainDataList)trainLabelArr=np.array(trainLabelList).T#获取当前特征数⽬，也就是数据集的横轴⼤⼩featureNum=trainDataArr.shape[1]#初始化最⼤信息增益maxG_D_A=-1#初始化最⼤信息增益的特征maxFeature=-1#对每⼀个特征进⾏遍历计算forfeatureinrange(featureNum):#“5.2.2信息增益”中“算法5.1（信息增益的算法）”第⼀步：#1.计算数据集D的经验熵H(D)H_D=calc_H_D(trainLabelArr)#2.计算条件经验熵H(D|A)#由于条件经验熵的计算过程中只涉及到标签以及当前特征，为了提⾼运算速度（全部样本#做成的矩阵运算速度太慢，需要剔除不需要的部分），将数据集矩阵进⾏切割#数据集在初始时刻是⼀个Arr=60000*784的矩阵，针对当前要计算的feature，在训练集中切割下#Arr[:,feature]这么⼀条来，因为后续计算中数据集中只⽤到这个（没明⽩的跟着算⼀遍例5.2）#trainDataArr[:,feature]:在数据集中切割下这么⼀条#trainDataArr[:,feature].flat：将这么⼀条转换成竖着的列表#np.array(trainDataArr[:,feature].flat)：再转换成⼀条竖着的矩阵，⼤⼩为60000*1（只是初始是#这么⼤，运⾏过程中是依据当前数据集⼤⼩动态变的）trainDataArr_DevideByFeature=np.array(trainDataArr[:,feature].flat)#3.计算信息增益G(D|A)G(D|A)=H(D)-H(D|A)G_D_A=H_D-calcH_D_A(trainDataArr_DevideByFeature,trainLabelArr)#不断更新最⼤的信息增益以及对应的featureifG_D_A>maxG_D_A:maxG_D_A=G_D_AmaxFeature=featurereturnmaxFeature,maxG_D_AdefgetSubDataArr(trainDataArr,trainLabelArr,A,a):'''更新数据集和标签集:paramtrainDataArr:要更新的数据集:paramtrainLabelArr:要更新的标签集:paramA:要去除的特征索引:parama:当data[A]==a时，说明该⾏样本时要保留的:return:新的数据集和标签集'''#返回的数据集retDataArr=[]#返回的标签集retLabelArr=[]#对当前数据的每⼀个样本进⾏遍历foriinrange(len(trainDataArr)):#如果当前样本的特征为指定特征值aiftrainDataArr[i][A]==a:#那么将该样本的第A个特征切割掉，放⼊返回的数据集中retDataArr.append(trainDataArr[i][0:A]+trainDataArr[i][A+1:])#将该样本的标签放⼊返回标签集中retLabelArr.append(trainLabelArr[i])#返回新的数据集和标签集returnretDataArr,retLabelArrdefcreateTree(*dataSet):'''递归创建决策树:paramdataSet:(trainDataList，trainLabelList)<<--元祖形式:return:新的⼦节点或该叶⼦节点的值'''#设置Epsilon，“5.3.1ID3算法”第4步提到需要将信息增益与阈值Epsilon⽐较，若⼩于则直接处理后返回TEpsilon=0.1#从参数中获取trainDataList和trainLabelListtrainDataList=dataSet[0][0]trainLabelList=dataSet[0][1]#打印信息：开始⼀个⼦节点创建，打印当前特征向量数⽬及当前剩余样本数⽬print('startanode',len(trainDataList[0]),len(trainLabelList))#将标签放⼊⼀个字典中，当前样本有多少类，在字典中就会有多少项#也相当于去重，多次出现的标签就留⼀次。举个例⼦，假如处理结束后字典的长度为1，那说明所有的样本#都是同⼀个标签，那就可以直接返回该标签了，不需要再⽣成⼦节点了。classDict={iforiintrainLabelList}#如果D中所有实例属于同⼀类Ck，则置T为单节点数，并将Ck作为该节点的类，返回T#即若所有样本的标签⼀致，也就不需要再分化，返回标记作为该节点的值，返回后这就是⼀个叶⼦节点iflen(classDict)==1:#因为所有样本都是⼀致的，在标签集中随便拿⼀个标签返回都⾏，这⾥⽤的第0个（因为你并不知道#当前标签集的长度是多少，但运⾏中所有标签只要有长度都会有第0位。returntrainLabelList[0]#如果A为空集，则置T为单节点数，并将D中实例数最⼤的类Ck作为该节点的类，返回T#即如果已经没有特征可以⽤来再分化了，就返回占⼤多数的类别iflen(trainDataList[0])==0:#返回当前标签集中占数⽬最⼤的标签returnmajorClass(trainLabelList)#否则，按式5.10计算A中个特征值的信息增益，选择信息增益最⼤的特征AgAg,EpsilonGet=calcBestFeature(trainDataList,trainLabelList)#如果Ag的信息增益⽐⼩于阈值Epsilon，则置T为单节点树，并将D中实例数最⼤的类Ck#作为该节点的类，返回TifEpsilonGet<Epsilon:returnmajorClass(trainLabelList)#否则，对Ag的每⼀可能值ai，依Ag=ai将D分割为若⼲⾮空⼦集Di，将Di中实例数最⼤的#类作为标记，构建⼦节点，由节点及其⼦节点构成树T，返回TtreeDict={Ag:{}}#特征值为0时，进⼊0分⽀#getSubDataArr(trainDataList,trainLabelList,Ag,0)：在当前数据集中切割当前feature，返回新的数据集和标签集treeDict[Ag][0]=createTree(getSubDataArr(trainDataList,trainLabelList,Ag,0))treeDict[Ag][1]=createTree(getSubDataArr(trainDataList,trainLabelList,Ag,1))returntreeDictdefpredict(testDataList,tree):'''预测标签:paramtestDataList:样本:paramtree:决策树:return:预测结果'''#treeDict=copy.deepcopy(tree)#死循环，直到找到⼀个有效地分类whileTrue:#因为有时候当前字典只有⼀个节点#例如{73:{0:{74:6}}}看起来节点很多，但是对于字典的最顶层来说，只有73⼀个key，其余都是value#若还是采⽤for来读取的话不太合适，所以使⽤下⾏这种⽅式读取key和value(key,value),=tree.items()#如果当前的value是字典，说明还需要遍历下去iftype(tree[key]).__name__=='dict':#获取⽬前所在节点的feature值，需要在样本中删除该feature#因为在创建树的过程中，feature的索引值永远是对于当时剩余的feature来设置的#所以需要不断地删除已经⽤掉的特征，保证索引相对位置的⼀致性dataVal=testDataList[key]deltestDataList[key]#将tree更新为其⼦节点的字典tree=value[dataVal]#如果当前节点的⼦节点的值是int，就直接返回该int值#例如{403:{0:7,1:{297:7}}，dataVal=0#此时上⼀⾏tree=value[dataVal]，将tree定位到了7，⽽7不再是⼀个字典了，#这⾥就可以直接返回7了，如果tree=value[1]，那就是⼀个新的⼦节点，需要继续遍历下去iftype(tree).__name__=='int':#返回该节点值，也就是分类值returntreeelse:#如果当前value不是字典，那就返回分类值returnvaluedefaccuracy(testDataList,testLabelList,tree):'''测试准确率:paramtestDataList:待测试数据集:para