Decision Tree Gear Up!

CS200 | Spring 2023

What We’ll Be Covering

1. Intro to the assignment
2. Decision Trees
3. Architecture
4. Building the Tree
5. Design Check
6. Roadmap

Learning objectives

• Select and justify an appropriate data structure
• Create a class hierarchy that makes proper use of interfaces and abstract classes
• Develop examples and tests
• Write programs that behave as expected based on a provided collection of test cases (i.e. works with the autograder!)
• Identify potential societal impacts of a program

​

Intro

The Assignment

You will be generating a decision tree that can predict output values from input values.

​

But what is a decision tree?

squash

orange

high carb

high fiber

likeToEat

true

decision tree

?

?

?

?

?

?

The Assignment

A decision tree is a basic concept used in machine learning, using a dataset to determine future decisions.

​

What does it look like?

squash

orange

high carb

high fiber

likeToEat

true

decision tree

?

?

?

?

?

?

Decision Trees

An Example Dataset!

lowCarb

highFiber

likeToEat

color

name

spinach

kale

sweet potato

peas

eggplant

carrot

“green”

“green”

“orange”

“green”

“purple”

“orange”

true

true

true

false

true

true

false

true

true

true

true

false

false

true

true

false

true

false

An Example Dataset!

lowCarb

highFiber

likeToEat

color

name

spinach

kale

sweet potato

peas

eggplant

carrot

“green”

“green”

“orange”

“green”

“purple”

“orange”

true

true

true

false

true

true

false

true

true

true

true

false

false

true

true

false

true

false

An Example Decision Tree!

color

highFiber

lowCarb

highFiber

false

false

false

true

true

true

orange

purple

green

false

false

true

true

true

false

An Example Decision Tree!

color

Check the color attribute of the vegetable

An Example Decision Tree!

color

highFiber

lowCarb

true

If the color is “orange”, then check the highFiber attribute

If the color is “green”, then check the lowCarb attribute

If the color is “green”, then check the lowCarb attribute

If the color is “purple”, then this tree would return true!

orange

purple

green

An Example Decision Tree!

color

highFiber

lowCarb

highFiber

false

false

true

true

If highFiber is true, then this tree would return true!

If highFiber is false, then this tree would return false!

If lowCarb is false, then this tree would return false!

If lowCarb is true, then check the highFiber attribute

orange

purple

green

false

false

true

true

An Example Decision Tree!

color

highFiber

lowCarb

highFiber

false

false

false

true

true

true

orange

purple

green

false

false

true

true

true

false

If highFiber is true, then this tree would return true! Otherwise, this tree would return false!

Architecture

The Architecture Of Your Program!

Decision Tree (DecisionLeaf, ValueEdge, AttributeNode)

• These are the classes that make up your decision tree
• What data/information these classes will need to hold?
• What are the possible classes you might need?

Dataset

TreeGenerator

• These are the classes that define your data
• What’s the difference between a datum and a dataset?
• What do these classes need to implement?
• What are some useful functions these classes will have?

• This is the class that will generate your decision tree
• What fields and methods does this class need to have?
• What fields/methods in other classes will this use?
• What’s the difference between this and the other tree classes?

A lot of this part of the project is up to you!

Building the Tree

lowCarb

highFiber

likeToEat

color

name

spinach

kale

sweet potato

peas

eggplant

carrot

“green”

“green”

“orange”

“green”

“purple”

“orange”

true

true

true

false

true

true

false

true

true

true

true

false

false

true

true

false

true

false

Let’s Look At The Data!

[spinach, kale, sweet potato, peas, eggplant, carrot]

Constructing a Tree!

lowCarb

highFiber

likeToEat

color

name

spinach

kale

sweet potato

peas

eggplant

carrot

“green”

“green”

“orange”

“green”

“purple”

“orange”

true

true

true

false

true

true

false

true

true

true

true

false

false

true

true

false

true

false

Let’s Look At The Data!

true

false

lowCarb

[spinach, kale, sweet potato, eggplant, carrot]

[peas]

Constructing a Tree!

Let’s Look At The Data!

lowCarb

highFiber

likeToEat

color

name

spinach

kale

sweet potato

peas

eggplant

carrot

“green”

“green”

“orange”

“green”

“purple”

“orange”

true

true

true

false

true

true

false

true

true

true

true

false

false

true

true

false

true

false

true

false

lowCarb

false

color

[sweet potato, carrot]

[spinach, kale]

[eggplant]

Constructing a Tree!

Let’s Look At The Data!

lowCarb

highFiber

likeToEat

color

name

spinach

kale

sweet potato

peas

eggplant

carrot

“green”

“green”

“orange”

“green”

“purple”

“orange”

true

true

true

false

true

true

false

true

true

true

true

false

false

true

true

false

true

false

true

false

lowCarb

false

color

[sweet potato]

false

false

true

true

true

highFiber

highFiber

[carrot]

[spinach]

[kale]

Constructing a Tree!

true

false

lowCarb

false

color

false

false

true

false

false

true

true

true

highFiber

highFiber

true

Constructing a Tree!

Design Check

Design Check Requirements

1. Complete the design check conceptual questions on Gradescope!
2. Complete the design check tasks and submit it on Gradescope
3. Make sure you are ready to discuss your answers with your design check TA!

​

Finally, Check the handout for more info!

Roadmap

Getting Started

​

1. Prepare for your design check
2. Write tests
3. Create and implement methods for your data classes
4. Create and implement classes/methods for your tree’s structure
5. Make sure you have a solid grasp on how your tree is supposed to function and how all your classes interact with each other
6. Create and implement your tree generation class
7. Test your implementation!

Questions?