id3

import math

import pandas as pd


def entropy(data):
    """
    Calculate the entropy of a dataset.
    Assumes the last column contains the labels.
    """

    labels = data.iloc[:, -1]
    total = len(labels)


    counts = labels.value_counts()


    entropy_value = 0
    for count in counts:
        prob = count / total
        entropy_value -= prob * math.log2(prob)

    return entropy_value
def info_gain(data, feature):



    total_entropy = entropy(data)


    values = data[feature].unique()


    weighted_entropy = 0
    for value in values:
        subset = data[data[feature] == value]
        weighted_entropy += (len(subset) / len(data)) * entropy(subset)


    return total_entropy - weighted_entropy
def id3(data):


    labels = data.iloc[:, -1]


    if len(labels.unique()) == 1:
        return labels.iloc[0]


    best_feature = max(data.columns[:-1], key=lambda f: info_gain(data, f))


    tree = {best_feature: {}}


    for value in data[best_feature].unique():

        subset = data[data[best_feature] == value].drop(columns=[best_feature])


        tree[best_feature][value] = id3(subset)

    return tree
def predict(tree, instance):


    if not isinstance(tree, dict):
        return tree


    feature = next(iter(tree))

    value = instance.get(feature)


    if value not in tree[feature]:
        return "Unknown value for feature '{}': {}".format(feature, value)


    return predict(tree[feature][value], instance)
def predict(tree, instance):


    if not isinstance(tree, dict):
        return tree


    feature = next(iter(tree))

    value = instance.get(feature)


    if value not in tree[feature]:
        return "Unknown value for feature '{}': {}".format(feature, value)


    return predict(tree[feature][value], instance)
    
    
    tree = id3(data)

    print("Decision Tree:", tree)

    new_sample = {'Outlook': 'Sunny', 'Temperature': 'Cool', 'Humidity': 'High', 'Wind': 'Strong'}

    prediction = predict(tree, new_sample)

    print("Prediction for new sample:", prediction)