Bài giảng Tìm kiếm và trình diễn thông tin - Bài 4: Trọng số từ, mô tả hình không gian vecto - Nguyễn Bá Ngọc

Nội dung text: Bài giảng Tìm kiếm và trình diễn thông tin - Bài 4: Trọng số từ, mô tả hình không gian vecto - Nguyễn Bá Ngọc

1. (IT4853) Tìm kiếm và trình diễn thông tin Trọng số từ, mô hình không gian vec-tơ 1
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  1. Trọng số từ  2. Mô hình không gian vec-tơ 3
4. Xếp hạng kết quả tìm kiếm  Theo tiêu chí tương đồng:  Đánh giá mức tương đồng giữa văn bản và truy vấn  Trả về những văn bản có mức tương đồng cao và theo thứ tự giảm dần giá trị đó. 4
5. Mức tương đồng  Trong xếp hạng, quan hệ thứ tự quan trọng hơn tính chính xác của các giá trị.  Thông thường mức tương đồng được đưa về miền giá trị [0, 1].  Văn bản thường được đánh giá dựa trên cách sử dụng từ truy vấn. 5
6. Ch. 6 Hệ số Jaccard  Hai đối tượng bất kỳ được đánh giá là tương đồng nếu chia sẻ những đặc trưng chung.  Hệ số Jaccard được sử dụng khá rộng rãi để đánh giá mức tương đồng.  Đối với hai tập hợp A và B:  Jaccard(A, B) = |A ∩ B| / |A ∪ B|  0 <= Jaccard(A, B) <= 1  Jaccard(A, A) = 1  Jaccard(A, B) = 0 nếu ∩ = ∅ Cần xét đến vai trò tương đối giữa các đặc trưng 6
7. Trọng số từ  Thể hiện tầm quan trọng của từ đối với văn bản:  Đồng biến với số lần từ được sử dụng trong văn bản.  Nghịch biến với số văn bản sử dụng nó. 7
8. Trọng số tf.idf  Trọng số tf.idf được tính như sau: wtf.idf(t, d) = wtf(t,d) x idf(t) 8
9. Thành phần tf  Term Frequency (tf)  Trọng số 1 + 푙표 푡 , ế 푡 > 0 푤 푡, = 10 푡, 푡, 푡 0, ế 푛 ượ 푙ạ푖  Trong đó: tft,d là tần suất từ t trong văn bản d là số lần từ t được sử dụng trong văn bản d 9
10. Thành phần idf  Inverse document frequency (idf)  Xác định idf(t) như sau: idf(t) = log10(N/dft)  Trong đó N là số văn bản trong bộ dữ liệu; dft là số văn bản chứa từ t 10
11. Nội dung chính  1. Trọng số từ  2. Mô hình không gian vec-tơ 11
12. Biểu diễn văn bản và truy vấn  Trong không gian vec-tơ M chiều, với M = |V| là kích thước bộ từ vựng, mỗi thuật ngữ trong bộ từ vựng là một trục của không gian:  Mỗi văn bản, mỗi truy vấn là một điểm trong không gian này  M có thể rất lớn, vec-tơ biểu diễn văn bản và truy vấn là những vec-tơ thưa.  Ký hiệu , 푞 là biểu diễn vec-tơ của văn bản d và truy vấn q. 12
13. Xác định mức tương đồng  Tương đồng là đặc tính nghịch của sự khác biệt.  Có thể xác định mức khác biệt bằng khoảng cách.  Thử nghiệm 1: Xếp hạng văn bản theo thứ tự tăng dần của khoảng các Euclide giữa các điểm biểu diễn văn bản và truy vấn. 13
14. Ví dụ khoảng cách Euclide  Khoảng cách Euclide giữa biểu diễn vec-tơ của q và d2 tương đối lớn mặc dù phân bố từ khá giống nhau 14
15. Sử dụng khoảng cách góc  Thử nghiệm 2: Từ văn bản d thiết lập d’ bằng cách lặp lại nội dung của d.  Về mặt nội dung thì d và d’ là tương đương. Văn bản d’ tuy dài hơn nhưng không cung cấp thông tin mới.  Khoảng cách Euclide giữa d và d’ có thể rất lớn  Góc giữa biểu diễn vec-tơ của d và d’ bằng 0 thể hiện mức tương đồng cực đại  Xếp hạng văn bản theo thứ tự tăng dần của góc giữa các biểu diễn vec-tơ của văn bản và truy vấn. 15
16. Thay thế góc bằng cosine  Hai phương pháp sau là tương đương  Xếp hạng văn bản theo thứ tự tăng dần góc giữa các biểu diễn vec-tơ của văn bản và truy vấn  Xếp hạng văn bản theo thứ tự giảm dần cosine góc giữa các biểu diễn vec-tơ của văn bản và truy vấn.  Cosine là hàm đơn điệu giảm trong khoảng [0o,180o] 16
17. Sử dụng cosine thay góc Tính cosine như thế nào? Ưu điểm sử dụng cosine so với góc? 17
18. Mức tương đồng Cosine t3  Mức tương đồng cosine thể hiện bằng cosine 1 góc giữa hai vec-tơ D  Là tích vô hướng chia cho tích độ dài các vec-tơ 1 Q |V | 2 (w  w ) t1 d q  i,d i,q Sim (d,q) i 1 cos |V | |V | t d  q 2 2 2 D2  wi,d   wi,q i 1 i 1 D1 = 2T1 + 3T2 + 5T3 Simcos(D1 , Q) = 10 / (4+9+25)(0+0+4) = 0.81 D2 = 3T1 + 7T2 + 1T3 Simcos(D2 , Q) = 2 / (9+49+1)(0+0+4) = 0.13 Q = 0T1 + 0T2 + 2T3 D1 phù hợp với truy vấn hơn D2 6 lần theo độ tương đồng Cosine nhưng chỉ hơn 5 lần theo tích vô hướng. 18
19. Chuẩn hóa cosine  Chia mỗi thành phần vec-tơ cho độ dài của nó, độ dài vec-tơ được xác định như sau: x x2 2 i i  Độ dài vec-tơ đã chuẩn hóa bằng 1, vì vậy mỗi văn bản là một điểm trên bề mặt siêu cầu có bán kính 1 đơn vị.  Chuẩn hóa làm mờ sự khác biệt trọng số giữa các văn bản dài và ngắn 19
20. Cosine cho vec-tơ đã chuẩn hóa  Cosine góc giữa các vec-tơ đã chuẩn hóa bằng tích vô hướng của các vec-tơ này: V cos(q,d) q d q d i 1 i i Với và 푞 là những vec-tơ đã chuẩn hóa 20
21. Hệ ký hiệu SMART u – số lượng từ duy nhất trong văn bản SMART – System for the Mechanical Analysis and Retrieval of Text CharLength – số ký tự trong văn bản Vì sao cơ số hàm log để trống? 21
22. Xác định biểu diễn vec-tơ cho truy vấn và văn bản  Trong thực tế, cách biểu diễn vec-tơ cho văn bản và truy vấn có thể khác nhau.  Ký hiệu SMART mô tả vắn tắt cách xác định biểu diễn vec-tơ cho văn bản và truy vấn theo định dạng ddd.qqq  Phương pháp chuẩn là lnc.ltc:  Văn bản: Lấy log tf, không sử dụng idf, và chuẩn hóa cosine  Truy vấn: Lấy log tf, idf, chuẩn hóa cosine 22
23. Ví dụ phương pháp lnc.ltc  Văn bản: Bảo hiểm ô tô bảo hiểm xe máy  Truy vấn: bảo hiểm ô tô tốt nhất Thuật Truy vấn Văn bản Tích ngữ tf- tf- df idf wt n’lize tf- tf-wt wt n’lize raw wt raw xe máy 0 5000 2.3 1 tốt nhất 1 50000 1.3 0 ô tô 1 10000 2.0 1 bảo hiểm 1 1000 3.0 2 Số văn bản N = ? 23
24. Ví dụ phương pháp lnc.ltc  Văn bản: Bảo hiểm ô tô bảo hiểm xe máy  Truy vấn: bảo hiểm ô tô tốt nhất Thuật Truy vấn Văn bản Tích ngữ tf- tf- df idf wt n’lize tf- tf-wt wt n’lize raw wt raw xe máy 0 0 5000 2.3 0 0 1 1 1 0.52 0 tốt nhất 1 1 50000 1.3 1.3 0.34 0 0 0 0 0 ô tô 1 1 10000 2.0 2.0 0.52 1 1 1 0.52 0.27 bảo hiểm 1 1 1000 3.0 3.0 0.78 2 1.3 1.3 0.68 0.53 N = 102 * 10000 = 1000 000 Độ dài văn bản = 12 02 12 1.32 1,92 Độ dài truy vấn = 1,32 02 2,02 3.02 3,83 Score = 0+0+0.27+0.53 = 0.8 24
25. Ví dụ độ tương đồng cosine Tần suất từ (tf) Từ d1 d2 d3 a 115 58 20 b 10 7 11 c 2 0 6 d 0 0 38 Trong ví dụ này, không tính idf (idf = 1). 25
26. Ví dụ độ tương đồng cosine Log tần suất từ Sau khi chuẩn hóa Từ d1 d2 d3 Từ d1 d2 d3 a 3,06 2,76 2,30 a 0,789 0,832 0,524 b 2,00 1,85 2,04 b 0,515 0,555 0,465 c 1,30 0 1,78 c 0,335 0 0,405 d 0 0 2,58 d 0 0 0,588 cos(d1,d2) ≈ 0.789 × 0.832 + 0.515 × 0.555 + 0.335 × 0.0 + 0.0 × 0.0 ≈ 0.94 cos(d1,d3) ≈ 0.79 cos(d2,d3) ≈ 0.69 26
27. Mô hình không gian vec-tơ  D, Q: Tập các vec-tơ  F: Lý thuyết đại số  R: Mức tương đồng cosine. 27
28. Bài tập 4.1  Khoảng cách Euclide (hoặc khoảng cách L2) giữa hai vec- tơ được xác định như sau: M 2 x y  xi yi i 1  Cho truy vấn q và các văn bản d1, d2, Hãy chứng minh rằng nếu 푞 và 푖 đều được chuẩn hóa thành vec-tơ đơn vị thì kết quả xếp hạng theo thứ tự tăng dần khoảng cách Euclide giống kết quả xếp hạng theo thứ tự giảm dần mức tương đồng cosine 28
29. Bài tập 4.2  a) Trọng số idf của từ xuất hiện trong mọi văn bản bằng bao nhiêu? So sánh ảnh hưởng của trọng số idf với thao tác lọc từ dừng?  b) Trọng số tf-idf của một từ có thể vượt quá 1 hay không? 29
30. Bài tập 4.3  Cho bảng tần suất từ và tần suất văn bản như sau: Doc1 Doc2 Doc3 df idf xe máy 27 4 24 xe máy 18 165 ô tô 3 33 0 ô tô 6723 bảo hiểm 0 33 29 bảo hiểm 19 241 tốt nhất 14 0 17 tốt nhất 25 235  Với số lượng văn bản N = 806 791, hãy tính ma trận trọng số tf.idf 30