devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

ID3决策树及Python实现（详细）_动手实现id3决策树

作者：花生_TL007 | 2024-04-10 12:27:17

赞

踩

动手实现id3决策树

目录

一、划分特征的评价指标：

二、决策树学习算法伪代码：

三、决策树生成实例：

四、Python实现ID3决策树：

一、划分特征的评价指标：

1、信息熵 Ent(D)：

信息熵，是度量样本集合纯度的一种指标，Ent(D)的值越小，则样本集D的纯度越高；

2、信息增益 Gain(D,a)：

信息增益越大，则意味着使用属性a来划分所获得的“纯度提升”越大；ID3决策树算法就是基于信息增益来划分属性，下面介绍ID3决策树的构建过程；

公式中各变量说明：

D：样本集；

y：标签（比如好瓜、坏瓜）；

pk：某一类样本占总样本数的比例；

V：属性的取值（比如纹理属性有3种取值：清晰、稍糊、模糊）；

Dv：属性值==V从样本集D划分出的一个样本子集；

二、决策树学习算法伪代码：

决策树的生成是一个递归的过程，在决策树基本算法中，有三种情形会导致递归返回：

  1. 当前结点包含的样本全属于同一类别，无需划分；
  2. 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
  3. 当前结点包含的样本集合为空，不能划分； 

三、决策树生成实例：

3.1 首先获取一个训练样本集D，作为决策树的训练依据：

3.2 计算信息增益：

1、计算信息熵 Ent(D)：

2、计算当前特征集合 {色泽,根蒂,敲声,纹理,脐部,触感} 中各个特征a的信息增益Gain(D,a)：

 以“色泽”为例计算Gain(D,色泽)：

色泽的取值：{青绿,乌黑,浅白}，使用“色泽”特征对D划分可以得到3个子集：D1(色泽=青绿)={1,4,6,10,13,17}，D2(色泽=乌黑)={2,3,7,8,9,15}，D1(色泽=浅白)={5,11,12,14,16}，计算划分子集后分支结点的熵 ：

所以，得到Gain(D,色泽)：

 同理，计算其他特征的信息增益Gain(D,a)：

3.3 选取最优信息增益，选取最优划分特征：

因为Gain(D,纹理)最大，所以选取“纹理”作为本轮划分的最优划分特征，继而可以得到基于“纹理”的根节点划分：

3.4 决策树算法再对每个分支进一步划分（递归）：

将每个分支可以看成一个新的样本集，进行进一步的划分，在计算各特征信息增益时，需要将上一轮选出的最优特征在样本中去掉，不需要再对该特征进行比较。

就比如D1={1,2,3,4,5,6,8,10,15}，特征集合={色泽,根蒂,敲声,脐部,触感}。基于D1计算出各特征的信息增益Gain(D1,a)：

继续选取最大的特征信息增益，选出最优划分特征，即重复3.3步骤，递归实现决策树的建立；

3.5 生成最终的决策树：

四、Python实现ID3决策树：

总样本集：

  1. ['青绿','蜷缩','浊响','清晰','凹陷','硬滑','好瓜'],
  2. ['乌黑','蜷缩','沉闷','清晰','凹陷','硬滑','好瓜'],
  3. ['乌黑','蜷缩','浊响','清晰','凹陷','硬滑','好瓜'],
  4. ['青绿','蜷缩','沉闷','清晰','凹陷','硬滑','好瓜'],                
  5. ['青绿','稍蜷','浊响','清晰','稍凹','软粘','好瓜'],               
  6. ['乌黑','稍蜷','浊响','稍糊','稍凹','软粘','好瓜'],                
  7. ['乌黑','稍蜷','浊响','清晰','稍凹','硬滑','好瓜'],
  8. ['浅白','蜷缩','浊响','清晰','凹陷','硬滑','好瓜'],
  9. ['浅白','蜷缩','浊响','模糊','平坦','硬滑','坏瓜'],
  10.              
  11. ['乌黑','稍蜷','沉闷','稍糊','稍凹','硬滑','坏瓜'],
  12. ['青绿','硬挺','清脆','清晰','平坦','软粘','坏瓜'],
  13. ['浅白','蜷缩','浊响','模糊','平坦','软粘','坏瓜'],
  14. ['青绿','稍蜷','浊响','稍糊','凹陷','硬滑','坏瓜'],  
  15. ['浅白','稍蜷','沉闷','稍糊','凹陷','硬滑','坏瓜'],
  16. ['浅白','硬挺','清脆','模糊','平坦','硬滑','坏瓜'],
  17. ['乌黑','稍蜷','浊响','清晰','稍凹','软粘','坏瓜'],
  18. ['青绿','蜷缩','沉闷','稍糊','稍凹','硬滑','坏瓜']

