python对决策树的实现_python实现决策树

python对决策树的实现

一、实验目的

此表中有14条实例数据，就是我们的训练数据。

其中 Outlook, Temperature, Humidity, Wind 称作条件属性，PlayTennis 称作是决策属性(标签)。

每一个属性都有各自的值记做：

1 Value(Outlook)={Sunny, OverCast, Rain}
2 Value(Temperature)={Hot, Mild, Cool}
3 Value(Humidity)={High, Normal}
4 Value(Wind)={Strong, Weak}
5 Value(PlayTennis)={NO, Yes}

有以上数据，目的是建立决策树，导入数据，选择特征值并挑选最佳特征位，训练数据计算熵值。

二、代码实现过程

1、引用

1 from math import log    #进行对数运算
2 from matplotlib.font_manager import FontProperties  #中文字体
3 import matplotlib.pyplot as plt  #画图

2、算给定数据集的经验熵（香农熵）

香农熵公式：

 1 def calcShannonEnt(dataSet):
 2     numEntries=len(dataSet)                          #数据集行数
 3     labelCounts={}                                   #声明保存每个标签（label）出现次数的字典
 4     for featVec in dataSet:                          #对每组特征向量进行统计
 5         currentLabel=featVec[-1]                     #提取标签信息
 6         if currentLabel not in labelCounts.keys():   #如果标签没有放入统计次数的字典，添加进去
 7             labelCounts[currentLabel]=0
 8         labelCounts[currentLabel]+=1                 #label计数
 9 #以上是将每个标签出现的次数放入labelCounts字典中，目的就是求出香农公式里的P(x)
10     shannonEnt=0.0                                   #经验熵
11     for key in labelCounts:                          #计算经验熵
12         prob=float(labelCounts[key])/numEntries      #选择该标签的概率
13         shannonEnt-=prob*log(prob,2)                 #利用公式计算
14     return shannonEnt                                #返回经验熵

3、创建数据集

以上面给的数据为例，因为数据较少，没有进行文件数据的读取操作，直接定义数据

　　

 1 def createDataSet():
 2     data = [
 3         ['Sunny', 'Hot', 'High', 'Weak', 'No'],
 4         ['Sunny', 'Hot', 'High', 'Strong', 'No'],
 5         ['Overcast', 'Hot', 'High', 'Weak', 'Yes'],
 6         ['Rain', 'Mild', 'High', 'Weak', 'Yes'],
 7         ['Rain', 'Cool', 'Normal', 'Weak', 'Yes'],
 8         ['Rain', 'Cool', 'Normal', 'Strong', 'No'],
 9         ['Overcast', 'Cool', 'Normal', 'Strong', 'Yes'],
10         ['Sunny', 'Mild', 'High', 'Weak', 'No'],
11         ['Sunny', 'Cool', 'Normal', 'Weak', 'Yes'],
12         ['Rain', 'Mild', 'Normal', 'Weak', 'Yes'],
13         ['Sunny', 'Mild', 'Normal', 'Strong', 'Yes'],
14         ['Overcast', 'Mild', 'High', 'Strong', 'Yes'],
15         ['Overcast', 'Hot', 'Normal', 'Weak', 'Yes'],
16         ['Rain', 'Mild', 'High', 'Strong', 'No'],
17     ]
18     labels = ['Outlook', 'Temperature', 'Humidity', 'Wind']
19     return data,labels                               #最后返回的是数据集和分类属性

4、对数据集进行划分

例如、观察矩阵的第一列是否满足需要，如果满足需要，就把后面的添加进来，然后追加到新的矩阵中。

为什么这么做呢？除此之外，axis是轴的意思，这段代码给出了三个参数，第一个是要被划分的数据集（dataSet），第二个是轴线（axis），也就是说的第一列，第二列等，第三个是value，看这一列的数值是否等于value

目的就是为下面的步骤做准备，选出最好的数据分化方式。

1 def SplitData(dataSet,axis,value):
2     retDataSet=[]                                     #创建返回的数据集列表
3     for featVec in dataSet:                           #遍历数据集
4         if featVec[axis]==value:                      #如果
5             reduceFeatVec=featVec[:axis]              #去掉axis特征
6             reduceFeatVec.extend(featVec[axis+1:])    #将符合条件的添加到返回的数据集
7             retDataSet.append(reduceFeatVec)
8     #返回划分后的数据集
9     return retDataSet

5、选择最好的数据分化方式

信息增益的公式（信息增益于集合熵的关系式）：

