php - MySQL / PHP: タグ / タクソノミーで類似 / 関連アイテムを検索

Question

私はこのような都市テーブルを持っています。

|id| Name    |
|1 | Paris   |
|2 | London  |
|3 | New York|

このようなタグテーブルがあります。

|id| tag            |
|1 | Europe         |
|2 | North America  |   
|3 | River          |

そして、citys_tags テーブル:

|id| city_id | tag_id |
|1 | 1       | 1      | 
|2 | 1       | 3      | 
|3 | 2       | 1      |
|4 | 2       | 3      | 
|5 | 3       | 2      |     
|6 | 3       | 3      |

最も関連性の高い都市を計算するにはどうすればよいですか? 例えば。都市 1 (パリ) を見ていたら、結果は次のようになります: ロンドン (2)、ニューヨーク (3)

Jaccard インデックスを見つけましたが、これを実装する最善の方法がわかりません。

score 18 · Accepted Answer

あなたは、どの都市が最も密接に関連しているかをどのように計算するのですか?について質問します。例えば。都市 1 (パリ) を見ていたら、結果は次のようになります: ロンドン (2)、ニューヨーク (3)提供されたデータセットに基づいて、関連するものは 1 つだけです。それは都市間の共通タグです。共通のタグを共有する都市が最も近いものになります。以下は、共通のタグを共有する都市 (最も近い都市を見つけるために提供されているものを除く) を見つけるサブクエリです。

SELECT * FROM `cities`  WHERE id IN (
SELECT city_id FROM `cities_tags` WHERE tag_id IN (
SELECT tag_id FROM `cities_tags` WHERE city_id=1) AND city_id !=1 )

働く

私の場合、「パリ」にはIDが1つあります

 SELECT tag_id FROM `cities_tags` WHERE city_id=1

パリが持っているすべてのタグIDが見つかります

SELECT city_id FROM `cities_tags` WHERE tag_id IN (
    SELECT tag_id FROM `cities_tags` WHERE city_id=1) AND city_id !=1 )

パリにもあるのと同じタグを持つパリを除くすべての都市を取得します

これがあなたのフィドルです

Jaccardの類似性/インデックスについて読んでいると、実際の用語が何であるかを理解するためのいくつかのものが見つかりました。この例を見てみましょう。2つのセットAとBがあります

A={A, B, C, D, E} を設定

B={I、H、G、F、E、D} を設定します。

ジャカード類似度を計算する式は、JS=(A 交差 B)/(A 結合 B) です。

A と B の交差 = {D,E}= 2

ユニオン B ={A, B, C, D, E,I, H, G, F} =9

JS=2/9 =0.2222222222222222

今、あなたのシナリオに向かってください

パリには tag_ids 1,3 があるので、これのセットを作成し、セット P ={Europe,River} と呼びます。

London には tag_ids 1,3 があるので、これのセットを作成し、Set L ={Europe,River} と呼びます。

New York には tag_ids 2,3 があるので、これのセットを作成し、Set NW ={North America,River} と呼びます。

JS パリをロンドンで計算する JSPL = P 交差 L / P 結合 L 、JSPL = 2/2 = 1

ニューヨークでの JS パリの計算 JSPNW = P 交差 NW / P 結合 NW ,JSPNW = 1/3 = 0.3333333333

以下のフィドルの例を見ることができる完璧なジャカードインデックスを計算するこれまでのクエリは次のとおりです

SELECT a.*, 
( (CASE WHEN a.`intersect` =0 THEN a.`union` ELSE a.`intersect` END ) /a.`union`) AS jaccard_index 
 FROM (
SELECT q.* ,(q.sets + q.parisset) AS `union` , 
(q.sets - q.parisset) AS `intersect`
FROM (
SELECT cities.`id`, cities.`name` , GROUP_CONCAT(tag_id SEPARATOR ',') sets ,
(SELECT  GROUP_CONCAT(tag_id SEPARATOR ',')  FROM `cities_tags` WHERE city_id= 1)AS parisset

FROM `cities_tags` 
LEFT JOIN `cities` ON (cities_tags.`city_id` = cities.`id`)
GROUP BY city_id ) q
) a ORDER BY jaccard_index DESC

