机器学习实验二之决策树

1、机器学习实训实验报告（二）专业班级学号姓名实验项目名称：基于信息增益生成决策树实验内容：1、熟知决策树的概念，和决策树基本算法思想。2、理解信息增益的计算方法。3、利用书上表4.2训练集部分数据进行学习，画出决策树实验过程： 算法分析：决策树算法思想：1）树以代表训练样本的单个结点 开始。2） 如果样本都在同一个类. 则该 结点成为树叶，并用该类标记。3）否则，算法选择最有分类能力 的属性作为决策树的当前结点.4）根据当前决策结点属性取值的 不同，将训练样本 数据集til分 为若干子集，每个取值形成一个 分枝，有几个取值形成几个分枝。 匀针对上一步得到的一个子集， 重复进行先前步骤，递4

2、9;l形成每 个划分样本上的决策树。一旦一 个属性出现在一个结点上，就不 必在该结点的任何后代考虑它。5）递归划分步骤仅当下列条件之 一成立时停止： 给定结点的所有样本属于同一 类。 没有剩余属性可以用来进一步 划分样本在这种情况下使用 多数表决，将给定的结点转换成 树叶，并以样本中元组个数最多 的类别作为类别标记，同时也可 以存放该结点样本的类别分布， 如果某一分枝tc,没有满足该 分支中已有分类的样本，则以样 本的多数类创建一个树叶。源程序代码：from matplotlib.fo nt_ma nager import Fon tPropertiesimport matplotlib.py

3、plot as pltfrom math import logimport operator'''函数说明：计算给定数据集的经验熵(香农熵)'''def calcSha nnonEn t(dataSet):numE ntires = len( dataSet)#返回数据集的行数labelCounts = #保存每个标签(Label)出现次数的字典for featV ec in dataSet: #对每组特征向量进行统计currentLabel = featVec-1#提取标签(Label)信息if curre ntLabel not in lab

4、elCo un ts.keys():#如果标签(Label)没有放入统计次数的字典，添加进去labelCo un tscurre ntLabel = 0labelCountscurrentLabel += 1#Label 计数shannonEnt = 0.0#经验熵(香农熵)for key in labelCou nts:# 计算香农熵prob = float(labelCountskey) / numEntires#选择该标签(Label)的概率shannonEnt -= prob * log(prob, 2) # 利用公式计算return shannonEnt#返回经验熵(香农熵)'

5、;''函数说明：创建测试数据集'''def createDataSet():dataSet = 1,0, 1,0, 0, 0, 'no',# 数据集2, 0, 0, 0, 0, 0, 'no',2, 0, 1, 0, 0, 0, 'yes',1, 1, 1, 0, 1, 1, 'yes',2, 1, 1, 1, 1, 1, 'no',1,2, 2, 0, 2, 1, 'no',0, 1,0, 1,0, 0, 'no',2, 1, 1, 0, 1

6、, 1, 'yes',0, 0, 1,2, 2, 0, 'yes',1, 0, 0, 1, 1, 0, 'yes'信息熵和信息增益： 熵是一个信息论中很抽象的概 念，从熵定义的角度来看，熵表 示一组信息中，所有随机变量出 现的期望，他的计算公是：En tropy(S)H(x)= E p(xi)*log1/(p(xi) (i=1,2,.n)=- E p(xi)*log(p(xi) (i=1,2,.n)其中log的底数是2.公式的理解是：p(i)表示第i个变 量出现的概率，则1/p(i)表示若p(i)发生的样本容量，如果用二进 制来表示样本容量，则n

7、=Iog21/p(i),所以将所有的随机的变量 和用二进制表示的样本容量的二 进制数的容量相加就得到熵。从中可以看到，熵表示了一个分 类中数据的杂乱程度，熵越小的 话，分类就越有规律，所以我们 自然会联想到，若要在数据挖掘 中使得分类的效果最好，就要设 法减小这个信息熵。从而我们又 引入了信息增益的概念。因为对 于一个集合，可能有多种分类的 方法，那么哪种分类是最优呢？ 如果原来的分组的信息熵记为H(x),那么划分后的分组的信息熵我们 用计算公式：l(X; split) =p(good)*H(g)+p(wro ng)*H(w),这里的p(good)是符号化表示。我 假如将一箱苹果数目为x，其中

8、有好有坏，按一种标准比如外观 将好的分为一堆(good)有g个， 则 p(good)=g/x。H (g)的计算方 法同信息熵的计算方法。信息增益的公式为： Gai n( X;split)=H(x)-I(X;split);当然得到的Gain()的值越大表示分labels ='色泽'，根蒂','敲声','纹理','脐部'，触感'#特征标 签return dataSet, labels#返回数据集和分类属性“'函数说明：按照给定特征划分数据集'''def splitDataSet(data

9、Set, axis, value): retDataSet = #创建返回的数据集列表for featV ec in dataSet:# 遍历数据集if featVecaxis = value: reducedFeatVec = featVec:axis#去掉 axis 特征reducedFeatVec.exte nd(featVecaxis+1:)#将符合条件的添加到返回的数据集retDataSet.appe nd(reducedFeatVec) return retDataSet#返回划分后的数据集“'函数说明：选择最优特征'''def chooseBest

