Understanding Decision Trees in Data Science

decision trees n.w
1 / 65
Embed
Share

Explore the concept of decision trees with practical examples and visual representations. Learn how decision trees can be used to make informed decisions in a machine learning context based on feature analysis and classification.

  • Decision Trees
  • Data Science
  • Machine Learning
  • Classification
  • Feature Analysis
rayaanacharya
kunselman_k Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. DECISION TREES David Kauchak CS 158 Fall 2019

  2. Admin Assignment 1 due tomorrow (Friday) Assignment 2 out soon: start ASAP! (due next Sunday) Lecture notes posted Keep up with the reading Videos

  3. A sample data set Features Label Hour Weather Accident Stall Commute 8 AM Sunny No No Long 8 AM Cloudy No Yes Long 10 AM Sunny No No Short 9 AM Rainy Yes No Long 9 AM Sunny Yes Yes Long 10 AM Sunny No No Short 10 AM Cloudy No No Short 9 AM Sunny Yes No Long 10 AM Cloudy Yes Yes Long 10 AM Rainy No No Short 8 AM Cloudy Yes No Long 9 AM Rainy No No Short 8 AM, Rainy, Yes, No? 10 AM, Rainy, No, No? Can you describe a model that could be used to make decisions in general?

  4. Decision trees Leave At Tree with internal nodes labeled by features 10 AM 9 AM 8 AM Stall? Accident? Branches are labeled by tests on that feature No Yes Long No Yes Leaves labeled with classes Short Long Short Long

  5. Decision trees Leave At Tree with internal nodes labeled by features 10 AM 9 AM 8 AM Stall? Accident? Branches are labeled by tests on that feature No Yes Long No Yes Leaves labeled with classes Short Long Short Long Leave = 8 AM Weather = Rainy Accident = Yes Stall = No

  6. Decision trees Leave At Tree with internal nodes labeled by features 10 AM 9 AM 8 AM Stall? Accident? Branches are labeled by tests on that feature No Yes Long No Yes Leaves labeled with classes Short Long Short Long Leave = 8 AM Weather = Rainy Accident = Yes Stall = No

  7. Decision trees Leave At Tree with internal nodes labeled by features 10 AM 9 AM 8 AM Stall? Accident? Branches are labeled by tests on that feature No Yes Long No Yes Leaves labeled with classes Short Long Short Long Leave = 10 AM Weather = Rainy Accident = No Stall = No

  8. Decision trees Leave At Tree with internal nodes labeled by features 10 AM 9 AM 8 AM Stall? Accident? Branches are labeled by tests on that feature No Yes Long No Yes Leaves labeled with classes Short Long Short Long Leave = 10 AM Weather = Rainy Accident = No Stall = No

  9. To ride or not to ride, that is the question Terrain Unicycle- type Weather Go-For-Ride? Trail Normal Rainy NO Road Normal Sunny YES Trail Mountain Sunny YES Road Mountain Rainy YES Trail Normal Snowy NO Road Normal Rainy YES Road Mountain Snowy YES Trail Normal Sunny NO Road Normal Snowy NO Trail Mountain Snowy YES Build a decision tree

  10. Recursive approach Base case: If all data belong to the same class, create a leaf node with that label Otherwise: - calculate the score for each feature if we used it to split the data - pick the feature with the highest score, partition the data based on that data value and call recursively

  11. Partitioning the data Terrain Trail Road Terrain Unicycle- type Weather Go-For- Ride? ? Trail Normal Rainy NO Road Normal Sunny YES Trail Mountain Sunny YES Road Mountain Rainy YES Trail Normal Snowy NO Road Normal Rainy YES Road Mountain Snowy YES Trail Normal Sunny NO Road Normal Snowy NO Trail Mountain Snowy YES

  12. Partitioning the data Terrain Trail Road Terrain Unicycle- type Weather Go-For- Ride? ? Trail Normal Rainy NO Road Normal Sunny YES Trail Mountain Sunny YES Road Mountain Rainy YES Trail Normal Snowy NO Road Normal Rainy YES Road Mountain Snowy YES Trail Normal Sunny NO Road Normal Snowy NO Trail Mountain Snowy YES

  13. Partitioning the data Terrain Trail Road Terrain Unicycle- type Weather Go-For- Ride? Trail Normal Rainy NO YES: 4 NO: 1 Road Normal Sunny YES Trail Mountain Sunny YES Road Mountain Rainy YES Trail Normal Snowy NO Road Normal Rainy YES Road Mountain Snowy YES Trail Normal Sunny NO Road Normal Snowy NO Trail Mountain Snowy YES

  14. Partitioning the data Terrain Trail Road Terrain Unicycle- type Weather Go-For- Ride? Trail Normal Rainy NO YES: 4 NO: 1 ? Road Normal Sunny YES Trail Mountain Sunny YES Road Mountain Rainy YES Trail Normal Snowy NO Road Normal Rainy YES Road Mountain Snowy YES Trail Normal Sunny NO Road Normal Snowy NO Trail Mountain Snowy YES

  15. Partitioning the data Terrain Trail Road Terrain Unicycle- type Weather Go-For- Ride? Trail Normal Rainy NO YES: 4 NO: 1 YES: 2 NO: 3 Road Normal Sunny YES Trail Mountain Sunny YES Road Mountain Rainy YES Trail Normal Snowy NO Road Normal Rainy YES Road Mountain Snowy YES Trail Normal Sunny NO Road Normal Snowy NO Trail Mountain Snowy YES

  16. Partitioning the data Terrain Trail Road Terrain Unicycle- type Weather Go-For- Ride? Trail Normal Rainy NO YES: 4 NO: 1 YES: 2 NO: 3 Road Normal Sunny YES Trail Mountain Sunny YES Unicycle Road Mountain Rainy YES Normal Mountain Trail Normal Snowy NO Road Normal Rainy YES ? ? Road Mountain Snowy YES Trail Normal Sunny NO Road Normal Snowy NO Trail Mountain Snowy YES

  17. Partitioning the data Terrain Trail Road Terrain Unicycle- type Weather Go-For- Ride? Trail Normal Rainy NO YES: 4 NO: 1 YES: 2 NO: 3 Road Normal Sunny YES Trail Mountain Sunny YES Unicycle Road Mountain Rainy YES Normal Mountain Trail Normal Snowy NO Road Normal Rainy YES YES: 4 NO: 0 YES: 2 NO: 4 Road Mountain Snowy YES Trail Normal Sunny NO Road Normal Snowy NO Trail Mountain Snowy YES

  18. Partitioning the data Terrain Trail Road Terrain Unicycle- type Weather Go-For- Ride? Trail Normal Rainy NO YES: 4 NO: 1 YES: 2 NO: 3 Road Normal Sunny YES Trail Mountain Sunny YES Unicycle Road Mountain Rainy YES Normal Mountain Trail Normal Snowy NO Road Normal Rainy YES YES: 4 NO: 0 YES: 2 NO: 4 Road Mountain Snowy YES Trail Normal Sunny NO Road Normal Snowy NO Weather Trail Mountain Snowy YES Sunny Rainy Snowy YES: 2 NO: 1 YES: 2 NO: 2 YES: 2 NO: 1

  19. Partitioning the data Terrain Unicycle Weather Trail Normal Sunny Road Mountain Rainy Snowy YES: 4 NO: 1 YES: 2 NO: 3 YES: 4 NO: 0 YES: 2 NO: 4 YES: 2 NO: 1 YES: 2 NO: 2 YES: 2 NO: 1 calculate the score for each feature if we used it to split the data What score should we use? If we just stopped here, which tree would be best? How could we make these into decision trees?

  20. Decision trees Terrain Unicycle Weather Trail Normal Sunny Road Mountain Rainy Snowy YES: 4 NO: 1 YES: 2 NO: 3 YES: 4 NO: 0 YES: 2 NO: 4 YES: 2 NO: 1 YES: 2 NO: 2 YES: 2 NO: 1 How could we make these into decision trees?

  21. Decision trees Terrain Unicycle Weather Trail Normal Sunny Road Mountain Rainy Snowy YES: 4 NO: 1 YES: 2 NO: 3 YES: 4 NO: 0 YES: 2 NO: 4 YES: 2 NO: 1 YES: 2 NO: 2 YES: 2 NO: 1

  22. Decision trees Terrain Unicycle Weather Trail Normal Sunny Road Mountain Rainy Snowy YES: 4 NO: 1 YES: 2 NO: 3 YES: 4 NO: 0 YES: 2 NO: 4 YES: 2 NO: 1 YES: 2 NO: 2 YES: 2 NO: 1 Training error: the average error over the training set For classification, the most common error is the number of mistakes Training error for each of these?

  23. Decision trees Terrain Unicycle Weather Trail Normal Sunny Road Mountain Rainy Snowy YES: 4 NO: 1 YES: 2 NO: 3 YES: 4 NO: 0 YES: 2 NO: 4 YES: 2 NO: 1 YES: 2 NO: 2 YES: 2 NO: 1 3/10 2/10 4/10 Training error: the average error over the training set

  24. Training error vs. accuracy Terrain Unicycle Weather Trail Normal Sunny Road Mountain Rainy Snowy YES: 4 NO: 1 YES: 2 NO: 3 YES: 4 NO: 0 YES: 2 NO: 4 YES: 2 NO: 1 YES: 2 NO: 2 YES: 2 NO: 1 Training error: Training accuracy: 3/10 2/10 4/10 7/10 8/10 6/10 training error = 1-accuracy (and vice versa) Training error: the average error over the training set Training accuracy: the average percent correct over the training set

  25. Recurse Terrain Unicycle- type Weather Go-For- Ride? Unicycle Trail Normal Rainy NO Normal Mountain Road Normal Sunny YES Trail Mountain Sunny YES YES: 4 NO: 0 YES: 2 NO: 4 Road Mountain Rainy YES Trail Normal Snowy NO Road Normal Rainy YES Road Mountain Snowy YES Trail Normal Sunny NO Road Normal Snowy NO Trail Mountain Snowy YES

  26. Recurse Unicycle Normal Mountain YES: 4 NO: 0 YES: 2 NO: 4 Terrain Unicycle- type Weather Go-For- Ride? Terrain Unicycle- type Weather Go-For- Ride? Trail Normal Rainy NO Trail Mountain Sunny YES Road Normal Sunny YES Road Mountain Rainy YES Trail Normal Snowy NO Road Mountain Snowy YES Road Normal Rainy YES Trail Mountain Snowy YES Trail Normal Sunny NO Road Normal Snowy NO

  27. Recurse Unicycle Normal Mountain YES: 4 NO: 0 Terrain Unicycle- type Weather Go-For- Ride? Trail Mountain Sunny YES What should we do? Road Mountain Rainy YES Road Mountain Snowy YES Trail Mountain Snowy YES

  28. Recurse Unicycle Normal Mountain YES: 4 NO: 0 Terrain Unicycle- type Weather Go-For- Ride? No need to examine other features since all examples have the same label. Trail Mountain Sunny YES Road Mountain Rainy YES Road Mountain Snowy YES Trail Mountain Snowy YES

  29. Recurse Unicycle Normal Mountain YES: 4 NO: 0 YES: 2 NO: 4 Terrain Unicycle- type Weather Go-For- Ride? Trail Normal Rainy NO Road Normal Sunny YES Trail Normal Snowy NO Road Normal Rainy YES Trail Normal Sunny NO Road Normal Snowy NO

  30. Recurse Unicycle Normal Mountain Still two features left we can split on YES: 4 NO: 0 YES: 2 NO: 4 Terrain Unicycle- type Weather Go-For- Ride? Trail Normal Rainy NO Road Normal Sunny YES Trail Normal Snowy NO Road Normal Rainy YES Trail Normal Sunny NO Road Normal Snowy NO

  31. Recurse Terrain Unicycle Trail Road Normal Mountain YES: 4 NO: 0 YES: 2 NO: 4 Terrain Unicycle- type Weather Go-For- Ride? Trail Normal Rainy NO Road Normal Sunny YES Trail Normal Snowy NO Road Normal Rainy YES Trail Normal Sunny NO Road Normal Snowy NO

  32. Recurse Terrain Unicycle Trail Road Normal Mountain YES: 2 NO: 1 YES: 0 NO: 3 YES: 4 NO: 0 YES: 2 NO: 4 Terrain Unicycle- type Weather Go-For- Ride? Trail Normal Rainy NO Road Normal Sunny YES Trail Normal Snowy NO Road Normal Rainy YES Trail Normal Sunny NO Road Normal Snowy NO

  33. Recurse Terrain Unicycle Trail Road Normal Mountain YES: 2 NO: 1 YES: 0 NO: 3 YES: 4 NO: 0 YES: 2 NO: 4 Terrain Unicycle- type Weather Go-For- Ride? Weather Trail Normal Rainy NO Sunny Rainy Snowy Road Normal Sunny YES Trail Normal Snowy NO YES: 1 NO: 1 YES: 0 NO: 2 YES: 1 NO: 1 Road Normal Rainy YES Trail Normal Sunny NO Road Normal Snowy NO

  34. Recurse Terrain Unicycle Trail Road Normal Mountain YES: 2 NO: 1 YES: 0 NO: 3 YES: 4 NO: 0 YES: 2 NO: 4 1/6 Terrain Unicycle- type Weather Go-For- Ride? Weather Trail Normal Rainy NO Sunny Rainy Snowy Road Normal Sunny YES Trail Normal Snowy NO YES: 1 NO: 1 YES: 0 NO: 2 YES: 1 NO: 1 Road Normal Rainy YES Trail Normal Sunny NO 2/6 Road Normal Snowy NO Which should we pick?

  35. Recurse Unicycle Normal Mountain Terrain YES: 4 NO: 0 Trail Road YES: 2 NO: 1 YES: 0 NO: 3 Terrain Unicycle- type Weather Go-For- Ride? Road Normal Sunny YES Road Normal Rainy YES Road Normal Snowy NO

  36. Recurse Unicycle Normal Mountain Terrain YES: 4 NO: 0 Trail Road Weather YES: 0 NO: 3 Sunny Rainy Snowy YES: 1 NO: 1 YES: 0 NO: 1 YES: 1 NO: 0

  37. Recurse Unicycle Terrain Unicycle- type Weather Go-For- Ride? Normal Mountain Trail Normal Rainy NO Terrain Road Normal Sunny YES YES: 4 NO: 0 Trail Trail Mountain Sunny YES Road Road Mountain Rainy YES Weather YES: 0 NO: 3 Trail Normal Snowy NO Sunny Rainy Road Normal Rainy YES Snowy Road Mountain Snowy YES YES: 1 NO: 0 YES: 0 NO: 1 YES: 1 NO: 0 Trail Normal Sunny NO Road Normal Snowy NO Trail Mountain Snowy YES Are we always guaranteed to get a training error of 0? Training error?

  38. Problematic data Terrain Unicycle- type Weather Go-For- Ride? Trail Normal Rainy NO Road Normal Sunny YES Trail Mountain Sunny YES Road Mountain Snowy NO Trail Normal Snowy NO Road Normal Rainy YES Road Mountain Snowy YES Trail Normal Sunny NO Road Normal Snowy NO Trail Mountain Snowy YES When can this happen?

  39. Recursive approach Base case: If all data belong to the same class, create a leaf node with that label OR all the data has the same feature values Do we always want to go all the way to the bottom?

  40. What would the tree look like for Terrain Unicycle- type Weather Go-For- Ride? Trail Mountain Rainy YES Trail Mountain Sunny YES Road Mountain Snowy YES Road Mountain Sunny YES Trail Normal Snowy NO Trail Normal Rainy NO Road Normal Snowy YES Road Normal Sunny NO Trail Normal Sunny NO

  41. What would the tree look like for Unicycle Terrain Unicycle- type Weather Go-For- Ride? Normal Mountain Trail Mountain Rainy YES Terrain YES Trail Mountain Sunny YES Trail Road Road Mountain Snowy YES NO Weather Road Mountain Sunny YES Trail Normal Snowy NO Sunny Rainy Snowy Trail Normal Rainy NO NO YES NO Road Normal Snowy YES Road Normal Sunny NO Trail Normal Sunny NO Is that what you would do?

  42. What would the tree look like for Unicycle Terrain Unicycle- type Weather Go-For- Ride? Normal Mountain Trail Mountain Rainy YES Terrain YES Trail Mountain Sunny YES Trail Road Road Mountain Snowy YES NO Weather Road Mountain Sunny YES Trail Normal Snowy NO Sunny Rainy Snowy Trail Normal Rainy NO NO YES NO Road Normal Snowy YES Road Normal Sunny NO Maybe Trail Normal Sunny NO Unicycle Normal Mountain YES NO

  43. What would the tree look like for Unicycle Terrain Unicycle- type Weather Go-For- Ride? Normal Mountain Trail Mountain Rainy YES Terrain YES Trail Mountain Sunny YES Trail Road Road Mountain Snowy YES NO Weather Road Mountain Sunny YES Trail Normal Snowy NO Sunny Rainy Snowy Trail Normal Rainy NO NO YES NO Road Normal Snowy YES Road Normal Sunny NO Trail Normal Sunny NO An aside, how did we decide to pick the label for normal->road->rainy?

  44. What would the tree look like for Terrain Unicycle-type Weather Jacket ML grade Go-For-Ride? Trail Mountain Rainy Heavy D YES Trail Mountain Sunny Light C- YES Road Mountain Snowy Light B YES Road Mountain Sunny Heavy A YES Mountain YES Trail Normal Snowy Light D+ NO Trail Normal Rainy Heavy B- NO Road Normal Snowy Heavy C+ YES Road Normal Sunny Light A- NO Trail Normal Sunny Heavy B+ NO Trail Normal Snowy Light F NO Normal NO Trail Normal Rainy Light C YES

  45. Overfitting Terrain Unicycle- type Weather Go-For- Ride? Unicycle Normal Mountain Trail Mountain Rainy YES Trail Mountain Sunny YES YES NO Road Mountain Snowy YES Road Mountain Sunny YES Overfitting occurs when we bias our model too much towards the training data Trail Normal Snowy NO Trail Normal Rainy NO Road Normal Snowy YES Road Normal Sunny NO Our goal is to learn a general model that will work on the training data as well as other data (i.e. test data) Trail Normal Sunny NO

  46. Overfitting Our decision tree learning procedure always decreases training error Is that what we want?

  47. Test set error! Machine learning is about predicting the future based on the past. -- Hal Daume III past future Training Data Testing Data model/ predictor model/ predictor

  48. Overfitting Even though the training error is decreasing, the testing error can go up!

  49. Overfitting Unicycle Terrain Unicycle- type Weather Go-For- Ride? Normal Mountain Trail Mountain Rainy YES Terrain YES Trail Mountain Sunny YES Trail Road Road Mountain Snowy YES NO Weather Road Mountain Sunny YES Trail Normal Snowy NO Sunny Rainy Snowy Trail Normal Rainy NO NO YES NO Road Normal Snowy YES Road Normal Sunny NO Trail Normal Sunny NO How do we prevent overfitting?

  50. Preventing overfitting Base case: - If all data belong to the same class, create a leaf node with that label - OR all the data has the same feature values - OR We ve reached a particular depth in the tree - ? One idea: stop building the tree early

