ươ ươ

ạ ữ ệ ạ ữ ệ

Ch Ch

ng 4: Phân lo i d  li u ng 4: Phân lo i d  li u

ữ ệ

Khai phá d  li u

(Data mining)

1

ộ

N i dung

ạ ữ ệ

ổ

 4.1. T ng quan v  phân lo i d  li u ề

ạ ữ ệ

ế ị

ớ

 4.2. Phân lo i d  li u v i cây quy t đ nh

ạ ữ ệ

ạ

ớ

 4.3. Phân lo i d  li u v i m ng Bayesian

ạ ữ ệ

ạ

ớ

 4.4. Phân lo i d  li u v i m ng Neural

ươ

ạ ữ ệ

 4.5. Các ph

ng pháp phân lo i d  li u khác

 4.6. Tóm t

tắ

2

ố

4.0. Tình hu ng 1

Evade

Tid Refund

Marital Status

Taxable Income

No

Yes

Single

125K

1

No

Married

100K

No

2

No

Single

70K

No

3

No

Yes

Married

120K

4

ố

Yes

Divorced 95K

No

5

No

Married

60K

No

6

Ông A (Tid = 100) có  ả kh  năng tr n  thu ???ế

No

Yes

Divorced 220K

7

Yes

Single

85K

No

8

No

Married

75K

No

9

Yes

10 No

Single

90K

10

3

ố

4.0. Tình hu ng 2

ớ

ủ

ệ

ộ

ị

V i thông tin c a m t applicant A, xác đ nh li u ngân hàng có cho A  vay không?

4

ố

4.0. Tình hu ng 3

ố

ệ

Khóa

MãSV

MônH c1ọ

MônH c2ọ

T tNghi p

…

2004

1

9.0

8.5

…

Có

2004

2

6.5

8.0

…

Có

2004

3

4.0

2.5

…

Không

2004

8

5.5

3.5

…

Không

2004

14

5.0

5.5

…

Có

…

…

…

…

…

…

2005

90

7.0

6.0

…

Có

2006

24

9.5

7.5

…

Có

2007

82

5.5

4.5

…

Không

2008

47

2.0

3.0

…

Không

…

…

…

…

…

…

ị

ẽ ố

ệ

Làm sao xác đ nh li u sinh  viên A s  t

ệ t nghi p?

5

4.0. Tình hu ng …ố

ướ ậ

ệ

ấ

ẫ

ả ề

Cho tr

c t p hu n luy n (training set), d n ra mô t

v  class A và class B?

ướ

ố ượ

ẫ

ố ượ

ẫ

ớ

Cho tr

c m u/đ i t

ị ng m i, làm sao xác đ nh class cho m u/đ i t

ng đó?

ố ượ

ự

ự

ệ

ẫ

ợ

Li u class đó có th c s  phù h p/đúng cho m u/đ i t

ng đó?

6

ạ ữ ệ

ổ

ề 4.1. T ng quan v  phân lo i d  li u

ạ ữ ệ

 Phân lo i d  li u (classification)

 D ng phân tích d  li u nh m rút trích các mô hình mô  ằ ự

ữ ệ ữ ệ ướ ớ ữ ệ ạ ặ ả  các l p d  li u ho c d  đoán xu h ng d  li u t

ướ

ự

ệ

ấ

ộ

ạ  B c h c (giai đo n hu n luy n): xây d ng b  phân lo i

 Quá trình g m hai b ạ ọ ệ

ằ

ọ ậ

ệ

ấ

(classifier) b ng vi c phân tích/h c t p hu n luy n

ạ

ố ượ

ớ

 B c phân lo i (classification): phân lo i d  li u/đ i t

ng m i

ướ ế

ủ

ộ

ạ ượ

ạ ữ ệ ể c đánh giá là có th

ượ

ấ

ậ

ộ n u đ  chính xác c a b  phân lo i đ ch p nh n đ

c (acceptable)

ả ủ

ộ ớ

ầ

ớ

ữ ệ

ố ượ

ồ ướ c:

y = f (X) v i y là nhãn (ph n mô t ) c a m t l p (class) và X là d  li u/đ i t

ộ ị

ướ

ệ

ậ

ấ

ọ

ượ

ướ

ị

­ B c h c: X trong t p hu n luy n, m t tr  y đ

c cho tr

c v i X

ng ớ  xác đ nh f ế

ệ

ấ

ậ

ọ

ướ

ớ

’, y’) và X’ <> m i X trong t p hu n luy n; n u acceptable thì

