Smis | Course Paper

Data Mining

Classification: Basic Concepts, Decision

Trees, and Model Evaluation

Lecture Notes for Chapter 4

Introduction to Data Mining

by

Tan, Steinbach, Kumar

Classification: Definition

OGiven a collection of records (training set )

–Each record contains a set of attributes, one of the

attributes is the class.

OFind a model for class attribute as a function

of the values of other attributes.

OGoal: previously unseen records should be

assigned a class as accurately as possible.

–A test set is used to determine the accuracy of the

model. Usually, the given data set is divided into

training and test sets, with training set used to build

the model and test set used to validate it.

Illustrating Classification Task

Apply

Model

Induction

Deduction

Learn

Model

Tid Attrib1 Attrib2 Attrib3 Class

1 Yes Large 125K No

2 No Medium 100K No

3 No Small 70K No

4 Yes Medium 120K No

5 No Large 95K Yes

6 No Medium 60K No

7 Yes Large 220K No

8 No Small 85K Yes

9 No Medium 75K No

10 No Small 90K Yes

10

Tid Attrib1 Attrib2 Attrib3 Class

11 No Small 55K ?

12 Yes Medium 80K ?

13 Yes Large 110K ?

14 No Small 95K ?

15 No Large 67K ?

10

Test Set

Learning

algorithm

Training Set

Examples of Classification Task

OPredicting tumor cells as benign or malignant

OClassifying credit card transactions

as legitimate or fraudulent

OClassifying secondary structures of protein

as alpha-helix, beta-sheet, or random

coil

OCategorizing news stories as finance,

weather, entertainment, sports, etc

Classification Techniques

ODecision Tree based Methods

ORule-based Methods

OMemory based reasoning

ONeural Networks

ONaïve Bayes and Bayesian Belief Networks

OSupport Vector Machines

Example of a Decision Tree

Tid Refund Marital

Status

Taxable

Income Cheat

1Yes Single 125K No

2No Married 100K No

3No Single 70K No

4Yes Married 120K No

5No Divorced 95K Yes

6No Married 60K No

7Yes Divorced 220K No

8No Single 85K Yes

9No Married 75K No

10 No Single 90K Yes

10

categorical

continuous

class

Refund

MarSt

TaxInc

YES

NO

Yes No

Married

Single, Divorced

< 80K > 80K

Splitting Attributes

Training Data Model: Decision Tree

Another Example of Decision Tree

Tid Refund Marital

Status

Taxable

Income Cheat

1Yes Single 125K No

2No Married 100K No

3No Single 70K No

4Yes Married 120K No

5No Divorced 95K Yes

6No Married 60K No

7Yes Divorced 220K No

8No Single 85K Yes

9No Married 75K No

10 No Single 90K Yes

10

categorical

continuous

class

MarSt

Refund

TaxInc

YES

NO

Yes No

Married

Single,

Divorced

< 80K > 80K

There could be more than one tree that

fits the same data!

Decision Tree Classification Task

Apply

Model

Induction

Deduction

Learn

Model

Tid Attrib1 Attrib2 Attrib3 Class

1 Yes Large 125K No

2 No Medium 100K No

3 No Small 70K No

4 Yes Medium 120K No

5 No Large 95K Yes

6 No Medium 60K No

7 Yes Large 220K No

8 No Small 85K Yes

9 No Medium 75K No

10 No Small 90K Yes

10

Tid Attrib1 Attrib2 Attrib3 Class

11 No Small 55K ?

12 Yes Medium 80K ?

13 Yes Large 110K ?

14 No Small 95K ?

15 No Large 67K ?

10

Test Set

Tree

Induction

algorithm

Training Set

Decision

Tree

Apply Model to Test Data

Refund

MarSt

TaxInc

YES

NO

Yes No

Married

Single, Divorced

< 80K > 80K

Refund Marital

Status

Taxable

Income Cheat

No Married 80K ?

10

Test Data

Start from the root of tree.

Apply Model to Test Data

Refund

MarSt

TaxInc

YES

NO

Yes No

Married

Single, Divorced

< 80K > 80K

Refund Marital

Status

Taxable

Income Cheat

No Married 80K ?

10

Test Data

Apply Model to Test Data

Refund

MarSt

TaxInc

YES

NO

Yes No

Married

Single, Divorced

< 80K > 80K

Refund Marital

Status

Taxable

Income Cheat

No Married 80K ?

10

Test Data

Apply Model to Test Data

Refund

MarSt