下面从总样本种提取序号5、12、17为验证集，剩下为训练集进行训练决策树；

（1）训练集：

  1. ['青绿','蜷缩','浊响','清晰','凹陷','硬滑','好瓜'],
  2. ['乌黑','蜷缩','沉闷','清晰','凹陷','硬滑','好瓜'],
  3. ['乌黑','蜷缩','浊响','清晰','凹陷','硬滑','好瓜'],
  4. ['青绿','蜷缩','沉闷','清晰','凹陷','硬滑','好瓜'],
  5. ['乌黑','稍蜷','浊响','稍糊','稍凹','软粘','好瓜'],
  6. ['乌黑','稍蜷','浊响','清晰','稍凹','硬滑','好瓜'],
  7. ['浅白','蜷缩','浊响','清晰','凹陷','硬滑','好瓜'],
  8.  
  9. ['浅白','蜷缩','浊响','模糊','平坦','硬滑','坏瓜'],
  10. ['乌黑','稍蜷','沉闷','稍糊','稍凹','硬滑','坏瓜'],
  11. ['浅白','蜷缩','浊响','模糊','平坦','软粘','坏瓜'],
  12. ['青绿','稍蜷','浊响','稍糊','凹陷','硬滑','坏瓜'],
  13. ['浅白','稍蜷','沉闷','稍糊','凹陷','硬滑','坏瓜'],
  14. ['浅白','硬挺','清脆','模糊','平坦','硬滑','坏瓜'],
  15. ['青绿','蜷缩','沉闷','稍糊','稍凹','硬滑','坏瓜']

（2）验证集：

  1. ['青绿','稍蜷','浊响','清晰','稍凹','软粘'], ['好瓜']
  2. ['青绿','硬挺','清脆','清晰','平坦','软粘'], ['坏瓜']
  3. ['乌黑','稍蜷','浊响','清晰','稍凹','软粘'], ['坏瓜']

下面编写各个函数，每个函数有特定的功能，代码的分析过程已在code后注释。

4.1 构建样本集：

  1. #? 构建数据集
  2. #  返回一个元组 (dataSet,labels)
  3. def createDataSet():    # 创造示例数据
  4.     dataSet=[['青绿','蜷缩','浊响','清晰','凹陷','硬滑','好瓜'],
  5.              ['乌黑','蜷缩','沉闷','清晰','凹陷','硬滑','好瓜'],
  6.              ['乌黑','蜷缩','浊响','清晰','凹陷','硬滑','好瓜'],
  7.              ['青绿','蜷缩','沉闷','清晰','凹陷','硬滑','好瓜'],                
  8.              ['青绿','稍蜷','浊响','清晰','稍凹','软粘','好瓜'],               
  9.              ['乌黑','稍蜷','浊响','稍糊','稍凹','软粘','好瓜'],                
  10.              ['乌黑','稍蜷','浊响','清晰','稍凹','硬滑','好瓜'],
  11.              
  12.              ['乌黑','稍蜷','沉闷','稍糊','稍凹','硬滑','坏瓜'],
  13.              ['青绿','硬挺','清脆','清晰','平坦','软粘','坏瓜'],
  14.              ['浅白','蜷缩','浊响','模糊','平坦','软粘','坏瓜'],
  15.              ['青绿','稍蜷','浊响','稍糊','凹陷','硬滑','坏瓜'],  
  16.              ['浅白','稍蜷','沉闷','稍糊','凹陷','硬滑','坏瓜'],
  17.              ['乌黑','稍蜷','浊响','清晰','稍凹','软粘','坏瓜'],
  18.              ['青绿','蜷缩','沉闷','稍糊','稍凹','硬滑','坏瓜']]
  19.     labels = ['色泽','根蒂','敲声','纹理','脐部','触感']  #六个特征
  20.     return dataSet,labels

函数作用：用于构建训练集

变量说明：

  1. dataSet：样本集
  2. labels：所有特征