ể

ạ ị

­ B c phân lo i: đánh giá f v i (X ’’ cho X’’ (m i)ớ dùng f đ  xác đ nh y

7

ạ ữ ệ

ổ

ề 4.1. T ng quan v  phân lo i d  li u

ệ

ấ

ọ

B c h c/hu n luy n

ướ

ụ

ạ

ướ B c phân lo i (đánh giá và áp d ng)

8

ạ ữ ệ

ổ

ề 4.1. T ng quan v  phân lo i d  li u

ạ ữ ệ

 Phân lo i d  li u

 D ng h c có giám sát (supervised learning)

ạ ọ

desired response Y state X

Environment Teacher

+

actual response ­ (cid:0)

Learning  System

9

error signal

ạ ữ ệ

ổ

ề 4.1. T ng quan v  phân lo i d  li u

ả

 Các gi

ạ ữ ệ ế ị

ạ ạ

ậ i thu t phân lo i d  li u  Phân lo i v i cây quy t đ nh (decision tree) ạ ớ  Phân lo i v i m ng Bayesian ạ ớ  Phân lo i v i m ng neural ạ ớ  Phân lo i v i k ph n t ầ ử ậ ạ ớ

ầ ấ  c n g n nh t (k­nearest

neighbor)

 Phân lo i v i suy di n d a trên tình hu ng (case­based

ạ ớ ự ễ ố

reasoning)

 Phân lo i d a trên ti n hoá gen (genetic algorithms) ế  Phân lo i v i lý thuy t t p thô (rough sets) ế ậ  Phân lo i v i lý thuy t t p m  (fuzzy sets) … ế ậ

10

ạ ự ạ ớ ạ ớ ờ

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

ơ ở ữ ệ

ướ

C  s  d  li u khách hàng

AllElectronics dùng cho b

ọ c h c

11

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

ể

ộ

ộ

ả ủ

ộ ớ

c a m t l p (class label)

ừ ộ

ả ủ

ử

ế

ộ

ộ

ộ

m t node n i: k t qu  c a m t phép th  trên thu c tính

 Cây quy t đ nh (decision tree) – mô hình phân lo i ạ  Node n i: phép ki m th  (test) trên m t thu c tính ử  Node lá: nhãn/mô t  Nhánh t ứ ươ ng  ng t

ượ ừ c t

CSDL

ấ

ế ị ọ Cây quy t đ nh h c đ ệ AllElectronics hu n luy n

12

ế ị ộ

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

ả

ế ị

ự

ậ

 Gi

i thu t xây d ng cây quy t đ nh

 ID3, C4.5, CART (Classification and Regression Trees

13

– binary decision trees)

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

14

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

ủ

ặ

ả

 Đ c đi m c a gi ể

ậ i thu t

 Gi

ậ ể ị ệ i thu t tham lam (không có quay lui), chia đ  tr , đ

ừ ố ả qui, t trên xu ng

ứ ạ ấ ầ ử ệ D g m |ồ D| ph n t

 Đ  ph c t p v i t p hu n luy n  ớ ậ ỗ ng), m i ph n t

 O(n*|D|*log|D|)

ứ

ứ

ủ

ỗ

ỗ

ớ

ộ

 M i thu c tính  ng v i m i m c (level) c a cây.

ứ

ỗ

ử

ệ

ấ

ượ

 Cho m i m c c a cây, |D| phân t ủ

hu n luy n đ

ệ c duy t qua.

 In­memory  ???

15

