精华内容
参与话题
问答
  • 决策树 ID3算法

    2018-09-29 20:57:08
    决策树ID3算法概述 决策树的构造 信息熵,信息增益 entropy,infomation gain shannon entropy 划分数据集 去除dataset中的一列。 递归构造决策树(分类器) 处理最后一个节点 递归建树 ...
    
    
    
    

    决策树ID3算法概述

    决策树类似于20问题,可以用一个流程图来表示。

    二十个问题的游戏,游戏的规则很简单:参与游戏的一方在脑海里想某个事物,
    其他参与者向他提问题,只允许提20个问题,问题的答案也只能用对或错回答。问问题的人通过
    推断分解,逐步缩小待猜测事物的范围。
    

    文末的决策树:根据已有的数据来预测一个患者适合哪种类型的隐形眼镜。
    在这里插入图片描述

    决策树(Decison Tree)树中每个节点的分类依据都是特征(feature) ,节点下都是对象。特征即有无脚蹼,是否有羽毛,有脚蹼和无脚蹼称为这个feature下的不同value。当一个特征被确定之后,分支(branch)即依赖value来构造。
    ID3 (Iterative Dichotomiser 3)含义为迭代二叉树3代。

    分类算法中,k-近邻算法可以完成很多分类任务,但是它最大的缺点就是无法给出数据的内在含义。从原始数据中创建规则构造决策树的过程就是学习过程。

    优点:

    • 直观

    缺点:

    • 容易产生过度匹配
    • ID3 只适用于标称性数值,不能直接用于处理数值型数值。

    决策树的构造

    思考构建一个决策树可以由三部分组成。

    • 1.如何决定规则:哪些特征在分类时起决定作用
      • 1.1 评估每个特征:引入概念 信息熵,信息增益
      • 1.2 遍历选出最佳的特征
    • 2.如何划分
    • 3.如何构建

    递归建树在递归划分时实现。
    伪代码:

    def create_tree(dataset):
      这个特征下,每个子项下是否都为同一类:
        if so (到叶子)
          return 标签
        else (到节点)
          除去该特征,构造子集 sub_dataset
          寻找子集中的最佳特征
          创建分支节点
          for 每个子集:
            create_tree(sub_dataset)
          return 分支节点
    

    信息熵,信息增益 entropy,infomation gain

    信息熵:
    如果一个待分类的事务在多个分类中,那么对于一种分类方案。如xx的分类方式xi,i=1,2,3...{x_i,i=1,2,3...},那么xix_i
    l(xi)=log2p(xi)l(x_i)=-log_2{p(x_i)}
    p(xi)p(x_i)为该分类的概率。
    对于这个分类,我们计算它的期望
    H=i=1np(xi)log2p(xi)H =-\sum_{i=1}^np(x_i)log_2{p(x_i)}

    分类的结果让数据越混乱,越大,因此最优的分类方案有最小的熵,它和原数据集的熵的差值即为信息增益。

    '''
    一个判断是否是海洋生物的dataset。
    1,0表示有无
    no surfacing 不浮出水面能否生存
    flippers 表示有脚蹼
    yes/no 是否鱼类
    '''
    dataset = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    
    # shannon entropy
    def calc_shannon_ent(dataset):
        num_entries = len(dataset)  # dataset 的条目数
        labels_counts = {}
        for feat_vec in dataset:
            cur_label = feat_vec[-1]
            if cur_label not in labels_counts.keys():
                labels_counts[cur_label] = 1
            else:
                labels_counts[cur_label] += 1
        shannon_ent = 0.0
        for key in labels_counts:
            prob = float(labels_counts[key]) / num_entries
            shannon_ent -= prob * log(prob, 2)
        return shannon_ent
    
    >>> calc_shannon_ent(data)
    0.9709505944546686
    >>> -0.4*log(0.4,2)-0.6*log(0.6,2)
    0.9709505944546686
    

    在分类中,可能一种分类下的分支产生的’yes/no’结果为(1,3),另一种为(2,2),那么计算shannon_ent这两种分类就有优劣了。

    划分数据集

    已知分类的特征,划分数据集。

    # 去除dataset中的一列。
    def split_dataset(dataset, axis, value):
        ret_dataset = []
        for feat_vec in dataset:
            if feat_vec[axis] == value:
                reduce_dataset = feat_vec[:axis]
                reduce_dataset.extend(feat_vec[axis + 1:])
                ret_dataset.append(reduce_dataset)
        return ret_dataset
    

    选取该dataset下最佳的分类方式。

    def choose_best_feature_to_split(dataset):
        # 去除最后一个'yes/no'标签
        num_feat = len(dataset[0]) - 1
        # 原始熵,信息增益,特征序号
        base_shannon_ent = calc_shannon_ent(dataset)
        best_gain = 0.0
        best_feature = -1
        # 遍历每个特征,抽取一个列,计算熵的总和
        # vec 为行,list为列
        for i in range(num_feat):
            featlist = [feat_vec[i] for feat_vec in dataset]
            # set去重
            unique_feat = set(featlist)
            new_entropy = 0.0
            # 这个特征下不同的值划分产生的子集,计算子集的期望
            for value in unique_feat:
                sub_dataset = split_dataset(dataset, i, value)
                # 计算期望
                prob = len(sub_dataset) / float(len(dataset))
                new_entropy += prob * calc_shannon_ent(sub_dataset)
            # 比较
            gain = base_shannon_ent - new_entropy
            if (gain > best_gain):
                best_gain = gain
                best_feature = i
        return best_feature
    

    递归构造决策树(分类器)

    工作原理:
    对原始数据集,基于最好的属性值划分数据集,由于特征值可能多于两个,因此可能存在大于两个分支的数据集划分。第一次划分之后,数据将被向下传递到树分支的下一个节点,在这个节点上,我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。
    递归终点:

    1.这个子集下特征全部一致
    2.用完全部特征(最后一个特征)

    处理最后一个节点

    如果用到最后一个特征,但子集下特征还不一致,那么需要额外处理,处理这个(唯一的)混乱子集。显然挑一个结果次数最多的,返回标签。

    def majority_cnt(classlist):
        class_count = {}
        for vote in classlist:
            if vote not in class_count:
                class_count[vote] = 0
            else:
                class_count[vote] += 1
        sorted_class_count = sorted(
            class_count.items(), key=operator.itemgetter(1), reverse=True)
        return sorted_class_count[0][0]
    

    递归建树

    import operator
    from math import log
    import pathlib
    
    dataset = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    
    
    # shannon entropy
    def calc_shannon_ent(dataset):
        num_entries = len(dataset)  # dataset 的条目数
        labels_counts = {}
        for feat_vec in dataset:
            cur_label = feat_vec[-1]
            if cur_label not in labels_counts.keys():
                labels_counts[cur_label] = 1
            else:
                labels_counts[cur_label] += 1
        shannon_ent = 0.0
        for key in labels_counts:
            prob = float(labels_counts[key]) / num_entries
            shannon_ent -= prob * log(prob, 2)
        return shannon_ent
    
    
    # 去除dataset中的一列。
    def split_dataset(dataset, axis, value):
        ret_dataset = []
        for feat_vec in dataset:
            if feat_vec[axis] == value:
                reduce_dataset = feat_vec[:axis]
                reduce_dataset.extend(feat_vec[axis + 1:])
                ret_dataset.append(reduce_dataset)
        return ret_dataset
    
    
    def choose_best_feature_to_split(dataset):
        # 去除最后一个'yes/no'标签
        num_feat = len(dataset[0]) - 1
        # 原始熵,信息增益,特征序号
        base_shannon_ent = calc_shannon_ent(dataset)
        best_gain = 0.0
        best_feature = -1
        # 遍历每个特征,抽取一个列,计算熵的总和
        # vec 为行,list为列
        for i in range(num_feat):
            featlist = [feat_vec[i] for feat_vec in dataset]
            # set去重
            unique_feat = set(featlist)
            new_entropy = 0.0
            # 这个特征下不同的值划分产生的子集,计算子集的期望
            for value in unique_feat:
                sub_dataset = split_dataset(dataset, i, value)
                # 计算期望
                prob = len(sub_dataset) / float(len(dataset))
                new_entropy += prob * calc_shannon_ent(sub_dataset)
            # 比较
            gain = base_shannon_ent - new_entropy
            if (gain > best_gain):
                best_gain = gain
                best_feature = i
        return best_feature
    
    
    def majority_cnt(classlist):
        class_count = {}
        for vote in classlist:
            if vote not in class_count:
                class_count[vote] = 0
            else:
                class_count[vote] += 1
        sorted_class_count = sorted(
            class_count.items(), key=operator.itemgetter(1), reverse=True)
        return sorted_class_count[0][0]
    
    
    # 递归建树
    def create_tree(dataset, labels):
        classlist = [i[-1] for i in dataset]
        # 是否该(sub)dataset下分类全部一致
        if classlist.count(classlist[0]) == len(classlist):
            return classlist[0]
        # 分类完只剩最后一个label,剩下的dataset仍然没有完全被分类,调用majority_cnt 返回剩下中的最多的一个分类
        if len(classlist) == 1:
            return majority_cnt(classlist)
        best_feature = choose_best_feature_to_split(dataset)
        best_feature_label = labels[best_feature]
        myTree = {best_feature_label: {}}
        del(labels[best_feature])
        feat_list = [i[best_feature]for i in dataset]
        unique_list = set(feat_list)
        for feat in unique_list:
            sub_labels = labels[:]
            myTree[best_feature_label][feat] = create_tree(
                split_dataset(dataset, best_feature, feat), sub_labels)
        return myTree
    
    
    if __name__ == '__main__':
        print(create_tree(dataset,labels))
    

    {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

    实例-使用决策树预测隐形眼镜类型

    增加原始数据处理的过程

    if __name__ == '__main__':
        fp = open('lenses.txt','r')
        # lenses return as a 2 decison array
        lenses = [eachline.strip().split('\t') for eachline in fp.readlines()]
        lenses_label = ['age', 'prescript', 'astigmatic', 'tearRate']
        lenses_tree = create_tree(lenses, lenses_label)
        print(lenses_tree)
    
    {'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic': {'yes': {'prescript': {'hyper': {'age': {'young': 'hard', 'presbyopic': 'no lenses', 'pre': 'no lenses'}}, 'myope': 'hard'}}, 'no': {'age': {'young': 'soft', 'presbyopic': {'prescript': {'hyper': 'soft', 'myope': 'no lenses'}}, 'pre': 'soft'}}}}}}
    

    pickle模块存储

    构造决策树是很耗时的任务。一般分类时调用已有的决策树。使用Python模块pickle序列化对象。

    def storeTree(inputTree, filename):
        import pickle
        fw = open(filename, 'w')
        pickle.dump(inputTree, fw)
        fw.close()
    
    
    def grabTree(filename):
        import pickle
        fr = open(filename)
        return pickle.load(fr)
    
    展开全文
  • 决策树ID3算法

    2015-01-25 10:25:51
    决策树模型是一种经典的分类算法,是通过一系列的判断规则对数据进行分类的过程。...决策树最早由JRossQuinlan于20世纪80年代提出,也就是经典的ID3算法ID3算法通过选择最大的信息增益属性作为每一步分支

    决策树模型是一种经典的分类算法,是通过一系列的判断规则对数据进行分类的过程。主要分为模型训练和类别预测两个阶段,在模型训练阶段通过有监督的学习得到一系列的规则,在预测阶段通过这些规则进行分类。此外,决策树也已经被扩展到回归分析中,可以分为分类决策树和回归决策树。

    决策树最早由JRossQuinlan于20世纪80年代提出,也就是经典的ID3算法,ID3算法通过选择最大的信息增益属性作为每一步分支的决策属性,对于离散型的属性,每个取值作为一个分支,这种策略的目的是使得树的深度尽量少,然存在一个重大的缺陷是在选择分裂属性时往往偏向于选择属性取值较多的属性,也即忽略了树节点的广度,一个极端的情况就是在数据属性中存在一个ID属性,在ID的训练中,由于每个ID只对应于一个样本,当以该属性进行分支时,每个分支节点的分类准确率均为100%,此时属性的信息增益由样本个数决定而不取决于属性的具体含义。因此在92年的时候Quinlan又提出了C4.5,改用信息增益率来选择分裂属性,即在选择分裂属性时增加考虑属性的分裂信息度(用于衡量树的广度和均匀度,详见下文)。此外,C4.5还增加了对连续型属性的支持,通过一种合适的离散化算法寻找最优的分割点把数据离散化成两类,进而使用相同的方式进行分支。

    以上所述只是决策树的基本模型,在C4.5中还有一个重要的任务是剪枝,即去除没有作用不大的分支以缩小树的大小,在树的训练中还涉及到很多的模型检验方法,如N折交叉检验等。在算法实现上树节点的构造、算法程序优化等都是需要琢磨的细节,理论与实际运用之间存在较大差距,在此本文局限于简单的理论理解。在接下来的行文中主要是ID3算法的理论部分。

    一、分类问题


    二、ID3算法

    在样本中,是一个属性向量,映射每次选择中的一个属性值把样本划分到一个子集,如此循环直到达到子集的终止条件,在达到终止条件的子集中使用得到最优的判别类型,由此可见,ID3算法是在之前,首先根据构造一系列的规则对划分子集以提高算法的预测精度。

    熵是衡量信息离散程度的重要标准,在集合中类别i的频率记为,则集合R的信息熵为:

    在每一步的分裂中,都是希望划分后的子集的熵越小越好,因此在进行分裂属性选择时,通过信息增益来衡量分裂属性的好坏,用表示分裂后的子集,则该属性的信息增益为:


    其中表示属性的可能取值,表示集合R的样本数。

    在ID3的训练中,用Atts表示待分属性集合,树的分支过程求得:


    //寻找最大的信息增益属性

                         intmaxGainIndex=0;//最佳的分裂信息增益下标

                         doublemaxGain=-Double.MAX_VALUE;

                         for(inti=0;i<Atts.size();i++){

                                    doublegain=computeGain(items,Atts.get(i),t_node.entropyVal);

                                    if(maxGain<gain){

                                              maxGain=gain;

                                              maxGainIndex=i;

                                    }

                         }

    ID3算法采用自顶向下的贪婪搜索遍历可能的决策树空间。

    ID3算法的思想:

    1)自顶向下贪婪搜索;

    2)在构建每一个分支节点时,选择信息增益最大的属性;

    3)根据分裂属性划分样本子集;

    4)重复以上过程直到满足终止条件。

     

    ID3算法的程序实现相对比较简单,网络上资源众多,不再累述。

     

    三、剪枝

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

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

    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


    未完待续

    参考文献:

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

    http://blog.csdn.net/v_july_v/article/details/7577684

     

     

    展开全文
  • 决策树ID3算法matlab源代码

    热门讨论 2011-05-27 14:00:19
    决策树ID3算法matlab源代码片段 function [Tree RulesMatrix]=DecisionTree(DataSet,AttributName) %输入为训练集,为离散后的数字,如记录1:1 1 3 2 1; %前面为属性列,最后一列为类标 if nargin error('请输入...
  • 用python编写的决策树ID3算法,运用了Car-Evaluation的例子。BUG较少,综合了网上的优秀代码,并进一步形成自己的代码。代码基本有注释,风格良好,能够很快看懂。内含有比较规范的报告文档,包含所有流程图,说明图...
  • 决策树ID3算法 python

    2018-04-09 19:04:08
    机器学习算法 决策树 ID3算法 python3 带例子可直接运行
  • 决策树ID3算法java实现

    2018-04-28 00:03:36
    决策树ID3算法的Java实现111111111111111111111111111111111111111111111111111111
  • Tom编写的机器学习教材中PlayTennis例题—ID3算法python实现
  • 重点研究了经典的、具有较大影响力的决策树分类算法——ID3算法,并对其性能优劣作了比较分析。就ID3算法两个较为明显的缺陷进行了探讨,提出了优化算法。
  • ID3算法决策树的经典算法,本文档用实例演示了决策树ID3算法
  • 主要介绍了python实现决策树ID3算法的示例代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 决策树ID3算法的详细介绍(简单易懂) 决策树ID3算法的详细介绍(简单易懂) 决策树ID3算法的详细介绍(简单易懂)
  • 前言ID3算法决策树的经典,也是基础算法,本文将详细介绍ID3算法。算法详解ID3算法的核心是在决策树各个节点上通过计算每个属性的信息增益来进行分枝节点的选择,我在另一篇文章中已经介绍来信息增益,这篇文章将...

    前言

    ID3算法是决策树的经典,也是基础算法,本文将详细介绍ID3算法。

    算法详解

    ID3算法的核心是在决策树各个节点上通过计算每个属性的信息增益来进行分枝节点的选择,我在另一篇文章中已经介绍来信息增益,这篇文章将直接介绍算法。
    ID3算法是迭代算法,通过计算每个属性的信息增益不断生成决策树分枝,最终将样本标签按照各个属性分到各个叶子结点,生成树状结构。以一个经典例子解释:

    代码链接


    参考文献

    周志华《机器学习》
    李航《统计学习方法》
    我的blog:决策树ID3算法的Python实现:
                      决策树ID3算法的R实现:

    展开全文
  • 决策树ID3算法案例

    2018-08-12 18:20:03
    import pandas as pd file_root="G:/python/源码/源码/lesson.csv" dataframe=pd.read_csv(file_root,encoding="gbk") #print(dataframe) x=dataframe.ix[:,1:5].as_matrix() ...
    import pandas as pd
    file_root="G:/python/源码/源码/lesson.csv"
    dataframe=pd.read_csv(file_root,encoding="gbk")
    #print(dataframe)
    x=dataframe.ix[:,1:5].as_matrix()
    y=dataframe.ix[:,5].as_matrix()
    for i in range(0,len(x)):
        for j in range(0,len(x[i])):
            if (x[i][j]=="是" or x[i][j]=="高" or x[i][j]=="多"):
                x[i][j]=1
            else:x[i][j]=-1
    for i in range(0,len(y)):
        if(y[i]=="高"):
            y[i]=1
        else:
            y[i]=-1
    #容易出错的地方:直接将X,Y进行训练
    #正确做法:将x,y转化为dataframe,然后再转化为数组并指定整数格式
    xf=pd.DataFrame(x).as_matrix().astype(int)
    yf=pd.DataFrame(y).as_matrix().astype(int)
    from sklearn.tree import DecisionTreeClassifier
    model=DecisionTreeClassifier(criterion="entropy")#使用ID3算法
    model.fit(xf,yf)
    #可视化
    from sklearn.tree import export_graphviz
    from sklearn.externals.six import StringIO
    with open("G:/python 安装/graphviz/bin/dtc.dot","w") as file:
        export_graphviz(model,feature_names=["combat","num","promption","datam"],out_file=file)
    #用graphviz将.dot转化为png、pdf
    #dot -Tpng dtc.dot -o lesson.png
    展开全文
  • 决策树ID3算法原理

    2017-10-28 15:44:36
    1、决策树算法(Decision Tree):决策树算法在机器学习中算是很经典的一个算法决策树树是一个类似于流程图的树结构(如下图所示):其中,每个内部结点表示在一个属性上的测试,每个分支代表一个属性输出,而每个...
  • 决策树ID3算法实现

    2019-03-04 20:53:00
    决策树ID3算法基于信息增益来选择最优特征,于是自己实现了一把,直接上代码。 1 """ 2 CreateTime : 2019/3/3 22:19 3 Author : X 4 Filename : decision_tree.py 5 """ 6 7 import pandas as ...

空空如也

1 2 3 4 5 ... 20
收藏数 3,511
精华内容 1,404
关键字:

决策树id3算法