コサイン類似度に基づくソート処理の実装方法とその性能比較

文書の類似度を計算する方法に「コサイン類似度」を用いる方法があります。

これは、出現する単語を出現回数などで数値化して、空間ベクトルに変換した上でベクトル同士の類似度を計算する、という手法です。

• コサイン類似度
  http://www.cse.kyoto-su.ac.jp/~g0846020/keywords/cosinSimilarity.html

最近、このコサイン類似度を使って、似ているデータを検索するWebアプリを試しに作っていたのですが、ふと、

「このコサイン類似度を使ったソート処理をPostgreSQLでどのように実装するともっとも高速な実装になるのだろうか。また、現実的なパフォーマンスを考えた時にデータ量や次元のサイズはどこまで増やせるのだろうか」

ということが気になりました。

PostgreSQLは、その拡張性の高さがウリの一つですが、そのため「UDFを作る」ということを考えても、実装方法にもいろいろあります。

今回は、PostgreSQL内部でデータ処理を実装するに当たって、どのような実装方法があるのか、それぞれどのように性能が違うのか、そしてその時にデータサイズがどのように影響するのかを見てみます。

■前提条件

今回は以下の前提条件で実装と性能比較を行います。

• ソート処理するデータはPostgreSQLに蓄積されているものを対象とする
• 空間ベクトルを表すデータは、PostgreSQL の float8 の配列で1カラムに保持する
• コサイン類似度による類似度を計算し、もっとも類似度の高いレコードをN件取得する

TF-IDFでデータベース内の類似テキストを検索する Part 4 （MADlib svec編）

TF-IDF 感動巨編3部作は前回のエントリで完結したわけですが、今回はその番外編、スピンオフとして「MADlib svec編」をお送りします。

MADlib には、sparse（疎）な配列、つまり多くの要素がゼロであるような配列を扱うデータ型として svec というデータ型があります。

• MADlib: Sparse Vectors
  https://madlib.incubator.apache.org/docs/latest/group__grp__svec.html

本エントリでは、TF-IDF のベクトルに MADlib の svec を使って、通常の float8[] などとどのように違うのかを見てみます。

■「MADlib」とは何か

MADlib については、ガッツリと割愛します。以前のエントリで詳しくご紹介しましたので、そちらを参照してください。

• データ分析用ライブラリ MADlib を使って PostgreSQL で機械学習する
  http://pgsqldeepdive.blogspot.jp/2016/04/madlib-postgresql.html

■「svec」 とは何か

svec は、ゼロの多い sparse な配列を圧縮して保持するデータ型です。データ分析をしていると、頻繁に遭遇するデータの構造になります。

例えば、float8 の配列で以下のようにゼロが並ぶデータがあったとします。

'{0, 33,...40,000個のゼロ..., 12, 22 }'::float8[]

TF-IDFでデータベース内の類似テキストを検索する Part 3 （性能改善編）

PostgreSQL 感動巨編 TF-IDF 3部作の最終回、「性能改善編」です。

• TF-IDFでデータベース内の類似テキストを検索する Part 1 （基本機能編）
  http://pgsqldeepdive.blogspot.jp/2016/07/tf-idf-part-1.html
• TF-IDFでデータベース内の類似テキストを検索する Part 2 （実践編）
  http://pgsqldeepdive.blogspot.jp/2016/07/tf-idf-part-2.html

前回の最後で、今回作成した UDF である euclidean_distance の処理に時間がかかってそうだ、ということが分かってきました。

そのため、本エントリではこの UDF をもう少し詳細に見ながら、パフォーマンスを改善する方法を探ります。

■euclidean_distanceの性能分析

処理時間がかかっていることが分かった euclidean_distance 関数ですが、改めて処理を詳細に見ていきます。

CREATE OR REPLACE FUNCTION euclidean_distance(tfidf_a jsonb, tfidf_b jsonb)
  RETURNS float8
AS $$
    from sklearn.metrics.pairwise import euclidean_distances
    import json

    aa = json.loads(tfidf_a)
    bb = json.loads(tfidf_b)
    w = list(set(aa.keys()).union(set(bb.keys())))
    vec_a = []
    vec_b = []
    for t in w:
        if t in aa:
            vec_a.append(aa[t])
        else:
            vec_a.append(0)
        if t in bb:
            vec_b.append(bb[t])
        else:
            vec_b.append(0)
    distance = euclidean_distances([vec_a], [vec_b])
    return distance[0][0]
$$
LANGUAGE 'plpython2u';

まず、ボトルネックの確認のため、少しずつこの関数のコードをコメントアウトして実行時間を比較してみると、

TF-IDFでデータベース内の類似テキストを検索する Part 2 （実践編）

前回の TF-IDF Part 1 の続きです。

• TF-IDFでデータベース内の類似テキストを検索する Part 1 （基本機能編）
  http://pgsqldeepdive.blogspot.jp/2016/07/tf-idf-part-1.html

今回は、現実的なドキュメントをPostgreSQLに格納して TF-IDF の類似度に基づく検索をしてみます。

■検索対象とするドキュメント

今回題材として使うドキュメント（コーパス）はPostgreSQLの日本語マニュアルです。

• PostgreSQL 9.5.3文書
  https://www.postgresql.jp/document/9.5/html/index.html

PostgreSQLのマニュアルは、かなりしっかりした内容が書かれている反面、ボリュームが多い、どこに書いてあるのか分からない、そもそも分かっていない人には分かりづらい、などの指摘がされることがあります。

