¿Cuáles son algunas formas estándar de calcular la distancia entre documentos?

34

Cuando digo "documento", tengo en mente páginas web como artículos de Wikipedia e historias de noticias. Prefiero las respuestas que ofrecen métricas de distancia léxica de vainilla o métricas de distancia semántica de última generación, con mayor preferencia por la última.

Mate
fuente

Respuestas:

48

Hay varias maneras diferentes de hacerlo dependiendo de la cantidad exacta de información semántica que desea conservar y la facilidad con que se tokenizan sus documentos (los documentos html probablemente sean bastante difíciles de tokenizar, pero posiblemente podría hacer algo con etiquetas y contexto .)

Algunos de ellos han sido mencionados por ffriend, y los vectores de párrafo de user1133029 son realmente sólidos, pero me di cuenta de que profundizaría un poco más sobre las ventajas y desventajas de los diferentes enfoques.

  • Distancia al coseno : probado una verdadera distancia del coseno es probablemente la métrica de distancia más común utilizada genéricamente en múltiples dominios. Dicho esto, hay muy poca información en la distancia del coseno que en realidad se puede asignar a cualquier cosa semántica, lo que parece no ser ideal para esta situación.
  • Distancia de Levenshtein : también conocida como edit distance, esto generalmente solo se usa en el nivel de token individual (palabras, bigrams, etc.). En general, no recomendaría esta métrica, ya que no solo descarta cualquier información semántica, sino que también tiende a tratar las alteraciones de palabras muy diferentes de manera muy similar, pero es una métrica extremadamente común para este tipo de cosas.
  • LSA : forma parte de un gran arsenal de técnicas para evaluar la similitud de documentos topic modeling. LSA ha pasado de moda recientemente y, en mi experiencia, no es el enfoque de modelado de temas más sólido, pero es relativamente sencillo de implementar y tiene algunas implementaciones de código abierto
  • LDA : también es una técnica utilizada topic modeling, pero es diferente de LSAque realmente aprende representaciones internas que tienden a ser más suaves e intuitivas. En general, los resultados que obtiene LDAson mejores para modelar similitudes de documentos que LSA, pero no tan buenos para aprender a discriminar fuertemente entre los temas.
  • Asignación de Pachinko : es una extensión realmente ordenada además de LDA. En general, esta es solo una versión significativamente mejorada de LDA, con el único inconveniente de que toma un poco más de tiempo entrenar y las implementaciones de código abierto son un poco más difíciles de conseguir.
  • word2vec - Google ha estado trabajando en una serie de técnicas para reducir de manera inteligente las palabras y documentos a vectores más razonables que los vectores dispersos producidos por técnicas como Count Vectorizersy TF-IDF. Word2vec es excelente porque tiene varias implementaciones de código abierto. Una vez que tenga el vector, se puede usar cualquier otra métrica de similitud (como la distancia del coseno) con mucha más eficacia.
  • doc2vec - También conocido como paragraph vectors, este es el último y más grande en una serie de documentos de Google, que analiza representaciones vectoriales densas de documentos. La gensimbiblioteca en Python tiene una implementación word2vecque es lo suficientemente sencilla como para que se pueda aprovechar de manera bastante razonable para construir doc2vec, pero asegúrese de tener en cuenta la licencia si desea seguir esta ruta

Espero que ayude, avíseme si tiene alguna pregunta.

indico
fuente
6

Hay una serie de medidas de distancia semántica, cada una con sus ventajas y desventajas. Estos son solo algunos de ellos:

  • distancia cosenoidal , producto interno entre vectores de características del documento;
  • LSA , otro modelo basado en vectores, pero que utiliza SVD para eliminar ruido de la matriz original de documentos a término;
  • Basado en WordNet , verificado por humanos, aunque apenas extensible.

Comience con un enfoque más simple y luego avance según los problemas de su caso específico.

amigo
fuente
1
Tenga en cuenta que al hacer LSA, generalmente usa la distancia del coseno en las proyecciones de LSA del conjunto de datos original. Solo para aclarar.
Simon
6

Empíricamente, he encontrado que LSA es muy superior a LDA cada vez y en cada conjunto de datos que lo he probado. He hablado con otras personas que han dicho lo mismo. También se ha utilizado para ganar una serie de concursos SemEval para medir la similitud semántica entre documentos, a menudo en combinación con una medida basada en Wordnet, por lo que no diría que está pasando de moda, o definitivamente es inferior a LDA, lo cual es mejor para el modelado de temas y no la similitud semántica en mi experiencia, contrario a lo que algunos respondedores han declarado.

