Масштабируемая кластеризация для исследовательского анализа данных

Авторы Аурик Цяо, Джейкоб Джексон

Данные быстро становятся ценным ресурсом для компаний во всех секторах, обещая решить самые сложные проблемы, с которыми сталкиваются предприятия. Однако данные требуют полной, сквозной обработки, прежде чем из них можно будет извлечь большую пользу. Хотя это лишь часть методов анализа данных и моделирования, используемых в исследованиях искусственного интеллекта, глубокое обучение привлекло внимание исследователей и разработчиков систем по всему миру. Это привело к тому, что другие важные методы машинного обучения, такие как кластеризация на основе плотности, деревья решений и линейные модели, остались недооцененными, поскольку объем данных, собираемых современными предприятиями, быстро растет.

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

Введение в кластеризацию и HDBSCAN

Кластеризация - это задача организации набора данных объектов в группы (или кластеры) похожих объектов. Это пример обучения без учителя, и он не требует, чтобы каждый объект данных был сначала помечен категорией вручную. В результате кластеризация полезна для исследовательского анализа данных, исследования наборов данных, которые еще недостаточно изучены.

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

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

Кроме того, k -means предполагает, что все скопления имеют примерно шарообразную форму и похожи друг на друга по размеру. Он может дать сбой при использовании в реальных наборах данных, в которых формы и размеры кластеров различаются и не соответствуют этим предположениям.

HDBSCAN означает H иерархический D уровень - B ased S частный C глянцевый A приложения к N oise. Это алгоритм кластеризации, который преодолевает многие ограничения k -средних. Например, он не требует установки трудно определяемого параметра, прежде чем его можно будет использовать. Мы можем объяснить другие преимущества HDBSCAN, разбив каждый термин:

  • Иерархический: точки упорядочиваются по иерархии кластеров внутри кластеров, что позволяет идентифицировать кластеры разного размера.
  • На основе плотности: использует плотность соседних точек для построения кластеров, что позволяет идентифицировать кластеры любой формы.
  • Приложения с шумом: ожидается, что реальные данные будут заполнены шумом, что позволит идентифицировать точки шума и исключать их из кластеров.

Чтобы подробнее узнать о сравнении HDBSCAN с другими алгоритмами кластеризации, мы рекомендуем этот пост в блоге.

Масштабирование алгоритма HDBSCAN

Традиционная реализация HDBSCAN состоит из двух основных этапов:

  1. Постройте граф k -nearest-neighbors (k -NN) с неориентированным ребром, соединяющим каждую точку p с k наиболее похожие на p. Используйте информацию k -NN, чтобы определить новую метрику, называемую расстоянием взаимной достижимости между всеми парами точек в данных.
  2. Найдите минимальное остовное дерево (MST), соединяющее все точки в данных в соответствии с расстоянием взаимной достижимости. Это дерево представляет собой иерархию кластеров, и отдельные кластеры могут быть извлечены с помощью простой эвристики.

Чтобы получить более подробную информацию об этих этапах, мы рекомендуем эту запись в блоге или исходную статью.

Построение k -NN-графа и поиск минимального остовного дерева являются дорогостоящими с точки зрения вычислений и непрактичными для больших наборов данных - они оба масштабируются квадратично с количеством точек в наборе данных. Наше решение состоит в том, чтобы заменить обе фазы приближениями, которые более эффективны, имеют лучшую масштабируемость и легче реализовать в распределенной системе. Конечно, это решение только приблизительно соответствует точному результату HDBSCAN, но мы находим, что на практике оно работает хорошо.

Аппроксимация графика k -NN:

Для аппроксимации шага 1 мы используем недавно опубликованный алгоритм NN-Descent. Он основан на том принципе, что сосед соседа, скорее всего, будет соседом. Каждая точка p содержит список из k других точек, которые являются k ближайшими к p точками, которые были нашел пока. На каждом этапе обновления сравниваются два случайно выбранных элемента a и b в списке соседей точки. Если b ближе к a, чем самая дальняя точка в списке соседей a, то самая дальняя точка в a список соседей заменяется на b. ŒПовторение этого обновления повышает точность аппроксимации графика k- NN с каждой итерацией.

NN-Descent обладает несколькими желательными качествами, которые делают его подходящим для нашего применения. Было показано, что он хорошо работает с различными наборами данных и метриками расстояния, он имеет субквадратичное эмпирическое время выполнения и может масштабироваться до более крупных наборов данных, а также его можно легко распределить между несколькими ядрами и машинами.

Приблизительно к MST:

Чтобы приблизиться к шагу 2, мы находим минимальное остовное дерево графа, созданного NN-Descent, а не полный граф, соединяющий все точки данных. Единственными важными ребрами MST являются те, которые соединяют точки в одном кластере, и эти ребра должны в основном присутствовать в графе k -NN. Это резко уменьшает размер входного графа для алгоритма MST и позволяет масштабировать вычисления до более крупных наборов данных.

Результаты кластеризации

Чтобы оценить качество приближения, мы оценили кластеризацию на 300-мерном наборе данных встраивания слов и 98 304-мерном наборе данных встраивания изображений. Мы обнаружили, что результаты были значимыми в обоих случаях. Вот примеры кластеров из обоих наборов данных:

Мы также провели количественную оценку качества аппроксимации с помощью индекса Фаулкса-Маллоуз. Мы сгенерировали синтетические кластеры из 100 000 точек, 20% из которых были шумом, а оставшиеся точки назначили случайным образом среди 1000 кластеров. Затем мы сравнили результат кластеризации нашей реализации с точными кластерами, полученными в результате реализации HDBSCAN в scikit-learn-contrib. В десяти измерениях индекс Фаулкса-Маллоуз равен 0,961, что указывает на высокую степень сходства между точной и приблизительной кластеризацией (максимально возможное значение - 1). Таблица результатов для размеров 1–10 приведена ниже:

Результаты производительности

Самая быстрая библиотека HDBSCAN, известная нам, - это реализация в scikit-learn-contrib, упомянутая выше. Мы сравнили эту библиотеку с нашей собственной реализацией на наборе данных 300-мерного встраивания слов. При ограничении одним потоком наша реализация завершилась за 10 минут, в то время как scikit-learn-contrib / hdbscan заняла более 24 часов на том же оборудовании. Кроме того, мы провели сравнение, используя тест, разработанный авторами scikit-learn-contrib / hdbscan. Оба были запущены с настройками по умолчанию, и обоим удалось найти 10 синтетических кластеров. Вот график, на котором сравнивается время их выполнения с использованием набора данных различных размеров:

Хотя scikit-learn-contrib / hdbscan работает быстрее при небольших размерах набора данных, его асимптотическое поведение быстро догоняет его. Из графика видно, что его время выполнения масштабируется примерно квадратично с размером набора данных, в то время как производительность нашей реализации масштабируется почти линейно.

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

Это приложение HDBSCAN было создано в течение двух месяцев в рамках проекта стажировки. Если это тот проект, над которым вы хотели бы работать, Petuum нанимает!