Спектральная кластеризация данных | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 18 июля, печатный экземпляр отправим 22 июля.

Опубликовать статью в журнале

Авторы: ,

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №9 (247) март 2019 г.

Дата публикации: 03.03.2019

Статья просмотрена: 330 раз

Библиографическое описание:

Мухамадиева, З. Б. Спектральная кластеризация данных / З. Б. Мухамадиева, С. А. Салимов. — Текст : непосредственный // Молодой ученый. — 2019. — № 9 (247). — С. 88-90. — URL: https://moluch.ru/archive/247/56935/ (дата обращения: 05.07.2020).



В статье рассматриваются задачи решения проблемы большой масштабируемости данных как в использовании памяти, так и в вычислительном времени, когда число экземпляров данных 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 карты признаков для решения задачи первичной оптимизации, характеризующей модель спектральной кластеризации ядра. Это приводит к уменьшению временной и пространственной сложности по сравнению со стандартным спектральным кластером, поскольку избегается построение матрицы Лапласа и ее собственное разложение. Ряд экспериментов, проведенных на известных бенчмарках, показывает полезность предложенного алгоритма.

Литература:

  1. K. Tas¸ demir, Vector quantization based approximate spectral clustering of large datasets, Pattern Recognit. 45 (8) (2012) 3034–3044.
  2. 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.
  3. Мухамадиева К. Б., Самадов С. С. Механизмы работы нейронных сетей // Молодой ученый. — 2019. — № 1. — С. 21–23. — URL https://moluch.ru/archive/239/54451/.
Основные термины (генерируются автоматически): спектральная кластеризация, KSC, ARI, PCA, решение задачи, данные, спектральная кластеризация ядра, быстрая спектральная кластеризация, первичная оптимизация, предложенный метод.


Ключевые слова

спектрал кластеризация, метод Kernel, большой объем данных, аппроксимация Nystrom

Похожие статьи

Применение методов кластеризации для обработки новостного...

Для решения данной задачи используется кластеризация полнотекстовых статей. Кратко рассматриваются различные типы алгоритмов

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

Поэтапный процесс кластерного анализа данных на основе...

Рассмотрим задачу кластеризации данных. Имеется выборка и функция, отображающая

Кластерный анализ обработки данных может быть использован в области цифрового.

Метод естественной кластеризации данных. Метод k средних при решении задачи распознавания...

Кластерный анализ разработки современных алгоритмов...

Кластерный анализ – технология группирования объектов в ранее неизвестные группы [1]. Кластерный анализ применяется во

Также одна из областей изучения информатики является интеллектуальный анализ данных. В ходе решения задач анализа данных, которые в...

Метод естественной кластеризации данных | Статья в журнале...

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

Первичная обработка сигналов вейвлетами на примере...

Методы решения задачи кластеризации и прогнозирования в электронном архиве. Первичная обработка сигналов вейвлетами на примере подготовки данных к

Рассмотрим второй пример использование кластеризации решения задач на поиск информации по заданным параметрам.

Использование матриц комбинаторного типа для построения...

Будем формулировать задачу кластеризации таким образом, чтобы одно решающее правило работало во всех

. Для решения задачи 1, прежде всего понадобится провести процедуру параметризации матрицы комбинаторного типа H. Структура матрицы комбинаторного типа...

Выделение границ фонем речевого сигнала с помощью...

Существует несколько методом для ее решения. В этой статье будет рассмотрен метод, основанный на измерении скорости изменения

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

Алгоритмы планирования масштабируемых заданий кластерной...

В данной работе рассматривается возможность повышения эффективности работы планировщика заданий кластерной системы при учете в процессе планирования способности пакетных заданий изменять число используемых ресурсов.

Методы решения задачи кластеризации и прогнозирования...

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

Таким образом, применяя данные методы при использовании документов электронного архива, можно предсказать значения нужных аналитику атрибутов.

Похожие статьи

Применение методов кластеризации для обработки новостного...

Для решения данной задачи используется кластеризация полнотекстовых статей. Кратко рассматриваются различные типы алгоритмов

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

Поэтапный процесс кластерного анализа данных на основе...

Рассмотрим задачу кластеризации данных. Имеется выборка и функция, отображающая

Кластерный анализ обработки данных может быть использован в области цифрового.

Метод естественной кластеризации данных. Метод k средних при решении задачи распознавания...

Кластерный анализ разработки современных алгоритмов...

Кластерный анализ – технология группирования объектов в ранее неизвестные группы [1]. Кластерный анализ применяется во

Также одна из областей изучения информатики является интеллектуальный анализ данных. В ходе решения задач анализа данных, которые в...

Метод естественной кластеризации данных | Статья в журнале...

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

Первичная обработка сигналов вейвлетами на примере...

Методы решения задачи кластеризации и прогнозирования в электронном архиве. Первичная обработка сигналов вейвлетами на примере подготовки данных к

Рассмотрим второй пример использование кластеризации решения задач на поиск информации по заданным параметрам.

Использование матриц комбинаторного типа для построения...

Будем формулировать задачу кластеризации таким образом, чтобы одно решающее правило работало во всех

. Для решения задачи 1, прежде всего понадобится провести процедуру параметризации матрицы комбинаторного типа H. Структура матрицы комбинаторного типа...

Выделение границ фонем речевого сигнала с помощью...

Существует несколько методом для ее решения. В этой статье будет рассмотрен метод, основанный на измерении скорости изменения

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

Алгоритмы планирования масштабируемых заданий кластерной...

В данной работе рассматривается возможность повышения эффективности работы планировщика заданий кластерной системы при учете в процессе планирования способности пакетных заданий изменять число используемых ресурсов.

Методы решения задачи кластеризации и прогнозирования...

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

Таким образом, применяя данные методы при использовании документов электронного архива, можно предсказать значения нужных аналитику атрибутов.

Задать вопрос