Si usa gensim (una biblioteca de Python), tiene LSA, LDA y word2vec, por lo que puede comparar fácilmente el 3. doc2vec es una idea genial, pero no se escala muy bien y es probable que tenga que implementarlo usted mismo como yo. desconocen las implementaciones de código abierto. No escala bien, ya que para cada documento, se debe construir un modelo nuevo y separado usando SGD, un algoritmo de aprendizaje automático lento. Pero probablemente le dará los resultados más precisos. LSA y LDA tampoco escalan bien (sin embargo, word2vec sí), LDA escala peor en general. Sin embargo, las implementaciones de Gensim son muy rápidas, ya que utiliza SVD iterativo.

Otra nota, si usa word2vec, aún tendrá que determinar una forma de componer vectores a partir de documentos, ya que le da un vector diferente por palabra. La forma más sencilla de hacer esto es normalizar cada vector y tomar la media sobre todos los vectores de palabras en el documento, o tomar una media ponderada mediante la ponderación idf de cada palabra. Por lo tanto, no es tan simple como 'use word2vec', tendrá que hacer algo más para calcular la similitud del documento.

Yo personalmente iría con LSA, ya que he visto que funciona bien empíricamente, y la biblioteca de gensim escala muy bien. Sin embargo, no hay almuerzo gratis, así que preferiblemente pruebe cada método y vea cuál funciona mejor para sus datos.

Simon
fuente
¿Cómo exactamente has usado LSA? Vale la pena señalar que LDA es en realidad un envoltorio bastante delgado alrededor de LSA (es pLSA con un dirichlet antes) que se ha demostrado empíricamente que aumenta en gran medida la generalización. Es casi seguro que verá mejores precisiones con LSA, pero eso generalmente es el resultado de un sobreajuste, que es un problema muy notable con LSA. Además, ¿qué quieres decir exactamente con escalar aquí? doc2vec en realidad no requiere un nuevo modelo para cada documento, y para el cálculo no hay una diferencia notable entre LSA y LDA, ambos muy escalables.
Slater Victoroff
No he observado un ajuste excesivo con LSA y, como dije, he conocido a muchas otras personas que han visto un mejor rendimiento con respecto a LDA. Además, he visto que LSA se usa en muchas entradas ganadoras en competencias paralelas, nunca he visto a LDA usado en una entrada ganadora. Esa es la conferencia académica para comparar la similitud semántica entre documentos, así que supongo que saben lo que están haciendo. Doc2vec, si se refiere a la implementación del vector de párrafo de Mikolov, hace SGD en cada documento por separado. Entonces es muy lento.
Simon
@SlaterVictoroff Creo que eso ha terminado de decir cosas para decir que es demasiado ajustado. Se sabe que LDA es pobre para la búsqueda / recuperación de información y casos de recomendación, empíricamente se ha demostrado que LSA funciona mucho mejor y eso también coincide con mi propia experiencia, ya que me gusta validar estos hallazgos con nuestros propios datos. Las versiones de Doc2Vec hacen un descenso de gradiente por documento, depende del algoritmo utilizado en Doc2Vec, ya que generalmente se refiere a muchos algoritmos diferentes.
Simon
3

El estado del arte parece ser "vectores de párrafo" introducidos en un artículo reciente: http://cs.stanford.edu/~quocle/paragraph_vector.pdf . La distancia coseno / euclidiana entre vectores de párrafo probablemente funcionaría mejor que cualquier otro enfoque. Esto probablemente aún no sea factible debido a la falta de implementaciones de código abierto.

La siguiente mejor opción es la distancia del coseno entre vectores LSA o la distancia del coseno entre vectores BOW sin procesar. A veces funciona mejor elegir diferentes esquemas de ponderación, como TF-IDF.

usuario1133029
fuente
Tenga en cuenta mis comentarios a continuación sobre la escalabilidad del vector de párrafo. Esta técnica parece muy prometedora, pero es difícil de implementar y no se escala bien en absoluto, ya que está haciendo un SGD por separado para cada documento, lo cual es muy costoso, si recuerdo el documento correctamente
Simon
1

Es útil tener en su bolsa de herramientas la familia de algoritmos de hashing sensibles a la localidad . Esta familia no es semántica en absoluto. En realidad se considera el texto como una secuencia de bits. Me resulta útil en conjuntos de datos sucios cuando el mismo texto aparece muchas veces con ligeras diferencias.

Puede usar ssdeep (que se basa en el hash de Nilsimsa ) para identificar dichos documentos. Ssdeep fue originalmente planeado para el dominio de spam. Los spammers a menudo hacen pequeños cambios en el mensaje (agregan un espacio) para evitar la detección por firma exacta (por ejemplo, md5 ).

Dado que muchas versiones de casi el mismo documento en el mismo conjunto de datos causarán estragos en los métodos estadísticos que se aplicarán en él, hacer tal limpieza puede ser muy beneficioso.

DaL
fuente