Algorithme pour trouver des articles avec un texte similaire

StackOverflow https://stackoverflow.com/questions/246961

Question

J'ai beaucoup d'articles dans une base de données (avec titre, texte), je cherche un algorithme pour trouver les X articles les plus similaires, quelque chose comme "Questions connexes" de Stack Overflow. quand vous posez une question.

J'ai essayé de rechercher Google pour cela, mais je n'ai trouvé que des pages sur d'autres "textes similaires". questions, quelque chose comme comparer chaque article avec tous les autres et stocker une similitude quelque part. SO le fait en " temps réel " sur le texte que je viens de taper.

Comment?

Était-ce utile?

La solution

La

modifier la distance n'est pas un candidat probable, car ce serait l'orthographe / l'ordre des mots. dépendantes et beaucoup plus onéreuses en calculs que ne le laisse supposer Will, compte tenu de la taille et du nombre des documents sur lesquels vous voudriez réellement rechercher.

Quelque chose comme Lucene est la voie à suivre. Vous indexez tous vos documents, puis lorsque vous voulez trouver des documents similaires à un document donné, vous transformez votre document donné en requête et recherchez l'index. En interne, Lucene utilisera tf-idf et un index inversé pour que l'ensemble du processus prenne une durée proportionnelle au nombre de documents pouvant correspondre, et non au nombre total de documents dans la collection.

Autres conseils

Cela dépend de votre définition de similiar.

L'algorithme edit-distance est l'algorithme standard pour les suggestions de dictionnaire (en latin) et peut travailler sur des textes entiers. Deux textes sont similaires s'ils ont fondamentalement les mêmes mots (lettres eh) dans le même ordre. Ainsi, les deux critiques de livres suivantes seraient assez similaires:

1) "C’est un excellent livre"

2) "Ce ne sont pas de bons livres"

(Le nombre de lettres à supprimer, insérer, supprimer ou modifier pour transformer (2) en (1) est appelé "distance de modification".)

Pour implémenter cela, vous voudriez visiter chaque revue par programmation. Cela n’est peut-être pas aussi coûteux que cela en a l'air, et si c’est trop coûteux, vous pouvez effectuer les comparaisons en tâche de fond et stocker le n-plus-similaire dans un champ de base de données lui-même.

Une autre approche consiste à comprendre quelque chose de la structure des langues (latines). Si vous supprimez des mots courts (non capitalisés ou cités) et attribuez une pondération aux mots (ou préfixes) communs ou uniques, vous pouvez effectuer une comparaison Bayesianesque. Les deux critiques de livre suivantes peuvent être simulées et jugées similaires:

3) "La révolution française a été bla bla guerre et paix bla bla France". - > France / Français (2) Révolution (1) Guerre (1) Paix (1) (un dictionnaire a été utilisé pour combiner la France et le français)

4) "Ce livre est bla bla une révolution dans la cuisine française." - > France (1) Révolution (1)

Pour implémenter cela, vous voudrez identifier les "mots-clés" dans une critique lors de sa création / mise à jour, et pour rechercher des critiques similaires, utilisez ces mots-clés dans la clause where d'une requête (idéalement, "texte intégral" recherchant si la base de données le supporte), avec éventuellement un post-traitement de l’ensemble de résultats pour la notation des candidats trouvés.

Les livres ont aussi des catégories - les thrillers se déroulent-ils en France de la même manière que les études historiques françaises, et ainsi de suite? Des méta-données autres que le titre et le texte pourraient être utiles pour que les résultats restent pertinents.

Le tutoriel de ce lien ressemble à ce que vous recherchez. Il est facile à suivre et fonctionne très bien.

Son algorithme récompense à la fois les sous-chaînes communes et un ordre commun de ces sous-chaînes et devrait donc choisir assez bien des titres similaires.

Je suggère d'indexer vos articles à l'aide de Apache Lucene , une Performance, une bibliothèque de moteur de recherche de texte complet entièrement écrite en Java. Cette technologie convient à presque toutes les applications nécessitant une recherche en texte intégral, en particulier multiplate-forme . Une fois indexé, vous pourrez facilement trouver des articles connexes.

Un des algorithmes couramment utilisés est la Carte auto-organisée . C'est un type de réseau de neurones qui catégorisera automatiquement vos articles. Ensuite, vous pouvez simplement trouver l'emplacement d'un article actuel sur la carte et tous les articles proches de celle-ci sont liés. La partie importante de l’algorithme consiste à quantifier les entrées vectorielles . Il y a plusieurs façons de faire avec du texte. Vous pouvez hacher votre document / titre, vous pouvez compter les mots et l’utiliser comme un vecteur n dimensionnel, etc. J'espère que cela m'aidera, même si j’ai peut-être ouvert une boîte de Pandore d’un parcours sans fin dans l’IA.

