diff options
Diffstat (limited to 'sourcecodes/bnt-master/BNT/examples/static/dtree')
8 files changed, 311 insertions, 0 deletions
diff --git a/sourcecodes/bnt-master/BNT/examples/static/dtree/CVS/Entries b/sourcecodes/bnt-master/BNT/examples/static/dtree/CVS/Entries new file mode 100644 index 00000000..81dc9c31 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/examples/static/dtree/CVS/Entries @@ -0,0 +1,6 @@ +/test_housing.m/1.1.1.1/Wed May 29 15:59:54 2002// +/test_restaurants.m/1.1.1.1/Wed May 29 15:59:54 2002// +/test_zoo1.m/1.1.1.1/Wed May 29 15:59:54 2002// +/tmp.dot/1.1.1.1/Wed May 29 15:59:54 2002// +/transform_data_into_bnt_format.m/1.1.1.1/Wed May 29 15:59:54 2002// +D diff --git a/sourcecodes/bnt-master/BNT/examples/static/dtree/CVS/Repository b/sourcecodes/bnt-master/BNT/examples/static/dtree/CVS/Repository new file mode 100644 index 00000000..f45a3265 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/examples/static/dtree/CVS/Repository @@ -0,0 +1 @@ +FullBNT/BNT/examples/static/dtree diff --git a/sourcecodes/bnt-master/BNT/examples/static/dtree/CVS/Root b/sourcecodes/bnt-master/BNT/examples/static/dtree/CVS/Root new file mode 100644 index 00000000..f3bd14a6 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/examples/static/dtree/CVS/Root @@ -0,0 +1 @@ +:ext:nsaunier@bnt.cvs.sourceforge.net:/cvsroot/bnt diff --git a/sourcecodes/bnt-master/BNT/examples/static/dtree/test_housing.m b/sourcecodes/bnt-master/BNT/examples/static/dtree/test_housing.m new file mode 100644 index 00000000..40184b47 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/examples/static/dtree/test_housing.m @@ -0,0 +1,87 @@ +% Here the training data is adapted from UCI ML repository, 'housing' data +% Input variables: 12 continous, one binary +% Ouput variables: continous +% The testing result trace is in the end of this script, it is same to the graph in page 219 of +% Leo Brieman etc. 1984 book titled "Classification and regression trees". + +dtreeCPD=tree_CPD; + +% load data +fname = fullfile(BNT_HOME, 'examples', 'static', 'uci_data', 'housing', 'housing.data'); +data=load(fname); +data=data'; +data=transform_data_into_bnt_format(data,[1:3,5:14]); + +% learn decision tree from data +ns=1*ones(1,14); +ns(4)=2; +dtreeCPD1=learn_params(dtreeCPD,1:14,data,ns,[1:3,5:14],'stop_cases',5,'min_gain',0.006); + +% evaluate on data +[score,outputs]=evaluate_tree_performance(dtreeCPD1,1:14,data,ns,[1:3,5:14]); +fprintf('Mean square deviation (using regression tree to predict) in old training data %6.3f\n',score); + + +% show decision tree using graphpad +% It should be easy, but still not implemented + + + +% >> test_housing +% Create node 1 split at 6 gain 38.2205 Th 6.939000e+000. Mean 22.5328 Cases 506 +% Create node 2 split at 13 gain 14.4503 Th 1.437000e+001. Mean 19.9337 Cases 430 +% Create node 3 split at 8 gain 4.9809 Th 1.358000e+000. Mean 23.3498 Cases 255 +% Create node 4 split at 1 gain 0.7722 Th 1.023300e+001. Mean 45.5800 Cases 5 +% Create leaf node(samevalue) 5. Mean 50.0000 Std 0.0000 Cases 4 +% Add subtree node 5 to 4. #nodes 5 +% Create leaf node(samevalue) 6. Mean 27.9000 Std 0.0000 Cases 1 +% Add subtree node 6 to 4. #nodes 6 +% Add subtree node 4 to 3. #nodes 6 +% Create node 7 split at 6 gain 2.8497 Th 6.540000e+000. Mean 22.9052 Cases 250 +% Create node 8 split at 13 gain 0.5970 Th 7.560000e+000. Mean 21.6297 Cases 195 +% Create leaf node(nogain) 9. Mean 23.9698 Std 1.7568 Cases 43 +% Add subtree node 9 to 8. #nodes 9 +% Create leaf node(nogain) 10. Mean 20.9678 Std 2.8242 Cases 152 +% Add subtree node 10 to 8. #nodes 10 +% Add subtree node 8 to 7. #nodes 10 +% Create leaf node(nogain) 11. Mean 27.4273 Std 3.4512 Cases 55 +% Add subtree node 11 to 7. #nodes 11 +% Add subtree node 7 to 3. #nodes 11 +% Add subtree node 3 to 2. #nodes 11 +% Create node 12 split at 1 gain 2.2467 Th 6.962150e+000. Mean 14.9560 Cases 175 +% Create node 13 split at 5 gain 0.5172 Th 5.240000e-001. Mean 17.1376 Cases 101 +% Create leaf node(nogain) 14. Mean 20.0208 Std 3.0672 Cases 24 +% Add subtree node 14 to 13. #nodes 14 +% Create leaf node(nogain) 15. Mean 16.2390 Std 2.9746 Cases 77 +% Add subtree node 15 to 13. #nodes 15 +% Add subtree node 13 to 12. #nodes 15 +% Create node 16 split at 5 gain 0.6133 Th 6.050000e-001. Mean 11.9784 Cases 74 +% Create leaf node(nogain) 17. Mean 16.6333 Std 4.5052 Cases 12 +% Add subtree node 17 to 16. #nodes 17 +% Create leaf node(nogain) 18. Mean 11.0774 Std 3.0090 Cases 62 +% Add subtree node 18 to 16. #nodes 18 +% Add subtree node 16 to 12. #nodes 18 +% Add subtree node 12 to 2. #nodes 18 +% Add subtree node 2 to 1. #nodes 18 +% Create node 19 split at 6 gain 6.0493 Th 7.420000e+000. Mean 37.2382 Cases 76 +% Create node 20 split at 1 gain 1.9900 Th 7.367110e+000. Mean 32.1130 Cases 46 +% Create node 21 split at 8 gain 0.6273 Th 1.877300e+000. Mean 33.3488 Cases 43 +% Create leaf node(samevalue) 22. Mean 45.6500 Std 6.1518 Cases 2 +% Add subtree node 22 to 21. #nodes 22 +% Create leaf node(nogain) 23. Mean 32.7488 Std 3.5690 Cases 41 +% Add subtree node 23 to 21. #nodes 23 +% Add subtree node 21 to 20. #nodes 23 +% Create leaf node(samevalue) 24. Mean 14.4000 Std 3.7363 Cases 3 +% Add subtree node 24 to 20. #nodes 24 +% Add subtree node 20 to 19. #nodes 24 +% Create node 25 split at 1 gain 1.1001 Th 2.733970e+000. Mean 45.0967 Cases 30 +% Create leaf node(nogain) 26. Mean 45.8966 Std 4.4005 Cases 29 +% Add subtree node 26 to 25. #nodes 26 +% Create leaf node(samevalue) 27. Mean 21.9000 Std 0.0000 Cases 1 +% Add subtree node 27 to 25. #nodes 27 +% Add subtree node 25 to 19. #nodes 27 +% Add subtree node 19 to 1. #nodes 27 +% Mean square deviation (using regression tree to predict) in old training data 9.405 +% + + diff --git a/sourcecodes/bnt-master/BNT/examples/static/dtree/test_restaurants.m b/sourcecodes/bnt-master/BNT/examples/static/dtree/test_restaurants.m new file mode 100644 index 00000000..9727847a --- /dev/null +++ b/sourcecodes/bnt-master/BNT/examples/static/dtree/test_restaurants.m @@ -0,0 +1,98 @@ +% Here the training data is adapted from Russell95 book. See restaurant.names for description. +% (1) Use infomation-gain as the split testing score, we get the the same decision tree as the book Russell 95 (page 537), +% and the Gain(Patrons) is 0.5409, equal to the result in Page 541 of Russell 95. (see below output trace) +% (Note: the dtree in that book has small compilation error, the Type node is from YES of Hungry node, not NO.) +% (2) Use gain-ratio (Quilan 93), the splitting defavorite attribute with more values. (e.g. the Type attribute here) + +dtreeCPD=tree_CPD; + +% load data +fname = fullfile(BNT_HOME, 'examples', 'static', 'uci_data', 'restaurant', 'restaurant.data'); +data=load(fname); +data=data'; + +%make the data be BNT compliant (values for discrete nodes are from 1-n, here n is the node size) + % e.g. if the values are [0 1 6], they must be mapping to [1 2 3] +%data=transform_data(data,'tmp.dat',[]); %here no cts nodes + +% learn decision tree from data +ns=2*ones(1,11); +ns(5:6)=3; +ns(9:10)=4; +dtreeCPD1=learn_params(dtreeCPD,1:11,data,ns,[]); + +% evaluate on data +[score,outputs]=evaluate_tree_performance(dtreeCPD1,1:11,data,ns,[]); +fprintf('Accuracy in training data %6.3f\n',score); + +% show decision tree using graphpad + + + +% --------------------------Output trace: using Information-Gain------------------------------ +% The splits are Patron, Hungry, Type, Fri/Sat +% ********************************* +% Create node 1 split at 5 gain 0.5409 Th 0. Class 1 Cases 12 Error 6 +% Create leaf node(onecla) 2. Class 1 Cases 2 Error 0 +% Add subtree node 2 to 1. #nodes 2 +% Create leaf node(onecla) 3. Class 2 Cases 4 Error 0 +% Add subtree node 3 to 1. #nodes 3 +% Create node 4 split at 4 gain 0.2516 Th 0. Class 1 Cases 6 Error 2 +% Create leaf node(onecla) 5. Class 1 Cases 2 Error 0 +% Add subtree node 5 to 4. #nodes 5 +% Create node 6 split at 9 gain 0.5000 Th 0. Class 1 Cases 4 Error 2 +% Create leaf node(nullset) 7. Father 6 Class 1 +% Create node 8 split at 3 gain 1.0000 Th 0. Class 1 Cases 2 Error 1 +% Create leaf node(onecla) 9. Class 1 Cases 1 Error 0 +% Add subtree node 9 to 8. #nodes 9 +% Create leaf node(onecla) 10. Class 2 Cases 1 Error 0 +% Add subtree node 10 to 8. #nodes 10 +% Add subtree node 8 to 6. #nodes 10 +% Create leaf node(onecla) 11. Class 2 Cases 1 Error 0 +% Add subtree node 11 to 6. #nodes 11 +% Create leaf node(onecla) 12. Class 1 Cases 1 Error 0 +% Add subtree node 12 to 6. #nodes 12 +% Add subtree node 6 to 4. #nodes 12 +% Add subtree node 4 to 1. #nodes 12 +% ******************************** +% +% Note: +% ***Create node 4 split at 4 gain 0.2516 Th 0. Class 1 Cases 6 Error 2 +% This mean we create a new node number 4, it is splitting at the attribute 4, and info-gain is 0.2516, +% "Th 0" means threshhold for splitting continous attribute, "Class 1" means the majority class at node 4 is 1, +% and "Cases 6" means it has 6 cases attached to it, "Error 2" means it has two errors if changing the class lable of +% all the cases in it to the majority class. +% *** Add subtree node 12 to 6. #nodes 12 +% It means we add the child node 12 to node 6. +% *** Create leaf node(onecla) 10. Class 2 Cases 1 Error 0 +% here 'onecla' means all cases in this node belong to one class, so no need to split further. +% 'nullset' means no training cases belong to this node, we use its parent node majority class as its class +% +% +% +% ---------------Output trace: using GainRatio----------------------- +% The splits are Patron, Hungry, Fri/Sat, Price +% +% +% Create node 1 split at 5 gain 0.3707 Th 0. Class 1 Cases 12 Error 6 +% Create leaf node(onecla) 2. Class 1 Cases 2 Error 0 +% Add subtree node 2 to 1. #nodes 2 +% Create leaf node(onecla) 3. Class 2 Cases 4 Error 0 +% Add subtree node 3 to 1. #nodes 3 +% Create node 4 split at 4 gain 0.2740 Th 0. Class 1 Cases 6 Error 2 +% Create leaf node(onecla) 5. Class 1 Cases 2 Error 0 +% Add subtree node 5 to 4. #nodes 5 +% Create node 6 split at 3 gain 0.3837 Th 0. Class 1 Cases 4 Error 2 +% Create leaf node(onecla) 7. Class 1 Cases 1 Error 0 +% Add subtree node 7 to 6. #nodes 7 +% Create node 8 split at 6 gain 1.0000 Th 0. Class 2 Cases 3 Error 1 +% Create leaf node(onecla) 9. Class 2 Cases 2 Error 0 +% Add subtree node 9 to 8. #nodes 9 +% Create leaf node(nullset) 10. Father 8 Class 2 +% Create leaf node(onecla) 11. Class 1 Cases 1 Error 0 +% Add subtree node 11 to 8. #nodes 11 +% Add subtree node 8 to 6. #nodes 11 +% Add subtree node 6 to 4. #nodes 11 +% Add subtree node 4 to 1. #nodes 11 +% +% diff --git a/sourcecodes/bnt-master/BNT/examples/static/dtree/test_zoo1.m b/sourcecodes/bnt-master/BNT/examples/static/dtree/test_zoo1.m new file mode 100644 index 00000000..23c258b3 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/examples/static/dtree/test_zoo1.m @@ -0,0 +1,21 @@ +% Here the training data is adapted from UCI ML repository, 'zoo' data + +dtreeCPD=tree_CPD; + +% load data +fname = fullfile(BNT_HOME, 'examples', 'static', 'uci_data', 'zoo', 'zoo1.data') +data=load(fname); +data=data'; + +data=transform_data_into_bnt_format(data, []); + +% learn decision tree from data +ns=2*ones(1,17); +ns(13)=6; +ns(17)=7; +dtreeCPD1=learn_params(dtreeCPD,1:17,data,ns,[],'stop_cases',5); % a node with less than 5 cases will not be splitted + +% evaluate on data +[score,outputs]=evaluate_tree_performance(dtreeCPD1,1:17,data,ns,[]); +fprintf('Accuracy in old training data %6.3f\n',score); + diff --git a/sourcecodes/bnt-master/BNT/examples/static/dtree/tmp.dot b/sourcecodes/bnt-master/BNT/examples/static/dtree/tmp.dot new file mode 100644 index 00000000..de359ea7 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/examples/static/dtree/tmp.dot @@ -0,0 +1,31 @@ +digraph G { +center = 1; +size="4,4"; +n1 [ label = "1 :" ]; +n2 [ label = "2 :" ]; +n3 [ label = "3 :" ]; +n4 [ label = "4 :" ]; +n5 [ label = "5 :" ]; +n6 [ label = "6 :" ]; +n7 [ label = "7 :" ]; +n8 [ label = "8 :" ]; +n9 [ label = "9 :" ]; +n10 [ label = "10 :" ]; +n1 -> n5 [label="1.000"]; +n2 -> n7 [label="0.800"]; +n2 -> n10 [label="0.200"]; +n3 -> n2 [label="1.000"]; +n4 -> n8 [label="1.000"]; +n5 -> n3 [label="0.143"]; +n5 -> n5 [label="0.571"]; +n5 -> n8 [label="0.286"]; +n6 -> n4 [label="1.000"]; +n7 -> n6 [label="0.333"]; +n7 -> n9 [label="0.667"]; +n8 -> n1 [label="0.333"]; +n8 -> n5 [label="0.333"]; +n8 -> n10 [label="0.333"]; +n9 -> n2 [label="1.000"]; +n10 -> n9 [label="1.000"]; + +} \ No newline at end of file diff --git a/sourcecodes/bnt-master/BNT/examples/static/dtree/transform_data_into_bnt_format.m b/sourcecodes/bnt-master/BNT/examples/static/dtree/transform_data_into_bnt_format.m new file mode 100644 index 00000000..92739590 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/examples/static/dtree/transform_data_into_bnt_format.m @@ -0,0 +1,66 @@ +function [bnt_data, old_values] = transform_data_into_bnt_format(data,cnodes) +% TRANSFORM_DATA_TO_BNT_FORMAT Ensures discrete variables have values 1,2,..,k +% e.g., if the values of a discrete are [0 1 6], they must be mapped to [1 2 3] +% +% data(i,j) is the value for i-th node in j-th case. +% bnt_data(i,j) is the new value. +% old_values{i} are the original values for node i. +% cnodes is the list of all continous nodes, e.g. [3 5] means the 3rd and 5th node is continuous +% +% Author: yimin.zhang@intel.com +% Last updated: Jan. 22, 2002 by Kevin Murphy. + +num_nodes=size(data,1); +num_cases=size(data,2); +old_values=cell(1,num_nodes); + +for i=1:num_nodes + if (myismember(i,cnodes)==1) %cts nodes no need to be transformed + %just copy the data + bnt_data(i,:)=data(i,:); + continue; + end + values = data(i,:); + sort_v = sort(values); + %remove the duplicate values in sort_v + v_set = unique(sort_v); + + %transform the values + for j=1:size(values,2) + index = binary_search(v_set,values(j)); + if (index==-1) + fprintf('value not found in tranforming data to bnt format.\n'); + return; + end + bnt_data(i,j)=index; + end + old_values{i}=v_set; +end + + +%%%%%%%%%%%% + +function index=binary_search(vector, value) +% BI_SEARCH do binary search for value in the vector +% Author: yimin.zhang@intel.com +% Last updated: Jan. 19, 2002 + +begin_index=1; +end_index=size(vector,2); +index=-1; +while (begin_index<=end_index) + mid=floor((begin_index+end_index)/2); + if (isstr(vector(mid))) + % need to write a strcmp to return three result (< = >) + else + if (value==vector(mid)) + index=mid; + return; + elseif (value>vector(mid)) + begin_index=mid+1; + else + end_index=mid-1; + end + end +end +return; |