ộ ộ ố ượ (đ i t g m ầ ử ồ n thu c tính

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

 Attribute_selection_method

ứ ẽ ọ

ấ ạ ể ươ ng th c dùng heuristic đ  ch n tiêu chí r  nhánh  ệ D thành  ậ ộ i m t node, i.e. phân ho ch t p hu n luy n

 Ph ạ t các phân ho ch con v i các nhãn phù h p

ế

ạ

ỗ

ộ

 X p h ng m i thu c tính

ị ố ể

ể ẽ

ộ

ọ

ộ  Thu c tính đ

c ch n đ  r  nhánh là thu c có tr  s  đi m

ượ ấ ớ (score) l n nh t

ộ

ộ

ọ

 Đ  đo ch n thu c tính phân tách (splitting attribute):

information gain, gain ratio, gini index

16

ạ ợ ớ

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

ộ

A là thu c tính phân tách (splitting attribute).

17

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

 Đ  đo Information Gain

ộ  D a trên lý thuy t thông tin (information theory) c a

ế ự

ươ ề ứ ủ ủ ị ộ Claude Shannon v  giá tr  (n i dung thông tin) c a tin ấ ẽ ng  ng v i information gain l n nh t s

 Thu c tính t ộ ớ ớ c ch n làm splitting attribute cho node N.

ệ ạ ầ ả ấ

ượ

ạ

ọ đ

ể

ố

ạ ử i thi u s  phép th  (test) đ  phân

ạ

ạ i c n phân ho ch các ph n t ắ ả ữ (randomness) ít nh t gi a các phân ho ch t o đ ố ậ  Cách ti p c n này giúp t ầ ử .

ế ộ lo i m t ph n t

18

ượ ầ ử  Node N là node hi n t  trong D. ẫ ự  Splitting attribute đ m b o s  trùng l p (impurity)/ng u nhiên  c. ể

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

ộ

 Đ  đo Information Gain

 L

ượ ầ ử ể ạ ầ ộ ng thông tin c n đ  phân lo i m t ph n t trong

ấ ể ộ

ầ ử ấ ỳ

ề ớ

ộ

b t k  trong D thu c v  l p C

 pi: xác su t đ  m t ph n t

i

ớ

v i i = 1..m

ầ ử ủ ớ

ậ

c a l p C

 Ci,D: t p các ph n t

i trong D

m

ủ D (= Entropy c a D): Info(D)

Info

D

(

)

log

(

)

p i

p i

2

(cid:0) (cid:0) (cid:0)

i

(cid:0)

1 D

C

|

|

|/|

p i

Di ,

19

(cid:0)

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

 Đ  đo Information Gain

ầ ử

ể

ạ

ộ

ự

 L

trong D d a trên

ượ ng thông tin c n đ  phân lo i m t ph n t ộ

thu c tính A: Info

ầ A(D)

ạ

 Thu c tính A dùng phân tách D thành v phân ho ch {D

1, D2, …, Dj,

ộ …, Dv}.

ạ

ỗ

ầ ử

 M i phân ho ch D

trong D.

j g m |Dồ

j| ph n t

ứ

ẽ

ộ

 L

ế ng thông tin này s  cho bi ạ

ữ ầ ử ừ ộ ớ

ứ

ộ

m t l p hay

t

ượ ạ ề ớ

ắ t m c đ  trùng l p gi a các phân  ho ch, nghĩa là m t phân ho ch ch a các ph n t nhi u l p khác nhau.

ợ

ỏ

ố

 Mong đ i: Info

t.

v

D

A(D) càng nh  càng t |

|

ộ

Info

D

Info

D

(

)

*

(

)

A

j

(cid:0) (cid:0)

j D

|

|

j

1

20

(cid:0)

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

ộ

 Đ  đo Information Gain

ệ ộ ữ ị t gi a tr  thông tin

 Information gain chính là đ  sai bi ạ ớ

ướ ầ ị c phân ho ch) và tr  thông tin

A(D) (sau phân ho ch v i A).