其中，|S|为原集合的数量，|Sa|为分类后子集中元素的个数。Entropy(S)为原集合的熵 所以，G(S,A)是在给定属性A的值知道后，导致期望熵的减少,也就是说，若知道A的值，可以获得最大的信息增益，则属性A对数据集分类数量的降低有很大的积极作用。知道A之后，得到的信息是相对其他属性最多的。

 1 def chooseBestFeatureToSplit(dataSet):
 2     numFeatures = len(dataSet[0]) - 1                 #特征数量
 3     baseEntropy = calcShannonEnt(dataSet)             #计数数据集的香农熵
 4     bestInfoGain = 0.0                                #信息增益
 5     bestFeature = -1                                  #最优特征的索引值
 6     for i in range(numFeatures):                      #循环的作用就是遍历所有特征
 7         featList = [example[i] for example in dataSet]# 获取dataSet的第i个所有特征
 8         uniqueVals = set(featList)                    #创建set集合{}，元素不可重复
 9         newEntropy = 0.0                              #经验条件熵
10         for value in uniqueVals:                      #计算信息增益
11             subDataSet = splitDataSet(dataSet, i, value)#subDataSet划分后的子集
12             prob = len(subDataSet) / float(len(dataSet))#计算子集的概率
13             newEntropy += prob * calcShannonEnt((subDataSet))#根据公式计算经验条件熵
14         infoGain = baseEntropy - newEntropy           #信息增益
15         print("第%d个特征的增益为%.3f" % (i, infoGain))  #打印每个特征的信息增益
16         if (infoGain > bestInfoGain):                 #计算信息增益
17             bestInfoGain = infoGain                   #更新信息增益，找到最大的信息增益
18             bestFeature = i                           #记录信息增益最大的特征的索引值
19     return bestFeature                                #最终返回的是信息增益最大特征的索引值

以上运行完以后可以先实验程序

1 mydata,labels=createDataSet()                         
2 chooseBestFeatureToSplit(mydata)

6、找到出现次数最多的分类名称

1 def moretype_con(classList):
2     classCount={}                                     #主要是存储每个类标签出现的频率
3     for i in classList:
4         if i not  in classList.keys(): classCount[i]=0 # 如果一次也没有，次数就赋值为0
5         classCount+=1
6         sorted_classCount=sorted(classCount.iteriterms(),key=operator.itemgetter(1),reverse=True)
7     return  sorted_classCount

7、递归创建决策树

 1 def createTree(dataSet, labels,featLabels):
 2     classList = [example[-1] for example in dataSet]  # 取分类标签（是否出去玩：yes or no）
 3     if classList.count(classList[0]) == len(classList):# 如果类别完全相同则停止继续划分
 4         return classList[0]
 5     if len(dataSet[0]) == 1:                          # 遍历完所有特征时返回出现次数最多的类标签
 6         return majorityCnt(classList)    
 7     bestFeat = ChoosebestSplitData(dataSet)           # 选择最优特征
 8     bestFeatLabel = labels[bestFeat]                  # 最优特征的标签
 9     featLabels.append(bestFeatLabel)
10     myTree = {bestFeatLabel: {}}                      # 根据最优特征的标签生成树
11                                                       # 删除已经使用的特征标签
12                                                       # 得到训练集中所有最优解特征的属性值
13     featValues = [example[bestFeat] for example in dataSet]
14     uniqueVals = set(featValues)                      # 去掉重复的属性值
15     for value in uniqueVals:                          # 遍历特征，创建决策树
16         del_bestFeat = bestFeat
17         del_labels = labels[bestFeat]
18         del (labels[bestFeat])
19         myTree[bestFeatLabel][value] = createTree(SplitData(dataSet, bestFeat, value), labels, featLabels)
20         labels.insert(del_bestFeat, del_labels)
21     return myTree

8、获取叶节点的数目和树的层次

（1）、获取叶节点的数目

 1 def getleaf_num(myTree):
 2     leaf_num=0
 3     Start = next(iter(myTree))
 4     #print("\nStart",Start)
 5     Then = myTree[Start]
 6     #print("\nThen",Then)
 7     for key in Then.keys():
 8         if type(Then[key]).__name__ == 'dict':
 9             leaf_num += getleaf_num(Then[key])
10         else:
11             leaf_num += 1
12     return leaf_num

