1 Generowanie drzew decyzyjnych dla dużych zbiorów danych

2 Plan wykładu Problematyki związane z dużymi zbiorami danychAlgorytmy generowania drzewa: SPRINT Algorytm sekwencyjny Algorytm równoległy Soft tree: drzewo z „elastycznymi podziałami”

3 Problemy związane z dużymi zbiorami danychDane w praktyce są gigantyczne Dane nie mieszczą się w pamięci Dane zawierają szumy (okłamywania) Generowanie drzewa jest czasochłonne

4 Algorytmy dla dużego zbioru danychMuszą działać bez założenia o wielkości pamięci Muszą działać w miarę szybko (w akceptowanym czasie) Muszą dać dobry wynik w przypadku wystąpienia szumu w zbiorze danych Muszą dać zrozumiałe dla człowieka wyniki Muszą dać dobrą jakość klasyfikacji

5 Standardowe algorytmyKażdy węzeł stowarzyszony z podzbiorem danych -> ograniczenie pamięciowe Przy wyznaczeniu najlepszego podziału dane są wielokrotnie sortowane -> czasochłonne

6 Miara złożoności zbioru (c.d.)Gini Index: Gini(X) = 1- j [p(j | X)]2 gdzie p(j | X) = Cj / |X|: jest częstość wystąpienia j-tej klasy w zbiorze X Entropia: Ent(X) = - j p(j | X) log p(j | X) Konflikt: Conflict(X) = ij CiCj conflict = 6 conflict = 5 conflict = 8 conflict = 9

7 Miara jakości podziałuZbiór danych przy węźle t jest podzielony na k części ni : liczba obiektów w i - tym poddrzewie, n : liczba obiektów w węźle t Miara Gini: Kryterium podziału: Minimalizuje GINIsplite Miara Gain: Kryterium podziału: Maksymalizuje Gainsplite Miara Discern: Kryterium podziału: Maksymalizuje Discern

8 Wyznaczanie optymalnego podziału atrybutów rzeczywistychSortuj wartości atrybutu Przeglądaj kolejną wartość progową, obliczając rozkład klas decyzyjnych Wybierz wartość progową o najmniejszym GINI index

9 Złożoność algorytm szukania optymalnego podziałuDany atrybut rzeczywisty a i zbiór możliwych wartości progowych (1, 2,...N ), najlepszy test (a< i) można znaleźć w czasie (N) Minimalna liczba prostych zapytań SQL potrzebna do szukania najlepszego testu jest (dN), gdzie d jest liczba klas decyzyjnych Wada: szukanie najlepszego podziału jest kosztowne, jeśli atrybut zawiera dużo różnych wartości.

10 Algorytm SPRINT - charakterystykiNadaje się dla danych częściowo umieszczonych na dysku Używa się techniki pre-sortowania w celu przyspieszenia procesu obliczenia na atrybutach rzeczywistych Dane są sortowane tylko raz przed obliczeniem Łatwo można zrównoleglić

11 SPRINT - struktura danychKażdy atrybut ma swoją listę wartości Każdy element listy ma trzy pole: wartość atrybutu, numer klasy i rid (numer obiektu w zbiorze danych) Rzeczywiste atrybuty są uporządkowane (tylko raz przy utworzeniu) Na początku listy są stowarzyszone z korzeniem drzewa Kiedy węzeł jest podzielony, listy są podzielone i są stowarzyszone z odpowiednimi następnikami Listy są zapisane na dysku w razie potrzeby

12 Przykład: listy wartościAge Class rid 17 High 1 20 5 23 32 Low 4 43 2 68 3 Car Type Class rid family High sports 1 2 Low 3 truck 4 high 5

13 Podział listy wartości

14 Struktura danych - HistogramSPRINT używa: indeksu Gini do oceny jakości podziału funkcji testu typu (a  ) dla atrybutów rzeczywistych funkcji testu typu (a  V) dla atrybutów symbolicznych Histogram: rozkład klas decyzyjnych zbadanego zbioru danych Dla atrybutu rzeczywistego dwa histogramy: Cbelow– histogram dla danych „poniżej” wartości progowej Cabove – histogram dla danych „powyżej” wartości progowej Dla atrybutu symbolicznego jeden histogram zwany count matrix

15 Histogram: przykład Punkt podziału Count matrix Histogram klas AgeClass rid 17 High 1 20 5 23 32 Low 4 43 2 68 3 5 high family 4 Low truck 3 2 High sports 1 rid Class Car Type Punkt podziału Count matrix Histogram klas H L family 2 1 sports truck

