Решения для непрерывной онлайн-идентификации кластеров?

11

Позвольте мне показать вам пример гипотетического приложения онлайн кластерной:

введите описание изображения здесь

В момент времени n точек 1,2,3,4 выделяются синему кластеру A, а точки b, 5,6,7 выделяются красному кластеру B.

В момент времени n + 1 вводится новая точка a, которая назначается синему кластеру A, но также вызывает назначение точки b также синему кластеру A.

В конечных точках 1, 2, 3, 4, a, b принадлежат A, а точки 5, 6, 7 - B. Мне это кажется разумным.

То, что кажется простым на первый взгляд, на самом деле немного сложнее - сохранить идентификаторы через временных шагов. Позвольте мне попытаться сделать этот момент ясно с более пограничным например:

введите описание изображения здесь

Зеленая точка приведет к объединению двух синих и двух красных точек в один кластер, который я произвольно решил закрасить синим - учтите, что это уже мое человеческое эвристическое мышление на работе!

Компьютер для принятия этого решения должен будет использовать правила. Например, когда точки объединяются в кластер, идентичность кластера определяется большинством. В этом случае мы столкнемся с ничьей - и синий и красный могут быть допустимыми для нового (здесь синего цвета) кластера.

Представьте себе пятую красную точку, близкую к зеленой. Тогда большинство будет красным (3 красных против 2 синих), поэтому красный будет хорошим выбором для нового кластера - но это будет противоречить еще более четкому выбору красного для самого правого кластера, поскольку они были красными и, вероятно, должны остаться такими. ,

Я считаю это сомнительным думать об этом. В конце концов, я думаю, что для этого нет идеальных правил - скорее эвристика, оптимизирующая некоторую стабильность criterea.

Это, наконец, приводит к моим вопросам:

  1. Есть ли у этой «проблемы» имя, на которое можно сослаться?
  2. Существуют ли "стандартные" решения для этого и ...
  3. ... может быть, даже пакет R для этого?

Разумное наследование кластерных идентичностей при повторяющейся кластеризации

Раффаэль
источник
Перекрестная публикация из stats stats.stackexchange.com/questions/111911/… И stackoverflow: stackoverflow.com/questions/24970702/…
Имеет выход - Anony-Mousse
Является ли проблемой то, что вы пытаетесь поддерживать идентичность кластеров в максимально возможной степени на каждом временном шаге? Так что в N + 1 вы можете сказать, как изменился кластер, потому что существует некоторая связь между кластерами в N и кластерами в N + 1? И хитрость в том, что происходит, если кластеры разделяются и объединяются?
Spacedman
@Spacedman: БИНГО :) joyofdata.de/blog/…
Раффаэль
Я приглашаю вас взглянуть на это и это
farhawa

Ответы:

1

Дилемма стабильности-пластичности, скорости обучения и алгоритмы забывания:

Во-первых, позвольте мне сказать, что это действительно замечательный вопрос, который заставляет задуматься, который действительно улучшает понимание алгоритмов ML.

  1. Есть ли у этой «проблемы» имя, на которое можно сослаться?

Это обычно называется «стабильностью». Что забавно, так это то, что стабильность на самом деле полезна в обычной кластеризации, то есть не в сети. «Стабильность» алгоритма часто выбирается в качестве критерия выбора правильного количества кластеров. Более конкретно, проблема стабильности онлайн-кластеризации, которую вы описали, называется stability-plasticity dilemma.

  1. Существуют ли "стандартные" решения для этого и ...

Во-первых, общая картина заключается в том, что многие алгоритмы онлайн-кластеризации удивительно стабильны, когда они хорошо обучены большой группе исходных данных. Тем не менее, это все еще проблема, если вы хотите точно определить кластерные точки, позволяя алгоритму реагировать на новые данные. Trickiness из вас точки кратко рассмотрены в Введении к Machine Learning By Этхем Alpaydin. На странице 319 он выводит алгоритм k-средних онлайн посредством применения стохастического градиентного спуска, но упоминает, что он stability-plasticity dilemmaвозникает при выборе значения для скорости обучения. Небольшая скорость обучения приводит к стабильности, но система теряет адаптивность, тогда как большая скорость обучения приобретает адаптивность, но теряет стабильность кластера.

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

Другой метод, который я видел, - это своего рода алгоритм забывания, например, забывание более старых точек по мере созревания потока данных. Это обеспечивает довольно стабильную систему в быстрых масштабах времени и позволяет развиваться в более медленных временных масштабах. Adaptive Resonance Theoryбыл создан, чтобы попытаться решить stability-plasticity dilemma. Вы можете найти эту статью интересной.

Я недостаточно разбираюсь в R, чтобы предложить алгоритм, но я предлагаю вам поискать mini-batch k-meansалгоритм, который позволяет вам контролировать скорость обучения в его алгоритме стохастического градиентного спуска.

Надеюсь, это поможет!

AN6U5
источник