nagdmc gini tree

NAG DMC

Decision Tree: nagdmc gini tree
Purposenagdmc gini tree classifies data by using a binary tree computed using the Gini index criterion.

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

Parameters1:

rec1 – longInput

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

nvar – long

Input

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

nrec – long

Input

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

dblk – long

Input

On entry: the total number of records in the data block.
Constraint: dblk ≥ rec1 + nrec.
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 byj = 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

Input

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.

nagdmc gini tree.1

NAG DMC
10:nagdmc gini treebcat[nvar] – long

Input

On entry: bcat[i] contains the base level value for the ncat[i] categories on the ith variable. If
ncat[i] > 0, for i = 0, 1, . . . , nvar − 1, the categorical values on the ith variable are given bybcat[i] + j, for j = 0, 1, . . . , ncat[i] − 1; otherwise bcat[i] is not referenced. If the base level foreach categorical variable is zero, bcat can be 0.
11:

prior[c] – double

Input

On entry: prior[i] contains the prior weight on the ith category value on the dependent variable,for i = 0, 1, . . . , c − 1, where c = ncat[yvar]. If prior is not 0, an equal weighting is put on each of
the category values on the dependent variable.
Constraint: if prior is not 0, the elements in prior must sum equal to 1.0.
12:

mns – long

Input

On entry: if the number of data records at a node is greater than or equal to mns, a partition ofdata is attempted; otherwise a leaf node is forced.
Constraint: 1 < mns < nrec.
13:

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: 1 ≤ mnc ≤ mns/2.
14:alpha – double

InputOn entry: if the decrease in misclassification rate due to partitioning data at a parent node into its
child nodes is less than alpha, the parent node is forced to be a leaf node.
Constraint: 0.0 ≤ alpha < 1.0.
15:

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 a binary classification tree are available by using in a C program the code:
CTNode *proot;
proot = (CTNode *)iproot;
where CTNode is a C structure with the following members:
type – int
if this node is a leaf, type is set to one; otherwise type is set to 0;
ndata – longthe number of data records at this node;
nig – long []nig[k] gives the number of data records at the node in category bcat[yvar] + k of the dependent
variable, for k = 0, 1, . . . , ncat[yvar] − 1;yval – longthe modal category of the dependent variable over data records at the node;
parent – CTNode *if this node is not the root of a binary tree, a pointer to the parent node; otherwise parent is
set to 0.
If type = 1, the remaining structure members are set equal to dummy values; otherwise thefollowing information is available:svar – longthe index in the data of the variable on which records are partitioned;
ncats – longnagdmc gini tree.2

nagdmc gini tree

NAG DMC

if independent variable svar is categorical, the number of categories on variable j ∗ ; otherwisezero;sval – double
if ncats = 0, sval gives the scalar value of the test on variable svar; otherwise sval is notreferenced;
lr – char []if ncats = 0, lr is not referenced; otherwise it is an array of ncats elements, the value of lr[i]determines the direction in the binary tree taken by data records at the node with categorybcat[svar] + i on variable svar, for i = 0, 1, . . . , ncats − 1. The possible values for lr[i] are:’l’ data records at the node with category value bcat[svar] + i on svar are sent to theleft child node;’r’ data records at the node with category value bcat[svar] + i on svar are sent to theright child node.
’a’ the ith category on svar is absent at this node.
giv – double
the Gini index criterion value;
improve – double
the improvement in Gini index value obtained by partitioning data records at this node;
lchild – CTNode *a pointer to left child node;
rchild – CTNode *a pointer to right child node.
A C source code example that accesses the information in a binary classification tree is given in‘Explanatory Code’.
16:

info – int *On exit: info gives information on the success of the function call:

Output0: the function successfully completed its task.
i; i = 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14: the specification of the ith formal parameter wasincorrect.
99: the function failed to allocate enough memory.
100: an internal error occurred during the execution of the function.

Notation
nrec
nxvar
ncat
bcat
mns
mnc
alpha

the number of records, p.
the number of variables, m.
the number of categories on variables, cy and cj , for j = 1, 2, . . . , m.
the base level categories, by and bj , for j = 1, 2, . . . , m.
the minimum number of records, s, required for a partition to be attempted.
the minimum number of records, t, at each child.
the pruning constant, α.

Description
Let xi denote the values of m independent variables and yi the value of the dependent variable forthe ith data record at a node A, for i = 1, 2, . . . , p. The jth independent variable can be continuousor categorical and its ith value is denoted by xij , for j = 1, 2, . . . , m. If the jth independent variable
is categorical it takes the cj consecutive values bj , bj +1, . . . , bj +cj −1, for a base level value bj . The
dependent variable is a categorical variable with cy consecutive values by , by + 1, . . . , by + cy − 1, fora base level value by . Furthermore, let o denote the modal category and lk be the number of records
that belong to the kth category, for k = 1, 2, . . . , cy , over the values of the dependent variable atnode A.

