Déterminer à quel point une chaîne donnée est similaire à une collection de chaînes

10

Je ne sais pas si cette question appartient ici et je m'en excuse sinon. Ce que je cherche à faire est de développer une manière programmatique dans laquelle je peux déterminer de manière probabiliste si une chaîne donnée "appartient" dans un sac de chaînes. Par exemple, si j'ai un sac de 10 000 noms de villes américaines et que j'ai ensuite la chaîne «Philadelphie», je voudrais une mesure quantitative de la probabilité que «Philadelphie» soit un nom de ville américain basé sur les noms de villes américaines que je connais déjà. Bien que je sache que je ne serai pas en mesure de séparer les vrais noms de ville des faux noms de ville dans ce contexte, je m'attendrais au moins à avoir des chaînes telles que "123.75" et "Le renard roux rapide a sauté par-dessus les chiens paresseux". un certain seuil.

Pour commencer, j'ai regardé Levenshtein Distance et fouillé un peu sur la façon dont cela a été appliqué à des problèmes au moins quelque peu similaires à celui que j'essaie de résoudre. Une application intéressante que j'ai trouvée était la détection du plagiat, avec un article décrivant comment la distance de Levenshtein a été utilisée avec un algorithme de Smith-Waterman modifié pour noter les articles en fonction de leur probabilité d'être une version plagarisée d'un papier de base donné. Ma question est de savoir si quelqu'un pourrait m'orienter dans la bonne direction avec d'autres algorithmes ou méthodologies établis qui pourraient m'aider. J'ai l'impression que cela peut être un problème que quelqu'un dans le passé a essayé de résoudre, mais jusqu'à présent, mon Google-fu m'a échoué.

Andrew
la source
Si vous disposez d'exemples positifs et négatifs, vous pouvez essayer de former un classificateur. Pour les fonctionnalités, pour commencer, j'essaierais de tirer quelques statistiques simples telles que celles suggérées par Yuval Filmus.
Nick
Notez cette question connexe .
Raphael
Les noms de villes semblent être un mauvais exemple; ils sont partout, surtout aux États-Unis. Ici, la recherche de table semble être le moyen le plus efficace. Votre problème est-il plus général?
Raphael

Réponses:

5

nnnn=2

Compte tenu de l'heuristique, vous pouvez utiliser la probabilité d'obtenir un score qui serait (espérons-le) plus élevé pour vos données d'échantillonnage que pour d'autres textes. Afin de déterminer un seuil raisonnable, vous pouvez effectuer une validation croisée. Choisissez un ensemble d'exemples de phrases qui ne sont pas des noms de ville. Divisez les noms des villes en deux parties, une grande (disons 80%) et une petite (disons 20%). Entraînez votre modèle sur la grande partie (c'est-à-dire collectez des statistiques sur la grande partie), puis évaluez votre modèle sur la petite partie et sur l'échantillon de mauvaises phrases. Déterminez s'il existe un seuil raisonnable qui dépasse la plupart des noms de ville, mais seulement une petite quantité de mauvaises phrases.

Yuval Filmus
la source
Merci. J'avais commencé à chercher dans le n-gramme mais je ne savais pas si j'étais totalement hors de la base donc je suis content que vous l'ayez mentionné. La longueur des mots semble également intéressante et quelque chose à laquelle je n'avais pas pensé.
Andrew
Vous voudrez peut-être ajouter la fréquence des caractères à cela. En particulier, cela devrait éliminer tous les trucs nombreux. Un avantage est que ces fréquences sont des vecteurs de nombres qui peuvent être entraînés / reconnus dans un certain nombre de modèles statistiques.
Raphael
1
1n+1n