Phát hiện trùng lặp gần đúng bằng độ tương đồng Jaccard và MinHash

Tìm tài liệu tương tự: độ tương đồng Jaccard và MinHash

• Định nghĩa vấn đề
  • Thảo luận về cách xác định các tài liệu tương tự trong một bộ sưu tập tài liệu quy mô lớn
  • Ví dụ, khi thu thập dữ liệu web, có thể tải cùng một trang nhiều lần và xuất hiện nhiều phiên bản với khác biệt nhỏ ở metadata hoặc sau các chỉnh sửa nhỏ
  • Bài viết này khám phá phương pháp khử trùng lặp gần đúng bằng độ tương đồng Jaccard và MinHash

Độ tương đồng

• Định nghĩa độ tương đồng
  • Định nghĩa độ tương đồng giữa hai tài liệu và cách tìm các cặp có giá trị độ tương đồng lớn hơn hoặc bằng một ngưỡng nhất định
  • Định nghĩa hàm độ tương đồng S:U×U→[0,1], và nếu S(A,B)≥S_crit thì coi hai tài liệu là trùng lặp gần đúng

Độ tương đồng Jaccard

• Độ tương đồng Jaccard
  • Một hàm biểu diễn độ tương đồng của hai tập hữu hạn bằng tỷ lệ giữa giao và hợp của chúng
  • J(A,B)=∣A∩B∣/∣A∪B∣
  • Hai tập càng giống nhau thì càng chia sẻ phần lớn các phần tử giống nhau

Mở rộng độ tương đồng Jaccard

• Phương pháp mở rộng
  • Chuyển tài liệu thành tập đặc trưng và tìm kiếm các tập có độ tương đồng Jaccard cao
  • Có thể áp dụng trực tiếp với corpus nhỏ, nhưng không hiệu quả với corpus lớn

Xấp xỉ độ tương đồng Jaccard

• Chữ ký MinHash
  • Sử dụng lấy mẫu để xấp xỉ độ tương đồng Jaccard
  • Tiền tính chữ ký có kích thước cố định cho mỗi tài liệu để ước lượng độ tương đồng một cách hiệu quả

Sử dụng nhiều hàm băm hơn

• Nhiều hàm băm
  • Dùng nhiều hàm băm để tóm tắt mỗi tài liệu thành một vector gồm k phần tử
  • Xấp xỉ độ tương đồng Jaccard bằng cách đếm số giá trị băm khớp nhau giữa hai chữ ký

So sánh tất cả tài liệu

• Nhóm tài liệu
  • Nhóm các tài liệu để chỉ so sánh những tài liệu tương tự
  • Dùng giá trị MinHash làm khóa nhóm để tìm trùng lặp gần đúng một cách hiệu quả

Phát hiện trùng lặp linh hoạt hơn

• Sử dụng nhiều khóa
  • Dùng nhiều khóa để đặt tài liệu vào nhiều bucket và so sánh trong từng bucket
  • Có thể phát hiện trùng lặp ngay cả ở mức độ tương đồng thấp hơn

Kết luận

• Kết luận
  • Có thể tìm tài liệu tương tự một cách hiệu quả thông qua các thuật toán như MinHash
  • Hy vọng bài viết này giúp nhiều kỹ sư hơn biết đến và hiểu rõ các thuật toán này

Phụ lục: biểu diễn tài liệu dưới dạng tập hợp

• n-gram

  • Biểu diễn tài liệu bằng n-gram để so sánh
  • Độ chính xác của phép so sánh thay đổi tùy theo giá trị n

• Tách từ

  • Tách tài liệu thành từ hoặc token để dùng làm đặc trưng
  • Cũng có thể dùng tokenizer tinh vi hơn

Ý kiến của GN⁺

• Tầm quan trọng của phát hiện tài liệu tương tự

  • Việc loại bỏ trùng lặp trong các tập dữ liệu lớn rất quan trọng để nâng cao chất lượng dữ liệu và tiết kiệm dung lượng lưu trữ
  • Đặc biệt cần thiết trong quá trình thu thập dữ liệu web hoặc thu thập dữ liệu nói chung

