Daniel@0: % Here the training data is adapted from Russell95 book. See restaurant.names for description.
Daniel@0: % (1) Use infomation-gain as the split testing score, we get the the same decision tree as the book Russell 95 (page 537),
Daniel@0: % and the Gain(Patrons) is 0.5409, equal to the result in Page 541 of Russell 95. (see below output trace)
Daniel@0: % (Note: the dtree in that book has small compilation error, the Type node is from YES of Hungry node, not NO.)
Daniel@0: % (2) Use gain-ratio (Quilan 93), the splitting defavorite attribute with more values. (e.g. the Type attribute here)
Daniel@0: 
Daniel@0: dtreeCPD=tree_CPD;
Daniel@0: 
Daniel@0: % load data
Daniel@0: fname = fullfile(BNT_HOME, 'examples', 'static', 'uci_data', 'restaurant', 'restaurant.data');
Daniel@0: data=load(fname);
Daniel@0: data=data';
Daniel@0: 
Daniel@0: %make the data be BNT compliant (values for discrete nodes are from 1-n, here n is the node size)
Daniel@0:   % e.g. if the values are [0 1 6], they must be mapping to [1 2 3]
Daniel@0: %data=transform_data(data,'tmp.dat',[]); %here no cts nodes
Daniel@0: 
Daniel@0: % learn decision tree from data 
Daniel@0: ns=2*ones(1,11);
Daniel@0: ns(5:6)=3;
Daniel@0: ns(9:10)=4;
Daniel@0: dtreeCPD1=learn_params(dtreeCPD,1:11,data,ns,[]);
Daniel@0: 
Daniel@0: % evaluate on data
Daniel@0: [score,outputs]=evaluate_tree_performance(dtreeCPD1,1:11,data,ns,[]);
Daniel@0: fprintf('Accuracy in training data %6.3f\n',score);
Daniel@0: 
Daniel@0: % show decision tree using graphpad
Daniel@0: 
Daniel@0: 
Daniel@0: 
Daniel@0: % --------------------------Output trace: using Information-Gain------------------------------
Daniel@0: % The splits are Patron, Hungry, Type, Fri/Sat
Daniel@0: % *********************************
Daniel@0: % Create node 1 split at 5 gain 0.5409 Th 0. Class 1 Cases 12 Error 6 
Daniel@0: % Create leaf node(onecla) 2. Class 1 Cases 2 Error 0 
Daniel@0: % Add subtree node 2 to 1. #nodes 2
Daniel@0: % Create leaf node(onecla) 3. Class 2 Cases 4 Error 0 
Daniel@0: % Add subtree node 3 to 1. #nodes 3
Daniel@0: % Create node 4 split at 4 gain 0.2516 Th 0. Class 1 Cases 6 Error 2 
Daniel@0: % Create leaf node(onecla) 5. Class 1 Cases 2 Error 0 
Daniel@0: % Add subtree node 5 to 4. #nodes 5
Daniel@0: % Create node 6 split at 9 gain 0.5000 Th 0. Class 1 Cases 4 Error 2 
Daniel@0: % Create leaf node(nullset) 7. Father 6 Class 1
Daniel@0: % Create node 8 split at 3 gain 1.0000 Th 0. Class 1 Cases 2 Error 1 
Daniel@0: % Create leaf node(onecla) 9. Class 1 Cases 1 Error 0 
Daniel@0: % Add subtree node 9 to 8. #nodes 9
Daniel@0: % Create leaf node(onecla) 10. Class 2 Cases 1 Error 0 
Daniel@0: % Add subtree node 10 to 8. #nodes 10
Daniel@0: % Add subtree node 8 to 6. #nodes 10
Daniel@0: % Create leaf node(onecla) 11. Class 2 Cases 1 Error 0 
Daniel@0: % Add subtree node 11 to 6. #nodes 11
Daniel@0: % Create leaf node(onecla) 12. Class 1 Cases 1 Error 0 
Daniel@0: % Add subtree node 12 to 6. #nodes 12
Daniel@0: % Add subtree node 6 to 4. #nodes 12
Daniel@0: % Add subtree node 4 to 1. #nodes 12
Daniel@0: % ********************************
Daniel@0: % 
Daniel@0: % Note:
Daniel@0: % ***Create node 4 split at 4 gain 0.2516 Th 0. Class 1 Cases 6 Error 2 
Daniel@0: % This mean we create a new node number 4, it is splitting at the attribute 4, and info-gain is 0.2516, 
Daniel@0: % "Th 0" means threshhold for splitting continous attribute, "Class 1" means the majority class at node 4 is 1,
Daniel@0: % and "Cases 6" means it has 6 cases attached to it, "Error 2" means it has two errors if changing the class lable of 
Daniel@0: % all the cases in it to the majority class.
Daniel@0: % *** Add subtree node 12 to 6. #nodes 12
Daniel@0: % It means we add the child node 12 to node 6.
Daniel@0: % *** Create leaf node(onecla) 10. Class 2 Cases 1 Error 0 
Daniel@0: % here 'onecla' means all cases in this node belong to one class, so no need to split further. 
Daniel@0: %      'nullset' means no training cases belong to this node, we use its parent node majority class as its class
Daniel@0: % 
Daniel@0: % 
Daniel@0: % 
Daniel@0: % ---------------Output trace: using GainRatio-----------------------
Daniel@0: % The splits are Patron, Hungry, Fri/Sat, Price
Daniel@0: % 
Daniel@0: % 
Daniel@0: % Create node 1 split at 5 gain 0.3707 Th 0. Class 1 Cases 12 Error 6 
Daniel@0: % Create leaf node(onecla) 2. Class 1 Cases 2 Error 0 
Daniel@0: % Add subtree node 2 to 1. #nodes 2
Daniel@0: % Create leaf node(onecla) 3. Class 2 Cases 4 Error 0 
Daniel@0: % Add subtree node 3 to 1. #nodes 3
Daniel@0: % Create node 4 split at 4 gain 0.2740 Th 0. Class 1 Cases 6 Error 2 
Daniel@0: % Create leaf node(onecla) 5. Class 1 Cases 2 Error 0 
Daniel@0: % Add subtree node 5 to 4. #nodes 5
Daniel@0: % Create node 6 split at 3 gain 0.3837 Th 0. Class 1 Cases 4 Error 2 
Daniel@0: % Create leaf node(onecla) 7. Class 1 Cases 1 Error 0 
Daniel@0: % Add subtree node 7 to 6. #nodes 7
Daniel@0: % Create node 8 split at 6 gain 1.0000 Th 0. Class 2 Cases 3 Error 1 
Daniel@0: % Create leaf node(onecla) 9. Class 2 Cases 2 Error 0 
Daniel@0: % Add subtree node 9 to 8. #nodes 9
Daniel@0: % Create leaf node(nullset) 10. Father 8 Class 2
Daniel@0: % Create leaf node(onecla) 11. Class 1 Cases 1 Error 0 
Daniel@0: % Add subtree node 11 to 8. #nodes 11
Daniel@0: % Add subtree node 8 to 6. #nodes 11
Daniel@0: % Add subtree node 6 to 4. #nodes 11
Daniel@0: % Add subtree node 4 to 1. #nodes 11
Daniel@0: % 
Daniel@0: %