Топологічний аналіз даних
У прикладній математиці топологічний аналіз даних (англ. Topological data analysis, TDA) — це підхід до аналізу даних із застосуванням методів топології. Видобуток інформації з наборів даних, які є багатовимірними, неповними та шумними, зазвичай є складним завданням. Топологічний аналіз даних (ТАД) забезпечує загальну структуру для аналізу таких даних у спосіб, який не чутливий до конкретного вибраного показника та забезпечує зменшення розмірності та стійкість до шуму. Крім того, він успадковує функторіальність, фундаментальну концепцію сучасної математики, завдяки своїй топологічній природі, що дозволяє адаптуватися до нових математичних інструментів.
Початковою мотивацією є вивчення форми даних. ТАД поєднав алгебраїчну топологію та інші інструменти з чистої математики, щоб дозволити математично точне вивчення "форми". Основним інструментом є персистентна гомологія, адаптація гомології до даних у вигляді хмари точок. Персистентна гомологія застосовувалася до багатьох типів даних у багатьох областях. Крім того, її математична основа також має теоретичне значення.
Базова теорія[ред. | ред. код]
Інтуітивний підхід[ред. | ред. код]
Будь-який набір даних можна трактувати як хмару точок в просторі параметрів, де кожен запис (строка) даних буде однією точкою. ТАД базується на ідеї, що форма наборів даних містить важливу інформацію. Реальні багатовимірні дані зазвичай розріджені та мають тенденцію мати релевантні маловимірні характеристики. Одним із завдань ТАД є надання точної характеристики цього факту. Наприклад, траєкторія простої системи хижак-жертва, керована рівняннями Лотки–Вольтерра, утворює замкнуте коло в просторі станів[1]. ТАД надає інструменти для виявлення та кількісної оцінки такого періодичного руху[2].
Рання історія[ред. | ред. код]
Прекурсори до повноцінної концепції топологічного аналізу даних з'являлись поступово. В 1990 році Patrizio Frosini ввів поняття функції розміру, що була еквівалентна до 0-вимірної персистентної гомології[3].
Концепції[ред. | ред. код]
Нижче подано перелік концепцій, що є базовими для топологічного аналізу даних
- Хмара точок
- Комплекс Чеха та Комплекс Вієторіса-Ріпса
- Персистентна гомологія
- Група персистентної гомології для даної хмари точок, що означається як , where is the Čech complex of radius of the point cloud and is the homology group.
- Діаграма персистентності
- Відстань Вассерштайна між діаграмами персистентності, та її варіації, наприклад, горловинна відстань (англ. bottleneck distance)
Обчислення[ред. | ред. код]
Перші обчислюванні алгоритми, які обчислювали фільтрацію комплексів, їхні інваріанти, персистентні гомології через застосування гладки функції Морзе і reduction to the canonical form by upper-triangular matrices були запропоновані Баранніковим[4].
Одне з питань, яке виникає під час обчислення, - це вибір симплеційного комплексу. Найбільш природнім вибором на перший погляд є комплекс Чеха або комплекс Вієторіса-Ріпса, однак їхні розміри ростуть швидко із збільшенням кількості точок в хмарі точок даних. Комплексу Вієторіса–Ріпса надають перевагу над комплексом Чеха, тому що його визначення простіше, а комплекс Чеха потребує додаткових зусиль для визначення в загальному кінцевому метричному просторі. Вивчаються ефективні способи зниження обчислювальної вартості гомології. Для прикладу, α-комплекс і witness комплек використовуються для редукування розмірності і розміру комплексів.[5]
У вільному доступі є ціла низка програмних пакетів, що дозволяють розв'язувати обчислювальні задачі топологічного аналізу, для прикладу: javaPlex, Dionysus, Perseus, PHAT, DIPHA, GUDHI, Ripser, TDAstats та інші. Порівняння деяких з них було виконано у роботі Otter et al.[6]
Примітки[ред. | ред. код]
- ↑ Epstein, Charles; Carlsson, Gunnar; Edelsbrunner, Herbert (1 грудня 2011). Topological data analysis. Inverse Problems. 27 (12): 120201. arXiv:1609.08227. Bibcode:2011InvPr..27a0101E. doi:10.1088/0266-5611/27/12/120201. S2CID 250913810.
- ↑ diva-portal.org/smash/record.jsf?pid=diva2%253A575329&dswid=4297. www.diva-portal.org. Архів оригіналу за 19 листопада 2015. Процитовано 5 листопада 2015.
- ↑ Frosini, Patrizio (1 грудня 1990). A distance for similarity classes of submanifolds of a Euclidean space. Bulletin of the Australian Mathematical Society. 42 (3): 407—415. doi:10.1017/S0004972700028574. ISSN 1755-1633.
- ↑ Barannikov, Sergey (1994). Framed Morse complex and its invariants. Advances in Soviet Mathematics. ADVSOV. 21: 93—115. doi:10.1090/advsov/021/03. ISBN 9780821802373. S2CID 125829976.
- ↑ De Silva, Vin; Carlsson, Gunnar (1 січня 2004). Topological Estimation Using Witness Complexes. SPBG'04. Aire-la-Ville, Switzerland, Switzerland: Eurographics Association. с. 157—166. doi:10.2312/SPBG/SPBG04/157-166. ISBN 978-3-905673-09-8.
{{cite book}}: Проігноровано|journal=(довідка) - ↑ Otter, Nina; Porter, Mason A.; Tillmann, Ulrike; Grindrod, Peter; Harrington, Heather A. (29 червня 2015). A roadmap for the computation of persistent homology. EPJ Data Science. 6 (1): 17. arXiv:1506.08903. Bibcode:2015arXiv150608903O. doi:10.1140/epjds/s13688-017-0109-5. PMC 6979512. PMID 32025466.
Джерела[ред. | ред. код]
- Lesnick, Michael (2013). Studying the Shape of Data Using Topology. Institute for Advanced Study.
- Oudot, Steve Y. (2015). Persistence Theory: From Quiver Representations to Data Analysis. American Mathematical Society. ISBN 978-1-4704-2545-6.
Посилання[ред. | ред. код]
- Зарічний, М. М. Обчислювальна геометрія і топологія. www.mmf.lnu.edu.ua (uk-ua) . Процитовано 13 листопада 2022.
- Applied Topology, by Stanford