（2）、获取树的层次

 1 def getTree_Depth(myTree):
 2     Depth = 0
 3     Start=next(iter(myTree))
 4     Then = myTree[Start]
 5     for key in Then.keys():
 6         if type(Then[key]).__name__ == 'dict':
 7             thisDepth =1 + getTree_Depth(Then[key])
 8         else:
 9             thisDepth = 1
10     if thisDepth>Depth:Depth=thisDepth
11     return Depth

（3）、查看树的叶节点的数目和树的层次

1 mydata,labels=createDataSet()
2 myTree=createTree(mydata,labels)
3 ​
4 print("叶子节点",getleaf_num(myTree))
5 print("树的层数节",getTree_Depth(myTree))

9、绘制树

（1）、定义箭头样式

1 def plotNode(nodeTxt, centerPt, parentPt, nodeType):                                          
2     font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)        #设置中文字体
3     createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',    #绘制结点
4         xytext=centerPt, textcoords='axes fraction',
5         va="center", ha="center", bbox=nodeType, arrowprops=dict(arrowstyle="<-"), FontProperties=font)

（2）、标注有向边属性值

1 def plotMidText(cntrPt, parentPt, txtString):
2     xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]                               #计算标注位置
3     yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
4     createPlot.ax1.text(xMid, yMid, txtString)

（3）、绘制决策树

 1 def plotTree(myTree, parentPt, nodeTxt):
 2     decisionNode = dict(boxstyle="sawtooth", fc="0.8")  # 设置结点格式
 3     leafNode = dict(boxstyle="round4", fc="0.8")
 4     #设置叶结点格式
 5     numLeafs = getleaf_num(myTree)                                                 #获取决策树叶结点数目，决定了树的宽度
 6     depth = getTree_Depth(myTree)                                                  #获取决策树层数
 7     firstStr = next(iter(myTree))                                                  #下个字典
 8     cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)    #中心位置
 9     plotMidText(cntrPt, parentPt, nodeTxt)                                         #标注有向边属性值
10     plotNode(firstStr, cntrPt, parentPt, decisionNode)                             #绘制结点
11     secondDict = myTree[firstStr]                                                  #下一个字典，也就是继续绘制子结点
12     plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD                            #y偏移
13     for key in secondDict.keys():
14         if type(secondDict[key]).__name__=='dict':                                #测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
15             plotTree(secondDict[key],cntrPt,str(key))                              #不是叶结点，递归调用继续绘制
16         else:                                                                      #如果是叶结点，绘制叶结点，并标注有向边属性值
17             plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
18             plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
19             plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
20     plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD

10、测试

1 myDat,labels=creatDataSet()
2     myTree=createTree(myDat,labels)
3     print(myTree)
4     createPlot(myTree)