nagdmc gini tree.3

nagdmc gini tree

NAG DMCABDCE

Figure 1: Graphical representation of a binary 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 and E do not have childnodes and are known as leaf nodes. Node B is neither the root node nor a leaf nodeand is known as an internal node. Given positive values for the scalars s and t ≤ s/2,a partition of p ≥ s data records at a parent node into q ≥ t records at one child nodeand r ≥ t records at the other child node is based on the outcome of a test at the parentnode.
Consider the case of partitioning p data records at a parent node A into child nodes B and C
such that each record at node A is sent to either node B or node C (see Figure 1). Let s be theminimum number of data records at a parent node required to partition data. If p < s, a partitionof 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. Firstly, a test on a continuous independent
variable j sends the ith data record at the parent node to the left child node if xij ≤ u and otherwise
to the right child node, for a value u that minimises a criterion and sends at least t data records
to left and right child nodes. Secondly, a test on a categorical independent variable j sends the ith
data record at the parent node to the child node determined by the binary partition of category
values that minimises a criterion and sends at least t data records to left and right child nodes. In
both cases, the criterion most often used in a binary classification tree is based on the Gini indexof impurity.
The test chosen at parent node A is the univariate test which partitions p ≥ s records at a node A
into q ≥ t records at child node B and r ≥ t records at child node C and minimises the sum overthe child nodes, g, of the Gini index of impurity:#" cycyX
1 X
22g =2−q (bk ) + r (ck ) ,p
k=1

k=1

where bk is the probability that data at node B belongs to the kth category of the dependent
variable i.e.,bk =wk lk,cy
Xwi lik = 1, 2, . . . , cy ,i=1where lk is the number of records at the node that belong to the kth category of the dependent
variable, and the kth weight wk = cy πk for the prior probability πk with,πk ≥ 0cyX,πk = 1 

k = 1, 2, . . . , cy ,k=1

with the probability ck defined in a similar fashion using data records at node C, for k = 1, 2, . . . , cy .

nagdmc gini tree.4

nagdmc gini tree

NAG DMC

Suppose that a data partition on independent variable 1 ≤ j ∗ ≤ m gives the minimum value g ∗of Gini index of impurity over child nodes. The improvement, z, in the Gini index of impurity iscomputed by subtracting g ∗ from the Gini index of impurity value over node A, i.e.,z =1−cyX(ak )2 − g ∗ ,k=1

where the probability ak is defined similarly to bk .
Once a partition of data at a parent node into left and right child nodes has been found, the processcontinues recursively by considering partitions of data records at child nodes. When the recursive
computation process terminates, nodes are removed from a binary tree if the decrease in the rateof misclassification of the dependent variable between a child node and its parent node is less thanthe value of a user-supplied scalar, α. This removal of nodes is known as pruning.

References and Further Reading
Brieman L. Friedman J. Olshen R. and Stone C. (1984) Classification and Regression Trees Belmont
Calif.

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.
The test value for the Gini index of impurity is printed along with the improvement in the Gini
index value obtained by partitioning data records at the node. Finally, the modal category of thedependent variable is printed followed by the number of data records at the node. If the function
is called with iproot as its second argument, the entire tree is printed.
#include <stdio.h>void step_through(long bcat[], long node) {long i, j;
CTNode *lnode;
lnode = (CTNode *)node;
if (lnode == 0) return;printf("\n Node%8p""\n Parent %8p""\n type: %8i""\n svar: %8li""\n sval: %8.4f""\n giv:%8.4f""\n imp:%8.4f""\n yval: %8li""\n ndata: %8li",
lnode,lnode->parent,lnode->type,lnode->svar,lnode->sval,lnode->giv,lnode->improve,lnode->yval,lnode->ndata);
j = 0 + (bcat != 0 ? bcat[lnode->svar] : 0);if (lnode->ncats > 0) {printf("\n lr:");for (i = 0; i < lnode->ncats; ++i) {if (lnode->lr[i] != ABSENT)
printf(" Category %li goes %c;",j+i,lnode->lr[i]);}printf("\b");}printf("\n");step_through(bcat,(long)(lnode->lchild));
step_through(bcat,(long)(lnode->rchild));}

nagdmc gini tree.5

NAG DMC

nagdmc gini tree

See Also
nagdmc free gini tree
nagdmc load gini tree
nagdmc save gini tree
nagdmc predict gini tree
gini tree ex.creturns memory containing a binary classification tree to the operating system.
loads a binary classification tree into memory.
saves a binary classification tree to a binary file.
classifies new data using a binary classification tree.
the example calling program.

nagdmc gini tree.6