Topologiczna analiza danych cz. 5


Kontynuuję to o czym pisałam o tutaj (klik) .

Zbiór elementów grupy Z_{1}  których obrazem w grupie Z_{0} przy przekształceniu {\partial_1} jest 0, określa się nazwą jądra ( kernel) operatora. Oczywiście suma czy różnica takich elementów także daje zero, co oznacza, jest to zresztą ogólna właściwość algebraiczna, że elementy jądra tworzą podgrupę. Zbiór ten w naszym przypadku złożony jest z jednego elementu, reprezentującego kompleks łańcuchowy odpowiadający brzegowi trójkąta. Symbolicznie zapisujemy to w następujący sposób:

to1

Zwróćmy uwagę, ze brzeg ów, jest z kolei obrazem całego trójkąta (A) przy odwzorowaniu {\partial_2}

to2

Mamy tu do czynienia z podgrupą, gdyż suma formalna brzegów figur, jest brzegiem figury będącej ich sumą. Operator brzegu przypisuje figurom płaskim ich brzegi, a brzegi takie są zawsze łańcuchami cyklicznymi, czyli zamkniętymi pętlami. Nic więc dziwnego, że elementy grupy Y_{1} leżą w grupie C_{1} ( bo każdy cykl w przekształceniu {\partial_1} jest mapowany na 0). W naszym wypadku grupy te są wręcz równe, wynika to jednak z faktu że rozważamy wyjątkowo prosty przykład. Gdyby zamiast trójkąta rozważać figurę która zawiera „dziurę” w swoim wnętrzu, istniałyby także cykle krawędzi, które nie są brzegami żadnej powierzchni ( nie mają żadnego „wypełnienia” ). W takim wypadku grupa Y_{1} byłaby podgrupą właściwą, zaś grupa C_{1} cykli krawędziowych zawiewałaby obok elementów będących brzegami rozmaitych pól płaskich na jakie dzielilibyśmy taką figurę, także elementy będące cyklami pomimo iż nie otaczają „niczego”. Pierwszą grupą homologii {H_1} nazywamy grupę ilorazową grup C_{1}/Y_{1}. Analogicznie n-tą grupą homologii jest grupa ilorazowa grup C_{n}/Y_{n}:

to3

.

Wyliczmy zatem grupy homologii dla naszych grup łańcuchowych Z_{k}. Dla k=2 jądro jest puste, gdyż żadna kombinacja 2-wymiarowych elementów ( a mamy tylko jeden: A ), nie sumuje sie do zamkniętej powłoki. Oczywiście nie ma także żadnych 3-wymiarowych obiektów… Zatem:

to4

widać zatem że wszystkie grupy homologii {H_n} dla {n \geq 2} są równe 0.

to5

Zwróćmy tu uwagę, że w powyższym równaniu 0 po prawej stronie oznacza trywialną grupę złożona z jednego elementu – identyczności w grupie abelowej – a więc 0.

Teraz wyliczmy grupę homologii dla n=0. Ponieważ arbitralnie przyjęliśmy, że {\partial_0 = 0} to jądrem tego odwzorowania jest cała grupa wierzchołków, a wiec jądro to trójelementowa grupa wolna o 3 generatorach <x,y,z> Przypomnijmy że powyżej wyliczyliśmy jakie są elementy produkowane z krawędzi przez odwzorowanie {\partial_1} . Obraz ten produkuje 3 elementy, które jednak, jak już wspominaliśmy nie są niezależne, bowiem wierzchołki owe spinają się w pętle brzegu trójkąta. Mieliśmy relację a+b-c=0 ( którą formalnie powinniśmy zapisać za pomocą symboli wierzchołków x,y,z, gdyż rozumiemy ja jako relację w zbiorze Z_{0} a nie  Z_{1}którego elementami są a,b,c). Tym samym w zbiorze <y-x,z-y,z-x> tylko dwa elementy są niezależne, a trzeci można wyeliminować. Zatem grupa brzegów {img( \partial_1)} jest grupą wolną o generatorach <y-x,z-y> zaś trzeci element z-x jest od nich zależny ( łatwo sprawdzić że jest ich sumą!). Mamy:

to5

