nagdmc entropy tree

NAG DMC

Decision Tree: nagdmc entropy tree
Purposenagdmc entropy tree computes an n-ary classification tree by using an entropy criterion.

Declaration#include <nagdmc.h>void nagdmc entropy tree(long rec1, long nvar, long nrec, long dblk, double data[],long nxvar, long xvar[], long yvar, long ncat[],long cat[], long mnc, long *iproot, int *info);

Parameters1:

rec1 – long
On entry: the index in the data of the first data record used in the analysis.
Constraint: rec1 ≥ 0.

Input

2:

nvar – long
On entry: the number of variables in the data.
Constraint: nvar > 1.

Input

3:

nrec – long
On entry: the number of consecutive records, beginning at rec1, used in the analysis.
Constraint: nrec > 1.

Input

4:

dblk – long
On entry: the total number of records in the data block.
Constraint: dblk ≥ rec1 + nrec.

Input

5:

data[dblk ∗ nvar] – double
Input
On entry: the data values for the jth variable (for j = 0, 1, . . . , nvar−1) are stored in data[i∗nvar+j],
for i = 0, 1, . . . , dblk − 1.

6:nxvar – long
Input
On entry: the number of independent variables. If nxvar = 0 then all variables in the data,excluding yvar, are treated as independent variables.
Constraint: 0 ≤ nxvar < nvar.

7:

xvar[nxvar] – long
Input
On entry: the indices indicating the position in data in which values of the independent variables
are stored. If nxvar = 0 then xvar must be 0, and the indices of independent variables are given by
j = 0, 1, . . . , nvar − 1; j 6= yvar.
Constraints: if nxvar > 0, 0 ≤ xvar[i] < nvar, for i = 0, 1, . . . , nxvar − 1; otherwise xvar must be0.

8:yvar – long
On entry: the index in data in which values of the dependent variable are stored.
Constraints: 0 ≤ yvar < nvar; if nxvar > 0, yvar 6= xvar[i], for i = 0, 1, . . . , nxvar − 1.

9:ncat[nvar] – long
Input
On entry: ncat[i] contains the number of categories in the ith variable, for i = 0, 1, . . . , nvar − 1. If
the ith variable is continuous, ncat[i] must be set equal to zero.
Constraints: ncat[i] ≥ 0, for i = 0, 1, . . . , nvar − 1, (i 6= yvar); ncat[yvar]> 1.

10:

cat[d] – long
Input
On entry: a list of category values for variables in the same variable order as ncat, where d is equal
to the sum of the elements in ncat.

Input

nagdmc entropy tree.1

nagdmc entropy tree

NAG DMC11:

mnc – long

Input

On entry: during the search for an optimal partition of data at a node each candidate partition
must contain at least mnc data records.
Constraint: mnc ≤ nrec/2.
12:iproot – long *OutputOn exit: iproot is an integer cast of the memory location pointing to the root node in the tree.
This value is passed to the functions described in ‘See Also’. Information on the detail of a decision
tree can be found by using the value of iproot.
Detail of partitions in an entropy classification tree are available by using in a C program the code:
ENode *proot;
proot = (ENode *)iproot;
where ENode is a C structure with the following members:
nchildren – longthe number of child nodes belonging to the node;ndata – longthe number of data records at this node;nclasses – longthe number of categories on the dependent variable;
ninclasses – long []ninclasses[k] gives the number of data records at the node in kth category of the dependent
variable, for k = 0, 1, . . . , nclasses − 1;
modal class – longthe modal category of the dependent variable over data records at the node;index – longthe index in the data used to partition data records;
discrete – longif discrete = 1, the variable described by index is categorical; otherwise the variable iscontinuous;
value – double
the value of the test if the variable used to partition data records is continuous; otherwise notreferenced;
children – ENode **if this node is not a leaf node, children[i] points to the ith child node,i = 0, 1, . . . , nchildren − 1; otherwise children is set to 0;

forparent – ENode *if this node is not the root node, a pointer to the parent node; otherwise parent is set to 0.
A C source code example that accesses the information in this classification tree is given in‘Explanatory Code’.
13:

info – int *OutputOn exit: info gives information on the success of the function call:
0: the function successfully completed its task.
i; i = 1, 2, . . . , 4, 6, 7, . . . , 9, 11: the specification of the ith formal parameter was incorrect.
99: the function failed to allocate enough memory.
100: an internal error occurred during the execution of the function.

nagdmc entropy tree.2

nagdmc entropy tree

NAG DMC

Notation
nrec the number of data records, n.
nxvar determines the number of independent variables, p.
ncat contains the number of category values on variables, c and cj , for j = 1, 2, . . . , p.
mnc the minimum number of data records at child nodes, s.

