1 Z ŁOŻONE SYSTEMY KLASYFIKUJĄCE DLA DANYCH Z NIEZRÓWNOWAŻONYMI LICZEBNIE KLASAMI DECYZYJNYMI Autor: inż. Tomasz Maciejewski Promotor: dr hab. inż. Jerzy Stefanowski

2 P ROBLEM UCZENIA MASZYNOWEGO Dane wyjściowe: Zestaw przykładów opisanych za pomocą zbioru atrybutów oraz przynależności do jednej z możliwych klas decyzyjnych Cel: Stworzenie klasyfikatora przypisującego dowolny przykład do odpowiedniej klasy decyzyjnej Maksymalizacja skuteczności klasyfikatora Weryfikacja: Podział na zbiór treningowy oraz testowy Cross walidacja

3 C ZYM JEST „ SKUTECZNOŚĆ ”? Skuteczność klasyfikatora jest pojęciem względnym Zależy od jego przyszłego zastosowania Najczęściej wyrażana w postaci wielkości liczbowej opisującej pewną własność klasyfikatora Mierzona na zbiorze testowym Reprezentowana za pomocą odpowiedniej miary, najpopularniejsze z nich, to: Jakość klasyfikacji Błąd klasyfikatora

4 W CZYM PROBLEM ? Większość standardowych algorytmów oraz miar została opracowana zakładając niejawnie równomierny rozkład przykładów pomiędzy klasami Co jeśli założenie nie zostało spełnione? Klasyfikator preferuje przydział do klasy „większościowej” W przypadku dużej różnicy w liczności klas, rozpoznawanie klasy „mniejszościowej” staje się nieopłacalne Uzyskany klasyfikator nie dostarcza żadnej wiedzy, a jego przydatność jest niewielka

5 W CZYM PROBLEM ? - P RZYKŁAD Klasy decyzyjne = {Zdrowy, Chory} Obserwacje – 10 000: 9990 x Zdrowy 10 x Chory Trafność klasyfikatora „Zdrowy”: 99,9% Trafność klasyfikatora: 99,9% 9980 x Zdrowy 20 x Chory Czy klasyfikatory można uznać za „równo skuteczne”?

6 P ROBLEM W PROBLEMIE Skuteczność klasyfikatora należy rozpatrywać w kontekście problemu, który ma rozwiązać Niezrównoważenie liczebne klas stanowi problem jeśli: Przywiązuje się różną wagę do klasyfikacji przykładów z różnych klas Skupia się na rozpoznaniu obserwacji wyjątkowych

7 I STOTA PROBLEMU W przypadku wystąpienia nierównowagi klas, niedoreprezentowane są zazwyczaj klasy reprezentującej obiekty wyjątkowe, na których rozpoznaniu najbardziej zależy Standardowe miary nie uwzględniają dysproporcji pomiędzy klasami, co powoduje zwiększenie wagi klasy większościowej w ocenie skuteczności

8 I LE MIERZYSZ ? W przypadku nierównowagi klas należy wykorzystać miary lepiej dopasowane do tego typu problemów Sensitivity Specificity Precision F-miara Krzywa ROC, AUC

9 S ZABLE W DŁOŃ W przypadku wystąpienia omawianego problemu można podjąć walkę na jednym z frontów: Przetwarzanie wstępne zbioru danych treningowych Stworzenie algorytmu indukcji klasyfikatora mającego na uwadze dysproporcje między klasami Wykorzystanie złożonych klasyfikatorów: Boosting, bagging, etc. Cost-sensitive learning

10 F LIRTOWANIE ZE ZBIOREM DANYCH Zabiegi ingerujące w zbiór danych mające na celu uzyskanie lepszego klasyfikatora, można podzielić na: „Nadlosowywanie” przykładów klasy mniejszościowej, w tym: Duplikacja istniejących przykładów Tworzenie sztucznych przykładów Usuwanie przykładów z klasy większościowej Czyszczenie zbioru danych

11 SMOTE Dogenerowanie nowych przykładów klasy mniejszościowej pomiędzy przykładami pierwotnymi Uogólnienie obszaru decyzyjnego Parametry: Liczba sąsiadów brana pod uwagę Liczba dogenerowanych przykładów Zastosowana miara odległości Problemy „Small disjuncts”

12 P ODOBNI INACZEJ Podobieństwo przykładów można wyrazić za pomocą odległości między nimi w przestrzeni atrybutów Należy przy tym uwzględnić: Różne typy: atrybutów Wartości brakujące Popularne miary: Euklidesowa HOEM HVDM DVDM IVDM, WVDM

13 SMOTE – MODYFIKACJE Borderline SMOTE Nadlosowywanie obszarów granicznych Występuje w dwóch wersjach Safe-Level SMOTE Skomplikowany algorytm nadlosowywania w oparciu o sąsiedztwo przykładu pozytywnego oraz jego najbliższego pozytywnego sąsiada Czy to działa?

14 W YRZUĆ ŚMIECI ! Usuwanie „niepotrzebnych” przykładów z klasy większościowej ma na celu zrównoważenie wag obu klas Powoduje utratę informacji Dobór przykładów do usunięcie w taki sposób, aby ich brak nie wpłynął na detekcje przykładów z tej klasy Heurystyczny wybór przykładów nadmiarowych

15 S EGREGACJA ODPADÓW EasyEnsemble - złożony klasyfikator tworzony poprzez losowanie ze zwracaniem przykładów z klasy większościowej BalanceCascade - kaskada klasyfikatorów, filtrująca w każdym węźle przykłady z klasy większościowej metody z rodziny NearMiss - filtrowanie przykładów klasy większościowej w oparciu o ich sąsiedztwo One-sided selection - filtrowanie w oparciu o algorytm kNN oraz metody czyszczenia danych

16 P OSPRZĄTAJ POKÓJ ! Metody czyszczenia zbioru danych mają na celu: Wyeliminowanie szumów Wyeliminowanie nakładania się klas powstałego m.in. na wskutek dogenerowania nowych przykładów Popularne środki czystości: Tomek links Wilson ENN NCL

17 P RASA Batista: A Study of the Behavior of Several Methods for Balancing Bunkhumpornpat: Safe-Level-SMOTE Chawla: SMOTE - Synthetic Minority Over- sampling Technique Han: Borderline-SMOTE A New Over-Sampling Method He: Learning from Imbalance Data Wilson: Improved Heterogeneous Distance Functions

18 D ZIĘ -K U -J E -M Y ZA UWAGĘ