Zauważmy że możliwe jest przejście od <x,y,z> do <x,y-x,z-y> bo polega ono na zamianie generatorów x,y,z przez ich liniowe i niezależne kombinacje co jest operacją dopuszczalną ( gdyż nie zmienia struktury grupy, stare generatory są liniowymi kombinacjami nowych i nie zmieniliśmy liczby generatorów niezależnych). Mamy zatem:

H_{0}=<x,y-x,z-y>/(y-x,z-y>==C

Wynik nie jest zaskakujący, zwłaszcza że grupa {H_0} ma geometryczną interpretację: mierzy ilość składowych spójnych figury, w naszym wypadku trójkąta, który oczywiście ma tylko jedną składową spójną. Pozostałe grupy homologii, w naszym wypadku trywialne, także dają się geometrycznie interpretować. Mierzą one mianowicie ilość dziur o stosownych wymiarach. I tak np. grupa {H_1} mierzy ilość „pustych oczek” czyli dziur w figurze otoczonych jednowymiarowymi łańcuchami cyklicznymi które nie są wypełnione ( nie są brzegiem żadnej figury płaskiej pełnej). Z kolei {H_2} mierzy ilość cykli 2-wymiarowych które otaczają 2 wymiarowe otwory ( coś jak wnętrze walca, rurki, lunety), które nie są brzegiem żadnej figury posiadającej objętość ( wyplenionej). Branie grupy ilorazowej we wzorze na grupę homologii właśnie taki ma cel – eliminuje z pełnej grupy cykli na n-tym poziomie te cykle, które są brzegami figur wymiaru n+1. Stąd homologia mierzy wzajemne położenia  składowych o rożnych wymiarach w figurze geometrycznej.

Zapisz

Topologiczna analiza danych cz. 4


W poprzednim poście o tutaj tym nawiązując do homologii wspomniałam o pewnym płaskim obiekcie A. Można w związku z nim sformułować grupę łańcuchową obiektu A (traktując już go jako kompleks). Ogólnie rzecz ujmując  n-tą grupą łańcuchową kompleksu A nazywamy grupę abelową obiektów o wymiarze n oznaczamy przez Z_{n}.

I tak grupa krawędzi, a więc 1-sza grupa łańcuchowa naszego trójkąta, jest generowana przez 3 elementy <a,b,c>. Nie jest to jednak grupa wolna ( a więc nie wszystkie elementy te są niezależne!). Z faktu istnienia relacji a+b-c=0 wynika że istnieje pomiędzy generatorami grupy związek, zaś sama grupa ma co najwyżej 2 niezależne elementy ( i tu już mamy pełną dowolność, mogą być to dowolne dwa boki trójkąta, np. a,b lub ich dowolna kombinacja liniowa). Jak widać niektóre związki pomiędzy elementami grupy łańcuchowej Z_{n} ( krawędzi) w naszym przypadku były interesujące, czyli grupy takie mają czasami wewnętrzną strukturę! Istnieją także związki pomiędzy grupami o różnych {n}!

Weźmy grupę jaka jest związana z wnętrzem ( powierzchnią) trójkąta. Mamy tylko jeden trójkąt, cała grupa Z_{2} jest zatem dosyć uboga, zawiera bowiem tylko jeden element .

Wszystko co możemy z takim elementem nawyczyniać, sprowadza się do dodawania ( bądź odejmowania) go pewną liczbę razy, np. elementami grupy są wyrażenia: A+A,27A,-6A Brak jest też jakichkolwiek związków ograniczających ten element, jest więc to grupa wolna abelowa o jednym elemencie, czyli grupa izomorficzna ze zbiorem liczb całkowitych . Jednak brzeg tej figury, czyli zbiór jej skierowanych krawędzi, jak widzieliśmy ma niebanalną strukturę! Zdefiniujmy operator, oznaczany symbolem , który działając na 2 wymiarowy trójkąt A przyporządkuje mu element grupy łańcuchowej wymiaru 1-mniejszej, a więc element z Z_{1}, który będzie reprezentował brzeg figury A. Oczywiście wyliczenie wygląda następująco:

to1

Całkiem podobnie możemy postąpić w wypadku krawędzi. Krawędzie są skierowane, zdefiniujmy więc podobne odwzorowanie do obiektów o wymiarze 1- mniej, w tym wypadku do grupy wierzchołków, które owo skierowanie będzie brało pod uwagę. Naturalne jest przyjęcie że operator {\partial_1} który każdej krawędzi przyporządkuje element grupy łańcuchowej wierzchołków będzie działał w sposób następujący:

to2

A co z brzegiem wierzchołka? Czy możliwe jest zdefiniowanie operacji {\partial_0} ? Ile wynosi na przykład sigma_{0}(x) ? Arbitralnie przyjmiemy że wynik to 0 w każdym wypadku. Mamy więc taka sytuację:

to3

Zera na początku i na końcu pokazanego ciągu grup i wzajemnych odwzorowań oznaczają że w trójkącie nie ma obiektów o wymiarze mniejszym niż 0 i większym niż 2. To jeszcze nie koniec na tym. Temat będę ciągnąć dalej, proszę o cierpliwość. Być może wyjdzie mi „Moda na sukces” a w ostatnim odcinku będzie mowa o muchach owocówkach…

Zapisz

Zapisz

Topologia w analizie danych cz. 3


blog1

Na rysunku powyżej, mamy obiekt płaski, trójkąt A. Jest to element powierzchni obdarzony orientacją zadaną przez kierunek obiegu jego krawędzi. Krawędzie te oznaczymy a,b,c. Krawędzie te łączą wierzchołki, na rysunku oznaczone x,y,z. Wypisane obiekty mają następujące wymiary: trójkąt jest obiektem 2 wymiarowym, krawędzie skierowane są 1-dno wymiarowe, zaś wierzchołki to obiekty 0-wymiarowe. Brak na rysunku obiektów o wymiarach większych niż 2 i mniejszych niż 0 oczywiście. Obiekty te nie są bynajmniej niezależne, ale połączone są w dosyć szczególny sposób. Na przykład każda krawędź ma dwa wierzchołki, zaś fakt iż złożenie krawędzie jest tak szczególne że tworzą pętlę – brzeg trójkąta – wynika że wierzchołek będący końcem jednej z krawędzi jest początkiem następnej i sytuacja ta powtarza się tworząc cykl wierzchołków, w którym każdy z nich pojawia się dwa razy – raz jako początek a raz jako koniec pewnej krawędzi. Przy budowie teorii homologii (a bada ona właśnie takie wzajemne relacje pomiędzy elementami składowymi obiektu geometrycznego ) jest zdefiniowanie dla każdego wymiaru części składowych, formalnego odwzorowania w grupę przemienną.  Spełniona jest tu własność a+b=c ponieważ położenie wzajemne krawędzi jest takie ze tworzą one pętlę. Ponieważ suma jest czysto formalna, nic nie zabrania nam rozważać obiektów bardziej wymyślnych, na przykład 4a-3b+6c. Konsekwentnie ma+mb-mc=m(a+b-c)=0 taka kombinacja oznacza m-krotne obejście pętli brzegu trójkąta. Całkiem identyczne obiekty, sumy formalne, możemy rozważać w wypadku wierzchołków czy wnętrza trójkąta i innych, więcej wymiarowych obiektów gdyby takowe występowały.W kolejnym wpisie o grupie łańcuchowej kompleksu. Ogólnie – teoria homologii jest twardym rdzeniem topologii algebraicznej a TDA, o której od kilku postów piszę opiera się na niej bardzo mocno. Sporo pracy przede mną…, sporo jeszcze do poznania i napisania. Dłuższe partie wolę opisać w „kawałkach” i bardziej się nad niektórymi szczególikami zastanowić. Ważne, że plan jest. Jak to wszystko składa się w jedną całość – cierpliwości…

 

Topologia w analizie danych cz. 2


W poprzedniej części tematu wspominałam o kształtach danych i ich reprezentacji. Przedstawiłam ogólny zarys TDA. Dziś krótka notatka o mierzeniu kształtów przy użyciu homologii w nieco poszerzonym znaczeniu. Homologia persystentna to algebraiczna metoda znajdowania topologicznych cech w danych (składowe, klastry, “dziury” etc.) i  została zapoczątkowana przez: Edelsbrunnera, Letschera, Zomorodiana, Carlsona. Rozszerzyli oni pojęcie homologii na chmurę punktów. Metoda ta posiada pewien schemat działania. Tak jak już wspomniałam rozkład punktów posiada pewien kształt. Pierwszym krokiem jest wybór liczby ε  a następnie należy połączyć punkty, które nie są dalej od siebie niż o ε. Tym sposobem powstaje graf tzw. kompleks symplicjalny. Jeśli ε jest za mały, to mamy wiele składowych. Jeśli ε jest za duży, to mamy tylko jedną składową. Pytanie tylko jaki promień wybrać, żeby usunąć szum? odpowiedź jest prostsza niż mogłoby się wydawać – rozważyć wszystkie promienie jednocześnie. Charakterystyczne jest to, że każda dziura pojawia się przy pewnym promieniu ε_{1} i znika przy innym ε_{2}. Persystencję powtałej dziury możemy określić przez czas jest życia, czyli przedział [ε_{1}, ], to pozwala na oddzielenie istotnych cech od szumu. Zauważmy, że gdybyśmy tak po prostu łączyli grupy, które są od siebie odległe o mnie niż , to otrzymamy dendrogram znany dobrze z analizy hierarchicznej. W miarę zgłębiania tematu TDA będę zamieszczała na blogu kolejne posty.

Topologia w analizie danych cz. 1


Chciałabym dziś opowiedzieć o czym co w ostatnich latach dość mocno rozwija się a w przyszłości będzie masowo uprawiane. Pominąwszy zbędne wstępy przejdę do rzeczy. Ktokolwiek słyszał o Topological Data Analysis kojarzy to pojęcie z „explozją danych” i pojęciem „big data” oraz z klasteryzacją, taksonomią, a przede wszystkim topologią (w dużej mierze algebraiczną). Spektrum pojęcia Topological Data Analysis  jest szersze – nie zawsze chodzi o problemy typu Big Data (z tym już mniej lub bardziej badacze umieją sobie radzić), ale bardziej ze zrozumieniem co tam jest. Dziś bardziej interesująca jest złożoność danych w sensie odkrycia struktury ukrytej w danych,a to wymaga bardziej metodycznego postępowania.Głównym punktem wyjścia jest fakt, iż dane mają pewien kształt, który ma znaczenie i zależy od wybranych cech/kolumn/urządzeń pomiarowych oraz metryki między kolumnami – jest to pierwszy krok w analizie.  Badacz często staje przed nie lada wyzwaniem ponieważ dane zwykle są wielowymiarowe i nie trafiają do naszej percepcji a złożone dane to wiele hipotez do sprawdzenia. Z pomocą przychodzi topologia, która umożliwia niezależność od współrzędnych (nie ważne, z której strony patrzymy, okrąg pozostanie okręgiem) oraz „compressed drepresentation” czyli możliwość zakodowania nieskończonych danych w niewielkiej liczbie zmiennych. Połączenie topologii i analizy danych jest możliwe, można założyć, że dana jest gładka rozmaitość a funkcje są gładkie lub ciągłe. Zaletą posiłkowania się topologią jest to, że przy odpowiednio bogatej rodzinie funkcji odtworzymy początkowy obiekt, a wyboru funkcji można dokonać tak, aby wygasić pewne (nieistotne) cechy.  Ogólnie zarys idei jest taki:

Zakłada się, że przestrzeń topologiczna X ma pokrycie

to1

czyli

to2

dla każdego elementu pokrycia U_{alfa}  przaz pi_{0}f^{-1}U_{alfa}  oznacza się składowe łukowej spójności

Następnie, tworzy się sumę rozłączną zbiorów pi_{0}f^{-1}U_{alfa}

a w rezultacie tworzy się graf łącząc te pary, dla których f^{-1}U_{alfa} nachodzą się.

Na tym jeszcze nie koniec. Zamienia się punkty na otwarte pokrycia zbioru wartości, następnie  zamienia się “składową spójności z przeciwobrazu” na “klastry w przeciwobrazie”. Dalej buduje się kompleks symplicjalny w ten są sposób z odpowiednim algorytmem klastrowania zamiast pi_{0}

Co otrzymujemy?

Otrzymamy węzły jako klastry danych oraz krawędzie reprezentujące współdzielone punkty między klastrami. Dzięki temu uzyskujemy struktury węzłów i krawędzi, które będą oddawać kształt (network modelling). Co więcej mamy lepsze zrozumienie kształtu danych bez wcześniejszego założenia o jakimkolwiek modelu.

Temat drążę dalej i w kolejnym odcinku opowiem o idei homologia persystentnej. Wiem też, że pakiet R jest wyposażony w narzędzie TDA, o którym także być może wspomnę.

Zapisz

Zapisz

Topologia z praktycznej strony cz. 1


Celem topologii jest tworzenie narzędzi pozwalających odróżniać i klasyfikować zbiory (przestrzenie topologiczne) metodami nieco bardziej wymagającymi niż samo zliczanie elementów (domena teorii mnogości), ale ciągle pozwalającymi na utożsamianie dość niepodobnych do siebie zbiorów. Takie spojrzenie jest szczególnie przydatne wtedy, gdy o zbiorze wiemy niewiele, w szczególności zbyt mało, by mierzenie było możliwe. To sprawia, że topologia ma ważne zastosowania poza matematyką. Realne zastosowanie znajduje na przykład problem liczenia ilości „dziur” w zbiorach kostkowych lub problem pokrycia w odniesieniu do sieci sensorowych. Sieci sensorowe wykorzystywane są do monitorowania wymagających kontroli obszarów. Może to chodzić o ochronę terenu przed niepowołanymi osobami, zapobieganie pożarom czy skażeniom. Sensory rozmieszczane są losowo na przykład poprzez rozrzucanie ich z samolotu. Problem pokrycia sprowadza się do odpowiedzi na pytanie: czy cały obszar jest w zasięgu sensorów? Problem może być rozwiązany metodami topologii algebraicznej. Sensory komunikują się ze sobą poprzez sieć radiową, co pozwala skonstruować graf sąsiadów. Pozwala to na zbudowanie wielościanu w taki sposób, że ewentualne luki pokrycia objawiają się jako dziury w wielościanie, których obecność może być wykryta metodami topologii algebraicznej. To czego dowiaduję się o zastosowaniach topologii pochodzi z anglojęzycznych źródeł. Niektóre zastosowania są całkowitą nowością, a śledzenie tego uznaję za niezmiernie ciekawe.  Poniższy link dotyczy topologii obliczeniowej i coraz bardziej rozpowszechniającej się metody „Persistent homology”.

Nie sposób też omówić w jednym poście całej masy zastosowań topologii. Mam w zanadrzu kilkanaście ciekawych zastosowań, o których wspomnę na blogu niebawem. Być może zamieszczę też własne pomysły.

Łańcuchy Markowa – prosty przykład


Analiza Markow uwzględnia sekwencję zdarzeń i analizuje tendencję wystąpienia zdarzenia biorąc pod uwagę zdarzenia wcześniejsze. Korzystając z tej analizy, można wygenerować nowy ciąg losowych, ale powiązanych ze sobą zdarzeń, które wyglądają podobnie do stanu źródłowego. Innymi słowy, chodzi o ciąg losowy, w którym prawdopodobieństwo każdego zdarzenia zależy jedynie od wyniku poprzedniego. Proces Markowa bazuje wyłącznie na rozkładzie prawdopodobieństw warunkowych. Może się jednak zdarzyć, że będziemy mieć do czynienia z deterministycznym procesem chaotycznym, w którym jutrzejsze zachowanie określone jest ścisłym wzorem, a mimo to proces będzie sprawiał wrażenie, że jest zerowego rzędu (to znaczy zupełnie nie zależy od przeszłości) – tu już sprawa się nieco komplikuje. W tym wpisie nie będę brnęła zbyt daleko w szczegóły pokażę jaka jest zasada działania łańcuchów Markowa na przykładzie symulacji w pakiecie R – przykład dotyczy pogody.

lancuch

Symulacja zawiera macierz przejścia z jednego stanu do drugiego, a stanami przejścia są trzy stany pogodowe: słonecznie, deszczowo, pochmurnie. Na diagramie pokazano w postaci grafu stany pogodowe i prawdopodobieństwa przejścia z jednego stanu do drugiego. Model jest uproszczony. Pakiet R dysponuje wbudowanym „narzędziem” które się wywołuje do takiej analizy – „markovchain”. Być może wkrótce ukażą się na blogu bardziej skomplikowane przypadku.