Decision_tree_training_with_data.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Decision_tree_training_with_data.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyMHSm/vWq6XA7XcBwVEVqoD",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/tutr464b/Decision-tree/blob/main/Decision_tree_training_with_data.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "v2PHLXnwxuzY",
        "outputId": "3cd02ae2-8bbd-448d-b80d-a4e77e208cb2"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "--2021-12-08 16:02:13--  https://cloudstore.zih.tu-dresden.de/index.php/s/gxBP63LNy9SgNFD/download\n",
            "Resolving cloudstore.zih.tu-dresden.de (cloudstore.zih.tu-dresden.de)... 141.30.62.64\n",
            "Connecting to cloudstore.zih.tu-dresden.de (cloudstore.zih.tu-dresden.de)|141.30.62.64|:443... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 3974305 (3.8M) [text/plain]\n",
            "Saving to: ‘adult.data.txt’\n",
            "\n",
            "adult.data.txt      100%[===================>]   3.79M  --.-KB/s    in 0.1s    \n",
            "\n",
            "2021-12-08 16:02:14 (26.4 MB/s) - ‘adult.data.txt’ saved [3974305/3974305]\n",
            "\n",
            "--2021-12-08 16:02:14--  https://cloudstore.zih.tu-dresden.de/index.php/s/yw5ayzYk9g2bc3p/download\n",
            "Resolving cloudstore.zih.tu-dresden.de (cloudstore.zih.tu-dresden.de)... 141.30.62.64\n",
            "Connecting to cloudstore.zih.tu-dresden.de (cloudstore.zih.tu-dresden.de)|141.30.62.64|:443... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 2003153 (1.9M) [text/plain]\n",
            "Saving to: ‘adult.test.txt’\n",
            "\n",
            "adult.test.txt      100%[===================>]   1.91M  --.-KB/s    in 0.1s    \n",
            "\n",
            "2021-12-08 16:02:14 (16.2 MB/s) - ‘adult.test.txt’ saved [2003153/2003153]\n",
            "\n"
          ]
        }
      ],
      "source": [
        "!wget https://cloudstore.zih.tu-dresden.de/index.php/s/gxBP63LNy9SgNFD/download -O adult.data.txt\n",
        "!wget https://cloudstore.zih.tu-dresden.de/index.php/s/yw5ayzYk9g2bc3p/download -O adult.test.txt"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "#data from TU Dresden\n"
      ],
      "metadata": {
        "id": "dHXnMTKEx_1L"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!ls"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "KM0tRpabyDBr",
        "outputId": "2247c88d-92a5-464a-efcd-cd2c48fa115a"
      },
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "adult.data.txt\tadult.test.txt\tsample_data\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import numpy as np\n",
        "from math import log"
      ],
      "metadata": {
        "id": "UUXnksCLyFcz"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def openfile(path, fname):\n",
        "    \"\"\"opens the file at path+fname and returns a list of examples and attribute values.\n",
        "    examples are returned as a list with one entry per example. Each entry then\n",
        "    is a list of attribute values, one of them being the class label. The returned list attr\n",
        "    contains one entry per attribute. Each entry is a list of possible values or an empty list\n",
        "    for numeric attributes.\n",
        "    \"\"\"\n",
        "    datafile = open(path + fname, \"r\")\n",
        "    examples = []\n",
        "    for line in datafile:\n",
        "        line = line.strip()\n",
        "        line = line.strip('.')\n",
        "        # ignore empty lines. comments are marked with a |\n",
        "        if len(line) == 0 or line[0] == '|':\n",
        "            continue\n",
        "        ex = [x.strip() for x in line.split(\",\")]\n",
        "        examples.append(ex)\n",
        "    attr = []\n",
        "    for i in range(len(examples[0])):\n",
        "        values = list({x[i] for x in examples})  # set of all different attribute values\n",
        "        if values[0].isdigit():  # if the first value is a digit, assume all are numeric\n",
        "            attr.append([])\n",
        "        else:\n",
        "            attr.append(values)\n",
        "\n",
        "    return examples, attr"
      ],
      "metadata": {
        "id": "9fcQipq4yNsW"
      },
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def calc_entropy(examples, cls_index):\n",
        "    \"\"\"calculates the entropy over all examples. The index of the class label in the example\n",
        "    is given by cls_index. Can also be the index to an attribute.\n",
        "    \"\"\"\n",
        "    global attr\n",
        "    # get attributes of examples with index cls_index\n",
        "    example_classifications = [example[cls_index] for example in examples]\n",
        "    # get unique counts of example_attributes\n",
        "    unique, counts = np.unique(example_classifications, return_counts=True)\n",
        "\n",
        "    # normalize counts to total number of examples for getting probs\n",
        "    probs = counts/len(examples)\n",
        "    # print(probs)\n",
        "\n",
        "    entropy = -np.sum(probs*np.log2(probs))\n",
        "\n",
        "    return entropy"
      ],
      "metadata": {
        "id": "SqBNll8QyPkl"
      },
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def calc_ig(examples, attr_index, cls_index):\n",
        "    \"\"\"Calculates the information gain over all examples for a specific attribute. The\n",
        "    class index must be specified.\n",
        "\n",
        "    uses calc_entropy\n",
        "    \"\"\"\n",
        "    global attr\n",
        "    # get attributes of examples with index attr_indx\n",
        "    example_attributes = [example[attr_index] for example in examples]\n",
        "\n",
        "    # get unique counts of example_attributes\n",
        "    unique, counts = np.unique(example_attributes, return_counts=True)\n",
        "\n",
        "    # example split\n",
        "    remainder = 0\n",
        "    for j in range(len(unique)):\n",
        "        # get all examples with attribute unique[j]\n",
        "        examples_unique = [example for example in examples if example[attr_index] == unique[j]]\n",
        "        remainder += len(examples_unique)/len(examples)*calc_entropy(examples_unique, cls_index)\n",
        "    return calc_entropy(examples, cls_index) - remainder"
      ],
      "metadata": {
        "id": "ubOSpm5eyRjf"
      },
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def majority(examples, attr_index):\n",
        "    \"\"\"Returns the value of attribute \"attr_index\" that occurs the most often in the examples.\"\"\"\n",
        "    # create a flat list of all attribute values (with duplicates, so we can count)\n",
        "    attr_vals = [example[attr_index] for example in examples]\n",
        "\n",
        "    # among all unique attribute values, find the maximum with regards to occurrence in the attr_vals list\n",
        "\n",
        "    maj_attr_val = max(set(attr_vals), key=attr_vals.count)\n",
        "    return maj_attr_val"
      ],
      "metadata": {
        "id": "aRRWq6TByT7R"
      },
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "def choose_best_attr(examples, attr_avail, cls_index):\n",
        "    \"\"\"Iterates over all available attributes, calculates their information gain and returns the one\n",
        "    that achieves the highest. attr_avail is a list of booleans corresponding to the list of attributes.\n",
        "    it is true if the attribute has not been used in the tree yet (and is not numeric).\n",
        "    \"\"\"\n",
        "    igs = []  # list of information gains for each attribute\n",
        "\n",
        "    for j in range(len(attr)):\n",
        "        if attr_avail[j]:\n",
        "            igs.append(calc_ig(examples, j, cls_index))\n",
        "        else:\n",
        "            igs.append(-1)\n",
        "\n",
        "    return igs.index(max(igs))  # return index of the attribute with highest IG"
      ],
      "metadata": {
        "id": "Lz7y3nJIyV6o"
      },
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def dtree_learning(examples, attr_avail, default, cls_index):\n",
        "  global attr\n",
        "  if len(examples) == 0:\n",
        "    return [None, default]\n",
        "  elif len({x[cls_index] for x in examples}) == 1:\n",
        "    #all the examples are classified in a class\n",
        "    return [None, examples[0][cls_index]]\n",
        "  elif attr_avail.count(True) == 0:\n",
        "    #No more attribute to classify -> majority class prdiction\n",
        "    return [None, majority(examples, cls_index)]\n",
        "  else:\n",
        "    best = choose_best_attr(examples, attr_avail, cls_index)\n",
        "    tree = [best, []]\n",
        "    for v in attr[best]:\n",
        "        examples_v = [x for x in examples if x[best] == v]\n",
        "        # why is it important to make a copy and not change it directly?\n",
        "        new_attr_avail = attr_avail.copy()\n",
        "        new_attr_avail[best] = False\n",
        "        subtree = dtree_learning(examples_v, new_attr_avail, majority(examples, cls_index), cls_index)\n",
        "        tree[1].append(subtree)\n",
        "    return tree"
      ],
      "metadata": {
        "id": "c-lpIsMeycjn"
      },
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def dtree_classify(dtree, x):\n",
        "    \"\"\"Classifies a single example x using the given decision tree. Returns the predicted class label.\n",
        "    \"\"\"\n",
        "    # attribute index of splitting attribute\n",
        "    attr_split_index = dtree[0]\n",
        "\n",
        "    if attr_split_index is not None:\n",
        "        # get attribute value for example\n",
        "        example_split_attr = x[attr_split_index]\n",
        "\n",
        "        # subtree position\n",
        "        subtree_pos = attr[attr_split_index].index(example_split_attr)\n",
        "\n",
        "        return dtree_classify(dtree[1][subtree_pos], x)  # descend into subtree recursively\n",
        "    else:\n",
        "        return dtree[1]"
      ],
      "metadata": {
        "id": "vq61X341z6ZD"
      },
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def dtree_test(dtree, examples, cls_index):\n",
        "    \"\"\"Classify all examples using the given decision tree. Prints the achieved accuracy.\"\"\"\n",
        "    correct = 0\n",
        "    for j in range(len(examples)):\n",
        "        if dtree_classify(dtree, examples[j]) == examples[j][cls_index]:\n",
        "            correct += 1\n",
        "\n",
        "    print(\"{} out of {} correct ({:.2f}%)\".format(correct, len(examples), correct / len(examples) * 100))"
      ],
      "metadata": {
        "id": "elziRUBtz89A"
      },
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "###run the algorithm on real data"
      ],
      "metadata": {
        "id": "ArS4VKze0Cgo"
      },
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "path = \"./\"  # directory of your data\n",
        "datafile = \"adult.data.txt\"\n",
        "testfile = \"adult.test.txt\"\n",
        "examples, attr = openfile(path, datafile)  # load the training set\n",
        "test, test_attr = openfile(path, testfile)  # load the test set\n",
        "cls_index = len(attr) - 1  # the last attribute is assumed to be the class label\n",
        "# attr_names = [\"age\", \"workclass\", \"fnlwgt\", \"education\", \"education-num\", \"marital-status\", \"occupation\", \"relationship\", \"race\", \"sex\", \"capital-gain\", \"capital-loss\", \"hours-per-week\", \"native-country\", \"class\"]\n",
        "\n",
        "attr_avail = []  # marks which attributes are available for splitting (not numeric and not the class label)\n",
        "for i in range(len(attr)):\n",
        "    # the list attr[i] contains all possible values of attribute i. It is empty for numeric attributes.\n",
        "    attr_avail.append(len(attr[i]) > 0 and i != cls_index)\n",
        "\n",
        "# print(attr_avail)\n",
        "dtree = dtree_learning(examples, attr_avail, [], cls_index)\n",
        "\n",
        "print(\"Before removal of unknowns: \")\n",
        "print(\"Training Set\")\n",
        "dtree_test(dtree, examples, cls_index)\n",
        "print(\"Test Set\")\n",
        "dtree_test(dtree, test, cls_index)\n",
        "\n",
        "# Extra task removal of unknowns\n",
        "examples_removed = []\n",
        "test_removed = []\n",
        "\n",
        "for example in examples:\n",
        "    # print(example.__contains__(\"?\"))\n",
        "    if not example.__contains__(\"?\"):\n",
        "        examples_removed.append(example)\n",
        "\n",
        "for example in test:\n",
        "    if not example.__contains__(\"?\"):\n",
        "        test_removed.append(example)\n",
        "\n",
        "# print(len(examples_removed))\n",
        "# print(len(test_removed))\n",
        "dtree = dtree_learning(examples_removed, attr_avail, [], cls_index)\n",
        "\n",
        "print(\"After removal of unknowns: \")\n",
        "print(\"Training Set\")\n",
        "dtree_test(dtree, examples_removed, cls_index)\n",
        "print(\"Test Set\")\n",
        "dtree_test(dtree, test_removed, cls_index)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "O0VM2f3t0Fzd",
        "outputId": "f61cab60-74db-4636-b04a-aaf77a110f8e"
      },
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Before removal of unknowns: \n",
            "Training Set\n",
            "28186 out of 32561 correct (86.56%)\n",
            "Test Set\n",
            "13275 out of 16281 correct (81.54%)\n",
            "After removal of unknowns: \n",
            "Training Set\n",
            "25974 out of 30162 correct (86.11%)\n",
            "Test Set\n",
            "12203 out of 15060 correct (81.03%)\n"
          ]
        }
      ]
    }
  ]
}