数据挖掘算法，分类树的C4.5算法，用于模式分类.zip

function D = C4_5(train_features, train_targets, inc_node, region) % Classify using Quinlan's C4.5 algorithm % Inputs: % features - Train features % targets - Train targets % inc_node - Percentage of incorrectly assigned samples at a node % region - Decision region vector: [-x x -y y number_of_points] % % Outputs % D - Decision sufrace %NOTE: In this implementation it is assumed that a feature vector with fewer than 10 unique values (the parameter Nu) %is discrete, and will be treated as such. Other vectors will be treated as continuous [Ni, M] = size(train_features); inc_node = inc_node*M/100; Nu = 10; %For the decision region N = region(5); mx = ones(N,1) * linspace (region(1),region(2),N); my = linspace (region(3),region(4),N)' * ones(1,N); flatxy = [mx(:), my(:)]'; %Preprocessing %[f, 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,N^2));; %Find which of the input features are discrete, and discretisize the corresponding %dimension on the decision region discrete_dim = zeros(1,Ni); for i = 1:Ni, Nb = length(unique(train_features(i,:))); if (Nb <= Nu), %This is a discrete feature discrete_dim(i) = Nb; [H, flatxy(i,:)] = high_histogram(flatxy(i,:), Nb); end end %Build the tree recursively disp('Building tree') tree = make_tree(train_features, train_targets, inc_node, discrete_dim, max(discrete_dim), 0); %Make the decision region according to the tree disp('Building decision surface using the tree') targets = use_tree(flatxy, 1:N^2, tree, discrete_dim, unique(train_targets)); D = reshape(targets,N,N); %END function targets = use_tree(features, indices, tree, discrete_dim, Uc) %Classify recursively using a tree targets = zeros(1, size(features,2)); if (tree.dim == 0) %Reached the end of the tree targets(indices) = tree.child; break end %This is not the last level of the tree, so: %First, find the dimension we are to work on dim = tree.dim; dims= 1:size(features,1); %And classify according to it if (discrete_dim(dim) == 0), %Continuous feature in = indices(find(features(dim, indices) <= tree.split_loc)); targets = targets + use_tree(features(dims, :), in, tree.child(1), discrete_dim(dims), Uc); in = indices(find(features(dim, indices) > tree.split_loc)); targets = targets + use_tree(features(dims, :), in, tree.child(2), discrete_dim(dims), Uc); else %Discrete feature Uf = unique(features(dim,:)); for i = 1:length(Uf), in = indices(find(features(dim, indices) == Uf(i))); targets = targets + use_tree(features(dims, :), in, tree.child(i), discrete_dim(dims), Uc); end end %END use_tree function tree = make_tree(features, targets, inc_node, discrete_dim, maxNbin, base) %Build a tree recursively [Ni, L] = size(features); Uc = unique(targets); tree.dim = 0; %tree.child(1:maxNbin) = zeros(1,maxNbin); tree.split_loc = inf; if isempty(features), break end %When to stop: If the dimension is one or the number of examples is small if ((inc_node > L) | (L == 1) | (length(Uc) == 1)), H = hist(targets, length(Uc)); [m, largest] = max(H); tree.child = Uc(largest); break end %Compute the node's I for i = 1:length(Uc), Pnode(i) = length(find(targets == Uc(i))) / L; end Inode = -sum(Pnode.*log(Pnode)/log(2)); %For each dimension, compute the gain ratio impurity %This is done separately for discrete and continuous features delta_Ib = zeros(1, Ni); split_loc = ones(1, Ni)*inf; for i = 1:Ni, data = features(i,:); Nbins = length(unique(data)); if (discrete_dim(i)), %This is a discrete feature P = zeros(length(Uc), Nbins); 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)); else %This is a continuous feature P = zeros(length(Uc), 2); %Sort the features [sorted_data, indices] = sort(data); sorted_targets = targets(indices); %Calculate the information for each possible split I = zeros(1, L-1); for j = 1:L-1, for k =1:length(Uc), P(k,1) = length(find(sorted_targets(1:j) == Uc(k))); P(k,2) = length(find(sorted_targets(j+1:end) == Uc(k))); end Ps = sum(P)/L; P = P/L; info = sum(-P.*log(eps+P)/log(2)); I(j) = Inode - sum(info.*Ps); end [delta_Ib(i), s] = max(I); split_loc(i) = sorted_data(s); end end %Find the dimension minimizing delta_Ib [m, dim] = max(delta_Ib); dims = 1:Ni; tree.dim = dim; %Split along the 'dim' dimension Nf = unique(features(dim,:)); Nbins = length(Nf); if (discrete_dim(dim)), %Discrete feature for i = 1:Nbins, indices = find(features(dim, :) == Nf(i)); tree.child(i) = make_tree(features(dims, indices), targets(indices), inc_node, discrete_dim(dims), maxNbin, base); end else %Continuous feature tree.split_loc = split_loc(dim); indices1 = find(features(dim,:) <= split_loc(dim)); indices2 = find(features(dim,:) > split_loc(dim)); tree.child(1) = make_tree(features(dims, indices1), targets(indices1), inc_node, discrete_dim(dims), maxNbin); tree.child(2) = make_tree(features(dims, indices2), targets(indices2), inc_node, discrete_dim(dims), maxNbin); end