4.2 计算信息熵：

  1. #? 计算信息熵
  2. #  返回输入样本集dataSet的信息熵 Ent
  3. from math import log
  4. def calEnt(dataSet):
  5.     sampleCounts=len(dataSet)   # 样本集的样本数
  6.     labelCounts={}              # key为标签值label（好瓜、坏瓜），value为对应标签key在样本集中出现的次数
  7.     for sample in dataSet:      # 遍历样本集dataSet中每个样本sample
  8.         label=sample[-1]        # 标签label为样本sample的最后一个元素值
  9.         if label not in labelCounts.keys():     # 如果该标签label不在字典labelCounts的key值中
  10.             labelCounts[label]=0                # 则新增该key，并赋初值0
  11.         labelCounts[label]+=1   # 对遍历到的每个sample统计其所属标签的个数
  12.     Ent=0.0     # 信息熵初始化
  13.     for key in labelCounts:
  14.         pro=float(labelCounts[key])/sampleCounts    # 具体标签占总样本数的比例pro
  15.         Ent-=pro*log(pro,2)     # 计算样本集dataSet的信息熵Ent
  16.     return Ent

函数作用：计算样本集dataSet的信息熵E(dataSet)

变量说明：

  1. dataSet：传入的样本集
  2. sampleCounts：样本集中的样本数
  3. labelCounts：key为标签值（好瓜/坏瓜），value为对应标签key在样本集中出现的次数
  4. sample：具体样本
  5. label：标签（好瓜、坏瓜）
  6. pro：具体标签占总样本数的比例
  7. Ent：样本集dataSet的熵 Ent(D)

4.3 按给定的特征值划分出样本子集：

  1. #? 按给定特征值划分出样本子集
  2. #  指定特征列的索引index，对特征值==value的样本划分出来为一个样本子集retDataSet，并对这些样本的value去掉，返回样本子集 retDataSet
  3. def splitDataSet(dataSet,index,value):      # index是指定特征列的索引，value是该特征下的某一特征值
  4.     retDataSet=[]
  5.     for sample in dataSet:                  # 遍历样本集dataSet中的具体样本sample
  6.         if sample[index]==value:            # 找到目标特征值value的索引
  7.             # 去除特征值==value这些样本的vlaue值
  8.             reducedSample=sample[:index]            # 剪下目标索引前的列表
  9.             reducedSample.extend(sample[index+1:])  # 将目标索引后的列表添加到索引前列表的后面
  10.             retDataSet.append(reducedSample)        # 将sample[index]==value并去除该vlaue的样本添加到retDataSet样本集中
  11.     return retDataSet

函数作用：指定特征列的索引index，对样本集中特征值==value的具体样本sample划分出来，组成一个dataSet的样本子集retDataSet（并将这些样本中的这些value去掉，去掉sample[index]的目的是因为下轮比较各特征信息增益Gain从而获得最大信息增益bestGain（决定最优划分特征bestFeature）时，不能将已选出的最优特征放在比较队列中）

变量说明：

  1. dataSet：传入的样本集
  2. index：指定特征列的索引
  3. value：指定特征的某一特征值
  4. sample：dataSet的具体样本
  5. reducedSample：去除value后的具体样本（该样本sample[index]==value）
  6. retDataSet：按指定某一特征值划分出的样本子集

4.4 选取当前样本集下的最优划分特征索引：

  1. #? 选取当前样集下的最优划分特征索引
  2. #  返回最优划分特征的索引 bestFeatureIndex
  3. def chooseBestFeatureToSplit(dataSet):
  4.     featureCounts=len(dataSet[0])-1     # 获取当前样本集的特征个数，-1是因为最后一列是标签
  5.     baseEnt=calEnt(dataSet)             # 计算当前样本集的信息熵Ent(D)
  6.     bestGain=0.0;bestFeatureIndex=-1    # 初始化最优信息增益bestGain、最优特征bestFeature
  7.     for i in range(featureCounts):      # 遍历每个特征，求各自的信息增益Gain
  8.         featValList=[sample[i] for sample in dataSet]   # 第i个特征下所有样本出现的特征值（有重复）
  9.         uniqueVals=set(featValList)                     # 第i个特征的可能特征值（无重复）
  10.         newEnt=0.0          # 初始化信息熵
  11.         for value in uniqueVals:
  12.             subDataSet=splitDataSet(dataSet,i,value)    # 根据特定的特征值value划分出的样本子集
  13.             pro=len(subDataSet)/float(len(dataSet))     # 划分出的样本子集占总样本数的比例
  14.             newEnt+=pro*calEnt(subDataSet)              # 计算各特征值的熵并加和
  15.         Gain=baseEnt-newEnt                             # 计算信息增益Gain(D,a)
  16.         if(Gain>bestGain):      # 求最大的信息增益Gain
  17.             bestGain=Gain
  18.             bestFeatureIndex=i  # 获取最优划分特征的索引
  19.     return bestFeatureIndex

