Algoritmo para encontrar artículos con texto similar.

https://stackoverflow.com/questions/246961

05-07-2019
|

Pregunta

Tengo muchos artículos en una base de datos (con título, texto), estoy buscando un algoritmo para encontrar los X artículos más similares, algo así como las Preguntas relacionadas de Stack Overflow " cuando haces una pregunta

Traté de buscar en Google para esto, pero solo encontré páginas sobre otro " texto similar " problemas, algo así como comparar cada artículo con todos los demás y almacenar una similitud en algún lugar. SO hace esto en " tiempo real " en el texto que acabo de escribir.

¿Cómo?

Solución

Editar distancia no es un candidato probable, como lo sería la ortografía / el orden de las palabras Dependiente, y mucho más costoso computacionalmente de lo que Will lo está haciendo creer, considerando el tamaño y la cantidad de documentos que realmente le interesaría buscar.

Algo como Lucene es el camino a seguir. Indexa todos sus documentos, y cuando desea encontrar documentos similares a un documento dado, convierte su documento en una consulta y busca el índice. Internamente, Lucene utilizará tf-idf y un índice invertido para hacer que todo el proceso tome una cantidad de tiempo proporcional al número de documentos que puedan coincidir, no el número total de documentos en la colección.

Otros consejos

Depende de tu definición de similar.

El edit-distance es el algoritmo estándar para las sugerencias de diccionarios (en latín), y puede funcionar en textos completos. Dos textos son similares si tienen básicamente las mismas palabras (eh letras) 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, querrá visitar cada revisión mediante programación. Tal vez esto no sea tan costoso como parece, y si es demasiado costoso, podría hacer las comparaciones como una tarea en segundo plano y almacenar la n más similar en un campo de base de datos.

Otro enfoque es entender algo de la estructura de los idiomas (latinos). Si elimina las palabras cortas (sin mayúsculas ni las citadas) y asigna pesos a las palabras (o prefijos) que son comunes o únicas, puede hacer una comparación bayesiana. Las dos siguientes reseñas de libros podrían ser similares y resultaron ser similares:

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 francés)

4) " Este libro es bla, bla, una revolución en la cocina francesa. " - > Francia (1) Revolución (1)

Para implementar esto, desearía identificar las 'palabras clave' en una revisión cuando se creó / actualizar, y para encontrar revisiones similares, use estas palabras clave en la cláusula where de una consulta (idealmente 'texto completo' buscando si el la base de datos lo admite), quizás con un procesamiento posterior del conjunto de resultados para calificar a los candidatos encontrados.

Los libros también tienen categorías: ¿los thrillers ambientados en Francia son similares a los estudios históricos de Francia, etc.? 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 ser lo que necesita. Es fácil de seguir y funciona muy bien.

Su algoritmo recompensa tanto las subcadenas comunes como el ordenamiento común de esas subcadenas y, por lo tanto, debería seleccionar títulos similares bastante bien.

Le sugiero que indexe sus artículos usando Apache Lucene , un alto Biblioteca de motores de búsqueda de texto con todas las funciones escrita completamente en Java. Es una tecnología adecuada para casi cualquier aplicación que requiera búsqueda de texto completo, especialmente multiplataforma . Una vez indexado, puedes encontrar fácilmente artículos relacionados.

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 en la que se encuentra un artículo actual en el mapa y todos los artículos cercanos a él están relacionados. La parte importante del algoritmo es cómo vector cuantifique su aporte . Hay varias maneras de hacer con el texto. Puedes hacer un hash de tu documento / título, puedes contar las palabras y usarlas como vectores tridimensionales, etc. Espero que eso ayude, aunque es posible que te haya abierto una caja de Pandora de un viaje sin fin en AI.

SO hace la comparación solo en el título, no en el texto del cuerpo de la pregunta, así que solo en cadenas bastante cortas.

Puede usar su algoritmo (sin idea de cómo se ve) en el título del artículo y las palabras clave. Si tiene más tiempo de grabación de CPU, también en los resúmenes de sus artículos.

Secundando la sugerencia de Lucene para el texto completo, pero tenga en cuenta que Java no es un requisito; hay un puerto .NET disponible . También vea la página principal de Lucene para obtener enlaces a otros proyectos, incluyendo Lucy, un puerto C .

Tal vez lo que buscas es algo que haga parafraseando . Solo tengo un conocimiento superficial de esto, pero parafrasear es un concepto de proceso de lenguaje natural para determinar si hay dos los pasajes de texto en realidad significan lo mismo, aunque pueden usar palabras completamente diferentes.

Lamentablemente, no conozco ninguna herramienta que te permita hacer esto (aunque me gustaría encontrar una)

Puede usar el índice de texto completo de SQL Server para obtener la comparación inteligente, creo que SO está usando una llamada ajax, que realiza una consulta para responder preguntas similares.

¿Qué tecnologías estás usando?

