Tìm kiếm và trình diễn thông tin - Phân lớp và ứng dụng trong tìm kiếm

(IT4853) Tìm kiếm và trình diễn thông tin Phân lớp và ứng dụng trong tìm kiếm Giảng viên  TS. Nguyễn Bá Ngọc  Địa chỉ: Viện CNTT & TT/BM HTTT/B1-603  Email: ngocnb@soict.hust.edu.vn  Website: 2 Nội dung chính  Ứng dụng phân lớp trong tìm kiếm  Phương pháp Naïve Bayes  Đánh giá phương pháp phân lớp 3 Các khái niệm cơ bản  Ký hiệu X là tập văn bản;  C là tập lớp (còn được gọi là tập nhãn);  Dữ liệu huấn luyện là một phân lớp mẫu 𝐷 = 𝑑 ∈ 𝑋, 𝑐 ∈ 𝐶 ,  Qúa trình học phân lớp là đi xác định ánh xạ 𝛾 mô phỏng kết quả phân lớp D 𝛾: 𝑋 → 𝐶  Phân lớp là xác định định lớp phù hợp nhất với d bất kỳ trong X: 𝛾(𝑑) ∈ C 4 Minh họa 5 Ứng dụng trong công cụ tìm kiếm  Xác định ngôn ngữ  Các lớp: Tiếng Anh, tiếng Việt, v.v.  Xác định spam  Tìm kiếm theo chủ đề  Truy vấn cố định (standing queries), v.d., Google Alerts  Phân lớp bình luận: Khen, chê, v.v. 6 Phương pháp phân lớp thủ công  Yahoo, ODP, Pubmed;  Rất chính xác!  Đơn giản với dữ liệu nhỏ;  Phức tạp & chi phí cao trên quy mô lớn. 7 Phân lớp tự động? Phương pháp phân lớp dựa trên luật  Ví dụ, Google Alerts;  Môi trường tích hợp hỗ trợ viết luật phân lớp;  Nếu thỏa mãn biểu thức Boolean q thì thuộc lớp c  Có thể đạt độ chính xác rất cao;  Cần chi phí lớn. 8 Phương pháp phân lớp tự động  Xác suất, thống kê  Tiêu biểu: Naïve Bayes, Rocchio, kNN, SVMs  Cần thiết lập bộ dữ liệu huấn luyện; 9 Nội dung chính  Ứng dụng phân lớp trong tìm kiếm  Phương pháp Naïve Bayes  Đánh giá phương pháp phân lớp 10 Naïve Bayes  Phân lớp dựa trên xác suất;  Xác suất d thuộc c được tính như sau: 𝑝 𝑐 𝑑 ∝ 𝑝 𝑐 1≤𝑘≤𝑛𝑑 𝑝 𝑡𝑘 𝑐 ,  Trong đó:  nd là độ dài văn bản;  p(tk|c) xác suất tk thuộc c;  p(c) là xác suất tiền nghiệm của lớp c. 11 Tiêu trí xác suất cực đại  Văn bản được phân vào lớp với xác suất cực đại 𝛾 𝑑 = 𝑎𝑟𝑔max 𝑐∈𝐶 𝑝(𝑐) 1≤𝑘≤𝑛𝑑 𝑝(𝑡𝑘|𝑐) 12 Lấy log  Lấy tích nhiều đại lượng xác suất nhỏ có thể gây tràn số;  Lớp với xác suất lớn nhất không đổi nếu sử dụng logarithm  Trong thực tế sử dụng công thức sau: 𝛾 𝑑 = 𝑎𝑟𝑔max 𝑐∈𝐶 log 𝑝(𝑐) + 1≤𝑘≤𝑛𝑑 log 𝑝(𝑡𝑘|𝑐) 13 Giải thuật Naïve Bayes  Xác định p(c) và p(tk|c) dựa trên dữ liệu luyện: 𝑝 𝑐 = 𝑁𝑐 𝑁  Trong đó Nc là số văn bản của lớp c, N là số văn bản trong bộ dữ liệu luyện  Xác suất có điều kiện: 𝑝 𝑡𝑘 𝑐 = 𝑇𝑐𝑡𝑘 𝑡∈𝑉 𝑇𝑐𝑡  Trong đó Tct là số lần từ t xuất hiện trong lớp c. 14 Giá trị 0  Nếu có một từ t thuộc d nhưng không xuất hiện trong bất kỳ văn bản nào của lớp c thì:  p(t|c) = 0  Kéo theo p(c|d)=0. 15 Làm mịn  Làm mịn bằng cách cộng thêm 1: 𝑝 𝑡𝑘 𝑐 = 𝑇𝑐𝑡𝑘 + 1 𝑡∈𝑉(𝑇𝑐𝑡+1) = 𝑇𝑐𝑡𝑘 + 1 𝑡∈𝑉 𝑇𝑐𝑡 + 𝑉 16 Giải thuật Naïve Bayes: Huấn luyện 17 Giải thuật Naïve Bayes: Phân lớp 18 Nội dung chính  Ứng dụng phân lớp trong tìm kiếm  Phương pháp Naïve Bayes  Đánh giá phương pháp phân lớp 19 Khái quát 20  Đánh giá phải được thực hiện trên bộ dữ liệu kiểm thử độc lập với bộ dữ liệu huấn luyện;  Đánh giá kết quả phân lớp theo các tiêu trí: Độ chính xác (P), Độ đầy đủ (R), F1. Các độ đo cơ bản 21  Thống kê các đại lượng sau đối với một lớp: Thuộc lớp Không thuộc lớp Dự đoán thuộc lớp A (TP) B (FP) Dự đoán không thuộc lớp C (FN) D (TN) FPTP TP     |BA| |A| P FNTP TP     |CA| |A| R RP F   2PR 1 Lấy trung bình 22  Macro  Tính F1 cho từng lớp;  Lấy trung bình các giá trị F1  Micro:  Thống kê TP, TN, FP, FN cho từng lớp;  Lấy tổng các đại lượng thống kê này trên tất cả các lớp;  Tính F1 trên các giá trị tổng hợp này. Naïve Bayes và các bộ phân lớp khác 23 Bộ phân loại Naïve Bayes hoạt động tương đối tốt, tuy nhiên có nhiều bộ phân loại khác có kết quả cao hơn, ví dụ, SVM. 24