MySQL / PHP：通过标签/分类法查找相似/相关项目

Question

我有一个城市表，长这样。

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

我有一个标签表，长这样。

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

和一个cities_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指数，但我不确定如何最好地实现它。

- Tom

---

为什么不先从一些简单的东西开始，比如计算城市匹配的标签总数，然后根据匹配标签数量找到最接近的城市呢？ - Maximus2012

可以看一下这个链接：https://dev59.com/b03Sa4cB1Zd3GeqPu2QK - Kanishka Ganguly

@Panique：标签的名称并不重要。对于这个例子，它本可以是AAA、BBB和CCC。 - Martijn

“紧密相关”如何定义？是1/(标签数量的交集)吗？ - Aaron Miller

@Tom，请查看我更新的 http://sqlfiddle.com/#!2/e7456/1 Jaccard 相似度 fiddle。 - M Khalid Junaid

Answer 1

你的问题是如何计算哪些城市最相关？例如，如果我正在查看城市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为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 )

它将获取除巴黎外所有具有与巴黎相同标签的城市。

这是您的Fiddle。

在阅读关于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 intersect B = {D,E}= 2

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

JS=2/9 =0.2222222222222222

现在转向您的情况。

巴黎有标签id 1,3，因此我们将其集合并称为P = {欧洲，河流}

伦敦有标签id 1,3，因此我们将其集合并称为L = {欧洲，河流}

纽约有标签id 2,3，因此我们将其集合并称为NW = {北美，河流}

计算巴黎与伦敦的Jaccard相似度JSPL = P交L / P并L，JSPL = 2/2 = 1

计算巴黎与纽约的Jaccard相似度JSPNW = P交NW / P并NW，JSPNW = 1/3 = 0.3333333333

目前查询已经能够计算出完美的Jaccard指数，您可以在下面的fiddle示例中查看。

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相似性演示

- M Khalid Junaid

---

@TheGunner，考虑到您的标签不经常更改，使用一些缓存可能会很有用。 - Dzhuneyt

你必须在所有派生表的最顶层父级中添加 LIMIT，就像在查询的末尾添加 LIMIT 10 一样。 - M Khalid Junaid

q.sets + q.parisset 和 q.sets - q.parisset 到底是如何工作的？它们不是将逗号分隔的字符串转换为整数并返回它们的和吗？ - Stas Bichenko

我非常确定这个解决方案不可能起作用。我使用了不同的数据制作了一个Fiddle：http://sqlfiddle.com/#!2/ad2a9/1。我通过将“1”更改为“2”，将“3”更改为“8”，将“2”更改为“5”来改变`tag_id`。结果是不同的，尽管城市-标签关系保持不变（因为在`q.sets - q.parisset和q.sets + q.parisset期间，sets和parissets被转换为整数（因此仅保留第一个逗号前面的部分：2, 2和5, 8）。原始的Fiddle能够工作是巧合。这不是一个可行的答案。 - Stas Bichenko

如何使 q.sets - q.parisset 等于 intersect？在你的结果中，#1 和 #2 的交集必须为 2 而不是 0。我认为这个答案是错误的。 - Pars

Answer 2

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指数后：

在维基百科上更多地阅读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 |
+----------+---------------+

< p > < em > 再次编辑查询添加注释，并考虑当前城市的标签是所选城市标签的子集

- Travis Hegner

---

我的Jaccard指数不正确。我会在今天稍后进行编辑，以实现正确的实现。 - Travis Hegner

请查看新的查询，该查询实现了真正的Jaccard指数。 - Travis Hegner

Answer 3

很抱歉，但我认为没有一个答案是完全正确的。我结合了每个答案的优点并将它们整合在一起形成了自己的答案：

• @m-khalid-junaid 的 Jaccard指数 解释非常有趣和正确，但使用 (q.sets + q.parisset) AS union 和 (q.sets - q.parisset) AS intersect 实现是非常错误的。
• @n-lx 的版本是正确的，但需要Jaccard指数，这是非常重要的，如果一个城市有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指数是:

Florence: 1.000 (2/2)

London: 0.666 (2/3)

New York: 0.333 (1/3)

São Paulo: 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 Fidde

- Charles Cavalcante

Answer 4

这个查询没有任何花哨的函数或子查询，但速度很快。请确保cities.id、cities_tags.id、cities_tags.city_id和cities_tags.tag_id有索引。

该查询返回一个结果，包含：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。

- nl-x

---

它将返回重复项以及需要匹配的城市名称。 - M Khalid Junaid

@dianuj我已在查询中添加了注释以解决重复问题。（将“！=”更改为“>”）。而您的错误是：城市名称不匹配。 - nl-x

Answer 5

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

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

我尝试的是这样的：

// 查找城市名称：
从城市中获取城市名称（子查询）作为匹配计数，其中matchCount > 0

// 子查询：
选择城市具有的标签数量，该标签数量也由（子子查询）拥有

// 子子查询：
选择原始名称所具有的标签的ID

- Martijn