Более быстрая кластеризация Kmeans на многомерных данных с поддержкой графического процессора

Question

Мы использовали Kmeans для кластеризации наших логов. Типичный набор данных имеет 10 миль. образцы с 100k + функциями.

Чтобы найти оптимальное k - мы запускаем несколько Kmeans параллельно и выбираем тот, у которого лучший силуэт. В 90% случаев мы получаем k от 2 до 100. В настоящее время мы используем scmeit-learn Kmeans. Для такого набора данных кластеризация занимает около 24 часов на экземпляре ec2 с 32 ядрами и 244 ОЗУ.

В настоящее время я занимаюсь поиском более быстрого решения.

Что я уже тестировал:

1. Kmeans + Среднее смещение Комбинация - немного лучше (для k = 1024 -> ~ 13h)но все еще медленный.

2. Библиотека Kmcuda - не поддерживает разреженное представление матрицы. Для представления этого набора данных в виде плотной матрицы в памяти потребуется ~ 3 ТБ ОЗУ.

3. Tensorflow ( tf.contrib.factorization.python.ops.KmeansClustering () ) - только сегодня начал расследование, но либо я делаю что-то не так, либо не знаю, как его приготовитьВ моем первом тесте с 20 тысячами образцов и 500 функциями кластеризация на одном графическом процессоре медленнее, чем на одном потоке на процессоре.

4. Facebook FAISS - нет поддержки разреженныхпредставление.

Далее в моем списке PySpark MlLib Kmeans. Но имеет ли это смысл на 1 узле?

Будет ли обучение для моего варианта использования быстрее на нескольких графических процессорах? Например, TensorFlow с 8 Tesla V-100?

Есть ли какая-нибудь магическая библиотека, о которой я не слышал?

Или просто масштабировать вертикально?

Answer 1

1. Выберите алгоритм с умом. Есть умные алгоритмы, и есть глупые алгоритмы для kmeans. Lloyd's глупый, но пока единственный, который вы найдете в графических процессорах. Это тратит впустую много ресурсов с ненужными вычислениями. Потому что люди с GPU и «большими данными» не заботятся об эффективности использования ресурсов ... Хорошие алгоритмы включают Элкана, Хамерли, Ин-Яна, Экспониона, Кольца и т. Д. - они на намного быстрее, чем на Ллойде.

   Склеарн - один из лучших инструментов здесь, потому что он по крайней мере включает алгоритм Элкана. Но если я не ошибаюсь, это может быть многократное копирование ваших данных. Может быть, кусками, чтобы вы этого не заметили. Когда я сравнил k-средних из sklearn с моими сферическими k-средними в Python, моя реализация была во много раз быстрее. Я могу объяснить это только с помощью разреженных оптимизаций, пока версия sklearn выполняла плотные операции. Но, возможно, это улучшилось с тех пор.

2. Качество реализации важно. Была интересная статья о бенчмаркинге k-средних. Позвольте мне Google это:

   Kriegel, HP, Schubert, E. & Zimek, A. (2017). (Черное) искусство оценки времени выполнения: сравниваем ли мы алгоритмы или реализации? Knowledge and Information Systems, 52 (2), 341-378.

   Они показывают, как предположительно один и тот же алгоритм может иметь порядки различий во времени выполнения в зависимости от различий в реализации. У Spark там не очень хорошо ... Слишком высокие накладные расходы, слишком медленные алгоритмы.

3. Вам не нужны все данные.

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

4. Поскольку ваши данные редки, велика вероятность того, что k-means не подходит в любом случае. Вы проверили качество ваших результатов? Как вы обеспечиваете надлежащее масштабирование атрибутов? Насколько результат определяется просто тем, где векторы равны 0, а не фактическими ненулевыми значениями? Действительно ли результаты улучшаются с повторным запуском k-средних так часто? Что если вы не перезапустите k-means? Что если вы просто запустите его на примере, как описано в 3)? Что если вы просто выберете k случайных центров и выполните 0 итераций k-средних? Какой твой лучший силуэт? Скорее всего, вы не можете измерить разницу и просто зря тратите время и ресурсы! Итак, что вы делаете для обеспечения надежности ваших результатов?

Answer 2

спасибо @desertnaut за его предложение с библиотекой RAPIDS cuml .

Продолжение можно найти здесь.