Bài giảng Nhập môn khai phá dữ liệu - Chương 5: Phân lớp - Hà Quang Thụy

p
⚫ Giới thiệu
 ▪ Trực tiếp và gián tiếp
⚫ Trực tiếp
 ▪ 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 được học
 4. Lặp các bước 2-3 cho đến khi gặp điều kiện dừng
⚫ Gián tiếp
 ▪ Trích xuất luật từ mô hình phân lớp dữ liệu khác, chẳng hạn, mô
 hình cây quyết định, mô hình mạng nơ ron, 
 ▪ Ví dụ:C4.5Rule
Mở rộng luật: một số phương án
 ⚫ 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
 Mở rộng luật: một số phương án
⚫ Thuật toán RIPPER
▪ Bắt đầu từ một luật rỗng: {} → lớp
▪ Bổ sung các liên kết làm cực đại
 lợi ích thông tin FAIL
▪ 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 cả
 hai R0 và R1
 p0: số thể hiện đúng được bảo
 đảm bởi R0
 ▪ n0: số thể hiện sai được đảm bảo
 bởi R0
 ▪ P1: số thể hiện đúng được bảo
 đảm bởi R1
 ▪ n 1: số trường hợp sai được đảm
 bảo bởi R1
Luật phân lớp: từ cây quyết định
 Tập luật
 Liệt kê các đường đi từ gốc
Sinh luật gián tiếp: C4.5rules
⚫ Trích xuất luật từ cây quyết định chưa cắt tỉa
⚫ Với mỗi luật, r: A → y
 ▪ Xem xét luật thay thế r’: A’ → y, trong đó A’ nhận được từ A bằng
 cách bỏ đi một liên kết
 ▪ So sánh tỷ lệ lỗi r so với các r’
 ▪ Loại bỏ các r’ có lỗi thấp hơn r
 ▪ Lặp lại cho đến khi không cải thiện được lỗi tổng thể
⚫ Thay thế sắp xếp theo luật bằng sắp xếp theo tập con của
 luật (thứ tự lớp)
 ▪ 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ả của mỗi tập con
 ▪ Độ dài mô tả = L(lỗi) + g* L(mô hình)
 ▪ 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)
C4.5rules: Ví dụ
 Name Give Birth Lay Eggs Can Fly Live in Water Have Legs Class
 human yes no no no yes mammals
 python no yes no no no reptiles
 salmon no yes no yes no fishes
 whale yes no no yes no mammals
 frog no yes no sometimes yes amphibians
 komodo no yes no no yes reptiles
 bat yes no yes no yes mammals
 pigeon no yes yes no yes birds
 cat yes no no no yes mammals
 leopard shark yes no no yes no fishes
 turtle no yes no sometimes yes reptiles
 penguin no yes no sometimes yes birds
 porcupine yes no no no yes mammals
 eel no yes no yes no fishes
 salamander no yes no sometimes yes amphibians
 gila monster no yes no no yes reptiles
 platypus no yes no no yes mammals
 owl no yes yes no yes birds
 dolphin yes no no yes no mammals
 eagle no yes yes no yes birds
 C4.5rules: Ví dụ
 Give C4.5rules:
 Birth? (Give Birth=No, Can Fly=Yes) → Birds
 (Give Birth=No, Live in Water=Yes) → Fishes
 Yes No
 (Give Birth=Yes) → Mammals
 (Give Birth=No, Can Fly=No, Live in Water=No) → Reptiles
Mammals Live In ( ) → Amphibians
 Water?
 Yes No RIPPER:
 (Live in Water=Yes) → Fishes
 Sometimes (Have Legs=No) → Reptiles
 (Give Birth=No, Can Fly=No, Live In Water=No) 
 Fishes Amphibians Can → Reptiles
 Fly?
 (Can Fly=Yes,Give Birth=No) → Birds
 Yes No () → Mammals
 Birds Reptiles
Phân lớp Bayes
⚫ Giới thiệu
 ▪ Khung xác suất để xây dựng bộ phân lớp
 ▪ Mô hình phân lớp: Tập công thức tính xác suất