Related


Monumental Trees of Italy - A Natural Legacy of Grandeur and Cultural Significance

Monumental Trees of Italy - A Natural Legacy of Grandeur and Cultural Significance

michal
Decision Trees in Machine Learning

Decision Trees in Machine Learning

delilah
Exploring Trees Data Structures Using C - Second Edition

Exploring Trees Data Structures Using C - Second Edition

araminta
Decision Trees in Machine Learning with AIMA and WEKA

Decision Trees in Machine Learning with AIMA and WEKA

lupita
Decision Trees: A Visual Guide

Decision Trees: A Visual Guide

alannah
Height-Balanced Binary Trees and AVL Trees

Height-Balanced Binary Trees and AVL Trees

anava
Balanced Search Trees and Red-Black Trees

Balanced Search Trees and Red-Black Trees

gfaus
Spanning Trees and Minimum Spanning Trees

Spanning Trees and Minimum Spanning Trees

heda_3
Classification and Regression Trees

Classification and Regression Trees

isa_sch
Unrooted Trees in Phylogenetics

Unrooted Trees in Phylogenetics

jets_849
Trees in Discrete Structures

Trees in Discrete Structures

rosenfeld_d
Data Structure Concepts: AVL Trees and B-Trees

Data Structure Concepts: AVL Trees and B-Trees

jac_bu
AVL Trees in Data Structures

AVL Trees in Data Structures

nicolosi_m
AVL Trees: Balanced Search Trees for Efficient Operations

AVL Trees: Balanced Search Trees for Efficient Operations

brey148
Decision Trees in Classification

Decision Trees in Classification

casavant_n
Decision Trees in Machine Learning

Decision Trees in Machine Learning

jknap
Graphs and Trees Summary: Tree Definitions and Rooted Trees Explained

Graphs and Trees Summary: Tree Definitions and Rooted Trees Explained

antonacci_j
Scalability of Computing Triplet and Quartet Distances in Phylogenetic Trees

Scalability of Computing Triplet and Quartet Distances in Phylogenetic Trees

bazesi
Introduction to Classification Trees: CART Algorithm Overview

Introduction to Classification Trees: CART Algorithm Overview

rho_gar
Decision Trees

Decision Trees

tannehill_k
Rooted Trees in Discrete Structures

Rooted Trees in Discrete Structures

abendroth_k
Graphs and Trees: Understanding Relationships in Graph Theory

Graphs and Trees: Understanding Relationships in Graph Theory

ethington_d

More Related Content