IV EKSPLORACJA DANYCH Zadania eksploracji danych: klasyfikacja

Algorytmy i eksploracja danych

Algorytmy i eksploracja danych

Informacje ogólne

Zajęcia w cyklu "Semestr zimowy 2019/20" (zakończony)

Zajęcia w cyklu "Semestr zimowy 2020/21" (zakończony)

Zajęcia w cyklu "Semestr zimowy 2021/22" (zakończony)

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.

Właścicielem praw autorskich jest Politechnika Bydgoska im. Jana i Jędrzeja Śniadeckich.

Eksploracja danych

Rozwój oraz upowszechnienie rozwiązań technologicznych służących gromadzeniu informacji sprawiły, że we wszystkich obszarach działalności człowieka mamy do czynienia z przechowywaniem i przetwarzaniem danych. Zazwyczaj są one wykorzystywane jedynie w bieżącej działalności instytucji je gromadzących; analiza i interpretacja danych może jednak dostarczyć istotnej wiedzy na temat reguł i zależności rządzących procesami biznesowymi, zachowaniami konsumentów i zagrożeniami funkcjonowania firmy. Eksploracja danych to nowa dziedzina informatyki odpowiadająca na potrzebę zaawansowanej i automatycznej analizy informacji. Jej dynamiczny rozwój wynika z konieczności integracji istniejących algorytmów w celu efektywnego przetwarzania dużej ilości nowych typów danych. Obecnie, wraz z rozwojem narzędzi do generowania i przechowywania danych, eksploracji poddawane są coraz bardziej złożone informacje: multimedialne (zdjęcia, filmy, muzyka), przestrzenne (mapy), przebiegi czasow...

Rozwój oraz upowszechnienie rozwiązań technologicznych służących gromadzeniu informacji sprawiły, że we wszystkich obszarach działalności człowieka mamy do czynienia z przechowywaniem i przetwarzaniem danych. Zazwyczaj są one wykorzystywane jedynie w bieżącej działalności instytucji je gromadzących; analiza i interpretacja danych może jednak dostarczyć istotnej wiedzy na temat reguł i zależności rządzących procesami biznesowymi, zachowaniami konsumentów i zagrożeniami funkcjonowania firmy. Eksploracja danych to nowa dziedzina informatyki odpowiadająca na potrzebę zaawansowanej i automatycznej analizy informacji. Jej dynamiczny rozwój wynika z konieczności integracji istniejących algorytmów w celu efektywnego przetwarzania dużej ilości nowych typów danych. Obecnie, wraz z rozwojem narzędzi do generowania i przechowywania danych, eksploracji poddawane są coraz bardziej złożone informacje: multimedialne (zdjęcia, filmy, muzyka), przestrzenne (mapy), przebiegi czasowe, struktury chemiczne (sekwencje DNA), sieci społecznościowe. Niniejsza książka jest pierwszym na polskim rynku samodzielnym podręcznikiem przedstawiającym metody eksploracji danych w ujęciu algorytmicznym, a nie statystycznym. Zawiera omówienie podstawowych metod eksploracji, min. odkrywanie asocjacji, wzorców sekwencji, klasyfikację i grupowanie. Dla każdej z metod omówiono podstawowe algorytmy eksploracji ilustrowane licznymi przykładami. Dodatkowo, w celu sprawdzenia wiedzy czytelnika, przygotowano zestaw zadań i ćwiczeń do samodzielnego wykonania. Głównymi adresatami podręcznika są studenci informatyki, ekonomii, psychologii, socjologii – dziedzin, w których duże znaczenie ma przetwarzanie informacji. Z pewnością skorzystają z niego również doktoranci zajmujący się zagadnieniami eksploracji danych i odkrywania wiedzy.

IV EKSPLORACJA DANYCH Zadania eksploracji danych: klasyfikacja

Prezentacja na temat: "IV EKSPLORACJA DANYCH Zadania eksploracji danych: klasyfikacja"— Zapis prezentacji:

1 IV EKSPLORACJA DANYCH Zadania eksploracji danych: klasyfikacja

Klasyfikacja polega na przewidywaniu wartości jednej zmiennej na podstawie znanych wartości innych zmiennych. Przy zastosowaniu klasyfikacji zmienna, która będzie przewidywana jest kategoryczna.

2 IV EKSPLORACJA DANYCH Zadania eksploracji danych: klasyfikacja R

R - korzeń N N N - węzeł N L L - liść L L L L

3 IV EKSPLORACJA DANYCH Stosowanie algorytmu drzew decyzyjnych

Algorytmy drzew decyzyjnych należą do uczenia nadzorowanego i, jako takie, wymagają wstępnie sklasyfikowanej zmiennej celu. Należy dostarczyć zbiór uczący zawierający wartości zmiennej celu. Zbiór uczący powinien być bogaty i różnorodny, zapewniający zdrową reprezentatywną grupę typów rekordów, których klasyfikacja może być potrzebna w przyszłości. Drzewa decyzyjne uczą się poprzez przykład i jeżeli systematycznie brakuje przykładów dla podzbioru możliwego do określenia, to klasyfikacja i przewidywanie dla tego podzbioru będą problematyczne lub niemożliwe Klasy zmiennej celu muszą być dyskretne, to znaczy, nie można zastosować analizy drzew decyzyjnych do ciągłej zmiennej celu. Raczej zmienna celu musi przyjmować wartości, które są jasno wyznaczone jako przynależne do danej klasy lub nie.

