决策树算法(ID3)

时间:2022-09-25 13:33:46

Day

Outlook

Temperature

Humidity

Wind

PlayTennis

1

Sunny

Hot

High

Weak

No

2

Sunny

Hot

High

Strong

No

3

Overcast

Hot

High

Weak

Yes

4

Rain

Mild

High

Weak

Yes

5

Rain

Cool

Normal

Weak

Yes

6

Rain

Cool

Normal

Strong

No

7

Overcast

Cool

Normal

Strong

Yes

8

Sunny

Mild

High

Weak

No

9

Sunny

Cool

Normal

Weak

Yes

10

Rain

Mild

Normal

Weak

Yes

11

Sunny

Mild

Normal

Strong

Yes

12

Overcast

Mild

High

Strong

Yes

13

Overcast

Hot

Normal

Weak

Yes

14

Rain

Mild

High

Strong

No

对于上面例子,如何判断是否要去playtennis?

可以采用决策树的方式。

决策树是一种以实例为基础的归纳学习算法。从无序列/无规则的数据中,推导出树形表示的分类判决。

优点:计算量小、显示清晰

缺点:容易过拟合(需要修枝)(譬如,使用day做判决,一一对应虽然很准确,但是不能用在其他地方)、对时间顺序的数据,需要过多预处理工作

ID3算法:

1、对于实例,计算各个属性的信息增益

2、对于信息增益最大的属性P作为根节点,P的各个取值的样本作为子集进行分类

3、对于子集下,若只含有正例或反例,直接得到判决;否则递归调用算法,再次寻找子节点

决策树算法(ID3)

熵:表示随机变量的不确定性。

条件熵:在一个条件下,随机变量的不确定性。

信息增益:熵 - 条件熵,在一个条件下,信息不确定性减少的程度。

用信息增益最大的属性作为结点,是因为最终去不去打球的不确定性,在获得该属性的结果后,不确定性大大降低。

也就是说,该属性对于打球的选择很重要。

对于解决上述问题,

首先,计算系统熵,PlayTennis

P(No) = 5/14

P(Yes) = 9/14

Entropy(S) = -(9/14)*log(9/14)-(5/14)*log(5/14) = 0.94

然后,计算各个属性的熵。

譬如:Wind

其中,Wind中取值为weak的记录有8条,其中,playtennis的正例6个,负例2个;取值为strong的记录有6条,正例为3个,负例为3个。

Entrogy(weak) = -(6/8)*log(6/8)-(2/8)*log(2/8) = 0.811

Entrogy(strong) = -(3/6)*log(3/6)-(3/6)*log(3/6) = 1.0

对应的信息增益为:

Gain(Wind) = Entropy(S) – (8/14)* Entrogy(weak)-(6/14)* Entrogy(strong) = 0.048

