Tại sao textreuse packge trong R lại làm cho các thùng LSH lớn hơn các minhashes ban đầu?
Theo như tôi hiểu, một trong những chức năng chính của phương pháp LSH là giảm dữ liệu thậm chí vượt ra ngoài các hàm băm cơ bản (thường là các hàm băm nhỏ). Tôi đã sử dụng textreuse
gói trong R và tôi rất ngạc nhiên bởi kích thước dữ liệu mà nó tạo ra. textreuse
là một gói ROpenSci được đánh giá ngang hàng, vì vậy tôi cho rằng nó hoạt động chính xác, nhưng câu hỏi của tôi vẫn tồn tại.
Giả sử tôi sử dụng 256 hoán vị và 64 dải tương ứng cho các hàm minhash và LSH của mình - các giá trị thực thường được sử dụng để phát hiện độ tương đồng chắc chắn (~ 98%) thấp nhất là 50%.
Nếu tôi băm một tệp văn bản ngẫu nhiên bằng TextReuseTextDocument
(256 perms) và gán nó cho trtd
, tôi sẽ có:
object.size(trtd$minhashes)
> 1072 bytes
Bây giờ, hãy tạo các thùng LSH cho đối tượng này (64 dải) và gán nó cho l
, tôi sẽ có:
object.size(l$buckets)
> 6704 bytes
Vì vậy, hàm băm được giữ lại trong nhóm LSH lớn hơn sáu lần so với hàm băm ban đầu. Tôi hiểu điều này xảy ra vì textreuse
sử dụng thông báo md5 để tạo hàm băm của nhóm.
Nhưng điều này có quá lãng phí / quá mức cần thiết và tôi không thể cải thiện nó không? Có bình thường không khi kỹ thuật giảm dữ liệu của chúng tôi kết thúc với mức độ này? Và không phải sẽ hiệu quả hơn nếu so khớp các tài liệu dựa trên các băm ban đầu (tương tự như perms = 256 và band = 256) và sau đó sử dụng một ngưỡng để loại bỏ các kết quả dương tính giả?
Lưu ý rằng tôi đã xem xét các văn bản điển hình như Khai thác các tập dữ liệu lớn , nhưng câu hỏi này vẫn còn về cách triển khai cụ thể này. Cũng lưu ý rằng câu hỏi không chỉ vì tò mò mà còn vì nhu cầu. Khi bạn có hàng triệu hoặc hàng tỷ băm, những khác biệt này trở nên đáng kể.
Trả lời
Tác giả gói ở đây. Có, sẽ lãng phí nếu sử dụng nhiều băm / dải hơn mức bạn cần. (Mặc dù hãy nhớ rằng chúng ta đang nói về kilobyte ở đây, có thể nhỏ hơn nhiều so với tài liệu gốc.)
Câu hỏi đặt ra là bạn cần gì? Nếu bạn chỉ cần tìm các kết quả gần giống nhau (tức là với điểm Jaccard gần bằng 1,0), thì bạn không cần tìm kiếm đặc biệt nhạy cảm. Tuy nhiên, nếu bạn cần phát hiện một cách đáng tin cậy các kết quả phù hợp tiềm năng chỉ có phần trùng lặp một phần (tức là với điểm Jaccard gần bằng 0), thì bạn cần nhiều băm / dải hơn.
Vì bạn đã đọc MMD, bạn có thể tra cứu phương trình ở đó. Nhưng có hai hàm trong gói, được nêu ở đây , có thể giúp bạn tính toán số lượng băm / dải bạn cần. lsh_threshold()
sẽ tính toán điểm Jaccard ngưỡng sẽ được phát hiện; trong khi lsh_probability()
sẽ cho bạn biết khả năng một cặp tài liệu có điểm Jaccard nhất định sẽ bị phát hiện. Thử với hai hàm đó cho đến khi bạn nhận được số lượng băm / dải tối ưu cho vấn đề tìm kiếm của mình.