matlab实现的C4.5分类决策树算法

1、.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 incorrectlyassigned samples at a node%region- Decision region vector: -x x -yy number_of_points% Outputs

2、% 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 continuousNi, M= size(train_features);inc_node= inc_node*M/100;Nu= 10;%For the decisio

3、n regionN= 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);1 / 6.%flatxy= UW * (flatxy

4、 - m*ones(1,N2);%Findwhichoftheinputfeaturesarediscrete,anddiscretisize the corresponding%dimension on the decision regiondiscrete_dim = zeros(1,Ni);fori = 1:Ni,Nb = length(unique(train_features(i,:);if(Nb <= Nu),%This is a discrete featurediscrete_dim(i)= Nb;H, flatxy(i,:) =high_histogram(flatxy

5、(i,:), Nb);endend%Build the tree recursivelydisp('Building tree')tree= make_tree(train_features,train_targets, inc_node, discrete_dim,max(discrete_dim), 0);%Make the decision region according to the treedisp('Building decision surface using the tree')targets= use_tree(flatxy, 1:N2, t

6、ree,discrete_dim, unique(train_targets);D= reshape(targets,N,N);%ENDfunction targets = use_tree(features, indices, tree, discrete_dim, Uc)%Classify recursively using a treetargets = zeros(1, size(features,2);if(tree.dim = 0)%Reached the end of the tree2 / 6.targets(indices) = tree.child;breakend%Thi

7、s 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 itif(discrete_dim(dim) = 0),%Continuous featurein= indices(find(features(dim,indices) <= tree.split_loc);targets= targets +use_tree(features(dim

8、s, :), 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 featureUf= unique(features(dim,:);fori = 1:length(Uf),in= indices(find(features(dim,indic

9、es) = Uf(i);targets= targets +use_tree(features(dims, :), in, tree.child(i),discrete_dim(dims), Uc);endend%END use_treefunction tree = make_tree(features, targets, inc_node, discrete_dim, maxNbin, base)3 / 6.%Build a tree recursivelyNi, L= size(features);Uc= unique(targets);tree.dim= 0;%tree.child(1

10、:maxNbin) = zeros(1,maxNbin);tree.split_loc= inf;ifisempty(features),breakend%When to stop: If the dimension is one or the number of examples is smallif(inc_node> L)|(L= 1)|(length(Uc)= 1),H= hist(targets, length(Uc);m, largest= max(H);tree.child= Uc(largest);breakend%Compute the node's Ifori

11、 = 1:length(Uc),Pnode(i)= length(find(targets= Uc(i)/L;endInode = -sum(Pnode.*log(Pnode)/log(2);%For each dimension,computethegainratioimpurity%Thisisdone separatelyfordiscreteand continuousfeaturesdelta_Ib= zeros(1, Ni);split_loc= ones(1, Ni)*inf;fori = 1:Ni,data = features(i,:);Nbins= length(uniqu

12、e(data);if(discrete_dim(i),%This is a discrete feature4 / 6.P= zeros(length(Uc), Nbins);forj = 1:length(Uc),fork = 1:Nbins,indices= find(targets = Uc(j) &(features(i,:) = k);P(j,k) = length(indices);endendPk= sum(P);P= P/L;Pk= Pk/sum(Pk);info= sum(-P.*log(eps+P)/log(2);delta_Ib(i) =(Inode-sum(Pk

13、.*info)/-sum(Pk.*log(eps+Pk)/log(2);else%This is a continuous featureP = zeros(length(Uc), 2);%Sort the featuressorted_data, indices = sort(data);sorted_targets = targets(indices);%Calculate theinformationfor eachpossiblesplitI = zeros(1, L-1);forj = 1:L-1,fork =1:length(Uc),P(k,1)= length(find(sort

14、ed_targets(1:j)= Uc(k); P(k,2) =length(find(sorted_targets(j+1:end) = Uc(k); endPs= sum(P)/L;P= P/L;info= sum(-P.*log(eps+P)/log(2);I(j)= Inode - sum(info.*Ps);end5 / 6.delta_Ib(i), s = max(I);split_loc(i) = sorted_data(s);endend%Find the dimension minimizing delta_Ibm, dim = max(delta_Ib);dims= 1:N

15、i;tree.dim = dim;%Split along the 'dim' dimensionNf= unique(features(dim,:);Nbins= length(Nf);if(discrete_dim(dim),%Discrete featurefori = 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);endelse%Continuous featuretree.split_loc= split_loc(dim);indices1= find(features(dim,:) <=split_loc(dim);indices2= find(features(dim,