Decision Trees Overview

Decision Trees Overview

• Decision trees are a popular supervised classification technique
• They guide decision-making in a hierarchical structure through a series of questions
• Decisions can be simple or complex
• Ideal for situations with small datasets and binary decisions
• Widely used in data mining for tasks like predicting heart attacks, and disease diagnosis
• The process mirrors doctor-patient interaction for diagnosis

Learning Objectives

• Understand the fundamentals of decision trees
• Learn how to construct decision trees using simple datasets
• Identify common decision tree algorithms

What are Decision Trees?

• A supervised classification method that guides decision-making
• Decisions are hierarchical, made through sequentially asked questions
• The structure is a branched flow chart.
• Useful when data is limited but binary solutions are required.
• Create a clear and concise pathway to get to a final decision.

Case Study: Predicting Heart Attacks

• Data mining used to predict 30-day heart attack risk
• Uses patient data with 100+ variables, including blood pressure, age, and sinus issues
• Used CART (Classification and Regression Trees) algorithm
• Achieved 86.5% accuracy in predicting heart attack risk

Results of Heart Attack Predictions

• Low blood pressure (<90) indicates high heart attack risk (70% chance)
• Age <=62 correlates with high patient survival rates (98% chance)
• Patients with sinus issues were examined further for survival chance.
• 86.5% of the cases were correctly predicted using the decision tree

Disease Diagnosis

• Decision tree logic fits well in doctor-patient diagnosis, through sequential question asking.
• Decisions & symptoms & treatments are evaluated in a hierarchical manner.
• Decision rules can be used for disease diagnosis.

Machine Learning and Decision Trees

• Learn from existing data (past cases) and infer knowledge
• Decision trees use machine learning algorithms to extract patterns
• Accuracy is measured by how precisely decisions from the tree match real-world outcomes (predictive accuracy)

Decision Trees: Points to Consider

• Increased accuracy from more training data.
• More variables provide a wider decision-making range.
• Best-performing trees minimize the necessary questions
• Require minimal effort by decision-makers to achieve a solution

Exercise: Predicting Play Given Atmospheric Conditions

• An example dataset is given with the outlook, temperature, humidity, wind conditions to predict whether to play a game or not.

Data Set and Decision Tree Construction

• Decision trees are created by analyzing available data to establish decision rules.
• Past data analysis helps to identify trends and classify future events more accurately.
• Building a decision tree, when data isn’t exactly the same, is the best choice.

Decision Tree Construction Process

• Determine the root node of the tree
• Split the tree based on the values of chosen attributes/variables
• Determine the next nodes, based on the errors in earlier decisions.

Determining the Root Node

• Identifying the most important factor, which has the greatest impact on determining the outcome.
• Criteria used to compare various variables and identify the best candidate for the first decision variable.

Error Measurement and Decision Tree Performance

• Measuring the accuracy/error rate, used to evaluate the effectiveness of the tree, which needs balanced complexity
• Overfitting and underfitting must be avoided during tree construction.

The Splitting Criteria

• Choose a method that decides which factors to consider at each branch of the tree.
• Entropy (uncertainty), Gini Impurity, and Chi-Square are example methods.

Determine Root Node of a Tree: Outlook (Example)

• Sunny, Overcast, or Rainy, each provide a different result
• Accuracy is evaluated to determine which factor has the lowest error rate.

Determining the Root Node of a Tree: Temperature (Example)

• Hot, Mild, or Cool, each provide a different result.
• Results are ranked by the accuracy of the results.

Determining the Root Node of a Tree: Humidity (Example)

• High or Normal, to further classify outcome and measure accuracy.

Determining the Root Node of a Tree: Windy (Example)

• False or True, to further classify outcome and measure accuracy.

Determining the Root Node of a Tree (Final Node)

• Choosing the variable/factor that provides the least error in predictions.

Splitting the Tree

• Dividing the dataset into smaller segments according to the selected criteria
• Creating sub-trees (similar to branches) for each segment, to further segment the data.

Identifying the Next Nodes

• Applying the same split criteria method as the root node to further segment the data until a specified endpoint (leaf node).

Decision Tree Algorithms (Example)

• C4.5, CART, and CHAID algorithms are commonly used to create decision trees.

Key Elements of Decision Tree Algorithms

• Choosing the best criteria for splits to use at each node.
• Establish an appropriate end to branch creation.
• Removing redundant/unneeded parts of the completed tree.

Pruning the Decision Tree

• A process to reshape/trim the finished tree to improve its balance and usability
• Removing branches/subsets, based on accuracy and other criteria
• Pre-pruning and post-pruning techniques are used to avoid overfitting and achieve the best accuracy

Most Popular Decision Tree Algorithms

• C.45, CART, and CHAID are popular and well-known algorithms

Summary of Decision Trees

• Summarize the entire process of constructing a decision tree, from creating a root node and splitting the data, to determining the next node, to pruning, to evaluating, and finally determining the accuracy and usefulness of the data.

Lessons from Constructing Trees

• Advantages and disadvantages of decision trees and table lookups (comparison)
  • Accuracy, generality, and timeliness are important factors to consider when choosing between these two methods.

Observations about the Data

• The limitations of applying theoretical decision trees to real-life applications
• Discuss how and why 100% accuracy is not possible for real-world decision trees.