BÀI 3 (ti p): H C KHÔNG GIÁM SÁT ế Ọ& BÁN GIÁM SÁT

N i dungộ

1. Các khái ni m c b nệ ơ ả

2. Thu t toán ậ k-means

3. Bi u di n c mể ễ ụ

4. Phân c m phân c pụ ấ

5. Hàm kho ng cáchả

6. Chu n hóa d li uẩ ữ ệ

7. X lý nhi u lo i thu c tínhử ề ạ ộ

8. Ph ng pháp đánh giáươ

9. Khám phá các l và vùng d li uỗ ữ ệ

10. H c LUọ

11. H c PUọ

1. Các k/n c b nơ ả

● Phân c m là quá trình t ch c các ph n t DL thành các nhóm ụ ổ ứ ầ ửtrong đó các thành viên có tính ch t t ng t nhau. M i c m bao ấ ươ ự ỗ ụg m các ph n t DL t ng t nhau và khác bi t so v i các ph n t ồ ầ ử ươ ự ệ ớ ầ ửDL thu c các nhóm khácộ

● ng d ng: phân c m nhóm khách hàng d a theo s thích đ thi t Ứ ụ ụ ự ở ể ếk chi n l c marketing; phân c m khách hàng d a theo ch s c ế ế ượ ụ ự ỉ ố ơth đ b trí s n xu t qu n áo; phân c m bài báo đ t ng h p tin ể ể ố ả ấ ầ ụ ể ổ ợt c; ...ứ

2. Thu t toán ậ k-means

Algorithm k-means(k, D)1 ch n k đi m DL làm centroid (trung tâm c a c m)ọ ể ủ ụ2 repeat3 for m i đi m DL ỗ ể x ∈ D do4 tính kho ng cách t ả ừ x t i m i centroid;ớ ỗ5 gán x cho centroid g n nh tầ ấ // m t centroid đ i di n cho m t c mộ ạ ệ ộ ụ6 endfor7 tính toán l i các centroid d a trên các c m hi n t iạ ự ụ ệ ạ8 until the stopping criterion is met

Đi u ki n h i t :ề ệ ộ ụ1. S đi m DL đ c gán l i nh h n m t ng ngố ể ượ ạ ỏ ơ ộ ưỡ2. S centroid b thay đ i nh h n m t ng ngố ị ổ ỏ ơ ộ ưỡ3. T ng bình ph ng l i nh h n m t ng ngổ ươ ỗ ỏ ơ ộ ưỡ

trong đó:- k là s l ng c mố ượ ụ- C

j là c m th ụ ứ j

- mj là centroid c a ủ C

j (véc-t trung bình c a các đi m DL thu c ơ ủ ể ộ C

j)

- dist(x, mj) là kho ng cách gi a ả ữ x và m

j

+

+

+

+

+

+

++ + +

+ + + +

(A) L a ch n ng u ự ọ ẫnhiên k centroid

Vòng l p 1:ặ(B) Gán c mụ

Vòng l p 2:ặ(D) Gán c mụ

Vòng l p 3:ặ(F) Gán c mụ

(C) Tính l i centroidạ

(E) Tính l i centroidạ

(G) Tính l i centroidạ

Algorithm disk-k-means(k, D)1 Ch n ọ k đi m DL làm centroid ể m

j, j = 1, ..., k;

2 repeat3 kh i t o ở ạ s

j ← 0, j = 1, ..., k; // 0 là véc-t v i các thành ph n b ng 0ơ ớ ầ ằ

4 kh i t o ở ạ nj ← 0, j = 1, ..., k; // n

j là s đi m trong c m ố ể ụ j

5 for m i đi m DLỗ ể x ∈ D do6 j ← argmin dist(x ,m

i);

7 gán x cho c m ụ j;8 s

j ← s

j + x;

9 nj ← n

j + 1;

10 endfor11 m

j ← s

j / n

j, j = 1, ..., k;

12 until đ/k d ng th a mãnừ ỏ

● O(tkn) trong đó t là s vòng l p, ố ặ k là s c m, ố ụ n là s ví d ố ụtrong DL hu n luy nấ ệ

● Ch áp d ng cho DL t n t i mean, đ i v i DL r i r c, áp ỉ ụ ồ ạ ố ớ ờ ạd ng thu t toán ụ ậ k-modes

● Giá tr ị k cho tr cướ● Nh y c m v i các đi m DL ngo i lai (outlier) (các đi m n m ạ ả ớ ể ạ ể ằ

xa các đi m còn l i trong t p DL)ể ạ ậ● Nh y c m v i vi c kh i t o (th ng ti n đ n c c tr đ a ạ ả ớ ệ ở ạ ườ ế ế ự ị ị

ph ng)ươ● Không phù h p v i các c m có d ng siêu c uợ ớ ụ ạ ầ

+ +

đi m ngo i laiể ạ

+ +

đi m ngo i laiể ạ

a) Phân c m không mong mu nụ ố

a) Phân c m lý t ngụ ưở

+

+

+

+

+

+

(A) Kh i t o ng u nhiênở ạ ẫ

(B) Vòng l p 1ặ (C) Vòng l p 2ặ

+

+

(A) Kh i t o ng u nhiênở ạ ẫ

+

+

