精华内容
下载资源
问答
  • matlab版的信息增益算法实现
  • 基于信息增益的决策树算法(附MATLAB代码)

    千次阅读 热门讨论 2019-12-18 11:48:47
    基于信息增益的决策树算法(附MATLAB代码) 最近在学机器学习,本篇文章的内容正好是作业内容,所以拿来分享一下,顺便捋一下思路。下面内容只涉及到决策树学习基本算法(伪代码)、信息增益的计算和matlab代码实现。...

    基于信息增益的决策树算法(附MATLAB代码)

    最近在学机器学习,本篇文章的内容正好是作业内容,所以拿来分享一下,顺便捋一下思路。下面内容只涉及到决策树学习基本算法(伪代码)、信息增益的计算和matlab代码实现。决策树算法原理不再赘述,请自行百度。水平有限,如有错误,欢迎指正!

    一、决策树学习基本算法

    在这里插入图片描述

    二、 信息增益的计算

    1.信息熵

    “信息熵”(information entropy)是度量样本集合纯度最常用的一种指标,假定当前样本集合D中第k类样本所占的比例为Pkk = 1,2,…,|Y|),则D的信息熵定义为
    图1
    Ent(D)的值越小,D的纯度越高。

    2.信息增益

    假定离散属性aV个可能的值a1,a2,…,aV,若使用a来对样本集D进行划分,则会产生V个分支节点,其中第v个分支节点包含了D中所有在属性a上取值为av的样本,记为Dv,这时可以计算出Dv的信息熵,同时考虑到不同的分支结点所包含的样本数不同,给分支结点赋予权重|Dv|/|D|,即样本数越多的分支结点的影响越大,于是可计算出用属性a对样本集D进行划分所获得的“信息增益”(information gain)
    图2

    3.划分属性选择

    一般而言,信息增益越大,则意味着使用属性a来进行划分所获得的“纯度提升”就越大,因此,我们可用信息增益来进行决策树的划分选择,即选择属性a = arg* max Gain(D,a),这就是著名的ID3决策树学习算法。

    三、MATLAB代码实现

    %****************************************
    %main.m
    %****************************************
    clear,clc
    [~,data] = xlsread('data.xlsx',3)       %读入数据集
    [~,feature] = xlsread('feature.xlsx')   %读入属性集
    Node = createTree(data, feature);       %生成决策树
    drawTree(Node)                          %绘制决策树
    
    %****************************************
    %createTree.m
    %****************************************
    %生成决策树ID3算法
    %data:训练集
    %feature:属性集
    function [node] = createTree(data, feature)
        type = mostType(data);  %cell类型
        [m, n] = size(data);
        %生成节点node
        %value:分类结果,若为null则表示该节点是分支节点
        %name:节点划分属性
        %branch:节点属性值
        %children:子节点
        node = struct('value','null','name','null','branch','null','children',{});
        temp_type = data{1, n};
        temp_b = true;
        for i = 1 : m
            if temp_type ~= data{i, n}
                temp_b = false;
            end
        end
        %样本中全为同一分类结果,则node节点为叶节点
        if temp_b == true
            node(1).value = data(1, n); %cell类型
            return;
        end
        %属性集合为空,将结果标记为样本中最多的分类
        if isempty(feature) == 1
            node.value = type;  %cell类型
            return;
        end 
        %获取最优划分属性
        feature_bestColumn = bestFeature(data); %最优属性列数,double类型
        best_feature = data(:,feature_bestColumn); %最优属性列,cell类型
        best_distinct = unique(best_feature); %最优属性取值
        best_num = length(best_distinct); %最优属性取值个数
        best_proc = cell(best_num, 2);
        best_proc(:, 1) = best_distinct(:, 1);
        best_proc(:, 2) = num2cell(zeros(best_num, 1));
        %循环该属性的每一个值
        for i = 1:best_num
            %为node创建一个bach_node分支,设样本data中该属性值为best_proc(i, 1)的集合为Dv
            bach_node = struct('value', 'null', 'name', 'null', 'branch', 'null', 'children',{});
            Dv_index = 0;
            for j = 1:m
                if data{j, feature_bestColumn} == best_proc{i, 1}
                    Dv_index = Dv_index + 1;
                end
            end
            Dv = cell(Dv_index, n);
            Dv_index2 = 1;
            for j = 1:m
                if best_proc{i, 1} == data{j, feature_bestColumn}
                    Dv(Dv_index2, :) = data(j, :);
                    Dv_index2 = Dv_index2 + 1;
                end
            end
            Dfeature = feature;
            %Dv为空则将结果标记为样本中最多的分类
            if isempty(Dv) == 1
                bach_node.value = type;
                bach_node.name = feature(feature_bestColumn);
                bach_node.branch = best_proc(i, 1);
                node.children(i) = bach_node;
                return;
            else
                Dfeature(feature_bestColumn) = [];
                Dv(:,feature_bestColumn) = [];
                %递归调用createTree方法
                bach_node = createTree(Dv, Dfeature);
                bach_node(1).branch = best_proc(i, 1);
                bach_node(1).name = feature(feature_bestColumn);
                node(1).children(i) = bach_node;
            end
        end
    end
    
    %****************************************
    %mostType.m
    %****************************************
    %计算样本最多的结果
    function [res] = mostType(data)         %返回值cell类型
        [m,n] = size(data);
        res = data(:, n);
        res_distinct = unique(res);
        res_num = length(res_distinct);
        res_proc = cell(res_num,2);
        res_proc(:, 1) = res_distinct(:, 1);
        res_proc(:, 2) = num2cell(zeros(res_num,1));
        for i = 1:res_num
            for j = 1:m
                if res_proc{i, 1} == data{j, n};
                    res_proc{i, 2} = res_proc{i, 2} + 1;
                end
            end
        end
    end
    
    %****************************************
    %getEntropy.m
    %****************************************
    %计算信息熵
    function [entropy] = getEntropy(data)       %返回值double类型
        entropy = 0;
        [m,n] = size(data);
        label = data(:, n);
        label_distinct = unique(label);
        label_num = length(label_distinct);
        proc = cell(label_num,2);
        proc(:, 1) = label_distinct(:, 1);
        proc(:, 2) = num2cell(zeros(label_num, 1));
         for i = 1:label_num
            for j = 1:m
                if proc{i, 1} == data{j, n}
                    proc{i, 2} = proc{i, 2} + 1;
                end
            end
            proc{i, 2} = proc{i, 2} / m;
        end
        for i = 1:label_num
            entropy = entropy - proc{i, 2} * log2(proc{i, 2});
        end
    end
    
    %****************************************
    %getGain.m
    %****************************************
    %计算信息增益
    function [gain] = getGain(entropy, data, column)        %返回值double类型
        [m,n] = size(data);
        feature = data(:, column);
        feature_distinct = unique(feature);
        feature_num = length(feature_distinct);
        feature_proc = cell(feature_num, 2);
        feature_proc(:, 1) = feature_distinct(:, 1);
        feature_proc(:, 2) = num2cell(zeros(feature_num, 1));
        f_entropy = 0;
         for i = 1:feature_num
           feature_row = 0;
           for j = 1:m
               if feature_proc{i, 1} == data{j, column}
                   feature_proc{i, 2} = feature_proc{i, 2} + 1;
                   feature_row = feature_row + 1;
               end
           end
           feature_data = cell(feature_row,n);
           feature_row = 1;
           for j = 1:m
               if feature_distinct{i, 1} == data{j, column}
                   feature_data(feature_row, :) = data(j, :);
                   feature_row = feature_row + 1;
               end
           end
           f_entropy = f_entropy + feature_proc{i, 2} / m * getEntropy(feature_data);
        end
        gain = entropy - f_entropy;
    end
    
    %****************************************
    %bestFeature.m
    %****************************************
    %获取最优划分属性
    function [column] = bestFeature(data)       %返回值double类型
        [~,n] = size(data);
        featureSize = n - 1;
        gain_proc = cell(featureSize, 2);
        entropy = getEntropy(data);
        for i = 1:featureSize
            gain_proc{i, 1} = i;
            gain_proc{i, 2} = getGain(entropy, data, i);
        end
        max = gain_proc{1,2};
        max_label = 1;
        for i = 1:featureSize
            if gain_proc{i, 2} >= max
                max = gain_proc{i, 2};
                max_label = i;
            end
        end
        column = max_label;
    end
    
    %****************************************
    %drawTree.m
    %****************************************
    % 画出决策树
    function [] = drawTree(node)
        % 遍历树
        nodeVec = [];
        nodeSpec = {};
        edgeSpec = [];
        [nodeVec,nodeSpec,edgeSpec,~] = travesing(node,0,0,nodeVec,nodeSpec,edgeSpec);
        treeplot(nodeVec);
        [x,y] = treelayout(nodeVec);
        [~,n] = size(nodeVec);
        x = x';
        y = y';
        text(x(:,1),y(:,1),nodeSpec,'FontSize',15,'FontWeight','bold','VerticalAlignment','bottom','HorizontalAlignment','center');
        x_branch = [];
        y_branch = [];
        for i = 2:n
            x_branch = [x_branch; (x(i,1)+x(nodeVec(i),1))/2];
            y_branch = [y_branch; (y(i,1)+y(nodeVec(i),1))/2];
        end
        text(x_branch(:,1),y_branch(:,1),edgeSpec(1,:),'FontSize',12,'Color','blue','FontWeight','bold','VerticalAlignment','bottom','HorizontalAlignment','center');
    end
    
    % 遍历树
    function [nodeVec,nodeSpec,edgeSpec,current_count] = travesing(node,current_count,last_node,nodeVec,nodeSpec,edgeSpec)
        nodeVec = [nodeVec last_node];
        if isempty(node.value)
            nodeSpec = [nodeSpec node.children(1).name];
        else 
            if strcmp(node.value, '是')
                nodeSpec = [nodeSpec '好瓜'];
            else
                nodeSpec = [nodeSpec '坏瓜'];
            end
        end
        edgeSpec = [edgeSpec node.branch];
        current_count = current_count + 1;
        current_node = current_count;
        if ~isempty(node.value)
            return;
        end
        for next_ndoe = node.children
            [nodeVec,nodeSpec,edgeSpec,current_count] = travesing(next_ndoe,current_count,current_node,nodeVec,nodeSpec,edgeSpec);
        end
    end
    

    代码链接:.m文件下载

    四、运行结果

    训练集:
    在这里插入图片描述
    根据训练集生成决策树如下:
    在这里插入图片描述
    测试集及结果:
    在这里插入图片描述
    声明:本人并没有写测试部分的代码,感兴趣的可以自己写一下。

    五、代码和数据集

    链接:https://pan.baidu.com/s/1nDWsmaMo_aJr0LCFEJCadA
    提取码:7jrq

    展开全文
  • 1、ID3算法简介及基本原理ID3算法基于信息熵来选择最佳的测试属性,它选择当前样本集中具有最大信息增益值的属性作为测试属性;样本集的划分则依据测试属性的取值进行,测试属性有多少个不同的取值就将样本集划分为...

    本文将详细介绍ID3算法,其也是最经典的决策树分类算法。

    1、ID3算法简介及基本原理 
    ID3算法基于信息熵来选择最佳的测试属性,它选择当前样本集中具有最大信息增益值的属性作为测试属性;样本集的划分则依据测试属性的取值进行,测试属性有多少个不同的取值就将样本集划分为多少个子样本集,同时决策树上相应于该样本集的节点长出新的叶子节点。ID3算法根据信息论的理论,采用划分后样本集的不确定性作为衡量划分好坏的标准,用信息增益值度量不确定性:信息增益值越大,不确定性越小。因此,ID3算法在每个非叶节点选择信息增益最大的属性作为测试属性,这样可以得到当前情况下最纯的划分,从而得到较小的决策树。

    设S是s个数据样本的集合。假定类别属性具有m个不同的值:这里写图片描述,设这里写图片描述是类这里写图片描述中的样本数。对一个给定的样本,它总的信息熵为这里写图片描述,其中,这里写图片描述是任意样本属于这里写图片描述的概率,一般可以用这里写图片描述估计。

    设一个属性A具有k个不同的值这里写图片描述,利用属性A将集合S划分为k个子集这里写图片描述,其中这里写图片描述包含了集合S中属性A取这里写图片描述值的样本。若选择属性A为测试属性,则这些子集就是从集合S的节点生长出来的新的叶节点。设这里写图片描述是子集这里写图片描述中类别为这里写图片描述的样本数,则根据属性A划分样本的信息熵为这里写图片描述 
    其中,这里写图片描述这里写图片描述是子集这里写图片描述中类别为这里写图片描述的样本的概率。

    最后,用属性A划分样本集S后所得的信息增益(Gain)为这里写图片描述

    显然这里写图片描述越小,Gain(A)的值就越大,说明选择测试属性A对于分类提供的信息越大,选择A之后对分类的不确定程度越小。属性A的k个不同的值对应的样本集S的k个子集或分支,通过递归调用上述过程(不包括已经选择的属性),生成其他属性作为节点的子节点和分支来生成整个决策树。ID3决策树算法作为一个典型的决策树学习算法,其核心是在决策树的各级节点上都用信息增益作为判断标准来进行属性的选择,使得在每个非叶子节点上进行测试时,都能获得最大的类别分类增益,使分类后的数据集的熵最小。这样的处理方法使得树的平均深度较小,从而有效地提高了分类效率。

    2、ID3算法的具体流程 
    ID3算法的具体流程如下: 
    1)对当前样本集合,计算所有属性的信息增益; 
    2)选择信息增益最大的属性作为测试属性,把测试属性取值相同的样本划为同一个子样本集; 
    3)若子样本集的类别属性只含有单个属性,则分支为叶子节点,判断其属性值并标上相应的符号,然后返回调用处;否则对子样本集递归调用本算法。

    数据如图所示

    序号  天气  是否周末    是否有促销   销量
    1   坏   是   是   高
    2   坏   是   是   高
    3   坏   是   是   高
    4   坏   否   是   高
    5   坏   是   是   高
    6   坏   否   是   高
    7   坏   是   否   高
    8   好   是   是   高
    9   好   是   否   高
    10  好   是   是   高
    11  好   是   是   高
    12  好   是   是   高
    13  好   是   是   高
    14  坏   是   是   低
    15  好   否   是   高
    16  好   否   是   高
    17  好   否   是   高
    18  好   否   是   高
    19  好   否   否   高
    20  坏   否   否   低
    21  坏   否   是   低
    22  坏   否   是   低
    23  坏   否   是   低
    24  坏   否   否   低
    25  坏   是   否   低
    26  好   否   是   低
    27  好   否   是   低
    28  坏   否   否   低
    29  坏   否   否   低
    30  好   否   否   低
    31  坏   是   否   低
    32  好   否   是   低
    33  好   否   否   低
    34  好   否   否   低

    采用ID3算法构建决策树模型的具体步骤如下: 
    1)根据公式这里写图片描述,计算总的信息熵,其中数据中总记录数为34,而销售数量为“高”的数据有18,“低”的有16 
    这里写图片描述

    2)根据公式这里写图片描述这里写图片描述,计算每个测试属性的信息熵。

    对于天气属性,其属性值有“好”和“坏”两种。其中天气为“好”的条件下,销售数量为“高”的记录为11,销售数量为“低”的记录为6,可表示为(11,6);天气为“坏”的条件下,销售数量为“高”的记录为7,销售数量为“低”的记录为10,可表示为(7,10)。则天气属性的信息熵计算过程如下: 
    这里写图片描述 
    这里写图片描述 
    这里写图片描述

    对于是否周末属性,其属性值有“是”和“否”两种。其中是否周末属性为“是”的条件下,销售数量为“高”的记录为11,销售数量为“低”的记录为3,可表示为(11,3);是否周末属性为“否”的条件下,销售数量为“高”的记录为7,销售数量为“低”的记录为13,可表示为(7,13)。则节假日属性的信息熵计算过程如下: 
    这里写图片描述 
    这里写图片描述 
    这里写图片描述

    对于是否有促销属性,其属性值有“是”和“否”两种。其中是否有促销属性为“是”的条件下,销售数量为“高”的记录为15,销售数量为“低”的记录为7,可表示为(15,7);其中是否有促销属性为“否”的条件下,销售数量为“高”的记录为3,销售数量为“低”的记录为9,可表示为(3,9)。则是否有促销属性的信息熵计算过程如下: 
    这里写图片描述 
    这里写图片描述 
    这里写图片描述

    根据公式这里写图片描述,计算天气、是否周末和是否有促销属性的信息增益值。 
    这里写图片描述 
    这里写图片描述 
    这里写图片描述

    3)由计算结果可以知道是否周末属性的信息增益值最大,它的两个属性值“是”和“否”作为该根节点的两个分支。然后按照上面的步骤继续对该根节点的两个分支进行节点的划分,针对每一个分支节点继续进行信息增益的计算,如此循环反复,直到没有新的节点分支,最终构成一棵决策树。

    由于ID3决策树算法采用了信息增益作为选择测试属性的标准,会偏向于选择取值较多的即所谓的高度分支属性,而这类属性并不一定是最优的属性。同时ID3决策树算法只能处理离散属性,对于连续型的属性,在分类前需要对其进行离散化。为了解决倾向于选择高度分支属性的问题,人们采用信息增益率作为选择测试属性的标准,这样便得到C4.5决策树的算法。此外常用的决策树算法还有CART算法、SLIQ算法、SPRINT算法和PUBLIC算法等等。

    使用ID3算法建立决策树的MATLAB代码如下所示 
    ID3_decision_tree.m

    %% 使用ID3决策树算法预测销量高低
    clear ;
    
    %% 数据预处理
    disp('正在进行数据预处理...');
    [matrix,attributes_label,attributes] =  id3_preprocess();
    
    %% 构造ID3决策树,其中id3()为自定义函数
    disp('数据预处理完成,正在进行构造树...');
    tree = id3(matrix,attributes_label,attributes);
    
    %% 打印并画决策树
    [nodeids,nodevalues] = print_tree(tree);
    tree_plot(nodeids,nodevalues);
    
    disp('ID3算法构建决策树完成!');

    id3_preprocess.m:

    function [ matrix,attributes,activeAttributes ] = id3_preprocess(  )
    %% ID3算法数据预处理,把字符串转换为0,1编码
    
    % 输出参数:
    % matrix: 转换后的0,1矩阵;
    % attributes: 属性和Label;
    % activeAttributes : 属性向量,全1;
    
    %% 读取数据
    txt = {  '序号'    '天气'    '是否周末'    '是否有促销'    '销量'
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  
            ''        ''      ''          ''            ''  }
    attributes=txt(1,2:end);
    activeAttributes = ones(1,length(attributes)-1);
    data = txt(2:end,2:end);
    
    %% 针对每列数据进行转换
    [rows,cols] = size(data);
    matrix = zeros(rows,cols);
    for j=1:cols
        matrix(:,j) = cellfun(@trans2onezero,data(:,j));
    end
    
    end
    
    function flag = trans2onezero(data)
        if strcmp(data,'') ||strcmp(data,'')...
            ||strcmp(data,'')
            flag =0;
            return ;
        end
        flag =1;
    end

    id3.m:

    function [ tree ] = id3( examples, attributes, activeAttributes )
    %% ID3 算法 ,构建ID3决策树
        ...参考:https://github.com/gwheaton/ID3-Decision-Tree
    
    % 输入参数:
    % example: 输入0、1矩阵;
    % attributes: 属性值,含有Label;
    % activeAttributes: 活跃的属性值;-1,1向量,1表示活跃;
    
    % 输出参数:
    % tree:构建的决策树;
    
    %% 提供的数据为空,则报异常
    if (isempty(examples));
        error('必须提供数据!');
    end
    
    % 常量
    numberAttributes = length(activeAttributes);
    numberExamples = length(examples(:,1));
    
    % 创建树节点
    tree = struct('value', 'null', 'left', 'null', 'right', 'null');
    
    % 如果最后一列全部为1,则返回“true”
    lastColumnSum = sum(examples(:, numberAttributes + 1));
    
    if (lastColumnSum == numberExamples);
        tree.value = 'true';
        return
    end
    % 如果最后一列全部为0,则返回“falseif (lastColumnSum == 0);
        tree.value = 'false';
        return
    end
    
    % 如果活跃的属性为空,则返回label最多的属性值
    if (sum(activeAttributes) == 0);
        if (lastColumnSum >= numberExamples / 2);
            tree.value = 'true';
        else
            tree.value = 'false';
        end
        return
    end
    
    %% 计算当前属性的熵
    p1 = lastColumnSum / numberExamples;
    if (p1 == 0);
        p1_eq = 0;
    else
        p1_eq = -1*p1*log2(p1);
    end
    p0 = (numberExamples - lastColumnSum) / numberExamples;
    if (p0 == 0);
        p0_eq = 0;
    else
        p0_eq = -1*p0*log2(p0);
    end
    currentEntropy = p1_eq + p0_eq;
    
    %% 寻找最大增益
    gains = -1*ones(1,numberAttributes); % 初始化增益
    
    for i=1:numberAttributes;
        if (activeAttributes(i)) % 该属性仍处于活跃状态,对其更新
            s0 = 0; s0_and_true = 0;
            s1 = 0; s1_and_true = 0;
            for j=1:numberExamples;
                if (examples(j,i)); 
                    s1 = s1 + 1;
                    if (examples(j, numberAttributes + 1)); 
                        s1_and_true = s1_and_true + 1;
                    end
                else
                    s0 = s0 + 1;
                    if (examples(j, numberAttributes + 1)); 
                        s0_and_true = s0_and_true + 1;
                    end
                end
            end
    
            % 熵 S(v=1)
            if (~s1);
                p1 = 0;
            else
                p1 = (s1_and_true / s1); 
            end
            if (p1 == 0);
                p1_eq = 0;
            else
                p1_eq = -1*(p1)*log2(p1);
            end
            if (~s1);
                p0 = 0;
            else
                p0 = ((s1 - s1_and_true) / s1);
            end
            if (p0 == 0);
                p0_eq = 0;
            else
                p0_eq = -1*(p0)*log2(p0);
            end
            entropy_s1 = p1_eq + p0_eq;
    
            % 熵 S(v=0)
            if (~s0);
                p1 = 0;
            else
                p1 = (s0_and_true / s0); 
            end
            if (p1 == 0);
                p1_eq = 0;
            else
                p1_eq = -1*(p1)*log2(p1);
            end
            if (~s0);
                p0 = 0;
            else
                p0 = ((s0 - s0_and_true) / s0);
            end
            if (p0 == 0);
                p0_eq = 0;
            else
                p0_eq = -1*(p0)*log2(p0);
            end
            entropy_s0 = p1_eq + p0_eq;
    
            gains(i) = currentEntropy - ((s1/numberExamples)*entropy_s1) - ((s0/numberExamples)*entropy_s0);
        end
    end
    
    % 选出最大增益
    [~, bestAttribute] = max(gains);
    % 设置相应值
    tree.value = attributes{bestAttribute};
    % 去活跃状态
    activeAttributes(bestAttribute) = 0;
    
    % 根据bestAttribute把数据进行分组
    examples_0= examples(examples(:,bestAttribute)==0,:);
    examples_1= examples(examples(:,bestAttribute)==1,:);
    
    % 当 value = false or 0, 左分支
    if (isempty(examples_0));
        leaf = struct('value', 'null', 'left', 'null', 'right', 'null');
        if (lastColumnSum >= numberExamples / 2); % for matrix examples
            leaf.value = 'true';
        else
            leaf.value = 'false';
        end
        tree.left = leaf;
    else
        % 递归
        tree.left = id3(examples_0, attributes, activeAttributes);
    end
    % 当 value = true or 1, 右分支
    if (isempty(examples_1));
        leaf = struct('value', 'null', 'left', 'null', 'right', 'null');
        if (lastColumnSum >= numberExamples / 2); 
            leaf.value = 'true';
        else
            leaf.value = 'false';
        end
        tree.right = leaf;
    else
        % 递归
        tree.right = id3(examples_1, attributes, activeAttributes);
    end
    
    % 返回
    return
    end

    print_tree.m:

    function [nodeids_,nodevalue_] = print_tree(tree)
    %% 打印树,返回树的关系向量
    global nodeid nodeids nodevalue;
    nodeids(1)=0; % 根节点的值为0
    nodeid=0;
    nodevalue={};
    if isempty(tree) 
        disp('空树!');
        return ;
    end
    
    queue = queue_push([],tree);
    while ~isempty(queue) % 队列不为空
         [node,queue] = queue_pop(queue); % 出队列
    
         visit(node,queue_curr_size(queue));
         if ~strcmp(node.left,'null') % 左子树不为空
            queue = queue_push(queue,node.left); % 进队
         end
         if ~strcmp(node.right,'null') % 左子树不为空
            queue = queue_push(queue,node.right); % 进队
         end
    end
    
    %% 返回 节点关系,用于treeplot画图
    nodeids_=nodeids;
    nodevalue_=nodevalue;
    end
    
    function visit(node,length_)
    %% 访问node 节点,并把其设置值为nodeid的节点
        global nodeid nodeids nodevalue;
        if isleaf(node)
            nodeid=nodeid+1;
            fprintf('叶子节点,node: %d\t,属性值: %s\n', ...
            nodeid, node.value);
            nodevalue{1,nodeid}=node.value;
        else % 要么是叶子节点,要么不是
            %if isleaf(node.left) && ~isleaf(node.right) % 左边为叶子节点,右边不是
            nodeid=nodeid+1;
            nodeids(nodeid+length_+1)=nodeid;
            nodeids(nodeid+length_+2)=nodeid;
    
            fprintf('node: %d\t属性值: %s\t,左子树为节点:node%d,右子树为节点:node%d\n', ...
            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.right,'null') % 左右都为空
            flag =1;
        else
            flag=0;
        end
    end

    tree_plot.m

    function tree_plot( p ,nodevalues)
    %% 参考treeplot函数
    
    [x,y,h]=treelayout(p);
    f = find(p~=0);
    pp = p(f);
    X = [x(f); x(pp); NaN(size(f))];
    Y = [y(f); y(pp); NaN(size(f))];
    
    X = X(:);
    Y = Y(:);
    
        n = length(p);
        if n < 500,
            hold on ; 
            plot (x, y, 'ro', X, Y, 'r-');
            nodesize = length(x);
            for i=1:nodesize
    %            text(x(i)+0.01,y(i),['node' num2str(i)]); 
                text(x(i)+0.01,y(i),nodevalues{1,i}); 
            end
            hold off;
        else
            plot (X, Y, 'r-');
        end;
    
    xlabel(['height = ' int2str(h)]);
    axis([0 1 0 1]);
    
    end

    queue_push.m

    function [ newqueue ] = queue_push( queue,item )
    %% 进队
    
    % cols = size(queue);
    % newqueue =structs(1,cols+1);
    newqueue=[queue,item];
    
    end

    queue_pop.m

    function [ item,newqueue ] = queue_pop( queue )
    %% 访问队列
    
    if isempty(queue)
        disp('队列为空,不能访问!');
        return;
    end
    
    item = queue(1); % 第一个元素弹出
    newqueue=queue(2:end); % 往后移动一个元素位置
    
    end

    queue_curr_size.m

    function [ length_ ] = queue_curr_size( queue )
    %% 当前队列长度
    
    length_= length(queue);
    
    end

    转载自https://blog.csdn.net/lfdanding/article/details/50753239

    转载于:https://www.cnblogs.com/litthorse/p/8961458.html

    展开全文
  • ID3算法(MATLAB)

    2019-10-01 03:57:03
    ID3算法起源于概念学习系统(CLS),以信息熵的下降速度为选取测试属性的标准,即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准,然后继续这个过程,直到生成的决策树能完美分类训练样例。...

      ID3算法是一种贪心算法,用来构造决策树。ID3算法起源于概念学习系统(CLS),以信息熵的下降速度为选取测试属性的标准,即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准,然后继续这个过程,直到生成的决策树能完美分类训练样例。

      ①对当前样本集合,计算所有属性的信息增益

      ②选择信息增益最大的属性作为测试属性,把测试属性取值相同的样本划为同一个子样本集;

      ③若子样本集的类别属性只含有单个属性,则分支为叶子节点,判断其属性值并标上相应的符号,然后返回调用处;否则对子样本集递归调用本算法。


       结合餐饮案例实现ID3的具体实施步骤。

      T餐饮企业作为大型的连锁企业,生产的产品种类比较多,另外涉及的分店所处的位置也不同、数目也比较多。对于企业的高层来讲,了解周末和非周末销量是否有大的区别,以及天气、促销活动等因素是否能够影响门店的销量这些信息至关重要。因此,为了让决策者准确地了解和销量有关的一系列影响因素,需要构建模型来分析天气、是否周末和是否有促销活动对其销量的影响,下面以单个门店来进行分析。

      ①计算总的信息熵,其中数据中总记录数为34,而销售数量为“高”的数据有18,“低”的有16。$$I(18,16)=-\frac{18}{34} \log _{2} \frac{18}{34}-\frac{16}{34} \log _{2} \frac{16}{34}=0.997503$$

      ②计算每个测试属性的信息熵。

      对于天气属性,其属性值有“好”和“坏”两种。

      其中天气为“好”的条件下,销售数量为“高”的记录为11,销售数量为“低”的记录为6,可表示为(11,6);

      天气为“坏”的条件下,销售数量为“高”的记录为7,销售数量为“低”的记录为10,可表示为(7,10)。

    $$\begin{array}{*{20}{l}}
    {I(11,6) = - \frac{{11}}{{17}}{{\log }_2}\frac{{11}}{{17}} - \frac{6}{{17}}{{\log }_2}\frac{6}{{17}} = 0.936667}\\
    {I(7,10) = - \frac{7}{{17}}{{\log }_2}\frac{7}{{17}} - \frac{{10}}{{17}}{{\log }_2}\frac{{10}}{{17}} = 0.977418}\\
    {E\left( {天气} \right) = \frac{{17}}{{34}}I(11,6) + \frac{{17}}{{34}}I(7,10) = 0.957043}
    \end{array}$$

      对于是否周末属性,其属性值有“是”和“否”两种。

      其中是否周末属性为“是”的条件下,销售数量为“高”的记录为11,销售数量为“低”的记录为3,可表示为(11,3);

      是否周末属性为“否”的条件下,销售数量为“高”的记录为7,销售数量为“低”的记录为13,可表示为(7,13)。

    $$\begin{array}{*{20}{l}}
    {\begin{array}{*{20}{l}}
    {I(11,3) = - \frac{{11}}{{14}}{{\log }_2}\frac{{11}}{{14}} - \frac{3}{{14}}{{\log }_2}\frac{3}{{14}} = 0.749595}\\
    {I(7,13) = - \frac{7}{{20}}{{\log }_2}\frac{7}{{20}} - \frac{{13}}{{20}}{{\log }_2}\frac{{13}}{{20}} = 0.934068}
    \end{array}}\\
    {E\left( {是否周末} \right) = \frac{{14}}{{34}}I(11,3) + \frac{{20}}{{34}}I(7,13) = 0.858109}
    \end{array}$$

      对于是否有促销属性,其属性值有“是”和“否”两种。

      其中是否有促销属性为“是”的条件下,销售数量为“高”的记录为15,销售数量为“低”的记录为7,可表示为(15,7);

      其中是否有促销属性为“否”的条件下,销售数量为“高”的记录为3,销售数量为“低”的记录为9,可表示为(3,9)。

    $$\begin{array}{*{20}{c}}
    {I(15,7) = - \frac{{15}}{{22}}{{\log }_2}\frac{{15}}{{22}} - \frac{7}{{22}}{{\log }_2}\frac{7}{{22}} = 0.902393}\\
    {I(3,9) = - \frac{3}{{12}}{{\log }_2}\frac{3}{{12}} - \frac{9}{{12}}{{\log }_2}\frac{9}{{12}} = 0.811278}\\
    {E\left( {是否有促销} \right) = \frac{{22}}{{34}}I(15,7) + \frac{{12}}{{34}}I(3,9) = 0.870235}
    \end{array}$$

      ③计算天气、是否周末和是否有促销属性的信息增益值。

      天气:$0.997503-0.957043=0.04046$

      是否周末:$0.997503-0.858109=0.139394$

      有无促销属性:$0.997503-0.870235=0.127268$

      其中,是否周末的信息增益值最大,以其为根节点,其左右分支为“是”与“否”,

      ④依据增益值生成决策树。

      代码:

    %% 使用ID3决策树算法预测销量高低
    clear ;
    % 参数初始化
    inputfile = '../data/sales_data.xls'; % 销量及其他属性数据
    %% 数据预处理
    disp('正在进行数据预处理...');
    [matrix,attributes_label,attributes] =  id3_preprocess(inputfile);
    %% 构造ID3决策树,其中id3()为自定义函数
    disp('数据预处理完成,正在进行构造树...');
    tree = id3(matrix,attributes_label,attributes);
    %% 打印并画决策树
    [nodeids,nodevalues] = print_tree(tree);
    tree_plot(nodeids,nodevalues);
    disp('ID3算法构建决策树完成!');

      依据结果,我们可以得出以下结论:

      若周末属性为“是”,天气为“好”,则销售数量为“高”;

      若周末属性为“是”,天气为“坏”,促销属性为“是”,则销售数量为“高”;

      若周末属性为“是”,天气为“坏”,促销属性为“否”,则销售数量为“低”;

      若周末属性为“否”,促销属性为“否”,则销售数量为“低”;

      若周末属性为“否”,促销属性为“是”,天气为“好”,则销售数量为“高”;

      若周末属性为“否”,促销属性为“是”,天气为“坏”,则销售数量为“低”。

     

      由于ID3决策树算法采用了信息增益作为选择测试属性的标准,会偏向于选择取值较多的即所谓的高度分支属性,而这类属性并不一定是最优的属性。同时,ID3决策树算法只能处理离散属性,对于连续型的属性,在分类前需要对其进行离散化。

    转载于:https://www.cnblogs.com/fangxiaoqi/p/11453558.html

    展开全文
  • 决策树之信息增益计算模拟

    千次阅读 2017-09-01 15:13:01
    决策树算法有一个关键步骤就是最优特征的选择,利用信息增益算法选择该特征,例子来自于《统计学习方法》 利用MATLAB2017A版本,编写MATLAB程序计算之,将上述的数据保存到data5.xlsx中 clear;clc;close all ...

    决策树算法有一个关键步骤就是最优特征的选择,利用信息增益算法选择该特征,例子来自于《统计学习方法》

    利用MATLAB2017A版本,编写MATLAB程序计算之,将上述的数据保存到data5.xlsx中

    clear;clc;close all
    % 计算信息增益,决策树算法的基础
    data = readtable('data5.xlsx');
    data = string(table2cell(data));
    %
    H = @(p) sum(-p.*log2(p));
    % 计算H(D)
    HDD = data(:, end);
    uHDD = unique(HDD);
    n = length(HDD);
    HD = getHDi(HDD, uHDD);
    % 计算g(D)
    gD = HD - cellfun(@(z)...
         sum(z == unique(z)') *...
         arrayfun(@(x)getHDi(HDD(z == x), uHDD),...
         unique(z)) / n, num2cell(data(:, 2: end-1),1));
    [~, idx] = max(gD);
    fprintf('选择第%d个特征最为最优特征\n', idx);
    
    function y = getHDi(x, uHDD)
    H = @(p) nansum(-p*log2(p)');
    y = H(sum(x == uHDD') / length(x));
    end

    展开全文
  • 将ace增强后的图像信息熵与图像标准差的乘积作为目标函数, ace的增益因子a作为待寻优的变量; 使用pso算法对ace的增益因子a进行寻优,并返回最优的增益因子; 将最优增益代入ace算法中,对图像进行增强; 采用引导...
  • [机器学习]决策树算法MATLAB实现

    千次阅读 2020-11-22 11:42:43
    此文章包含树的建立(使用信息增益,基尼指数),绘图,预测以及剪枝(后剪枝),部分代码为老师提供。文章中所有的代码以及老师提供的代码以及实验的要求都在以下连接,需要可以自取。应该说,最好就是跟着实验要求去...
  • 决策树算法Matlab实现(train+test)

    万次阅读 2017-07-13 15:34:08
    决策树是一种特别简单的机器学习分类算法。决策树想法来源于人类的决策...决策树模型构建过程为,在特征集合中无放回的依次递归抽选特征作为决策树的节点——当前节点信息增益或者增益率最大,当前节点的值作为当前节点
  • ID3决策树算法是基于信息增益来构建的,信息增益可以由训练集的信息熵算得,这里举一个简单的例子 data=[心情好 天气好 出门 心情好 天气不好 出门 心情不好 天气好 出门 心情不好 天气不好 不出门] 前面...
  • 关于matlab实现无线传感器网络DV-HOP算法中如何计算能量损耗 用MATLAB实现无线传感器网络DV-HOP算法,然后根据下列文字编写代码计算能量损耗:  目前,在低能量无线电通信领域有大量的研究。无线电通信特性的不同...
  • random forest-matlab C4.5

    2018-06-15 11:23:35
    决策树C4.5算法,从1248个属性中选出18个分类属性,每一个属性里的每一个值a,通过,>a把数据分成两个部分,然后计算每一部份的信息熵,计算这个属性值a的“信息增益“,然后得到这个属性最大信息增益的分类间隔数;...
  • 一、简介 本文所采用的基于熵的切割点和最小描述...过滤措施的例子有距离、信息增益、一致性和相关性。另一方面,包装法使用一种学习算法来度量所选特性的分类性能。在这个过程中可以使用不同的学习算法,比如k近邻(KNN
  • 一、简介 本文所采用的基于熵的切割点和最小描述...过滤措施的例子有距离、信息增益、一致性和相关性。另一方面,包装法使用一种学习算法来度量所选特性的分类性能。在这个过程中可以使用不同的学习算法,比如k近邻(KNN
  • 将ace增强后的图像信息熵与图像标准差的乘积作为目标函数, ace的增益因子a作为待寻优的变量; 使用pso算法对ace的增益因子a进行寻优,并返回最优的增益因子; 将最优增益代入ace算法中,对图像进行增强; 采用...
  • 结果表明:改进的Fischer算法运算复杂度低,能够根据子载波信道增益大小分配比特.与8PSK固定调制方式MIMO-OFDM系统相比,更能够在保证系统信道质量所需误码率和总发射功率前提下,根据信道状态信息,动态分配比特和功率,...
  • 语音识别的MATLAB实现

    热门讨论 2009-03-03 21:39:18
    语音识别的MATLAB实现 声控小车结题报告 小组成员:关世勇 吴庆林 一、 项目要求: 声控小车是科大华为科技制作竞赛命题组的项目,其要求是编写一个语言识别程序并适当改装一个小型机动车,使之在一个预先不知道...
  • 将ace增强后的图像信息熵与图像标准差的乘积作为目标函数, ace的增益因子a作为待寻优的变量; 使用pso算法对ace的增益因子a进行寻优,并返回最优的增益因子; 将最优增益代入ace算法中,对图像进行增强; 采用引导...
  • ID3算法的基本思想是,选择信息增益最大的属性作为当前的分类属性。 看Tom M. Mitchell老师的《Machine Learing》第三章中的例子: 我们先解释一下这张表,表中有14条实例数据,就是我们的训练数据,其中Outlook,...
  • 分别采用硬判决、最大似然译码(MLD)、以及和积算法(SPA)三种译码方法对(7,4)汉明为了节省仿真时间,对随机产生8*105个二进制信息进行编译码,仿真结果表明,在加性高斯信道下,得到在误码率为10-4时 (7,4)...
  • 用于仿真LTE标准所需的MATLAB算法。  MATLAB作为《全面详解LTE:MATLAB建模、仿真与实现》一个鲜明的特点,通过一系列的程序,展现了每一个LTE的核心技术。通过一步步综合这些核心技术,最终建立LTE物理层的系统...
  • 本文所采用的基于熵的切割点和最小描述长度...过滤措施的例子有距离、信息增益、一致性和相关性。另一方面,包装法使用一种学习算法来度量所选特性的分类性能。在这个过程中可以使用不同的学习算法,比如k近邻(KNN)、
  • 本文所采用的基于熵的切割点和最小描述长度...过滤措施的例子有距离、信息增益、一致性和相关性。另一方面,包装法使用一种学习算法来度量所选特性的分类性能。在这个过程中可以使用不同的学习算法,比如k近邻(KNN)、
  • 用于仿真LTE标准所需的MATLAB算法。  MATLAB作为《全面详解LTE:MATLAB建模、仿真与实现》一个鲜明的特点,通过一系列的程序,展现了每一个LTE的核心技术。通过一步步综合这些核心技术,最终建立LTE物理层的系统...
  • 用于仿真LTE标准所需的MATLAB算法。  MATLAB作为《全面详解LTE:MATLAB建模、仿真与实现》一个鲜明的特点,通过一系列的程序,展现了每一个LTE的核心技术。通过一步步综合这些核心技术,最终建立LTE物理层的系统...
  • 一、简介 本文所采用的基于熵的切割点和最小描述...过滤措施的例子有距离、信息增益、一致性和相关性。另一方面,包装法使用一种学习算法来度量所选特性的分类性能。在这个过程中可以使用不同的学习算法,比如k近邻(KNN
  • 一、简介 本文所采用的基于熵的切割点和最小描述...过滤措施的例子有距离、信息增益、一致性和相关性。另一方面,包装法使用一种学习算法来度量所选特性的分类性能。在这个过程中可以使用不同的学习算法,比如k近邻(KNN
  • 一、简介 本文所采用的基于熵的切割点和最小描述...过滤措施的例子有距离、信息增益、一致性和相关性。另一方面,包装法使用一种学习算法来度量所选特性的分类性能。在这个过程中可以使用不同的学习算法,比如k近邻(KNN
  • 本书以仿真应用为中心,系统、详细地讲述了过程控制系统的仿真,并结合MATLAB/Simulink仿真工具的应用,通过大量经典的仿真实例,全面讲述过程控制系统的结构、原理、设计和参数整定等知识。 全书分为基础篇、实战...
  • DecisionTree.zip

    2019-12-18 11:17:54
    最近在学机器学习,本文件的内容正好是作业内容,文件内容主要是基于信息增益的决策树算法matlab实现代码。做作业的成果,拿来分享。

空空如也

空空如也

1 2
收藏数 38
精华内容 15
关键字:

matlab信息增益算法

matlab 订阅