matlab实现的ID3 分类决策树 算法.doc

function D = ID3(train_features, train_targets, params, region) % Classify using Quinlans ID3 algorithm% Inputs:% features - Train features% targets - Train targets% params - Number of bins for the data, Percentage of incorrectly assigned samples at a node% region - Decision region vector: -x x -y y number_of_points% Outputs% D - Decision sufrace Ni, M = size(train_features); %NiM %Get parametersNbins, inc_node = process_params(params);inc_node = inc_node*M/100; %For the decision regionN = region(5);mx = ones(N,1) * linspace (region(1),region(2),N); %linspace()my = linspace (region(3),region(4),N) * ones(1,N);flatxy = mx(:), my(:); %Preprocessingf, t, UW, m = PCA(train_features, train_targets, Ni, region);train_features = UW * (train_features - m*ones(1,M);flatxy = UW * (flatxy - m*ones(1,N2); %First, bin the data and the decision region dataH, binned_features= high_histogram(train_features, Nbins, region);H, binned_xy = high_histogram(flatxy, Nbins, region); %Build the tree recursivelydisp(Building tree)tree = make_tree(binned_features, train_targets, inc_node, Nbins); %Make the decision region according to the treedisp(Building decision surface using the tree)targets = use_tree(binned_xy, 1:N2, tree, Nbins, unique(train_targets); D = reshape(targets,N,N);%END function targets = use_tree(features, indices, tree, Nbins, Uc)%Classify recursively using a tree targets = zeros(1, size(features,2); %size(features,2)features if (size(features,1) = 1), %Only one dimension left, so work on it for i = 1:Nbins, in = indices(find(features(indices) = i); if isempty(in), if isfinite(tree.child(i), targets(in) = tree.child(i); else %No data was found in the training set for this bin, so choose it randomally n = 1 + floor(rand(1)*length(Uc); targets(in) = Uc(n); end end end breakend %This is not the last level of the tree, so:%First, find the dimension we are to work ondim = tree.split_dim;dims= find(ismember(1:size(features,1), dim); %And classify according to itfor i = 1:Nbins, in = indices(find(features(dim, indices) = i); targets = targets + use_tree(features(dims, :), in, tree.child(i), Nbins, Uc);end %END use_tree function tree = make_tree(features, targets, inc_node, Nbins)%Build a tree recursively Ni, L = size(features);Uc = unique(targets); %When to stop: If the dimension is one or the number of examples is smallif (Ni = 1) | (inc_node L), %Compute the children non-recursively for i = 1:Nbins, tree.split_dim = 0; indices = find(features = i); if isempty(indices), if (length(unique(targets(indices) = 1), tree.child(i) = targets(indices(1); else H = hist(targets(indices), Uc); m, T = max(H); tree.child(i) = Uc(T); end else tree.child(i) = inf; end end breakend %Compute the nodes Ifor i = 1:Ni, Pnode(i) = length(find(targets = Uc(i) / L;endInode = -sum(Pnode.*log(Pnode)/log(2); %For each dimension, compute the gain ratio impuritydelta_Ib = zeros(1, Ni);P = zeros(length(Uc), Nbins);for i = 1:Ni, for j = 1:length(Uc), for k = 1:Nbins, indices = find(targets = Uc(j) & (features(i,:) = k); P(j,k) = length(indices); end end Pk = sum(P); P = P/L; Pk = Pk/sum(Pk); info = sum(-P.*log(eps+P)/log(2); delta_Ib(i) = (Inode-sum(Pk.*info)/-sum(Pk.*log(eps+Pk)/log(2);end %Find the dimension minimizing delta_Ib m, dim = max(delta_Ib); %Split along the dim dimensiontree.split_dim = dim;di