HivemallでMinhash!〜似てる記事を探し出そう。〜
こんにちは。俺やで。
前回の投稿に続き(間が空きましたが)、
ビッグデータに対応したHiveで使える機械学習ライブラリ、
「Hivemall」の使い方、第2弾となります。
今回はMinhashという手法について書きたいと思います。
※前回
【超入門】Hivemallで機械学習 〜Treasure Dataでロジスティック回帰編〜
しかし!
Hivemallは一言で言えば「機械学習ライブラリ」ではありますが、
Minhash、これ自体は機械学習の分野の言葉ではないです…
すみません。でもおもしろい考え方(手法?)なので!
よろしくお願いします。
■1. Minhashとは?
2つの集合の重なり度合いを推定する!
Jaccard係数という数字をご存知でしょうか。
「難しいそうな言葉出てきた」と思われるかもしれませんが、
そんなことないです。
Jaccard係数は「2つの集合がどれだけ重なっているか」を示す数字です。
図と式を見てください。
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を使って2つのWebサイトにアクセスしているユーザーの重なり度合いを見たい(マーケティングに活かしたい)、と思うことがあるわけです。クロス集計はデータ分析の基本ですよね。
その2つの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という有名なサンプルデータです。3行だけ見てみます。
記事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とか、そういうの除く)。
なので記事1と同じような内容の記事2を、記事1を読んだ人にレコメンドしてあげてもいいんじゃない?と考えることもできますよね。
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のレコードがありませんが、
“似た記事”がなかったよ!っていうことです。
(偶数番になってしまったのはたまたまです。)
しかしながら、これを使えば記事のレコメンドができるかもですね!
しかも投げるクエリも上の2つだけ!簡単です!万歳Hivemall!
〜追記〜
もうちょっと言いたかったこと、その1
まず、「minhashは機械学習の分野の話ではない」、と冒頭申し上げました。
じゃあ何なのか。
乱択アルゴリズムの守備範囲になります。
データをぜーんぶ見なくても、サンプリングしたデータからその”ぜーんぶ”がわかること。
これが乱択アルゴリズムだと僕は理解しています。
間違ってたらごめんなさい。
HyperLogLogとかおもしろいです。(名前がすでにおもしろい)
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
もうちょっと言いたかったこと、その2
今回「minhashによるレコメンド」を題材に取り上げましたが、
レコメンド手法としては正直微妙です。。
minhashを紹介するのにわかりやすい例がないとなーと思い、レコメンドを取り上げた次第です。
Hivemallでちゃんとレコメンドしたいのであれば、
MatrixFactorization
がよいでしょう。
Hivemallの開発者の方が書いておられる記事になります。
HivemallでMatrix Factorization
もうちょっと言いたかったこと、その3
minhash自体は20世紀の間には確立されていたらしく、
最近ではminhashの進化版、b-bit minhashなるものがあります。
興味ある方は見てみてください。基本的な考え方はminhashと大差ないです。
b-Bit Minwise Hashing
以上です!
なお今回もTreasureData上で試させていただきました。毎度お世話になります。
そして、申し遅れました。私ビッグデータ解析部吉村と申します。
またの機会に!

関連記事
-
-
D3.jsとその活用事例について
D3.jsとは? D3とは「Data Driven Document」の略で、データに基づいてドキュメントを操作するための JavaScript ライブラリです。 ご存知の方も多いと思いますが、ちょっとだけD3.jsの基本的な使い方、そして弊社プラットフォームでの利用についてご紹介したいと思います。 …
-
-
Treasure Dataで大規模なマスタデータを扱う際にはtimeカラムインデックスを活用しよう
DACではTreasure Dataを利用して各種データの蓄積や集計を行っています。Treasure Dataは時系列のデータを扱うのに特にすぐれたアーキテクチャなのですが、セグメントIDとユーザーIDの組み合わせといった大量のマスタデータを利用した計算にも利用することもできます。そのような場合にt …
-
-
【入門編】TreasureDataでWEBログ分析をしてみた
この記事は Treasure Data Advent Calendar 2015 – Qiita の24日目の記事です。 こんにちは。 今回はWEBログの集計や解析をする際によく使うHiveQLのクエリと、UDF(User Defined Functions)について実際の集計クエリを使 …
-
-
Google BigQuery / Tableauを使ってみた
TableauからGoogle BigQueryへ接続してみました。 弊社で利用しているTreasureDataからデータ出力してBigQueryへロード、Tableauから接続まで実際に行った手順について記載します。 TreasureDataからAmazonS3へデータ出力 まず、データが蓄積され …
-
-
PyStanによるはじめてのマルコフ連鎖モンテカルロ法
はじめに こんにちは。システム開発部の中村です。 社内で行っている『データ解析のための統計モデリング入門』(所謂緑本)の輪読会に参加した所、 大変わかりやすい本だったものの、Macユーザには悲しい事に実装サンプルがWinBUGSだったため、 9章の一般化線形モデルのベイズ推定によるアプローチをPyt …
-
-
GoogleAppsScriptとTreasureData REST APIを使ってサーバレスにTwitterのデータを取得
またまたTreasureDataネタです。 ただ、今回はクエリ系のネタではなく、GoogleAppsScriptとTreasureDataのREST APIを使ってTwitterのデータをTreasureDataに入れてみたので、その方法を紹介したいと思います。 はじめに ログデータだけではなく、公 …
-
-
【Hivemall入門】RandomForestで毒キノコ推定モデルを作る
こんにちは。俺やで。 今回も前回から間が空いてしましたが、ビッグデータに対応したHiveで使える機械学習ライブラリ、 Hivemallの使い方について、書かせていただければと思います。 なお今回はQiitaのTreasure Data / Advent Calender 2015の12/3日分として …
-
-
いま必要なのは「アナリティクスアプローチ」
こんにちは。 ビッグデータ解析部のakiです。 解析部で、Markezineでの連載をはじめましたのでご紹介です。 いま必要なのは「アナリティクスアプローチ」、ビッグデータ活用の課題とこれから (http://markezine.jp/article/detail/21293) マーケターのかた向け …
-
-
【超入門】Hivemallで機械学習 〜Treasure Dataでロジスティック回帰編〜
こんにちは。俺やで。 ビッグデータとかデータサイエンティストとかいう言葉が未だブームですね。 (「データサイエンティスト」は下火か。) ビッグデータ扱えるエンジニアも、 統計解析ができるアナリストも、 どっちもできるスーパーマンも世の中にはたくさんいますが、 ビッグデータも統計解析も扱えるインフラは …
-
-
Tableau 9.2で郵便番号の特性を地図で可視化してみる
Tableau 9.2から郵便番号地図が表示可能に 弊社ではデータ分析ツールのTableauを利用しています。オーディエンスデータの重複を分析したり、デモグラフィック属性を表示したりするなどデータの可視化に役立ちますTableauでは9.2から日本の郵便番号を用いて地図を可視化できるようになりました …