У меня есть несколько точек в R p , и я хочу сгруппировать точки так, чтобы:
Каждый кластер содержит равное количество элементов . (Предположим, что число кластеров делит n .)
Каждый кластер в некотором смысле является «пространственно связным», как кластеры из средних.
Легко придумать множество процедур кластеризации, которые удовлетворяют одной или другой из них, но кто-нибудь знает способ получить оба сразу?
Ответы:
Я предлагаю двухэтапный подход:
получить хорошие начальные оценки центров кластеров, например, с использованием жестких или нечетких K-средних.
Используйте глобальное присвоение ближайшего соседа, чтобы связать точки с центрами кластеров: вычислить матрицу расстояний между каждой точкой и каждым центром кластера (вы можете сделать задачу чуть меньше, рассчитав только разумные расстояния), реплицировать каждый центр кластера X раз и решить линейную задачу проблема назначения . Для каждого центра кластера вы получите ровно X совпадений с точками данных, так что в глобальном масштабе расстояние между точками данных и центрами кластеров сведено к минимуму.
Обратите внимание, что вы можете обновить центры кластеров после шага 2 и повторить шаг 2, чтобы в основном запустить K-средних с фиксированным числом точек на кластер. Тем не менее, будет хорошей идеей сначала получить правильное предположение.
источник
Попробуйте этот вариант k-средних:
Инициализация :
k
центры из набора данных случайным образом или даже лучше, используя стратегию kmeans ++В конце концов, у вас должно быть разделение, удовлетворяющее вашим требованиям, равное + -1 к одинаковому количеству объектов на кластер (убедитесь, что последние несколько кластеров также имеют правильное число. Первые
m
кластеры должны иметьceil
объекты, а остальные - точноfloor
объекты.)Шаг итерации :
Реквизиты: список для каждого кластера с «предложениями обмена» (объекты, которые предпочли бы быть в другом кластере).
Шаг E : вычислить обновленные центры кластеров, как в обычном k-средних
Шаг M : повторение всех точек (либо только одна, либо все в одной партии)
Вычислить ближайший центр кластера для объекта / всех центров кластера, которые ближе, чем текущие кластеры. Если это другой кластер:
Размеры кластеров остаются неизменными (+ - разница потолок / этаж), объекты перемещаются только из одного кластера в другой, если это приводит к улучшению оценки. Поэтому он должен сходиться в некоторой точке, например, k-средних. Это может быть немного медленнее (то есть больше итераций), хотя.
Я не знаю, было ли это опубликовано или реализовано ранее. Это именно то, что я бы попробовал (если бы я попытался использовать k-means. Есть гораздо лучшие алгоритмы кластеризации.)
Хорошее место для начала может быть с реализацией k-средних в ELKI , которая, кажется, уже поддерживает три разные инициализации (включая k-means ++), и авторы сказали, что они также хотят иметь разные стратегии итерации, чтобы охватить все различные общие варианты по модульному принципу (например, Lloyd, MacQueen, ...).
источник
Это проблема оптимизации. У нас есть Java-библиотека с открытым исходным кодом, которая решает эту проблему (кластеризация, где количество на кластер должно быть между заданными диапазонами). Вам нужно, чтобы ваше общее количество очков было не более нескольких тысяч, но не более 5000 или, может быть, 10000.
Библиотека находится здесь:
https://github.com/PGWelch/territorium/tree/master/territorium.core
Сама библиотека настроена на проблемы географического / ГИС-типа - поэтому вы увидите ссылки на X и Y, широты и долготы, клиентов, расстояние и время и т. Д. Вы можете просто игнорировать «географические» элементы и использовать их как чистый кластеризатор.
Вы предоставляете набор изначально пустых входных кластеров, каждый из которых имеет минимальное и максимальное целевое количество. Кластерер назначит точки вашим входным кластерам, используя эвристический алгоритм оптимизации (свопы, ходы и т. Д.). При оптимизации он, во-первых, устанавливает приоритеты для каждого кластера в пределах своего минимального и максимального количественного диапазона, а затем, во-вторых, минимизирует расстояния между всеми точками в кластере и центральной точкой кластера, поэтому кластер является пространственно связным.
Вы предоставляете решателю метрическую функцию (то есть функцию расстояния) между точками, используя этот интерфейс:
https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/TravelMatrix.java
Метрика на самом деле структурирована так, чтобы возвращать как расстояние, так и «время», потому что она предназначена для географических задач, основанных на путешествиях, но для произвольных проблем кластеризации просто установите «время» равным нулю, а расстояние - как фактическую метрику, которую вы используете между точки.
Вы бы настроили свою проблему в этом классе:
https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/Problem.java
Ваши баллы будут «Клиенты», а их количество будет 1. В классе клиентов убедитесь, что вы установили costPerUnitTime = 0 и costPerUnitDistance = 1, предполагая, что вы возвращаете метрическое расстояние в поле «расстояние», возвращаемое TravelMatrix.
https://github.com/PGWelch/territorium/blob/master/territorium.core/src/main/java/com/opendoorlogistics/territorium/problem/Customer.java
Смотрите здесь пример запуска решателя:
https://github.com/PGWelch/territorium/blob/master/territorium.core/src/test/java/com/opendoorlogistics/territorium/TestSolver.java
источник
Я предлагаю недавнюю статью « Дискриминационная кластеризация путем максимизации регулярной информации» (и ссылки в ней). В частности, в разделе 2 говорится о балансе классов и предположении кластера.
источник
Недавно я сам нуждался в этом для небольшого набора данных. Мой ответ, хотя он имеет относительно длительное время работы, гарантированно сходится к локальному оптимуму.
источник