こんにちは。俺やで。
前回の投稿に続き（間が空きましたが）、 ビッグデータに対応した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(id) | 使われている単語(words) |
|---|---|
| 1 | ["197:2","321:3","399:1","561:1","575:1","587:1",…] |
| 2 | ["7:1","1039:1","1628:1","1849:1","2686:1","2918:1"…] |
| 3 | ["77:9","137:1","248:1","271:1","357:1","377:3",…] |
どんなデータになっているかというと、 記事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"とオプションつけました。
[sql] select minhash(id, words, "-n 100") as (clusterId, rowid) --"'-n 100'は100個hash関数を使うためのオプション" from news20; [/sql]
・結果 テーブル名「 news20_minhash 」とします。
| 記事ID(id) | 最小のhash値(cluster_id) |
|---|---|
| 1 | 896574361 |
| 1 | 320726648 |
| ・・・ | ・・・ |
| 2 | 1726436972 |
| 2 | 1103952875 |
| ・・・ | ・・・ |
| 3 | 1406179360 |
| ・・・ | ・・・ |
hash関数を100個用意したので、1つの記事IDごとに100レコードできます。 15,935記事分データがあるので、全部で15,935 × 100 = 1,593,500レコードになるわけですね。
集計する
それでは次のクエリで一気に、 どの記事はどの記事と似ているのか出してしまいます。
[sql] 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 [/sql]
14行目でレコードを削っていますが、 100個hash関数を使って「minhashの値が一致する数が10個以下」なので、 Jaccard係数（=集合どうしの重なり度合い）が0.1以上のもののみを残してます。 閾値が0.1で正しいのかどうかは吟味してません。悪しからず。
上のクエリを投げた結果が次です。
| 記事ID(id) | 似ている記事(related_articles) |
|---|---|
| 2 | [10022,282,7422,10402] |
| 4 | [3764,4884,664,10364] |
| 6 | [7146] |
| ・・・ | ・・・ |
出ました！
各記事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上で試させていただきました。毎度お世話になります。
そして、申し遅れました。私ビッグデータ解析部吉村と申します。
またの機会に！