16 Wyznaczanie najlepszego podziału - atrybut rzeczywistyKażdy węzeł ma listy wartości obiektów w danym węźle Wejście: lista wartości atrybutu a Wyjście: (a) 1. Cbelow = 0 2. Cabove = rozkład klas obiektów w danym węźle 3. Przeglądaj kolejną wartość atrybutu 3.1 Oblicz jakość podziału 3.2 Modyfikuj Cbelow i Cabove 4. Wybierz najlepszy podział

17 Wyznaczanie podziału-atrybutu rzeczywistego (c.d.)

18 Wyznaczanie podziału -atrybutu symbolicznego5 high family 4 Low truck 3 2 High sports 1 rid Class Car Type L H Count Matrix Lista wartości CarType 1. Wyznacz macierz rozkładu klas obiektów w danym węźle 2. Używając algorytmu aproksymacyjnego (w SLIQ) wyznacz podzbiór wartości V  Da t. żeby test (aV) był optymalny

19 Wykonanie podziału Każda lista jest podzielona na dwie listyAtrybut testujący: Podziel wartości listy zgodnie z testem Atrybut nie testujący: Nie można używać testu Używaj rid Skorzystaj z tablicy haszującej

20 Wykonanie podziału (c.d.)- atrybutu nie testującegoPrzy podziale atrybutu testującego, wstaw rid rekordów do tablicy haszującej. Tablica haszująca: informacje o tym do którego poddrzewa rekord został przeniesiony. Algorytm: Przeglądaj kolejny rekord listy Dla każdego rekordu wyznacz (na podstawie tablicy haszującej) poddrzewo, do którego rekord ma być przeniesiony

21 Wykonanie podziału (c.d) - duża tablica haszującaProblem: Tablica haszująca nie mieści się w pamięci Algorytm: Krok 1: Podziel zbiór wartości atrybutu testującego na małe porcje tak, żeby tablica haszująca mieściła się w pamięci Krok 2: Dla każdej porcji Podziel rekordy atrybutu testującego do właściwego podrzewa Buduj tablicę haszującej Przeglądaj kolejny rekord atrybutu nietestującego i przynieś go do odpowiedniego poddrzewa jeśli rekord występuje w tablicy haszującej Krok 3: Jeśli wszystkie rekordy zostały przydzielone do poddrzew stop wpp. goto krok 2

22 SPRINT – algorytm równoległyListy wartości atrybutów są równo podzielone Atrybut rzeczywisty: sortuj zbiór wartości i podziel go na równe przedziały Atrybut numeryczny: podziel według rid Każdy procesor ma jedną część każdej listy

23 Podział zbioru danych Procesor 0 Procesor 1 Age Class rid 17 High 1 205 23 Car Type Class rid family High sports 1 2 Procesor 1 Age Class rid 32 Low 4 43 High 2 68 3 Car Type Class rid family Low 3 truck 4 high 5

24 Wyznaczanie najlepszego podziału – atrybut rzeczywistyKażdy procesor ma przedział wartości atrybutu Każdy procesor inicjalizuje Cbelow i Cabove uwzględniając rozkład klas w innych procesorach Każdy procesor przegląda swoją listę i wyznacza najlepszą lokalną wartość progową Procesory komunikują się w celu szukania najlepszej globalnej wartości progowej

25 Wyznaczanie najlepszego podziału – atrybut symbolicznyKażdy procesor buduje lokalne count matrix i wysyła wynik do centralnego procesora Centralny procesor oblicza globalny count matrix Procesory wyznaczają najlepszy podział na podstawie globalnego count matrix

26 Histogramy w obliczeniu równoległymProcess 0 Age Class rid 17 High 1 20 5 23 H L Cbelow Cabove 4 2 Process 1 Age Class rid 32 Low 4 43 High 2 68 3 H L Cbelow 3 Cabove 1 2

27 Wykonanie podziału Podział atrybutu testującego: Każdy procesor wyznacza poddrzewa, do których rekordy w lokalnej liście będą przeniesione Procesory wymieniają ze sobą informacje Podział pozostałych atrybutów: Po otrzymaniu informacji ze wszystkich procesorów każdy procesor buduje tablicę haszującą i wykonuje podziały dla pozostałych atrybutów

28 SPRINT Wada: Dodatkowe struktury danychNieefektywny jeśli atrybut ma dużo wartości Nie wykorzystuje mocnych narzędzi systemów baz danych

29 Drzewo z „elastycznymi podziałami” - klasyfikacja

30 Elastyczna wartość progowa vs. ostra wartość progowaStandardowy test: (a<) Nowy test: „Elastyczna” wartość progowa: zamiast  przedział (1, 2). Funkcja testu: trójka (a, 1, 2) Zbiór obiektów jest podzielony na trzy podzbiory: a  1 i a  2: przedziały pewności 1 < a <  : przedział niepewności

