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

Я пытался понять различные алгоритмы кластеризации 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. Итерация заканчивается, когда все экземпляры повторяются, и ни одна из точек не меняет сегменты.

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

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

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

1. $\bar{x}$
2. $\bar{x}$$||x_i - \bar{x}||_2$
3. $\{ 1 + (L-1) [M/K] \}$$L=1, \dots, K$$[\ \cdot\ ]$$1$

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

$x \in \mathcal{X}$$K$

1. $\mathcal{C}$$\mathcal{X}$$K$$C \in \mathcal{C}$$v_C$

2. $\mathcal{X}$$x \in \mathcal{X}$

   $s = 1$

   $x$$C$$C^{-} = C \setminus \{ x \}$

   $$\begin{align*} C^+ = \Big\{ \mathrm{argmin}_{C^* \in (\mathcal{C} \setminus C) \cup C^{-}}\ \frac{1}{n} d(x,v_C^*) + \frac{1}{n} \sum_{y \in C^*} [d(y,v_{C^* \cup x}) - d(y,v_{C^*})] \Big\} \cup \{ x \} \end{align*}$$

   $C^{+} \neq C$$C \leftarrow C^{-}$$C^* \leftarrow C^{+}$$v_{C}$$v_{C^*}$$s \leftarrow 0$

3. $s=0$

$C^*$$\mathrm{argmin}$$x$$C^*$$d$$v_C$$v_{C^* \cup \{x \}}$

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