⚫ Cơ sở khoa học: X/suất có điều kiện, đ/lý Bayes
 ▪ Xác suất có điều kiện Hai biến cố A và C
 P(A,C) P(A,C)
 P(C | A) = ; P(A | C) =
 P(A) P(C)
 ▪ Định lý Bayes: P(c|x) = P(x|c).P(c)/P(x)
 ▪ P(x) bằng nhau cho tất cả các lớp
 ▪ Tìm c sao cho P(c|x) lớn nhất Tìm c sao cho P(x|c).P(c) 
 lớn nhất
 ▪ P(c): tần suất xuất hiện của các dữ liệu thuộc lớp c
 ▪ Vấn đề: cách thức tính P(x|c)?
⚫ Hai ví dụ áp dụng điển hình
 ▪ Khai phá quan điểm để đánh giá mức nhận thức về sản 
 phẩm trên thị trường
 ▪ Xây dựng bộ lọc thư rác
 Định lý Bayes: Ví dụ
⚫ Cho biết
 ▪ Bệnh nhân viêm màng não M có triệu chứng cứng cổ S 
 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
⚫ Với một bệnh nhân bị cứng cổ S, hỏi xác suất
 anh/cô ta bị viêm màng não M ? 
 P(S | M )P(M ) 0.5 1/50000
 P(M | S) = = = 0.0002
 P(S) 1/ 20
Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data Mining
(Chapter 5: Classification: Alternative Techniques), Addison Wesley, 2005,
Phân lớp Bayes
⚫ n+1 thuộc tính (bao gồm lớp) là các biến ngẫu 
 nhiên.
⚫ Cho một bản ghi với các giá trị thuộc tính (A1, A2, 
 , An) là giá trị quan sát được các biến ngẫu 
 nhiên
 ▪ Cần dự báo nhãn c
 ▪ Tìm lớp c để cực đại xác suất P(C|A1, A2, , An)
⚫ Có thể tính xác suất hậu nghiệm P(C|A1, A2, , 
 An) từ dữ liệu học? 
Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data Mining
(Chapter 5: Classification: Alternative Techniques), Addison Wesley, 2005,
Phân lớp Naïve Bayes
⚫ Giả thiết Naïve Bayes: 
 ⚫ giả thiết độc lập: xác suất xuất hiện của thuộc
 tính trong đối tượng độc lập với ngữ cảnh và vị
 trí của nó trong đối tượng:
 p(c | x, ) =  p(c | x,T)p(T | x)
 T in 
Phân lớp Naïve Bayes
⚫ Cho
 ▪ Tập ví dụ Dexam = Dlearn + Dtest
 ▪ Tập lớp C= {C1, C2, , Cn} với mỗi Ci một ngưỡng i > 0
⚫ Tính xác suất tiên nghiệm
 ▪ Trên tập ví dụ học Dlearn
 ▪ Xác suất p(Ci) = Mi/M, M= ||Dlearn||, Mi = ||X Dlearn  Ci||
 ▪ Xác suất một giá trị đặc trưng fj thuộc lớp C:
 1+ TF( f ,C) 1+ TF( f ,C)
 p( f | C) = j = j
 j |F |
 j | Fj | + |{d DC}|
 | Fj | +TF( fl ,C)
 l=1
 Fj : Tập các giá trị phân biệt của thuộc tính Aj
 DC: Tập ví dụ có nhãn lớp C
 TF (fj, C): số lần giá trị đặc trưng fj tại thuộc tính Aj xuất hiện
 trong C
 Phân lớp Naïve Bayes
 ⚫ Cho dữ liệu X mới
 ▪ Tính xác suất hậu nghiệm
 p(C)*  ( p( f j | C))
P(C | X ) = j 1..n ; X = ( f , f ,..., f )
 k j 2 n
  p(Ci )*  ( p( f j | Ci ))
 i=1 j 1..n
 ▪ Nếu P(C|X) > C thì X C
 ▪ n là số lượng thuộc tính, k là số lượng nhãn
 Phân lớp k-NN
  X l * Yl
 Sm( X ,Y ) = Cos( X ,Y ) = l
 2 2
  X l Yl
 l l
