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.