Bài giảng Khai phá dữ liệu web (PGS.TS. Hà Quang Thụy)

BÀI GI NG NH P MÔN KHAI PHÁ D LI U

Ữ Ệ

Ả

Ậ

CH

NG 5. PHÂN L P

ƯƠ

Ớ

Ộ

TR

Ạ Ọ

ƯỜ

PGS. TS. HÀ QUANG TH YỤ HÀ N I 9-2011 NG Đ I H C CÔNG NGH Ệ Đ I H C QU C GIA HÀ N I Ộ Ố Ạ Ọ

N i dung

ộ

ớ

i thi u phân l p ệ ớ Phân l p h c giám sát ọ ớ Phân l p h c bán giám sát ọ

ớ

Bài toán phân l pớ

 Đ u vào ầ ậ

 T p d li u D = {d ữ ệ

 T p các l p C

1, C2, …, Ck m i d li u d thu c m t l p C

 T p ví d D

ậ ớ ỗ ữ ệ ộ

 T p ví d D

ậ ộ ớ i={d˛ Dexam: d thu c Cộ

 Đ u raầ

 Mô hình phân l p: ánh x t

ậ ạ ậ ụ exam = D1+D2+ …+ Dk v i Dớ ụ exam đ i di n cho t p D ệ

 S d ng mô hình

ử ụ

 d ˛

D sang C ạ ừ ớ

ng d ố ượ ủ ớ D \ Dexam : xác đ nh l p c a đ i t ị

Phân l p: Quá trình hai pha

ớ

cho t p l p đã có ậ ớ

 Xây d ng mô hình: Tìm mô t ả 1, C2, …, Ck} mi n D sang t p l p C ề

c t p l p C = {C t) t ế ừ

ậ ớ i={d˛ Dexam: d˛ Ci}

ự  Cho tr ướ ậ ớ  Cho ánh x (ch a bi ư ạ ụ exam=D1+D2+ …+ Dk v i Dớ  Có t p ví d D ậ Dexam đ ọ ượ ự

c g i là t p ví d m u. ậ

ạ ạ

ụ ẫ  Xây d ng ánh x (mô hình) phân l p trên: D y b phân l p.  Mô hình: Lu t phân l p, cây quy t đ nh, công th c toán h c… ớ ế ị ộ ứ ớ ọ ớ

ạ

ộ

ớ

 Tách Dexam thành Dtrain (2/3) + Dtest (1/3). Dtrain và Dtest “tính đ i ạ

ậ  Pha 1: D y b phân l p

ệ ụ

di n” cho mi n ng d ng ề ứ ự ố

ị ộ ệ

 Dtrain : xây d ng mô hình phân l p (xác đ nh tham s mô hình)  Dtest : đánh giá mô hình phân l p (các đ đo hi u qu ) ả  Ch n mô hình có ch t l ấ ượ ộ

ử ụ

 d ˛

ọ

ủ ớ ị ớ ớ ng nh t ấ  Pha 2: S d ng b phân l p ớ D \ Dexam : xác đ nh l p c a d.

Ví d phân l p: Bài toán cho vay

ụ Tid

ớ Refund

Marital Status

Taxable Income

Cheat

Single

75K

Yes

Married

50K

Single

75K

Married

150K

Yes

Single

40K

Married

80K

Yes

Single

75K

Yes

Married

50K

Yes

Married

50K

Married

150K

Yes

Single

40K

Married

150K

Yes

Married

80K

Yes

Single

40K

Married

80K

Yes

Phân l p: Quá trình hai pha

ớ

Phân l p: Quá trình hai pha

ớ

Attrib2

Attrib3 Class

Tid Attrib1

No

Yes

Large

125K

Learning algorithm

No

Medium

100K

No

Small

70K

No

Yes

Medium

120K

Induction

Yes

Large

95K

No

Medium

60K

No

Yes

Large

220K

Yes

Small

85K

Learn Model

No

Medium

75K

Yes

10 No

Small

90K

Model

Training Set

Apply Model

Attrib2

Attrib3 Class

Tid Attrib1

?

11 No

Small

55K

?

12 Yes

Medium

80K

Deduction

?

13 Yes

Large

110K

?

14 No

Small

95K

?

15 No

Large

67K

Test Set

Các lo i phân l p

ớ

ạ

ớ

ị

ớ

 Phân l p nh phân/ đa l p: ớ ị  |C|=2: phân l p nh phân.  |C|>2: phân l p đa l p. ơ  Đ n nhãn: m i tài li u đ

c gán vào chính xác

ớ ớ  Phân l p đ n nhãn/ đa nhãn: ỗ

ượ

ệ

ơ m t l p. ộ ớ

 Đa nhãn: m t tài li u có th đ

c gán nhi u h n

ể ượ

ệ

ộ

ề

 Phân c p: l p này là cha/con c a l p kia

ộ ớ m t l p. ấ

ủ ớ

ớ

Các v n đ đánh giá mô hình

ề

ấ

ng pháp đánh giá hi u

– Các ph ươ ỏ

ệ quả ể đánh giá đ

c ượ hi u qu ả ệ

Câu h i: Làm th nào đ ế c a ủ m t ộ mô hình?

– Đ đo đ ộ

ể đánh giá hi u ệ quả

c tính đáng

ế

ể

c ượ ướ

ng pháp so sánh

– Ph

Câu h i: ỏ Làm th nào đ có đ tin c y?ậ ươ

mô hình ể

ệ qu ả t

ế

ươ

Câu h i: ỏ Làm th nào đ so sánh hi u đ i gi a các mô hình

có tính c nh tranh? ạ

ữ

ố

Đánh giá phân l p nh phân

ớ

ị

– Theo d li u test – Giá tr th c: P d ị

ữ ệ ự

ớ

ươ ọ ma tr n nh m l n ậ

ng / N âm; Giá tr qua phân l p: T ị ẫ

ầ

– S d ng các ký hi u TP (true positives), TN (true

đúng/F sai. : còn g i là ệ

ử ụ

ị

negatives), FP (false positives), FN (false negatives) • TP: s ví d d ng P mà thu t toán phân l p cho giá tr đúng T ậ ố • TN: s ví d âm N mà thu t toán phân l p cho giá tr đúng T ậ ố ng P mà thu t toán phân l p cho giá tr sai F • FP: s ví d d ậ ố - FN: s ví d âm N mà thu t toán phân l p cho giá tr sai F ố ậ - Đ h i t

p , các đ đo F

, đ chính xác

ộ ồ ưở

ộ

TP +

r ụ ươ ụ ụ ươ ụ ng ớ ớ ớ ớ ộ ị ị 1 và Fb

Đánh giá phân l p nh phân

ớ

ị

ng án khác đánh giá mô hình nh phân theo

ươ

ị

đ chính xác (accuracy) và h s l

i (Error rate)

– Ph ộ

ệ ố ỗ

– Ma tr n nh m l n

ẫ

ậ

ầ

L p d báo ự

ớ

L p = 1

ớ

L p th c s

ự

ớ

ự

L p = 0

ớ

ớ L p = 1 f11 f01

L p = 0 f10 f00

So sánh hai ph

ng án

ươ

ậ ể

ụ ớ ớ

ự

ụ

– T p test có 9990 ví d l p 0 và 10 ví d l p 1. ụ ớ Ki m th : mô hình d đoán c 9999 ví d là l p 0 ử ả và 1 ví d l p 1 (chính xác: TP) ụ ớ – Theo ph

ươ

ng án (precision, recall) có r = 1/10=0.1; p =1/1=1; f1 = 2*0.1/(0.1+1.0)= 0.18

– Theo ph

ng án (accurary, error rate) có

ươ

ượ

–

ể ệ

ạ

ả

ớ

accurary=0.9991; error rate = 9/10000 = 0.0009 Đ c coi là r t chính xác ! ấ f1 th hi n vi c đánh giá nh y c m v i giá d ữ ệ li uệ

Đánh giá phân l p đa l p

ớ

ồ

ớ

ỗ ớ

ự

ớ

c các đ i l

ượ

- Bài toán ban đ u: C g m có k l p ầ i , cho th c hi n thu t toán v i các d – Đ i v i m i l p C ệ ậ ố ớ ữ i, TFi, FPi, FNi ng TP test nh n đ li u thu c D ạ ượ ậ ộ ệ (nh b ng d i đây) ướ ư ả

Giá tr th c ị ự

L p ớ Ci

Thu c l p

ộ ớ Ci

Không thu c ộ l p ớ Ci

Thu c l p

ộ ớ Ci

TPi

TNi

ị

Giá tr qua b ộ phân l p đa ớ l pớ

FPi

FNi

Không thu c ộ l p ớ Ci

Đánh giá phân l p đa l p

ớ

 T

ự ộ

ớ

 Đ chính xác Pr

ng t ươ ộ

ị s ví d d ỷ ệ ố ố ổ

l ng đ ượ ậ

b phân l p hai l p (nh phân) ớ ủ ớ Ci là t i c a l p ụ ươ toán phân l p cho giá tr đúng trên t ng s ví d đ ị phân l p vào l p

ớ c thu t c thu t toán ậ ụ ượ

=Pr

TP i + TN

TP i

 Đ h i t

ớ ớ Ci :

i c a l p

l ộ ồ ưở ượ

s ví d d ỷ ệ ố ố ổ ng đ ụ ươ ị c thu t ậ ng th c s ự ự

=Re

TP i + FP i

TP i

ủ ớ Ci là t ụ ươ toán phân l p cho giá tr đúng trên t ng s ví d d thu c l p ng Re ớ ộ ớ Ci:

Đánh giá phân l p đa l p

ớ

ộ ồ

ụ

ộ

i và p

i : đ h i ph c và đ chính xác đ i ố

- Các giá tr ị r i. v i l p C ớ ớ

ộ

Đánh giá theo các đ đo vi trung bình-microaveraging (đ -

m và p

r c a chu ng) ộ

trung bình l n-macroaveraging ượ ư r M và p M ớ

1 K 1 = c

(cid:229) (cid:229)

1 K 1 = c TP c

TP c +

)

(cid:229) (cid:229)

= c 1 TP ( c

FP c

)

= 1

1 c TP ( c

(cid:229) (cid:229)

Các k thu t phân l p ậ

ớ

ỹ

 Các ph

ươ

ế ị

ng pháp cây quy t đ nh Decision Tree based Methods

 Các ph

ươ

ng pháp d a trên lu t ự

ậ

Rule-based Methods

 Các ph

ươ

ng pháp Bayes «ngây th » và m ng tin c y Bayes ơ

ạ

ậ

Naïve Bayes and Bayesian Belief Networks

 Các ph

ng pháp máy vector h tr

ươ

ỗ ợ

Support Vector Machines

 L p lu n d a trên ghi nh ớ ư

ậ

Memory based reasoning

 Các ph

ươ

ng pháp m ng n ron ạ

ng pháp khác

Neural Networks ươ

 M t s ph ộ ố

Phân l p cây quy t đ nh

ế ị

ớ

ế ị

 Mô hình phân l p là cây quy t đ nh ớ  Cây quy t đ nh

ế ị

ộ ộ ố

; không có cung vào + không/m t s cung ra ộ

cung ra (g n v i đi u ki n ki m tra giá tr thu c tính c a nút) ; có chính xác m t cung vào và m t s ộ ố ộ ủ ị

 G c: ố tên thu c tính  Nút trong: tên thu c tính ộ ể ệ ề ắ  Lá ho c nút k t thúc: ị ớ ; có chính xác m t cung vào + giá tr l p không có cung ra.

 Ví d : xem trang ti p theo  Xây d ng cây quy t đ nh

ớ ế ặ ộ

ế ế ị

ể ị ế ỗ

 Ph t ươ

 M t s thu t toán ph bi n: Hunt, h ID3+C4.5+C5.x

ụ ọ G c: toàn b d li u h c ọ ự ộ ữ ệ ộ ậ ỏ ố ớ

ụ ự ươ ng ng v i m t t p các ví d h c. ọ ng châm: “chia đ tr ”, “chia nh và ch ng ”. M i nút ứ ộ ố ậ

ế ị

ổ ế  S d ng cây quy t đ nh

ử ụ  Ki m tra t ể

g c theo các đi u ki n ừ ố ề ệ

Ví d cây quy t đ nh và s d ng ế ị

ử ụ

ụ

K t lu n

ậ : Gán giá tr ị YES vào tr

ế

ườ Cheat cho b n ghi

ả

Ví d cây quy t đ nh phân l p văn b n

ế ị

ụ

ả

ớ

ạ

ớ

 Phân l p văn b n vào l p AI : trí tu nhân t o  D a vào các t

ự

ệ ả khóa có trong văn b n: System, Process, ả ừ Timetable (Phân tích mi n ng d ng)

ề ứ

ụ

System

1. If System=0 and Process=0 then Class AI = Yes.

2. If System=0 and Process=1 then Class AI = No.

Timetable

Process

3. If System=1 and Timetable=1 then Class AI = Yes.

1 0 0

If System=1 and Timetable=0 then Class AI = No.

Yes

1 Yes

D ng cây quy t đ nh: thu t toán Hunt

ế ị

ự

ậ

 Thu t toán d ng cây quy t đ nh s m nh t, đ quy theo nút c a cây,

ế ị ủ ệ ấ ớ

 Input

ậ b t đ u t ự g c ắ ầ ừ ố

c xem xét ượ

 Cho nút t trên cây quy t đ nh đang đ  Cho t p các ví d h c D  Cho t p nhãn l p (giá tr l p) y

ụ ọ

1, y1, … yk. (k l p)ớ

 Output

 Xác đ nh nhãn nút t và các cung ra (n u có) c a t

ế ị t. ị ớ ậ ậ ớ

ủ ế ị

t đ u thu c vào m t l p y thì nút t là m t lá

1: N u m i ví d trong D ộ ớ ề ộ ộ

 N i dung ộ ụ ọ ế c gán nhãn y. và đ ượ t ch a các ví d thu c nhi u l p thì 2: N u Dế ể ọ

t và gán nhãn nút t là A

ộ ạ

ậ

ộ

ậ ạ

ủ

ứ

ớ

ộ

t theo t p giá tr c a A thành các t p con t t

ng ng v i m t nút con u c a t: c

ủ ươ i u là mi n giá tr A theo phân ho ch, t p con nói trên đ ượ

ề

ậ

ớ

ị

ạ ỗ ậ cung n i t t ố xem xét v i u ti p theo. Th c hi n thu t toán v i t ng nút con u c a t. ơ

ạ ớ ừ

ự

ủ

ế

ệ

ậ

ề ớ ụ ứ đ phân ho ch D 2.1. Ch n 1 thu c tính A ạ 2.2. T o phân ho ch D ị ủ 2.3. M i t p con theo phân ho ch c a D

Ví d : thu t toán Hunt ậ

ụ

ả

ộ

ệ

g c v i 10 b n ghi ừ ố ọ ướ

ị

ớ ch n thu c tính Refund c 2: ậ

ồ

trái sang ph i.

ố ừ

ủ ộ ớ

ả

ướ ả

ả

ụ

ọ

ộ

ạ

ớ

i thích ả - Xu t phát t ấ -Th c hi n b có hai giá ự tr Yes, No. Chia thành hai t p g m 3 b n ghi có ả Refund = Yes và 7 b n ghi có Refund = No ả - Xét hai nút con c a g c t ả Nút trái có 3 b n ghi cùng thu c l p Cheat=No (B c 1) nên là lá gán No (Don’t cheat). Nút ph i ả có 7 b n ghi có c No Ch n thu c tính Marital và Yes nên áp d ng b c 2. ướ Status v i phân ho ch Married và hai giá tr kia… ị

Thu t toán cây quy t đ nh ID3

ế ị

ậ

Thu c tính t

ộ

ố

t nh t: Đ đo Gini ộ

ấ

t nh t gán cho nút t. ộ ố ấ

 B c 4.1. ch n thu c tính A t ướ ọ  T n t ộ ố ộ ồ ạ  Đ đo Gini ộ

i m t s đ đo: Gini, Information gain…

[

tGini

-= 1)(

] 2)| t

jp (

ỗ ạ ộ ậ

 Đo tính h n t p c a m t t p ví d m u ụ ẫ ủ  Công th c tính đ đo Gini cho nút t: ộ

= 1

(cid:229) ứ

 Gini (t) l n nh t = 1-1/n

ủ ớ ầ

ấ ả ớ

Trong đó p(j|t) là t n su t liên quan c a l p j t ạ ấ c (v i nớ c là s các l p t ớ ạ ố ỗ ạ ấ ớ ạ i nút t i nút t): khi các b n c l p; tính h n t p cao nh t, không có

ghi t phân bi i t phân b đ u cho n ố ề ớ ệ

t c các b n ghi thu c m t l p duy ữ  Gini (t) nh nh t = 0 khi t ỏ t gi a các l p ấ ấ ả ộ ớ ả ộ

C1 C2

ố ng h p ợ C1 C2 nh t.ấ  Ví d : ụ B n tr ườ C1 0 C2 6

1 5

2 4

3 3

Gini= 0.000

Gini= 0.278

Gini= 0.444

Gini= 0.500

Chia t p theo đ đo Gini

ộ

ậ

CART, SLIQ, SPRINT

ậ c phân ho ch thành k ph n (k nút con c a t) thì ủ ầ ạ

 Dùng trong các thu t toán  Khi m t nút t đ ộ ấ ượ

GINI

)( i

ch t l ng c a vi c chia tính b ng ượ ệ ủ ằ

split

n i n

= 1

(cid:229)

ạ

ả i nút con I (c a nút t). ủ ậ ng b n ghi t ả ố ả ố ượ ạ i nút t, ủ trong đó  n là s b n ghi c a t p b n ghi t  .ni là s l

Chia t p theo đ đo Gini: Ví d

ộ

ậ

ụ

 Tính toán GINI cho Refund (Yes, No), Marital Status (Single&Divorced, Married) và Taxable Income (<80K, ‡

 Refund: 3/10 * (0) + 7/10 * (1-(3/7)2 –

80K).

 Marital Status: 4/10 * 0 + 6/10 * (1- (3/6) 2

(4/7)2) = 7/10*(24/49) = 24/70

– (3/6) 2) = 6/10 * ½ = 3/10

ộ ầ

ươ i m t s ph ộ ố

GINI

)( i

split

n i n

= 1

[

tGini

-= 1)(

] 2)| t

jp (

ế ố (cid:229)

= 1

(cid:229) ủ ậ

ằ ớ

 Taxable Income: thu c tính liên t c c n ụ chia kho ng (t n t ng pháp ồ ạ ả theo Gini, k t qu 2 thùng và 80K là m c) ả 3/10 * (0) + 7/10 * (1-(3/7)2 – (4/7)2) = 7/10*(24/49) = 24/70 Nh v y, Gini c a Refund và Taxable ư Income b ng nhau (24/70) và l n h n Gini c a Marital Status (3/10) nên ch n Refund cho g c cây quy t đ nh.

ơ ọ ủ

ế ị ố

Ch n thu c tính: Information Gain ộ  Đ đo Information Gain

ọ ộ

 Thông tin thu đ c sau khi phân ho ch t p ví d ạ ượ  Dùng cho các thu t toán ID3, h C4.5 ọ ậ

 Entropy

ậ ụ

Entropy

)( t

( jp

log)| t

( jp

)| t

 Công th c tính entropy nút t:

(cid:229)

ứ

i nút t ủ ớ ạ

Trong đó p(j|t) là t n su t liên quan c a l p j t đ không đ ng nh t t ấ i nút t. ộ

c) (v i nớ c là s các l p t

ồ  Entropy (t) l n nh t = log (n ớ ầ ấ ạ ấ ố

ả ỗ ạ ấ ớ i nút t): khi các ớ ạ c l p; tính h n t p cao nh t, không

 Entropy (t) nh nh t = 0 khi t

b n ghi t ạ có phân bi

t c các b n ghi thu c m t l p duy i t phân b đ u cho n ố ề t gi a các l p ớ ệ ấ ữ ỏ ấ ả ộ ớ ả ộ

 Tính toán entropy (t) cho m t nút t

ng t

nh Gini (t)

 L y loga c s 2 thay cho loga t ộ

ươ

ự

nhiên nh t.ấ ấ ơ ố ự

Ch n thu c tính: Information Gain ộ  Đ đo Information Gain

ọ ộ

Gain

entropy

)( t

entropy

)( i

chia

n i n

= 1

- (cid:229)

i nút t, k là s t p con trong phân ạ

ho ch, n ố ượ ố ượ ạ ng b n ghi t ố ậ ả ng b n ghi trong t p con th i. ứ ả Trong đó, n là s l i là s l

Đ đo gi m entropy sau khi phân ho ch: ch n thu c tính làm cho ộ ộ ọ ậ ạ

ấ

ấ ậ

ố ế ng ch n phân ho ch chia thành nhi u t p con ề ậ ướ ạ

chia

GainRATIO

SplitINFO

log

ả Gain đ t l n nh t. ạ ớ C4.5 là m t trong 10 thu t toán KPDL ph bi n nh t. ộ  H n ch ế: Xu h ọ ạ  C i ti n ả ế

Gain SplitINFO

n i n

= 1

 Dùng GainRatio đ kh c ph c xu h

(cid:229)

 Áp d ng: T ti n hành

ng ch n phân ho ch nhi u ụ ể ắ ướ ề ạ ọ

ự ế

t p con ậ ụ

Phân l p d a trên lu t ậ ự  Gi

ớ

 Phân l p các b n ghi d a vào t p các lu t “ki u” if … then

ớ i thi u ệ ớ

 Lu tậ

ự ể ả ậ ậ

 Lu t: <đi u ki n>

ﬁ y ậ ệ

ự ế ố ề ề ọ ộ

ủ ệ

 Ví dụ

ề Trong đó: <đi u ki n> là s k t n i các thu c tính (còn g i là tiên đ /đi u ệ ề ki n c a lu t: LHS bên trái) y là nhãn l p (còn g i là k t qu c a lu t: RHS bên ph i). ế ả ủ ậ ớ ậ ả ọ

Cheat = “No”

 S d ng lu t ậ



ộ

c g i là “b o đ m” th hi n r (b n ghi) n u các thu c tính c a r ả

ể ệ

ủ

ế

ả

ọ

ộ

M t lu t đ ậ ượ đáp ng đi u ki n c a lu t. ề ứ

ả ậ

ủ

ệ



c áp d ng cho th hi n.

Khi đó, v ph i c a lu t cũng đ ả ủ

ế

ậ

ượ

ể ệ

ụ

Refund = ‘Yes” ﬁ (Refund = “No”) (cid:217) (Marital Status = “Married”) ﬁ ử ụ

ớ

Xây d ng lu t phân l p ậ  Gi

ớ

 Tr c ti p và gián ti p ế

ự i thi u ệ ế ự  Tr c ti p ự

ế

ấ

ắ ầ ừ ộ ậ ỗ ở ộ

ọ

ộ

ở

L p các b

c h c ọ c 2-3 cho đ n khi g p đi u ki n d ng ừ ặ

ọ ả ướ

ả ế

ặ

 Trích xu t lu t tr c ti p t d li u ế ừ ữ ệ ậ ự  Ví d : ụ RIPPER, CN2, Holte’s 1R  Trích xu t lu t tr c ti p t d li u ế ừ ữ ệ ậ ự 1. B t đ u t m t t p r ng 2. M r ng lu t b ng hàm H c_m t_lu t ậ ậ ằ 3. Xóa m i b n ghi “b o đ m” b i lu t v a đ ậ ừ ượ ả 4. ệ ề  Gián ti pế

ấ

mô hình phân l p d li u khác, ch ng h n, mô ạ ẳ ớ ấ

 Trích xu t lu t t ậ ừ ế ị

 Ví d :C4.5Rule

hình cây quy t đ nh, mô hình m ng n ron, … ạ ữ ệ ơ

ụ

ng án

ộ ố

ươ

M r ng lu t: m t s ph ậ  S d ng th ng kê

ố

ở ộ ử ụ ố

 Th ng kê các đ c tr ng cho ví d ặ  Tìm đ c tr ng đi n hình cho t ng l p ớ ừ ể

ư ụ

 Thu t toán CN2 ậ ở ầ

ư ặ

ằ ế ỗ

ổ

 Kh i đ u b ng liên k t r ng: {}  B sung các liên k t làm c c ti u entropy: {A}, {A, B}… ể ự  Xác đ nh k t qu lu t theo đa s c a các b n ghi đ m b o lu t ậ ố ủ

ế ả ả ả

ﬁ

i ích thông tin FAIL

ượ

ả b i R0ở

ể ệ ể ệ ể ệ

ả

ng h p

 p0: s ố th hi n đúng đ  n0: s tố h hi n sai  P1: s ố th hi n đúng đ  n 1: s tr ợ sai đ ố ườ

à R1 ế ả ậ ị  Thu t toán RIPPER ậ  B t đ u t l pớ m t lu t r ng: {} ắ ầ ừ ộ ậ ỗ  B sung các liên k t làm c c đ i l ạ ợ ự ổ ế  R0: {} => l p ớ (lu t kh i đ ng ở ộ ) ậ  R1: {A} => l p (quy t c sau khi thêm liên kêt) ắ ớ  Gain (R0, R1) = t [log (p1 / (p1 + n1)) - log (p0 / (p0 + n0))] v i ớ t: s ố th hi n đúng đ m b o ể ệ ả

ả b i R1ở ả b i R1ở

ả c hai R0 v ả c b o đ m ả c ượ đ m b o ả c b o đ m ượ c ượ đ m b o ả

Lu t phân l p: t

cây quy t đ nh

ớ

ậ

ừ

ế ị

ng đi t

T p lu t ậ ậ t kê các đ Li ệ

ườ

g c ừ ố

Sinh lu t gián ti p: C4.5rules

ế

ậ

cây quy t đ nh ch a c t t a

ắ ỉ

ế ị

ậ ừ

ớ

ậ

→ y, trong đó A’ nh n đ ậ c t ượ ừ A b ng ằ

ỏ

ộ l ỷ ệ ỗ

 So sánh t  Lo i b các r’ có l  L p l

ạ ỏ ỗ

 Trích xu t lu t t ấ  V i m i lu t, r: A → y ỗ  Xem xét lu t thay th r’: A’ ế ậ cách b đi m t liên k t ế i r so v i các r’ l ớ i th p h n r ấ i cho đ n khi không c i thi n đ ế ắ

ế ặ ạ ể

ậ

ệ ằ ơ ả  Thay th s p x p theo lu t b ng s p x p theo t p con ậ c l ượ ỗ ổ ắ i t ng th ế

ộ ế ả ớ

ậ ớ c a m i t p con ỗ ậ ả ủ

= L(l ộ ỗ

ư ừ ệ ộ

ế l p) c a lu t (th t ứ ự ớ ậ ủ  M i t p con là m t t p các lu t v i cùng m t k t qu (l p) ộ ậ ỗ ậ  Tính toán đ dài mô t ộ  Đ dài mô t ả  g : tham s đ m s hi n di n c a các thu c tính d th a trong ố ế ậ

ủ m t t p lu t (giá tr chu n, g=0.5) i) + g* L(mô hình) ự ệ ẩ ộ ậ ị

C4.5rules: Ví dụ

Name

Give Birth

Lay Eggs

Can Fly

yes no no no

yes human no python no salmon yes whale no frog no komodo yes bat no pigeon yes cat leopard shark yes turtle penguin porcupine eel salamander gila monster platypus owl dolphin eagle

no no yes no no no no no yes no

no yes yes no yes yes no yes no no yes yes no yes yes yes yes yes no yes

no no no no no no yes yes no no no no no no no no no yes no yes

Live in Water Have Legs no no yes yes sometimes yes yes no yes no yes no yes no yes no sometimes yes sometimes yes yes no yes no sometimes yes yes no yes no yes no no yes yes no

Class mammals reptiles fishes mammals amphibians reptiles mammals birds mammals fishes reptiles birds mammals fishes amphibians reptiles mammals birds mammals birds

C4.5rules: Ví dụ

C4.5rules:

(Give Birth=No, Can Fly=Yes) ﬁ

Birds

Give Birth?

(Give Birth=No, Live in Water=Yes) ﬁ

Fishes

Yes

(Give Birth=Yes) ﬁ

Mammals

(Give Birth=No, Can Fly=No, Live in Water=No) ﬁ

Reptiles

Mammals

( ) ﬁ

Amphibians

Live In Water?

RIPPER:

Yes

(Live in Water=Yes) ﬁ

Fishes

(Have Legs=No) ﬁ

Reptiles

Sometimes

Fishes

Amphibians

(Give Birth=No, Can Fly=No, Live In Water=No)

Can Fly?

ﬁ

Reptiles

(Can Fly=Yes,Give Birth=No) ﬁ

Birds

Yes

() ﬁ

Mammals

Birds

Reptiles

Phân l p Bayes ớ

 Gi

ớ

i thi u ệ

ự

ộ

ớ

)

ACP )

