Быстрый k-означает, как алгоритм для 10 ^ 10 баллов?

14

Я хочу сделать кластеризацию k-средних на множестве 10-мерных точек. Подвох: 10 ^ 10 баллов .

Я ищу только центр и размер самых больших кластеров (скажем, от 10 до 100 кластеров); Меня не волнует, в каком кластере заканчивается каждая точка. Использование k-средних определенно не важно; Я просто ищу подобный эффект, любой приблизительный k-средних или связанный алгоритм был бы хорош (минибат-SGD означает, ...). Поскольку GMM в некотором смысле является той же проблемой, что и k-means, выполнение GMM для данных того же размера также интересно.

В этом масштабе субсэмплирование данных, вероятно, существенно не меняет результат: шансы найти те же самые топ-10 кластеров с использованием 1/10000-й выборки данных очень хороши. Но даже тогда это проблема из 10 ^ 6 баллов, которая находится на грани проходимости.

Алекс я
источник
1
Несколько алгоритмов описаны в книге «Mining of Massive Datasets», которую вы можете скачать бесплатно здесь . Прочтите главу 7 «Кластеризация».
ланенок

Ответы:

12

К-среднее основано на средних .

Он моделирует кластеры, используя средства, и, таким образом, улучшение путем добавления большего количества данных является незначительным. Погрешность средней оценки уменьшается с 1 / sqrt (n); поэтому добавление большего количества данных окупается все меньше и меньше ...

Стратегии для таких больших данных всегда вращаются вокруг выборки:

Если вы хотите сублинейное время выполнения, вы должны сделать выборку!

Фактически, Mini-Batch-Kmeans и т. Д. Делают именно это: многократно выбирают данные из набора данных.

Однако выборка (в частности, несмещенная выборка) также не является бесплатной ... обычно вам придется считывать данные линейно для выборки, поскольку вы не получаете произвольный доступ к отдельным записям.

Я бы пошел с алгоритмом MacQueen. Это онлайн; по умолчанию он выполняет однократную передачу ваших данных (хотя это популярное повторение). Распространение нелегко, но я полагаю, вы можете позволить линейно читать ваши данные, скажем, 10 раз с SSD?

ВЫЙТИ - Anony-Mousse
источник
Я не знал об онлайн-алгоритме MacQueen! Дает ли он обычно те же результаты, что и «классические» K-средства? А как насчет использования отбора проб из пласта? Таким образом, у OP есть образец для повторного запуска K-средних на случай, если несколько значений K должны быть проверены.
Виктор Ма
6

В качестве дополнительного комментария отметим, что использование K-средних для 10D-данных может оказаться в никуда, в соответствии с проклятием размерности. Конечно, это немного различается в зависимости от характера данных, но как только я попытался определить порог, при котором K-Means начинает вести себя странно в отношении размерности, я получил что-то вроде 7D. После 7 измерений он начал пропускать правильные кластеры (мои данные были сгенерированы вручную в соответствии с 4 хорошо разделенными гауссовыми распределениями, и я использовал функцию kmeans MATLAB для моего небольшого эксперимента).

Касра Маншаи
источник
Это возможно и, конечно, всегда зависит от данных. Однако, учитывая, что плакат содержит 10 ^ 10 (предположительно независимых) образцов, кажется, что 10 измерений не будут слишком большими проблемами здесь.
Райан Дж. Смит
2
Спасибо за ваш комментарий @ RyanJ.Smith. Ваш комментарий точно в том же направлении, что и мой. Я просто не видел ничего относительно этой проблемы в посте. И о количестве образцов; однако у него есть много примеров, которые он все еще может застрять в проблеме размерности. Я думаю, что вы спорите о противоположной стороне проблемы низкого размера выборки, которая, по моему мнению, недопустима. Если у него большие данные, то небольшая выборка будет проблемой, но я думаю, что большой объем данных не обязательно что-то значит.
Касра Маншаи
10 измерений пока не много.
ВЫЙТИ - Anony-Mousse
1
Как вы определяете моего друга? То, что я сказал, было результатом эксперимента, разработанного, чтобы ответить на такой вопрос, однако на него НЕ МОЖЕТ ответить вообще! Что именно «много» в вашем комментарии точно? это зависит от многих обстоятельств, о которых я упоминал в своем ответе. в некоторых ситуациях 10D может быть проблематичным.
Kasra Manshaei