上記のクエリでは、カスタム計算エイリアスを取得するために、結果セットを 2 つのサブセレクトに派生させました。

ここに画像の説明を入力

上記のクエリにフィルターを追加して、それ自体との類似性を計算しないようにすることができます

SELECT a.*, 
( (CASE WHEN a.`intersect` =0 THEN a.`union` ELSE a.`intersect` END ) /a.`union`) AS jaccard_index 
 FROM (
SELECT q.* ,(q.sets + q.parisset) AS `union` , 
(q.sets - q.parisset) AS `intersect`
FROM (
SELECT cities.`id`, cities.`name` , GROUP_CONCAT(tag_id SEPARATOR ',') sets ,
(SELECT  GROUP_CONCAT(tag_id SEPARATOR ',')  FROM `cities_tags` WHERE city_id= 1)AS parisset

FROM `cities_tags` 
LEFT JOIN `cities` ON (cities_tags.`city_id` = cities.`id`) WHERE  cities.`id` !=1
GROUP BY city_id ) q
) a ORDER BY jaccard_index DESC

この結果は、パリがロンドンと密接に関連しており、次にニューヨークと関連していることを示しています

Jaccard 類似性フィドル

score 7 · Accepted Answer

select c.name, cnt.val/(select count(*) from cities) as jaccard_index
from cities c 
inner join 
  (
  select city_id, count(*) as val 
  from cities_tags 
  where tag_id in (select tag_id from cities_tags where city_id=1) 
  and not city_id in (1)
  group by city_id
  ) as cnt 
on c.id=cnt.city_id
order by jaccard_index desc

このクエリはを静的に参照しているため、節と節のcity_id=1両方でそれを変数にする必要があります。where tag_id innot city_id in

Jaccard インデックスを正しく理解していれば、「最も関連性の高い」順に並べられた値も返されます。この例の結果は次のようになります。

|name      |jaccard_index  |
|London    |0.6667         |
|New York  |0.3333         |

編集

Jaccard インデックスの実装方法をよりよく理解すると、次のようになります。

Jaccard インデックスについてウィキペディアでもう少し読んだ後、サンプルデータセットのクエリを実装するより良い方法を思いつきました。基本的に、選択した都市をリスト内の他の都市と個別に比較し、2 つの都市間で選択された個別の合計タグの数で割った共通タグの数を使用します。

select c.name, 
  case -- when this city's tags are a subset of the chosen city's tags
    when not_in.cnt is null 
  then -- then the union count is the chosen city's tag count
    intersection.cnt/(select count(tag_id) from cities_tags where city_id=1) 
  else -- otherwise the union count is the chosen city's tag count plus everything not in the chosen city's tag list
    intersection.cnt/(not_in.cnt+(select count(tag_id) from cities_tags where city_id=1)) 
  end as jaccard_index
  -- Jaccard index is defined as the size of the intersection of a dataset, divided by the size of the union of a dataset
from cities c 
inner join 
  (
    --  select the count of tags for each city that match our chosen city
    select city_id, count(*) as cnt 
    from cities_tags 
    where tag_id in (select tag_id from cities_tags where city_id=1) 
    and city_id!=1
    group by city_id
  ) as intersection
on c.id=intersection.city_id
left join
  (
    -- select the count of tags for each city that are not in our chosen city's tag list
    select city_id, count(tag_id) as cnt
    from cities_tags
    where city_id!=1
    and not tag_id in (select tag_id from cities_tags where city_id=1)
    group by city_id
  ) as not_in
on c.id=not_in.city_id
order by jaccard_index desc

クエリは少し長く、どの程度スケーリングされるかはわかりませんが、質問で要求されているように、真の Jaccard インデックスを実装しています。新しいクエリの結果は次のとおりです。

+----------+---------------+
| name     | jaccard_index |
+----------+---------------+
| London   |        1.0000 |
| New York |        0.3333 |
+----------+---------------+

再度編集してクエリにコメントを追加し、現在の都市のタグが選択した都市のタグのサブセットである場合を考慮します

php - MySQL / PHP: タグ / タクソノミーで類似 / 関連アイテムを検索

5 に答える 5

働く

編集

Related

Reference