10、FeatureToSplit(dataSet):num Features = len(dataSet0) - 1#特征数量baseE ntropy = calcSha nnonEn t(dataSet)#计算数据集的香农熵best In foGain = 0.0#信息增益bestFeature = -1#最优特征的索引值for i in range(num Features):# 遍历所有特征#获取dataSet的第i个所有特征featList = examplei for example in dataSetuniqueVals = set(featList)#创建 set集合,元素不可重复

11、newE ntropy = 0.0#经验条件熵for value in uniq ueVals:# 计算信息增益subDataSet = splitDataSet(dataSet, i, value) #subDataSet划分后的子集prob = len(subDataSet) / float(len(dataSet) #计算 子集的概率newEntropy += prob * calcShannonEnt(subDataSet) #根据公式计算经验条件熵infoGain = baseE ntropy - n ewE ntropy#信息增益# print("第%d 个特征的增益为

12、.3f" % (i, infoGain)#打印每个特征的信息增益if (in foGai n > bestl nfoGa in):# 计算信息增益bestl nfoGa in = in foGai n#更新信息增益，找到最大的信息增益bestFeature = i#记录信息增益最大的特征的索引值return bestFeature#返回信息增益最大的特征的索引值配的越好。'''函数说明：统计classList中出现此处取多的兀素(类标签)"def majorityC nt(classList): classCo unt = for vote i

13、n classList:#统计classList中每个兀素出现的次数if vote not in classCo un t.keys():classCo un tvote = 0 classCo un tvote += 1sortedClassCo unt =sorted(classCo un t.items(),key =operator.itemgetter(1), reverse = True)#根据字典的值降序排序return sortedClassCountOO#返回 classList 中出现次数取多的兀素”'函数说明：创建决策树”def createTree(dataSe

14、t, labels, featLabels):classList = example-1 for example in dataSet#取分类标签(是否放贷:yes or no)if classList.count(classListO) = len(classList):#如果类别完全相同则停止继续划分retur n classListOif len(dataSet0) = 1:#遍历完所有特征时返回出现次数最多的类标签return majorityC nt(classList) bestFeat = chooseBestFeatureToSplit(dataSet)# 选择最优特征best

15、FeatLabel = labelsbestFeat#最优特征的标签featLabels.appe nd(bestFeatLabel) myTree = bestFeatLabel:#根据最优特征的标签生成树del(labelsbestFeat)#删除已经使用特征标签featValues = examplebestFeat for example in dataSet# 得至 U训练集中所有最优特征的属性值un iqueVals = set(featValues)# 去掉重复的属性值for value in uni queVals:#遍历特征，创建决策树。myTreebestFeatLabel

