Bài giảng nhập môn khai phá dữ liệu - Chương 1: Giới thiệu chung về khai phá dữ liệu

dụ  milk  wheat bread [support = 8%, confidence = 70%]  2% milk  wheat bread [support = 2%, confidence = 72%]  Nói rằng: luật đầu tiên là tổ tiên luật thứ hai.  Một luật là dư thừa nếu độ hỗ trợ của nó là khít với giá trị “mong muốn”, dựa theo tổ tiên của luật. 134 26 Luật kết hợp định lượng age(X,”30-34”)  income(X,”24K - 48K”)  buys(X,”high resolution TV”)  Thuộc tính số là sự rời rạc hóa động d  Độ tin cậy hoặc độ cô đọng của luật là cực đại  Luật kết hợp định lượng 2-D: Aquan1  Aquan2  Acat  Phân cụm các luật kết hợp Liền kề nhau từ các luật Tổng quát dựa trên Lưới 2-D  Ví dụ Khai phá luật KH dựa theo khoảng cách  Phương pháp đóng thùng không nắm bắt được ngữ nghĩa của dữ liệu khoảng  Phân vùng dựa trên khoảng cách, rời rạc có ý nghĩa hơn khi xem xét :  Mật độ/ số điểm trong một khoảng  Tính “gần gũi” của các điểm trong một khoảng Price($) Equi-width (width $10) Equi-depth (depth 2) Distance- based 7 [0,10] [7,20] [7,7] 20 [11,20] [22,50] [20,22] 22 [21,30] [51,53] [50,53] 50 [31,40] 51 [41,50] 53 [51,60] 135 27 Độ đo hấp dẫn: Tương quan (nâng cao)  play basketball  eat cereal [40%, 66.7%] là lạc  Phần trĕm chung của sinh viên ĕn ngũ cốc là 75% cao hơn so với 66.7%.  play basketball  not eat cereal [20%, 33.3%] là chính xác hơn, do độ hỗ trợ và tin cậy thấp hơn  Độ đo sự kiện phụ thuộc/tương quan: lift (nâng cao) Basketball Not basketball Sum (row) Cereal 2000 1750 3750 Not cereal 1000 250 1250 Sum(col.) 3000 2000 5000)()( )( , BPAP BAPcorr BA  Chương 4: Khai phá luật kết hợp  Khai phá luật kết hợp (Association rule)  Các thuật toán khai phá vô hướng luật kết hợp (giá trị lôgic đơn chiều) trong CSDL giao dịch  Khai phá kiểu đa dạng luật kết hợp/tương quan  Khai phá kết hợp dựa theo ràng buộc  Khai phá mẫu dãy 136 28 KPDL dựa trên ràng buộc  Tìm tất cả các mẫu trong CSDL tự động? — phi hiện thực!  Mẫu có thể quá nhiều mà không mục đích!  KPDL nên là quá trình tương tác  Người dùng trực tiếp xác định KPDL gì khi dùng ngôn ngữ hỏi KPDL (hoặc giao diện đồ họa)  KP dựa theo ràng buộc  Linh hoạt người dùng: cung cấp ràng buộc trên cái mà KP  Tối ưu hệ thống: thĕm dò các ràng buộc để hiệu quả KP: KP dựa theo ràng buộc Ràng buộc trong KPDL  Ràng buộc kiểu tri thức:  classification, association, etc.  Ràng buộc dữ liệu — dùng câu hỏi kiếu SQL  Tìm các cặp sản phẩn mua cùng nhau trong Vancouver vào Dec.’00  Ràng buộc chiều/cấp  Liên quan tới vùng, giá, loại hàng, lớp khách hàng  Ràng buộc luật (mẫu)  Mua hàng nhỏ (price < $10) nhanh hơn mua hàng lớn (sum > $200)  Ràng buộc hấp dẫn  Luật mạng: min_support  3%, min_confidence  60% 137 29 KP ràng buộc tìm kiếm dựa theo ràng buộc  KP ràng buộc tìm/lập luận dựa theo ràng buộc  Cả hai hướng tới rút gọn không gian tìm kiếm  Tìm mọi mẫu bảm đảm ràng buộc tìm một vài (một_ câu trả lời của tìm dựa theo ràng buộc trong AI (TTNT)  Cố tìm theo ràng buộc tìm kiếm heuristic  Tích hợp hai cái cho một bài toán tìm kiếm thú vị  KP ràng buộc quá trình hỏi trong hệ CSDL quan hệ  Quá trình hỏi trong CSDL quan hệ đòi hỏi tìm tất cả  KP mẫu ràng buộc chung một triết lý tương tựng như cố gắng chọn về chiều sâu của câu hỏi KP mấu phổ biến ràng buộc: vấn đề tố ưu hóa câu hỏi  Cho một câu hỏi KP Mấu phổ biến với một tập ràng buộc C, thì thuật toán nên là  Mạnh mẽ: chỉ tìm các tập phố biến bảo đảm ràng buộc C  đầy đủ: Tìm tất cả tập phổ biến bảo đảm ràng buộc C  Giải pháp “thơ ngây/hồn nhiên” (naïve)  Tìm tất cát tập PB sau đó kiểm tra ràng buộc  Tiếp cận hiệu quả hơn  Phân tích tính chất các ràng buộc một cách toàn diện  Khai thác chúng sâu sắc có thể nhất trong tính toán mẫu PB. 138 30 Không đơn điêu trong KP theo ràng buộc  Chống đơn điệu (Anti-monotonicity)  Một tập mục S vi phạm ràng buộc, mọi tập lớn hơn nó cũng vi phạm  sum(S.Price)  v là chống đơn điệu  sum(S.Price)  v là không chống đơn điệu  Ví dụ. C: range(S.profit)  15 là chống đơn điệu  Tập mục ab vi phạm C  Cũng vậy mọi tập chứa ab TID Transaction 10 a, b, c, d, f 20 b, c, d, f, g, h 30 a, c, d, e, f 40 c, e, f, g TDB (min_sup=2) Item Profit a 40 b 0 c -20 d 10 e -30 f 30 g 20 h -10 Ràng buộc nào là chống đơn điệu Ràng buộc Chống đơn điệu v  S No S  V no S  V yes min(S)  v no min(S)  v yes max(S)  v yes max(S)  v no count(S)  v yes count(S)  v no sum(S)  v ( a  S, a  0 ) yes sum(S)  v ( a  S, a  0 ) no range(S)  v yes range(S)  v no avg(S)  v,   { , ,  } convertible support(S)   yes support(S)   no 139 31 Tính đơn điệu trong KP luật dựa theo ràng buộc  Tính đơn điệu  Khi một tập mục S thỏa mãn ràng buộc, thì mọi tập lớn hơn của nó cũng thỏa mãn  sum(S.Price)  v là đơn điệu  min(S.Price)  v là đơn điệu  Ví dụ. C: range(S.profit)  15  Tập mục ab đảm bảo C  Cũng vậy mọi tập chứa ab TID Transaction 10 a, b, c, d, f 20 b, c, d, f, g, h 30 a, c, d, e, f 40 c, e, f, g TDB (min_sup=2) Item Profit a 40 b 0 c -20 d 10 e -30 f 30 g 20 h -10 Ràng buộc đơn điệu Ràng buộc Đơn điệu v  S yes S  V yes S  V no min(S)  v yes min(S)  v no max(S)  v no max(S)  v yes count(S)  v no count(S)  v yes sum(S)  v ( a  S, a  0 ) no sum(S)  v ( a  S, a  0 ) yes range(S)  v no range(S)  v yes avg(S)  v,   { , ,  } convertible support(S)   no support(S)   yes 140 32 Tính cô đọng  Tính cô đọng:  Cho A1, là tập mục bảo đảm một ràng buộc cô đọng C, thì mọi S bảm đảm C là dựa trên A1 , chằng hạn., S chứa một tập con thuộc A1  Tư tưởng: Bỏ qua xem xét CSDL giao dịch, có chĕng một tập mục S bảo đảm ràng buộc C có thể được xác định dựa theo việc chọn các mục  min(S.Price)  v là cô đọng  sum(S.Price)  v không cô đọng  Tối ưu hóa: Nếu C là cô đọng có thể đẩy đếm trước Ràng buộc cô đọng Ràng buộc Cô đọng v  S yes S  V yes S  V yes min(S)  v yes min(S)  v yes max(S)  v yes max(S)  v yes count(S)  v weakly count(S)  v weakly sum(S)  v ( a  S, a  0 ) no sum(S)  v ( a  S, a  0 ) no range(S)  v no range(S)  v no avg(S)  v,   { , ,  } no support(S)   no support(S)   no 141 33 Thuật toán Apriori— Ví dụ TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5 Database D itemset sup. {1} 2 {2} 3 {3} 3 {4} 1 {5} 3 itemset sup. {1} 2 {2} 3 {3} 3 {5} 3 Scan D C1 L1 itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5} itemset sup {1 2} 1 {1 3} 2 {1 5} 1 {2 3} 2 {2 5} 3 {3 5} 2 itemset sup {1 3} 2 {2 3} 2 {2 5} 3 {3 5} 2 L2 C2 C2Scan D C3 L3itemset{2 3 5} Scan D itemset sup {2 3 5} 2 Thuật toán Naïve: Apriori +ràng buộc TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5 Database D itemset sup. {1} 2 {2} 3 {3} 3 {4} 1 {5} 3 itemset sup. {1} 2 {2} 3 {3} 3 {5} 3 Scan D C1 L1 itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5} itemset sup {1 2} 1 {1 3} 2 {1 5} 1 {2 3} 2 {2 5} 3 {3 5} 2 itemset sup {1 3} 2 {2 3} 2 {2 5} 3 {3 5} 2 L2 C2 C2Scan D C3 L3itemset{2 3 5} Scan D itemset sup {2 3 5} 2 Constraint: Sum{S.price < 5} 142 34 Thuật toán Apriori ràng buộc: Đẩy ràng buộc chống đơn điệu xuống sâu TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5 Database D itemset sup. {1} 2 {2} 3 {3} 3 {4} 1 {5} 3 itemset sup. {1} 2 {2} 3 {3} 3 {5} 3 Scan D C1 L1 itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5} itemset sup {1 2} 1 {1 3} 2 {1 5} 1 {2 3} 2 {2 5} 3 {3 5} 2 itemset sup {1 3} 2 {2 3} 2 {2 5} 3 {3 5} 2 L2 C2 C2Scan D C3 L3itemset{2 3 5} Scan D itemset sup {2 3 5} 2 Constraint: Sum{S.price < 5} Thuật toán Apriori ràng buộc: Đẩy ràng buộc chống đơn điệu xuống sâu TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5 Database D itemset sup. {1} 2 {2} 3 {3} 3 {4} 1 {5} 3 itemset sup. {1} 2 {2} 3 {3} 3 {5} 3 Scan D C1 L1 itemset {1 2} {1 3} {1 5} {2 3} {2 5} {3 5} itemset sup {1 2} 1 {1 3} 2 {1 5} 1 {2 3} 2 {2 5} 3 {3 5} 2 itemset sup {1 3} 2 {2 3} 2 {2 5} 3 {3 5} 2 L2 C2 C2Scan D C3 L3itemset{2 3 5} Scan D itemset sup {2 3 5} 2 Constraint: min{S.price <= 1 } 143 35 Chương 4: Khai phá luật kết hợp  Khai phá luật kết hợp (Association rule)  Các thuật toán khai phá vô hướng luật kết hợp (giá trị lôgic đơn chiều) trong CSDL giao dịch  Khai phá kiểu đa dạng luật kết hợp/tương quan  Khai phá kết hợp dựa theo ràng buộc  Khai phá mẫu dãy CSDL tuần tự và Phân tích mẫu tuần tự Phần mềm phân tích chuỗi thời gian EidoSearch: Trợ giúp đánh dấu mẫu dữ liệu hấp dẫn và EidoSearch đi tìm mọi mẫu tương tự từ quá khứ và hiện tại, phân tích kết quả tìm kiếm này, và chỉ ra xu hướng gì sẽ xảy ra. Gait-CAD Matlab toolbox: trực quan hóa và phân tích chuỗi thời gian, bao gồm phân lớp, hồi quy, và phân cụm. Giấy phép GNU-GPL. Miningco: chương trình mã nguồn mở tự động tìm ra mẫu và quan hệ trong weblogs và các bộ dữ liệu khác. SAS Enterprise Miner XAffinity (TM): xác định mối quan hệ thân hoặc mẫu trong giao dịch và dòng dữ liệu nháy phím 144 36 CSDL TT và PT MTT (2)  CSDL giao dịch, CSDL chuỗi thời gian CSDL tuần tự  Mấu PB mấu TT (PB)  Ứng dụng của KP Mấu TT  Tuần tự mua của khách hàng:  Đầu tiên mua máy tính, sau đó CD-ROM, và sau đó là máy ảnh số, trong vòng 3 tháng.  Phẫu thuật y tế, thảm họa tự nhiên (động đất), quá trình KH và kỹ nghệ, chứng khoán và thị trường.  Mẫu gọi điện thoại, dòng click tại Weblogs  Dãy DNA và cấu trúc gene Khái niệm KP mấu TT  Cho một tập các dãy, tìm tập đầy đủ các dãy con phổ biến CSDL dãy TT dãy TT : Một phần tử chứa một tập mục. Tập mục trong một phần tử là không thứ tự , và viết chúng theo ABC. là dãy con của Cho độ hỗ trợ min_sup =2, là mẫu tuần tự sequential pattern SID sequence 10 20 30 40 145 37 Một số chủ đề khai phá dữ liệu nóng 146 03/02/17 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ỤYHÀ NỘI 9-2015TRƯỜNG ĐẠI HỌC CÔNG NGHỆĐẠI HỌC QUỐC GIA HÀ NỘI Nội dung Giới thiệu phân lớpPhân lớp học giám sátPhân lớp học bán giám sát 147 03/02/17 2 Bài toá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 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 toá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 đạidiệ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. 148 03/02/17 3 Ví dụ phân lớp: Bài toá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 Phân lớp: Quá trình hai pha 149 03/02/17 4 Phân lớp: Quá trình hai pha Apply Model Learn Model Tid Attrib1 Attrib2 Attrib3 Class 1 Yes Large 125K No 2 No Medium 100K No 3 No Small 70K No 4 Yes Medium 120K No 5 No Large 95K Yes 6 No Medium 60K No 7 Yes Large 220K No 8 No Small 85K Yes 9 No Medium 75K No 10 No Small 90K Yes 10 Tid Attrib1 Attrib2 Attrib3 Class 11 No Small 55K ? 12 Yes Medium 80K ? 13 Yes Large 110K ? 14 No Small 95K ? 15 No Large 67K ? 10 Các loại phân lớp – Phân lớp nhị phân/đa lớp Nhị phân: hai lớp (|C| = 2)Đa lớp: số lượng lớp > 2 (|C| > 2) – Phân lớp đơn nhãn/đa nhãn/phân cấpĐơn nhãn: Một đối tượng chỉ thuộc duy nhất một lớp – Đa nhãn: Một đối tượng thuộc một hoặc nhiều lớp – Phân cấp: Lớp này là con của lớp kia 150 03/02/17 5 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ìnhCâ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? Đá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 (truenegatives), FP (false positives), FN (false negatives) • TP: số ví dụ dương P mà thuật toán phân đúng (T) giá trị P • TN: số ví dụ âm N mà thuật toán phân đúng (T) giá trị âm N • FP: số ví dụ dương P mà thuật toán (F) phân lớp cho giá trị N - FN: số ví dụ âm N mà thuật toán (F) phân lớp cho dương P - Độ hồi tưởng , độ chính xác , các độ đo F1 và F FPTP TP FNTPTPπ  151 03/02/17 6 Đá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 thực sự Lớp = 1 f11 f10Lớp = 0 f01 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ểmthử: 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ó = 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 152 03/02/17 7 Đánh giá phân lớp đa lớp Lớp Ci Giá trị thực Thuộc lớp Ci Không thuộc lớp Ci Giá trị qua bộ phân lớp đa lớp Thuộc lớp Ci TPi FNi Không thuộc lớp Ci FPi TNi - Bài toá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 toá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) Đá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ậttoán phân lớp cho giá trị đúng trên tổng số ví dụ được thuật toánphân lớp vào lớp Ci :  Độ hồi tưởng Rei của lớp Ci là tỷ lệ số ví dụ dương được thuậttoá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: ii ii FNTP TPPr  ii ii FPTP TP Re 153 03/02/17 8 Đá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 đốivớ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 1    Kc cc K c cFPTP TP )(1 1   Kc cc K c cTNTP TP  Kc cM K 11   Kc cM K 11  Các kỹ thuật phân lớp  Các phương pháp cây quyết địnhDecision Tree based Methods  Các phương pháp dựa trên luậtRule-based Methods  Các phương pháp Bayes «ngây thơ» và mạng tin cậy BayesNaï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ơronNeural Networks  Một số phương pháp khác 154 03/02/17 9  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úttương ứng với một tập các ví dụ học. Gốc: toàn bộ dữ liệu học Một số thuật toá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 Phân lớp cây quyết định Ví dụ cây quyết định và sử dụng Kết luận: Gán giá trị NO (không gian lận) vào trường Cheat cho bản ghi 155 03/02/17 10 1Yes System Process Timetable Yes No No 0 1 0 1 0 1. If System=0 and Process=0 then Class AI = Yes. 2. If System=0 and Process=1 then Class AI = No. 3. If System=1 and Timetable=1 then Class AI = Yes. 4. If System=1 and Timetable=0 then Class AI = No. 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)  Thuật toá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 dung1: 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à A2.2. Tạo phân hoạch Dt theo tập giá trị của A thành các tập con2.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 đượcxem 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. Dựng cây quyết định: thuật toán Hunt 156 03/02/17 11 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 Ví dụ: thuật toán Hunt Thuật toán cây quyết định ID3 157 03/02/17 12  Chiến lược tham lam Phân chia tập dữ liệu dựa trên việc kiểm tra các thuộc tính làmtối ưu hóa chiến lược xác định  Vấn đề cần giải quyết Xác định cách phân chia tập dữ liệu Cách xác định điều kiện kiểm tra thuộc tính Cách xác định cách chia tốt nhất Theo một số độ đo Khi nào thì dừng phân chia (bước 2) Tất cả các dữ liệu thuộc về cùng một lớp Tất cả các dữ liệu có giá trị “tương tự nhau” Ràng buộc dừng phân chia khác: (i) số lượng dữ liệu nhỏ thuangưỡng cho trước, (ii) test khi-bình phương cho thấy phân bố lớpkhông phụ thuộc các thuộc tính hiện có; (iii) nếu phân chia khôngcải thiện chất lượng Rút gọn cây  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 Công thức tính độ đo Gini cho nút t: 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ảnghi 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 Chọn thuộc tính: Độ đo Gini   1 2)|(1)( j tjptGini C1 0C2 6 Gini=0.000 C1 2C2 4 Gini=0.444 C1 3C2 3 Gini=0.500 C1 1C2 5 Gini=0.278 158 03/02/17 13  Dùng trong các thuật toá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ấtlượng của việc chia tính bằng 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). Chia tập theo độ đo Gini  ki isplit iGINInnGINI 1 )(  Tính toá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ầnchia khoảng (tồn tại một số phương pháptheo 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/70Như vậy, Gini của Refund và TaxableIncome bằng nhau (24/70) và lớn hơn Ginicủa Marital Status (3/10) nên chọn MaritalStatus cho gốc cây quyết định ! Chia tập theo độ đo Gini: Ví dụ  ki isplit iGINInnGINI 1 )(   1 2)|(1)( j tjptGini Cheat / Don’t Cheat MaritalStatus Don’t Cheat MarriedSingle,Divorced 159 03/02/17 14  Độ đ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 Công thức tính entropy nút t: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ácbản ghi tại t phân bố đều cho nc lớp; tính hỗn tạp cao nhất, khôngcó 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 duynhất. Lấy loga cơ số 2 thay cho loga tự nhiên  Tính toán entropy (t) cho một nút tương tự như Gini (t) Chọn thuộc tính: Information Gain  j tjptjptEntropy )|(log)|()(  Độ đo Information Gain 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 toá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  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 Chọn thuộc tính: Information Gain  ki ii nnnnSplitINFO 1 log  ki ichia ientropynntentropyGain 1 )()( SplitINFO GainGainRATIO chia 160 03/02/17 15  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:  yTrong đó: là sự kết nối các thuộc tính (còn gọi là tiên đề/điềukiệ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ộctí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. Phân lớp dựa trên luật  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ệu1. Bắt đầu từ một tập rỗng2. Mở rộng luật bằng hàm Học_một_luật3. Xóa mọi bản ghi “bảo đảm” bởi luật vừa được học4. 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 Xây dựng luật phân lớp 161 03/02/17 16  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à R1p0: 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 Mở rộng luật: một số phương án 162 03/02/17 17 Luật phân lớp: từ cây quyết định Tập luậtLiệt kê các đường đi từ gốc  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) Sinh luật gián tiếp: C4.5rules 163 03/02/17 18 C4.5rules: Ví dụ Name Give Birth Lay Eggs Can Fly Live in Water Have Legs Classhuman yes no no no yes mammalspython no yes no no no reptilessalmon no yes no yes no fisheswhale yes no no yes no mammalsfrog no yes no sometimes yes amphibianskomodo no yes no no yes reptilesbat yes no yes no yes mammalspigeon no yes yes no yes birdscat yes no no no yes mammalsleopard shark yes no no yes no fishesturtle no yes no sometimes yes reptilespenguin no yes no sometimes yes birdsporcupine yes no no no yes mammalseel no yes no yes no fishessalamander no yes no sometimes yes amphibiansgila monster no yes no no yes reptilesplatypus no yes no no yes mammalsowl no yes yes no yes birdsdolphin yes no no yes no mammalseagle no yes yes no yes birds C4.5rules: Ví dụ C4.5rules: (Give Birth=No, Can Fly=Yes)  Birds (Give Birth=No, Live in Water=Yes)  Fishes (Give Birth=Yes)  Mammals (Give Birth=No, Can Fly=No, Live in Water=No)  Reptiles ( )  Amphibians GiveBirth? Live InWater? CanFly? Mammals Fishes Amphibians Birds Reptiles Yes No Yes Sometimes No Yes No RIPPER: (Live in Water=Yes)  Fishes (Have Legs=No)  Reptiles (Give Birth=No, Can Fly=No, Live In Water=No)  Reptiles (Can Fly=Yes,Give Birth=No)  Birds ()  Mammals 164 03/02/17 19  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ệnHai biến cố A và 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)? Phân lớp Bayes )( ),()|( )( ),()|( CP CAPCAP AP CAPACP    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 ? Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data Mining(Chapter 5: Classification: Alternative Techniques), Addison Wesley, 2005, Định lý Bayes: Ví dụ 0002.020/1 50000/15.0 )( )()|()|(  SP MPMSPSMP 165 03/02/17 20  Các thuộc tính (bao gồm nhãn lớp) là các biếnngẫ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ệuhọc? Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data Mining(Chapter 5: Classification: Alternative Techniques), Addison Wesley, 2005, Phân lớp Bayes 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:   inT xTpTxcpxcp )|(),|(),|( 166 03/02/17 21 Phân lớp Naï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 = ||Y  Dlearn / Y Ci||  Xác suất một đặc trưng fj thuộc lớp C:  Cho dữ liệu X mới  Tính xác suất hậu nghiệm  Nếu P(C|X) > Cthì X  C!TF (fj| X): số lần đặc trưng fj xuất hiện trong X   n i il jj CjTFV CfTFCfP 1 ),(|| ),(1)|(       n i VF )X,f(TFiji VF )X,f(TFj j j j j )C|f(p(*)C(p )C|f(p(*)C(p )X|C(P 1 Phân lớp k-NN  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    l l ll l ll YX Y*X )Y,X(Cos)Y,X(Sm 22 167 03/02/17 22 Phân lớp k-NN: Ví dụ  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 X X X (a) 1-nearest neighbor (b) 2-nearest ne ighbor (c) 3-nearest neighbor 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). 168 03/02/17 23 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 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 169 03/02/17 24 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:  Thỏa mãn:  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:  Thỏa mãn: 21 1. =2 2 (1)        . 1 1,. . . . , (2 )i ic d b i n       =1 1 . + (3)2 n ii C   . 1 1,....,i i ic d b i n      0 1,...., (4)i i n    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 170 03/02/17 25 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  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. 171 03/02/17 26 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  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 172 03/02/17 27 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ó.  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2cho 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 173 03/02/17 28  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án1: Cố định tập tài liệu không nhãn DU  D \ DK dùng trong E-bước và M-bước2: dùng DK xây dựng mô hình ban đầu 03: for i = 0, 1, 2, . . . cho đến khi kết quả đảm bảo do4: for mỗi tài liệu d  DU do5: E-bước: dùng phân lớp Bayes thứ nhất xác định P(c|d,i)6: end for7: for mỗi lớp c và từ khóa t do8: M-bước: xác định c,t dùng công thức (*) để xây dựng mô hình i+19: end for10: end for Mô hình sinh: Thuật toán EM 174 03/02/17 29 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 175 03/02/17 30 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 dungGọiL : Tập các dữ liệu gán nhãn.U : Tập các dữ liệu chưa gán nhãnLặp (cho đến khi U = )Huấn luyện bộ phân lớp giám sát h trên tập LSử dụng h để phân lớp dữ liệu trong tập UTìm tập con U’  U có độ tin cậy cao nhất:L + U’  LU – U’  UVấ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  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 176 03/02/17 31  Mô hình thuật toánCo-Training 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 177 03/02/17 32 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ơ) 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. 178 03/02/17 33 Ngày 10/10/2014  Buổi trình bày DataSectionJapan DataSection: Social Media Ming9h00 ngày Thứ Hai 13/10/2014GĐ 103 nhà G2  Các phương pháp dựa trên luật KSE 11h50, PH 212 nhà E3Hai tiết từ 9h00-10h50 179 03/02/17 1 BÀI GIẢNG KHAI PHÁ DỮ LIỆU CHƯƠNG 6. PHÂN CỤM DỮ LiỆU PGS. TS. HÀ QUANG THỤYHÀ NỘI 9-2014TRƯỜNG ĐẠI HỌC CÔNG NGHỆĐẠI HỌC QUỐC GIA HÀ NỘI Nội dung Giới thiệu bài toán phân cụmMột số độ đo cơ bản cho phân cụmPhân cụm phẳngPhân cụm phân cấpPhân cụm dựa trên mật độPhân cụm dựa trên mô hìnhGán nhãn cụmĐánh giá phân cụm Charu C. Aggarwal, Chandan K. Reddy (Eds., 2014). Data Clustering: Algorithmsand Applications. CRC Press 2014. 180 03/02/17 2 1. Giới thiệu bài toán phân cụm  Bài toán  Tập dữ liệu D = {di}  Phân các dữ liệu thuộc D thành các cụm  Các dữ liệu trong một cụm: “tương tự” nhau (gần nhau)  Dữ liệu hai cụm: “không tương tự” nhau (xa nhau)  Đo “tương tự” (gần) nhau ?  Tiên đề phân cụm: Nếu người dùng lựa chọn một đối tượng d thì họcũng lựa chọn các đối tượng cùng cụm với d  Khai thác “cách chọn lựa” của người dùng  Đưa ra một số độ đo “tương tự” theo biểu diễn dữ liệu  Một số nội dung liên quan  Xây dựng độ đo tương tự  Khai thác thông tin bổ sung  Số lượng cụm cho trước, số lượng cụm không cho trước Sơ bộ tiếp cận phân cụm  Phân cụm mô hình và phân cụm phân vùng  Mô hình: Kết quả là mô hình biểu diễn các cụm dữ liệu  Vùng: Danh sách cụm và vùng dữ liệu thuộc cụm  Phân cụm đơn định và phân cụm xác suất  Đơn định: Mỗi dữ liệu thuộc duy nhất một cụm  Xác suất: Danh sách cụm và xác suất một dữ liệu thuộc vào cáccụm  Phân cụm phẳng và phân cụm phân cấp  Phẳng: Các cụm dữ liệu không giao nhau  Phân cấp: Các cụm dữ liệu có quan hệ phân cấp cha- con  Phân cụm theo lô và phân cụm tăng  Lô: Tại thời điểm phân cụm, toàn bộ dữ liệu đã có  Tăng: Dữ liệu tiếp tục được bổ sung trong quá trình phân cụm 181 03/02/17 3 Các phương pháp phân cụm  Các phương pháp phổ biến  Phân vùng, phân cấp, dựa theo mật độ, dựa theo lưới, dựa theo mô hình, và phân cụm mờ  Phân cụm phân vùng (phân cụm phẳng)  Xây dựng từng bước phân hoạch các cụm và đánh giá chúng theo các tiêu chí tương ứng  Tiếp cận: từ dưới lên (gộp dần), từ trên xuống (chia dần)  Độ đo tương tự / khoảng cách  K-mean, k-mediod, CLARANS,  Hạn chế: Không điều chỉnh được lỗi  Phân cụm phân cấp  Xây dựng hợp (tách) dần các cụm tạo cấu trúc phân cấp và đánh giá theo các tiêu chí tương ứng  Độ đo tương tự / khoảng cách  HAC: Hierarchical agglomerative clustering  CHAMELEON, BIRRCH và CURE, Các phương pháp phân cụm  Phân cụm dựa theo mật độ  Hàm mật độ: Tìm các phần tử chính tại nơi có mật độ cao  Hàm liên kết: Xác định cụm là lân cận phần tử chính  DBSCAN, OPTICS  Phân cụm dựa theo lưới  Sử dụng lưới các ô cùng cỡ: tuy nhiên cụm là các “ô” phân cấp  Tạo phân cấp ô lưới theo một số tiêu chí: số lượng đối tượng trong ô  STING, CLIQUE, WaweCluster  Phân cụm dựa theo mô hình  Giải thiết: Tồn tại một số mô hình dữ liệu cho phân cụm  Xác định mô hình tốt nhất phù hợp với dữ liệu  MCLUST  Phân cụm mờ  Giả thiết: không có phân cụm “cứng” cho dữ liệu và đối tượng có thểthuộc một số cụm  Sử dụng hàm mờ từ các đối tượng tới các cụm  FCM (Fuzzy CMEANS), 182 03/02/17 4 2. Một số độ đo cơ bản  Độ đo tương đồng  Biểu diễn: vector n chiều  Giá trị nhị phân: Ma trận kề, độ đoJaccard  Giá trị rời rạc [0,m]: Chuyển m giátrị thành nhị phân, độ đo Jaccard  Giá trị thực : độ đo cosin haivector  Độ đo khác biệt  Đối ngẫu độ đo tương đồng  Thuộc tính nhị phân: đối cứng, không đối xứng  Giá trị rời rạc: hoặc tương tự trênhoặc dạng đơn giản (q thuộc tínhgiống nhau)  Giá trị thực: Khoảng cáchManhattan, Euclide, Mincowski  Tính xác định dương, tính đốixứng, tính bất đẳng thức tam giác Một số độ đo cơ bản  Ví dụ về độ khác biệt  CSDL xét nghiệm bệnhnhân  Quy về giá trị nhị phân: M/F, Y/N, N/P  Lập ma trận khác biệt chotừng cặp đối tượng.  Ví dụ, cặp (Nam, Vân): a=2, b=1, c=1, d=3D(Nam, Vân) =(1+1)/(2+1+1)=0.5 183 03/02/17 5 3. Thuât toán K-mean gán cứng  Một số lưu ý  Điều kiện dừng  Sau bước 2 không có sự thay đổi cụm  Điều kiện dừng cưỡng bức  Khống chế số lần lặp  Giá trị mục tiêu đủ nhỏ  Vấn đề chọn tập đại diện ban đầu ở bước Khởi động  Có thể dùng độ đo khoảng cách thay cho độ đo tương tự a. Thuât toán K-mean gán cứng  Một số lưu ý (tiếp) và ví dụ  Trong bước 2: các trọng tâm có thể không thuộc S  Thực tế: số lần lặp  50  Thi hành k-mean với dữ liệu trên đĩa  Toàn bộ dữ liệu quá lớn: không thể ở bộ nhớ trong  Với mỗi vòng lặp: duyệt CSDL trên đĩa 1 lần  Tính được độ tương tự của d với các ci. Tính lại ci mới: bước 2.1 khởi động (tổng, bộ đếm); bước 2.2 cộng và tăng bộ đếm; bước 2.3 chỉ thực hiện k phép chia. Bing Liu (2007), Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Spinger, 2007. 184 03/02/17 6 Thuât toán K-mean mềm  Input  Số nguyên k > 0: số cụm biết trước  Tập dữ liệu D (cho trước)  Output  Tập k “đại diện cụm” C làm cực tiểu lỗi “lượng tử”  Định hướng  Tinh chỉnh C dần với tỷ lệ học  (learning rate) Thuât toán K-mean  Ưu điểm  Đơn giản, dễ sử dụng  Hiệu quả về thời gian: tuyến tính O(tkn), t số lần lặp, k số cụm, n là số phần tử  Một thuật toán phân cụm phổ biến nhất  Thường cho tối ưu cục bộ. Tối ưu toàn cục rất khó tìm  Nhược điểm  Phải “tính trung bình được”: dữ liệu phân lớp thì dựa theo tần số  Cần cho trước k : số cụm  Nhạy cảm với ngoại lệ (cách xa so với đại đa số dữ liệu còn lại): ngoại lệ thực tế, ngoại lệ do quan sát sai (làm sạch dữ liệu)  Nhạy cảm với mẫu ban đầu: cần phương pháp chọn mẫu thô tốt  Không thích hợp với các tập dữ liệu không siêu-ellip hoặc siêucầu (các thành phần con không ellip/cầu hóa) Bing Liu (2007), Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Spinger, 2007. 185 03/02/17 7 Thuât toán K-mean Trái: Nhạy cảm với chọn mẫu ban đầuPhải: Không thích hợp với bộ dữ liệu không siêu ellip/cầu hóa Bing Liu (2007), Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Spinger, 2007. b. Thuât toán PAM (K-mediod)  K-mediod  Biến thể của K-mean: thay trọng tâm bằng một phần tử của D  Hàm mục tiêu  PAM: Partition Around Mediods 186 03/02/17 8 4. Phân cụm phân cấp  HAC: Hierarchical agglomerative clustering  Một số độ đo phân biệt cụm  Độ tương tự hai tài liệu  Độ tương tư giữa hai cụm  Độ tương tự giữa hai đại diện  Độ tương tự cực đại giữa hai dữ liệu thuộc hai cụm: single-link  Độ tương tự cực tiểu giữa hai dữ liệu thuộc hai cum: complete-link  Độ tương tự trung bình giữa hai dữ liệu thuộc hai cum  Sơ bộ về thuật toán  Đặc điểm: Không cho trước số lượng cụm k, cho phép đưa ra cácphương án phân cụm theo các giá trị k khác nhau  Lưu ý: k là một tham số  “tìm k tốt nhất”  Tinh chỉnh: Từ cụ thể tới khái quát a. Phân cụm phân cấp từ dưới lên  Giải thích  G là tập các cụm trong phân cụm  Điều kiện |G| < k có thể thay thế bằng |G|=1 187 03/02/17 9 Phân cụm phân cấp từ dưới lên  Hoạt động HAC  Cho phép với mọi k  Chọn phân cụm theo “ngưỡng” về độ tương tự HAC với các độ đo khác nhau  Ảnh hưởng của các độ đo  Trên: Hoạt động thuật toán khác nhau theo các độ đo khác nhau: độ tương tự cực tiểu (complete-link) có tính cầu hơn so với cực đại  Dưới: Độ tương tự cực đại (Single-link) tạo cụm chuỗi dòng 188 03/02/17 10 b. Phân cụm phân cấp BIRCH  Balanced Iterative Reducing Clustering Using Hierarchies  Tính khả cỡ: Làm việc với tập dữ liệu lớn  Tính bất động: Gán không đổi đối tượng –> cụm  Khái niệm liên quan  Đặc trưng phân cụm CF: tóm tắt của cụm  CF = , n: số phần tử, LS: vector tổng các thành phần dữ liêu; SS : vector tổng bình phương các thành phần các đối tượng  . Khi ghép cụm không tính lại các tổng  Cây đặc trưng phân cụm CF Tree  Một cây cân bằng  Hai tham số: bề rộng b và ngưỡng t  Thuật toán xây dựng cây BIRCH: Năm độ đo khoảng cách 189 03/02/17 11 Cây đặc trưng phân cụm CF Tree  Mỗi nút không là lá cónhiều nhất là B cành  Mỗi nút lá có nhiềunhất L đặc trưng phâncụm mà đảm bảongưỡng T  Cỡ của nút được xácđịnh bằng số chiềukhông gian dữ liệu vàtham số P kích thướctrang bộ nhớ Chèn vào CF Tree và BIRCH  Cây ban đầu rỗng  Chèn một “cụm” a vào cây  Xác định lá thích hợp: Duyệt từ gốc xuống một cách đệ quy để tới nút con gần a nhất theo 1 trong 5 khoảng cách nói trên  Biến đổi lá: Nếu gặp lá L1 gần a nhất, kiểm tra xem L1 có “hấp thụ“ a không (chưa vượt ngưỡng); nếu có thì đặc trưng CF của L1 bổ sung;Nếu không, tạo nút mới cho a; nếu không đủ bộ nhớ cho lá mới thì cần chia lá cũ  Biến đổi đường đi tới lá khi bổ sung phần tử mới  Tinh chỉnh việc trộn: Tian Zhang, Raghu Ramakrishnan, Miron Livny (1996). BIRCH: An Efficient DataClustering Method for Very Large Databases, SIGMOD Conference 1996: 103-114 190 03/02/17 12 Các thuật toán phân cụm khác  Nghiên cứu giáo trình  Phân cụm phân cấp từ trên xuống DIANA  Đối ngẫu phân cụm phân cấp từ trên xuống: phần tử khác biệt -> cụm khác biệt S,  Thêm vào S các phần tử có d > 0  Phân cụm phân cấp ROCK  RObust Clustering using linKs: xử lý dữ liệu rời rạc, quyết định “gần” theotập phần tử láng giềng sim (p, q) > >0.  Phân cụm dựa trên mật độ DBSCAN  Density-Based Spatial Clustering of Application with Noise  #-neighborhood: vùng lân cận bán kính #  | #-neighborhood| > MinPts gọi đối tượng lõi  P đạt được trực tiếp theo mật độ từ q nếu q là đối tượng lõi và p thuộc #-neighborhood của q.  Đạt được nếu có dãy mà mỗi cái sau là đạt được trực tiếp từ cái trước  Phân cụm phân cấp dựa trên mô hình  Làm phù hợp phân bố cụm với mô hình toán học  Phân cụm cực đại kỳ vọng, phân cụm khái niệm, học máy mạng nơron  Phân cụm cực đại kỳ vọng: khởi tạo, tính giá trị kỳ vọng, cực đại hóa kỳ vọng 7. Biểu diễn cụm và gán nhãn  Các phương pháp biểu diễn điển dình  Theo đại diện cụm  Đại diện cụm làm tâm  Tính bán kính và độ lệch chuẩn để xác định phạm vi của cụm  Cụm không ellip/cầu hóa: không tốt  Theo mô hình phân lớp  Chỉ số cụm như nhãn lớp  Chạy thuật toán phân lớp để tìm ra biểu diễn cụm  Theo mô hình tần số  Dùng cho dữ liệu phân loại  Tần số xuất hiện các giá trị đặc trưng cho từng cụm  Lưu ý  Dữ liệu phân cụm ellip/cầu hóa: đại diện cụm cho biểu diễn tốt  Cụm hình dạng bất thường rất khó biểu diễn 191 03/02/17 13 Gán nhãn cụm  Phân biệt các cụm (MU)  Chọn đặc trưng tương quan cụm  Nxy (x có đặc trưng t, y dữ liệu thuộc C)  N11 : số dữ liệu chứa t thuộc cụm C  N10 : số dữ liệu chứa t không thuộc cụm C  N01 : số dữ liệu không chứa t thuộc cụm C  N00 : số dữ liệu không chứa t không thuộc cụm C  N: Tổng số dữ liệu  Hướng “trọng tâm” cụm  Dùng các đặc trưng tần số cao tại trọng tâm cụm  Tiêu đề  Chon đặc trưng của dữ liệu trong cụm gần trọng tâm nhất Ví dụ: Gán nhãn cụm văn bản  Ví dụ  Ba phương pháp chọn nhãn cụm đối với 3 cụm là cụm 4 (622 tài liệu),cụm 9 (1017 tài liệu), cụm 10 (1259 tài liệu) khi phân cụm 10000 tài liệuđầu tiên của bộ Reuters-RCV1  centroid: các từ khóa có tần số cao nhất trong trọng tâm; mutualinformation (MU): thông tin liên quan phân biệt các cụm; title: tiêu đề tàiliệu gần trọng tâm nhất. Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to InformationRetrieval, Cambridge University Press. 2008. 192 03/02/17 14 8. Đánh giá phân cụm  Đánh giá chất lượng phân cụm là khó khăn  Chưa biết các cụm thực sự  Một số phương pháp điển hình  Người dùng kiểm tra  Nghiên cứu trọng tâm và miền phủ  Luật từ cây quyết định  Đọc các dữ liệu trong cụm  Đánh giá theo các độ đo tương tự/khoảng cách  Độ phân biệt giữa các cụm  Phân ly theo trọng tâm  Dùng thuật toán phân lớp  Coi mỗi cụm là một lớp  Học bộ phân lớp đa lớp (cụm)  Xây dựng ma trận nhầm lẫn khi phân lớp  Tính các độ đo: entropy, tinh khiết, chính xác, hồi tưởng, độđo F và đánh giá theo các độ đo này Đánh giá theo độ đo tương tự  Độ phân biệt các cụm  Cực đại hóa tổng độ tương tự nội tại của các cụm  Cực tiểu hóa tổng độ tương tự các cặp cụm khác nhau  Lấy độ tương tự cực tiểu (complete link), cực đại (single link)  Một số phương pháp điển hình  Phân ly theo trọng tâm 193 03/02/17 15 Ví dụ: Chế độ và đặc điểm phân cụm web  Hai chế độ  Trực tuyến: phân cụm kết quả tìm kiếm người dùng  Ngoại tuyến: phân cụm tập văn bản cho trước  Đặc điểm  Chế độ trực tuyến: tốc độ phân cụm  Web số lượng lớn, tăng nhanh và biến động lớn  Quan tâm tới phương pháp gia tăng  Một lớp quan trọng: phân cụm liên quan tới câu hỏi tìm kiếm  Trực tuyến  Ngoại tuyến Carpineto C., Osinski S., Romano G., Weiss D. (2009). A survey of webclustering engines, ACM Comput. Surv. , 41(3), Article 17, 38 pages. Ví dụ 194 03/02/17 16 Phân cụm kết quả tìm kiếm 195