Uniform Manifold Approximation and Projection (UMAP) — алгоритм машинного обучения, выполняющий нелинейное снижение размерности.
История создания и описание UMAP был создан Лилендом Макиннесом совместно с его коллегами из Таттского института. Целью было получить алгоритм, похожий на t-SNE, но с более сильным математическим обоснованием.
При снижении размерности UMAP сначала выполняет построение взвешенного графа, соединяя ребрами только те объекты, которые являются ближайшими соседями. Множество из ребер графа — это нечёткое множество с функцией принадлежности, она определяется как вероятность существования ребра между двумя вершинами. Затем алгоритм создает граф в низкоразмерном пространстве и приближает его к исходному, минимизируя сумму дивергенций Кульбака-Лейблера для каждого ребра из множеств.
Алгоритм UMAP используется в различных областях науки: биоинформатика, материаловедение, машинное обучение.
Принцип работы алгоритма На обработку алгоритму поступает выборка из объектов: . UMAP рассчитывает расстояние между объектами по заданной метрике и для каждого объекта определяет список из его ближайших соседей: .
Помимо этого, для каждого объекта рассчитывается расстояние до его ближайшего соседа: . А также величина , заданная уравнением:
.
Далее алгоритм выполняет построение взвешенного ориентированного графа, в котором ребра соединяют каждый объект с его соседями. Вес ребра от объекта до его соседа рассчитывается следующим образом:
Полученная ранее нормирует сумму весов для каждого объекта к заданному числу .
Так как UMAP строит взвешенный ориентированный граф, то между вершинами могут существовать два ребра с разными весами. Вес ребра интерпретируется как вероятность существования данного ребра от одного объекта к другому. Исходя из этого, ребра между двумя вершинами объединяются в одно с весом, равным вероятности существования хотя бы одного ребра:
.
Таким образом, алгоритм получает взвешенный неориентированный граф.
Множество ребер такого графа является нечетким множеством из случайных величин Бернулли. Алгоритм создает новый граф в низкоразмерном пространстве и приближает множество его ребер к исходному. Для этого он минимизирует сумму дивергенций Кульбака-Лейблера для каждого ребра из исходного и нового нечетких множеств:
,
— функция принадлежности нечеткого множества из ребёр в высокоразмерном пространстве,
— функция принадлежности нечеткого множества из ребёр в низкоразмерном пространстве.
UMAP решает задачу минимизации с помощью стохастического градиентного спуска. Полученное множество из ребер определяет новое расположение объектов и, соответственно, низкоразмерное отображение исходного пространства.
Программное обеспечение Руководство по установке библиотеки Применение в языке R
Литература
Примечания
Ссылки Авторская презентация алгоритма Авторский туториал и преимущества UMAP Примеры работ в UMAP: 1 и 2 Обзор алгоритма Принцип работы алгоритма и примеры
Категория:Алгоритмы машинного обучения Категория:Снижение размерности Категория:Анализ данных