{"id":267,"date":"2018-07-19T10:46:14","date_gmt":"2018-07-19T10:46:14","guid":{"rendered":"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=267"},"modified":"2018-07-19T10:46:14","modified_gmt":"2018-07-19T10:46:14","slug":"classification","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/chapter\/classification\/","title":{"rendered":"Classification"},"content":{"raw":"
\r\n\r\nClassification<\/strong>\r\n\r\n \r\n

In this session, we continue our examination of classification methods for data mining. One attractive classification method involves the construction of a decision tree<\/em>, a collection of decision<\/em> nodes<\/em>, connected by branches<\/em>, extending downward from the root node <\/em>until terminating in leaf nodes<\/em>. Beginning at the root node, which by convention is placed at the top of the decision tree diagram, attributes are tested at the decision nodes, with each possible outcome resulting in a branch. Each branch then leads either to another decision node or to a terminating leaf node. Figure 1 provides an example of a simple decision tree. The target variable for the decision tree in Figure 1 is credit risk<\/em>, with potential customers being classified as either good or bad credit risks.<\/p>\r\n \r\n

The predictor variables are savings<\/em> (low, medium, and high), assets<\/em> (low or not low), and income<\/em> (\u2264$50,000 or ><\/em>$50,000). Here, the root node represents a decision node, testing whether each record has a low, medium, or high savings level (as defined by the analyst or domain expert). The data set is partitioned, or split<\/em>, according to the values of this attribute.<\/p>\r\n \r\n

Those records with low savings are sent via the leftmost branch (savings<\/em> = low<\/em>) to another decision node. The records with high savings are sent via the rightmost branch to a different decision node. The records with medium savings are sent via the middle branch directly to a leaf node, indicating the termination of this branch. Why a leaf node and not another decision node? Because, in the data set (not shown), all of the records with medium savings levels have been classified as good credit risks. There is no need for another decision node, because our knowledge that the customer has medium savings predicts good credit with 100% accuracy in the data set. For customers with low savings, the next decision node tests whether the customer has low assets. Those with low assets are then classified as bad credit risks; the others are classified as good credit risks. For customers with high savings, the next decision node tests whether the customer has an income of at most $30,000.<\/p>\r\n \r\n

Customers with incomes of $30,000 or less are then classified as bad credit risks, with the others classified as good credit risks. When no further splits can be made, the decision tree algorithm stops growing new nodes. For example, suppose that all of the branches terminate in \u201cpure\u201d leaf nodes, where the target variable is unary for the records in that node (e.g., each record in the leaf node is a good credit risk). Then no further splits are necessary, so no further nodes are grown. However, there are instances when a particular node contains \u201cdiverse\u201d attributes (with nonunary values for the target attribute), and yet the decision tree cannot make a split. For example, suppose that we consider the records from Figure 1 with high savings and low income (\u2264$30,000).<\/p>\r\n \r\n

Suppose that there are five records with these values, all of which also have low assets. Finally, suppose that three of these five customers have been classified as bad credit risks and two as good credit risks, as shown in Table 1. In the real world, one often encounters situations such as this, with varied values for the response variable, even for exactly the same values for the predictor variables.<\/p>\r\n

such customers is \u201cbad,\u201d with 60% confidence, as determined by the three-fifths of customers in this node who are bad credit risks. Note that not all attributes are tested for all records. Customers with low savings and low assets, for example, are not tested with regard to income in this example.<\/p>\r\n \r\n\r\n<\/div>\r\n

\r\n

\"\"<\/p>\r\n \r\n

Table 1: Sample records that lead to pure leaf node<\/strong><\/p>\r\n \r\n

\"\"<\/p>\r\n \r\n\r\nCertain requirements must be met before decision tree algorithms may be applied:\r\n

    \r\n \t
  1. Decision tree algorithms represent supervised learning, and as such require pre-classified target variables. A training data set must be supplied which provides the algorithm with the values of the target variable.<\/span><\/li>\r\n \t
  2. This training data set should be rich and varied, providing the algorithm with a healthy cross section of the types of records for which classification may be needed in the future. Decision trees learn by example, and if examples are systematically lacking for a definable subset of records, classification and prediction for this subset will be problematic or impossible.<\/span><\/li>\r\n \t
  3. T<\/span>he target attribute classes must be discrete. That is, one cannot apply decision tree analysis to a continuous target variable. Rather, the target variable must take on values that are clearly demarcated as either belonging to a particular class or not belonging.<\/span><\/li>\r\n<\/ol>\r\n<\/div>\r\n \r\n

    Why in the example above, did the decision tree choose the savings attribute for the root node split? Why did it not choose assets or income instead? Decision trees seek to create a set of leaf nodes that are as \u201cpure\u201d as possible, that is, where each of the records in a particular leaf node has the same classification. In this way, the decision tree may provide classification assignments with the highest measure of confidence available.<\/p>\r\n \r\n

    However, how does one measure uniformity, or conversely, how does one measure heterogeneity? We shall examine two of the many methods for measuring leaf node purity, which lead to the two leading algorithms for constructing decision trees:<\/p>\r\n \r\n\r\nClassification and regression trees (CART) algorithm C4.5 algorithm.\r\n\r\n \r\n\r\nCOMPARISON OF THE C5.0 AND CART ALGORITHMS APPLIED TO REAL DATA<\/strong>\r\n\r\n \r\n

    Next, we apply decision tree analysis using Clementine on a real-world data set. The data set adult<\/em> was abstracted from U.S. census data by Kohavi and is available online from the University of California at Irvine Machine Learning Repository.<\/p>\r\n

    <\/p>\r\n

    Here, we are interested in classifying whether or not a person\u2019s income is less than $50,000, based on the following set of predictor fields.<\/p>\r\n \r\n\r\nNumerical variables<\/strong>\r\n\r\n \r\n\r\nAge, Years of education, Capital gains, Capital losses, Hours worked per week.\r\n\r\nCategorical variables, Race, Gender, Work class, Marital status.\r\n

    The numerical\u00a0 variables\u00a0 were normalized so that all values\u00a0 ranged between zero and 1.Some\u00a0 collapsing\u00a0 of\u00a0 low-frequency\u00a0 classes\u00a0 was\u00a0 carried\u00a0 out\u00a0 on the\u00a0 work class and marital\u00a0 status categories.Clementine\u00a0 was used to compare\u00a0 the C5.0\u00a0 algorithm (an\u00a0 update\u00a0 of\u00a0 the\u00a0 C4.5\u00a0 algorithm)\u00a0 with\u00a0 CART,\u00a0 examining\u00a0 a\u00a0 training\u00a0 set of\u00a0 24,986 records. The decision tree produced by the CART algorithm.<\/p>\r\n \r\n

    \"\"<\/p>","rendered":"

    \n

    Classification<\/strong><\/p>\n

     <\/p>\n

    In this session, we continue our examination of classification methods for data mining. One attractive classification method involves the construction of a decision tree<\/em>, a collection of decision<\/em> nodes<\/em>, connected by branches<\/em>, extending downward from the root node <\/em>until terminating in leaf nodes<\/em>. Beginning at the root node, which by convention is placed at the top of the decision tree diagram, attributes are tested at the decision nodes, with each possible outcome resulting in a branch. Each branch then leads either to another decision node or to a terminating leaf node. Figure 1 provides an example of a simple decision tree. The target variable for the decision tree in Figure 1 is credit risk<\/em>, with potential customers being classified as either good or bad credit risks.<\/p>\n

     <\/p>\n

    The predictor variables are savings<\/em> (low, medium, and high), assets<\/em> (low or not low), and income<\/em> (\u2264$50,000 or ><\/em>$50,000). Here, the root node represents a decision node, testing whether each record has a low, medium, or high savings level (as defined by the analyst or domain expert). The data set is partitioned, or split<\/em>, according to the values of this attribute.<\/p>\n

     <\/p>\n

    Those records with low savings are sent via the leftmost branch (savings<\/em> = low<\/em>) to another decision node. The records with high savings are sent via the rightmost branch to a different decision node. The records with medium savings are sent via the middle branch directly to a leaf node, indicating the termination of this branch. Why a leaf node and not another decision node? Because, in the data set (not shown), all of the records with medium savings levels have been classified as good credit risks. There is no need for another decision node, because our knowledge that the customer has medium savings predicts good credit with 100% accuracy in the data set. For customers with low savings, the next decision node tests whether the customer has low assets. Those with low assets are then classified as bad credit risks; the others are classified as good credit risks. For customers with high savings, the next decision node tests whether the customer has an income of at most $30,000.<\/p>\n

     <\/p>\n

    Customers with incomes of $30,000 or less are then classified as bad credit risks, with the others classified as good credit risks. When no further splits can be made, the decision tree algorithm stops growing new nodes. For example, suppose that all of the branches terminate in \u201cpure\u201d leaf nodes, where the target variable is unary for the records in that node (e.g., each record in the leaf node is a good credit risk). Then no further splits are necessary, so no further nodes are grown. However, there are instances when a particular node contains \u201cdiverse\u201d attributes (with nonunary values for the target attribute), and yet the decision tree cannot make a split. For example, suppose that we consider the records from Figure 1 with high savings and low income (\u2264$30,000).<\/p>\n

     <\/p>\n

    Suppose that there are five records with these values, all of which also have low assets. Finally, suppose that three of these five customers have been classified as bad credit risks and two as good credit risks, as shown in Table 1. In the real world, one often encounters situations such as this, with varied values for the response variable, even for exactly the same values for the predictor variables.<\/p>\n

    such customers is \u201cbad,\u201d with 60% confidence, as determined by the three-fifths of customers in this node who are bad credit risks. Note that not all attributes are tested for all records. Customers with low savings and low assets, for example, are not tested with regard to income in this example.<\/p>\n

     <\/p>\n<\/div>\n

    \n

    \"\"<\/p>\n

     <\/p>\n

    Table 1: Sample records that lead to pure leaf node<\/strong><\/p>\n

     <\/p>\n

    \"\"<\/p>\n

     <\/p>\n

    Certain requirements must be met before decision tree algorithms may be applied:<\/p>\n

      \n
    1. Decision tree algorithms represent supervised learning, and as such require pre-classified target variables. A training data set must be supplied which provides the algorithm with the values of the target variable.<\/span><\/li>\n
    2. This training data set should be rich and varied, providing the algorithm with a healthy cross section of the types of records for which classification may be needed in the future. Decision trees learn by example, and if examples are systematically lacking for a definable subset of records, classification and prediction for this subset will be problematic or impossible.<\/span><\/li>\n
    3. T<\/span>he target attribute classes must be discrete. That is, one cannot apply decision tree analysis to a continuous target variable. Rather, the target variable must take on values that are clearly demarcated as either belonging to a particular class or not belonging.<\/span><\/li>\n<\/ol>\n<\/div>\n

       <\/p>\n

      Why in the example above, did the decision tree choose the savings attribute for the root node split? Why did it not choose assets or income instead? Decision trees seek to create a set of leaf nodes that are as \u201cpure\u201d as possible, that is, where each of the records in a particular leaf node has the same classification. In this way, the decision tree may provide classification assignments with the highest measure of confidence available.<\/p>\n

       <\/p>\n

      However, how does one measure uniformity, or conversely, how does one measure heterogeneity? We shall examine two of the many methods for measuring leaf node purity, which lead to the two leading algorithms for constructing decision trees:<\/p>\n

       <\/p>\n

      Classification and regression trees (CART) algorithm C4.5 algorithm.<\/p>\n

       <\/p>\n

      COMPARISON OF THE C5.0 AND CART ALGORITHMS APPLIED TO REAL DATA<\/strong><\/p>\n

       <\/p>\n

      Next, we apply decision tree analysis using Clementine on a real-world data set. The data set adult<\/em> was abstracted from U.S. census data by Kohavi and is available online from the University of California at Irvine Machine Learning Repository.<\/p>\n

      \n

      Here, we are interested in classifying whether or not a person\u2019s income is less than $50,000, based on the following set of predictor fields.<\/p>\n

       <\/p>\n

      Numerical variables<\/strong><\/p>\n

       <\/p>\n

      Age, Years of education, Capital gains, Capital losses, Hours worked per week.<\/p>\n

      Categorical variables, Race, Gender, Work class, Marital status.<\/p>\n

      The numerical\u00a0 variables\u00a0 were normalized so that all values\u00a0 ranged between zero and 1.Some\u00a0 collapsing\u00a0 of\u00a0 low-frequency\u00a0 classes\u00a0 was\u00a0 carried\u00a0 out\u00a0 on the\u00a0 work class and marital\u00a0 status categories.Clementine\u00a0 was used to compare\u00a0 the C5.0\u00a0 algorithm (an\u00a0 update\u00a0 of\u00a0 the\u00a0 C4.5\u00a0 algorithm)\u00a0 with\u00a0 CART,\u00a0 examining\u00a0 a\u00a0 training\u00a0 set of\u00a0 24,986 records. The decision tree produced by the CART algorithm.<\/p>\n

       <\/p>\n

      \"\"<\/p>\n","protected":false},"author":4,"menu_order":36,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-r-baskaran"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-267","chapter","type-chapter","status-publish","hentry","contributor-dr-r-baskaran"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/267","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":1,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/267\/revisions"}],"predecessor-version":[{"id":271,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/267\/revisions\/271"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/267\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/media?parent=267"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapter-type?post=267"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/contributor?post=267"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/license?post=267"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}