PostgreSQLで2つのリスト間の類似度を算出する方法を考える

あるリストを元に、それと似た内容を持つリストをデータベースの中から探したい、というケースはいくつか考えられる。

例えば、

いくつかの商品を組み合わせて作ったセット商品のうち、今見ている商品と同じような構成のものを探す
SNSで自分と同じようなフレンド構成を持つユーザーを抽出して自分と似たユーザーを探す
あるユーザーの購入履歴を元に同じような購入履歴を持つユーザーを抽出し、それらのユーザーが買っていてまだ買っていない商品をレコメンドする

基本となるのは、リスト同士を比較してその類似度を元に並べ替えてより類似したものを見つける、ということだと思うのだけど、実際どのように実装されているのだろうか。

上記の例はどれもデータがどんどん増えていくので、あらかじめリスト間の類似度を算出しておく、ということはできそうにないし、データが増える度に既存のリストとの類似度をチェックして保存しておく、というのは検索は速そうだけどデータ容量が無駄に大きくなる。となると、検索の都度類似度をチェックして抽出している、と思われる。

あるセット商品と構成が似たセット商品を探す

最初の、「構成が似たセット商品を探す」という例で検索を行う関数を作ってみた。

データのイメージはこんな形。(PRODUCT_PARTSテーブルとする) セットコードは複数の部品コードと関連付けられている。

PRODUCT_CD	PART_CD
セット1	A
セット1	B
セット1	C
セット2	A
セット2	D
セット3	F

たくさんのセットが、それぞれ複数の部品を持つ状態で保存されているとする。例えばこの中で、セットAと構成が似ているセットを類似度が高い順に表示したい。

PostgreSQLにはARRAY型があるので、2つの部品コードが入ったARRAYを比較して、返り値として0.0（全く同じ要素を持たない）〜1.0（完全に同じ構成）を返す関数を作ってみる。

比較元リストを元に比較先リストに同じ要素が何%入っているかで類似度を算出している。長い方のリストを元に算出するようにしたら、intersectになるかな？

検索は下記のようなクエリで実行する。比較対象元セットの部品リストはあらかじめ取得しておき、SF_GET_LIST_SIMILARITYの第一引数に渡す。

QUERY_SIMILARITY.sql

SELECT
    T1.PRODUCT_CD,
    T1.ARR_PC,
    SF_GET_LIST_SIMILARITY(ARRAY['A','B','C','D','E']::text[], T1.ARR_PC) AS SIM 
FROM
(
    SELECT
        PP.PRODUCT_CD AS PRODUCT_CD,
        ARRAY_AGG(PP.PARTS_CD) AS ARR_PC
    FROM
        PRODUCT_PARTS PP
    GROUP BY
        PP.PRODUCT_CODE
) T1
WHERE
    SF_GET_LIST_SIMILARITY(ARRAY['A','B','C','D','E']::text[], T1.ARR_PC) &gt; 0 
ORDER BY
    SIM DESC
;