This chapter discusses the features and capabilities of the Decision Tree Inducer (its associated visualizer, the Tree Visualizer, is described in Chapter 4). This chapter provides an overview of this tool and discusses the ways of using it to generate Decision Tree classifiers. It then explains the Tree Visualizer's functionality when working with the main window. Finally, it lists and describes the sample files provided for this tool.
 | Note: It is assumed that you have read Chapter 8, “MineSet Inducers and Classifiers,” before proceeding with this chapter. |
A decision tree classifier assigns each record to a class. The underlying structure used for classification is a decision tree, such as the one shown in Figure 9-1.
A Decision Tree classifier is induced (generated) automatically from data. The data, which is made up of records and a label associated with each record, is called the training set (see Chapter 8, “MineSet Inducers and Classifiers”).
The Decision Tree Inducer requires a training set, as described in the “Training Set” section of Chapter 8. Files are generated by extracting data from a source (such as an ASCII file or a table in an Oracle, INFORMIX, or Sybase database). To apply the generated classifier, you should have a dataset of records with the same attributes as the training set, except that the label need not be present.
There are two ways to run the Decision Tree Inducer:
From the Tool Manager.
Connect to the server and select a data source (see “Connecting to a Server and Choosing a Data Source” in Chapter 3). In the Data Transformations panel, make the appropriate transformations; specifically, remove any column that you do not want considered.
To see the induction process, choose Client File from Tool Manager and type /usr/lib/MineSet/data/iris.schema. You'll see four continuous attributes and one discrete attribute in the Data Transformation panel. Since there is only one discrete attribute, the label option automatically shows it. Select the Decision Tree Inducer, and ensure you have selected the Classifier & Accuracy mode. To run the Inducer, click Go!.
You'll see a small popup window with information and statistics, followed by another window showing the classifier structure in the Evidence Visualizer.
From the command line.
To induce a decision tree classifier from the command line, refer to Appendix E, “Command-Line Interface to MIndUtil: Classifiers, Discretization, Column Importance, and File Conversions.”
To access the options for configuring the Decision Tree Inducer, select the Mining Tools tab on the Data Destination panel (Figure 9-2). From the subsequent tabs, select Classifiers. Ensure that the inducer you select is Decision Tree (the default). Your selections in the Mode and Algorithm menus determine the options available in the Further Inducer Options menu. After you have made your selections in these menus, click Go! to run the inducer, which, in turn, creates the classifier.
Figure 9-3 shows the two possible induction algorithms for creating the two MineSet classifiers: Decision Tree and Evidence.
The Discrete Labels menu provides a list of possible discrete labels. Discrete attributes (binned values, character string values, or a few integers) have a limited number of values. You should select a label attribute with few values; for instance, two or three (see “Training Set” in Chapter 8). If there are no discrete attributes, the menu shows No Discrete Label, and the Go! button is disabled. You then must create a discrete attribute by binning or adding a new column using the Tool Manager's Data Transformations panel.
The generated classifier is named with the prefix of the session filename (as determined in Tool Manager) with the suffix -dt.class. By default, all classifiers are stored on the server in the file_cache directory, which defaults to mineset_files. These classifiers can be used for future classification of unlabeled records; that is, they can be used to predict the labels for unlabeled datasets (see “The Apply Classifier Button” in Chapter 3).
Selecting Further Classifier Options causes the Classifier Options dialog box to appear. This dialog box consists of three panels:
The top panel indicates the choices you made in the Tool Manager's Data Destination panel.
The bottom-left panel lets you specify further Inducer Options.
The bottom-right panel lets you specify the Accuracy Options (unless the mode you chose in the Data Destination panel was Classifier Only, in which case this area is empty). The options shown in this panel depend on the type of Accuracy Estimation you chose (see “Accuracy Estimation” in Chapter 8).
To fine-tune the Decision Tree induction algorithm, you can change the following Decision Tree Inducer options (see Figure 9-4):
-
The default (0) indicates there is no limit to the number of levels in the decision tree. Limit the number of levels to speed up the induction or when you want to study the decision tree and not be distracted by too many nodes. Note that restricting the size decreases the run time but might degrade accuracy. Setting this option does not affect the attributes chosen at levels before the maximum level.
-
This option offers three splitting criteria selections. The definitions below are technical. It is difficult to know in advance which one of these criteria might be better. You should try them all and select the one that leads to the highest accuracy estimate or to a decision tree you find easiest to understand.
Mutual Info—This is the change in purity (that is, the entropy) between the parent node and the weighted average of the purities of the child nodes. The weighted average is based on the number of records at each child node.
Normalized Mutual Info (the default)—This is the Mutual Info divided by the log (base 2) of the number of child nodes.
Gain Ratio—This is the Mutual Info divided by the entropy of the split while ignoring the label values.
Normalized Mutual Info and Gain Ratio give preference to attributes with few values.
-
This is a lower bound on the number of records that must be present in at least two of the node's children. The default for this option is 5. For example, if there is a three-way split in the node, at least two out of the three children must have at least five records. This provides another method of limiting the size of the decision tree.
Raising this number creates smaller trees and speeds up the induction time. If you expect the data to contain noise (errors or anomalies), increase this number. If your dataset contains only a few hundred records, you can decrease this number to 2 or 3. If your dataset is very small (< 100 records), you might want to decrease this number to 1.
-
A decision tree is built based on the limits imposed by Max # of Levels and Split Lower Bound. Statistical tests are then made to determine when some subtrees are not significantly better than a single leaf node in which case those subtrees are pruned.
The default pruning factor of 0.85 indicates the recommended amount of pruning to be applied to the decision tree. Higher numbers indicate more pruning; lower numbers indicate less pruning. If your data might contain noise (errors or anomalies), increase this number to create smaller trees. The lowest possible value is 0 (no pruning); there is no upper value limit.
Pruning is slower than limiting the maximum number of tree levels or increasing the split lower bound because a full tree is built and then pruned. Pruning, however, is done selectively, resulting in a more accurate classifier.
The Tree Visualizer's main window shows the decision tree. This decision tree consists of nodes connected by lines (see Figure 9-1).
decision
leaf
Decision nodes specify the attribute that is tested at the node. Values (or ranges of values) against which the attributes are tested are shown at the lines. Each possible value for the attribute matches exactly one line. For example, the root of the decision tree in Figure 9-1 tests the attribute petal_length; the two lines emanating from the node specify the ranges of values for that attribute (≤2.6 and >2.6,) so that every possible value matches either the right branch or the left branch. If the value is unknown and there is no line labeled with a question mark (?), the majority class of the current node is predicted.
Leaf nodes in a decision tree specify a class. Follow the left branch in Figure 9-1 from the root to a leaf labeled iris-setosa. Note that the Decision Tree classifier classifies all records with petal_length ≤ 2.6 inches as belonging to the class iris-setosa.
The base of each node has a height and a color. The height corresponds to the number of records from the training set that have reached this node. In general, the more records, the more reliable the class distribution at every node.
Each node has a measure of purity (a number from 0 to 100) associated with it. This measure indicates how likely it is to accurately predict the correct class for the records at a given node. The color of the base indicates the purity of the node based on a street-light analogy: red indicates low purity (a prediction is difficult), yellow indicates mixed, green indicates high purity (making a prediction is easy and thus more likely to be correct).
All possible outcomes are marked on the horizontal lines emanating from each decision node. Each line indicates the value (or range of values) against which the attribute of that node was tested.
To classify a record, start at the root, and test how to branch at every decision node. By following the appropriate lines based on the record's attribute values, you reach a leaf node. The label, or class, associated with the leaf node is the predicted classification of the record.
Some decisions are quickly made and take a shorter path (for example, petal_length ≤ 2.6 implies iris-setosa). Other decisions can take a longer path (for example, the right branches, petal_length > 2.6 and petal_width > 1.65). In general, every leaf corresponds to a rule that is the conjunction of all tests at the decision nodes and all the values (or ranges of values) on the lines leading to it from the root.
In the root of the tree shown in Figure 9-1, the purity is 0.06, indicating that it is extremely difficult to correctly predict the class. Indeed, the root has almost an equal number of records from each class.
The left child of the root has an purity of 100 because all records with petal_length ≤ 2.6 inches are of the iris-setosa class; thus, the prediction of iris-setosa is likely to be very accurate for all records with petal_length ≤ 2.6 inches. The right child of the root has a purity of 36.92. In this child, which matches records whose petal_length > 2.6 inches, there are no records belonging to the iris-setosa class; thus, the class is more likely to be iris-versicolor or iris-virginica. Because only two possibilities exist at this node, there is a higher purity than at the root.
The decision tree leaves segment the data into clusters sharing the same classification rule (path that leads to each leaf). By looking at the leaves, it is possible to see clusters that share the same set of properties.
The external controls for the visualizer associated with the Decision Tree Classifier are the same as those for the Tree Visualizer. For a description of these controls, see “External Controls” in Chapter 4.
The pulldown menus for the visualizer associated with the Decision Tree Classifier are the same as those for the Tree Visualizer. For a description of these menus, see “External Controls” in Chapter 4.
Select Search Panel in the Show menu to bring up a dialog box that lets you specify criteria to search for objects (Figure 9-5). The search panel is the same search panel described in “The Search Panel” in Chapter 4; however, the item choices for decision trees are always the same. These are described below.
The search can be restricted to specific class labels, either by selecting the values in the class list or by using the Class item, which allows more powerful comparison operators (such as Matches). Other items are described below:
“Record count” lets you restrict the search to bars or bases (depending on the choice of the radio button bars/bases) with a given number of records. For example, you can restrict the search to bars containing over 50 records.
“Test attribute” lets you restrict the search to nodes labeled by the given value that the node is testing. Note that decision node labels represent the test attribute, while leaf node labels show the predicted label. For example, if you select Test attribute contains age, only nodes that test the value of age are considered.
“Test value” lets you restrict the search to nodes having an incoming line labeled with a value you specify.
“Percent” lets you restrict the search to bars representing a percentage of the overall records at a node. For example, you might want to find all nodes such that a given class accounts for more than 80 percent of the records. To do this, click the class label, and select Percent > 80. Setting this item is meaningless if you select bases and not bars (the value for the bases is 0).
“Purity” lets you restrict the search to nodes with a range of purity levels. For example, if you want to look at pure nodes (with one class predominant), you can select Purity > 90.
“Level” lets you restrict the search to a specific level or range of levels. For example, you can search only the first five levels.
The following items and options are less useful for decision trees.
Once the search is complete, yellow spotlights highlight objects matching the search criteria. To display information about an object under a yellow spotlight, move the pointer over that spotlight; the information appears in the upper left corner, under the label “Pointer is over.” To select and zoom to an object under a yellow spotlight, left-click the spotlight; if you press the Shift key while clicking, zooming does not occur.
The following examples show cases in which the Decision Tree Inducer can be useful. Each of these examples is associated with a sample data file provided with MineSet. By running the inducer, you can generate the -dt.treeviz files described below.
| Note: The data files, which have a .schema extension, are located in /usr/lib/MineSet/data on the client workstation. The classifier visualization files, which have a -dt.treeviz extension, reside on the client workstation in /usr/lib/MineSet/treeviz/examples. |
The cars dataset contains information about different models of cars from the 1970s and early 1980s. Attributes include weight, acceleration, and miles per gallon (mpg). The file /usr/lib/MineSet/treeviz/examples/cars-dt.treeviz shows the Decision Tree classifier induced for this problem. This file was generated by running the inducer on /usr/lib/MineSet/data/cars.schema with the label set to origin (Japan, U.S., Europe) and the brand deleted to make the problem non-trivial.
If you have a dataset of car attributes, you might want to know what characterizes cars of different origins.
In the decision tree, you can see that cubic inches is an excellent discriminator for U.S.-made cars. Cars with large engines (>190.5 cubic inches) are all made in the U.S., but smaller cars are made everywhere. Note that in this tree, the root node (that is, the entire training dataset) has many more U.S. cars (67.8%), yet after a single split on the cubic inches, it is more difficult to predict the origin of cars with small engines. The purity of the root is 22.6 (orange color) showing that there is one class (U.S. in this case) that is dominant. The right node (cubic inches > 190.5) has purity 100 (green), indicating that we have identified a very pure subpopulation (all cars with large engines were made in the U.S.). The left node from the root has purity 0.33 (red). This subproblem is much harder than the original one: the number of records for each class is approximately the same. Branching left from this node, we can see that very small engines (≤85.5 cubic inches) are all Japanese.
The adult dataset contains information about working adults. This dataset was extracted from the U.S. Census Bureau. It contains data about people older than 16, with a gross income of more than $100 per year who work at least one hour a week. You might want to know how to characterize males and females. The file /usr/lib/MineSet/treeviz/examples/adult-sex-dt.treeviz shows the Decision Tree classifier induced for this problem. This file was generated by running the inducer on /usr/lib/MineSet/data/adult.schema, with the label set to sex, after removing the relationship column (which would have made the classifier trivial). Note that this dataset contains almost 50,000 records; thus, running the Decision Tree Inducer can take several minutes.
The resulting visualization provides the following insights:
The most important attribute is marital status.
From the height of the base, it is obvious that most people are either divorced, married to a civilian spouse, or never married.
The distribution at the root shows more males in this dataset. (Note that this database contains information about working adults and is not representative of the entire population.)
The left-most node contains divorced working adults. We can see that the distribution is more balanced than at the root (60% female, 40% male). The second node contains married working adults. We can see that 89% are males. The third node contains working adults that have not married. As with the divorced group, they are approximately equal in number, with slightly more males. The right-most node contains working widowed adults. We can see that 81% are females, probably because of their higher life expectancy.
If you want to target working females for a new product, you can use the search panel to identify segments that have a large population of females. You can do this by choosing
class matches female
record count > 1000
percent > 70
Two yellow spotlights show the matching nodes. Since they are both on one path, look at the node closest to the root. The path translates into the rule
marital_status = never_married and occupation = administrative_clerical implies that 71.6% are female |
In this training set, out of 10,776 females at the root, 1129 satisfy this rule. This simple segment contains over 10% of working women.
If you have a dataset of working adults, you might want to find out what factors affect salary. You might then divide the records into two classes: those making ≤ $50,000 a year, and those making more. Each record then has an attribute with two values: “- 50,000” and “50,000+”. You can run a MineSet classifier to help determine what factors influence salary. The file /usr/lib/MineSet/treeviz/examples/adult-salary-dt.treeviz shows the Decision Tree classifier induced for this problem. This file was generated by running the inducer on /usr/lib/MineSet/data/adult.schema with gross_income binned at the user-specified threshold of 50000 and the label set to gross_income_bin.
The resulting visualization provides the following insights:
The root, which represents the entire training set, shows 70% of the working adults earning ≤ $50,000.
Age is the most important factor. Only 3% of the people under 27 years old earn more than $50,000. Note that the base color is green, indicating a mostly pure segment.
Education is an important factor for predicting salary for people over 27 years old. A high value leads to a node where 55% earn over $50,000.
Of the segment that is older than 27 years and well educated, relationship is an important predictor of salary. For those persons that are married, chances of earning $50,000 or more increase to 73% for husbands and 76% for wives. (Note, however, that the node containing wives is small, representing few females.) If the person in this group is not married, chances of earning $50,000 or more decrease to 28% for males and 23% for females.
In this dataset, each record describes four characteristics of iris flowers: petal width, petal length, sepal width, and sepal length. Each iris was further classified into the types iris-setosa, iris-versicolor, or iris-virginica. The goal is to understand what characterizes each iris type.
Before running a classifier, click the Column Importance tab in the Tool Manager's Classifiers tab; then click Go!. You obtain a ranking of the importance of the features: petal_width, petal_length, and sepal_length. You can map these to the axes in the Scatter Visualizer, with the iris_type mapped to the color, and see the clusters.
The file /usr/lib/MineSet/treeviz/examples/iris-dt.treeviz shows the Decision Tree classifier induced for this problem. This file was generated by running the inducer on /usr/lib/MineSet/data/iris.schema.
Running the Tree Visualizer, you can see that the root is red (low purity), indicating that it's hard to make a prediction at the root. However, the left branch (petal-length ≤ 2.6 inches) goes to a green node (pure) containing only iris-setosas. The other branches are also quickly able to separate the classes using another test on the petal_width. The path petal-length > 2.6 and petal-width ≤ 1.65 ends with an impure leaf. There are 3 records of type iris-virginica and 33 of iris-versicolor. The decision tree did not split this node because it was deemed insignificant (by default, every split must contain five records).
To summarize: the flowers with petal length ≤ 2.6 inches are predicted as iris-setosa, those with petal length > 2.6 inches and petal width ≤1.65 inches are predicted as iris-versicolor, and those with a petal length >2.6 inches and a petal width > 1.65 inches are predicted as iris-virginica.
Note that because the decision tree makes binary splits on continuous attributes while Column Importance discretizes the data, the root split of the tree is different from the first attribute in column importance (see Chapter 11 for more details).
The file /usr/lib/MineSet/treeviz/examples/mushroom-dt.treeviz shows the Decision Tree classifier induced for the classification of mushrooms. This file was generated by running the inducer on /usr/lib/MineSet/data/mushroom.schema.
The goal is to understand which mushrooms are edible and which are poisonous, given this dataset. There are over 8000 records in this set; thus, running this inducer might take several minutes. Note that under the default mode of the one-third holdout for accuracy estimation, a third of the records are kept for testing.
Each mushroom has many characteristics, including cap color, bruises, and odor. If you build a Decision Tree classifier, you can see that using only the odor attribute lets you determine in 50% of the cases whether the mushroom is poisonous or edible. If the mushroom has no odor, there is a 3% chance it is poisonous. The next attribute to look at is the shape of the stalk. If it tapers, the mushroom is edible; but if enlarges, there is a 10% chance the mushroom is poisonous. About 600 mushrooms reach this node. You can follow the tree down further nodes to see what other attributes to consider.
This dataset consists of voting records. The goal is to identify the party a congressperson belongs to given data about key votes. The dataset includes votes for each member of the U.S. House of Representatives on the 16 key votes identified by the Congressional Quarterly Almanac (CQA). The CQA lists nine types of votes: voted for, paired for, and announced for (these three are simplified to yes); voted against, paired against, and announced against (these three are simplified to no); voted present, voted present to avoid conflict of interest, and did not vote or otherwise make a position known (these three are simplified to an unknown disposition).
Before running a classifier, look at the 16 votes to see if you can perceive which features are important. Then run the Decision Tree classifier.
The file /usr/lib/MineSet/treeviz/examples/vote-dt.treeviz shows the Decision Tree classifier induced for this problem. This file was generated by running the inducer on /usr/lib/MineSet/data/vote.schema.
The breast cancer dataset contains information about females undergoing breast cancer diagnosis. Each record is a patient with attributes such as cell size, clump thickness, and marginal adhesion. The final attribute is whether the diagnosis is malignant or benign. The file /usr/lib/MineSet/treeviz/examples/breast-dt.treeviz shows the Decision Tree classifier induced for this problem. This file was generated by running the inducers on /usr/lib/MineSet/data/breast.schema.
The decision tree shows that uniformity_of_cell_size is a very strong discriminatory attribute. While the root is red (low purity), the two children of the root are shades of green (high purity), with the left node having over 97% of one class. While the accuracy is better with a fully built tree, a tree with a single test is already very accurate. As described in the “Decision Tree Inducer Options” section, you can limit the tree size to one level and estimate its accuracy.
The hypothyroid diseases dataset is similar to the one for breast cancer. The file /usr/lib/MineSet/treeviz/examples/hypothyroid-dt.treeviz shows the Decision Tree classifier induced for this problem. This file was generated by running the inducer on /usr/lib/MineSet/data/hypothyroid.schema.
There are 3163 records in this dataset and most of them do not have hypothyroid (95.45%). While this means that one can predict “negative” and be correct with high probability, it's those people that have hypothyroid that we are most worried about. In technical terms, the false negatives are very important.
Looking at the decision tree, you can see that the root node is “green” (easy to predict). However, the single attribute on “fti” at the root shows that it is relatively easy to identify many of the negative diagnosis. People with high fti are 99.83% negative, and all those where the value is unknown are also negative (perhaps the doctor decided not to measure this attribute because something else was obvious), but the rest (145 people) are hard cases. We started with 2109 records (two-thirds of the whole dataset), but only 145 are really “interesting” to mine because it was very easy to throw away most cases. In this example most of the data is uninteresting and you want to concentrate on a small part quickly. Of the 145 people, you can see that about 65% are positive and 35% negative, which is why it's hard to make a decision and the base of the node is orange-red.
As you move down the tree, increase the height scale (slider on the top left of the visualizer) to see the different heights. The node that catches most of the people with hypothyroid has the conditions “fti ≤ 64.5 and tsh > 5.96.” It contains 90 of the 96 records that have hypothyroid.
This dataset is a diagnosis problem for diabetes using statistics gathered from a Native American tribe in Phoenix Arizona. The task is to determine whether a patient has diabetes, given some medical attributes, such as blood pressure, body mass, glucose level, and age.
The file /usr/lib/MineSet/treeviz/examples/pima-dt.treeviz shows the Decision Tree classifier induced for this problem. This file was generated by running the inducer on /usr/lib/MineSet/data/pima.schema.
There are 3,186 records in this DNA dataset. The domain is drawn from the field of molecular biology. Splice junctions are points on a DNA sequence at which “superfluous” DNA is removed during protein creation. The task is to recognize exon/intron boundaries, referred to as EI sites; intron/exon boundaries, referred to as IE sites; or neither. The IE borders are referred to as “acceptors” and the EI borders are “donors.” The records were originally taken from GenBank 64.1 (genbank.bio.net). The attributes provide a window of 60 nucleotides. The classification is the middle point of the window, thus providing 30 nucleotides at each side of the junction.
In this example, the root of the decision tree shows the distribution of the three classes. By pointing to the bars, you can see that the composition is about 24% exon/intron, 24% intron/exon, and 52% none. The “left_01” in front of the root node indicates that this is an important attribute to look at first. The “left_01” notation refers to the first nucleotide found to the left of the splice junction in question. The choices of attribute values for this first nucleotide (and all nucleotides in general) are the “A”, “G”, “T”, and “C” nucleotides. If the “left_01” nucleotide is a “G”, then the “G” branch is taken and followed to the next node, where the distribution now shows that such a nucleotide is more likely to be an “exon/intron” or an “intron/exon” than at the root: the distribution is 35% for “exon/intron,” 41% for “intron/exon”, and 24% for “none.” If the “left_01” nucleotide is an “A”, “T”, or “C”, then the corresponding “A”, “T”, or “C” branch is taken instead and in all three cases, the probability of “none” increases dramatically (88%, 90%, and 95% respectively). This testing and branching process is repeated until the final node with the predicted class (“exon/intron”, “intron/exon”, or “none”) is reached.
For this dataset, the Evidence Classifier (Chapter 10) is more appropriate than a Decision Tree due to the probabilistic nature of this domain. This can be verified by comparing the estimated accuracies.