類似度計算と転置Indexとb-Bit Minwise Hashing

Recommend Engineでの類似度計算

RecommendEngineを作る時の話。アイテム間の相関を計算する為にユーザーの購買データからJaccard係数やCos類似度を求める手法が一般的です(アイテム×ユーザーTableと、アイテム×アイテム相関Tableが必要)。しかしアイテムの個数(N)×ユーザー数(M)の行列を作り、Nの中から2つのアイテムを取り出してそれぞれの係数や類似度を求め、それを個数分繰り返していたら行列が大きくなる程計算が大変になります。特にアイテムの購買という行為がほとんど発生しないので、購買のベクトルがほとんど0となる疎ベクトルが作られて効率が悪く感じられます。一時期はこれを回避する為にベクトル数を減らす(購買データが多いユーザーに超超限定する)事で回避していたんですが、ユーザーが偏るしデータも少なくなってしまう事を問題として認識していました。そこでデータ数を減らすよりもっと色んな方法あるっしょって事で調べてみました。

レコメンドにおける類似度計算その傾向と対策 #DSIRNLP 第4回 2013.9.1 // Speaker Deck
転置Indexを使う手法。特定のアイテムAを買ったUser一覧をIndexから引き、User一覧が買った商品一覧を引いて来てアイテムA以外の共起回数を計算する。この方法では共起回数の計算はそこまで大変ではなく、アイテム数とユーザー数の両方が増えても処理時間への影響が小さい(らしい)です。

b-Bit Minwise Hashing
b-bit miniwise Hashingという手法。ハッシュ関数(MurmurHash3等)を使って2つのアイテムの全ベクトル要素に対して適用し、それぞれの最小の値が一致する確率はJaccard係数と等しいという理論から導きだされます。ハッシュ関数だけ共有すれば分散処理も行ける優れもの。b-bitというのは保存するbit数の事でMurmurHash3の下位1bitで良いようです。ただしハッシュ値の衝突が生じるので衝突確率を補正した値をJaccard係数とするようです。

自分が詳しく把握していなかったのは上の2つなんですが、他に調べていて手法が見つかったらここに纏めて行こうと思います。