hivemallで文字列のcosine類似度を取る

概要

hive上で文字列の類似度を出してみる。用途としては表記揺れを検出したいとか。

@CretedDate 2015/12/23
@Versions hive 0.13くらい, hivemall 0.4くらい

使うデータ

この前使った駅データ.jpの路線名データを利用してみる。下記のようなデータ。

line_cd line_name
1001    中央新幹線
1002    東海道新幹線
1003    山陽新幹線
1004    東北新幹線
1005    上越新幹線
1006    上越新幹線(ガーラ湯沢支線)
1007    山形新幹線
1008    秋田新幹線
1009    北陸新幹線
1010    九州新幹線
　・
　・

line_nameの類似度を取って、一番似ている路線名を引っ張ってみる。

hiveでngramを取る

ngramsという関数がhiveに用意されているので、それを使う。

ngrams(array, n, top-k)

まず split(station_name, '') で文字列を1文字ずつの配列に分割し、bi-gramで取りたいのでn=2に,文字列長が全部収まるように k=50にしてクエリを投げてみる。

SELECT
  line_cd,
  line_name,
  ngrams(split(line_name, ''), 2, 20) line_name_ngram
FROM
  test_lines
GROUP BY
  line_cd,
  line_name

1001    中央新幹線    [[["","中"],1],[["中","央"],1],[["央","新"],1],[["幹","線"],1],[["新","幹"],1],[["線",""],1]]
1002    東海道新幹線    [[["","東"],1],[["幹","線"],1],[["新","幹"],1],[["東","海"],1],[["海","道"],1],[["線",""],1],[["道","新"],1]]
1003    山陽新幹線    [[["","山"],1],[["山","陽"],1],[["幹","線"],1],[["新","幹"],1],[["線",""],1],[["陽","新"],1]]
1004    東北新幹線    [[["","東"],1],[["北","新"],1],[["幹","線"],1],[["新","幹"],1],[["東","北"],1],[["線",""],1]]
1005    上越新幹線    [[["","上"],1],[["上","越"],1],[["幹","線"],1],[["新","幹"],1],[["線",""],1],[["越","新"],1]]
　・
　・

こんな感じでngramのカウントが取れる。同一の並びが複数あった場合はカウントアップされてまとめられる。下記の「ゆうゆうあぶくまライン」は「ゆう」が2回カウントされている。

11228    ゆうゆうあぶくまライン    [[["ゆ","う"],2],[["","ゆ"],1],[["あ","ぶ"],1],[["う","あ"],1],[["う","ゆ"],1],[["く","ま"],1],[["ぶ","く"],1],[["ま","ラ"],1],[["イ","ン"],1],[["ラ","イ"],1],[["ン",""],1]]

今回はngramなのでsplitしてるけど、英文を区切る場合はsentenceという関数があったり、日本語の場合はhivemallにKuromojiUDF.javaが用意されていたりする。

空文字を含む結果を消してみる

[["", "中"],1]や[["線", ""],1]のように文字の終端との繋がりが空文字表現されているが、これはexplodeして消してみる。

消した後、元に戻しつつhivemallのfeatureに変換する。

WITH line1 AS (
  -- ngramを取る
  SELECT
    line_cd,
    line_name,
    ngrams(split(line_name, ''), 2, 20) line_name_ngrams
  FROM
    test_lines
  GROUP BY
    line_cd,
    line_name
), line2 AS (
  -- explodeで展開
  SELECT
    line_cd,
    line_name,
    line_name_ngram
  FROM
    line1 LATERAL VIEW explode(line_name_ngrams) dummy as line_name_ngram
)
-- 0文字の文字列との連結を除外し、hivemallのfeatureに変換
SELECT
  line_cd,
  line_name,
  COLLECT_LIST(FEATURE(CONCAT(line_name_ngram.ngram[0], line_name_ngram.ngram[1]), line_name_ngram.estfrequency)) AS line_name_ngram
FROM
  line2
WHERE
  LENGTH(line_name_ngram.ngram[0]) > 0 AND LENGTH(line_name_ngram.ngram[1]) > 0
GROUP BY
  line_cd,
  line_name

これで馴染みのあるhivemall形式の一覧になった。あとはこれに対してcosine similarityすればいい。

1001    中央新幹線    ["中央:1.0","央新:1.0","幹線:1.0","新幹:1.0"]
1002    東海道新幹線  ["幹線:1.0","新幹:1.0","東海:1.0","海道:1.0","道新:1.0"]
1003    山陽新幹線    ["山陽:1.0","幹線:1.0","新幹:1.0","陽新:1.0"]
1004    東北新幹線    ["北新:1.0","幹線:1.0","新幹:1.0","東北:1.0"]
1005    上越新幹線    ["上越:1.0","幹線:1.0","新幹:1.0","越新:1.0"]
　・
　・

ブルートフォースで類似度を取る

まずはブルートフォース的に距離を測ってみる。今回はたかだか614路線、376996パターンの距離を測るだけなので、そのまま突っ込んでしまえば良い。

