Isomap

Isomap - это метод нелинейного уменьшения размерности . Это один из нескольких широко используемых методов низкоразмерного вложения. ^[1] Isomap используется для вычисления квазиизометрического низкоразмерного вложения набора многомерных точек данных. Алгоритм обеспечивает простой метод оценки внутренней геометрии многообразия данных, основанный на грубой оценке соседей каждой точки данных на многообразии. Isomap очень эффективен и обычно применим к широкому спектру источников данных и размерностей.

Введение [ править ]

Isomap является одним из представителей методов изометрического отображения и расширяет метрическое многомерное масштабирование (MDS) за счет включения геодезических расстояний, налагаемых взвешенным графом. Чтобы быть конкретным, классическое масштабирование метрической MDS выполняет низкоразмерное встраивание на основе попарного расстояния между точками данных, которое обычно измеряется с использованием прямого евклидова расстояния . Isomap отличается использованием геодезического расстояния, индуцированного графом окрестностей, вложенным в классическое масштабирование. Это сделано для включения структуры коллектора в результирующее вложение. Isomap определяет геодезическое расстояние как сумму весов ребер на кратчайшем пути между двумя узлами (вычисляется с использованиемАлгоритм Дейкстры , например). Верхние n собственных векторов матрицы геодезических расстояний представляют координаты в новом n- мерном евклидовом пространстве.

Алгоритм [ править ]

Ниже приводится очень общее описание алгоритма Isomap .

• Определите соседей каждой точки.
  • Все точки в некотором фиксированном радиусе.
  • K ближайших соседей.
• Постройте граф окрестностей.
  • Каждая точка соединена с другой, если это K ближайшего соседа.
  • Длина ребра равна евклидову расстоянию.
• Вычислить кратчайший путь между двумя узлами.
  • Алгоритм Дейкстры
  • Алгоритм Флойда – Уоршолла
• Вычислить низкоразмерное вложение.
  • Многомерное масштабирование

Расширения ISOMAP [ править ]

• Landmark ISOMAP (L-ISOMAP) : Landmark-Isomap - это вариант Isomap, который работает быстрее, чем Isomap. Однако точность коллектора снижается из-за незначительного фактора. В этом алгоритме используются n << N контрольных точек из общего числа N точек данных, и вычисляется матрица nxN геодезического расстояния между каждой точкой данных и контрольными точками. Затем к матрице применяется Landmark-MDS (LMDS), чтобы найти евклидово вложение всех точек данных. ^[2]

• C Isomap  : C-Isomap включает увеличение областей с высокой плотностью и сжатие областей с низкой плотностью точек данных в коллекторе. Веса краев, которые максимизированы в многомерном масштабировании (MDS), изменяются, а все остальное остается неизменным. ^[2]
• Развертывание параллельного переноса  : заменяет оценки геодезических расстояний на основе путей Дейкстры на приближения на основе параллельного переноса , повышая устойчивость к нерегулярности и пустотам в выборке. ^[3]

Возможные проблемы [ править ]

Связность каждой точки данных в графе соседства определяется как ее ближайшие k евклидовых соседей в многомерном пространстве. Этот шаг уязвим для "ошибок короткого замыкания", если k слишком велико по отношению к структуре коллектора или если шум в данных немного сдвигает точки за пределы коллектора. ^[4] Даже одна ошибка короткого замыкания может изменить многие элементы в матрице геодезических расстояний, что, в свою очередь, может привести к совершенно иному (и неправильному) низкоразмерному встраиванию. И наоборот, если k слишком мало, граф окрестности может стать слишком разреженным для точной аппроксимации геодезических путей. Но в этот алгоритм были внесены улучшения, чтобы он лучше работал с разреженными и зашумленными наборами данных. ^[5]

Связь с другими методами [ править ]

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

${\ displaystyle K = - {\ frac {1} {2}} HD ^ {2} H \,}$

где - поэлементный квадрат матрицы геодезических расстояний D = [ D _ij ], H - центрирующая матрица, заданная формулой${\ Displaystyle D ^ {2} = D_ {ij} ^ {2}: = (D_ {ij}) ^ {2}}$

${\ displaystyle H = I_ {n} - {\ frac {1} {N}} e_ {N} e_ {N} ^ {T}, \ quad {\ text {where}} e_ {N} = [1 \ \ dots \ 1] ^ {T} \ in \ mathbb {R} ^ {N}.}$

Однако матрица ядра K не всегда положительно полуопределенная . Основная идея для ядра Isomap состоит в том, чтобы сделать эту K как матрицу ядра Мерсера (которая является положительно полуопределенной) с использованием метода постоянного сдвига, чтобы связать ее с PCA ядра, чтобы естественным образом возникало свойство обобщения. ^[6]

См. Также [ править ]

• Ядро PCA
• Спектральная кластеризация
• Нелинейное уменьшение размерности

Ссылки [ править ]

Внешние ссылки [ править ]

• Веб-страница Isomap в Стэнфордском университете
• Первоначальная статья Tenenbaum et al.
• Сравнение глобальных и локальных методов нелинейного уменьшения размерности в Массачусетском технологическом институте, Тененбаум и др.