HivemallでMinhash！〜似てる記事を探し出そう。〜

こんにちは。俺やで。

前回の投稿に続き（間が空きましたが）、
ビッグデータに対応したHiveで使える機械学習ライブラリ、
「Hivemall」の使い方、第２弾となります。

今回はMinhashという手法について書きたいと思います。
※前回
【超入門】Hivemallで機械学習 〜Treasure Dataでロジスティック回帰編〜

しかし！
Hivemallは一言で言えば「機械学習ライブラリ」ではありますが、
Minhash、これ自体は機械学習の分野の言葉ではないです…
すみません。でもおもしろい考え方（手法？）なので！
よろしくお願いします。

■1. Minhashとは？

２つの集合の重なり度合いを推定する！

Jaccard係数という数字をご存知でしょうか。
「難しいそうな言葉出てきた」と思われるかもしれませんが、
そんなことないです。
Jaccard係数は「２つの集合がどれだけ重なっているか」を示す数字です。
図と式を見てください。

JがJaccard係数を表します。
A∩Bが積集合（AかつB）。A∪Bが和集合（AまたはB）。
つまり「AとBをあわせたすべての要素のうち、AとBに共通な要素の数の割合」がJaccard係数になります！

なるほどなーる。

これを推定するのがMinhashです！

うれしいの？

「joinしてcountしたら終わりじゃん…」
もっともです。

でもちゃんとうれしいケースがあります。
それは「大量のデータを繰り返しjoinしてcountする必要がある」場合です。

Minhashは「Jaccard係数を推定してくれる」ものだと申し上げましたが、
「推定」であるのと引き換えに計算量をものすごく軽くしてくれます。
ですから「大量のデータを繰り返しjoinしてcountする必要がある」とき、Minhashは便利なのです。

もっと具体例

もうちょっと具体的なケースを挙げましょう。
一つ目がDMP（Data Management Platform）です。
たとえばDMPを使って２つのWebサイトにアクセスしているユーザーの重なり度合いを見たい（マーケティングに活かしたい）、と思うことがあるわけです。クロス集計はデータ分析の基本ですよね。

その２つのWebサイトにそれぞれ数百万人ユーザーがいたら、
正直にjoinしてcountするのもけっこう大変です。

大変なだけで計算できないことはないのですが、
DMPの機能に落とし込んで、こんなリクエストがひっきりなしに送られてきてしまうと、
全部正直に計算してられません。。

そこでMinhashです。計算量をぐっと落としてくれます。

二つ目の具体例がレコメンドです。

商品Aと商品Bがあるとしましょう。
商品Aと商品Bの購入者のJaccard係数がとても高かった場合、
つまり商品A（B）の購入者が商品B（A）の購入者である確率が高かった場合、
商品Aの購入者には商品Bをおすすめして良さそうですよね！

でももし、商品Aと商品Bと商品Cがあったら。
商品Aの購入者に商品Bと商品Cのどちらを薦めましょうか。
AとBのJaccard係数とAとCのそれを比べなければなりません。

ではもし、商品が1,000点あったら。10,000点あったら。大変そうです。
そんなときのMinhash。こんなことにも使えます。

Minhashを詳しく！

どうやってJaccard係数を推定してるかお話します。
というかお話させてください！
ここが書きたかったんですから。
まずはさきほどの図を再掲です。

ここで、
・Aの要素数をa
・Bの要素数をb
・A∩Bの要素数をc
とします。（変数の置き方にセンスがない）
とすると、Jaccard係数は次の計算式になります。

分母はa+bだけだと重なり部分がダブルカウントされているので、cを引いてます。

ではここで、とあるhash関数を用意します。
このhash関数にAとBの要素を適用すると整数値が返ってきます。

このhash関数をAの要素すべてに適用しましょう。
ある要素には31223といった数字が。別の要素には8352といった数字が返ってきます。
その中で最小のものをmin(A)としましょう。

同様に、Bのすべての要素にも同じhash関数を適用するとmin(B)ができるはずです。

それでは min(A) = min(B) となる確率P(A,B)はいくつでしょうか。

これは、A∪Bの中でhash値が最小となる要素が、A∩Bの中に含まれている確率に等しいです。
つまり、

なんと！
Jaccard係数J(A,B)と、
min(A)=min(B)となる確率P(A,B)がまったく同じになります。

感動です！感動！（伝わりましたか…）

これを利用すれば、たとえば10,000個相異なるhash関数を用意して、
そのうちmin(A)=min(B)となるhash関数が100個だった場合、
J(A,B) = 100/10,000 = 0.1 になりますし、
5,000個hash関数を用意して、1,500個がmin(A)=min(B)となった場合、
J(A,B) = 1,500/5,000 = 0.3 になります。

つまり、逐一「joinしてcount」しなくても、
各集合Xに対してmin(X)をあらかじめ計算しておけば、
min(X)を比較するだけでJaccard係数が計算できてしまうのです！

