Toggle navigation

• Projekt Jupyter
• Návody
• Stiahnuť
• Prihlásiť sa na test
• Prihlásiť sa

1. Data Lab
2. ZSU
3. cv04_ID3.ipynb

Toto je statické zobrazenie, ak chcete Notebook spustiť, prihláste sa do prostredia Data Lab.

ID3 Decision Tree Algorithm - Student Assignment

Total Points: 8 (4 parts × 2 points each)

---

ID3 Pseudokód

ID3(examples, target_attribute, attributes):
    1. Vytvoriť koreňový uzol
    
    2. Ak majú všetky záznamy v uzli rovnakú triedu:
       - Vrátiť listový uzol s názvom danej triedy
    
    3. Ak sme prešli všetky attributes:
       - Vrátiť listový uzol s názvom početnejšej triedy
    
    4. Inak:
       a) Vybrať najlepší atribút "A" pomoocu informačného zisku "Gain(S, A)":
          - Vypočítať pre každý atribút: Gain(S, A) = Entropy(S) - Σ (|Sv|/|S|) × Entropy(Sv)
          - Vybrať atribút s najvyšším informačným ziskom
       
       b) Nastaviť "A" ako rozhodovací atribút pre aktuálny uzol
       
       c) Pre každú hodnotu "v" atribútu "A":
          - Vytvoriť novú vetvu s pre záznamy kde A = v
          - examples_v = podmnožina záznamov, kde A = v
          - Ak je examples_v prázdne:
              - Vrátiť listový uzol s názvom početnejšej triedy
          - Inak:
              - Opakovať výpočet algoritmu: ID3(examples_v, target_attribute, attributes - {A})
    
    5. Vrátiť koreňový uzol (return root)

Entropy(S) = - Σ p_i × log2(p_i)
    kde "p_i" je pomer triedy "i" v datasete "S"

---

Setup - Required Imports

import math
import pandas as pd
from collections import Counter
from typing import Dict, List, Any, Union

Load Dataset

# Test dataset - Play Tennis
data = [
    {"Outlook": "Sunny", "Temperature": "Hot", "Humidity": "High", "Wind": "Weak", "PlayTennis": "No"},
    {"Outlook": "Sunny", "Temperature": "Hot", "Humidity": "High", "Wind": "Strong", "PlayTennis": "No"},
    {"Outlook": "Overcast", "Temperature": "Hot", "Humidity": "High", "Wind": "Weak", "PlayTennis": "Yes"},
    {"Outlook": "Rain", "Temperature": "Mild", "Humidity": "High", "Wind": "Weak", "PlayTennis": "Yes"},
    {"Outlook": "Rain", "Temperature": "Cool", "Humidity": "Normal", "Wind": "Weak", "PlayTennis": "Yes"},
    {"Outlook": "Rain", "Temperature": "Cool", "Humidity": "Normal", "Wind": "Strong", "PlayTennis": "No"},
    {"Outlook": "Overcast", "Temperature": "Cool", "Humidity": "Normal", "Wind": "Strong", "PlayTennis": "Yes"},
    {"Outlook": "Sunny", "Temperature": "Mild", "Humidity": "High", "Wind": "Weak", "PlayTennis": "No"},
    {"Outlook": "Sunny", "Temperature": "Cool", "Humidity": "Normal", "Wind": "Weak", "PlayTennis": "Yes"},
    {"Outlook": "Rain", "Temperature": "Mild", "Humidity": "Normal", "Wind": "Weak", "PlayTennis": "Yes"},
    {"Outlook": "Sunny", "Temperature": "Mild", "Humidity": "Normal", "Wind": "Strong", "PlayTennis": "Yes"},
    {"Outlook": "Overcast", "Temperature": "Mild", "Humidity": "High", "Wind": "Strong", "PlayTennis": "Yes"},
    {"Outlook": "Overcast", "Temperature": "Hot", "Humidity": "Normal", "Wind": "Weak", "PlayTennis": "Yes"},
    {"Outlook": "Rain", "Temperature": "Mild", "Humidity": "High", "Wind": "Strong", "PlayTennis": "No"}
]
df = pd.DataFrame(data)