函数作用：计算各特征的信息增益Gain(dataset,feature)，从而选出最优划分特征bestFeature，最后返回最优划分特征的索引bestFeatureIndex；

变量说明：

  1. dataSet：传入的样本集
  2. featureCounts：当前样本集中特征的个数
  3. baseEnt：当前样本集的熵 Ent(D)
  4. bestGain：各特征中最大的信息增益 Gain(dataSet,bestFeature)
  5. bestFeatureIndex：最优划分特征的索引列号
  6. sample[i]：具体样本第i个特征值
  7. featureValList：第i个特征下所有样本中出现的特征值（有重复值）
  8. uniqueVals：第i个特征的可能特征值（无重复值）
  9. newEnt：不同特征值下的熵 Ent(Di)
  10. subDataSet：根据特定的特征值value划分出的样本子集
  11. pro：样本子集占总样本数的比例
  12. Gain：各个特征的信息增益Gain(D,a)

4.5 求样本集中出现次数最多的标签：

  1. #? 求样本集中出现次数最多的标签
  2. #  用于叶子节点的取值，返回样本集中出现次数最多的标签 sortedLabelCounts[0][0]
  3. import operator
  4. def majorLabel(labelList):
  5.     labelCounts={}      # key为标签（好瓜/坏瓜），value为标签在labelList中出现的次数
  6.     for label in labelList:     # 遍历所有样本的标签
  7.         if label not in labelCounts.keys(): # 如果该标签不在labelCounts的key值中
  8.             labelCounts[label]=0            # 则增加该key值，并赋初值=0
  9.         labelCounts[label]+=1               # 对labelCounts中已有的标签计数+1
  10.     sortedLabelCounts=sorted(labelCounts.items(),key=operator.itemgetter(1),reverse=True)   # 根据value值逆序排序labelCounts
  11.     return sortedLabelCounts[0][0]          # 返回第一个元素的第一个元素（标签）

函数作用：选取叶子结点的取值，返回样本集中出现次数最多的标签（好瓜/坏瓜）sortedLabelCounts[0][0]；

变量说明：

  1. labelList：返回样本集中所有样本的标签（有重复值）
  2. labelCounts：字典，key为标签，value为该标签key在labelList中出现的次数
  3. label：具体标签（好瓜/坏瓜）
  4. labelCounts.keys()：labelCounts的key值
  5. labelCounts[label]：labelCounts中key值==label对应的value值
  6. sortedLabelCounts：根据value值，逆序排列labelCounts字典
  7. sotredLabelCounts[0][0]：样本集中出现次数最多的标签

4.6 递归生成决策树：

  1. #? 生成决策树 主方法
  2. #  递归生成决策树 decisionTree
  3. #  递归是逐级由深向浅的返回
  4. def createTree(dataSet,labels):
  5.     labelList=[sample[-1] for sample in dataSet]    # 返回当前样本集dataSet中所有样本的标签（有重复值列表）
  6.     # 跳出递归，生成叶子节点（好瓜/坏瓜）
  7.     if labelList.count(labelList[0])==len(labelList):   # 如果labelList中的标签完全相同
  8.         return labelList[0]                             # 则直接返回该标签
  9.     if len(dataSet[0])==1:              # 如果当前样本集dataSet的样本长度==1（只剩最后一列标签，无特征可供继续划分又不满足所有标签相同）
  10.         return majorLabel(labelList)    # 就返回出现次数最多的标签作为叶子节点
  11.     
  12.     bestFeatureIndex=chooseBestFeatureToSplit(dataSet)  # 获取当前样本集dataSet最优划分特征的索引
  13.     bestFeature=labels[bestFeatureIndex]                # 获取当前样本集dataSet的最优划分特征
  14.     decisionTree={bestFeature:{}}   # 字典存储决策树的信息
  15.     del(labels[bestFeatureIndex])   # 删除已经选出的特征
  16.     featureVals=[sample[bestFeatureIndex] for sample in dataSet] # 样本集中所有样本中的最优特征对应的特征值组成的列表（有重复值）
  17.     uniqueVals=set(featureVals)     # 最优特征对应的所有可能取值（无重复值）
  18.     for value in uniqueVals:        # 遍历最优特征所有可能的取值value
  19.         subLabels=labels[:]         # 将最优特征去除后的特征列表传递给subLabels
  20.         decisionTree[bestFeature][value]=createTree(splitDataSet(dataSet,bestFeatureIndex,value),subLabels)  # 递归生成decisionTree
  21.     return decisionTree

