DecisionTreeLearning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Learning\n",
    "\n",
    "This notebook serves as supporting material for **Lecture 13 - Learning** from the lecture Grundlagen der Künstlichen Intelligenz (IN2062). This notebook is absorbed from [learning.ipynb](https://github.com/aimacode/aima-python/blob/master/learning.ipynb) and uses implementations from [learning.py](https://github.com/aimacode/aima-python/blob/master/learning.py) of the AIMA repository from the book *Artificial Intelligence: A Modern Approach*. Let's start by importing everything from the module:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "pycharm": {
     "is_executing": false,
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "from learning import *\n",
    "from notebook import *\n",
    "from utils import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CONTENTS\n",
    "\n",
    "* Introduction\n",
    "\n",
    "* Decision Tree Learner\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Introduction\n",
    "\n",
    "\n",
    "You can find the code for the dataset here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "pycharm": {
     "is_executing": false,
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
       "   \"http://www.w3.org/TR/html4/strict.dtd\">\n",
       "<!--\n",
       "generated by Pygments <https://pygments.org/>\n",
       "Copyright 2006-2020 by the Pygments team.\n",
       "Licensed under the BSD license, see LICENSE for details.\n",
       "-->\n",
       "<html>\n",
       "<head>\n",
       "  <title></title>\n",
       "  <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
       "  <style type=\"text/css\">\n",
       "/*\n",
       "generated by Pygments <https://pygments.org/>\n",
       "Copyright 2006-2020 by the Pygments team.\n",
       "Licensed under the BSD license, see LICENSE for details.\n",
       "*/\n",
       "pre { line-height: 125%; }\n",
       "td.linenos pre { color: #000000; background-color: #f0f0f0; padding-left: 5px; padding-right: 5px; }\n",
       "span.linenos { color: #000000; background-color: #f0f0f0; padding-left: 5px; padding-right: 5px; }\n",
       "td.linenos pre.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }\n",
       "span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }\n",
       "body .hll { background-color: #ffffcc }\n",
       "body { background: #f8f8f8; }\n",
       "body .c { color: #408080; font-style: italic } /* Comment */\n",
       "body .err { border: 1px solid #FF0000 } /* Error */\n",
       "body .k { color: #008000; font-weight: bold } /* Keyword */\n",
       "body .o { color: #666666 } /* Operator */\n",
       "body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       "body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       "body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       "body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       "body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       "body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       "body .gd { color: #A00000 } /* Generic.Deleted */\n",
       "body .ge { font-style: italic } /* Generic.Emph */\n",
       "body .gr { color: #FF0000 } /* Generic.Error */\n",
       "body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       "body .gi { color: #00A000 } /* Generic.Inserted */\n",
       "body .go { color: #888888 } /* Generic.Output */\n",
       "body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       "body .gs { font-weight: bold } /* Generic.Strong */\n",
       "body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       "body .gt { color: #0044DD } /* Generic.Traceback */\n",
       "body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       "body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       "body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       "body .kp { color: #008000 } /* Keyword.Pseudo */\n",
       "body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       "body .kt { color: #B00040 } /* Keyword.Type */\n",
       "body .m { color: #666666 } /* Literal.Number */\n",
       "body .s { color: #BA2121 } /* Literal.String */\n",
       "body .na { color: #7D9029 } /* Name.Attribute */\n",
       "body .nb { color: #008000 } /* Name.Builtin */\n",
       "body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       "body .no { color: #880000 } /* Name.Constant */\n",
       "body .nd { color: #AA22FF } /* Name.Decorator */\n",
       "body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       "body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       "body .nf { color: #0000FF } /* Name.Function */\n",
       "body .nl { color: #A0A000 } /* Name.Label */\n",
       "body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       "body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       "body .nv { color: #19177C } /* Name.Variable */\n",
       "body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       "body .w { color: #bbbbbb } /* Text.Whitespace */\n",
       "body .mb { color: #666666 } /* Literal.Number.Bin */\n",
       "body .mf { color: #666666 } /* Literal.Number.Float */\n",
       "body .mh { color: #666666 } /* Literal.Number.Hex */\n",
       "body .mi { color: #666666 } /* Literal.Number.Integer */\n",
       "body .mo { color: #666666 } /* Literal.Number.Oct */\n",
       "body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       "body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       "body .sc { color: #BA2121 } /* Literal.String.Char */\n",
       "body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       "body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       "body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       "body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       "body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       "body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       "body .sx { color: #008000 } /* Literal.String.Other */\n",
       "body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       "body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       "body .ss { color: #19177C } /* Literal.String.Symbol */\n",
       "body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       "body .fm { color: #0000FF } /* Name.Function.Magic */\n",
       "body .vc { color: #19177C } /* Name.Variable.Class */\n",
       "body .vg { color: #19177C } /* Name.Variable.Global */\n",
       "body .vi { color: #19177C } /* Name.Variable.Instance */\n",
       "body .vm { color: #19177C } /* Name.Variable.Magic */\n",
       "body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "\n",
       "  </style>\n",
       "</head>\n",
       "<body>\n",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">class</span> <span class=\"nc\">DataSet</span><span class=\"p\">:</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;</span>\n",
       "<span class=\"sd\">    A data set for a machine learning problem. It has the following fields:</span>\n",
       "\n",
       "<span class=\"sd\">    d.examples   A list of examples. Each one is a list of attribute values.</span>\n",
       "<span class=\"sd\">    d.attrs      A list of integers to index into an example, so example[attr]</span>\n",
       "<span class=\"sd\">                 gives a value. Normally the same as range(len(d.examples[0])).</span>\n",
       "<span class=\"sd\">    d.attr_names Optional list of mnemonic names for corresponding attrs.</span>\n",
       "<span class=\"sd\">    d.target     The attribute that a learning algorithm will try to predict.</span>\n",
       "<span class=\"sd\">                 By default the final attribute.</span>\n",
       "<span class=\"sd\">    d.inputs     The list of attrs without the target.</span>\n",
       "<span class=\"sd\">    d.values     A list of lists: each sublist is the set of possible</span>\n",
       "<span class=\"sd\">                 values for the corresponding attribute. If initially None,</span>\n",
       "<span class=\"sd\">                 it is computed from the known examples by self.set_problem.</span>\n",
       "<span class=\"sd\">                 If not None, an erroneous value raises ValueError.</span>\n",
       "<span class=\"sd\">    d.distance   A function from a pair of examples to a non-negative number.</span>\n",
       "<span class=\"sd\">                 Should be symmetric, etc. Defaults to mean_boolean_error</span>\n",
       "<span class=\"sd\">                 since that can handle any field types.</span>\n",
       "<span class=\"sd\">    d.name       Name of the data set (for output display only).</span>\n",
       "<span class=\"sd\">    d.source     URL or other source where the data came from.</span>\n",
       "<span class=\"sd\">    d.exclude    A list of attribute indexes to exclude from d.inputs. Elements</span>\n",
       "<span class=\"sd\">                 of this list can either be integers (attrs) or attr_names.</span>\n",
       "\n",
       "<span class=\"sd\">    Normally, you call the constructor and you&#39;re done; then you just</span>\n",
       "<span class=\"sd\">    access fields like d.examples and d.target and d.inputs.</span>\n",
       "<span class=\"sd\">    &quot;&quot;&quot;</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">examples</span><span class=\"o\">=</span><span class=\"kc\">None</span><span class=\"p\">,</span> <span class=\"n\">attrs</span><span class=\"o\">=</span><span class=\"kc\">None</span><span class=\"p\">,</span> <span class=\"n\">attr_names</span><span class=\"o\">=</span><span class=\"kc\">None</span><span class=\"p\">,</span> <span class=\"n\">target</span><span class=\"o\">=-</span><span class=\"mi\">1</span><span class=\"p\">,</span> <span class=\"n\">inputs</span><span class=\"o\">=</span><span class=\"kc\">None</span><span class=\"p\">,</span>\n",
       "                 <span class=\"n\">values</span><span class=\"o\">=</span><span class=\"kc\">None</span><span class=\"p\">,</span> <span class=\"n\">distance</span><span class=\"o\">=</span><span class=\"n\">mean_boolean_error</span><span class=\"p\">,</span> <span class=\"n\">name</span><span class=\"o\">=</span><span class=\"s1\">&#39;&#39;</span><span class=\"p\">,</span> <span class=\"n\">source</span><span class=\"o\">=</span><span class=\"s1\">&#39;&#39;</span><span class=\"p\">,</span> <span class=\"n\">exclude</span><span class=\"o\">=</span><span class=\"p\">()):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;</span>\n",
       "<span class=\"sd\">        Accepts any of DataSet&#39;s fields. Examples can also be a</span>\n",
       "<span class=\"sd\">        string or file from which to parse examples using parse_csv.</span>\n",
       "<span class=\"sd\">        Optional parameter: exclude, as documented in .set_problem().</span>\n",
       "<span class=\"sd\">        &gt;&gt;&gt; DataSet(examples=&#39;1, 2, 3&#39;)</span>\n",
       "<span class=\"sd\">        &lt;DataSet(): 1 examples, 3 attributes&gt;</span>\n",
       "<span class=\"sd\">        &quot;&quot;&quot;</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">name</span> <span class=\"o\">=</span> <span class=\"n\">name</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">source</span> <span class=\"o\">=</span> <span class=\"n\">source</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">values</span> <span class=\"o\">=</span> <span class=\"n\">values</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">distance</span> <span class=\"o\">=</span> <span class=\"n\">distance</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">got_values_flag</span> <span class=\"o\">=</span> <span class=\"nb\">bool</span><span class=\"p\">(</span><span class=\"n\">values</span><span class=\"p\">)</span>\n",
       "\n",
       "        <span class=\"c1\"># initialize .examples from string or list or data directory</span>\n",
       "        <span class=\"k\">if</span> <span class=\"nb\">isinstance</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">,</span> <span class=\"nb\">str</span><span class=\"p\">):</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span> <span class=\"o\">=</span> <span class=\"n\">parse_csv</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">elif</span> <span class=\"n\">examples</span> <span class=\"ow\">is</span> <span class=\"kc\">None</span><span class=\"p\">:</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span> <span class=\"o\">=</span> <span class=\"n\">parse_csv</span><span class=\"p\">(</span><span class=\"n\">open_data</span><span class=\"p\">(</span><span class=\"n\">name</span> <span class=\"o\">+</span> <span class=\"s1\">&#39;.csv&#39;</span><span class=\"p\">)</span><span class=\"o\">.</span><span class=\"n\">read</span><span class=\"p\">())</span>\n",
       "        <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span> <span class=\"o\">=</span> <span class=\"n\">examples</span>\n",
       "\n",
       "        <span class=\"c1\"># attrs are the indices of examples, unless otherwise stated.</span>\n",
       "        <span class=\"k\">if</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span> <span class=\"ow\">is</span> <span class=\"ow\">not</span> <span class=\"kc\">None</span> <span class=\"ow\">and</span> <span class=\"n\">attrs</span> <span class=\"ow\">is</span> <span class=\"kc\">None</span><span class=\"p\">:</span>\n",
       "            <span class=\"n\">attrs</span> <span class=\"o\">=</span> <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">])))</span>\n",
       "\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attrs</span> <span class=\"o\">=</span> <span class=\"n\">attrs</span>\n",
       "\n",
       "        <span class=\"c1\"># initialize .attr_names from string, list, or by default</span>\n",
       "        <span class=\"k\">if</span> <span class=\"nb\">isinstance</span><span class=\"p\">(</span><span class=\"n\">attr_names</span><span class=\"p\">,</span> <span class=\"nb\">str</span><span class=\"p\">):</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr_names</span> <span class=\"o\">=</span> <span class=\"n\">attr_names</span><span class=\"o\">.</span><span class=\"n\">split</span><span class=\"p\">()</span>\n",
       "        <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr_names</span> <span class=\"o\">=</span> <span class=\"n\">attr_names</span> <span class=\"ow\">or</span> <span class=\"n\">attrs</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">set_problem</span><span class=\"p\">(</span><span class=\"n\">target</span><span class=\"p\">,</span> <span class=\"n\">inputs</span><span class=\"o\">=</span><span class=\"n\">inputs</span><span class=\"p\">,</span> <span class=\"n\">exclude</span><span class=\"o\">=</span><span class=\"n\">exclude</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">set_problem</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">target</span><span class=\"p\">,</span> <span class=\"n\">inputs</span><span class=\"o\">=</span><span class=\"kc\">None</span><span class=\"p\">,</span> <span class=\"n\">exclude</span><span class=\"o\">=</span><span class=\"p\">()):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;</span>\n",
       "<span class=\"sd\">        Set (or change) the target and/or inputs.</span>\n",
       "<span class=\"sd\">        This way, one DataSet can be used multiple ways. inputs, if specified,</span>\n",
       "<span class=\"sd\">        is a list of attributes, or specify exclude as a list of attributes</span>\n",
       "<span class=\"sd\">        to not use in inputs. Attributes can be -n .. n, or an attr_name.</span>\n",
       "<span class=\"sd\">        Also computes the list of possible values, if that wasn&#39;t done yet.</span>\n",
       "<span class=\"sd\">        &quot;&quot;&quot;</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">target</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr_num</span><span class=\"p\">(</span><span class=\"n\">target</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">exclude</span> <span class=\"o\">=</span> <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">map</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr_num</span><span class=\"p\">,</span> <span class=\"n\">exclude</span><span class=\"p\">))</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">inputs</span><span class=\"p\">:</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">inputs</span> <span class=\"o\">=</span> <span class=\"n\">remove_all</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">target</span><span class=\"p\">,</span> <span class=\"n\">inputs</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">inputs</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">a</span> <span class=\"k\">for</span> <span class=\"n\">a</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attrs</span> <span class=\"k\">if</span> <span class=\"n\">a</span> <span class=\"o\">!=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">target</span> <span class=\"ow\">and</span> <span class=\"n\">a</span> <span class=\"ow\">not</span> <span class=\"ow\">in</span> <span class=\"n\">exclude</span><span class=\"p\">]</span>\n",
       "        <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">values</span><span class=\"p\">:</span>\n",
       "            <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">update_values</span><span class=\"p\">()</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">check_me</span><span class=\"p\">()</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">check_me</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Check that my fields make sense.&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">assert</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr_names</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attrs</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">assert</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">target</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attrs</span>\n",
       "        <span class=\"k\">assert</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">target</span> <span class=\"ow\">not</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">inputs</span>\n",
       "        <span class=\"k\">assert</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">inputs</span><span class=\"p\">)</span><span class=\"o\">.</span><span class=\"n\">issubset</span><span class=\"p\">(</span><span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attrs</span><span class=\"p\">))</span>\n",
       "        <span class=\"k\">if</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">got_values_flag</span><span class=\"p\">:</span>\n",
       "            <span class=\"c1\"># only check if values are provided while initializing DataSet</span>\n",
       "            <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">map</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">check_example</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span><span class=\"p\">))</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">add_example</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">example</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Add an example to the list of examples, checking it first.&quot;&quot;&quot;</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">check_example</span><span class=\"p\">(</span><span class=\"n\">example</span><span class=\"p\">)</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">example</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">check_example</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">example</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Raise ValueError if example has any invalid values.&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">if</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">values</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">a</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attrs</span><span class=\"p\">:</span>\n",
       "                <span class=\"k\">if</span> <span class=\"n\">example</span><span class=\"p\">[</span><span class=\"n\">a</span><span class=\"p\">]</span> <span class=\"ow\">not</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">values</span><span class=\"p\">[</span><span class=\"n\">a</span><span class=\"p\">]:</span>\n",
       "                    <span class=\"k\">raise</span> <span class=\"ne\">ValueError</span><span class=\"p\">(</span><span class=\"s1\">&#39;Bad value </span><span class=\"si\">{}</span><span class=\"s1\"> for attribute </span><span class=\"si\">{}</span><span class=\"s1\"> in </span><span class=\"si\">{}</span><span class=\"s1\">&#39;</span>\n",
       "                                     <span class=\"o\">.</span><span class=\"n\">format</span><span class=\"p\">(</span><span class=\"n\">example</span><span class=\"p\">[</span><span class=\"n\">a</span><span class=\"p\">],</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr_names</span><span class=\"p\">[</span><span class=\"n\">a</span><span class=\"p\">],</span> <span class=\"n\">example</span><span class=\"p\">))</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">attr_num</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">attr</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Returns the number used for attr, which can be a name, or -n .. n-1.&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">if</span> <span class=\"nb\">isinstance</span><span class=\"p\">(</span><span class=\"n\">attr</span><span class=\"p\">,</span> <span class=\"nb\">str</span><span class=\"p\">):</span>\n",
       "            <span class=\"k\">return</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr_names</span><span class=\"o\">.</span><span class=\"n\">index</span><span class=\"p\">(</span><span class=\"n\">attr</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">elif</span> <span class=\"n\">attr</span> <span class=\"o\">&lt;</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attrs</span><span class=\"p\">)</span> <span class=\"o\">+</span> <span class=\"n\">attr</span>\n",
       "        <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">attr</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">update_values</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">values</span> <span class=\"o\">=</span> <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">map</span><span class=\"p\">(</span><span class=\"n\">unique</span><span class=\"p\">,</span> <span class=\"nb\">zip</span><span class=\"p\">(</span><span class=\"o\">*</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span><span class=\"p\">)))</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">sanitize</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">example</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Return a copy of example, with non-input attributes replaced by None.&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">return</span> <span class=\"p\">[</span><span class=\"n\">attr_i</span> <span class=\"k\">if</span> <span class=\"n\">i</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">inputs</span> <span class=\"k\">else</span> <span class=\"kc\">None</span> <span class=\"k\">for</span> <span class=\"n\">i</span><span class=\"p\">,</span> <span class=\"n\">attr_i</span> <span class=\"ow\">in</span> <span class=\"nb\">enumerate</span><span class=\"p\">(</span><span class=\"n\">example</span><span class=\"p\">)]</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">classes_to_numbers</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">classes</span><span class=\"o\">=</span><span class=\"kc\">None</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Converts class names to numbers.&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">classes</span><span class=\"p\">:</span>\n",
       "            <span class=\"c1\"># if classes were not given, extract them from values</span>\n",
       "            <span class=\"n\">classes</span> <span class=\"o\">=</span> <span class=\"nb\">sorted</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">values</span><span class=\"p\">[</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">target</span><span class=\"p\">])</span>\n",
       "        <span class=\"k\">for</span> <span class=\"n\">item</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span><span class=\"p\">:</span>\n",
       "            <span class=\"n\">item</span><span class=\"p\">[</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">target</span><span class=\"p\">]</span> <span class=\"o\">=</span> <span class=\"n\">classes</span><span class=\"o\">.</span><span class=\"n\">index</span><span class=\"p\">(</span><span class=\"n\">item</span><span class=\"p\">[</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">target</span><span class=\"p\">])</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">remove_examples</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">value</span><span class=\"o\">=</span><span class=\"s1\">&#39;&#39;</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Remove examples that contain given value.&quot;&quot;&quot;</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">x</span> <span class=\"k\">for</span> <span class=\"n\">x</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span> <span class=\"k\">if</span> <span class=\"n\">value</span> <span class=\"ow\">not</span> <span class=\"ow\">in</span> <span class=\"n\">x</span><span class=\"p\">]</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">update_values</span><span class=\"p\">()</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">split_values_by_classes</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Split values into buckets according to their class.&quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">buckets</span> <span class=\"o\">=</span> <span class=\"n\">defaultdict</span><span class=\"p\">(</span><span class=\"k\">lambda</span><span class=\"p\">:</span> <span class=\"p\">[])</span>\n",
       "        <span class=\"n\">target_names</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">values</span><span class=\"p\">[</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">target</span><span class=\"p\">]</span>\n",
       "\n",
       "        <span class=\"k\">for</span> <span class=\"n\">v</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span><span class=\"p\">:</span>\n",
       "            <span class=\"n\">item</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">a</span> <span class=\"k\">for</span> <span class=\"n\">a</span> <span class=\"ow\">in</span> <span class=\"n\">v</span> <span class=\"k\">if</span> <span class=\"n\">a</span> <span class=\"ow\">not</span> <span class=\"ow\">in</span> <span class=\"n\">target_names</span><span class=\"p\">]</span>  <span class=\"c1\"># remove target from item</span>\n",
       "            <span class=\"n\">buckets</span><span class=\"p\">[</span><span class=\"n\">v</span><span class=\"p\">[</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">target</span><span class=\"p\">]]</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">item</span><span class=\"p\">)</span>  <span class=\"c1\"># add item to bucket of its class</span>\n",
       "\n",
       "        <span class=\"k\">return</span> <span class=\"n\">buckets</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">find_means_and_deviations</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;</span>\n",
       "<span class=\"sd\">        Finds the means and standard deviations of self.dataset.</span>\n",
       "<span class=\"sd\">        means     : a dictionary for each class/target. Holds a list of the means</span>\n",
       "<span class=\"sd\">                    of the features for the class.</span>\n",
       "<span class=\"sd\">        deviations: a dictionary for each class/target. Holds a list of the sample</span>\n",
       "<span class=\"sd\">                    standard deviations of the features for the class.</span>\n",
       "<span class=\"sd\">        &quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">target_names</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">values</span><span class=\"p\">[</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">target</span><span class=\"p\">]</span>\n",
       "        <span class=\"n\">feature_numbers</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">inputs</span><span class=\"p\">)</span>\n",
       "\n",
       "        <span class=\"n\">item_buckets</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">split_values_by_classes</span><span class=\"p\">()</span>\n",
       "\n",
       "        <span class=\"n\">means</span> <span class=\"o\">=</span> <span class=\"n\">defaultdict</span><span class=\"p\">(</span><span class=\"k\">lambda</span><span class=\"p\">:</span> <span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"o\">*</span> <span class=\"n\">feature_numbers</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">deviations</span> <span class=\"o\">=</span> <span class=\"n\">defaultdict</span><span class=\"p\">(</span><span class=\"k\">lambda</span><span class=\"p\">:</span> <span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"o\">*</span> <span class=\"n\">feature_numbers</span><span class=\"p\">)</span>\n",
       "\n",
       "        <span class=\"k\">for</span> <span class=\"n\">t</span> <span class=\"ow\">in</span> <span class=\"n\">target_names</span><span class=\"p\">:</span>\n",
       "            <span class=\"c1\"># find all the item feature values for item in class t</span>\n",
       "            <span class=\"n\">features</span> <span class=\"o\">=</span> <span class=\"p\">[[]</span> <span class=\"k\">for</span> <span class=\"n\">_</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">feature_numbers</span><span class=\"p\">)]</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">item</span> <span class=\"ow\">in</span> <span class=\"n\">item_buckets</span><span class=\"p\">[</span><span class=\"n\">t</span><span class=\"p\">]:</span>\n",
       "                <span class=\"k\">for</span> <span class=\"n\">i</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">feature_numbers</span><span class=\"p\">):</span>\n",
       "                    <span class=\"n\">features</span><span class=\"p\">[</span><span class=\"n\">i</span><span class=\"p\">]</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">item</span><span class=\"p\">[</span><span class=\"n\">i</span><span class=\"p\">])</span>\n",
       "\n",
       "            <span class=\"c1\"># calculate means and deviations fo the class</span>\n",
       "            <span class=\"k\">for</span> <span class=\"n\">i</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"n\">feature_numbers</span><span class=\"p\">):</span>\n",
       "                <span class=\"n\">means</span><span class=\"p\">[</span><span class=\"n\">t</span><span class=\"p\">][</span><span class=\"n\">i</span><span class=\"p\">]</span> <span class=\"o\">=</span> <span class=\"n\">mean</span><span class=\"p\">(</span><span class=\"n\">features</span><span class=\"p\">[</span><span class=\"n\">i</span><span class=\"p\">])</span>\n",
       "                <span class=\"n\">deviations</span><span class=\"p\">[</span><span class=\"n\">t</span><span class=\"p\">][</span><span class=\"n\">i</span><span class=\"p\">]</span> <span class=\"o\">=</span> <span class=\"n\">stdev</span><span class=\"p\">(</span><span class=\"n\">features</span><span class=\"p\">[</span><span class=\"n\">i</span><span class=\"p\">])</span>\n",
       "\n",
       "        <span class=\"k\">return</span> <span class=\"n\">means</span><span class=\"p\">,</span> <span class=\"n\">deviations</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"fm\">__repr__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
       "        <span class=\"k\">return</span> <span class=\"s1\">&#39;&lt;DataSet(</span><span class=\"si\">{}</span><span class=\"s1\">): </span><span class=\"si\">{:d}</span><span class=\"s1\"> examples, </span><span class=\"si\">{:d}</span><span class=\"s1\"> attributes&gt;&#39;</span><span class=\"o\">.</span><span class=\"n\">format</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">,</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">examples</span><span class=\"p\">),</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attrs</span><span class=\"p\">))</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(DataSet)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Class Attributes\n",
    "\n",
    "* **examples**: Holds the items of the dataset. Each item is a list of values.\n",
    "\n",
    "* **attrs**: The indexes of the features (by default in the range of [0,f), where *f* is the number of features). For example, `item[i]` returns the feature at index *i* of *item*.\n",
    "\n",
    "* **attrnames**: An optional list with attribute names. For example, `item[s]`, where *s* is a feature name, returns the feature of name *s* in *item*.\n",
    "\n",
    "* **target**: The attribute a learning algorithm will try to predict. By default the last attribute.\n",
    "\n",
    "* **inputs**: This is the list of attributes without the target.\n",
    "\n",
    "* **values**: A list of lists which holds the set of possible values for the corresponding attribute/feature. If initially `None`, it gets computed (by the function `setproblem`) from the examples.\n",
    "\n",
    "* **distance**: The distance function used in the learner to calculate the distance between two items. By default `mean_boolean_error`.\n",
    "\n",
    "* **name**: Name of the dataset.\n",
    "\n",
    "* **source**: The source of the dataset (url or other). Not used in the code.\n",
    "\n",
    "* **exclude**: A list of indexes to exclude from `inputs`. The list can include either attribute indexes (attrs) or names (attrnames)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Class Helper Functions\n",
    "\n",
    "These functions help modify a `DataSet` object to your needs.\n",
    "\n",
    "* **sanitize**: Takes as input an example and returns it with non-input (target) attributes replaced by `None`. Useful for testing. Keep in mind that the example given is not itself sanitized, but instead a sanitized copy is returned.\n",
    "\n",
    "* **classes_to_numbers**: Maps the class names of a dataset to numbers. If the class names are not given, they are computed from the dataset values. Useful for classifiers that return a numerical value instead of a string.\n",
    "\n",
    "* **remove_examples**: Removes examples containing a given value. Useful for removing examples with missing values, or for removing classes (needed for binary classifiers).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DECISION TREE LEARNER\n",
    "\n",
    "### Overview\n",
    "\n",
    "#### Decision Trees\n",
    "A decision tree is a flowchart that uses a tree of decisions and their possible consequences for classification. At each non-leaf node of the tree an attribute of the input is tested, based on which a corresponding branch leading to a child-node is selected. At the leaf node the input is classified based on the class label of this leaf node. The paths from root to leaves represent classification rules based on which leaf nodes are assigned class labels.\n",
    "<img src=\"img/decision_tree_learner_restaurant.png\" alt=\"Drawing\" style=\"width: 600px;\"/>\n",
    "#### Decision Tree Learning\n",
    "Decision tree learning is the construction of a decision tree from class-labeled training data. The data is expected to be a tuple in which each record of the tuple is an attribute used for classification. The decision tree is built top-down, by choosing a variable at each step that best splits the set of items. There are different metrics for measuring the \"best split\". These generally measure the homogeneity of the target variable within the subsets.\n",
    "\n",
    "#### Gini Impurity\n",
    "Gini impurity of a set is the probability of a randomly chosen element to be incorrectly labeled if it was randomly labeled according to the distribution of labels in the set.\n",
    "\n",
    "$$I_G(p) = \\sum{p_i(1 - p_i)} = 1 - \\sum{p_i^2}$$\n",
    "\n",
    "We select a split which minimizes the Gini impurity in child nodes.\n",
    "\n",
    "#### Information Gain\n",
    "Information gain is based on the concept of entropy from information theory. Entropy is defined as:\n",
    "\n",
    "$$B(p) = -\\sum{p_i \\log_2{p_i}}$$\n",
    "\n",
    "Information Gain is difference between entropy of the parent and weighted sum of entropy of children. The feature used for splitting is the one which provides the most information gain.\n",
    "\n",
    "#### Pseudocode\n",
    "\n",
    "You can view the pseudocode by running the cell below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "pycharm": {
     "is_executing": false,
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "### AIMA3e\n",
       "__function__ DECISION-TREE-LEARNING(_examples_, _attributes_, _parent\\_examples_) __returns__ a tree  \n",
       "&emsp;__if__ _examples_ is empty __then return__ PLURALITY\\-VALUE(_parent\\_examples_)  \n",
       "&emsp;__else if__ all _examples_ have the same classification __then return__ the classification  \n",
       "&emsp;__else if__ _attributes_ is empty __then return__ PLURALITY\\-VALUE(_examples_)  \n",
       "&emsp;__else__  \n",
       "&emsp;&emsp;&emsp;_A_ &larr; argmax<sub>_a_ &isin; _attributes_</sub> IMPORTANCE(_a_, _examples_)  \n",
       "&emsp;&emsp;&emsp;_tree_ &larr; a new decision tree with root test _A_  \n",
       "&emsp;&emsp;&emsp;__for each__ value _v<sub>k</sub>_ of _A_ __do__  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;_exs_ &larr; \\{ _e_ : _e_ &isin; _examples_ __and__ _e_._A_ = _v<sub>k</sub>_ \\}  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;_subtree_ &larr; DECISION-TREE-LEARNING(_exs_, _attributes_ &minus; _A_, _examples_)  \n",
       "&emsp;&emsp;&emsp;&emsp;&emsp;add a branch to _tree_ with label \\(_A_ = _v<sub>k</sub>_\\) and subtree _subtree_  \n",
       "&emsp;&emsp;&emsp;__return__ _tree_  \n",
       "\n",
       "---\n",
       "__Figure ??__ The decision\\-tree learning algorithm. The function  IMPORTANCE is described in Section __??__. The function PLURALITY\\-VALUE selects the most common output value among a set of examples, breaking ties randomly."
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pseudocode(\"Decision Tree Learning\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation\n",
    "The nodes of the tree constructed by our learning algorithm are stored using either `DecisionFork` or `DecisionLeaf` based on whether they are a parent node or a leaf node respectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
       "   \"http://www.w3.org/TR/html4/strict.dtd\">\n",
       "<!--\n",
       "generated by Pygments <https://pygments.org/>\n",
       "Copyright 2006-2020 by the Pygments team.\n",
       "Licensed under the BSD license, see LICENSE for details.\n",
       "-->\n",
       "<html>\n",
       "<head>\n",
       "  <title></title>\n",
       "  <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
       "  <style type=\"text/css\">\n",
       "/*\n",
       "generated by Pygments <https://pygments.org/>\n",
       "Copyright 2006-2020 by the Pygments team.\n",
       "Licensed under the BSD license, see LICENSE for details.\n",
       "*/\n",
       "pre { line-height: 125%; }\n",
       "td.linenos pre { color: #000000; background-color: #f0f0f0; padding-left: 5px; padding-right: 5px; }\n",
       "span.linenos { color: #000000; background-color: #f0f0f0; padding-left: 5px; padding-right: 5px; }\n",
       "td.linenos pre.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }\n",
       "span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }\n",
       "body .hll { background-color: #ffffcc }\n",
       "body { background: #f8f8f8; }\n",
       "body .c { color: #408080; font-style: italic } /* Comment */\n",
       "body .err { border: 1px solid #FF0000 } /* Error */\n",
       "body .k { color: #008000; font-weight: bold } /* Keyword */\n",
       "body .o { color: #666666 } /* Operator */\n",
       "body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       "body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       "body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       "body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       "body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       "body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       "body .gd { color: #A00000 } /* Generic.Deleted */\n",
       "body .ge { font-style: italic } /* Generic.Emph */\n",
       "body .gr { color: #FF0000 } /* Generic.Error */\n",
       "body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       "body .gi { color: #00A000 } /* Generic.Inserted */\n",
       "body .go { color: #888888 } /* Generic.Output */\n",
       "body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       "body .gs { font-weight: bold } /* Generic.Strong */\n",
       "body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       "body .gt { color: #0044DD } /* Generic.Traceback */\n",
       "body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       "body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       "body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       "body .kp { color: #008000 } /* Keyword.Pseudo */\n",
       "body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       "body .kt { color: #B00040 } /* Keyword.Type */\n",
       "body .m { color: #666666 } /* Literal.Number */\n",
       "body .s { color: #BA2121 } /* Literal.String */\n",
       "body .na { color: #7D9029 } /* Name.Attribute */\n",
       "body .nb { color: #008000 } /* Name.Builtin */\n",
       "body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       "body .no { color: #880000 } /* Name.Constant */\n",
       "body .nd { color: #AA22FF } /* Name.Decorator */\n",
       "body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       "body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       "body .nf { color: #0000FF } /* Name.Function */\n",
       "body .nl { color: #A0A000 } /* Name.Label */\n",
       "body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       "body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       "body .nv { color: #19177C } /* Name.Variable */\n",
       "body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       "body .w { color: #bbbbbb } /* Text.Whitespace */\n",
       "body .mb { color: #666666 } /* Literal.Number.Bin */\n",
       "body .mf { color: #666666 } /* Literal.Number.Float */\n",
       "body .mh { color: #666666 } /* Literal.Number.Hex */\n",
       "body .mi { color: #666666 } /* Literal.Number.Integer */\n",
       "body .mo { color: #666666 } /* Literal.Number.Oct */\n",
       "body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       "body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       "body .sc { color: #BA2121 } /* Literal.String.Char */\n",
       "body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       "body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       "body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       "body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       "body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       "body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       "body .sx { color: #008000 } /* Literal.String.Other */\n",
       "body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       "body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       "body .ss { color: #19177C } /* Literal.String.Symbol */\n",
       "body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       "body .fm { color: #0000FF } /* Name.Function.Magic */\n",
       "body .vc { color: #19177C } /* Name.Variable.Class */\n",
       "body .vg { color: #19177C } /* Name.Variable.Global */\n",
       "body .vi { color: #19177C } /* Name.Variable.Instance */\n",
       "body .vm { color: #19177C } /* Name.Variable.Magic */\n",
       "body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "\n",
       "  </style>\n",
       "</head>\n",
       "<body>\n",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">class</span> <span class=\"nc\">DecisionFork</span><span class=\"p\">:</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;</span>\n",
       "<span class=\"sd\">    A fork of a decision tree holds an attribute to test, and a dict</span>\n",
       "<span class=\"sd\">    of branches, one for each of the attribute&#39;s values.</span>\n",
       "<span class=\"sd\">    &quot;&quot;&quot;</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">attr</span><span class=\"p\">,</span> <span class=\"n\">attr_name</span><span class=\"o\">=</span><span class=\"kc\">None</span><span class=\"p\">,</span> <span class=\"n\">default_child</span><span class=\"o\">=</span><span class=\"kc\">None</span><span class=\"p\">,</span> <span class=\"n\">branches</span><span class=\"o\">=</span><span class=\"kc\">None</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Initialize by saying what attribute this node tests.&quot;&quot;&quot;</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr</span> <span class=\"o\">=</span> <span class=\"n\">attr</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr_name</span> <span class=\"o\">=</span> <span class=\"n\">attr_name</span> <span class=\"ow\">or</span> <span class=\"n\">attr</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">default_child</span> <span class=\"o\">=</span> <span class=\"n\">default_child</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">branches</span> <span class=\"o\">=</span> <span class=\"n\">branches</span> <span class=\"ow\">or</span> <span class=\"p\">{}</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"fm\">__call__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">example</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Given an example, classify it using the attribute and the branches.&quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">attr_val</span> <span class=\"o\">=</span> <span class=\"n\">example</span><span class=\"p\">[</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr</span><span class=\"p\">]</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">attr_val</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">branches</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">branches</span><span class=\"p\">[</span><span class=\"n\">attr_val</span><span class=\"p\">](</span><span class=\"n\">example</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "            <span class=\"c1\"># return default class when attribute is unknown</span>\n",
       "            <span class=\"k\">return</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">default_child</span><span class=\"p\">(</span><span class=\"n\">example</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">add</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">subtree</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Add a branch. If self.attr = val, go to the given subtree.&quot;&quot;&quot;</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">branches</span><span class=\"p\">[</span><span class=\"n\">val</span><span class=\"p\">]</span> <span class=\"o\">=</span> <span class=\"n\">subtree</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">display</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">indent</span><span class=\"o\">=</span><span class=\"mi\">0</span><span class=\"p\">):</span>\n",
       "        <span class=\"n\">name</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr_name</span>\n",
       "        <span class=\"nb\">print</span><span class=\"p\">(</span><span class=\"s1\">&#39;Test&#39;</span><span class=\"p\">,</span> <span class=\"n\">name</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">for</span> <span class=\"p\">(</span><span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">subtree</span><span class=\"p\">)</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">branches</span><span class=\"o\">.</span><span class=\"n\">items</span><span class=\"p\">():</span>\n",
       "            <span class=\"nb\">print</span><span class=\"p\">(</span><span class=\"s1\">&#39; &#39;</span> <span class=\"o\">*</span> <span class=\"mi\">4</span> <span class=\"o\">*</span> <span class=\"n\">indent</span><span class=\"p\">,</span> <span class=\"n\">name</span><span class=\"p\">,</span> <span class=\"s1\">&#39;=&#39;</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"s1\">&#39;==&gt;&#39;</span><span class=\"p\">,</span> <span class=\"n\">end</span><span class=\"o\">=</span><span class=\"s1\">&#39; &#39;</span><span class=\"p\">)</span>\n",
       "            <span class=\"c1\">#subtree.display(indent + 1)</span>\n",
       "\n",
       "            <span class=\"k\">if</span> <span class=\"n\">indent</span> <span class=\"o\">&gt;</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
       "                <span class=\"n\">subtree</span><span class=\"o\">.</span><span class=\"n\">display</span><span class=\"p\">(</span><span class=\"n\">indent</span> <span class=\"o\">+</span> <span class=\"mi\">1</span><span class=\"p\">)</span>\n",
       "            <span class=\"k\">else</span><span class=\"p\">:</span>\n",
       "                <span class=\"n\">subtree</span><span class=\"o\">.</span><span class=\"n\">display</span><span class=\"p\">()</span>\n",
       "            \n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"fm\">__repr__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
       "        <span class=\"k\">return</span> <span class=\"s1\">&#39;DecisionFork(</span><span class=\"si\">{0!r}</span><span class=\"s1\">, </span><span class=\"si\">{1!r}</span><span class=\"s1\">, </span><span class=\"si\">{2!r}</span><span class=\"s1\">)&#39;</span><span class=\"o\">.</span><span class=\"n\">format</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">attr_name</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">branches</span><span class=\"p\">)</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(DecisionFork)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`DecisionFork` holds the attribute, which is tested at that node, and a dict of branches. The branches store the child nodes, one for each of the attribute's values. Calling an object of this class as a function with input tuple as an argument returns the next node in the classification path based on the result of the attribute test."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "pycharm": {
     "is_executing": false,
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
       "   \"http://www.w3.org/TR/html4/strict.dtd\">\n",
       "<!--\n",
       "generated by Pygments <https://pygments.org/>\n",
       "Copyright 2006-2020 by the Pygments team.\n",
       "Licensed under the BSD license, see LICENSE for details.\n",
       "-->\n",
       "<html>\n",
       "<head>\n",
       "  <title></title>\n",
       "  <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
       "  <style type=\"text/css\">\n",
       "/*\n",
       "generated by Pygments <https://pygments.org/>\n",
       "Copyright 2006-2020 by the Pygments team.\n",
       "Licensed under the BSD license, see LICENSE for details.\n",
       "*/\n",
       "pre { line-height: 125%; }\n",
       "td.linenos pre { color: #000000; background-color: #f0f0f0; padding-left: 5px; padding-right: 5px; }\n",
       "span.linenos { color: #000000; background-color: #f0f0f0; padding-left: 5px; padding-right: 5px; }\n",
       "td.linenos pre.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }\n",
       "span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }\n",
       "body .hll { background-color: #ffffcc }\n",
       "body { background: #f8f8f8; }\n",
       "body .c { color: #408080; font-style: italic } /* Comment */\n",
       "body .err { border: 1px solid #FF0000 } /* Error */\n",
       "body .k { color: #008000; font-weight: bold } /* Keyword */\n",
       "body .o { color: #666666 } /* Operator */\n",
       "body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       "body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       "body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       "body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       "body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       "body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       "body .gd { color: #A00000 } /* Generic.Deleted */\n",
       "body .ge { font-style: italic } /* Generic.Emph */\n",
       "body .gr { color: #FF0000 } /* Generic.Error */\n",
       "body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       "body .gi { color: #00A000 } /* Generic.Inserted */\n",
       "body .go { color: #888888 } /* Generic.Output */\n",
       "body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       "body .gs { font-weight: bold } /* Generic.Strong */\n",
       "body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       "body .gt { color: #0044DD } /* Generic.Traceback */\n",
       "body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       "body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       "body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       "body .kp { color: #008000 } /* Keyword.Pseudo */\n",
       "body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       "body .kt { color: #B00040 } /* Keyword.Type */\n",
       "body .m { color: #666666 } /* Literal.Number */\n",
       "body .s { color: #BA2121 } /* Literal.String */\n",
       "body .na { color: #7D9029 } /* Name.Attribute */\n",
       "body .nb { color: #008000 } /* Name.Builtin */\n",
       "body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       "body .no { color: #880000 } /* Name.Constant */\n",
       "body .nd { color: #AA22FF } /* Name.Decorator */\n",
       "body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       "body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       "body .nf { color: #0000FF } /* Name.Function */\n",
       "body .nl { color: #A0A000 } /* Name.Label */\n",
       "body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       "body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       "body .nv { color: #19177C } /* Name.Variable */\n",
       "body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       "body .w { color: #bbbbbb } /* Text.Whitespace */\n",
       "body .mb { color: #666666 } /* Literal.Number.Bin */\n",
       "body .mf { color: #666666 } /* Literal.Number.Float */\n",
       "body .mh { color: #666666 } /* Literal.Number.Hex */\n",
       "body .mi { color: #666666 } /* Literal.Number.Integer */\n",
       "body .mo { color: #666666 } /* Literal.Number.Oct */\n",
       "body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       "body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       "body .sc { color: #BA2121 } /* Literal.String.Char */\n",
       "body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       "body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       "body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       "body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       "body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       "body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       "body .sx { color: #008000 } /* Literal.String.Other */\n",
       "body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       "body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       "body .ss { color: #19177C } /* Literal.String.Symbol */\n",
       "body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       "body .fm { color: #0000FF } /* Name.Function.Magic */\n",
       "body .vc { color: #19177C } /* Name.Variable.Class */\n",
       "body .vg { color: #19177C } /* Name.Variable.Global */\n",
       "body .vi { color: #19177C } /* Name.Variable.Instance */\n",
       "body .vm { color: #19177C } /* Name.Variable.Magic */\n",
       "body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "\n",
       "  </style>\n",
       "</head>\n",
       "<body>\n",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">class</span> <span class=\"nc\">DecisionLeaf</span><span class=\"p\">:</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;A leaf of a decision tree holds just a result.&quot;&quot;&quot;</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">result</span><span class=\"p\">):</span>\n",
       "        <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">result</span> <span class=\"o\">=</span> <span class=\"n\">result</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"fm\">__call__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">example</span><span class=\"p\">):</span>\n",
       "        <span class=\"k\">return</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">result</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">display</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
       "        <span class=\"nb\">print</span><span class=\"p\">(</span><span class=\"s1\">&#39;RESULT =&#39;</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">result</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"fm\">__repr__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
       "        <span class=\"k\">return</span> <span class=\"nb\">repr</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">result</span><span class=\"p\">)</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(DecisionLeaf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The leaf node stores the class label in `result`. All input tuples' classification paths end on a `DecisionLeaf` whose `result` attribute decide their class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "pycharm": {
     "is_executing": false,
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
       "   \"http://www.w3.org/TR/html4/strict.dtd\">\n",
       "<!--\n",
       "generated by Pygments <https://pygments.org/>\n",
       "Copyright 2006-2020 by the Pygments team.\n",
       "Licensed under the BSD license, see LICENSE for details.\n",
       "-->\n",
       "<html>\n",
       "<head>\n",
       "  <title></title>\n",
       "  <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
       "  <style type=\"text/css\">\n",
       "/*\n",
       "generated by Pygments <https://pygments.org/>\n",
       "Copyright 2006-2020 by the Pygments team.\n",
       "Licensed under the BSD license, see LICENSE for details.\n",
       "*/\n",
       "pre { line-height: 125%; }\n",
       "td.linenos pre { color: #000000; background-color: #f0f0f0; padding-left: 5px; padding-right: 5px; }\n",
       "span.linenos { color: #000000; background-color: #f0f0f0; padding-left: 5px; padding-right: 5px; }\n",
       "td.linenos pre.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }\n",
       "span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }\n",
       "body .hll { background-color: #ffffcc }\n",
       "body { background: #f8f8f8; }\n",
       "body .c { color: #408080; font-style: italic } /* Comment */\n",
       "body .err { border: 1px solid #FF0000 } /* Error */\n",
       "body .k { color: #008000; font-weight: bold } /* Keyword */\n",
       "body .o { color: #666666 } /* Operator */\n",
       "body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
       "body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
       "body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
       "body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
       "body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
       "body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
       "body .gd { color: #A00000 } /* Generic.Deleted */\n",
       "body .ge { font-style: italic } /* Generic.Emph */\n",
       "body .gr { color: #FF0000 } /* Generic.Error */\n",
       "body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
       "body .gi { color: #00A000 } /* Generic.Inserted */\n",
       "body .go { color: #888888 } /* Generic.Output */\n",
       "body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
       "body .gs { font-weight: bold } /* Generic.Strong */\n",
       "body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
       "body .gt { color: #0044DD } /* Generic.Traceback */\n",
       "body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
       "body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
       "body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
       "body .kp { color: #008000 } /* Keyword.Pseudo */\n",
       "body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
       "body .kt { color: #B00040 } /* Keyword.Type */\n",
       "body .m { color: #666666 } /* Literal.Number */\n",
       "body .s { color: #BA2121 } /* Literal.String */\n",
       "body .na { color: #7D9029 } /* Name.Attribute */\n",
       "body .nb { color: #008000 } /* Name.Builtin */\n",
       "body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
       "body .no { color: #880000 } /* Name.Constant */\n",
       "body .nd { color: #AA22FF } /* Name.Decorator */\n",
       "body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
       "body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
       "body .nf { color: #0000FF } /* Name.Function */\n",
       "body .nl { color: #A0A000 } /* Name.Label */\n",
       "body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
       "body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
       "body .nv { color: #19177C } /* Name.Variable */\n",
       "body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
       "body .w { color: #bbbbbb } /* Text.Whitespace */\n",
       "body .mb { color: #666666 } /* Literal.Number.Bin */\n",
       "body .mf { color: #666666 } /* Literal.Number.Float */\n",
       "body .mh { color: #666666 } /* Literal.Number.Hex */\n",
       "body .mi { color: #666666 } /* Literal.Number.Integer */\n",
       "body .mo { color: #666666 } /* Literal.Number.Oct */\n",
       "body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
       "body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
       "body .sc { color: #BA2121 } /* Literal.String.Char */\n",
       "body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
       "body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
       "body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
       "body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
       "body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
       "body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
       "body .sx { color: #008000 } /* Literal.String.Other */\n",
       "body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
       "body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
       "body .ss { color: #19177C } /* Literal.String.Symbol */\n",
       "body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
       "body .fm { color: #0000FF } /* Name.Function.Magic */\n",
       "body .vc { color: #19177C } /* Name.Variable.Class */\n",
       "body .vg { color: #19177C } /* Name.Variable.Global */\n",
       "body .vi { color: #19177C } /* Name.Variable.Instance */\n",
       "body .vm { color: #19177C } /* Name.Variable.Magic */\n",
       "body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
       "\n",
       "  </style>\n",
       "</head>\n",
       "<body>\n",
       "<h2></h2>\n",
       "\n",
       "<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">DecisionTreeLearner</span><span class=\"p\">(</span><span class=\"n\">dataset</span><span class=\"p\">):</span>\n",
       "    <span class=\"sd\">&quot;&quot;&quot;[Figure 18.5]&quot;&quot;&quot;</span>\n",
       "\n",
       "    <span class=\"n\">target</span><span class=\"p\">,</span> <span class=\"n\">values</span> <span class=\"o\">=</span> <span class=\"n\">dataset</span><span class=\"o\">.</span><span class=\"n\">target</span><span class=\"p\">,</span> <span class=\"n\">dataset</span><span class=\"o\">.</span><span class=\"n\">values</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">decision_tree_learning</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">,</span> <span class=\"n\">attrs</span><span class=\"p\">,</span> <span class=\"n\">parent_examples</span><span class=\"o\">=</span><span class=\"p\">()):</span>\n",
       "        <span class=\"k\">if</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">plurality_value</span><span class=\"p\">(</span><span class=\"n\">parent_examples</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">if</span> <span class=\"n\">all_same_class</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">):</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">DecisionLeaf</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">][</span><span class=\"n\">target</span><span class=\"p\">])</span>\n",
       "        <span class=\"k\">if</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">attrs</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">plurality_value</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">A</span> <span class=\"o\">=</span> <span class=\"n\">choose_attribute</span><span class=\"p\">(</span><span class=\"n\">attrs</span><span class=\"p\">,</span> <span class=\"n\">examples</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">tree</span> <span class=\"o\">=</span> <span class=\"n\">DecisionFork</span><span class=\"p\">(</span><span class=\"n\">A</span><span class=\"p\">,</span> <span class=\"n\">dataset</span><span class=\"o\">.</span><span class=\"n\">attr_names</span><span class=\"p\">[</span><span class=\"n\">A</span><span class=\"p\">],</span> <span class=\"n\">plurality_value</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">))</span>\n",
       "        <span class=\"k\">for</span> <span class=\"p\">(</span><span class=\"n\">v_k</span><span class=\"p\">,</span> <span class=\"n\">exs</span><span class=\"p\">)</span> <span class=\"ow\">in</span> <span class=\"n\">split_by</span><span class=\"p\">(</span><span class=\"n\">A</span><span class=\"p\">,</span> <span class=\"n\">examples</span><span class=\"p\">):</span>\n",
       "            <span class=\"n\">subtree</span> <span class=\"o\">=</span> <span class=\"n\">decision_tree_learning</span><span class=\"p\">(</span><span class=\"n\">exs</span><span class=\"p\">,</span> <span class=\"n\">remove_all</span><span class=\"p\">(</span><span class=\"n\">A</span><span class=\"p\">,</span> <span class=\"n\">attrs</span><span class=\"p\">),</span> <span class=\"n\">examples</span><span class=\"p\">)</span>\n",
       "            <span class=\"n\">tree</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"n\">v_k</span><span class=\"p\">,</span> <span class=\"n\">subtree</span><span class=\"p\">)</span>\n",
       "        <span class=\"k\">return</span> <span class=\"n\">tree</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">plurality_value</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;</span>\n",
       "<span class=\"sd\">        Return the most popular target value for this set of examples.</span>\n",
       "<span class=\"sd\">        (If target is binary, this is the majority; otherwise plurality).</span>\n",
       "<span class=\"sd\">        &quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">popular</span> <span class=\"o\">=</span> <span class=\"n\">argmax_random_tie</span><span class=\"p\">(</span><span class=\"n\">values</span><span class=\"p\">[</span><span class=\"n\">target</span><span class=\"p\">],</span> <span class=\"n\">key</span><span class=\"o\">=</span><span class=\"k\">lambda</span> <span class=\"n\">v</span><span class=\"p\">:</span> <span class=\"n\">count</span><span class=\"p\">(</span><span class=\"n\">target</span><span class=\"p\">,</span> <span class=\"n\">v</span><span class=\"p\">,</span> <span class=\"n\">examples</span><span class=\"p\">))</span>\n",
       "        <span class=\"k\">return</span> <span class=\"n\">DecisionLeaf</span><span class=\"p\">(</span><span class=\"n\">popular</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">count</span><span class=\"p\">(</span><span class=\"n\">attr</span><span class=\"p\">,</span> <span class=\"n\">val</span><span class=\"p\">,</span> <span class=\"n\">examples</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Count the number of examples that have example[attr] = val.&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">return</span> <span class=\"nb\">sum</span><span class=\"p\">(</span><span class=\"n\">e</span><span class=\"p\">[</span><span class=\"n\">attr</span><span class=\"p\">]</span> <span class=\"o\">==</span> <span class=\"n\">val</span> <span class=\"k\">for</span> <span class=\"n\">e</span> <span class=\"ow\">in</span> <span class=\"n\">examples</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">all_same_class</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Are all these examples in the same target class?&quot;&quot;&quot;</span>\n",
       "        <span class=\"n\">class0</span> <span class=\"o\">=</span> <span class=\"n\">examples</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">][</span><span class=\"n\">target</span><span class=\"p\">]</span>\n",
       "        <span class=\"k\">return</span> <span class=\"nb\">all</span><span class=\"p\">(</span><span class=\"n\">e</span><span class=\"p\">[</span><span class=\"n\">target</span><span class=\"p\">]</span> <span class=\"o\">==</span> <span class=\"n\">class0</span> <span class=\"k\">for</span> <span class=\"n\">e</span> <span class=\"ow\">in</span> <span class=\"n\">examples</span><span class=\"p\">)</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">choose_attribute</span><span class=\"p\">(</span><span class=\"n\">attrs</span><span class=\"p\">,</span> <span class=\"n\">examples</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Choose the attribute with the highest information gain.&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">return</span> <span class=\"n\">argmax_random_tie</span><span class=\"p\">(</span><span class=\"n\">attrs</span><span class=\"p\">,</span> <span class=\"n\">key</span><span class=\"o\">=</span><span class=\"k\">lambda</span> <span class=\"n\">a</span><span class=\"p\">:</span> <span class=\"n\">information_gain</span><span class=\"p\">(</span><span class=\"n\">a</span><span class=\"p\">,</span> <span class=\"n\">examples</span><span class=\"p\">))</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">information_gain</span><span class=\"p\">(</span><span class=\"n\">attr</span><span class=\"p\">,</span> <span class=\"n\">examples</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Return the expected reduction in entropy from splitting by attr.&quot;&quot;&quot;</span>\n",
       "\n",
       "        <span class=\"k\">def</span> <span class=\"nf\">I</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">):</span>\n",
       "            <span class=\"k\">return</span> <span class=\"n\">information_content</span><span class=\"p\">([</span><span class=\"n\">count</span><span class=\"p\">(</span><span class=\"n\">target</span><span class=\"p\">,</span> <span class=\"n\">v</span><span class=\"p\">,</span> <span class=\"n\">examples</span><span class=\"p\">)</span> <span class=\"k\">for</span> <span class=\"n\">v</span> <span class=\"ow\">in</span> <span class=\"n\">values</span><span class=\"p\">[</span><span class=\"n\">target</span><span class=\"p\">]])</span>\n",
       "\n",
       "        <span class=\"n\">n</span> <span class=\"o\">=</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">)</span>\n",
       "        <span class=\"n\">remainder</span> <span class=\"o\">=</span> <span class=\"nb\">sum</span><span class=\"p\">((</span><span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">examples_i</span><span class=\"p\">)</span> <span class=\"o\">/</span> <span class=\"n\">n</span><span class=\"p\">)</span> <span class=\"o\">*</span> <span class=\"n\">I</span><span class=\"p\">(</span><span class=\"n\">examples_i</span><span class=\"p\">)</span> <span class=\"k\">for</span> <span class=\"p\">(</span><span class=\"n\">v</span><span class=\"p\">,</span> <span class=\"n\">examples_i</span><span class=\"p\">)</span> <span class=\"ow\">in</span> <span class=\"n\">split_by</span><span class=\"p\">(</span><span class=\"n\">attr</span><span class=\"p\">,</span> <span class=\"n\">examples</span><span class=\"p\">))</span>\n",
       "        <span class=\"k\">return</span> <span class=\"n\">I</span><span class=\"p\">(</span><span class=\"n\">examples</span><span class=\"p\">)</span> <span class=\"o\">-</span> <span class=\"n\">remainder</span>\n",
       "\n",
       "    <span class=\"k\">def</span> <span class=\"nf\">split_by</span><span class=\"p\">(</span><span class=\"n\">attr</span><span class=\"p\">,</span> <span class=\"n\">examples</span><span class=\"p\">):</span>\n",
       "        <span class=\"sd\">&quot;&quot;&quot;Return a list of (val, examples) pairs for each val of attr.&quot;&quot;&quot;</span>\n",
       "        <span class=\"k\">return</span> <span class=\"p\">[(</span><span class=\"n\">v</span><span class=\"p\">,</span> <span class=\"p\">[</span><span class=\"n\">e</span> <span class=\"k\">for</span> <span class=\"n\">e</span> <span class=\"ow\">in</span> <span class=\"n\">examples</span> <span class=\"k\">if</span> <span class=\"n\">e</span><span class=\"p\">[</span><span class=\"n\">attr</span><span class=\"p\">]</span> <span class=\"o\">==</span> <span class=\"n\">v</span><span class=\"p\">])</span> <span class=\"k\">for</span> <span class=\"n\">v</span> <span class=\"ow\">in</span> <span class=\"n\">values</span><span class=\"p\">[</span><span class=\"n\">attr</span><span class=\"p\">]]</span>\n",
       "\n",
       "    <span class=\"k\">return</span> <span class=\"n\">decision_tree_learning</span><span class=\"p\">(</span><span class=\"n\">dataset</span><span class=\"o\">.</span><span class=\"n\">examples</span><span class=\"p\">,</span> <span class=\"n\">dataset</span><span class=\"o\">.</span><span class=\"n\">inputs</span><span class=\"p\">)</span>\n",
       "</pre></div>\n",
       "</body>\n",
       "</html>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "psource(DecisionTreeLearner)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The implementation of `DecisionTreeLearner` provided in [learning.py](https://github.com/aimacode/aima-python/blob/master/learning.py) uses information gain as the metric for selecting which attribute to test for splitting. The function builds the tree top-down in a recursive manner. Based on the input it makes one of the four choices:\n",
    "<ol>\n",
    "<li>If the input at the current step has no training data we return the mode of classes of input data received in the parent step (previous level of recursion).</li>\n",
    "<li>If all values in training data belong to the same class it returns a `DecisionLeaf` whose class label is the class which all the data belongs to.</li>\n",
    "<li>If the data has no attributes that can be tested we return the class with highest plurality value in the training data.</li>\n",
    "<li>We choose the attribute which gives the highest amount of entropy gain and return a `DecisionFork` which splits based on this attribute. Each branch recursively calls `decision_tree_learning` to construct the sub-tree.</li>\n",
    "</ol>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example\n",
    "\n",
    "We will now use the Decision Tree Learner to learn a decision tree for the example from **lecture 13, slide 13**.\n",
    "First, create the dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "pycharm": {
     "is_executing": false,
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<DataSet(): 12 examples, 11 attributes>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "attrnames = ['Alt', 'Bar', 'Fri', 'Hun', 'Pat', 'Price', 'Rain', 'Res', 'Type', 'Est', 'WillWait']\n",
    "examples = [\n",
    "            ['T', 'F', 'F', 'T', 'Some', '$$$', 'F', 'T', 'French',  '0-10',  'T'],\n",
    "            ['T', 'F', 'F', 'T', 'Full', '$',   'F', 'F', 'Thai',    '30-60', 'F'], \n",
    "            ['F', 'T', 'F', 'F', 'Some', '$',   'F', 'F', 'Burger',  '0-10',  'T'], \n",
    "            ['T', 'F', 'T', 'T', 'Full', '$',   'F', 'F', 'Thai',    '10-30', 'T'], \n",
    "            ['T', 'F', 'T', 'F', 'Full', '$$$', 'F', 'T', 'French',  '>60',   'F'], \n",
    "            ['F', 'T', 'F', 'T', 'Some', '$$',  'T', 'T', 'Italian', '0-10',  'T'], \n",
    "            ['F', 'T', 'F', 'F', 'None', '$',   'T', 'F', 'Burger',  '0-10',  'F'], \n",
    "            ['F', 'F', 'F', 'T', 'Some', '$$',  'T', 'T', 'Thai',    '0-10',  'T'], \n",
    "            ['F', 'T', 'T', 'F', 'Full', '$',   'T', 'F', 'Burger',  '>60',   'F'], \n",
    "            ['T', 'T', 'T', 'T', 'Full', '$$$', 'F', 'T', 'Italian', '10-30', 'F'], \n",
    "            ['F', 'F', 'F', 'F', 'None', '$',   'F', 'F', 'Thai',    '0-10',  'F'], \n",
    "            ['T', 'T', 'T', 'T', 'Full', '$',   'F', 'F', 'Burger',  '30-60', 'T']\n",
    "           ]\n",
    "\n",
    "lecture_dataset = DataSet(examples=examples, attr_names=attrnames, target='WillWait')\n",
    "lecture_dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "DTL = DecisionTreeLearner(lecture_dataset)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Take a look at the tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "DecisionFork(4, 'Pat', {'Some': 'T', 'None': 'F', 'Full': DecisionFork(3, 'Hun', {'F': 'F', 'T': DecisionFork(8, 'Type', {'French': 'T', 'Thai': DecisionFork(9, 'Est', {'10-30': 'T', '0-10': 'F', '>60': 'T', '30-60': 'F'}), 'Burger': 'T', 'Italian': 'F'})})})"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DTL"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Display the tree properly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test Pat\n",
      " Pat = Some ==> RESULT = T\n",
      " Pat = None ==> RESULT = F\n",
      " Pat = Full ==> Test Hun\n",
      " Hun = F ==> RESULT = F\n",
      " Hun = T ==> Test Type\n",
      " Type = French ==> RESULT = T\n",
      " Type = Thai ==> Test Est\n",
      " Est = 10-30 ==> RESULT = T\n",
      " Est = 0-10 ==> RESULT = F\n",
      " Est = >60 ==> RESULT = T\n",
      " Est = 30-60 ==> RESULT = F\n",
      " Type = Burger ==> RESULT = T\n",
      " Type = Italian ==> RESULT = F\n"
     ]
    }
   ],
   "source": [
    "DTL.display()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-info\">\n",
    "    <h3>Note</h3>\n",
    "    <p>The calculated decision tree could be different from the one showed in the lecture slide 19. The reason is that after spliting the samples with Patrons, the information gain for the five attributes: Hun, Price, Res, Type, and Est are equal. Therefore, the algorithm randomly chooses one of the five attribute and split the samples further. We illustrate this by calculating the information gain values in the following.</p> \n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/decision_tree_restaurant_result.png\" alt=\"Drawing\" style=\"width: 500px;\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We adapt the functions from learning.py first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def split_by(attr, examples, values):\n",
    "        \"\"\"Return a list of (val, examples) pairs for each val of attr.\"\"\"\n",
    "        return [(v, [e for e in examples if e[attr] == v])\n",
    "                for v in values[attr]]\n",
    "\n",
    "def count(attr, val, examples):\n",
    "    \"\"\"Count the number of examples that have example[attr] = val.\"\"\"\n",
    "    return sum(e[attr] == val for e in examples)\n",
    "\n",
    "def information_gain(attr, examples, values, target):\n",
    "    \"\"\"Return the expected reduction in entropy from splitting by attr.\"\"\"\n",
    "    def I(examples):\n",
    "        return information_content([count(target, v, examples)\n",
    "                                    for v in values[target]])\n",
    "    N = len(examples)\n",
    "    remainder = sum((len(examples_i)/N) * I(examples_i)\n",
    "                    for (v, examples_i) in split_by(attr, examples, values))\n",
    "    return I(examples) - remainder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We get three child datasets after spliting the samples with attribute Patrons. All the samples of the child dataset for Pat=\"None\" and for Pat=\"Some\" have the same value for the target. So we only need to split the tree further for Pat=\"Full\". We define the child dataset first:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<DataSet(): 6 examples, 10 attributes>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "attrnames = ['Alt', 'Bar', 'Fri', 'Hun', 'Price', 'Rain', 'Res', 'Type', 'Est', 'WillWait']\n",
    "examples = [\n",
    "            ['T', 'F', 'F', 'T', '$',   'F', 'F', 'Thai',    '30-60', 'F'], \n",
    "            ['T', 'F', 'T', 'T', '$',   'F', 'F', 'Thai',    '10-30', 'T'], \n",
    "            ['T', 'F', 'T', 'F', '$$$', 'F', 'T', 'French',  '>60',   'F'],\n",
    "            ['F', 'T', 'T', 'F', '$',   'T', 'F', 'Burger',  '>60',   'F'], \n",
    "            ['T', 'T', 'T', 'T', '$$$', 'F', 'T', 'Italian', '10-30', 'F'],\n",
    "            ['T', 'T', 'T', 'T', '$',   'F', 'F', 'Burger',  '30-60', 'T']\n",
    "           ]\n",
    "child_dataset = DataSet(examples=examples, attr_names=attrnames, target='WillWait')\n",
    "child_dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Information gain of attribute Alt is 0.109170338675599\n",
      "Information gain of attribute Bar is 0.0\n",
      "Information gain of attribute Fri is 0.109170338675599\n",
      "Information gain of attribute Hun is 0.2516291673878229\n",
      "Information gain of attribute Price is 0.2516291673878229\n",
      "Information gain of attribute Rain is 0.109170338675599\n",
      "Information gain of attribute Res is 0.2516291673878229\n",
      "Information gain of attribute Type is 0.2516291673878229\n",
      "Information gain of attribute Est is 0.2516291673878229\n"
     ]
    }
   ],
   "source": [
    "for attr in child_dataset.inputs:\n",
    "    info_gain = information_gain(attr, child_dataset.examples, \n",
    "                                 child_dataset.values, child_dataset.target)\n",
    "    print(\"Information gain of attribute {} is {}\".format(child_dataset.attr_names[attr], info_gain))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see that the information gain of Hun, Price, Res, Type, and Est are all 0.2516. So it does not matter along which of the five attributes to split further. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we use the learned decision tree to classify a sample with \n",
    "    'Alt'= 'F', 'Bar'='F', 'Fri'='F', 'Hun='F', 'Pat'='None', 'Price'='$', 'Rain'='F', 'Res'='F', 'Type'='Thai', 'Est'='0-10'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "F\n"
     ]
    }
   ],
   "source": [
    "print(DTL(['F', 'F', 'F', 'F','None', '$', 'F', 'F', 'Thai', '0-10']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, the Decision Tree learner classifies the sample as \"F\"."
   ]
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.9"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "metadata": {
     "collapsed": false
    },
    "source": []
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}