Cwiczenia 6


1. [trzeba] Dla ktorego zbioru entropia bedzie wieksza? 

   a) {31/32, 1/256, 1/256, 1/256, 1/256, 1/256, 1/256, 1/256, 1/256}

   b) {1/2, 1/4, 1/8, 1/16, 1/32, 1/32}

  Odp. a) 0,06054 + 7*0,03125 ~= 0,28   b) 0,5 + 0,5 + 0,375 + 0,25 + 0,15625 + 0,15625 ~= 1,9375

  Co oznacza wartosc entropii?

  Odp. Dolne ograniczenie na srednia liczbe bitow, ktore trzeba uzyc
       do zakodowania kazdej wartosci przy danym rozkladzie.

 Podac przyklad, w jaki sposob mozna zakodowac wartosci o rozkladzie a) uzywajac srednio mniej niz 1 bit na wartosc.


2. [warto] Zad 18.10 z ksiazki
    
   Załóżmy, że atrybut rozdziela zbiór E na podzbiory Ei, i każdy z nich ma pi-pozytywnych oraz ni-negatywnych. 
   Pokazać, ze atrybut ma Gain>0, chyba żę pi/(pi+ni) jest jednakowe dla wszystkich i. (Wtedy 0).

3. [warto] (18.4) Dlaczego na zadnej sciezce w dowolnym drzewie decyzyjnym nie testujemy tego samego atrybutu symbolicznego dwa razy?

4. [warto] Co sie dzieje przy konstrukcji drzewa, kiedy zbior jest sprzeczny, tzn. zawiera przyklady o takich samych wartosciach atrybutow majace inna decyzje (pytanie powiazane z zadaniem 18.8)? 
Jakie decyzje przypisac lisciom w drzewie, ktore maja niejednoznaczny rozklad decyzji (zad. 18.8 a)?

5. [trzeba] Konstrukcja drzewa, np. zadanie 3 z egzaminu czerwiec 2004

6. [trzeba] Efektywny algorytm na znajdowanie najlepszego ciecia dla atrybutow numerycznych
	Wsk. O(nlogn) poprzez posortowanie

7. [trzeba] Zalozmy, ze mamy zbior treningowy dla problemu zgadywania, czy w dany sklep bedzie otwarty w niedziele:
       
     
      Kolor       rodzaj    * Czy otwarty * 
      sklepu      sklepu    * w niedziele *
                                       
X1  niebieski    spozywczy       Tak
X2  niebieski    spozywczy       Tak
X3  zielony      RTV             Nie
X4  zielony      spozywczy       Tak
X5  zolty        spozywczy       Nie


a) utworzyc drzewo decyzyjne:
   
                rodzaj sklepu
                   /   \
                  /     \
              spozywczy RTV
                /         \
             kolor       NIE
            /  |  \
           /   |   \
          /    |    \
 niebieski  zielony zolty
        /      |      \
      TAK     TAK     NIE

b) Wartosci brakujace: jak sprawdzic w tym przypadku czy otwarty bedzie pewien sklep spozywczy A, gdy nie znamy jego koloru?

Przejrzec sciezki dla wszystkich kolorow, zsumowac rozklady (w zbiorze treningowym) ze wszystkich otrzymanych lisci, i wybrac najczestsza decyzje, w tym przypadku bedzie to zalozenie, ze sie zachowa jak wiekszosc sklepow spozywczych w zbiorze treningowym, czyli ze bedzie otwarty.


c) Przycinanie: sprawdz drzewo zbiorem walidacyjnym i przytnij poddrzewa, ktore nie poprawiaja skutecznosci w zbiorze walidacyjnym

Y1  niebieski     spozywczy  Nie
Y2  zielony       spozywczy  Tak
Y3  zolty         spozywczy  Tak
Y4  niebieski     RTV        Nie

Wychodzi na to, ze sprawdzanie koloru nie tylko nic nie daje, ale wrecz psuje. Nalezy skrocic drzewo:


                rodzaj sklepu
                   /   \
                  /     \
              spozywczy RTV
                /         \
              TAK         NIE

Na koniec trzeba sprawdzic, czy nie mozna zredukowac drzewa calkowicie.