本文主要是介绍决策树(Decision Tree) | 算法实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
01 起
决策树相关的理论知识,我们在这篇文章中有详细讲解。
今天我们基于决策树原理,写一个函数来训练决策树吧。本文基于ID3算法构建决策树,此算法构建决策树的中心思想是:
始终寻找信息增益最大的特征作为当前分支的最优特征
信息增益,即:g(D,A)=H(D)-H(D|A)
02 实现思路(ID3)
利用训练数据,训练决策树,主要思路如下,共8个步骤,重点在于递归:
- 自定义信息熵计算函数,用于计算数据集的信息熵
- 自定义数据划分函数,用于根据指定特征的指定取值,划分数据集
- step2的自数据集作为输入给step1的函数,可以计算出按某指定特征的某指定取值(A=ai)划分的数据集的信息熵H(Di),同时计算按某指定特征的某指定取值(A=ai)划分的数据集的样本概率|Di|/|D|
- 遍历该特征各个取值,计算各取值下划分的数据集的信息熵H(Di)和样本概率|Di|/|D|,相乘,再求和得到得到特征A对数据集D的经验条件熵H(D|A)
- 计算特征A对数据集的信息增益g(D,A)=H(D)-H(D|A)
- 以此类推,计算各特征对数据集的信息增益,取信息增益最大的特征为最佳划分特征,得到树T1
- 对T1各结点继续step3-6,选择信息增益最大的特征,继续划分数据,得到新的决策树
- 直到信息增益小于阈值,或无特征可划分,或每个分支下的所有实例都具有相同的分类,决策树完成
下面我们基于这8个步骤的思路,给出python代码。
03 实现
step1 自定义信息熵计算函数,用于计算数据集的信息熵
"""
输入:数据集,每一行是一条数据,最后一列是各条数据集的类别
输出:该数据集的信息熵
思路:
建立一个字典,对数据集各数据的类别计数,
从而计算各类别出现频率(作为概率pi),
最后调用信息熵公式计算 H(D)=-求和(pi*logpi)
"""
def calEntropy(dataset):n=len(dataset)labelCounts={}#对数据集各数据的类别计数for data in dataset:datalabel=data[-1] #取data最后一列,类别列if datalabel not in labelCounts.keys():labelCounts[datalabel]=0labelCounts[datalabel]+=1entropy=0.0#计算各类别出现频率(作为概率pi),调用信息熵公式计算 H(D)=-求和(pi*logpi)for key in labelCounts.keys():prob=float(labelCounts[key])/nentropy -= prob*log(prob,2)return entropy
step2 自定义数据划分函数,用于根据指定特征的指定取值,划分数据集
"""
输入:数据集、特征所在列索引、特征取值
输出:满足指定特征等于指定取值的数据子集
"""
def splitDataset(dataset,index,value):subDataset=[]for data in dataset:if data[index]==value:#抽取除了data[index]的内容(一个特征用于计算其对数据集的经验条件熵时,不需要此特征在子数据集中)splitData=data[:index] #取索引之前的元素splitData.extend(data[index+1:]) #再合并索引之后的元素subDataset.append(splitData)return subDataset
step3~6 选择信息增益最大的特征作为数据集划分特征
"""
输入:数据集
输出:该数据集的最佳划分特征
"""
def chooseFeature(dataset):#初始化numFeature=len(dataset[0])-1 #因为最后一列是类别baseEntropy=calEntropy(dataset) #H(D)bestInfoGain=0.0bestFeatureIndex=-1#创建特征A各取值a的列表for i in range(numFeature):featureList=[data[i] for data in dataset]uniqueValue=set(featureList)empEntropy=0.0 #初始化特征A对数据集D的经验条件熵H(D|A)#计算特征A各取值a的信息熵H(Di)和样本概率|Di|/|D|,并相乘for value in uniqueValue:subDataset=splitDataset(dataset,i,value) #(列索引为i的特征)特征A取value值所划分的子数据集prob=len(subDataset)/float(len(dataset)) #计算|Di|/|D|empEntropy += prob*calEntropy(subDataset) #H(D|A)#取信息增益最大的特征为最佳划分特征infoGain=baseEntropy-empEntropy #信息增益if infoGain>bestInfoGain:bestInfoGain=infoGainbestFeatureIndex=ireturn bestFeatureIndex
step7~8 递归构建决策树
def majorClass(classList):classCount={}for vote in classList:if vote not in classCount.keys():classCount[vote]=0classCount[vote]+=1#对classCount按value降序排序sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)return sortedClassCount[0][0] #返回类别最大的类别名"""
输入:数据集(list类型),数据集特征列表(按在数据集的位置排序)(list类型)
输出:该数据集的决策树
思路:【递归】1. 若数据集属于同一类,则返回该类别,划分停止2. 若数据集所有特征已经遍历,返回当前计数最多的类别为该结点类别,划分停止3. 否则继续分支,调用chooseFeature()函数,选择当前数据集最优特征4. 遍历当前最优特征各属性值,划分数据集,并递归调用自身createTree()构建子数据集的决策树5. 完成
"""
def createTree(dataset,featureLabels):classList=[data[-1] for data in dataset] #取数据集各数据类别#若数据集属于同一类,则返回该类别,划分停止if classList.count(classList[0])==len(classList):return classList[0]#若数据集所有特征已经遍历,返回当前计数最多的类别为该结点类别,划分停止if len(dataset[0])==1:return majorClass(classList)#否则继续分支,调用chooseFeature()函数,选择当前数据集最优特征bestFeatureIndex=chooseFeature(dataset)bestFeature=featureLabels[bestFeatureIndex]#用于存储决策树,字典结构存储树的所有信息,并可体现包含关系desitionTree={bestFeature:{}} del(featureLabels[bestFeatureIndex]) #删除已被用于划分数据的特征#得到当前最优划分特征的各属性值featureValues=[data[bestFeatureIndex] for data in dataset]uniqueValues=set(featureValues)#遍历当前最优特征各属性值,划分数据集,并递归调用自身createTree()构建子数据集的决策树for value in uniqueValues:#得到已删除当前最优划分特征的特征列表,用于递归调用subFeatureLabels=featureLabels[:] #用当前最优划分特征的指定值分割子数据集,用于递归调用subData=splitDataset(dataset,bestFeatureIndex,value) desitionTree[bestFeature][value]=createTree(subData,subFeatureLabels)return desitionTree
至此,决策树训练函数完成,下面我们利用西瓜分类数据集来简单测试一下吧~
04 测试
西瓜分类数据集长这样,基于西瓜的各个特征,判断西瓜是好瓜还是坏瓜:
我们直接调用刚才写好的决策树训练函数,看看西瓜分类数据的决策树吧
watermalon=pd.read_csv(r"D:\python\data\watermalon.txt",sep="\t")
watermalon_list=np.array(watermalon).tolist() #构建数据集
features=watermalon.columns.tolist()[0:-1] #提取特征列表
my_tree=createTree(watermalon_list,features)
最后训练得到的决策树长这样,这是一个嵌套格式的字典,每个子字典代表了一个分支
05 总结
本文基于ID3算法,造了个轮子,给出决策树训练函数,输入列表类型的数据集和数据集的特征列表,可以数据该数据集的分类决策树,得到的决策树使用嵌套格式的字典存储。
但是,嵌套格式的字典并不直观,不能一目了然地观察决策树结构。
别担心,下期我们会就此决策树,给出函数来绘制决策树,帮助我们更加直观地理解训练出来的决策树结构。
同时,我们会在下期给出决策树的利用方法——如何利用训练好的决策树分类测试数据?
敬请期待~~
06 参考
- 《统计学习方法》 李航 Chapter5
- 《机器学习实战》 Peter Harrington Chapter3
这篇关于决策树(Decision Tree) | 算法实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!