Кластеризация (k-означает или иным образом) с ограничением минимального размера кластера

14

Мне нужно объединить единицы в кластеров, чтобы минимизировать сумму квадратов внутри группы (WSS), но мне нужно убедиться, что каждый из кластеров содержит не менее единиц. Любая идея, если какая-либо из функций кластеризации R позволяет кластеризовать в кластеров с учетом ограничения минимального размера кластера? Кажется, kmeans () не предлагает опцию ограничения размера.м кkmk

r clustering Сайрус С
источник

Ответы:

5

Используйте EM Clustering

В EM-кластеризации алгоритм итеративно уточняет исходную модель кластера, чтобы соответствовать данным, и определяет вероятность того, что точка данных существует в кластере. Алгоритм завершает процесс, когда вероятностная модель соответствует данным. Функция, используемая для определения соответствия, является логарифмической вероятностью данных, заданных моделью.

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

Мариана Софер
источник
Спасибо Марианна. Я бы предпочел решение, которое в меньшей степени опирается на (как правило, неоправданные) параметрические модели, но обязательно рассмотрит его.
Cyrus S
4

Эта проблема решается в этой статье:

Брэдли, П.С., К.П. Беннетт и Айхан Демириз. «Ограниченная кластеризация k-средних». Microsoft Research, Redmond (2000) : 1-8.

У меня есть реализация алгоритма в Python.

Бехруз Бабаки
источник
Это прекрасно, спасибо! Я использовал rPythonпакет в R для создания интерфейса к этой реализации, к которому я обращался из своего R-скрипта.
Майкл Олрогге
@MichaelOhlrogge У вас есть где-нибудь пример (github?) На интерфейсе, который вы написали для вызова этого пакета Python формы R? Благодарность!
Матифу
Извините, я просмотрел свой старый код, но больше не мог его найти.
Майкл Олрогге
3

Я думаю, что это было бы просто вопросом запуска средства k как части цикла if с проверкой размеров кластера, т. Е. Подсчета n в кластере k - также следует помнить, что средство k даст разные результаты для каждого запуска с одними и теми же данными, поэтому вам, вероятно, все равно следует запустить его как часть цикла, чтобы извлечь «лучший» результат


источник
1
Спасибо, Алекс. Однако я вижу проблему с этим: что если над циклами сгенерированные решения никогда не удовлетворяют ограничению? Это может произойти, если k средств были настроены для работы без ограничения размера кластера. Я хотел бы решение, которое избегает этого. (Характер приложения таков, что мне действительно нужно убедиться, что кластеры имеют минимальный размер.)
Cyrus S
1

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

Если ваш набор данных огромен, вы также можете объединить оба метода кластеризации: начальную неиерархическую кластеризацию и затем иерархическую кластеризацию с использованием групп из неиерархического анализа. Вы можете найти пример такого подхода в работе Мартинеса-Пастора и др. (2005).

Мануэль Рамон
источник
Спасибо, Мануэль. Это на самом деле звучит как очень интригующая возможность. Мне нужно подумать о том, будет ли иерархическое разделение налагать определенные ограничения, которые не позволят алгоритму достичь оптимального разделения кластера непосредственно под ограничением размера. Но интуитивно я вижу, что это может сработать.
Cyrus S
0

Этого можно достичь, изменив шаг назначения кластера (E в EM), сформулировав его как задачу оптимизации линейной сети с минимальным расходом (MCF).

Я написал пакет на python, который использует SimpleMinCostFlow из инструментов исследования операций Google, который является быстрой реализацией C ++. У него есть стандартное API-интерфейс.

joshlk
источник