函数作用：递归生成决策树 decisionTree

变量说明：

  1. dataSet：传入的样本集
  2. labels：传入的特征列表
  3. labelList：存放样本集dataSet中所有样本的标签（有重复值）
  4. sample：样本集的具体样本
  5. labelList[0]：第一个样本的标签
  6. dataSet[0]：样本集中的第一个样本
  7. majorLabel(labelList)：样本集中出现次数最多的标签
  8. bestFeatureIndex：当前样本集中最优划分特征的索引列
  9. bestFeature：当前样本集中最优的划分特征
  10. labels[bestFeatureIndex]：最优划分特征索引对应的具体特征
  11. decisionTree：生成的决策树
  12. featureVals：样本集dataSet中最优特征对应的所有特征值（有重复值）
  13. uniqueVals：最优特征对应的可能取值（无重复值）
  14. value：最优特征对应的具体取值
  15. subLabels：去除最优特征后的特征列表

4.7 对决策样本进行分类：

  1. #? 对验证样本进行分类
  2. #  返回一个对样本分类后的标签classLabel
  3. def classify(decisionTree,features,testSample):
  4. 	rootFeature=list(decisionTree.keys())[0]        # rootFeature：根节点是何种特征
  5. 	rootDict=decisionTree[rootFeature]              # rootDict为根节点的value值，是一个字典
  6. 	rootFeatureIndex=features.index(rootFeature)    # 获取根节点在特征列表中的索引
  7. 	for value in rootDict.keys():               # value为特征rootFeature的不同取值，并遍历value
  8. 		if testSample[rootFeatureIndex]==value:     # 如果待测样本的该特征的特征值==value
  9. 			if type(rootDict[value])==dict:     # 如果该特征值value对应的value'是一个字典
  10. 				classLabel=classify(rootDict[value],features,testSample)    # 则需要递归继续向决策树的下面结点查询
  11. 			else:                               # 如果该特征值value对应的value'是一个单独的值（标签）
  12. 				classLabel=rootDict[value]      # 则该值就是要找的标签
  13. 	return classLabel   # 返回该样本testSample的标签

函数作用：对传入的待测样本testSample根据已生成的决策树decisionTree计算出该样本的标签（好瓜/坏瓜），返回该标签 classLabel

变量说明：

  1. decisionTree：某一结点出发的决策树
  2. features：所有特征列表
  3. testSample：待测试样本
  4. decisionTree.keys()：（某一特征值下）对应根结点
  5. decisionTree[rootFeature]：根节点对应的各个分支，字典
  6. rootFeature：根节点（如纹理）
  7. rootDict：根节点下的分支，字典（纹理结点对应的三个分支：模糊、清晰、稍糊）
  8. rootFeatureIndex：节点在特征列表features中的索引；
  9. value：以根节点为特征的不同特征取值（如模糊/清晰/稍糊）
  10. testSample[rootFeatureIndex]：待测试样本中以根节点为特征对应的具体特征值
  11. rootDict[value]：具体特征值对应的value（可能是一个字典/标签）
  12. classLabel：该待测试样本计算出的标签

4.8 执行：

  1. if __name__=='__main__':    # 如果在当前模块/文件下执行，将会指定下述代码
  2.     dataSet, labels=createDataSet()
  3.     decisionTree=createTree(dataSet, labels)
  4.     print(f"\ndecisionTree={decisionTree}\n")     # 输出决策树模型结果
  5.     # 验证集
  6.     features=  ['色泽','根蒂','敲声','纹理','脐部','触感']  # 特征列表     
  7.     testSample=['浅白','蜷缩','浊响','清晰','凹陷','硬滑']  # 待测样本
  8.     print(f"测试结果1sampleLabel= {classify(decisionTree,features,testSample)}\n")   # 输出测试结果
  9.  
  10.     features=  ['色泽','根蒂','敲声','纹理','脐部','触感']  # 特征列表     
  11.     testSample=['浅白','硬挺','清脆','模糊','平坦','硬滑']  # 待测样本
  12.     print(f"测试结果2sampleLabel= {classify(decisionTree,features,testSample)}\n")   # 输出测试结果
  13.  
  14.     features=  ['色泽','根蒂','敲声','纹理','脐部','触感']  # 特征列表     
  15.     testSample=['浅白','蜷缩','浊响','模糊','平坦','硬滑']  # 待测样本
  16.     print(f"测试结果3sampleLabel= {classify(decisionTree,features,testSample)}\n")   # 输出测试结果