16、value=createTree(splitDataSet(dataSet, bestFeat, value), labels, featLabels) return myTree'''函数说明：获取决策树叶子结点的数目'''def getNumLeafs(myTree):numLeafs = 0#初始化叶子firstStr = next(iter(myTree)#python3 中 myTree.keys()返回的是dict_keys,不在是list,#所以不能使用myTree.keys()O的方法获取结点属性，可以 使用 list(myTre

17、e.keys()0seco ndDict = myTreefirstStr#获取下一组字典for key in sec on dDict.keys():if type(secondDictkey)._name_='dict':# 测试该结点是否为字典，如果不是字典，代表此结点为叶子结点nu mLeafs += getNumLeafs(sec on dDictkey) else:nu mLeafs +=1retur n nu mLeafs'''函数说明：获取决策树的层数'''def getTreeDepth(myTree):maxD

18、epth = 0#初始化决策树深度firstStr = n ext(iter(myTree)#python3 中 myTree.keys()返回的是 dict_keys,不在是 list, #所以不能使用myTree.keys()O的方法获取结点属性，可以 使用 list(myTree.keys()Oseco ndDict = myTreefirstStr#获取下一个字典for key in sec on dDict.keys():if type(secondDictkey)._name_='dict':# 测试该结点是否为字典，如果不是字典，代表此结点为叶子结点thisDep

19、th = 1 + getTreeDepth(seco ndDictkey) else:thisDepth = 1if thisDepth > maxDepth: maxDepth = thisDepth# 更新层数return maxDepth'''函数说明：绘制结点'''def plotNode( no deTxt, cen terPt, pare ntPt, no deType): arrow_args = dict(arrowstyle="<-")#定义箭头格式font = FontProperties(fn

20、ame=r"C:/Users/asus/Desktop/ 机器学习 实验/实验一 /msyh.ttc", size=14)#解决中文显示冋题，指定为黑体createPlot.ax1.a nno tate( no deTxt, xy=pare ntPt, xycoords='axes fractio n',#绘制结点xytext=ce nterPt, textcoords='axes fraction', va="ce nter",ha="ce nter",bbox=no deType,arrowprop

21、s=arrow_args, Fon tProperties=fo nt)'''函数说明：标注有向边属性值'''def plotMidText(cntrPt, parentPt, txtString):xMid = (pare ntPt0-cntrPt0)/2.0 + cntrPtO# 计算标注位置yMid = (pare ntPt1-cntrPt1)/2.0 + cntrPt1 createPlot.ax1.text(xMid,yMid,txtStri ng,va="ce nter",ha="ce nter"

22、;, rotati on=30)'''函数说明：绘制决策树'''def plotTree(myTree, pare ntPt, no deTxt):decisio nN ode = dict(boxstyle="sawtooth", fc="0.8")# 设置结点格式leafNode = dict(boxstyle="rou nd4", fc="0.8")# 设置叶结点格式numLeafs = getNumLeafs(myTree)# 获取决策树叶结点数目，决定了树的

23、宽度depth = getTreeDepth(myTree)# 获取决策树层数firstStr = n ext(iter(myTree)# 下个字典cntrPt=(plotTree.xOff+(1.0+float (n umLeafs)/2.0/plotTree.totalW, plotTree.yOff)#中心位置plotMidText(cntrPt, pare ntPt, n odeTxt)#标注有向边属性值plotNode(firstStr, cntrPt, pare ntPt, decisio nNode)#绘制结点secondDict = myTreefirstStr#下一个字典，也

24、就是继续绘制子结点plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD#y 偏移for key in sec on dDict.keys():if type(secondDictkey)._name_='dict':#测试该结点是否为字典，如果不是字典，代表此结点为叶子结点plotTree(seco ndDictkey,cntrPt,str(key)# 不是叶结点，递归调用继续绘制else:#如果是叶结点，绘制叶结点，并标注有向边属性值plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW plotNode(seco ndDictkey,(plotTree.xOff,plotTree.yOff), cn trPt, leafNode)plotMidText(plotTree.xOff,plotTree.yOff), cntrPt,str(key)plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD'''函数说明：创建绘制面板'''def createPlot( in Tree):fig = plt.figure(1, facec