Кластеризация на выходе t-SNE

78

У меня есть приложение, в котором было бы удобно кластеризовать зашумленный набор данных, прежде чем искать эффекты подгрупп в кластерах. Сначала я посмотрел на PCA, но для достижения 90% изменчивости требуется ~ 30 компонентов, поэтому кластеризация на нескольких компьютерах приведет к выбросу большого количества информации.

Затем я попробовал t-SNE (впервые), который дает мне странную форму в двух измерениях, которая очень поддается кластеризации с помощью k-средних. Более того, запуск случайного леса на данных с назначением кластера в качестве результата показывает, что кластеры имеют достаточно разумную интерпретацию с учетом контекста проблемы, с точки зрения переменных, составляющих необработанные данные.

Но если я собираюсь сообщить об этих кластерах, как мне их описать? Кластеры K-средних на главных компонентах показывают людей, которые находятся рядом друг с другом с точки зрения производных переменных, которые составляют X% дисперсии в наборе данных. Какое эквивалентное утверждение можно сделать о кластерах t-SNE?

Возможно что-то с эффектом:

t-SNE показывает приблизительную смежность в лежащем в основе многомерном многообразии, поэтому кластеры на низкоразмерном представлении многомерного пространства максимизируют «вероятность» того, что смежные лица не будут находиться в одном кластере

Кто-нибудь может предложить лучшую рекламу, чем это?

generic_user
источник
1
Я бы подумал, что хитрость заключается в описании кластеров на основе исходных переменных, а не переменных в сокращенном пространстве.
Тим
1
Правильно, но без краткого, интуитивно понятного описания того, какую цель минимизирует алгоритм назначения кластера, я могу быть открыт для обвинений в выборе алгоритма кластеризации, который облегчает получение желаемых результатов.
generic_user
2
Для некоторых предостережений и хороших визуальных эффектов на t-SNE также взгляните на distill.pub/2016/misread-tsne
Tom Wenseleers

Ответы:

97

Проблема с t-SNE состоит в том, что он не сохраняет ни расстояния, ни плотность. Это только в некоторой степени сохраняет ближайших соседей. Разница невелика, но влияет на любой алгоритм на основе плотности или расстояния.

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

Теперь запустите t-SNE на этих данных. Вы обычно получите круг довольно однородной плотности. Если вы используете низкое недоумение, там могут быть даже странные паттерны. Но вы не можете больше различать выбросы.

Теперь давайте все усложним. Давайте использовать 250 точек в нормальном распределении в (-2,0) и 750 точек в нормальном распределении в (+2,0).

Входные данные

Предполагается, что это будет простой набор данных, например, с EM:

EM кластеризация

Если мы запустим t-SNE с недоумением по умолчанию 40, мы получим шаблон странной формы:

t-SNE p = 40

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

Если мы запустим t-SNE со слишком малым недоумением, таким как 20, мы получим больше таких шаблонов, которых не существует:

t-SNE p = 20

Это будет кластеризовать, например, с DBSCAN, но это даст четыре кластера. Так что будьте осторожны, t-SNE может создавать «поддельные» шаблоны!

Оптимальная путаница, кажется, где-то около 80 для этого набора данных; но я не думаю, что этот параметр должен работать для любого другого набора данных.

t-SNE p = 80

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

В заключение, используйте t-SNE для визуализации (и попробуйте разные параметры, чтобы получить что-то визуально приятное!), Но не запускайте кластеризацию впоследствии , в частности, не используйте алгоритмы на основе расстояния или плотности, поскольку эта информация была намеренно (!) потерянный. Подходы, основанные на графе соседства, могут быть хорошими, но тогда вам не нужно сначала запускать t-SNE заранее, просто используйте соседей немедленно (потому что t-SNE пытается сохранить этот nn-граф в значительной степени неповрежденным).

Больше примеров

Эти примеры были подготовлены для презентации статьи (но пока не могут быть найдены в статье, как я сделал этот эксперимент позже)

Эрих Шуберт и Майкл Герц.
Внутреннее t-стохастическое вложение соседей для визуализации и обнаружения выбросов - средство против проклятия размерности?
В кн .: Материалы 10-й Международной конференции по поиску и применению сходства (SISAP), Мюнхен, Германия. 2017

Во-первых, у нас есть эти входные данные:

Рыбы

Как вы можете догадаться, это происходит от изображения "color me" для детей.

Если мы запустим это через SNE ( не t-SNE , а предшественник):

SNE рыба

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

Но вы будете действительно удивлены выходом t-SNE:

t-SNE рыба

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

