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

Топологический анализ данных — новая область теоретических исследований для задач анализа данных (Data mining) и компьютерного зрения.

Основные вопросы:

1. Как из низкоразмерных представлений получать структуры высоких размерностей;
2. Как дискретные единицы складываются в глобальные структуры.

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

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

1. Замена набора элементов данных некоторым семейством симплициальных комплексов в соответствии с параметром близости.
2. Анализ этих топологических комплексов с помощью алгебраической топологии, а конкретно новой теорией персистентных гомологий.
3. Перекодировка устойчивой гомологии набора данных в параметризованную версию чисел Бетти, называемую баркодом.

Облако точек

Основная статья: Облако точек

Данные часто представлены множеством точек в Евклидовом пространстве E_n, форма которого отражает описываемый данными феномен.

Реальные трёхмерные объекты могут представляться в виде облака точек. Например, лазером отмечаются отдельные точки, и их неструктурированный набор служит представлением объекта в компьютере. Облаком точек считается любой (возможно, зашумленный) набор точек в E_n или проекций точек в более низкой размерности.

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

Для преобразования облака точек в метрическом пространстве в целостный объект точки используются в качестве вершин графа, рёбрам которого приписаны расстояния, затем граф превращается в симплициальный комплекс и изучается средствами алгебраической топологии.

См. также

• Снижение размерности
• Интеллектуальный анализ данных
• Компьютерное зрение
• Вычислительная топология
• Цифровая топология
• Дискретная теория Морса
• Анализ формы
• Анализ структурированных данных (статистика)

Ссылки

• Topological Methods in Scientific Computing, Statistics and Computer Science Stanford group
• BARCODES: THE PERSISTENT TOPOLOGY OF DATA
• Topological Data Analysis: the algebraic topology of point data clouds?  (недоступная ссылка с 13-05-2013 [3987 дней] — история)
• Sanjay Rana. Topological Data Structures for Surfaces (неопр.). — John Wiley and Sons, 2004.
• TOPOLOGY AND DATA, GUNNAR CARLSSON, BULLETIN (New Series) OF THE AMERICAN MATHEMATICAL SOCIETY, Volume 46, Number 2, April 2009, Pages 255–308, Article electronically published on January 29, 2009
• Edelsbrunner; Letscher; Zomorodian. Topological Persistence and Simplification (англ.) // Discrete & Computational Geometry : journal. — 2002. — Vol. 28, no. 4. — P. 511—533. — ISSN 0179-5376.
• Barannikov, S. Framed Morse complex and its invariants (неопр.) // Advances in Soviet Mathematics. — 1994. — Т. 21. — С. 93—115.