{"id":229,"date":"2018-08-27T06:39:29","date_gmt":"2018-08-27T06:39:29","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=229"},"modified":"2019-01-02T06:45:53","modified_gmt":"2019-01-02T06:45:53","slug":"classification-and-regression-trees-i","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/classification-and-regression-trees-i\/","title":{"rendered":"Classification and Regression Trees – I"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Machine Learning. In this module we will be discussing in detail the Classification and Regression Tree (CART) approach for the construction of Decision Trees.<\/p>\r\n \r\n\r\nLearning Objectives:<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of this module are as follows:\r\n\r\n \r\n

\u2022\u00a0 To explain CART approach to decision tree building<\/p>\r\n

\u2022\u00a0 To outline the key features of CART<\/p>\r\n

\u2022\u00a0 To explain the various steps of the CART approach<\/p>\r\n

\u2022\u00a0 To discuss the recursive partitioning approach<\/p>\r\n

\u2022\u00a0 To outline the Gini Index<\/p>\r\n \r\n\r\n15.1 <\/strong>Decision Tree & CART<\/strong>\r\n\r\n \r\n

Any\u00a0 decision\u00a0 tree\u00a0 will\u00a0 successively\u00a0 split\u00a0 the\u00a0 data\u00a0 into\u00a0 smaller\u00a0 and\u00a0 smaller subsets. Ideally all the samples associated with a leaf node should be from the same class. Such a subset, or node, is considered pure<\/em> in this case. A generic tree-growing methodology,\u00a0 known\u00a0 as CART, successively splits nodes until they are pure.<\/p>\r\n \r\n\r\n15.2\u00a0 The CART approach<\/strong>\r\n\r\n \r\n

As we have discussed Classification And Regression Trees is a generic methodology for the construction of effective decision trees. CART was developed by Breiman, Friedman, Olshen, Stone in early 80\u2019s. They are the pioneers in bringing the tree-based modeling paradigm into the statistical fold. They proposed a rigorous approach involving cross-validation to select the optimal tree. In this context Quinlan developed C4.5 a machine learning approach for generating the decision tree which was essentially an extension of based on his earlier ID3 algorithm.<\/p>\r\n \r\n

This is a non-parametric technique, using the methodology of tree building. CART are binary tree structured classifiers constructed by repeated splits of subsets (nodes) of the search space S into two descendant subsets. Each terminal subset is assigned a class label; the resulting partition of S corresponds to the classifier. The method classifies objects or predicts outcomes by selecting from among the large number of variables, that is by selecting the most important variables that affect the outcome variable. CART analysis is a form of binary recursive partitioning. We will discuss this aspect later on.<\/span><\/p>\r\n\r\n<\/div>\r\n \r\n\r\n15.2.1 An Example from Clinical Research<\/strong>\r\n\r\n \r\n

Let us consider a dataset from University of California for the development of a reliable clinical decision rule to classify new patients into categories after<\/em> admission for a heart attack. The dataset has 19 variables collected during the first 24 hours for 215 patients (for those who survived the 24 hours) after their admittance to San Diego Hospital. The goal of the work is to identify the patients with high risk that is those patients who would not survive 30 days<\/p>\r\n \r\n\r\n\"\"\r\n

\r\n

Figure 15.1 shows a part of the decision tree where all patients are divided into two subsets (binary partitioning), one subset A of patients whose minimum systolic blood pressure over the initial 24 hour period > 91 and the other subset B of patients whose minimum systolic blood pressure over the initial 24 hour period \u00a3 91. Now in the subset A, we further partition the set based on whether age > 62.5 and so on.<\/p>\r\n \r\n\r\n15.2.2 Definition of CART<\/strong>\r\n\r\n \r\n

Now let us define CART. CART builds classification or regression trees for categorical attributes (classification) or numeric attributes (regression). Tree models where the target variable can take a finite set of values are called classification trees. Regression tree analysis is where the target variable can take continuous values typically real numbers such as the price of a house,or a patient\u2019s length of stay in a hospital. The term <\/span>C<\/strong>lassification <\/span>A<\/strong>nd <\/span>R<\/strong>egression<\/span> T<\/strong>ree (CART) analysis is used to refer to both types of attributes categorical and numeric. Trees used for classification and regression are similar but differ how they determine the splitting procedure.<\/span><\/p>\r\n \r\n

15.2.3 Salient Aspects of CART<\/strong><\/p>\r\n \r\n

One of the key features of CART is automated attribute or feature selection. The process can automatically select relevant fields irrespective of the total number of fields. Moreover no data preprocessing or transformation of the variables is needed. The CART is is tolerant to missing values, and there is only a moderate loss of accuracy due to missing values.<\/span><\/p>\r\n \r\n

15.3\u00a0\u00a0 CART- General Framework - The Six Questions<\/strong><\/p>\r\n \r\n

Associated with CART are six questions to be answered or six issues to be addressed. The following are the questions:<\/span><\/p>\r\n \r\n

    \r\n \t
  1. How many splits will be there at each node?<\/strong><\/li>\r\n<\/ol>\r\nShould the questions to be asked for the split at each node be binary (e.g., is gender male or female) or numeric (e.g., height is 5\u20194\u201d) or multi-valued (e.g., caste)?\r\n\r\n<\/div>\r\n
    \r\n\r\n \r\n\r\n2.\u00a0<\/strong>Which properties should be tested at each node?<\/strong>\r\n\r\n \r\n

    The decision on which variable or feature to use for splitting is an important issue and in fact determines the efficiency of the procedure.<\/p>\r\n \r\n\r\n3.<\/strong>When does a node become a leaf?<\/strong>\r\n\r\n \r\n

    We need a criteria to determine that the subset of examples associated with a node need not be partitioned further.<\/p>\r\n \r\n\r\n4.<\/strong>How to prune a large tree?<\/strong>\r\n\r\n \r\n

    Simplify the tree by pruning peripheral branches to avoid over fitting. Some parts of the tree need not be explored or partitioned further since deep trees that fit the training data well, will not generalize well to new test data.<\/strong> How do we determine this?<\/p>\r\n \r\n\r\n5.<\/strong>If a leaf node is impure, how to assign labels?<\/strong>\r\n\r\n \r\n

    In case the leaf node is impure that is results in more than one output variable value, how do we assign an output value for unknown samples.<\/p>\r\n \r\n\r\n6.<\/strong>How to handle missing data?<\/strong>\r\n\r\n \r\n

    The issue here is how to account for missing data of some features when decisions regarding this data are taken.<\/p>\r\n\r\n<\/div>\r\n \r\n\r\n15.4\u00a0 CART Steps<\/strong>\r\n

    \r\n\r\n \r\n\r\nThe following are the steps used by CART for the construction of the decision tree.\r\n\r\n \r\n

    1.Initialization<\/strong>: Initially a tree is created with a single root node containing all the training data.<\/p>\r\n

    2.Tree growing: <\/strong>Recursive Partitioning is the most important component of tree construction. This procedure consists of 5 sub steps which are described below:<\/p>\r\n

    a.The first step here is the selection of the splitting criterion which in most cases is based on likelihood. For this purpose we need to find the best question for splitting each node. We then split the node that results in the greatest increase in the likelihood.<\/p>\r\n

    b.We then rank all of the best splits and then the best split in the variable is selected in terms of the reduction in impurity (heterogeneity). This aspect we will discuss later.<\/p>\r\n

    c.The Predicted classes are assigned to the nodes according to a rule that minimizes misclassification costs.<\/p>\r\n

    d.The next step is the decision about the stopping criteria that is how far to grow? We generally stop expanding a node when all the records belong to the same class or when all the records have similar attribute values. Stopping criteria decides whether to continue splitting a node.<\/p>\r\n

    e.Using surrogates program best available information is used to replace missing data, normally based on a variable that is relative to the outcome variable.<\/p>\r\n

    3.Stop tree building<\/strong>: When every aspect of the dataset has been taken into account while building the decision tree, the tree building process itself is stopped.<\/p>\r\n

    4.Tree Pruning: <\/strong>An independent test set or cross-validation is generally used to prune the tree. Pruning is carried out by trimming off parts of the tree that don\u2019t work. Another method is to first order the nodes of a large tree by contribution to tree accuracy and this ordering is used as a basis to prune nodes.<\/p>\r\n

    5.Optimal Tree Selection: <\/strong>This process is the selection of the best tree that fits dataset with a low percentage of error. The decision about the best tree is made after growing and pruning. This selection of optimal tree is also based on balancing simplicity against accuracy.<\/p>\r\n\r\n<\/div>\r\n \r\n\r\n15.5\u00a0 Recursive Partitioning<\/strong>\r\n

    \r\n\r\n \r\n\r\nThe key idea behind the CART technique is recursive partitioning. Let us understand this concept in detail. The recursive procedure is described as follows:\r\n\r\n \r\n

    i.Consider all the data samples.<\/p>\r\n

    ii.Consider all<\/em> possible values of all<\/em> variables.<\/p>\r\n

    iii.Select the variable and the value (X<\/em>=t<\/em>1<\/em>) that produces the greatest \u201cseparation\u201d in the target. This point of the variable X (X<\/em>=t<\/em>1<\/em>) is called a \u201csplit\u201d.<\/p>\r\niv.If X<\/em>< t<\/em>1<\/em> then send the data to the \u201cleft\u201d; otherwise, send data point to the \u201cright\u201d.\r\n

    v.Now repeat same process on these two \u201cnodes\u201d<\/p>\r\n \r\n

    What you get as output is a \u201ctree\u201d. Note that CART only uses binary<\/em> splits. The main step in the process is Recursive Partitioning (step iii) where we<\/p>\r\n \r\n

    \u2022 First we pick a value of x<\/em>i, say s<\/em>i, that divides the training data into two (not necessarily equal) portions<\/p>\r\n

    \u2022 Then we measure how \u201cpure\u201d or homogeneous each of the resulting portions are. In this context a partition being \u201cPure\u201d means that they contain records of mostly one class.<\/p>\r\n

    \u2022 The algorithm tries different values of x<\/em>i, and s<\/em>i to maximize purity in initial split<\/p>\r\n

    \u2022 After we get a \u201cmaximum purity\u201d split, we repeat the process for a second split, and so on<\/p>\r\n \r\n\r\n15.6\u00a0 Features of CART<\/strong>\r\n\r\n \r\n\r\nSome of the important features of the process of CART are as follows:\r\n