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

Nội dung text: 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

1. (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
2. 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
3. Nội dung chính  Ứng dụng phân lớp trong tìm kiếm  Phương pháp Nạve Bayes  Đánh giá phương pháp phân lớp 3
4. 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
5. Minh họa 5
6. Ứ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
7. 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. Phân lớp tự động? 7
8. 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
9. Phương pháp phân lớp tự động  Xác suất, thống kê  Tiêu biểu: Nạve Bayes, Rocchio, kNN, SVMs  Cần thiết lập bộ dữ liệu huấn luyện; 9
10. Nội dung chính  Ứng dụng phân lớp trong tìm kiếm  Phương pháp Nạve Bayes  Đánh giá phương pháp phân lớp 10
11. Nạ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
12. 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
13. 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 ( ) + log (푡 | ) ∈ 1≤ ≤푛 13
14. Giải thuật Nạ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
15. 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
16. Làm mịn  Làm mịn bằng cách cộng thêm 1: 푡 + 1 푡 + 1 푡 = = 푡∈ ( 푡+1) 푡∈ 푡 + 16
17. Giải thuật Nạve Bayes: Huấn luyện 17
18. Giải thuật Nạve Bayes: Phân lớp 18
19. Nội dung chính  Ứng dụng phân lớp trong tìm kiếm  Phương pháp Nạve Bayes  Đánh giá phương pháp phân lớp 19
20. Khái quát  Đá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. 20
21. Các độ đo cơ bản  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ự đốn thuộc lớp A (TP) B (FP) Dự đốn khơng thuộc lớp C (FN) D (TN) | A | TP | A | TP P R | A  B | TP FP | A  C | TP FN 2PR F 1 P R 21
22. Lấy trung bình  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. 22
23. Nạve Bayes và các bộ phân lớp khác Bộ phân loại Nạ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. 23