Вопрос или проблема
Я ищу алгоритм кластеризации для целей объединения информации о маршрутизации.
Предположим, у нас есть следующие множества:
A={1,2,3,4,5}
B={2,3,4,6}
C={3,4,7,8}
D={8,9,10,11}
Если мы хотим создать 3 группы, вы могли бы составить различные комбинации ({1A;2B;3CD},{1A;2BC;3D} и т.д.). Если мы рассматриваем перекрытие элементов в качестве метрики, что-то вроде 1A, 2B и 3CD будет иметь оценку 2, так как только один элемент (8) перекрывается между C и D. Однако, если мы сгруппируем 1AB, 2C, 3D, оценка будет 6, так как три элемента (2,3,4) перекрываются между A и B. Если мы определим 2 группы, вы можете получить даже выше: 1AB, 2CD с оценкой 7. Я также должен упомянуть, что начальные множества могут быть взвешены, представляя множественные появления множества, равные его весу. Выход алгоритма предоставит таблицу назначений множеств индексу группы. Существует ли алгоритм, который может выполнить это эффективно (есть сотни миллионов записей для кластеризации).
Я изучил алгоритм Apriori, который, похоже, делает нечто подобное, но не предоставляет окончательные кластеры (только подсчет экземпляров для перекрытий, но не делает назначения; хотя я мог что-то неправильно понять). Другие аналогичные темы подошли к применению кластеризации k-средних на основе метрики расстояния перекрытия — однако это тоже кажется не совсем верным, так как это не говорит вам, какие элементы перекрываются (опять же, я могу что-то упускать). Кажется, что иерархическая (агломеративная) кластеризация была бы хорошим подходом в принципе, но опять же, непонятно, на какой метрике будет выполняться кластеризация (снова, поскольку перекрытия не содержат никакой информации об элементах в множествах).
Вы можете использовать любую технику кластеризации, определяя подходящую метрику расстояния. В случае данных множеств одной из распространенных метрик расстояния является Jaccard. Индекс Жаккара определяется как размер пересечения, делённый на размер объединения.
.
Ответ или решение
Теория
Кластеризация множеств на основе общих элементов является важной задачей в анализе данных, особенно когда речь идет о комбинировании информации, как, например, в маршрутизации или в других сферах, где множество данных может быть представлено в виде наборов. Основная цель заключается в объединении данных таким образом, чтобы максимизировать перекрытия — использование общих элементов в различных множеств. Это требует применения алгоритмов, способных учитывать такие характеристики данных, где расстояние/схожесть между множествами играет ключевую роль. Среди таких методов можно выделить агломеративную иерархическую кластеризацию и использование метрики Жаккара.
Метрика Жаккара является одним из стандартных способов измерения степени пересечения множеств. Она определяется как отношение размера пересечения множеств к размеру их объединения. Метрика Жаккара отлично подходит для оценки схожести между множествами, что может служить основой для кластеризации множеств.
Пример
Рассмотрим простейший пример, описанный в вашем вопросе, с множествами: A = {1, 2, 3, 4, 5}, B = {2, 3, 4, 6}, C = {3, 4, 7, 8}, и D = {8, 9, 10, 11}. Основная задача — определить оптимальное объединение этих множеств в заданное количество кластеров (например, 2 или 3 группы), таким образом, чтобы максимизировать общее количество пересекающихся элементов.
Если мы будем использовать метрику Жаккара, мы сможем рассчитать схожесть между каждыми двумя множествами. Например, J(A, B) будет равен 3 (число общих элементов {2, 3, 4}) деленное на 6 (уникальные элементы всех множеств {1, 2, 3, 4, 5, 6}), что дает 0.5. На основе этих значений мы можем приступить к иерархической кластеризации, начиная с самых похожих множеств.
Применение
Итак, как мы можем применять данные теоретические принципы на практике? В данном контексте иерархическая агломеративная кластеризация подойдет, т.к. она хорошо работает с разными метриками схожести и позволяет группировать элементы на основе их пересечений. Типичная стратегия включат в себя следующие шаги:
-
Задание матрицы расстояний: Вычислить матрицу расстояний между всеми парами множеств, используя метрику Жаккара.
-
Старт агломеративной кластеризации: Начать с каждого множества в его собственном кластере и последовательно объединять пары кластеров, для которых расстояние минимально. Оценка группировок ведется по изменению общего числа пересечений.
-
Подбор оптимального числа кластеров: Можно использовать кросс-валидацию для проверки качества модели на разных уровнях кластеризации. N-мерность и время выполнения следует учитывать, особенно на больших данных.
-
Построение дендрограммы: Это наглядное отображение процесса кластеризации, которое позволяет определить наиболее удачные точки разреза, т.е. определения числа групп.
Следует также учесть, что при работе с такими методами на больших наборах данных важно оптимизировать выполнение, например, используя распараллеливание вычислений. В случае веса множеств, что влияет на мультипликативность их присутствия, требуется хотя бы линейное взвешивание пересечений.
Заключение
Хотя сходные алгоритмы, такие как Apriori, подходят для обнаружения частых множеств, их сфера применения отличается от нашей задачи, специализированной на конечном этапе — ассоциации множеств. Иерархическая кластеризация с использованием метрики Жаккара предлагает сбалансированное и теоретически обоснованное решение задачи группировки множеств на основе общего элемента.