MYSQL&PHPにて、類似するタグ付けがなされているものを見つけたい

Question

レコメンドエンジンほどまで行かず、単にとある項目と、それに対するタグが複数あるだけのイメージのものがあり、どういったDB設計にしようか、またどのように参照したら良いのかで躓いています。

取り急ぎ合計２カラムだけのデータが大量にあるようなテーブルにしようかと思うのですが、

項目１ タグ１,タグ２,タグ３,タグ４,タグ５,タグ６,タグ７
項目２ タグ４,タグ８,タグ９,タグ１０,タグ１１,タグ１２
項目３ タグ１,タグ２,タグ３

この場合項目１に一番近いものとして項目３が引っ張ってこれるようにしたいのですが、どのようなコードにしたら良いのでしょうか。

Answer 1

要件にもよりますが、自分なら正規化してタグテーブルと関連テーブルに分けますかね。

タグテーブル （id, name)
関連テーブル （項目id, タグid)

そのうえで関連性を見つけるときは、項目idが1のタグと同じタグが多い項目idを探す感じでしょうか
以下イメージですが...

select 項目id, count(*) from 関連テーブル
where タグid in (select タグid from 関連テーブル where 項目id = 1) 
group by 項目id
order by count(*) desc
limit 5;

※ただし、データ量が多いなら、もう少し工夫しないと遅そうですが...

Comments

[cutter]

ありがとう御座います。
一般的なサーバーで、レコードが百万件以上ですと、なかなか難しそうでしょうか。

[popobot]

関係テーブルが100万ですか？　項目テーブルが100万ですか？
関係テーブルが100万ぐらいならそんなにでもないかもしれません。レコードのサイズも小さいのでデータ量もそんなには行かないですし。
ただフルスキャンなので、他の処理との兼ね合いもあるので、全然平気というレベルではないかと。必要があれば検証してみてください。
このデータを頻繁に使うのであれば、週次バッチで作っておくのもありかもしれませんね。頻繁に変わるものでもなので、リアルタイム性はそんなに必要ないのならですが。

[cutter]

週次バッチ・・・なるほど、ありがとう御座います！

[cutter]

ちなみに何故テーブルを分けるのでしょうか。１レコードに１タグの方が扱いやすいからでしょうか。

[popobot]

そうですね。検索や集計しやすいからですね。
以下にタグ2が含まれるかどうかは"タグ2,"でlike検索すればわかりますが、明らかにidで検索したほうが早いですね。
タグ１,タグ２,タグ３,タグ４,タグ５,タグ６,タグ７

Answer 2

すごく単純な方法だと、比較する２つの同じ長さの配列のドット積をだすことかな。
返り値が大きければ大きいほど共通項が多いので似ている。

<?php

// 項目１ タグ１,タグ２,タグ３,タグ４,タグ５,タグ６,タグ７
$item1 = [1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0];
// 項目２ タグ４,タグ８,タグ９,タグ１０,タグ１１,タグ１２
$item2 = [0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1];
// 項目３ タグ１,タグ２,タグ３
$item3 = [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0];


echo array_sum(array_map(function($a,$b) { return $a * $b; }, $item1, $item2));
echo array_sum(array_map(function($a,$b) { return $a * $b; }, $item1, $item3));

Comments

[退会済みユーザー]

もし自分がやるならPythonとnumpyを使用してバッチで類似度を算出、DBに保存しますかね。性能的にも精度的にも高いので。

[cutter]

ありがとう御座います。そこまで高い精度でなくても良いのですが、教えて頂いたスクリプトでも制度はそこそこ大丈夫そうでしょうか。
また、レコードが１００万件などですとやはり重くなってきますでしょうか。。

[退会済みユーザー]

100万件をこのphpコードでやるのは速度的な問題でかなりつらいです。重いどころか終わらないかも。

Answer 3

基本方針は icchii様と同様（「正規化してタグテーブルと関連テーブルに分け」る）ですが、
関連性の計算にはJaccard係数を使用するのが良いでしょう。

例えば以下のように"関連テーブル"を定義した場合、

CREATE TABLE relations (
  item_id int,
  tag_id int,

  PRIMARY KEY (item_id, tag_id),
  UNIQUE INDEX (tag_id, item_id)
);

項目1 に対する他の項目の Jaccard係数は以下のSQLで算出できます。

SELECT 
  item_id,
  dist_count,
  matched_count,
  (matched_count / (dist_count + 7 - matched_count)) jaccard_index # "7" は項目1 のタグ数
FROM (
  SELECT 
    dist.item_id, 
    COUNT(*) dist_count, 
    COUNT(org.item_id) matched_count
  FROM relations AS dist 
  LEFT OUTER JOIN relations AS org 
    ON dist.tag_id = org.tag_id AND org.item_id = 1
  WHERE dist.item_id <> 1 
  GROUP BY dist.item_id
) AS tmp 
ORDER BY jaccard_index DESC;

http://sqlfiddle.com/#!9/7ddec0/9

しかし、この方法ではデータ量が多くなると性能面で問題が生じる可能性があります。

実際、上のSQLの実行計画を見てみると、tmp一時テーブルに対する ORDER BY 句のところで filesort が発生しています。
http://sqlfiddle.com/#!9/7ddec0/10

「レコードが百万件以上」で問題になるか否かは性能要件とサーバ・ネットワーク等の性能しだいなので何とも言えませんが、
性能を改善したい場合は、 icchii様のコメントにあるように「バッチ処理で Jaccard係数を保存しておく」などの対策が必要になります。
※ 当然ですが、その場合はリアルタイムのデータではなくなります。

Comments

[cutter]

Jaccard係数・・・なるほど、ありがとう御座います。具体的なコードや情報をありがとう御座います。
調べてみようと思います。

Answer 4

既存ライブラリのソースを読んで勉強したほうが早いのでは。

レコメンドエンジン(協調フィルタリング)をPHP+Redisで実装 - Qiita

協調フィルタリング型レコメンドエンジン開発のため仕様について考える - Qiita

協調フィルタリングは枯れた技術

すでに枯れた技術らしいので、自分でシコシコやっても車輪の再発明すぎるかもしれない？

Answer 5

「近い」の概念が曖昧です。どういう条件を満たせば近いと判定されるのでしょうか？

項目４ タグ１,タグ２,タグ４
項目５ タグ１,タグ２,タグ３,タグ８

このような候補が合った場合、項目４は項目３に比べて近いでしょうか？
また項目５は項目３と一致するタグの数は同じですが、タグの数という意味ではより項目１に近く、異なるタグがあるという意味では遠いように思います。

単純に一致するタグが多いものという条件でいいなら(この場合項目３と項目５は共に一致するタグの数が３なので同じ近さということに成ります)、タグ１を保有する項目に＋１、タグ２を保有する項目に＋１....タグ7を保有する項目に＋１と集計して、値が最大のものを抜き出すようにコードを書けば良いと思います。

Comments

[cutter]

わかりづらく申し訳ありません。
より多くのタグが重複しているもの、ですので、項目４も同じポイントになります。
一番でなくても良いのですが、同じだけ重複している順といいますか、レコメンドエンジンのように類似しているものを並べられれば良いのですが・・・