Bài giảng Tìm kiếm và trình diễn thông tin - Bài 17: Phát hiện trùng lặp gần - 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 17: Phát hiện trùng lặp gần - Nguyễn Bá Ngọc

1. (IT4853) Tìm kiếm và trình diễn thông tin Phát hiện trùng lặp gần
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. Phát hiện trùng lặp  Trùng lặp tuyệt đối  Dễ dàng loại bỏ, v.d., bằng tổng đại diện.  Trùng lặp gần  Khó phát hiện  Người dùng không mong muốn những kết quả trùng lặp.  Có thể coi một tài liệu vốn phù hợp là không phù hợp nếu lặp lại ngay trong danh sách kết quả. Cần loại bỏ những tài liệu trùng lặp! 3
4. Trùng lặp gần 4
5. Phát hiện trùng lặp gần  Tính độ tương đồng dựa trên “ký tự”  Rất khó tính độ tương đồng ngữ nghĩa  Những văn bản cùng nội dung nhưng được diễn đạt khác nhau không phải trùng lặp.  Sử dụng ngưỡng θ để kết luận “trùng lặp”.  Ví dụ, Coi hai tài liệu là trùng lặp gần nếu độ tương đồng > 80%. 5
6. Mô hình tập shingles  Shingle là một n-gram trên từ (bộ n-từ).  Ví dụ, với n = 3, “a rose is a rose is a rose” có mô hình tập shingles như sau:  { a-rose-is, rose-is-a, is-a-rose }  Tính tổng đại diện cho các shingles m  Tổng đại diện là các giá trị số trong khoảng 1 2 .  Ký hiệu sk là tổng đại diện của shingle k. Xác định độ tương đồng của hai tài liệu bằng hệ số Jaccard 6
7. Hệ số Jaccard  Cho hai tập đặc trưng A và B Vớ𝑖 ≠ ∅ ℎ표ặ ≠ ∅, ∩ 퐽 , = ∪  Jaccard(A,A) = 1  Jaccard(A,B) = 0 nếu A ∩ B = 0  Miền giá trị là khoảng [0, 1] 7
8. Ví dụ tính hệ số Jaccard  Cho ba tài liệu: d1: “Jack London traveled to Oakland” d2: “Jack London traveled to the city of Oakland” d3: “Jack traveled from Oakland to London”  Hãy tính hệ số Jaccard J(d1, d2) và J(d1, d3) sử dụng các bộ 2-từ (shingle với kích thước bằng 2)? 8
9. Ví dụ tính hệ số Jaccard  Cho ba tài liệu: d1: “Jack London traveled to Oakland” d2: “Jack London traveled to the city of Oakland” d3: “Jack traveled from Oakland to London”  Hãy tính hệ số Jaccard J(d1, d2) và J(d1, d3) sử dụng các bộ 2-từ (shingle với kích thước bằng 2)? J(d1, d2) = 3/8 = 0.375; J(d1, d3) = 0 Hệ số Jaccard rất nhạy cảm với trật tự từ 9
10. Biểu diễn khung của văn bản  Biểu diễn khung (sketch) – là tập con kích thước cố định của tập shingles với, v.d., n = 200.  Được xác định dựa trên một tập hợp các thao tác trộn π1 . . . π200.  Sketch của d được định nghĩa là: 10
11. Phép trộn và giá trị cực tiểu tài liệu 1: {sk} tài liệu 2: {sk} Sử dụng mins∈d1 π(s) = mins∈d2 π(s) như phép thử tính trùng lặp của d1 và d2 . Trong trường hợp này phép trộn π khẳng định: d1 ≈ d2 11
12. Hệ số Jaccard trên biểu diễn khung  Sketches  Mỗi tài liệu là một vec-tơ với n = 200 số.  Dễ xử lý hơn so với tập shingles  Chúng ta tính hệ số Jaccard bằng cách nào? 12
13. Hệ số Jaccard trên biểu diễn khung  Đặt U là hợp các shingles của d1 và d2, còn I là giao  Có |U|! phép trộn trên U  Với s′ ∈ I , có bao nhiêu phép trộn π để argmins∈d1 π(s) = s′ = argmins∈d2 π(s)?  Trả lời: (|U| − 1)!  Có (|U| − 1)! phép trộn cho mỗi s trong I ⇒ |I |(|U| − 1)! phép trộn thỏa mãn argmins∈d1 π(s) = argmins∈d2 π(s)  Như vậy, tỉ lệ phép trộn thỏa mãn mins∈d1 π(s) = mins∈d2 π(s) là: 13
14. Ước lượng hệ số Jaccard  Hệ số Jaccard bằng tỉ lệ phép trộn thành công.  Phép trộn π là thành công nếu mins ∈d1 π(s) = mins ∈d2 π(s)  Ước lượng xác suất trộn thành công  Sử dụng n phép chộn, v.d., n = 200  Đếm số lượng k phép trộn thành công  k/n được coi như J(d1, d2). 14
15. Cài đặt  Sử dụng hàm băm như phép trộn: m m hi : {1 2 } → {1 2 }  Với n = 200, cần n hàm băm  Với mỗi hi cần xác định các giá trị cực tiểu  Đếm số phép trộn thành công k  Giá trị gần đúng của độ tương đồng là k/n. 15
16. Ví dụ Kết quả trộn Cực tiểu 16
17. Bài tập Cho mô hình tập shingle của văn bản Hãy ước lượng hệ số Jaccard: J(d1, d2), J(d1, d3), J(d2, d3) 17
18. Đáp án h(x) = 5x + 5 mod 4 g(x) = (3x + 1) mod 4 Các biểu diễn khung 18
19. Đáp án 19
20. Tổng kết  Đầu vào: N tài liệu  Lựa chọn kích thước bộ n-từ, ví dụ, n = 5  Sử dụng 200 phép trộn ngẫu nhiên (200 hàm băm)  Tính N biểu diễn khung −1  Tính độ phù hợp theo cặp 2  Kết luận trùng lăp gần với độ tương đồng > θ  Bỏ qua các trùng lặp khi đánh chỉ mục 20
21. Phương pháp hiệu quả phát hiện trùng lặp gần 2  Cần phải ước lượng O(N ) hệ số với N là số trang web.  Các giải pháp cải thiện hiệu năng:  Giải pháp 1: hàm băm cục bộ (LSH) Andoni, Alexandr, Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab Mirrokni. 2006. Locality-sensitive hashing using stable distributions. In Nearest Neighbor Methods in Learning and Vision: Theory and Practice. MIT Press. 314, 519, 522, 524,527  Giải pháp khác: sắp xếp (Henzinger 2006) Henzinger, Monika R., Allan Heydon, Michael Mitzenmacher, and Marc Najork. 2000. On near-uniform URL sampling. In Proc. WWW, pp. 295–308. North-Holland. DOI: dx.doi.org/10.1016/S1389-1286(00)00055-4. 442, 524, 527, 528 21