Homework 1 - Programming Solutions

Note: The output of ID3 varies depending whether you use < or <= to check for the best attribute. Therefore, there are two correct solutions for each data set.

mushroom data set

If < was used:	If <= was used:
LEVEL1: ODOR BRANCH: almond LEVEL2: edible (20) BRANCH: anise LEVEL2: edible (23) BRANCH: none LEVEL2: SPORE-PRINT-COLOR BRANCH: black LEVEL3: edible (70) BRANCH: brown LEVEL3: edible (61) BRANCH: chocolate LEVEL3: edible (0) BRANCH: white LEVEL3: CAP-SHAPE BRANCH: convex LEVEL4: edible (2) BRANCH: flat LEVEL4: edible (6) BRANCH: bell LEVEL4: edible (0) BRANCH: knobbed LEVEL4: poisonous (1) BRANCH: sunken LEVEL4: edible (0) BRANCH: green LEVEL3: poisonous (6) BRANCH: purple LEVEL3: edible (0) BRANCH: foul LEVEL2: poisonous (82) BRANCH: pungent LEVEL2: poisonous (15) BRANCH: creosote LEVEL2: poisonous (11) BRANCH: musty LEVEL2: poisonous (3) ----------------------- Training accuracy: 100% Testing accuracy: 99%	LEVEL1: ODOR BRANCH: almond LEVEL2: edible (20) BRANCH: anise LEVEL2: edible (23) BRANCH: none LEVEL2: SPORE-PRINT-COLOR BRANCH: black LEVEL3: edible (70) BRANCH: brown LEVEL3: edible (61) BRANCH: chocolate LEVEL3: edible (0) BRANCH: white LEVEL3: POPULATION BRANCH: scattered LEVEL4: edible (0) BRANCH: abundant LEVEL4: edible (0) BRANCH: several LEVEL4: edible (5) BRANCH: solitary LEVEL4: edible (3) BRANCH: clustered LEVEL4: poisonous (1) BRANCH: numerous LEVEL4: edible (0) BRANCH: green LEVEL3: poisonous (6) BRANCH: purple LEVEL3: edible (0) BRANCH: foul LEVEL2: poisonous (82) BRANCH: pungent LEVEL2: poisonous (15) BRANCH: creosote LEVEL2: poisonous (11) BRANCH: musty LEVEL2: poisonous (3) ----------------------- Training accuracy: 100% Testing accuracy: 100%

If < was used:

If <= was used:

LEVEL1: ODOR

BRANCH: almond
LEVEL2: edible (20)
BRANCH: anise
LEVEL2: edible (23)
BRANCH: none
LEVEL2: SPORE-PRINT-COLOR
BRANCH: black
LEVEL3: edible (70)
BRANCH: brown
LEVEL3: edible (61)
BRANCH: chocolate
LEVEL3: edible (0)
BRANCH: white
LEVEL3: CAP-SHAPE
BRANCH: convex
LEVEL4: edible (2)
BRANCH: flat
LEVEL4: edible (6)
BRANCH: bell
LEVEL4: edible (0)
BRANCH: knobbed
LEVEL4: poisonous (1)
BRANCH: sunken
LEVEL4: edible (0)

BRANCH: green
LEVEL3: poisonous (6)
BRANCH: purple
LEVEL3: edible (0)

BRANCH: foul
LEVEL2: poisonous (82)
BRANCH: pungent
LEVEL2: poisonous (15)
BRANCH: creosote
LEVEL2: poisonous (11)
BRANCH: musty
LEVEL2: poisonous (3)
-----------------------
Training accuracy: 100%
Testing accuracy: 99%

LEVEL1: ODOR
BRANCH: almond
LEVEL2: edible (20)
BRANCH: anise
LEVEL2: edible (23)
BRANCH: none
LEVEL2: SPORE-PRINT-COLOR
BRANCH: black
LEVEL3: edible (70)
BRANCH: brown
LEVEL3: edible (61)
BRANCH: chocolate
LEVEL3: edible (0)
BRANCH: white
LEVEL3: POPULATION
BRANCH: scattered
LEVEL4: edible (0)
BRANCH: abundant
LEVEL4: edible (0)
BRANCH: several
LEVEL4: edible (5)
BRANCH: solitary
LEVEL4: edible (3)
BRANCH: clustered
LEVEL4: poisonous (1)
BRANCH: numerous
LEVEL4: edible (0)

