DecisionTree.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "DecisionTree.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "K6X7pLpZP4nR"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import pandas as pd\n",
        "class Node:\n",
        "  def __init__(self,class_name,condition):\n",
        "    self.class_name = class_name # column name eg : Age\n",
        "    self.condition = condition # value of that column eg : >21\n",
        "    self.children = []\n",
        "  \n",
        "  def getId(self):\n",
        "    return self.class_name + \" \" + self.condition # Age >21"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "class DecisionTree:\n",
        "  def __init__(self,dataset,target_class):\n",
        "    self.root = Node(\"Root node\",\"has no condition\") \n",
        "    self.dataset = dataset\n",
        "    self.target_class = target_class\n",
        "    #max information gain classes that are used by the constructed tree for classifying \n",
        "    self.max_gain_classes = [] \n",
        "  \n",
        "  def get_entropy(self,column,dataset,p,n):\n",
        "    categories = {}\n",
        "    for entry in list(dataset[column]):\n",
        "      categories[entry] = None\n",
        "\n",
        "    entropy = 0\n",
        "    for entry in list(categories.keys()):\n",
        "      df = dataset[dataset[column]==entry]\n",
        "      p_df,n_df,I_pn = self.get_info_gain(list(df[self.target_class]))\n",
        "      entropy+=((p_df+n_df)/(p+n))*I_pn\n",
        "    return entropy\n",
        "\n",
        "  \n",
        "  def get_info_gain(self,column):\n",
        "    categories = {}\n",
        "    for entry in column:\n",
        "      categories[entry] = categories[entry] + 1 if entry in categories else 1\n",
        "    keys = list(categories.keys())\n",
        "    p = categories[\"Y\"]/len(column) if \"Y\" in categories else 0\n",
        "    n = categories[\"N\"]/len(column) if \"N\" in categories else 0\n",
        "    P_ratio = p/(n+p)\n",
        "    N_ratio = n/(n+p)\n",
        "    if(P_ratio==0):\n",
        "      return p,n,-1*(N_ratio*np.log2(N_ratio))\n",
        "    elif(N_ratio==0):\n",
        "      return p,n,-1*(P_ratio*np.log2(P_ratio))\n",
        "    return p,n,-1*((P_ratio*np.log2(P_ratio)) + (N_ratio*np.log2(N_ratio)))\n",
        "  \n",
        "  def build(self,node,dataset):\n",
        "    if node is None:\n",
        "      node = self.root\n",
        "\n",
        "    #node in which corresponding dataset has same values in target column has it's child as leaf node\n",
        "    target_column = list(dataset[self.target_class])\n",
        "    p,n,target_column_info_gain = self.get_info_gain(target_column)\n",
        "    if target_column_info_gain==0: \n",
        "      node.children.append(Node(self.target_class,\"Y\" if n==0 else \"N\"))\n",
        "      return node\n",
        "\n",
        "    max_gain = 0\n",
        "    class_Indexes = {}\n",
        "    columns = list(dataset.columns) \n",
        "    max_gain_class = columns[0]\n",
        "\n",
        "    #calculate entropy and information gain for each column and select column which has highest information gain\n",
        "    for index in range(0,len(columns)):\n",
        "      if(columns[index]==self.target_class):\n",
        "        continue\n",
        "      column_entropy = self.get_entropy(columns[index],dataset,p,n)\n",
        "      class_Indexes[columns[index]] = index \n",
        "      gain = target_column_info_gain - column_entropy\n",
        "      if(gain > max_gain):\n",
        "        max_gain = gain\n",
        "        max_gain_class = columns[index]\n",
        "      self.max_gain_classes.append(max_gain_class)\n",
        "\n",
        "    # generate seperate datasets for each value of max_gain_class\n",
        "    class_Map = {}\n",
        "    records = list(dataset.to_records(index=False))\n",
        "    for row in records:\n",
        "      if row[class_Indexes[max_gain_class]] in class_Map:\n",
        "        class_Map[row[class_Indexes[max_gain_class]]].append(tuple(row))  \n",
        "      else : \n",
        "        class_Map[row[class_Indexes[max_gain_class]]]=[tuple(row)]\n",
        "\n",
        "    for key in class_Map:\n",
        "      df_child = pd.DataFrame(list(class_Map[key]),columns = columns)\n",
        "      df_child.drop(columns=[max_gain_class]) # remove the redundant max_gain_class column from the child dataset\n",
        "      child = self.build(Node(max_gain_class,key),df_child) # get remaining subtree with the given child as it's root\n",
        "      node.children.append(child)\n",
        "\n",
        "    return node\n"
      ],
      "metadata": {
        "id": "wG1npIMiYQw2"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "training_data = [\n",
        "  ['<21', 'High', 'M', 'Single', 'N'],\n",
        "  ['<21', 'High', 'M', 'Married', 'N'],\n",
        "  ['21-35', 'High', 'M', 'Single', 'Y'],\n",
        "  ['>35', 'Medium', 'M', 'Single', 'Y'],\n",
        "  ['>35', 'Low', 'F', 'Single', 'Y'],\n",
        "  ['>35', 'Low', 'F', 'Married', 'N'],\n",
        "  ['21-35', 'Low', 'F', 'Married', 'Y'],\n",
        "  ['<21', 'Medium', 'M', 'Single', 'N'],\n",
        "  ['<21', 'Low', 'F', 'Married', 'Y'],\n",
        "  ['>35', 'Medium', 'F', 'Single', 'Y'],\n",
        "  ['<21', 'Medium', 'F', 'Married', 'Y'],\n",
        "  ['21-35', 'Medium', 'M', 'Married', 'Y'],\n",
        "  ['21-35', 'High', 'F', 'Single', 'Y'],\n",
        "  ['>35', 'Medium', 'M', 'Married', 'N']\n",
        "]\n",
        "header = [\"Age\", \"Income\",\"Gender\",\"Marital Status\",\"Buys\"]\n",
        "dataset = pd.DataFrame(training_data,columns=header)\n",
        "dt = DecisionTree(dataset,\"Buys\")\n",
        "root = dt.build(None,dataset)"
      ],
      "metadata": {
        "id": "VIvke340IcnR"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#generate IF-THEN rules from the constructed tree\n",
        "rules = []\n",
        "def buildRules(root,rule_string,target_class):\n",
        "  if(len(root.children)==0):\n",
        "    rules.append(rule_string)\n",
        "    return\n",
        "  for node in root.children:\n",
        "    if(node.class_name==target_class):\n",
        "      buildRules(node,rule_string + \" THEN \" + node.getId(),target_class)\n",
        "    else :\n",
        "      buildRules(node,rule_string + \" IF \" + node.getId(),target_class)\n",
        "\n",
        "buildRules(root,\"\",\"Buys\")\n",
        "for rule in rules:\n",
        "  print(rule)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "uJ7Nq5eTIcHJ",
        "outputId": "8add9474-f7d0-4352-8e24-e5bec9cb468d"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            " IF Age <21 IF Gender M THEN Buys N\n",
            " IF Age <21 IF Gender F THEN Buys Y\n",
            " IF Age 21-35 THEN Buys Y\n",
            " IF Age >35 IF Marital Status Single THEN Buys Y\n",
            " IF Age >35 IF Marital Status Married THEN Buys N\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def bfs(root,data):\n",
        "  child_list=[root]\n",
        "  index=0\n",
        "  while(len(child_list)!=0):\n",
        "    node = child_list[0]\n",
        "    for child in node.children:\n",
        "      if(child.condition in ['Y','N']):\n",
        "        return child.condition\n",
        "      if(data[index]==child.condition):\n",
        "        child_list.append(child)\n",
        "        index+=1\n",
        "    child_list.remove(node)\n",
        "  return None\n",
        "\n",
        "#prediction by level wise search of queries and reaching upto leaf node\n",
        "def predict(data,root,classes,columns):\n",
        "  #remove the classes which are not in max information gain classes list\n",
        "  for index in range(0,len(data)) :\n",
        "    if columns[index] not in classes:\n",
        "      data.remove(data[index]) \n",
        "  return bfs(root,data)\n",
        "\n",
        "\n",
        "testing_data = [\n",
        "  ['<21', 'Low', 'F', 'Married']\n",
        "]\n",
        "\n",
        "ans = predict(testing_data[0],root,dt.max_gain_classes,header)\n",
        "print(ans)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "g7nizLkCxepT",
        "outputId": "de3c8f0f-fda2-47b7-a7a5-b619dc0c8059"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Y\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "cZQvfFZxr3KW"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}