Нестандартная кластеризация 4: Self-Organizing Maps, тонкости, улучшения, сравнение с t-SNE

Часть первая — Affinity propagation
Часть вторая — DBSCAN
Часть третья — кластеризация временных рядов
Часть четвёртая — SOM

Self-organizing maps (SOM, самоорганизующиеся карты Кохонена) — знакомая многим классическая конструкция. Их часто поминают на курсах машинного обучения под соусом «а ещё нейронные сети умеют вот так». SOM успели пережить взлёт в 1990-2000 годах: тогда им пророчили большое будущее и создавали новые и новые модификации. Однако, в XXI веке SOM понемногу уходят на задний план. Хоть новые разработки в сфере самоорганизующихся карт всё ещё ведутся (большей частью в Финляндии, родине Кохонена), даже на родном поле визуализации и кластеризации данных карты Кохонена всё чаще уступает t-SNE.

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

Основные идеи алгоритма

Вкратце напомню стандартный алгоритм обучения SOM[1]. Здесь и далее $$ ($$) — матрица со входными данными, где $$ — количество элементов в наборе данных, а $$ — размерность данных. $$ — матрица весов ($$), где $$ — количество нейронов в карте. $$ — скорость обучения, $$ — коэффициент кооперации (см. ниже), $$ — количество эпох.

$$ ($$) — матрица расстояний между нейронами в слое. Обращу ваше внимание, что последняя матрица это не то же самое, что $$. Для нейронов есть два расстояния: расстояние в слое ($$) и разница между значениями.

Также обратите внимание, что хоть нейроны часто для удобства рисуются так, будто бы они «нанизаны» на квадратную сетку, это совсем не означает, что и хранятся они как тензор $$. Сетку олицетворяет $$.

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

Алгоритм 1 (стандартный алгоритм обучения SOM):
Вход: $$, $$, $$, $$, $$, $$

1. Инициализировать $$
2. $$ раз:
   
   
   1. Перемешать список индексов случайным образом order: = shuffle($$)
   2. Для каждого $$ из order:
      
      1. $$ // Берём случайный вектор из X
      2. $$ // Находим номер ближайшего к нему нейрона
      3. $$ // Находим коэффициент близости нейронов по сетке. Pаметьте, что $$ всегда 1
      4. $$
   3. $$ := $$$$
   4. $$ := $$$$

Каждую эпоху обучения мы перебираем элементы входного датасета. Для каждого элемента мы находим ближайший к этому $$ нейрон, затем обновляем его веса и веса всех его соседей по слою в зависимости от расстояния до $$ и от коэффициента кооперации $$. Чем больше $$, тем больше нейронов эффективно обновляют веса на каждом шаге. Картинка ниже — графическая интерпретация шагов А1.2.2.1-А1.2.2.4 для случая, когда $$ большой (1) и когда малый (2) при одной и той же скорости обучения и ближайшем векторе.

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

Несколько эпох обучения карты Кохонена для наглядности:

Если моего краткого напоминания алгоритма оказалось недостаточно, прочитайте эту статью, где шаги в А1 рассмотрены более подробно.

Таким образом, основные идеи SOM:

• Принудительное внедрение некоторого порядка между нейронами. $$ мягко переносится на $$, в пространство данных.
• Стратегия Winner Takes All (WTA). На каждом шаге обучения мы определяем ближайший «победивший» нейрон и исходя из этого знания обновляем веса.
• Кооперация перерастает в эгоизм $$ глобальная примерная подстройка перерастает в точную локальную. Пока $$ большая, обновляется заметная часть $$ и стратегия WTA не так видна, когда $$ стремится к нулю, $$ обновляются по одному.

Сразу напрашивается несколько тривиальных модификаций:

• Не обязательно использовать гауссиану для вычисления $$ на шаге А1.2.2.3. Первый кандидат в альтернативные варианты — распределение Коши. Как известно, оно имеет более тяжёлые хвосты: больше нейронов будут изменяться на этапе кооперации.
• Затухания $$ и $$ не обязаны быть экспоненциальными. Кривая затухания в виде сигмоиды или ветви гауссианы может дать алгоритму больше времени для грубой подстройки.
• Не обязательно крутиться в цикле именно $$ раз. Можно прекращать итерации, если значения W не будут меняться на протяжении нескольких эпох.
• Обучение напоминает обычный SGD. «Напоминает», потому что не существует какой-либо функции энергии, которую бы этот процесс оптимизировал[2]. Строгую математику нам портит шаг А1.2.2.1 — взятие ближайшего вектора. Существуют модификации SOM, где энергия таки есть, но мы и так вдаёмся в детали. Смысл в том, что это не мешает использовать на шаге А1.2.2.4 вместо обычных обновлений весов, скажем, импульс Нестерова (Nesterov momentum).
• Добавление небольших случайных пертурбаций в градиент хоть и приносит меньшую пользу, чем в случае обычных многослойных нейронных сетей, всё равно выглядит полезным приёмом для избегания седловых точек[3].
• Self-organizing maps поддерживают обучение подвыборками (batches)[1]. Их применение позволяет проводить обучение быстрее и глаже проскакивать плохие конфигурации $$
• Не забывайте про нормализацию входных значений и использование вектора весов входных переменных, если известно, что какие-то фичи важнее других.

Топология нейронов

Чуть менее очевидная модификация самоорганизующихся карт, в которой состоит их сила и уникальность, но про которую постоянно забывают, кроется в этапе инициализации $$ и $$. Слой Кохонена в примерах постоянно изображают как сетку, но это ни в коей мере не обязательно. Наоборот, всячески советуется подстраивать взаимное расположение нейронов ($$) в слое под данные.

Как минимум, вместо обычной сетки лучше использовать гексагональную: квадратная сетка искажает результаты в пользу прямых линий, да и менее приятна на вид чем шестиугольная. Если предполагается, что данные циклические, стоит инициализировать $$, будто нейроны находятся на ленте или даже на торе (см. рис. ниже, номер 1). Если вы пытаетесь вместить в SOM трёхмерные данные, которые заведомо не ложатся на гиперскладку, следует воспользоваться структурой «ворсистый ковёр» (2). Если известно, что какие-то кластеры могут далеко отстоять от других, попробуйте «лепестковую» структуру слоя (3). Совсем хорошо, если известно, что данные имеют некоторую иерархию: тогда можно в качестве $$ можно взять матрицу расстояний графа этой иерархии (4).

В общем, $$ ограничивается вашей фантазией, знанием о данных и удобством последующей визуализации нейронов. Из-за последнего фактора не стоит делать, например, кубический слой Кохонена. Утверждение собственного порядка между нейронами — мощный инструмент, но следует помнить, что чем сложнее структура $$, тем сложнее инициализировать начальные веса в $$ и тем больше вероятность получить на выходе так называемый перекрут (kink) в слое Кохонена. Перекрут — дефект обучения, когда $$ глобально соответствует $$ и данным, за исключением некоторых особых точек, в которых слой перекручивается, неестественно растягивается или делится между двумя кластерами. При этом выбраться из этого состояния алгоритм обучения SOM не может, не разрушив уже устоявшейся структуры. Несложно увидеть, что перекрут — аналог глубокого локального минимума в обучении обычных нейронных сетей.

Абстрактный пример классического перекрута:

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

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

Поэтому часто приходится делать так, чтобы нейроны просто равномерно рассеялись по всему пространству данных без пересечений (как на рисунке посередине), и мириться с тем, что не во всех областях плотность нейронов будет отвечать плотности данных.

Winner relaxation/winner enhancing

Эта идея была изначально предложена Кохоненом[1], а затем обобщена его последователями[4]. Что если отнимать или прибавлять к обновлению нейрона-победителя обновления его соседей? Математически это выглядит так: шаг А1.2.2.4 для нейрона победителя заменяется на

$$

Где $$ — параметр расслабления. Обновления остальных нейронов остаются без изменений либо к ним добавляется часть расслабляющего слагаемого. Звучит странно; получается, что если $$ и у нейрона много соседей, то он может даже откатываться назад от $$? Если не применять ограничение сверху на длину вектора, так и есть:

При отрицательном $$ нейрон как бы подтягивает к себе своих соседей, а при положительном, наоборот, стремится выпрыгнуть из их окружения. Разница особенно заметна в начале обучения. Вот пример состояния SOM после первой эпохи для одинаковой начальной конфигурации и отрицательном, нулевом и положительном $$ соответственно:

Из-за описанных выше эффектов $$ нейроны разлетаются более широким веером, при $$ — вытягиваются. Соответственно, в первом случае покрытие будет более равномерным, а во втором — больший эффект будут иметь малые обособленные кластеры и выбросы. В последнем случае в верхней части графика также видно возможный перекрут. В литературе советуется $$, но я обнаружил, что хорошие результаты можно получить и при гораздо больших по модулю значениях. Обратите внимание, что в добавленное слагаемое входит $$, которое, в свою очередь, зависит от $$. Следовательно, вышеописанный приём будет играть большую роль в начале обучения — на этапе сотрудничества.

Cluster refinement phase

Часто случается так, что после основного цикла алгоритма оказывается, что хоть нейроны SOM и прицепились к чему-то, их плотность на кластерах вполне сравнима с плотностью в местах, где кластеров нет. Проводить анализ в таких условиях довольно сложно. Нарни Манукьян и команда предлагают[5] довольно простое решение: вслед за основным алгоритмом запускать ещё один цикл подгонки нейронов. Алгоритм 2, Cluster refinement phase (фаза подстройки кластеров): Вход: $$, $$, $$, $$, $$, $$

1. $$ раз:
   
   
   1. Перемешать список индексов случайным образом order: = shuffle($$)
   2. Для каждого $$ из order:
      
      
      1. $$ // Берём случайный вектор из X
      2. $$ // Находим коэффициент близости нейронов к выбранному элементу данных
      3. $$
   3. $$ := $$$$
   4. $$ := $$$$

Хоть алгоритм выглядит и очень похоже на А1, обратите внимание, что теперь мы не ищем ближайший нейрон, а просто пододвигаем все нейроны к $$. Из-за взаимодействия $$ в экспоненте в A2.2.2.2 и на этапе обновления весов изменяются по сути только нейроны, находящиеся в определённом кольце от $$. Для наглядности посмотрим на пять эпох подстройки:

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

Впрочем, последнюю проблему можно избежать, если взять вместо экспоненты какую-нибудь функцию, которая после некоторого максимального значения обращается в 0.

Авторы статьи советуют использовать вместо отдельного параметра скорости обучения ту же $$, но это откровенно говоря не работает: если $$ большой (порядка единицы), алгоритм идёт вразнос, если маленький (0.01), то ничего вообще не обновляется. Странно, быть может, у них были какие-то хорошие данные или подогнанный вектор важности переменных?

Визуализация, Rectifying SOM

Пока что я не сказал ни слова именно о кластеризации данных при помощи SOM. Построенная при помощи $$ и $$ сетка — забавная визуализация, но сама по себе она ничего не говорит о количестве кластеров. Более того, я бы даже сказал, что красивые разноцветные сетки, которые можно нагуглить по запросу «SOM визуализация» — скорее приём для пресс-релизов и популярных статей, чем реально полезная вещь.

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

Более интересный способ — запустить поверх получившейся матрицы $$ какой-нибудь другой алгоритм кластеризации. Подойдёт, например, DBSCAN, особенно вместе CR-модификацией SOM, описанной выше. Функцию расстояния второго алгоритма следует комбинировать из расстояния по сетке в слое ($$) и реального расстояния между нейронами ($$), чтобы не потерять топологическую информацию о складке.

Но более продвинутым кажется накапливание релевантной информации о кластерах прямо во время работы основного алгоритма. Эрен Голге и Пинар Дайгулу предлагают[6] каждую эпоху работы основного алгоритма запоминать, сколько раз активировался нейрон (т.е. нейрон оказывался победителем или его вес обновлялся, т.к. победителем оказывался близкий по слою нейрон), и на основании этого судить, олицетворяет ли нейрон кластер или повис в пустом пространстве.

Алгоритм 3, Rectifying SOM (А1 с изменениями):
Вход: $$, $$, $$, $$, $$, $$