BRANCH: green
LEVEL3: poisonous (6)
BRANCH: purple
LEVEL3: edible (0)

BRANCH: foul
LEVEL2: poisonous (82)
BRANCH: pungent
LEVEL2: poisonous (15)
BRANCH: creosote
LEVEL2: poisonous (11)
BRANCH: musty
LEVEL2: poisonous (3)
-----------------------
Training accuracy: 100%
Testing accuracy: 100%

tictactoe data set

If < was used:	If <= was used:
LEVEL1: middle-middle BRANCH: b LEVEL2: top-left BRANCH: x LEVEL3: bottom-left BRANCH: x LEVEL4: positive (14) BRANCH: o LEVEL4: top-right BRANCH: b LEVEL4: positive (2) BRANCH: o LEVEL3: middle-right BRANCH: b LEVEL4: positive (2) BRANCH: x LEVEL4: top-right BRANCH: o LEVEL4: bottom-left BRANCH: b LEVEL3: top-middle BRANCH: o LEVEL4: positive (1) BRANCH: x LEVEL4: negative (1) BRANCH: b LEVEL4: positive (0) BRANCH: x LEVEL2: top-right BRANCH: o LEVEL3: bottom-left BRANCH: x LEVEL4: bottom-right BRANCH: o LEVEL4: bottom-right BRANCH: b LEVEL4: middle-right BRANCH: x LEVEL3: bottom-left BRANCH: x LEVEL4: positive (16) BRANCH: o LEVEL4: bottom-middle BRANCH: b LEVEL4: positive (7) BRANCH: b LEVEL3: positive (16) BRANCH: o LEVEL2: middle-left BRANCH: x LEVEL3: bottom-left BRANCH: x LEVEL4: top-left BRANCH: o LEVEL4: top-left BRANCH: b LEVEL4: bottom-middle BRANCH: o LEVEL3: middle-right BRANCH: b LEVEL4: bottom-middle BRANCH: x LEVEL4: bottom-right BRANCH: o LEVEL4: negative (6) BRANCH: b LEVEL3: bottom-middle BRANCH: b LEVEL4: positive (6) BRANCH: x LEVEL4: middle-right BRANCH: o LEVEL4: top-left ----------------------- Training accuracy: 100% Testing accuracy: 80%	LEVEL1: middle-middle BRANCH: b LEVEL2: top-left BRANCH: x LEVEL3: bottom-middle BRANCH: b LEVEL4: positive (8) BRANCH: x LEVEL4: bottom-left BRANCH: o LEVEL4: positive (8) BRANCH: o LEVEL3: middle-right BRANCH: b LEVEL4: positive (2) BRANCH: x LEVEL4: top-right BRANCH: o LEVEL4: bottom-left BRANCH: b LEVEL3: bottom-right BRANCH: b LEVEL4: positive (0) BRANCH: x LEVEL4: positive (1) BRANCH: o LEVEL4: negative (1) BRANCH: x LEVEL2: top-right BRANCH: o LEVEL3: bottom-left BRANCH: x LEVEL4: bottom-right BRANCH: o LEVEL4: bottom-right BRANCH: b LEVEL4: middle-right BRANCH: x LEVEL3: bottom-left BRANCH: x LEVEL4: positive (16) BRANCH: o LEVEL4: bottom-middle BRANCH: b LEVEL4: positive (7) BRANCH: b LEVEL3: positive (16) BRANCH: o LEVEL2: middle-left BRANCH: x LEVEL3: bottom-left BRANCH: x LEVEL4: top-left BRANCH: o LEVEL4: top-left BRANCH: b LEVEL4: bottom-right BRANCH: o LEVEL3: middle-right BRANCH: b LEVEL4: bottom-middle BRANCH: x LEVEL4: bottom-right BRANCH: o LEVEL4: negative (6) BRANCH: b LEVEL3: bottom-middle BRANCH: b LEVEL4: positive (6) BRANCH: x LEVEL4: bottom-left BRANCH: o LEVEL4: bottom-right -------------------------- Training accuracy: 100% Testing accuracy: 76%

