Численные методы в топологическом анализе данных (TDA): устойчивые гомологии

Геометрия скрытых структур в больших данных

В эпоху Big Data исследователи часто работают с наборами данных (Point Clouds), которые представляют собой миллионы точек в пространствах очень высокой размерности (сотни и тысячи координат). Это могут быть профили экспрессии генов, данные функциональной МРТ мозга или финансовые транзакции. Традиционные методы машинного обучения (кластеризация, PCA) опираются на метрику — точные расстояния между точками. Но в многомерных пространствах метрика теряет свою силу, шумы искажают расстояния, и методы дают сбои. Нужен был инструмент, устойчивый к растяжениям, сжатиям и непрерывным деформациям данных.

Этим инструментом стала алгебраическая топология, адаптированная для компьютеров под названием Топологический Анализ Данных (TDA). Топология изучает форму объектов (связность, наличие дыр, туннелей и пустот). Например, топологически кофейная кружка и бублик — это один и тот же объект, так как у обоих есть ровно одна дырка. Главный численный алгоритм TDA называется Устойчивыми гомологиями (Persistent Homology). Он позволяет компьютеру находить глобальные топологические структуры в хаосе дискретных многомерных точек.

Симплициальные комплексы и фильтрация Виеториса-Рипса

Как из разрозненных точек собрать сплошной топологический объект? Программа создает математические связи (симплексы). Точка — это симплекс 0-мерный. Отрезок между двумя точками — 1-мерный. Треугольник (с заливкой) — 2-мерный, тетраэдр — 3-мерный. Алгоритм начинает «раздувать» вокруг каждой точки данных гиперсферу радиуса R.

Если две сферы пересекаются, компьютер проводит между точками отрезок. Если три сферы попарно пересекаются, алгоритм закрашивает их треугольником. Эта структура называется комплексом Виеториса-Рипса. Фишка метода в том, что радиус R медленно увеличивается от нуля до бесконечности (процесс фильтрации). При малом R у нас просто набор точек. При увеличении R точки сливаются в кластеры, образуются циклы (дырки), а при очень большом R все сливается в один гигантский монолит без дыр. Алгоритм отслеживает «рождение» (появление дыры) и «смерть» (закрашивание дыры треугольниками) каждого топологического свойства.

Вычисление штрих-кодов и матричная редукция

С вычислительной точки зрения процесс отслеживания гомологий сводится к тяжелой линейной алгебре. Для каждого шага фильтрации компьютер строит матрицу границ (Boundary matrix), которая описывает, какие вершины образуют какие грани. Элементы этой матрицы лежат в поле вычетов по модулю 2 (цифры только 0 и 1).

Затем к этой гигантской разреженной матрице применяется специальный алгоритм редукции столбцов (аналог метода Гаусса), который приводит матрицу к нормальной форме. Из этой формы программа извлекает так называемые «числа Бетти» (инварианты) и строит финальный результат TDA — штрих-код (Barcode) или диаграмму устойчивости. Если какая-то дыра «живет» долго (длинный штрих-код), значит, это реальная топологическая макроструктура данных (например, циклическая структура в химической молекуле или вирусной РНК). Если дыра появляется и сразу исчезает — это просто шум. TDA произвел фурор в поиске новых материалов и анализе сложнейших нейросетей, давая инженерам возможность буквально «увидеть» форму многомерного массива данных.