Вопрос или проблема
Существует ли способ выполнить кластеризацию на основе порога инерции, при котором инерция каждого кластера не может превышать определённую инерцию
Я пробовал иерархическую кластеризацию с полным связыванием и порогом расстояния, но не могу контролировать общие расстояния кластера.
Дополнительная информация:
Я использую предварительно вычисленную матрицу расстояний. Основная цель здесь – разделить пункты назначения между водителями, используя сеть дорог (матрица расстояний пунктов назначения)
Целевая функция K-средних заключается в минимизации общей дисперсии между всеми кластерами. Целевая функция иерархической кластеризации заключается в том, чтобы поддерживать расстояние между двумя кластерами в пределах заданного порога. Ваша целевая функция – удерживать дисперсию внутри кластеров в пределах порога. Это не укладывается ни в K-средние, ни в иерархическую.
Вам нужно использовать комбинацию K-средних и иерархической кластеризации.
Что вы можете сделать, так это запустить цикл от 2 до n_points. Установите количество кластеров как переменную. Запустите K-средние и оцените дисперсию во всех кластерах. Остановите цикл, когда дисперсия в любом кластере превысит порог.
Предупреждение: это вычислительно затратное упражнение. Вы можете попробовать запускать не с 2, а с более высокого номера
Ответ или решение
Кластеризация на основе максимальной инерции: управление дисперсией в кластерах
Вопрос, который вы поднимаете, касается важной и часто трудной задачи в области кластеризации данных — управления инерцией кластеров с целью не превышать заданный порог. Неправильная кластеризация может привести к неэффективному распределению объектов, что в вашем случае затрудняет распределение маршрутов между водителями на основе расстояний между пунктами назначения. Поэтому подход, который вы выбираете, должен быть достаточно гибким и одновременно оптимальным.
Основы инерции
Инерция — это мера разброса объектов внутри кластеров. В идеале, инерция должна оставаться ниже определенного порога, чтобы обеспечить однородность и эффективность кластера. При этом необходимо учитывать, что стандартные методы кластеризации, такие как K-means или иерархическая кластеризация, не могут быть напрямую использованы в вашем контексте, так как их цели и ограничения не поддерживают ваш критерий для определения качества кластеров.
Предложенный подход: комбинированная стратегия
Предложенная стратегия заключается в том, чтобы применить макет как K-means, так и иерархической кластеризации, чтобы создать кластеры с учетом ваших критериев. Рассмотрим шаги этого подхода:
-
Инициализация: Установите начальное количество кластеров. Рекомендуется начинать с большего числа, чем 2, для снижения вычислительных затрат при поиске решения.
-
Цикл кластеризации: Реализуйте цикл, который будет наращивать количество кластеров от начального значения до n. На каждом шаге применяйте K-means к вашему предcomputed расстоянию для классификации объектов.
-
Оценка инерции: После выполнения K-means, оцените инерцию каждого кластера. Если инерция в любом из кластеров превышает заданный порог, вы должны прекратить попытки создания кластеров с данными параметрами.
-
Корректировка: Если инерция превышает порог, вы можете рассмотреть возможность изменения параметров K-means или применения иерархической кластеризации к результирующим кластерам, чтобы еще больше оптимизировать сбор данных.
-
Финализация: После завершения процесса необходимо проанализировать полученные кластеры и убедиться, что они не только соответствуют критериям инерции, но и удобно управляемы водителями.
Важно учесть: вычислительная сложность
Стоит учесть, что приведенный выше метод может быть вычислительно затратным, особенно при больших объемах данных. Для оптимизации этого процесса можно использовать параллельные вычисления или другие методы ускорения, такие как метод случайной инициализации центров кластеров, чтобы снизить время обработки.
Заключение
Ваша задача — кластеризация с учетом строгости инерции — требует творческого подхода, выходящего за рамки стандартных методов. Применение гибридной стратегии K-means с элементами иерархической кластеризации предоставляет возможность создать адекватные кластеры, которые соответствуют вашим правилам разброса. Это не только повысит качество кластеров, но и улучшит эффективность распределения маршрутов между водителями.