三、整个程序

  1 from math import log
  2 import operator
  3 from matplotlib.font_manager import FontProperties
  4 import matplotlib.pyplot as plt
  5 #计算数据集的香农公式的值
  6 ​
  7 ​
  8 #新建数据集合
  9 def creatDataSet():
 10     # 数据集
 11     data = [
 12         ['Sunny', 'Hot', 'High', 'Weak', 'No'],
 13         ['Sunny', 'Hot', 'High', 'Strong', 'No'],
 14         ['Overcast', 'Hot', 'High', 'Weak', 'Yes'],
 15         ['Rain', 'Mild', 'High', 'Weak', 'Yes'],
 16         ['Rain', 'Cool', 'Normal', 'Weak', 'Yes'],
 17         ['Rain', 'Cool', 'Normal', 'Strong', 'No'],
 18         ['Overcast', 'Cool', 'Normal', 'Strong', 'Yes'],
 19         ['Sunny', 'Mild', 'High', 'Weak', 'No'],
 20         ['Sunny', 'Cool', 'Normal', 'Weak', 'Yes'],
 21         ['Rain', 'Mild', 'Normal', 'Weak', 'Yes'],
 22         ['Sunny', 'Mild', 'Normal', 'Strong', 'Yes'],
 23         ['Overcast', 'Mild', 'High', 'Strong', 'Yes'],
 24         ['Overcast', 'Hot', 'Normal', 'Weak', 'Yes'],
 25         ['Rain', 'Mild', 'High', 'Strong', 'No'],
 26     ]
 27     labels = ['Outlook', 'Temperature', 'Humidity', 'Wind']  # 5个特征
 28 ​
 29     return data,labels
 30 ​
 31 ​
 32 ​
 33 ​
 34 def xiangnong(dataSet):
 35     #返回数据集行数
 36     numEntries=len(dataSet)
 37     #保存每个标签（label）出现次数的字典
 38     labelCounts={}
 39     #对每组特征向量进行统计
 40     for featVec in dataSet:
 41         currentLabel=featVec[-1]                     #提取标签信息
 42         if currentLabel not in labelCounts.keys():   #如果标签没有放入统计次数的字典，添加进去
 43             labelCounts[currentLabel]=0
 44         labelCounts[currentLabel]+=1                 #label计数
 45 ​
 46     shannonEnt=0.0                                   #经验熵
 47     #计算经验熵
 48     for key in labelCounts:
 49         prob=float(labelCounts[key])/numEntries      #选择该标签的概率
 50         shannonEnt-=prob*log(prob,2)                 #利用公式计算
 51     return shannonEnt
 52 ​
 53 ​
 54 #对数据集进行划分
 55 ​
 56 def SplitData(dataSet,axis,value):
 57     #创建返回的数据集列表
 58     retDataSet=[]
 59     #遍历数据集
 60     for featVec in dataSet:
 61         if featVec[axis]==value:
 62             #去掉axis特征
 63             reduceFeatVec=featVec[:axis]
 64             #将符合条件的添加到返回的数据集
 65             reduceFeatVec.extend(featVec[axis+1:])
 66             retDataSet.append(reduceFeatVec)
 67     #返回划分后的数据集
 68     return retDataSet
 69 ​
 70 ​
 71 #选择最好的数据集划分方式
 72 ​
 73 def ChoosebestSplitData(data):
 74     numFeatures = len(data[0]) - 1  # 获取样本集中特征个数，-1是因为最后一列是label
 75     baseEntropy = xiangnong(data)  # 计算根节点的信息熵
 76     bestInfoGain = 0.0  # 初始化信息增益
 77     bestFeature = -1  # 初始化最优特征的索引值
 78     for i in range(numFeatures):  # 遍历所有特征，i表示第几个特征
 79         featList = [example[i] for example in  data]  # 将dataSet中的数据按行依次放入example中，然后取得example中的example[i]元素，即获得特征i的所有取值
 80         uniqueVals = set(featList)  # 由上一步得到了特征i的取值，比如[1,1,1,0,0]，使用集合这个数据类型删除多余重复的取值，则剩下[1,0]
 81         newEntropy = 0.0
 82         for value in uniqueVals:
 83             subDataSet = SplitData(data, i, value)  # 逐个划分数据集，得到基于特征i和对应的取值划分后的子集
 84             prob = len(subDataSet) / float(len(data))  # 根据特征i可能取值划分出来的子集的概率
 85             newEntropy += prob * xiangnong(subDataSet)  # 求解分支节点的信息熵
 86         infoGain = baseEntropy - newEntropy  # 计算信息增益
 87         if (infoGain > bestInfoGain):  # 对循环求得的信息增益进行大小比较
 88             bestInfoGain = infoGain
 89             bestFeature = i  # 如果计算所得信息增益最大，则求得最佳划分方法
 90     return bestFeature  # 返回划分属性（特征）
 91 ​
 92 ​
 93 ​
 94 #该函数使用分类名称的列表，然后创建键值为ClassList中唯一的数据字典，字典对象存储了ClassList中每个类标签出现的评率，最后利用operator操作键值排序
 95 #字典，并返回出现次数最多的分类名称。
 96 def moretype_con(classList):
 97     classCount={}#主要是存储每个类标签出现的评率
 98     for i in classList:
 99         if i not  in classList.keys(): classCount[i]=0 # 如果一次也没有，次数就赋值为0
