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

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

結論的には、[こちら](https://qiita.com/Ayumu-y/items/79c112d99b20e855bc3c)の記事の方法で探す方法の方が良かったが、メモとして残す。


※参考：[BigQueryのSQLで類似度文字列検索をする](https://sucrose.hatenablog.com/entry/2017/06/11/234015)

## 使用クエリ
```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`毎の行数を格納しておく。

```sql
/* 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`カラムを掛け算する。
後程の行程で、コサイン類似度の分子とする。（後程説明を書きます）
```sql
/* 上記の２つのテーブルを内部結合する */
/* 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`関数を使用してそれらの平方根を出す。
```sql
/* 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関数を使用して、第一引数内で第二引数が出現する位置が
```sql
/* 類似値の計算をして、類似値が高い順に出力する */
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関数](https://cloud.google.com/bigquery/docs/reference/standard-sql/mathematical_functions?hl=ja#sqrt)
※参考：[STRPOS関数](https://cloud.google.com/bigquery/docs/reference/standard-sql/string_functions?hl=ja#strpos)

## おまけ（分からなかった言葉）
### コサイン類似度とは
2つのベクトルが「どれくらい似ているか」という類似性を表す尺度。
1に近いほど「似ている」、-1に近いほど「似ていない」ということを表す。

計算式は下記の通り。
これを上記のクエリのWITH句毎に、必要な数値を用意し、最終的に計算を行ったというイメージ。
![di-capture03.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/883573/47b7b866-2a5f-5460-0c0d-cf0e11f6448f.png)
※参考：[コサイン類似度とは？](https://atmarkit.itmedia.co.jp/ait/articles/2112/08/news020.html)

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


### L2ノルムとは
ベクトル要素の、絶対値の自乗の総和の平方根で計算される。
L2のノルムの値はユークリッド距離と呼ばれ、2点間の直線距離を表す。
※参考：[L2ノルム](https://ai-maimoko.hatenablog.jp/entry/2021/08/16/225651#L2%E3%83%8E%E3%83%AB%E3%83%A0)