В статье рассматриваются задачи решения проблемы большой масштабируемости данных как в использовании памяти, так и в вычислительном времени, когда число экземпляров данных N велико. Для решения этой проблемы мы представляем алгоритм быстрой спектральной кластеризации, способный эффективно обрабатывать миллионы точек данных в масштабе ПК. Предложенный метод основан на постановке задачи спектральной кластеризации на основе ядра, также известной как спектральная кластеризация ядра.
Ключевые слова: спектрал кластеризация, метод Kernel, большой объем данных, аппроксимация Nystrom
Кластеризация данных представляет собой ценный инструмент анализа данных в современных приложениях машинного обучения и интеллектуального анализа данных. Во многих случаях кластеризация do -mains используется для получения первых сведений о данных в процессе анализа и для решения ряда реальных проблем, таких как сегментация клиентов в маркетинговых кампаниях, устранение неисправностей в мониторинге промышленных процессов, моделирование тем в интеллектуальном анализе текста, сегментация изображений в компьютерном зрении.
Показано, что спектральная кластеризация (SC- Spectral clustering) [2] является одним из наиболее эффективных алгоритмов кластеризации, благодаря своей способности решать нелинейные сепарабельные задачи. Эта эффективность может быть объяснена тем, что данные в исходном пространстве отображаются в новое вложение, где шаблоны подобных точек возникают легче. Это вложение является пространством, охватываемым собственными векторами матрицы Лапласа, которая получена из матрицы подобия графа. Основным недостатком SC является его кубическая вычислительная сложность и узкое место квадратичной памяти. Он нуждается систематического свойства вне образца, которое только приблизительно. Для решения этих задач были предложены некоторые доказанные алгоритмы спектральной кластеризации. Примеры включают в себя, где матрица подобия данных и структура кластеризации изучаются одновременно, где предлагает только сам начальный граф данных как часть кластеризации процедур. Соответственно линейность регуляризация явно добавляется в целевую функцию методов SC, чтобы лучше справляться с многомерными данными, который использует полу-контролируемое обучение рамки для выполнения кластеризации, где добавление неотрицательных ограничений в кластеризацию графа MinMax приводит к решениям, которые очень близки к матрице индикаторов идеального класса, спектральной кластеризации ядра [2] (KSC — kernel spectral clustering). KSC позволяет решать вопросы выбора подходящего количества кластеров и прогнозирования членства новых точек с использованием подхода, основанного на модели ядра. Точнее, KSC представляет собой модель спектральной кластеризации в пределах метода опорных векторов наименьших квадратов. Основная задача формулируется как взвешенный объект PCA (principial component analysis) ядра и, как и в случае классификатора, бинарная модель кластеризации выражается гиперплоскостью в многомерном пространстве, индуцированном ядром. Кроме того, после обучения модели KSC возможно присвоение принадлежности невидимым точкам путем вычисления их проекций на собственные векторы, вычисленные на этапе обучения. Параметры модели KSC получены путем решения задачи на собственные значения в двойном весовом пространстве размера n это tr × Ntr, являющемся Ntr числом обучающих экземпляров. Что касается СК, то при большом Ntr проблема может стать неразрешимой. В этой статье мы обсудим стратегию решения этой проблемы с помощью процедуры фиксированного размера, которая была введена для задач классификации и регрессии, соответственно. Этот подход был первоначально предложен в нашей предыдущей работе и основан на приближении Нюстрема нелинейного отображения, индуцированного матрицей ядра, для решения задачи первичной оптимизации. В частности, после вычисления приближенного явного отображения признаков через случайное подмножество размера m Ntr первичная задача переформулируется в не напряженной форме. Его решение может быть получено путем вычисления собственного разложения матрицы M × m, а стоимость вычисления членства в кластере уменьшается до 0. По сравнению с в данной работе проводится больше сравнений с другими алгоритмами быстрой спектральной кластеризации, получаются дополнительные сведения о производительности кластеризации в зависимости от размера подмножества Nystrom и улучшается понимание полученных результатов.
2. Соответствующая работа
Было разработано несколько алгоритмов ускорения спектральной кластеризации. Кластеризация итераций мощности находит очень низкоразмерное вложение набора данных, используя усеченную итерацию мощности на матрице парного сходства, которая оказывается эффективным индикатором кластера. В спектральной группировке методом Nystrom, вместо точных, значительно меньших вычислительных затратах, вычисляются приближенные собственные векторы Лапласа. Был разработан близкородственный метод, где гарантии исполнения также были доказаны теоретически. Быстрая аппроксимальная спектральная кластеризация использует локальную кластеризацию k-средних и дерево случайных проекций для масштабирования спектральной кластеризации. Также был предложен ряд инкрементальных методов, в которых некоторые начальные кластеры, вычисленные на небольшом подмножестве данных, модифицируются путем обновления системы собственных значений с использованием методов линейной алгебры, c помощью гиперболического сглаживания, с помощью проекции на основе модели. Параллельно спектральной кластеризации матрицы Лапласа выполняется через сохранение ближайших соседей и как использовать память и вычисления параллельно на распределенных компьютерах. Ряд методов используется неполного разложения Холецкого для построения аппроксимации Лапласа графа и уменьшить размер на собственные значения [2]. Спектральная кластеризация на основе ориентиров [3] работает путем выбора репрезентативных точек данных в качестве ориентиров и представляет исходные точки данных в виде линейных комбинаций этих ориентиров. Спектральное вложение данных может быть эффективно вычислено с помощью представления на основе ориентиров. Другие подходы включают консенсуса спектральной кластеризации, векторное квантование на основе примерной спектральной кластеризации, приблизительная попарной кластеризации, низкого ранга Kernel PCA, крупномасштабных мульти-вид спектральной кластеризации [1].
Метод Nystrom
Метод Nystrom использовался для масштабирования алгоритмов на основе ядра, включая метод опорных векторов, Гауссовские процессы, анализ главных компонент ядра [3]. В этой области приблизительные явные карты признаков, соответствующие определенным ядрам, могут служить основой для снижения стоимости обучения нелинейным моделям с большими наборами данных [1].
Оценка эффективности
Эффективность кластеризации оценивается с помощью двух качественных метрик, а именно критерия Дэвиса–Булдина (DB) и скорректированного индекса Ранда. Первый измеряет разделение между каждой парой кластеров и в пределах каждого кластера, насколько тесно сгруппированы все данные. Индекс ARI измеряет соответствие между двумя разделами и обычно используется для оценки корреляции между результатом алгоритма кластеризации и доступной основой истины. Наборы данных, используемые в экспериментах, в основном включают базы данных, доступные в репозитории UCI [2]. Хотя, строго говоря, они относятся к задачам классификации, они также могут быть использованы для оценки производительности алгоритмов кластеризации (где метки играют роль основной истины), с учетом кластерного предположения. Последний утверждает, что если точки находятся в одном кластере, то они, вероятно, относятся к одному классу [3]. В этих случаях методы спектральной кластеризации, как правило, превосходят K-средние, следовательно, более высокие значения ARI. Нетрудно заметить, что предложенный метод очень эффективен и превосходит другие подходы, в случае больших баз данных. Поэтому он представляет собой ценный инструмент для кластеризации крупномасштабных наборов данных.
В этой статье мы представили эффективный и точный алгоритм спектральной кластеризации. Предложенный подход, разработанный в условиях ядра, использует приближение Nystrom карты признаков для решения задачи первичной оптимизации, характеризующей модель спектральной кластеризации ядра. Это приводит к уменьшению временной и пространственной сложности по сравнению со стандартным спектральным кластером, поскольку избегается построение матрицы Лапласа и ее собственное разложение. Ряд экспериментов, проведенных на известных бенчмарках, показывает полезность предложенного алгоритма.
Литература:
- K. Tas¸ demir, Vector quantization based approximate spectral clustering of large datasets, Pattern Recognit. 45 (8) (2012) 3034–3044.
- L. Wang, C. Leckie, R. Kotagiri, J. Bezdek, Approximate pairwise clustering for large data sets via sampling plus extension, Pattern Recognit. 44 (2) (2011) 222–235.
- Мухамадиева К. Б., Самадов С. С. Механизмы работы нейронных сетей // Молодой ученый. — 2019. — № 1. — С. 21–23. — URL https://moluch.ru/archive/239/54451/.
