K-означает: сколько итераций в практических ситуациях?

10

У меня нет отраслевого опыта в области интеллектуального анализа данных или больших данных, поэтому я хотел бы услышать, как вы поделились своим опытом.

Люди на самом деле используют k-means, PAM, CLARA и т. Д. В действительно большом наборе данных? Или они просто случайно выбирают из него образец? Если они просто возьмут образец набора данных, будет ли результат надежным, если набор данных не распределяется нормально?

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

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

Foo
источник
number of iterations always grow with the data sizeНе обязательно.
ttnphns
Существуют различные критерии для остановки итераций в K-средних. Интересно, что просто установить число итераций на фиксированное значение (скажем, 10 или 20) является одним из разумных способов. K-means предназначен для быстрого метода, поэтому, если вы хотите, чтобы критерий сходимости проверялся после каждой итерации, этот критерий должен быть простым / быстрым для вычисления.
ttnphns
1
Есть ли какой-нибудь «научный» способ определения максимального числа итераций, которые нужно выполнить?
Foo
Ваш последний комментарий - хороший вопрос. Честно говоря, я не знаю. возможно другие люди ответят на это.
ttnphns

Ответы:

6
  1. К-значит дешево. Вы можете позволить себе запускать его много раз .

  2. Есть плохие алгоритмы (стандартные) и хорошие алгоритмы. Для хороших алгоритмов последующие итерации часто стоят намного меньше, чем 1% первой итерации.

  3. Есть действительно медленные реализации. Не используйте их.

  4. К-значит на "больших" данных не существует. Потому что это работает только на низкоразмерных векторных данных. Вы не будете превышать память современного сервера с такими данными. да, существуют большие данные - но вы не можете использовать k-means, скажем, за месяц данных Twitter, потому что это не даст вам ничего полезного.

При хорошей реализации на современном сервере самый большой набор данных, который вы можете найти, где k-means по-прежнему дает полезный результат, вероятно, требуется менее 1 минуты для вычисления до сходимости. Так зачем думать о пределе итераций?

ВЫЙТИ - Anony-Mousse
источник
1
Согласен. В этой статье (« Масштабируемые K-средние по ранжированному поиску» ) авторы утверждают, что K-среднее сходится после 20–50 итераций во всех практических ситуациях, даже на многомерных наборах данных при их тестировании. Итак, кроме K-средних, знаете ли вы какой-либо алгоритм, который занимает огромное количество итераций до сходимости?
Foo
Может быть, обучение SVM? Я полагаю, что это итеративный, попытка найти лучший (и наименьший, так как от этого зависит прогноз!) Набор векторов поддержки.
ВЫЙТИ - Anony-Mousse
Очевидное решение для запуска k-средних в наборах данных высокой размерности состоит в том, чтобы сначала запустить PCA или другой метод уменьшения размерности, а затем выполнить k-means
nico