Analiza dyskryminacyjna, Drzewa klasyfikacyjne, Klasyfikatory SLIQ i SPRINT

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

"Prawie na pewno" vs "Na pewno" - czyli jedna z subtelności probabilistyki

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