Em matemática aplicada, a análise topológica de dados (TDA, na abreviatura do nome em inglês, ) é uma abordagem para a análise de conjuntos de dados por meio de técnicas da topologia. A extração de informações de conjuntos de dados de dimensão alta, incompletos e com ruídos é um desafio. A TDA fornece uma estrutura geral para analisar esses dados de maneira insensível à métrica específica escolhida e fornece redução de dimensionalidade e robustez ao ruído. Além disso, ela herda funtorialidade, um conceito fundamental da matemática moderna, de sua natureza topológica, o que lhe permite adaptar-se às novas ferramentas matemáticas.
A motivação inicial é estudar a forma dos dados. A TDA combinou a topologia algébrica e outras ferramentas da matemática pura para permitir o estudo matematicamente rigoroso da "forma". A ferramenta principal é a homologia persistente, uma adaptação da homologia para dados de nuvem de pontos. A homologia persistente foi aplicada a muitos tipos de dados em muitas áreas. Além disso, sua base matemática também é de importância teórica. As características exclusivas da TDA fazem dela uma ponte promissora entre topologia e geometria.
Teoria básica
Intuição A premissa subjacente à TDA é que a forma é importante. Dados reais em altas dimensões quase sempre são esparsos e tendem a ter características de baixa dimensão relevantes. Uma tarefa de TDA é fornecer uma caracterização precisa desse fato. Um exemplo ilustrativo é um sistema predador-presa simples, governado pelas equações de Lotka-Volterra. Pode-se observar facilmente que a trajetória do sistema forma um círculo fechado no espaço de estados. A TDA fornece ferramentas para detectar e quantificar esse movimento recorrente.
Muitos algoritmos para a análise de dados, incluindo aqueles usados na TDA, exigem a escolha de vários parâmetros. Sem conhecimento prévio do domínio, é difícil escolher a coleção correta de parâmetros para um conjunto de dados. A principal percepção da homologia persistente é que podemos usar as informações obtidas de todos os valores de um parâmetro. É claro que apenas essa percepção é fácil de fazer; a parte difícil é codificar essa enorme quantidade de informações em um formato compreensível e fácil de representar. Com a TDA, há uma interpretação matemática quando a informação é um grupo de homologia. Em geral, a suposição é que as características que persistem para uma ampla variedade de parâmetros são "verdadeiras" características. Presume-se que as características que persistem apenas para uma faixa estreita de parâmetros sejam ruídos, embora a justificativa teórica para isso não seja clara.
História antiga Os precursores do conceito completo de homologia persistente apareceram gradualmente ao longo do tempo.Edelsbrunner H. Persistent homology: theory and practice[J]. 2014. Em 1990, Patrizio Frosini introduziu a função tamanho, que é equivalente à 0ª homologia persistente. Quase uma década depois, Vanessa Robins estudou as imagens de homomorfismos induzidos pela inclusão.Robins V. Towards computing homology from finite approximations[C]//Topology proceedings. 1999, 24(1): 503-532. Finalmente, logo em seguida, Edelsbrunner et al. introduziram o conceito de homologia persistente juntamente com um algoritmo eficiente e sua visualização como um diagrama de persistência. Carlsson et al. reformularam a definição inicial e deu um método de visualização equivalente chamado códigos de barras de persistência, interpretando a persistência na linguagem da álgebra comutativa.
Em topologia algébrica, a homologia persistente surgiu através do trabalho de Barannikov na teoria de Morse. O conjunto de valores críticos de função Morse suave foi particionado canonicamente em pares "nascimento-morte", complexos filtrados foram classificados e a visualização de seus invariantes, equivalente ao diagrama de persistência e códigos de barras de persistência, foi dada em 1994 pela forma canônica de Barannikov.
Conceitos Alguns conceitos amplamente usados são apresentados a seguir. Observe que algumas definições podem variar de autor para autor.
Uma nuvem de pontos é frequentemente definida como um conjunto finito de pontos em algum espaço euclidiano, mas pode ser considerada qualquer espaço métrico finito.
O complexo de Čech de uma nuvem de pontos é o nervo da cobertura de bolas com um raio fixo em torno de cada ponto da nuvem.
Um módulo de persistência indexado por consiste de um espaço vetorial , para cada , e uma transformação linear sempre que , de tal modo que para todo e sempre que Uma definição equivalente é um funtor de considerado como um conjunto parcialmente ordenado para a categoria dos espaços vetoriais.
O grupo de homologia persistente de uma nuvem de pontos é o módulo de persistência definido como , em que é o complexo de Čech de raio da nuvem de pontos e é o grupo de homologia.
Um código de barras de persistência é um multiconjunto de intervalos em e um diagrama de persistência é um multiconjunto de pontos em ( )
A distância de Wasserstein entre dois diagramas de persistência e é definida como em que e varia sobre as bijeções entre e . Para uma ilustração, pode consultar a figura 3.1 em Munch.Munch E. Applications of persistent homology to time varying systems[D]. Duke University, 2013. A distância de gargalo entre e é Este é um caso especial da distância de Wasserstein, obtido ao considerar .
Propriedade básica
Teorema da estrutura O primeiro teorema de classificação para a homologia persistente apareceu em 1994 através das formas canônicas de Barannikov. O teorema da classificação que interpreta a persistência na linguagem da álgebra comutativa apareceu em 2005: para um módulo de persistência finitamente gerado com coeficientes em um corpo , Intuitivamente, as partes livres correspondem aos geradores da homologia que aparecem no nível da filtração e nunca desaparecem, enquanto as partes de torção correspondem às que aparecem no nível da filtração e duram por etapas da filtração (ou equivalentemente, desaparecem no nível da filtração).
A homologia persistente é visualizada através de um código de barras ou diagrama de persistência. O código de barras originou-se na matemática abstrata. Especificamente, a categoria dos complexos filtrados finitos sobre um corpo é semissimples. Qualquer complexo filtrado é isomorfo à sua forma canônica, uma soma direta de complexos filtrados simples uni e bidimensionais.
Estabilidade A estabilidade é desejável por fornecer robustez contra ruídos. Se é qualquer espaço homeomorfo a um complexo simplicial, e são funções tame contínuas, então os espaços vetoriais de persistência e são apresentados finitamente e , onde refere-se à distância de gargalo e é a aplicação que leva uma função tame contínua no diagrama de persistência de sua -ésima homologia.
Fluxo de trabalho O fluxo de trabalho básico na TDA é: Nuvem de pontos complexos aninhados módulo de persistência código de barras ou diagrama
Se é uma nuvem de pontos, substitua por uma família aninhada de complexos simpliciais (como o complexo de Čech ou Vietoris-Rips). Esse processo converte a nuvem de pontos para uma filtragem de complexos simpliciais. Tomando-se a homologia de cada complexo nessa filtração obtém-se um módulo de persistência Aplique o teorema da estrutura para fornecer uma versão parametrizada do número de Betti, diagrama de persistência ou, equivalentemente, código de barras.
Graficamente, centro|miniaturadaimagem|488x488px| Um uso comum de persistência na TDA
Cálculo O primeiro algoritmo sobre todos os corpos para homologia persistente no contexto da topologia algébrica foi descrito por Barannikov através da redução à forma canônica por matrizes triangulares superiores. O primeiro algoritmo para homologia persistente sobre foi dado por Edelsbrunner et al. Zomorodian e Carlsson deram o primeiro algoritmo prático para calcular a homologia persistente em todos os corpos. O livro de Edelsbrunner e Harer fornece orientação geral sobre topologia computacional.
Uma questão que surge na computação é a escolha do complexo. O complexo de Čech e o complexo de Vietoris – Rips são mais naturais à primeira vista; no entanto, seu tamanho aumenta rapidamente com o número de pontos de dados. O complexo de Vietoris – Rips é preferível ao complexo de Čech porque sua definição é mais simples e o complexo de Čech requer um esforço extra para definir em um espaço métrico finito geral. Foram estudadas formas eficientes de reduzir o custo computacional da homologia. Por exemplo, o complexo α e o complexo testemunha são usados para reduzir a dimensão e o tamanho dos complexos.
Recentemente, a teoria de Morse discreta mostrou-se promissora para a homologia computacional, pois pode reduzir um complexo simplicial dado a um complexo celular muito menor que é homotópico ao original. Essa redução pode de fato ser realizada à medida em que o complexo é construído usando a teoria matroide, levando a maiores aumentos de desempenho. Outro algoritmo recente economiza tempo ignorando as classes de homologia com baixa persistência.
Há vários pacotes de software disponíveis, como por exemplo javaPlex, Dionysus, Perseus, PHAT, DIPHA, Gudhi, Ripser e TDAstats. Uma comparação entre essas ferramentas é feita por Otter et al. Giotto-tda é um pacote Python dedicado à integração de TDA no fluxo de trabalho de aprendizagem de máquina por meio de uma API scikit-learn. Um pacote R chamado TDA é capaz de calcular conceitos inventados recentemente, como paisagem e o estimador de distância do núcleo. O pacote Topology ToolKit é especializado em dados contínuos, definidos em variedades de baixa dimensão (1, 2 ou 3), como os que normalmente são encontrados em visualização científica. Outro pacote R, o TDAstats, implementa a biblioteca rápida C++ Ripser para calcular a homologia persistente. Ele também usa o onipresente pacote ggplot2 para gerar visualizações de homologia persistente reproduzíveis, personalizáveis e com qualidade de publicação, especificamente códigos de barras topológicos e diagramas de persistência. O código de exemplo abaixo mostra como a linguagem de programação R pode ser usada para calcular a homologia persistente.
# instalar pacote a partir do CRAN e carregar conjuntos de dados install.packages("TDAstats") library("TDAstats") data("unif2d") data("circle2d")
# calcular a homologia persistente para ambos os conjuntos de dados unif.phom <- calculate_homology(unif2d) circ.phom <- calculate_homology(circle2d)
# plotar nuvem de pontos distribuídos uniformemente como um diagrama de persistência plot_persist(unif.phom)
# plotar nuvem circular de pontos como um código de barras # nota-se uma única barra persistente, como seria de se esperar para uma circunferência (único 1-ciclo/laço) plot_barcode(circ.phom)
miniaturadaimagem| Diagrama de persistência criado pelo código de exemplo (conjunto de dados unif.2d) para um conjunto de 100 pontos distribuídos uniformemente dentro de um quadrado bidimensional unitário. Nenhum dos 0-ciclos ou 1-ciclos é considerado um sinal verdadeiro (nenhum existe realmente dentro de uma nuvem de pontos quadrada unitária). Embora algumas características pareçam persistir, as marcas nos eixos mostram que a característica mais persistente persiste por menos de 0,20 unidades, o que é relativamente pequeno para uma nuvem de pontos em um quadrado unitário. miniaturadaimagem| Código de barras topológico criado pelo código de exemplo (conjunto de dados circ.2d) para um conjunto de 100 pontos distribuídos uniformemente em torno da circunferência de um círculo. A única e longa característica unidimensional na parte superior do código de barras representa o único 1-ciclo presente em um círculo.
Visualização