基于ID3算法生成决策树

2024-03-18 10:38
文章标签 算法 生成 决策树 id3

本文主要是介绍基于ID3算法生成决策树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

决策树的类型有很多,有CART、ID3和C4.5等,其中CART是基于基尼不纯度(Gini)的,而ID3和C4.5都是基于信息熵的,它们两个得到的结果都是一样的,本次定义主要针对ID3算法。

在构造决策树时,第一个问题就是:当前的那个特征在划分数据是起着决定性的作用。为了找到决策性的特征必须对每个特征进行评估。因此本文针对ID3算法使用的信息熵方法划分数据的特征来进行实验。

信息熵

如果待分类的的事物有多种,比如有A,B,C三类,则A的信息为:

X(a)=-lon2(p(a)),即log以2为底的a出现的概率。

而熵的定义为信息的期望值,即:

这里写图片描述

在划分数据前和划分数据后信息方式的变化称为信息增益。因此我们找出信息增益最大的一个特征用来划分数据集。ID3的原理即使Gain达到最大值。信息增益即为熵的减少或者是数据无序度的减少.

计算信息熵

计算的公式见上图,在计算是要统计每个类别出现的次数,然后用公式去计算即可。
如求下列数据的信息熵,dataset为数据集,最后一列为类别,前两列为特征。

dataSet=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]
def calShannon(dataSet):    #这里的dataset为python列表形式m=len(dataSet)          #得到样本个数labelCount={}for featVec in dataSet:  #遍历每一个样本label=featVec[-1]    #这里最后一列为样本的类别if label not in labelCount.keys():labelCount[label]=0labelCount[label]+=1shan=0.0for key in labelCount:prob=float(labelCount[key])/mshan -=prob * math.log(prob,2)print ("the shannon is %f " % shan) return shan

将上述代码保存到tree.py中,然后运行,即可计算此数据的信息熵

>>> import tree
>>> dataSet=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]
>>> tree.calShannon(dataSet)
the shannon is 0.970951 
0.9709505944546686

划分数据集

按给定的特征划分数据集:

#特别注意这里的nFeat,所选择的数据特征,value为这个特征里的值
def split(dataSet,nFeat,value):         #the num of feature ,and using value to split,datasetretData=[]for featVec in dataSet:   #遍历样本if featVec[nFeat]==value:  reducedVec=featVec[:nFeat]reducedVec.extend(featVec[nFeat+1:])  #this mean reduce the featureretData.append(reducedVec)return retData

运行结果如下:

#第0个特征,值为1,返回的是去掉第0个特征后剩余的样本
>>> tree.split(dataSet,0,1)  
[[1, 'yes'], [1, 'yes'], [0, 'no']]
>>> tree.split(dataSet,1,1)
[[1, 'yes'], [1, 'yes'], [0, 'no'], [0, 'no']]

这里需要重点理解一下:

我如果选择第0个特征进行划分,那么在第0个特征中有许多不同的值,那么,应该计算这些不同值划分过后的信息熵之和,为以第0个特征划分后的信息熵。

举个例子,如果要以第0个特征划分数据,在第0个数据上有2个不同的值分别为0,1那么应该将数据划分为两部分,调用两次tree.split(dataSet,0,1),
tree.split(dataSet,0,0),然后分别求出他们的信息熵,再求和,就是最后所得的信息熵了。

因此理解上述的过程后,即可实现如何才是最好的样本划分方式:
这里解释一下: featList = [example[i] for example in dataSet]

python中的列表推到式,其中dataSet为样本,example每次取出一个样本,然后将这个样本的exampe[i]即第i个元素加到featlist中。
即此句的作用是快速的取出样本中第i个特征的所有值。

def chooseBestFeature(dataSet):numFeatures = len(dataSet[0]) - 1      #the last column is used for the labelsbaseEntropy = calShannon(dataSet)  # the origin shannonbestInfoGain = 0.0; bestFeature = -1for i in range(numFeatures):        #iterate over all the featuresfeatList = [example[i] for example in dataSet]#create a list of all the examples of this featureuniqueVals=set(featList) # have how many value in this featurenewShannon=0.0for value in uniqueVals:subDataSet=split(dataSet,i,value)prob=len(subDataSet)/float(len(dataSet))newShannon +=prob*calShannon(subDataSet)infoGain=baseEntropy-newShannonif infoGain>bestInfoGain:bestInfoGain=newShannonbestFeature=ireturn bestFeature 

同样将上述代码加到tree.py中,运行得到:

>>> tree.chooseBestFeature(dataSet)
the shannon is 0.970951 
the shannon is 0.000000 
the shannon is 0.918296 
the shannon is 0.000000 
the shannon is 1.000000 
0      #即最好的特质是0,它使得信息增益最大

构建决策树

这里有几点需要说明:
1. 如果用完所有的特征仍然不能区分样本,则以投票算法返回
2. 如果为用完特征样本已经同属于一类,则直接返回
3. 递归处理

投票算法:

def majorityCnt(classList):classCount={}for vote in classList:if vote not in classCount.keys(): classCount[vote] = 0classCount[vote] += 1sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)return sortedClassCount[0][0]

这里sorted我更喜欢写成:
sorted(classCount.items(), key=lambda x:x[1], reverse=True)

构造决策树:

def createTree(dataSet,labels):classList = [example[-1] for example in dataSet]if classList.count(classList[0]) == len(classList): return classList[0]#stop splitting when all of the classes are equalif len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSetreturn majorityCnt(classList)bestFeat = chooseBestFeature(dataSet)bestFeatLabel = labels[bestFeat]myTree = {bestFeatLabel:{}}del(labels[bestFeat])featValues = [example[bestFeat] for example in dataSet]uniqueVals = set(featValues)for value in uniqueVals:subLabels = labels[:]       #copy all of labels, so trees don't mess up existing labelsmyTree[bestFeatLabel][value] = createTree(split(dataSet, bestFeat, value),subLabels)return myTree     

运行结果:

>>> data,label=tree.createDataSet()
>>> data
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> label
['no surfacing', 'flippers']
>>> myTree=tree.createTree(data,label)
the shannon is 0.970951 
the shannon is 0.000000 
the shannon is 0.918296 
the shannon is 0.000000 
the shannon is 1.000000 
the shannon is 0.918296 
the shannon is 0.000000 
the shannon is 0.000000 
>>> myTree
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

myTree是用嵌套的字典来模拟树形结构。

这篇关于基于ID3算法生成决策树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/822079

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人,是不是经常需要制作各种PPT来分享我的生活和想法。但是,你们知道,有时候灵感来了,时间却不够用了!😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手!🌟 什么是Kimi? 一款月之暗面科技有限公司开发的AI办公工具,帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师,Kimi都能够为你的办公文

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];