Data Mining Project

(C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002

YES

YES

NO

NO

NO

NO

NO

NO

Yes

No

{Married}

{Single,

Divorced}

< 80K

> 80K

Taxable

Income

Marital

Status

Refund

Classification Rules

(Refund=Yes) ==> No

(Refund=No, Marital Status={Single,Divorced},

Taxable Income<80K) ==> No

(Refund=No, Marital Status={Single,Divorced},

Taxable Income>80K) ==> Yes

(Refund=No, Marital Status={Married}) ==> No

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

Singl

e

90K

Yes

10

NameGive BirthLay EggsCan FlyLive in WaterHave LegsClass

humanyesnononoyesmammals

pythonnoyesnononoreptiles

salmonnoyesnoyesnofishes

whaleyesnonoyesnomammals

frognoyesnosometimesyesamphibians

komodonoyesnonoyesreptiles

batyesnoyesnoyesmammals

pigeonnoyesyesnoyesbirds

catyesnononoyesmammals

leopard sharkyesnonoyesnofishes

turtlenoyesnosometimesyesreptiles

penguinnoyesnosometimesyesbirds

porcupineyesnononoyesmammals

eelnoyesnoyesnofishes

salamandernoyesnosometimesyesamphibians

gila monsternoyesnonoyesreptiles

platypusnoyesnonoyesmammals

owlnoyesyesnoyesbirds

dolphinyesnonoyesnomammals

eaglenoyesyesnoyesbirds

Give

Birth?

Live In

Water?

Can

Fly?

Mammals

Fishes

Amphibians

Birds

Reptiles

Yes

No

Yes

Sometimes

No

Yes

No

Name

Blood Type

Give Birth

Can Fly

Live in Water

Class

lemur

warm

yes

no

no

?

turtle

cold

no

no

sometimes

?

dogfish shark

cold

yes

no

yes

?

Atr1

……...

AtrN

Class

A

B

B

C

A

C

B

Set of Stored Cases

k

n

n

c

+

+

=

1

(ii) Step 1

(iii) Step 2

R1

(iv) Step 3

R1

R2

PREDICTED CLASS

AmphibiansFishesReptilesBirdsMammals

ACTUALAmphibians00002

CLASSFishes03000

Reptiles00301

Birds00121

Mammals02104

PREDICTED CLASS

AmphibiansFishesReptilesBirdsMammals

ACTUALAmphibians20000

CLASSFishes02001

Reptiles10300

Birds10030

Mammals00106

Status =

Single

Status =

Divorced

Status =

Married

Income

> 80K

...

Yes: 3

No: 4

{ }

Yes: 0

No: 3

Refund=

No

Yes: 3

No: 4

Yes: 2

No: 1

Yes: 1

No: 0

Yes: 3

No: 1

(a) General-to-specific

Name

Blood Type

Give Birth

Can Fly

Live in Water

Class

turtle

cold

no

no

sometimes

?

Tid Refund Marital

Status

Taxable

Income

Class

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

k

n

kp

n

c

+

+

=

Name

Blood Type

Give Birth

Can Fly

Live in Water

Class

human

warm

yes

no

no

mammals

python

cold

no

no

no

reptiles

salmon

cold

no

no

yes

fishes

whale

warm

yes

no

yes

mammals

frog

cold

no

no

sometimes

amphibians

komodo

cold

no

no

no

reptiles

bat

warm

yes

yes

no

mammals

pigeon

warm

no

yes

no

birds

cat

warm

yes

no

no

mammals

leopard shark

cold

yes

no

yes

fishes

turtle

cold

no

no

sometimes

reptiles

penguin

warm

no

no

sometimes

birds

porcupine

warm

yes

no

no

mammals

eel

cold

no

no

yes

fishes

salamander

cold

no

no

sometimes

amphibians

gila monster

cold

no

no

no

reptiles

platypus

warm

no

no

no

mammals

owl

warm

no

yes

no

birds

dolphin

warm

yes

no

yes

mammals

eagle

warm

no

yes

no

birds

Name

Blood Type

Give Birth

Can Fly

Live in Water

Class

hawk

warm

no

yes

no

?

grizzly bear

warm

yes

no

no

?

Refund=No,

Status=Single,

Income=85K

(Class=Yes)

Refund=No,

Status=Single,

Income=90K

(Class=Yes)

Refund=No,

Status = Single

(Class = Yes)

(b) Specific-to-general

Rule-based Ordering

(Refund=Yes) ==> No

(Refund=No, Marital Status={Single,Divorced},

Taxable Income<80K) ==> No

(Refund=No, Marital Status={Single,Divorced},

Taxable Income>80K) ==> Yes

(Refund=No, Marital Status={Married}) ==> No

Class-based Ordering

(Refund=Yes) ==> No

(Refund=No, Marital Status={Single,Divorced},

Taxable Income<80K) ==> No

(Refund=No, Marital Status={Married}) ==> No

(Refund=No, Marital Status={Single,Divorced},

Taxable Income>80K) ==> Yes

(i) Original Data

n

n

c

=

class = +

class = -

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

-

-

-

-

--

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

+

+

+

+

+

+

+

R1

R3R2

+

+

Rule Set

r1: (P=No,Q=No) ==> -

r2: (P=No,Q=Yes) ==> +

r3: (P=Yes,R=No) ==> +

r4: (P=Yes,R=Yes,Q=No) ==> -

r5: (P=Yes,R=Yes,Q=Yes) ==> +

P

QR

Q

-++

-+

NoNo

No

Yes

Yes

Yes

NoYes

Atr1

……...

AtrN

Unseen Case

Unknown record

X

X

X

(a) 1-nearest neighbor

(b) 2-nearest neighbor

(c) 3-nearest neighbor

å

-

=

i

i

i

q

p

q

p

d

2

)