(B) Vòng l p 1ặ (B) Vòng l p 2ặ

+ +

+

+

(A) Hai c m siêu c u t nhiênụ ầ ự (A) K t qu c a ế ả ủ k-means (k = 2)

3. Bi u di n c mể ễ ụ

● Các cách bi u di n ph bi n:ể ễ ổ ế– D a trên centroid: Phù h p v i c m d ng ê-líp ự ợ ớ ụ ạ

ho c d ng c uặ ạ ầ

– D a trên mô hình phân lo i: G/s m i c m ng v i ự ạ ỗ ụ ứ ớm t l p v i các thành viên c a c m có nhãn l p ộ ớ ớ ủ ụ ớt ng ngươ ứ

– D a trên các giá tr ph bi n trong c m: Phù h p ự ị ổ ế ụ ợv i giá tr r i r c, bao g m văn b nớ ị ờ ạ ồ ả

1 1 11

1111

1 1

1 1 3 3 3

33

22

2 2

22

2 x

1.5

y

x ≥ 2 → c m 1ụX >2, y > 1.5 → c m 2ụX > 2, y ≤ 1.5 → c m 3ụ

4. Phân c m phân c pụ ấ

● DL đ c chia thành m t chu i các ượ ộ ỗc m l ng nhau theo c u trúc cây ụ ồ ấ(dendogram)

● Lá c a cây là các đi m DL, g c ủ ể ốch a m t c m duy nh t, các nút ứ ộ ụ ấtrung gian ch a các nút c m conứ ụ

● Phân c m t d i lên: M t c p ụ ừ ướ ộ ặc m g n nh t t i m i m c đ c ụ ầ ấ ạ ỗ ứ ượg p l i m c ti p theo. Quá trình ộ ạ ở ứ ếl p l i cho t i khi ch còn m t c mặ ạ ớ ỉ ộ ụ

● Phân c m t trên xu ng: M t c m ụ ừ ố ộ ụban đ u ch a toàn b DL. C m ầ ứ ộ ụnày đ c chia thành các c m con. ượ ụM t c m con đ c chia m t cách ộ ụ ượ ộđ quy t i khi ch còn m t ph n tệ ớ ỉ ộ ầ ử

9

8

6 7

1 2 3 4 5

Algorithm Agglomerative(D)1 Coi m i đi m DL trong ỗ ể D là m t c m,ộ ụ2 Tính toán các c p kho ng cách c a ặ ả ủ x

1, x

2, ..., x

n ∈ D;

3 repeat4 tìm hai c m g n nhau nh t;ụ ầ ấ5 k t h p hai c m thành c m m i ế ợ ụ ụ ớ c;6 tính toán kho ng cách t ả ừ c t i các c m khác;ớ ụ7 until ch còn l i m t c mỉ ạ ộ ụ

p1 p

2

p3

p4

p5

13 2

4

4

3

1 2

p1

p2

p3

p4

p5

● P2 liên k t đ n: ế ơ– K/c gi a hai c m là k/c ng n nh t gi a hai đi m DL c a m i c mữ ụ ắ ấ ữ ể ủ ỗ ụ

– Phù h p v i các c m không có d ng ê-lípợ ớ ụ ạ

– Có th gây ra hi u ng chu i do nhi u trong DLể ệ ứ ỗ ễ

– Đ ph c t p tính toán: O(ộ ứ ạ n2)

● P2 liên k t đ y đ :ế ầ ủ– K/c gi a hai c m là k/c l n nh t gi a hai đi m DL c a m i c mữ ụ ớ ấ ữ ể ủ ỗ ụ

– Không g p hi u ng chu i nh ng nh y c m v i đi m DL ngo i laiặ ệ ứ ỗ ư ạ ả ớ ể ạ

– Đ ph c t p tính toán O(ộ ứ ạ n2 log n)

● P2 liên k t trung bình:ế– K/c gi a hai c m là k/c trung bình gi a hai đi m DL c a m i c mữ ụ ữ ể ủ ỗ ụ

– Đ ph c t p tính toán: O(ộ ứ ạ n2log n)

Hi u ng chu i c a pệ ứ ỗ ủ 2 liên k t đ nế ơ

K/q c a pủ 2 liên k t đ y đế ầ ủ

● Ngoài ra còn có các p2 khác, vd:– K/c gi a hai c m là k/c gi a hai centroid c a chúngữ ụ ữ ủ

– P2 Ward: K/c gi a hai c m là đ tăng t ng bình ữ ụ ộ ổph ng l i t hai c m đó t i c m m i (n u) đ c k t ươ ỗ ừ ụ ớ ụ ớ ế ượ ếh pợ

● u đi m: Phân c m phân c p cho phép t o ra s Ư ể ụ ấ ạ ốl ng c m tùy theo m c trên câyượ ụ ứ

● Nh c đi m: Phân c m phân c p có chi phí tính ượ ể ụ ấtoán và l u tr caoư ữ

5. Hàm kho ng cáchả5.1 Thu c tính liên t cộ ụ

