При использовании алгоритма кластеризации K-Means возможно ли иметь набор данных, который приводит к бесконечному L oop?

Question

Этот вопрос является более теоретическим и не предназначен специально для решения проблем.

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

Пример:

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

Мой код случайно завис перед тем, как использовать K-Means, поэтому я не верю, что это невозможно, но, пожалуйста, дайте мне знать, если это известное явление или это невозможно из-за природы алгоритма.

Если вам нужна дополнительная информация, просто спросите меня в комментарии. Использование Python 3.7

Answer 1

tl; dr Нет, алгоритм K-средних всегда имеет конечную точку, если алгоритм закодирован правильно.

Объяснение:

Идеальный способ думать об этом не в ощущение того, что точки данных могут вызвать проблемы, а скорее о том, как kmeans работает в более широком смысле. Алгоритм k-means всегда работает в конечном пространстве . Для N точек данных существует только N ^ k отдельных расположений точек данных. (Это число может быть довольно большим, но все же конечным)

Во-вторых, алгоритм k-средних всегда оптимизирует функцию потерь на основе суммы квадратов расстояний между каждой точкой данных и он назначен центром кластера. Это означает две очень важные вещи: Каждое из N ^ k отдельных расположений может быть расположено в порядке возрастания / убывания минимальных потерь до максимальных потерь. Кроме того, алгоритм K-средних никогда не превратит go из состояния с меньшими потерями net в более высокие потери net.

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

Последний крайний случай: Что если более одного минимальное состояние имеет равные потери? Это крайне маловероятный сценарий, но он может вызвать проблемы тогда и только тогда, когда алгоритм плохо закодирован для t ie прерывателей. По сути, единственный способ, которым это может вызвать цикл, - это если точка данных имеет равное расстояние для двух кластеров, и ей разрешено изменять кластеры от своего текущего кластера даже на равном расстоянии. Достаточно сказать, что алгоритмы, как правило, кодируются так, что точки данных никогда не меняются на ie или каким-либо другим детерминированным образом, таким образом полностью исключая этот сценарий.