3. ID3.ipynb

{
  "metadata": {
    "language_info": {
      "codemirror_mode": {
        "name": "python",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.8"
    },
    "kernelspec": {
      "name": "python",
      "display_name": "Python (Pyodide)",
      "language": "python"
    }
  },
  "nbformat_minor": 4,
  "nbformat": 4,
  "cells": [
    {
      "cell_type": "code",
      "source": "import math\n\n\ndef load_dataset(filename):\n    with open(filename, 'r') as file:\n        lines = file.readlines()\n        dataset = [line.strip().split(',') for line in lines]\n        attributes = dataset[0][1:]  # Extract attribute names from the first row\n        dataset = dataset[1:]  # Remove the first row (attribute names)\n        return dataset, attributes\n\n\ndef create_tree(data, attributes):\n    class_labels = [instance[-1] for instance in data]\n    if len(set(class_labels)) == 1:\n        return class_labels[0]\n    if len(attributes) == 0:\n        majority_class = get_majority_class(class_labels)\n        return majority_class\n    best_attribute = select_best_attribute(data, attributes)\n    tree = {best_attribute: {}}\n    attribute_values = get_attribute_values(data, best_attribute)\n    for value in attribute_values:\n        subset = get_instances_with_attribute_value(data, best_attribute, value)\n        subset_attributes = attributes[:]\n        subset_attributes.remove(best_attribute)\n        tree[best_attribute][value] = create_tree(subset, subset_attributes)\n    return tree\n\n\ndef select_best_attribute(data, attributes):\n    best_attribute = None\n    best_information_gain = -1.0\n    for attribute in attributes:\n        attribute_values = get_attribute_values(data, attribute)\n        subset_entropy = 0.0\n        for value in attribute_values:\n            subset = get_instances_with_attribute_value(data, attribute, value)\n            subset_probability = len(subset) / float(len(data))\n            subset_entropy += subset_probability * calculate_entropy(subset)\n        information_gain = calculate_entropy(data) - subset_entropy\n        if information_gain > best_information_gain:\n            best_information_gain = information_gain\n            best_attribute = attribute\n    return best_attribute\n\n\ndef get_attribute_values(data, attribute):\n    attribute_index = -1\n    for i in range(len(data[0])):\n        if data[0][i] == attribute:\n            attribute_index = i\n            break\n    attribute_values = []\n    for instance in data[1:]:\n        attribute_values.append(instance[attribute_index])\n    return list(set(attribute_values))\n\n\ndef get_instances_with_attribute_value(data, attribute, value):\n    attribute_index = -1\n    for i in range(len(data[0])):\n        if data[0][i] == attribute:\n            attribute_index = i\n            break\n    instances = []\n    for instance in data[1:]:\n        if instance[attribute_index] == value:\n            instances.append(instance)\n    return instances\n\n\ndef calculate_entropy(data):\n    class_labels = [instance[-1] for instance in data]\n    label_counts = count_class_labels(class_labels)\n    entropy = 0.0\n    for count in label_counts.values():\n        probability = count / len(data)\n        entropy -= probability * math.log2(probability)\n    return entropy\n\n\ndef count_class_labels(class_labels):\n    label_counts = {}\n    for label in class_labels:\n        if label in label_counts:\n            label_counts[label] += 1\n        else:\n            label_counts[label] = 1\n    return label_counts\n\n\ndef get_majority_class(class_labels):\n    label_counts = count_class_labels(class_labels)\n    majority_class = max(label_counts, key=label_counts.get)\n    return majority_class\n\n\n# Load the dataset\ndataset, attributes = load_dataset('student-mat.csv')\n\n# Build the ID3 decision tree\ntree = create_tree(dataset, attributes)\n\n# Print the tree\nprint(tree)\n",
      "metadata": {
        "trusted": true
      },
      "execution_count": 20,
      "outputs": [
        {
          "name": "stdout",
          "text": "{'sex': {'19': '19', '18': '18', '11': '11', '10': '10', '13': '13', '12': '12', '15': '15', '14': '14', '17': '17', '16': '16', '0': '0', '5': '5', '20': '20', '7': '7', '6': '6', '9': '9', '8': '8', '4': '4'}}\n",
          "output_type": "stream"
        }
      ]
    },
    {
      "cell_type": "code",
      "source": "import math\n\n\ndef load_dataset(filename):\n    with open(filename, 'r') as file:\n        lines = file.readlines()\n        dataset = [line.strip().split(',') for line in lines]\n        attributes = dataset[0][1:]  # Extract attribute names from the first row\n        dataset = dataset[1:]  # Remove the first row (attribute names)\n        return dataset, attributes\n\n\ndef create_tree(data, attributes):\n    class_labels = [instance[-1] for instance in data]\n    if len(set(class_labels)) == 1:\n        return class_labels[0]\n    if len(attributes) == 0:\n        majority_class = get_majority_class(class_labels)\n        return majority_class\n    best_attribute = select_best_attribute(data, attributes)\n    tree = {best_attribute: {}}\n    attribute_values = get_attribute_values(data, best_attribute)\n    for value in attribute_values:\n        subset = get_instances_with_attribute_value(data, best_attribute, value)\n        subset_attributes = attributes[:]\n        subset_attributes.remove(best_attribute)\n        tree[best_attribute][value] = create_tree(subset, subset_attributes)\n    return tree\n\n\ndef select_best_attribute(data, attributes):\n    best_attribute = None\n    best_information_gain = -1.0\n    for attribute in attributes:\n        attribute_values = get_attribute_values(data, attribute)\n        subset_entropy = 0.0\n        for value in attribute_values:\n            subset = get_instances_with_attribute_value(data, attribute, value)\n            subset_probability = len(subset) / float(len(data))\n            subset_entropy += subset_probability * calculate_entropy(subset)\n        information_gain = calculate_entropy(data) - subset_entropy\n        if information_gain > best_information_gain:\n            best_information_gain = information_gain\n            best_attribute = attribute\n    return best_attribute\n\n\ndef get_attribute_values(data, attribute):\n    attribute_index = -1\n    for i in range(len(data[0])):\n        if data[0][i] == attribute:\n            attribute_index = i\n            break\n    attribute_values = []\n    for instance in data[1:]:\n        attribute_values.append(instance[attribute_index])\n    return list(set(attribute_values))\n\n\ndef get_instances_with_attribute_value(data, attribute, value):\n    attribute_index = -1\n    for i in range(len(data[0])):\n        if data[0][i] == attribute:\n            attribute_index = i\n            break\n    instances = []\n    for instance in data[1:]:\n        if instance[attribute_index] == value:\n            instances.append(instance)\n    return instances\n\n\ndef calculate_entropy(data):\n    class_labels = [instance[-1] for instance in data]\n    label_counts = count_class_labels(class_labels)\n    entropy = 0.0\n    for count in label_counts.values():\n        probability = count / len(data)\n        entropy -= probability * math.log2(probability)\n    return entropy\n\n\ndef count_class_labels(class_labels):\n    label_counts = {}\n    for label in class_labels:\n        if label in label_counts:\n            label_counts[label] += 1\n        else:\n            label_counts[label] = 1\n    return label_counts\n\n\ndef get_majority_class(class_labels):\n    label_counts = count_class_labels(class_labels)\n    majority_class = max(label_counts, key=label_counts.get)\n    return majority_class\n\n\n# Load the dataset\ndataset, attributes = load_dataset('StudentsPerformance.csv')\n\n# Build the ID3 decision tree\ntree = create_tree(dataset, attributes)\n\n# Print the tree\nprint(tree)\n",
      "metadata": {
        "trusted": true
      },
      "execution_count": 3,
      "outputs": [
        {
          "name": "stdout",
          "text": "{'\"race/ethnicity\"': {'\"95\"': '\"95\"', '\"42\"': '\"42\"', '\"81\"': '\"81\"', '\"73\"': '\"73\"', '\"22\"': '\"22\"', '\"78\"': '\"78\"', '\"55\"': '\"55\"', '\"65\"': '\"65\"', '\"89\"': '\"89\"', '\"30\"': '\"30\"', '\"96\"': '\"96\"', '\"49\"': '\"49\"', '\"38\"': '\"38\"', '\"41\"': '\"41\"', '\"80\"': '\"80\"', '\"70\"': '\"70\"', '\"79\"': '\"79\"', '\"56\"': '\"56\"', '\"88\"': '\"88\"', '\"97\"': '\"97\"', '\"48\"': '\"48\"', '\"39\"': '\"39\"', '\"64\"': '\"64\"', '\"40\"': '\"40\"', '\"15\"': '\"15\"', '\"87\"': '\"87\"', '\"71\"': '\"71\"', '\"47\"': '\"47\"', '\"76\"': '\"76\"', '\"57\"': '\"57\"', '\"36\"': '\"36\"', '\"86\"': '\"86\"', '\"98\"': '\"98\"', '\"90\"': '\"90\"', '\"67\"': '\"67\"', '\"37\"': '\"37\"', '\"46\"': '\"46\"', '\"50\"': '\"50\"', '\"77\"': '\"77\"', '\"27\"': '\"27\"', '\"58\"': '\"58\"', '\"85\"': '\"85\"', '\"99\"': '\"99\"', '\"66\"': '\"66\"', '\"91\"': '\"91\"', '\"61\"': '\"61\"', '\"34\"': '\"34\"', '\"10\"': '\"10\"', '\"45\"': '\"45\"', '\"84\"': '\"84\"', '\"59\"': '\"59\"', '\"74\"': '\"74\"', '\"51\"': '\"51\"', '\"69\"': '\"69\"', '\"92\"': '\"92\"', '\"35\"': '\"35\"', '\"60\"': '\"60\"', '\"44\"': '\"44\"', '\"19\"': '\"19\"', '\"83\"': '\"83\"', '\"75\"': '\"75\"', '\"52\"': '\"52\"', '\"93\"': '\"93\"', '\"68\"': '\"68\"', '\"63\"': '\"63\"', '\"43\"': '\"43\"', '\"32\"': '\"32\"', '\"100\"': '\"100\"', '\"72\"': '\"72\"', '\"53\"': '\"53\"', '\"82\"': '\"82\"', '\"28\"': '\"28\"', '\"94\"': '\"94\"', '\"54\"': '\"54\"', '\"23\"': '\"23\"', '\"62\"': '\"62\"', '\"33\"': '\"33\"'}}\n",
          "output_type": "stream"
        }
      ]
    },
    {
      "cell_type": "code",
      "source": "import math\n\n\ndef load_dataset(filename):\n    with open(filename, 'r') as file:\n        lines = file.readlines()\n        dataset = [line.strip().split(',') for line in lines]\n        attributes = dataset[0][:-1]  # Extract attribute names from the first row\n        dataset = dataset[1:]  # Remove the first row (attribute names)\n        return dataset, attributes\n\n\ndef create_tree(data, attributes):\n    class_labels = [instance[-1] for instance in data]\n    if len(set(class_labels)) == 1:\n        return class_labels[0]\n    if len(attributes) == 0:\n        majority_class = get_majority_class(class_labels)\n        return majority_class\n    best_attribute, ranked_attributes = select_best_attribute(data, attributes)\n    tree = {best_attribute: {}}\n    for value in ranked_attributes:\n        subset = get_instances_with_attribute_value(data, best_attribute, value)\n        subset_attributes = attributes[:]\n        subset_attributes.remove(best_attribute)\n        tree[best_attribute][value] = create_tree(subset, subset_attributes)\n    return tree\n\n\ndef select_best_attribute(data, attributes):\n    best_attribute = None\n    best_information_gain = -1.0\n    ranked_attributes = []\n    for attribute in attributes:\n        attribute_values = get_attribute_values(data, attribute)\n        subset_entropy = 0.0\n        for value in attribute_values:\n            subset = get_instances_with_attribute_value(data, attribute, value)\n            subset_probability = len(subset) / float(len(data))\n            subset_entropy += subset_probability * calculate_entropy(subset)\n        information_gain = calculate_entropy(data) - subset_entropy\n        ranked_attributes.append((attribute, information_gain))\n    ranked_attributes.sort(key=lambda x: x[1], reverse=True)\n    return ranked_attributes[0][0], [attr[0] for attr in ranked_attributes]\n\n\ndef get_attribute_values(data, attribute):\n    attribute_index = attributes.index(attribute)\n    attribute_values = []\n    for instance in data:\n        attribute_values.append(instance[attribute_index])\n    return list(set(attribute_values))\n\n\ndef get_instances_with_attribute_value(data, attribute, value):\n    attribute_index = attributes.index(attribute)\n    instances = []\n    for instance in data:\n        if instance[attribute_index] == value:\n            instances.append(instance)\n    return instances\n\n\ndef calculate_entropy(data):\n    class_labels = [instance[-1] for instance in data]\n    label_counts = count_class_labels(class_labels)\n    entropy = 0.0\n    for count in label_counts.values():\n        probability = count / len(data)\n        entropy -= probability * math.log2(probability)\n    return entropy\n\n\ndef count_class_labels(class_labels):\n    label_counts = {}\n    for label in class_labels:\n        if label in label_counts:\n            label_counts[label] += 1\n        else:\n            label_counts[label] = 1\n    return label_counts\n\n\ndef get_majority_class(class_labels):\n    if len(class_labels) == 0:\n        return None\n    label_counts = count_class_labels(class_labels)\n    majority_class = max(label_counts, key=label_counts.get)\n    return majority_class\n\n# Load the dataset\ndataset, attributes = load_dataset('iris.csv')\n\n# Build the ID3 decision tree\ntree = create_tree(dataset, attributes)\n\n# Print the tree\nprint(tree)\n",
      "metadata": {
        "trusted": true
      },
      "execution_count": 2,
      "outputs": [
        {
          "name": "stdout",
          "text": "{'sepal_length': {'sepal_length': {'petal_length': {'petal_length': {'petal_width': {'petal_width': {'sepal_width': {'sepal_width': None}}, 'sepal_width': {'sepal_width': {'sepal_width': None}}}}, 'petal_width': {'petal_width': {'petal_width': {'sepal_width': {'sepal_width': None}}, 'sepal_width': {'sepal_width': {'sepal_width': None}}}}, 'sepal_width': {'petal_width': {'petal_width': {'sepal_width': {'sepal_width': None}}, 'sepal_width': {'sepal_width': {'sepal_width': None}}}}}}, 'sepal_width': {'petal_length': {'petal_length': {'petal_width': {'petal_width': {'sepal_width': {'sepal_width': None}}, 'sepal_width': {'sepal_width': {'sepal_width': None}}}}, 'petal_width': {'petal_width': {'petal_width': {'sepal_width': {'sepal_width': None}}, 'sepal_width': {'sepal_width': {'sepal_width': None}}}}, 'sepal_width': {'petal_width': {'petal_width': {'sepal_width': {'sepal_width': None}}, 'sepal_width': {'sepal_width': {'sepal_width': None}}}}}}, 'petal_length': {'petal_length': {'petal_length': {'petal_width': {'petal_width': {'sepal_width': {'sepal_width': None}}, 'sepal_width': {'sepal_width': {'sepal_width': None}}}}, 'petal_width': {'petal_width': {'petal_width': {'sepal_width': {'sepal_width': None}}, 'sepal_width': {'sepal_width': {'sepal_width': None}}}}, 'sepal_width': {'petal_width': {'petal_width': {'sepal_width': {'sepal_width': None}}, 'sepal_width': {'sepal_width': {'sepal_width': None}}}}}}, 'petal_width': {'petal_length': {'petal_length': {'petal_width': {'petal_width': {'sepal_width': {'sepal_width': None}}, 'sepal_width': {'sepal_width': {'sepal_width': None}}}}, 'petal_width': {'petal_width': {'petal_width': {'sepal_width': {'sepal_width': None}}, 'sepal_width': {'sepal_width': {'sepal_width': None}}}}, 'sepal_width': {'petal_width': {'petal_width': {'sepal_width': {'sepal_width': None}}, 'sepal_width': {'sepal_width': {'sepal_width': None}}}}}}}}\n",
          "output_type": "stream"
        }
      ]
    },
    {
      "cell_type": "code",
      "source": "",
      "metadata": {},
      "execution_count": null,
      "outputs": []
    }
  ]
}