算法分析与设计 决策树算法
一、 程序代码：
1.tree_plot.m
function tree_plot( p ,nodevalues)
%% 参考treeplot函数
[x,y,h]=treelayout(p); f = find(p~=0); pp = p(f);
X = [x(f); x(pp); NaN(size(f))]; Y = [y(f); y(pp); NaN(size(f))];
X = X(:); Y = Y(:);
n = length(p); if n < 500,
hold on ;
plot (x, y, 'ro', X, Y, 'r-'); nodesize = length(x); for i=1:nodesize
% text(x(i)+0.01,y(i),['node' num2str(i)]); text(x(i)+0.01,y(i),nodevalues{1,i}); end hold off; else
plot (X, Y, 'r-'); end;
xlabel(['height = ' int2str(h)]); axis([0 1 0 1]); end
2.queue_push.m
function [ newqueue ] = queue_push( queue,item ) %% 进队
% cols = size(queue);
% newqueue =structs(1,cols+1);
newqueue=[queue,item]; end
3.queue_pop.m
function [ item,newqueue ] = queue_pop( queue ) %% 访问队列
if isempty(queue)
disp('队列为空，不能访问！'); return; end
item = queue(1); % 第一个元素弹出
newqueue=queue(2:end); % 往后移动一个元素位置 end
4.queue_curr_size.m
function [ length_ ] = queue_curr_size( queue ) %% 当前队列长度
length_= length(queue); end
5.print_tree.m
function [nodeids_,nodevalue_] = print_tree(tree) %% 打印树，返回树的关系向量 global nodeid nodeids nodevalue;
nodeids(1)=0; % 根节点的值为0 nodeid=0; nodevalue={}; if isempty(tree) disp('空树！'); return ; end
queue = queue_push([],tree);
while ~isempty(queue) % 队列不为空
[node,queue] = queue_pop(queue); % 出队列
visit(node,queue_curr_size(queue));
if ~strcmp(node.left,'null') % 左子树不为空
queue = queue_push(queue,node.left); % 进队 end
if ~strcmp(node.right,'null') % 左子树不为空
queue = queue_push(queue,node.right); % 进队 end end
%% 返回 节点关系，用于treeplot画图 nodeids_=nodeids;
nodevalue_=nodevalue; end
function visit(node,length_)
%% 访问node 节点，并把其设置值为nodeid的节点 global nodeid nodeids nodevalue; if isleaf(node)
nodeid=nodeid+1;
fprintf('叶子节点，node: %d\\t，属性值: %s\\n', ... nodeid, node.value);
nodevalue{1,nodeid}=node.value;
else % 要么是叶子节点，要么不是
%if isleaf(node.left) && ~isleaf(node.right) % 左边为叶子节点,右边不是 nodeid=nodeid+1;
nodeids(nodeid+length_+1)=nodeid; nodeids(nodeid+length_+2)=nodeid;
fprintf('node: %d\\t属性值: %s\\t，左子树为节点：node%d，右子树为节点：node%d\\n', ...
nodeid, node.value,nodeid+length_+1,nodeid+length_+2); nodevalue{1,nodeid}=node.value; end end
function flag = isleaf(node) %% 是否是叶子节点
if strcmp(node.left,'null') && strcmp(node.right,'null') % 左右都为空 flag =1; else
flag=0; end end
6.id3_preprocess.m
function [ matrix,attributes,activeAttributes ] = id3_preprocess() %% ID3算法数据预处理，把字符串转换为0,1编码
% 输出参数：
% matrix： 转换后的0,1矩阵；
% attributes: 属性和Label；
% activeAttributes : 属性向量，全1；
%% 读取数据
txt = { '序号' '天气' '是否周末' '是否有促销' '销量' '' '坏' '是' '是' '高' '' '坏' '是' '是' '高' '' '坏' '是' '是' '高' '' '坏' '否' '是' '高' '' '坏' '是' '是' '' '坏' '否' '是' '' '坏' '是' '否' '' '好' '是' '是' '' '好' '是' '否' '' '好' '是' '是' '' '好' '是' '是' '' '好' '是' '是' '' '好' '是' '是' '' '坏' '是' '是' '' '好' '否' '是' '' '好' '否' '是' '' '好' '否' '是' '' '好' '否' '是' '' '好' '否' '否' '' '坏' '否' '否' '' '坏' '否' '是' '' '坏' '否' '是' '' '坏' '否' '是' '' '坏' '否' '否' '' '坏' '是' '否' '' '好' '否' '是' '' '好' '否' '是' '' '坏' '否' '否' '' '坏' '否' '否' '' '好' '否' '否' '' '坏' '是' '否' '' '好' '否' '是' '' '好' '否' '否' '' '好' '否' '否' attributes=txt(1,2:end);
activeAttributes = ones(1,length(attributes)-1); data = txt(2:end,2:end);
%% 针对每列数据进行转换
'高' '高' '高' '高' '高' '高' '高' '高' '高' '低' '高' '高' '高' '高' '高' '低' '低' '低' '低' '低' '低' '低' '低' '低' '低' '低' '低' '低' '低' '低' } [rows,cols] = size(data); matrix = zeros(rows,cols); for j=1:cols
matrix(:,j) = cellfun(@trans2onezero,data(:,j)); end end
function flag = trans2onezero(data)
if strcmp(data,'坏') ||strcmp(data,'否')... ||strcmp(data,'低') flag =0; return ; end flag =1; end
7.ID3_decision_tree.m
%% 使用ID3决策树算法预测销量高低 clear ;
%% 数据预处理
disp('正在进行数据预处理...');
[matrix,attributes_label,attributes] = id3_preprocess();
%% 构造ID3决策树，其中id3()为自定义函数 disp('数据预处理完成，正在进行构造树...'); tree = id3(matrix,attributes_label,attributes);
%% 打印并画决策树
[nodeids,nodevalues] = print_tree(tree); tree_plot(nodeids,nodevalues);
disp('ID3算法构建决策树完成！'); 8.id3.m
function [ tree ] = id3( examples, attributes, activeAttributes ) %% ID3 算法 ，构建ID3决策树
...参考：https://github.com/gwheaton/ID3-Decision-Tree
% 输入参数：
% example: 输入0、1矩阵；
% attributes: 属性值，含有Label；
% activeAttributes: 活跃的属性值；-1,1向量，1表示活跃；
% 输出参数：