信息增益matlab实现

python基础

浏览数:44

2019-8-29

一般地,一个决策树包含一个根节点,若干个内部节点和若干个叶节点,叶结点对应决策结果,其他每个节点对应于一个属性测试,每个结点包含的样本集合根据属性测试的结果被划分到子节点中;根节点包含样本全集,从根节点到每个叶节点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一颗泛化能力强,处理未见实例能力强的决策树。

信息熵
信息熵是度量样本集合纯度最常用的一种指标,假定当前样本集合D中第k类样本所占比例为pk(1,2,..|y|),则D的信息熵定义为


其中Ent(D)的值越小,则D的纯度越高。

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

一般而言,信息增益越大,则意味着使用属性a来进行划分所得的”纯度提升”越大。因此,我们可以用信息增益来进行决策树的划分属性选择。

实例分析
以下表的数据为例:其中有17个训练正例,学习目标是预测是不是好瓜的决策树。分类目标|Y|=2

信息熵计算得




上述实现代码为

close all;
clear all;
clc;
data = csvread('watermelon2.0.csv');
InforGain = gain(data);

function InforGain = gain(data) 
    [m, n] = size(data);
    InforGain = zeros(n-1,2);
    labels = data(:,n);
    for i=1:n
        tmp{i} = [];
        percen{i} = [];
        col = data(:,i);
        unicol = unique(col);
        %计算每一列有几类,并把每一类的信息熵和比例存储起来
        for j = 1:length(unicol)
            num = length(find(col==unicol(j)));
            pnum = length(find(col==unicol(j) & labels == 1));
            rate = pnum/num;
            if i==7
                rate = num/length(labels);
            end
            gain = -(rate*log2(rate)+(1-rate)*log2(1-rate));
            tmp{i}=[tmp{i} gain];
            percen{i}=[percen{i} num/length(col)];
        end
    end
    %整体信息熵
    InforEntropy = tmp{length(tmp)}(1);
    %将NAN转化为0
    for i = 1:length(tmp)
        tmp{i}(isnan(tmp{i})) = 0;
        %disp(tmp{i});
    end
    %求每一个属性列的信息增益
    for i = 1:length(percen)-1
        InforGain(i,:) = [i,roundn(InforEntropy-sum(tmp{i}.*percen{i}),-3)];
        disp(InforEntropy-sum(tmp{i}.*percen{i}));
    end

作者:听城