Улучшение кластеризации k-средних путем разъединения

Усовершенствование кластеризации методом разъединения в алгоритме k-средних

Обучение структуры соседства классов набора данных улучшает кластеризацию

Сопровождающая статья к статье «Улучшение кластеризации k-средних с помощью разделенных внутренних представлений» А.Ф. Агарапа и А.П. Асксарага, представленной на Международной совместной конференции нейронных сетей (IJCNN) 2020 года.

Фон

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

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

Мы определяем разделение как то, насколько далеки друг от друга точки данных разных классов относительно точек данных, более похожих по классу. Это аналогично тому, как описанный выше термин был использован в работе Frosst et al. (2019). Таким образом, максимизация разделения при обучении представления означает минимизацию расстояния между точками данных, более похожими по классу.

Рисунок автора.

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

Кластеризация

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

Рисунок автора.

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

Глубокая кластеризация

Таким образом, недавние работы, такие как Глубокая встраивающая кластеризация или DEC и Вариационная глубинная встраивающая или VADE в 2016 году, и ClusterGAN в 2018 году, воспользовались возможностью изучения представлений признаков с использованием нейронных сетей.

Рисунок из работы DEC (Xie et al., 2016). Структура сети DEC.

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

Мотивация

Можем ли мы сохранить принадлежность классов точек данных в наборе данных перед кластеризацией?

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

В 2019 году был предложен метод кластеризации Not Too Deep или N2D, в котором они изучали латентное кодовое представление набора данных, в котором они дополнительно искали скрытое многообразие с использованием таких техник, как t-SNE, Isomap и UMAP. Полученное многообразие представляет собой представление набора данных, удобное для кластеризации. Таким образом, после изучения многообразия они использовали его в качестве признаков набора данных для кластеризации. Используя такой подход, они смогли достичь хорошей производительности кластеризации. Метод N2D является относительно более простым подходом по сравнению с методами глубокой кластеризации, и мы предлагаем подобный подход.

Обучение разделенных представлений

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

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

Для разделения изученных представлений мы используем “мягкую потерю ближайшего соседа” или SNNL, которая измеряет взаимосвязь похожих классов данных. Эта функция потери минимизирует расстояния между похожими на класс данные в каждом скрытом слое нейронной сети. Работа над этой функцией потери, проведенная Frosst, Papernot и Hinton, использовала фиксированное значение температуры, обозначенное T. Фактор температуры определяет, как контролировать значимость расстояний между парами точек. Например, при низких температурах потеря определяется малыми расстояниями, тогда как фактические расстояния между отдельными представлениями, разделенными широко, становятся менее значимыми. Они использовали SNNL для дискриминирующих и генеративных задач в своей статье 2019 года.

Иллюстрация автором. Мы взяли показатель из работы Neelakantan et al., 2015, но он может быть любым.

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

Иллюстрация автором. Сравнение мягкой потери ближайшего соседа с температурой охлаждения и с фиксированной температурой. Мы выбрали и произвольно пометили 300 точек данных из гауссового распределения и применили на них градиентный спуск с использованием мягкой потери ближайшего соседа. Иллюстрация слева показывает начальное состояние помеченных точек. Мы можем видеть разделение кластеров в латентном коде от эпохи 20 до эпохи 50, что делает классы более изолированными. Мы представляем разделенные представления на стандартных наборах данных в <a href=статье.

Запуская градиентный спуск на случайно выбранных и помеченных 300 точках данных из гауссового распределения, мы видим, что при использовании нашей температуры отжига для SNNL мы обнаружили более быстрое разделение, чем при использовании фиксированной температуры. Как видно, уже на 20-й эпохе точки данных, подобные по классу, более скучены или сцеплены при использовании температуры отжига, чем при использовании фиксированной температуры, как и численно показывается значением SNNL.

Наш метод

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

Наш метод можно кратко описать следующим образом:

  1. Мы обучаем автоэнкодер с использованием составной функции потерь бинарной кросс-энтропии в качестве функции восстановления и функции потерь мягкого ближайшего соседа в качестве регуляризатора. SNNL для каждого скрытого слоя автоэнкодера минимизируется для сохранения структуры классового соседства набора данных.
  2. После обучения мы используем латентное кодирование набора данных в качестве характеристик для кластеризации.

Кластеризация на разделенных представлениях

Наша конфигурация эксперимента следующая:

  1. Мы использовали наборы данных бенчмарка MNIST, Fashion-MNIST и EMNIST Balanced. Каждое изображение в наборах данных было преобразовано в вектор размерности 784. Мы использовали их истинные метки в качестве псевдо-меток кластеризации для измерения точности кластеризации нашей модели.
  2. Мы не проводили настройку гиперпараметров или другие трюки обучения из-за вычислительных ограничений и чтобы сохранить наш подход простым.
  3. Дополнительные регуляризаторы, такие как отсев и нормализация пакета, были исключены, так как они могут повлиять на процесс разделения.
  4. Мы вычислили среднюю производительность нашей модели на протяжении четырех запусков, каждый из которых имел свое случайное зерно.

Производительность кластеризации

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

Рисунок автора.

Имея это в виду, мы симулировали отсутствие помеченных данных, используя небольшой поднабор помеченных обучающих данных наборов данных бенчмарка. Количество использованных помеченных примеров было выбрано произвольно.

Мы извлекли отчетную точность кластеризации DEC, VaDE, ClusterGAN и N2D из литературы в качестве базовых результатов, и в таблице выше видно сводку наших результатов, где наш подход превосходит базовые модели.

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

Визуализация разделенных представлений

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

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

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

Рисунок автора. 3D-визуализация, сравнивающая исходное представление и разделенное представление латентного кода трех наборов данных. Для достижения этой визуализации, представления кодировались с использованием t-SNE с perplexity = 50 и learning rate = 10, оптимизированными на 5,000 итераций, с одним и тем же случайным зерном для всех вычислений. Однако для кластеризации мы использовали более высокую размерность для достижения лучшей производительности кластеризации.

Обучение на меньшем числе помеченных примеров

Мы также попробовали обучить нашу модель на меньшем числе помеченных примеров.

Рисунок автора. Точность кластеризации на тестовых наборах данных MNIST и Fashion-MNIST при использовании небольших подмножеств помеченных данных для обучения. Исходное представление и базовый автокодировщик не используют помеченные данные.

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

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

Заключение

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

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

После публикации нашей работы, несколько других статей продолжили развивать мягкую потерю ближайшего соседа, или считались достаточно похожими. Особо стоит отметить статью о обучении с контрастивным предпочтением (SupCon) от Google, но разница заключается в том, что подход SupCon предлагает нормализацию вложений, увеличение использования аугментации данных, использование одноразового контрастного блока и двухступенчатое обучение.

С другой стороны, наша работа требует относительно небольших аппаратных ресурсов при достижении хороших результатов.

Литература

  • Frosst, Nicholas, Nicolas Papernot и Geoffrey Hinton. “Analyzing and improving representations with the soft nearest neighbor loss.” Международная конференция по машинному обучению. PMLR, 2019.
  • Goldberger, Jacob и др. “Neighbourhood components analysis.” Продвинутые методы обработки нейронной информации. 2005.
  • Khosla, Prannay, и др. “Supervised contrastive learning.” Продвинутые методы обработки нейронной информации 33 (2020): 18661–18673.
  • Salakhutdinov, Ruslan и Geoff Hinton. “Learning a nonlinear embedding by preserving class neighbourhood structure.” Искусственный интеллект и статистика. 2007.