1. Инициализировать $$
2. Инициализировать $$ // Excitement score — полный счёт возбуждения нейрона
3. $$ раз:
   
   
   1. Инициализировать $$ // Win count — счёт возбуждения нейрона в текущую эпоху
   2. Перемешать список индексов случайным образом order: = shuffle($$)
   3. Для каждого $$ из order:
      
      1. $$ // Берём случайный вектор из X
      2. $$ // Находим номер ближайшего к нему нейрона
      3. $$ // Находим коэффициент близости нейронов по сетке. Pаметьте, что $$ всегда 1
      4. $$
      5. $$ // Обновляем текущий счёт активации
   4. $$ := $$
   5. $$ := $$
   6. $$ // Накапливаем общий счёт

Чем чаще нейрон оказывается победителем, тем больше вероятность, что он где-то в толще кластера, а не вне её. Обратите внимание, что полный счёт нейронов накапливается с множителем $$: чем меньше скорость обучения, тем больший вес будет иметь WC. Так сделано, чтобы последние эпохи цикла вносили больший вклад, чем первые. Это можно сделать и другими способами, так что несильно привязывайтесь к именно этой конкретной форме.

ES — безразмерная величина, её абсолютные значения не несут особого смысла. Просто чем больше значение, тем больше шансов, что нейрон прицепился к чему-то значимому. После окончания А3 следует как-либо нормализовать получившийся вектор. После наложения ES на нейроны получится примерно такая картина:

Крупные красные точки представляют нейроны с высоким счётом возбуждения, маленькие красно-фиолетовые — с малым. Обратите внимание, что RSOM чувствителен ко способу финальной обработки ES и к кластерам разной плотности в данных (см. нижний правый угол картинки). Убедитесь, что вы задали больше эпох чем нужно для сходимости алгоритма, чтобы ES точно успел накопить правильные значения.

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

Прочее

В обзор не вошли

• Модификации SOM для работы с категориальными данными[7], последовательностями, картинками и прочими, неродными для SOM, видами данных[1].
• Работы связанные со временной асимметричностью функций близости нейронов по сетке.
  Автор утверждает, что это позволяет бороться с перекрутами[8].
• Исследования, связанные с контролем над степенью покрытости данных нейронами (борьба с искажениями на краях датасета)[9].
• Накопление информации о важности определённых входов[10].
• Кодирование данных при помощи SOM[1].
• Хитрые способы инициализации $$[11][12].
• Возможность добавить дополнительное слагаемое упругости. Упругость служит аналогом регуляризации в обычных нейронных сетях, запрещая слишком запутанные конфигурации.
• Многие другие интересные, но слишком специальные вещи.

Сравнение SOM и t-SNE

	SOM	t-SNE
