• 一、实验目的

        通过决策树的相关知识，使用C4.5生成算法对给出的数据集构建决策树模型。所给数集为14个关于天气情况的数据，需要根据所给的数据作出是否外出打球分类判断。每个数据有4个属性，分别为：Outlook, Temperature, Humidity和 Windy等。最后一列每种天气样本下，是否外出打球的分类。实验过程所使用的编程软件为MATLAB仿真软件，利用MATLAB实现算法及分类。

• 二、实验内容

        用表1数据集运用C4.5算法生成决策树。

• 三、实验数据

   表1每一行代表一种天气样本，共有14个样本；一共6列，其中第6列为类别标志属性，共有2类，分别标记为‘Yes’、‘No’对于两种不同分类结果；类别‘Yes’共有9个样本，类别‘No’共有5个样本。

  由于数据集中每个样本的数据都是完整的，没有空缺值，所以没有对该数据集进行必要的数据清洗工作。

表1.    原始数据

	Outlook	Temperature	Humidity	Windy	Play?
D1	Sunny	Hot	High	Weak	No
D2	Sunny	Hot	High	Strong	No
D3	Overcast	Hot	High	Weak	Yes
D4	Rain	Mild	High	Weak	Yes
D5	Rain	Cool	Normal	Weak	Yes
D6	Rain	Cool	Normal	Strong	No
D7	Overcast	Cool	Normal	Strong	Yes
D8	Sunny	Mild	High	Weak	No
D9	Sunny	Cool	Normal	Weak	Yes
D10	Rain	Mild	Normal	Weak	Yes
D11	Sunny	Mild	Normal	Strong	Yes
D12	Overcast	Mild	High	Strong	Yes
D13	Overcast	Hot	Normal	Weak	Yes
D14	Rain	Mild	High	Strong	No

表2.预处理后数据

	Outlook	Temperature	Humidity	Windy	Play?
D1	0	2	0	0	0
D2	0	2	0	1	0
D3	1	2	0	0	1
D4	2	1	0	0	1
D5	2	0	1	0	1
D6	2	0	1	1	0
D7	1	0	1	1	1
D8	0	1	0	0	0
D9	0	0	1	0	1
D10	2	1	1	0	1
D11	0	1	1	1	1
D12	1	1	0	1	1
D13	1	2	1	0	1
D14	2	1	0	1	0

• 四、实验步骤

（1）决策树分类算法的介绍：

        在没有相关领域知识的情况下，从海量数据中生成分类器的一种特别有效的方法即是生成一棵决策树（decisiontree)。决策树表示方法是应用最为广泛的逻辑方法之一，它能从一组既没有次序又没有规则的实例中挖掘出使用决策树表示形式的分类规则。决策树分类算法主要利用自顶向下的递归方式，在决策树的内部结点进行属性值之间的比较，并且依据不同的属性值判断从当前结点向下的分支，在决策树的叶子结点得出结论。事实上，从决策树的根结点到每一个叶子结点的一条路径即对应着一条合取规则，整棵决策树即对应着一组析取表达式规则。

        基于决策树的分类算法的一个最大的优点即是其在学习过程中不要求使用者了解相关问题所涉及的专业知识（这同时也是其最大的缺点），只要训练结果能用属性﹣结论式表示出来，即能够使用这一算法来学习。

        决策树是应用非常广泛的分类方法，其算法通常可分为两个阶段，前一阶段称为决策树生成算法；后一阶段称为决策树修剪算法。在此，主要介绍两种决策树生成算法：ID3算法和C4.5算法。

        ID3算法原理：

        决策树中任何一个非叶子结点对应着一个非类别属性，树枝代表这个属性的值。一个叶子结点表示从该决策树的根结点到叶子结点之间的路径对应的记录所属的类别属性值。任何一个非叶子结点都将与属性中具有最大信息量的非类别属性相关联。使用信息增益来选择可以最好地将样本进行分类的属性。

        计算信息增益过程如下：

        1.我们假设一个这样的数据样本集S，其中数据样本集S包含了s个数据样本，假设类别属性具有m个不同的值（判断指标）：Ci(i=1,2,3,…,m)，Si是Ci中的样本数，对于一个样本集总的信息熵为：

        其中，Pi表示任意样本属于Ci的概率，也可以用si/s 进行估计。我们假设一个属性A具有k个不同的值 {a1,a2,…,ak}, 利用属性A将数据样本S划分为k个子集{S1，S2，…，Sk}，其中Sj包含了集合S中属性A取aj值的样本。若是选择了属性A为测试属性，则这些子集就是从集合S的节点生长出来的新的叶子节点。设Sij是子集Sj中类别为Ci的样本数，则根据属性A划分样本的信息熵值为：

