Simplicial complexes — Симплициальные комплексы

Дискретная аппроксимация формы облака точек: точки, рёбра, треугольники и их многомерные аналоги.

Ключевые тезисы

Комплекс Вьеториса — Рипса соединяет точки, находящиеся ближе порога ε.
Комплекс Чеха точнее, но заметно дороже вычислительно.
Alpha-комплексы — компромисс для данных небольшой размерности.

Подробный разбор

2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Симплексы и комплексы

Как из облака точек собрать дискретную «фигуру».

0-симплекс — точка, 1-симплекс — отрезок, 2-симплекс — треугольник, 3-симплекс — тетраэдр.
Симплициальный комплекс — набор симплексов, склеенных по граням.
Комплекс аппроксимирует форму данных так, что её можно посчитать алгоритмически.

VR_{ε} (X) = {σ \subseteq X : d (x_{i}, x_{j}) \leq ε \forall x_{i}, x_{j} \in σ}

Обозначения

$σ$ стандартное отклонение — разброс величины
$ε$ радиус фильтрации: на каком масштабе точки считаются связанными
$x$ объект: вектор признаков

Комплекс Вьеториса — Рипса: симплекс входит, если все его вершины попарно ближе ε

Комплекс	Точность	Стоимость
Vietoris–Rips	приближённая	самая дешёвая, стандарт де-факто
Čech	точная (гомотопически)	очень дорогая
Alpha	точная в малых размерностях	нужна триангуляция Делоне
Witness	приближённая по опорным точкам	для больших выборок

Стоимость построения

Почему ограничиваются размерностями 0 и 1.

Число $k$ -симплексов в комплексе Рипса растёт как $(k + 1 n)$ в худшем случае. Для 1 000 точек одних только треугольников может быть до $1.6 \cdot 1 0^{8}$ — поэтому в реальных пайплайнах считают $H_{0}$ и $H_{1}$ , изредка $H_{2}$ .

Ограничение максимального ε резко сокращает комплекс.
Sparse Rips даёт приближение с контролируемой ошибкой и работает намного быстрее.
Ripser и GUDHI используют кограничную редукцию — на практике этого хватает для тысяч точек.

Связанные темы

Топология данных

Topology basics90%

Основы топологии · Топологический анализ данных

Топология изучает свойства, сохраняющиеся при непрерывных деформациях: связность, число дыр, компактность.

Homology90%

Гомологии · Топологический анализ данных

Алгебраический аппарат, который считает дыры разных размерностей в топологическом пространстве.

Persistent Homology90%

Персистентные гомологии · Топологический анализ данных

Центральный метод TDA: вместо одного порога ε рассматривается вся фильтрация, и отслеживается, когда топологические особенности рождаются и умирают.

Persistence Diagrams90%

Диаграммы персистентности · Топологический анализ данных

Каждая топологическая особенность — точка (рождение, смерть) на плоскости. Компактная сводка формы данных.

Persistence Landscapes90%

Ландшафты персистентности · Топологический анализ данных

Превращение диаграммы в набор кусочно-линейных функций — то есть в элемент гильбертова пространства.

Betti Numbers90%

Числа Бетти · Топологический анализ данных

Ранги групп гомологий: β₀ — число компонент, β₁ — число независимых циклов, β₂ — число полостей.

Mapper90%

Алгоритм Mapper · Топологический анализ данных

Строит граф-скелет данных: проекция фильтрующей функцией, покрытие интервалами, локальная кластеризация и склейка.

Topological features90%

Топологические признаки · Топологический анализ данных

Векторизация топологии: энтропия персистентности, суммарная длина жизни, числа Бетти, persistence images.

TDA + Machine Learning90%

TDA и машинное обучение · Топологический анализ данных

Топологические признаки подаются в бустинг или нейросеть, либо топология встраивается прямо в функцию потерь.

TDA + Time Series90%

TDA и временные ряды · Топологический анализ данных

Ряд вкладывается в фазовое пространство (Такенс), и топология полученного облака описывает динамику системы.

Metric spaces90%

Метрические пространства · Топологический анализ данных

Множество с функцией расстояния. Любой TDA-пайплайн начинается с выбора метрики.