(

)

,

(

X

å

-

=

i

i

i

n

n

n

n

V

V

d

2

2

1

1

2

1

)

,

(

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

å

=

=

D

d

i

i

i

Y

X

Y

X

d

w

w

Y

X

1

2

)

,

(

)

,

(

Tid Refund Marital

Status

Taxable

Income

Cheat

X Yes Single 125K

No

Y No Married 100K

No

10

correctly

predicts

X

times

of

Number

prediction

for

used

is

X

times

of

Number

=

X

w

)

(

)

(

)

|

(

)

|

(

A

P

C

P

C

A

P

A

C

P

=

)

(

)

,

(

)

|

(

)

(

)

,

(

)

|

(

C

P

C

A

P

C

A

P

A

P

C

A

P

A

C

P

=

=

0002

.

0

20

/

1

50000

/

1

5

.

0

)

(

)

(

)

|

(

)

|

(

=

´

=

=

S

P

M

P

M

S

P

S

M

P

)

(

)

(

)

|

(

)

|

(

2

1

2

1

2

1

n

n

n

A

A

A

P

C

P

C

A

A

A

P

A

A

A

C

P

K

K

K

=

Tid

Refund

Marital

Status

Taxable

Income

Evade

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

Singl

e

90K

Yes

10

categorical

categorical

continuous

class

2

2

2

)

(

2

2

1

)

|

(

ij

ij

i

A

ij

j

i

e

c

A

P

s

m

ps

-

-

=

0072

.

0

)

54

.

54

(

2

1

)

|

120

(

)

2975

(

2

)

110

120

(

2

=

=

=

-

-

e

No

Income

P

p

P(Refund=Yes|No) = 3/7

P(Refund=No|No) = 4/7

P(Refund=Yes|Yes) = 0

P(Refund=No|Yes) = 1

P(Marital Status=Single|No) = 2/7

P(Marital Status=Divorced|No)=1/7

P(Marital Status=Married|No) = 4/7

P(Marital Status=Single|Yes) = 2/7

P(Marital Status=Divorced|Yes)=1/7

P(Marital Status=Married|Yes) = 0

For taxable income:

If class=No:

sample mean=110

sample variance=2975

If class=Yes:

sample mean=90

sample variance=25

naive Bayes Classifier:

120K)

Income

Married,

No,

Refund

(

=

=

=

X

m

N

mp

N

C

A

P

c

N

N

C

A

P

N

N

C

A

P

c

ic

i

c

ic

i

c

ic

i

+

+

=

+

+

=

=

)

|

(

:

estimate

-

m

1

)

|

(

:

Laplace

)

|

(

:

Original

NameGive BirthCan FlyLive in WaterHave LegsClass

humanyesnonoyesmammals

pythonnononononon-mammals

salmonnonoyesnonon-mammals

whaleyesnoyesnomammals

frognonosometimesyesnon-mammals

komodonononoyesnon-mammals

batyesyesnoyesmammals

pigeonnoyesnoyesnon-mammals

catyesnonoyesmammals

leopard sharkyesnoyesnonon-mammals

turtlenonosometimesyesnon-mammals

penguinnonosometimesyesnon-mammals

porcupineyesnonoyesmammals

eelnonoyesnonon-mammals

salamandernonosometimesyesnon-mammals

gila monsternononoyesnon-mammals

platypusnononoyesmammals

owlnoyesnoyesnon-mammals

dolphinyesnoyesnomammals

eaglenoyesnoyesnon-mammals

Give BirthCan FlyLive in WaterHave LegsClass

yesnoyesno?

0027

.

0

20

13

004

.

0

)

(

)

|

(

021

.

0

20

7

06

.

0

)

(

)

|

(

0042

.

0

13

4

13

3

13

10

13

1

)

