language agnostic - Algoritmo para encontrar artículos con texto similar
language-agnostic string (14)
Tengo muchos artículos en una base de datos (con título, texto), estoy buscando un algoritmo para encontrar la X artículos más similares, algo así como "Preguntas relacionadas" de Stack Overflow cuando haces una pregunta.
Intenté buscar en Google esto, pero solo encontré páginas sobre otros problemas de "texto similar", algo así como comparar cada artículo con todos los demás y almacenar una similitud en alguna parte. SO lo hace en "tiempo real" en el texto que acabo de escribir.
¿Cómo?
Depende de tu definición de similar.
El algoritmo de edición-distancia es el algoritmo estándar para las sugerencias del diccionario (idioma latino), y puede trabajar en textos completos. Dos textos son similares si tienen básicamente las mismas palabras (letras eh) en el mismo orden. Así que las siguientes dos reseñas de libros serían bastante similares:
1) "Este es un gran libro"
2) "Estos no son grandes libros"
(El número de letras para eliminar, insertar, eliminar o modificar para convertir (2) en (1) se denomina ''distancia de edición'').
Para implementar esto, deseará visitar cada revisión mediante programación. Esto tal vez no sea tan costoso como suena, y si es demasiado costoso, podría hacer las comparaciones como una tarea en segundo plano y almacenar la n-la más similar en un campo de base de datos en sí.
Otro enfoque es entender algo de la estructura de los idiomas (latinos). Si tira palabras cortas (no capituladas o citadas) y asigna pesos a palabras (o prefijos) que son comunes o únicas, puede hacer una comparación Bayesianesque. Las dos siguientes reseñas de libros podrían ser simuladas y encontradas de manera similar:
3) "La revolución francesa fue bla, bla, guerra y paz, bla, bla, Francia". -> Francia / Francés (2) Revolución (1) Guerra (1) Paz (1) (tenga en cuenta que se ha utilizado un diccionario para combinar Francia y Francia)
4) "Este libro es blah blah, una revolución en la cocina francesa". -> Francia (1) Revolución (1)
Para implementar esto, debería identificar las ''palabras clave'' en una revisión cuando se creó / actualizó, y para encontrar revisiones similares use estas palabras clave en la cláusula where de una consulta (idealmente búsqueda de "texto completo" si la base de datos lo admite ), con tal vez un procesamiento posterior del conjunto de resultados para calificar a los candidatos encontrados.
Los libros también tienen categorías: ¿hay thrillers en Francia similares a los estudios históricos de Francia, y así sucesivamente? Los metadatos más allá del título y el texto pueden ser útiles para mantener los resultados relevantes.
El tutorial en este enlace parece que puede ser lo que necesita. Es fácil de seguir y funciona muy bien.
Su algoritmo recompensa las subcadenas comunes y un ordenamiento común de esas subcadenas, por lo que debería seleccionar títulos similares bastante bien.
Puede usar el índice de texto completo de SQL Server para obtener la comparación inteligente, creo que SO está utilizando una llamada ajax, que hace una consulta para devolver las preguntas similares.
¿Qué tecnologías estás usando?
SO hace la comparación solo en el título, no en el cuerpo del texto de la pregunta, por lo tanto solo en cadenas bastante cortas.
Puede usar su algoritmo (sin tener idea de cómo se ve) en el título del artículo y las palabras clave. Si tiene más tiempo de CPU para grabar, también en los resúmenes de sus artículos.
Secundando la sugerencia de Lucene para texto completo, pero tenga en cuenta que java no es un requisito; un puerto .NET está disponible . También vea la página principal de Lucene para enlaces a otros proyectos, incluido Lucy, un puerto C.
Si estás buscando palabras que hieren de la misma manera, puedes convertir a soundex y las palabras soundex para que coincidan ... funcionó para mí
Sugiero que indiques tus artículos usando Apache Lucene , una biblioteca de motor de búsqueda de texto de alto rendimiento y con todas las funciones escritas enteramente en Java. Es una tecnología adecuada para casi cualquier aplicación que requiera búsqueda de texto completo, especialmente multiplataforma . Una vez indexado, puede encontrar fácilmente artículos relacionados.
Tal vez lo que estás buscando es algo que parafrasea . Solo tengo un conocimiento superficial de esto, pero parafrasear es un concepto de procesamiento del lenguaje natural para determinar si dos pasajes de texto realmente significan lo mismo, aunque pueden usar palabras completamente diferentes.
Lamentablemente, no conozco ninguna herramienta que te permita hacer esto (aunque me gustaría encontrar uno)
Un algoritmo común utilizado es el mapa de autoorganización . Es un tipo de red neuronal que categorizará automáticamente sus artículos. Luego, simplemente puede encontrar la ubicación de un artículo actual en el mapa y todos los artículos cercanos están relacionados. La parte importante del algoritmo es cómo vectorizaría la cuantización de su entrada . Hay varias maneras de hacerlo con el texto. Puede copiar su documento / título, puede contar palabras y usarlo como un vector n dimensional, etc. Espero que ayude, aunque es posible que haya abierto una caja de Pandora para usted de un viaje interminable en IA.
La distancia de edición no es un candidato probable, ya que dependería de la ortografía / orden de palabras, y mucho más computacionalmente costosa de lo que Will te hace creer, teniendo en cuenta el tamaño y el número de documentos que realmente estarías interesado en buscar.
Algo como Lucene es el camino a seguir. Usted indexa todos sus documentos y luego, cuando desea encontrar documentos similares a un documento dado, convierte su documento dado en una consulta y busca en el índice. Internamente, Lucene utilizará tf-idf y un índice invertido para que todo el proceso tome una cantidad de tiempo proporcional a la cantidad de documentos que posiblemente coincidan, no la cantidad total de documentos en la colección.
Intenté algún método, pero ninguno funciona bien. Uno puede obtener un resultado relativamente saturado como este: Primero: obtenga un código de Google SimHash para cada párrafo de todo el texto y guárdelo en el databse. Segundo: índice para el código SimHash. Tercero: procese su texto para compararlo como se indica arriba, obtenga un código SimHash y busque todo el texto por el índice SimHash, que aparte de una distancia de Hamming como 5-10. Luego compara la similidad con el término vector. Esto puede funcionar para big data.
La forma más simple y rápida de comparar la similitud entre resúmenes es probablemente mediante la utilización del concepto de conjunto. Primero convierta los textos abstractos en un conjunto de palabras. Luego, comprueba cuánto se superpone cada conjunto. La función de conjunto de Python es muy útil para realizar esta tarea. Le sorprendería ver qué tan bien se compara este método con las opciones de "documentos similares / relacionados" que ofrece GScholar, ADS, WOS o Scopus.
puedes usar 1) Minhash / LSH https://en.wikipedia.org/wiki/MinHash
(también vea: http://infolab.stanford.edu/~ullman/mmds/book.pdf )
o
2) filtrado colaborativo: https://en.wikipedia.org/wiki/Collaborative_filtering
El enlace en la respuesta de @ alex77 apunta al Coeficiente Sorensen-Dice que fue descubierto independientemente por el autor de ese artículo: el artículo está muy bien escrito y vale la pena leerlo.
Terminé usando este coeficiente para mis propias necesidades. Sin embargo, el coeficiente original puede arrojar resultados erróneos cuando se trata de
- tres pares de palabras de letras que contienen una falta de ortografía, por ejemplo
[and,amd]y - tres pares de palabras de letras que son anagramas, por ejemplo
[and,dan]
En el primer caso, Dice informa erróneamente un coeficiente de cero mientras que en el segundo caso el coeficiente aparece como 0.5, que es engañosamente alto.
Se ha sugerido una mejora que en esencia consiste en tomar el primer y el último carácter de la palabra y crear un bigram adicional.
En mi opinión, la mejora solo es realmente necesaria para palabras de 3 letras; en palabras más largas, los otros bigrams tienen un efecto de memoria intermedia que cubre el problema. Mi código que implementa esta mejora se proporciona a continuación.
function wordPairCount(word)
{
var i,rslt = [],len = word.length - 1;
for(i=0;i < len;i++) rslt.push(word.substr(i,2));
if (2 == len) rslt.push(word[0] + word[len]);
return rslt;
}
function pairCount(arr)
{
var i,rslt = [];
arr = arr.toLowerCase().split('' '');
for(i=0;i < arr.length;i++) rslt = rslt.concat(wordPairCount(arr[i]));
return rslt;
}
function commonCount(a,b)
{
var t;
if (b.length > a.length) t = b, b = a, a = t;
t = a.filter(function (e){return b.indexOf(e) > -1;});
return t.length;
}
function myDice(a,b)
{
var bigrams = [],
aPairs = pairCount(a),
bPairs = pairCount(b);
debugger;
var isct = commonCount(aPairs,bPairs);
return 2*commonCount(aPairs,bPairs)/(aPairs.length + bPairs.length);
}
$(''#rslt1'').text(myDice(''WEB Applications'',''PHP Web Application''));
$(''#rslt2'').text(myDice(''And'',''Dan''));
$(''#rslt3'').text(myDice(''and'',''aMd''));
$(''#rslt4'').text(myDice(''abracadabra'',''abracabadra''));
*{font-family:arial;}
table
{
width:80%;
margin:auto;
border:1px solid silver;
}
thead > tr > td
{
font-weight:bold;
text-align:center;
background-color:aqua;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.0.0/jquery.min.js"></script>
<table>
<thead>
<tr>
<td>Phrase 1</td>
<td>Phrase 2</td>
<td>Dice</td>
</tr>
<thead>
<tbody>
<tr>
<td>WEB Applications</td>
<td>PHP Web Application</td>
<td id=''rslt1''></td>
</tr>
<tr>
<td>And</td>
<td>Dan</td>
<td id=''rslt2''></td>
</tr>
<tr>
<td>and</td>
<td>aMd</td>
<td id=''rslt3''></td>
</tr>
<tr>
<td>abracadabra</td>
<td>abracabadra</td>
<td id=''rslt4''></td>
</tr>
</tbody>
</table>
Tenga en cuenta la falta de ortografía deliberada en el último ejemplo: abraca dabra vs abraca badra . Aunque no se aplica una corrección de bigram extra, el coeficiente informado es 0,9. Con la corrección habría sido 0.91.
Con suerte, esto ayudará a otros que se encuentren con este hilo.