精华内容
下载资源
问答
  • ID3算法

    2017-10-26 21:21:13
    转载...对ID3算法的改进。Contents 1. 决策树的基本认识 2. ID3算法介绍 3. 信息熵与信息增益 4. ID3算法的C++实现决策树的基本认识决策树是一种依托决策而建立起来的一种树。在机器学习中

    转载http://blog.csdn.net/acdreamers/article/details/44661149

    对于决策树来说,主要有两种算法:ID3算法和C4.5算法。C4.5算法是
    对ID3算法的改进。

    Contents

     1. 决策树的基本认识
     2. ID3算法介绍
     3. 信息熵与信息增益
     4. ID3算法的C++实现
    
    1. 决策树的基本认识

      决策树是一种依托决策而建立起来的一种树。在机器学习中,决策树是一种预测模型,代表的是一种对象属性与对象值之间的一种映射关系,每一个节点代表某个对象,树中的每一个分叉路径代表某个可能的属性值,而每一个叶子节点则对应从根节点到该叶子节点所经历的路径所表示的对象的值。决策树仅有单一输出,如果有多个输出,可以分别建立独立的决策树以处理不同的输出。接下来讲解ID3算法。

    2. ID3算法介绍

      ID3算法是决策树的一种,它是基于奥卡姆剃刀原理的,即用尽量用较少的东西做更多的事。ID3算法,即Iterative Dichotomiser 3,迭代二叉树3 代,是Ross Quinlan发明的一种决策树算法,这个算法的基础就是上面提到的奥卡姆剃刀原理,越是小型的决策树越优于大的决策树,尽管如此,也不总是生成最小的树型结构,而是一个启发式算法。

      在信息论中,期望信息越小,那么信息增益就越大,从而纯度就越高。
      ID3算法的核心思想就是以信息增益来度量属性的选择,选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。

    3. 信息熵与信息增益

      在信息增益中,重要性的衡量标准就是看特征能够为分类系统带来多少信息,带来的信息越多,该特征越重要。在认识信息增益之前,先来看看信息熵的定义

      熵这个概念最早起源于物理学,在物理学中是用来度量一个热力学系统的无序程度,而在信息学里面,熵是对不确定性的度量。在1948年,香农引入了信息熵,将其定义为离散随机事件出现的概率,一个系统越是有序,信息熵就越低,反之一个系统越是混乱,它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

      假如一个随机变量的取值为(x1,x2,x3,x4,~xn),每一种取到的概率分别是(p1,p2,p3,p4,~~~pn),熵定义

      这里写图片描述

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

      对于分类系统来说,类别是变量,它的取值是C1,C2,C3,,,Cn,而每一个类别出现的概率分别是
      这里写图片描述
      而这里的就是类别的总数,此时分类系统的熵就可以表示为

      这里写图片描述

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

      信息增益是针对一个特征而言的,只看一个特征,系统有它和没有它时的信息量各是多少,差值就是这个特征给系统带来的信息量,即信息增益。

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

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

      这里写图片描述
      在决策树分类问题中,信息增益就是决策树在进行属性选择划分前和划分后信息的差值。假设利用属性Outlook来分类,那么如下图

      这里写图片描述

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

      这里写图片描述

      那么划分后的信息熵为

      这里写图片描述

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

      这里写图片描述
      信息增益的计算公式如下

    这里写图片描述

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

    在决策树的每一个非叶子结点划分之前,先计算每一个属性所带来的信息增益,选择最大信息增益的属性来划分,因为信息增益越大,区分样本的能力就越强,越具有代表性,很显然这是一种自顶向下的贪心策略。以上
    就是ID3算法的核心思想。

    1. 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算法

    2008-01-14 22:17:22
    matlab做的id3算法
  • ID3 算法

    千次阅读 2018-03-26 16:47:09
     ID3采用信息增益作为选择最优的分裂属性的方法,选择熵作为衡量节点纯度的标准,信息增益的计算公式如下:    其中,  表示父节点的熵;  表示节点i的熵,熵越大,节点的信息量越多,越不纯;  表示子节点i的...

    1)信息熵:


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

       的熵定义为

     

                 

     

       意思是一个变量的变化情况可能越多,那么它携带的信息量就越大,信息熵值越大,该系统越不稳定,存在的不定因素就越多。

     

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

     

                 

     

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

     

                 

     

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

      信息熵的增益是指:所有属性值的信息熵和某一个属性值的信息熵的差值,增益值越大,说明其具有更高的决策性,可做为优先节点,如一些例子

    例:通过当天的天气、温度、湿度和季节预测明天的天气

                                      表1 原始数据

    当天天气

    温度

    湿度

    季节

    明天天气

    25

    50

    春天

    21

    48

    春天

    18

    70

    春天

    28

    41

    夏天

    8

    65

    冬天

    18

    43

    夏天

    24

    56

    秋天

    18

    76

    秋天

    31

    61

    夏天

    6

    43

    冬天

    15

    55

    秋天

    4

    58

    冬天

     1.数据分割

          对于离散型数据,直接按照离散数据的取值进行分裂,每一个取值对应一个子节点,以“当前天气”为例对数据进行分割,如图1所示。

     

          对于连续型数据,ID3原本是没有处理能力的,只有通过离散化将连续性数据转化成离散型数据再进行处理。

          连续数据离散化是另外一个课题,本文不深入阐述,这里直接采用等距离数据划分的李算话方法。该方法先对数据进行排序,然后将连续型数据划分为多个区间,并使每一个区间的数据量基本相同,以温度为例对数据进行分割,如图2所示。

     

     2. 选择最优分裂属性

          ID3采用信息增益作为选择最优的分裂属性的方法,选择熵作为衡量节点纯度的标准,信息增益的计算公式如下:

                                                   

          其中, 表示父节点的熵; 表示节点i的熵,熵越大,节点的信息量越多,越不纯; 表示子节点i的数据量与父节点数据量之比。 越大,表示分裂后的熵越小,子节点变得越纯,分类的效果越好,因此选择 最大的属性作为分裂属性。

          对上述的例子的跟节点进行分裂,分别计算每一个属性的信息增益,选择信息增益最大的属性进行分裂。

          天气属性:(数据分割如上图1所示) 

      

          温度:(数据分割如上图2所示)

         

          湿度:

     

          

          季节:

     

          

         由于最大,所以选择属性“季节”作为根节点的分裂属性。

     

    3.停止分裂的条件

         停止分裂的条件已经在决策树中阐述,这里不再进行阐述。

         (1)最小节点数

      当节点的数据量小于一个指定的数量时,不继续分裂。两个原因:一是数据量较少时,再做分裂容易强化噪声数据的作用;二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。

      (2)熵或者基尼值小于阀值。

         由上述可知,熵和基尼值的大小表示数据的复杂程度,当熵或者基尼值过小时,表示数据的纯度比较大,如果熵或者基尼值小于一定程度时,节点停止分裂。

      (3)决策树的深度达到指定的条件

       节点的深度可以理解为节点与决策树跟节点的距离,如根节点的子节点的深度为1,因为这些节点与跟节点的距离为1,子节点的深度要比父节点的深度大1。决策树的深度是所有叶子节点的最大深度,当深度到达指定的上限大小时,停止分裂。

      (4)所有特征已经使用完毕,不能继续进行分裂。

         被动式停止分裂的条件,当已经没有可分的属性时,直接将当前节点设置为叶子节点。



    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,346
精华内容 3,338
关键字:

id3算法