`

Minkowski(xi, x

j) =

Euclidean(xi, x

j) =

Manhattan(xi, x

j) =

Weighted_Euclidean(xi, x

j) =

Squared_Euclidean(xi, x

j) =

Chebychev(xi, x

j) =

5.2 Thu c tính nh phân & r i r cộ ị ờ ạ

Đi m DL ể xj

1 01 a b a + b

Đi m DL ể xi

0 c d c + da +c b + d a + b + c + d

Ma tr n nh p nh ng c a hai đi m DL ch ch a thu c tính nh phânậ ậ ằ ủ ể ỉ ứ ộ ị

Thu c tính đ i x ng: Hai giá tr nh phân có t m quan tr ng nh nhauộ ố ứ ị ị ầ ọ ư

dist(xi, x

j) =

b + c

a + b + c + d

VD:x

11 1 1 0 1 0 0

x2

0 1 1 0 0 1 0dist(x

1, x

2) =

2 + 1

2 + 2 + 1 + 2= 3/7 = 0.429

Thu c tính b t đ i x ng: Hai giá tr nh phân có t m quan tr ng khác nhauộ ấ ố ứ ị ị ầ ọ

Jaccard(xi, x

j) =

b + c

a + b + c

Thu c tính r i r c t ng quát:ộ ờ ạ ổ

dist(xi, x

j) =

r - q

r

trong đó - r: s l ng thu c tínhố ượ ộ- q: s l ng giá tr kh p nhau gi a ố ượ ị ớ ữ x

i và x

j

6. Chu n hóa DL ẩVD:Thu c tính 1 có giá tr trong kho ng [0, 1], thu c tính 2 có giá tr trong kho ng [0, 1000]ộ ị ả ộ ị ảx

i: (0.1, 20), x

j : (0.9, 720)

Sau khi chu n hóa thu c tính 2 v kho ng [0, 1]ẩ ộ ề ảX

i: (0.1, 0.02), x

j : (0.9, 0.72) → dist(x

i, x

j) = 1.063

rg(xif) =

xij - min(f)

max(f) - min(f)

z(xif) =

xij - μ

f

σf

Thu c tính liên t c tuy n tính:ộ ụ ế

● Thu c tính liên t c d ng mũ: lo-ga-rít hóaộ ụ ạ

VD: AeBt

● Thu c tính r i r c không có tr t t (vd: các lo i ộ ờ ạ ậ ự ạhoa qu ): Có th chuy n v d ng nh phânả ể ể ề ạ ị

● Thu c tính r i r c có tr t t (vd: l a tu i): ộ ờ ạ ậ ự ứ ổchu n hóa t ng t thu c tính liên t c tuy n ẩ ươ ự ộ ụ ếtính

7. X lý nhi u lo i thu c tínhử ề ạ ộ

● DL ch a nhi u lo i thu c tính: nh phân đ i x ng, nh phân b t ứ ề ạ ộ ị ố ứ ị ấđ i x ng, liên t c tuy n tính, liên t c phi tuy n, r i r c, r i r c ố ứ ụ ế ụ ế ờ ạ ờ ạcó tr t tậ ự

● Chuy n đ i t t c v lo i thu c tính ph bi n nh t (vd liên t c ể ổ ấ ả ề ạ ộ ổ ế ấ ụtuy n tính)ế

● Tính k/c trên t ng thu c tính và t ng h p l iừ ộ ổ ợ ạ

trong đó r là s thu c tính trong DL, ố ộ dijf là k/c gi a ữ xi và xj tính

theo thu c tính ộ f, δijf = 1 n u thu c tính ế ộ f t n t i c ồ ạ ở ả xi và xj và

δijf = 0 n u ng c l iế ượ ạ

8. P2 đánh giá

● D a trên ng i dùng: D a trên đánh giá c a m t nhóm các ự ườ ự ủ ộchuyên gia. Đánh giá cu i cùng là trung bình c a c nhóm. ố ủ ảPhù h p v i m t s lo i DL (văn b n)ợ ớ ộ ố ạ ả

● D a trên kh năng phân lo i: S d ng DL đ c phân lo i. M i ự ả ạ ử ụ ượ ạ ỗl p t ng ng v i m t c m. S d ng các đ đo phân lo iớ ươ ứ ớ ộ ụ ử ụ ộ ạ

● Đ nén: Th hi n m c đ t p trung c a các đi m DL ộ ể ệ ứ ộ ậ ủ ểtrong m t c m xung quanh centroid (vd t ng bình ộ ụ ổph ng l i)ươ ỗ

● Đ cô l p: Th hi n m c đ phân tách c a các c m ộ ậ ể ệ ứ ộ ủ ụthông qua k/c gi a các centroidữ

● Đánh giá gián ti p: Phân c m đ c s d ng làm tác ế ụ ượ ử ụv trung gian → đánh giá kĩ thu t phân c m thông ụ ậ ụqua đánh giá tác v cu i. Vd: phân c m ng i dùng ụ ố ụ ườđ c áp d ng trong h g i ý (s n ph m)ượ ụ ệ ợ ả ẩ

9. Khám phá l và vùng DLỗ

● DL t n t i các vùng t p trung đi m DL và các vùng không ồ ạ ậ ểch a ho c ch a ít DL (các l )ứ ặ ứ ỗ

● Vi c khám phá các l DL có vai trò quan tr ng trong m t s ệ ỗ ọ ộ ống d ngứ ụ

● Bài toán phân lo i:ạ

1. G/s các đi m DL đã có có nhãn Y. Thêm các đi m DL m i ể ể ớm t cách ng u nhiên và gán nhãn Nộ ẫ

2. S d ng m t kĩ thu t phân lo i (vd cây quy t đ nh) đ ử ụ ộ ậ ạ ế ị ểphân lo i DLạ

3. Thu đ c mô hình phân lo i v i nhãn quan tâm N ượ ạ ớ

(A) Không gian DL g cố

(B) Phân vùng v i các đi m DL b sungớ ể ổ (C) Phân vùng trên DL g cố

10. H c LUọ

● H c có giám sát cho đ chính xác cao nh ng đòi h i nhi u DL có ọ ộ ư ỏ ềnhãn. Gán nhãn DL là công vi c th công, đòi h i nhi u th i gian ệ ủ ỏ ề ờvà công s c. Trong các ng d ng nh phân lo i văn b n web, ứ ứ ụ ư ạ ảcác nhãn DL liên t c thay đ i.ụ ổ

● H c LU (labeled and unlabeled examples) xây d ng b phân lo i ọ ự ộ ạtrên m t l ng nh DL có nhãn và s d ng m t l ng l n DL ộ ượ ỏ ử ụ ộ ượ ớkhông có nhãn đ c i thi n b phân lo iể ả ệ ộ ạ

● Vd: B phân lo i văn b n s d ng ‘bài t p’ làm đ c tr ng đ ộ ạ ả ử ụ ậ ặ ư ểphân lo i các văn b n thu c ch đ ạ ả ộ ủ ề giáo d c. ụ D a trên DL không ựcó nhãn, có th phát hi n ra ‘bài t p’ th ng cùng x/h v i ‘bài ể ệ ậ ườ ớgi ng’, t đó b sung ‘bài gi ng’ làm đ c tr ng cho b phân lo iả ừ ổ ả ặ ư ộ ạ

10.1 Thu t toán EMậ

● EM (Expectation Maximization) là thu t toán l p đ c c ậ ặ ể ựđ i hóa c l ng kh năng đ i v i DL khuy t thi u. ạ ướ ượ ả ố ớ ế ếB c kỳ v ng làm đ y DL khuy t thi u d a trên c ướ ọ ầ ế ế ự ướl ng c a tham s hi n t i. B c c c đ i hóa c l ng ượ ủ ố ệ ạ ướ ự ạ ướ ượl i tham s v i m c tiêu c c đ i hóa kh năng.ạ ố ớ ụ ự ạ ả

● EM + mô hình phân lo i:ạ

1) DL có nhãn L đ c dùng đ xây d ng b phân lo i ượ ể ự ộ ạ f

2) S d ng ử ụ f đ phân lo i DL ch a có nhãn ể ạ ư U

3) C p nh t l i f d a trên ậ ậ ạ ự L và U; quay l i 2), l p t i khi h i ạ ặ ớ ộtụ

Algorithm EM(L, U)1 H c b phân lo i NB ọ ộ ạ f t t p DL có nhãn ừ ậ L2 repeat

// B c Eướ3 for m i ví d ỗ ụ d

i trong U do

4 Dùng f đ tính Pr(ể cj|d

i)

5 endfor// B c Mướ

6 h c b phân lo i ọ ộ ạ f t ừ L và U (tính Pr(cj) và Pr(w

t|c

j)

7 until the classifier parameters stabilize

Cho Do g m các ví d có nhãn, ồ ụ D

u g m các ví d không có nhãnồ ụ

Hàm log likelihood có d ng:ạ

Thay vì c c đ i hóa log likelihood, ta c c đ i hóa kì v ng c a log likelihood đ y đ :ự ạ ự ạ ọ ủ ầ ủ

Xác su t đi u ki n c a m t văn b n bi t l p c a nó:ấ ề ệ ủ ộ ả ế ớ ủ

G/s các văn b n đ c sinh ra đ c l p, hàm likelihood có th vi t d i d ng:ả ượ ộ ậ ể ế ướ ạ

S d ng bi n indicator ử ụ ế hki, h

ki = 1 khi văn b n i có nhãn ả k, hàm log likelihood có d ng:ạ

Kì v ng c a log likelihood đ y đ :ọ ủ ầ ủ

Hàm log likelihood có d ng:ạ

Lagrangian:

L y đ o hàm theo ấ ạ λ, ta có

L y đ o hàm theo Pr(ấ ạ ck; Θ), ta có

v i ớ k = 1, 2, …, |C|

Tính t ng theo ổ k, ta có

C p nh t Pr(ậ ậ wt| c

j, Θ):

C p nh t Pr(ậ ậ cj| Θ):

10.2 Đ ng - hu n luy nồ ấ ệ

● Gi thi t t p các thu c tính ả ế ậ ộ X có th chia làm ểhai t p ậ X1 và X2 đ xây d ng hai b phân lo i ể ự ộ ạ f1 và f2

● Gi thi t 1: B phân lo i xây d ng trên toàn b ả ế ộ ạ ự ộthu c tính ộ f có k t qu phân lo i gi ng nh ế ả ạ ố ư f1 và f2

● Gi thi t 2: ả ế X1 và X2 đ c l p v i nhau đ i v i ộ ậ ớ ố ớnhãn l pớ

Algorithm co-training(L, U)1 repeat2 Xây d ng b phân lo i ự ộ ạ f

1 s d ng ử ụ L d a trên t p thu c tính ự ậ ộ X

1

3 Xây d ng b phân lo i ự ộ ạ f2 s d ng ử ụ L d a trên t p thu c tính ự ậ ộ X

2

4 Dùng f1 đ phân lo i các ví d trong ể ạ ụ U, v i m i l p ớ ỗ ớ c

i, l a ch n ự ọ n

i ví dụ

mà f1 t tin nh t và thêm vào ự ấ L.

5 Dùng f2 đ phân lo i các ví d trong ể ạ ụ U, v i m i l p ớ ỗ ớ c

i, l a ch n ự ọ n

i ví dụ

mà f2 t tin nh t và thêm vào ự ấ L.

6 until U r ng (ho c sau m t s vòng l p nh t đ nh)ỗ ặ ộ ố ặ ấ ị

++

++

++

++

+

--

-

- --

- --

-+

+

+

+-

--

-

-

- - -

- ---

-

+ + +

+++++

+

+ +

+

-

-- -

-

(A) DL phân lo i b i ạ ở f1 trên U (B) DL b sung b i ổ ở f

1 đ/v f

2

10.3 T - hu n luy nự ấ ệ

● B phân lo i ộ ạ f đ c xây d ng trên t p Lượ ự ậ● B phân lo i ộ ạ f đ c dùng đ phân lo i các ví ượ ể ạ

d trong t p Uụ ậ● Các ví d có đ t tin cao nh t đ c thêm vào ụ ộ ự ấ ượ

t p Lậ● Quá trình l p l i đ n khi k t thúc (vd: U r ng)ặ ạ ế ế ỗ

10.4 Suy di n trên SVMễ

● L a ch n siêu ph ng nh m c c đ i hóa biên ự ọ ẳ ằ ự ạd a trên các ví d không có nhãn ự ụ

y = 1

y = -1

x-

x+

siêu ph ng cũẳ

siêu ph ng m iẳ ớ

10.5 P2 d a trên đ thự ồ ị

● T ừ L và U, xây d ng đ th g m các đ nh là các ví d , ự ồ ị ồ ỉ ụcác c nh có tr ng s là đ t ng đ ng gi a các ví d .ạ ọ ố ộ ươ ồ ữ ụ– T m t đ nh, ch n k hàng xóm lân c n nh từ ộ ỉ ọ ậ ấ

– Ch n đ t ng đ ng trên m t ng ng t i thi uọ ộ ươ ồ ộ ưỡ ố ể

– S d ng đ th k t n i đ y đ v i đ t ng đ ng theo hàm ử ụ ồ ị ế ố ầ ủ ớ ộ ươ ồmũ

● Gán nhãn cho các ví d trong ụ U d a trên các ví d có ự ụnhãn trong L sao cho các đ nh t ng đ ng nhau có ỉ ươ ồcùng nhãn

● Mincut: Các đ nh có nhãn thu c L đ c gán giá tr {0,1} ỉ ộ ượ ịtùy theo l p positive hay negative; các c nh đ c đánh ớ ạ ượtr ng s ọ ố wij; tìm cách gán nhãn cho các đ nh ch a có nhãn ỉ ưthu c U sao cho Σộ (i,j) ∈ E wij|vi - vj| nh nh tỏ ấ

● Tìm phép chia t p đ nh ậ ỉ V thành hai t p ậ V+ và V- không giao nhau sao cho t ng tr ng s các c nh n i hai t p là ổ ọ ố ạ ố ậnh nh t. ỏ ấ V+ ch a các đ nh có nhãn positive thu c ứ ỉ ộ L và các đ nh thu c ỉ ộ U; V- ch a các đ nh có nhãn negative thu c ứ ỉ ộL và các đ nh thu c ỉ ộ U

● Thu t toán lu ng c c đ i v i đ ph c t p tính toán O(|ậ ồ ự ạ ớ ộ ứ ạ V|3)

● Tr ng Gaussianườ : T i thi u hóa Σố ể (i,j) ∈ E wij|vi – vj|2 v i các đ nh có giá tr thu c [0, 1]ớ ị ị ộ

● Đ th phồ ị ổ: T i thi u hóa cut(ố ể V+, V-) / (|V+||V-|) nh m cân b ng s l ng đ nh c a hai t p do ằ ằ ố ượ ỉ ủ ậmincut th ng có xu h ng ch n hai t p m t ườ ướ ọ ậ ấcân b ngằ

11. H c PUọ

● Trong m t s ng d ng ng i dùng ch quan ộ ố ứ ụ ườ ỉtâm đ n m t l p văn b n (positive) và không ế ộ ớ ảquan tâm đ n các văn b n khác (negative)ế ả

● Cho t p P g m các văn b n positive và t p U ậ ồ ả ậg m các văn b n ch a có nhãn (bao g m c ồ ả ư ồ ảvăn b n positive và negative), c n xây d ng ả ầ ựm t b phân lo i cho phép xác đ nh các văn ộ ộ ạ ịb n positiveả

11.1 ng d ng c a h c PUỨ ụ ủ ọ

● VD: C n xây d ng m t CSDL g m các công trình khoa h c v lĩnh v c ầ ự ộ ồ ọ ề ựkhai phá DL.

– Đ u tiên, s d ng các công trình thu c h i ngh , t p chí v khai phá DL làm các ầ ử ụ ộ ộ ị ạ ềvăn b n positiveả

– Ti p đó, tìm các công trình v khai phá DL trong các h i ngh và t p chí v CSDL ế ề ộ ị ạ ềvà trí tu nhân t oệ ạ

● H c v i nhi u ngu n DL không có nhãn: vd, tìm các trang web v máy inọ ớ ề ồ ề– Tìm các trang positive t trang amazon.comừ

– S d ng h c PU đ tìm các trang positive các trang khácử ụ ọ ể ở

● H c v i DL negative không đáng tin c yọ ớ ậ● M r ng t p DLở ộ ậ● Covariate shift

11.2 N n t ng lý thuy tề ả ế

+ ++

+

+++

+ +

+

+ ++

+

+++

+ +

+oo

o

o oo

oo o

o

oo o

o

o

o o

Phân lo i ch d a trên ví d positiveạ ỉ ự ụ Phân lo i d a trên ví d positive và negativeạ ự ụ

● (xi, yi) là các bi n ng u nhiên đ c l y t phân ế ẫ ượ ấ ừph i xác su t Dố ấ (xi, yi), y ∈ {1, -1} là bi n ng u ế ẫnhiên có đi u ki n mà ta c n c l c khi bi t ề ệ ầ ướ ượ ế x, Dx|y = 1 là phân ph i đi u ki n mà các ví d ố ề ệ ụpositive đ c sinh ra, Dượ x là phân ph i biên sinh ốra các ví d không có nhãnụ

● M c tiêu là xây d ng m t b phân lo i ụ ự ộ ộ ạ f đ phân ểlo i văn b n positive và negative, b phân lo i có ạ ả ộ ạxác su t sinh ra l i là nh nh t Pr(ấ ỗ ỏ ấ f(x) ≠ y)

Pr(f(x) ≠ y) = Pr(f(x) = 1 và y = -1) + Pr(f(x) = -1 và y = 1)

Ta có:Pr(f(x) = 1 và y = -1) = Pr(f(x) = 1) - Pr(f(x) = 1 và y = 1)

= Pr(f(x) = 1) - (Pr(y = 1) - Pr(f(x) = -1 và y = 1))

Suy ra:Pr(f(x) ≠ y) = Pr(f(x) = 1) – Pr(y = 1) + 2Pr(f(x) = -1| y = 1)Pr(y = 1)

Do Pr(y = 1) = const, t i thi u hóa:ố ểPr(f(x) = 1) + 2Pr(f(x) = -1| y = 1)Pr(y = 1)

N u Pr(ế f(x) = -1| y = 1) <<, x p x v i t i thi u hóa Pr(ấ ỉ ớ ổ ể f(x) = 1)

x p x v i t i thi u hóa Prấ ỉ ớ ố ểU(f(x) = 1) v i đ/k Prớ

P(f(x) = 1) ≥ r (recall)

+ ++

+

+++

+ +

+oo

o

o oo

oo o

o

oo o

o

o

o o

1 2 3 4 5 6

b phân lo i t i uộ ạ ố ư

11.3 Xây d ng b phân lo i: 2 - ự ộ ạb cướ● B c 1: Xác đ nh t p các văn b n negative đáng tin c y ướ ị ậ ả ậ RN t ừ U● B c 2: Xây d ng b phân lo i t P, RN, và U-RNướ ự ộ ạ ừ

. . . .

Positive Negative

P

U

Q = U - RN

P P P

B c 1ướ B c 2ướ

RN

B c 1:ướ● K thu t do thám:ỹ ậ

1. Ch n ng u nhiên m t t p S t P và đ a vào U (line 2-3). Các ọ ẫ ộ ậ ừ ưvăn b n trong S cho phép tìm ra các văn b n positive trong Uả ả

2. Xây d ng b phân lo i NB v i ự ộ ạ ớ PS làm t p positive và ậ Us làm t p negative (line 3-7). Dùng b phân lo i NB xác đ nh các xác ậ ộ ạ ịsu t Pr(1|ấ d) v i các văn b n trong ớ ả Us

3. S d ng xác su t Pr(1|ử ụ ấ d) v i các văn b n trong ớ ả S đ tìm ểng ng ưỡ t. Các văn b n có xác su t Pr(1|ả ấ d) < t đ c đ a vào ượ ưt p ậ RN (line 10-14)

Algorithm spy(P, U)1 RN ← ∅;2 S ← sample(P, s%);3 U

s ← U ⋃ S;

4 Ps ← P – S;

5 Gán m i văn b n trong ỗ ả Ps vào l p 1;ớ

6 Gãn m i văn b n trong ỗ ả Us vào l p -1;ớ

7 NB(Us, P

s); // xây d ng mô hình NBự

8 phân lo i các văn b n trong ạ ả Us s d ng b phân lo i NB;ử ụ ộ ạ

9 Xác đ nh ng ng xác su t ị ưỡ ấ t d a trên ự S;10 for m i văn b n ỗ ả d ∈ U

s do

11 if xác su t Pr(1|ấ d) < t then12 RN ← RN {⋃ d};13 endif14 endfor

● Kĩ thu t Cosine-Rocchio:ậ● B c 1: Xác đ nh t p negative ti m năng PNướ ị ậ ề

– Bi u di n các văn b n thành véc-t theo TF-IDFể ễ ả ơ

– Xây d ng véc-t đ c tr ng ự ơ ặ ư vP cho t p ậ P. Tính đ t ng đ ng ộ ươ ồcosine gi a các văn b n trong ữ ả P v i ớ vP và s p x p theo th t ắ ế ứ ựgi m d n. M t ng ng đ c xác đ nh đ l y h t các văn b n ả ầ ộ ưỡ ượ ị ể ấ ế ảpositive n trong ẩ U và l y đ c t i thi u các văn b n negative.ấ ượ ổ ể ả

● B c 2: Xây d ng b phân lo i ướ ự ộ ạ Rocchio f d a trên ự P và PN. Các văn b n trong ả U đ c phân lo i thành negative ượ ạb i ở f đ c đ a vào t p ượ ư ậ RN

Algorithm CR(P, U)1 PN = ∅; RN = ∅;2 Bi u di n m i văn b n ể ễ ố ả d ∈ P và U thành véc-t theo TF-IDF;ơ3

4 Tính cos(vp, d) cho m i văn b n ỗ ả d ∈ P;

5 S p x p t t c các văn b n ắ ế ấ ả ả d ∈ P d a trên cos(ự vp, d) theo th t gi m d n;ứ ự ả ầ

6 ω = cos(vp, d) v i ớ d đ c x p v trí (1- ượ ế ở ị l)*|P|;

7 for m i văn b n ỗ ả d ∈ U do8 if cos(v

p, d) < ω then

9 PN = PN {∪ d}10

11

12 for văn b n ả d ∈ U do13 if cos(c

PN, d) > cos(c

P, d) then

14 RN = RN {∪ d}

● Kĩ thu t ậ 1DNF: Các t trong P và U đ c thu th p đ ừ ượ ậ ểxây d ng t v ng (line 1). T p đ c tr ng positive PF ự ừ ự ậ ặ ưđ c xây d ng ch a các t x/h ph bi n trong P h n ượ ự ứ ừ ổ ế ơU (line 2-7). Các văn b n trong U không ch a thu c ả ứ ộtính nào trong PF đ c đ a vào t p RN (line 8-13)ượ ư ậ

● Kĩ thu t ậ NB: S d ng m t b phân lo i ử ụ ộ ộ ạ NB đ xây ểd ng t p RN t Uự ậ ừ

● Kĩ thu t ậ Rocchio: S d ng m t b phân lo i ử ụ ộ ộ ạ Rocchio đ xây d ng t p RN t Uể ự ậ ừ

Algorithm 1DNF(P, U)1 Gi s t p t v ng ả ử ậ ừ ự V = {w

1, ..., w

n}, w

i ∈ U ∪ P;

2 Kh i t o t p thu c tính positive ở ạ ậ ộ PF ← ∅;3 for m i ỗ w

i ∈ V do // freq(w

i, P): s l n ố ầ w

i xu t hi n trong ấ ệ P

4 if (freq(wi, P) / |P| > freq(w

i, U) / |U|) then

5 PF ← PF {∪ wi};

6 endif7 endfor8 RN ← U;9 for m i văn b n ỗ ả d ∈ U do10 if t n t i ồ ạ w

j sao cho freq(w

j, d) > 0 and w

j ∈ PF then

11 RN ← RN – {d}12 endif13 endfor

Algorithm NB(P, U)1 Gán các văn b n trong ả P nhãn l p 1;ớ2 Gán các văn b n trong ả U nhãn l p -1;ớ3 Xây d ng b phân lo i ự ộ ạ NB s d ng ử ụ P và U;4 S d ng b phân lo i đ phân lo i các văn b n trong ử ụ ộ ạ ể ạ ả U. Các văn b n đ c phânả ượ

lo i negative đ c đ a vào t p ạ ượ ư ậ RN

B c 2:ướ● EM + NB: B c expectation tính toán các xác su t nhãn ướ ấ

c a các văn b n trong U – RN. B c maximization c ủ ả ướ ướl ng l i tham s c a b phân lo i NBượ ạ ố ủ ộ ạ

● SVM: T i m i b c l p, b phân lo i SVM ạ ỗ ướ ặ ộ ạ f đ c xây ượd ng t ự ừ P và RN. B phân lo i f đ c s d ng đ phân ộ ạ ượ ử ụ ểlo i các văn b n trong ạ ả Q. Các văn b n đ c phân lo i ả ượ ạnegative đ c lo i kh i ượ ạ ỏ Q và b sung vào ổ RN. Quá trình l p k t thúc khi không còn văn b n nào trong đ c ặ ế ả ượphân lo i negativeạ

Algorithm EM(P, U, RN)1 M i văn b n trong ỗ ả P đ c gán nhãn l p 1;ượ ớ2 M i văn b n trong ỗ ả RN đ c gán nhãn l p -1;ượ ớ3 H c m t b phân lo i ọ ộ ộ ạ NB f t ừ P và RN4 repeat5 for m i văn b n ỗ ả d

i trong U - RN do

6 S d ng b phân lo i ử ụ ộ ạ f hi n t i đ tính Pr(ệ ạ ể cj| d

i)

7 endfor8 h c b phân lo i ọ ộ ạ NB m i ớ f t ừ P, RN và U - RN b ng cách tính Pr(ằ c

j) và Pr(w

t| c

j)

9 until các tham s c a b phân lo i n đ nhố ủ ộ ạ ổ ị

Algorithm I-SVM(P, RN, Q)1 M i văn b n trong ỗ ả P đ c gán nhãn l p 1;ượ ớ2 M i văn b n trong ỗ ả RN đ c gán nhãn l p –1;ượ ớ3 loop4 Dùng P và RN đ hu n luy n b phân lo i SVM ể ẩ ệ ộ ạ f;5 Phân lo i ạ Q s d ng ử ụ f;6 W là t p các văn b n trong ậ ả Q đ c phân lo i là negative;ượ ạ7 if W = ∅ then exit-loop // h i tộ ụ8 else Q ← Q – W;9 RN ← RN ∪ W;10 endif

11.4 Xây d ng b phân lo i: SVMự ộ ạ

● Cho t p DL hu n luy n {(ậ ấ ệ x1, y1), (x2, y2)…, (xn, yn)} trong đó xi là các véc-t và ơ yi {1, -1}. G/s ∈ k ví d đ u ụ ầ ∈ P có nhãn positive (y = 1), các ví d sau ụ ∈ U đ c coi nh có nhãn ượ ưnegative (y = -1)

● TH1: T p ậ P không ch a l i, theo lý thuy t khi s m u đ l n, ứ ỗ ế ố ẫ ủ ớcó th thu đ c b phân lo i đ t t n u t i thi u hóa các văn ể ượ ộ ạ ủ ố ế ố ểb n không có nhãn đ c phân lo i thành positive trong khi ả ượ ạràng bu c s ví d positive đ c phân lo i t tộ ố ụ ượ ạ ố

T i thi u hóa: ố ể

V i ràng bu c: ớ ộ <w ⋅ xi> + b ≥ 1, i = 1, 2, …, k-1

-1(<w ⋅ xi> + b) ≥ 1 - ξ

i, i = k, k+1, … n

ξi ≥ 0, i = k, k+1, …, n

● TH2: T p P ch a ví d negative (do DL có nhi u)ậ ứ ụ ễ

T i thi u hóa: ố ể

V i ràng bu c: ớ ộ yi(<w ⋅ x

i> + b) ≥ 1 - ξ

i, i = k, k+1, … n

ξi ≥ 0, i = k, k+1, …, n

trong đó C+ và C

- là các tr ng s c a l i positive và negative t ng ng đ c xác đ nhọ ố ủ ỗ ươ ứ ượ ị

d a trên t p validation theo đ đoự ậ ộr2

Pr(f(x) = 1)

r = Pr(f(x) = 1| y = 1)

p = Pr(y = 1| f(x) = 1)

Ta có:

Pr(f(x) = 1| y = 1)Pr(y = 1) = Pr(y = 1| f(x) = 1) Pr(f(x) = 1)

Suy ra:

r p

Pr(f(x) = 1 ) Pr(y = 1 )=

r2 pr

Pr(f(x) = 1 ) Pr(y = 1 )=

có t/c t ng t F-scoreươ ự

11.5 Xây d ng b phân lo i: c ự ộ ạ Ướl ng xác su tượ ấ● Cho ví d ụ x và nhãn y {1, -1}, cho ∈ s = 1 n u ế x là ví d ụ

đ c gán nhãn và ượ s = 0 n u ế x không có nhãn, ta có Pr(s = 1| x, y = -1) = 0

● M c tiêu: Xây d ng hàm phân lo i ụ ự ạ f(x) sao cho f(x) g n ầPr(y = 1| x) nh tấ

● Gi thuy t l a ch n ng u nhiên hoàn toàn: các ví d positive ả ế ự ọ ẫ ụđ c gán nhãn đ c l a ch n hoàn toàn ng u nhiên t các ượ ượ ự ọ ẫ ừví d positive Pr(ụ s = 1| x, y = 1) = Pr(s = 1| y = 1) = c

● N u dùng ế P và U đ xây d ng hàm phân lo i ể ự ạ g(x) thì g(x) = Pr(s = 1| x), khi đó f(x) = g(x) / c

g(x) = Pr(s = 1| x)= Pr(y = 1 và s = 1| x)= Pr(y = 1| x)Pr(s = 1| y = 1, x)= Pr(y = 1| x)Pr(s = 1| y = 1)= f(x)Pr(s = 1| y = 1)

c l ng Ướ ượ c s d ng t p validation ử ụ ậ V, v i ớ VP là t p các ví d positive trong ậ ụ V:

g(x) = Pr(s = 1| x)= Pr(s = 1| x, y = 1)Pr(y = 1| x) + Pr(s = 1| x, y = -1)Pr(y = -1| x)= Pr(s = 1| x, y = 1) × 1 + 0 × 0 do x ∈ V

P

= Pr(s = 1| y = 1).

Chú ý: N u ch c n x p h ng ế ỉ ầ ế ạ x theo xác su t thu c l p positive, có th dùng tr c ti p ấ ộ ớ ể ự ế g

Q&A

mailto: hieunk@soict.hust.edu.vn