chương 1, phân tích những ưu điểm nhược điểm của từng phương pháp tạo tiền đề để phục vụ việc lựa chọn, đề xuất giải pháp trong chương tiếp theo. Các bài toán kèm theo phương pháp tiếp cận được trình bày trong chương này bao gồm: Bài toán xử lý trùng lặp tin tức, bài toán phân loại tin tức, bài toán xác định từ khóa quan trọng của tin tức. Các phương pháp tiếp cận bài toán trùng lặp tin tức Về cơ bản tin tức sau khi thu thập dữ liệu và tiền xử lý loại bỏ các phần thừa, cũng như chuẩn hóa dữ liệu tin đầu vào thì bài toán phát hiện trùng lặp tin tức có thể quy về bài toán phát hiện trùng lặp nội dung văn bản text. Có rất nhiều phương pháp khác nhau để phát hiện trùng lặp văn bản - Gọi là các phương pháp NDD (Near Duplicate Detection)[3].
Luận văn sẽ giới thiệu một số phương pháp cơ bản bao gồm: - Bag of Words – So sánh các từ và tần số của những từ đó trên một bản tin với những bản tin khác. - Shingling – Phương pháp này cải tiến trên "Bag of Words" phương pháp tiếp cận bằng cách so sánh các cụm từ ngắn, cung cấp một số ngữ cho các từ. - Hashing – Phương pháp này sẽ cải thiện được quá trình kiểm tra trùng lặp bằng cách loại bỏ sự cần thiết để lưu trữ các bản sao của tất cả các nội dung. Các cụm từ được băm vào con số, mà sau đó có thể được so sánh để xác định sự trùng lặp.
- MinHash – Hàm băm giúp lưu trữ phản ánh một phần nội dung trùng lặp theo ngữ cảnh dựa trên sự tương đồng các vec-tơ nhị phân. - SimHash – Hàm băm giúp lưu trữ phản ánh một phần nội dung trùng lặp theo ngữ cảnh dựa vào dữ liệu thực thông qua độ đo cosine. Phần tiếp theo, luận văn sẽ đi vào phân tích chi tiết từng phương pháp tiếp cận trên để làm rõ hơn bài toán, cũng như phân tích những thuận lợi khó khăn khi áp dụng các phương pháp này vào thực tế. Bag of Words Bag of Words là một trong những kĩ thuật cơ bản nhất trong việc thực hiện kiểm tra phát hiện trùng lặp nội dung văn bản.
Giả định rằng chúng ta có một tập hợp các tài liệu độc lập, và muốn tìm thấy một bản sao trùng lặp của nó. Với mỗi tài liệu chúng ta sẽ so khớp nội dung trùng với các tài liệu khác. Nội dung trùng là các từ trùng lặp trong một túi từ (bag of word) bao gồm các từ ( được tách độc lập) từ nội dung bản tin. Chẳng hạn một đoạn tài liệu: A = “khám phá vẻ đẹp tiềm ẩn của Sơn Đoòng” LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 17 sẽ được chuyển về một tập hợp các từ bao gồm: 𝐵𝑎𝑔𝐴 = {𝑐ủ𝑎, đẹ𝑝, 𝑘ℎá𝑚_𝑝ℎá, 𝑡𝑖ề𝑚_ẩ𝑛, 𝑆ơ𝑛_ Đ𝑜ò𝑛𝑔, 𝑣ẻ} Để so sánh hai tài liệu chúng ta tìm ra các từ chungcủa hai tài liệu so với tập hợp từ của cả hai tài liệu độ đo này được gọi là hệ số Jaccard.
Chẳng hạn để so sánh câu 𝐵 = “𝑘ℎá𝑚 𝑝ℎá 𝑣ẻ đẹ𝑝 𝑡𝑖ề𝑚 ẩ𝑛 𝑐ủ𝑎 𝑃ℎ𝑜𝑛𝑔 𝑁ℎ𝑎” ta làm như sau: 𝐵𝑎𝑔𝐵 = {𝑐ủ𝑎, đẹ𝑝, 𝑘ℎá𝑚_𝑝ℎá, 𝑃ℎ𝑜𝑛𝑔_𝑁ℎ𝑎, 𝑡𝑖ề𝑚_ẩ𝑛, 𝑣ẻ} Hình 2. Mô phỏng BagofWords Hệ số Jaccard trong trường hợp này: 𝐽(𝐴 ∩ 𝐵) 4 𝐽(𝐴, 𝐵) = = ~0.67 𝐽(𝐴 ∪ 𝐵) 6 Giải pháp này đơn giản, và thuận lợi khi hai đoạn văn bản nội dung khác nhau với các từ trong túi từ khác nhau nhiều. Tuy nhiên nó cũng gây ra sự nhầm lẫn vì có những trường hợp hai câu có lượng lớn các từ giống nhau nhưng nghĩa có thể khác xa nhau. Hay nói cách khác, cách làm này không giữ lại được ngữ cảnh và sẽ xảy ra trường hợp sai sót.
Chẳng hạn như câu: “tôi thích bạn” và câu: “bạn thích tôi”. Rõ ràng ngữ cảnh nói chung hay trật tự sắp đặt các từ trong câu là quan trọng trong việc kiểm tra nội dung, để khắc phục nhược điểm này người ta đề xuất cải tiến thêm một phương pháp tiếp cận mà chúng ta sẽ nghiên cứu trong mục tiếp theo đó là Shingling. Shingling Shingling được trình bày vào năm 1997 bởi Broder và cộng sự. Thuật toán Shingling dựa trên tập hợp các bộ từ (token) chồng lên nhau (giả sử là k token).
Trong shingling, tất cả các chuỗi con từ của các từ liền kề sẽ được trích xuất. Qua đó, mỗi tài liệu D lấy được một tập SD. Đó là việc chuyển đổi một tài liệu thành một tập hợp của LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Sự giống nhau giữa hai tài liệu được đo bằng cách sử dụng hệ số Jaccard giữa các vectơ shingle.
Các tài liệu có độ tương đồng cao được coi là gần như trùng lặp. Xem xét trình tự của các từ trong một tài liệu. Tập hợp các shingle cấu thành tập các đặc trưng của một tài liệu. Việc lấy giá trị k rất nhạy cảm, và ảnh hưởng trực tiếp tới kích thước của shingle và qua đó ảnh hưởng đến tốc độ xử lý cũng như độ chính xác của việc phát hiện trùng lặp.
- Kích thước shingle dài: Những thay đổi ngẫu nhiên nhỏ của tài liệu gây ảnh hưởng lớn. - Kích thước shingle ngắn: Các tài liệu không liên quan có thể có quá nhiều sự tương đồng. Trở lại ví dụ ở trên hai mệnh đề: d1 = "tôi thích bạn" và d2 = "bạn thích tôi" Nếu theo cách tiếp cận Bagofword thì hai mệnh đề này giống nhau 100%. Theo cách tiếp cận này giả sử chọn k=2.67 𝐽(𝐴 ∪ 𝐵) 6 Vẫn có sự tương đồng giữa hai mệnh đề.
Kết luận: Shingling có thể kiểm tra trùng lặp giữ lại một phần ngữ cảnh của tài liệu. Tuy nhiên có một vấn đề xảy ra là việc lưu trữ tập shingle lớn, việc kiểm tra trùng lặp trở nên khó khăn và không khả thi trong thực tế. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Hashing Như đã đề cập ở mục trước, vấn đề lớn của phương pháp trên là việc lưu trữ và lưu trữ trùng lặp các đoạn k-gram từ diễn ra thường xuyên, và có k từ trong một cụm từ thì độ phức tạp lưu trữ sẽ rơi vào khoảng O(nk), Để giảm thiểu điều này chúng ta chuyển mỗi cụm từ qua một hàm băm nhất định để tạo đại diện, và thay vì lưu trữ cả một túi các từ ta sẽ lưu trữ đại diện tạo ra từ hàm băm, việc này sẽ thuận lợi hơn và giảm thiểu được không gian lưu trữ.
Ví dụ như trên khi lưu trữ các cụm từ với k-2 sẽ có các đoạn hash sau: Hình 2.2 Ví dụ về hashing Việc giảm được không gian lưu trữ là một bước tiến đáng kể tuy nhiên trong môi trường thực tế việc lưu trữ đầy đủ các hash của các cụm từ để so sánh hai tài liệu vẫn là một việc làm vô cùng khó khăn. Rất nhiều tài liệu có độ dài lớn, khi so sánh hai tài liệu với mô hình K-gram với các cụm từ (phrases) trùng lặp việc lưu trữ và tính toán vẫn là rất lớn. Đã có một vài nghiên cứu phát triển thêm để giảm bớt thời gian tính toán trùng lặp. Trong luận văn này sẽ đề cập đến hai hàm băm đặc biệt đó là MinHash và SimHash, chi tiết sẽ được giới thiệu trong mục tiếp.
MinHash MinHash là một cách tiếp cận mới với khả năng sử dụng bộ nhớ không phụ thuộc vào độ dài của tài liệu đồng thời cung cấp phương thức tốt hơn để tính toán độ tương đồng. Cách tiếp cận này dựa trên việc băm mỗi tài liệu ra một tập cố định các hash như một dạng chữ kí thô của tài liệu đó. Việc băm đặc biệt này được thực hiện bằng cách sử dụng một tập hợp k hàm băm ngẫu nhiên. Với mỗi hàm băm ngẫu nhiên kí hiệu là πi,, chúng ta truyền tải nội dung LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 20 của các cụm từ trong tài liệu thông qua hàm băm để tạo một dãy băm nhỏ nhất (minimum) kí hiệu là mi.
Mô phỏng minhash Chữ kí của tài liệu giờ sẽ là danh sách thứ tự các hàm băm tối thiểu m0. Tiếp đó một cách gần đúng ta có thể đo tương tự bằng hệ số Jaccard thông qua việc so sánh từng cặp mã băm của tập hàm băm tối thiểu của tài liệu, và đưa ra kết quả sự giống nhau của tài liệu. Ví dụ về minhash Việc làm này có 2 lợi điểm lớn: Về lưu trữ mỗi tài liệu chỉ yêu cầu không gian lưu trữ O(1) về mặt độ phức tạp tính toán trùng lặp cặp tài liệu đem ra so sánh cũng chỉ là O(1). Sử dụng Minhash đã cải thiện rất lớn việc tính toán trùng lặp giữa cặp tài liệu bất kì.
Nhưng trong thực tế chúng ta phải đối mặt với vấn đề truy vấn việc trùng lặp một tài liệu mới với một tập các tài liệu có sẵn, áp dụng phương pháp này thì độ phức tạp thời gian tính toán đã trở nên tuyến tính O(n). Trong Crawler, chúng ta phải thu thập tất cả dữ liệu từ các bài tin và xác định tất cả sự trùng lặp của các trang tin, số lượng tin tức LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 21 phải xử lý trùng lặp lên đến hàng triệu trang, ở điểm này dường như Minhash có thể trở nên hạn chế hơn về tốc độ. SimHash Simhashing là kĩ thuật có thể giúp chúng ta khắc phục vấn đề này. Đầu vào của chúng ta là tập các hash, simhash sẽ tạo ra một mã hash duy nhất với một đặc tính rất đặc biệt - hai tập hashed đầu vào sẽ cho ra một kết quả hashes tương tự.
Hầu hết các loại hàm băm khác thường có đặc tính đầu vào dù khác nhau rất ít nhưng kết quả băm rất khác nhau ở phía đầu ra. Với mỗi vị trí bit, chúng ta đếm số hash đầu vào với tập bit được set và trừ đi số input hash với bit không đc set. Sau khi thực hiện trừ mỗi vị trí với giá trị âm sẽ được set là 0, các vị trí khác sẽ set là 1: Hình 2. Mô phỏng việc lấy simhash LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 22 Để tính toán sự giống nhau giữa hai đoạn simhash, chúng ta đếm số bit khác nhau giữa hai dãy bit chính là sự khác nhau giữa hai tài liệu.
Ngược lại, số bit giống nhau được coi như sự thể hiện giống nhau của hai tài liệu. Mô phỏng việc tính trùng lặp bằng simhash Rõ ràng việc tính toán này thuận lợi hơn nhiều so với việc lưu trữ những dãy hash dài cho mỗi tài liệu, với phương pháp này ta chỉ cần lưu lại một dãy bit hữu hạn như một dấu vân.