Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM

Nội dung tài liệu: Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM

1. ĐẠI HÅC HUẾ TRƯỜNG ĐẠI HÅC KHOA HÅC NGUYỄN THẾ CƯỜNG NÂNG CAO HIỆU NĂNG PHÂN LÎP DỮ LIỆU TRÊN CƠ SÐ CẢI TIẾN THUẬT TOÁN SVM NGÀNH: KHOA HÅC MÁY TÍNH MÃ SÈ: 9.48.01.01 TÂM TẮT LUẬN ÁN TIẾN SĨ KHOA HÅC MÁY TÍNH Người hướng d¨n khoa học: PGS.TS. Huỳnh Th¸ Phùng HUẾ - NĂM 2023
2. Công tr¼nh được hoàn thành t¤i: Khoa Công ngh» Thông tin, Trường Đại học Khoa học, Đại học Hu¸. Người hướng d¨n khoa học: PGS. TS. Huỳnh Th¸ Phùng, Trường Đại học Khoa học, Đại học Hu¸. Ph£n bi»n 1: PGS. TS. Nguy¹n Th¡i Sơn, Trường Đại học Trà Vinh. Ph£n bi»n 2: PGS. TS. Nguy¹n T§n Khôi, Trường Đại học B¡ch khoa, Đại học Đà N®ng. Ph£n bi»n 3: PGS. TS. Nguy¹n Húu Quỳnh, Trường Đại học Thuỷ Lñi. Luªn ¡n s³ được b£o v» t¤i Hëi đồng ch§m luªn ¡n c§p Đại học Hu¸ họp t¤i: Vào lúc: giờ ngày th¡ng n«m 2023 Có thº t¼m hiºu luªn ¡n t¤i thư vi»n:
3. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM MÐ ĐẦU 1. Lý do chọn đề tài Để gi£i quy¸t bài to¡n ph¥n lo¤i m¨u, nhi·u thuªt to¡n đã được x¥y dựng để nhªn di»n c¡c m¨u kh¡c nhau tr¶n cơ sở c¡c m¨u thû đã được hu§n luy»n. Mët kỹ thuªt ph¥n lo¤i có gi¡m s¡t nêi ti¸ng là thuªt to¡n SVM (SVM). SVM được vªn dụng vào c¡c bài to¡n như: nhªn d¤ng h¼nh £nh, chú vi¸t, ¥m thanh, s­c th¡i giọng nói Nhªn th§y SVM v¨n đang là mët v§n đề thời sự cõa cëng đồng nghi¶n cùu học thuªt v¼ vªy chúng tôi chọn đề tài “Nâng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM” để nghi¶n cùu. 2. Động lực nghi¶n cùu Trong qu¡ tr¼nh nghi¶n cùu SVM và c¡c hướng ph¡t triºn, có thº kº đến mët vài bi¸n thº ti¶u biºu cõa SVM như: SVM x§p x¿ (PSVM), SVM x§p x¿ thông qua trị ri¶ng suy rëng (GEPSVM), SVM song sinh (TSVM), SVM song sinh có c§u trúc (S-TSVM), SVM song sinh dùng b¼nh phương tèi thiºu (LSTSVM). Đối với d¤ng dú li»u có c§u trúc phùc t¤p, nơi mà méi lớp gồm nhi·u cụm, méi cụm có xu hướng ph¥n phèi ri¶ng bi»t. SVM và c¡c bi¸n thº chưa khai th¡c đầy đủ c¡c thông tin v· sè lượng điểm dú li»u trong méi cụm, thông tin c§u trúc cõa tøng cụm. Điều này có thº £nh hưởng đ¸n hi»u n«ng (độ ch½nh x¡c, thời gian) ph¥n lớp dú li»u. Đó ch½nh là độc lực để luªn ¡n tªp trung nghi¶n cùu và đề xu§t mới c¡c gi£i ph¡p n¥ng cao hi»u n«ng ph¥n lớp dú li»u đối với d¤ng dú li»u có c§u trúc phùc t¤p. 1
4. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM 3. Đối tượng và ph¤m vi nghi¶n cùu Đối tượng nghi¶n cùu là c¡c thuªt to¡n học m¡y, bài to¡n ph¥n lớp dú li»u. Ph¤m vi nghi¶n cùu là học m¡y có gi¡m s¡t, c£i ti¸n SVM đối với lo¤i dú li»u có c§u trúc phùc t¤p. 4. Mục ti¶u cõa luªn ¡n Đề xu§t c¡c phương ph¡p mới nh¬m n¥ng cao hi»u n«ng ph¥n lớp dú li»u đối với d¤ng dú li»u có c§u trúc phùc t¤p, tr¶n cơ sở c£i ti¸n thuªt to¡n SVM. Khai th¡c được thông tin v· c§u trúc cõa tøng cụm và thông tin v· sè lượng điểm dú li»u cõa méi cụm trong c¡c lớp. 5. Phương ph¡p nghi¶n cùu và gi£i quy¸t ˆ C¡c phương ph¡p to¡n học Phương ph¡p nh¥n tû Lagrange, h» KKT (Karush - Kuhn - Tucker). Phương ph¡p dùng b¼nh phương tèi thiºu. ˆ C¡c phương ph¡p xû lý với dú li»u có nhi·u cụm Khai th¡c lớp-đối-cụm. Khai th¡c cụm-đối-lớp. ˆ Phương ph¡p thực nghi»m khoa học. 6. Ý nghĩa khoa học và thực ti¹n Ý nghĩa khoa học Nhúng đóng góp ch½nh cõa luªn ¡n v· khoa học: ˆ Đề xu§t c¡c thuªt to¡n ph¥n lớp nhị ph¥n với dú li»u có c§u trúc phùc t¤p, sû dụng chi¸n lược lớp-đối-cụm. 2
5. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM ˆ Đề xu§t c¡c thuªt to¡n ph¥n lớp nhị ph¥n với dú li»u có c§u trúc phùc t¤p, sû dụng chi¸n lược cụm-đối-lớp. Ý nghĩa thực ti¹n ˆ Có thº gi£i quy¸t được c¡c bài to¡n ph¥n lớp với dú li»u có c§u trúc phùc t¤p hoặc dú li»u không c¥n b¬ng. ˆ Luªn ¡n có thº được sû dụng làm tài li»u tham kh£o cho cëng đồng nghi¶n cùu đề tài v· ph¥n lớp dú li»u. 7. Bè cục cõa luªn ¡n Ngoài ph¦n mở đầu và k¸t luªn, luªn ¡n gồm 4 chương: ˆ Chương 1: là ki¸n thùc bê trñ v· bài to¡n Quy ho¤ch toàn phương QP và cơ sở to¡n học cõa thuªt to¡n SVM. ˆ Chương 2: là c¡c c£i ti¸n ti¶u biºu cõa SVM được tr¼nh bày mët c¡ch ng­n gọn, c¡c k¸t qu£ có c¡ch ti¸p cªn sû dụng hai si¶u ph¯ng để ph¥n lo¤i hai lớp dú li»u. ˆ Chương 3: là phương ph¡p lớp-đối-cụm với hai thuªt to¡n mới: SVM có c§u trúc có trọng sè (được gọi là WS-SVM) và C£i ti¸n cõa SVM dùng b¼nh phương tèi thiºu (được gọi là ILS-SVM). ˆ Chương 4: là chi¸n lược cụm-đối-lớp với thuªt to¡n mới: SVM dùng b¼nh phương tèi thiºu có trọng sè (được gọi là WLS-SVM). C¡c k¸t qu£ cõa luªn ¡n đưñc công bè trong 05 công tr¼nh khoa học được đăng trong c¡c hëi nghị và t¤p ch½ chuy¶n ngành trong và ngoài nước. Trong đó có 01 bài đăng trong chuy¶n san hëi th£o quèc gia, 01 bài đăng ở hëi th£o quèc t¸, 01 bài đăng ở t¤p ch½ Khoa học và Công ngh», Đại học Khoa học Hu¸, 01 bài đăng ở t¤p ch½ Kĩ thuªt và Công ngh», Đại học Hu¸, 01 bài đăng ở t¤p ch½ Tin học và Điều khiºn. 3
6. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM CHƯƠNG 1. CƠ SÐ TOÁN HÅC CỦA SVM 1.1. Hàm toàn phương. Hàm toàn phương dưới d¤ng chu©n 1 Q(x) = xT Gx + gT x + α; x 2 n; 2 R Hàm Q lồi khi và ch¿ khi G là ma trªn nûa x¡c định dương. Hơn núa, khi G x¡c định dương th¼ Q là hàm lồi chặt. 1.2. Bài to¡n quy ho¤ch toàn phương. D¤ng ma trªn têng qu¡t 8 >Q(x) = 1 xT Gx + gT x + α −! min; > 2 > :>Cx = d: Khi hàm mục ti¶u Q lồi, ta có bài to¡n quy ho¤ch toàn phương lồi. 1.3. Điều ki»n tèi ưu cõa bài to¡n QP Định lý 1.1 (Điều ki»n tèi ưu). (a) Gi£ sû x∗ là nghi»m cõa bài to¡n QP. Khi đó tồn t¤i c¡c bë h» sè ∗ ∗ ∗ m ∗ ∗ ∗ k λ = (λ1; : : : ; λm) 2 R , µ = (µ1; : : : ; µk) 2 R tho£ m¢n: 4
7. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM 8 m k > ∗ X ∗ X ∗ >Gx + g = λ ai + µ cj; > i j > i=1 j=1 > ∗ T ∗ >λ (a x − bi) = 0; i 2 I; > i i > > T ∗ :cj x = dj; j 2 J: H» tr¶n được gọi là h» KKT (Karush−Kuhn−T ucker) cõa bài to¡n QP, x∗ được gọi là điểm KKT, và c¡c h» sè λ∗, µ∗ được gọi là c¡c nh¥n tû Lagrange tương ùng với x∗. (b) N¸u bài to¡n QP là lồi, x∗ là mët điểm KKT cùng với c¡c nh¥n tû Lagrange λ∗, µ∗, th¼ x∗ cũng là nghi»m cõa bài to¡n QP . H» KKT có thº vi¸t l¤i dưới d¤ng ma trªn như sau: 8 >Gx∗ + g = AT λ∗ + CT µ∗; > > > ∗ ∗T ∗ >λ (Ax − b) = 0; > > :>Cx∗ = d: 1.4. Bài to¡n đối ng¨u Gi£ sû bài to¡n QP lồi, ta có hàm Lagrange cõa bài to¡n là 1 L(x; λ; µ) = xT Gx + gT x − λT (Ax − b) − µT (Cx − d); 2 n m k với c¡c bi¸n (x; λ; µ) 2 R × R+ × R : Tø phương tr¼nh døng T T rxL(x; λ; µ) = Gx + g − A λ − C µ = 0; ta có bài to¡n đối ng¨u: 8 > 1 T T T −1 T T T T m k :λ 2 R+ ; µ 2 R : 5
8. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM 1.5. Bài to¡n ph¥n lớp dú li»u X²t bài to¡n ph¥n lo¤i nhị ph¥n có tªp dú li»u được k½ hi»u bởi ma m×n T n trªn C ⊂ R , bao gồm m điểm (méi điểm là mët hàng cõa C) xj 2 R ; 1 ≤ j ≤ m. Gi£ sû r¬ng, yj 2 Ω = {−1; 1g là nh¢n cõa điểm dú li»u xj. mA×n Lớp f+g gồm mA điểm và được k½ hi»u bởi ma trªn A ⊂ R , lớp {−} mB ×n gồm mB điểm được k½ hi»u bởi ma trªn B ⊂ R . Điểm dú li»u xi được x¸p vào lớp A n¸u tương ùng ta có yi = 1, và được x¸p vào lớp B n¸u yi = −1. Bài to¡n đặt ra là: c¦n t¼m mët hàm ph¥n lớp n f : R ! {−1; 1g thỏa m¢n: f(xi) = yi; 8 i 2 Q := f1; 2; : : : ; mg 1.6. Hàm ph¥n lớp tuy¸n t½nh Khi dú li»u hai lớp là t¡ch được tuy¸n t½nh ta gi£i bài to¡n tèi ưu sau: 8 >min 1 kwk2; T :s.t. 1 − yi(w xi + b) ≤ 0; 8i 2 Q: 1.7. Si¶u ph¯ng l· m·m Khi dú li»u hai lớp bị chồng l§n mët ph¦n, ta gi£i bài to¡n sau: 8 1 2 Pm > min kwk + c i=1 ξi; T : s.t. 1 − yi(w xi + b) − ξi ≤ 0; ξi ≥ 0; 8i 2 Q: 1.8. Hàm ph¥n lớp phi tuy¸n Cho ¡nh x¤ Φ: Rn ! Rm sao cho: m Φ(x) = (a1'1(x); a2'2(x); : : : ; am'm(x)) 2 R : 6
9. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM Ta c¦n t¼m ¡nh x¤ Φ sao cho hai tªp Φ(A) và Φ(B) (trong Rm) là t¡ch được tuy¸n t½nh. Nghĩa là tồn t¤i cặp (w; b) 2 Rm × R sao cho: T yi(w Φ(xi) + b) ≥ 1; 8 i 2 Q: Áp dụng kĩ thuªt ph¥n lớp tuy¸n t½nh trong không gian Rm b¬ng phương ph¡p hàm Lagrange và đưa v· bài to¡n đối ng¨u: 8 >max − 1 λT Dλ + λT e; s.t. λ ≥ 0; λT y = 0; T m trong đó D là ma trªn vuông với Dij = yiyjΦ(xi) Φ(xj), e 2 R là véc-tơ với t§t c£ c¡c thành ph¦n b¬ng 1. 1.9. Hàm ph¥n lớp có trọng sè Ta s³ đưa th¶m c¡c bi¸n phụ ξi và gi£i bài to¡n tèi ưu sau: 8 1 2 P + P − > min kwk + x 2A δ ξi + x 2B δ ξi; T : s.t. yi(w xi + b) ≥ 1 − ξi; 8i 2 Q: Tương tự bài to¡n l· m·m, b¬ng phương ph¡p nh¥n tû Lagrange, ta gi£i bài to¡n b¬ng c¡ch đưa v· bài to¡n đối ng¨u. 1.10. Tiºu k¸t chương Như vªy, tư tưởng to¡n học cõa SVM thực ch§t là t¼m c¡ch t¡ch c¡c lớp dú li»u bởi mët si¶u ph¯ng có kho£ng c¡ch đến c¡c tªp dú li»u là lớn nh§t. Lời gi£i cho c¡c trường hñp tø đơn gi£n đến phùc t¤p đã được tr¼nh bày b¬ng mët phương ph¡p nh§t qu¡n là sû dụng quy t­c nh¥n tû Lagrange. Trong chương ti¸p theo, luªn ¡n cung c§p ng­n gọn v· c¡c phương ph¡p sû dụng hai si¶u ph¯ng, song song hoặc không nh§t thi¸t song song để ph¥n lớp dú li»u. 7
10. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM CHƯƠNG 2. CÁC BIẾN THỂ CỦA SVM 2.1. SVM x§p x¿ (PSVM) PSVM (Proximal Support Vector Machine) t¡ch hai lớp dú li»u b¬ng c¡ch gi£i bài to¡n tèi ưu 8 >min c 1 kξk2 + 1 (wT w + b2); s.t D(Cw + eb) + ξ = e: Với D 2 Rm×m là ma trªn đường ch²o nhªn gi¡ trị 1 hoặc −1 tương ùng với nh¢n cõa điểm dú li»u xi; i = 1; : : : ; m. 2.2. PSVM thông qua c¡c trị ri¶ng suy rëng (GEPSVM) GEPSVM (Proximal Support Vector Machine Via Generalized Eigen- values) t¼m hai si¶u ph¯ng không nh§t thi¸t song song: T • f+(x)(= w+x + b+) = 0 là g¦n với lớp f+g và c¡ch xa lớp {−}, T • f−(x)(= w−x + b−) = 0 là g¦n với lớp {−} và c¡ch xa lớp f+g. Vi»c t¼m si¶u ph¯ng f+(x) = 0 tương đương với bài to¡n tèi ưu kAw + e b k2=k(wT ; b )k2 min + A + + + 2 T 2 (w+;b+)6=0 kBw+ + eBb+k =k(w+; b+)k 2.3. SVM song sinh (TSVM) TSVM (Twin Support Vector Machine) t¼m hai si¶u ph¯ng: 8
11. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM T f+(x)(= w+x + b+) = 0 là g¦n với lớp f+g và để lớp {−} v· mët ph½a, T f−(x)(= w−x + b−) = 0 là g¦n với lớp {−} và để lớp f+g v· mët ph½a. 2.3.1. Trường hñp tuy¸n t½nh Trong trường hñp hai lớp dú li»u là t¡ch được tuy¸n t½nh, TSVM t¼m hai si¶u ph¯ng b¬ng c¡ch gi£i hai bài to¡n QP lồi như sau: 8 1 2 T : s.t. −(Bw+ + eBb+) + ξ ≥ eB; ξ ≥ 0; 8 1 2 T : s.t. (Aw− + eAb−) + η ≥ eA; η ≥ 0: 2.3.2. Trường hñp phi tuy¸n Đặt Φ: Rn ! S = span(Φ(CT )). Trong S, si¶u ph¯ng Φ(xT )h + b = 0 có thº được vi¸t l¤i dưới d¤ng Φ(xT )Φ(CT )u + b = 0, u 2 Rm. Định nghĩa Φ(xT )Φ(CT ) = K(xT ; CT ), K là mët kernel x¡c định trước. TSVM x¡c T T T T định 2 si¶u ph¯ng: K(x ; C )u+ + b+ = 0 và K(x ; C )u− + b− = 0 b¬ng c¡ch gi£i hai bài to¡n QP lồi: 8 1 T 2 T T : s.t. −(K(B; C )u+ + eBb+) + ξ ≥ eB; ξ ≥ 0; 8 1 T 2 T T : s.t. (K(A; C )u− + eAb−) + η ≥ eA; η ≥ 0; 2.4. TSVM dùng b¼nh phương tèi thiºu (LSTSVM) LSTSVM (Least Squares Twin Support Vector Machine) cũng t¼m hai si¶u ph¯ng b¬ng c¡ch gi£i hai bài to¡n QP lồi với ràng buëc đẳng thùc 9
12. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM 8 1 2 1 T : s.t. −(Bw+ + eBb+) + ξ = eB; 8 1 2 1 T : s.t. (Aw− + eAb−) + η = eA: LSTSVM được mở rëng cho trường hñp phi tuy¸n như TSVM. 2.5. SVM song sinh có c§u trúc (S-TSVM) Trở l¤i bài to¡n ph¥n lo¤i ở Mục 1.5, gi£ sû có k cụm trong lớp f+g, mAi×n cụm thù i gồm mAi điểm được k½ hi»u bởi ma trªn Ai ⊂ R , có l cụm trong lớp {−}, cụm thù j gồm mBj điểm được k½ hi»u bởi ma trªn mBj ×n Bj ⊂ R . S-TSVM (Structural Twin Support Vector Machine) t¼m hai si¶u ph¯ng b¬ng c¡ch gi£i hai bài to¡n 8 1 2 T 1 2 2 1 T : s.t. − (Bw+ + eBb+) + ξ ≥ eB; ξ ≥ 0; 8 1 2 T 1 2 2 1 T : s.t.(Aw− + eAb−) + η ≥ eA; η ≥ 0: S-TSVM cũng d¹ dàng được mở rëng cho trường hñp phi tuy¸n. 2.6. Tiºu k¸t chương Như vªy, c¡c bi¸n thº cõa SVM đều dùng hai si¶u ph¯ng để ph¥n hai lớp dú li»u. C¡c thuªt to¡n tr¶n chưa khai th¡c được thông tin c§u trúc và sè lượng điểm dú li»u trong méi cụm. Trong chương ti¸p theo là c¡c k¸t qu£ đã đạt được tø vi»c khai th¡c c¡c thông tin tr¶n vào hu§n luy»n mô h¼nh, với chi¸n lược lớp-đối-cụm. 10
13. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM CHƯƠNG 3. PHƯƠNG PHÁP LÎP ĐỐI CỤM Chương 3 và Chương 4 là nhúng công tr¼nh ch½nh tªp trung vào ph¥n lớp dú li»u có c§u trúc, tùc là méi lớp có nhi·u cụm dú li»u, méi cụm có thº có sè lượng kh¡c nhau và c§u trúc kh¡c nhau. Chương này là hai thuªt to¡n với chi¸n lược lớp-đối-cụm: SVM Có C§u Trúc Có Trọng Sè (WS-SVM, công tr¼nh 2) và C£i Ti¸n cõa SVM Dùng B¼nh Phương Tèi Thiºu (ILS-SVM, công tr¼nh 3). 3.1. SVM có c§u trúc có trọng sè (WS-SVM) X²t bài to¡n ph¥n lo¤i hai lớp như ở Mục 2.5. WS-SVM (Weighted Least Squares Support Vector Machine) x¡c định (l + k) si¶u ph¯ng, méi trong chúng là g¦n với mët lớp và c¡ch xa mët cụm trong lớp kh¡c. Cụ thº, T t¼m l si¶u ph¯ng sao cho si¶u ph¯ng thù j, fj+(x) = wj+x+bj+ = 0 là g¦n với lớp f+g và c¡ch xa cụm Bj cõa lớp {−}; t¼m k si¶u ph¯ng sao cho si¶u T ph¯ng thù i, fi−(x) = wi−x+bi− = 0 là g¦n với lớp {−} và c¡ch xa cụm Ai n cõa lớp f+g. Ð đây wj+; wi− 2 R ; bj+; bi− 2 R; i = 1; : : : ; k; j = 1; : : : ; l. Bë ph¥n lo¤i được chọn là: f(x) = argmin(f+(x); f−(x)); +; − l k X mBj X mAi f (x) = jf (x)j; f (x) = jf (x)j: + m j+ − m i− j=1 B i=1 A Mët điểm dú li»u mới x được ph¥n lo¤i vào lớp f+g hoặc lớp {−} phụ thuëc vào f+(x) là b² hơn hay lớn hơn f−(x). 11
14. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM 3.1.1. Trường hñp tuy¸n t½nh Khi dú li»u hai lớp là t¡ch được tuy¸n t½nh, WS-SVM x¡c định (l + k) si¶u ph¯ng b¬ng c¡ch gi£i (l + k) bài to¡n QP như sau: 8 > 1 2 T µ+ 2 2 λ+ T :> s.t. − (Bjwj+ + eBjbj+) + ξj ≥ eBj; ξj ≥ 0; 8 1 2 T µ− 2 2 λ− T : s.t.(Aiwi− + eAibi−) + ηi ≥ eAi; ηi ≥ 0: j = 1; : : : ; l; và i = 1; : : : ; k. B¬ng phương ph¡p nh¥n tû Lagrange ta có nghi»m T T T −1 T zj+ = [wj+; bj+] = −[H H + µ+I + λ+F+] Gj αj; j = 1; : : : ; l; T T T −1 T zi− = [wi−; bi−] = [G G + µ−I + λ−F−] Hi γi; i = 1; : : : ; k; trong đó αj; γi là nghi»m cõa c¡c bài to¡n đối ng¨u 8 T 1 T T −1 T :s.t. 0 ≤ αj ≤ c+eBj; 8 T 1 T T −1 T :s.t. 0 ≤ γi ≤ c−eAi: 2 3 Σ+ 0 Với H = [A; eA], F+ = 4 5, Gj = [Bj; eBj], G = [B; eB], F− = 0 0 2 3 Σ− 0 4 5, Hi = [Ai; eAi] và I là ma trªn đơn vị bªc (n + 1). 0 0 12
15. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM 3.1.2. Trường hñp phi tuy¸n T T WS-SVM x¡c định l si¶u ph¯ng: K(x ; C )uj+ + bj+ = 0 là g¦n với T T lớp Φ(A) và c¡ch xa cụm Φ(Bj). X¡c định k si¶u ph¯ng: K(x ; C )ui− + bi− = 0 là g¦n với lớp Φ(B) và c¡ch xa cụm Φ(Ai) b¬ng c¡ch gi£i (l + k) bài to¡n QP như sau: 8 > min 1 kK(A; CT )u +e b k2 +c eT ξ + µ+ k[u ; b ]k2 > 2 j+ A j+ + Bj j 2 j+ j+ >uj+;bj+;ξj 2 j+ + j+ > > T : s.t. − (K(Bj; C )uj+ + eBjbj+) + ξj ≥ eBj; ξj ≥ 0; 8 > min 1 kK(B; CT )u +e b k2 +c eT η + µ− k[u ; b ]k2 > 2 i− B i− − Ai i 2 i− i− >ui−;bi−;ηi 2 i− − i− > > T : s.t. (K(Ai; C )ui− + eAibi−) + ηi ≥ eAi; ηi ≥ 0; 3.1.3. Thực nghi»m 3.1.3.1. Tªp dú li»u gi£ 2 chi·u Thực hi»n c¡c thuªt to¡n tr¶n c¡c tªp dú li»u gi£ có sè lượng lớn đº so s¡nh v· thời gian hu§n luy»n giúa c¡c thuªt to¡n. 3.1.3.2. C¡c tªp dú li»u cõa UCI So s¡nh v· thời gian hu§n luy»n, độ ch½nh x¡c kiºm thû, độ ch½nh x¡c th©m định ch²o 10-l¦n tr¶n c¡c tªp dú li»u cõa UCI. 3.2. C£i ti¸n LSSVM (ILS-SVM) ILS-SVM (Improvement Least Squares Support Vector Machine) (công tr¼nh 3) sû dụng chi¸n lược lớp-đối-cụm và c¡c ràng buëc đẳng thùc, gi£i 13
16. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM bài to¡n trực ti¸p b¬ng c¡ch dùng b¼nh phương tèi thiºu. Bë ph¥n lo¤i được chọn là f(x) = argmin(f+(x); f−(x)); +; − l k X mBj X mAi f (x) = f (x); f (x) = f (x): + m j+ − m i− j=1 B i=1 A 3.2.1. Trường hñp tuy¸n t½nh ILS-SVM x¡c định (l + k) si¶u ph¯ng b¬ng c¡ch gi£i (l + k) bài to¡n 8 > 1 2 c+ T µ+ 2 2 :> s.t. (Bjwj+ + eBjbj+) + ξj = eBj; 8 1 2 c− T µ− 2 2 : s.t. (Aiwi− + eAibi−) + ηi = eAi; j = 1; : : : ; l và i = 1; : : : ; k. B¬ng c¡ch thay th¸ c¡c ràng buëc đẳng thùc vào hàm mục ti¶u, gi£i c¡c phương tr¼nh đạo hàm b¬ng 0 ta có c¡c nghi»m h i−1 T T 1 T T µ+ T zj+ = [wj+; bj+] = H H + G Gj + I Gj eBj; c+ j c+ h i−1 T T 1 T T µ− T zi− = [wi−; bi−] = G G + H Hi + I Hi eAi: c− i c− Trong đó H = [A; eA], Gj = [Bj; eBj], j = 1; : : : ; l, G = [B; eB], Hi = [Ai; eAi], i = 1; : : : ; k, và I là ma trªn đơn vị bªc (n + 1). 14
17. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM 3.2.2. Trường hñp phi tuy¸n Khi dú li»u phi tuy¸n, tương tự như Mục (3.1.2), ILS-SVM x¡c định (l + k) si¶u ph¯ng b¬ng c¡ch gi£i (l + k) bài to¡n QP lồi chặt như sau: 8 > 1 T 2 c+ T µ+ 2 2 T :> s.t. (K(Bj; C )uj+ + eBjbj+) + ξj = eBj; 8 1 T 2 c− T µ− 2 2 T : s.t. (K(Ai; C )ui− + eAibi−) + ηi = eAi; m m uj+ 2 R , j = 1; : : : ; l và ui− 2 R , i = 1; : : : ; k. 3.2.3. Thực nghi»m 3.2.3.1. Tªp dú li»u gi£ 2 chi·u Thực hi»n c¡c thuªt to¡n tr¶n c¡c tªp dú li»u gi£ 2 chi·u có sè lượng lớn để so s¡nh v· thời gian hu§n luy»n. 3.2.3.2. C¡c tªp dú li»u UCI So s¡nh v· thời gian hu§n luy»n, độ ch½nh x¡c kiºm thû, độ ch½nh x¡c th©m định ch²o 10-l¦n tr¶n c¡c tªp dú li»u cõa UCI. 3.3. Tiºu k¸t chương Với chi¸n lược lớp-đối-cụm, WS-SVM (công tr¼nh 2) chia hai bài to¡n QP ban đầu trong S-TSVM thành (l + k) bài to¡n QP có cỡ nhỏ hơn và được gi£i b¬ng phương ph¡p đối ng¨u. Cũng với chi¸n lược lớp-đối-cụm, ILS-SVM (công tr¼nh 3) đã khai th¡c thông tin v· sè lượng điểm dú li»u cõa méi cụm vào hu§n luy»n mô h¼nh. Thuªt to¡n được thi¸t lªp bởi c¡c ràng buëc đẳng thùc và được gi£i b¬ng c¡ch sû dụng b¼nh phương tèi thiºu. 15
18. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM CHƯƠNG 4. PHƯƠNG PHÁP CỤM ĐỐI LÎP Trong chương này là thuªt to¡n mới: SVM dùng b¼nh phương tèi thiºu có trọng sè (được gọi là WLS-SVM, công tr¼nh 5), với chi¸n lược cụm-đối-lớp. 4.1. Bi¸n đổi cõa S-TSVM Sû dụng chi¸n lược cụm-đối-lớp, ta có thº bi¸n đổi hai bài to¡n QP cõa S-TSVM trong Mục 2.5 thành c¡c bài to¡n như sau (công tr¼nh 4). 8 1 2 T 1 T : s.t. −(Bwi+ + eBbi+) + ξ ≥ eB; ξ ≥ 0; 8 1 2 T 1 T : s.t. (Awj− + eAbj−) + η ≥ eA; η ≥ 0; với i = 1; : : : ; k và j = 1; : : : ; l. C¡c bài to¡n này được gi£i b¬ng phương ph¡p nh¥n tû Lagrange. Ý tưởng cõa WLS-SVM (Weighted Least Squares Support Vector Machine) (công tr¼nh 5) xu§t ph¡t tø c¡c bài to¡n này. Th§y r¬ng, c¡c bài to¡n này mặc dù có thº gi£i đưñc, tuy nhi¶n c¡c ràng buëc b§t đẳng thùc đòi hỏi chúng ta ph£i đưa v· gi£i c¡c bài to¡n đối ng¨u, điều này v¨n tương đối phùc t¤p. Chúng ta có thº làm đơn gi£n bài to¡n hơn mà v¨n sû dụng chi¸n lược cụm-đối-lớp, b¬ng c¡ch dùng b¼nh phương tèi thiºu. 16
19. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM 4.2. LSSVM có trọng sè (WLS-SVM) Quay trở l¤i bài to¡n ph¥n lo¤i ở Mục 1.5. Trong trường hñp đơn gi£n, S-TSVM tỏ ra hi»u qu£ trong mô phỏng xu hướng ph¥n phèi dú li»u. H¼nh 4.1: S-TSVM trường hñp dú li»u có c§u trúc đơn gi£n Trong trường hñp dú li»u có c§u trúc phùc t¤p, S-TSVM chưa hi»u qu£ trong mô phỏng xu hướng dú li»u. Hơn núa, S-TSVM không khai th¡c thông tin v· sè lượng điểm dú li»u trong méi cụm. H¼nh 4.2: S-TSVM bị h¤n ch¸ khi dú li»u có c§u trúc phùc t¤p Để kh­c phục h¤n ch¸ này, WLS-SVM sû dụng chi¸n lược cụm-đối- lớp và khai th¡c thông tin v· sè lượng điểm dú li»u trong méi cụm để t¼m 17
20. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM (k + l) si¶u ph¯ng, méi si¶u ph¯ng là g¦n với mët cụm cõa lớp này và để lớp cán l¤i v· mët ph½a. Cụ thº, t¼m k si¶u ph¯ng sao cho: si¶u ph¯ng thù T i, fi+(x) = wi+x + bi+ = 0 là g¦n với cụm Ai và để lớp B v· mët ph½a; T t¼m l si¶u ph¯ng sao cho: si¶u ph¯ng thù j, fj−(x) = wj−x + bj− = 0 là g¦n với cụm Bj và để lớp A v· mët ph½a (xem H¼nh 4.3 và H¼nh 4.4). H¼nh 4.3: WLS-SVM trong trường hñp dú li»u có c§u trúc đơn gi£n. H¼nh 4.4: WLS-SVM trong trường hñp dú li»u có c§u trúc phùc t¤p Bë ph¥n lo¤i được chọn là: f(x) = argmin(f+(x); f−(x)); +; − 18
21. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM k l X mAi X mBj f (x) = f (x); f (x) = f (x): + m i+ − m j− i=1 A j=1 B Mët điểm dú li»u mới x được ph¥n lo¤i vào lớp f+g hay lớp {−} phụ thuëc vào f+(x) là b² hơn hay lớn hơn f−(x). 4.2.1. Trường hñp tuy¸n t½nh Chúng ta x¡c định (k + l) si¶u ph¯ng trong WLS-SVM b¬ng c¡ch gi£i (k + l) bài to¡n QP lồi chặt như sau 8 1 2 1 T 1 2 2 : s.t. (Bwi+ + eBbi+) + ξ = eB; 8 1 2 1 T 1 2 2 : s.t. (Awj− + eAbj−) + η = eA; i = 1; : : : ; k và j = 1; : : : ; l. B¬ng c¡ch thay th¸ c¡c ràng buëc đẳng thùc vào hàm mục ti¶u, gi£i c¡c đạo hàm b¬ng không ta có: h i−1 T T 1 T T µ+ T zi+ = [wi+; bi+] = H Hi + G G + I G eB; c+ i c+ h i−1 T T 1 T T µ− T zj− = [wj−; bj−] = G Gj + H H + I H eA: c− j c− Trong đó Hi = [Ai; eAi], G = [B; eB], Gj = [Bj; eBj], H = [A; eA], I là ma trªn đơn vị cỡ (n + 1). 4.2.2. Trường hñp phi tuy¸n WLS-SVM x¡c định (k + l) si¶u ph¯ng b¬ng c¡ch gi£i (k + l) bài to¡n QP lồi chặt như sau: 8 1 T 2 1 T 1 2 2 T : s.t. (K(B; C )ui+ + eBbi+) + ξ = eB; 19
22. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM 8 1 T 2 1 T 1 2 2 T : s.t. (K(A; C )uj− + eAbj−) + η = eA; B¬ng c¡ch làm tương tự trường hñp dú li»u tuy¸n t½nh ta có: h i−1 T T 1 T T µ+ T zi+ = [ui+; bi+] = H Hi + G G + I G eB; c+ i c+ h i−1 T T 1 T T µ− T zj− = [uj−; bj−] = G Gj + H H + I H eA: c− j c− T T Với Hi = [K(Ai; C ); eAi], G = [K(B; C ); eB], I là ma trªn đơn vị cỡ T T (m + 1), Gj = [K(Bj; C ); eBj], H = [K(A; C ); eA]. 4.3. Thực nghi»m 4.3.1. Tªp dú li»u gi£ 2 chi·u Thực hi»n c¡c thuªt to¡n TSVM, LSTSVM, S-TSVM và WLS-SVM tr¶n c¡c tªp dú li»u gi£ 2 chi·u có sè lượng lớn. 4.3.2. C¡c tªp dú li»u UCI So s¡nh v· thời gian hu§n luy»n, độ ch½nh x¡c kiºm thû, độ ch½nh x¡c th©m định ch²o 10-l¦n giúa c¡c thuªt to¡n WLS-SVM, S-TSVM, LSTSVM và TSVM. 4.4. Tiºu k¸t chương Như vªy, với chi¸n lược cụm-đối-lớp, WLS-SVM (công tr¼nh 5) đã khai th¡c thông tin v· sè lượng điểm dú li»u cõa méi cụm, thông tin c§u trúc cõa tøng cụm trong hu§n luy»n mô h¼nh. Thuªt to¡n tỏ ra hi»u qu£ v· mô phỏng xu hướng ph¥n phèi cõa c¡c cụm đối với c£ dú li»u có c§u trúc đơn gi£n và phùc t¤p. 20
23. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM KẾT LUẬN Trong lĩnh vực Học m¡y, ph¥n lo¤i m¨u có gi¡m s¡t đã, đang và s³ ti¸p tục ph¡t triºn không ngøng. Trong đó, thuªt to¡n SVM và c¡c bi¸n thº cõa nó v¨n tỏ ra hi»u qu£ so với c¡c phương ph¡p học m¡y kh¡c. Bởi l³, SVMs đưa bài to¡n ph¥n lo¤i m¨u v· mët bài to¡n tèi ưu, cụ thº là bài to¡n QP lồi hoặc lồi chặt. Luªn ¡n đã làm s¡ng tỏ r¬ng: tư tưởng to¡n học cõa SVM thực ch§t là t¼m c¡ch t¡ch c¡c lớp dú li»u bởi mët si¶u ph¯ng có kho£ng c¡ch đến c¡c tªp dú li»u là lớn nh§t, b¬ng mët phương ph¡p nh§t qu¡n là sû dụng quy t­c nh¥n tû Lagrange. Chương 1 là cung c§p c¡c kh¡i ni»m và k¸t qu£ cơ b£n v· to¡n. Cụ thº đó là hàm toàn phương, bài to¡n QP, điều ki»n tèi ưu cõa bài to¡n QP, bài to¡n đối ng¨u cõa bài to¡n QP lồi. Ti¸p đó là cơ sở to¡n học cõa SVM trong kỹ thuªt ph¥n lớp dú li»u, cho c¡c trường hñp kh¡c nhau, tø đơn gi£n đến phùc t¤p. Trường hñp đơn gi£n nh§t là hàm ph¥n lớp tuy¸n t½nh, ti¸p theo là kỹ thuªt si¶u ph¯ng l· m·m cho bài to¡n không t¡ch được tuy¸n t½nh, trường hñp hàm ph¥n lớp phi tuy¸n và cuèi cùng là ph¥n lớp có trọng sè. Chương 2 tr¼nh bày ng­n gọn mët sè bi¸n thº cõa SVM. Đầu ti¶n là c¡ch ti¸p cªn dùng hai si¶u ph¯ng song song để ph¥n lớp dú li»u (PSVM), sau đó là c¡c phương ph¡p ph¥n lớp dú li»u b¬ng c¡ch sû dụng hai si¶u ph¯ng không nh§t thi¸t song song (GEPSVM, LSTSVM, S-TSVM). Chúng tôi đã ch¿ ra ưu nhược cõa c¡c phương ph¡p tr¶n, khi dú li»u hai lớp có c§u trúc phùc t¤p. Chương 3 và chương 4 là c¡c k¸t qu£ mới mà chúng tôi đã công bè. Cụ 21
24. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM thº, Chương 3 là hai thuªt to¡n ph¥n lo¤i sû dụng chi¸n lược lớp-đối-cụm: SVM có c§u trúc có trọng sè (được gọi là WS-SVM, công tr¼nh 2) và C£i ti¸n cõa SVM dùng b¼nh phương tèi thiºu (được gọi là ILS-SVM, công tr¼nh 3). Bë ph¥n lo¤i cõa hai thuªt to¡n này đều dựa vào trung b¼nh có trọng sè c¡c kho£ng c¡ch tø mët điểm dú li»u đến c¡c si¶u ph¯ng g¦n với méi lớp. WS-SVM sû dụng thông tin c§u trúc theo cụm và được gi£i thông qua bài to¡n đối ng¨u, cán ILS-SVM sû dụng b¼nh phương tèi thiºu để t¼m ra nghi»m cõa c¡c bài to¡n QP. Chương 4 là bi¸n đổi cõa thuªt to¡n S-TSVM (công tr¼nh 4) và thuªt to¡n SVM dùng b¼nh phương tèi thiºu có trọng sè (được gọi là WLS-SVM, công tr¼nh 5) cho bài to¡n ph¥n lo¤i với chi¸n lược cụm-đối-lớp. Bë ph¥n lo¤i dựa vào trung b¼nh có trọng sè c¡c kho£ng c¡ch tø mët điểm tới c¡c si¶u ph¯ng g¦n với c¡c cụm. Thuªt to¡n WLS-SVM được gi£i b¬ng c¡ch sû dụng b¼nh phương tèi thiºu. C¡c thuªt to¡n đều gồm hai bước: Bước thù nh§t là ph¥n cụm trong méi lớp b¬ng phương ph¡p li¶n k¸t cõa Ward; Bước thù hai là hu§n luy»n mô h¼nh. Đối với c¡c bài to¡n có dú li»u lớn và méi lớp chùa nhi·u cụm có xu hướng ph¥n phèi kh¡c nhau, phương ph¡p cụm-đối-lớp tỏ ra hi»u qu£ hơn trong mô phỏng xu hướng ph¥n phèi cõa c¡c cụm và do đó đạt được độ ch½nh x¡c cao hơn trong ph¥n lo¤i. Có thº phương ph¡p này không phù hñp cho bài to¡n ph¥n lo¤i nhi·u lớp, tuy nhi¶n nó có thº hi»u qu£ đối với bài to¡n ph¥n lo¤i nhị ph¥n với dú li»u không c¥n b¬ng. K¸t hñp phương ph¡p lớp-đối-cụm và cụm-đối-lớp có thº gi£i quy¸t được bài to¡n ph¥n lo¤i nhi·u lớp hay không. Đây cũng là mët trong nhúng hướng nghi¶n cùu đáng để cëng đồng học thuªt quan t¥m tới. Ngoài ra, có thº ¡p dụng mët trong c¡c phương ph¡p tr¶n với c¡c kĩ thuªt xû lý t½n hi»u ¥m thanh để x¥y dựng ùng dụng nhªn d¤ng s­c th¡i giọng nói. 22
25. N¥ng cao hi»u n«ng ph¥n lớp dú li»u tr¶n cơ sở c£i ti¸n thuªt to¡n SVM DANH MỤC CÁC CÆNG TRÌNH KHOA HÅC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN 1. Nguy¹n Th¸ Cường, M¡y véc-tơ tựa song sinh và ¡p dụng, T¤p ch½ Khoa học và Công ngh», Đại học Khoa học, Đại học Hu¸, T. 17, Tr. 1-13, 2020. 2. Nguyen The Cuong and Huynh The Phung, Weighted structural support vector machine, Journal of Computer Science and Cybernetics, Vietnam, vol. 37, no. 1, pp. 43–56, 2021. 3. Nguyen The Cuong and Nguyen Thanh Vi, Improvement of least square - twin support vector machine, Journal of Research and Development on Information and Communication Technology, vol. 2021, no. 1, pp. 8-13, 2021. 4. Nguyen The Cuong, Hierarchical multi twin support vector machine, Hue University Journal of Science: Techniques and Technology, vol. 130, no. 2B, 2021. 5. Nguyen The Cuong and Huynh The Phung, Weighted least square - sup- port vector machine, in 2021 RIVF International Conference on Comput- ing and Communication Technologies (RIVF), Hanoi, ser. 15. IEEE, 2021. 23