本文代码均已在 MATLAB R2019b 测试通过,如有错误,欢迎指正。

ID3算法涉及了递归部分,有点难度,我打算最后一次实验来写,这次先写算法中最简单的部分:选择信息增益最大的一个条件属性作为根节点。

(一)决策树生成算法的基本原理

决策树是一种典型的分类方法,首先对数据进行处理,利用归纳算法生成可读的规则和决策树,然后使用决策树对新数据进行分类。决策树是类似流程图的倒立的树型结构。最顶层节点为根节点,是整个决策树的开始;树的每个内部节点表示在一个属性上的测试,其每个分支代表一个测试输出;树的每个叶节点代表一个类别。最后生成类似于下图所示的决策树。

(二)ID3算法的基本原理

ID3算法主要针对属性选择问题而提出,是决策树学习方法中最具影响和最为典型的算法。在ID3算法中,选择具有最大信息增益(information gain)的属性作为当前划分节点。在信息增益的计算中,运用了信息论中的熵(Entropy)概念作为启发式函数。
ID3算法的具体流程如下:
(1)对当前样本集合,计算所有属性的信息增益;
(2)选择信息增益最大的属性作为测试属性,把测试属性取值相同的样本划为同一个子样本集;
(3)若子样本集的类别属性只包含一个取值,则分支为叶子节点,将叶子节点的类别标记为类别属性的取值,返回调用处;否则对子样本集递归调用本算法。
- 信息增益:Gain(S, A)= Entropy(S) –Entropy(S, A)
- Entropy(S)是决策S初始的不确定性;
- Entropy(S, A)是收到A属性的信息后,决策S的不确定性;
- Gain(S, A)是属性A对决策S的信息增益;Gain(S, A)越大,说明属性A对降低决策S的不确定性起到的作用越大。

(三)Matlab初步实现ID3算法

以下所有matlab代码均由我自己编写,我认为写法比较简单。

clear;clc;

% 原始数据集data,最后一列为决策属性,其余为条件属性
data=[
0   2   0   0   0
0   2   0   1   0
1   2   0   0   1
2   1   0   0   1
2   0   1   0   1
2   0   1   1   0
1   0   1   1   1
0   1   0   0   0
0   0   1   0   1
2   1   1   0   1
0   1   1   1   1
1   1   0   1   1
1   2   1   0   1
2   1   0   1   0
];

[n,m]=size(data); % n行m列
S=data(:,m); % 决策属性S
S_unique=unique(S); % 对决策属性取值进行去重
S_num=length(S_unique); % 去重后属性取值个数
for i=1:S_num
    p(i)=sum(S_unique(i)==S)/n; % p(i)表示第i个决策属性取值的行数占n行元组中的比例
end
E0=-sum(p.*log2(p)); % 计算初始信息熵,E0=0.9403
fprintf("初始信息熵为%f\n",E0);

% m-1个条件属性,分别计算获得每个条件属性后的信息熵以及信息增益
% Gain(S,A)=Entropy(S)–Entropy(S,A)  
for k=1:m-1
    A=data(:,k);
    A_unique=unique(A);
    A_num=length(A_unique); % 去重后属性取值个数
    E(k)=0;
    % 取出属性A取值相同的行,构成一个数据子集,总共有A_num个不同的数据子集
    for i=1:A_num 
        % A==A_unique(i)返回一个取值0或1的逻辑向量,若为1说明A取值为A_unique(i)
        data_new=data(A==A_unique(i),:); % 取出属性A取值相同的行,将其构成数据子集
        % 以下均是对当前取出的数据子集进行操作
        S=data_new(:,m); % 决策属性S
        S_unique=unique(S); % 对决策属性取值进行去重
        S_num=length(S_unique); % 去重后属性取值个数
        [n_new,m_new]=size(data_new); % 当前取出的数据子集有n_new行m_new列
        p=zeros(1,S_num); % 一定要写这句来限制矩阵大小!防止之后计算sum(p.*log2(p))时计算多余的p
        for j=1:S_num
            p(j)=sum(S_unique(j)==S)/n_new; % p(j)表示第j个决策属性取值的行数占n_new行元组中的比例
        end
        w=n_new/n; % 当前数据子集的加权比重(当前数据子集行数占原数据子集行数的比例)
        E(k)=E(k)-w*sum(p.*log2(p));
    end
    G(k)=E0-E(k);
    fprintf("获得第%d个条件属性后,信息熵为%f,信息增益为%f\n",k,E(k),G(k));
end

[mx,mxpos]=max(G);
fprintf("\n结论:选择信息增益最大的第%d个条件属性作为根节点,其信息增益为:%f\n",mxpos,mx);

运行结果:

初始信息熵为0.940286
获得第1个条件属性后,信息熵为0.693536,信息增益为0.246750
获得第2个条件属性后,信息熵为0.911063,信息增益为0.029223
获得第3个条件属性后,信息熵为0.788450,信息增益为0.151836
获得第4个条件属性后,信息熵为0.892159,信息增益为0.048127

结论:选择信息增益最大的第1个条件属性作为根节点,其信息增益为:0.246750