最后，我们利用属性A划分样本集S后得到的信息熵增益为：

C4.5算法原理：C4.5算法是由ID3算法演变而来的，使用了信息增益比例的概念。

信息增益比例概念是在信息增益概念的基础上发展起来的，任何一个属性的信息增益比例可以使用以下的公式给出：

GainRatio(A)=

其中，

（2）C4.5算法的流程图

（3）由ID3算法改为C4.5算法，主要在SelectFeature.m文件里修改增加如下代码用于计算信息熵和计算信息增益增益比：

SplitI=0;

SplitI = SplitI- prob *log2(prob);%计算信息熵

GainRatio=CurGain/SplitI;%计算增益比例

各部分的代码与注释如下所示：

• ①main_Tree.m

clc;
clear;
load Data

CreatTree(Data);
% 用C4.5算法构建决策树，输入预处理后的数据

• ②CreatTree.m

function CreatTree(data)
% %% 用C4.5算法构建决策树，输入预处理后的数据
n = size(data, 2); % 取出data的总列数

disp('original data:');

disp(data); % 输出预处理后的表格数据

ClassList = data(:, n);  % 取出数据最后一列，该列为类别标签

ClassCount = length(unique(ClassList));  % 类别标签个数

if ClassCount == 1   % 若只有一个标签，说明当前已达到叶子节点，结束
    
    disp('final data: ');
    
    disp(data);
    
    disp('The current classification is over');
    
    return;
    
end

BestFeature = SelectFeature(data);  % 选取使熵增益最大的属性?????

disp(['BestFeature : ', num2str(BestFeature)]); % 输出该属性各标签的信息

LabelList = unique(data(: , BestFeature)); % 对该属性的标签进行排列

NumLabel = length(LabelList); % 统计标签类别有多少个

for i = 1 : NumLabel  % 以该属性的每个标签为父节点生成子树
    
    Subset = SplitData(data, BestFeature, i);  % 得到该标签下的数据子集
    
    CreatTree(Subset);  % 递归调用，生成子树
    
end
end

③SelectFesture.m

function [BestFeature] =SelectFeature(data)
%% 选取数据集中使得熵增益最大的属性

[m , n] = size(data);%取出行数和列数

BaseEntropy = CalEntropy(data);  % 计算数据的初始熵

NumFeture = n - 1; % 倒数第二列

BestGain = 0;

for i = 1: NumFeture  % 遍历所有属性，得到熵增益最大的属性；
    
    LabelList = unique(data(: , i)); % 排序每一列标记
    
    NumLabel = length(LabelList); % 每个属性的标签个数
    %初始化
    CurEntropy = 0;
    SplitI=0;
    
    for j = 1 : NumLabel % 计算每一个属性的每一个标签的熵
        
        prob = length(find(data(: , i) == LabelList(j) )) / m;  % 该标签在该属性中出现的概率，93第九行
        
        CurEntropy = CurEntropy + prob * CalEntropy(SplitData(data, i, j));%计算该标签的熵，93 
        
        SplitI = SplitI- prob *log2(prob);% 计算信息熵
        
    end
    
    CurGain = BaseEntropy - CurEntropy; % 熵增益
    
    GainRatio=CurGain/SplitI;%信息增益比例
    
    if  GainRatio > BestGain % 取最高的信息增益比例
        
        BestGain = GainRatio;
        
        BestFeature = i;
        
    end
    
end
        
end

• ④SplitData.m

function [Subset] = SplitData(data, feature, label)
%%  将数据集按照某个属性的某个标签分割得到子集，

%输入参数feature为属性，label为该属性的标签。


m = size(data, 1); % 取出行数

Subset = data;

Subset(: , feature) = []; % 将Subset中属于第feature个的所有标签取空

LabelList = unique(data(:, feature)); % 对数据集的第feature列的标签排列

k = 0;

for i = 1 : m %分割各类的标签
    
    if data(i , feature) ~= LabelList(label)
        
        Subset(i - k , :) = [];
        
        k = k + 1;
        
    end
    
end



end

• ⑤CalEntropy.m

  function [Entropy ] =  CalEntropy(data)
  %% 计算当前数据集的熵
          [m , n] = size(data); % 取出数据集行数和列数
          
          LabelList = unique(data(:, n)); % 对数据集的最后一列排序
          
          NumLabel = length(LabelList); % 统计出标签的类别有几个
          
          Entropy = 0;
          
          for i = 1: NumLabel
              
              prob =  length(find(data(: , n) == LabelList(i) )) / m;
              
              Entropy = Entropy - prob * log2(prob); % 计算出初始熵
              
          end
          
  end
  
  

• 五、实验结果：

• 利用C4.5算法生成决策树如下图所示：

•