一般地，一个决策树包含一个根节点，若干个内部节点和若干个叶节点，叶结点对应决策结果，其他每个节点对应于一个属性测试，每个结点包含的样本集合根据属性测试的结果被划分到子节点中；根节点包含样本全集，从根节点到每个叶节点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一颗泛化能力强，处理未见实例能力强的决策树。
信息熵
信息熵是度量样本集合纯度最常用的一种指标，假定当前样本集合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
