JavaScript 全文検索の関連性スコアリングのサンプル コードの詳細な紹介

全文検索は、機械学習分野の他のほとんどの問題とは異なり、Web プログラマーが日常業務で頻繁に遭遇する問題です。顧客がどこかに検索ボックスを提供するように要求する場合は、WHERE title LIKE %:query% のような SQL ステートメントを記述して検索機能を実装します。最初は問題ありませんでしたが、ある日お客様から「検索にエラーがありました！」と連絡がありました

もちろん、検索には「エラー」はありませんでしたが、検索結果が顧客が望んでいたものではありませんでした。平均的なユーザーは完全一致の方法を知らないため、得られる検索結果の品質は低くなります。この問題を解決するために、全文検索を使用することにしました。退屈な学習期間の後、MySQL の FULLTEXT index を有効にし、「MATCH() … AGAINST()」などのより高度な query 構文を使用しました。

さて、問題は解決し、花は完成しました！データベースのサイズが小さい場合は問題ありません。

しかし、データが増えると、データベースの速度がどんどん遅くなることに気づくでしょう。 MySQL は、あまり使いやすい全文検索ツールではありません。そこで、ElasticSearch を使用し、コードをリファクタリングし、Lucene を利用した全文検索クラスターをデプロイすることにしました。非常にうまく、速く、正確に機能することがわかります。 この時点で、なぜ Lucene がこれほど素晴らしいのか、疑問に思わずにはいられません。

この記事 (主に TF-IDF、Ok

api

BM-25、および通常の関連性スコアを紹介) と次の記事 (主にインデックスの紹介) では、全文検索の背後にある 基本概念 について説明します。 関連性

検索クエリごとに、各ドキュメントの「関連性スコア」を簡単に定義します。ユーザーが検索するとき、ドキュメントの出現時間の代わりに関連性スコアを使用して並べ替えることができます。こうすることで、作成された時間がどれだけ前であっても、最も関連性の高いドキュメントが最初にランク付けされます (もちろん、ドキュメントの作成時間に関係する場合もあります)。

単語間の相関関係を計算する方法はたくさんありますが、最も単純な統計ベースの方法から始めます。この方法では、言語自体の理解は必要ありませんが、単語の使用数をカウントし、一致し、文書内の固有の単語の蔓延に基づいて重み付けすることによって「関連性スコア」を決定します。

このアルゴリズムは、単語が名詞であるか動詞であるかは気にせず、単語の意味も気にしません。重要なのは、どの単語が一般的で、どの単語が珍しいかということだけです。検索クエリに一般的な単語と珍しい単語の両方が含まれている場合は、一般的な単語の重みを下げながら、珍しい単語を含むドキュメントに高いスコアを与える方がよいでしょう。

このアルゴリズムはOkapi BM25と呼ばれます。これには 2 つの基本概念が含まれています。用語頻度 (

用語頻度)、略称用語頻度 ("TF")

と逆文書頻度 (逆文書頻度)、略称 ("IDF") です。これは「TF-IDF」と呼ばれるもので、文書内の用語の重要性を示すために使用される統計的尺度です。 TF-IDF用語頻度 (

用語頻度) は、

「TF」と呼ばれ、非常に単純な指標です。文書内に特定の単語が出現する回数です。この値を文書内の総単語数で割ると、スコアが得られます。たとえば、文書内に 100 単語があり、「the」という単語が 8 回出現する場合、「the」の TF は 8 または 8/100、つまり 8% になります (表現方法によって異なります)。

逆ドキュメント頻度 (

逆ドキュメント頻度) は、

"IDF" と呼ばれ、少し複雑です。単語がまれであればあるほど、この値は高くなります。これは、文書の総数をその用語を含む文書の数で割り、商の対数を取ることによって得られます。単語がレアであればあるほど、生成される「IDF」は高くなります。 これら 2 つの数値を掛け合わせると (TF*IDF)、文書内の単語の重みが得られます。 「重み」は次のように定義されます: その単語はどれくらいまれで、ドキュメントにどのくらいの頻度で出現しますか? この概念は、ドキュメントの検索クエリに使用できます。クエリ内の各キーワードについて、TF-IDF スコアを計算し、それらを加算します。最も高いスコアを持つドキュメントが、クエリ ステートメントに最もよく一致するドキュメントです。

なんてクールなんだろう！

Okapi BM25

上記のアルゴリズムは機能するアルゴリズムですが、完璧ではありません。これにより、統計に基づいた相関スコア アルゴリズムが得られ、さらに改善することができます。

Okapi BM25 は、これまでで最も高度なランキング アルゴリズムの 1 つと考えられています (そのため、ElasticSearch と呼ばれます)。 okapi BM25 は、TF-IDF に基づいて 2 つの調整可能なパラメータ k1 と b を追加します。これらはそれぞれ「ターム周波数飽和」と「フィールド長仕様」を表します。これはなに？

