Скрытые отношения
Как можно найти все скрытые отношения среди тегов, извлеченных из нескольких документов?
Мой набор данных основан на наборе документов, каждый из которых я извлекаю из группы тегов, моя задача — найти связь между различными тегами из разных документов:
Doc_id tags
1 a, b, c
2 c, k, m
3 m, n, p
Результаты скрытого отношения должны быть такими:
a -> k using c
b -> m using c
a -> n using c, m (a->c->m->n)
и так далее.
Решение
Перевод в графики
То, что вы описываете своими тегами, — это график, узлами которого будут ваши теги и вершины вашего отношения. Вы можете прочитать следующую страницу википедии, если хотите:
https://en.wikipedia.org/wiki/Graph_theory
Вы также можете прочитать этот, более сфокусированный на реализации графа:
https://en.wikipedia.org/wiki/Graph_(abstract_data_type)
То, что вы хотите знать, это если два тега (в графе, два узла) связаны, но не напрямую (в одном классе, но не в соседях).
Реализация графиков
Вы можете написать его самостоятельно или найти хорошую реализацию, которая уже работает.
Вот этот, например: https://github.com/clue/graph (не знаю, действительно ли это хорошо, просто искал на github и взял первый результат).
Реализовать сам график может быть хорошей тренировкой. Я думаю, что ООП является лучшим подходом для этого.
Получение вашего ответа
Теперь вам нужно узнать, есть ли дорога между двумя тегами. В вашем примере каждый тег имеет дорогу к другому, но это не всегда так.
Поиск путей в графе не является тривиальным алгоритмом, и реализация может быть сложной. Есть много способов сделать это.
Наивным решением является сохранение массива уже посещенные узлы. Вы начинаете с узла, установите этот узел как посетил, и добавить всех своих соседей в массив доступные узлы. Затем вы делаете то же самое со всеми соседями. Когда вы встречаете уже посещенный узел, вы ничего не делаете (в противном случае вы получите бесконечный цикл). Когда алгоритм останавливается, у вас есть массив всех доступные теги из вашего начального тега.
Надеюсь, это поможет, я буду ждать вашего ответа, чтобы увидеть, если вам нужно что-то еще. Учтите, что этот алгоритм, вероятно, уже реализован в репозитории clue / graph, который я связал.
Другие решения
Других решений пока нет …