31 Drzewo z „elastycznymi podziałami” vs. standardowe drzewoTaxInc,75,85 <85K >75K Standardowe drzewo (z ostrym podziałem) Drzewo z „nieostrym podziałem”

32 Klasyfikacja nowego obiektuI strategia - fuzzy decision tree: Przy węzłach wewnętrznych, wyznacz prawdopodobieństwa, że obiekt należy do lewego i do prawego poddrzewa. Dla każdego liścia, oblicz prawdopodobieństwo tego, że obiekt należy do tego liścia Klasa, do której należy obiekt jest związana z liściem o największym prawdopodobieństwie

33 Klasyfikacja nowego obiektu (c.d.)II strategia: rough decision tree Używaj obu poddrzew (jeśli obiekt należy do przedziału niepewności) Utwórz wektor wyników agregując wyniki otrzymane z poddrzew Głosuj, żeby znaleźć najlepszą decyzję

34 Wyznaczanie najlepszego podziałuAtrybut symboliczny: standardowo Atrybut rzeczywisty: Używaj techniki „dziel i rządź” Używaj zapytań SQL do szybkiego obliczenia rozkładu klas w przedziałach

35 a(o1) <  < a(o2) i d(o1)  d(o2)Techniki ulepszania Definicja: wartość podziału  jest brzegowa, jeśli istnieją 2 kolejne rekordy o1 i o2 takie, że a(o1) <  < a(o2) i d(o1)  d(o2) 1 2 3 4 5 6 7 8 DISCERN() 1 2 3 4 5 6 7 8

36 Techniki ulepszania – Usunąć wartości niegraniczneObserwacja: optymalna wartość progowa należy do zbioru wartości granicznych. Wniosek: wartości nie będące brzegowymi można usunąć ze zbioru możliwych wartości progowych.

37 Techniki ulepszania – Eliminować skrajne wartościDefinicja: Niech i oznacza i-tą klasę decyzyjną. Mediana(i) jest wartość progowa  taka, że |{x: a(x) <  i d(x) = i}| = |{x: a(x)   i d(x) = i}| Obserwacja: Funkcja Discern: {1, 2,... k}   jest jest rosnąca w przedziale [1, mini(Median(i))) jest malejąca w przedziale (maxi(Median(i)), k] Wniosek: Można ograniczyć przedział wyszukiwania best  [mini(Median(i)), maxi(Median(i))]

38 Eliminować skrajne wartości (c.d.)

39 Technika „dziel i rządź”Idea: Krok 1: Podziel zbiór wartości atrybutu na k przedziałów Krok 2: Oceń jakości przedziałów Krok 3: Wybierz najlepszy przedział Krok 4: Powtórz proces dla najlepszego przedziału 1 2 3 4 5 6 7 8 Cykl 1: a Cykl 2: Cykl 3: k = 3 . . .

40 Technika „dziel i rządź”– miara oceny jakości przedziałuProblem: jak ocenić jakość przedziału [L,R]? Miara oceny musi dobrze oszacować jakość najlepszej wartości progowej w przedziale [L,R].

41 Technika „dziel i zwycięż”vL vR Dla dowolnej   (vL, vR) Wartość oczekiwana: Odchylenie standardowe: Miara jakości przedziału:

42 Algorytm „dziel i rządź”Wejście: atrybut a, amin, amax Wyjście: optymalny test (a < ) Parametry: k ,  vL= amin; vR = amax; While (vL < vR) do { 1.Podziel przedział [vL , vR] na k równych przedziałów za pomocą punktów: pi = vL + i*(vR - vL) / k; dla (i =0,1,...,k) 2. Dla (i= 1,2,...,k) 2.1. Oblicz Eval([pi-1; pi], ); 2.2. Niech [pj-1; pj] będzie najlepszym przedziałem; 2.3. vL = pi-1; vR = pj; }; Return vL;

43 Kryterium oceny stabilności przedziałuPod-przedziały nie mają lepszej jakości Przedział jest w miarę mały Przedział zawiera małą liczbę obiektów

44 Wykonanie podziału Test jest typu (aV): standardowo Test typu (a, 1, 2): Jeśli (a(x) < 2) to x należy do lewego poddrzewa Jeśli (a(x) > 1) to x należy do prawego poddrzewa Jeśli (1 < a(x) < 2) to x należy do obu poddrzew

45 Drzewo z elastycznymi podziałami - obserwacjaZaleta: Nie wymaga dodatkowych struktur danych Nie wymaga umieszczenia danych w pamięci Korzysta się z SQL-owych zapytań Dobre rozwiązanie dla danych z szumami Wada: Czas klasyfikacji jest dłuższy