⚫ Cho trước
 - Một tập D các đối tượng dữ liệu biểu diễn bản ghi các đặc trưng
 - Một đo đo khoảng cách (Ơcơlit) hoặc tương tự (như trên)
 - Một số k > 0 (láng giềng gần nhất
⚫ Phân lớp đối tượng mới Xc được biểu diễn
 - Tính khoảng cách (độ tương tự) từ X tới tất cả dữ liệu thuộc D
 - Tìm k dữ liệu thuộc D gần X 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 
 của X: nhãn nhiều nhất trong k-láng giềng gần nhất
 Phân lớp k-NN: Ví dụ
 X X X
(a) 1-nearest neighbor (b) 2-nearest neighbor (c) 3-nearest neighbor
 ⚫ Ba trườ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ượng như nhau, chọn nhãn 
 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 –
 SVM): được Corters và Vapnik giới thiệu vào năm 1995.
 ⚫ SVM rất hiệu quả để giải quyết các bài toán với dữ liệu có 
 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}
 ⚫ Ci Є {-1,1} xác định dữ liệu dương hay âm
⚫ 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 dữ 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
 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: 11 2
 . = (1)
 22 
 ⚫ Thỏa mãn: 
 cdbin .1 +  1,...., = (2)
 ii 
⚫ Nếu dữ liệu học không tách rời tuyến tính: thêm biến {ξ1 ξn}:
 1 n
 ⚫ Cực tiểu: . +C i (3)
 2 i=1
 ⚫ Thỏa mãn: 
 cdbiniii( .1 + 1,....,) − =
 i 0 in = 1,...., (4)
 ⚫ Tổng quát: sử dụng hàm nhân
 - Biến đổi không gian biểu diễn dữ liệu sang số chiều lớn hơn để 
 khả tách tuyến tính
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
Sơ bộ về học bán giám sát
 ⚫ Học bán giám sát là gì ? Xiaojin Zhu [1] FQA
 ⚫ Học giám sát: tập ví dụ học đã đượ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)
 ⚫ ví dụ gắn nhãn
 ⚫ Thủ công: khó khăn → chuyên gia → tốn thời gian, tiền
 ⚫ Tự động: như tự động sinh corpus song hiệu quả chưa cao 
 ⚫ ví dụ chưa gắn nhãn
 ⚫ Dễ thu thập → nhiều
 ▪ 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 mở rộng
 ⚫ Có sẵn → có điều kiện tiến hành tự độ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 gắn 
 nhãn
 ⚫ Tạo ra bộ phân lớp tốt hơn so với chỉ dùng học giám sát: học 
 bán giám sát đòi hỏi điều kiện về dung lượng khối lượng
Cơ sở của học bán giám sát
 ⚫ Biểu diễn dữ liệu chưa mô tả hết ánh xạ gán nhãn
 trên dữ liệu.
 ⚫ Ánh xạ gán nhãn liên quan mô hình dữ liệu (mô
 hình/đặc trưng/nhân/ hàm tương tự) → mô hình đã
 có theo tự nhiên hoặc giả thiết dữ liệu tuân theo.
 Tập dữ liệu có nhãn chưa “đại diện miền dữ liệu”
 ⚫ Ví dụ trên hình vẽ cho phân lớp nhị phân
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ả
 ⚫ Nếu giả thiết mô hình không phù hợp → giảm hiệu 
 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ương pháp dựa theo đồ thị với trọng số cạnh là khoảng 
 cách
 ⚫ “Tồi” khi dùng phương pháp này song lại “tốt” khi 
 dùng phương pháp khác
 Phương pháp học bán giám sát
⚫ Các phương pháp học bán giám sát 
 điển hình
 ⚫ EM với mô hình trộn sinh
 ⚫ Self-training
 ⚫ Co-training
 ⚫ TSVM
 ⚫ Dựa trên đồ thị
 ⚫ ... 
