›
›

Khai phá dữ liệu - Chương 5: Phân lớp

ppt 63 trang vanle 3660
Download
Bạn đang xem 20 trang mẫu của tài liệu "Khai phá dữ liệu - Chương 5: Phân lớp", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptkhai_pha_du_lieu_chuong_5_phan_lop.ppt

Nội dung text: Khai phá dữ liệu - Chương 5: Phân lớp

  1. BÀI GIẢNG NHẬP MƠN KHAI PHÁ DỮ LIỆU CHƯƠNG 5. PHÂN LỚP PGS. TS. HÀ QUANG THỤY HÀ NỘI 9-2011 TRƯỜNG ĐẠI HỌC CƠNG NGHỆ ĐẠI HỌC QUỐC GIA HÀ NỘI 1
  2. Nội dung Giớ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 2
  3. Bài tốn phân lớp ⚫ Đầu vào ⚫ Tập dữ liệu D = {di} ⚫ Tập các lớp C1, C2, , Ck mỗi dữ liệu d thuộc một lớp Ci ⚫ Tập ví dụ Dexam = D1+D2+ + Dk với Di={d Dexam: d thuộc Ci} ⚫ Tập ví dụ Dexam đại diện cho tập D ⚫ Đầu ra ⚫ Mơ hình phân lớp: ánh xạ từ D sang C ⚫ Sử dụng mơ hình ⚫ d D \ Dexam : xác định lớp của đối tượng d 3
  4. Phân lớp: Quá trình hai pha ⚫ Xây dựng mơ hình: Tìm mơ tả cho tập lớp đã cĩ ⚫ Cho trước tập lớp C = {C1, C2, , Ck} ⚫ Cho ánh xạ (chưa biết) từ miền D sang tập lớp C ⚫ Cĩ tập ví dụ Dexam=D1+D2+ + Dk với Di={d Dexam: d Ci} 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 tốn học ⚫ Pha 1: Dạy bộ phân lớp ⚫ Tách Dexam thành Dtrain (2/3) + Dtest (1/3). Dtrain và Dtest “tính đại 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ượng nhất ⚫ Pha 2: Sử dụng bộ phân lớp ⚫ d D \ Dexam : xác định lớp của d. 4
  5. Ví dụ phân lớp: Bài tốn cho vay Tid Refund Marital Status Taxable Income Cheat 1 No Single 75K No 2 Yes Married 50K No 3 No Single 75K No 4 No Married 150K Yes 5 No Single 40K No 6 No Married 80K Yes 7 No Single 75K No 8 Yes Married 50K No 9 Yes Married 50K No 10 No Married 150K Yes 11 No Single 40K No 12 No Married 150K Yes 13 No Married 80K Yes 14 No Single 40K No 15 No Married 80K Yes B 5
  6. Phân lớp: Quá trình hai pha 6
  7. Phân lớp: Quá trình hai pha Tid Attrib1 Attrib2 Attrib3 Class Learning 1 Yes Large 125K No algorithm 2 No Medium 100K No 3 No Small 70K No 4 Yes Medium 120K No Induction 5 No Large 95K Yes 6 No Medium 60K No 7 Yes Large 220K No Learn 8 No Small 85K Yes Model 9 No Medium 75K No 10 No Small 90K Yes 10 Model Training Set Apply Tid Attrib1 Attrib2 Attrib3 Class Model 11 No Small 55K ? 12 Yes Medium 80K ? 13 Yes Large 110K ? Deduction 14 No Small 95K ? 15 No Large 67K ? 10 Test Set 7
  8. 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. ⚫ Phân lớp đơn nhãn/ đa nhãn: ⚫ Đơn nhãn: mỗi tài liệu được gán vào chính xác một lớp. ⚫ Đa nhãn: một tài liệu cĩ thể được gán nhiều hơn một lớp. ⚫ Phân cấp: lớp này là cha/con của lớp kia 8
  9. Các vấn đề đánh giá mơ hình – Các phương pháp đánh giá hiệu quả Câu hỏi: Làm thế nào để đánh giá được hiệu quả của một mơ hình? – Độ đo để đánh giá hiệu quả Câu hỏi: Làm thế nào để cĩ được ước tính đáng tin cậy? – Phương pháp so sánh mơ hình Câu hỏi: Làm thế nào để so sánh hiệu quả tương đối giữa các mơ hình cĩ tính cạnh tranh? 9
  10. Đánh giá phân lớp nhị phân – Theo dữ liệu test – Giá trị thực: P dương / N âm; Giá trị qua phân lớp: T đúng/F sai. : cịn gọi là ma trận nhầm lẫn – Sử dụng các ký hiệu TP (true positives), TN (true negatives), FP (false positives), FN (false negatives) • TP: số ví dụ dương P mà thuật tốn phân lớp cho giá trị đúng T • TN: số ví dụ âm N mà thuật tốn phân lớp cho giá trị đúng T • FP: số ví dụ dương P mà thuật tốn phân lớp cho giá trị sai F - FN: số ví dụ âm N mà thuật tốn phân lớp cho giá trị sai F - Độ hồi tưởng , độ chính xác , các độ đo F1 và F TP TP = = TP + FP TP +TN 10
  11. Đánh giá phân lớp nhị phân – Phươ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) – Ma trận nhầm lẫn Lớp dự báo Lớp = 1 Lớp = 0 Lớp = 1 f f Lớp thực sự 11 10 Lớp = 0 f01 f00 11
  12. 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ự đố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ĩ = 1/10=0.1; =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 12
  13. Đánh giá phân lớp đa lớp - Bài tốn ban đầu: C gồm cĩ k lớp – Đối với mỗi lớp Ci , cho thực hiện thuật tốn với các dữ liệu thuộc Dtest nhận được các đại lượng TPi, TFi, FPi, FNi (như bảng dưới đây) Giá trị thực Lớp Ci Khơng thuộc Thuộc lớp Ci lớp Ci Thuộc lớp Ci Giá trị qua bộ TPi TNi phân lớp đa lớp Khơng thuộc FPi FNi lớp Ci 13
  14. Đánh giá phân lớp đa lớp ⚫ Tương tự bộ phân lớp hai lớp (nhị phân) ⚫ Độ chính xác Pri của lớp Ci là tỷ lệ số ví dụ dương được thuật tốn phân lớp cho giá trị đúng trên tổng số ví dụ được thuật tốn phân lớp vào lớp Ci : TPi Pri = TPi + TNi ⚫ Độ hồi tưởng Rei của lớp Ci là tỷ lệ số ví dụ dương được thuật tốn phân lớp cho giá trị đúng trên tổng số ví dụ dương thực sự thuộc lớp Ci: TPi Re i = TPi + FPi 14
  15. Đánh giá phân lớp đa lớp - Các giá trị i và i : độ hồi phục và độ chính xác đối với lớp Ci. - Đánh giá theo các độ đo - vi trung bình-microaveraging (được ưa chuộng)  và  - trung bình lớn-macroaveraging M và M 1 K K M = M 1  c =  c K c=1 K c=1 K K TP TPc  = c=1 c  c=1 K = K (TPc + FPc ) (TP +TN ) c=1 c=1 c c 15
  16. 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 Nạ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 Neural Networks ⚫ Một số phương pháp khác 16
  17. 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 ▪ Gốc: tên thuộc tính; khơng cĩ cung vào + khơng/một số cung ra ▪ Nút trong: tên thuộc tính; cĩ chính xác một cung vào và một số cung ra (gắn với điều kiện kiểm tra giá trị thuộc tính của nút) ▪ Lá hoặc nút kết thúc: giá trị lớp; cĩ chính xác một cung vào + khơng cĩ cung ra. ▪ Ví dụ: xem trang tiếp theo ⚫ Xây dựng cây quyết định ▪ Phương châm: “chia để trị”, “chia nhỏ và chế ngự”. Mỗi nút tương ứng với một tập các ví dụ học. Gốc: tồn bộ dữ liệu học ▪ Một số thuật tốn phổ biến: Hunt, họ ID3+C4.5+C5.x ⚫ Sử dụng cây quyết định ▪ Kiểm tra từ gốc theo các điều kiện
  18. Ví dụ cây quyết định và sử dụng Kết luận: Gán giá trị YES vào trường Cheat cho bản ghi
  19. 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 0 1 then Class AI = Yes. 2. If System=0 and Process=1 Process Timetable then Class AI = No. 3. If System=1 and Timetable=1 0 1 0 then Class AI = Yes. 4. If System=1 and Timetable=0 1 then Class AI = No. Yes No No Yes
  20. Dựng cây quyết định: thuật tốn Hunt ⚫ Thuật tốn dựng cây quyết định sớm nhất, đệ quy theo nút của cây, bắt đầu từ gốc ⚫ Input ▪ Cho nút t trên cây quyết định đang được xem xét ▪ Cho tập các ví dụ học Dt. ▪ Cho tập nhãn lớp (giá trị lớp) y1, 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 ⚫ Nội dung 1: Nếu mọi ví dụ trong Dt đều thuộc vào một lớp y thì nút t là một lá và được gán nhãn y. 2: Nếu Dt chứa các ví dụ thuộc nhiều lớp thì 2.1. Chọn 1 thuộc tính A để phân hoạch Dt và gán nhãn nút t là A 2.2. Tạo phân hoạch Dt theo tập giá trị của A thành các tập con 2.3. Mỗi tập con theo phân hoạch của Dt tương ứng với một nút con u của t: cung nối t tới u là miền giá trị A theo phân hoạch, tập con nĩi trên được xem xét vơi u tiếp theo. Thực hiện thuật tốn với từng nút con u của t.
  21. Ví dụ: thuật tốn Hunt Giải thích - Xuất phát từ gốc với 10 bản ghi -Thực hiện bước 2: chọn thuộc tính Refund 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ừ trái sang phải. 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 và Yes nên áp dụng bước 2. Chọn thuộc tính Marital Status với phân hoạch Married và hai giá trị kia
  22. Thuật tốn cây quyết định ID3
  23. Thuộc tính tốt nhất: Độ đo Gini ⚫ Bước 4.1. chọn thuộc tính A tốt nhất gán cho nút t. ⚫ Tồn tại một số độ đo: Gini, Information gain ⚫ Độ đo Gini ▪ Đo tính hỗn tạp của một tập ví dụ mẫu 2 ▪ Cơng thức tính độ đo Gini cho nút t: Gini(t) =1− p( j | t) j=1 Trong đĩ p(j|t) là tần suất liên quan của lớp j tại nút t ▪ Gini (t) lớn nhất = 1-1/nc (với nc là số các lớp tại nút t): khi các bản ghi tại t phân bố đều cho nc lớp; tính hỗn tạp cao nhất, khơng cĩ phân biệt giữa các lớp ▪ Gini (t) nhỏ nhất = 0 khi tất cả các bản ghi thuộc một lớp duy nhất. ⚫ Ví dụ: Bốn trường hợp C1 0 C1 1 C1 2 C1 3 C2 6 C2 5 C2 4 C2 3 Gini=0.000 Gini=0.278 Gini=0.444 Gini=0.500
  24. Chia tập theo độ đo Gini ⚫ Dùng trong các thuật tốn CART, SLIQ, SPRINT ⚫ Khi một nút t được phân hoạch thành k phần (k nút con của t) thì chất lượng của việc chia tính bằng k ni GINIsplit =  GINI(i) i=1 n trong đĩ ▪ n là số bản ghi của tập bản ghi tại nút t, ▪ .ni là số lượng bản ghi tại nút con I (của nút t).
  25. Chia tập theo độ đo Gini: Ví dụ ⚫ Tính tốn GINI cho Refund (Yes, No), Marital Status (Single&Divorced, Married) và Taxable Income (<80K, 80K). ⚫ Refund: 3/10 * (0) + 7/10 * (1-(3/7)2 – (4/7)2) = 7/10*(24/49) = 24/70 ⚫ Marital Status: 4/10 * 0 + 6/10 * (1- (3/6) 2 – (3/6) 2) = 6/10 * ½ = 3/10 ⚫ Taxable Income: thuộc tính liên tục cần chia khoảng (tồn tại một số phương pháp theo Gini, kết quả 2 thùng và 80K là mốc) k n GINI = i GINI(i) 2 2 split  3/10 * (0) + 7/10 * (1-(3/7) – (4/7) ) = i=1 n 7/10*(24/49) = 24/70 2 Như vậy, Gini của Refund và Taxable Gini(t) =1− p( j | t) j=1 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.
  26. 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 tốn ID3, họ C4.5 ⚫ Entropy Entropy(t) = − p( j | t)log p( j | t) ▪ Cơng thức tính entropy nút t: j Trong đĩ p(j|t) là tần suất liên quan của lớp j tại nút t độ khơng đồng nhất tại nút t. ▪ Entropy (t) lớn nhất = log (nc) (với nc là số các lớp tại nút t): khi các bản ghi tại t phân bố đều cho nc lớp; tính hỗn tạp cao nhất, khơng cĩ phân biệt giữa các lớp ▪ Entropy (t) nhỏ nhất = 0 khi tất cả các bản ghi thuộc một lớp duy nhất. ▪ Lấy loga cơ số 2 thay cho loga tự nhiên ⚫ Tính tốn entropy (t) cho một nút tương tự như Gini (t)
  27. Chọn thuộc tính: Information Gain ⚫ Độ đo Information Gain k ni Gainchia = entropy(t) −  entropy(i) i=1 n Trong đĩ, n là số lượng bản ghi tại nút t, k là số tập con trong phân hoạch, ni là số lượng bản ghi trong tập con thứ i. Độ đo giảm entropy sau khi phân hoạch: chọn thuộc tính làm cho Gain đạt lớn nhất. C4.5 là một trong 10 thuật tốn KPDL phố biến nhất. ▪ Hạn chế: Xu hướng chọn phân hoạch chia thành nhiều tập con ⚫ Cải tiến Gain k n n GainRATIO = chia SplitINFO = − i log i SplitINFO i=1 n n ▪ Dùng GainRatio để khắc phục xu hướng chọn phân hoạch nhiều tập con ⚫ Áp dụng: Tự tiến hành
  28. Phân lớp dựa trên luật ⚫ Giới thiệu ▪ Phân lớp các bản ghi dựa vào tập các luật “kiểu” if then ⚫ Luật ▪ Luật: → y Trong đĩ: 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). ▪ Ví dụ Refund = ‘Yes” → Cheat = “No” (Refund = “No”)  (Marital Status = “Married”) → Cheat = “No” ⚫ Sử dụng luật ▪ Một 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 đáp ứng điều kiện của luật. ▪ Khi đĩ, vế phải của luật cũng được áp dụng cho thể hiện.
  29. Xây dựng luật phân lớ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
  30. 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 tố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 ⚫ Thuật tố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
  31. 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
  32. 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 tố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)
  33. 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
  34. 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
  35. Phân lớp Bayes ⚫ Giới thiệu ▪ Khung xác suất để xây dựng bộ phân lớp ▪ Xác suất cĩ điều kiện P(A,C) P(C | A) = Hai biến cố A và C P(A) P(A,C) P(A | C) = 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 tài liệu thuộc lớp c ▪ Vấn đề: làm thế nào để tính P(x|c)?
  36. Đị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 ? 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,
  37. Phân lớp Bayes ⚫ Các thuộc tính (bao gồm nhãn 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) ▪ 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 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,
  38. Phân lớp Nạve Bayes ⚫ Giả thiết Nạ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 
  39. Phân lớp văn bản Nạve Bayes ⚫ Cho ▪ Tập ví dụ Dexam = Dlearn + Dtest ▪ Tập từ vựng V = {f1, f2, , f||V||} ▪ 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 ▪ p(Ci) = Mi/M, M= ||Dlearn||, Mi = ||Doc Dlearn / Doc Ci|| ▪ Xác suất một đặc trưng (từ) fj thuộc lớp C: 1+TF( f j ,C) P( f j | C) = n |V | +TF( jl ,Ci ) i=1 ⚫ Cho tài liệu Doc mới TF (Fj ,Doc) ▪ Tính xác suất hậu nghiệm p(C)* ( p(Fj | C) F V ▪ j Nếu P(C|Doc) > C P(C | Doc) = n TF (Fj ,Doc) thì Doc C!  p(Ci )* ( p(Fj | Ci ) i=1 Fj V
  40. Phân lớp k-NN  X l *Yl l Sm(Doc,Di ) = Cos(Doc,Di ) = 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 Doc được biểu diễn - Tính khoảng cách (độ tương tự) từ Doc tới tất cả dữ liệu thuộc D - 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 của Doc: nhãn nhiều nhất trong k-láng giềng gần nhất
  41. 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
  42. Thuật tốn SVM ⚫ Thuật tố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 tốn với dữ liệu cĩ số chiều lớn (như các vector biểu diễn văn bản).
  43. Thuật tố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 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
  44. Thuật tốn SVM
  45. Thuật tố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: c . d+ b 1  i = 1, , n (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}: ⚫ Cực tiểu: 1 n . +C i (3) ⚫ Thỏa mãn: 2 i=1 ci( . d i+ b) 1 − i  i = 1, , n i 0 in = 1, , (4)
  46. 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
  47. 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]) ∼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 with co-training. InternationalJoint Conference on 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
  48. Sơ bộ về học bán giám sát ⚫ Học bán giám sát là gì ? Xiao 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
  49. 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 ⚫ 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 (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.
  50. 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
  51. 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 ⚫
  52. 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 tố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ĩ.
  53. Mơ hình sinh: Thuật tố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 tài 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 hố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
  54. Mơ hình sinh: Thuật tố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|)
  55. Mơ hình sinh: Thuật tốn EM ⚫ Nội dung thuật tốn 1: Cố định tập tài 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 tài 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
  56. Mơ hình sinh: Thuật tố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ị tồ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 tốn nhân là Bayes naive: cĩ thể chọn thuật tốn cơ bản khác ⚫ Chọn điểm bắt đầu bằng học tích cực
  57. Mơ hình sinh: Thuật tốn khác ⚫ Phân cụm - và - Nhãn ⚫ Sử dụng phân cụm cho tồ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
  58. 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 tốn NLP
  59. 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
  60. Co-Training ⚫ Mơ hình thuật tốn
  61. 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
  62. Chặn thay đổi miền dày đặc ⚫ Transductive SVMs (S3VMs) ⚫ Phương pháp phân biệt làm việc trên p(y|x) trực tiếp ⚫ Khi p(x) và p(y|x) khơng tương thích → đưa p(x) ra khỏi miền dầy đặc ⚫ Quá trình Gauxơ)
  63. Mơ hình đồ thị ⚫ Biểu diễn dữ liệu chưa mơ tả hết ánh xạ gán 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 (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.