决策树id3算法matlab实现

以下是使用MATLAB实现ID3算法的示例代码：

% 定义训练数据集
data = [1 0 1 0 1;
        1 0 1 1 1;
        1 1 1 0 0;
        0 0 1 0 1;
        0 0 0 0 0;
        0 1 1 0 0;
        0 1 0 1 0;
        0 1 0 1 1];

% 定义属性名称
attribute_names = {'Outlook', 'Temperature', 'Humidity', 'Windy'};

% 定义目标属性名称
target_attribute_name = 'PlayTennis';

% 调用ID3算法构建决策树
tree = id3(data, attribute_names, target_attribute_name);

% 定义测试数据集
test_data = [1 0 1 0;
             1 0 1 1;
             0 1 0 1];

% 对测试数据集进行分类
for i = 1:size(test_data, 1)
    classification = classify(tree, attribute_names, test_data(i,:));
    fprintf('Test data %d: %s\n', i, classification);
end

下面是ID3算法和分类函数的实现：

function tree = id3(data, attribute_names, target_attribute_name)
    % 获取目标属性的所有可能取值
    target_attribute = data(:,end);
    target_attribute_values = unique(target_attribute);

    % 如果数据集中所有实例的目标属性取值相同，则返回单节点决策树
    if numel(target_attribute_values) == 1
        tree.op = '';
        tree.kids = {};
        tree.class = target_attribute_values(1);
        return;
    end

    % 如果属性集为空，则返回单节点决策树，以数据集中出现最频繁的目标属性值作为该节点的类别
    if size(data, 2) == 1
        tree.op = '';
        tree.kids = {};
        tree.class = mode(target_attribute);
        return;
    end

    % 计算每个属性的信息增益
    [best_attribute_index, best_attribute_threshold] = choose_best_attribute(data);
    best_attribute_name = attribute_names{best_attribute_index};

    % 构建决策树
    tree.op = best_attribute_name;
    tree.threshold = best_attribute_threshold;
    tree.kids = {};

    % 根据最佳属性和其阈值将数据集分割成子集
    subsets = split_data(data, best_attribute_index, best_attribute_threshold);

    % 递归构建子树
    for i = 1:numel(subsets)
        subset = subsets{i};
        if isempty(subset)
            tree.kids{i} = struct('op', '', 'kids', {}, 'class', mode(target_attribute));
        else
            subtree = id3(subset, attribute_names, target_attribute_name);
            tree.kids{i} = subtree;
        end
    end
end

function [best_attribute_index, best_attribute_threshold] = choose_best_attribute(data)
    % 计算目标属性的熵
    target_attribute = data(:,end);
    target_attribute_entropy = entropy(target_attribute);

    % 计算每个属性的信息增益
    attributes = 1:size(data,2)-1;
    information_gains = zeros(numel(attributes),1);
    thresholds = zeros(numel(attributes), 1);

    for i = 1:numel(attributes)
        attribute_index = attributes(i);
        attribute_values = data(:,attribute_index);
        [threshold, information_gain] = choose_best_threshold(attribute_values, target_attribute);
        information_gains(i) = information_gain;
        thresholds(i) = threshold;
    end

    % 选择信息增益最大的属性
    [best_information_gain, best_attribute_index] = max(information_gains);
    best_attribute_threshold = thresholds(best_attribute_index);

    % 如果没有最佳阈值，则取属性值的中位数作为阈值
    if isnan(best_attribute_threshold)
        best_attribute_values = data(:,best_attribute_index);
        best_attribute_threshold = median(best_attribute_values);
    end
end

function [threshold, information_gain] = choose_best_threshold(attribute_values, target_attribute)
    % 对属性值进行排序
    [sorted_attribute_values, indices] = sort(attribute_values);
    sorted_target_attribute = target_attribute(indices);

    % 选择最佳阈值
    threshold = nan;
    best_information_gain = -inf;
    for i = 1:numel(sorted_attribute_values)-1
        % 计算当前阈值下的信息增益
        current_threshold = (sorted_attribute_values(i) + sorted_attribute_values(i+1)) / 2;
        current_information_gain = information_gain(sorted_target_attribute, sorted_attribute_values, current_threshold);

        % 如果当前信息增益比之前的更好，则更新最佳阈值和最佳信息增益
        if current_information_gain > best_information_gain
            threshold = current_threshold;
            best_information_gain = current_information_gain;
        end
    end

    information_gain = best_information_gain;
end

function subsets = split_data(data, attribute_index, threshold)
    % 根据属性和阈值将数据集分割成子集
    attribute_values = data(:,attribute_index);
    left_subset_indices = attribute_values <= threshold;
    right_subset_indices = attribute_values > threshold;

    % 构建左右子集
    left_subset = data(left_subset_indices,:);
    right_subset = data(right_subset_indices,:);

    subsets = {left_subset, right_subset};
end

function classification = classify(tree, attribute_names, instance)
    % 遍历决策树，对实例进行分类
    while ~isempty(tree.kids)
        attribute_index = find(strcmp(attribute_names, tree.op));
        attribute_value = instance(attribute_index);

        if attribute_value <= tree.threshold
            tree = tree.kids{1};
        else
            tree = tree.kids{2};
        end
    end

    classification = tree.class;
end

function e = entropy(target_attribute)
    % 计算目标属性的熵
    p = histc(target_attribute, unique(target_attribute)) / numel(target_attribute);
    p(p == 0) = [];
    e = -sum(p .* log2(p));
end

function ig = information_gain(target_attribute, attribute_values, threshold)
    % 计算信息增益
    n = numel(target_attribute);
    left_target_attribute = target_attribute(attribute_values <= threshold);
    right_target_attribute = target_attribute(attribute_values > threshold);

    left_entropy = entropy(left_target_attribute);
    right_entropy = entropy(right_target_attribute);

    p_left = numel(left_target_attribute) / n;
    p_right = numel(right_target_attribute) / n;

    ig = entropy(target_attribute) - p_left * left_entropy - p_right * right_entropy;
end

这个实现假设输入数据是一个矩阵，其中每行表示一个实例，每列表示一个属性，最后一列是目标属性。目标属性应该是二元的，即只有两个不同的取值。属性名称作为一个字符串向量传递，最后一个元素是目标属性名称。