ID3算法 matlab代码实现

对于决策树来说,主要有两种算法:ID3算法和C4.5算法,本资源实现的是决策树分类算法中的ID3算法，利用matlab编程实现

function [ tree ] = id3（ examples attributes activeAttributes）
%% ID3 算法 ，构建ID3决策树
    ...参考：https://github.com/gwheaton/ID3-Decision-Tree

% 输入参数：
% example: 输入矩阵；
% attributes: 属性值，含有Label；
% activeAttributes: 活跃的属性值；-11向量，1表示活跃；

% 输出参数：
% tree：构建的决策树；

%% 提供的数据为空，则报异常

if （isempty（examples））;
    error（‘必须提供数据！‘）;
end

% 常量
numberAttributes = length（activeAttributes）;%用于分类的属性数目
numberExamples = length（examples（:1））;%数据行数

% 创建树节点
tree = struct（‘value‘ ‘null‘）;

% 对class列进行统计
global NumofClass
matrix_class=zeros（1NumofClass）;
for i=1:NumofClass
    matrix_class（i）=length（find（examples（:numberAttributes+1）==i））;
end

%如果样本中的数据都属于一类，则标记为叶子节点
for i=1:NumofClass
    if（matrix_class（i）==numberExamples）
        tree.value=i;
        tree.NumofChild=0;
        return;
    end
end

global count;
% 如果活跃的属性为空或树的深度过高，则返回label最多的属性值
if （sum（activeAttributes） == 0） || count>30;
    tree.value=find（max（matrix_class））;
    tree.NumofChild=0;
    return
end

%% 计算当前属性的熵
currentEntropy=0;
for i=1:NumofClass
    if matrix_class（i）==0
        continue;
    end
    p=matrix_class（i）/numberExamples;
    currentEntropy=currentEntropy-p*log2（p）;
end

%% 寻找最大增益
gains = -1*ones（1numberAttributes）; % 初始化增益
%NumofActiveAttributes=length（find（activeAttributes~=0））;
for i=1:numberAttributes;
    if （activeAttributes（i）~=0） % 该属性仍处于活跃状态，对其更新
        matrix=zeros（6NumofClass）;  %计数矩阵行为活跃属性，列为类别
        for j=1:numberExamples;
            a=examples（ji）;%row a
            b=examples（jnumberAttributes+1）;%column b
            matrix（ab）=matrix（ab）+1;
        end     
        %计算当前属性每个类的熵
        matrix_Ent=zeros（16）;
        for m=1:6
            for n=1:NumofClass
                if（matrix（mn）==0）
                    continue;
                else
                    tmp=matrix（mn）/numberExamples;
                    matrix_Ent（1m）=matrix_Ent（1m）-tmp*log2（tmp）;
                end
            end
        end
        tmp=0;
        for j=1:5
            if（matrix_Ent（1j）==0）
                continue;
            end
            tmp=tmp+（sum（matrix（j:））/numberExamples）*matrix_Ent（1j）;
        end
        gains（i） = currentEntropy - tmp;
    end
end

% 选出最大增益
[~ bestAttribute] = max（gains）;
% 设置相应值
tree.value = attributes{bestAttribute};
% 去活跃状态
activeAttributes（bestAttribute） = 0;

% 根据bestAttribute把数据进行分组
NumofChild=1;
for i=1:6
    examples_new=examples（examples（:bestAttribute）==i:）;
    %leaf=struct（‘value‘‘null‘）;
    %叶子节点
    if（isempty（examples_new））
        %leaf.value=find（max（matrix_class））;
        %tree.child{NumofChild}=leaf;
        continue;
    end
    % 非叶子节点，递归
    tree.child{NumofChild} = id3（examples_new attributes activeAttributes）;
    tree.class{NumofChild}=i;
    NumofChild=NumofChild+1;
end
tree.NumofChild=NumofChild-1;
  
% 返回
return
end

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2017-01-12 10:59  ID3\
     文件        6875  2017-01-09 21:26  ID3\BalanceScale.txt
     文件       19889  2016-12-27 09:57  ID3\breast-cancer-wisconsin.data
     文件         220  2017-01-09 20:40  ID3\Bullons.txt
     文件       51867  2016-12-27 10:00  ID3\car.data
     文件       25920  2016-12-30 19:48  ID3\CarEvaluation.txt
     文件        3178  2016-12-30 19:54  ID3\id3.m
     文件        1397  2017-01-12 10:15  ID3\ID3_decision_tree.m
     文件         888  2017-01-12 10:59  ID3\id3_preprocess.m
     文件         984  2017-01-09 20:48  ID3\id3_test.m
     文件        8726  2016-12-27 10:02  ID3\machine.data
     文件        1478  2016-12-30 21:20  ID3\print_tree.m
     文件         707  2017-01-12 10:56  ID3\tree_plot.m