(

 Khung xác su t đ xây d ng b phân l p ấ ể  Xác su t có đi u ki n ấ ệ ề Hai bi n c A và C ố

ế

)

CAP

(

)

CAP ( , AP ( ) , CAP ( CP ( )

 Đ nh lý Bayes:

ị

P(c|x) = P(x|c).P(c)/P(x) ớ

ằ

t c các l p ấ ả ớ

ấ Tìm c sao cho P(x|

ộ ớ

ủ

ệ

ấ

 P(c): t n su t xu t hi n c a các tài li u thu c l p c ấ  V n đ : làm th nào đ tính P(x|c)?

 P(x) b ng nhau cho t  Tìm c sao cho P(c|x) l n nh t c).P(c) l n nh t ấ ớ ầ ề

ể

ế

ấ

Đ nh lý Bayes: Ví d

ị

ụ

 M t bác s bi

t ỹ ế

 B nh nhân viêm màng não có tri u ch ng c ng c S|M:

ứ

ệ

ổ

ộ ệ 50%

ộ ệ ộ ệ

ổ

 Xác su t m t b nh nhân b viêm màng não M là 1/50.000 ị  Xác su t m t b nh nhân b c ng c S là 1/20 ị ứ  M t b nh nhân b c ng c h i xác su t anh/cô ta b ị ấ ị ứ

ấ ấ ộ ệ

ổ ỏ

viêm màng não ?

(

)

/15.0

50000

SMP

(

)

0002

MPMSP ) SP )(

20/1

Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data Mining (Chapter

Addison Wesley, 2005,

5: Classification: Alternative Techniques), http://www.cs.uu.nl/docs/vakken/dm/dmhc13.pdf

Phân l p Bayes ớ

 Các thu c tính (bao g m nhãn l p) là các bi n ồ

ế

ớ

ộ

ẫ

 Cho m t b n ghi v i các giá tr thu c tính (A

ng u nhiên. ộ ả

ộ

ớ

ị

1, A2,

…, An)  C n d báo nhãn c ự ầ  Tìm l p c đ c c đ i xác su t P(C|A ạ

ể ự

ấ

ớ

1, A2, …, An)

 Có th tính xác su t P(C|A

d li u

ấ

ừ ữ ệ

1, A2, …, An) t

ể h c? ọ

Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data Mining (Chapter

Addison Wesley, 2005,

5: Classification: Alternative Techniques), http://www.cs.uu.nl/docs/vakken/dm/dmhc13.pdf

Phân l p Naïve Bayes

ớ

 Gi

ả  gi

ộ

ệ ủ ữ ả

ố ượ

ấ ớ

ấ ộ ậ ng:

thi t Naïve Bayes: ế t đ c l p: xác su t xu t hi n c a thu c thi ế ộ ậ ả ng đ c l p v i ng c nh và v tính trong đ i t ị trí c a nó trong đ i t ố ượ

ủ

(cid:229)=

(

t ),

()

(

)

| xcp

xTpTxcp

inT

ớ

ụ exam = Dlearn + Dtest

v ng V = {f

e ng

Phân l p văn b n Naïve Bayes ả  Cho  T p ví d D ậ  T p t ậ ừ ự  T p l p C= {C1, C2, …, Cn} v i m i C ậ ớ

1, f2, …, f||V||} ớ

i > 0

 Tính xác su t tiên nghi m ấ

ệ

ưỡ ộ ỗ i m t ng

learn

ậ

 Trên t p ví d h c D ụ ọ  p(Ci) = Mi/M, M= ||Dlearn||, Mi = ||Doc ˛  Xác su t m t đ c tr ng (t ) f ộ ặ

Dlearn / Doc ˛

(

)

, Cf j

ư ấ Ci|| +

)

