决策树算法(ID3)

决策树算法(ID3)

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

 

<span>决策树算法(ID3)</span>

 

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

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

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

 

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

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

 

 

对于解决上述问题,

首先,计算系统熵,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

 

 

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

 

 

<span>决策树算法(ID3)</span>

 

其中,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

  结果:

<span>决策树算法(ID3)</span>

 

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

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

  <span>决策树算法(ID3)</span>

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119485.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • python中astype 存在空值_python-DataFrame.astype()错误参数

    python中astype 存在空值_python-DataFrame.astype()错误参数使用列的字典时,astype引发ValueError.我试图将大DF中的稀疏列的类型转换(从float到int).我的问题是NaN值.即使将errors参数设置为’ignore’,使用列的字典时也不会忽略它们.这是一个玩具示例:t=pd.DataFrame([[1.01,2],[3.01,10],[np.NaN,20]])t.astype({0:int},errors=’ignore’)V…

  • CQRS模式学习

    CQRS模式学习由于存在增删改与查询逻辑有差异的这个问题,为了更好的针对差异进行抽象,我们可以将它们分开进行设计。也就是我们的CQRS模式,即命令查询的责任分离CommandQueryResponsibilitySegregation模式。 简单的需求当我们系统中的数据模型层级较少时,数据模型足够简单时,模型与数据库可以直接进行映射。这种简单数据模型使我们不需要针对其相互关系进行复杂的建模设计,直接在工程中使用经典的三层模型就足以支撑项目需求。对于这种简单系统,过度设计会增加后续维护、重构的成本(并不能保

    2022年10月30日
  • 深入理解extern使用方法

    深入理解extern使用方法

  • MongoDB(六)—-MongoDB索引的额外属性

    MongoDB(六)—-MongoDB索引的额外属性

    2020年11月12日
  • Squid 代理服务之透明代理服务器架构搭建

    文章目录1.服务器配置2.Squid服务器部署2.1修改Squid配置文件2.2开启路由转发,实现本机中不同网段的地址转发2.3修改防火墙规则3.客户端访问测试1.服务器配置服务器主机名IP地址主要软件Squid服务器squid_server内网ens33:192.168.10.20|外网ens37:10.0.0.100squidWeb服务器web_server10.0.0.200apacheWin10客户端192.1

  • webservice接口与HTTP接口的使用以及区别

    webservice接口与HTTP接口的使用以及区别一、webservice的概念Web是使应用程序可以与平台和编程语言无关的方式进行相互通信的一项技术。Web服务是一个软件接口,它描述了一组可以在网络上通过标准化的XML消息传递访问的操作。它使用基于XML语言的协议来描述要执行的操作或者要与另一个Web服务交换的数据。一组以这种方式交互的Web服务在面向服务的体系结构(Service-OrientedArchitectu…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号