7-Decision-Trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decision Trees \n",
    "\n",
    "\n",
    "by \n",
    "[__Michael Granitzer__ (michael.granitzer@uni-passau.de)]( http://www.mendeley.com/profiles/michael-granitzer/)  \n",
    "Jörg Schlötterer (joerg.schloetterer@uni-passau.de)\n",
    "\n",
    "with examples taken from the [scikit-learn documentation](http://scikit-learn.org/stable/)\n",
    "\n",
    "__License__\n",
    "\n",
    "This work is licensed under a [Creative Commons Attribution 3.0 Unported License](http://creativecommons.org/licenses/by/3.0/)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Setting up IPython Notebook\n",
    "The code below simply sets up ipython notebook and displays graphs inline (e.g. as HTML)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "import numpy.linalg as la\n",
    "np.set_printoptions(precision=3)\n",
    "def pp_float_list(ps):#pretty print functionality\n",
    "    return [\"%2.3f\" % p for p in ps]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ID3 Implementation\n",
    "\n",
    "The goal of this exercise is to implement basic ID 3 decision trees. \n",
    "\n",
    "Experiments are conducted on the [UCI CAR Dataset](http://archive.ics.uci.edu/ml/machine-learning-databases/car/).\n",
    "\n",
    "We will cover\n",
    "  \n",
    "  * Data Setup\n",
    "  * Impurity functions and impurity gain\n",
    "  * ID3 Algorithm for learning a decistion tree\n",
    "  * Classifying unseen examples\n",
    "  * Evaluation using random splitting\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Preparation and Preprocessing\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Download and import the data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "mkdir: CAR: File exists\n",
      "  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current\n",
      "                                 Dload  Upload   Total   Spent    Left  Speed\n",
      "100 51867  100 51867    0     0  41880      0  0:00:01  0:00:01 --:--:-- 41861\n",
      "  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current\n",
      "                                 Dload  Upload   Total   Spent    Left  Speed\n",
      "100  3097  100  3097    0     0   8727      0 --:--:-- --:--:-- --:--:--  8748\n",
      "1. Title: Car Evaluation Database\n",
      "\n",
      "2. Sources:\n",
      "   (a) Creator: Marko Bohanec\n",
      "   (b) Donors: Marko Bohanec   (marko.bohanec@ijs.si)\n",
      "               Blaz Zupan      (blaz.zupan@ijs.si)\n",
      "   (c) Date: June, 1997\n",
      "\n",
      "3. Past Usage:\n",
      "\n",
      "   The hierarchical decision model, from which this dataset is\n",
      "   derived, was first presented in \n",
      "\n",
      "   M. Bohanec and V. Rajkovic: Knowledge acquisition and explanation for\n",
      "   multi-attribute decision making. In 8th Intl Workshop on Expert\n",
      "   Systems and their Applications, Avignon, France. pages 59-78, 1988.\n",
      "\n",
      "   Within machine-learning, this dataset was used for the evaluation\n",
      "   of HINT (Hierarchy INduction Tool), which was proved to be able to\n",
      "   completely reconstruct the original hierarchical model. This,\n",
      "   together with a comparison with C4.5, is presented in\n",
      "\n",
      "   B. Zupan, M. Bohanec, I. Bratko, J. Demsar: Machine learning by\n",
      "   function decomposition. ICML-97, Nashville, TN. 1997 (to appear)\n",
      "\n",
      "4. Relevant Information Paragraph:\n",
      "\n",
      "   Car Evaluation Database was derived from a simple hierarchical\n",
      "   decision model originally developed for the demonstration of DEX\n",
      "   (M. Bohanec, V. Rajkovic: Expert system for decision\n",
      "   making. Sistemica 1(1), pp. 145-157, 1990.). The model evaluates\n",
      "   cars according to the following concept structure:\n",
      "\n",
      "   CAR                      car acceptability\n",
      "   . PRICE                  overall price\n",
      "   . . buying               buying price\n",
      "   . . maint                price of the maintenance\n",
      "   . TECH                   technical characteristics\n",
      "   . . COMFORT              comfort\n",
      "   . . . doors              number of doors\n",
      "   . . . persons            capacity in terms of persons to carry\n",
      "   . . . lug_boot           the size of luggage boot\n",
      "   . . safety               estimated safety of the car\n",
      "\n",
      "   Input attributes are printed in lowercase. Besides the target\n",
      "   concept (CAR), the model includes three intermediate concepts:\n",
      "   PRICE, TECH, COMFORT. Every concept is in the original model\n",
      "   related to its lower level descendants by a set of examples (for\n",
      "   these examples sets see http://www-ai.ijs.si/BlazZupan/car.html).\n",
      "\n",
      "   The Car Evaluation Database contains examples with the structural\n",
      "   information removed, i.e., directly relates CAR to the six input\n",
      "   attributes: buying, maint, doors, persons, lug_boot, safety.\n",
      "\n",
      "   Because of known underlying concept structure, this database may be\n",
      "   particularly useful for testing constructive induction and\n",
      "   structure discovery methods.\n",
      "\n",
      "5. Number of Instances: 1728\n",
      "   (instances completely cover the attribute space)\n",
      "\n",
      "6. Number of Attributes: 6\n",
      "\n",
      "7. Attribute Values:\n",
      "\n",
      "   buying       v-high, high, med, low\n",
      "   maint        v-high, high, med, low\n",
      "   doors        2, 3, 4, 5-more\n",
      "   persons      2, 4, more\n",
      "   lug_boot     small, med, big\n",
      "   safety       low, med, high\n",
      "\n",
      "8. Missing Attribute Values: none\n",
      "\n",
      "9. Class Distribution (number of instances per class)\n",
      "\n",
      "   class      N          N[%]\n",
      "   -----------------------------\n",
      "   unacc     1210     (70.023 %) \n",
      "   acc        384     (22.222 %) \n",
      "   good        69     ( 3.993 %) \n",
      "   v-good      65     ( 3.762 %) \n"
     ]
    }
   ],
   "source": [
    "#shell scripts for downloading the data and placing it in a corresponding directory\n",
    "!mkdir CAR \n",
    "!curl -o CAR/data \"http://archive.ics.uci.edu/ml/machine-learning-databases/car/car.data\"\n",
    "!curl -o CAR/description \"http://archive.ics.uci.edu/ml/machine-learning-databases/car/car.names\"\n",
    "#download the description and display it here.\n",
    "!cat CAR/description"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1728, 7) 7\n"
     ]
    }
   ],
   "source": [
    "#load the data via numpy's genfromtxt method\n",
    "auto = np.genfromtxt(\"./CAR/data\",dtype='object',delimiter=',')\n",
    "#store the feature names for later use\n",
    "feature = ['buying','maint','doors','persons','lug_boot','safety','recommendation']\n",
    "print (auto.shape, len(feature))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing impurity functions\n",
    "In the following, we will implement the impurity gain function $\\Delta\\iota(D,\\{D_1\\ldots D_s\\})$ and impurity function(s) $\\iota(D,\\{D_1\\ldots D_s\\})$.\n",
    "\n",
    "$$\n",
    "\\iota(D) = \\iota\\left(\\frac{|\\{(x,c(x))\\in D : c(x) = c_1\\}|}{|D|},...,\\frac{|\\{(x,c(x))\\in D : c(x) = c_k\\}|}{|D|}\\right)\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\Delta\\iota(D,\\{D_1\\ldots D_s\\}) = \\iota(D) - \\sum_{j=1}^{s}\\frac{|D_j|}{D}\\cdot\\iota(D_j)\n",
    "$$\n",
    "\n",
    "For theoretical details please refer to the [WEBIS lecture notes, ML:III](http://www.uni-weimar.de/medien/webis/teaching/lecturenotes/machine-learning/unit-en-decision-trees-impurity.pdf))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def impurity_gain(X,a,y,impurity,debug=False):\n",
    "    \"\"\"\n",
    "    X: data matrix n rows, d columns\n",
    "    a: column index of the attribute to evaluate the impurity gain for\n",
    "    y: concept vector with n rows and 1 column\n",
    "    impurity: impurity function of the form impurity(p_1....p_k) with k=|X[a].unique|\n",
    "    returns: impurity gain\n",
    "    Note: for more readable code we do not check any assertion \n",
    "    \"\"\"\n",
    "    attributes = np.unique(X[:,a])\n",
    "    concepts = np.unique(y)\n",
    "    #estimate the probabilty for a concept and the associated impurity h(p)\n",
    "    p = [np.sum(y==concept)/float(X.shape[0])  for concept in concepts]\n",
    "    h_p = impurity(np.array(p))\n",
    "    if debug: print (\"\\timpurity %0.3f for attribute %d: \"%(h_p,a), pp_float_list(p))\n",
    "    #now do the same for every attribute:\n",
    "    #i.e. we calculate the probability of all concepts given an attribute (resp. the splitting induced by the attribute)\n",
    "    h_pa =[]\n",
    "    d_num=float(X.shape[0])\n",
    "    for attribute in attributes:\n",
    "        da = X[:,a]==attribute\n",
    "        da_num =float(np.sum(da))\n",
    "        p = [np.sum(y[da,]==concept)/da_num for concept in concepts]\n",
    "        h_pa.append(da_num/d_num*impurity(np.array(p)))\n",
    "        if debug: print (\"\\t\\t impurity %0.3f for attribute %d with value %s: \"%(h_pa[-1],a,attribute), pp_float_list(p))\n",
    "    if debug:  print (\"\\t Estimated gain %0.3f\"%(h_p-np.sum(h_pa)))\n",
    "    return h_p-np.sum(h_pa)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And now define the impurity functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini(p):\n",
    "    \"\"\"\n",
    "    p: numpy array with np.sum(p)=1\n",
    "    \"\"\"\n",
    "    return 1-np.sum(p**2)\n",
    "\n",
    "def entropy(p):\n",
    "    \"\"\"\n",
    "    p: numpy array with np.sum(p)=1\n",
    "    \"\"\"\n",
    "    idx= np.where(p==0) #consider 0*log(0) as 0\n",
    "    r=p*np.log2(p)\n",
    "    r[idx]=0\n",
    "    return -np.sum(r)\n",
    "    \n",
    "def misclass(p):\n",
    "    \"\"\"\n",
    "    p: numpy array with np.sum(p)=1\n",
    "    \"\"\"\n",
    "    return 1-np.max(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lets visualise the functions for the 2D case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "//anaconda/envs/datsci/lib/python3.6/site-packages/ipykernel/__main__.py:12: RuntimeWarning: divide by zero encountered in log2\n",
      "//anaconda/envs/datsci/lib/python3.6/site-packages/ipykernel/__main__.py:12: RuntimeWarning: invalid value encountered in multiply\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAEKCAYAAAD9xUlFAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzs3XdcleX/x/HXxRIHuHAr4lZURIZ7Zq5ScW9T0xxlNr5p\nNpxZaVlZuTP3nmjmSM29wT1w4ADcSCJD5rl+f9zgz0yGcM65D3A9Hw8eCtye89bifM59jc8lpJQo\niqIoCoCV3gEURVEUy6GKgqIoivKMKgqKoijKM6ooKIqiKM+ooqAoiqI8o4qCoiiK8owqCoqiKMoz\nqigoiqIoz6iioCiKojxjo3eAV+Xk5CRdXFz0jqEoipKl+Pv7h0opi6R1XZYrCi4uLvj5+ekdQ1EU\nJUsRQtxKz3Vq+EhRFEV5RhUFRVEU5RlVFBRFUZRnVFFQFEVRnjFZURBCLBBCPBBCnE/h+0II8YsQ\n4poQ4qwQwsNUWRRFUZT0MeWdwiKgTSrfbwtUSvoYAsw2YRZFURQlHUxWFKSU+4GwVC7xAZZIzVGg\ngBCihKnyKIqiKGnTc59CKSD4uc9Dkr52V584ipKKxHiIfACR97RfI+5B1EPt6ykRVpDXCfIVA4fi\nkK8o5CsOtvbmy60oryhLbF4TQgxBG2LC2dlZ5zRKtiUlhIfAvbNw9wzcPQuPgyDyPkQ/Al52nrlI\n7QFf/mX7/FqhcCwFxWtACXco7gaFK4CVtRH+IoqScXoWhdtAmec+L530tf+QUs4D5gF4eXml8JOm\nKK8oPASCjv67CDxNGvEUVlC4kvZCXaZO0jv9Yknv+otp7/jzFgEbu5Qf35CoFZOIe1phSf41+feP\nb8GxuZAYp11vmzepSNTSikRpbyhSBURqhUdRjEvPorAZGCGEWAXUBcKllGroSDGdxAQIOQ5XdsDV\nnfDggvZ1azso6grV2mkvxiXcoVh1sMuTueezsk4aMiqaSqZ4eHhZK0rJxen0Coibp30/vzNUagmV\nWkG5JpnPpChpEFKa5o23EGIl0AxwAu4D4wFbACnlHCGEAGagrVCKBgZKKdNsauTl5SVV7yMl3SIf\nwrVdcPUvCNwNMeFgZQPO9bUX2vLNoEjV1N/xm5vBAGHX4dZBrXgF7oH4KLDOBeUaQ6XWWqEoVE7v\npEoWIoTwl1J6pXmdqYqCqaiioKQpPgYCtsCppXB9HyC1YZ/kd9zlm4O9o94p0y8hFm4d1grb1b/g\n0TXt68Vrgkd/qNkVchfUN6Ni8VRRUHKe+xfh5BI4uwqe/qMNvbj3gipvaMNCVtlkA/+jQG0I7MxK\nbcjJxh5cfcDjLSjbUM1BKC+lioKSM8RGwPkNWjG47QdWttrcgMdbUK5Z9ikEKblzWrsjOrsWYsOh\nUAXw6Ae1emsT4oqSRBUFJXuLfACHfwW/BRAXqc0LeLwFbj0hb2G905lfXDRc2qwVx1uHQFhrw0qN\nP4EilfVOp1iA9BaFLLFPQVGeibgHh37RikFiLFTvDHWHass3c/KwiV0eqNVT+wi9Cn4LwX8hnF0D\nNTpDk1FQtJreKZUsQN0pKFlD+G049DP4LwJDArj1gMb/A6eKeiezXFGhcGQGHP9Nu5ty9dGKQ/Ga\neidTdKCGj5Ts4XEwHPxJGzeXBnDvDY0+VssxX0V0GBydpW2Ui30CVd6EpqOgZG29kylmpIqCkrXF\nRcGBH7R5Aym1ydNGH0EB1eYkw54+1grD0Znafg23HtBykrZbW8n2VFFQsiYp4eIm2PEFPAmBWr3g\ntS8hf2m9k2UfMU+0objDv2gb4pqN0eZlrG31TqaYUHqLQjZfr6dkKQ+vwNKOsLa/thnr7R3QaY4q\nCMZm7wgtxsK7R6FsffjrC5jTGG7s1zuZYgFUUVD0FxsBf42F2fXhzil4YxoM2QvO9fROlr0VrgC9\n10CvVRAfDYvbw9qB2qS+kmOpJamKvi5shO2fQcRdqN0XWkyAfEX0TpVzCAFV2mo9oA79rE3qX9kB\nTUdD/RFgrV4ichp1p6Do4+ljWD8Y1g7QuogO2gU+M1VB0Ittbm1u4b1jUL4p7BoPi96AsBt6J1PM\nTBUFxfxuHoQ5jbT2FM2/gMF/QxlvvVMpAAVdoNdK6DwfHgRocw2nV2gLAJQcQRUFxXwS4mDneFjU\nTlvpMminNkyhhigsj1s3GH5QO/DHd7g2+R+d2pHrSnahioJiHg8vw/wWcGi61qNo6AEo7al3KiU1\nBZyh/2Z4fSIEbIXZDbSzHZRsTRUFxbSk1NoszG0CT25DzxXQ4RfIlU/vZEp6WFlDow9h8C7I5aAt\nGd7+uXZmhZItqaKgmE7ME1jVB7Z+Ai6NYPgRqPqm3qmUjCjpDkP2gfc72o7o+a/DP7f0TqWYgCoK\nimk8CoTfW8KV7dD6W+izTvX3z+rs8sCb07S9DeFB8FtzbdGAkq2ooqAYX+Ae+O01iLwP/TZC/Xdz\ndlvr7KZya23FWO5CsMQHTszXO5FiRKooKMYjJRydA8u6gEMJeGePtuZdyX6cKsI7u6HCa/Dn/2DL\nR9rqMiXLU0VBMY6EWNg8ArZ/CpXbwOCdqr11dmefX2uR0fBD7dCjpR21MxyULE0VBSXzIu5rew9O\nLYMmo6HHMm2lipL9WVlDy4naZrfb/jCvOdw7p3cqJRNUUVAy5+5ZbcLx/nnotghe+wKs1P9WOY5b\nNxi4TTsV7/dWcOkPvRMpGaR+epWMu3UEFr0JCK3NdfVOeidS9FTKA4bsgWLVYc1bcHKp3omUDFBF\nQcmYq7tgaSfIVwwG7YASbnonUiyBQ3F4a5PWdXXzCDgyU+9EyitSRUF5dRc2wsqe2gqUgdvUITjK\nv9nl1Sagq3WAHZ/Dnm9UQ70sRBUF5dWcXALr3obSXtB/i2p1rbycTS7oulA7I2PfVNg+BgwGvVMp\n6aDaUyrpd/hX+OtLqPg6dF+q7XBVlJRY20CHGZArv9YaI+YJdPhVdcW1cOq/jpI2KWHP17D/e3Dt\nCJ1/Axs7vVMpWYEQ0PpryF1A+38o9gl0XaDdSSgWSQ0fKakzGGDbp1pBqN0v6QdaFQTlFQihnZvR\nZioEbIEV3SE2Uu9USgpUUVBSJiVsGw3H52rn9Xb4VduspCgZUW8YdJwDN/ZrCxVU+22LZNKiIIRo\nI4S4LIS4JoQY85Lv5xdC/CGEOCOEuCCEGGjKPMor+vsrOPEbNHgfWk1WTe2UzHPvBZ3mat1V1w6A\nxHi9EykvMFlREEJYAzOBtoAr0EsI4frCZe8BF6WUtYBmwA9CCDU2YQkOTocDP4DnAGj5lSoIivG4\ndYc3f4Ar22DjMDAk6p1IeY4pJ5rrANeklNcBhBCrAB/g4nPXSMBBCCGAfEAYkGDCTEp6nPgddo2H\nGl3gzR9VQVCMz3uQNum8a4J2Cl+76er/MwthyqJQCgh+7vMQoO4L18wANgN3AAegh5RSLWbW09m1\nWivkSq2123w1h6CYSqOPtGWqB3+EXI7QcpIqDBZA7yWprYHTwGtABWCnEOKAlPLJ8xcJIYYAQwCc\nnZ3NHjLHCNgKG4dqR2d2XwzWtnonUrK7FuMgNgIO/wL2jtBklN6JcjxTTjTfBso893nppK89byCw\nQWquATeAqi8+kJRynpTSS0rpVaSI2kFrEtf3ahN/JWpBr5Vgm1vvREpOIAS0/Q7cesLfk+HYXL0T\n5XimLAongEpCiHJJk8c90YaKnhcEtAAQQhQDqgDXTZhJeZngE7CyNxSuAH3Xq7MQFPOysgKfmVC1\nnbYE+vQKvRPlaCYrClLKBGAEsAO4BKyRUl4QQgwTQgxLuuwroIEQ4hywG/hUSqmObjKn0KuwvCvk\nK6qdp5ynkN6JlJzI2kbbGFm+GWx6D67s0DtRjiVkFute6OXlJf38/PSOkT1Eh8H81yEmXDtvt6CL\n3omUnC42Eha9AY+uw6C/oNiLq9iVjBJC+EspvdK6Tu1ozqkS42FtfwgP1o7PVAVBsQS58kHPlVr7\n7ZU91JnPOlBFISdKbl9xYz+0/xnK1tc7kaL8v/yloNcKiHwAq/tCQqzeiXIUVRRyouO/gd8CaPgB\nuPfWO42i/FcpT+g4C4KOwJaP1SE9ZqT3PgXF3K7thu2fQpU3oMV4vdMoSspqdIGHV2DfFChSBRqO\n1DtRjqCKQk7y8DKsHQhFXaHzPLVbWbF8TT+FhwGwcxw4VYIqbfVOlO2p4aOcIjoMVvTQzkLotVLt\nRVCyBisr6Dhb21S5fjDcv6B3omxPFYWcICEO1rwFT25DzxVQQLUKUbIQuzzaGxm7fLCiJ0Q+1DtR\ntqaKQk6wbTTcPKAdklOmjt5pFOXVOZbUCkPUA1jdR3ujo5iEKgrZ3ZnV4L9QW2lUq6feaRQl40p5\naCuSgo/B7ol6p8m2VFHIzkKvwZaPwLk+vDZO7zSKknk1uoD3O3BkBlzepneabEkVhewqPkbremqT\nC7r8rvWWUZTsoNVkKF4TfIdDeIjeabIdVRSyq7++gPvnoNMcbYeoomQXtvbQbbHWqmXdIEhUhzUa\nkyoK2dEFXzgxHxq8D5Vb651GUYyvcAWtRUvwUdjztd5pshVVFLKbsBuw+X0o5aXmEZTsrWZX8HhL\nO87z2i6902QbqihkJwlxsG6gdppV1wXaRjVFyc7aTNV26G8YChH39E6TLaiikJ3smgB3TmmnWBUs\nq3caRTE9uzzQdSHER2s7ng2JeifK8lRRyC4CtsLRmVBnKFRrr3caRTGfolXhjWnaBs390/ROk+Wl\nuygIIQoKIaoLIcoLIVQxsSSPg7XleSVqQauv9E6jKObn3hvcemodVW8c0DtNlpbqi7sQIr8Q4vOk\nM5SPAnOBNcAtIcRaIURzc4RUUmEwwMah2m1z14XavgRFyWmEgDd/gELlYcM78PSx3omyrLTe8a8D\ngoHGUsoqUspGUkovKWUZYArgI4QYZPKUSspOzIdbh6DtFG2ZnqLkVLnyQZf52oltO77QO02Wleo2\nVylly1S+5w/4Gz2Rkn5hN2DXeKjYEtz76J1GUfRXsjY0+hAO/ADVO0KlFF/ClBSka25ACGH7kq85\nGT+Okm4Gg7YfwcoG2k/Xbp8VRdEO5ilSFTaPhJhwvdNkOWnNKTQXQoQAd4UQfwkhXJ779l+mDKak\nwX+Bttqi1WTIX1rvNIpiOWxyad1UI+/BX1/qnSbLSetO4TugtZTSCZgH7BRC1Ev6nnprqpd/bsFf\n46B8c21Hp6Io/1bKExqMhJNLtHPJlXRLqyjYSSkvAEgp1wEdgcVCiI6ANHU45SWk1IaNhNAOzVHD\nRorycs0+A6fKScNIT/ROk2WkVRTihRDFkz9JKhAtgAlAJRPmUlLivwhu7NP2IxQoo3caRbFctvbg\nMwsi7sBO1QcsvdIqCmOAYs9/QUoZAjRDW5KqmNPjIG2MtFwT8ByodxpFsXxlvKH+e9rpg4F79E6T\nJaRaFKSUu6SUZwCEEHZCCDchRE0gWkqp+tWak5TabbCU0GGGGjZSlPRq/gUUrqj9/MRG6J3G4qV3\nSeqbQCDwCzADuCaEaGvKYMoLTi2F63ug5UTV7E5RXoVtbq1JZHiw1jRSSVV6exj9ADSXUjaTUjYF\nmgM/mS6W8i/hIdoOTZfG4KU2kCvKK3OuB/WGax0AbuzXO41FS29RiJBSXnvu8+uAug8zl22fakcP\ndvgFrFQvQkXJkNfGQsFy8MeHkBCrdxqLld5XGD8hxFYhxAAhRH/gD+CEEKKzEKJzSn9ICNFGCHFZ\nCHFNCDEmhWuaCSFOCyEuCCH2ZeDvkL0F/g0BW6DJJ1qzL0VRMsYuj9ZiOywQjs7SO43FSm9RsAfu\nA03RVh49BHID7YF2L/sDQghrYCbQFnAFegkhXF+4pgAwC+ggpawOdHv1v0I2lhCn3SUULKedt6wo\nSuZUeh2qvAH7vocnd/ROY5FSbYiXTEqZkfWPdYBrUsrrAEKIVYAPcPG5a3oDG6SUQUnP8yADz5N9\nHZ8LoVeg12rVEltRjKX1NzCzrrZ3oct8vdNYnAwNUAsh3hVC9BBCpFZUSqG13U4WkvS151UGCgoh\n9goh/IUQL+3ZIIQYIoTwE0L4PXz4MCORs56Ie7B3KlRqBVXa6J1GUbKPQuWg4Ug4txZuHdY7jcXJ\n6KylABoBGzL5/DaAJ/Am0BoYK4So/OJFUsp5Sec4eBUpUiSTT5lF7JoAibHQRu0RVBSja/QxOJaG\nraPVuc4vyFBRkFLOlFK+L6XskMplt4Hn+zCUTvra80KAHVLKKCllKLAfqJWRTNlK0DE4s1LbiakO\nzlEU47PLA60nw/1z4LdA7zQWJcPrG4UQac0znAAqCSHKCSHsgJ7A5heu2QQ0EkLYCCHyAHWBSxnN\nlC0YEmHbKHAoCY0/0TuNomRfrh21vT9/T4aoR3qnsRiZWfQ+MbVvSikTgBHADrQX+jVSygtCiGFC\niGFJ11wCtgNngePAfCnl+UxkyvpOLoG7Z7SGd7ny6Z1GUbIvIeCN77XWF39/pXcaiyGkTLkDthDi\nbErfAipLKc2+JMbLy0v6+fmZ+2nNIzoMfvWEotVgwJ+qv5GimMO2MXBsDgzZCyXd9U5jMkIIfyml\nV1rXpbUktRjaBPA/Lz4+oKbtjW3PNxDzGNpOVQVBUcyl2RhtJdK20fD2jhz/s5fW8NEWIJ+U8tYL\nHzeBvSZPl5PcOw9+v2u9jYrX1DuNouQcuQvA6xMg+BicXa13Gt2l1Tp7kJTyYArf622aSDmQlNq7\nFPsC0PxzvdMoSs7j3kc7wnPnuBx/Slu6J5qFEB5CiJFCiPeFEB6mDJXjXNwEtw5Bi3GQp5DeaRQl\n57GygrbfQ+R9OPij3ml0ld7zFMYBi4HCgBOwUAjxpSmD5RiJCbDnayhSFTxeuqFbURRzKO0JNbvB\n0TkQcV/vNLpJ751CH8BbSjleSjkeqAf0M12sHOTsaq2/0WtfgpW13mkUJWdr9hkkxsGBaXon0U16\ni8IdtE6pyXLx393JyqtKiIW9U6Bkbaj60maziqKYU+EK4NEP/BbCP7f0TqOL9BaFcOCCEGKREGIh\ncB54LIT4RQjxi+niZXP+iyE8SJtLyOHL4BTFYjQZDcIK9k3VO4ku0tU6G9iY9JFsr/Gj5DBxUbD/\ne22bffnmeqdRFCVZ/lJQ5x3tIJ6GH0CRKnonMqv0nqew2NRBcpxjcyHqAfRYpu4SFMXSNPoI/Bdp\ni0C6L9E7jVmlOnwkhPhDCNFeCGH7ku+VF0JMEkK8bbp42dTTx3BoOlRuA8519U6jKMqL8jppXYov\nboI7p/VOY1ZpzSm8AzQGAoQQJ5LOaf5bCHEDmAv4SylV39lXdfhXiAnXVhwpimKZ6r8HuQtqXVRz\nkFSHj6SU94DRwGghhAtQAngKXJFSRps8XXYU+QCOzoYaXVQ7C0WxZPb5tWGkneO0E9rKNtA7kVmk\na05BCPE+sDSp55GSGQd+hIQYaKbaWVgyKSWhkXGERsYS/jT+2ceTF36fmHKTYQTgYG9D/ty2//lw\nzG1L4Xx2FHWwx9pKzSlZLO934Mgs2D0JBm7LEfN/6V19VAzwE0KcBBagnZaWyo+D8lKPg7Wmd+69\nwami3mlyvLgEA0Fh0QSHRRP03Efy59FxLz+mUQhwtLfFMbcNtlYpj8AmSklkTALhT+NJMLz8x8XO\n2orSBXNTplAenJM+kn/v4pSHPHbp/RFVTMIuDzT5BLZ+Atd2Q6XX9U5kcqmep/CvC4UQQCtgIOAF\nrAF+l1IGmi7ef2Xp8xQ2jdB2ML9/EgqUSft6xWjiEgxcuR/B+dvhnL0dzvnb4QTcjSAu0fDsmty2\n1v96UXYulJuijvb/eYfvkMsGKyvBvah7hMeGp/ic9jb2lHUsi5SS6LhEHj+NJzz6/+80HkXFEhz2\n9FkRuvUoiicxCc/+vJWACkXyUbNUfmqUyo9b6fy4lnRUhcLcEuJghqfWsHLIPq1PUhZkrPMUnpFS\nSiHEPeAekAAUBNYJIXZKKUdnPGoOEXoVTq+AOkNUQTCDhxGxHA4M5fiNMM69UAAc7G2oUTI/Axu6\nUKW4A2UL58G5UF6c8tkh0jE88DThKTP8Z7Ds0jIM0pDqta87v87ndT+nSJ4i5M1lQ6kCuVO9Pjw6\nXisQYVFcvR/J+dvhHLgWyoZTWgOB5wuFp0tBGlV0wrlQnnTlVjLIxk4b7vUdBpc2Q/WOeicyqXTd\nKQghPgDeAkKB+YCvlDJeCGEFXJVSmu10+Sx7p7B2IFzZAR+chnxF9U6T7UTHJXDsRhiHroZy8Foo\nAfciAHDIZfPsXXaNUvmpWSo/zoXyYJXBcfzjd48z/vB4QiJD6Fq5Kw1LNkzx2muPr/Hb2d/IZZOL\nUV6j6FixY4ZfvO8/ieFcSDjnku5yzt4O52FELAClC+amcSUnGlZ0okEFJwrltcvQcyipMCTCrPqA\nhOFHwDrr3a2l904hvUVhIrBASvmfZiBCiGpJZy2bRZYsCg8uwax60Ph/WksLxSiu3I/grwv3OHA1\nlJNB/xCfKLGzscLbpSANKzrRqKIT1UvmN8pEbkRcBD/4/cD6q+txdnBmQoMJeBf3TvPP3Qy/yfjD\n4zn54CT1S9RnfIPxlMpXKtN5pJTcCI3i4LVQDl4N5UjgIyJiExACqpd0pGFFJ1pWK4aHc8EMF0Dl\nBRc3w5p+0Gke1Oqhd5pXZuyisFRK2S+tr5lDliwKvu/ChY3w0QV1XkImXbkfwZ9n7/LnubtcexAJ\naC+CjSppRcCrbCFy2xm32+ze4L18deQrQmNC6e/an+Huw8ltk/ow0PMM0sCay2v4yf8nJJIPPD6g\nZ5WeWBuxK25CooGzt8Of3SklF8nijva0qVGcN91K4KkKROYYDDC7PljZwLCDWW4lkrGLwkkppcdz\nn1sD56SUrpmL+eqyXFEIvw0/1wKvt+GN7/ROkyW9WAiEgDouhXjTrQRtqhenqKN92g+SAWExYUw5\nNoVtN7dRqWAlvmrwFdWdqmf48e5G3mXi0Ykcun0I9yLuTGwwkfIFyhsx8f+LiInn74AH/Hn2Lnuv\nPCQuwUAxx1y0rVFCFYjMOLUcNr0LfddDxay1EskoRUEI8RnwOZAbSN6sJoA4YJ6U8jMjZH0lWa4o\n/PWlts555CkoWFbvNFnGP1FxrD8Zwhq/YK7cf6EQ1ChOUQfTFALQhma23tjKlONTiIyPZKjbUAbV\nGISt9X+6vWTosbdc38LUE1OJjo9mWK1hDKwxEFurzD92Sl5WIIo72tPFsxQ9vZ0pUyiPyZ4720mI\ng5/dwKkS9P9D7zSvxNh3Ct/qUQBeJksVhZhw+LE6VG4FXVU3kLRIKTl+I4yVx4PYev4ecQkG3MsU\noLNHKZMXgmT3ou4x+ehk9oXsw83JjYkNJlKxoPH3lIQ+DWXK8SnsuLmDKgWrMKnhJFwLm/7GO7lA\nbDp9h72XHyCBxpWK0LtOGVpUK4atddZcbmlWh37WdjkP2audhZJFGOtOoaqUMiClM5mllCczkTFD\nslRRODgddo3X1jaXdNc7jcVKvitYeTyIwIdRONjb0Ll2KXrWcaZaCUezZDBIA+uurONH/x8xSAPv\n136f3lV7G3Xc/2V2B+3m66NfExYTRv/q/Rleazj2NqYvfgB3Hj9ljV8wq08Eczc8hiIOuejuVVrd\nPaQlJhx+qqENH3VbqHeadDNWUZgnpRwihNjzkm9LKeVrmQmZEVmmKCTEwnQ3KFoV3tqkdxqLFHDv\nCfP2X2fL2bvEJRjwcC5ArzrOtHMrafTJ4tTcenKLCYcn4Hffj7ol6jK+/njKOJhvL8mTuCf84PcD\nG65uwMXRhQkNJuBZzNNsz5+QaGDflYesPB7E3wHa3UOTSkUY0qQ8DSoUVnsgXmbnOK2x5fsnoVA5\nvdOki9GGj5L2ItSXUh4yVrjMyDJF4dQy2PQe9NsIFcxeOy2WlJITN/9hzr5A/g54QB47a7p6lqZ3\nXWeqFjfPXUGyBEMCyy4uY8bpGdhZ2THKO3N7CTLr6N2jTDg8gduRt+lRpQcfenxIPrt8Zs1wN/wp\nq08Es/xYEA8jYqlZKj/Dm1WgdfXiqkfT857chek1wWsgvPG93mnSxdhzCqeklBYxeJYlioLBoO1L\nsLGDoQey3NI1UzAYJLsDHjB77zVOBj2mUF47BjZwoV/9shTIY/7NVpfDLjP+8HguPLpA8zLN+bLe\nlxTNo/+mwuj4aH499SvLLy2nWN5ijKs3jsalG5s9R0x8IhtP3Wbe/uvcCI2inFNe3mlcns4epbC3\nNd9dnEXzfQ/Or9eWmuctrHeaNBm7KEwDjgAb9G6ElyWKwuVtsLIndJ4Pbt30TqOruAQDm8/cYe6+\nQK4+iKR0wdwMaVKebp5lzDpE9CxPYhy/nfuN+Wfn45jLkc/qfkbrsq0tbojkzMMzjDs0juvh12lf\nvj2jvUdTwL6A2XMkGiQ7Ltxjzr5AzoaEU8QhF283LEefes442ptuxVSW8CAAZtWFZp9BszF6p0mT\nsYtCBJAXredRDNqyVCmlNO/9PlmkKCxoo+1PGHkSjLCMMSsyGCSbz9zhh52XCQ57StXiDgxvVoE3\na5bARqcVLmcenmH8ofEEhgfSrnw7PvX+VJcX2vSKS4xj3tl5/H7ud90LmJSSw4GPmLMvkANXQ8mf\n25bhzSowoIFLzr5zWNETgo9pdwt2lj05b9SiYEksvigEH4ffW0KbKVBvuN5pzE5Kyd7LD5m6PYCA\nexG4lnDkk9aVaV6lqG7vxqPjo5lxegbLLi6jaJ6ijKs/jialm+iSJSMuh11m3OFxXHx00SKGus6F\nhPPjzsvsufyQYo65+PD1ynTzLK1bsdfVrcOwsC28MQ3qvKN3mlQZ+07hpT9BUsr9afy5NsDPgDUw\nX0o5JYXrvNGGp3pKKdel9pgWXxRW9YGbB7V3DrnMO0moN/9bYUzddpnjN8MoWzgP/2tVhXY1S+i6\nc9YSJm+NIcGQwNKLS5l5eiZ2VnZ84v0JnSp20nXY69j1R0zdHsDJoMeUd8rLJ62r0LZGcYsbijMp\nKbU3gVEPYYS/RTfKM3ZReH7rnj1QB+185hSX1SS1wrgCtARCgBNALynlxZdctxNtWGpBli4Koddg\nhpd2KEcCeHZTAAAgAElEQVQOOn/58r0Ivt9xmV2X7lPEIRcjW1Sip3cZXTdCPYl7wo9+P7L+6nrK\nOpZlQv0JeBVP8+fB4t0Mv8mEIxPwv++vy/LZF0kp2XXpAd/vCODK/UjcSufn0zZVaVjRSbdMZnfp\nD1jdF7ouhBqd9U6TIpMOHwkhygDTpZRdUrmmPjBBStk66fPPAKSU375w3YdAPOANbMnSReGPD+D0\nSu0uIV8RvdOY3D9RcXy34zKrTgSRz86GYc0qMLChi+6HwPwd9DeTj07mUcwj+rv25133d822Icwc\n9Npol5pEg2Tjqdv8tPMKtx8/pWnlIkzoUJ1yTnl1y2Q2hkSYWQfs8mm7nC30Tim9RSGjb+VCgGpp\nXFMKCH7hz/yrZ7AQohTQCZidwRyWI+K+VhDce2f7gpBokCw/dovmP+xljV8wAxuUY//o5rzXvKKu\nBSH0aSif7PuED/Z8QEH7gqx4YwUfe32crQoCgJWwonuV7vj6+OJZzJPvTnzHW9vfIvCxWQ9B/Bdr\nK0FXz9Ls/l9TvnyzGidv/UPrn/bz/Y4AouMS0n6ArMzKGuqPgLun4eYBvdNkWrp+goUQvwLJtxRW\ngDtgjBYX04FPpZSG1MYhhRBDgCEAzs7ORnhaEzg+FxLjoMH7eicxqTPBjxm76TxnQ8KpW64Qk3xq\nUKW4g66ZXmwyN8J9BG/XfNukTeYsQfG8xZnVYhZ/3viTqcen0u2Pbgx1G8rbNd42SvO+jLC3tWZw\n4/J0cC/JlK0BzNwTiO+pO4xt50rr6sWy73xDrV6w52utL1K5rLOI4WXSO6fQ/7lPE4Cbae1wTs/w\nkRDiBtryVgAntE6sQ6SUvik9rkUOH8U/hR+qQrnG0GOZ3mlMIiwqju93BLDqRDBF8uXiizer0aFW\nSd1/yO9G3mXS0UkcvH0QtyJuTGowiQoFzHYQoMV49PQRU45PYfvN7VQuWJlJDSZlqs23sRy/Eca4\nTecJuBdBk8pFmJidh5T2fw9/T4b3jkORKnqn+Q+jzykIIeyAqmh3DJellHFpXG+DNtHcAriNNtHc\nW0p5IYXrF5FV5xTOrIaNQ7RWuln8XcKLDAbJqhPBfLcjgIiYBAY2cOGD1yvhoPPGJYM0sPbyWn70\n/xGJZGTtkfSq2kvXcXVLYInzKQmJBpYcucVPO68Qm2DgnSblGNG8ki6bF00q8iH8WE07h73NN3qn\n+Q9jrz56A5gLBKK9sy8HDJVSbkvHn5uOtiR1gZTyayHEMAAp5ZwXrl1EVi0KC9pC5D2tOVY2uj2+\nGRrF6HVnOX4zzGKGiuDfR1zWK1GP8fXHU9qhtN6xLMbzK69e5ehQU3sQEcOUrQFsOHUbl8J5+L5b\nLbxdstlJhGv6w4198HEA2FrWXJaxi0IA0E5KeS3p8wrAn1LKqplO+oosrig8vAIzveH1idDoQ73T\nGIXBIFl85CZTtwdga23F2HaudPMsrftQUYIhgSUXlzDr9CzsrO0Y5aVvAztL9/weje6Vu/OR50cW\nsUfjcGAon64/S8g/TxnYoByjWlfJPncNgXtgaUfo8jvU7Kp3mn8x9uqjiOSCkOQ6EJGhZNnNycVg\nZQvuffROYhQ3Q6PoOe8oE/+4SP3yhdn5UVO6e5XR/YX3cthl+mztw0/+P9GoVCM2+WyiUyV9N29Z\nunol6rGhwwb6ufZj7ZW1dNzUkf0hqe43NYsGFZzY/kET+tUry4JDN2j7835O3AzTO5ZxlGsKBV3A\nf5HeSTIsvXcKs4GywBq0OYVuQBCwC0BKucGEGf/Fou4UEmL/f4K5+xK902TKi3cH49tXp4tHKd1f\ndOMS45h7di4Lzi3AMZcjn9f9nFZlW+meK6t5se/TaO/RFLQvqHcsjgQ+YvT6M9nrruHAD7B7krbD\n2cn4p/ZllLGHj1I7XkhKKd9+lXCZYVFF4dw6WD8oy5+Z8PzcQfMqRfi2sxvF8+s/Hnr6wWnGHx7P\n9fDrdKjQgVFeoyy6gZ2ls9QOsVGxCXy3PYDFR25lj7mGiPvwkyvUexdafaV3mmdUQzxzWNQOHgfB\nyNNglfWagUkpWesXwvjNF7CxFhZzd2ApZwpkV5Z6lsTzdw3Dmlbg45aVs+6Z0av6QNBR+PiSdq6K\nBTD2nUI54H3Ahec2vEkpO2QiY4ZYTFF4FAi/esBrY7VeR1lMREw8X2w8z+Yzd2hQoTA/dne3iLuD\n5ydHe1bpyYeeH5LXNpuua9fRi6fOWUKDPdDuGib/eZGVx4Op7VyAX3rWzprnRV/dBcu7QLdFUL2T\n3mkA4xeFM8DvwDnAkPx1KeW+zITMCIspCjvHweEZ8PFFcCiud5pXcib4Me+vPMXtx0/5uGVlhjWt\noPtRi8+fU1zWsSwTG0w06znFOVXQkyDGHx6v2/nUKdly9g6frT8HAqZ2ceONmiX0jvRqDInwszsU\nLm8xZ7Qbuygck1LWNUqyTLKIopAQp21Sca4HPZfrm+UVGAyS+Qev8932yxRztOfnnu54WcDYbfKG\nq7CYMAZUH8CwWsN033CVk1higz2A4LBoRqw8xZngx/Su68y4dq5Z60Cffd9prS9GnoJC5fVOY/Ql\nqT8LIcYLIeoLITySPzKZMeu6vBWiQ8FzgN5J0i00MpaBi07wzdYAWlQrytaRjXUvCI+ePnrWwK6Q\nfSGWv7mcDz0/VAXBzJ5vsOdVzMsiGuwBlCmUh3XD6jO0aXlWHAuiw4yDXLmfhVbC1+4LwgpOLtU7\nyStJ753Ct0A/tB3NycNHMrXzFEzFIu4UlnSER9fggzNah0QLd/haKB+sPk3403jGtnOlb11nXceO\nX2xgN7zWcAbUGJDtG9hlBVLKZw32ouKjGOI2hEE1BunWYC/ZvisP+d+a00TGJjC+fXV6euu/dyZd\nVvSE2/7aMLPO/4bGvlPoBpSXUjaVUjZP+si6azAz45+bcH0P1O5n8QVBSsmcfYH0/f0Y+XPbsum9\nhvSrV1bXH6a7kXd5d/e7fH7wc1wcXVjXfh3vuL2jCoKFEELQrnw7fH18ed35dWaenknPP3tyIfSl\nLcvMpmnlImz9oDHeLoX4bMM5Rq87S0x8oq6Z0sVzAEQ9gCvb9U6SbuktCucBtUAc4OQS7Zawdl+9\nk6QqOi6BEStPMWVbAG1rlGDTew2pVsJRtzwGaWB1wGo6buqI/31/xtQZw+I2iylfQP+xVuW/Cucu\nzHdNv+OX5r/wOOYxvbf25ke/H4lJiNEtU1EHexYPrMPI1yqy1j+EHnOPcDf8qW550qXi6+BYKkvt\ncE5vUSgABAghdgghNid/mDKYRUqMh1PLoFIryF8q7et1EvQoms6zDrP13F0+bVOVGb1rkzeXfoff\n3Ay/ycDtA5l8bDK1itRio89G+lTro/tEppK25s7N2dhxI50qdmLhhYV02dyFE/dO6JbHykrwcasq\nzOnrybUHkbT/9SDHb1hwiwxrG+0N5LXd8M8tvdOkS3rnFJq+7Os5bknqpS2wug/0WgVV2uqTIQ37\nrzzk/ZWnAPilV22aVtbvFLgXG9iN9h6NTwWfrDEWrPzHsbvHmHB4AiGRIRbRYO/q/QiGLvUnKCya\nce1ddR8aTdHjYJheE5qMgte+0C2G2tFsCsu6wv3z8OF57R2ABZFSMnf/db7bHkDlYg7M7edJ2cL6\nbfq6HHaZsYfGcinsEi2cW/BF3S8okid7H1OaEzxNeMqMUzNYdmkZRXIXYVz9cTQprd8ZIk9i4vlo\n1Wl2Bzygm2dpvupYwzKXrVrAa4dRJpqFEAeTfo0QQjx57iNCCPHEWGGzhMfBcG2XNsFsYQXhX/MH\nNUuw4d0GuhWEuMQ4fj31Kz239ORB9AN+bPYj05tPVwUhm8htk5tR3qNY2nYpDnYOvLf7PcYcGMM/\nMf/oksfR3pbf3vKy/HkGzwEQcReu7dQ7SZpSLQpSykZJvzpIKR2f+3CQUuo3a6mHU0lrjT366Zvj\nBffCY+g6+wjbzt1lTNuqzOhVmzx2+hSt0w9O0+2Pbsw7O483yr/Bpo6baFm2pS5ZFNNyK+LGmnZr\nGF5rODtu7qDjpo5sv7EdPUYekucZ5vZLnmc4xNmQx2bPkarKrSFfcfBLrbeoZcii3abMTEo4uxrK\nN4MCznqneebS3Sd0mnWIW4+i+H2AN8OaVtBlTDU6Ppqpx6fy1ra3eJrwlDmvz+HrRl+TP1d+s2dR\nzMfW2pZ33d9ldbvVlMxbklH7RzFyz0geRD/QJU/r6sXxfa8h9rZW9Jh7lJ0X7+uS46WsbcG9lzba\nEPVI7zSpUkUhPe6d1fYn1Oisd5Jn9l15SLc5R5AS1g5rQPMq+nS5PHznMJ03d2bZpWX0rNqTjT4b\naViqoS5ZFH1ULliZZW8s4xOvTzh65ygdfTuy7so6Xe4aKhVzYOO7DalcLB9Dlvqx8NANs2dIUfVO\nIBPh8p96J0mVKgrpccEXhDVUeVPvJACsPB7E24tOULpgbja+1wDXkuYfyQuPDWfsobEM3TkUWytb\nFrdZzOd1P1cdTXMoaytr+lfvz/oO66lauCoTj0zknb/eIfhJsNmzFHHIxaoh9WlZrRgT/7jIxD8u\nkGiwgAU1xd20U9ku+OqdJFWqKKRFSrjoC+WaQN7CukYxGCRTtwfw2YZzNKroxNph9SmRP7fZc+y+\ntZuOmzryR+AfDK45mHUd1uFRLOe2wlL+n7OjM/NbzWdc/XFceHSBzps7s/jCYhIN5t19nNvOmtl9\nPXm7YTkWHrrJsGX+RMclmDXDfwgBrh3hxj6Itty9FaoopOX+BQi7Dq4+usaIiU9k5KpTzN4bSK86\nzvze3wsHe/O2hgh9GsrHez/mw70f4pTbiRVvruADjw/IZZ3LrDkUy2YlrOhWuRsbfTZSt0RdpvlN\no9+2flz956pZc1hbCca1d2VCe1d2X7pPr3lHeRgRa9YM/+HqA4YErammhVJFIS0XfbW2FlXb6Rbh\nn6g4+s4/xpaz2gqjbzrVwMaMJ1JJKdkcuBkfXx/2Bu9lZO2RrHhzBa6FXc2WQcl6iuctzq+v/crU\nxlMJiQih+5buzD49m/jEeLPmGNCwHHP7eXHlfiQdZx7iqp6dVkvW1harXLSMMxZeRhWF1Eipjf+5\nNIJ8+qyzvxceQ7e5Rzh7O5wZvWubfYXRncg7DN81nC8OfkH5/OVZ10E1sFPSTwjBG+XfwLejL63K\ntmLWmVl039Kd86HnzZqjpWsx1gytT1yigW5zj3A6WKclq0JodwuBe+CphS2bTaKKQmoeBsCjq7oN\nHd0MjaLL7MPcC49hydt1aOdW0mzPbZAGVgaspNOmTpx8cJLP6nzG4raLKZ9fNbBTXl0h+0JMbTKV\nGa/N4EncE/ps7cO0E9N4mmC+jWY1S+dn/bAGONrb0ue3oxy+Fmq25/4X145giIfL2/R5/jSoopCa\nC76AgKrtzf7Ul+4+oeucI0THJbDinbrUK2++Se7kBnbfHPsG96LubPTZSO9qvbES6n8XJXOalmmK\nr48vXSp1YfHFxWZvsOdcWDu4p3TBPAxYeIIdF+6Z7bmfKeUJjqUtdghJ/ZSn5uImKNsQHIqZ9Wn9\nb/1Dj7lHsLESrB1WH7fS5ulanmBIYP65+XTZ3IVrj68xueFk5rw+h1L5LLcjrJL1ONg5MK7+OH5v\n9TsAb+94m4lHJhIRZ56x/qKO9qweWg/Xko68u/wk6/1DzPK8zzwbQtoNMZbXLUgVhZQ8vAwPL5l9\n6Gj/lYf0nX+MQnntWDe8PhWLOpjleQPCAuj9Z29+PvkzTUo3YVPHTfhUVB1NFdOpU6IO6zusZ0D1\nAWy4uoGOmzqyL9g8jZcL5LFj+eC61CtfiP+tPWP+TW6uPpAYZ5GH76iikJKLmwEB1cw3dLT13F0G\nLT6Bi1Ne1g5rQOmCeUz+nLGJsfxy8pd/NbD7qflPOOV2MvlzK0pum9z8z+t/LGu7DEc7R0b8PYLR\n+0cTFmP6dfx5c9mwYIA3ratrm9ym77pivl3Ypb3BoaRFDiGpopCSi77gXA8cS5jl6dacCGbEipO4\nlS7AqiH1KOJg+rX/yQ3sfjv3G+3Kt1MN7BTd1CxSkzXt1vCu+7vsvLWTjr4d2Xp9q8lfpHPZWDOz\ntwddPUszfddVJm25iMEcu5+trMC1A1zdCbE6LpF9CVUUXib0mtb73ExDR0uO3GT0+rM0qlSEpYPq\nkD+3aZd7RsdH8+2xb3lr21vEJsQy9/W5TG40WTWwU3Rla23L8FrDWdtuLWUcyvDpgU95/+/3uRdl\n2slgG2srvuvi9mz382cbzpmnMLj6QGIsXNlh+ud6BaoovMylpFu6ah1M/lRLjtxk3KYLtHQtxvy3\nvEze9vrw7cN02tSJlQEr6VW1Fxt9NtKgVAOTPqeivIqKBSuypO0SRnmN4tjdY3Ta1Im1V9ZikAaT\nPaeVlWBsu2q8/1pFVvsFm6cwlKkL+YpZ3BCSSV+BhBBtgJ8Ba2C+lHLKC9/vA3wKCCACGC6lPGPK\nTOlywRdK1zH5OczJBaGVazFm9PbAzsZ0NTo8NpzvT3zPpsBNuDi6sLjtYmoXrW2y50sWHx9PSEgI\nMTH6HfiuGJ+9vT2lS5fG1tY0d7XWVta8Vf0tmjs3Z+LhiUw6MoltN7Yxof4EnB1N075eCMHHLSsj\ngF/+vgbAt51rYmVlosUWVtbaG89TyyAuCuwso5mkyYqCEMIamAm0BEKAE0KIzVLKi89ddgNoKqX8\nRwjRFpgH1DVVpnQJu661ym71tUmfxpwFYdetXUw+OpnHsY95p+Y7DK011Gz9ikJCQnBwcMDFxUWt\nZMompJQ8evSIkJAQypUrZ9LnKuNQht9a/caGqxuY5jeNLpu7MKL2CPpW64u1lfGP3RRC8FHLyoCZ\nCoOrD5z4Da7+pbXWtgCmHD6qA1yTUl6XUsYBq4B/DdJLKQ9LKZPP8TsKlDZhnvS5uFn71dV0Q0fm\nKgjJDew+2vsRRfMUZVW7VYz0GGnWBnYxMTEULlxYFYRsRAhB4cKFzXb3J4SgS+Uu+Pr4Uq9kPab5\nTaPv1r4ma7CXXBhGmmMoqWwDyFvEooaQTFkUSgHPN1MPSfpaSgYBL933LYQYIoTwE0L4PXz40IgR\nX+Kir7bj0EQnrJmjIEgp8b3mi4+vD/uC9/GBxwcsf3M5VQtVNfpzpYcqCNmPHv9Ni+Utxi/Nf+H7\nJt9zJ+oO3bd0Z9bpWSZpsGe2wmBlrS17v/IXxEUb//EzwCImmoUQzdGKwqcv+76Ucp6U0ktK6VWk\niAkb0/1zC+6cMtmqI3MUhNuRtxm2axhjD42lYoGKrOuwjsE1B6sGdi8xbtw4du3aleo1mzdvZsqU\nKaleo5iPEII25drg6+NLa5fWzD4zm+5bunP24VmTPJdZCoOrD8RHaUd1WgBTTjTfBso893nppK/9\nixDCDZgPtJVS6nt46aXkoSPjFwVTF4TkBnY/n/wZgeDzup/To0oP1a8oFZMmTUrzmg4dOtChg+lX\noSmvpqB9QaY0nsIb5d5g0pFJ9N3al76ufRnhPoI8tsbb9GmWOYayjSBPYW0IyYTD1ullyleME0Al\nIUQ5IYQd0BPY/PwFQghnYAPQT0p5xYRZ0ueCL5Rw147MM6JVx4NMWhCuh19nwPYBTDk+BY+iHmz0\n2Uivqr1UQXjOV199RZUqVWjUqBG9evVi2rRpDBgwgHXr1gHg4uLC+PHj8fDwoGbNmgQEBACwaNEi\nRowYoWd0JRVNSjfB18eXbpW7sfTiUrps7sKxu8eM+hwv3jGM33zBuJvqrG2081qubId4/VfpmexO\nQUqZIIQYAexAW5K6QEp5QQgxLOn7c4BxQGFgVtIYZYKU0stUmVL1OBhu+0GL8UZ92C1n7/DZxnM0\nq1LE6AUh3hDP4guLmX16NvY29nzd6Gval29vsWP4E/+4wMU7xm0A5lrSkfHtq6d6zYkTJ1i/fj1n\nzpwhPj4eDw8PPD09/3Odk5MTJ0+eZNasWUybNo358+cbNatiGvns8jG2/ljalGvDhMMTGPzXYLpU\n6sL/vP6Hg51xeoclF4bYRANz913HMbcNo1obcY7O1QdOLtaa5FXV9yx4k+5TkFJuBba+8LU5z/1+\nMDDYlBnSLWCL9qsRh472XH7AR6tP4122ELP7eBq1IFx6dInxh8dzKewSLcu25PO6n6t+RSk4dOgQ\nPj4+2NvbY29vT/v2L+9n1blzZwA8PT3ZsGGDOSMqRuBd3Jv1HdYz6/QsFl9czIGQA4ytP5ZmZZoZ\n5fGFEIxpU5UnTxOYuScQB3tbhjWtYJTHplwTyF1QW/2YnYtClnLjABSqAIWN8x/5+I0whi/zp0px\nB+YP8CK3nXHWVMcmxjLnzBwWnl9IQfuC/NTsJ14v+7pRHtvU0npHr7dcubSlutbW1iQk6HzIu5Ih\n9jb2fOz1Ma1dWjP28Fje//t92rq0ZUzdMRSyL5TpxxdCMLljDSJjE5iyLQAHexv61C2b+eDWtlC+\nOdw8mPnHyiQ16AzasZvBx7QGeEZwLiSctxedoFSB3CweWAdHe+Os/Dn14BRdN3dl/rn5tK/QHl8f\n3yxTEPTUsGFD/vjjD2JiYoiMjGTLli16R1JMrLpTdVa/uVprsBe0Ex9fH/68/qdR5gKsrQQ/dq/F\na1WL8qXveTad/s/6mYxxrgdPQiDczOc7vEAVBYBHgRAdCmXqZPqhrj2IoP/C4+TPbcuywXUpnC/z\nG8Wi46P55tg39N/Wn7jEOOa+PpevGn6lGtilk7e3Nx06dMDNzY22bdtSs2ZN8udX/3bZ3fMN9pwd\nnBlzYAwj/h5hlAZ7ttZWzOrjgbdLIf635gy7L93PfODk15+go5l/rMyQUmapD09PT2l0J5dJOd5R\nyvuXMvUwQY+iZN2vd0nPr3bKGw8jjRLtUMgh2WptK1lzUU357bFvZVRclFEe11wuXryodwQppZQR\nERFSSimjoqKkp6en9Pf31zlR1mcp/23TIyExQS4+v1h6LfWSdZfXlasDVstEQ2KmH/fJ0zjZ7pcD\nsvIXW+Xha6GZDBkv5eQSUv45KtO5Xgbwk+l4jVV3CgDBR8G+ADhVzvBDPHgSQ9/fj/E0PpFlg+vg\n4pS55lbhseF8efBLhu4aSi6bXCxuu5gxdcYYdQ12TjJkyBDc3d3x8PCgS5cueHh46B1JMaPkBnsb\nfDZQo3ANvjr6FYP/GkzQk6BMPa6DvS2L365DmUJ5GLz4BGeCH2cipA2U9tRej3SkigJA0DGtja1V\nxv45nsTE89aC4zyMiGXhQG+qFnfMVJydt7Qx0C3Xt/BOzXdY236tWTqaZmcrVqzg9OnTBAQE8Nln\nn+kdR9FJcoO9CfUncOnRJTpv7syi84tIMGR8YUGhvHYsG1SXgnnt6L/wOIEPIzMRsB7cOw+xmXiM\nTFJFIToMQi9neD4hLsHAsKX+XHsQydx+nng4F8xwlIfRD/loz0d8vPdj3RrYKUp293yDvfol6/OD\n/w/029qPK/9kfP9s8fz2LB9cFxsrQf8Fx3kQkcFNaGXqgkzU9kzpRBWFkBParxlYeWQwSEavO8Ph\nwEd819WNxpUy1pdJJjew2+TD/pD9fOjxISveXKFbAztFyQlebLDX448ezDw9k7jEuAw9XtnCefm9\nvzePIuMYtMiPqNgM3H2U8QYEBB/PUAZjUEUh6ChY2UDJVx9j/v6vy/ievsOo1lXo7JGxrt+3I28z\ndOdQxh4aS6UClVjXYR2Dag7CxkptIVEUU3u+wV6bcm2Yc2YOPbb0yHCDvVplCjCzT20u3AnnvRUn\nSUh8xdPi7PNDUVddVyCpohB8DIq7gd2rTeAuPXKT2XsD6V3XmXebvfqGN4M0sPzScjpt6sSZh2f4\nvO7nLGyzkHL5TXtoiaIo/1XQviDfNv6WmS1mEhEXQd+tffnuxHdEx796O+vXqhZjcsea7L38kC99\nz7/63ogydbQRDEPiKz+3MeTsopAQB7f9X3no6K8L9xi/+QItqhZlUofqr9xr6Prj6/Tf1l9rYFdM\nNbCzNL6+vly8eDHtC5VsJ7nBXvcq3TPVYK93XWfef60iq04E82tSd9V0c64HsU/gwaVXfl5jyNmv\nQvfOQUKMNrmTTieD/mHkqlPULJWfX3vXxsY6/f+E8YZ4fjv7G13/6MqNJzf4ptE3zG4xm5L5SmYk\nvWIiqRUF1f4i+8tnl48v633JgtYLsBJWDP5rMBMOT+BJ3Ks1c/y4ZWU6e5Tix51XWOsXnPYfSJb8\nehRs3G6v6ZWzi0LyeuB0FoUboVEMXuxHUQd7fh/gTR679I/7X3x0kd5/9uaXU7/QvExzfH18aV/B\ncjuaZjfLli2jTp06uLu7M3ToUBITE8mXLx9ffPEFtWrVol69ety/f5/Dhw+zefNmRo0ahbu7O4GB\ngTRr1owPP/wQLy8vfv75Z27evMlrr72Gm5sbLVq0IChIW+s+YMAAhg0bhpeXF5UrV37WTqNJkyac\nPn36WZZGjRpx5swZXf4dlPRLbrA3sMZANl7bSCffTuwJ2pPuPy+EYEpnNxpXcuKzDefYdyWdp0YW\ndIF8xXQrCjl7NjPoqHbspmOJNC8NjYxlwMLjSClZ/HYdnNLZviImIYY5Z+aw6MIiCtoXZHqz6bQo\n2yKzybOmbWO0uzNjKl4T2qZ+MtqlS5dYvXo1hw4dwtbWlnfffZfly5cTFRVFvXr1+Prrrxk9ejS/\n/fYbX375JR06dKBdu3Z07dr12WPExcXh56ctE2zfvj39+/enf//+LFiwgJEjR+Lr6wvAzZs3OX78\nOIGBgTRv3pxr164xaNAgFi1axPTp07ly5QoxMTHUqlXLuP8OiknY29jzsefHtC6rNdgbuWckbVza\nMKbOGArnLpzmn7ez0dphdJ97lHeX+bN6aH1qlEqjxYoQ2ryCTpPNOfdOIbkJXpm05xNi4hN5Z4kf\n98Jj+H2AN+XSuVv55P2TdPujG7+f/50OFTrg6+ObcwuCjnbv3o2/vz/e3t64u7uze/durl+/jp2d\nHUDDF2YAABQaSURBVO3atQO0dtk3b95M8TF69Ojx7PdHjhyhd+/eAPTr14+DB/+/s2X37t2xsrKi\nUqVKlC9fnoCAALp168aWLVuIj49nwYIFDBgwwCR/T8V0khvsvef+HruDdtNxU0e2XN+SrklkB3tb\nFg30Jn9uW95edIK74U/TfsIy9eDxLYjIfJ+mV5Vz7xQe34LI++Cc+tCRlJJP15/lVNBj5vT1SNfm\ntKj4KKb7T2fV5VWUyleKeS3nUb9kfWMlz7rSeEdvKlJK+vfvz7fffvuvr0+bNu3Z8F1a7bLz5k3f\nG4EXhwOFEOTJk4eWLVuyadMm1qxZg7+//yv+DRRLYGtty7Baw2hZtiXjDo/jswOfse3GNsbWG0vx\nvMVT/bPFHO1ZOLAOXWYf5p0lfqwZWj/14efkxS/Bx0x2ZnxKcu6dQlDSeF0adwqz9gay6fQdPmlV\nmTY10h5mOnj7IJ02dWL15dX0rdaXDR02qIKgsxYtWrBu3ToePHgAQFhYGLdu3UrxegcHByIiIlL8\nfoMGDVi1ahUAy5cvp3Hjxs++t3btWgwGA4GBgVy/fp0qVaoAMHjwYEaOHIm3tzcFC2Z817uivwoF\nKrCkzRI+9f6UE/dO0HFTR9ZcXoNBpr4noUpxB37p5c6FO0/4ZO0ZDIZU7jKKu4GN/f+/TplRzi0K\nwUchlyMUrZbiJdvP3+X7HZfxcS/Je80rpvpwj2Me88XBLxi+azi5bXKzpO0SPq3zqWpgZwFcXV2Z\nPHkyrVq1ws3NjZYtW3L37t0Ur+/Zsyfff/89tWvXJjAw8D/f//XXX1m4cCFubm4sXbqUn3/++dn3\nnJ2dqVOnDm3btmXOnDnY29sD2vCUo6MjAwcONP5fUDE7aytr+rpqb/pqOtXkq6NfMWjHIG49SfnN\nBmh7GD5vW42t5+4xfffVlC+0sdM21OrRHO//2rvz6CjqLYHj3xsSjIATFgPvkYAEBSOENCHIFkQw\nOiqDElGeC4ioLM8ReUceKuKIIwpHZnAZ5SkgIqKiLLIERRBwQRRIokYwLBokSlAhooRNliR3/uim\n7eydpTt0cj/n5JCq+nXV/dFQt6v6V/fnTSnVs+mn2kpnv9hLdX5SqZu3ZR/S6P96XwfO2Kh/nMor\ntV1BQYGu2bNG+7zdRzu/1llf+PIFPZl3snpirAUCqbxyVd1xxx26ePHiErft27dP27Vrp/n5VS/X\nfLaoS+9tWQoKCnTpt0u155s9Nf71eJ27ba6ezj9dZvsHFqfrBQ+9qyvS95W+47WPqT7eVPXU8WqJ\nEyudXYYTubA/o9RbRweOnGDk/DQaNwhh9rB4QkNKnkoz53gO9398P//85J/8peFfeHvA24yJG0P9\nevV9Gb0JMPPnz6d79+5MmTKFoEpW4jVnLxHhhnY3sDxpOQktE3jmi2cYumoou37bVWr7J5M60a1N\nUx5Y/DXppZXbbtUDCvJg35c+jL64uvkvNDsV0BIro544nc+o+V9w6PhpXh7WlebnhRZro6os+24Z\nA1cMZOO+jYyLH8eb/d/k4qYX+yF4c7aaN29eoWGsZwwbNoy9e/cyePDgGojK+EvzBs15rt9zTL98\nOj8f+5lb3r2FGV/NKLHAXv3gIF4a2oXw885h1Py0kkcknTk/+fkWUt1MCj9uAQmCyK6FVqtrpFH6\n3kM8e7OjxPHE2UeyGbV2FJM+n0T7Ju1Zct0S7oy50wrYGWMQEa5uczUrBq6gf9v+zNo6i7+t/Btf\n5xR/WLFZo3N45Y5LOX7KOeT9+Kkio98aNHVO/OXnL5vrZlLYuwVaxMA55xVafWak0QNXX1xspFF+\nQT5vbH+DQcmD2PbrNh7t8Shzr55Lm7A2fgzcGBMIGoc2ZkrvKbyY+CLH8o5x+6rbmZYyrViBvXJH\nJLXqDtkpUFDBaqtVUPeSQn4eZKcVK4K3JuMX/nfNLpI6tyxW9XT3od3csfoOpqVOI75FvLtglhWw\nM8aU5bLIy1g+cDk3X3wzb+xwfqjc9NOmQm3KHJHUugf88TscLGOkUjWre2e1/d/A6WOF6h1lHjjK\nuIXpOFo15qkbY90PIJ0uOM2sr2cxeOVgfjj8A1N7T+XFxBfLfVDFGGPOaBjSkEd6PMK8a+YRHBTs\nvP382aRCBfZGXBbFTfGRPL/+O9Zu3//ni8+cp/xY8qLuJYUzMxq5/rKPnDjNqNfTCA2px8yhXdwj\njTIOZji/KEqfQWLrRCtgV8slJyfz1FMVf+K6b9++7ppIVZWWlsbYsWMBOHnyJFdeeSWdO3dm4cKF\njBgxolLlvNPT01m1apV7ubL9NFUX3yKeJdct4e6Yu0nenUzS8iTW/7geODMiKYbYyDDGLUz/c57n\nZhdBg2b+nYnNm3GrZ9NPlZ9TWHyn6tOXqKpqfn6BjnwtVds+/J5+nvmrqqr+cfoPfTrtaY19LVb7\nLeyn639YX7Xj1XG1fSz75ZdfrqmpqdW+302bNmliYmKV9/Pqq6/qvffeWw0RFVfb31tf+ubXb/TG\nFTdqzLwYHffROM05nqOqqtm/H9e4yR/olU9/rEdOuJ51WHCL6vNdqnxM7DmFUvy4xX2V8NInu/lg\n+34evjaanhc2I+2XNG5aeROvfvMqSRclsTxpOVe0vqKGAzZVlZWVRXR0NMOHD6d9+/YMGTKEdevW\nkZCQQLt27UhJSWHevHmMGTMGcJaqiImJweFw0KdPHwDy8/MZP348MTExxMbG8sILLxQ7zj333EPX\nrl3p2LEjjz32mHv9hAkT6NChA7GxsYwfP77UY3z88ccMGDCAAwcOMHToUFJTUwuV7z5zRbJ69Wq6\ndOmCw+EgMdFZYDElJYWePXsSFxdHr1692LVrF6dOnWLSpEksXLjQfcXh2c+ySoCPHTuWXr160bZt\nW5YsWeKLt6VO69isI28NeIuxcWP5aO9HJK1IYuXulbQMC2XGrXHszjnKg0u+dhbca9UdDmbCsV/9\nElvdGkeZmw2Hs6HVfWz4NofpH+ziekdLbu4WzpObn2ThroVENIrg5X9/mR5/rdhsbKZ801KmsfO3\nndW6z+im0TzU7aFy22VmZrJ48WLmzp3LpZdeyoIFC9i4cSPJyclMnTqVpKQkd9vJkyezZs0aIiIi\nOHTI+WDR7NmzycrKIj09neDgYH777bdix5gyZQpNmzYlPz+fxMREtm7dSkREBMuWLWPnzp2IiHt/\nJR3jjObNmzNnzhymT5/unpPhjJycHEaOHMmGDRuIiopyxxEdHc2nn35KcHAw69atY+LEibzzzjtM\nnjyZtLQ0ZsyYATifpTjjvvvuK7UE+M8//8zGjRvZuXMn119/fYnPX5iqCQkKYWTsSBJbJzLp80lM\n3DiRVXtWManHJCZcG83UVTuZveF7RrfxmHQn+j98HlfdulJwTVrxS2MH9731FRe3OI/reh5i0MpB\nLNq1yF3AzhJC7RMVFUWnTp0ICgqiY8eOJCYmIiJ06tSpWMnshIQEhg8fzssvv0x+vnOe3HXr1jF6\n9GiCg52fo5o2bVrsGIsWLaJLly7ExcWRkZHB9u3bCQsLIzQ0lLvvvpulS5fSoEGDUo/hjc2bN9On\nTx+ioqIKxZGbm8vgwYOJiYnh/vvvJyMjo9x9lVUCPCkpiaCgIDp06MD+/ftL24WpBm0bt+W1a15j\nQrcJfLH/C5JWJHFeeAr9Y1owbfVOPvujNdSr77dJd3x6pSAi1wD/B9QD5qjqU0W2i2t7f+A4MFxV\nffdM949b0JAGjFh9kgI5SvuYtYz7ZDUXhl3I6/1fxxFuE5/4kjef6H3lnHP+nBQpKCjIvRwUFFSs\nZPbMmTPZsmUL7733HvHx8V6Vut6zZw/Tp08nNTWVJk2aMHz4cE6cOEFwcDApKSmsX7+eJUuWMGPG\nDD788MNKHaMsjz76KP369WPZsmVkZWXRt2/fKu3P8+9LKzrxvKmwekH1GHLJEPq26svjnz/O1JSp\ndA6P44IWAxizKIPNLWI5x08PsfnsSkFE6gH/Aq4FOgC3ikiHIs2uBdq5fkYBL/kqHgDdu5nvQtqz\n6/gmGl34LJ/+tI7RsaNZdN0iSwjGbffu3XTv3p3JkycTHh7O3r17ueqqq5g1a5Y7gRS9fXT48GEa\nNmxIWFgY+/fv5/333wfg6NGj5Obm0r9/f5599ln3NJwlHcMbPXr0YMOGDezZs6dQHLm5uURERACF\nbxGVVQa8rBLgpmZENIpg1lWzeCLhCXbnZpLbbBp5jdaT/Hsk+tNXkHfS5zH48vZRNyBTVb9X1VPA\n20DR2SIGAvNdX45vBhqLSPmTFlTGyaPsz9nOuIb5hEYsoHVYSytgZ0r0wAMP0KlTJ2JiYujVqxcO\nh4MRI0bQunVrYmNjcTgcLFiwoNBrHA4HcXFxREdHc9ttt5GQkADAkSNHGDBgALGxsfTu3Ztnnnmm\n1GN4Izw8nNmzZzNo0CAcDod7RrgHH3yQhx9+mLi4uEJXPv369WP79u3uL5o9lVUC3NQcESHpoiRW\nDFxBn8jLoNkqnm7yPd/WK3AmBl8f31eXhiJyE3CNqo5wLd8OdFfVMR5t3gWeUtWNruX1wEOqWurA\n765du2plxoW/uXY6/9r7KseDQhgbP5ZhHYdZvSI/2LFjB5dcUvqcFSZw2XvrH2t/WMsjn/w3pwty\nGRzsYOLQNyu1HxH5QlW7ltcuIL5oFpFRIpImImk5OTmV2kebRhFEnQ7ljcR53NXpLksIxpiAcNUF\nV7Fm8Ht0PxlGy4atfX48X54Z9wGtPJYjXesq2gZVnQ3MBueVQmWCSeh5Kwk9b63MS40xpkY1Obcx\nM0d/5pdj+fJKIRVoJyJRIlIfuAVILtImGRgmTj2AXFUtfZ5EY4wxPuWzKwVVzRORMcAanENS56pq\nhoj83bV9JrAK53DUTJxDUm0C21pIVa1mVC1jw1RrL5/eWFfVVThP/J7rZnr8rsC9vozB1KzQ0FAO\nHjxIs2bNLDHUEqrKwYMHCQ0tPiuhCXz2bavxqcjISLKzs6nsAAFzdgoNDSUyMrKmwzA+YEnB+FRI\nSIi7JIMx5uwXEENSjTHG+IclBWOMMW6WFIwxxrj5rMyFr4hIDvBDJV9+PuCfmSrOHtbnusH6XDdU\npc8XqGp4eY0CLilUhYikeVP7ozaxPtcN1ue6wR99tttHxhhj3CwpGGOMcatrSWF2TQdQA6zPdYP1\nuW7weZ/r1HcKxhhjylbXrhSMMcaUoVYmBRG5RkR2iUimiEwoYbuIyPOu7VtFpEtNxFmdvOjzEFdf\nt4nI5yIS8JNSl9dnj3aXikieazbAgOZNn0Wkr4iki0iGiHzi7xirmxf/tsNEZKWIfO3qc0BXWxaR\nuSJyQES+KWW7b89fqlqrfnCW6d4NtAXqA18DHYq06Q+8DwjQA9hS03H7oc+9gCau36+tC332aPch\nzmq9N9V03H54nxsD24HWruXmNR23H/o8EZjm+j0c+A2oX9OxV6HPfYAuwDelbPfp+as2Xil0AzJV\n9XtVPQW8DQws0mYgMF+dNgONReSv/g60GpXbZ1X9XFV/dy1uxjnLXSDz5n0GuA94Bzjgz+B8xJs+\n3wYsVdUfAVQ10PvtTZ8VOE+ctdkb4UwKef4Ns/qo6gacfSiNT89ftTEpRAB7PZazXesq2iaQVLQ/\nd+P8pBHIyu2ziEQANwAv+TEuX/LmfW4PNBGRj0XkCxEZ5rfofMObPs8ALgF+ArYB/1DVAv+EVyN8\nev6y0tl1jIj0w5kUetd0LH7wHPCQqhbUoQl+goF4IBE4F9gkIptV9duaDcunrgbSgSuAC4G1IvKp\nqh6u2bACU21MCvuAVh7Lka51FW0TSLzqj4jEAnOAa1X1oJ9i8xVv+twVeNuVEM4H+otInqou90+I\n1c6bPmcDB1X1GHBMRDYADiBQk4I3fb4TeEqdN9wzRWQPEA2k+CdEv/Pp+as23j5KBdqJSJSI1Adu\nAZKLtEkGhrm+xe8B5Krqz/4OtBqV22cRaQ0sBW6vJZ8ay+2zqkapahtVbQMsAf4zgBMCePdvewXQ\nW0SCRaQB0B3Y4ec4q5M3ff4R55URItICuBj43q9R+pdPz1+17kpBVfNEZAywBufIhbmqmiEif3dt\nn4lzJEp/IBM4jvOTRsDyss+TgGbAi65PznkawMXEvOxzreJNn1V1h4isBrYCBcAcVS1xaGMg8PJ9\nfgKYJyLbcI7IeUhVA7Z6qoi8BfQFzheRbOAxIAT8c/6yJ5qNMca41cbbR8YYYyrJkoIxxhg3SwrG\nGGPcLCkYY4xxs6RgjDHGzZKCMUWIyLki8omI1POy/RhXxUoVkfMrcbwxInJXxSM1pvpZUjCmuLtw\nFpXL97L9Z8CVwA+VPN5cnIX7jKlxlhSMKW4IsMI1L8EGEXnPVc9/pogU+z+jql+palZ5OxWRLBH5\nH9ecFikicpHr9ceBLBHpVu09MaaCLCkY48FVSqGtx0m+G85P8R1wFlsbVMVD5KpqJ5yVPZ/zWJ8G\nXFbFfRtTZZYUjCnsfOCQx3KKq5Z/PvAWVa8u+5bHnz091h8AWlZx38ZUmSUFYwr7Awj1WC5aB8br\nujAissY1LeacUl7v+Xuo69jG1ChLCsZ4cM1OV09EziSGbq4KnUHAzcBGABGZX953AKp6tap2VtUR\nHqtv9vhzk8f69kDAFq4ztYclBWOK+4A/bxOl4rz/vwPYAyxzrY/FOdMXIjLWVc0yEtha5MqgqCYi\nshX4B3C/x/oEYG219cCYSrIqqcYUISJdcJ6wXwHGq+qAItv/DXhFVQdXcL9ZQNeiZZ1FJA4Yp6q3\nVylwY6qBXSkYU4Sqfgl8hLN+f0nbD1c0IZTjfODRatyfMZVmVwrGGGPc7ErBGGOMmyUFY4wxbpYU\njDHGuFlSMMYY42ZJwRhjjJslBWOMMW7/D7LvboyG0FoQAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10f884048>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "#lets plot the functions for the 2D case \n",
    "p1=np.linspace(0,1,40)\n",
    "imp_gini=[gini(np.array([p,1-p])) for p in p1]\n",
    "imp_ent=[entropy(np.array([p,1-p])) for p in p1]\n",
    "imp_mc=[misclass(np.array([p,1-p])) for p in p1]\n",
    "plt.plot (p1,imp_gini,label=\"gini\")\n",
    "plt.plot (p1,imp_ent,label=\"entropy\")\n",
    "plt.plot (p1,imp_mc,label=\"misclassification\")\n",
    "plt.xlabel(\"(p,1-p)\")\n",
    "plt.ylabel(\"impurity(p1,p2)\")\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Splitting\n",
    "\n",
    "Splitting is done by testsing all attributes against the concept attribute and taking the best one. \n",
    "\n",
    "We define a function therefore"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_split_criterion(X,y,impurity,debug=False):\n",
    "    \"\"\"\n",
    "    X: data matrix n rows, d columns\n",
    "    y: vector with n rows, 1 column containing the target concept\n",
    "    impurity: impurity function of the form impurity(p_1....p_k) with k=|X[a].unique|\n",
    "    returns: (idx of best attribute, impurity gain)\n",
    "    \"\"\"\n",
    "    att_num = X.shape[1]\n",
    "    imp_gains=[]\n",
    "    for i in range(att_num):\n",
    "        imp_gains.append(impurity_gain(X,i,y,impurity,debug))\n",
    "    if debug: print (\"Gains for concept (listed on attributes)\",(pp_float_list(imp_gains)))\n",
    "    best = np.argmax(imp_gains)\n",
    "    return (best,imp_gains[best])\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\timpurity 0.300 for attribute 0:  ['0.222', '0.040', '0.700', '0.038']\n",
      "\t\t impurity 0.062 for attribute 0 with value b'high':  ['0.250', '0.000', '0.750', '0.000']\n",
      "\t\t impurity 0.101 for attribute 0 with value b'low':  ['0.206', '0.106', '0.597', '0.090']\n",
      "\t\t impurity 0.095 for attribute 0 with value b'med':  ['0.266', '0.053', '0.620', '0.060']\n",
      "\t\t impurity 0.042 for attribute 0 with value b'vhigh':  ['0.167', '0.000', '0.833', '0.000']\n",
      "\t Estimated gain 0.000\n",
      "\timpurity 0.300 for attribute 1:  ['0.222', '0.040', '0.700', '0.038']\n",
      "\t\t impurity 0.068 for attribute 1 with value b'high':  ['0.243', '0.000', '0.727', '0.030']\n",
      "\t\t impurity 0.095 for attribute 1 with value b'low':  ['0.213', '0.106', '0.620', '0.060']\n",
      "\t\t impurity 0.095 for attribute 1 with value b'med':  ['0.266', '0.053', '0.620', '0.060']\n",
      "\t\t impurity 0.042 for attribute 1 with value b'vhigh':  ['0.167', '0.000', '0.833', '0.000']\n",
      "\t Estimated gain 0.000\n",
      "\timpurity 0.300 for attribute 2:  ['0.222', '0.040', '0.700', '0.038']\n",
      "\t\t impurity 0.061 for attribute 2 with value b'2':  ['0.188', '0.035', '0.755', '0.023']\n",
      "\t\t impurity 0.076 for attribute 2 with value b'3':  ['0.229', '0.042', '0.694', '0.035']\n",
      "\t\t impurity 0.081 for attribute 2 with value b'4':  ['0.236', '0.042', '0.676', '0.046']\n",
      "\t\t impurity 0.081 for attribute 2 with value b'5more':  ['0.236', '0.042', '0.676', '0.046']\n",
      "\t Estimated gain 0.000\n",
      "\timpurity 0.300 for attribute 3:  ['0.222', '0.040', '0.700', '0.038']\n",
      "\t\t impurity 0.000 for attribute 3 with value b'2':  ['0.000', '0.000', '1.000', '0.000']\n",
      "\t\t impurity 0.153 for attribute 3 with value b'4':  ['0.344', '0.062', '0.542', '0.052']\n",
      "\t\t impurity 0.147 for attribute 3 with value b'more':  ['0.323', '0.057', '0.559', '0.061']\n",
      "\t Estimated gain 0.000\n",
      "\timpurity 0.300 for attribute 4:  ['0.222', '0.040', '0.700', '0.038']\n",
      "\t\t impurity 0.120 for attribute 4 with value b'big':  ['0.250', '0.042', '0.639', '0.069']\n",
      "\t\t impurity 0.106 for attribute 4 with value b'med':  ['0.234', '0.042', '0.681', '0.043']\n",
      "\t\t impurity 0.073 for attribute 4 with value b'small':  ['0.182', '0.036', '0.781', '0.000']\n",
      "\t Estimated gain 0.000\n",
      "\timpurity 0.300 for attribute 5:  ['0.222', '0.040', '0.700', '0.038']\n",
      "\t\t impurity 0.173 for attribute 5 with value b'high':  ['0.354', '0.052', '0.481', '0.113']\n",
      "\t\t impurity 0.000 for attribute 5 with value b'low':  ['0.000', '0.000', '1.000', '0.000']\n",
      "\t\t impurity 0.127 for attribute 5 with value b'med':  ['0.312', '0.068', '0.620', '0.000']\n",
      "\t Estimated gain 0.000\n",
      "Gains for concept (listed on attributes) ['0.000', '0.000', '0.000', '0.000', '0.000', '0.000']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(0, 0.0)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_split_criterion(auto[:,0:6],auto[:,6],misclass,True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The ID 3 Algorithm\n",
    "\n",
    "Given the impurity gain and the ID3 Algorithm gets pretty easy now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def id3(X,y,impurity,attributes=None,debug=False,print_progress = True):\n",
    "    \"\"\"\n",
    "    X: data matrix n rows, d columns\n",
    "    y: vector with n rows and 1 column containing the target concept\n",
    "    impurity: impurity function of the form impurity(p_1....p_k) with k=|X[a].unique|\n",
    "    attributes: dictonary contaiing all attributes relevant for the data and all values per attribut. Will be estimated \n",
    "                automatically when it is None\n",
    "    returns: root note\n",
    "    \"\"\"\n",
    "    def new_node(branches, concept, attribute): #create \n",
    "        #new node function for better structure.\n",
    "        return (branches,concept,attribute)\n",
    "    \n",
    "    def max_concept(concepts,uniq):#return the concept frequencies       \n",
    "        bins = [np.sum(concepts==u) for u in uniq]\n",
    "        return bins\n",
    "    \n",
    "    ########## set label\n",
    "    uniq_c = np.unique(y) \n",
    "    label=uniq_c[np.argmax(max_concept(y,uniq_c))]\n",
    "    ###########  stop criterion 1\n",
    "    if len(uniq_c)==1:#stop criterion 1: pure class\n",
    "        if print_progress: \n",
    "            print (\"\\t\\t Leaf Node with label %s due to purity\"%(label))\n",
    "        return new_node(None,label,None)#leaf node    \n",
    "    ###########  manage attributes (first call and stop criterion)\n",
    "    if attributes==None: #get feature space: all attributes and their values\n",
    "       attributes = {key: np.unique(X[:,key]) for key in range(X.shape[1])}\n",
    "    elif len(attributes)==0: #stop criterion 2: no attributes\n",
    "        if print_progress: \n",
    "            print (\"\\t\\t Leaf Node with label %s due to exhausted attributes\"%(label))\n",
    "        return new_node(None,label,None)#leaf node\n",
    "    ########## housekeeping    \n",
    "    level = X.shape[1]-len(attributes)+1 #only for printing purpose        \n",
    "    ###########  get split criterion\n",
    "    att_index=attributes.keys()\n",
    "    (a,gain) = get_split_criterion(X[:,0:6],y,impurity,debug)\n",
    "    if a not in attributes:\n",
    "        a = [x for x in attributes.keys()][0]\n",
    "    #a = att_index[a] #split criterion returns the attribute relativ to att_index\n",
    "    ########## housekeeping\n",
    "    if print_progress: \n",
    "        print (\"Level %d: choosing attribute %d out of %s with gain %f\"%(level,a,attributes.keys(),gain))\n",
    "    values = attributes.pop(a)\n",
    "    ########## estimate splits for all values\n",
    "    \n",
    "    splits = [X[:,a]==v for v in values]  \n",
    "    branches={}\n",
    "    for v,split in zip(values,splits):\n",
    "        if not np.any(split):\n",
    "            if print_progress:\n",
    "                print (\"Level %d: Empty split for value %s of attribute %d\"%(level,v,a))\n",
    "            branches[v] = new_node(None,label,None)\n",
    "        else: \n",
    "            if print_progress: \n",
    "                print (\"Level %d: Recursion for value %s of attribute %d\"%(level,v,a))\n",
    "            branches[v]=id3(X[split,:],y[split],impurity,attributes=attributes,debug=debug,print_progress=print_progress)\n",
    "    attributes[a]=values\n",
    "    return new_node(branches,label,a)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "//anaconda/envs/datsci/lib/python3.6/site-packages/ipykernel/__main__.py:12: RuntimeWarning: divide by zero encountered in log2\n",
      "//anaconda/envs/datsci/lib/python3.6/site-packages/ipykernel/__main__.py:12: RuntimeWarning: invalid value encountered in multiply\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Level 1: choosing attribute 5 out of dict_keys([0, 1, 2, 3, 4, 5]) with gain 0.262184\n",
      "Level 1: Recursion for value b'high' of attribute 5\n",
      "Level 2: choosing attribute 3 out of dict_keys([0, 1, 2, 3, 4]) with gain 0.495905\n",
      "Level 2: Recursion for value b'2' of attribute 3\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 2: Recursion for value b'4' of attribute 3\n",
      "Level 3: choosing attribute 0 out of dict_keys([0, 1, 2, 4]) with gain 0.490507\n",
      "Level 3: Recursion for value b'high' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([1, 2, 4]) with gain 0.811278\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 3: Recursion for value b'low' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([2, 4, 1]) with gain 0.811278\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 3: Recursion for value b'med' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([2, 4, 1]) with gain 0.798795\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 3: Recursion for value b'vhigh' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([2, 4, 1]) with gain 1.000000\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 2: Recursion for value b'more' of attribute 3\n",
      "Level 3: choosing attribute 0 out of dict_keys([2, 4, 1, 0]) with gain 0.385011\n",
      "Level 3: Recursion for value b'high' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([2, 4, 1]) with gain 0.585676\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "Level 5: choosing attribute 2 out of dict_keys([2, 4]) with gain 0.184243\n",
      "Level 5: Recursion for value b'2' of attribute 2\n",
      "Level 6: choosing attribute 4 out of dict_keys([4]) with gain 0.918296\n",
      "Level 6: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'med' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "Level 5: choosing attribute 2 out of dict_keys([4, 2]) with gain 0.184243\n",
      "Level 5: Recursion for value b'2' of attribute 2\n",
      "Level 6: choosing attribute 4 out of dict_keys([4]) with gain 0.918296\n",
      "Level 6: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'med' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "Level 5: choosing attribute 2 out of dict_keys([4, 2]) with gain 0.184243\n",
      "Level 5: Recursion for value b'2' of attribute 2\n",
      "Level 6: choosing attribute 4 out of dict_keys([4]) with gain 0.918296\n",
      "Level 6: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'med' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 3: Recursion for value b'low' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([4, 2, 1]) with gain 0.711795\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([4, 2]) with gain 0.739820\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.739820\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.739820\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "Level 5: choosing attribute 2 out of dict_keys([2, 4]) with gain 0.184243\n",
      "Level 5: Recursion for value b'2' of attribute 2\n",
      "Level 6: choosing attribute 4 out of dict_keys([4]) with gain 0.918296\n",
      "Level 6: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'med' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 3: Recursion for value b'med' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([4, 2, 1]) with gain 0.747835\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "Level 5: choosing attribute 2 out of dict_keys([4, 2]) with gain 0.184243\n",
      "Level 5: Recursion for value b'2' of attribute 2\n",
      "Level 6: choosing attribute 4 out of dict_keys([4]) with gain 0.918296\n",
      "Level 6: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'med' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([4, 2]) with gain 0.739820\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.739820\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'vgood' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "Level 5: choosing attribute 2 out of dict_keys([2, 4]) with gain 0.184243\n",
      "Level 5: Recursion for value b'2' of attribute 2\n",
      "Level 6: choosing attribute 4 out of dict_keys([4]) with gain 0.918296\n",
      "Level 6: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'med' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 3: Recursion for value b'vhigh' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([4, 2, 1]) with gain 0.788076\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "Level 5: choosing attribute 2 out of dict_keys([4, 2]) with gain 0.184243\n",
      "Level 5: Recursion for value b'2' of attribute 2\n",
      "Level 6: choosing attribute 4 out of dict_keys([4]) with gain 0.918296\n",
      "Level 6: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'med' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "Level 5: choosing attribute 2 out of dict_keys([4, 2]) with gain 0.184243\n",
      "Level 5: Recursion for value b'2' of attribute 2\n",
      "Level 6: choosing attribute 4 out of dict_keys([4]) with gain 0.918296\n",
      "Level 6: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'med' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 1: Recursion for value b'low' of attribute 5\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 1: Recursion for value b'med' of attribute 5\n",
      "Level 2: choosing attribute 3 out of dict_keys([4, 2, 1, 0, 3]) with gain 0.301422\n",
      "Level 2: Recursion for value b'2' of attribute 3\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 2: Recursion for value b'4' of attribute 3\n",
      "Level 3: choosing attribute 0 out of dict_keys([4, 2, 1, 0]) with gain 0.263512\n",
      "Level 3: Recursion for value b'high' of attribute 0\n",
      "Level 4: choosing attribute 4 out of dict_keys([4, 2, 1]) with gain 0.365863\n",
      "Level 4: Recursion for value b'big' of attribute 4\n",
      "Level 5: choosing attribute 1 out of dict_keys([2, 1]) with gain 0.811278\n",
      "Level 5: Recursion for value b'high' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'low' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 4\n",
      "Level 5: choosing attribute 2 out of dict_keys([2, 1]) with gain 0.548795\n",
      "Level 5: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'4' of attribute 2\n",
      "Level 6: choosing attribute 1 out of dict_keys([1]) with gain 0.811278\n",
      "Level 6: Recursion for value b'high' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'low' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'med' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'5more' of attribute 2\n",
      "Level 6: choosing attribute 1 out of dict_keys([1]) with gain 0.811278\n",
      "Level 6: Recursion for value b'high' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'low' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'med' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 3: Recursion for value b'low' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([1, 2, 4]) with gain 0.548795\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 3: Recursion for value b'med' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([2, 4, 1]) with gain 0.548795\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 3: Recursion for value b'vhigh' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([2, 4, 1]) with gain 0.311278\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.666667\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 1.000000\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 2: Recursion for value b'more' of attribute 3\n",
      "Level 3: choosing attribute 0 out of dict_keys([2, 4, 1, 0]) with gain 0.228807\n",
      "Level 3: Recursion for value b'high' of attribute 0\n",
      "Level 4: choosing attribute 4 out of dict_keys([2, 4, 1]) with gain 0.388707\n",
      "Level 4: Recursion for value b'big' of attribute 4\n",
      "Level 5: choosing attribute 1 out of dict_keys([2, 1]) with gain 0.811278\n",
      "Level 5: Recursion for value b'high' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'low' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 1\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 4\n",
      "Level 5: choosing attribute 1 out of dict_keys([2, 1]) with gain 0.380241\n",
      "Level 5: Recursion for value b'high' of attribute 1\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'low' of attribute 1\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 1\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 3: Recursion for value b'low' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([2, 1, 4]) with gain 0.439655\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "Level 5: choosing attribute 2 out of dict_keys([2, 4]) with gain 0.184243\n",
      "Level 5: Recursion for value b'2' of attribute 2\n",
      "Level 6: choosing attribute 4 out of dict_keys([4]) with gain 0.918296\n",
      "Level 6: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'med' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([4, 2]) with gain 0.739820\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.739820\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.709443\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 3: Recursion for value b'med' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([2, 4, 1]) with gain 0.430729\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.709443\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.739820\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'good' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "Level 5: choosing attribute 2 out of dict_keys([2, 4]) with gain 0.184243\n",
      "Level 5: Recursion for value b'2' of attribute 2\n",
      "Level 6: choosing attribute 4 out of dict_keys([4]) with gain 0.918296\n",
      "Level 6: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'med' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 5: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([4, 2]) with gain 0.709443\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 3: Recursion for value b'vhigh' of attribute 0\n",
      "Level 4: choosing attribute 1 out of dict_keys([2, 4, 1]) with gain 0.380930\n",
      "Level 4: Recursion for value b'high' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'low' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.709443\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'med' of attribute 1\n",
      "Level 5: choosing attribute 4 out of dict_keys([2, 4]) with gain 0.709443\n",
      "Level 5: Recursion for value b'big' of attribute 4\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'med' of attribute 4\n",
      "Level 6: choosing attribute 2 out of dict_keys([2]) with gain 0.811278\n",
      "Level 6: Recursion for value b'2' of attribute 2\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 6: Recursion for value b'3' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'4' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 6: Recursion for value b'5more' of attribute 2\n",
      "\t\t Leaf Node with label b'acc' due to purity\n",
      "Level 5: Recursion for value b'small' of attribute 4\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n",
      "Level 4: Recursion for value b'vhigh' of attribute 1\n",
      "\t\t Leaf Node with label b'unacc' due to purity\n"
     ]
    }
   ],
   "source": [
    "#test it\n",
    "root = id3(auto[:,0:6],auto[:,6],entropy,print_progress=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classifying the Tree\n",
    "\n",
    "For classifying we simply need to traverse the tree. However, before that we want to inspect the learned rules and write a general print function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "#lets make a function to print the tree\n",
    "\n",
    "def print_tree(t,attribute_names,test=\"\", level=0):\n",
    "    \"\"\"\n",
    "    t: node of the (sub)tree\n",
    "    attribute_names: names of the attribute for better printing\n",
    "    test: string specifying the test that yielded the node t\n",
    "    level: current level of the tree\n",
    "    \"\"\"\n",
    "\n",
    "    prefix =\"\"\n",
    "    for i in range(level): \n",
    "        prefix += \" \"\n",
    "    prefix += \" |--(%s):\"%(test)\n",
    "    if t[2]==None:\n",
    "        print (\"%s assign label %s\"%(prefix, t[1]))\n",
    "    else:\n",
    "        print (\"%s test attribute %s \"%(prefix,attribute_names[t[2]]))\n",
    "    \n",
    "    if t[0] is None: return\n",
    "    \n",
    "    for v,branch in t[0].items():\n",
    "        print_tree(branch,attribute_names,\"%s=%s\"%(attribute_names[t[2]],v), level+1)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " |--(): test attribute safety \n",
      "  |--(safety=b'high'): test attribute persons \n",
      "   |--(persons=b'2'): assign label b'unacc'\n",
      "   |--(persons=b'4'): test attribute buying \n",
      "    |--(buying=b'high'): test attribute maint \n",
      "     |--(maint=b'high'): assign label b'acc'\n",
      "     |--(maint=b'low'): assign label b'acc'\n",
      "     |--(maint=b'med'): assign label b'acc'\n",
      "     |--(maint=b'vhigh'): assign label b'unacc'\n",
      "    |--(buying=b'low'): test attribute maint \n",
      "     |--(maint=b'high'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'vgood'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'acc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'vgood'\n",
      "       |--(doors=b'5more'): assign label b'vgood'\n",
      "      |--(lug_boot=b'small'): assign label b'acc'\n",
      "     |--(maint=b'low'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'vgood'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'good'\n",
      "       |--(doors=b'3'): assign label b'good'\n",
      "       |--(doors=b'4'): assign label b'vgood'\n",
      "       |--(doors=b'5more'): assign label b'vgood'\n",
      "      |--(lug_boot=b'small'): assign label b'good'\n",
      "     |--(maint=b'med'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'vgood'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'good'\n",
      "       |--(doors=b'3'): assign label b'good'\n",
      "       |--(doors=b'4'): assign label b'vgood'\n",
      "       |--(doors=b'5more'): assign label b'vgood'\n",
      "      |--(lug_boot=b'small'): assign label b'good'\n",
      "     |--(maint=b'vhigh'): assign label b'acc'\n",
      "    |--(buying=b'med'): test attribute maint \n",
      "     |--(maint=b'high'): assign label b'acc'\n",
      "     |--(maint=b'low'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'vgood'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'good'\n",
      "       |--(doors=b'3'): assign label b'good'\n",
      "       |--(doors=b'4'): assign label b'vgood'\n",
      "       |--(doors=b'5more'): assign label b'vgood'\n",
      "      |--(lug_boot=b'small'): assign label b'good'\n",
      "     |--(maint=b'med'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'vgood'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'acc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'vgood'\n",
      "       |--(doors=b'5more'): assign label b'vgood'\n",
      "      |--(lug_boot=b'small'): assign label b'acc'\n",
      "     |--(maint=b'vhigh'): assign label b'acc'\n",
      "    |--(buying=b'vhigh'): test attribute maint \n",
      "     |--(maint=b'high'): assign label b'unacc'\n",
      "     |--(maint=b'low'): assign label b'acc'\n",
      "     |--(maint=b'med'): assign label b'acc'\n",
      "     |--(maint=b'vhigh'): assign label b'unacc'\n",
      "   |--(persons=b'more'): test attribute buying \n",
      "    |--(buying=b'high'): test attribute maint \n",
      "     |--(maint=b'high'): test attribute doors \n",
      "      |--(doors=b'2'): test attribute lug_boot \n",
      "       |--(lug_boot=b'big'): assign label b'acc'\n",
      "       |--(lug_boot=b'med'): assign label b'acc'\n",
      "       |--(lug_boot=b'small'): assign label b'unacc'\n",
      "      |--(doors=b'3'): assign label b'acc'\n",
      "      |--(doors=b'4'): assign label b'acc'\n",
      "      |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'low'): test attribute doors \n",
      "      |--(doors=b'2'): test attribute lug_boot \n",
      "       |--(lug_boot=b'big'): assign label b'acc'\n",
      "       |--(lug_boot=b'med'): assign label b'acc'\n",
      "       |--(lug_boot=b'small'): assign label b'unacc'\n",
      "      |--(doors=b'3'): assign label b'acc'\n",
      "      |--(doors=b'4'): assign label b'acc'\n",
      "      |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'med'): test attribute doors \n",
      "      |--(doors=b'2'): test attribute lug_boot \n",
      "       |--(lug_boot=b'big'): assign label b'acc'\n",
      "       |--(lug_boot=b'med'): assign label b'acc'\n",
      "       |--(lug_boot=b'small'): assign label b'unacc'\n",
      "      |--(doors=b'3'): assign label b'acc'\n",
      "      |--(doors=b'4'): assign label b'acc'\n",
      "      |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'vhigh'): assign label b'unacc'\n",
      "    |--(buying=b'low'): test attribute maint \n",
      "     |--(maint=b'high'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'vgood'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'acc'\n",
      "       |--(doors=b'3'): assign label b'vgood'\n",
      "       |--(doors=b'4'): assign label b'vgood'\n",
      "       |--(doors=b'5more'): assign label b'vgood'\n",
      "      |--(lug_boot=b'small'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'low'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'vgood'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'good'\n",
      "       |--(doors=b'3'): assign label b'vgood'\n",
      "       |--(doors=b'4'): assign label b'vgood'\n",
      "       |--(doors=b'5more'): assign label b'vgood'\n",
      "      |--(lug_boot=b'small'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'good'\n",
      "       |--(doors=b'4'): assign label b'good'\n",
      "       |--(doors=b'5more'): assign label b'good'\n",
      "     |--(maint=b'med'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'vgood'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'good'\n",
      "       |--(doors=b'3'): assign label b'vgood'\n",
      "       |--(doors=b'4'): assign label b'vgood'\n",
      "       |--(doors=b'5more'): assign label b'vgood'\n",
      "      |--(lug_boot=b'small'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'good'\n",
      "       |--(doors=b'4'): assign label b'good'\n",
      "       |--(doors=b'5more'): assign label b'good'\n",
      "     |--(maint=b'vhigh'): test attribute doors \n",
      "      |--(doors=b'2'): test attribute lug_boot \n",
      "       |--(lug_boot=b'big'): assign label b'acc'\n",
      "       |--(lug_boot=b'med'): assign label b'acc'\n",
      "       |--(lug_boot=b'small'): assign label b'unacc'\n",
      "      |--(doors=b'3'): assign label b'acc'\n",
      "      |--(doors=b'4'): assign label b'acc'\n",
      "      |--(doors=b'5more'): assign label b'acc'\n",
      "    |--(buying=b'med'): test attribute maint \n",
      "     |--(maint=b'high'): test attribute doors \n",
      "      |--(doors=b'2'): test attribute lug_boot \n",
      "       |--(lug_boot=b'big'): assign label b'acc'\n",
      "       |--(lug_boot=b'med'): assign label b'acc'\n",
      "       |--(lug_boot=b'small'): assign label b'unacc'\n",
      "      |--(doors=b'3'): assign label b'acc'\n",
      "      |--(doors=b'4'): assign label b'acc'\n",
      "      |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'low'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'vgood'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'good'\n",
      "       |--(doors=b'3'): assign label b'vgood'\n",
      "       |--(doors=b'4'): assign label b'vgood'\n",
      "       |--(doors=b'5more'): assign label b'vgood'\n",
      "      |--(lug_boot=b'small'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'good'\n",
      "       |--(doors=b'4'): assign label b'good'\n",
      "       |--(doors=b'5more'): assign label b'good'\n",
      "     |--(maint=b'med'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'vgood'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'acc'\n",
      "       |--(doors=b'3'): assign label b'vgood'\n",
      "       |--(doors=b'4'): assign label b'vgood'\n",
      "       |--(doors=b'5more'): assign label b'vgood'\n",
      "      |--(lug_boot=b'small'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'vhigh'): test attribute doors \n",
      "      |--(doors=b'2'): test attribute lug_boot \n",
      "       |--(lug_boot=b'big'): assign label b'acc'\n",
      "       |--(lug_boot=b'med'): assign label b'acc'\n",
      "       |--(lug_boot=b'small'): assign label b'unacc'\n",
      "      |--(doors=b'3'): assign label b'acc'\n",
      "      |--(doors=b'4'): assign label b'acc'\n",
      "      |--(doors=b'5more'): assign label b'acc'\n",
      "    |--(buying=b'vhigh'): test attribute maint \n",
      "     |--(maint=b'high'): assign label b'unacc'\n",
      "     |--(maint=b'low'): test attribute doors \n",
      "      |--(doors=b'2'): test attribute lug_boot \n",
      "       |--(lug_boot=b'big'): assign label b'acc'\n",
      "       |--(lug_boot=b'med'): assign label b'acc'\n",
      "       |--(lug_boot=b'small'): assign label b'unacc'\n",
      "      |--(doors=b'3'): assign label b'acc'\n",
      "      |--(doors=b'4'): assign label b'acc'\n",
      "      |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'med'): test attribute doors \n",
      "      |--(doors=b'2'): test attribute lug_boot \n",
      "       |--(lug_boot=b'big'): assign label b'acc'\n",
      "       |--(lug_boot=b'med'): assign label b'acc'\n",
      "       |--(lug_boot=b'small'): assign label b'unacc'\n",
      "      |--(doors=b'3'): assign label b'acc'\n",
      "      |--(doors=b'4'): assign label b'acc'\n",
      "      |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'vhigh'): assign label b'unacc'\n",
      "  |--(safety=b'low'): assign label b'unacc'\n",
      "  |--(safety=b'med'): test attribute persons \n",
      "   |--(persons=b'2'): assign label b'unacc'\n",
      "   |--(persons=b'4'): test attribute buying \n",
      "    |--(buying=b'high'): test attribute lug_boot \n",
      "     |--(lug_boot=b'big'): test attribute maint \n",
      "      |--(maint=b'high'): assign label b'acc'\n",
      "      |--(maint=b'low'): assign label b'acc'\n",
      "      |--(maint=b'med'): assign label b'acc'\n",
      "      |--(maint=b'vhigh'): assign label b'unacc'\n",
      "     |--(lug_boot=b'med'): test attribute doors \n",
      "      |--(doors=b'2'): assign label b'unacc'\n",
      "      |--(doors=b'3'): assign label b'unacc'\n",
      "      |--(doors=b'4'): test attribute maint \n",
      "       |--(maint=b'high'): assign label b'acc'\n",
      "       |--(maint=b'low'): assign label b'acc'\n",
      "       |--(maint=b'med'): assign label b'acc'\n",
      "       |--(maint=b'vhigh'): assign label b'unacc'\n",
      "      |--(doors=b'5more'): test attribute maint \n",
      "       |--(maint=b'high'): assign label b'acc'\n",
      "       |--(maint=b'low'): assign label b'acc'\n",
      "       |--(maint=b'med'): assign label b'acc'\n",
      "       |--(maint=b'vhigh'): assign label b'unacc'\n",
      "     |--(lug_boot=b'small'): assign label b'unacc'\n",
      "    |--(buying=b'low'): test attribute maint \n",
      "     |--(maint=b'high'): assign label b'acc'\n",
      "     |--(maint=b'low'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'good'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'acc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'good'\n",
      "       |--(doors=b'5more'): assign label b'good'\n",
      "      |--(lug_boot=b'small'): assign label b'acc'\n",
      "     |--(maint=b'med'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'good'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'acc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'good'\n",
      "       |--(doors=b'5more'): assign label b'good'\n",
      "      |--(lug_boot=b'small'): assign label b'acc'\n",
      "     |--(maint=b'vhigh'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'acc'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'unacc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(lug_boot=b'small'): assign label b'unacc'\n",
      "    |--(buying=b'med'): test attribute maint \n",
      "     |--(maint=b'high'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'acc'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'unacc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(lug_boot=b'small'): assign label b'unacc'\n",
      "     |--(maint=b'low'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'good'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'acc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'good'\n",
      "       |--(doors=b'5more'): assign label b'good'\n",
      "      |--(lug_boot=b'small'): assign label b'acc'\n",
      "     |--(maint=b'med'): assign label b'acc'\n",
      "     |--(maint=b'vhigh'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'acc'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'unacc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(lug_boot=b'small'): assign label b'unacc'\n",
      "    |--(buying=b'vhigh'): test attribute maint \n",
      "     |--(maint=b'high'): assign label b'unacc'\n",
      "     |--(maint=b'low'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'acc'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'unacc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(lug_boot=b'small'): assign label b'unacc'\n",
      "     |--(maint=b'med'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'acc'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'unacc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(lug_boot=b'small'): assign label b'unacc'\n",
      "     |--(maint=b'vhigh'): assign label b'unacc'\n",
      "   |--(persons=b'more'): test attribute buying \n",
      "    |--(buying=b'high'): test attribute lug_boot \n",
      "     |--(lug_boot=b'big'): test attribute maint \n",
      "      |--(maint=b'high'): assign label b'acc'\n",
      "      |--(maint=b'low'): assign label b'acc'\n",
      "      |--(maint=b'med'): assign label b'acc'\n",
      "      |--(maint=b'vhigh'): assign label b'unacc'\n",
      "     |--(lug_boot=b'med'): test attribute maint \n",
      "      |--(maint=b'high'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(maint=b'low'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(maint=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(maint=b'vhigh'): assign label b'unacc'\n",
      "     |--(lug_boot=b'small'): assign label b'unacc'\n",
      "    |--(buying=b'low'): test attribute maint \n",
      "     |--(maint=b'high'): test attribute doors \n",
      "      |--(doors=b'2'): test attribute lug_boot \n",
      "       |--(lug_boot=b'big'): assign label b'acc'\n",
      "       |--(lug_boot=b'med'): assign label b'acc'\n",
      "       |--(lug_boot=b'small'): assign label b'unacc'\n",
      "      |--(doors=b'3'): assign label b'acc'\n",
      "      |--(doors=b'4'): assign label b'acc'\n",
      "      |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'low'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'good'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'acc'\n",
      "       |--(doors=b'3'): assign label b'good'\n",
      "       |--(doors=b'4'): assign label b'good'\n",
      "       |--(doors=b'5more'): assign label b'good'\n",
      "      |--(lug_boot=b'small'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'med'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'good'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'acc'\n",
      "       |--(doors=b'3'): assign label b'good'\n",
      "       |--(doors=b'4'): assign label b'good'\n",
      "       |--(doors=b'5more'): assign label b'good'\n",
      "      |--(lug_boot=b'small'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'vhigh'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'acc'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(lug_boot=b'small'): assign label b'unacc'\n",
      "    |--(buying=b'med'): test attribute maint \n",
      "     |--(maint=b'high'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'acc'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(lug_boot=b'small'): assign label b'unacc'\n",
      "     |--(maint=b'low'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'good'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'acc'\n",
      "       |--(doors=b'3'): assign label b'good'\n",
      "       |--(doors=b'4'): assign label b'good'\n",
      "       |--(doors=b'5more'): assign label b'good'\n",
      "      |--(lug_boot=b'small'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'med'): test attribute doors \n",
      "      |--(doors=b'2'): test attribute lug_boot \n",
      "       |--(lug_boot=b'big'): assign label b'acc'\n",
      "       |--(lug_boot=b'med'): assign label b'acc'\n",
      "       |--(lug_boot=b'small'): assign label b'unacc'\n",
      "      |--(doors=b'3'): assign label b'acc'\n",
      "      |--(doors=b'4'): assign label b'acc'\n",
      "      |--(doors=b'5more'): assign label b'acc'\n",
      "     |--(maint=b'vhigh'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'acc'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(lug_boot=b'small'): assign label b'unacc'\n",
      "    |--(buying=b'vhigh'): test attribute maint \n",
      "     |--(maint=b'high'): assign label b'unacc'\n",
      "     |--(maint=b'low'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'acc'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(lug_boot=b'small'): assign label b'unacc'\n",
      "     |--(maint=b'med'): test attribute lug_boot \n",
      "      |--(lug_boot=b'big'): assign label b'acc'\n",
      "      |--(lug_boot=b'med'): test attribute doors \n",
      "       |--(doors=b'2'): assign label b'unacc'\n",
      "       |--(doors=b'3'): assign label b'acc'\n",
      "       |--(doors=b'4'): assign label b'acc'\n",
      "       |--(doors=b'5more'): assign label b'acc'\n",
      "      |--(lug_boot=b'small'): assign label b'unacc'\n",
      "     |--(maint=b'vhigh'): assign label b'unacc'\n"
     ]
    }
   ],
   "source": [
    "print_tree(root,feature)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can use the same code, strip away all printing and do the classifcation. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Now classify using the tree\n",
    "\n",
    "def classify_tree(t, x):\n",
    "    \"\"\"\n",
    "    t: node of the tree\n",
    "    x: row vector containing the examples\n",
    "    return: concept for x\n",
    "    \"\"\"\n",
    "    \n",
    "    if t[2]==None:\n",
    "        return t[1]\n",
    "    else:\n",
    "        value = x[t[2]]\n",
    "        branch = t[0][value]\n",
    "        if t[0] is None: \n",
    "            raise TypeError(\"Tree not correct. Got None branch for value %s of attribute %s is specified for testing\"%(value,t[2]))\n",
    "        return classify_tree(branch,x)\n",
    "    \n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lets test classifying on a single example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "According to the attributes ['buying', 'maint', 'doors', 'persons', 'lug_boot', 'safety']\n",
      "Should i buy the car [b'vhigh' b'vhigh' b'3' b'more' b'big' b'med']?\n",
      "The car is b'unacc' (in truth it is b'unacc')\n"
     ]
    }
   ],
   "source": [
    "print (\"According to the attributes %s\"%(feature[:-1]))\n",
    "print (\"Should i buy the car %s?\"%(auto[52,0:6]))\n",
    "print (\"The car is %s (in truth it is %s)\"%(classify_tree(root,auto[52,0:6]),auto[52,6]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evaluating the classification accuracy\n",
    "\n",
    "Of course we want to estimate the error. Therefore we write a function that given a set of examples predicts their concept. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "def error(X,y,t,debug=False):\n",
    "    predict =[]\n",
    "    for i,x in enumerate(X):\n",
    "        y_pred =classify_tree(t,x)\n",
    "        if debug:\n",
    "            print (\"%s concept: %s classified as %s\"%(y[i]==y_pred,y[i],y_pred))\n",
    "        predict.append(y_pred)\n",
    "    correct = y==predict\n",
    "    return (1-np.sum(correct)/float(len(y)),correct,predict) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So applying it on the training set we geht the training error (this could be extracted out of the training process also)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Error on training set 0.000000 (it is perfect, smells like overfitting)\n"
     ]
    }
   ],
   "source": [
    "(err,cor,pre) = error(auto[:,0:6],auto[:,6],root,False)\n",
    "print (\"Error on training set %f (it is perfect, smells like overfitting)\"%(err))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Random Splitting\n",
    "\n",
    "However, how good does the decision tree generalize? Lets evaluate it using random splitting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_splitting(X,y,impurity,root,fraction=0.8):\n",
    "    #prepare test training split\n",
    "    idx =  np.random.permutation(np.arange(X.shape[0])) # create a array with indices 1..N and permutate it\n",
    "    bound = int(len(idx)*fraction)\n",
    "    X_train = X[idx[0:bound],:]  # take the first 80% as training data. \n",
    "    y_train = y[idx[0:bound]]  # take the first 80% as training data. \n",
    "    X_test  = X[idx[bound:],:]  # take the last 20% as test data. \n",
    "    y_test  = y[idx[bound:]]  # take the last 20% as test data. \n",
    "    #print len(y_test), len(y_train)\n",
    "    #now train it\n",
    "    t = id3(X_train, y_train,impurity,print_progress=False) \n",
    "    err_train=error(X_train,y_train,t)[0]\n",
    "    #and test it\n",
    "    err_test = error(X_test,y_test,t)[0]\n",
    "    return (err_train,err_test)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since we rely on random splitting, there is a chance to get a very bad/very good split. Hence, random splitting has to be conducted several times in a row and the results have to be averaged in order to obtain a reliable estiamtor. A better way is to do cross-validation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<function gini at 0x10f77bf28>: Average training error 0.000000;Average test error 0.126446\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "//anaconda/envs/datsci/lib/python3.6/site-packages/ipykernel/__main__.py:12: RuntimeWarning: divide by zero encountered in log2\n",
      "//anaconda/envs/datsci/lib/python3.6/site-packages/ipykernel/__main__.py:12: RuntimeWarning: invalid value encountered in multiply\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<function entropy at 0x10f77bea0>: Average training error 0.000000;Average test error 0.121364\n",
      "<function misclass at 0x10f77ba60>: Average training error 0.000000;Average test error 0.187066\n"
     ]
    }
   ],
   "source": [
    "impurities=[gini,entropy,misclass]\n",
    "X=auto[:,0:6]\n",
    "y=auto[:,6]\n",
    "for imp in impurities:\n",
    "    etr=0\n",
    "    ete=0\n",
    "    splits=20\n",
    "    for i in range(splits):\n",
    "        (err_train,err_test)=random_splitting(X,y,imp,root,0.3) #alternative root root[0]['high']\n",
    "        etr+=err_train\n",
    "        ete+=err_test\n",
    "    print (\"%s: Average training error %f;Average test error %f\"%(imp,etr/splits,ete/splits))\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see that generalization error is higher than the training error (depends of course on the number of training samples used)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.6.2"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "210px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}