Neden R'deki metin yeniden kullanım paketi LSH kovalarını orijinal mini karelerden çok daha büyük hale getiriyor?
Anladığım kadarıyla LSH yönteminin ana işlevlerinden biri, temeldeki karmaların (genellikle küçük karmalar) ötesinde bile veri azaltmadır. textreusePaketi R'de kullanıyorum ve ürettiği verilerin boyutu beni şaşırttı. textreusehakemli bir ROpenSci paketidir, bu yüzden işini doğru bir şekilde yaptığını varsayıyorum, ancak sorum devam ediyor.
Minhash ve LSH işlevlerim için sırasıyla 256 permütasyon ve 64 bant kullandığımı varsayalım - % 50'ye varan göreceli kesinlik (~% 98) benzerlikleri tespit etmek için sıklıkla kullanılan gerçekçi değerler .
TextReuseTextDocument(256 izin) kullanarak rastgele bir metin dosyasına hashing uygular ve atarsam trtd, sahip olacağım:
object.size(trtd$minhashes)
> 1072 bytes
Şimdi bu nesne için (64 bant) LSH kovaları oluşturalım ve atayalım l, sahip olacağım:
object.size(l$buckets)
> 6704 bytes
Dolayısıyla, LSH kovalarındaki tutulan karmalar, orijinal mini karmalardan altı kat daha büyüktür. Bunun , kova karmalarını oluşturmak için textreuse bir md5 özeti kullandığı için olduğunu anlıyorum .
Ama bu çok savurgan / abartılı değil mi ve bunu geliştiremez miyim? Veri azaltma tekniğimizin bu ölçüde şişkinliğe neden olması normal mi? Belgeleri orijinal karmalara göre eşleştirmek (perms = 256 ve bantlar = 256'ya benzer) ve ardından yanlış pozitifleri ayıklamak için bir eşik kullanmak daha etkili değil mi?
Büyük Veri Kümelerinin Madenciliği gibi tipik metinleri gözden geçirdiğime dikkat edin , ancak bu soru bu özel uygulama ile ilgili kalır. Ayrıca sorunun yalnızca meraktan değil, ihtiyaçtan kaynaklandığını da unutmayın. Milyonlarca veya milyarlarca karmaya sahip olduğunuzda, bu farklılıklar önemli hale gelir.
Yanıtlar
Paket yazarı burada. Evet, ihtiyacınız olandan daha fazla karma / bant kullanmak israf olur. (Burada orijinal belgelerden çok daha küçük olabilecek kilobaytlardan bahsettiğimizi unutmayın.)
Soru şu ki, neye ihtiyacın var? Yalnızca aynı olan eşleşmeleri bulmanız gerekiyorsa (yani, Jaccard puanı 1,0'a yakın olan), o zaman özellikle hassas bir aramaya ihtiyacınız yoktur. Ancak, yalnızca kısmi bir örtüşmeyi paylaşan potansiyel eşleşmeleri güvenilir şekilde tespit etmeniz gerekiyorsa (yani, 0'a yakın bir Jaccard puanıyla), o zaman daha fazla karma / banda ihtiyacınız vardır.
MMD'yi okuduğunuza göre, denklemi oradan inceleyebilirsiniz. Ancak pakette, burada belgelenen ve ihtiyacınız olan karma / bant sayısını hesaplamanıza yardımcı olabilecek iki işlev vardır . lsh_threshold()tespit edilecek Jaccard puanı eşiği hesaplayacaktır; bu arada lsh_probability(), belirli bir Jaccard puanına sahip bir çift belgenin tespit edilme olasılığının ne kadar olduğunu size söyleyecektir. Arama probleminiz için en uygun karma / bant sayısını elde edene kadar bu iki işlevle oynayın.