精华内容
下载资源
问答
  • 分类算法之决策树ID3详解
    万次阅读 多人点赞
    2017-08-19 20:19:24
    回顾决策树的基本知识,其构建过程主要有下述三个重要的问题:

         (1)数据是怎么分裂的

         (2)如何选择分类的属性

         (3)什么时候停止分裂

         从上述三个问题出发,以实际的例子对ID3算法进行阐述。

    先上问题吧,我们统计了14天的气象数据(指标包括outlook,temperature,humidity,windy),并已知这些天气是否打球(play)。如果给出新一天的气象指标数据:sunny,cool,high,TRUE,判断一下会不会去打球。

    table 1

    outlooktemperaturehumiditywindyplay
    sunnyhothighFALSEno
    sunnyhothighTRUEno
    overcasthothighFALSEyes
    rainymildhighFALSEyes
    rainycoolnormalFALSEyes
    rainycoolnormalTRUEno
    overcastcoolnormalTRUEyes
    sunnymildhighFALSEno
    sunnycoolnormalFALSEyes
    rainymildnormalFALSEyes
    sunnymildnormalTRUEyes
    overcastmildhighTRUEyes
    overcasthotnormalFALSEyes
    rainymildhighTRUEno

    这个问题当然可以用朴素贝叶斯法求解,分别计算在给定天气条件下打球和不打球的概率,选概率大者作为推测结果。

    现在我们使用ID3归纳决策树的方法来求解该问题。

    预备知识:

    (1)信息熵


    补充两个对数去处公式:

    (2) 信息增益


    用决策树来预测:

    决策树的形式类似于“如果天气怎么样,去玩;否则,怎么着怎么着”的树形分叉。那么问题是用哪个属性(即变量,如天气、温度、湿度和风力)最适合充当这颗树的根节点,在它上面没有其他节点,其他的属性都是它的后续节点。

    那么借用上面所述的能够衡量一个属性区分以上数据样本的能力的“信息增益”(Information Gain)理论。

    如果一个属性的信息增益量越大,这个属性作为一棵树的根节点就能使这棵树更简洁,比如说一棵树可以这么读成,如果风力弱,就去玩;风力强,再按天气、温度等分情况讨论,此时用风力作为这棵树的根节点就很有价值。如果说,风力弱,再又天气晴朗,就去玩;如果风力强,再又怎么怎么分情况讨论,这棵树相比就不够简洁了。

    用熵来计算信息增益:


    复制代码
    1 计算分类系统熵
    类别是 是否出去玩。取值为yes的记录有9个,取值为no的有5个,即说这个样本里有9个正例,5 个负例,记为S(9+,5-),S是样本的意思(Sample)。那么P(c1) = 9/14, P(c2) = 5/14
    这里熵记为Entropy(S),计算公式为:
    Entropy(S)= -(9/14)*log2(9/14)-(5/14)*log2(5/14)
    2 分别以Wind、Humidity、Outlook和Temperature作为根节点,计算其信息增益
    
    我们来计算Wind的信息增益
    当Wind固定为Weak时:记录有8条,其中正例6个,负例2个;
    同样,取值为Strong的记录6个,正例负例个3个。我们可以计算相应的熵为:
    Entropy(Weak)=-(6/8)*log(6/8)-(2/8)*log(2/8)=0.811
    Entropy(Strong)=-(3/6)*log(3/6)-(3/6)*log(3/6)=1.0
    现在就可以计算出相应的信息增益了:
    所以,对于一个Wind属性固定的分类系统的信息量为 (8/14)*Entropy(Weak)+(6/14)*Entropy(Strong)
    Gain(Wind)=Entropy(S)-(8/14)*Entropy(Weak)-(6/14)*Entropy(Strong)=0.940-(8/14)*0.811-(6/14)*1.0=0.048
    这个公式的奥秘在于,8/14是属性Wind取值为Weak的个数占总记录的比例,同样6/14是其取值为Strong的记录个数与总记录数之比。
    
    
    同理,如果以Humidity作为根节点:
    Entropy(High)=0.985 ; Entropy(Normal)=0.592
    Gain(Humidity)=0.940-(7/14)*Entropy(High)-(7/14)*Entropy(Normal)=0.151
    以Outlook作为根节点:
    Entropy(Sunny)=0.971 ; Entropy(Overcast)=0.0 ; Entropy(Rain)=0.971
    Gain(Outlook)=0.940-(5/14)*Entropy(Sunny)-(4/14)*Entropy(Overcast)-(5/14)*Entropy(Rain)=0.247
    以Temperature作为根节点:
    Entropy(Cool)=0.811 ; Entropy(Hot)=1.0 ; Entropy(Mild)=0.918
    Gain(Temperature)=0.940-(4/14)*Entropy(Cool)-(4/14)*Entropy(Hot)-(6/14)*Entropy(Mild)=0.029
    这样我们就得到了以上四个属性相应的信息增益值:
    Gain(Wind)=0.048 ;Gain(Humidity)=0.151 ; Gain(Outlook)=0.247 ;Gain(Temperature)=0.029
    最后按照信息增益最大的原则选Outlook为根节点。子节点重复上面的步骤。这颗树可以是这样的,它读起来就跟你认为的那样:

    ID3优点是理论清晰、方法简单、学习能力较强,但也存在一些缺点:

    (1)只能处理分类属性的数据,不能处理连续的数据;

    (2)划分过程会由于子集规模过小而造成统计特征不充分而停止;

    (3)ID3算法在选择根节点和各内部节点中的分支属性时,采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性,在有些情况下这类属性可能不会提供太多有价值的信息。

    更多相关内容
  • ID3算法(含实例)

    万次阅读 多人点赞 2018-08-27 17:38:46
    (1)ID3算法简介 (2)ID3算法节点分裂规则 (3)ID3算法实例 (4)剪枝 ------------------------------------------------------------------------------------------------------------------------- 一、...

    主要内容

    (1)ID3算法简介

    (2)ID3算法节点分裂规则

    (3)ID3算法实例

    (4)剪枝

    -------------------------------------------------------------------------------------------------------------------------

    一、简介

    1、信息熵Entropy

    H(S)=\sum p_{i}log(p_{i})

    其中为第i个类别的概率,S是样例集合

    信息熵越大,样本越混乱;信息熵越小,样本越纯净。

    2、期望信息

    设特征A具有v个不同的类别,其样本个数分别记为

    H(S|A) = \sum_{i} \frac{|c_{j}|}{|c|}p_{ij}log(p_{ij})

    E(A)特征A的期望信息,\frac{c_{j}}{c}为特征A的第j个类别的数量占特征A所有类别的概率,为特征A下第j个类别中占样例集合S不同类别的概率

    3、信息增益

    H(S|A)为特征A的信息增益

    G_{A}(S) = H(S) - H(S|A)

    信息熵越小,信息增益越大,样本越纯净

    选择信息增益最大的特征作为分裂标准

    二、实例

    1、样本(特征必须离散变量,支持多特征、多分类)

    1024个样本,4个特征,2个分类

    计数年龄收入学生信誉是否购买
    64
    64
    128
    60
    64
    64
    64
    128
    64
    132
    64
    32
    32
    64

    2、计算信息熵

    H\left ( S \right ) =- \sum_{i}p_{i}log(p_{i}) = -\frac{384}{1024}*log\left ( \frac{384}{1024} \right )- \frac{1024-384}{1024}*log\left ( \frac{1024-384}{1024} \right ) =0.9544

    3、计算特征A的信息熵

    假设以年龄为例:

    分为青年:384/0.375(样本/概率)、中年:256/0.25(样本/概率)、老年:384/0.375(样本/概率)

    以年龄为特征的熵为:

    H(S|A) =0.375*H(S|A_{1})+0.25*H(S|A_{2})+0.375*H(S|A_{3})

    青年:128/256(买/不买),概率为1/3和2/3(买/不买)

    H(S|A_{1})=-[\frac{1}{3}*log(\frac{1}{3})+\frac{2}{3}*log(\frac{2}{3})]=0.9149

    中年:256/0(买/不买),概率为1和0(买/不买)

    H(S|A_{2})=-[0*log(0)+1*log(1)]=0

    老年:256/128(买/不买),概率为2/3和1/3(买/不买)

    H(S|A_{3})=-[\frac{2}{3}*log(\frac{2}{3})+\frac{1}{3}*log(\frac{1}{3})]=0.9149

    故得到以年龄为特征的熵(平均信息期望/条件熵)为

    H(S|A) =0.375*H(S|A_{1})+0.25*H(S|A_{2})+0.375*H(S|A_{3})=0.6862

    年龄特征的信息增益为:

    G_{A}(S)=H(S)-H(S|A)=0.9544-0.6862=0.2628

    同理可得

    收入:H(S|B)=0.7811,G_{B}(S)=0.1733

    学生:H(S|C)=0.9631,G_{C}(S)=0.0183

    信誉:H(S|D)=0.9048,G_{D}(S)=0.0496

    可以看出,‘年龄’的信息增益最大,因此选择‘年龄’作为节点来划分。

    按此方法,直至叶节点为’纯‘的结束。

    三、剪枝

    树的剪枝包括预剪枝和后剪枝,通过提前停止树的构造进行剪枝的方法称为预剪枝,后剪枝是首先构造完整的决策树,然后把置信度不够节点子树替代为叶子节点的过程。

    预剪枝判断停止树的生长可以归纳为以下几种:

    1、树的高度限制:设定树的高度最大值,当达到限定值时,停止树的生长;

    2、训练样本限制:对一个拥有较少训练样本的节点进行分裂时容易出现过拟合现象,因此设定样本量阀值,当样本量少于阀值时停止生长;

    3、系统性能增益:当属性的信息增益小于某个指定的阀值时停止增长。

    相对而言预剪枝比较简单,在实际的运用中运用最广的还是后剪枝。

    后剪枝算法主要有以下几类:

    1、降低错误剪枝REP(Reduced Error Pruning);

    2、悲观错误剪枝PER(Pessimistic Error Pruning);

    3、基于错误剪枝EBP(Error-Based Pruning);

    4、代价-复杂度剪枝CCP(Cost-Complexity Pruning);

    5、最小错误剪枝MEP(Minimun Error Pruning)

    以上算法的理论介绍详见:

    http://wenku.baidu.com/view/415c3cc19ec3d5bbfd0a7464.html?re=view

    四、总结

    1、ID3算法的流程

    (1)自上而下贪婪搜索

    (2)遍历所有的属性,按照信息增益最大的属性进行分裂

    (3)根据分裂属性划分样本

    (4)重复上述流程,直至满足条件结束

    2、ID3算法的特点

    (1)上述过程可以看出,ID3算法倾向于选择属性值较多的属性,有些时候不能提供有价值的信息

    (2)贪婪性以及奥姆剃刀原理(尽量用较少的东西做更多的事)

    (3)不适用于连续变量

    (4)只能用于分类

     

    注:以上内容属个人理解,学艺不精,请各位大神多多指教

    展开全文
  • 决策树之ID3算法

    万次阅读 多人点赞 2015-03-27 00:32:39
    对于决策树来说,主要有两种算法:ID3算法和C4.5算法。C4.5算法是 对ID3算法的改进。今天主要先讲ID3算法,之后会讲C4.5算法和随机森林等。   Contents    1. 决策树的基本认识  2. ID3算法介绍  3. ...

    今天,我来讲解的是决策树。对于决策树来说,主要有两种算法:ID3算法C4.5算法。C4.5算法是

    对ID3算法的改进。今天主要先讲ID3算法,之后会讲C4.5算法随机森林等。

     

    Contents

     

         1. 决策树的基本认识

         2. ID3算法介绍

         3. 信息熵与信息增益

         4. ID3算法的C++实现

     

     

    1. 决策树的基本认识

     

       决策树是一种依托决策而建立起来的一种树。在机器学习中,决策树是一种预测模型,代表的是一种对

       象属性与对象值之间的一种映射关系,每一个节点代表某个对象,树中的每一个分叉路径代表某个可能

       的属性值,而每一个叶子节点则对应从根节点到该叶子节点所经历的路径所表示的对象的值。决策树仅

       有单一输出,如果有多个输出,可以分别建立独立的决策树以处理不同的输出。接下来讲解ID3算法。

     

     

    2. ID3算法介绍

     

       ID3算法是决策树的一种,它是基于奥卡姆剃刀原理的,即用尽量用较少的东西做更多的事。ID3算法

       即Iterative Dichotomiser 3迭代二叉树3代,是Ross Quinlan发明的一种决策树算法,这个

       算法的基础就是上面提到的奥卡姆剃刀原理,越是小型的决策树越优于大的决策树,尽管如此,也不总

       是生成最小的树型结构,而是一个启发式算法。

     

       在信息论中,期望信息越小,那么信息增益就越大,从而纯度就越高。ID3算法的核心思想就是以信息

       增益来度量属性的选择,选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍

       历可能的决策空间。

     

     

    3. 信息熵与信息增益

     

       在信息增益中,重要性的衡量标准就是看特征能够为分类系统带来多少信息,带来的信息越多,该特征越

       重要。在认识信息增益之前,先来看看信息熵的定义

     

       这个概念最早起源于物理学,在物理学中是用来度量一个热力学系统的无序程度,而在信息学里面,熵

       是对不确定性的度量。在1948年,香农引入了信息熵,将其定义为离散随机事件出现的概率,一个系统越

       是有序,信息熵就越低,反之一个系统越是混乱,它的信息熵就越高。所以信息熵可以被认为是系统有序

       化程度的一个度量。

     

       假如一个随机变量的取值为,每一种取到的概率分别是,那么

       的熵定义为

     

                 

     

       意思是一个变量的变化情况可能越多,那么它携带的信息量就越大。

     

       对于分类系统来说,类别是变量,它的取值是,而每一个类别出现的概率分别是

     

                 

     

       而这里的就是类别的总数,此时分类系统的熵就可以表示为

     

                 

     

       以上就是信息熵的定义,接下来介绍信息增益

     

       信息增益是针对一个一个特征而言的,就是看一个特征,系统有它和没有它时的信息量各是多少,两者

       的差值就是这个特征给系统带来的信息量,即信息增益

     

       接下来以天气预报的例子来说明。下面是描述天气数据表,学习目标是play或者not play

     

       

     

       可以看出,一共14个样例,包括9个正例和5个负例。那么当前信息的熵计算如下

     

       

     

       在决策树分类问题中,信息增益就是决策树在进行属性选择划分前和划分后信息的差值。假设利用

       属性Outlook来分类,那么如下图

     

       

     

          划分后,数据被分为三部分了,那么各个分支的信息熵计算如下

     

           

     

           那么划分后的信息熵为

     

            

     

            代表在特征属性的条件下样本的条件熵。那么最终得到特征属性带来的信息增益为

     

            

     

       信息增益的计算公式如下

     

       

     

       其中为全部样本集合,是属性所有取值的集合,的其中一个属性值,中属性

       值为的样例集合,中所含样例数。

     

       在决策树的每一个非叶子结点划分之前,先计算每一个属性所带来的信息增益,选择最大信息增益的属性来划

       分,因为信息增益越大,区分样本的能力就越强,越具有代表性,很显然这是一种自顶向下的贪心策略。以上

       就是ID3算法的核心思想。

     

     

    4. ID3算法的C++实现

     

       接下来开始用C++实现ID3算法,包括以下文件

     

       

     

    ID3.h

    #ifndef _ID3_H_
    #define _ID3_H_
     
    #include <utility>
    #include <list>
    #include <map>
     
    #define Type int   //样本数据类型
     
    #define   Map1        std::map< int, Type >    //定义一维map
    #define   Map2        std::map< int, Map1 >    //定义二维map
    #define   Map3        std::map< int, Map2 >    //定义三维map
    #define   Pair        std::pair<int, Type>
    #define   List        std::list< Pair >        //一维list
    #define   SampleSpace std::list< List >        //二维list 用于存放样本数据
    #define   Child       std::map< int, Node* >   //定义后继节点集合
    #define   CI          const_iterator
     
    /*
     *   在ID3算法中,用二维链表存放样本,结构为list< list< pair<int, int> > >,简记为SampleSpace,取名样本空间
     *   样本数据从根节点开始往下遍历。每一个节点的定义如下结构体
     */
     
    struct Node
    {
        int index;                    //当前节点样本最大增益对应第index个属性,根据这个进行分类的
        int type;                     //当前节点的类型
        Child next;                   //当前节点的后继节点集合
        SampleSpace sample;           //未分类的样本集合
    };
     
    class ID3{
     
    public:
     
        ID3(int );    
        ~ID3();
     
        void PushData(const Type*, const Type);   //将样本数据Push给二维链表
        void Build();                             //构建决策树
        int  Match(const Type*);                  //根据新的样本预测结果
        void Print();                             //打印决策树的节点的值
     
    private:
     
        void   _clear(Node*);
        void   _build(Node*, int);
        int    _match(const int*, Node*);
        void   _work(Node*);
        double _entropy(const Map1&, double);
        int    _get_max_gain(const SampleSpace&);
        void   _split(Node*, int);
        void   _get_data(const SampleSpace&, Map1&, Map2&, Map3&);
        double _info_gain(Map1&, Map2&, double, double);
        int    _same_class(const SampleSpace&);
        void   _print(Node*);
     
    private:
     
        int dimension;
        Node *root;
    };
     
    #endif // _ID3_H_


    ID3.cpp

    #include <iostream>
    #include <cassert>
    #include <cmath>
     
    #include "ID3.h"
     
    using namespace std;
     
    //初始化ID3的数据成员
    ID3::ID3(int dimension)
    {
        this->dimension = dimension;
     
        root = new Node();
        root->index = -1;
        root->type = -1;
        root->next.clear();
        root->sample.clear();
    }
     
    //清空整个决策树
    ID3::~ID3()
    {
        this->dimension = 0;
        _clear(root);
    }
     
    //x为dimension维的属性向量,y为向量x对应的值
    void ID3::PushData(const Type *x, const Type y)
    {
        List single;
        single.clear();
        for(int i = 0; i < dimension; i++)
            single.push_back(make_pair(i + 1, x[i]));
        single.push_back(make_pair(0, y));
        root->sample.push_back(single);
    }
     
    void ID3::_clear(Node *node)
    {
        Child &next = node->next;
        Child::iterator it;
        for(it = next.begin(); it != next.end(); it++)
            _clear(it->second);
        next.clear();
        delete node;
    }
     
    void ID3::Build()
    {
        _build(root, dimension);
    }
     
    void ID3::_build(Node *node, int dimension)
    {
        //获取当前节点未分类的样本数据
        SampleSpace &sample = node->sample;
     
        //判断当前所有样本是否是同一类,如果不是则返回-1
        int y = _same_class(sample);
     
        //如果所有样本是属于同一类
        if(y >= 0)
        {
            node->index = -1;
            node->type = y;
            return;
        }
     
        //在_max_gain()函数中计算出当前节点的最大增益对应的属性,并根据这个属性对数据进行划分
        _work(node);
     
        //Split完成后清空当前节点的所有数据,以免占用太多内存
        sample.clear();
     
        Child &next = node->next;
        for(Child::iterator it = next.begin(); it != next.end(); it++)
            _build(it->second, dimension - 1);
    }
     
    //判断当前所有样本是否是同一类,如果不是则返回-1
    int ID3::_same_class(const SampleSpace &ss)
    {
        //取出当前样本数据的一个Sample
        const List &f = ss.front();
     
        //如果没有x属性,而只有y,直接返回y
        if(f.size() == 1)
            return f.front().second;
     
        Type y = 0;
        //取出第一个样本数据y的结果值
        for(List::CI it = f.begin(); it != f.end(); it++)
        {
            if(!it->first)
            {
                y = it->second;
                break;
            }
        }
     
        //接下来进行判断,因为list是有序的,所以从前往后遍历,发现有一对不一样,则所有样本不是同一类
        for(SampleSpace::CI it = ss.begin(); it != ss.end(); it++)
        {
            const List &single = *it;
            for(List::CI i = single.begin(); i != single.end(); i++)
            {
                if(!i->first)
                {
                    if(y != i->second)
                        return -1;         //发现不是同一类则返回-1
                    else
                        break;
                }
            }
        }
        return y;     //比较完所有样本的输出值y后,发现是同一类,返回y值。
    }
     
    void ID3::_work(Node *node)
    {
        int mai = _get_max_gain(node->sample);
        assert(mai >= 0);
        node->index = mai;
        _split(node, mai);
    }
     
    //获取最大的信息增益对应的属性
    int ID3::_get_max_gain(const SampleSpace &ss)
    {
        Map1 y;
        Map2 x;
        Map3 xy;
     
        _get_data(ss, y, x, xy);
        double s = ss.size();
        double entropy = _entropy(y, s);   //计算熵值
     
        int mai = -1;
        double mag = -1;
     
        for(Map2::iterator it = x.begin(); it != x.end(); it++)
        {
            double g = _info_gain(it->second, xy[it->first], s, entropy);    //计算信息增益值
            if(g > mag)
            {
                mag = g;
                mai = it->first;
            }
        }
     
        if(!x.size() && !xy.size() && y.size())   //如果只有y数据
            return 0;
        return mai;
    }
     
    //获取数据,提取出所有样本的y值,x[]属性值,以及属性值和结果值xy。
    void ID3::_get_data(const SampleSpace &ss, Map1 &y, Map2 &x, Map3 &xy)
    {
        for(SampleSpace::CI it = ss.begin(); it != ss.end(); it++)
        {
        int c = 0;
            const List &v = *it;
            for(List::CI p = v.begin(); p != v.end(); p++)
            {
                if(!p->first)
                {
                    c = p->second;
                    break;
                }
            }
            ++y[c];
            for(List::CI p = v.begin(); p != v.end(); p++)
            {
                if(p->first)
                {
                    ++x[p->first][p->second];
                    ++xy[p->first][p->second][c];
                }
            }
        }
    }
     
    //计算熵值
    double ID3::_entropy(const Map1 &x, double s)
    {
        double ans = 0;
        for(Map1::CI it = x.begin(); it != x.end(); it++)
        {
            double t = it->second / s;
            ans += t * log2(t);
        }
        return -ans;
    }
     
    //计算信息增益
    double ID3::_info_gain(Map1 &att_val, Map2 &val_cls, double s, double entropy)
    {
        double gain = entropy;
        for(Map1::CI it = att_val.begin(); it != att_val.end(); it++)
        {
            double r = it->second / s;
            double e = _entropy(val_cls[it->first], it->second);
            gain -= r * e;
        }
        return gain;
    }
     
    //对当前节点的sample进行划分
    void ID3::_split(Node *node, int idx)
    {
        Child &next = node->next;
        SampleSpace &sample = node->sample;
     
        for(SampleSpace::iterator it = sample.begin(); it != sample.end(); it++)
        {
            List &v = *it;
            for(List::iterator p = v.begin(); p != v.end(); p++)
            {
                if(p->first == idx)
                {
                    Node *tmp = next[p->second];
                    if(!tmp)
                    {
                        tmp = new Node();
                        tmp->index = -1;
                        tmp->type = -1;
                        next[p->second] = tmp;
                    }
                    v.erase(p);
                    tmp->sample.push_back(v);
                    break;
                }
            }
        }
    }
     
    int ID3::Match(const Type *x)
    {
        return _match(x, root);
    }  
     
    int ID3::_match(const Type *v, Node *node)
    {
        if(node->index < 0)
            return node->type;
     
        Child &next = node->next;
        Child::iterator p = next.find(v[node->index - 1]);
        if(p == next.end())
            return -1;
     
        return _match(v, p->second);
    }
     
    void ID3::Print()
    {
        _print(root);
    }
     
    void ID3::_print(Node *node)
    {
        cout << "Index    = " << node->index << endl;
        cout << "Type     = " << node->type << endl;
        cout << "NextSize = " << node->next.size() << endl;
        cout << endl;
     
        Child &next = node->next;
        Child::iterator p;
        for(p = next.begin(); p != next.end(); ++p)
            _print(p->second);
    }

    main.cpp

    #include <iostream>
    #include "ID3.h"
     
    using namespace std;
     
    enum outlook {SUNNY, OVERCAST, RAIN };
    enum temp    {HOT,   MILD,     COOL };
    enum hum     {HIGH,  NORMAL         };
    enum windy   {WEAK,  STRONG         };
     
    int samples[14][4] =
    {
        {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}
    };
     
    int main()
    {
        ID3 Tree(4);
        Tree.PushData((int *)&samples[0], 0);
        Tree.PushData((int *)&samples[1], 0);
        Tree.PushData((int *)&samples[2], 1);
        Tree.PushData((int *)&samples[3], 1);
        Tree.PushData((int *)&samples[4], 1);
        Tree.PushData((int *)&samples[5], 0);
        Tree.PushData((int *)&samples[6], 1);
        Tree.PushData((int *)&samples[7], 0);
        Tree.PushData((int *)&samples[8], 1);
        Tree.PushData((int *)&samples[9], 1);
        Tree.PushData((int *)&samples[10], 1);
        Tree.PushData((int *)&samples[11], 1);
        Tree.PushData((int *)&samples[12], 1);
        Tree.PushData((int *)&samples[13], 0);
     
        Tree.Build();
        Tree.Print();
        cout << endl;
        for(int i = 0; i < 14; ++i)
            cout << "predict value :    " <<Tree.Match( (int *)&samples[i] ) << endl;
        return 0;
    }

    Makefile

    Test: main.cpp ID3.h ID3.cpp
        g++ -o Test ID3.cpp main.cpp
     
    clean:
        rm Test

     

    展开全文
  • 数据挖掘--决策树ID3算法(例题)

    万次阅读 多人点赞 2018-12-01 22:46:23
    ID3算法 案例: 熵 分割线---------------------------------------------------------------------------- 第一种因素的熵 分割线-----------------------------------------------------------------...

    决策树分类算法

    决策树分类算法通常分为两个步骤:决策树生成和决策树修剪。

    决策树生成算法的输入参数是一组带有类别标记的样本,输出是构造一颗决策树,该树可以是一棵二叉树或多叉树。二叉树的内部结点(非叶子结点)一般表示为一个逻辑判断,构造决策树的方法是采用自上而下的递归方法。

    首先要先知道熵和信息增益怎么求。
    案例:
    四种不同的影响因素,一个结果(yes/no)

    下面式子为训练样本集的熵
    在这里插入图片描述
    分割线----------------------------------------------------------------------------
    在这里插入图片描述
    考虑第一种因素:outlook
    (当outlook都是overcast时,4个都是yes)
    在这里插入图片描述
    (当outlook为rainy时,5个中有3个yes,2个no)
    在这里插入图片描述
    (当outlook为sunny时,5个中有3个no,2个yes)
    在这里插入图片描述

    第一种因素outlook对应的信息增益为:
    在这里插入图片描述
    在这里插入图片描述
    第二、三、四种因素对应的信息增益为:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    样本的概率分布越均衡,它的信息量(熵)就越大,样本集的混杂程度也越高。
    信息增益越大,说明属性对分类提供的信息越多。

    分割线----------------------------------------------------------------------------

    ID3算法
    案例:
    在这里插入图片描述

    在这里插入图片描述
    分割线----------------------------------------------------------------------------

    在这里插入图片描述
    第一种因素的熵
    在这里插入图片描述
    分割线----------------------------------------------------------------------------
    在这里插入图片描述
    第二种因素的熵
    在这里插入图片描述
    分割线----------------------------------------------------------------------------
    在这里插入图片描述
    第三种因素的熵:
    在这里插入图片描述
    分割线----------------------------------------------------------------------------
    在这里插入图片描述
    第四种因素的熵:
    在这里插入图片描述
    分割线----------------------------------------------------------------------------

    最后选择信息增益最大的作为根节点:outlook
    接着对outlook下的三种因素计算重复以上的运算:
    Entropy(outlook),Entropy(outlook,overcast),Entropy(outlook,rainy),Entropy(outlook,sunny)
    接着求信息增益:
    发现在overcast时,humidity的信息增益最大,所以选择humidity作为叶节点。
    发现在rain时,windy的信息增益最大,选择windy作为叶节点。
    最后得到下面的结果。
    在这里插入图片描述

    下面的这个案例更加清楚:
    在这里插入图片描述
    求得age的信息增益最大,然后作为根节点,得到下图
    在这里插入图片描述
    然后对age分类下的三种情况,分别求对应的信息增益:
    因为在30-40之间只有yes,所以不需要计算
    在<30情况下,计算信息增益,发现student的信息增益最大,则将student设为节点;
    在>40情况下,发现credit rating的信息增益最大,则设它为节点。
    在这里插入图片描述

    展开全文
  • 决策树算法ID3算法(Python3实现)

    万次阅读 多人点赞 2018-07-19 16:57:30
    2、使用ID3算法递归构建决策树并使用决策树执行分类 2.1 ID3算法概述 2.2 递归终止的条件: 2.3 代码实现如下: 3、Matplotlib实现决策树可视化 4、决策树的存储与读取 5、决策树优点和缺点 1、数据集准备 ...
  • 决策树ID3、CART、C4.5之间的区别

    万次阅读 2018-09-16 18:36:30
    C4.5是基于ID3优化后产出的算法,主要优化了关于节点分支的计算方式,优化后解决了ID3分支过程中总喜欢偏向取值较多的属性 ID3是信息增益分支: 而CART一般是GINI系数分支: C4.5一般是信息增益率分支:   ...
  • jquery 选择多个id:$("#id1,#id2,#id3,#id4")

    万次阅读 2014-08-15 10:05:45
    $("#id1,#id2,#id3,#id4")
  • php输出Resource id #3

    万次阅读 2017-10-30 11:34:16
    php输出Resource id #3,这个结果表示的是输出一个记录集合因为返回的是句柄,把文件内容读出来就行了。 这里我们可以使用$fp打开文件下面是是报错的信息 $file=fopen("./aa.txt","r"); echo $file; fclose($...
  • sql查询多条数据如 id = 1,21,3

    万次阅读 2019-08-16 14:59:24
    有这样一张表 查询其中news_id为 1,19的数据sql语句为 select * from t_news where FIND_IN_SET(news_id,'1,20,3') 结果如下
  • 3、解决办法, 1、在 server.properties 找到 log.dirs 配置的路径, 操作命令如下: 2、进入配置的 log.dirs=/tmp-9092/kafka-logs 路径下面 3、meta.properties,修改里面的cluster.id即可, 修改为错误提示...
  • No package ID ff found for ID 0xffffffff. 问题原因及解决方案 constraintlayout 2.0.0-alpha4版本的问题,回退到2.0.0-alpha3就可以了. PS: 这个是在一个英文网站上搜到的,刚好受用,哈哈. 附录 ...
  • python3 获取 进程id 线程id

    万次阅读 2020-01-21 09:52:53
    1.获取线程id import threading # 1 获取线程ID,NAME t = threading.currentThread() #线程ID print('Thread id : %d' % t.ident) #线程NAME print('Thread name : %s' % t.getName()) 输出: Thread id : ...
  • 对于CAN ID的理解

    万次阅读 多人点赞 2017-09-02 21:25:33
    本文主要讲的是自己对于CAN ID的理解,希望对需要的人有帮助,本文以通俗的方式来理解,不涉及到具体CAN通信。 在接触CAN之前,应该接触过IIC通信,在IIC通信中,在同一条IIC通信总线上每个device有唯一的ID,后续...
  • iphone IMEI查询完整ID

    千次下载 热门讨论 2014-08-24 14:25:11
    IMEI快速查询苹果完整邮箱ID
  • nodeid, node.value,nodeid+length_+1,nodeid+length_+2); nodevalue{1,nodeid}=node.value; end end function flag = isleaf(node) %% 是否是叶子节点 if strcmp(node.left,'null') && strcmp(node....
  • CAN笔记(17) 预定义报文ID

    万次阅读 2019-09-11 08:45:12
    网络管理NMT、特殊协议报文、过程数据对象PDO和服务数据对象SDO的报文ID分配
  • 苹果解ID

    千次下载 热门讨论 2014-02-04 13:25:55
    iPhone345代的手机屏幕锁解锁,激活解除ID锁。
  • 九种分布式ID生成算法详解

    万次阅读 2020-09-04 19:53:56
    一、分布式ID简介 1、什么是分布式ID? 在我们业务数据量不大的时候,单库单表完全可以支撑现有业务,数据再大一点搞个MySQL主从同步读写分离也能对付。 但随着数据日渐增长,主从同步也扛不住了,就需要对数据库...
  • Mybatis-Plus雪花id的使用以及解析机器 ID 和数据标识 ID概述结构源码Mybatis-Plus使用雪花id1.引入Mybatis-Plus依赖2.在application.yml配置文件中增加如下配置项3.原有的mapper接口增加继承BaseMapper接口4.实体类...
  • android @id和@+id的区别

    万次阅读 多人点赞 2018-05-29 08:40:46
    今天,简单讲讲android里关于@id和@+id的区别。之前,自己在布局里无论什么情况都使用@+id,可是后来发现有些代码用的是@id,自己不知道这两者之间有什么区别。于是就在网上查找资料,最终是解决了问题。这里记录...
  • 文档来源,Mybatis-Plus 2.... 最新文档,Mybatis-Plus 3.X:https://mybatis.plus/guide/ 不想看过程的直接可以看结尾的解决方法。 首先看官方介绍: ...官方说这里默认使用ID_WORKER策略 实际测试时却一直报错,...
  • Linux id 命令 - 显示用户id和组id信息

    万次阅读 2017-05-24 15:10:00
    Linux id命令用于显示用户的ID,以及所属群组的IDid会显示用户以及所属群组的实际与有效ID。若两个ID相同,则仅显示实际ID。若仅指定用户名称,则显示目前用户的ID。 语法 id [-gGnru][--help][--version]...
  • 数仓建模—ID Mapping(下)

    万次阅读 2021-09-02 18:18:59
    上一节我们已经讲过什么是ID Mapping 了,顾名思义我们知道ID Mapping 的操作对象是ID,目标或者是动作是Mapping,也就是说我们要做的事情其实就是想把不同平台不同设备上的ID 打通,从而更好的去刻画用户,也就是说...
  • 还可以参考这位@TableId(value = “id“,type = IdType.AUTO) 设置后无效的解决办法的解决方式,也比较玄学。 思考 好吧,其实也不玄学,说下自己的思考。 我们创建表的时候,表id字段是设置自动增长的,并且主键...
  • Android 动态添加View 并设置id

    万次阅读 多人点赞 2018-03-22 16:55:27
    然后通过setId()方法引用这个ids.xml资源文件中的id就行了 textView1 .setId (R .id .text _view_1) ; MainActivity.java package com .yechaoa .addview ; import android .graphics .Color ; ...
  • apple id连接服务器失败怎么办

    万次阅读 2021-07-30 01:02:13
    类型:浏览辅助大小:710KB语言:中文 评分:10.0标签:立即下载apple id在软件下载等地方都是需要用到的,有小伙伴使用中显示连接服务器失败,无法进行操作,这种情况怎么办呢,西西小编来为大家介绍。apple id连接...
  • data-idid 的区别 data-id 的样式写法

    万次阅读 多人点赞 2018-05-18 14:58:31
    id是选择器data-id只是行内存放数据的一个标签,跟input里面的value作用是一样的同时在HTML5 中增加了一项新功能是 自定义数据属性 ,也就是 data-* 自定义属性。在HTML5中我们可以使用以 data- 为前缀来设置我们...
  • 数仓建模—ID Mapping(上)

    万次阅读 2021-07-21 10:10:27
    ID Mapping ID Mapping 就如同它的名字一样,我们要做的就是将一系列的ID 关联起来,从而可以更加准确完善的分析一个用户。 选取合适的用户标识对于提高用户行为分析的准确性有非常大的影响,尤其是对用户画像、推荐...
  • 获取Google Advertising ID 和 Android ID

    万次阅读 2018-09-18 14:49:24
    获取GoogleID(GAID): ...String ANDROID_ID = Settings.System.getString(getContentResolver(),Settings.System.ANDROID_ID); Log.d(&quot;MainActivity&quot;,&quot;Android ID: &quot; + ANDR...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,687,063
精华内容 4,274,825
关键字:

id3

友情链接: IO-light-led.rar