【データ抽出/BigQuery】2つの異なるテーブルからtitle名同士を比較して類似度を算出する

今回の課題

worksマスタと、配信停止コンテンツリストのテーブル同士の、
コンテンツのtitle名の類似度を計算して、配信停止コンテンツリストに追加すべきコンテンツ（類似度が高いコンテンツ）が無いか探したかった。

結論的には、こちらの記事の方法で探す方法の方が良かったが、メモとして残す。

※参考：BigQueryのSQLで類似度文字列検索をする

使用クエリ

/* worksマスタのbigramを出す。 */
with works_mst_ngram as (
    select
        title
        , substr(title, i, 2) as ngram
        , count(*) as count
    from
        `worksマスタ`, unnest(generate_array(1, 100)) as i
    where
        length(substr(title, i, 2)) = 2
    group by
        title
        , ngram
)
/* 配信停止コンテンツのbigramを出す */
, unsubscribed_contents_mst_ngram as (
    select
        title_name
        , substr(title_name, i, 2) as ngram
        , count(*) as count
    from
        `配信停止コンテンツリスト`, unnest(generate_array(1, 100)) as i
    group by
        title_name
        , ngram
) 
/* 上記の２つのテーブルを内部結合する */
/* count × countをする */
, inner_product as (
    select
        a.title as title1
        , b.title_name as title2
        , sum(a.count * b.count) as inner_product -- コサイン類似度の分子
    from
        works_mst_ngram as a
        inner join unsubscribed_contents_mst_ngram as b
            on a.ngram = b.ngram
            and a.title < b.title_name
    group by
        title1, title2
)
/* worksマスタのノルム値を出すための前処理をする */
, works_norm as (
    select
        title
        , sum(count*count) as sum
    from
        works_mst_ngram
    group by
        title
)
/* コンテンツマスタのL2ノルムを算出する */
, works_mst_l2_norm as (
    select
        title
        , sqrt(sum) as norm
    from
        works_norm
)
/* 配信停止コンテンツのノルム値を出すための前処理をする */
, unsubscribed_norm as (
    select
        title_name
        , sum(count*count) as sum
    from
        unsubscribed_contents_mst_ngram
    group by 
        title_name
)
/* 配信停止コンテンツのL2ノルムを算出する */
, unsubscribed_l2_norm as (
    select
        title_name
        , sqrt(sum) as norm
    from
        unsubscribed_norm
)
/* 類似値の計算をして、類似値が高い順に出力する */
select
    p.title1
    , p.title2
    , p.inner_product / n1.norm / n2.norm as cosine
from
    inner_product as p
    inner join works_mst_l2_norm as n1
        on p.title1 = n1.title
        inner join unsubscribed_l2_norm as n2
            on p.title2 = n2.title_name
-- where
--     strpos(title1, title2) = 0 and strpos(title2, title1) = 0
order by
    cosine desc

クエリを分解して理解する

1)bigramを出す

• GENERATE_ARRAY(1, 100)で１から十分な配列を作って、
  2文字ずつSUBSTR()で抜き出してbigramを作る。（データが多い場合はngramのnを大きく設定した方が良さそう。）
• WHERE句でbigramだけにフィルタリングして、余分な行を削除する。
  （これをしないと、ngramカラムに文字列が入っていない行が残ってしまう。）
• countカラムに、titleとngram毎の行数を格納しておく。

/* worksマスタのngramを出す。*/
with works_mst_ngram as (
    select
        title
        , substr(title, i, 2) as ngram
        , count(*) as count
    from
        `worksマスタ`, unnest(generate_array(1, 100)) as i
    where
        length(substr(title, i, 2)) = 2
    group by
        title
        , ngram
)
/* 配信停止コンテンツのngramを出す */
, unsubscribed_contents_mst_ngram as (
    select
        title_name
        , substr(title_name, i, 2) as ngram
        , count(*) as count
    from
        `配信停止コンテンツリスト`, unnest(generate_array(1, 100)) as i
    group by
        title_name
        , ngram
) 

2)1)のWITH句同士を内部結合する

• 1)のWITH句同士をINNER JOIN結合する
• 1)のWITH句同士のcountカラムを掛け算する。
  後程の行程で、コサイン類似度の分子とする。（後程説明を書きます）

/* 上記の２つのテーブルを内部結合する */
/* count × countをする */
, inner_product as (
    select
        a.title as title1
        , b.title_name as title2
        , sum(a.count * b.count) as inner_product -- コサイン類似度の分子
    from
        works_mst_ngram as a
        inner join unsubscribed_contents_mst_ngram as b
            on a.ngram = b.ngram
            and a.title < b.title_name
    group by
        title1, title2
)

3)1)のテーブルからL2ノルムを算出する

• コサイン類似度の分母を出すために、
  前処理の段階でcount*countをしたもの(countカラムを2乗した数値)を合算して、
  L2ノルムを出す段階でSQRT関数を使用してそれらの平方根を出す。

/* worksマスタのノルム値を出すための前処理をする */
, works_norm as (
    select
        title
        , sum(count*count) as sum
    from
        works_mst_ngram
    group by
        title
)
/* コンテンツマスタのL2ノルムを算出する */
, works_mst_l2_norm as (
    select
        title
        , sqrt(sum) as norm
    from
        works_norm
)
/* 配信停止コンテンツのノルム値を出すための前処理をする */
, unsubscribed_norm as (
    select
        title_name
        , sum(count*count) as sum
    from
        unsubscribed_contents_mst_ngram
    group by 
        title_name
)
/* 配信停止コンテンツのL2ノルムを算出する */
, unsubscribed_l2_norm as (
    select
        title_name
        , sqrt(sum) as norm
    from
        unsubscribed_norm
)

4)類似度を計算して、類似度が高い順にデータを出力する

• これまでに用意したカラムを使って、コサイン類似度を実際に算出する。
• ORDER BY句でコサイン類似度の降順でソートする。
• WHERE句にて、STRPOS関数を使用して、第一引数内で第二引数が出現する位置が

/* 類似値の計算をして、類似値が高い順に出力する */
select
    p.title1
    , p.title2
    , p.inner_product / n1.norm / n2.norm as cosine -- コサイン類似度を算出
from
    inner_product as p
    inner join works_mst_l2_norm as n1
        on p.title1 = n1.title
        inner join unsubscribed_l2_norm as n2
            on p.title2 = n2.title_name
-- where
--     strpos(title1, title2) = 0 and strpos(title2, title1) = 0
order by
    cosine desc

※参考：SQRT関数
※参考：STRPOS関数

おまけ（分からなかった言葉）

コサイン類似度とは

2つのベクトルが「どれくらい似ているか」という類似性を表す尺度。
1に近いほど「似ている」、-1に近いほど「似ていない」ということを表す。

計算式は下記の通り。
これを上記のクエリのWITH句毎に、必要な数値を用意し、最終的に計算を行ったというイメージ。

※参考：コサイン類似度とは？

ノルム値とは

統計データの基準値のこと。
ノルム値の算出方法としては、「平均値」や「偏差値」などがある。

L2ノルムとは

ベクトル要素の、絶対値の自乗の総和の平方根で計算される。
L2のノルムの値はユークリッド距離と呼ばれ、2点間の直線距離を表す。
※参考：L2ノルム