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、对于子集下,若只含有正例或反例,直接得到判决;否则递归调用算法,再次寻找子节点
熵:表示随机变量的不确定性。
条件熵:在一个条件下,随机变量的不确定性。
信息增益:熵 - 条件熵,在一个条件下,信息不确定性减少的程度。
用信息增益最大的属性作为结点,是因为最终去不去打球的不确定性,在获得该属性的结果后,不确定性大大降低。
也就是说,该属性对于打球的选择很重要。
对于解决上述问题,
首先,计算系统熵,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
此时,可以画出部分决策树:
其中,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
结果:
当然,你也可以进行预测判断:
print estimator.predict([['rain', 'mild', 'high', 'strong']])
决策树算法(ID3)的更多相关文章
-
决策树算法——ID3
决策树算法是一种有监督的分类学习算法.利用经验数据建立最优分类树,再用分类树预测未知数据. 例子:利用学生上课与作业状态预测考试成绩. 上述例子包含两个可以观测的属性:上课是否认真,作业是否认真,并以 ...
-
【面试考】【入门】决策树算法ID3,C4.5和CART
关于决策树的purity的计算方法可以参考: 决策树purity/基尼系数/信息增益 Decision Trees 如果有不懂得可以私信我,我给你讲. ID3 用下面的例子来理解这个算法: 下图为我们 ...
-
数据挖掘 决策树算法 ID3 通俗演绎
决策树是对数据进行分类,以此达到预測的目的.该决策树方法先依据训练集数据形成决策树,假设该树不能对全部对象给出正确的分类,那么选择一些例外添�到训练集数据中,反复该过程一直到形成正确的决策集.决策树代 ...
-
ID3决策树算法原理及C++实现(其中代码转自别人的博客)
分类是数据挖掘中十分重要的组成部分.分类作为一种无监督学习方式被广泛的使用. 之前关于"数据挖掘中十大经典算法"中,基于ID3核心思想的分类算法C4.5榜上有名.所以不难看出ID3 ...
-
决策树算法原理(ID3,C4.5)
决策树算法原理(CART分类树) CART回归树 决策树的剪枝 决策树可以作为分类算法,也可以作为回归算法,同时特别适合集成学习比如随机森林. 1. 决策树ID3算法的信息论基础 1970年昆兰找 ...
-
python机器学习笔记 ID3决策树算法实战
前面学习了决策树的算法原理,这里继续对代码进行深入学习,并掌握ID3的算法实践过程. ID3算法是一种贪心算法,用来构造决策树,ID3算法起源于概念学习系统(CLS),以信息熵的下降速度为选取测试属性 ...
-
ID3和C4.5分类决策树算法 - 数据挖掘算法(7)
(2017-05-18 银河统计) 决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来判断其可行性的决策分析方法,是直观运用概率分析的一种图解法.由于这种决策分支画 ...
-
机器学习-ID3决策树算法(附matlab/octave代码)
ID3决策树算法是基于信息增益来构建的,信息增益可以由训练集的信息熵算得,这里举一个简单的例子 data=[心情好 天气好 出门 心情好 天气不好 出门 心情不好 天气好 出门 心情不好 天气不好 ...
-
day-8 python自带库实现ID3决策树算法
前一天,我们基于sklearn科学库实现了ID3的决策树程序,本文将基于python自带库实现ID3决策树算法. 一.代码涉及基本知识 1. 为了绘图方便,引入了一个第三方treePlotter模块进 ...
-
机器学习回顾篇(7):决策树算法(ID3、C4.5)
.caret, .dropup > .btn > .caret { border-top-color: #000 !important; } .label { border: 1px so ...
随机推荐
-
WPF入门教程系列五——Window 介绍
一.窗体类基本概念 对于WPF应用程序,在Visual Studio和Expression Blend中,自定义的窗体均继承System.Windows.Window类.用户通过窗口与 Windows ...
-
(转)yarn 集群部署,遇到的问题小结
link:http://blog.csdn.net/uniquechao/article/details/26449761 版本信息: hadoop 2.3.0 hive 0.11.0 1. ...
-
iOS-AFNetworking-上传图片
一.AFNetworking上传图片 /** 需要Demo,可留言 */ 1.利用AFnetworking上传图片. 2.注意将UIImage类型转化为NSData类型,传给后台. 二.Demo // ...
-
log4j输出日志乱码(转)
log4j日志文件乱码问题的解决方法 log4j日志文件中文乱码处理方法 log4j 控制台和文件输出乱码问题解决 写在前面,第三篇文章中将原因解释的最清楚,为什么设置为UTF-8或者GBK就生效了, ...
-
hdu4639 hehe ——斐波纳契数列,找规律
link:http://acm.hdu.edu.cn/showproblem.php?pid=4639 refer to: http://blog.csdn.net/dongdongzhang_/ar ...
-
css笔记--web端小于1px设计的处理方法
HTML代码 <!DOCTYPE html> <html> <head lang="en"> <meta charset="UT ...
-
为编写网络爬虫程序安装Python3.5
1. 下载Python3.5.1安装包1.1 进入python官网,点击menu->downloads,网址:https://www.python.org/downloads/ 1.2 根据系统 ...
-
Mac 实用工具
命令行常用工具: Iterm2 也是一个终端命令行工具,支持多工作区,使用清爽 http://www.iterm2.com/documentation.html 给你的命令行 代码上色 Solariz ...
-
AsyncTask学习
在学习Android的时候,开始用到比较多的异步处理的类大概就是AsyncTask,但是我们很多时候只知道调用,却不知道思考一些东西. 本文就简单的总结和分析了一些AsyncTask的知识. 一.As ...
-
锐捷Linux版的下载和使用(福大客户端)
下载锐捷程序包 点此下载 没有连接到锐捷里就进不了这个安装包的官方下载界面(好矛盾啊这个),所以我把它上传到博客园了. 解压文件 schaepher:~$ cd Downloads/ schaephe ...