ạ ớ Info(D) ban đ u (tr m i Info

(cid:0) (cid:0)

Gain

Info

D

Info

D

(

A )

(

)

(

)

A

21

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

Gain(age)=0.246 bits

Gain(income)?

Gain(student)?

Gain(credit_rating)?

 Splitting attribute?

22

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

 Đ  đo Gain Ratio: GainRatio(A)

ớ

 Dùng v i C4.5

ả

ạ

ộ

 Gi

ề ộ i quy t v n đ  m t thu c tính đ

c dùng t o ra r t nhi u

ấ ầ ử

ế ấ ạ

ượ ạ

ỉ ồ

ậ

ỗ

ề phân ho ch (th m chí m i phân ho ch ch  g m 1 ph n t ).

ớ ị

ẩ

 Chu n hoá information gain v i tr  thông tin phân tách (split

information): SplitInfoA(D)

ươ

ớ ị

ị ớ

ứ

ấ

 Splitting attribute A t

ng  ng v i tr  GainRatio(A) là tr  l n nh t.

v

ộ

D

D

|

|

|

|

SplitInfo

D

(

)

log*

A

2

j D

j D

|

|

|

|

j

1

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

GainRatio

(

A )

Gain ( SplitInfo

A ) D (

)

A

23

(cid:0)

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

SplitInfoincome(D)

Gain(income) = 0.029

GainRatio(income) = 0.029/0.926 = 0.031

GainRatio(age)?

GainRatio(student)?

GainRatio(credit_rating)?

 Splitting attribute?

24

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

ớ

 Đ  đo Gini Index  Dùng v i CART

ộ

ỗ

ị

 S  phân tách nh  phân (binary split) cho m i thu c tính A

ự  A (cid:0)

SA?

ộ ậ

ồ

ộ

ộ

ị

 SA là m t t p con g m m t hay v­1 tr  thu c tính A.

ấ ươ

ủ

ỏ

ị

ộ ậ

ứ

 Gini index c a m t thu c tính là tr  nh  nh t t

ớ ng  ng v i m t t p

ộ ậ

ộ  2ừ v – 2 t p con.

con SA t

ấ ể ố

ươ

ớ

ỏ

ng  ng v i gini index nh  nh t đ  t

ự i đa hóa s

 Splitting attribute t ả

ề ộ

ữ

ạ

ứ ắ suy gi m v  đ  trùng l p gi a các phân ho ch.

25

ộ

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

{low,high} = Giniincome(cid:0) {medium,high} = Giniincome(cid:0)

{medium} = 0.315 {low} = 0.300

{medium,high}/{low}=0.300 {youth,senior}/{middle_aged} = 0.375

26

Giniincome(cid:0) Giniincome(cid:0)  Giniincome (cid:0)     Giniage (cid:0)     Ginistudent=0.367     Ginicredit_rating=0.429  Splitting attribute?

ạ ữ ệ

ế ị

ớ

4.2. Phân lo i d  li u v i cây quy t đ nh

ế ị

ự

ừ ơ ở ữ ệ

ấ

 Xây d ng cây quy t đ nh t

c  s  d  li u hu n

ệ

luy n AllElectronics

 Dùng đ  đo Information Gain

ộ

 Dùng đ  đo Gain Ratio

ộ

 Dùng đ  đo Gini Index

ộ

 Các cây quy t đ nh h c đ

ế ị ọ ượ ố c gi ng nhau???

 Ti n hành đánh giá và phân lo i v i các cây quy t đ nh

ạ ớ ế ị

27

ượ ế ọ h c đ c

ạ ữ ệ

ạ

ớ

4.3. Phân lo i d  li u v i m ng Bayesian

ự

ủ

ị

 D a trên đ nh lý c a Bayes

 Phân lo i Naïve Bayesian

ả ị

ệ ớ

ộ ậ

ề

 Gi

đ nh: đ c l p có đi u ki n l p (class conditional

independence)

ạ

 Phân lo i Bayesian belief networks

ươ

 Ph

ấ ạ ự ng pháp phân lo i d a trên xác su t

28

ạ

ạ ữ ệ

ạ

ớ

4.3. Phân lo i d  li u v i m ng Bayesian

29

Reverend Thomas Bayes (1702-1761)

ạ ữ ệ

ạ

ớ

4.3. Phân lo i d  li u v i m ng Bayesian

ộ

ề ớ

ộ

 Đ nh lý Bayes

Cho m t RID, RID thu c v   l p  “yes” (buys_computer = yes)

ố ượ

ộ

 X: m t tuple/đ i t

ng (evidence)

ả

ế

 H: gi

thuy t (hypothesis)

ề ớ

ộ

 X thu c v  l p C.

X

ượ

ị

ở ị c xác đ nh b i tr

ộ

X đ ủ c a các thu c tính.

30

ị

ạ ữ ệ

ạ

ớ

4.3. Phân lo i d  li u v i m ng Bayesian

 Đ nh lý Bayes

 P(H|X): posterior probability

ố ớ

ủ

ề

ệ

ấ

 Xác su t có đi u ki n c a H đ i v i X.

ụ

ấ

 Ví d : P(buys_computer=yes|age=young, income=high) là xác su t

ủ

mua máy tính c a khách hàng có tu i

ổ “young” và thu nh p ậ “high”.

 P(X|H): posterior probability

ố ớ

ủ

ề

ệ

ấ

 Xác su t có đi u ki n c a X đ i v i H.

ụ

ấ

 Ví d : P(age=young, income=high|buys_computer=yes) là xác su t

khách hàng mua máy tính có tu i ổ “young” và thu nh p ậ “high”.

 P(age=young, income=high|buys_computer=yes) = 0

 P(age=young, income=high|buys_computer=no) = 2/5 = 0.4

31

ị

ạ ữ ệ

ạ

ớ

4.3. Phân lo i d  li u v i m ng Bayesian

ị

 Đ nh lý Bayes

 P(H): prior probability

ấ ủ

 Xác su t c a H

ụ

ủ

ấ

 Ví d : P(buys_computer=yes) là xác su t mua máy tính c a

khách hàng nói chung.

 P(buys_computer=yes) = 9/14 = 0.643  P(buys_computer=no) = 5/14 = 0.357

 P(X): prior probability

ấ ủ

 Xác su t c a X

ụ

ấ

 Ví d : P(age=young, income=high) là xác su t khách hàng có

tu i ổ “young” và thu nh p ậ “high”.

 P(age=young, income=high) = 2/14 = 0.143

32

ạ ữ ệ

ạ

ớ

4.3. Phân lo i d  li u v i m ng Bayesian

ị

 Đ nh lý Bayes

 P(H), P(X|H), P(X) có th  đ

ể ượ ừ ậ c tính t ữ ệ  t p d  li u cho

tr c.ướ

 P(H|X) đ

(

(

)

ượ ừ ị c tính t đ nh lý Bayes.

XHP

(

|

)

HPHXP | ) XP (

)

P(buys_computer=yes|age=young, income=high) = P(age=young, income=high| buys_computer=yes)P(buys_computer=yes)/P(age=young, income=high) = 0

P(buys_computer=no|age=young, income=high) = P(age=young, income=high| buys_computer=no)P(buys_computer=no)/P(age=young, income=high) = 0.4*0.357/0.143 = 0.9986

33

(cid:0)

ạ ữ ệ

ạ

ớ

4.3. Phân lo i d  li u v i m ng Bayesian

 Cho tr

ữ ệ ướ ậ ấ ả ớ

ạ ủ  (nhãn) c a  ố ượ ng ệ c t p d  li u hu n luy n D v i mô t i, i=1..m, quá trình phân lo i m t tuple/đ i t

ượ

ế

 X đ

ạ c phân lo i vào C

ỉ ế i n u và ch  n u

ớ

P(Ci|X) > P(Cj|X) v i 1<=j<=m, j<>i

(

(

)

i

ộ ư ớ các l p Cớ ạ X = (x1, x2, …, xn) v i m ng Bayesian nh  sau:

(

|

)

XCP i

CPCXP | ) i XP (

)

ế

ấ

ố

 T i đa hóa P(C

i|X) (i.e. ch n Cọ

i n u P(C

ị ớ i|X) là tr  l n nh t)

ố

 T i đa hóa P(X|C

i)P(Ci)

ặ

 P(C1) = P(C2) = .. = P(Cm) ho c P(C

i) = |Ci,D|/|D| …

34

(cid:0)

ạ ữ ệ

ạ

ớ

4.3. Phân lo i d  li u v i m ng Bayesian

n

(

|

)

(

|

)

(

|

(*)

|

(*..*)

|

)

CXP i

CxP k

i

i

i

CxP n

i

CxP 1

CxP 2

(cid:0) (cid:0) (cid:0)

k

1

(cid:0)

 P(X|Ci) đ

ượ ớ ả ị c tính v i gi đ nh class conditional

independence.

 xk, k = 1..n: tr  thu c tính A

k c a Xủ

ộ ị

 P(xk|Ci) đ

ờ ạ

ộ  Ak là thu c tính r i r c.  P(xk|Ci) = |{X’|x’k = xk (cid:0)  X’ (cid:0)

Ci}|/|Ci,D|

ụ

ộ

 Ak là thu c tính liên t c.

35

ụ

ấ

ố

ộ

ố

 P(xk|Ci) tuân theo m t phân b  xác su t nào đó (ví d : phân b  Gauss).

ượ ư c tính nh  sau:

ạ ữ ệ

ạ

ớ

4.3. Phân lo i d  li u v i m ng Bayesian

ế  N u P(x

k|Ci) = 0 thì P(X|Ci) = 0!!!

 Ban đ uầ

 P(xk|Ci) = |{X’|x’k = xk (cid:0)  X’ (cid:0)

Ci}|/|Ci,D|

 Laplace (Pierre Laplace, nhà toán h c Pháp, 1749­

ọ

 P(xk|Ci) = (|{X’|x’k = xk (cid:0)  X’ (cid:0)

Ci}|+1)/(|Ci,D| + m)

 z­estimate

 P(xk|Ci) = (|{X’|x’k = xk (cid:0)  X’ (cid:0)

Ci}| + z*P(xk))/(|Ci,D| + z)

36

1827)

ạ ữ ệ

ạ

ớ

4.3. Phân lo i d  li u v i m ng Bayesian

C1 = {X’|X’.buys_computer = yes}

C2 = {X’’|X’’.buys_computer = no}

37

 X (cid:0) C1

ạ ữ ệ

ạ

ớ

4.4. Phân lo i d  li u v i m ng Neural

 M ng Neural sinh h c ọ

38

ạ

ạ ữ ệ

ạ

ớ

4.4. Phân lo i d  li u v i m ng Neural

 Quá trình x  lý thông tin t ử

ạ ạ ộ ủ i m t neuron c a m ng Neural

39

nhân t oạ

ạ ữ ệ

ạ

ớ

4.4. Phân lo i d  li u v i m ng Neural

 M ng neural feed­forward đa t ng

40

ạ ầ

ạ ữ ệ

ạ

ớ

4.4. Phân lo i d  li u v i m ng Neural

 Gi

ả ậ ọ ề ượ i thu t h c lan truy n ng c (Backpropagation) có

41

giám sát

ạ ữ ệ

ạ

ớ

4.4. Phân lo i d  li u v i m ng Neural

42

ạ ữ ệ

ạ

ớ

4.4. Phân lo i d  li u v i m ng Neural

Output vector

j

j

j

jk

Output nodes

(cid:0) (cid:0) (cid:0) Err O O 1( ) wErr k

k Err

j

j

j

(cid:0) (cid:0) (cid:0) (cid:0) l)(

(cid:0) (cid:0) l )( w ij w ij OErr j i

Hidden nodes

j

j

j

j

(cid:0) (cid:0) (cid:0) Err O 1( )( ) OTO j

j

jI

Input nodes

1 wij (cid:0) O (cid:0) (cid:0)

j

j

i

Input vector: xi

43

(cid:0) (cid:0) (cid:0) (cid:0) I e 1 Ow ij i

ạ ữ ệ

ạ

ớ

4.4. Phân lo i d  li u v i m ng Neural

44

ạ ữ ệ

ạ

ớ

4.4. Phân lo i d  li u v i m ng Neural

45

ạ ữ ệ

ạ

ớ

4.4. Phân lo i d  li u v i m ng Neural

46

ươ

ạ ữ ệ

4.5. Các ph

ng pháp phân lo i d  li u khác

Unknown record

 Phân lo i k­nn (k­nearest

ạ neighbor)

 Cho tr ấ

ướ ậ ữ ệ

i các l p

c t p d  li u  ệ ớ

ự ớ

ng t ậ ố

 Ph  thu c ộ ụ

ể

ộ ị

ả  Đ  đo kho ng cách đ  xác  ự ươ ng t

đ nh s  t

ự .

ị

ầ ử

ề

láng gi ng

47

ố  Tr  k, s  ph n t  k <= |D|1/2

hu n luy n D v ớ ,  ạ phân lo i record/object X  ớ ự vào các l p d a vào k  ầ ử ươ  v i X   t ph n t ấ nh t (dùng lu t s  đông:  majority vote)

ươ

ạ ữ ệ

4.5. Các ph

ng pháp phân lo i d  li u khác

 Ch n đ  đo ọ

ộ

ộ

p

q

qpd ( ),

(

2)

 Đ  đo Euclidean

i

i

i

(cid:0) (cid:0) (cid:0)

 Ch n tr  k ọ

ả ễ ị ả

ế

ế

ỏ

ưở

ễ

ở

 N u k quá nh  thì k t qu  d  b   nh h

ng b i nhi u.

ầ ử

ề

ề

ọ

ượ

láng gi ng ch n đ

ể c có th

 N u k quá l n thì nhi u ph n t ớ ớ  các l p khác.

ế ế ừ đ n t

k quá l n!ớ

ị

X

48

ươ

ạ ữ ệ

4.5. Các ph

ng pháp phân lo i d  li u khác

X

X

X

(a) 1-nearest neighbor

(b) 2-nearest neighbor

(c) 3-nearest neighbor

X (cid:0)

PLUS

MINUS

X (cid:0)

MINUS

X (cid:0) hay X (cid:0)

PLUS ?

49

4.6. Tóm t

tắ

 ID3, C4.5, CART

 Classification v i Decision trees ớ

ự

ấ

ố

 D a trên lý thuy t xác su t th ng kê ế

 Classification với mạng Bayesian

 Classification với mạng Neural

50

 D aự  trên khoảng cách

 K­nn classification

ỏ

ỏH i & Đáp … H i & Đáp …

51