「単語頻度の飽和」を直観的に理解するには、野球について議論している同じような長さの 2 つの記事を想像してください。また、すべての文書 (これら 2 つを除く) には野球関連のコンテンツがあまり含まれていないと仮定します。そのため、「野球」という単語の IDF が高くなります。これは非常にまれで重要です。 どちらの記事も野球について論じており、かなりのスペースを割いていますが、一方の記事は他方の記事よりも「野球」という言葉を多く使用しています。この場合、ある記事のスコアは本当に別の記事と大きく異なるのでしょうか?どちらの文書も野球全般について論じているため、「野球」という単語が 40 回出現するか 80 回出現するかは問題ではありません。実際には 30 回が上限です。

これは「単語頻度の飽和」です。ネイティブの TF-IDF アルゴリズムには飽和の概念がないため、「baseball」が 80 回出現する文書は、40 回出現する文書の 2 倍のスコアを持ちます。場合によっては、これが私たちが行うものです。必要ですが、場合によってはこれを望まないこともあります。

さらに、Okapi BM25 には、彩度の変化率を調整するために使用される k1 パラメーターもあります。この値は通常、1.2 から 2.0 の間でより速くなります。プロセス (つまり、上の 2 つのドキュメントには「baseball」という単語が多く含まれているため、同じスコアになります)

フィールド長の正規化により、ドキュメントの長さがすべてのドキュメントの平均の長さに短縮されます。単一フィールドのコレクション (私たちのものなど) に便利です。異なる長さのドキュメントを同じ比較基準 (「タイトル」と「タイトル」など) に統合することはより意味があり、タイトルとタイトルを統合することもできます。フィールドの長さの削減は b で表され、その値は 0 から 1 の間であり、1 はすべての削減を意味し、0 は削減が実行されないことを意味します

アルゴリズム

アルゴリズムについては、Okapi BM25 Wikipedia で説明しています。式の各項が何であるかは理解できるはずです。では、式については触れずに、直接コードに進みましょう:

静的

メソッドを定義します。 Tokenize() の目的は、 文字列 を解析してトークンの 配列にすることです。(エントロピーを減らすために) Porter Stemmer アルゴリズムを実行して、エントロピーの量を減らし、マッチングを改善します。 (「歩く」と「歩く」の一致は同じです) また、エントロピーをさらに減らすために、ストップ ワード (非常に一般的な単語) も除外します。私が書いている概念について詳しく説明する前に、ご了承ください。このセクションで説明しすぎると

BM25.Tokenize = function(text) {
    text = text
        .toLowerCase()
        .replace(/\W/g, ' ')
        .replace(/\s+/g, ' ')
        .trim()
        .split(' ')
        .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;
};

ここで、addDocument() メソッドが驚くべき働きをします。基本的に、this.documents と this.terms という 2 つの類似したデータ構造を構築し、維持します。

this.documentsis は、すべてのドキュメントを保存するデータベースです。文書のすべての元のテキスト、文書の長さ情報、および文書内のすべての単語の数と頻度を保管するリストが保存されます。このデータ構造を使用すると、簡単かつ迅速に行うことができます。必要な時間計算量は O(1) だけです)。次の質問に答えてください: 文書 #3 には、「walk」という単語が何回現れますか?

別のデータ構造である this.terms も使用します。これはコーパス内のすべての単語を表します。このデータ構造を通じて、次の質問に O(1) 時間で答えることができます。「walk」という単語はいくつの文書に出現しますか?彼らのIDは何ですか?

最後に、各文書の長さを記録し、コーパス全体の文書の平均長を記録します。

上記のコードでは、idf は 0 に初期化されており、updateidf() メソッドには

注釈が付けられています

ことに注意してください。これは、このメソッドの実行が非常に遅く、インデックス作成後に 1 回だけ実行する必要があるためです。 1 回実行すればニーズを満たすことができるため、5,000 回実行する必要はありません。最初にコメントアウトし、大量のインデックス作成操作の後で実行すると、時間を大幅に節約できます。この

関数のコードは次のとおりです:

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

这是一个非常简单的函数，但是由于它需要遍历整个语料库中的所有词语，并更新所有词语的值，这就导致它工作的就有点慢。这个方法的实现采用了逆向文档频率 (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);
};

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

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

示例，源代码，注意事项和下一步计划

上面的示例有很多方法进行优化，我们将在 “全文搜索”的第二部分中介绍它们，欢迎继续收看。我希望我能在几个星期之后完成它。下面列了下次将要提到的内容：

• 反向索引和快速搜索

• 快速索引

• 更好的搜索结果

为了这个演示，我编了一个小的维基百科爬虫，爬到相当多（85000）维基百科文章的第一段。由于索引到所有85K文件需要90秒左右，在我的电脑我已经削减了一半。不想让你们仅仅为了一个简单的全文本演示浪费你的笔记本电脑电量。

因为索引是一个繁重的、模块化的CPU操作，我把它当成一个网络工作者。索引运行在一个后台线程上–在这里你可以找到完整的源代码。你也会发现到词干算法和我的停用词列表中的源代码参考。至于代码许可，还是一如既往为教育目的而免费，而不用于任何商业目的。

最后是演示。一旦索引完成，尝试寻找随机的东西和短语，维基百科会知道的。注意，只有40000段的索引，所以你可能要尝试一些新的话题。

以上がJavaScript 全文検索の関連性スコアリングのサンプル コードの詳細な紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。