⚫ So sánh các phương pháp
 ⚫ Đòi hỏi các giả thiết mô hình mạnh. Giả thiết mô 
 hình phù hợp cấu trúc dữ liệu: khó kiểm nghiệm
 ⚫ Một số định hướng lựa chọn
 ⚫ Lớp phân cụm tốt: dùng EM với mô hình sinh trộn.
 ⚫ Đặc trưng phân thành hai phần riêng rẽ: co-training
 ⚫ Nếu hai điểm tương tự hướng tới một lớp: dựa trên đồ thị
 ⚫ Đã 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
 ⚫ 
Phương pháp học bán giám sát
 ⚫ Dùng dữ liệu chưa gán nhãn
 ⚫ Hoặc biến dạng hoặc thay đổi thứ tự giả thiết thu nhờ chỉ dữ 
 liệu có nhãn
 ⚫ Mô tả chung
 ⚫ Giả thiết dưới dạng p(y|x) còn dữ liệu chưa có nhãn p(x)
 ⚫ 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ương pháp là phân biệt: TSVM, quy tắc hóa thông tin, 
 quá trình Gauxơ, dựa theo đồ thị
 ⚫ Có dữ liệu không nhãn: nhận được xác suất p(x)
 ⚫ Phân biệt “học lan truyền” với “học bán giám sát”
 ⚫ Đ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”
 ⚫ 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.
 ⚫ Lan truyền để thu hẹp lạ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ộ
 ⚫ 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ượng nhiều dữ liệu chưa nhãn cho P(x|y) mô hình 
 trộn đồng nhất. Miền dữ liệu được phân thành các thành 
 phần, 
 ⚫ Lý tưởng hóa tính "Đồng nhất": chỉ cần một đối tượng có 
 nhãn cho mỗi thành phần
 ⚫ Tính đồng nhất
 ⚫ Là tính chất cần có của mô hình
 ⚫ Cho họ phân bố {p} là đồng nhất nếu 1 2 thì p1 p2
 cho tới một hoán đối vị trí các thành phần tính khả tách 
 của phân bố tới các thành phần
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 → dữ liệu 
 không nhãn sẽ làm tăng độ chính xác phân lớp
 ⚫ 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
 ⚫ Cực đại EM địa phương
 ⚫ Miền áp dụng
 ⚫ Khi mô hình trộn chính xác
 ⚫ 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 (|DK| << |D|)
Mô hình sinh: Thuật toán EM
 ⚫ Nội dung thuật toán
 1: Cố định tập dữ liệu không nhãn DU  D \ DK dùng trong E-bước 
 và M-bước
 K
 2: dùng D xây dựng mô hình ban đầu 0
 3: for i = 0, 1, 2, . . . cho đến khi kết quả đảm bảo do
 4: for mỗi dữ liệu d DU do
 5: E-bước: dùng phân lớp Bayes thứ nhất xác định P(c|d,i)
 6: end for
 7: for mỗi lớp c và từ khóa t do
 8: M-bước: xác định c,t dùng công thức (*) để xây dựng mô hình 
 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 độ 
 đo hồi tưởng, chính xác, F1...
 ⚫ 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
 ⚫ dành tập Dtest để đánh giá
 ⚫ Độ 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
 ⚫ Nhân là gốc của mô hình sinh
 ⚫ Các ví dụ có nhãn được chuyển đổi thành vector
 Fisher để phân lớp
Self-Training
 ⚫ Giới thiệu
 ⚫ Là kỹ thuật phổ biến trong SSL
 ⚫ EM địa phương là dạng đặc biệt của seft-training
 ⚫ 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
 Tìm tập con U’  U có độ tin cậy cao nhất:
 L + U’ L
 U – U’ U
 Vấn đề tập U' có "độ tin cậy cao nhất"
 ⚫ Thủ tục "bootstrapping"
 ⚫ Thường được áp dụng cho các bài toán NLP
Co-Training
 ⚫ Tư tưở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
 ⚫ 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ới ngưỡng được xác định trước
 ⚫ Một số lưu ý
 ⚫ Tập dữ liệu gán nhãn có ảnh hưởng lớn đến co-
 training
 ⚫ Quá ít: không hỗ trợ co-training
 ⚫ Quá nhiều: không thu lợi từ co-training
 ⚫ Cơ sở tăng hiệu quả co-training: thiết lập 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