《matlab实现的C45分类决策树算法》由会员分享，可在线阅读，更多相关《matlab实现的C45分类决策树算法（6页珍藏版）》请在金锄头文库上搜索。
1、.function D = C4_5(train_features, train_targets, inc_node, region)% Classify using Quinlans 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% D-
2、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 decision reg
3、ionN= 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 - m*ones(1,N2
4、);%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(i,:), Nb);endend%
5、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, tree,discrete_dim, unique(train_targets
6、);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%This is not the last level of the tree, s
7、o: %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(dims, :), in, tree.child(2),discrete_dim(dims),
8、 Uc);else%Discrete featureUf= unique(features(dim,:);fori = 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);endend%END use_treefunction tree = make_tree(features, targets, inc_node, discrete_dim, maxN
9、bin, base)3 / 6.%Build a tree recursivelyNi, L= size(features);Uc= unique(targets);tree.dim= 0;%tree.child(1: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= h
10、ist(targets, length(Uc);m, largest= max(H);tree.child= Uc(largest);breakend%Compute the nodes Ifori = 1:length(Uc),Pnode(i)= length(find(targets= Uc(i)/L;endInode = -sum(Pnode.*log(Pnode)/log(2);%For each dimension,computethegainratioimpurity%Thisisdone separatelyfordiscreteand continuousfeaturesdel
11、ta_Ib= zeros(1, Ni);split_loc= ones(1, Ni)*inf;fori = 1:Ni,data = features(i,:);Nbins= length(unique(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);en
12、dendPk= 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 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(sorted_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