そういう文書を読むときに、「関連するページ」を自動的にピックアップすることができれば、より深い理解や周辺の理解につながるのではないか、というのがもともとのモチベーションです。

■PostgreSQL内にコーパスを作成する

まず、PostgreSQLのマニュアルを保存するテーブルを作成します。スキーマは以下の通りです。

CREATE TABLE pgsql_doc (
  docid SERIAL PRIMARY KEY,
  filename TEXT NOT NULL,
  html TEXT NOT NULL,
  plain TEXT,
  tf JSONB,
  tfidf JSONB
);

TF-IDFでデータベース内の類似テキストを検索する Part 1 （基本機能編）

最近、「TF-IDF」と呼ばれる手法を使ってPostgreSQL内に保存されたテキストの類似度を計算して、似ているテキストを検索する方法を試していました。

一通り目途が立った気がしてきましたので、今回から3回に渡ってその方法をご紹介します。

• Part 1: 基本機能編
• Part 2: 実践編
• Part 3: 性能改善編

Part 1 は基本機能編ということで、TF-IDF に基づく類似性検索を PostgreSQL 内部で実装する方法をご紹介します。

Part 2 は実践編として、大量のドキュメントをPostgreSQLに格納して、TF-IDF を計算して検索するまでを解説します。

Part 3 は性能改善編ということで、検索性能を改善する方法を検討します。

■「TF-IDF」とは

TF-IDFは、自然言語処理で使われるアルゴリズムで、文書やコーパス（文書群）の中における単語の出現頻度を用いて、文書の単語に重み付けをする手法です。

• tf-idf - Wikipedia
  https://ja.wikipedia.org/wiki/Tf-idf

TF-IDFでは、「Term Frequency」と呼ばれる「単一の文書中における単語の出現頻度」と、「Inverse Document Frequency」と呼ばれる「コーパス全体における単語の出現頻度（の逆数）」を組み合わせて、単語に重み付けをします。

• TF: 特定の単語の出現回数 / 文書全体の単語数
• IDF: log(全文書数 / 単語を含んでいる文書数) + 1

として定義され、これらを組み合わせて「TF-IDF」が「TF * IDF」として計算されます。

このTF-IDFを用いて、文書中に出現する個々の単語に対して重み付けがされることになります。

形態素解析を使ってPostgreSQLに保存された文章データから話題を抽出する

PythonやPL/Python、PostgreSQLを使ってデータ分析をIn-Database処理させるのがマイブームです。

今回は、データベース内に保存された文章のテキストデータから単語の出現頻度を使って話題になっているトピックを抽出する、という処理を行ってみます。

• テキストを形態素解析する
• 形態素解析した結果をJSONBで取得する
• JSONBデータを対象に集計処理を行う
• 上記すべてをサーバサイドで実行する

といったことをPostgreSQLを使って処理してみます。

■データの準備

今回も東京カレンダーの「東京女子図鑑」からの文章をサンプルとして使ってみます。

• 31歳女性がするべき、銀座での“上質な”暮らし。大人の女の流儀とは？(1/2)[東京カレンダー]
  https://tokyo-calendar.jp/article/4640

今回は、docidという主キーとテキストを値としてdoctextカラムに持つテーブルを作成し、そこにテキストを保存しておくようにします。今回のテキストは約4,000文字あります。

snaga=# \d docs
      Table "public.docs"
 Column  |  Type   | Modifiers
---------+---------+-----------
 docid   | integer | not null
 doctext | text    |
Indexes:
    "docs_pkey" PRIMARY KEY, btree (docid)

snaga=# SELECT docid, length(doctext) FROM docs;
 docid | length
-------+--------
     1 |   4423
(1 row)

snaga=# SELECT docid, substring(doctext,0,60) AS doctext FROM docs;
 docid |                                                       doctext
-------+---------------------------------------------------------------------------------------------------------------------
     1 | 20代後半頃から、同期が1人また１人と、会社を辞めていきました。辞める理由はいろいろありますが、病んでしまった子もいれ
(1 row)

snaga=#

■形態素解析を行うユーザ定義関数を作成する

まず、テキストを入力として受け取り、形態素解析した結果をJSONB型として返却するユーザ定義関数を作成します。

自動要約API「summpy」を使ってPostgreSQLに文章の要約機能を追加する

昨日、PostgreSQL勉強会で「PostgreSQLハッキング 最初の一歩」と題して、PostgreSQLの拡張開発の初歩についていくつかお話させていただきました。

• 第33回 PostgreSQL 勉強会(2015年11月14日)
  http://www.postgresql.jp/wg/shikumi/pgstudy_33/view

本エントリでは、勉強会でPL/Pythonの例としてご紹介した「自動要約APIをPostgreSQLに組み込む」について、もう詳しく紹介させていただこうと思います。

（右のサムネイルの意味は本エントリの最後に分かります）

■「自動要約API」とは？

自動要約APIは、10月末にリクルートテクノロジーズさんがリリースされた自然言語処理のライブラリで、Pythonで書かれたものです。

• 自動要約APIを作ったので公開します | RECRUIT TECHNOLOGIES Member's blog
  http://blog.recruit-tech.co.jp/2015/10/30/summpy-released/
• recruit-tech/summpy
  https://github.com/recruit-tech/summpy

アルゴリズムについてはあまり詳しくは理解していないのですが、LexRankと呼ばれるアルゴリズムとMCP（Maximum Coverage Problem）と呼ばれるアルゴリズムが実装されており、形態素解析で品詞を分解したものにこれらのアルゴリズムを適用することで、「文章の中で重要度の高いセンテンスを選択する」ということを実現するようです。