函数说明：执行主函数代码，利用上述各函数打印出最终的决策树decisionTree并且对验证集待测样本进行测试检验

变量说明：

  1. features：特征列表
  2. testSample：待测试样本

4.9 运行结果：

  1. decisionTree={'纹理': {'稍糊': {'触感': {'硬滑': '坏瓜', '软粘': '好瓜'}}, '清晰': {'根蒂': {'硬挺': '坏瓜', '蜷缩': '好瓜', '稍蜷': {'色泽': {'青绿': '好瓜', '乌黑': {'触感': {'硬滑': '好瓜', '软粘': '坏瓜'}}}}}}, '模糊': '坏瓜'}}     
  2.  
  3. 测试结果1sampleLabel= 好瓜
  4.  
  5. 测试结果2sampleLabel= 坏瓜
  6.  
  7. 测试结果3sampleLabel= 坏瓜

决策树decisionTree：

  1. {'纹理': 
  2.     {'模糊': '坏瓜', 
  3.      '清晰': {'根蒂': 
  4.                 {'稍蜷': {'色泽': 
  5.                             {'乌黑': {'触感': 
  6.                                         {'软粘': '坏瓜', 
  7.                                          '硬滑': '好瓜'}}, 
  8.                              '青绿': '好瓜'}}, 
  9.                  '硬挺': '坏瓜', 
  10.                  '蜷缩': '好瓜'}}, 
  11.      '稍糊': {'触感': 
  12.                 {'软粘': '好瓜', 
  13.                  '硬滑': '坏瓜'}}}}

可视化为树状结构为：

