1 Promotor: dr inż. Maciej GrzendaJakub Wojtczak Analiza wpływu wykorzystania metod uzupełniania danych na realizację zadania klasyfikacji Promotor: dr inż. Maciej Grzenda
2 Problem niekompletnych danychJakub Wojtczak Problem niekompletnych danych ID Imię i Nazwisko Płeć Województwo Branża Wiek Zarobki 1 Jan Kowalski M lubuskie IT 27 3500 2 Adam Nowak śląskie Oświata 49 ???? 3 Agnieszka Witkowska K mazowieckie 46 10000 4 Dariusz Mróz łódzkie 33 5 Aleksandra Jońska 39 8000 Brak odpowiedzi na część pytań w ankietach, Błędne działanie części urządzeń pomiarowych, Ewolucja modelu danych (dodanie nowych atrybutów w trakcie użytkowania bazy danych). Tab. Przykładowe dane klientów firmy
3 Traktowanie niekompletnych danychJakub Wojtczak Traktowanie niekompletnych danych Usunięcie niekompletnych danych Pozyskanie i wykorzystanie informacji o parametrach rozkładu danych Próba wstawienia brakujących danych Ad 1. Całkowite usunięcie wszystkich niekompletnych rekordów Badanie stopnia niekompletności oraz istotności w kontekście dalszej analizy danych Przede wszystkim usunięcie całych rekordów/atrybutów ze zbioru danych prowadzi za sobą usunięcie wielu istniejących danych z tychże rekordów/atrybutów. Poza tym usunięcie niekompletnych rekordów może wpłynąć na rozkład danych. Ad 2. Znajomość rozkładu danych EM – estymujemy parametry rozkładu Ad 3. Ważnym założeniem jest korzystanie jedynie z informacji, jakie zawiera sam zbiór danych. Zakładany jest brak jakichkolwiek informacji pochodzących spoza zbioru danych (np. informacji o charakterze rozkładu).
4 Wstawianie niekompletnych wartości[2]Jakub Wojtczak Wstawianie niekompletnych wartości[2] Podmiana niekompletnych rekordów Wstawienie średniej/mody/mediany Hot deck (oraz cold deck) Modele predykcyjne Non-invasive imputation Metoda oparta o algorytm k-NN
5 Problemy uzupełniania niekompletnych zbiorówJakub Wojtczak Problemy uzupełniania niekompletnych zbiorów Wiele niepełnych atrybutów Wiele metod uzupełniania – dobór najbardziej odpowiedniej Parametryzacja metod Atrybuty ilościowe i jakościowe Definicja poprawności uzupełnienia
6 Automatyczny dobór metod wstawianiaJakub Wojtczak Automatyczny dobór metod wstawiania Dany jest zbiór metod uzupełniania danych Dany jest zbiór niepełnych atrybutów (w obrębie danego zbioru danych) Dopasowanie odpowiedniej metody dla każdego z atrybutów Algorytm genetyczny
7 Algorytm genetyczny – reprezentacja problemuJakub Wojtczak Algorytm genetyczny – reprezentacja problemu Metoda nr , Metoda nr , Metoda nr 2 Chromosom – wektor metod ID Imię i Nazwisko Płeć Województwo Branża Wiek Zarobki 1 Jan Kowalski M Lubuskie IT 27 3500 2 Adam Nowak Śląskie Oświata 49 ???? 3 Agnieszka Witkowska K Mazowieckie 46 10000 4 Dariusz Mróz Łódzkie 33 5 Aleksandra Jońska 39 8000 Brak odpowiedzi na część pytań w ankietach, Błędne działanie części urządzeń pomiarowych, Ewolucja modelu danych (dodanie nowych atrybutów w trakcie użytkowania bazy danych). Tab. Przykładowe dane klientów firmy
8 Miara jakości uzupełnienia danychJakub Wojtczak Miara jakości uzupełnienia danych Niepotrzebne dokładne odtworzenie Niepotrzebna próba odtworzenia szumu Nadrzędny cel – prawidłowe rozpoznanie litery K Skuteczność klasyfikacji miarą jakości uzupełnienia[3] Rys. Zaszumiona próbka wraz z brakującym fragmentem. Źródło: [1]
9 Jakub Wojtczak Hipoteza Optymalny dobór metod wstawiania dla poszczególnych atrybutów zbioru danych zależy od specyfiki zastosowanego (w celu mierzenia jakości wstawiania) modelu predykcyjnego.
10 Testy Metody uzupełniania danych: Testowe zbiory danych ([2]):Jakub Wojtczak Testy Metody uzupełniania danych: proste(losowy, mediana, moda, średnia), non-invasive imputation, kNN (wersje: moda, mediana, średnia), oparte o SOM (wersje: moda, mediana, średnia). Testowe zbiory danych ([2]): Iris (w wersjach Iris25, Iris50), Hepatitis (w wersjach Hepatitis, Hepatitis25, Hepatitis50), Votes (Votes, Votes50),
11 Jakub Wojtczak Testy Klasyfikatory: SVM, Perceptron wielowarstwowy (MLP), Drzewo decyzyjne. Pomiar jakości uzupełnienia – skuteczność klasyfikacji, wielokrotna walidacja krzyżowa.
12 Wyniki – porównanie zwycięskich chromosomówJakub Wojtczak Wyniki – porównanie zwycięskich chromosomów Zbiór danych Algorytm klasyfikacji Skuteczność klasyfikacji Zwycięski chromosom Iris25 C4.5 0,9333 [ NII ( ); NII ( ); KNN-median (5); KNN-median (1); ] MLP 0,9187 [ SOM-mean (2); NII ( ); NII ( ); Mean; ] SVM 0,9233 [ SOM-mean (2); NII (0.4906); KNN-mean (3); KNN-median (6); ] Iris50 0,8540 [ NII ( ); NII ( ); SOM-mean (2); KNN-mean (4); ] 0,8820 [ NII ( ); KNN-mean (8); KNN-mean (6); KNN-mean (7); ] 0,8460 [ SOM-mean (8); KNN-median (8); NII (0.0344); KNN-mean (3); ]
13 Wyniki – porównanie zwycięskich chromosomówJakub Wojtczak Wyniki – porównanie zwycięskich chromosomów Zbiór danych Algorytm klasyfikacji Skuteczność klasyfikacji Zwycięski chromosom Hepatitis25 C4.5 0,8239 [ KNN-mode (1); NII ( ); KNN-mode (7); NII ( ); NII ( ); KNN-mode (4); Mode; Mode; KNN-mode (9); Mode; KNN-mode (2); Mode; NII ( ); Mean; KNN-median (5); SOM-mode (8); KNN-median (6); KNN-median (7); Mode; ] Hepatitis25 MLP 0,8316 [ KNN-mode (9); NII (0.2811); SOM-mode (2); NII ( ); KNN-mode (9); NII ( ); KNN-mode (4); NII (0.2927); Mode; SOM-mode (9); Mode; Mode; SOM-mode (3); KNN-mean (10); Mode; SOM-mode (10); KNN-mean (5); KNN-mean (7); NII (0.2302); ] SVM 0,8465 [ KNN-mode (8); KNN-mode (2); NII ( ); NII (0.5); SOM-mode (6); KNN-mode (10); SOM-mode (10); KNN-mode (10); KNN-mode (10); NII ( ); SOM-mode (9); Mode; Mode; NII ( ); KNN-mean (5); Median; KNN-mean (10); Median; KNN-mode (10); ] Hepatitis50 0,8452 [ KNN-mode (5); KNN-mode (6); KNN-mode (10); SOM-mode (10); KNN-mode (4); NII ( ); KNN-mode (9); NII ( ); NII ( ); NII ( ); Mode; KNN-mode (7); Mode; Median; SOM-mean (4); Median; KNN-mean (10); NII ( ); NII ( ); ] 0,8323 [ KNN-mean (8); KNN-mode (2); KNN-mode (7); SOM-mode (2); NII ( ); NII ( ); NII ( ); KNN-mode (5); SOM-mode (8); Mode; KNN-mode (5); SOM-mode (9); Mode; KNN-median (8); KNN-mode (10); SOM-mean (3); Mean; SOM-mean (7); KNN-mode (6); ] 0,8329 [ SOM-median (2); SOM-mode (9); NII ( ); NII ( ); SOM-mode (4); SOM-mode (10); KNN-mode (6); SOM-mode (8); SOM-mode (6); NII ( ); SOM-mode (7); SOM-mode (10); KNN-mode (8); KNN-median (2); KNN-median (8); SOM-mean (3); SOM-mean (10); KNN-mode (4); NII ( ); ]
14 Wyniki – porównanie z mechanizmem zailmplementowanym w bibliotece WEKAJakub Wojtczak Wyniki – porównanie z mechanizmem zailmplementowanym w bibliotece WEKA Zbiór danych Klasyfikator Algorytm genetyczny Wbudowane mechanizmy klasyfikatorów WEKA Iris25 C4.5 0,9333 0,9252 MLP 0,9187 0,8701 SVM 0,9233 0,8689 Iris50 0,8540 0,8096 0,8820 0,7900 0,8460 0,7805
15 Wyniki – porównanie z mechanizmem zailmplementowanym w bibliotece WEKAJakub Wojtczak Wyniki – porównanie z mechanizmem zailmplementowanym w bibliotece WEKA Zbiór danych Klasyfikator Algorytm genetyczny Wbudowane mechanizmy klasyfikatorów WEKA Hepatitis25 C4.5 0,8239 0,8258 MLP 0,8316 0,7928 SVM 0,8465 0,8506 Hepatitis50 0,8452 0,7885 0,8323 0,7399 0,8329 0,8254
16 Wyniki – porównanie z mechanizmem zailmplementowanym w bibliotece WEKAJakub Wojtczak Wyniki – porównanie z mechanizmem zailmplementowanym w bibliotece WEKA Zbiór danych Klasyfikator Algorytm genetyczny Wbudowane mechanizmy klasyfikatorów WEKA Votes C4.5 0,9690 0,9656 MLP 0,9579 0,9455 SVM 0,9676 0,9595 Votes50 0,8885 0,8034 0,8832 0,8711 0,9143 0,9035
17 Podsumowanie Zaimplementowany algorytm osiąga satysfakcjonujące wynikiJakub Wojtczak Podsumowanie Zaimplementowany algorytm osiąga satysfakcjonujące wyniki Wyniki przeprowadzonych testów potwierdzają prawdziwość hipotezy Dalsze badania: usuwanie i ponowne wstawianie zaszumionych danych
18 Jakub Wojtczak Bibliografia P. Zawistowski, M.Grzenda, Handling Incomplete Data Using Evolution of Imputation Methods, 2009. S. Parsons, „Current approaches to handling imperfect information in data and knowledge bases,” IEEE Transactions on Knowledge and Data Engineering, nr 8(3), 1996. E. Acuña i C. Rodriguez, „The treatment of missing values and its effect in the classifier accuracy,” w Classification, Clustering and Data Mining Applications, Heidelberg, 2004.