Si está buscando palabras que tengan la misma herida, puede convertir a soundex y las palabras soundex que coinciden ... funcionaron para mí

Probé algún método pero ninguno funciona bien. Uno puede obtener un resultado relativamente satisfactorio como este: Primero: obtenga un código de Google SimHash para cada párrafo de todo el texto y guárdelo en la base de datos. Segundo: Índice para el código SimHash. Tercero: procese su texto para que se compare como se muestra arriba, obtenga un código de SimHash y busque todo el texto mediante el índice de SimHash que, aparte, forma una distancia de Hamming como 5-10. Luego compara la similidad con el término vector. Esto puede funcionar para big data.

puedes usar cualquiera 1) Minhash / LSH https://en.wikipedia.org/wiki/MinHash

(vea también: http://infolab.stanford.edu/~ullman/ mmds / book.pdf )

2) filtrado colaborativo: https://en.wikipedia.org/wiki/Collaborative_filtering

El enlace en la respuesta de @ alex77 apunta a un Sorensen -Dice Coefficient , que fue descubierto de forma independiente por el autor de ese artículo: el artículo está muy bien escrito y vale la pena leerlo.

He terminado usando este coeficiente para mis propias necesidades. Sin embargo, el coeficiente original puede producir resultados erróneos cuando se trata de

pares de palabras de tres letras que contienen un error ortográfico, por ejemplo, [and, amd] and
pares de palabras de tres letras que son anagramas, p. ej. [and,dan?

En el primer caso, Dice informa erróneamente un coeficiente de cero, mientras que en el segundo caso el coeficiente se eleva a 0,5, lo que es erróneamente alto.

Una mejora ha sido sugerido que en su esencia consiste en tomar el primer y último carácter de la palabra y crear un bigrama adicional.

En mi opinión, la mejora solo es realmente necesaria para las palabras de 3 letras: en palabras más largas, los otros bigramas tienen un efecto de amortiguamiento 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>

Note el error ortográfico deliberado en el último ejemplo: abraca dabra vs abraca badra . A pesar de que no se aplica ninguna corrección de bigrama adicional, el coeficiente reportado es de 0.9. Con la corrección habría sido 0.91.

Con suerte, esto ayudará a otros que se encuentren en este hilo.

Dado un texto de muestra, este programa enumera los textos del repositorio ordenados por similitud: implementación sencilla de una bolsa de palabras en C ++ . El algoritmo es lineal en la longitud total del texto de muestra y los textos del repositorio. Además, el programa es multihebra para procesar textos de repositorio en paralelo.

Aquí está el algoritmo central:

class Statistics {
  std::unordered_map<std::string, int64_t> _counts;
  int64_t _totWords;

  void process(std::string& token);
public:
  explicit Statistics(const std::string& text);

  double Dist(const Statistics& fellow) const;

  bool IsEmpty() const { return _totWords == 0; }
};

namespace {
  const std::string gPunctStr = ".,;:!?";
  const std::unordered_set<char> gPunctSet(gPunctStr.begin(), gPunctStr.end());
}

Statistics::Statistics(const std::string& text) {
  std::string lastToken;
  for (size_t i = 0; i < text.size(); i++) {
    int ch = static_cast<uint8_t>(text[i]);
    if (!isspace(ch)) {
      lastToken.push_back(tolower(ch));
      continue;
    }
    process(lastToken);
  }
  process(lastToken);
}

void Statistics::process(std::string& token) {
  do {
    if (token.size() == 0) {
      break;
    }
    if (gPunctSet.find(token.back()) != gPunctSet.end()) {
      token.pop_back();
    }
  } while (false);
  if (token.size() != 0) {
    auto it = _counts.find(token);
    if (it == _counts.end()) {
      _counts.emplace(token, 1);
    }
    else {
      it->second++;
    }
    _totWords++;
    token.clear();
  }
}

double Statistics::Dist(const Statistics& fellow) const {
  double sum = 0;
  for (const auto& wordInfo : _counts) {
    const std::string wordText = wordInfo.first;
    const double freq = double(wordInfo.second) / _totWords;
    auto it = fellow._counts.find(wordText);
    double fellowFreq;
    if (it == fellow._counts.end()) {
      fellowFreq = 0;
    }
    else {
      fellowFreq = double(it->second) / fellow._totWords;
    }
    const double d = freq - fellowFreq;
    sum += d * d;
  }
  return std::sqrt(sum);
}

La forma más sencilla y rápida de comparar la similitud entre los resúmenes es probablemente utilizando el concepto de conjunto. Primero convierte los textos abstractos en un conjunto de palabras. A continuación, compruebe cuánto se superpone cada conjunto. La característica de configuración de Python viene muy bien al realizar esta tarea. Le sorprendería ver qué tan bien se compara este método con esos " documentos similares / relacionados " opciones por ahí provistas por GScholar, ADS, WOS o Scopus.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow