决策树算法(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)
blank

相关推荐

  • JS大数运算_大数阶乘运算

    JS大数运算_大数阶乘运算/***大数与或操作*/global.andorOpera=function(a,b,type){//type=1是与运算,type=2是或运算,默认是与运算a=a+””;b=b+””;varaStr=toBin(a);varbStr=toBi

  • QT是什么?

    QT是什么?了解QT踏上开发这条路已经有好几年了,通过这些年的学习,自己也总结了一些基础的知识,在这里,跟大家分享下。QT是什么1.Qt是一个1991年由奇趣科技开发的跨平台C++图形用户界面应用程序开发框架。它既可以开发GUI程序,也可用于开发非GUI程序,比如控制台工具和服务器。2、Qt是面向对象的框架,使用特殊的代码生成扩展(称为元对象编译器(MetaObject

  • POJ3617 Best Cow Line 馋

    POJ3617 Best Cow Line 馋

  • 手机打开照相机_安卓11调用第三方相机

    手机打开照相机_安卓11调用第三方相机打开相机布局代码<Buttonandroid:id=”@+id/take_photo”android:layout_width=”match_parent”android:layout_height=”wrap_content”android:layout_gravity=”center”android:text=”打开相机”/><Buttonandroid:id=”@+id/chose_photo”andro

  • Maven 菜鸟教程 1 安装和配置[通俗易懂]

    Maven 菜鸟教程 1 安装和配置[通俗易懂]统一管理jar文件,自动处理jar文件之间的依赖关系统一项目的目录结构,对于不同IDE软件(如Eclipse,IntelliJIDEA)是透明的自动构建:打包,部署,升级jar文件简单方便

  • javascript按位异或(^)[通俗易懂]

    javascript按位异或(^)[通俗易懂]varnum1=25;varnum2=3;alert(num1^num2);//输出:26;对两个数值的二进制写法进行比较,只有当相同位置上的数字只有一个1时,才返回1,有两个1或者都是0则返回0,然后转换成十进制数值;

发表回复

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

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