MySQL / PHP: Find similar / related items by tag /

Question

I have a cities table which looks like this.

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

I have a tags table which looks like this.

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

and a cities_tags table:

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

How do I calculate which are the most closely related city? For example. If I were looking at city 1 (Paris), the results should be: London (2), New York (3)

I have found the Jaccard index but I'm unsure as how best to implement this.

Answer 1

This query is without any fancy functions or even sub queries. It is fast. Just make sure cities.id, cities_tags.id, cities_tags.city_id and cities_tags.tag_id have an index.

The queries returns a result containing: city1, city2 and the count of how many tags city1 and city2 have in common.

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

Change != into > to avoid each city to be returned twice. Meaning a city will then no longer appears once in the first column as well as once in the second column.

Change the two left join into inner join if you don't want to see the city combinations that have no tag matches.

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

This query is statically referring to city_id=1, so you'll have to make that a variable in both the where tag_id in clause, and the not city_id in clause.

If I understood the Jaccard index properly, then it also returns that value ordered by the 'most closely related'. The results in our example look like this:

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

---

Edit

With a better understanding of how to implement Jaccard Index:

After reading a bit more on wikipedia about the Jaccard Index, I've come up with a better way implement a query for our example dataset. Essentially, we will be comparing our chosen city with each other city in the list independently, and using the count of common tags divided by the count of distinct total tags selected between the two cities.

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

The query is a bit lengthy, and I don't know how well it will scale, but it does implement a true Jaccard Index, as requested in the question. Here are the results with the new query:

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

Edited again to add comments to the query, and take into account when the current city's tags are a subset of the chosen city's tags

Answer 3

You question about How do I calculate which are the most closely related city? For example. If I were looking at city 1 (Paris), the results should be: London (2), New York (3) and based on your provided data set there is only one thing to relate that is the common tags between the cities so the cities which shares the common tags would be the closest one below is the subquery which finds the cities (other than which is provided to find its closest cities) that shares the common tags

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 )

Working

I assume you will input one of the city id or name to find their closest one in my case "Paris" has the id one

 SELECT tag_id FROM `cities_tags` WHERE city_id=1

It will find all the tags id which paris has then

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

It will fetch all the cities except paris that has the some same tags that paris also has

Here is your Fiddle

While reading about the Jaccard similarity/index found some stuff to understand about the what actualy the terms is lets take this example we have two sets A & B

Set A={A, B, C, D, E}

Set B={I, H, G, F, E, D}

Formula to calculate the jaccard similarity is 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

Now move towards your scenario

Paris has the tag_ids 1,3 so we make the set of this and call our Set P ={Europe,River}

London has the tag_ids 1,3 so we make the set of this and call our Set L ={Europe,River}

New York has the tag_ids 2,3 so we make the set of this and call our Set NW ={North America,River}

Calculting the JS Paris with London JSPL = P intersect L / P union L , JSPL = 2/2 = 1

Calculting the JS Paris with New York JSPNW = P intersect NW / P union NW ,JSPNW = 1/3 = 0.3333333333

Here is the query so far which calcluates the perfect jaccard index you can see the below fiddle example

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 

In above query i have the i have derived the result set to two subselects in order get my custom calculated aliases

You can add the filter in above query not to calculate the similarity with itself

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

So the result shows Paris is closely related to London and then related to New York

Jaccard Similarity Fiddle

Answer 4

Too late, but I think that none of answers are fully correct. I got the best part of each one and put all together to make my own answer:

• The Jaccard Index explanaiton of @m-khalid-junaid is very interesting and correct, but the implementation of (q.sets + q.parisset) AS union and (q.sets - q.parisset) AS intersect is very wrong.
• The version of @n-lx is the way, but needs the Jaccard Index, this is very important, if a city have 2 tags and matches two tags of another city with 3 tags, the result will be the same of the matches on another city with only the same two tags. I think the full matches is most related.

My answer:

cities table like this.

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

cities_tag table like this.

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

With this sample data, Florence have a full matches with Paris, New York matches one tag, São Paulo have no tags matches and London matches two tags and have another one. I think the Jaccard Index of this sample is:

Florence: 1.000 (2/2)

London: 0.666 (2/3)

New York: 0.333 (1/3)

São Paulo: 0.000 (0/3)

My query is like this:

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

Answer 5

Could this be a push in the right direction?

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

What I tried was this:

// Find the citynames:
Get city.names (SUBQUERY) as matchCount FROM cities WHERE matchCount >0

// the subquery:
select the amount of tags cities have which (SUBSUBQUERY) also has

// the subsubquery
select the id of the tags the original name has