4 IV EKSPLORACJA DANYCH Jak drzewa decyzyjne wybierają atrybut dzielący:

Drzewa decyzyjne starają się stworzyć zbiór liści, które są najczystsze, tzn. takie które zawierają jak najwięcej rekordów należących do tej samej klasy. W ten sposób drzewa decyzyjne zapewniają przypisanie do klasy z największą miarą ufności. Metod określania jednorodności będącej miarą czystości liści jest wiele, a dwie najpopularniejsze to: Algorytm drzew klasyfikacyjnych i regresyjnych CART Algorytm C4.5

5 IV EKSPLORACJA DANYCH Φ(s│t) = 2 PLPP (s│t)

Algorytm drzew klasyfikacyjnych CART Φ(s│t) = 2 PLPP (s│t) gdzie: (s│t) = Σ │P(j│tL) – P(j│tP) │

6 IV EKSPLORACJA DANYCH Φ(s│t) = 2 PLPP (s│t) PL = PP =

Algorytm drzew klasyfikacyjnych CART Φ(s│t) = 2 PLPP (s│t) liczba rekordów w tL PL = liczba rekordów w zbiorze uczącym liczba rekordów w tP PP = liczba rekordów w zbiorze uczącym

7 IV EKSPLORACJA DANYCH (s│t) = Σ │P(j│tL) – P(j│tP) │

Algorytm drzew klasyfikacyjnych CART (s│t) = Σ │P(j│tL) – P(j│tP) │ liczba rekordów należących do klasy j w tL P(j│tL) = liczba rekordów w t liczba rekordów należących do klasy j w tP P(j│tP) = liczba rekordów w t

8 IV EKSPLORACJA DANYCH Algorytm drzew klasyfikacyjnych CART

9 IV EKSPLORACJA DANYCH Algorytm drzew klasyfikacyjnych CART

10 IV EKSPLORACJA DANYCH Algorytm drzew klasyfikacyjnych CART

11 IV EKSPLORACJA DANYCH Algorytm drzew klasyfikacyjnych CART

12 IV EKSPLORACJA DANYCH Algorytm C 4.5

Algorytmy C4.5 nie jest ograniczony do binarnych podziałów. Podczas, gdy CART tworzy drzewo binarne, C4.5 tworzy drzewo o bardziej zróżnicowanym kształcie. Dla zmiennych jakościowych algorytm C4.5 z definicji tworzy osobne gałęzie dla każdej wartości atrybutu jakościowego. Może to powodować nadmierne rozgałęzienie. Metoda mierzenia jednorodności w algorytmie C4.5 jest zupełnie inna i używa pojęcia zysk informacji lub redukcja entropii.

13 H(X) = –Σ pj log2(pj) IV EKSPLORACJA DANYCH Algorytm C 4.5

Dla zmiennej X przyjmującej k możliwych wartości z prawdopodobieństwem p odpowiednio p1, p2, …pi, można zdefiniować wielkość nazwaną entropią X określoną wzorem: H(X) = –Σ pj log2(pj)

14 HS(T) = Σ Pi HS(Ti) IV EKSPLORACJA DANYCH Algorytm C 4.5

Dla założenia, że możliwy jest podział S, dzielący zbiór T na kilka podzbiorów T1, T2, … Tk, wówczas ważona suma entropii dla pojedynczych podzbiorów określona jest wzorem: HS(T) = Σ Pi HS(Ti) i=1 k

15 IV EKSPLORACJA DANYCH H(X) = –Σ pj log2(pj) HS(T) = Σ Pi HS(Ti) i=1 k

16 IV EKSPLORACJA DANYCH Zalety drzew decyzyjnych szybka klasyfikacja

zrozumiały proces decyzyjny możliwość aproksymacji złożonych powierzchni decyzyjnych możliwość stosowania cech różnego typu efektywne z punktu widzenia przechowywania w pamięci

17 IV EKSPLORACJA DANYCH Klasyfikacja: drzewa decyzyjne

Drzewa decyzyjne – zdolność do interpretacji Reguły decyzyjne mogą zostać zbudowane z drzewa decyzyjnego po prostu przez przechodzenie dowolna ścieżką z korzenia do liścia. Pełny zbiór reguł decyzyjnych stworzonych przez drzewo jest równoważny (dla celów klasyfikacji) z drzewem decyzyjnym Wsparcie reguł decyzyjnych odnosi się do procentu rekordów w zbiorze danych, które są przypisane do danego liścia Ufność reguł wskazuje na procent rekordów w liściu, dla których reguła jest prawdziwa.

18 IV EKSPLORACJA DANYCH Wady drzew decyzyjnych

im więcej klas oraz im bardziej się one nakładają, tym większe drzewo decyzyjne trudno zapewnić jednocześnie wysoką jakość klasyfikacji i małe rozmiary drzewa w węzłach testowany jeden atrybut