Groonga Advent Calendar 2015の22日目の記事です。
はじめに
Groongaでのタグ検索と表記揺れとの戦い at Groonga Meatup 2015 - CreateField Blog こちらの発表では、編集距離ベースで誤字脱字ぽい類似タグを抽出して表記揺れを抽出する話をしました。
しかしながら、編集距離ベースでは文字情報しか見ていないので、文字数が少ないものや略語などの類似タグを抽出することはできません。
そこで、他のタグとの関連性で類似度を抽出するためGroongaのカラムでjaccard係数を計算できるプラグインを作りました。
Jaccard係数とは
Jaccard係数とは、2つの集合の類似度を測る尺度です。類似ドキュメントやレコメンドなどに利用されます。 Jaccard係数は以下の式で表せられます。
J(A,B) = A∩B / A∪B
Jaccard index - Wikipedia, the free encyclopedia
A∩BはAND集合、すなわちAとBの要素のうち重なっている集合を示します。
A∪BはOR集合、すなわちAとBの要素を足し合わせた集合を示します。
たとえば、
A:{'商品A', '商品B', '商品C'}
B:{'商品A', '商品C', '商品D'}
A∩B:{'商品A', '商品C'}
A∪B:{'商品A', '商品B', '商品C', '商品D'}
の場合、AとBのJaccard係数はA∩B/A∪B: 2/4 = 0.5となります。
column_similarityコマンド
Groongaのカラムのデータで類似度を計算できるコマンドです。現状Jaccard係数のみ実装されています。
たとえば、以下のようにUsersというテーブルにpurchase_historiesというベクターカラムがあるとします。
plugin_register commands/recommend
[[0,0.0,0.0],true]
table_create Users TABLE_HASH_KEY ShortText
[[0,0.0,0.0],true]
column_create Users purchase_histories COLUMN_VECTOR ShortText
[[0,0.0,0.0],true]
load --table Users
[
{
"_key": "Taro",
"purchase_histories": ["Product A", "Product B"]
},
{
"_key": "Jiro",
"purchase_histories": ["Product A", "Product B", "Product C"]
},
{
"_key": "Saburo",
"purchase_histories": ["Product D", "Product E", "Product F"]
},
{
"_key": "Shiro",
"purchase_histories": ["Product A", "Product C", "Product F"]
}
]
[[0,0.0,0.0],4]
この場合、Taroというユーザのpurchase_historiesと最も似たpurchase_historiesを持つユーザはJiroであることを抽出することができます。
column_similarity Users purchase_histories \
--key Taro --output_columns _key,_score,purchase_histories
[
[0,0.0,0.0],
[
[3],
[
["_key","ShortText"],
["_score","Int32"],
["purchase_histories","ShortText"]
],
[
"Jiro",
666,
["Product A","Product B","Product C"]
],
[
"Shiro",
250,
["Product A","Product C","Product F"]
],
[
"Saburo",
0,
["Product D","Product E","Product F"]
]
]
]
なお、現状_scoreはfloat出力できないため、便宜上1000倍されています。Groonga本体で小数出力ができるようになったら変更する予定です。
上記の例ではカラムは１つでしたが、複数のカラムを指定することも可能です。また、Groongaのスクリプト構文で検索した結果のみのjaccard similarityを計算することもできます。詳細はGitHubを参照してください。
今後について
テーブルの全レコードの類似度を計算するのは計算量がとても大きくなります。そこで、MinHash(b-bit MinHash, Odd Sketchesなど)と呼ばれる手法を使って高速にjaccard_similarityを推測できるコマンドを実装中です。
また、せっかくJaccard係数を実装するので簡単なレコメンド(ユーザベース協調フィルタリング)も試しに実装してみようと思っています。
