Một số thuật toán phân loại văn bản - Lê Hồng Phương

một số thuật toán phân loại văn bản Lê Hồng Phương Đại học Quốc gia Hà Nội Trường Đại học Khoa học Tự nhiên Viện Nghiên cứu Công nghệ FPT 6/2013 Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 1 / 29 Nội dung 1 Giới thiệu Bài toán phân loại văn bản Các mô hình xác suất 2 Một số mô hình phân loại Mô hình Bayes đơn giản Mô hình Bernoulli Mô hình TF-IDF 3 Thiết kế Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 2 / 29 Nội dung 1 Giới thiệu Bài toán phân loại văn bản Các mô hình xác suất 2 Một số mô hình phân loại Mô hình Bayes đơn giản Mô hình Bernoulli Mô hình TF-IDF 3 Thiết kế Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 3 / 29 Nội dung 1 Giới thiệu Bài toán phân loại văn bản Các mô hình xác suất 2 Một số mô hình phân loại Mô hình Bayes đơn giản Mô hình Bernoulli Mô hình TF-IDF 3 Thiết kế Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 4 / 29 Bài toán phân loại văn bản Bài toán Cho x là một văn bản. Biết x thuộc một trong các loại y ∈ {1, 2, . . . ,K}. Hãy tìm loại văn bản đúng nhất của x. Ví dụ: Giả sử x là một bài báo do phóng viên viết, gửi đăng trên trang tin điện tử vnExpress. Biên tập viên cần quyết định xem x thuộc thể loại nào là thích hợp nhất: “chính trị – xã hội ”, “quốc tế ”, “thể thao”. . . Giả sử x là một văn bản ngắn có mục tiêu điều khiển tivi. Mỗi thể loại tương ứng với một hành động điều khiển: “tắt”, “bật”, “chuyển kênh”,. . . : x = “hãy bật tivi” ⇒ y = “bật ” x = “chuyển sang kênh HBO ” ⇒ y = “chuyển kênh” Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 5 / 29 Bài toán phân loại văn bản Gọi y = hθ(x) là hàm phân loại của x trong đó θ là tham số của hàm. Ta cần tìm hθ(·) có khả năng phân loại tốt. Để tìm hθ, ta sử dụng phương pháp học có hướng dẫn từ dữ liệu mẫu: Dữ liệu học gồm N mẫu: (x1, y1), (x2, y2), . . . , (xN , yN). Hàm hθ được xây dựng sao cho nó khớp nhất với dữ liệu huấn luyện này. Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 6 / 29 Bài toán phân loại văn bản Mỗi văn bản x là một đối tượng cần phân loại, thông thường x được chuyển thành một biểu diễn véc-tơ thực D chiều: x = (x1, x2, . . . , xD), xj ∈ R Các thành phần xj , j = 1, 2, . . . ,D được gọi là các đặc trưng hay thuộc tính của x. Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 7 / 29 Nội dung 1 Giới thiệu Bài toán phân loại văn bản Các mô hình xác suất 2 Một số mô hình phân loại Mô hình Bayes đơn giản Mô hình Bernoulli Mô hình TF-IDF 3 Thiết kế Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 8 / 29 Mô hình xác suất Có nhiều phương pháp phân loại văn bản nhưng phương pháp phân loại cho kết quả tốt nhất hiện nay đều sử dụng các mô hình xác suất. Gọi hθ(x) = P (y|x; θ) là mô hình xác suất có điều kiện dự báo các khả năng hay xác suất thuộc loại y của đối tượng x. Đối tượng x sẽ được xếp vào loại có xác suất lớn nhất theo mô hình: ŷ = arg max k=1,2,...,K P (y = k|x; θ) Chú ý rằng trong mô hình xác suất thì∑ k=1,2,...,K P (y = k|x; θ) = 1. Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 9 / 29 Nội dung 1 Giới thiệu Bài toán phân loại văn bản Các mô hình xác suất 2 Một số mô hình phân loại Mô hình Bayes đơn giản Mô hình Bernoulli Mô hình TF-IDF 3 Thiết kế Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 10 / 29 Nội dung 1 Giới thiệu Bài toán phân loại văn bản Các mô hình xác suất 2 Một số mô hình phân loại Mô hình Bayes đơn giản Mô hình Bernoulli Mô hình TF-IDF 3 Thiết kế Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 11 / 29 Mô hình Bayes đơn giản dạng nhị thức Giả sử x là một văn bản chứa các từ thuộc từ điển gồm D từ, đánh số từ 1 tới D. Khi đó ta có thể biểu diễn x bởi véc-tơ nhị phân x = (x1, x2, . . . , xD), xj ∈ {0, 1}, trong đó xj = { 1, nếu từ thứ j xuất hiện trong x 0, nếu từ thứ j không xuất hiện trong x. Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 12 / 29 Mô hình Bayes đơn giản dạng nhị thức Trong mô hình Bayes đơn giản (naive Bayes–NB), ta giả định các đặc trưng xj ∈ {0, 1} và độc lập nhau đối với từng loại y. Từ đó P (x, y; θ) = P (x |y; θ)P (y; θ) = D∏ j=1 P (xj |y; θ)P (y; θ). Các tham số của mô hình: θk = P (y = k),∀k = 1, 2, . . . ,K θj|k = P (xj = 1|y = k),∀j = 1, 2, . . . ,D;∀k = 1, 2, . . . ,K Chú ý rằng θK = 1− ∑K−1 k=1 θk, nên mô hình có (K − 1) +DK tham số. Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 13 / 29 Mô hình Bayes đơn giản dạng nhị thức Hàm hợp lí trên tập dữ liệu huấn luyện (x1, y1), . . . , (xN , yN ) là L(θ) = N∏ i=1 P (xi, yi) = N∏ i=1  D∏ j=1 P (xj |y; θ)P (y; θ)  = N∏ i=1  D∏ j=1 θj|kθk  . Từ đó có ước lượng hợp lí cực đại: θ̂k = ∑N i=1 δ(yi = k) N , θ̂j|k = ∑N i=1 δ(xij = 1, yi = k)∑N i=1 δ(yi = k) , trong đó δ(·) là hàm chỉ số. Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 14 / 29 Mô hình Bayes đơn giản dạng đa thức Trong mô hình Bayes dạng đa thức, ta xét tần số xuất hiện của từng từ trong x thay vì chỉ xét từ đó có xuất hiện hay không như trong mô hình Bayes nhị phân. Tham số của mô hình: θk là xác suất tiên nghiệm văn bản thuộc lớp k; θj|k xác suất từ j xuất hiện trong lớp k. Gọi f(k, j) là số lần từ j xuất hiện trong loại văn bản k. Khi đó ước lượng hợp lí cực đại của các tham số là θ̂k = ∑N i=1 δ(yi = k) N , θ̂j|k = f(k, j)∑D j=1 f(k, j) Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 15 / 29 Quy tắc phân loại Với mỗi đối tượng x, ta phân nó vào loại y với y := k̂ = arg max k=1,2,...,K P (y = k|x) = arg max k=1,2,...,K D∏ j=1 θj|kθk. Nếu sử dụng hàm loga, ta có quy tắc phân loại tuyến tính: y := k̂ = arg max k=1,...,K  D∑ j=1 log θj|k + log θk  . Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 16 / 29 Quy tắc phân loại Với mỗi văn bản x, gọi V là tập từ thuộc x. Thuật toán phân loại x trong mô hình Bayes đơn giản như sau: Algorithm 1: Thuật toán phân loại Bayes đơn giản Data: x, θk, θj|k, k = 1, 2, . . . ,K, j = 1, 2, . . . ,D for k = 1, 2, . . . ,K do s[k]← log θk ; for j ∈ V do s[k]← s[k] + log θj|k; return arg maxk s[k]; Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 17 / 29 Làm trơn mô hình Ta cần làm trơn mô hình để xử lí trường hợp θj|k = 0. Nếu θj|k = 0,∀k = 1, 2, . . . ,K thì P (x) = K∑ k=1 θk D∏ j=1 θj|k  = 0. Từ đó P (y = k|x) = 0 0 , ∀k = 1, 2, . . . ,K nên ta không thể phân loại x. Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 18 / 29 Làm trơn mô hình Ta sử dụng phương pháp làm trơn Laplace: θ̂j|k = θ̂j|k + α θ̂k + D × α trong đó α là hệ số làm trơn. Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 19 / 29 Nội dung 1 Giới thiệu Bài toán phân loại văn bản Các mô hình xác suất 2 Một số mô hình phân loại Mô hình Bayes đơn giản Mô hình Bernoulli Mô hình TF-IDF 3 Thiết kế Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 20 / 29 Mô hình Bernoulli Trong mô hình Bayes đơn giản ở trên, θj|k là tần suất từ hay tần suất vị trí trong các văn bản thuộc lớp k có chứa từ j. Mô hình Bernoulli sử dụng tham số này theo cách khác, là tần suất văn bản thuộc lớp k có chứa từ j. Như vậy, mô hình Bernoulli chỉ sử dụng thông tin từ j có xuất hiện trong văn bản lớp k hay không, không quan tâm từ đó xuất hiện bao nhiêu lần. Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 21 / 29 Mô hình Bernoulli Gọi f(k, j) là số lần văn bản thuộc loại k chứa từ j. Khi đó θ̂j|k = f(k, j)∑D j=1 f(k, j) . Làm trơn mô hình: θ̂j|k = θ̂j|k + α θ̂k + D × α trong đó α là hệ số làm trơn. Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 22 / 29 Quy tắc phân loại Với mỗi văn bản x, gọi V là tập từ thuộc x. Thuật toán phân loại x trong mô hình Bernoulli như sau: Algorithm 2: Thuật toán phân loại Bernoulli Data: x, θk, θj|k, k = 1, 2, . . . ,K, j = 1, 2, . . . ,D for k = 1, 2, . . . ,K do s[k]← log θk ; for j = 1, 2, . . . ,D do if j ∈ V then s[k]← s[k] + log θj|k; else s[k]← s[k] + log(1− θj|k); return arg maxk s[k]; Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 23 / 29 Nội dung 1 Giới thiệu Bài toán phân loại văn bản Các mô hình xác suất 2 Một số mô hình phân loại Mô hình Bayes đơn giản Mô hình Bernoulli Mô hình TF-IDF 3 Thiết kế Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 24 / 29 Mô hình TF-IDF Gọi tf(j,x) là số lần từ j xuất hiện trong văn bản x và df(j) là số văn bản có chứa từ j trong tập huấn luyện. Ta tính nghịch đảo của tần số văn bản chứa từ j như sau: idf(j) = log ( N df(j) ) . Về mặt trực quan, idf(j) là nhỏ nếu từ j xuất hiện trong nhiều văn bản và là lớn nhất nếu nó chỉ xuất hiện trong một văn bản. Mỗi văn bản được biểu diễn dạng véc-tơ x = (x1, x2, . . . , xD), trong đó xj = tf(j,x)× idf(j), ∀j = 1, 2, . . . ,D. Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 25 / 29 Mô hình TF-IDF Tiếp theo, ta tính các tham số của mô hình: ck = ∑ i:yi=k xi, ∀k = 1, 2, . . . ,K. Quy tắc phân loại cho văn bản x là: y = arg max k cos(x, ck) = arg max k ∑D j=1 xj × ckj√∑D j=1 x 2 j × √∑D j=1 c 2 kj Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 26 / 29 Quy tắc phân loại Với mỗi văn bản x, gọi V là tập từ thuộc x. Thuật toán phân loại x trong mô hình TF-IDF như sau: Algorithm 3: Thuật toán phân loại TF-IDF Data: x, ck, k = 1, 2, . . . ,K for k = 1, 2, . . . ,K do s[k]← cos(x, ck); return arg maxk s[k]; Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 27 / 29 Nội dung 1 Giới thiệu Bài toán phân loại văn bản Các mô hình xác suất 2 Một số mô hình phân loại Mô hình Bayes đơn giản Mô hình Bernoulli Mô hình TF-IDF 3 Thiết kế Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 28 / 29 Thiết kế Xem tài liệu thiết kế chi tiết các lớp trong gói phần mềm com.fpt.nao.text. Các lớp chính cài đặt các thuật toán phân loại: NBTextClassifier BernoulliClassifier TFIDFClassifier Lớp TextClassifierTester minh họa cách sử dụng các thuật toán phân loại ở trên. Lê Hồng Phương (HUS, VNU) Một số thuật toán phân loại văn bản 6/2013 29 / 29