• Ưu điểm của MinHash

  • MinHash có thể phát hiện tài liệu tương tự theo cách hiệu quả và có khả năng mở rộng
  • Linh hoạt hơn các phương pháp khử trùng lặp dựa trên băm truyền thống

• Các kỹ thuật tương tự khác

  • Các thuật toán sketch khác như HyperLogLog cũng có thể được dùng để giải quyết các bài toán tương tự
  • Có thể kết hợp hai thuật toán để tạo ra giải pháp mạnh hơn

• Các điểm cần cân nhắc khi áp dụng thực tế

  • Tầm quan trọng của việc chọn hàm băm: lựa chọn hàm băm ảnh hưởng lớn đến độ chính xác của kết quả
  • Cân bằng giữa hiệu năng và độ chính xác: dùng càng nhiều hàm băm thì độ chính xác càng cao, nhưng chi phí hiệu năng cũng tăng

• Công nghệ được khuyến nghị

  • Có thể dễ dàng áp dụng bằng các công cụ như triển khai MinHashLSH của Spark
  • Khuyến nghị tích cực tận dụng các kỹ thuật này để khử trùng lặp hiệu quả trong các tập dữ liệu lớn

[GN⁺]

Ý kiến Hacker News

• Độ tương đồng Jaccard và điểm F1 cũng có thể được dùng theo cùng cách với tập mờ

  • Với tập mờ, cần chọn cặp T-Norm/T-Conorm phù hợp
  • Cách này hữu ích cho việc kiểm chứng phân đoạn ảnh y tế
  • Hầu hết mọi người đặt ngưỡng ở 0.5 và dùng tập nhị phân
  • Điều này làm giảm đáng kể độ chính xác của toán tử kiểm chứng

• Có kinh nghiệm triển khai khử trùng lặp cho cơ sở dữ liệu của chính phủ Pháp bằng Python

  • Hiện tại khuyến nghị dùng datasketch
  • Cũng có một công cụ mới tên là rensa
  • rensa là phiên bản nhanh hơn được viết bằng Rust

• Đây là công nghệ được phát triển ở giai đoạn đầu của Google để khử trùng lặp

  • Được giải thích chi tiết trong "Mining Massive Datasets" của Jeffrey Ullman
  • Công nghệ này ban đầu được phát triển tại AltaVista

• Có kinh nghiệm triển khai hệ thống Minhash

  • Đã giải quyết bài toán tìm ma trận nghịch đảo (xấp xỉ) của các ma trận con trong một ma trận lớn
  • Dùng Minhashing để tìm các ma trận tương tự
  • Điều chỉnh độ chọn lọc tìm kiếm bằng cách dùng băm đa độ phân giải

• Đang phát triển công cụ trực quan hóa vì Minhash và các biến thể của nó khá khó hiểu

  • Dự kiến sẽ bao gồm cả phép tính độ tương đồng Jaccard

• Hiểu kỹ thuật này qua ví dụ mã nguồn sẽ dễ hơn

  • Đã học kỹ thuật này từ Douglas Eck của Google
  • Được dùng cho phân cụm bài hát

• Nhóm NVIDIA đã phát hành thuật toán khử trùng lặp mờ tăng tốc bằng GPU

  • Có cung cấp kho GitHub và tài liệu
  • Cũng bao gồm ví dụ Python

• Chiến lược khử trùng lặp kết hợp băm hoặc mạng nơ-ron nhỏ với công cụ tìm kiếm vector là khá phổ biến

  • Có mô hình RETSim của Google và dự án engine USearch

• Đã chỉ ra lỗi chính tả cho tác giả

  • Phải là S(A,C) thay vì S(A,B)

• Đang giải quyết bài toán gộp các mục tin tức tương tự trong Postgres thành một

  • Có 600.000 mục feed
  • Nội dung và phần tóm tắt rất giống nhau