Description
Let xi denote the values of p independent variables and yi the value of the dependent variable forthe ith data record at a node A in a classification tree, for i = 1, 2, . . . , n. The jth independent
variable can be continuous or categorical and its ith value is denoted by xij , for j = 1, 2, . . . , p.
If the jth independent variable is categorical it takes cj category values, for j = 1, 2, . . . , p. The
dependent variable is a categorical variable with c category values.
AB

ECD

F

Figure 1: Graphical representation of an n-ary tree showing parent nodes connected bylines to their child nodes. The root node, node A, is associated with all data records
and is the only node not to have a parent node. Nodes C, D, E and F do not havechild nodes and are known as leaf nodes. Node B is neither the root node nor a leaf
node and is known as an internal node. Given a positive value for the scalar s, apartition of m ≥ s data records at a parent node into records at child nodes is basedon the outcome of a test at the parent node. In this example the test at node A is on acategorical variable with three category values, and the test at node B is either a test
on a continuous variable or on a categorical variable with two category values.
Consider the case of partitioning m data records in a set X at a parent node such that each datarecord in X is sent to a single child node (see Figure 1). If m is less than a user-supplied value s, apartition of data is not computed; otherwise a data partition is defined by computing a univariate
test on an independent variable. Two kinds of test are available. For a discrete variable j with r
unique values u1 , u2 , . . . , ur , a criterion is evaluated for a partition of X into:{X1 , X2 , . . . , Xk , . . . , Xr },where Xk contains those members of X that satisfy:
xij = uk ,i = 1, 2, . . . , m; k = 1, 2, . . . , r.

For a continuous variable j a criterion is evaluated for each possible binary partition of X into X1
and X2 , where X1 contains those members of X that satisfy:
xij ≤ tl ,i = 1, 2, . . . , m.

and X2 contains those members of X that satisfy:
xij > tl ,i = 1, 2, . . . , m,and tl is found by sorting the data values on variable j and computing the mid-point of neighbouring
ordered values, for l = 1, 2, . . . , m − 1. The partition which optimises a criterion is retained.
The process of computing partitions continues recursively for each node created until the numberof data records at a node is less than s or the data records at a node are all the same.

nagdmc entropy tree.3

nagdmc entropy tree

NAG DMCThe criterion used to determine partitions is the gain ratio which is based on values of entropy. In
particular, the entropy of X is:cu Xuii,
E(X) = −log2mm
i=1
where ui is the number of data records in X that belong to the ith category. Now consider apartition of X into disjoint and exhaustive sets X1 , X2 , . . . , Xr ; the weighted average of entropy ofeach partition is given by,r1X
I(X1 , X2 , . . . , Xr ) =|X |E(Xi ),m i=1 iand the gain ratio R by:
E(X) − I(X1 , X2 , . . . , Xr )R=,
S(X1 , X2 , . . . , Xr )where S(·) is the split information:
r
1X|Xi ||Xi | log2.
S(X1 , X2 , . . . , Xr ) =m i=1mReferences and Further Reading
Quinlan J R (1987) Simplifying decision trees Int. J. Man-Machine Studies 27 221–234
Quinlan J R (1993) C4.5: Programs for Machine Learning San Mateo: Morgan Kaufmann

Explanatory CodeThe following C function prints the memory locations of nodes in a tree and its parent node. Thetype (leaf or internal) of each node is printed along with the detail of the partition at that node. Ifthe function is called with iproot as its argument, the entire tree is printed.
#include <stdio.h>void step_through(long node) {long i;
ENode *lnode;
lnode = (ENode *)node;
if (lnode == 0)
return;printf("\n Node %8p""\n Parent %8p""\n No. data at node %8li""\n Modal class %li",
lnode,lnode->parent,lnode->ndata,lnode->modal_class);
printf("\n Class distribution at node:");for (i=0; i<lnode->nclasses; ++i)
printf(" %li",lnode->ninclasses[i]);if (lnode->index > 0) {printf("\n Partition on index %li",lnode->index);
if (lnode->discrete == 0)
printf("; continuous test value: %8.4f",lnode->children[0]->value);
printf("\n");for (i=0; i<lnode->nchildren; ++i)
step_through((long)(lnode->children[i]));}else
printf("\n Leaf node\n");}nagdmc entropy tree.4

NAG DMC

nagdmc entropy tree

See Also
nagdmc free entropy tree
returns to the operating system memory used by an entropy tree.
nagdmc load entropy treeloads an entropy tree from a file.
nagdmc predict entropy tree computes predictions given an entropy tree.
nagdmc prune entropy tree prunes an entropy tree using pessimistic error pruning.
nagdmc save entropy tree
writes an entropy tree to a file.
entropy tree ex.cthe example calling program.

nagdmc entropy tree.5