Analiza dyskryminacyjna

Temat pracy dotyczy problemu dyskryminacji oraz budowy drzew klasyfikacyjnych w kontekście ich przydatności do rozwiązywania zadań o dużym wymiarze prób losowych i/lub dużym wymiarze wektora obserwacji, w których podstawowego znaczenia nabiera złożoność obliczeniowa drzewa. Radzenie sobie z dużymi zbiorami danych wymaga konstrukcji specjalnych technik sortowania danych w trakcie budowy drzewa, kodowania, organizacji wzrostu i przycinania drzewa. Wymaga także zrównoleglenia obliczeń. Przedmiotem pracy jest sformułowanie modelu analizy dyskryminacyjnej oraz analiza możliwych rozwiązań podanych zagadnień, wraz z implementacją jednego z nich.

W pierwszym rozdziale omawiam problem dyskryminacji pod nadzorem, nazywanej analizą dyskryminacyjną, wprowadzając formalny model klasyfikacyjny osadzony w przestrzeni probabilistycznej.

Rozdział drugi poświęcony jest budowie drzew klasyfikacyjnych, gdzie ze szczególną uwagą potraktowano problem złożoności i skalowalności. Rozdział wprowadza formalną definicję drzewa klasyfikacyjnego w oparciu o podstawy teorii grafów oraz o model klasyfikacyjny przedstawiony w rozdziale pierwszym. Dodatkowo omawiam nowatorską technikę przycinania drzew wykorzystującą zasadę minimalnej długości kodu, MDL – Minimum Description Length (M. Mehta, J. Rissanen, R. Agrawal, 1995).

W rozdziale trzecim i czwartym skupiam się na przedstawieniu indukcji drzew decyzyjnych metodą Supervised Learning in Quest – SLIQ (M. Mehta, R. Agrawal, J. Rissanen, 1996) oraz Scalable Parallelizable Induction of Decision Trees – SPRINT (J.C. Shafer, R. Agrawal, M. Mehta, 1996).

Rozdział piąty prezentuje implementację klasyfikatora SLIQ wraz z implementacją przycinania drzew metodą MDL. Implementację przeprowadziłem we współpracy z Instytutem Podstaw Informatyki Polskiej Akademii Nauk w ramach rozwoju pakietu „dmLab”. Tekst rozdziału zawiera również analizę złożoności czasowej i skalowalności implementacji.

Pracę kończą dodatki A i B, w których zebrałem podstawowe pojęcia wykorzystane w tekście z topologii, teorii miary, probabilistyki oraz teorii grafów.

Praca została przygotowana pod opieką Pana Profesora Jacka Koronackiego. Serdecznie zapraszam do lektury 🙂

Drzewa klasyfikacyjne – ich budowa, problemy złożoności i skalowalności.

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Johnny Bravo - Na pewno

Interpretacja słów niemożliwe i pewne nie sprawia na ogół żadnego kłopotu. Mówiąc, że coś jest niemożliwe, bądź pewne, mocno i zdecydowanym tonem akcentujemy fakt rozumiany jako coś niepodważalnego.

Johnny Bravo - Niemozliwe

W życiu codziennym rzadko dysponujemy takimi faktami, częściej posiadamy dobrze umotywowane przypuszczenia, że coś jest prawie niemożliwe lub prawie pewne. Rozumienie wyrażeń prawie niemożliwe i prawie pewne jest intuicyjnie łatwe, o ile potrafimy określić granicę kiedy prawie niemożliwe zaczyna być możliwe, a możliwe przechodzi w prawie pewne. Powyższe gierki słowne można nawet uporządkować rosnąco:

niemożliwe < prawie niemożliwe < możliwe < prawie pewne < pewne

Idąc dalej powiemy, że to co jest prawie pewne lub pewne jest też zarazem możliwe. Nawet to co prawie niemożliwe pozostawia cień szansy na możliwość. Tej ciekawej własności nie posiada natomiast wyrażenie niemożliwe. Ufff…

Johnny Bravo - Prawie niemozliwe

Ale jak to się ma do teorii prawdopodobieństwa? Największe bogactwo probabilistyki to umiejętność wartościowania w sposób liczbowy wszelkich możliwych przypuszczeń, fachowo nazywanych zdarzeniami losowymi. Probabilistyka potrafi wartościować również zdarzenia rozumiane jako fakty, określane mianem zdarzenia losowego niemożliwego oraz zdarzenia losowego pewnego.

Przykładem prawie niemożliwego zdarzenia losowego może być wylosowanie danej liczby spośród zbioru liczb naturalnych. Niech

$$A_n=\{1,2,\ldots,n\}$$

oznacza zbiór liczb naturalnych nie większych niż $n$. Jeśli $k\in A_n$ to prawdopodobieństwo wylosowania liczby $k$ ze zbioru $A_n$ wynosi

$$P_n(k)=\frac{1}{n}$$

W przypadku granicznym $n\to\infty$ najbardziej naturalnym będzie przyjąć, że prawdopodobieństwo takiego zdarzenia wynosi 0 (w uproszczeniu 1/∞). Czyżby istniały zdarzenia z prawdopodobieństwem 0, które mogą jednak zachodzić?

Johnny Bravo - Prawie na pewno

Analogicznie dochodzimy do wniosku, że zdarzeniem prawie pewnym będzie każde zdarzenie losowe zachodzące z prawdopodobieństwem 1, jednak różne od całego zbioru zdarzeń elementarnych. Wartość

$$1-P_n(k)=1-\frac{1}{n}=\frac{n-1}{n}$$

reprezentuje prawdopodobieństwo zdarzenia wylosowania liczby naturalnej ze zbioru $A_n$ różnej od wybranej liczby $k\in A_n$. Gdy $n\to\infty$ oczywiście $\frac{n-1}{n}\to 1$.

Warto zauważyć, że może istnieć wiele różnych zdarzeń prawie pewnych bądź zdarzeń prawie niemożliwych. Natomiast zdarzenia pewne i niemożliwe są jednoznacznie określone.

  • Zdarzenie niemożliwe – jest to pusty podzbiór przestrzeni zdarzeń elementarnych.
  • Zdarzenie pewne – jest to pełny zbiór zdarzeń elementarnych.

Podsumowanie

  • Zdarzenie niemożliwe – pusty podzbiór przestrzeni zdarzeń elementarnych, zdarzenie o prawdopodobieństwie 0.
  • Zdarzenie prawie niemożliwe – niepusty podzbiór przestrzeni zdarzeń elementarnych, o prawdopodobieństwie 0. Zainteresowanym polecam zapoznanie się z pojęciem zbioru miary 0.
  • Zdarzenie prawie pewne – podzbiór właściwy przestrzeni zdarzeń elementarnych, o prawdopodobieństwie 1.
  • Zdarzenie pewne – podzbiór pełny przestrzeni zdarzeń elementarnych, zdarzenie o prawdopodobieństwie 1.

Pozdrowienia,

Mariusz Gromada