Сходимость в методе К-средних Хартиган-Вонга и других алгоритмах

10

Я пытался понять различные алгоритмы кластеризации k-средних, которые в основном реализованы в statsпакете Rязыка.

Я понимаю алгоритм Ллойда и онлайн-алгоритм МакКуина. Я понимаю их следующим образом:

Алгоритм Ллойда:

Первоначально выбираются случайные наблюдения «k», которые будут служить центроидами кластеров «k». Затем выполняются следующие шаги в итерации, пока центроиды не сходятся.

  1. Евклидово расстояние между каждым наблюдением и выбранными центроидами вычислено.
  2. Наблюдения, которые являются самыми близкими к каждому центроиду, помечены в «k» сегментах.
  3. Среднее значение всех наблюдений в каждом ведре служит новыми центроидами.
  4. Новые центроиды заменяют старые центроиды, и итерация возвращается к шагу 1, если старый и новый центроиды не сходятся.

Условия сходимости следующие: старые и новые центроиды абсолютно идентичны, разница между центроидами мала (порядка 10 ^ -3) или достигается максимальное количество итераций (10 или 100).

Алгоритм Маккуина:

Это онлайн-версия, в которой первые 'k' экземпляры выбраны в качестве центроидов.

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

Повторите этот шаг, пока каждый экземпляр не будет помещен в соответствующее ведро.

Этот алгоритм имеет только одну итерацию, и цикл продолжается для экземпляров 'x'

Алгоритм Хартиган-Вонга:

  1. Назначьте все точки / экземпляры случайным группам и вычислите соответствующий центроид.
  2. Начиная с первого экземпляра, найдите ближайший центроид и попробуйте это ведро. Если ведро изменилось, то пересчитайте новые центроиды, то есть центроид нового назначенного ведра и центроид старого назначения ковша, поскольку это два центроида, на которые повлияло изменение
  3. Перебери все точки и получи новые центроиды.
  4. Выполните вторую итерацию точек 2 и 3, которая выполняет своего рода операцию очистки и переназначает паразитные точки для исправления сегментов.

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

Теперь я не уверен, что то, что я думаю в пункте 4 алгоритма Хартиган-Вонга, является правильным методом алгоритма. У меня вопрос, является ли следующий метод для Хартиган-Вонга правильным методом для реализации k-средних? Есть только две итерации для этого метода? если нет, то каково условие конвергенции (когда остановиться)?

Другое возможное объяснение реализации, что я понимаю.

  1. Назначьте все точки / экземпляры случайным группам и вычислите соответствующий центроид.
  2. Начиная с первого экземпляра, найдите ближайший центроид и назначьте это ведро. Если ведро изменилось, то пересчитайте новые центроиды, то есть центроид нового назначенного ведра и центроид старого назначения ковша, как те два центроида, которые затронуты изменением.
  3. Как только в какой-либо точке произойдет изменение в корзине, вернитесь к первому экземпляру и повторите шаги снова.
  4. Итерация заканчивается, когда все экземпляры повторяются, и ни одна из точек не меняет сегменты.

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

Любые объяснения будут полезны, и, пожалуйста, дайте мне знать, если я понимаю, что любой из этих методов неверен.

Sid
источник
Что такое "ведро"?
ВЫЙТИ - Anony-Mousse
@ Anony-Mousse "ведро" это "кластер". Например: k-means используется для разделения данных на «k» сегменты / кластеры
Сид
Но тогда это звучит как алгоритм MacQueens.
ВЫЙТИ - Anony-Mousse
@ Anony-мусс. да, кроме первого шага, Хартиган-Вонг выглядит так же, как алгоритм MacQueens. Но я не уверен, что это правильное понимание. Может быть какая-то концепция, которую мне не хватает для итераций и сходимости.
Сид

Ответы:

1

Алгоритм HW из статьи 1979 года принимает в качестве входных исходные кластеры. Однако авторы предлагают способ их получения в последнем разделе. Они пишут, что гарантируется, что ни один кластер не будет пустым после первоначального назначения в подпрограмме . Это выглядит следующим образом:

  1. x¯
  2. x¯||xix¯||2
  3. {1+(L1)[M/K]}L=1,,K[  ]1

Что касается основного алгоритма, он описан в статье под названием K-средние Хартигана против K-средних Ллойда - пора ли перемены? N Slonim, E Aharoni, K Crammer, опубликовано в 2013 году AJCAI . Обратите внимание, что эта версия просто использует случайный начальный раздел. Это происходит следующим образом.

xXK

  1. CXKCCvC

  2. XxX

    s=1

    xCC=C{x}

    C+={argminC(CC)C 1nd(x,vC)+1nyC[d(y,vCx)d(y,vC)]}{x}

    C+CCCCC+vCvCs0

  3. s=0

CargminxCdvCvC{x}

Я думаю, что ответы на все ваши вопросы подразумеваются в приведенном выше алгоритме ... Тем не менее, я все еще должен убедиться, что эта реализация алгоритма является стандартной . В частности, если это реализовано в R. Любые комментарии / редактирование приветствуются.

Perochkin
источник