Introduction détaillée à l'exemple de code de notation de pertinence pour la recherche en texte intégral JavaScript-js tutoriel-php.cn

La recherche en texte intégral, contrairement à la plupart des autres problèmes dans le domaine de l'apprentissage automatique, est un problème que les programmeurs Web rencontrent souvent dans leur travail quotidien. Le client peut vous demander de fournir un champ de recherche quelque part, puis vous écrirez une instruction SQL telle que WHERE title LIKE %:query% pour implémenter la fonction de recherche. Au début, cela ne posait aucun problème, jusqu'au jour où le client est venu vous voir et vous a dit : "Il y a eu une erreur dans la recherche !"

Bien sûr, il n'y a pas eu d'"erreur" dans la recherche, c'était simplement que les résultats de la recherche ne correspondaient pas à ce que souhaitait le client. L'utilisateur moyen ne sait pas comment effectuer une correspondance exacte, les résultats de recherche obtenus sont donc de mauvaise qualité. Pour résoudre le problème, vous décidez d'utiliser la recherche en texte intégral. Après une période d'apprentissage ennuyeux, vous avez activé le FULLTEXT index de MySQL et utilisé une syntaxe de requête plus avancée, telle que "MATCH() ... AGAINST( )".

Bon, le problème est résolu et les fleurs sont terminées ! Cela ne pose aucun problème lorsque la taille de la base de données est petite.

Mais lorsque vous avez de plus en plus de données, vous constaterez que votre base de données devient de plus en plus lente. MySQL n'est pas unoutil de recherche en texte intégral très facile à utiliser. Vous décidez donc d'utiliser ElasticSearch, de refactoriser votre code et de déployer un cluster de recherche en texte intégral optimisé par Lucene . Vous constaterez que cela fonctionne très bien, rapidement et avec précision.

À ce stade, vous ne pouvez pas vous empêcher de vous demander : pourquoi Lucene est-elle si géniale ?

Cet article (présente principalement TF-IDF, Ok

api BM-25 et les scores de pertinence ordinaires) et l'article suivant (présente principalement l'indexation) vous parleront de la recherche en texte intégral Le concept de base derrière tout cela.

Pertinence

Pour chaque requête de recherche, il est facile de définir un « score de pertinence » pour chaque document. Lorsque les utilisateurs effectuent une recherche, nous pouvons utiliser les scores de pertinence pour trier au lieu de l'heure d'apparition du document. De cette façon, le document le plus pertinent sera classé en premier, quelle que soit la date de sa création (bien sûr, cela est parfois également lié à l'heure de création du document).

Il existe de très nombreuses façons de calculer la corrélation entre du texte, mais nous commencerons par la méthode la plus simple, basée sur les statistiques. Cette méthode ne nécessite pas de compréhension de la langue elle-même, mais détermine un « score de pertinence » en comptant l'utilisation des mots, la correspondance et la pondération en fonction de la prévalence des mots uniques dans le document.

Cet algorithme ne se soucie pas de savoir si le mot est un nom ou un verbe, ni de la signification du mot. La seule chose qui l'intéresse, c'est de savoir quels mots sont courants et lesquels sont rares. Si une requête de recherche contient à la fois des mots courants et des mots rares, vous feriez mieux d'attribuer un score plus élevé au document contenant les mots rares tout en réduisant le poids des mots courants.

Cet algorithme s'appelle Okapi BM25. Il contient deux concepts de base : la fréquence des mots (

fréquence du terme), abrégée en fréquence du terme (« TF ») , et la fréquence inverse du document (inverse fréquence du document), abrégée en (« IDF ») . Leur regroupement s'appelle « TF-IDF », qui est une mesure statistique utilisée pour indiquer l'importance d'un terme dans un document.

TF-IDF

