Изомап
Isomap — это метод нелинейного уменьшения размерности . Это один из нескольких широко используемых методов низкоразмерного встраивания. [1] Isomap используется для вычисления квазиизометрического низкоразмерного внедрения набора многомерных точек данных. Алгоритм предоставляет простой метод оценки внутренней геометрии многообразия данных на основе грубой оценки соседей каждой точки данных на многообразии. Isomap высокоэффективен и обычно применим к широкому спектру источников данных и размерностей.
Введение
[ редактировать ]Isomap является одним из представителей методов изометрического картографирования и расширяет метрическое многомерное масштабирование (MDS) за счет включения геодезических расстояний, определяемых взвешенным графом. Точнее, классическое масштабирование метрического MDS выполняет низкоразмерное встраивание на основе попарного расстояния между точками данных, которое обычно измеряется с использованием прямолинейного евклидова расстояния . Isomap отличается использованием геодезического расстояния, индуцированного графом окрестностей, встроенным в классическое масштабирование. Это делается для включения структуры многообразия в полученное вложение. Isomap определяет геодезическое расстояние как сумму весов ребер вдоль кратчайшего пути между двумя узлами (вычисленного с использованием алгоритма Дейкстры , например, ). Верхние n собственных векторов матрицы геодезических расстояний представляют координаты в новом n -мерном евклидовом пространстве.
Алгоритм
[ редактировать ]очень общее описание алгоритма Isomap Ниже приведено .
- Определите соседей каждой точки.
- Все точки в некотором фиксированном радиусе.
- К ближайшие соседи.
- Постройте граф окрестности.
- Каждая точка связана с другой, если она является 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 имеет вид
где — поэлементный квадрат матрицы геодезических расстояний D = [ D ij ], H — центрирующая матрица, определяемая формулой
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3adf5e4dbed1feaf8088f8d68cffcbbe86fffd41)
Однако ядро матрицы K не всегда является положительно полуопределенным . Основная идея ядра Isomap состоит в том, чтобы сделать это K как матрицу ядра Мерсера (то есть положительно полуопределенную) с использованием метода постоянного сдвига, чтобы связать его с ядром PCA так, чтобы естественным образом возникло свойство обобщения. . [6]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б Тененбаум, Джошуа Б.; Сильва, Вин де; Лэнгфорд, Джон К. (22 декабря 2000 г.). «Глобальная геометрическая основа для нелинейного уменьшения размерности». Наука . 290 (5500): 2319–2323. дои : 10.1126/science.290.5500.2319 .
- ^ Jump up to: а б Сильва, Вин; Тененбаум, Джошуа (2002). «Глобальные и локальные методы нелинейного уменьшения размерности» . Достижения в области нейронных систем обработки информации . 15 . МТИ Пресс.
- ^ Буднинский, Макс; Инь, Глория; Фэн, Леман; Тонг, Иин; Дебрен, Матье (2019). «Развертывание параллельного транспорта: подход к обучению на основе соединений» . SIAM Journal по прикладной алгебре и геометрии . 3 (2): 266–291. arXiv : 1806.09039 . дои : 10.1137/18M1196133 . ISSN 2470-6566 .
- ^ М. Баласубраманян, Э. Л. Шварц, Алгоритм Isomap и топологическая устойчивость. Наука, 4 января 2002 г.: Том. 295 нет. 5552 р. 7
- ^ А. Саксена , А. Гупта и А. Мукерджи . Нелинейное уменьшение размерности с помощью локально линейных изомап, . Конспекты лекций по информатике , 3316:1038–1043, 2004.
- ^ Х. Чой, С. Чой, Надежная изомап ядра, Распознавание образов, Том. 40, № 3, стр. 853-862, 2007 г.