4.10 实现决策树的总代码：

  1. #! Decision Tree(ID3算法 信息增益Gain)
  2.  
  3. #? 构建数据集
  4. #  返回一个元组 (dataSet,labels)
  5. def createDataSet():    # 创造示例数据
  6.     dataSet=[['青绿','蜷缩','浊响','清晰','凹陷','硬滑','好瓜'],
  7.              ['乌黑','蜷缩','沉闷','清晰','凹陷','硬滑','好瓜'],
  8.              ['乌黑','蜷缩','浊响','清晰','凹陷','硬滑','好瓜'],
  9.              ['青绿','蜷缩','沉闷','清晰','凹陷','硬滑','好瓜'],                
  10.              ['青绿','稍蜷','浊响','清晰','稍凹','软粘','好瓜'],               
  11.              ['乌黑','稍蜷','浊响','稍糊','稍凹','软粘','好瓜'],                
  12.              ['乌黑','稍蜷','浊响','清晰','稍凹','硬滑','好瓜'],
  13.              
  14.              ['乌黑','稍蜷','沉闷','稍糊','稍凹','硬滑','坏瓜'],
  15.              ['青绿','硬挺','清脆','清晰','平坦','软粘','坏瓜'],
  16.              ['浅白','蜷缩','浊响','模糊','平坦','软粘','坏瓜'],
  17.              ['青绿','稍蜷','浊响','稍糊','凹陷','硬滑','坏瓜'],  
  18.              ['浅白','稍蜷','沉闷','稍糊','凹陷','硬滑','坏瓜'],
  19.              ['乌黑','稍蜷','浊响','清晰','稍凹','软粘','坏瓜'],
  20.              ['青绿','蜷缩','沉闷','稍糊','稍凹','硬滑','坏瓜']]
  21.     labels = ['色泽','根蒂','敲声','纹理','脐部','触感']  #六个特征
  22.     return dataSet,labels
  23.  
  24. #? 计算信息熵
  25. #  返回输入样本集dataSet的信息熵 Ent
  26. from math import log
  27. def calEnt(dataSet):
  28.     sampleCounts=len(dataSet)   # 样本集的样本数
  29.     labelCounts={}              # key为标签值label（好瓜、坏瓜），value为对应标签key在样本集中出现的次数
  30.     for sample in dataSet:      # 遍历样本集dataSet中每个样本sample
  31.         label=sample[-1]        # 标签label为样本sample的最后一个元素值
  32.         if label not in labelCounts.keys():     # 如果该标签label不在字典labelCounts的key值中
  33.             labelCounts[label]=0                # 则新增该key，并赋初值0
  34.         labelCounts[label]+=1   # 对遍历到的每个sample统计其所属标签的个数
  35.     Ent=0.0     # 信息熵初始化
  36.     for key in labelCounts:
  37.         pro=float(labelCounts[key])/sampleCounts    # 具体标签占总样本数的比例pro
  38.         Ent-=pro*log(pro,2)     # 计算样本集dataSet的信息熵Ent
  39.     return Ent
  40.  
  41. #? 按给定特征值划分出样本子集
  42. #  指定特征列的索引index，对特征值==value的样本划分出来为一个样本子集retDataSet，并对这些样本的value去掉，返回样本子集 retDataSet
  43. def splitDataSet(dataSet,index,value):      # index是指定特征列的索引，value是该特征下的某一特征值
  44.     retDataSet=[]
  45.     for sample in dataSet:                  # 遍历样本集dataSet中的具体样本sample
  46.         if sample[index]==value:            # 找到目标特征值value的索引
  47.             # 去除特征值==value这些样本的vlaue值
  48.             reducedSample=sample[:index]            # 剪下目标索引前的列表
  49.             reducedSample.extend(sample[index+1:])  # 将目标索引后的列表添加到索引前列表的后面
  50.             retDataSet.append(reducedSample)        # 将sample[index]==value并去除该vlaue的样本添加到retDataSet样本集中
  51.     return retDataSet
  52.  
  53. #? 选取当前样集下的最优划分特征索引
  54. #  返回最优划分特征的索引 bestFeatureIndex
  55. def chooseBestFeatureToSplit(dataSet):
  56.     featureCounts=len(dataSet[0])-1     # 获取当前样本集的特征个数，-1是因为最后一列是标签
  57.     baseEnt=calEnt(dataSet)             # 计算当前样本集的信息熵Ent(D)
  58.     bestGain=0.0;bestFeatureIndex=-1    # 初始化最优信息增益bestGain、最优特征bestFeature
  59.     for i in range(featureCounts):      # 遍历每个特征，求各自的信息增益Gain
  60.         featValList=[sample[i] for sample in dataSet]   # 第i个特征下所有样本出现的特征值（有重复）
  61.         uniqueVals=set(featValList)                     # 第i个特征的可能特征值（无重复）
  62.         newEnt=0.0          # 初始化信息熵
  63.         for value in uniqueVals:
  64.             subDataSet=splitDataSet(dataSet,i,value)    # 根据特定的特征值value划分出的样本子集
  65.             pro=len(subDataSet)/float(len(dataSet))     # 划分出的样本子集占总样本数的比例
  66.             newEnt+=pro*calEnt(subDataSet)              # 计算各特征值的熵并加和
  67.         Gain=baseEnt-newEnt                             # 计算信息增益Gain(D,a)
  68.         if(Gain>bestGain):      # 求最大的信息增益Gain
  69.             bestGain=Gain
  70.             bestFeatureIndex=i  # 获取最优划分特征的索引
  71.     return bestFeatureIndex
  72.  
  73. #? 求样本集中出现次数最多的标签
  74. #  用于叶子节点的取值，返回样本集中出现次数最多的标签 sortedLabelCounts[0][0]
  75. import operator
  76. def majorLabel(labelList):
  77.     labelCounts={}      # key为标签（好瓜/坏瓜），value为标签在labelList中出现的次数
  78.     for label in labelList:     # 遍历所有样本的标签
  79.         if label not in labelCounts.keys(): # 如果该标签不在labelCounts的key值中
  80.             labelCounts[label]=0            # 则增加该key值，并赋初值=0
  81.         labelCounts[label]+=1               # 对labelCounts中已有的标签计数+1
  82.     sortedLabelCounts=sorted(labelCounts.items(),key=operator.itemgetter(1),reverse=True)   # 根据value值逆序排序labelCounts
  83.     return sortedLabelCounts[0][0]          # 返回第一个元素的第一个元素（标签）
  84.  
  85. #? 生成决策树 主方法
  86. #  递归生成决策树 decisionTree
  87. #  递归是逐级由深向浅的返回
  88. def createTree(dataSet,labels):
  89.     labelList=[sample[-1] for sample in dataSet]    # 返回当前样本集dataSet中所有样本的标签（有重复值列表）
  90.     # 跳出递归，生成叶子节点（好瓜/坏瓜）
  91.     if labelList.count(labelList[0])==len(labelList):   # 如果labelList中的标签完全相同
  92.         return labelList[0]                             # 则直接返回该标签
  93.     if len(dataSet[0])==1:              # 如果当前样本集dataSet的样本长度==1（只剩最后一列标签，无特征可供继续划分又不满足所有标签相同）
  94.         return majorLabel(labelList)    # 就返回出现次数最多的标签作为叶子节点
  95.     
  96.     bestFeatureIndex=chooseBestFeatureToSplit(dataSet)  # 获取当前样本集dataSet最优划分特征的索引
  97.     bestFeature=labels[bestFeatureIndex]                # 获取当前样本集dataSet的最优划分特征
  98.     decisionTree={bestFeature:{}}   # 字典存储决策树的信息
  99.     del(labels[bestFeatureIndex])   # 删除已经选出的特征
  100.     featureVals=[sample[bestFeatureIndex] for sample in dataSet] # 样本集中所有样本中的最优特征对应的特征值组成的列表（有重复值）
  101.     uniqueVals=set(featureVals)     # 最优特征对应的所有可能取值（无重复值）
  102.     for value in uniqueVals:        # 遍历最优特征所有可能的取值value
  103.         subLabels=labels[:]         # 将最优特征去除后的特征列表传递给subLabels
  104.         decisionTree[bestFeature][value]=createTree(splitDataSet(dataSet,bestFeatureIndex,value),subLabels)  # 递归生成decisionTree
  105.     return decisionTree
  106.  
  107.      
  108. #? 对验证样本进行分类
  109. #  返回一个对样本分类后的标签classLabel
  110. def classify(decisionTree,features,testSample):
  111. 	rootFeature=list(decisionTree.keys())[0]        # rootFeature：根节点是何种特征
  112. 	rootDict=decisionTree[rootFeature]              # rootDict为根节点的value值，是一个字典
  113. 	rootFeatureIndex=features.index(rootFeature)    # 获取根节点在特征列表中的索引
  114. 	for value in rootDict.keys():               # value为特征rootFeature的不同取值，并遍历value
  115. 		if testSample[rootFeatureIndex]==value:     # 如果待测样本的该特征的特征值==value
  116. 			if type(rootDict[value])==dict:     # 如果该特征值value对应的value'是一个字典
  117. 				classLabel=classify(rootDict[value],features,testSample)    # 则需要递归继续向决策树的下面结点查询
  118. 			else:                               # 如果该特征值value对应的value'是一个单独的值（标签）
  119. 				classLabel=rootDict[value]      # 则该值就是要找的标签
  120. 	return classLabel   # 返回该样本testSample的标签
  121.  
  122.  
  123.  
  124. if __name__=='__main__':    # 如果在当前模块/文件下执行，将会指定下述代码
  125.     dataSet, labels=createDataSet()
  126.     decisionTree=createTree(dataSet, labels)
  127.     print(f"\ndecisionTree={decisionTree}\n")     # 输出决策树模型结果
  128.     # 验证集
  129.     features=  ['色泽','根蒂','敲声','纹理','脐部','触感']  # 特征列表     
  130.     testSample=['浅白','蜷缩','浊响','清晰','凹陷','硬滑']  # 待测样本
  131.     print(f"测试结果1sampleLabel= {classify(decisionTree,features,testSample)}\n")   # 输出测试结果
  132.  
  133.     features=  ['色泽','根蒂','敲声','纹理','脐部','触感']  # 特征列表     
  134.     testSample=['浅白','硬挺','清脆','模糊','平坦','硬滑']  # 待测样本
  135.     print(f"测试结果2sampleLabel= {classify(decisionTree,features,testSample)}\n")   # 输出测试结果
  136.  
  137.     features=  ['色泽','根蒂','敲声','纹理','脐部','触感']  # 特征列表     
  138.     testSample=['浅白','蜷缩','浊响','模糊','平坦','硬滑']  # 待测样本
  139.     print(f"测试结果3sampleLabel= {classify(decisionTree,features,testSample)}\n")   # 输出测试结果

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/398667
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号