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


こんにちは。俺やで。

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

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

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

■1. Minhashとは?

2つの集合の重なり度合いを推定する!

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

Hivemall_Minhash_pic1

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係数を推定してるかお話します。
というかお話させてください!
ここが書きたかったんですから。
まずはさきほどの図を再掲です。
Hivemall_Minhash_pic1
ここで、
・Aの要素数をa
・Bの要素数をb
・A∩Bの要素数をc
とします。(変数の置き方にセンスがない)
とすると、Jaccard係数は次の計算式になります。
Hivemall_Minhash_Jaccard_Formula

分母は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の中に含まれている確率に等しいです。
つまり、
Hivemall_minhash_picture3

なんと!
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″とオプションつけました。

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

・結果 テーブル名「 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レコードになるわけですね。

集計する

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

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)
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上で試させていただきました。毎度お世話になります。

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

またの機会に!


DACエンジニア採用情報

  関連記事

data-tenki
気象予報士とビッグデータ解析の意外な関係

DACから気象予報士が誕生しました ビッグデータ解析部のMikeです。 2015年1月の気象予報士試験に合格し、めでたく4月からアドテク業界ただ一人(本当?)の気象予報士となりました 。 そんなわけで、今回は気象予報士とビッグデータ解析の関係についてお話したいと思います。 なぜ気象予報士を目指したか …

no image
Treasure Dataで長期間の集計

プラットフォーム・ワン T氏です。プラットフォーム・ワンでは、DSPのMarketOneとSSPのYIELD ONE提供しています。 MarketOneやYIELD ONEのログを調査する場合にTreasure Dataを使うことがあります。Treasure Dataでは大量のデータに対してHive …

image1
トレジャーデータの新機能「Data Connector」でクライアントレスなビッグデータ連携を実現する

トレジャーデータは、スキーマレスな大量のデータ(ビッグデータ)をパブリッククラウド上に保管して集計や抽出をするためのサービスなのですが、他システムからの連携データをトレジャーデータのテーブルに格納するまでが一苦労でした。 他システムとの外部連携を行う場合、一般的にローカルサーバー内のストレージを外部 …

bigdata
HyperLoglogでcount distinctを速くする

こんにちは。俺やで。 HyperLoglogについて書きます。おもしろいです。名前が。 ■1. HyperLoglogとは? count distinctを速くするアルゴリズム 以前、Minhashについて書きました。 (Treasure Dataさんのブログにも載せていただきました。ありがとうござ …

tf
ディープラーニングで「顔が似ているAKB48のメンバーを教えてくれるbot」を構築

概要 こんにちは、システム開発部の中村です。 今回は、Facebook Messenger APIを利用して、 画像をアップロードすると、似ているAKB48のメンバーを教えてくれるbotを実装しました。 尚、ディープラーニングやTensorFlowそのものの解説というより、 「エンジンとしてディープ …

chain
PyStanによるはじめてのマルコフ連鎖モンテカルロ法

はじめに こんにちは。システム開発部の中村です。 社内で行っている『データ解析のための統計モデリング入門』(所謂緑本)の輪読会に参加した所、 大変わかりやすい本だったものの、Macユーザには悲しい事に実装サンプルがWinBUGSだったため、 9章の一般化線形モデルのベイズ推定によるアプローチをPyt …

【超入門】Hivemallで機械学習_サムネイル
【超入門】Hivemallで機械学習 〜Treasure Dataでロジスティック回帰編〜

こんにちは。俺やで。 ビッグデータとかデータサイエンティストとかいう言葉が未だブームですね。 (「データサイエンティスト」は下火か。) ビッグデータ扱えるエンジニアも、 統計解析ができるアナリストも、 どっちもできるスーパーマンも世の中にはたくさんいますが、 ビッグデータも統計解析も扱えるインフラは …

Screen Shot 2014-11-17 at 9.33.19 PM
Amazon ElastiCache/Redisのパフォーマンス確認

はじめに こんにちは、AudienceOne開発部です。AudienceOne開発部ではいわゆるビッグデータと呼ばれる大量のデータをアドホックあるいは定常的に日々ETLだの集合演算だのをする一方で、様々な大規模データ処理ソリューションを継続的に検証しております。 本記事は、その中でもユーザが保持して …

toadstool
【Hivemall入門】RandomForestで毒キノコ推定モデルを作る

こんにちは。俺やで。 今回も前回から間が空いてしましたが、ビッグデータに対応したHiveで使える機械学習ライブラリ、 Hivemallの使い方について、書かせていただければと思います。 なお今回はQiitaのTreasure Data / Advent Calender 2015の12/3日分として …

heatmap
巨大データベースのスケールアップと引越作業

はじめに ビッグデータ解析部でオーディエンスデータ解析基盤の開発、運用を担当している Mike です。 弊社ではインターネット広告配信ログをはじめとする「ビッグデータ」と呼ぶにふさわしいデータボリュームを扱うオーディエンスデータ解析基盤を構築しています。今秋、そのうちの1構成要素である、データサイズ …