Dlaczego textreuse packge in R sprawia, że wiadra LSH są znacznie większe niż oryginalne minhashy?
O ile rozumiem, jedną z głównych funkcji metody LSH jest redukcja danych, nawet poza bazowe skróty (często minhasze). Korzystałem z textreusepakietu w R i jestem zaskoczony wielkością generowanych przez niego danych. textreusejest recenzowanym pakietem ROpenSci , więc zakładam, że działa poprawnie, ale moje pytanie pozostaje.
Powiedzmy, że używam 256 permutacji i 64 pasm odpowiednio dla moich funkcji minhash i LSH - realistyczne wartości, które są często używane do wykrywania ze względną pewnością (~ 98%) podobieństw tak niskich, jak 50%.
Jeśli zaszyfuję losowy plik tekstowy za pomocą TextReuseTextDocument(256 pozwoleń) i przypiszę go do trtd, będę miał:
object.size(trtd$minhashes)
> 1072 bytes
Teraz stwórzmy wiadra LSH dla tego obiektu (64 pasma) i przypiszmy go do l, będę miał:
object.size(l$buckets)
> 6704 bytes
Zatem zachowane skróty w zasobnikach LSH są sześć razy większe niż oryginalne minhashy. Rozumiem, że dzieje się tak, ponieważ textreuse używa skrótu MD5 do tworzenia skrótów zasobnika.
Ale czy to nie jest zbyt marnotrawne / przesada i czy nie mogę tego poprawić? Czy to normalne, że nasza technika redukcji danych przerasta do tego stopnia? I czy nie jest skuteczniejsze dopasowanie dokumentów na podstawie oryginalnych skrótów (podobnie jak perms = 256 i bands = 256), a następnie użycie progu do wyeliminowania fałszywych alarmów?
Zwróć uwagę, że przejrzałem typowe teksty, takie jak Mining of Massive Datasets , ale pozostaje to pytanie dotyczące tej konkretnej implementacji. Zwróć również uwagę, że pytanie jest nie tylko z ciekawości, ale raczej z potrzeby. Kiedy masz miliony lub miliardy haszów, te różnice stają się znaczące.
Odpowiedzi
Autor pakietu tutaj. Tak, marnotrawstwo byłoby użycie większej liczby haszów / pasm niż potrzebujesz. (Chociaż pamiętaj, że mówimy tutaj o kilobajtach, które mogą być znacznie mniejsze niż w oryginalnych dokumentach).
Pytanie brzmi, czego potrzebujesz? Jeśli chcesz znaleźć tylko dopasowania, które są bliskie identyczności (tj. Z wynikiem Jaccard bliskim 1,0), nie potrzebujesz szczególnie wrażliwego wyszukiwania. Jeśli jednak potrzebujesz niezawodnego wykrywania potencjalnych dopasowań, które tylko częściowo pokrywają się (tj. Z wynikiem Jaccarda bliższym 0), potrzebujesz więcej haszów / pasm.
Ponieważ przeczytałeś MMD, możesz tam sprawdzić równanie. Jednak pakiet zawiera dwie funkcje, udokumentowane tutaj , które mogą pomóc w obliczeniu liczby potrzebnych skrótów / pasm. lsh_threshold()obliczy próg wyniku Jaccarda, który zostanie wykryty; while lsh_probability()powie Ci, jakie jest prawdopodobieństwo, że zostanie wykryta para dokumentów z danym wynikiem Jaccarda. Baw się tymi dwiema funkcjami, aż uzyskasz liczbę skrótów / pasm optymalną dla twojego problemu wyszukiwania.