CfP j

TF n

(

)

ừ j thu c l p C: | ộ ớ (

, Cj l

= 1

( FTF

Doc

)

 Cho tài li u Doc m i ớ ệ

( Cp

(

)

(cid:229)

( CFp j

VF j

( CP

Doc

)

(

Doc

)

(cid:213) ˛ ệ

 Tính xác su t h u nghi m ấ ậ  N u P(C|Doc) >

( Cp

(

)

( CFp j

= 1

VF j

e ế (cid:229) (cid:213) ˛ thì Doc ˛ C!

Phân l p k-NN ớ

* YX l l

(

)

Cos

(

)

, DDoc i

(cid:229)

2 l

Y l

 Cho tr

cướ

(cid:229) (cid:229)

ữ ệ ư

ng d li u bi u di n b n ghi các đ c tr ng ả ng t ễ ể ặ ươ ặ (nh trên) ư ự

Ơ ơ ầ ề

ộ ậ ộ ộ ố  Phân l p đ i t ớ

c bi u di n ễ ể i t ớ ấ ả ữ ệ

- M t t p D các đ i t ố ượ - M t đo đo kho ng cách ( c lit) ho c t ả - M t s k > 0 (láng gi ng g n nh t ấ ng m i Doc đ ượ ớ ng t ) t ộ ươ ầ

ố ượ - Tính kho ng cách (đ t Doc t ả ự ừ - Tìm k d li u thu c D g n Doc nh t ấ ộ ữ ệ - Dùng nhãn l p c a k-láng gi ng g n nh t đ xác đ nh nhãn l p ầ ủ

t c d li u thu c D ộ

ề ớ ớ ị

c a Doc: nhãn nhi u nh t trong k-láng gi ng g n nh t ấ ủ ề ấ ầ ấ ể ề

Phân l p k-NN: Ví d

ớ

ụ

(a) 1-nearest neighbor

(b) 2-nearest neighbor

ườ

 Ba tr -

ề

ng nh nhau, ch n nhãn ố ượ ư

ng h p nh hình v ẽ 1-NN: Ch n l p “-”: láng gi ng có nhãn “-” là nhi u nh t ấ ề 2-NN: Ch n l p “-”: hai nhãn có s l ọ có t ng kho ng cách g n nh t ấ 3-NN: Ch n l p “+”: láng gi ng có nhãn “+” là nhi u nh t ấ ề

ợ ọ ớ ọ ớ ả ọ ớ

ầ ổ

ề

Thu t toán SVM

ậ

 Thu t toán máy vector h tr (Support Vector Machine – ỗ ợ

c Corters và Vapnik gi

i thi u vào năm 1995.

ậ SVM): đ

ượ

ớ

ệ

i quy t các bài toán v i d li u có

ớ ữ ệ

ế

 SVM r t hi u qu đ gi ấ ệ ề ớ

ả ể ả ư

s chi u l n (nh các vector bi u di n văn b n). ố

ể

ễ

ả

Thu t toán SVM

ậ

 T p d li u h c: D= {

ữ ệ

ậ

ọ

(Xi, Ci), i=1,…n}

ng hay âm

ữ ệ

ị

ươ

 Ci Є {-1,1} xác đ nh d li u d

 Tìm m t siêu ph ng:

ẳ

ộ

αSVM .d + b phân chia d ữ

li u thành hai mi n. ệ

ề

 Phân l p m t tài li u m i: xác đ nh d u c a

ủ

ệ

ấ

ớ

ộ

ớ

ị

 f(d) = αSVM .d + b

 Thu c l p d

ng n u

ộ ớ

ươ

ế f(d) > 0

 Thu c l p âm n u

ộ ớ

ế f(d) < 0

Thu t toán SVM

ậ

Thu t toán SVM

ậ

 N u d li u h c là tách r i tuy n tính:

 C c ti u: ự

ể

(1)

1 2

a� = � � � �

� � � � �

 Th a mãn: ỏ

+ (cid:0)

" = i

c i

a� � �

n d b . 1,....,  N u d li u h c không tách r i tuy n tính: thêm bi n { ờ

(2) ế ξ1… ξn}:

ữ ệ ế ế ọ ờ

� � � ế

 C c ti u:

ự

ể

(3)

x(cid:0) C

 Th a mãn: ỏ

ữ ệ ế ọ

(

)

1,....,

(cid:0) -

1 2 c i x

+ d . b " = 0 i

1 1,....,

" = n

i (4)

(cid:0)

Phân l p bán giám sát

ớ

 Gi

ớ

i thi u phân l p bán giám sát ớ

ệ

 Khái ni m s b

ơ ộ

ệ

 T i sao h c bán giám sát

ạ

ọ

 N i dung phân l p bán giám sát

ộ

ớ

 M t s cách ti p c n c b n

ộ ố

ơ ả

ế

ậ

 Các ph

ng án h c bán giám sát phân l p

ươ

ọ

ớ

 Phân l p bán giám sát trong NLP

ớ

H c bán giám sát:Tài li u tham kh o

ệ

ả

ọ 1. Xiaojin Zhu (2006 ***). Semi-Supervised Learning

Literature Survey, 1-2006. (Xiao Zhu [1])

http://www.cs.wisc.edu/

jerryzhu/pub/ssl survey.pdf

∼

Zhou, D., Huang, J., & Scholkopf, B. (2005). Learning from labeled and unlabeled data on a directed graph. ICML05, 22nd International Conference on Machine Learning. Bonn, Germany.

Zhou, Z.-H., & Li, M. (2005). Semi-supervised regression InternationalJoint Conference on

with co-training. Artificial Intelligence (IJCAI).

Zhu, X. (2005). Semi-supervised learning with graphs. Doctoral dissertation, Carnegie Mellon University (mã s ố CMU-LTI-05-192).

1. Olivier Chapelle, Mingmin Chi, Alexander Zien (2006) A Continuation Method for Semi-Supervised SVMs. Proceedings of the 23rd International Conference on Machine Learning, Pittsburgh, PA, 2006. và các tài li u khác

ệ

S b v h c bán giám sát

ơ ộ ề ọ

ọ

 H c bán giám sát là gì ?  H c giám sát: t p ví d h c đã đ

Xiao Zhu [1] FQA ượ

c gán nhãn (ví d g n ậ ọ ụ ắ

nhãn) là t p các c p (t p thu c tính, nhãn) ặ ậ ộ ụ ọ ậ

chuyên gia ﬁ

ố đ ng sinh corpus song hi u qu ch a cao

t n th i gian, ti n ề ư

ờ ệ

ả

ﬁ



ế

ỏ



 Th công: khó khăn  T đ ng: nh t ư ự ộ  ví d ch a g n nhãn ắ ư ậ ﬁ  D thu th p ử ử

ự ớ

ả

 ví d g n nhãn ụ ắ ủ ự ộ ụ ễ x lý ti ng nói: bài nói nhi u, xây d ng tài nguyên đòi h i công phu ề x lý văn b n: trang web vô cùng l n, ngày càng đ có đi u ki n ti n hành t

 Có s n ẵ ﬁ

nhi uề

ự ộ ệ ề

c m r ng ở ộ ượ đ ng g n nhãn ắ ư

ế  H c bán giám sát: dùng c ví d có nhãn và ví d ch a ả ụ ụ

ớ ố ơ

ọ

ỉ

ng kh i l

ọ ắ

t h n so v i ch dùng h c giám sát: h c ượ ề

ố ượ

ớ ề

ệ

g n nhãn  T o ra b phân l p t ộ ạ bán giám sát đòi h i đi u ki n v dung l ỏ

C s c a h c bán giám sát ọ

ơ ở ủ

h t ánh x gán

ạ

ễ

ể

ả ế

ẳ

 Bi u di n d li u ch a mô t ữ ệ ữ ệ ị

ễ

ể

ạ

ặ

nhãn trên d li u  ch ng h n, ngh ch lý “hi u qu nh nhau” trong bi u di n văn b n ệ ạ ả ả  Ánh x gán nhãn có liên quan mô hình d li u ữ ệ ự ﬁ ng t ) ươ t d thi nhiên ho c gi ế ữ ả

ự

ặ

(mô hình / đ c tr ng/ nhân / hàm t ư mô hình đã có theo t li u tuân theo. ệ

Hi u l c c a h c bán giám sát ọ

ệ ự

ủ

 D li u ch a nhãn không luôn luôn hi u qu

ệ gi m hi u

ư thi

ợ ﬁ t mô hình không phù h p

ế

ả ệ

ả

ữ ệ  N u gi ế quả

ệ

ề

ươ

ề

ế

ề

 M t s ph ộ ố ị

ng pháp c n đi u ki n v mi n quy t ề

ầ ậ ộ ỗ ợ

ề

ơ ớ ằ

đ nh: tránh mi n có m t đ cao:  Transductive SVM (máy h tr vector lan truy n)  Information Regularization (quy t c hóa thông tin)  mô hình quá trinh Gaux v i nhi u phân l p b ng không  ph ả

 “T i” khi dùng ph

ng pháp này song l

t” khi

i “t ạ ố

ắ ễ ng pháp d a theo đ th v i tr ng s c nh là kho ng ồ ị ớ ọ ớ ố ạ ự

dùng ph

ươ ng pháp khác

ươ

ươ cách ồ

ng pháp h c bán giám sát

ọ

ng pháp h c bán giám sát đi n hình

ể

ọ

ộ

Ph ươ  Các ph ươ  EM v i mô hình tr n sinh ớ  Self-training  Co-training  TSVM  D a trên đ th ồ ị ự  ...

thi

 So sánh các ph  Đòi h i các gi ả ỏ

ạ

ả

ế

hình phù h p c u trúc d li u: khó ki m nghi m

ợ

t mô ệ

ự

ng pháp ươ t mô hình m nh. Gi thi ế ể ấ ướ ố

ữ ệ ng l a ch n ọ ộ . t: dùng EM v i mô hình sinh tr n

ớ

ầ ng t

ng t

ẽ ộ ớ

ặ ế

ể

ớ

i m t l p: d a trên đ th ồ ị ự

ấ

 M t s đ nh h ộ ố ị  L p ớ (cid:219) phân c m t ụ  Đ c tr ng phân thành hai ph n riêng r : co-training ư h  N u hai đi m t ự ướ ươ  Đã s d ng SVM thì m r ng TSVM ở ộ ử ụ  Khó nâng c p h c giám sát đã có: dùng self-traning ọ  …

ng pháp h c bán giám sát

ươ

ọ

ư  Ho c bi n d ng ho c thay đ i th t

Ph  Dùng d li u ch a gán nhãn ổ ạ

ữ ệ ế d li u có nhãn

thi gi ứ ự ả ặ ế t thu nh ch ỉ ờ

ế ướ ạ

i d ng p(y|x) còn d li u ch a có nhãn p(x) ữ ệ

ớ

ộ ươ

 Mô t  Gi  Mô hình sinh có tham s chung phân b k t n i p(x, y) ố ế ố ố  Mô hình tr n v i EM m r ng thêm self-training ở ộ  Nhi u ph t: TSVM, quy t c hóa thông tin, ng pháp là phân bi ắ ề

ơ ự

chung t d thi ặ ữ ệ ả ả

ọ

ệ quá trình Gaux , d a theo đ th ồ ị  Có d li u không nhãn: nh n đ ượ t “h c lan truy n” v i “h c bán giám sát” ớ ế

ọ ề

ề ạ

c xác su t p(x) ấ ậ

ớ ọ

ọ ọ

ụ ữ ệ ữ ệ

ậ

ộ

ạ

ả

 Lan truy n đ thu h p l

 dùng ví d có / không có nhãn,  “h c d li u nhãn/không nhãn,  “h c d li u phân l p/có nhãn b ph n”. ớ  Có c lan truy n ho c quy n p. ặ ề ẹ ạ

ữ ệ  Phân bi ệ  Đa d ng v cách g i. H n ch bài toán phân l p. ạ  “Bán giám sát”

ề i cho quy n p: h c ch d li u s n. ọ ỉ ữ ệ ẵ

ể Quy n p: có th liên quan t ạ i d li u ch a có. ể ạ ớ ữ ệ ư

Mô hình sinh: Thu t toán EM

ậ

 S bơ ộ

ớ ể

ạ

ữ ệ

 Lý t

ng nhi u d li u ch a nhãn cho P(x|y) mô hình c phân thành các thành ề ệ ấ

 Mô hình s m nh t, phát tri n lâu nh t ấ ấ  Mô hình có d ng p(x,y) = p(y)*p(x|y)  V i s l ư ề ớ ố ượ tr n đ ng nh t. Mi n tài li u đ ượ ồ ộ ph n, ầ ưở

ng có ồ ng hóa tính "Đ ng nh t": ch c n m t đ i t ấ ộ ố ượ ỉ ầ

 Tính đ ng nh t ấ ồ

nhãn cho m i thành ph n ỗ ầ

ủ ấ ầ

 Là tính ch t c n có c a mô hình  Cho h phân b {p

„ q ấ ế q ố b } là đ ng nh t n u

ố ị ớ ộ „ pq 2 2 thì pq 1 tính kh tách ả

ọ ồ ầ (cid:222) i m t hoán đ i v trí các thành ph n i các thành ph n cho t c a phân b t ủ ố ớ ầ

Mô hình sinh: Thu t toán EM  Tính xác th c c a mô hình

ậ ự ủ

 Gi

thi

t mô hình tr n là chính xác

ả

ế

ộ

không nhãn s làm tăng đ chính xác phân l p

ộ

d li u ữ ệ ớ

ẽ  Chú ý c u trúc t

ấ

ố

t mô hình tr n: n u tiêu đ ề

ế

ộ

ượ

c chia thành các tiêu đ con thì nên mô hình ề

ề

đ hóa thành đa chi u thay cho đ n chi u ươ ự

ụ

ề

 Khi mô hình tr n chính xác

ề  C c đ i EM đ a ph ị ạ  Mi n áp d ng ộ

 Ký hi uệ

ﬁ

 D: t p ví d đã có (có nh n /ch a có nhãn) ư  DK: t p ví d có nhãn trong D (|D

K| << |D|)

ẵ

ụ ụ ậ ậ

Mô hình sinh: Thu t toán EM

ậ

ậ ệ

ộ ố ị và M-b

 N i dung thu t toán ậ cướ

1: C đ nh t p tài li u không nhãn DU ˝ D \ DK dùng trong E-b c ướ

ự

0 ả ả

ả do ế

ế ệ d ˛ DU do

(c|d,Q ớ Bayes th nh t xác đ nh P ứ ấ ị

t do

q ỗ ớ c và t ừ c: xác đ nh ị ứ ự ể khóa c,t dùng công th c (*) đ xây d ng mô hình

ầ Q 2: dùng DK xây d ng mô hình ban đ u 3: for i = 0, 1, 2, . . . cho đ n khi k t qu đ m b o 4: for m i tài li u ỗ 5: E-b c: dùng phân l p ướ 6: end for 7: for m i l p 8: M-b ướ i+1 9: end for 10: end for

Mô hình sinh: Thu t toán EM

ậ

 M t s v n đ v i EM

ộ ố ấ ạ

ộ

ề ớ ụ ị

ị

ế

ị

ệ

 Ph m vi áp d ng: mô hình tr n chính xác  N u c c tr đ a ph ươ ự ữ ệ ả

ầ

ng khác xa c c tr toàn c c ụ ự thì khai thác d li u không nhãn không hi u qu ả  "K t qu đ m b o yêu c u": đánh giá theo các ng, chính xác, F

đ đo h i t

ả ả 1... ồ ưở  M t s v n đ khác c n l u ý: ề

ầ ư  Thu t toán nhân là Bayes naive: có th ch n thu t toán

ế ộ ộ ố ấ ậ c b n khác ơ ả ọ

 Ch n đi m b t đ u b ng h c tích c c ự

ể ậ ọ

ắ ầ ể ằ ọ

Mô hình sinh: Thu t toán khác

ậ

 Phân c m - và - Nhãn

ụ

ử ụ

ộ

ụ

 S d ng phân c m cho toàn b ví d ụ  c d li u có nhãn và không có nhãn ả ữ ệ test đ đánh giá  dành t p Dậ

 Đ chính xác phân c m cao

ụ

ộ

ể

ợ ữ ệ

ọ

 Mô hình phân c m phù h p d li u ụ  Nhãn c m (nhãn d li u có nhãn) làm nhãn d li u khác  Ph ng pháp nhân Fisher cho h c phân ươ bi tệ  Ph

ng pháp nhân là m t ph

ng pháp đi n

ươ

ể

ộ

hình

ố

c chuy n đ i thành vector

ượ

ể

ổ

 Nhân là g c c a mô hình sinh ủ  Các ví d có nhãn đ ụ Fisher đ phân l p ể

ớ

ụ ữ ệ ữ ẹ

Self-Training

 Gi

ớ

i thi u ệ ậ

ỹ ổ ế

 Là k thu t ph bi n trong SSL ươ

ng là d ng đ c bi t c a seft-training ị ạ ặ ệ ủ

ậ ậ

)

 EM đ a ph  N i dung ộ G iọ L : T p các d li u gán nhãn. ữ ệ U : T p các d li u ch a gán nhãn ữ ệ ư L pặ (cho đ n khi U = ế

ệ

ộ ể ậ

˝ ữ ệ ộ Hu n luy n b phân l p giám sát h trên t p L ậ ớ S d ng h đ phân l p d li u trong t p U ớ U có đ tin c y cao nh t: Tìm t p con U’ ấ ậ

L U

ng đ

c áp d ng cho các bài toán NLP

ấ ậ

 Th t c "bootstrapping"  Th ượ

ụ

ấ ử ụ ậ L + U’ (cid:222) U – U’ (cid:222) V n đ t p U' có "đ tin c y cao nh t" ộ ề ậ ấ ủ ụ ườ

 T t

ư ưở

Co-Training ng ộ ữ ệ

 M t d li u có hai khung nhìn  Ví d , các trang web

ụ ộ

 N i dung văn b n ả  Tiêu đ văn b n ề

ả

Co-Training

 Mô hình thu t toán

ậ

Co-Training

ề

 Đi u ki n d ng ệ ư ạ ớ

ừ ữ ệ ặ

 T p d li u gán nhãn có nh h

ng l n đ n

ỗ  ho c t p d li u ch a gán nhãn là r ng  ho c s vòng l p đ t t ng đ i ng c xác đ nh tr ượ ưỡ ị c ướ

ả

ưở

ế

ớ

ặ ậ ặ ố  M t s l u ý ộ ố ư ậ

ữ ệ co-training  Quá ít: không h tr co-training  Quá nhi u: không thu l

ỗ ợ

 C s tăng hi u qu co-training: thi

t l p

ế ậ

ề

ệ

co-training i t ợ ừ ả

ơ ở tham số  Kích c t p d li u gán nhãn ữ ệ  Kích c t p d li u ch a gán nhãn ữ ệ  S các m u thêm vào sau m i vòng l p

 B phân l p thành ph n r t quan tr ng

ặ ố

ộ

ọ

ỡ ậ ỡ ậ ẫ ớ ỗ ầ ấ

Ch n thay đ i mi n dày đ c

ổ

ề

ặ

t làm vi c trên p(y|x)

ệ

ươ tr c ti p

 Transductive SVMs (S3VMs) ng pháp phân bi ệ ế

 Ph ự

ng thích

ươ

đ a ư

p(x) ra kh i mi n d y đ c

 Khi p(x) và p(y|x) không t ặ ỏ

ề

ầ

 Quá trình Gaux )ơ

ﬁ

Mô hình đ thồ ị

ể

ễ

ạ

h t ánh x gán ệ

ả ế ị

ư ẳ

 Bi u di n d li u ch a mô t ữ ệ ữ ệ (ch ng h n, ngh ch lý “hi u qu ả

nhãn trên d li u nh nhau” trong bi u di n văn b n) ễ

ạ

ặ

mô hình đã có theo t

ự

 Ánh x gán nhãn có liên quan mô hình d ữ ng li u (mô hình / đ c tr ng/ nhân / hàm t ươ ệ t ) ự ﬁ nhiên ho c gi ả ặ thi

t d li u tuân theo.

ế ữ ệ

ạ ả ư ể

Bài giảng Khai phá dữ liệu web (PGS.TS. Hà Quang Thụy) - Chương 5. Phân lớp

BÀI GI NG NH P MÔN KHAI PHÁ D LI U

Ữ Ệ

Ả

Ậ

CH

NG 5. PHÂN L P

ƯƠ

Ớ

TR

Ạ Ọ

ƯỜ

PGS. TS. HÀ QUANG TH YỤ HÀ N I 9-2011 NG Đ I H C CÔNG NGH Ệ Đ I H C QU C GIA HÀ N I Ộ Ố Ạ Ọ

N i dung

ộ

Bài toán phân l pớ

Phân l p: Quá trình hai pha

ớ

Ví d phân l p: Bài toán cho vay

ụ Tid

ớ Refund

Phân l p: Quá trình hai pha

ớ

Phân l p: Quá trình hai pha

ớ

Attrib2

Attrib3 Class

Tid Attrib1

No

No

No

No

Yes

No

No

Yes

Learn Model

No

Yes

Model

Apply Model

Attrib2

Attrib3 Class

Tid Attrib1

?

?

?

?

?

Các lo i phân l p

ớ

ạ

Các v n đ đánh giá mô hình

ề

ấ

Đánh giá phân l p nh phân

ớ

ị

Đánh giá phân l p nh phân

ớ

ị

L p d báo ự

ớ L p = 1 f11 f01

So sánh hai ph

ng án

ươ

Đánh giá phân l p đa l p

ớ

ớ

Đánh giá phân l p đa l p

ớ

ớ

Đánh giá phân l p đa l p

ớ

ớ

Các k thu t phân l p ậ

ớ

ỹ

Phân l p cây quy t đ nh

ế ị