Два важных момента, чтобы объяснить это:

  1. SGD опирается на итеративную процедуру уточнения и может застрять в локальных оптимумах. В частности, это затрудняет алгоритм «переворачивает» часть данных, которые он отразил, так как это потребует перемещения точек через другие, которые должны быть отдельными. Поэтому, если некоторые части рыбы зеркально отражены, а другие части не зеркально отражены, возможно, это не удастся исправить.

  2. t-SNE использует t-распределение в проецируемом пространстве. В отличие от гауссовского распределения, используемого обычным SNE, это означает, что большинство точек будут отталкивать друг друга , потому что они имеют 0 сродство во входной области (гауссово быстро получает ноль), но> 0 сродство в выходной области. Иногда (как в MNIST) это делает визуализацию лучше. В частности, это может помочь «разделить» набор данных немного больше, чем во входной области. Это дополнительное отталкивание также часто вызывает очки для более равномерного использования области, что также может быть желательным. Но здесь, в этом примере, отталкивающие эффекты фактически приводят к разделению фрагментов рыбы.

Мы можем помочь (на этом игрушечном наборе данных) в первой проблеме, используя исходные координаты в качестве исходного положения, а не случайные координаты (как обычно используется с t-SNE). На этот раз изображение sklearn вместо ELKI, потому что версия sklearn уже имела параметр для передачи начальных координат:

Рыба, t-SNE, с исходными координатами в качестве инициализации

Как вы можете видеть, даже при «идеальном» начальном размещении t-SNE «сломает» рыбу в ряде мест, которые были изначально связаны, потому что отталкивание Student-t в выходной области сильнее, чем сродство Гаусса на входе пространство.

Как вы можете видеть, t-SNE (и SNE тоже!) - интересные методы визуализации , но с ними нужно обращаться осторожно. Я бы предпочел не применять k-means на результат! потому что результат будет сильно искажен, и ни расстояния, ни плотность не сохранятся хорошо. Вместо этого лучше использовать его для визуализации.

Эрих Шуберт
источник
1
Спасибо за ответ. Я могу представить методы адаптивной кластеризации на основе соседей, но есть ли какие-то конкретные хорошо разработанные, которые вы могли бы порекомендовать?
generic_user
1
CHAMAELEON, вероятно, является наиболее цитируемым, но, похоже, для основного шага доступен только двоичный файл. Идея звучит неплохо, но вы быстро ощутите те же эффекты, которые t-SNE делает видимыми. Такие, как склонность к «скоплению», как видно с p = 20, проблемы с концентраторами и анти-концентраторами и т. Д.
Эрих Шуберт
2
@AlexR: Недоумение используется для вычисления сходства в многомерном пространстве, которое t-sne затем пытается сопоставить в 2D. Изменение недоумения означает изменение сходства, поэтому я не понимаю, как сравнение полученных расхождений KL может быть значимым.
говорит амеба, восстанови Монику
1
@AlexR. «От недоумения зависит только условная вероятность пространства нижних измерений» - это утверждение неверно. Недоумение используется для выбора сигм, необходимых для eq (1), поэтому оно влияет на cond. Probs. на полном пространстве.
говорит амеба, восстанови Монику
1
Для некоторых предостережений и хороших визуальных эффектов на t-SNE также взгляните на distill.pub/2016/misread-tsne
Tom Wenseleers
34

Я хотел бы высказать несколько несогласное мнение с хорошо аргументированным (+1) и высоко голосуемым ответом @ErichSchubert. Эрих не рекомендует кластеризацию на выходе t-SNE и показывает несколько игрушечных примеров, где это может вводить в заблуждение. Он предлагает вместо этого применить кластеризацию к исходным данным.

используйте t-SNE для визуализации (и попробуйте другие параметры, чтобы получить что-то визуально приятное!), но не запускайте кластеризацию впоследствии, в частности, не используйте алгоритмы на основе расстояния или плотности, поскольку эта информация была намеренно (!) потеряна.