SO fait la comparaison uniquement sur le titre, pas sur le corps du texte de la question, donc uniquement sur des chaînes plutôt courtes.

Vous pouvez utiliser leur algorithme (aucune idée de ce à quoi il ressemble) sur le titre de l'article et les mots-clés. Si vous avez plus de temps CPU à graver, également sur les résumés de vos articles.

Souscrivant à la proposition de Lucene concernant le texte intégral, notez que Java n’est pas une obligation; un port .NET est disponible . Consultez également la page principale de Lucene pour des liens vers d'autres projets, notamment Lucy, un port C .

Peut-être que ce que vous cherchez, c’est paraphrasé . Je n'ai qu'une connaissance sommaire de cela, mais la paraphrase est un concept du traitement du langage naturel pour déterminer si deux des passages de texte signifient en fait la même chose - bien que l’on puisse utiliser des mots complètement différents.

Malheureusement, je ne connais aucun outil vous permettant de le faire (bien que cela m'intéresserait d'en trouver un)

Vous pouvez utiliser l'index de recherche en texte intégral SQL Server pour obtenir une comparaison intelligente. Je crois que SO utilise un appel ajax, qui effectue une requête pour renvoyer des questions similaires.

Quelles technologies utilisez-vous?

Si vous recherchez des mots semblables, vous pouvez convertir en soundex et les mots soundex qui correspondent ... qui ont fonctionné pour moi

J'ai essayé une méthode, mais aucune ne fonctionne bien. On peut obtenir un résultat relativement satisfait comme ceci:    Premièrement: obtenez un code Google SimHash pour chaque paragraphe de tout le texte et stockez-le dans la base de données.    Deuxièmement: Index pour le code SimHash.    Troisièmement: traitez votre texte à comparer comme ci-dessus, obtenez un code SimHash et recherchez tout le texte par index SimHash qui, mis à part, forment une distance de Hamming telle que 5-10. Comparez ensuite la similité avec le vecteur de terme.   Cela peut fonctionner pour le Big Data.

Le lien dans la réponse de @ alex77 pointe vers un Sorensen -Dice Coefficient , qui a été découvert indépendamment par l'auteur de cet article - l'article est très bien écrit et mérite d'être lu.

J'ai fini par utiliser ce coefficient pour mes propres besoins. Cependant, le coefficient initial peut donner des résultats erronés lorsqu’il s’agit de

  • Les paires de mots de trois lettres qui contiennent une faute d’orthographe, par exemple. [et, amd] et
  • paires de mots de trois lettres qui sont des anagrammes, par exemple. [et, dan]

Dans le premier cas, Dice indique à tort un coefficient nul alors que dans le second cas, le coefficient est égal à 0,5, ce qui est erronément élevé.

Une amélioration a été suggéré , ce qui consiste essentiellement à prendre le premier et le dernier caractère du mot et à créer un bigram supplémentaire.

À mon avis, l’amélioration n’est vraiment nécessaire que pour les mots de 3 lettres. En d'autres termes, les autres bigrammes ont un effet tampon qui masque le problème. Mon code qui implémente cette amélioration est donné ci-dessous. 

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>

Notez les fautes d'orthographe délibérées dans le dernier exemple: abraca dabra vs abraca badra . Même si aucune correction bigramme supplémentaire n'est appliquée, le coefficient indiqué est de 0,9. Avec la correction, cela aurait été de 0,91.

J'espère que cela aidera les autres qui rencontrent ce sujet.

À partir d'un exemple de texte, ce programme répertorie les textes de référentiel classés par similarité: implémentation simple du sac de mots en C ++ . L'algorithme est linéaire dans la longueur totale du texte exemple et du texte du référentiel. De plus, le programme est multi-threadé pour traiter les textes du référentiel en parallèle.

Voici l'algorithme principal: 

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);
}

Le moyen le plus simple et le plus rapide de comparer les similitudes entre les résumés consiste probablement à utiliser le concept d'ensemble. Convertissez d’abord des textes abstraits en un ensemble de mots. Ensuite, vérifiez combien chaque ensemble se chevauche. La fonction set de Python est très pratique pour cette tâche. Vous seriez surpris de voir à quel point cette méthode se compare bien à ces "papiers similaires / liés". les options proposées par GScholar, ADS, WOS ou Scopus.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top