感動が伝わったでしょうか！？！？
最初の元を使う、集合論的な考え方をしているのがまたおもしろい！

■2. Hivemallでminhashを実行してみる

やっと本題！Hivemall！
チュートリアルにMinhashによるレコメンド手法が紹介されています。

この手法をクエリを追いつつ見ていきましょう！

まずは使うデータ

データを見ていきます。
news20という有名なサンプルデータです。３行だけ見てみます。

どんなデータになっているかというと、
記事ID:1の記事には、単語ID:197の単語が2回、単語ID:321の単語が3回、単語ID:399の単語が1回…出現している、
記事ID:2の記事には、単語ID:7の単語が1回、単語ID:1039の単語が1回、単語ID:1628の単語が1回…出現している、
…
という内容で15,935記事分のデータが入っています。
各記事にどんな単語が含まれているか、を表しているのですね。

同じ単語が使われている記事は、同じような内容になっている可能性が高いです。
（Iとかhaveとか、そういうの除く）。
なので記事１と同じような内容の記事２を、記事１を読んだ人にレコメンドしてあげてもいいんじゃない？と考えることもできますよね。

minhashを使ってどの記事とどの記事が”似てる”のか探してみましょう、というのが今回のお題です。
なお今回は「どんなワードが使われているか」を見るだけで、
何回その数字がどれだけ使われたかという「回数」は考慮しません。

hash値の最小値を計算する

このnews20のデータが入っているテーブルをnews20としましょう。
下のクエリを投げると、各レコードのwordsにhash関数を適用したうち最小の値を返してくれます。
今回は100個hash関数を用意することにしたので、”-n 100″とオプションつけました。

select
  minhash(id, words, "-n 100") as (clusterId, rowid) --"'-n 100'は100個hash関数を使うためのオプション"
from
  news20;

・結果　テーブル名「 news20_minhash 」とします。

hash関数を100個用意したので、1つの記事IDごとに100レコードできます。
15,935記事分データがあるので、全部で15,935 × 100 = 1,593,500レコードになるわけですね。

集計する

それでは次のクエリで一気に、
どの記事はどの記事と似ているのか出してしまいます。

select j.rowid, collect_set(rid) as related_article from
(select
  l.rowid, r.rowid as rid, count(*) as cnt --minhashの値が一致する数
from
  news20_minhash l
  LEFT OUTER JOIN
  news20_minhash r
     ON (l.clusterid = r.clusterid) --minhashの値が一致するレコードのみをjoin
where
  l.rowid != r.rowid --同じ記事どうしは除外
group by
  l.rowid, r.rowid
having
  cnt > 10 --minhashの値が一致する数が10個以下のものは除外
) j
group by j.rowid
order by j.rowid asc

14行目でレコードを削っていますが、
100個hash関数を使って「minhashの値が一致する数が10個以下」なので、
Jaccard係数（=集合どうしの重なり度合い）が0.1以上のもののみを残してます。
閾値が0.1で正しいのかどうかは吟味してません。悪しからず。

上のクエリを投げた結果が次です。

出ました！

各記事IDに内容が似た記事IDがrelated_articlesに配列で入っています。

記事ID:1,3,5のレコードがありませんが、
“似た記事”がなかったよ！っていうことです。
（偶数番になってしまったのはたまたまです。）

しかしながら、これを使えば記事のレコメンドができるかもですね！

しかも投げるクエリも上の２つだけ！簡単です！万歳Hivemall！

〜追記〜

もうちょっと言いたかったこと、その１

まず、「minhashは機械学習の分野の話ではない」、と冒頭申し上げました。
じゃあ何なのか。

乱択アルゴリズムの守備範囲になります。

データをぜーんぶ見なくても、サンプリングしたデータからその”ぜーんぶ”がわかること。
これが乱択アルゴリズムだと僕は理解しています。
間違ってたらごめんなさい。

HyperLogLogとかおもしろいです。（名前がすでにおもしろい）
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

もうちょっと言いたかったこと、その２

今回「minhashによるレコメンド」を題材に取り上げましたが、
レコメンド手法としては正直微妙です。。
minhashを紹介するのにわかりやすい例がないとなーと思い、レコメンドを取り上げた次第です。

Hivemallでちゃんとレコメンドしたいのであれば、
MatrixFactorization
がよいでしょう。

Hivemallの開発者の方が書いておられる記事になります。
HivemallでMatrix Factorization

もうちょっと言いたかったこと、その３

minhash自体は20世紀の間には確立されていたらしく、
最近ではminhashの進化版、b-bit minhashなるものがあります。
興味ある方は見てみてください。基本的な考え方はminhashと大差ないです。
b-Bit Minwise Hashing

以上です！

なお今回もTreasureData上で試させていただきました。毎度お世話になります。

そして、申し遅れました。私ビッグデータ解析部吉村と申します。

またの機会に！

  関連記事