¿Por qué el paquete textreuse en R hace que los cubos de LSH sean mucho más grandes que los minhashes originales?
Por lo que tengo entendido, una de las funciones principales del método LSH es la reducción de datos incluso más allá de los hash subyacentes (a menudo minhashes). He estado usando el textreusepaquete en R y me sorprende el tamaño de los datos que genera. textreusees un paquete ROpenSci revisado por pares , así que supongo que hace su trabajo correctamente, pero mi pregunta persiste.
Digamos que utilizo 256 permutaciones y 64 bandas para mis funciones minhash y LSH respectivamente, valores realistas que a menudo se usan para detectar con relativa certeza (~ 98%) similitudes tan bajas como 50%.
Si hago un hash en un archivo de texto aleatorio usando TextReuseTextDocument(256 permisos) y lo asigno trtd, tendré:
object.size(trtd$minhashes)
> 1072 bytes
Ahora creemos los cubos LSH para este objeto (64 bandas) y asígnelos a l, tendré:
object.size(l$buckets)
> 6704 bytes
Por lo tanto, los hash retenidos en los cubos de LSH son seis veces más grandes que los minhashes originales. Entiendo que esto sucede porque textreuse usa un resumen md5 para crear los hashes del cubo.
¿Pero no es esto demasiado derrochador / exagerado y no puedo mejorarlo? ¿Es normal que nuestra técnica de reducción de datos termine hinchándose hasta este punto? ¿Y no es más eficaz hacer coincidir los documentos en función de los valores hash originales (similar a permanentes = 256 y bandas = 256) y luego usar un umbral para eliminar los falsos positivos?
Tenga en cuenta que he revisado los textos típicos como Minería de conjuntos de datos masivos , pero esta pregunta permanece sobre esta implementación en particular. También tenga en cuenta que la pregunta no es solo por curiosidad, sino por necesidad. Cuando tiene millones o miles de millones de hashes, estas diferencias se vuelven significativas.
Respuestas
Autor del paquete aquí. Sí, sería un desperdicio usar más hashes / bandas de las que necesita. (Aunque tenga en cuenta que aquí estamos hablando de kilobytes, que podrían ser mucho más pequeños que los documentos originales).
La pregunta es, ¿qué necesitas? Si solo necesita encontrar coincidencias que sean casi idénticas (es decir, con una puntuación de Jaccard cercana a 1.0), entonces no necesita una búsqueda particularmente sensible. Sin embargo, si necesita detectar de manera confiable posibles coincidencias que solo comparten una superposición parcial (es decir, con una puntuación Jaccard más cercana a 0), entonces necesita más hashes / bandas.
Como ha leído MMD, puede buscar la ecuación allí. Pero hay dos funciones en el paquete, documentadas aquí , que pueden ayudarlo a calcular cuántos hashes / bandas necesita. lsh_threshold()calculará la puntuación umbral de Jaccard que se detectará; while lsh_probability()le dirá la probabilidad de que se detecten un par de documentos con una puntuación Jaccard determinada. Juegue con esas dos funciones hasta que obtenga el número de hashes / bandas que sea óptimo para su problema de búsqueda.