python绘制决策树,决策树的matlab实现
它是决策树机器学习中的一种常用算法,也是监督学习的一种。字面上也很好理解。与支持向量机(SVM)和神经网络等其他算法相比,决策树似乎更“接近”。
优点:计算复杂度不高,输出结果简单易懂,对中间值缺失值不敏感,可以处理无关的特征数据。
缺点:可能会出现过匹配。
使用数据类型:数值型和名义型。
因为简介的原因,我们用一个例子让决策树“未知”。
有一天,老师问我如何仅凭头发和声音判断同学的性别。
为了解决这个问题,同学们迅速统计了7个同学的特点。数据如下。
头发
声音
性别
非常长
厚的
男人
非常短
厚的
男人
非常短
厚的
男人
非常长
微薄的
妇女
非常短
微薄的
妇女
非常短
厚的
妇女
非常长
厚的
妇女
非常长
厚的
妇女
机智的同学a认为。首先,根据头发判断。如果不能,通过声音判断。画下图。
于是,一个简单直观的决策树出现了。头发长,声音粗的男人;长发细声的那个是女生;头发短声音粗的是男生;短发声音细的那个是女生。
这是机器学习中的决策树。这太简单了。
这时候同学B又出现了,他想先用声音判断,再用头发判断,大摇大摆的画决策树。
b的决策树:首先判断声音,声音细的女生;声音粗长头发的是男生;声音粗长头发的那个是女生。
问题是,同学A的决策树好还是同学B的决策树好?在制作计算机决策树时,对于多个特征,应该用哪个特征作为最佳区分特征?
数据集划分的一个主要原则就是让无序的数据变得更加有序。
分割数据集的方法有很多,但每种方法都有其优缺点。因此,如果可以度量数据的复杂度,那么按照某个特征分类的数据复杂度会比按照特征分类的数据复杂度降低更多,这个特征会被认为是最好的分类特征。
克劳德香农定义了熵和信息增益。
熵用来表示信息的复杂性。熵越大,信息越复杂。公式如下。
“信息增益”是指两个信息熵之差。
首先,计算分类前的熵。有8名学生,3名男性,5名女性。
熵(总数)(-3/8 log2)3/8)-5/8 log2)5/8)=0.9544
接下来分别计算同学A和同学B的信息熵。
老师首先将头发分类。结果长发中有1男3女。有两男两女留着短发。
熵(同学A有长发)(-1/4 log2)1/4)-3/4 log2)3/4)=0.8113
熵(同学A是短发)(-2/4log2 )2/4)-2/4log2 )2/4)=1
熵(同学a )=4/80.8113 4/81=0.9057
信息增益(同学a )=熵(总)-熵(同学a )=0.9544-0.9057=0.0487
同样,按照同学B的方法,首先根据声音的特点,分类的结果是粗音三男三女。纤细的声音里有0男2女。
熵(同学B声音粗)(-3/6log2 )3/6)-3/6log2(3/6)=1
熵(同学B声音粗)=-2/2log2 )2/2)=0
熵(同学b )=6/81 2/8*0=0.75
信息增益(同学b )=熵)总)-熵)同学b )=0.9544-0.75=0.2087
同学B的方法中,首先根据语音特征进行分类,信息增益大,区分样本能力强,具有代表性。
以上是决策树ID3算法的核心思想。
然后用python代码实现ID3算法。
从math导入日志
进口经营者
计算差异交换(数据):#数据的熵
Num entries=len (data) #数据条目数
labelCounts={}
对于数据集中的featVec:
Current=featvec [-1] #每行数据的最后一个字(类别)
ifcurrentlabelnotinlabelcounts . keys():
count[当前标签]=0
LabelCounties [current label]=1 #有几个类,统计每个类的个数。
可汗
onEnt=0
对于标签帐户中的密钥:
prob=float(labe counts[key])/numentries #计算单个类的熵
ShannonEnt-=prob*log(prob,2) #累加每个类的熵。
返回shannonEnt
Def createDataSet1(): #创建样本数据
数据集=[[长,粗,公],
[短,粗,男],
[短,粗,男],
[长,瘦,女],
[矮,瘦,女],
[短,粗,女],
[长,粗,母],
[长,粗,母]]
Labels=[头发,声音] #两个功能
返回数据集,标签
定义分割数据集(数据集,轴,值):#按特定特征分类的数据
retDataSet=[]
对于数据集中的featVec:
if featVec[轴]==值:
reducedFeatVec=featVec[:axis]
reducedfeatvec . extend(featVec[轴1:])
ret dataset . append(reducedFeatVec)
返回retDataSet
DEF ChooseBestFeaturesSplit(dataset):#选择最佳分类特征。
numFeatures=len(dataSet[0])-1
Baseentropy=calcshannonent(数据集)#原始熵
bestInfoGain=0
bestFeature=-1
对于范围内的I(num features):
featList=[example[i]数据集中的示例]
uniqueVals=set(featList)
新熵=0
对于唯一值:
subDataSet=splitDataSet(数据集,I,值)
prob=len(子数据集)/float(len(数据集))
新熵=prob * calcshannonent(子数据集)#按特征分类后的熵
增益=基础熵-新熵#原始熵和根据特征分类的熵之间的差
If (infoGainbestInfoGain): #如果除以某个特征后熵值下降最多,则该子特征为最佳分类特征。
bestInfoGain=信息增益
bestFeature=i
返回最佳功能
Def majorityCnt(classList): #按分类后的类别数排序,比如最终分类为2男1女,则判定为男性;
classCount={}
对于类别列表中的投票:
如果vote不在classCount.keys()中:
classCount[vote]=0
classCount[vote]=1
sortedClassCount=sorted(class count . items(),key=operator.itemgetter(1),reverse=True)
返回sortedClassCount[0][0]
定义创建树(数据集,标签):
Class list=[example [-1]例如在数据集中] #类别:男性或女性
if class list . count(class list[0])==len(class list):
返回类列表[0]
if len(dataSet[0])==1:
返回majorityCnt(classList)
best fat=ChooseBestFeaturesSplit(dataset)#选择最佳特征
bestFeatLabel=labels[bestFeat]
我的树={bestefatlabel: {}} #分类结果以字典形式保存。
del(标签[最佳成绩])
featValues=[example[bestFeat]数据集中的示例]
唯一值=集合(特征值)
对于唯一值:
子标签=标签[:]
myTree[bestFeatLabel][value]=create tree(split dataset \
(数据集,最佳特征,值),子标签)
返回我的树
if __name__==__main__ :
Dataset,labels=createDataset1 () #创建列数据
Print(创建树(数据集,标签))#输出决策树模型结果
输出是:
{ 声音:{ 薄:女,厚:{ 头发:{ 短:男,长:女 }}}
这个结果的意义是:第一,按照声音分类,声音对女生来说没问题;然后按照头发分类:声音粗,男生短发;声音粗,头发长对于女生来说。
这个结果也是同学b的结果。
注:判断分类结束的依据是,根据某一特征分类后,如果出现最终类别(男性或女性),则判定分类结束。使用这种方法,在数据量大、特征多的情况下,容易造成过拟合,需要进行决策分支剪枝。分支剪枝法一般是在根据某个特征分类后的熵小于设定值时停止分类。
ID算法的缺点:
在选择根节点和内部节点中的分支属性时,ID算法使用信息增益作为评价标准。信息增益的缺点是倾向于选择值多的属性。在某些情况下,这些属性可能不会提供太多有价值的信息。
ID3算法只能为描述属性离散的数据集构造决策树。
为了改进决策树,提出了ID4.5算法和CART算法。后面会介绍这两种算法。
参考:
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。