Term Frequency (

Term Frequency), appelé « TF », est une métrique très simple : le nombre de fois qu'un mot spécifique apparaît dans un document. Vous pouvez diviser cette valeur par le nombre total de mots du document pour obtenir un score. Par exemple, s’il y a 100 mots dans le document et que le mot « le » apparaît 8 fois, alors le TF du « le » est de 8 ou 8/100 ou 8 % (selon la façon dont vous souhaitez l’exprimer).

Inverse Document Frequency (

Inverse Document Frequency), appelée « IDF », est un peu plus compliquée : plus un mot est rare, plus cette valeur est élevée. Il s'obtient en divisant le nombre total de documents par le nombre de documents contenant le terme, puis en prenant le logarithme du quotient. Plus le mot est rare, plus le « Tsahal » qu’il produira sera élevé. Si vous multipliez ces deux nombres ensemble (TF*IDF), vous obtiendrez le poids d'un mot dans le document. Le « poids » est défini comme : quelle est la rareté du mot et à quelle fréquence apparaît-il dans le document ?

Vous pouvez utiliser ce concept pour les requêtes de recherche sur des documents. Pour chaque mot-clé de la requête, calculez leur score TF-IDF et additionnez-les. Le document ayant le score le plus élevé est celui qui correspond le mieux à l'instruction de requête.

Comme c'est cool !

Okapi BM25

L'algorithme ci-dessus est un algorithme utilisable, mais il n'est pas parfait. Il donne un algorithme de score de corrélation basé sur des statistiques, que nous pouvons encore améliorer.

