我们经常使用决策树处理分类问题，但近年的调查表明决策树也是一种常用的数据挖掘算法
中小学可以完成多分类任务，但最大的缺点是不能给出数据的内在含义，决策树的主要优点是数据格式非常容易理解
决策树的优缺点：
优点：计算复杂度不高，输出结果简单易懂，对中间值丢失不敏感，能够处理无关的特征数据
缺点：可能发生过度匹配问题
适用的数据类型：数值型和公称型
构建决策树时，我们要解决的第一个问题是当前数据集上的哪些特征在对数据进行分类时起决定性作用。
为了找到决定性的特征，将最佳的结果分类，必须评价各自的特征。 测试完成后，将绘制原始数据集
分为几个数据的子集。 如果一个分支下的数据相同，这些数据子集将分布在第一个决策点的所有分支上
类型时，当前不需要阅读的垃圾邮件正确分类了数据，不需要进一步拆分数据集。 对于数据子
如果集中的数据不是同一类型，则必须重复拆分数据子集的过程。 分割数据子集的算法和分割原始数据集的方法
的方法相同，直到同一类型的所有数据都在一个数据子集中
决策树的一般流程
(1)数据采集)可以使用任何方法
)2)准备数据：因为树形结构算法只适用于公称型数据，所以数值型数据必须离散化
)3)分析数据)可以使用任何方法，但结构树完成后，应检查图形是否符合预期
(4)训练算法)结构树的数据结构
(5)测试算法)利用经验树计算错误率
(6)算法的使用)该步骤适用于任何监测学习算法，应用决策树可以更好地理解数据的内在含义
根据数据集构建决策树算法所需的子功能模块运行如下： 得到原始数据集
最好的属性值划分数据集，并且可能多余两个特征值，因此可能存在大于两个分支的数据集划分
第一次拆分后，数据传递到树分支的下一个节点。 在该节点上，还可以
子分类数据。
1计算给定数据集的香农熵2 frommathimportlog 3导入操作器4导入器5
6
7defcalcshannonent(dataset ) :8 # )计算数据集的实例总数
9创建9numentries=len(dataset ) 10 labelCounts={}11 #词典。 他的键值是最后一列中的值，如果当前键值不存在，则扩展词典并将当前键值添加到词典中。
12 #每个键值都记录了当前类别的出现次数。 最后，利用所有类标签的发生频率计算类出现的概率。 我们
13 #以此概率计算香农熵，计数所有类标签发生的次数。
14 forfeatvecindataset : # thethenumberofuniqueelementsandtheiroccurance
15 #编写所有可能分类的词典
16 current label=feat vec [-1 ] 17 ifcurrentlabelnotinlabelcounts.keys (3360标签计数[ current label ]=018标签计数)
19 shannonEnt=0.0
香农定理，以20 forkeyinlabelcounts :21 prob=float (label counts [ key ] )/numEntries22 #为底求出对数
23Shannonent-=prob*log(prob，2 ) #log base 2
24 returnshannonent 25 defcreatedataset (:26 dataset=[ 1，1，' yes']，27 [ 1，1，' yes']，28 [ 1，0，' no ' ] '
33返回数据，标签S34
35 #按给定特征划分数据集
36 #个输入参数：要分割的数据集、分割数据集的特征和特征返回值。
37 #注： python没有考虑内存分配问题
38 defsplitdataset (数据、轴、值) :39 #创建新的列表对象
40 ret dataset=[ ] 41 forfeatvecindataset :42 iffeatvec [ axis ]==value :43 #提取
44 reducedfeatvec=feat vec [ : axis ] # chopoutaxisusedforsplitting
45 reducedfeatvec.extend (feat vec [ axis 1: ] ) 46 ret dataset.append (reducedfeatvec ) 47 returnr
etDataSet4849 #选择最好的数据集划分方式
50 defchooseBestFeatureToSplit(dataSet):51 numFeatures = len(dataSet[0]) - 1 #the last column is used for the labels
52 #计算了整个数据集的香农熵
53 baseEntropy =calcShannonEnt(dataSet)54 bestInfoGain = 0.0; bestFeature = -1
55 for i in range(numFeatures): #iterate over all the features
56 #创建唯一的分类标签列表
57 featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
58 uniqueVals = set(featList) #get a set of unique values
59 newEntropy = 0.0
60 for value inuniqueVals:61 #计算每种划分方式的信息熵
62 subDataSet =splitDataSet(dataSet, i, value)63 prob = len(subDataSet)/float(len(dataSet))64 newEntropy += prob *calcShannonEnt(subDataSet)65 infoGain = baseEntropy - newEntropy #calculate the info gain; ie reduction in entropy
66 if (infoGain >bestInfoGain):67 #计算最好的增益compare this to the best gain so far
68 bestInfoGain = infoGain #if better than current best, set to best
69 bestFeature =i70 returnbestFeature71
72 #这与投票代码非常类似，该函数使用分类名称的列表，然后创建键值为classList中唯一值的数据字典，字典对象
73 #存储了classList中每个类标签出现的频率，最后利用operator操作键值排序字典，并返回出现次数最多的分类名称。
74 defmajorityCnt(classList):75 classCount={}76 for vote inclassList:77 if vote not in classCount.keys(): classCount[vote] =078 classCount[vote] += 1
79 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)80 returnsortedClassCount[0][0]81
82 #创建树的函数代码
83 """
84 两个输入参数：数据集和标签列表85 """
86 defcreateTree(dataSet,labels):87 classList = [example[-1] for example indataSet]88 #类别完全相同则停止继续划分
89 if classList.count(classList[0]) ==len(classList):90 return classList[0]#stop splitting when all of the classes are equal
91 #遍历完所有特征时，返回出现次数最多的
92 if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
93 returnmajorityCnt(classList)94 bestFeat =chooseBestFeatureToSplit(dataSet)95 bestFeatLabel =labels[bestFeat]96 myTree ={bestFeatLabel:{}}97 del(labels[bestFeat])98 #得到列表包含的所有属性值
99 featValues = [example[bestFeat] for example indataSet]100 uniqueVals =set(featValues)101 for value inuniqueVals:102 subLabels = labels[:] #copy all of labels, so trees don"t mess up existing labels
103 myTree[bestFeatLabel][value] =createTree(splitDataSet(dataSet, bestFeat, value),subLabels)104 returnmyTree105
106 #使用决策树分类函数
107 defclassify(inputTree,featLabels,testVec):108 firstStr =list(inputTree.keys())[0]109 secondDict =inputTree[firstStr]110 featIndex =featLabels.index(firstStr)111 key =testVec[featIndex]112 valueOfFeat =secondDict[key]113 ifisinstance(valueOfFeat, dict):114 classLabel =classify(valueOfFeat, featLabels, testVec)115 else: classLabel =valueOfFeat116 returnclassLabel117
118
119 myDat,label=createDataSet()120
121 print("数据集"+str(myDat))122 print("labels"+str(label))123 #A=calcShannonEnt(myDat)
124 #print("香农熵"+str(A))
125 #B=splitDataSet(myDat,0,1)
126 #print("按给定特征划分数据集"+str(B))
127 #C=chooseBestFeatureToSplit(myDat)
128 #print("最好的增益"+str(C))
129 """
130 # 结果告诉我们，第0个特征是最好的用于划分数据集的特征。131 # 如果我们按照第一个特征属性划分数据，也就是说第一个特征是1的放在一组，132 # 第一个特征是0的放在另一组133 #"""
134 mytree=treePlotter.retrieveTree(0)135 D=classify(mytree,label,[1,0])136 print(D)