Сложность	$$	Barnes-Hut t-SNE — $$, но другие реализации могут быть более вычислительноёмкими
Количество гиперпараметров	3-5, возможно намного больше + матрица расстояний на нейронах. Обязательны количество эпох, learning rate и начальный коэффициент сотрудничества. Также часто указываются затухание скорости обучения и коэффициент сотрудничества, но с ними почти никогда не возникает проблем.	3-4, возможно больше + метрика на данных. Обязательны количество эпох, learning rate и perplexity, часто встречается early exaggeration. Perplexity довольно магический, однозначно придётся с ним повозиться.
Разрешение результирующей визуализации	Элементов не больше, чем нейронов ($$)	Элементов не больше, чем элементов в наборе данных ($$)
Топология визуализации	Любая, нужно лишь предоставить матрицу расстояний между нейронами	Только обычная плоскость или трёхмерное пространство
Дообучение, расширение структуры	Есть, довольно тривиально реализовать	Нет
Поддержка дополнительных слоёв преобразований	Есть, можно поставить перед слоем Кохонена сколько угодно плотносоединённых или свёрточных слоёв и обучить обычным backprop'ом	Нет, только ручное преобразование данных и feature-engeneering
Предпочитаемые типы кластеров	По умолчанию отлично отображает кластеры в виде двумерных складок и экзотические кластеры. Нужны ухищрения, чтобы хорошо визуализировать структуры с размерностью больше двух.	Замечательно отображает гипершары. Гиперскладки и экзотические чуть хуже, сильно зависит от функции расстояния.
Предпочитаемая размерность пространства данных	Зависит от данных, но чем больше, тем хуже. Алгоритм может деградировать даже при $$, так как у гиперскладки, образованной нейронами появляется слишком много степеней свободы.	Любая, пока не начнёт сказываться проклятие размерности
Проблемы с начальными данными	Нужно инициализировать веса нейронов. Это может быть технически сложно в случае нестандартной матрицы расстояний между нейронами (особенно топологии типа «граф»)	Нет
Проблемы с выбросами	Есть, особенно если они распределены неравномерно	Нет, на визуализации они тоже будут выбросами
Эффекты на краях распределения данных	Часть данных остаётся недопокрытой SOM	Почти незаметны
Проблемы с ложноположительными кластерами	Нет	Ещё какие
Размер кластеров в визуализации	Несёт смысловую нагрузку	Почти всегда ничего не значит
Расстояние между кластерами в визуализации	Несёт смысловую нагрузку	Часто ничего не значит
Плотность кластеров в визуализации	Обычно имеет смысловую нагрузку, но может вводить в заблуждение в случае плохой инициализации	Часто ничего не значит
Форма кластеров в визуализации	Несёт смысловую нагрузку	Может обманывать
Как сложно оценить качество кластеризации	Очень сложно :(	Очень сложно :(

Казалось бы, SOM выигрывает по вычислительной сложности, однако не стоит радоваться раньше времени, не увидев $$ под О-большим. $$ зависит от желаемого разрешения самоорганизующейся карты, которое зависит от разброса и неоднородности данных, которое, в свою очередь, неявно зависит от $$ и $$. Так что в реальной жизни сложность — что-то вроде $$.

В приведённой таблице видны сильные и слабые стороны SOM и t-SNE. Легко можно понять, почему самоорганизующиеся карты уступили место другим методам кластеризации: хоть визуализация картами Кохонена более осмыслена, позволяет наращивание новых нейронов и задание желаемой топологии на нейронах, деградация алгоритма при большом $$ сильно подкашивает востребованность SOM в современной науке о данных. Кроме того, если визуализацию при помощи t-SNE можно сразу использовать, самоорганизующимся картам нужна постобработка и/или дополнительные усилия по визуализации. Дополнительный негативный фактор — проблемы с инициализацией $$ и перекрутами.

Значит ли это, что самоорганизующиеся карты остались в прошлом data science? Не совсем. Нет-нет, да и приходится иногда обрабатывать не очень многомерные данные — для этого вполне можно воспользоваться SOM. Визуализации получаются действительно довольно красивые и эффектные. Если не лениться применять доработки алгоритма, SOM отлично находит кластеры на гиперскладках.

Спасибо за внимание. Надеюсь, моя статья вдохновить кого-нибудь на создание новых SOM-визуализаций. С гитхаба можно скачать код с минимальным примером SOM с основными оптимизациями, предложенными в статье и посмотреть на анимированное обучение карты. В следующий раз я постараюсь рассмотреть алгоритм «нейронный газ», который также основан на конкурентном обучении.

[1]: Self-Organizing Maps, book; Teuvo Kohonen
[2]: Energy functions for self-organizing maps; Tom Heskesa, Theoretical Foundation SNN, University of Nijmegen
[3]: bair.berkeley.edu/blog/2017/08/31/saddle-efficiency
[4]: Winner-Relaxing Self-Organizing Maps, Jens Christian Claussen
[5]: Data-Driven Cluster Reinforcement and Visualization in Sparsely-Matched Self-Organizing Maps; Narine Manukyan, Margaret J. Eppstein, and Donna M. Rizzo
[6]: Rectifying Self Organizing Maps for Automatic Concept Learning fromWeb Images; Eren Golge & Pinar Duygulu
[7]: An Alternative Approach for Binary and Categorical Self-Organizing Maps; Alessandra Santana, Alessandra Morais, Marcos G. Quiles
[8]: Temporally Asymmetric Learning Supports Sequence Processing in Multi-Winner Self-Organizing Maps
[9]: Magnification Control in Self-Organizing Maps and Neural Gas; Thomas Villmann, Jens Christian Claussen
[10]: Embedded Information Enhancement for Neuron Selection in Self-Organizing Maps; Ryotaro Kamimural, Taeko Kamimura
[11]: Initialization Issues in Self-organizing Maps; Iren Valova, George Georgiev, Natacha Gueorguieva, Jacob Olsona
[12]: Self-organizing Map Initialization; Mohammed Attik, Laurent Bougrain, Frederic Alexandre