WITH line1 AS (
  -- ngramを取る
  SELECT
    line_cd,
    line_name,
    ngrams(split(line_name, ''), 2, 20) line_name_ngrams
  FROM
    test_lines
  GROUP BY
    line_cd,
    line_name
), line2 AS (
  -- explodeで展開
  SELECT
    line_cd,
    line_name,
    line_name_ngram
  FROM
    line1 LATERAL VIEW explode(line_name_ngrams) dummy as line_name_ngram
), line3 AS (
  -- 0文字の文字列との連結を除外し、hivemallのfeatureに変換
  SELECT
    line_cd,
    line_name,
    COLLECT_LIST(FEATURE(CONCAT(line_name_ngram.ngram[0], line_name_ngram.ngram[1]), line_name_ngram.estfrequency)) AS line_name_ngram
  FROM
    line2
  WHERE
    LENGTH(line_name_ngram.ngram[0]) > 0 AND LENGTH(line_name_ngram.ngram[1]) > 0
  GROUP BY
    line_cd,
    line_name
), line4 AS (
  -- ブルートフォースアタック！ - サーバーは死ぬ
  SELECT
    l1.line_cd AS line_cd_1,
    l1.line_name AS line_name_1,
    l2.line_cd AS line_cd_2,
    l2.line_name AS line_name_2,
    cosine_similarity(l1.line_name_ngram, l2.line_name_ngram) AS similarity
  FROM
    line3 l1 JOIN line3 l2
)
SELECT
  *
FROM
  line4
WHERE
  similarity > 0.7
  AND line_cd_1 != line_cd_2
ORDER BY
  similarity DESC
;

ちゃんと類似の駅名が取れていることがわかる。

99808    伊予鉄道環状線    99809    伊予鉄道環状線    1
99809    伊予鉄道環状線    99808    伊予鉄道環状線    1
28006    東京メトロ有楽町線    28007    東京メトロ有楽町新線    0.8249579071998596
28007    東京メトロ有楽町新線    28006    東京メトロ有楽町線    0.8249579071998596
99332    千葉都市モノレール２号線    99331    千葉都市モノレール１号線    0.8181818127632141
99331    千葉都市モノレール１号線    99332    千葉都市モノレール２号線    0.8181818127632141
99514    名古屋市営地下鉄名城線    99515    名古屋市営地下鉄名港線    0.800000011920929
99515    名古屋市営地下鉄名港線    99514    名古屋市営地下鉄名城線    0.800000011920929
　・
　・

minhashを使った類似度計算

今回はたかだか614件のデータなのでブルートフォースでも問題ないけど、データ量が増えてくると類似度を取る必要があるパターン数が爆発的に増えるので厳しくなってくる。

その対応としてminhashでクラスタを作る方法があるらしいので使ってみる。こちらの記事で行われている方法。

WITH line1 AS (
  -- ngramを取る
  SELECT
    line_cd,
    line_name,
    ngrams(split(line_name, ''), 2, 20) line_name_ngrams
  FROM
    test_lines
  GROUP BY
    line_cd,
    line_name
), line2 AS (
  -- explodeで展開
  SELECT
    line_cd,
    line_name,
    line_name_ngram
  FROM
    line1 LATERAL VIEW explode(line_name_ngrams) dummy as line_name_ngram
), line3 AS (
  -- 0文字の文字列との連結を除外し、hivemallのfeatureに変換
  SELECT
    line_cd,
    line_name,
    COLLECT_LIST(FEATURE(CONCAT(line_name_ngram.ngram[0], line_name_ngram.ngram[1]), line_name_ngram.estfrequency)) AS line_name_ngram
  FROM
    line2
  WHERE
    LENGTH(line_name_ngram.ngram[0]) > 0 AND LENGTH(line_name_ngram.ngram[1]) > 0
  GROUP BY
    line_cd,
    line_name
), line4 AS (
  -- クラスタID取得
  SELECT
    MINHASH(line_cd, line_name_ngram) AS (cluster_id, line_cd)
  FROM
    line3
), line5 AS (
  -- クラスタIDのJOIN
  SELECT
    line3.line_cd,
    line3.line_name,
    line3.line_name_ngram,
    line4.cluster_id
  FROM
    line3 JOIN line4 ON line3.line_cd = line4.line_cd
)
SELECT DISTINCT
  l1.line_cd AS line_cd1,
  l1.line_name AS line_name1,
  l2.line_cd AS line_cd2,
  l2.line_name AS line_name2,
  COSINE_SIM(l1.line_name_ngram, l2.line_name_ngram) AS similarity
FROM
  line5 l1 JOIN line5 l2 ON l1.cluster_id = l2.cluster_id
WHERE
  l1.line_cd != l2.line_cd
ORDER BY
  similarity DESC
LIMIT
  30

上位についてはまったく同じ結果になっている。

99808   伊予鉄道環状線  99809   伊予鉄道環状線  1.0
99809   伊予鉄道環状線  99808   伊予鉄道環状線  1.0
28007   東京メトロ有楽町新線    28006   東京メトロ有楽町線  0.8249579
28006   東京メトロ有楽町線  28007   東京メトロ有楽町新線    0.8249579
99331   千葉都市モノレール１号線    99332   千葉都市モノレール２号線    0.8181818
99332   千葉都市モノレール２号線    99331   千葉都市モノレール１号線    0.8181818
99514   名古屋市営地下鉄名城線  99515   名古屋市営地下鉄名港線  0.8
99515   名古屋市営地下鉄名港線  99514   名古屋市営地下鉄名城線  0.8
　・
　・

この処理ではそれぞれのレコードに複数のクラスタIDが振られ（なので最後にDISTINCTしないと重複したレコードが出てきたりする）、JOINをした上でsimilarityを取るので、類似度を測るよりは負荷が少ないJOINで対象を絞れる。

今回の例ではレコード数が614件。ブルートフォースでは614^2の376996回の類似度計算が行われたけど、minhashを使った方では10590回しか行われていない。およそ97.2%類似度計算回数を減らせたことになる。