Топологічний аналіз даних: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Звірі (обговорення | внесок) |
Звірі (обговорення | внесок) |
||
| Рядок 21: | Рядок 21: | ||
Перші обчислюванні алгоритми, які обчислювали фільтрацію комплексів, їхні інваріанти, персистентні гомології через застосування гладки функції Морзе і reduction to the canonical form by upper-triangular matrices були запропоновані Баранніковим<ref name="Barannikov 1994">{{Cite journal|title = Framed Morse complex and its invariants |url = https://www.researchgate.net/publication/267672645 |journal = Advances in Soviet Mathematics | date = 1994|pages = 93–115|volume = 21|first = Sergey|last = Barannikov |series = ADVSOV |doi=10.1090/advsov/021/03|isbn = 9780821802373 |s2cid = 125829976 }}</ref>. |
Перші обчислюванні алгоритми, які обчислювали фільтрацію комплексів, їхні інваріанти, персистентні гомології через застосування гладки функції Морзе і reduction to the canonical form by upper-triangular matrices були запропоновані Баранніковим<ref name="Barannikov 1994">{{Cite journal|title = Framed Morse complex and its invariants |url = https://www.researchgate.net/publication/267672645 |journal = Advances in Soviet Mathematics | date = 1994|pages = 93–115|volume = 21|first = Sergey|last = Barannikov |series = ADVSOV |doi=10.1090/advsov/021/03|isbn = 9780821802373 |s2cid = 125829976 }}</ref>. |
||
Одне з питань, яке виникає під час обчислення, - це вибір [[Симпліційний комплекс|симплеційного комплексу]]. Найбільш природнім вибором на перший погляд є комплекс Чеха або комплекс Вієторіса-Ріпса, однак їхні розміри ростуть швидко із збільшенням кількості точок в хмарі точок даних. Комплексу Вієторіса–Ріпса надають перевагу над комплексом Чеха, тому що його визначення простіше, а комплекс Чеха потребує додаткових зусиль для визначення в загальному кінцевому метричному просторі. Вивчаються ефективні способи зниження обчислювальної вартості гомології. Для прикладу, |
Одне з питань, яке виникає під час обчислення, - це вибір [[Симпліційний комплекс|симплеційного комплексу]]. Найбільш природнім вибором на перший погляд є комплекс Чеха або комплекс Вієторіса-Ріпса, однак їхні розміри ростуть швидко із збільшенням кількості точок в хмарі точок даних. Комплексу Вієторіса–Ріпса надають перевагу над комплексом Чеха, тому що його визначення простіше, а комплекс Чеха потребує додаткових зусиль для визначення в загальному кінцевому метричному просторі. Вивчаються ефективні способи зниження обчислювальної вартості гомології. Для прикладу, α-комплекс і witness комплек використовуються для редукування розмірності і розміру комплексів.<ref>{{Cite book|title = Topological Estimation Using Witness Complexes|publisher = Eurographics Association|journal = Proceedings of the First Eurographics Conference on Point-Based Graphics|date = 2004-01-01|location = Aire-la-Ville, Switzerland, Switzerland|isbn = 978-3-905673-09-8|pages = 157–166|series = SPBG'04|doi = 10.2312/SPBG/SPBG04/157-166|first1 = Vin|last1 = De Silva|first2 = Gunnar|last2 = Carlsson}}</ref> |
||
У вільному доступі є ціла низка програмних пакетів, що дозволяють розв'язувати обчислювальні задачі топологічного аналізу, для прикладу: [http://appliedtopology.github.io/javaplex/ javaPlex], [http://www.mrzv.org/software/dionysus/ Dionysus], [http://www.sas.upenn.edu/~vnanda/perseus/index.html Perseus], [https://archive.today/20130629100858/http://phat.googlecode.com/ PHAT], [https://github.com/DIPHA/dipha/ DIPHA], [https://project.inria.fr/gudhi/software/ GUDHI], [https://github.com/Ripser/ripser Ripser], [https://CRAN.R-project.org/package=TDAstats TDAstats] та інші. Порівняння деяких з них було виконано у роботі Otter et al.<ref>{{cite journal|title = A roadmap for the computation of persistent homology|journal= EPJ Data Science|volume= 6|arxiv= 1506.08903|date = 2015-06-29|first1 = Nina|last1 = Otter|first2 = Mason A.|last2 = Porter|first3 = Ulrike|last3 = Tillmann|first4 = Peter|last4 = Grindrod|first5 = Heather A.|last5 = Harrington|issue= 1|pages= 17|author5-link=Heather Harrington|doi= 10.1140/epjds/s13688-017-0109-5|pmid= 32025466|pmc= 6979512|bibcode= 2015arXiv150608903O}}</ref> |
|||
== Примітки == |
== Примітки == |
||
Версія за 15:11, 17 січня 2023
У прикладній математиці топологічний аналіз даних (англ. 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