Масштабирование иерархической кластеризации для больших данных
Масштабирование иерархической кластеризации для больших данных' can be condensed as 'Scaling hierarchical clustering for big data
Узнайте, как использовать рекурсивную агломеративную кластеризацию (RAC) для иерархической кластеризации больших наборов данных
Введение
Агломеративная кластеризация – один из лучших инструментов кластеризации в науке о данных, но традиционные реализации не масштабируются для больших наборов данных.
В этой статье я расскажу вам немного о фоне агломеративной кластеризации, введении в рекурсивную агломеративную кластеризацию (RAC) на основе исследований Google 2021 года, сравнении времени выполнения между RAC++ и AgglomerativeClustering из scikit-learn и, наконец, кратком объяснении теории, лежащей в основе RAC.
Фон агломеративной кластеризации
В науке о данных часто полезно кластеризовать неразмеченные данные. Кластеризация является неотъемлемой частью инструментария дата-саентиста и применяется в таких областях, как группировка результатов поисковых систем, классификация генотипов, обнаружение аномалий в банковской сфере и др.
Агломеративная кластеризация – один из самых популярных подходов к кластеризации в науке о данных и это обусловлено следующими причинами:
- Что такое EDI? Об электронном обмене данными
- Google Cloud и NVIDIA повышают сотрудничество на новый уровень
- Связь ИИ и этики комплексные решения в внедрении здравоохранения
✅ Легко использовать с минимальной настройкой параметров✅ Создает содержательные таксономии✅ Хорошо работает с высокоразмерными данными✅ Не требует заранее заданного числа кластеров✅ Всегда создает одни и те же кластеры
В сравнении с методами разделения, такими как K-Means, где дата-саентист должен угадывать количество кластеров, очень популярным методом, основанным на плотности, таким как DBSCAN, требуется некоторая настройка параметров радиуса вычисления плотности (эпсилон) и минимального размера окрестности, а модели смеси Гауссианов делают сильные предположения о распределении данных в кластерах.
С агломеративной кластеризацией все, что вам нужно указать, это метрика расстояния.
На высоком уровне агломеративная кластеризация следует следующему алгоритму:
Определение расстояния между всеми парами кластеров (каждый кластер начинается как отдельная точка)Объединение двух кластеров, которые находятся ближе всего друг к другуПовторение
Результатом является красивая дендрограмма, которую затем можно разделить на основе экспертных знаний в области.
В таких областях, как биология и обработка естественного языка, кластеры (клетки, гены или слова) естественным образом образуют иерархические отношения. Агломеративная кластеризация позволяет более естественный и данных-ориентированный выбор конечной границы кластеризации.
На рисунке ниже представлена пример агломеративной кластеризации известного набора данных Iris.
Так почему бы не использовать агломеративную кластеризацию для каждой задачи без учителя?
❌ Агломеративная кластеризация имеет ужасное время выполнения при увеличении размера наборов данных.
К сожалению, традиционная агломеративная кластеризация не масштабируется. Время выполнения составляет O(n³) или O(n²log(n)), если реализовано с использованием мин-кучи. Еще хуже, агломеративная кластеризация выполняется последовательно на одном ядре и не может быть масштабирована с помощью вычислений.
В области NLP агломеративная кластеризация является одним из лучших методов… для небольших наборов данных.
Рекурсивная агломеративная кластеризация (RAC)
Рекурсивная агломеративная кластеризация (RAC) – это метод, предложенный Google для масштабирования преимуществ традиционной агломеративной кластеризации на большие наборы данных.
RAC снижает сложность времени выполнения и параллелизует операции для использования многоядерной архитектуры. Несмотря на эти оптимизации, RAC дает точно такие же результаты, что и традиционная агломеративная кластеризация, когда данные полностью связаны (см. ниже).
Примечание: Полностью связанные данные означают, что можно рассчитать метрику расстояния между любой парой точек. Неполностью связанные наборы данных имеют ограничения на связность (обычно предоставляемые в виде матрицы связи), при которых некоторые точки считаются несвязанными.
Даже с ограничениями на связность (данные, которые не полностью связаны), RAC и агломеративная кластеризация обычно все равно идентичны, как видно на втором примере набора данных Swiss Roll выше.
Однако могут возникать значительные расхождения, когда возможно очень мало кластеров. Хорошим примером является набор данных Noisy Moons:
RAC++ масштабируется для больших наборов данных по сравнению со scikit-learn
Мы можем сравнить RAC++ (реализацию рекуррентной агломеративной кластеризации) с его аналогом, AgglomerativeClustering, в scikit-learn.
Сгенерируем некоторые примеры данных с 25 измерениями и проверим, сколько времени занимает агломеративная кластеризация при использовании racplusplus.rac по сравнению с sklearn.cluster.AgglomerativeClustering для наборов данных разного размера от 1 000 до 64 000 точек.
Примечание: Я использую матрицу связности для ограничения потребления памяти.
import numpy as npimport racplusplusfrom sklearn.cluster import AgglomerativeClusteringimport timepoints = [1000, 2000, 4000, 6000, 10000, 14000, 18000, 22000, 26000, 32000, 64000]for point_no in points: X = np.random.random((point_no, 25)) distance_threshold = .17 knn = kneighbors_graph(X, 30, include_self=False) # Матрица должна быть симметричной - выполняется внутренним образом в scikit-learn symmetric = knn + knn.T start = time.time() model = AgglomerativeClustering( linkage="average", connectivity=knn, n_clusters=None, distance_threshold=distance_threshold, metric='cosine' )sklearn_times.append(time.time() - start)start = time.time()rac_labels = racplusplus.rac( X, distance_threshold, symmetric, batch_size=1000, no_cores=8, metric="cosine" )rac_times.append(time.time() - start)Вот график результатов времени выполнения для каждого набора данных:
Как видно, есть значительные различия во времени выполнения между RAC++ и традиционной агломеративной кластеризацией.
Даже при немногим более 30 тысяч точек RAC++ работает примерно в 100 раз быстрее! Еще более важно, агломеративная кластеризация scikit-learn достигает предельного времени выполнения при ~35 тысячах точек, тогда как RAC++ может масштабироваться до сотен тысяч точек до достижения разумного предельного времени выполнения.
RAC++ может масштабироваться для высоких размерностей
Мы также можем сравнить, насколько хорошо RAC++ масштабируется для данных с высокой размерностью по сравнению с его традиционным аналогом.
Время, затраченное на генерацию кластеров по отношению к размерности для 3 000 точек
Для 3 000 точек можно видеть, что традиционная агломеративная кластеризация работает быстрее, но масштабируется линейно, тогда как RAC++ почти постоянно. Работа с вложениями размерностью 768 или 1536 стала стандартом в области NLP, поэтому важно масштабировать размерность, чтобы соответствовать этим требованиям.
RAC++ имеет лучшее время выполнения
Исследователи в Google доказали, что у RAC время выполнения составляет O(nk), где k – ограничение связности, а n – количество точек – линейное время выполнения. Однако это не включает в себя начальный расчет матрицы расстояний, который имеет квадратичное время выполнения – O(n²).
Наши результаты, при постоянном ограничении связности в 30 соседях, подтверждают квадратичное время выполнения:
+ — — — — — — -+ — — — — — +| Количество данных | Секунды |+ - - - - - - -+ - - - - - +| 2000 | 0.051 || 4000 | 0.125 || 6000 | 0.245 || 10000 | 0.560 || 14000 | 1.013 || 18000 | 1.842 || 22000 | 2.800 || 26000 | 3.687 || 32000 | 5.590 || 64000 | 22.499 |+ - - - - - - -+ - - - - - +Удвоение точек данных приводит к увеличению времени в 4 раза.
Квадратичное время выполнения ограничивает производительность RAC++ на действительно массивных наборах данных, однако это время выполнения уже является значительным улучшением перед традиционным O(n³) или оптимизированным с использованием min-heap O(n²log(n)).
Примечание: разработчики RAC++ работают над передачей матрицы расстояний в качестве параметра, что позволит получить линейное время выполнения для RAC++.
Как работает RAC
Почему RAC++ так быстро? Мы можем свести основной алгоритм к нескольким шагам:
Объединение кластеров с обратными ближайшими соседямиСлияние пар кластеровОбновление соседей
Обратите внимание, что единственное отличие между этим и традиционным агломеративным алгоритмом кластеризации заключается в том, что мы убеждаемся, что пары обратных ближайших соседей объединяются вместе. Отсюда и появляется название Reciprocal Agglomerative Clustering (RAC). Как вы увидите, эта обратная связь позволяет нам параллельно выполнять самый вычислительно сложный шаг агломеративной кластеризации.
Объединение кластеров с обратными ближайшими соседями
Сначала мы проходим циклом, чтобы найти кластеры с обратными ближайшими соседями, то есть такие, у которых ближайшие соседи – это они сами (помните, расстояние может быть направленным!).
Слияние пар
RAC может быть параллелизирован, потому что не имеет значения, в каком порядке объединяются пары обратных ближайших соседей, главное, чтобы метод связи был сокращаемым.
Метод связи – это функция, которая определяет расстояние между двумя кластерами на основе попарных расстояний между точками, содержащимися в каждом кластере. Сокращаемый метод связи гарантирует, что новый объединенный кластер не будет ближе к любому другому кластеру после слияния.
К счастью, четыре самых популярных метода связи являются приводимыми:
- Единичная связь – минимальное расстояние
- Средняя связь – среднее расстояние
- Полная связь – максимальное расстояние
- Связь Уорда – минимизация дисперсии
Поскольку мы знаем, что наши определенные взаимные пары являются ближайшими соседями друг друга, и мы знаем, что приводимые объединения связей никогда не будут делать новый объединенный кластер ближе к другому кластеру, мы можем безопасно объединить все взаимно ближайшие пары соседей сразу. Каждая пара ближайших соседей может быть помещена в доступную нить для объединения согласно методу связи.
Тот факт, что мы можем объединить взаимно ближайших соседей одновременно, является фантастическим, потому что объединение кластеров является самым вычислительно затратным шагом!
Обновление ближайших соседей
С методом приводимой связи порядок обновления ближайших соседей после объединения также не имеет значения. Поэтому, с некоторым умным проектированием, мы также можем обновлять соответствующих соседей параллельно.
Вывод
С помощью нескольких тестовых наборов данных мы показали, что RAC++ дает точно такие же результаты, как и традиционная агломеративная кластеризация (т.е. sklearn) для полностью связанных наборов данных с гораздо лучшим временем выполнения. Понимая приводимые метрики связи и базовое понимание параллельного программирования, мы можем понять логику, которая делает RAC++ настолько быстрым.
Для более полного понимания (и доказательства) алгоритма, на который был опирается RAC++ в рамках проекта с открытым исходным кодом, ознакомьтесь с исходным исследованием Google.
Будущее
Портер Ханли начал разрабатывать RAC++ для создания таксономий для клинических терминов, полученных с помощью настроенных вложений BERT. Каждое из этих медицинских вложений имело 768 измерений, и из множества алгоритмов кластеризации, которые он попробовал, только агломеративная кластеризация давала хорошие результаты.
Все остальные методы кластеризации высокого масштаба требовали сокращения размерности, чтобы дать любые последовательные результаты. К сожалению, нет надежного способа сократить размерность – всегда будет потеря информации.
После того, как были обнаружены исследования Google по RAC, Портер решил создать специальную реализацию кластеризации с открытым исходным кодом для поддержки своих исследований кластеризации клинических терминов. Портер руководил разработкой, а я совместно разработал части RAC, особенно обертывание C++ реализации на языке Python, оптимизацию времени выполнения и упаковку программного обеспечения для распространения.
RAC++ позволяет выполнять множество приложений кластеризации, которые слишком медленны с использованием традиционной агломеративной кластеризации, и в конечном итоге будет масштабируемым до миллионов точек данных.
Хотя RAC++ уже можно использовать для кластеризации больших наборов данных, есть еще место для улучшений… RAC++ все еще находится в разработке – пожалуйста, внесите свой вклад!
Авторы содействия:
- Портер Ханли, старший программист в Daceflow.ai: github
- Дэниел Фрис, студент магистратуры по статистике и науке о данных в Стэнфорде, дата-саентист в IBM: github
GitHub – porterehunley/RACplusplus: Высокопроизводительная реализация Взаимной Агломеративной…