TaxInc

YES

NO

Yes No

Married

Single, Divorced

< 80K > 80K

Refund Marital

Status

Taxable

Income Cheat

No Married 80K ?

10

Test Data

Apply Model to Test Data

Refund

MarSt

TaxInc

YES

NO

Yes No

Married

Single, Divorced

< 80K > 80K

Refund Marital

Status

Taxable

Income Cheat

No Married 80K ?

10

Test Data

Apply Model to Test Data

Refund

MarSt

TaxInc

YES

NO

Yes No

Married

Single, Divorced

< 80K > 80K

Refund Marital

Status

Taxable

Income Cheat

No Married 80K ?

10

Test Data

Assign Cheat to “No”

Decision Tree Classification Task

Apply

Model

Induction

Deduction

Learn

Model

Tid Attrib1 Attrib2 Attrib3 Class

1 Yes Large 125K No

2 No Medium 100K No

3 No Small 70K No

4 Yes Medium 120K No

5 No Large 95K Yes

6 No Medium 60K No

7 Yes Large 220K No

8 No Small 85K Yes

9 No Medium 75K No

10 No Small 90K Yes

10

Tid Attrib1 Attrib2 Attrib3 Class

11 No Small 55K ?

12 Yes Medium 80K ?

13 Yes Large 110K ?

14 No Small 95K ?

15 No Large 67K ?

10

Test Set

Tree

Induction

algorithm

Training Set

Decision

Tree

Decision Tree Induction

OMany Algorithms:

–Hunt’s Algorithm (one of the earliest)

–CART

–ID3, C4.5

–SLIQ,SPRINT

General Structure of Hunt’s Algorithm

OLet Dtbe the set of training records

that reach a node t

OGeneral Procedure:

–If Dtcontains records that

belong the same class yt, then t

is a leaf node labeled as yt

–If Dtis an empty set, then t is a

leaf node labeled by the default

class, yd

–If Dtcontains records that

belong to more than one class,

use an attribute test to split the

data into smaller subsets.

Recursively apply the

procedure to each subset.

Tid Refund Marital

Status

Taxable

Income Cheat

1 Yes Single 125K No

2 No Married 100K No

3 No Single 70K No

4 Yes Married 120K No

5 No Divorced 95K Yes

6 No Married 60K No

7 Yes Divorced 220K No

8 No Single 85K Yes

9 No Married 75K No

10 No Single 90K Yes

10

Dt

?

Hunt’s Algorithm

Don’t

Cheat

Refund

Don’t

Cheat

Don’t

Cheat

Yes No

Refund

Don’t

Cheat

Yes No

Marital

Status

Don’t

Cheat

Single,

Divorced Married

Taxable

Income

Don’t

Cheat

< 80K >= 80K

Refund

Don’t

Cheat

Yes No

Marital

Status

Don’t

Cheat

Single,

Divorced Married

Tid Refund Marital

Status

Taxable

Income Cheat

1Yes Single 125K No

2No Married 100K No

3No Single 70K No

4Yes Married 120K No

5No Divorced 95K Yes

6No Married 60K No

7Yes Divorced 220K No

8No Single 85K Yes

9No Married 75K No

10 No Single 90K Yes

10

Tree Induction

OGreedy strategy.

–Split the records based on an attribute test

that optimizes certain criterion.

OIssues

–Determine how to split the records

How to specify the attribute test condition?

How to determine the best split?

–Determine when to stop splitting

Tree Induction

OGreedy strategy.

–Split the records based on an attribute test

that optimizes certain criterion.

OIssues

–Determine how to split the records

How to specify the attribute test condition?

How to determine the best split?

–Determine when to stop splitting

How to Specify Test Condition?

ODepends on attribute types

–Nominal

–Ordinal

–Continuous

ODepends on number of ways to split

–2-way split

–Multi-way split

Splitting Based on Nominal Attributes

OMulti-way split: Use as many partitions as distinct

values.

OBinary split: Divides values into two subsets.

Need to find optimal partitioning.

CarType

Family

Sports

Luxury

CarType

{Family,

Luxury} {Sports}

CarType

{Sports,

Luxury} {Family} OR

OMulti-way split: Use as many partitions as distinct

values.

OBinary split: Divides values into two subsets.

Need to find optimal partitioning.

OWhat about this split?

Splitting Based on Ordinal Attributes

Size

Small

Medium

Large

Size

{Medium,

Large} {Small}

Size

{Small,

Medium} {Large} OR

Size

{Small,