Я хорошо знаю, каким образом вывод t-SNE может вводить в заблуждение (см. Https://distill.pub/2016/misread-tsne/ ), и я согласен, что в некоторых ситуациях он может давать странные результаты.

Но давайте рассмотрим некоторые реальные многомерные данные.

Возьмите данные MNIST : 70000 однозначных изображений. Мы знаем, что в данных 10 классов. Эти классы кажутся хорошо разделенными для человеческого наблюдателя. Однако кластеризация данных MNIST в 10 кластеров является очень сложной проблемой. Я не знаю ни одного алгоритма кластеризации, который бы правильно группировал данные в 10 кластеров; что еще более важно, я не знаю никакой эвристики кластеризации, которая указала бы, что в данных есть 10 (не больше и не меньше) кластеров. Я уверен, что наиболее распространенные подходы не смогут это указать.

Но давайте вместо этого сделаем t-SNE. (Можно найти много цифр t-SNE, примененных к MNIST онлайн, но они часто неоптимальны. По моему опыту, для достижения хороших результатов необходимо довольно рано выполнять преувеличение в течение некоторого времени. Ниже я использую perplexity=50, max_iter=2000, early_exag_coeff=12, stop_lying_iter=1000). Вот то, что я получаю, слева без метки, а справа окрашено в соответствии с основной истиной:

MNIST T-SNE

Я бы сказал, что немаркированное представление t-SNE действительно предлагает 10 кластеров. Применение хорошего алгоритма кластеризации на основе плотности, такого как HDBSCAN с тщательно подобранными параметрами, позволит сгруппировать эти 2D данные в 10 кластеров.

В случае, если кто-то усомнится в том, что левый график выше действительно предлагает 10 кластеров, вот что я получаю с помощью трюка с «поздним преувеличением», где я дополнительно запускаю max_iter=200итерации exaggeration=4(этот трюк предлагается в этой замечательной статье: https://arxiv.org /abs/1712.09005 ):

MNIST t-SNE с поздним преувеличением

Теперь должно быть совершенно очевидно, что существует 10 кластеров.

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

А теперь еще больше реальных данных.

В случае MNIST мы знаем основную правду. Рассмотрим теперь некоторые данные с неизвестной наземной правдой. Кластеризация и t-SNE обычно используются для описания вариабельности клеток в данных одноклеточной RNA-seq. Например, Shekhar et al. В 2016 г. была предпринята попытка идентифицировать кластеры среди 27000 клеток сетчатки (в геноме мыши имеется около 20 тыс. Генов, поэтому размерность данных в принципе составляет около 20 тыс., Однако обычно начинается с уменьшения размерности с помощью PCA до 50 или около того). Они выполняют t-SNE и по отдельности выполняют кластеризацию (сложный конвейер кластеризации, за которым следуют некоторые объединения кластеров и т. Д.). Конечный результат выглядит приятным:

введите описание изображения здесь

Причина, по которой он выглядит таким приятным, заключается в том, что t-SNE создает четко различимые кластеры, а алгоритм кластеризации дает абсолютно одинаковые кластеры. Приятно.

Однако, если вы посмотрите в дополнениях, то увидите, что авторы испробовали много разных подходов к кластеризации. Многие из них выглядят ужасно на графике t-SNE, потому что, например, большой центральный кластер разделен на множество подкластеров:

введите описание изображения здесь

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

амеба говорит восстановить монику
источник
2
И для последнего примера, разве это не то, что @ErichSchubert наблюдал выше: вы можете получить визуально «приятные» результаты - что, очевидно, неправильно? Как с недоумением 20? Что tSNE любит разделять части (как в рыбе), которые не были разделены? Итак, вы знаете, что кластеры, которые вы видите, действительно являются отдельными кластерами? Мне не нравится этот "черный ящик" там. Да, мы склонны верить таким заговорам больше, но что, если они ошибаются?
Anony-Mousse
1
Ну, tSNE основан на NN. Соглашение с этим следует ожидать. tSNE - хороший выбор для визуализации NN. Хотя это не хорошо сохраняет сходство, поэтому, как я понимаю, его следует интерпретировать с осторожностью. Разрыв в tSNE не предполагает большого расстояния.
Anony-Mousse
1
+1 Любопытно, как работает UMAP по сравнению с t-SNE.
Пол
1
@Paul: автор заявляет о превосходстве UMAP с точки зрения времени вычислений. В наборе данных MNIST я обнаружил, что UMAP генерирует лучшее встраивание, чем t-SNE, но не уверен в других наборах данных. Насколько я знаю, недавно была версия t-SNE CUDA, которая намного быстрее, чем предыдущий самый быстрый t-SNE, но я не смог установить и протестировать.
SiXUlm
1
@SiXUlm github.com/KlugerLab/FIt-SNE работает намного быстрее, чем t- SNE Barnes-Hut, и часто быстрее, чем UMAP. Кроме того, во многих случаях можно добиться очень похожего встраивания с помощью t-SNE с использованием некоторых дополнительных настроек, например, в MNIST t-SNE с небольшим преувеличением дает почти то же самое, что и UMAP, см. Пример ноутбука Python в репозитории FIt-SNE.
говорит амеба, восстанови Монику
6

Я думаю, что с большим недоумением t-SNE может реконструировать глобальную топологию, как указано в https://distill.pub/2016/misread-tsne/ .

Из изображения рыбы я отобрал 4000 точек для t-SNE. С большим недоумением (2000), изображение рыбы было практически реконструировано.

Вот оригинальное изображение. Исходное изображение

Вот изображение, реконструированное с помощью t-SNE с недоумением = 2000. Восстановленное изображение t-SNE (недоумение = 2000)

renxwise
источник
8
Если вы выберете такие большие затруднения, это уже не так. Каждая точка примерно повседневная соседа. Это больше не локально. Да, двумерное изображение может быть затем приблизительно восстановлено, потому что оно является двумерным. Но не делать все это проще.
Anony-Mousse
1
Мое мнение, что tSNE с большим недоумением может реконструировать глобальную топологию. 2d изображение является примером, потому что его внутренняя размерность равна 2. Реальное применение tSNE должно выбирать правильную путаницу в соответствии с целью захвата локальных или глобальных характеристик.
renxwise
1
Сложность такого уровня означает, что вы используете слишком большое «ядро» и фактически просто используете расстояния. Это тогда вероятно вырождается в приблизительную и очень дорогую MDS. Просто используйте MDS тогда. SNE / tSNE действительно следует использовать с небольшими затруднениями и локальными окрестностями.
Эрих Шуберт
3
Именно так. Когда недоумение достаточно велико, tSNE действительно приближено к MDS, что показывает, что tSNE также может охватить глобальную структуру. Таким образом, утверждения о том, что tSNE может захватывать только локальные структуры, являются неверными. В отличие от MDS, tSNE может балансировать между локальными и глобальными структурами посредством выбора недоумения. Очевидно, что выбор недоумения зависит от набора данных.
Renxwise
Есть ли эмпирическое правило для выбора вероятного недоумения?
Catbuilts
5

Основываясь на имеющихся у нас математических данных, этот метод технически может сохранить расстояния! почему вы все игнорируете эту функцию! t -SNE - это преобразование евклидовых расстояний большой размерности между выборками в условные вероятности, которые представляют сходства. Я пробовал t- -SNE с более чем 11 000 образцов (в контексте геномики) параллельно с различными согласованными алгоритмами кластеризации, включая спектральную кластеризацию, сродство и, что важно, с кластеризацией GMM (которая является алгоритмом кластеризации на основе плотности!). В результате я нашел очень хороший согласованный результат между двумя подходами ( т-SNE против согласованных алгоритмов кластеризации). Я полагаю, что интеграция t-SNE с согласованными алгоритмами кластеризации могла бы обеспечить лучшее подтверждение существующих локальных и глобальных структур данных.

Реза Рафи
источник
Существуют ли параметры, которые будут влиять на вероятность сохранения расстояний t-SNE?
Кит Хьюджитт
Это не консенсусные алгоритмы кластеризации. Консенсусная кластеризация - это тип ансамблевого обучения, который объединяет результаты повторения алгоритма кластеризации с некоторыми изменениями в параметрах или входных данных для получения окончательного результата кластеризации. Вы можете использовать подходы согласованной кластеризации со спектральной кластеризацией или GMM или любым другим алгоритмом кластеризации, но моя точка зрения на вашу терминологию немного не верна, вот и все :)
Кристофер Джон
1

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

Джеймс Ли
источник
0

Лично я испытал это однажды, но не с t-SNE или PCA. Мои исходные данные находятся в 15-мерном пространстве. Используя UMAP, чтобы сократить его до 2D и 3D вложений, я получил 2 отлично и визуально разделимых кластера на 2D и 3D графиках. Слишком хорошо, чтобы быть правдой. Но когда я «посмотрел» на исходные данные из диаграммы постоянства, я понял, что есть гораздо более «значимые» кластеры, а не только 2.

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

  • Кластеры в проецируемых данных соответствуют / подтверждают некоторую классификацию, определенную априори (представьте себе набор данных MNIST, где кластеры проецируемых данных очень хорошо соответствуют классификации цифр), и / или,

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

SiXUlm
источник
Почему вы доверяете «диаграмме постоянства» больше, чем UMAP? Я не думаю, что просмотр диаграммы постоянства можно описать как «просмотр исходных данных» ...
говорит амеба «Восстановить Монику»
Ты прав. Диаграмма постоянства показывает только некоторые характеристики исходных данных, чаще всего связанных компонентов, одномерных отверстий и гораздо более редких, двух или более размерных отверстий из-за дорогостоящих вычислений. Поэтому я должен был сказать, что могу только частично «посмотреть» на исходные данные, посмотрев на соответствующую диаграмму постоянства. Но я могу доверять тому, что наблюдаю из этой диаграммы постоянства, потому что она построена непосредственно из исходных данных.
SiXUlm
В отличие от этого, используя UMAP или любые другие методы уменьшения размеров, мы работаем только с прогнозируемой / измененной версией исходных данных. Как отмечалось в ответе с наибольшим количеством голосов, кластеризация может быть разной для разных вариантов выбора параметров.
SiXUlm