|

(

06

.

0

7

2

7

2

7

6

7

6

)

|

(

=

´

=

=

´

=

=

´

´

´

=

=

´

´

´

=

N

P

N

A

P

M

P

M

A

P

N

A

P

M

A

P

X

1

X

2

X

3

Y

1000

1011

1101

1111

0010

0100

0111

0000

X

1

X

2

X

3

Y

Black box

Output

Input

X

1

X

2

X

3

Y

1000

1011

1101

1111

0010

0100

0111

0000



X

1

X

2

X

3

Y

Black box

0.3

0.3

0.3

t=0.4

Output

node

Input

nodes

î

í

ì

=

>

-

+

+

=

otherwise

0

true

is

if

1

)

(

where

)

0

4

.

0

3

.

0

3

.

0

3

.

0

(

3

2

1

z

z

I

X

X

X

I

Y



X

1

X

2

X

3

Y

Black box

w

1

t

Output

node

Input

nodes

w

2

w

3

)

(

t

X

w

I

Y

i

i

i

-

=

å

)

(

t

X

w

sign

Y

i

i

i

-

=

å

Activation

function

g(S

i

)

S

i

O

i

I

1

I

2

I

3

w

i1

w

i2

w

i3

O

i

Neuron iInputOutput

threshold, t

Input

Layer

Hidden

Layer

Output

Layer

x

1

x

2

x

3

x

4

x

5

y

[

]

2

)

,

(

å

-

=

i

i

i

i

X

w

f

Y

E

B

1

B

2

B

1

B

2

B

1

B

2

b

11

b

12

b

21

b

22

margin

B

1

b

11

b

12

0

=

+

·

b

x

w

r

r

1

-

=

+

·

b

x

w

r

r

1

+

=

+

·

b

x

w

r

r

î

í

ì

-

£

+

·

-

³

+

·

=

1

b

x

w

if

1

1

b

x

w

if

1

)

(

r

r

r

r

r

x

f

2

||

||

2

Margin

w

r

=

î

í

ì

-

£

+

·

-

³

+

·

=

1

b

x

w

if

1

1

b

x

w

if

1

)

(

i

i

r

r

r

r

r

i

x

f

2

||

||

)

(

2

w

w

L

r

=

î

í

ì

+

-

£

+

·

-

³

+

·

=

i

i

i

i

1

b

x

w

if

1

-

1

b

x

w

if

1

)

(

x

x

r

r

r

r

r

i

x

f

÷

ø

ö

ç

è

æ

+

=

å

=

N

i

k

i

C

w

w

L

1

2

2

||

||

)

(

x

r

Original

Training data

....

D

1

D

2

D

t-1

D

t

D

Step 1:

Create Multiple

Data Sets

C

1

C

2

C

t -1

C

t

Step 2:

Build Multiple

Classifiers

C

*

Step 3:

Combine

Classifiers

å

=

-

=

-

÷

÷

ø

ö

ç

ç

è

æ

25

13

25

06

.

0

)

1

(

25

i

i

i

i

e

e

Original Data

1

2

3

4

5

6

7

8

9

10

Bagging (Round 1)

7

8

10

8

2

5

10

10

5

9

Bagging (Round 2)

1

4

9

1

2

3

2

7

3

2

Bagging (Round 3)

1

8

5

10

5

5

9

6

3

7

Original Data

1

2

3

4

5

6

7

8

9

10

Boosting (Round 1)

7

3

2

8

7

9

4

10

6

3

Boosting (Round 2)

5

4

9

4

2

5

1

7

4

2

Boosting (Round 3)

4

4

8

10

4

5

4

6

3

4

(

)

å

=

¹

=

N

j

j

j

i

j

i

y

x

C

w

N

1

)

(

1

d

e

÷

÷

ø

ö

ç

ç

è

æ

-

=

i

i

i

e

e

a

1

ln

2

1

factor

ion

normalizat

the

is

where

)

(

if

exp

)

(

if

exp

)

(

)

1

(

j

i

i

j

i

i

j

j

j

i

j

i

Z

y

x

C

y

x

C

Z

w

w

j

j

ï

î

ï

í

ì

¹

=

=

-

+

a

a

(

)

å

=

=

=

T

j

j

j

y

y

x

C

x

C

1

)

(

max

arg

)

(

*

d

a

Boosting

Round 1

+++

-------

0.00940.00940.4623

B1

 = 1.9459

Original

Data

+++

-----

++

0.1

0.10.1

Boosting

Round 1

+++

-------

Boosting

Round 2

--------

++

Boosting

Round 3

++++++++++

Overall

+++

-----

++

0.00940.00940.4623

0.3037

0.00090.0422

0.0276

0.1819

0.0038

B1

B2

B3

 = 1.9459

 = 2.9323

 = 3.8744