php - MySQL / PHP：按标签/分类查找相似/相关项目

Question

我有一个像这样的城市表。

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

我有一个看起来像这样的标签表。

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

和一个 city_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），根据您提供的数据集，只有一件事需要关联，那就是城市之间的公共标签，所以共享公共标签的城市将是下面最接近的一个子查询，它找到共享公共标签的城市（除了提供用于查找其最近的城市）

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 或名称之一以找到最接近的城市 ID 或名称，在我的情况下，“巴黎”的 ID 为 1

 SELECT tag_id FROM `cities_tags` WHERE city_id=1

它将找到 paris 拥有的所有标签 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 相似度/索引时发现了一些东西来了解这些术语的实际含义让我们以这个例子为例，我们有两组 A 和 B

设置 A={A, B, C, D, E}

设置 B={I、H、G、F、E、D}

计算jaccard相似度的公式为JS=(A intersect B)/(A union B)

A 相交 B = {D,E}= 2

A 联合 B ={A, B, C, D, E,I, H, G, F} =9

JS=2/9 =0.2222222222222222

现在走向你的场景

Paris 的 tag_ids 为 1,3，所以我们制作了这个集合并调用我们的 Set P ={Europe,River}

伦敦的 tag_ids 为 1,3，所以我们制作了这个集合并调用我们的集合 L ={Europe,River}

纽约的 tag_ids 为 2,3，所以我们制作了这个集合并调用我们的 Set NW ={North America,River}

用伦敦计算 JS 巴黎 JSPL = P intersect L / P union L , JSPL = 2/2 = 1

计算 JS 巴黎与纽约 JSPNW = P intersect NW / P union NW ,JSPNW = 1/3 = 0.3333333333

这是迄今为止计算完美jaccard索引的查询，您可以看到下面的小提琴示例

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

在上面的查询中，我将结果集派生为两个子选择，以获取我的自定义计算别名

在此处输入图像描述

您可以在上面的查询中添加过滤器，而不是计算与自身的相似度

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 in子句和not city_id in子句中都将其设为变量。

如果我正确理解了 Jaccard 索引，那么它还会返回按“最密切相关”排序的值。我们示例中的结果如下所示：

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

编辑

更好地理解如何实现 Jaccard 索引：

在 wikipedia 上阅读了更多关于 Jaccard 索引的内容后，我想出了一个更好的方法来为我们的示例数据集实现查询。本质上，我们将独立地比较我们选择的城市与列表中的其他城市，并使用公共标签的数量除以两个城市之间选择的不同总标签的数量。

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 |
+----------+---------------+

再次编辑以向查询添加注释，并考虑当前城市的标签何时是所选城市标签的子集

score 4 · Accepted Answer

为时已晚，但我认为没有一个答案是完全正确的。我得到了每个人中最好的部分并将所有内容放在一起做出我自己的答案：

@m-khalid-junaid的Jaccard Index解释非常有趣和正确，但是and的实现是非常错误的。(q.sets + q.parisset) AS union(q.sets - q.parisset) AS intersect
@n-lx 的版本是这样的，但是需要 Jaccard Index，这很重要，如果一个城市有 2 个标签，并匹配另一个城市的两个标签和 3 个标签，结果将与另一个城市的匹配结果相同只有两个标签相同的城市。我认为完整的比赛是最相关的。

我的答案：

cities像这样的表。

| id | Name      |
| 1  | Paris     |
| 2  | Florence  |
| 3  | New York  |
| 4  | São Paulo |
| 5  | London    |

cities_tag像这样的表。

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

有了这个样本数据，Florence与 Paris完全匹配， New York匹配一个标签，São Paulo没有标签匹配，London匹配两个标签并有另一个标签。我认为这个样本的 Jaccard 指数是：

佛罗伦萨： 1.000 (2/2)

伦敦： 0.666 (2/3)

纽约： 0.333 (1/3)

圣保罗： 0.000 (0/3)

我的查询是这样的：

select jaccard.city, 
       jaccard.intersect, 
       jaccard.union, 
       jaccard.intersect/jaccard.union as 'jaccard index'
from 
(select
    c2.name as city
    ,count(ct2.tag_id) as 'intersect' 
    ,(select count(distinct ct3.tag_id) 
      from cities_tags ct3 
      where ct3.city_id in(c1.id, c2.id)) as 'union'
from
    cities as c1
    inner join cities as c2 on c1.id != c2.id
    left join cities_tags as ct1 on ct1.city_id = c1.id
    left join cities_tags as ct2 on ct2.city_id = c2.id and ct1.tag_id = ct2.tag_id
where c1.id = 1
group by c1.id, c2.id) as jaccard
order by jaccard.intersect/jaccard.union desc

SQL 语言

score 2 · Accepted Answer

这个查询没有任何花哨的功能，甚至没有子查询。它很快。只要确保 city.id、cities_tags.id、cities_tags.city_id 和 city_tags.tag_id 有一个索引。

查询返回一个结果，其中包含：city1、city2以及city1和 city2 共有的标签数量。

select
    c1.name as city1
    ,c2.name as city2
    ,count(ct2.tag_id) as match_count
from
    cities as c1
    inner join cities as c2 on
        c1.id != c2.id              -- change != into > if you dont want duplicates
    left join cities_tags as ct1 on -- use inner join to filter cities with no match
        ct1.city_id = c1.id
    left join cities_tags as ct2 on -- use inner join to filter cities with no match
        ct2.city_id = c2.id
        and ct1.tag_id = ct2.tag_id
group by
    c1.id
    ,c2.id
order by
    c1.id
    ,match_count desc
    ,c2.id

换成避免每个城市被退回两次!=。>这意味着一个城市将不再在第一列和第二列中出现一次。

如果您不想看到没有标签匹配的城市组合，请将两者更改为left join。inner join

score 1 · Accepted Answer

这可能是朝着正确方向的推动吗？

SELECT cities.name, ( 
                    SELECT cities.id FROM cities
                    JOIN cities_tags ON cities.id=cities_tags.city_id
                    WHERE tags.id IN(
                                     SELECT cities_tags.tag_id
                                     FROM cites_tags
                                     WHERE cities_tags.city_id=cites.id
                                     )
                    GROUP BY cities.id
                    HAVING count(*) > 0
                    ) as matchCount 
FROM cities
HAVING matchCount >0

我尝试的是这样的：

// 查找城市名称：
Get city.names (SUBQUERY) as matchCount FROM cities WHERE matchCount >0

// 子查询：
选择城市拥有的标签数量（SUBSUBQUERY）也有

// 子查询
选择原始名称具有的标签的 id

php - MySQL / PHP：按标签/分类查找相似/相关项目

5 回答 5

在职的

编辑

我的答案：

SQL 语言

Related

Reference