Каким образом можно сделать рекурсивную функцию кластеризации объектов?

Question

[rshruslan]

Всем привет, у меня имеется такой объект с тегами где ключ - тег, а значение объект тегов (где ключ - тег, а значение это кол-во пересечения этих двух тегов)




Каким образом можно рекурсивно сделать так, чтобы искалась цепочка всех несовместных тегов (чтобы в группе каждые теги были не совместны никак) вот как пример 1 группа:



Был бы благодарен за псевдокод или хотя бы алгоритм.

Answer 1

[Wataru]

У вас есть граф, где вершины - теги, и есть ребра между ними. Если брать ребро там, где два тега не совместимы, то у вас задача поиска клик.

Во первых, тут есть неоднозначность. Может быть так что теги A,B,C попарно несовместимы, но заодно попарно несовместимы теги A,D,E - куда относить тег A, в какую группу?

Поиск самой большой группы - сложная задача тут нет простых алгоритмов. Полный перебор и всякое тому подобное тут работает.

Если надо просто достаточно большую группу найти, то можно делать жадно. Есть текущая "цепочка несовместимых тегов", есть какие-то уже откинутые теги, есть какие-то оставшиеся, вот берите любой из оставшихся и, если он подходит, то добавляйте его к несовместимым тегам. Если нет - отбрасывайте.

Еще есть Алгоритм Брона — Кербоша. Он перебирает все максимальные клики.

Comments

[rshruslan]

Во первых, тут есть неоднозначность. Может быть так что теги A,B,C попарно несовместимы, но заодно попарно несовместимы теги A,D,E - куда относить тег A, в какую группу?

В данном случае это отдельная группа будет.

Поиск самой большой группы - сложная задача тут нет простых алгоритмов. Полный перебор и всякое тому подобное тут работает.

Поиск самой большой группы - не нужно, нужно найти просто все группы несовместеных тегов.

[Wataru]

rshruslan, Ну вот Алгоритм Брона—Кербоша - это ваше. Там даже псевдокод есть.

[rshruslan]

Wataru, С моим типам данных тоже можно будет сделать?

[rshruslan]

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

[Wataru]

rshruslan, Конечно. Надо только уметь получать все вершины, не соедененные с данной в графе. Т.е. те теги, которые совместимы с данным.

Быстрее будет, кончено, сначала преобразовать ваш json в двумерный массив - матрицу смежности. Ну или получить для каждого тега список совместимых с ним. Еще быстрее будет работать, если перенумеровать все теги и строить граф на номерах вершин, а не на строках-тегах.

[rshruslan]

Wataru,

Ну или получить для каждого тега список совместимых с ним.

Есть такая возможность

[Wataru]

rshruslan,

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

Вы получите все максимальные наборы попарно несовместимых тегов. Такие, что к ним ничего добавить нельзя.

В вашем примере вы получите список "2005", "2016" и "XXXTENTACION". А так же множество других наборов. В моем примере с A,B,C,D,E вы получите и A,B,C и A,D,E.

[rshruslan]

Wataru, Вот мне как раз таки такое и надо.

Ну или получить для каждого тега список совместимых с ним.

И после этого уже работать с Алгоритмом Брона — Кербоша.? Правильно понимаю?

[Wataru]

rshruslan, Смотрите, алгоритм работает с графом. Граф, это вершины и ребра между ними. Я вам уже сказал, что вершины - это ваши теги. Ребро есть между двумя несовместимыми тегами, там где у вас 0 в вашем json.

В алгоритме по ссылке написано:

удаляя из candidates и not вершины, не СОЕДИНЕННЫЕ с v

Т.е. вам надо как-то пройтись по всем вершинам, не соединенным с данной. Ну или уметь узнавать, соединены ли 2 данные вершины. Не соединены = нет ребра = совместимы.

Ну или явно постройте граф и запускайте алгоритм, или везде где идет работа с графом переводите это в ваши термины с тегами и совместимостью.

[rshruslan]

Wataru,

Т.е. вам надо как-то пройтись по всем вершинам, не соединенным с данной. Ну или уметь узнавать, соединены ли 2 данные вершины. Не соединены = нет ребра = совместимы.

Если вершина - тег, и не соединенны это 0 в моем JSON, то это легко довольно таки найти.
Но так легко найти группу из 2 элементов, а если их 10...100..вот тут уже и возникают сложности)

[rshruslan]

Wataru, И вот как раз таки до этого я и дошел, а дальше уже прям сложности возникают)

[Wataru]

rshruslan, Ну пройдитесь по ссылке из ответа на алгоритм. Там что-то типа оптимизированного перебора. Да, для 100 тегов может работать долго, а может и нет, если клик не очень много.

[rshruslan]

Wataru, У меня их 30к в основной БД)