Bài giảng Tìm kiếm và trình diễn thông tin: Bài 13 - TS.Nguyễn Bá Ngọc

Với bài học "Phân lớp và ứng dụng trong tìm kiếm thuộc bài 13" của bộ bài giảng Tìm kiếm và trình diễn thông tin hướng đến trình bày ứng dụng phân lớp trong tìm kiếm; các khái niệm cơ bản; ứng dụng trong công cụ tìm kiếm; phương pháp phân lớp thủ công;...
Nội dung trích xuất từ tài liệu:
Bài giảng Tìm kiếm và trình diễn thông tin: Bài 13 - TS.Nguyễn Bá Ngọc(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: http://is.hust.edu.vn/~ngocnb 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 4Minh 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.Phân lớp tự động? 7 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 ?(?) + log ?(?? |?) ?∈? 1≤?≤?? 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) ?∈? ??? + ? 16Giải thuật Naïve Bayes: Huấn luyện 17Giả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 Đá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 ...