Автор Бетул Мешиоглу
Необходимость уменьшения размерности и связанные с этим проблемы:
Когда мы имеем дело с данными с многочисленными функциями, мы не можем извлечь значимые релевантные структуры данных, которые скрыты в высоких измерениях. Чтобы решить эту проблему, нам нужно преобразовать данные из более высокого измерения в более низкое измерение, где человеческий разум гораздо лучше понимает структуры с помощью визуализации или с помощью других инструментов. К сожалению, не все структуры данных могут быть полностью представлены в нижнем измерении. Например, методы анализа главных компонентов (PCA) и многомерного масштабирования (MDS) не всегда переносят нелинейность данных в более низкие измерения. Даже для алгоритмов, которые могут нести нелинейность, мы сталкиваемся с проблемой вычисления расстояния между точками данных, когда имеем дело с многообразиями данных. Вычисление евклидова расстояния между точками данных не отражает истинной топологии многообразия.
Что такое Isomap?
Метод под названием Isomap решает эту проблему, вычисляя расстояние между точками данных путем создания пути, который соединяет все промежуточные точки данных. Это расстояние называется геодезическим путем. Я хотел бы сравнить это со спиральной горкой на детской площадке. Для ребенка, который находится на вершине горки, есть два способа дотянуться до земли. Они могут либо спрыгнуть на землю, либо соскользнуть вниз. Спрыгнув на землю, вы проходите евклидово расстояние, а соскальзывая вниз, вы проходите геодезический путь. Это можно проиллюстрировать следующим образом:
На рисунке А пунктирная линия показывает евклидово расстояние, а синяя сплошная линия показывает геодезический путь. Когда мы распутываем этот бросок (приводя его к двумерному), мы видим, что точки данных на самом деле дальше друг от друга, чем то, что Евклидово расстояние заставило бы нас поверить в трехмерность. Это геодезическое расстояние на самом деле отражает истинную низкоразмерную геометрию многообразия, но PCA и MDS используют евклидово расстояние, поэтому не могут уловить внутреннюю двумерность.
Как работает Isomap?
Isomap сочетает в себе основные алгоритмические функции PCA и MDS; вычислительная эффективность, глобальная оптимальность и гарантии асимптотической сходимости. Помимо этого, они дают возможность изучить особенности нелинейных многообразий. Они построены на алгоритме MDS, но, как упоминалось выше, также оценивают геодезическое расстояние между удаленными точками, используя только входные пространственные расстояния.
Три шага алгоритма, достигающего этого, следующие:
1) Определить, какие точки являются соседями в многообразии (М), исходя из расстояний между парами точек во входном пространстве. Это хорошее приближение к геодезическому расстоянию для соседних точек. Для расчета можно использовать два метода:
· Расчет расстояния от определенной точки данных до всех точек данных в пределах фиксированного радиуса.
· Рассчитать расстояния от определенной точки данных до всех K ближайших соседей.
В конце концов получается взвешенный граф, где вершины представляют точки данных, а ребра представляют веса (расстояния между точками данных).
2) После того, как график получен, он обновляется следующим образом:
· Если две точки (i, j) соединяются, ничего не меняйте
· Если нет, пройдитесь по всем точкам данных (k=1,2,3,…, N) и для каждой точки данных рассчитайте расстояние от i до k и от k до j. Сложите эти два расстояния. Найдите точку данных (k), обеспечивающую кратчайшее расстояние от i до j (i+k+j+k). Это расстояние заносится в график (матрицу). Окончательная матрица будет содержать кратчайшие пути между всеми парами точек.
3) Последний шаг уменьшает размерность, применяя классическую МДС к матрице, полученной на шаге 2. Но в этом случае преобразование данных в d-мерное евклидово пространство осуществляется за счет сохранения внутренних геометрических особенностей многообразия.
Заключение
Остаточная дисперсия стабилизируется при более низких размерностях, чем PCA или MDS, что означает, что этот алгоритм захватывает больше статистических характеристик данных при более низких размерностях (2D или 3D), чем PCA или MDS. Кроме того, он работает и для нелинейных данных. Но мне интересно, будет ли этот алгоритм работать хорошо, если данных будет слишком мало. Мне также интересно, если бы швейцарский рулет был слишком туго свернут, алгоритм начал бы путаться в том, какая точка данных принадлежит какой поверхности? Создатели алгоритма говорят, что нам понадобится непрактичный размер выборки, чтобы преодолеть эти проблемы, но в целом он все еще сходится.
Примечание. Это краткое изложение статьи «Глобальная геометрическая структура для нелинейного уменьшения размерности», опубликованной Джошуа Б. Тененбаумом, Вин де Сильва, Джоном К. Лэнгфордом. Картинка тоже взята из этой газеты.
