MySQL/PHP: поиск похожих/связанных элементов по тегам/таксономии

У меня есть таблица городов, которая выглядит так.

|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 index, но я не уверен, как лучше всего это реализовать.

Ответ 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 )

В

Я предполагаю, что вы введете один из идентификаторов города или имя, чтобы найти их ближайший в моем случае "Париж" имеет идентификатор

 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 )

Он выберет все города, кроме paris, которые имеют те же теги, что и paris также имеет

Вот ваш Fiddle

В то время как чтение о сходстве/индексе Jaccard обнаружило некоторые вещи, чтобы понять, что действительно означает, что эти термины позволяют взять этот пример, мы имеем два набора 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, поэтому мы делаем набор этого и называем наш Set P = {Европа, река}

В Лондоне есть tag_ids 1,3, поэтому мы делаем набор этого и называем наш Установить L = {Европа, река}

В Нью-Йорке есть tag_ids 2,3, поэтому мы делаем набор этого и называем наш Установите NW = {Северная Америка, река}

Вычисление JS Paris с лондонским JSPL = P пересекает L/P union L, JSPL = 2/2 = 1

Вычисление JS Paris с New York JSPNW = P пересекает NW/P союз NW, JSPNW = 1/3 = 0,33333333333

Вот запрос до сих пор, который вычисляет идеальный индекс 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

Ответ 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 tags are a subset of the chosen city tags
    when not_in.cnt is null 
  then -- then the union count is the chosen city tag count
    intersection.cnt/(select count(tag_id) from cities_tags where city_id=1) 
  else -- otherwise the union count is the chosen city tag count plus everything not in the chosen city 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 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 |
+----------+---------------+

Отредактировано снова, чтобы добавить комментарии к запросу и принять во внимание, когда текущие метки города являются подмножеством выбранных городских тегов

Ответ 3

Этот запрос без каких-либо фантастических функций или даже подзапросов. Это быстро. Просто убедитесь, что city.id, cities_tags.id, cities_tags.city_id и cities_tags.tag_id имеют индекс.

Запросы возвращают результат, содержащий: city1, city2 и count количества тегов city1 и city2.. p >

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, если вы не хотите видеть комбинации городов, у которых нет совпадений с тегами.

Ответ 4

Может ли это быть нажатием в правильном направлении?

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

Я пробовал это:

//Найдите имена городов:
Получить city.names(SUBQUERY) как matchCount FROM города WHERE matchCount > 0

//подзапрос:
выберите количество тегов, которые имеют города (SUBSUBQUERY) и

//подсубъект
выберите идентификатор тегов, имя оригинала

Ответ 5

Слишком поздно, но я думаю, что ни один из ответов не является полностью правильным. Я получил лучшую часть каждого и собрал все вместе, чтобы ответить на мой вопрос:

Jaccard Index explanaiton of @m-khalid-junaid очень интересен и верен, но реализация (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      |

С этими образцовыми данными Флоренция имеет полные совпадения с Парижем, Нью-Йорк соответствует одному тегу Сан-Паулу имеют без тегов и Лондон соответствуют двум тегам и имеют другой. Я думаю, что индекс 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