ID3算法MATLAB实现，机器学习作业

ID3算法，使用熵最小策略构建决策树，MATLAB实现代码。对应中科大机器学习课程中ID3算法实现.

%% ID3函数，使用熵最小策略构建决策树，并打印显示
% zzhh@mail.ustc.edu.cn 创建时间：2019年3月17日
% 运行版本：R2018a（9.4.0.813654）win64
function myTree = ID3（datasetlabels）
% 输入参数：
% dataset：数据集，元胞数组或字符串数组
% labels：属性标签，元胞数组或字符串数组
% 输出参数：
% myTree：构建的决策树，containers.Map类型

myTree = createTree（datasetlabels）; %生成决策树
[nodeidsnodevaluebranchvalue] = print_tree（myTree）; %解析决策树
tree_plot（nodeidsnodevaluebranchvalue）; %画出决策树
end

%% 使用熵最小策略构建决策树
function myTree = createTree（datasetlabels）
% 输入参数：
% dataset：数据集，元胞数组或字符串数组
% labels：属性标签，元胞数组或字符串数组
% 输出参数：
% myTree：构建的决策树，containers.Map类型

% 数据为空，则报错
if（isempty（dataset））
    error（‘必须提供数据！‘）
end
size_data = size（dataset）;
% 数据大小与属性数量不一致，则报错
if （size_data（2）-1）~=length（labels）
    error（‘属性数量与数据集不一致！‘）
end

classList = dataset（:size_data（2））;
%全为同一类，熵为0，返回
if length（unique（classList））==1
    myTree =  char（classList（1））;
    return 
end
%%属性集为空，应该用找最多数的那一类，这里取值NONE
if size_data（2） == 1
    myTree =  ‘NONE‘;
    %myTree =  char（classList（1））;
    return
end
% 选取特征属性
bestFeature = chooseFeature（dataset）; 
bestFeatureLabel = char（labels（bestFeature））;
% 构建树
myTree = containers.Map;
leaf = containers.Map;
% 该属性下的不同取值 
featValues = dataset（:bestFeature）; 
uniqueVals = unique（featValues）;
% 删除该属性
labels=[labels（1:bestFeature-1） labels（bestFeature+1:length（labels））]; %删除该属性
% 对该属性下不同取值，递归调用ID3函数
for i=1:length（uniqueVals）
    subLabels = labels（:）‘;
    value = char（uniqueVals（i））;
    subdata = splitDataset（datasetbestFeaturevalue）;%数据集分割
    leaf（value） = createTree（subdatasubLabels）; %递归调用
    myTree（char（bestFeatureLabel）） = leaf;
end
end

%% 计算信息熵
function shannonEnt = calShannonEnt（dataset）
data_size = size（dataset）;
labels = dataset（:data_size（2））;
numEntries = data_size（1）;
labelCounts = containers.Map;
for i = 1:length（labels）
    label = char（labels（i））;
    if labelCounts.isKey（label）
        labelCounts（label） = labelCounts（label）+1; 
    else
        labelCounts（label） = 1;
    end  
end
shannonEnt = 0.0;
for key = labelCounts.keys
    key = char（key）;
    labelCounts（key）;
    prob = labelCounts（key） / numEntries;
    shannonEnt = shannonEnt - prob*（log（prob）/log（2））;
end  
end

%% 选择熵最小的属性特征
function bestFeature=chooseFeature（dataset~）
baseEntropy = calShannonEnt（dataset）;
data_size = size（dataset）;
numFeatures = data_size（2） - 1;
minEntropy = 2.0;
bestFeature = 0;
for i = 1:numFeatures
    uniqueVals = unique（dataset（:i））;
    newEntropy = 0.0;
    for j=1:length（uniqueVals）
        value = uniqueVals（j）;
        subDataset = splitDataset（datasetivalue）;
        size_sub = size（subDataset）;
        prob = size_sub（1）/data_size（1）;
        %ShannonEnt = calShannonEnt（subDataset）;
        newEntropy = newEntropy + prob*calShannonEnt（subDataset）;
    end
    %gain = baseEntropy- newEntropy;
    if newEntropy        minEntropy = newEntropy;
        bestFeature = i;
    end
end
end
%% 分割数据集，取出该特征

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      53649  2019-03-17 14:25  ID3_shared\car_data.csv

     文件        425  2019-03-17 13:44  ID3_shared\golf.csv

     文件       5594  2019-04-21 21:58  ID3_shared\ID3.m

     文件       1396  2019-05-22 19:05  ID3_shared\ID3_run.m

     文件        464  2019-03-17 14:17  ID3_shared\sale.csv

     文件        614  2019-03-11 16:17  ID3_shared\watermelon.csv

     目录          0  2019-06-05 16:20  ID3_shared

----------- ---------  ---------- -----  ----

                62142                    7