# Define attributes and target
attributes = [attr for attr in list(df.columns) if attr != "PlayTennis"]
target = "PlayTennis"

print(f"Dataset size: {len(df)} samples")
print(f"Attributes: {attributes}")
print(f"Target: {target}")

---

Part 1: Calculate Entropy (2 points)

Implementujte funkciu, ktorá vypočíta hodnotu entrópie vo vstupnom datasete.

Vzorec: $H(S) = -\sum_{i=1}^{c} p_i \cdot \log_2(p_i)$

Premenné:

• $H(S)$ - entrópia datasetu $S$
• $c$ - počet tried v cieľovom atribúte
• $p_i$ - pomer záznamov patriacich do triedy $i$ (i.e., $p_i = \frac{|S_i|}{|S|}$)
• $|S|$ - celkový počet záznamov v datasete $S$

Vstupy:

• dataset: Vstupne dáta, dané ako pandas dataframe
• labels: Zoznam tried cieľového atribútu, daný ako list obsahujúci reťazce (strings)

Požadovaný výstup:

• entropy: Hodnota entrópie

Hint: Použite math.log2() pre výpočet logaritmu.

def calculate_entropy(labels: List[str]) -> float:
    # Sample return value: 0.9709505944546686
    """
    Calculate the entropy of a list of labels.
    
    Args:
        dataset: pd.DataFrame - the data for which to calculate entropy
        labels: List of class labels
    
    Returns:
        entropy: float - The entropy value
    """
    entropy = 0.0
    c = len(labels)
    S_count = len(labels)
    
    for i in set(labels):
        Si_count = labels.count(i)
    
    # TODO: Implementovať zvyšok výpočtu entrópie
    
    return entropy

---

Part 2: Calculate Information Gain (2 points)

Implementujte funkciu, ktorá vypočíta informačný zisk pre daný atribút.

Vzorec: $Gain(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} \cdot H(S_v)$

Premenné:

• $Gain(S, A)$ - informačný zisk atribútu $A$ v datasete $S$
• $H(S)$ - entrópia celého datasetu $S$
• $A$ - atribút, ktorý vyhodnocujeme
• $Values(A)$ - všetky unikátne hodnoty atribútu $A$
• $v$ - jedna konkrétna hodnota atribútu $A$
• $S_v$ - podmnožina datasetu $S$, kde atribút $A$ má hodnotu $v$
• $|S_v|$ - počet záznamov v podmnožine $S_v$
• $|S|$ - celkový počet záznamov v datasete $S$
• $H(S_v)$ - entrópia podmnožiny $S_v$

Vstupy:

• dataset: Vstupné dáta, dané ako pandas dataframe
• attribute: Názov atribútu (string), pre ktorý počítame informačný zisk
• target: Názov cieľového atribútu (string)

Výstup:

• gain: Hodnota informačného zisku

Hint: Použite funkciu calculate_entropy() z predošlej úlohy.

def calculate_information_gain(dataset: pd.DataFrame, attribute: str, target: str) -> float:
    # Sample return value: 0.2467498197744391
    """
    Calculate the information gain for a given attribute.
    
    Args:
        dataset: pd.DataFrame - the data to use in gain calculation
        attribute: The attribute to calculate gain for
        target: The target attribute (class label)
    
    Returns:
        gain: float - The information gain value
    """
    gain = 0.0
    values_a = dataset[attribute].unique().tolist()
    S_labels = dataset[target].tolist()
    
    for v in values_a:
        Sv = dataset[dataset[attribute] == v]
        Sv_labels = Sv[target].tolist()
    
    # TODO: Implementovať zvyšok výpočtu informačného zisku
    
    return gain

---

