Существует ли эффективный способ кластеризации узлов в графе с использованием подобия Жаккара, чтобы в каждом кластере было не менее K узлов?
Сходство Жаккара между узлами i и j:
Пусть S будет множеством соседей i, а T будет множеством соседей j. Тогда сходство между i и j определяется как |(S ⋂ T)| / |(S ⋃ T)|.
Вы пробовали реализовать какой-то алгоритм самостоятельно?
Вычислите все попарные ненулевые подобия (т. е. когда они имеют хотя бы одного общего соседа; это делает набор кандидатов намного меньше квадратной матрицы).
Отсортируйте их по сходству и обработайте пары по убыванию сходства. Изначально каждый объект является своим кластером.
Когда A и B еще не находятся в одном кластере, и в любом кластере меньше k членов, соедините два кластера. Повторяйте, пока не будут обработаны все сходства.
Обратите внимание, что у вас все еще могут быть кластеры с менее чем k элементами. Например, если в вашем наборе данных всего менее k узлов или есть небольшие несвязанные подграфы и т. д.
Вам действительно следует принимать кластеры менее чем из k узлов, т. е. некластеризованные узлы. Почему все группируется? В реальных данных всегда будут выбросы и шум.