Okapi BM25 est considéré jusqu'à présent comme l'un des algorithmes de classement les plus avancés (il s'appelle donc ElasticSearch). Okapi BM25 ajoute deux paramètres réglables, k1 et b, basés sur TF-IDF, qui représentent respectivement le « terme saturation de fréquence » et la « spécification de longueur de champ ». Qu'est-ce que c'est que ça ?

Pour comprendre intuitivement la « saturation de la fréquence des mots », imaginez deux articles de longueur similaire traitant du baseball. Supposons également que tous les documents (sauf ces deux-là) n’ont pas beaucoup de contenu lié au baseball, donc le mot « baseball » aura un IDF élevé – c’est extrêmement rare et important. Les deux articles discutent du baseball et y consacrent tous deux une place considérable, mais l’un utilise le mot « baseball » plus que l’autre. Alors dans ce cas, un article a-t-il vraiment un score très différent d’un autre article ? Puisque les deux documents parlent du baseball en général, peu importe que le mot « baseball » apparaisse 40 ou 80 fois. En fait, 30 fois devrait être le plafond !

Il s'agit de la "saturation de fréquence des mots". L'algorithme natif TF-IDF n'a aucune notion de saturation, donc un document avec "baseball" apparaissant 80 fois a un score deux fois plus élevé qu'un document qui apparaît 40 fois. Parfois, à ce moment-là, ce que nous voulons, mais parfois nous ne le voulons pas. De plus, l'Okapi BM25 dispose également d'un paramètre k1, qui sert à ajuster le taux de changement de saturation. La valeur du paramètre k1 est généralement comprise entre 1,2 et 2,0. . Plus la valeur est faible, plus le processus de saturation est rapide (ce qui signifie que les deux documents ci-dessus ont le même score, car ils contiennent tous deux un grand nombre du mot « baseball »)

Réduction de la longueur du champ ( Field-length). la normalisation réduit la longueur d'un document à la longueur moyenne de tous les documents. Ceci est utile pour les collections à champ unique (comme la nôtre) pour unifier les documents de longueurs différentes selon les mêmes critères de comparaison. Cela est plus significatif pour les collections à deux champs ( tels que "titre" et "corps"). Il peut également unifier les champs de titre et de corps selon la même condition de comparaison. La réduction de la longueur du champ est représentée par b et sa valeur est 0. Entre Savoir ce qu'est chaque terme de la formule. , c'est définitivement facile à comprendre, nous ne mentionnerons donc pas la formule et passerons directement au code :

Nous définissons une méthode simple

Statique

Tokenize(), le but. consiste à analyser la

chaîne

dans le

BM25.Tokenize = function(text) {
    text = text
        .toLowerCase()
        .replace(/\W/g, &#39; &#39;)
        .replace(/\s+/g, &#39; &#39;)
        .trim()
        .split(&#39; &#39;)
        .map(function(a) { return stemmer(a); });

    // Filter out stopStems
    var out = [];
    for (var i = 0, len = text.length; i < len; i++) {
        if (stopStems.indexOf(text[i]) === -1) {
            out.push(text[i]);
        }
    }

    return out;
};

Copier après la connexion

tableau

de jetons De cette façon, nous réduisons tous les jetons (pour réduire l'entropie). L'algorithme de Porter Stemmer est utilisé pour réduire la quantité d'entropie et améliorer. le degré de correspondance ("marche" et "marche" sont les mêmes). Et nous filtrons également les mots vides (mots très courants) pour réduire davantage la valeur d'entropie. Veuillez me supporter si j'explique trop cette section avant d'entrer dans le vif du sujet. C'est là que la méthode addDocument() opère sa magie. Deux structures de données similaires : this.documents et this.terms this.documents est une base de données qui enregistre tous les documents originaux. le texte du document, les informations sur la longueur du document et une liste, la liste stocke le nombre et la fréquence de tous les mots et mots du document, en utilisant cette structure de données, nous pouvons facilement et rapidement (oui, très rapidement, seulement exiger. une complexité temporelle de O(1)). Nous utilisons également une autre structure de données, this.terms. Il représente tous les mots du corpus. Grâce à cette structure de données, nous pouvons répondre aux questions suivantes en temps O(1) : Dans combien de documents le mot « marcher » apparaît-il ? Quelle est leur identité ? Enfin, nous enregistrons la longueur de chaque document et enregistrons la longueur moyenne des documents sur l'ensemble du corpus.

BM25.prototype.addDocument = function(doc) {
    if (typeof doc.id === &#39;undefined&#39;) { throw new Error(1000, &#39;ID is a required property of documents.&#39;); };
    if (typeof doc.body === &#39;undefined&#39;) { throw new Error(1001, &#39;Body is a required property of documents.&#39;); };

    // Raw tokenized list of words
    var tokens = BM25.Tokenize(doc.body);

    // Will hold unique terms and their counts and frequencies
    var _terms = {};

    // docObj will eventually be added to the documents database
    var docObj = {id: doc.id, tokens: tokens, body: doc.body};

    // Count number of terms
    docObj.termCount = tokens.length;

    // Increment totalDocuments
    this.totalDocuments++;

    // Readjust averageDocumentLength
    this.totalDocumentTermLength += docObj.termCount;
    this.averageDocumentLength = this.totalDocumentTermLength / this.totalDocuments;

    // Calculate term frequency
    // First get terms count
    for (var i = 0, len = tokens.length; i < len; i++) {
        var term = tokens[i];
        if (!_terms[term]) { 
            _terms[term] = {
                count: 0,
                freq: 0
            }; 
        };
        _terms[term].count++;
    }

    // Then re-loop to calculate term frequency.
    // We&#39;ll also update inverse document frequencies here.
    var keys = Object.keys(_terms);
    for (var i = 0, len = keys.length; i < len; i++) {
        var term = keys[i];
        // Term Frequency for this document.
        _terms[term].freq = _terms[term].count / docObj.termCount;

        // Inverse Document Frequency initialization
        if (!this.terms[term]) {
            this.terms[term] = {
                n: 0, // Number of docs this term appears in, uniquely
                idf: 0
            };
        }

        this.terms[term].n++;
    };

    // Calculate inverse document frequencies
    // This is SLOWish so if you want to index a big batch of documents,
    // comment this out and run it once at the end of your addDocuments run
    // If you&#39;re only indexing a document or two at a time you can leave this in.
    // this.updateIdf();

    // Add docObj to docs db
    docObj.terms = _terms;
    this.documents[docObj.id] = docObj;
};

Copier après la connexion

Notez que dans le code ci-dessus, idf est initialisé à 0 et la méthode updateidf() est

commentée

. En effet, cette méthode s'exécute très lentement et ne doit être exécutée qu'une seule fois, après l'indexation. Puisque l’exécuter une fois peut répondre aux besoins, il n’est pas nécessaire de l’exécuter 5 000 fois. Le commenter d’abord et l’exécuter après un grand nombre d’opérations d’indexation peut faire gagner beaucoup de temps. Voici le code de cette

fonction

BM25.prototype.updateIdf = function() {
    var keys = Object.keys(this.terms);
    for (var i = 0, len = keys.length; i < len; i++) {
        var term = keys[i];
        var num = (this.totalDocuments - this.terms[term].n + 0.5);
        var denom = (this.terms[term].n + 0.5);
        this.terms[term].idf = Math.max(Math.log10(num / denom), 0.01);
    }
};

Copier après la connexion

这是一个非常简单的函数，但是由于它需要遍历整个语料库中的所有词语，并更新所有词语的值，这就导致它工作的就有点慢。这个方法的实现采用了逆向文档频率 (inverse document frequency) 的标准公式（你可以在 Wikipedia 上找到这个公式）— 由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到。我做了一些修改，让返回值一直大于0。

BM25.prototype.search = function(query) {

    var queryTerms = BM25.Tokenize(query);
    var results = [];

    // Look at each document in turn. There are better ways to do this with inverted indices.
    var keys = Object.keys(this.documents);
    for (var j = 0, nDocs = keys.length; j < nDocs; j++) {
        var id = keys[j];
        // The relevance score for a document is the sum of a tf-idf-like
        // calculation for each query term.
        this.documents[id]._score = 0;

        // Calculate the score for each query term
        for (var i = 0, len = queryTerms.length; i < len; i++) {
            var queryTerm = queryTerms[i];

            // We&#39;ve never seen this term before so IDF will be 0.
            // Means we can skip the whole term, it adds nothing to the score
            // and isn&#39;t in any document.
            if (typeof this.terms[queryTerm] === &#39;undefined&#39;) {
                continue;
            }

            // This term isn&#39;t in the document, so the TF portion is 0 and this
            // term contributes nothing to the search score.
            if (typeof this.documents[id].terms[queryTerm] === &#39;undefined&#39;) {
                continue;
            }

            // The term is in the document, let&#39;s go.
            // The whole term is :
            // IDF * (TF * (k1 + 1)) / (TF + k1 * (1 - b + b * docLength / avgDocLength))

            // IDF is pre-calculated for the whole docset.
            var idf = this.terms[queryTerm].idf;
            // Numerator of the TF portion.
            var num = this.documents[id].terms[queryTerm].count * (this.k1 + 1);
            // Denomerator of the TF portion.
            var denom = this.documents[id].terms[queryTerm].count 
                + (this.k1 * (1 - this.b + (this.b * this.documents[id].termCount / this.averageDocumentLength)));

            // Add this query term to the score
            this.documents[id]._score += idf * num / denom;
        }

        if (!isNaN(this.documents[id]._score) && this.documents[id]._score > 0) {
            results.push(this.documents[id]);
        }
    }

    results.sort(function(a, b) { return b._score - a._score; });
    return results.slice(0, 10);
};

Copier après la connexion

最后，search() 方法遍历所有的文档，并给出每个文档的 BM25 分数，然后按照由大到小的顺序进行排序。当然了，在搜索过程中遍历语料库中的每个文档实是不明智。这个问题在 Part Two （反向索引和性能）中得到解决。

上面的代码已经做了很好的注释，其要点如下：为每个文档和每个词语计算 BM25 分数。词语的 idf 分数已经预先计算好了，使用的时候只需要查询即可。词语频率作为文档属性的一部分也已经预先计算好了。之后只需要简单的四则运算即可。最后给每个文档增加一个临时变量 _score，然后根据 score 做降序排列并返回前 10 个结果。