Part 3: Find Best Attribute (2 points)

Implementujte funkciu, ktorá vráti názov atribútu s najvyšším informačným ziskom.

Vstupy:

• dataset: Vstupné dáta, dané ako pandas dataframe
• attributes: Zoznam názvov atribútov, pre ktoré počítame informačný zisk
• target: Názov cieľového atribútu

Vystup:

• best_attribute: Názov atribútu s najvyšším informačným ziskom

Hint: Použite funkciu calculate_information_gain() z predošlej úlohy.

def find_best_attribute(dataset: pd.DataFrame, attributes: List[str], target: str) -> str:
    # Sample return value: "Outlook"
    """
    Find the attribute with the highest information gain.
    
    Args:
        dataset: pd.DataFrame
        attributes: List of attribute names to consider
        target: The target attribute (class label)
    
    Returns:
        best_attribute: str - The name of the best attribute
    """
    best_attribute = None
    
    # TODO: Implement finding the best attribute
    
    return best_attribute

---

Part 4: Build Decision Tree - ID3 Algorithm (2 points)

Implementujte ID3 algoritmus pre rekurzívne zostavenie rozhodovacieho stromu.

Vstupy:

• dataset: Vstupné dáta, dané ako pandas dataframe
• attributes: Zoznam názvov atribútov
• target: Názov cieľového atribútu

Výstup:

• tree: Vnorený slovník (dictionary), ktorý reprezentuje rozhodovací strom

Požadovaná štruktúra stromu:

• Listový uzol: {"label": <názov_triedy>}
• Rozhodovací uzol: {"attribute": <názov_atribútu>, "children": {<hodnota1>: <podstrom>, <hodnota2>: <podstrom>, ...}}

Hint: Využite pseudokód, ktorý popisuje chod algoritmu na začiatku tohto notebooku. Použite rekurziu a funkcie, ktoré ste definovali v predošlých úlohách.

def build_tree(dataset: pd.DataFrame, attributes: List[str], target: str) -> Dict:
    # Sample return value:
    # {"attribute": "Outlook", "children": {
    #     "Sunny": {"attribute": "Humidity", "children": {"High": {"label": "No"}, "Normal": {"label": "Yes"}}},
    #     "Overcast": {"label": "Yes"},
    #     "Rain": {"attribute": "Wind", "children": {"Weak": {"label": "Yes"}, "Strong": {"label": "No"}}}
    # }}
    """
    Build a decision tree using the ID3 algorithm.
    
    Args:
        dataset: pd.DataFrame
        attributes: List of available attribute names
        target: The target attribute (class label)
    
    Returns:
        tree: Dict - A nested dictionary representing the decision tree
    """

    tree = {}    

    # TODO: Implementovať ID3 algoritmus

    return tree

---

Testing

V tejto časti môžete testovať svoje implementácie funkcií na datasete uloženom v premennej data. Cieľom je predikovať, či sa na základe daného počasia bude hrať tenis (Play Tennis).

# Test Part 1: Entropy
test_labels = ["Yes", "Yes", "Yes", "Yes", "Yes", "No", "No", "No", "No"]
entropy_result = calculate_entropy(test_labels)
print(f"Part 1 - Entropy of {test_labels}:")
print(f"Your result: {entropy_result:.4f}")
print(f"Expected: ~0.9911")
print()

# Test Part 2: Information Gain
gain_outlook = calculate_information_gain(df, "Outlook", target)
print(f"Part 2 - Information Gain for 'Outlook': {gain_outlook:.4f}")
print(f"Expected: ~0.2467")
print()

# Test Part 3: Best Attribute
best = find_best_attribute(df, attributes, target)
print(f"Part 3 - Best attribute: {best}")
print(f"Expected: Outlook")
print()

# Test Part 4: Build Decision Tree
tree = build_tree(df, attributes, target)
print("Part 4 - Decision Tree:")
print(tree)
print()

---

© 2020-2025 KKUI