Binární rozhodovací strom – informační zisk
A) Zadání
- Zkonstruujte binární rozhodovací strom tak, aby modeloval funkční
závislost y=f(x) danou tabulkou pod textem:
• Vstupní atributy jsou {x1, x2, x3, x4}.
• Výstupní klasifikační atribut tvoří funkce y(x), jejíž hodnoty do tabulky doplňte rozkladem vašeho student ID v binární soustavě, přičemž vzhledem k počtu řádků tabulky použijte pouze 16 posledních bitů (v horním řádku tabulky je MSB, v dolním pak LSB).
• Maximální hloubka stromu Dmax = 3.
- Konstrukci stromu proveďte na základě informačního zisku, tj. výpočtem podmíněných entropií. Technicky využijte libovolný nástroj – doporučený je papír a tužka.
- Do předloženého formuláře doplňte následující hodnoty:
• Vaše ID a jeho posledních 16 bitů v binární soustavě.
• Dělicí atribut {x1, x2, x3, x4} a hodnotu podmíněné entropie H(S|xi) vybraného atributu vepište vždy k odpovídajícímu uzlu namísto symbolického textu (hodnota 0 atributu koresponduje vždy s levou větví uzlu, hodnota 1 s pravou); nevyužité uzly ponechte prázdné.
• V případě shodné hodnoty podmíněné entropie u dvou či více atributů volte vždy ten v pořadí první podle indexu.
• Hodnotu klasifikační chyby MisclassRate v % vypočtenou z hodnot špatně (zde FP) a správně (zde TP) klasifikovaných záznamů trénovací množiny (tabulky).
• Skutečně dosaženou hloubku stromu Dvalid ≤ Dmax.
B) Info
Tabulka funkční závislosti y=f(x):
| x1 | x2 | x3 | x4 | y(x) |
| 0 | 0 | 0 | 0 | MSB(ID_16) |
| 0 | 0 | 0 | 1 | … |
| 0 | 0 | 1 | 0 | … |
| 0 | 0 | 1 | 1 | … |
| 0 | 1 | 0 | 0 | … |
| 0 | 1 | 0 | 1 | … |
| 0 | 1 | 1 | 0 | … |
| 0 | 1 | 1 | 1 | … |
| 1 | 0 | 0 | 0 | … |
| 1 | 0 | 0 | 1 | … |
| 1 | 0 | 1 | 0 | … |
| 1 | 0 | 1 | 1 | … |
| 1 | 1 | 0 | 0 | … |
| 1 | 1 | 0 | 1 | … |
| 1 | 1 | 1 | 0 | … |
| 1 | 1 | 1 | 1 | LSB(ID_16) |