If < was used:

If <= was used:

LEVEL1:  middle-middle

BRANCH: b
LEVEL2:  top-left
BRANCH: x
LEVEL3:  bottom-left
BRANCH: x
LEVEL4: positive (14)
BRANCH: o
LEVEL4:  top-right
BRANCH: b
LEVEL4: positive (2)

BRANCH: o
LEVEL3:  middle-right
BRANCH: b
LEVEL4: positive (2)
BRANCH: x
LEVEL4:  top-right
BRANCH: o
LEVEL4:  bottom-left

BRANCH: b
LEVEL3:  top-middle
BRANCH: o
LEVEL4: positive (1)
BRANCH: x
LEVEL4: negative (1)
BRANCH: b
LEVEL4: positive (0)

BRANCH: x
LEVEL2:  top-right
BRANCH: o
LEVEL3:  bottom-left
BRANCH: x
LEVEL4:  bottom-right
BRANCH: o
LEVEL4:  bottom-right
BRANCH: b
LEVEL4:  middle-right

BRANCH: x
LEVEL3:  bottom-left
BRANCH: x
LEVEL4: positive (16)
BRANCH: o
LEVEL4:  bottom-middle
BRANCH: b
LEVEL4: positive (7)

BRANCH: b
LEVEL3: positive (16)

BRANCH: o
LEVEL2:  middle-left
BRANCH: x
LEVEL3:  bottom-left
BRANCH: x
LEVEL4:  top-left
BRANCH: o
LEVEL4:  top-left
BRANCH: b
LEVEL4:  bottom-middle

BRANCH: o
LEVEL3:  middle-right
BRANCH: b
LEVEL4:  bottom-middle
BRANCH: x
LEVEL4:  bottom-right
BRANCH: o
LEVEL4: negative (6)

BRANCH: b
LEVEL3:  bottom-middle
BRANCH: b
LEVEL4: positive (6)
BRANCH: x
LEVEL4:  middle-right
BRANCH: o
LEVEL4:  top-left
-----------------------
Training accuracy: 100%
Testing accuracy: 80%

LEVEL1: middle-middle

BRANCH: b
LEVEL2: top-left
BRANCH: x
LEVEL3: bottom-middle
BRANCH: b
LEVEL4: positive  (8)
BRANCH: x
LEVEL4: bottom-left
BRANCH: o
LEVEL4: positive  (8)

BRANCH: o
LEVEL3: middle-right
BRANCH: b
LEVEL4: positive  (2)
BRANCH: x
LEVEL4: top-right
BRANCH: o
LEVEL4: bottom-left

BRANCH: b
LEVEL3: bottom-right
BRANCH: b
LEVEL4: positive  (0)
BRANCH: x
LEVEL4: positive  (1)
BRANCH: o
LEVEL4: negative  (1)

BRANCH: x
LEVEL2: top-right
BRANCH: o
LEVEL3: bottom-left
BRANCH: x
LEVEL4: bottom-right
BRANCH: o
LEVEL4: bottom-right
BRANCH: b
LEVEL4: middle-right

BRANCH: x
LEVEL3: bottom-left
BRANCH: x
LEVEL4: positive  (16)
BRANCH: o
LEVEL4: bottom-middle
BRANCH: b
LEVEL4: positive  (7)

BRANCH: b
LEVEL3: positive  (16)

BRANCH: o
LEVEL2: middle-left
BRANCH: x
LEVEL3: bottom-left
BRANCH: x
LEVEL4: top-left
BRANCH: o
LEVEL4: top-left
BRANCH: b
LEVEL4: bottom-right

BRANCH: o
LEVEL3: middle-right
BRANCH: b
LEVEL4: bottom-middle
BRANCH: x
LEVEL4: bottom-right
BRANCH: o
LEVEL4: negative  (6)

BRANCH: b
LEVEL3: bottom-middle
BRANCH: b
LEVEL4: positive  (6)
BRANCH: x
LEVEL4: bottom-left
BRANCH: o
LEVEL4: bottom-right
--------------------------
Training accuracy:  100%
Testing accuracy:  76%

Last modified: Wed Mar 15 10:27:31 2000