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