100         classCount+=1
101         sorted_classCount=sorted(classCount.iteriterms(),key=operator.itemgetter(1),reverse=True)
102     return  sorted_classCount
103 #创建树
104 def createTree(dataSet, labels,featLabels):
105 ​
106     # 取分类标签（是否出去玩：yes or no）
107     classList = [example[-1] for example in dataSet]
108     # 如果类别完全相同则停止继续划分
109     if classList.count(classList[0]) == len(classList):
110         return classList[0]
111     # 遍历完所有特征时返回出现次数最多的类标签
112     if len(dataSet[0]) == 1:
113         return majorityCnt(classList)
114     # 选择最优特征
115     bestFeat = ChoosebestSplitData(dataSet)
116     # 最优特征的标签
117     bestFeatLabel = labels[bestFeat]
118     featLabels.append(bestFeatLabel)
119     # 根据最优特征的标签生成树
120     myTree = {bestFeatLabel: {}}
121     # 删除已经使用的特征标签
122     # 得到训练集中所有最优解特征的属性值
123     featValues = [example[bestFeat] for example in dataSet]
124     # 去掉重复的属性值
125     uniqueVals = set(featValues)
126     # 遍历特征，创建决策树
127     for value in uniqueVals:
128         del_bestFeat = bestFeat
129         del_labels = labels[bestFeat]
130         del (labels[bestFeat])
131         myTree[bestFeatLabel][value] = createTree(SplitData(dataSet, bestFeat, value), labels, featLabels)
132         labels.insert(del_bestFeat, del_labels)
133     return myTree
134 ​
135 def getleaf_num(myTree):
136     leaf_num=0
137     Start = next(iter(myTree))
138 ​
139     Then = myTree[Start]
140 ​
141     for key in Then.keys():
142         if type(Then[key]).__name__ == 'dict':
143             leaf_num += getleaf_num(Then[key])
144         else:
145             leaf_num += 1
146     return leaf_num
147 ​
148 def getTree_Depth(myTree):
149     Depth = 0
150     Start=next(iter(myTree))
151     Then = myTree[Start]
152     for key in Then.keys():
153         if type(Then[key]).__name__ == 'dict':
154             thisDepth =1 + getTree_Depth(Then[key])
155         else:
156             thisDepth = 1
157     if thisDepth>Depth:Depth=thisDepth
158     return Depth
159 ​
160 ​
161 def plotNode(nodeTxt, centerPt, parentPt, nodeType):                                           #定义箭头格式
162     font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)        #设置中文字体
163     createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',    #绘制结点
164         xytext=centerPt, textcoords='axes fraction',
165         va="center", ha="center", bbox=nodeType, arrowprops=dict(arrowstyle="<-"), FontProperties=font)
166 ​
167 """
168 函数说明:标注有向边属性值
169 """
170 def plotMidText(cntrPt, parentPt, txtString):
171     xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]                                            #计算标注位置
172     yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
173     createPlot.ax1.text(xMid, yMid, txtString)
174 ​
175 """
176 函数说明:绘制决策树
177 ​
178 Parameters:
179     myTree - 决策树(字典)
180     parentPt - 标注的内容
181     nodeTxt - 结点名
182 """
183 def plotTree(myTree, parentPt, nodeTxt):
184     decisionNode = dict(boxstyle="sawtooth", fc="0.8")  # 设置结点格式
185     leafNode = dict(boxstyle="round4", fc="0.8")
186     #设置叶结点格式
187     numLeafs = getleaf_num(myTree)                                                          #获取决策树叶结点数目，决定了树的宽度
188     depth = getTree_Depth(myTree)                                                            #获取决策树层数
189     firstStr = next(iter(myTree))                                                            #下个字典
190     cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)    #中心位置
191     plotMidText(cntrPt, parentPt, nodeTxt)                                                    #标注有向边属性值
192     plotNode(firstStr, cntrPt, parentPt, decisionNode)                                        #绘制结点
193     secondDict = myTree[firstStr]                                                            #下一个字典，也就是继续绘制子结点
194     plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD                                        #y偏移
195     for key in secondDict.keys():
196         if type(secondDict[key]).__name__=='dict':                                            #测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
197             plotTree(secondDict[key],cntrPt,str(key))                                        #不是叶结点，递归调用继续绘制
198         else:                                                                                #如果是叶结点，绘制叶结点，并标注有向边属性值
199             plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
200             plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
201             plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
202     plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD
203 ​
204 """
205 函数说明:创建绘制面板
206 ​
207 Parameters:
208     inTree - 决策树(字典)
209 """
210 def createPlot(inTree):
211     fig = plt.figure(1, facecolor='white')#创建fig
212     fig.clf()#清空fig
213     axprops = dict(xticks=[], yticks=[])
214     createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)#去掉x、y轴
215     plotTree.totalW = float(getleaf_num(inTree))#获取决策树叶结点数目
216     plotTree.totalD = float(getTree_Depth(inTree))#获取决策树层数
217     plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0#x偏移
218     plotTree(inTree, (0.5,1.0), '')#绘制决策树
219     plt.show()#显示绘制结果
220 if __name__=='__main__':
221     myDat,labels=creatDataSet()
222     featLabels = []
223     myTree=createTree(myDat,labels,featLabels)
224     createPlot(myTree)