同理,Gain(Humidity = 0.151;Gain(Outlook = 0.247;Gain(Temperature = 0.029

此时,可以得到跟节点为:Outlook

对应点决策树:

Outlook分为三个集合:

Sunny:{1,2,8,9,11},正例:2、反例:3

Overcast:{3,7,12,13},正例:4、反例:0

Rain:{4,5,6,10,14},正例:3、反例:2

至此,可以得到:

Sunny:

Day

Outlook

Temperature

Humidity

Wind

PlayTennis

1

Sunny

Hot

High

Weak

No

2

Sunny

Hot

High

Strong

No

8

Sunny

Mild

High

Weak

No

9

Sunny

Cool

Normal

Weak

Yes

11

Sunny

Mild

Normal

Strong

Yes

Entropy(S) = -(3/5)*log(3/5)-(2/5)*log(2/5) = 0.971

对于Wind,weak时,正例为1,反例为2;Strong时,正例为1,反例为1.

Entrogy(weak) = -(1/3)*log(1/3)-(2/3)*log(2/3) = 0.918

Entrogy(strong) = -(1/2)*log(1/2)-(1/2)*log(1/2) = 1

Gain(Wind) = Entropy(S) – 3/5* Entrogy(weak)-2/5* Entrogy(strong) = 0.0202

同理,Gain(Humidity) = 0.971;Gain(Temperature) = 0.571

此时,可以画出部分决策树:

决策树算法(ID3)

其中,python代码:

import math
#香农公式计算信息熵
def calcShannonEnt(dataset):
numEntries = len(dataset)
labelCounts = {}
for featVec in dataset:
currentLabel = featVec[-1]#最后一位表示分类
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] +=1 shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob*math.log(prob, 2)
return shannonEnt def CreateDataSet():
dataset = [['sunny', 'hot','high','weak', 'no' ],
['sunny', 'hot','high','strong', 'no' ],
['overcast', 'hot','high','weak', 'yes' ],
['rain', 'mild','high','weak', 'yes' ],
['rain', 'cool','normal','weak', 'yes' ],
['rain', 'cool','normal','strong', 'no' ],
['overcast', 'cool','normal','strong', 'yes' ],
['sunny', 'mild','high','weak', 'no' ],
['sunny', 'cool','normal','weak', 'yes' ],
['rain', 'mild','normal','weak', 'yes' ],
['sunny', 'mild','normal','strong', 'yes' ],
['overcast', 'mild','high','strong', 'yes' ],
['overcast', 'hot','normal','weak', 'yes' ],
['rain', 'mild','high','strong', 'no' ],
]
labels = ['outlook', 'temperature', 'humidity', 'wind']
return dataset, labels
#选取属性axis的值value的样本表
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec) return retDataSet
#选取信息增益最大的属性作为节点
def chooseBestFeatureToSplit(dataSet):
numberFeatures = len(dataSet[0])-1
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeature = -1
for i in range(numberFeatures):
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
newEntropy =0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy
if(infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature
#对于属性已经用完,仍然没有分类的情况,采用投票表决的方法
def majorityCnt(classList):
classCount ={}
for vote in classList:
if vote not in classCount.keys():
classCount[vote]=0
classCount[vote] += 1
return max(classCount) def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet]
#类别相同停止划分
if classList.count(classList[0])==len(classList):
return classList[0]
#属性用完,投票表决
if len(dataSet[0])==1:
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(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[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree myDat,labels = CreateDataSet()
tree = createTree(myDat,labels)
print tree

  

在计算决策树的时候,sklearn库提供了决策树的计算方法(tree),但是,这个库提供的是:

scikit-learn uses an optimised version of the CART algorithm.

对于本文中使用的ID3算法是不支持的。

然而https://pypi.python.org/pypi/decision-tree-id3/0.1.2

该库支持ID3算法。

按照官网说明,注意安装时的依赖库的版本,该升级的升级,该安装的安装即可。‘

from id3 import Id3Estimator
from id3 import export_graphviz X = [['sunny', 'hot', 'high', 'weak'],
['sunny', 'hot', 'high', 'strong'],
['overcast', 'hot', 'high', 'weak'],
['rain', 'mild', 'high', 'weak'],
['rain', 'cool', 'normal', 'weak'],
['rain', 'cool', 'normal', 'strong'],
['overcast', 'cool', 'normal', 'strong'],
['sunny', 'mild', 'high', 'weak'],
['sunny', 'cool', 'normal', 'weak'],
['rain', 'mild', 'normal', 'weak'],
['sunny', 'mild', 'normal', 'strong'],
['overcast', 'mild', 'high', 'strong'],
['overcast', 'hot', 'normal', 'weak'],
['rain', 'mild', 'high', 'strong'],
]
Y = ['no','no','yes','yes','yes','no','yes','no','yes','yes','yes','yes','yes','no']
f = ['outlook','temperature','humidity','wind']
estimator = Id3Estimator()
estimator.fit(X, Y,check_input=True)
export_graphviz(estimator.tree_, 'tree.dot', f)

  然后通过GraphViz工具生成PDF

dot -Tpdf tree.dot -o tree.pdf

  结果:

决策树算法(ID3)

当然,你也可以进行预测判断:

print estimator.predict([['rain',     'mild',  'high',   'strong']])

  决策树算法(ID3)

决策树算法(ID3)的更多相关文章

  1. 决策树算法——ID3

    决策树算法是一种有监督的分类学习算法.利用经验数据建立最优分类树,再用分类树预测未知数据. 例子:利用学生上课与作业状态预测考试成绩. 上述例子包含两个可以观测的属性:上课是否认真,作业是否认真,并以 ...

  2. 【面试考】【入门】决策树算法ID3,C4.5和CART

    关于决策树的purity的计算方法可以参考: 决策树purity/基尼系数/信息增益 Decision Trees 如果有不懂得可以私信我,我给你讲. ID3 用下面的例子来理解这个算法: 下图为我们 ...

  3. 数据挖掘 决策树算法 ID3 通俗演绎

    决策树是对数据进行分类,以此达到预測的目的.该决策树方法先依据训练集数据形成决策树,假设该树不能对全部对象给出正确的分类,那么选择一些例外添�到训练集数据中,反复该过程一直到形成正确的决策集.决策树代 ...

  4. ID3决策树算法原理及C++实现(其中代码转自别人的博客)

    分类是数据挖掘中十分重要的组成部分.分类作为一种无监督学习方式被广泛的使用. 之前关于"数据挖掘中十大经典算法"中,基于ID3核心思想的分类算法C4.5榜上有名.所以不难看出ID3 ...

  5. 决策树算法原理(ID3,C4.5)

    决策树算法原理(CART分类树) CART回归树 决策树的剪枝 决策树可以作为分类算法,也可以作为回归算法,同时特别适合集成学习比如随机森林. 1. 决策树ID3算法的信息论基础   1970年昆兰找 ...

  6. python机器学习笔记 ID3决策树算法实战

    前面学习了决策树的算法原理,这里继续对代码进行深入学习,并掌握ID3的算法实践过程. ID3算法是一种贪心算法,用来构造决策树,ID3算法起源于概念学习系统(CLS),以信息熵的下降速度为选取测试属性 ...

  7. ID3和C4.5分类决策树算法 - 数据挖掘算法(7)

    (2017-05-18 银河统计) 决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来判断其可行性的决策分析方法,是直观运用概率分析的一种图解法.由于这种决策分支画 ...

  8. 机器学习-ID3决策树算法(附matlab/octave代码)

    ID3决策树算法是基于信息增益来构建的,信息增益可以由训练集的信息熵算得,这里举一个简单的例子 data=[心情好 天气好  出门 心情好 天气不好 出门 心情不好 天气好 出门 心情不好 天气不好 ...

  9. day-8 python自带库实现ID3决策树算法

    前一天,我们基于sklearn科学库实现了ID3的决策树程序,本文将基于python自带库实现ID3决策树算法. 一.代码涉及基本知识 1. 为了绘图方便,引入了一个第三方treePlotter模块进 ...

  10. 机器学习回顾篇(7):决策树算法(ID3、C4.5)

    .caret, .dropup > .btn > .caret { border-top-color: #000 !important; } .label { border: 1px so ...

随机推荐

  1. WPF入门教程系列五——Window 介绍

    一.窗体类基本概念 对于WPF应用程序,在Visual Studio和Expression Blend中,自定义的窗体均继承System.Windows.Window类.用户通过窗口与 Windows ...

  2. (转)yarn 集群部署,遇到的问题小结

    link:http://blog.csdn.net/uniquechao/article/details/26449761   版本信息: hadoop 2.3.0  hive 0.11.0   1. ...

  3. iOS-AFNetworking-上传图片

    一.AFNetworking上传图片 /** 需要Demo,可留言 */ 1.利用AFnetworking上传图片. 2.注意将UIImage类型转化为NSData类型,传给后台. 二.Demo // ...

  4. log4j输出日志乱码(转)

    log4j日志文件乱码问题的解决方法 log4j日志文件中文乱码处理方法 log4j 控制台和文件输出乱码问题解决 写在前面,第三篇文章中将原因解释的最清楚,为什么设置为UTF-8或者GBK就生效了, ...

  5. hdu4639 hehe ——斐波纳契数列,找规律

    link:http://acm.hdu.edu.cn/showproblem.php?pid=4639 refer to: http://blog.csdn.net/dongdongzhang_/ar ...

  6. css笔记--web端小于1px设计的处理方法

    HTML代码 <!DOCTYPE html> <html> <head lang="en"> <meta charset="UT ...

  7. 为编写网络爬虫程序安装Python3&period;5

    1. 下载Python3.5.1安装包1.1 进入python官网,点击menu->downloads,网址:https://www.python.org/downloads/ 1.2 根据系统 ...

  8. Mac 实用工具

    命令行常用工具: Iterm2 也是一个终端命令行工具,支持多工作区,使用清爽 http://www.iterm2.com/documentation.html 给你的命令行 代码上色 Solariz ...

  9. AsyncTask学习

    在学习Android的时候,开始用到比较多的异步处理的类大概就是AsyncTask,但是我们很多时候只知道调用,却不知道思考一些东西. 本文就简单的总结和分析了一些AsyncTask的知识. 一.As ...

  10. 锐捷Linux版的下载和使用(福大客户端)

    下载锐捷程序包 点此下载 没有连接到锐捷里就进不了这个安装包的官方下载界面(好矛盾啊这个),所以我把它上传到博客园了. 解压文件 schaepher:~$ cd Downloads/ schaephe ...