hw2/src/P3.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1200,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "\n",
    "sns.reset_defaults()\n",
    "sns.set_theme(rc={'figure.dpi': 72, 'savefig.dpi': 300,\n",
    "              'figure.autolayout': True})\n",
    "sns.set_style('ticks')\n",
    "sns.set_context('paper')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1201,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load the dataset.\n",
    "df = pd.read_csv('data/lungcancer.csv')\n",
    "X = df.drop(columns=['LUNG_CANCER'])\n",
    "y = df['LUNG_CANCER']\n",
    "\n",
    "# Preprocess\n",
    "X['GENDER'] = X['GENDER'] == 'M'\n",
    "y = y == 'YES'\n",
    "\n",
    "for c in X.columns:\n",
    "    if c == 'GENDER' or c == 'AGE':\n",
    "        continue\n",
    "    X[c] = X[c] == 2\n",
    "\n",
    "l = 10\n",
    "s = X['AGE'].min()\n",
    "e = X['AGE'].max()\n",
    "labels = [\"{0}-{1}\".format(i, i + l) for i in range(s, e, l)]\n",
    "X['age_group'] = pd.cut(X['AGE'], range(s, e + l, l), right=False, labels=labels)\n",
    "X = X.drop(columns=['AGE'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1202,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "\n",
    "class Decision:\n",
    "    def __init__(self,\n",
    "                 feature,\n",
    "                 value,\n",
    "                 true_child=None,\n",
    "                 false_child=None,\n",
    "                 level=0,\n",
    "                 id=0,\n",
    "                 data=None):\n",
    "        self.feature = feature\n",
    "        self.value = value\n",
    "        self.true_child = true_child\n",
    "        self.false_child = false_child\n",
    "        self.level = level\n",
    "        self.id = id\n",
    "        self.data = data\n",
    "\n",
    "    def match(self, x):\n",
    "        val = x[self.feature]\n",
    "        if isinstance(val, int) or isinstance(val, float):\n",
    "            return val >= self.value\n",
    "        else:\n",
    "            return val == self.value\n",
    "\n",
    "\n",
    "class Leaf:\n",
    "    def __init__(self, data, id, level, lcnt, label):\n",
    "        self.labels_count = lcnt\n",
    "        self.label = label\n",
    "        self.id = id\n",
    "        self.level = level\n",
    "\n",
    "\n",
    "class DecisionTree:\n",
    "    def __init__(self, max_depth=0):\n",
    "        self.max_depth = max_depth\n",
    "        self.tree = None\n",
    "\n",
    "    def learn(self, X, y):\n",
    "        self.tree = self._build_tree(np.c_[X, y].tolist())\n",
    "        self._depth_prune()\n",
    "\n",
    "    def predict(self, X):\n",
    "        preds = []\n",
    "        for x in X:\n",
    "            pred = self._predict(x, self.tree)\n",
    "            preds.append(pred)\n",
    "        return np.array(preds)\n",
    "\n",
    "    def get_n_leaves(self):\n",
    "        return len(self._get_leaves(self.tree))\n",
    "\n",
    "    def get_n_nodes(self):\n",
    "        inners = self._get_inners(self.tree)\n",
    "        return self.get_n_leaves() + len(inners)\n",
    "\n",
    "    def get_depth(self):\n",
    "        leaves = self._get_leaves(self.tree)\n",
    "        maxd = 0\n",
    "        for leaf in leaves:\n",
    "            if leaf.level > maxd:\n",
    "                maxd = leaf.level\n",
    "        return maxd\n",
    "\n",
    "    def _predict(self, X, node):\n",
    "        if isinstance(node, Leaf):\n",
    "            return node.label\n",
    "        if node.match(X):\n",
    "            return self._predict(X, node.true_child)\n",
    "        else:\n",
    "            return self._predict(X, node.false_child)\n",
    "\n",
    "    def _build_tree(self, data, level=0, id=0):\n",
    "        gain, decision = self._find_best_split(data)\n",
    "        if gain == 0:\n",
    "            lcnt = self._count_labels(data)\n",
    "            label = self._max_label(lcnt)\n",
    "            return Leaf(data, id, level, lcnt, label)\n",
    "        true_d, false_d = self._partition(data, decision)\n",
    "        decision.true_child = self._build_tree(true_d, level + 1, 2 * id + 2)\n",
    "        decision.false_child = self._build_tree(false_d, level + 1, 2 * id + 1)\n",
    "        decision.level = level\n",
    "        decision.id = id\n",
    "        decision.data = data\n",
    "        return decision\n",
    "\n",
    "    def _partition(self, data, decision):\n",
    "        true_d, false_d = [], []\n",
    "        for d in data:\n",
    "            if decision.match(d):\n",
    "                true_d.append(d)\n",
    "            else:\n",
    "                false_d.append(d)\n",
    "        return true_d, false_d\n",
    "\n",
    "    def _find_best_split(self, data):\n",
    "        best_gain = 0\n",
    "        best_split = None\n",
    "        current_entropy = self._entropy(data)\n",
    "        n_features = len(data[0]) - 1\n",
    "        for col in range(n_features):\n",
    "            values = set([d[col] for d in data])\n",
    "            for val in values:\n",
    "                decision = Decision(col, val)\n",
    "                true_d, false_d = self._partition(data, decision)\n",
    "                if len(true_d) == 0 or len(false_d) == 0:\n",
    "                    continue\n",
    "                gain = self._info_gain(true_d, false_d, current_entropy)\n",
    "                if gain >= best_gain:\n",
    "                    best_gain, best_split = gain, decision\n",
    "        return best_gain, best_split\n",
    "\n",
    "    def _entropy(self, data):\n",
    "        entries = self._count_labels(data)\n",
    "        avg_entropy = 0\n",
    "        for label in entries:\n",
    "            prob = entries[label] / len(data)\n",
    "            avg_entropy = -(avg_entropy + (prob * math.log(prob, 2)))\n",
    "        return avg_entropy\n",
    "\n",
    "    def _info_gain(self, td, fd, cur_ent):\n",
    "        p = len(td) / (len(td) + len(fd))\n",
    "        return cur_ent - p * self._entropy(td) - (1 - p) * self._entropy(fd)\n",
    "\n",
    "    def _get_leaves(self, node):\n",
    "        if isinstance(node, Leaf):\n",
    "            return [node]\n",
    "        t = self._get_leaves(node.true_child)\n",
    "        f = self._get_leaves(node.false_child)\n",
    "        return t + f\n",
    "\n",
    "    def _get_inners(self, node):\n",
    "        if isinstance(node, Leaf):\n",
    "            return []\n",
    "        t = self._get_inners(node.true_child)\n",
    "        f = self._get_inners(node.false_child)\n",
    "        return [node] + t + f\n",
    "\n",
    "    def _prune(self, node, pruned):\n",
    "        if isinstance(node, Leaf):\n",
    "            return node\n",
    "        if node.id in pruned:\n",
    "            lcnt = self._count_labels(node.data)\n",
    "            label = self._max_label(lcnt)\n",
    "            return Leaf(node.data, node.id, node.level, lcnt, label)\n",
    "        node.true_child = self._prune(node.true_child, pruned)\n",
    "        node.false_child = self._prune(node.false_child, pruned)\n",
    "        return node\n",
    "\n",
    "    def _depth_prune(self):\n",
    "        if self.max_depth < 1:\n",
    "            return\n",
    "        inners = self._get_inners(self.tree)\n",
    "        for inner in inners:\n",
    "            if inner.level >= self.max_depth:\n",
    "                self._prune(self.tree, [inner.id])\n",
    "\n",
    "    def _max_label(self, lcnt):\n",
    "        maxcnt = 0\n",
    "        label = ''\n",
    "        for key, value in lcnt.items():\n",
    "            if lcnt[key] > maxcnt:\n",
    "                maxcnt = lcnt[key]\n",
    "                label = key\n",
    "        return label\n",
    "\n",
    "    def _count_labels(self, data):\n",
    "        cnt = {}\n",
    "        for d in data:\n",
    "            label = d[-1]\n",
    "            if label not in cnt:\n",
    "                cnt[label] = 0\n",
    "            cnt[label] += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1203,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def split_data(X, y, train_size):\n",
    "    p = np.random.permutation(len(y))\n",
    "    X, y = X[p], y[p]\n",
    "    trlen = int(train_size * len(y))\n",
    "    X_train = X[:trlen]\n",
    "    X_test = X[trlen:]\n",
    "    y_train = y[:trlen]\n",
    "    y_test = y[trlen:]\n",
    "    return X_train, X_test, y_train, y_test\n",
    "\n",
    "\n",
    "def confusion_matrix(y_true, y_pred, labels):\n",
    "    m = np.zeros((labels.shape[0], labels.shape[0]), dtype=int)\n",
    "    for i in range(m.shape[0]):\n",
    "        for j in range(m.shape[1]):\n",
    "            m[i, j] = np.sum((y_true == labels[i]) & (y_pred == labels[j]))\n",
    "    return m\n",
    "\n",
    "\n",
    "def accuracy(y_true, y_pred):\n",
    "    return (y_true == y_pred).sum() / len(y_true)\n",
    "\n",
    "\n",
    "def eval(iterations, train_splits):\n",
    "    for ts in train_splits:\n",
    "        scores = []\n",
    "        for it in range(iterations):\n",
    "            print(f'Results for iteration {it + 1} with train size {ts*100:.0f}%:')\n",
    "            X_train, X_test, y_train, y_test = split_data(X.values, y.values, ts)\n",
    "            dt = DecisionTree()\n",
    "            dt.learn(X_train, y_train)\n",
    "            y_pred = dt.predict(X_test)\n",
    "            labels = np.sort(np.unique(y_test))\n",
    "            acc = accuracy(y_test, y_pred)\n",
    "            scores.append(acc)\n",
    "            print('Accuracy:', round(acc, 4))\n",
    "            print('Confusion Matrix:')\n",
    "            print(confusion_matrix(y_test, y_pred, labels))\n",
    "            print('Depth:', dt.get_depth())\n",
    "            print('Number of nodes:', dt.get_n_nodes())\n",
    "            print('Number of leaves:', dt.get_n_leaves())\n",
    "            print()\n",
    "        if iterations > 1:\n",
    "            m = round(np.mean(scores), 4)\n",
    "            s = round(np.std(scores), 4)\n",
    "            print(f'Average accuracy of {iterations} iterations with train size {ts*100:.0f}%: {m} ± {s}')\n",
    "            print('\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1204,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Results for iteration 1 with train size 25%:\n",
      "Accuracy: 0.8578\n",
      "Confusion Matrix:\n",
      "[[ 12  19]\n",
      " [ 14 187]]\n",
      "Depth: 5\n",
      "Number of nodes: 15\n",
      "Number of leaves: 8\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Part a\n",
    "eval(1, [0.25])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1205,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Results for iteration 1 with train size 25%:\n",
      "Accuracy: 0.875\n",
      "Confusion Matrix:\n",
      "[[  0  29]\n",
      " [  0 203]]\n",
      "Depth: 4\n",
      "Number of nodes: 9\n",
      "Number of leaves: 5\n",
      "\n",
      "Results for iteration 2 with train size 25%:\n",
      "Accuracy: 0.8793\n",
      "Confusion Matrix:\n",
      "[[  0  28]\n",
      " [  0 204]]\n",
      "Depth: 4\n",
      "Number of nodes: 9\n",
      "Number of leaves: 5\n",
      "\n",
      "Results for iteration 3 with train size 25%:\n",
      "Accuracy: 0.8707\n",
      "Confusion Matrix:\n",
      "[[  0  29]\n",
      " [  1 202]]\n",
      "Depth: 2\n",
      "Number of nodes: 5\n",
      "Number of leaves: 3\n",
      "\n",
      "Results for iteration 4 with train size 25%:\n",
      "Accuracy: 0.8793\n",
      "Confusion Matrix:\n",
      "[[  0  28]\n",
      " [  0 204]]\n",
      "Depth: 0\n",
      "Number of nodes: 1\n",
      "Number of leaves: 1\n",
      "\n",
      "Results for iteration 5 with train size 25%:\n",
      "Accuracy: 0.8534\n",
      "Confusion Matrix:\n",
      "[[ 13  15]\n",
      " [ 19 185]]\n",
      "Depth: 4\n",
      "Number of nodes: 11\n",
      "Number of leaves: 6\n",
      "\n",
      "Results for iteration 6 with train size 25%:\n",
      "Accuracy: 0.7716\n",
      "Confusion Matrix:\n",
      "[[ 18  13]\n",
      " [ 40 161]]\n",
      "Depth: 4\n",
      "Number of nodes: 9\n",
      "Number of leaves: 5\n",
      "\n",
      "Results for iteration 7 with train size 25%:\n",
      "Accuracy: 0.8664\n",
      "Confusion Matrix:\n",
      "[[  3  27]\n",
      " [  4 198]]\n",
      "Depth: 6\n",
      "Number of nodes: 19\n",
      "Number of leaves: 10\n",
      "\n",
      "Average accuracy of 7 iterations with train size 25%: 0.8565 ± 0.0357\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Part b\n",
    "eval(7, [0.25])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1206,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Results for iteration 1 with train size 45%:\n",
      "Accuracy: 0.8706\n",
      "Confusion Matrix:\n",
      "[[  1  20]\n",
      " [  2 147]]\n",
      "Depth: 5\n",
      "Number of nodes: 13\n",
      "Number of leaves: 7\n",
      "\n",
      "Results for iteration 2 with train size 45%:\n",
      "Accuracy: 0.8647\n",
      "Confusion Matrix:\n",
      "[[  9  13]\n",
      " [ 10 138]]\n",
      "Depth: 5\n",
      "Number of nodes: 17\n",
      "Number of leaves: 9\n",
      "\n",
      "Results for iteration 3 with train size 45%:\n",
      "Accuracy: 0.8588\n",
      "Confusion Matrix:\n",
      "[[  4  18]\n",
      " [  6 142]]\n",
      "Depth: 5\n",
      "Number of nodes: 11\n",
      "Number of leaves: 6\n",
      "\n",
      "Results for iteration 4 with train size 45%:\n",
      "Accuracy: 0.8588\n",
      "Confusion Matrix:\n",
      "[[  0  22]\n",
      " [  2 146]]\n",
      "Depth: 5\n",
      "Number of nodes: 17\n",
      "Number of leaves: 9\n",
      "\n",
      "Results for iteration 5 with train size 45%:\n",
      "Accuracy: 0.8294\n",
      "Confusion Matrix:\n",
      "[[ 14   7]\n",
      " [ 22 127]]\n",
      "Depth: 5\n",
      "Number of nodes: 21\n",
      "Number of leaves: 11\n",
      "\n",
      "Results for iteration 6 with train size 45%:\n",
      "Accuracy: 0.8824\n",
      "Confusion Matrix:\n",
      "[[ 12   7]\n",
      " [ 13 138]]\n",
      "Depth: 6\n",
      "Number of nodes: 23\n",
      "Number of leaves: 12\n",
      "\n",
      "Results for iteration 7 with train size 45%:\n",
      "Accuracy: 0.8176\n",
      "Confusion Matrix:\n",
      "[[  1  26]\n",
      " [  5 138]]\n",
      "Depth: 5\n",
      "Number of nodes: 13\n",
      "Number of leaves: 7\n",
      "\n",
      "Average accuracy of 7 iterations with train size 45%: 0.8546 ± 0.0213\n",
      "\n",
      "\n",
      "Results for iteration 1 with train size 65%:\n",
      "Accuracy: 0.8899\n",
      "Confusion Matrix:\n",
      "[[ 0 12]\n",
      " [ 0 97]]\n",
      "Depth: 5\n",
      "Number of nodes: 13\n",
      "Number of leaves: 7\n",
      "\n",
      "Results for iteration 2 with train size 65%:\n",
      "Accuracy: 0.7982\n",
      "Confusion Matrix:\n",
      "[[12  3]\n",
      " [19 75]]\n",
      "Depth: 5\n",
      "Number of nodes: 23\n",
      "Number of leaves: 12\n",
      "\n",
      "Results for iteration 3 with train size 65%:\n",
      "Accuracy: 0.8807\n",
      "Confusion Matrix:\n",
      "[[ 0 12]\n",
      " [ 1 96]]\n",
      "Depth: 6\n",
      "Number of nodes: 17\n",
      "Number of leaves: 9\n",
      "\n",
      "Results for iteration 4 with train size 65%:\n",
      "Accuracy: 0.8807\n",
      "Confusion Matrix:\n",
      "[[ 5  8]\n",
      " [ 5 91]]\n",
      "Depth: 6\n",
      "Number of nodes: 19\n",
      "Number of leaves: 10\n",
      "\n",
      "Results for iteration 5 with train size 65%:\n",
      "Accuracy: 0.844\n",
      "Confusion Matrix:\n",
      "[[ 0 16]\n",
      " [ 1 92]]\n",
      "Depth: 7\n",
      "Number of nodes: 27\n",
      "Number of leaves: 14\n",
      "\n",
      "Results for iteration 6 with train size 65%:\n",
      "Accuracy: 0.8807\n",
      "Confusion Matrix:\n",
      "[[ 0 12]\n",
      " [ 1 96]]\n",
      "Depth: 3\n",
      "Number of nodes: 9\n",
      "Number of leaves: 5\n",
      "\n",
      "Results for iteration 7 with train size 65%:\n",
      "Accuracy: 0.8899\n",
      "Confusion Matrix:\n",
      "[[ 0 12]\n",
      " [ 0 97]]\n",
      "Depth: 5\n",
      "Number of nodes: 15\n",
      "Number of leaves: 8\n",
      "\n",
      "Average accuracy of 7 iterations with train size 65%: 0.8663 ± 0.0313\n",
      "\n",
      "\n",
      "Results for iteration 1 with train size 85%:\n",
      "Accuracy: 1.0\n",
      "Confusion Matrix:\n",
      "[[47]]\n",
      "Depth: 8\n",
      "Number of nodes: 19\n",
      "Number of leaves: 10\n",
      "\n",
      "Results for iteration 2 with train size 85%:\n",
      "Accuracy: 0.8936\n",
      "Confusion Matrix:\n",
      "[[ 3  4]\n",
      " [ 1 39]]\n",
      "Depth: 6\n",
      "Number of nodes: 31\n",
      "Number of leaves: 16\n",
      "\n",
      "Results for iteration 3 with train size 85%:\n",
      "Accuracy: 0.9149\n",
      "Confusion Matrix:\n",
      "[[ 4  1]\n",
      " [ 3 39]]\n",
      "Depth: 6\n",
      "Number of nodes: 27\n",
      "Number of leaves: 14\n",
      "\n",
      "Results for iteration 4 with train size 85%:\n",
      "Accuracy: 0.8936\n",
      "Confusion Matrix:\n",
      "[[ 3  3]\n",
      " [ 2 39]]\n",
      "Depth: 6\n",
      "Number of nodes: 31\n",
      "Number of leaves: 16\n",
      "\n",
      "Results for iteration 5 with train size 85%:\n",
      "Accuracy: 0.8723\n",
      "Confusion Matrix:\n",
      "[[ 0  6]\n",
      " [ 0 41]]\n",
      "Depth: 4\n",
      "Number of nodes: 9\n",
      "Number of leaves: 5\n",
      "\n",
      "Results for iteration 6 with train size 85%:\n",
      "Accuracy: 0.7447\n",
      "Confusion Matrix:\n",
      "[[ 0 11]\n",
      " [ 1 35]]\n",
      "Depth: 8\n",
      "Number of nodes: 29\n",
      "Number of leaves: 15\n",
      "\n",
      "Results for iteration 7 with train size 85%:\n",
      "Accuracy: 0.8936\n",
      "Confusion Matrix:\n",
      "[[ 1  4]\n",
      " [ 1 41]]\n",
      "Depth: 7\n",
      "Number of nodes: 29\n",
      "Number of leaves: 15\n",
      "\n",
      "Average accuracy of 7 iterations with train size 85%: 0.8875 ± 0.0698\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Part c\n",
    "eval(7, [0.45, 0.65, 0.85])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1207,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal max depth for Train set: 5\n",
      "Optimal max depth for Test set: 4\n",
      "Maximum accuracy for Train set: 0.9004\n",
      "Maximum accuracy for Test set: 0.8718\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAcYAAAFTCAYAAACjyazZAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAA0i0lEQVR4nO3de1iUdf7/8edwhgExBBXFU5goomgeUkulzFI7mHZARarN0tokM3Nby/21patuq6umrtlpSxI1S9PdTphZ0SZiWaiFgHgGFc8cBoYB5veHyRfzgBo3A8zrcV1cl8LM/X4zF/Caz+e+78/HZLfb7YiIiAgALo5uQEREpDZRMIqIiFSiYBQREalEwSgiIlKJglFERKQSBaOIiEglbo5uQMSZbN68mWeeeYZrr70WgJKSEh555BFuv/32qz7mxIkTmTt37hU/78iRIzz77LMA/PTTT3Tp0gWAyZMn07lz5yqfn5iYSPfu3QkICLji2iK1mUn3MYrUnM2bN7NmzRpmzZoFwOnTp7n33nv54osvHNrXLbfcwpdffnlFz4mNjWXmzJmEhIQY1JWIY2jEKOJAeXl5eHl5ATBgwABCQkLo06cP3377bUXo/PnPf2bYsGFkZ2fzzTffUFhYSE5ODs899xz9+vWrCLXhw4fTqVMnMjIyaNiwIQsXLmTfvn1MmTIFT09PAgICCA0NJS4u7pI9ffzxxyxduhSTycRtt93GI488Qnx8PP/9738pKyvjrrvuok2bNqSlpfHcc8+xbNmymnipRGqMglGkhiUlJREbG4vJZMLb25sZM2YAcPjwYdauXYuvry/ffvvtBZ9bUlLCG2+8wffff8/ixYvp169fxddOnTrFiBEj6NChAw8//DDbt29nyZIlTJo0iZ49ezJ//vwqezt58iRvvPEG77//Pm5ubjz66KP079+f//znP8yaNYuQkBDWrVtHv3796NChAzNnzqyeF0WkFlEwitSwvn37VkylVhYUFISvr+95n698tqN9+/YANG3alJKSkvMeW/nrVquVPXv2VJw77Nq1K6mpqZfs7cCBA+Tm5jJmzBjgzFTv/v37efnll/nXv/7FkSNHGDBgwOV9oyJ1lIJRpJZwcfm/i8Q9PDw4duwYwcHBZGZmVnzeZDJd8hi//Xrbtm1JTU2lR48eVYYiQEhICC1atOCdd97B1dWVpUuXct111xEfH8/MmTNxc3PjzjvvZPjw4ZhMJnSJgtRHCkaRWigmJoYpU6YQEhJCUFDQVR/n2Wef5fnnn8fd3R13d3euv/76Sz4+ICCA6OhoYmJiKCkpISIigpiYGFq1asXIkSPx9vbm5ptvpkGDBnTt2pVnnnmGZcuW4eHhcdU9itQ2uipVpB5bt24d3bp1o3nz5ixYsIDmzZszfPhwR7clUqtpxChSjzVu3Jgnn3wSs9lMYGAgjz32mKNbEqn1NGIUERGpREvCiYiIVKJgFBERqUTBKCIiUkmdvfgmLCzM0S2IiEgdlp6efsHP19lghIt/UyIiIpdyqcGVplJFREQqUTCKiIhUUqenUisrLy8nJycHm83m6FYcyt3dnWbNmp2z7qaIiFy+ehOMOTk5NGjQgAYNGji6FYfKy8sjJydHm8eKiFylejOssNlsTh+KAA0aNHD6UbOIyO9Rb4JRRESkOtSbqdSa9sILL7B//37S0tJo164drq6uzJ8/n4CAgIs+5/XXX2fw4MG0aNHioo8pLS3l//2//8ehQ4ewWCzcfffdxMTEXPCxaWlpmEymis1pRUTk91MwXqW//e1vAMTGxvLaa69hNpurfM7YsWOrfExSUhLXXHMNM2bMoLy8nJEjR3L77bcTGBh43mO/+OILIiIiFIwiItXI6YKx2FrK4RMWtmcdo1NoIE0DfPDyrJ6XYcGCBfz000+YzWYmTZrEyy+/TElJCZ6enrz22mtMnTqVRx55hLfffhtPT0/S09Pp2LEjf/nLXyqO0aRJEzZt2sSmTZvo1q0b8fHxFbu5T5kyhaKiItq3b8/EiRNZs2YNiYmJ9OzZ87KCWUREqlYvzzEWFNk4frrovI+TecXkHCtkwpyNvL5mOxPmbOTQ8UJO5hVf8PEFRVd+EUvfvn159dVX2bt3L1OmTCE+Ph4/Pz+ysrLOedwNN9zAihUr2LRpEyUlJRWfDw8P56mnnuKNN96gb9++zJ07F7vdzpIlS3jooYd47733gDPTqMOGDeOZZ56pl6FYbC1l76E8/vPtbvYeyqPYWqo6TlinJmupjuqcZciI0WazMXnyZHJzcwkPD2fq1KkVX3vllVfYsmULwcHBzJgxA19fX1566SV27txJs2bNmDVrFu7u7lddu6ysnDHTE7EUn/+iRYQ2IvK6IMp/3YGy3A6bfz5MasZRduw+ft7jfbzcSHh5MK6ul//+4ez5w0aNGrFo0SI8PT3ZvXs35eXl5zwuNDS04nE2mw0PDw8AMjIy6NKlC1FRURQUFPD000+TlJTEnj172LFjB0uWLKGwsJDIyMjL7qkuOny8kAn//IpyO7iYYPrjN7L0k184mW+tthrX+Hny4JBwpr72P9WphXVqspbq1L068yfdTOtgY+5EMCQYExMTCQ8PZ968eTz//PNs27aNzp0788svv5CVlcX7779PUlISS5cupU+fPpSVlbF8+XIWLVrE+vXrGTJkyFXXdnV14a2pt2EtOT8YXUwmTuZbWf75zooX94aOTbn9hlaUX2C/Zk8PtysKRaDixvpFixbx9NNP07ZtW6Kjo/ntftAmk+mCz//uu+84efIkEydOxNfXl+bNm+Pu7k7Lli0ZOnQokZGRfPrpp7Rt25Z9+/add9z6IN9Swpa0I+e8gcnKPkXs4A6cLiy59JOvgL+vB1nZp1SnltapyVqqU/fq7Mg6VreCMTU1lcGDBwPQp08ftm7dSufOndm7dy89e/bEZDIRERFBQkICZrOZnj17Vjz2448//l3BCODr7Y6v94VHnd6ebsyfdDM7fj3H2KQazzFWNmDAACZMmMA111yDt7c3R48evaznjRo1ihdffJFhw4bh4eFBt27d6N27N9deey0vvPACBQUFBAYGMnv2bNq3b8+8efPo0qXLJa+GrUvS9pzg9Y+2M2ZoR1xMVLyB6dquMa0M+CVoYPbExfSz6tTSOjVZS3XqVp1OoedfkFhdTHYDhhzPP/88Dz30EGFhYWzYsIGdO3fy5JNPkpGRwezZs1m8eDGffvopH374Id27d6dDhw7ccsst7Ny5k6VLlzJjxoxzjrdgwQIWLlx4Xp3Ku2vs2bOHNm3aVPe3UifVxdfCbrfz8f/28Na6HdzVN5QRt7Yj91SR4W9gzl6MpTq1s05N1lId56oTFhZWs9tOmc1mLBYLABaLBV9fXwDatWtHz549GT16NP379ycgIOCij60sLi6OuLi4cz6n/Rjrj+KSUhZ9kMrmHYd4NqY7N0Y2A6C1t7thUyVneXm60Tq4gerU0jo1WUt1VOcsQ65KjYiIICUlBYDk5OSKC0WOHj1K48aNWb58Oa1bt6Zr164Xfaw4h5xjBUx+NYldB04xZ0L/ilAUEXEUQ4Jx8ODBpKWlER0djaurKyUlJSQkJBAQEMDGjRt54IEH+Oyzz7j//vvp3r07rq6ujBgxgrS0NG677TYjWpJaKOWXwzwz92uaBZmZM6EfLZr4ObolERFjzjHWhN/OD9fF82pGqe2vRVm5neWJO/lgQyYPDglnWFToRa/SFRExQo2fYxS5mHxLCbOX/UDWwVO8PK43ndsGObolEZFzKBilxuw6eIqZ727hGl9P5k2MIrCht6NbEhE5j4LxKl3N7hoAn3zyCQMGDMDT0/Ocz61YsYLy8nICAgKYOXPmBZd5s1qtbNiw4Xff5+kIX6Ts418fbmNgz5Y8OjQCdzdXR7ckInJBTheM5SXF2E4doXjfz3i16oh7wya4eHhd8XGuZncNgOXLl9O/f/9zgnHJkiV88MEHuLu7Ex8fz4oVKxgzZsx5zz169CifffZZnQpGW2kZS9ZsZ+P3Bxh/fyS3dG/p6JZERC6pXgZjWXEhdtsF1ukzuVBWeIrstyaDvRxMLjQf8w9czQ3P/P+3D3f3xNXr8hfonj9/Pps3b8bDw4MZM2ZQWFjIX/7yF+x2OwMHDqRLly6kpaUxffp0Zs6cWfE8Nzc3PvzwQwYOHMioUaMuerxly5aRkpLCZ599xqBBg67oNXGEoyeLmPluCnmFJfzjqX5c29zf0S2JiFSp3gWjvbyM/Qsfx261nPc1r5Yd8W7T6f9C0F6OJXMLRXu2Ubz/l/Meb/L0ofUz72ByqXraLy0tjf3795OQkMAvv/zCokWLaN++PXfccQejR4/mo48+qljlp/Ki6nBmXdVFixaxcOFC2rRpw4wZMygoKDjveE888QTZ2dl1IhRTM47yynvf067lNbw8tje+Ph6ObklE5LLUu2A0ubjScvxrlxwxnvzm/YoRo891PfDrMvCiI8bLCUU4c4vEtm3biI2NBcDf3597772XhQsX8uCDD3LTTTdd8Hn5+fmcPHmSadOmYbfb+eCDD/jnP//JwIEDzzteXWC32/lw4y7e+zSN6FvbET0wDBcX3YohInVHvQtG4Mz050WmQF08vGj+6GyK9/2Md6sI3Bo2vqpzjL/VokUL+vTpw0svvcShQ4f49ttv+eqrrxg0aBB/+tOfGDlyJDExMQDn7Ihhs9l47rnnWLZsGX5+frRr144tW7Zc8Hgmk6lW76ZhKbYxb8WPbNt1jKmP3ED3Dk0c3ZKIyBWrl8F4KS4eXng2boVn41bVetxOnTrx2WefMXr0aIqKipg6dSp+fn786U9/wmw207FjR3x9fenUqRNTpkxhwYIFAAQEBPDYY48xevRovL29MZvNTJs2jWbNmp13vICAAPbv38/atWsZOnRotfb/e+07nMfMd1LwdHdj3sT+NG1U/zZPFhHnoJVv6qGafi2Sfszm1fd/pE/nZjxxb2e8PJzu/ZaI1DFa+UYMUVpWzjv//YWP/7ebx+7pxODerbW0m4jUeQpGuSJn90TbvusobZr7A3ZmPnkT7VvVj42SRUQUjHJFDp+wMGHOxopdtOc9E0WbZnXjilkRkcthyLZTjuDu7k5eXp6j23C4vLw83N3dDTv+9l1HKf/1rHS5HX7efdywWiIijlBvRozNmjUjJyeH48ed+w+1u7s7zZoZt9nvdS2uwcVExYixU2igYbVERByh3gSji4sLISEhjm6jXss8cJLEzfv459P9Sdt7gk6hgTQJ8HF0WyIi1areBKMYq7SsnAXv/0S7ltcQGtKQ0JCGjm5JRMQQ9eYcoxhrzVe7OF1g5eE7Ozq6FRERQykYpUo5RwtYkZjO48M74+tt3IU9IiK1gYJRLslut7Pog1S6dWhC707GXdQjIlJbKBjlkr5I2c+ug6cYN6yTo1sREakRCka5qJN5xbz1n595+M6ONPL3dnQ7IiI1QsEoF/X6R9tpHdyA22+o3p1IRERqMwWjXNDmHYdI3nGYJ++L1EbDIuJUFIxyHkuxjcWrtzFiYDtaNPFzdDsiIjVKwSjnWfpJGr7e7gy/+TpHtyIiUuMUjHKOtD0n+HTTXsY/0AV3N/14iIjz0V8+qWArLWPBqh+548Y22l9RRJyWglEqfLAhkyJrGaMHtXd0KyIiDqNgFAD2H87j/Q2Z/PHezvh4adk3EXFeCkahvNzOwlWp9OkUTI/wpo5uR0TEoRSMwqeb9nIwN5/H7tGybyIiCkYnd+xUEe9+/AuP3BVBQz9PR7cjIuJwCkYnZrfbeW31Ntq1bMiAHi0c3Y6ISK2gYHRi3207xI8ZR3nyvi6YTFr2TUQEFIxOq8BSwmtrthFzexjBgWZHtyMiUmsoGJ3Uv//7CwENvBjaL9TRrYiI1CoKRie0bddRNmzZT9wDXXB11Y+AiEhl+qvoZKy2MhauSmVov1DahjR0dDsiIrWOmxEHtdlsTJ48mdzcXMLDw5k6dWrF1+bOnUtycjJ+fn7MmzcPHx8fnnvuOQ4cOECbNm2YNm0abm6GtCXAyvXp2O12Rt4e5uhWRERqJUNGjImJiYSHh5OQkIDFYmHbtm0A5OXlsWnTJlauXElUVBTr1q1jw4YN+Pr6smLFCjp37szHH39sREsC7Mk5zeqNu3jyvki8PPTmQ0TkQgwJxtTUVHr06AFAnz592Lp1KwB+fn4EBwdjs9mwWCyYzWb27NnDDTfcAEBERATbt283oiWnV1Zu59X3fyKqWwhd2jV2dDsiIrWWIcOGgoICfHx8APD29qawsBA4M8VqtVoZMmQINpuN1atXk5qaysaNGxk0aBDfffcdxcXF5x1vwYIFLFy40IhWncZ/knZz9KSFlx7r7ehWRERqNUNGjGazGYvFAoDFYsHX1xeApKQk/P39Wb9+PdOmTWPOnDlERUVhNpuJiYmhpKQEf3//844XFxdHenr6OR9y+Y6csPDeZ2mMvacTDcwejm5HRKRWMyQYIyIiSElJASA5OZnIyEgAfHx88Pb2BiAoKIjCwkKysrLo1asXy5Ytw8fHh+7duxvRktOy2+3864NUOoUG0rdLc0e3IyJS6xkSjIMHDyYtLY3o6GhcXV0pKSkhISGBXr16YbfbGTVqFNOnTycuLo7g4GCWLl1KdHQ0Bw4cICoqyoiWnNZXWw/yy57jPHFvZy37JiJyGUx2u93u6CauRlhYmKZUq3C6wMoTf/+SEbe14+6+WuFGROSsS2WIbvCvx95ct4NmgWbuuPFaR7ciIlJnKBjrqa07c/n2p2zGP9AFVxdNoYqIXC4FYz1UbC1l0Yep3HvzdbQObuDodkRE6hQFYz207POduLu68MCt7RzdiohInaNgrGcOHMnnu205xD3QBQ93V0e3IyJS52jBzHqi2FrK4eOFpPxymGdjutGm2fkLJYiISNUUjPXE4ROFTPjnV5TbwcUE8yfdrPOLIiJXQVOp9YC1pIzv045Q/usdqeV22JF1zLFNiYjUUQrGOu5gbj4vv5VMWKsAzt6V4WKCTqGBjm1MRKSO0lRqHbZpew5zl/9Iz/CmtA5uwPxJN7Mj6xidQgNpEuDj6PZEROokBWMdVFZWTvynaaz9JotH7orgzpvaYDKZ8PPx0HlFEZHfScFYx5wusPJK/PccOJLP9MdvpOO1jRzdkohIvaJgrEMy9p9k5jspNGlkZt4zUQQ08HJ0SyIi9Y6CsQ6w2+18nryPJWu2c8eNbXj4znDcXHXdlIiIERSMtZzVVsZrH24jKTWbiSO70q9riKNbEhGp1xSMtdiRExZmvptCUXEpcyb0o1VTXVgjImI0BWMt9cPOI8xZ9gMdr23E0yOux+zt7uiWREScgoKxlikvt/P+hgxWJKYTM6g99958HS7aT1FEpMYoGGuRgiIb/0z4gfR9J/nrY73o0q6xo1sSEXE6CsZaYk/OaWa+swVfH3fmTuxP42u0co2IiCMoGGuBjT8cYOGqVG7uFsLYezppH0UREQdSMDqQrbSct9ft4PPN+3hieGcG3tDK0S2JiDg9BaODHD9dxKx3t3Air5hXxvelbYuGjm5JRERQMDrE9qxjvLL0e65t7s9fxvSigdnD0S2JiMivFIw1yG63s/abLN79+BfuveU6Rt7WHlfdiiEiUqs4bTAWW0s5fMLC9l/3L2wa4IOXZ/W/HBV1dh0lNKQhh44VMuWhnvTs2LTaa4mIyO/ntMF4+ISFCXM2Um4/s+P9P5/uj8kEpWX2aqvh5mrCbodn5n1dUWfuxCiube5fbTVERKR6OW0wbs86RvmvGVhuhy1pR0jNPMrPu49XW42I0EZ0bht0Tp1f9hxXMIqI1GJOG4ydQgNxMVExkusdEcyIgWHVXmfvoTyWf76zok6n0MBqryEiItXHZLfbq2/usAaFhYWRnp5+1c8/e+5vx6/nGJsYfI7R6DoiInL5LpUhTvsX2svTjdbBDWgdbOxWTjVVR0REqoe2gRcREalEwSgiIlKJglFERKQSBaOIiEglCkYREZFKFIwiIiKVKBhFREQqUTCKiIhUYsgN/jabjcmTJ5Obm0t4eDhTp06t+NrcuXNJTk7Gz8+PefPmYTabmTJlCvv27aNJkybMmTMHV1dXI9oSERGpkiEjxsTERMLDw0lISMBisbBt2zYA8vLy2LRpEytXriQqKop169axc+dOiouLWb58OcHBwXz77bdGtCQiInJZDAnG1NRUevToAUCfPn3YunUrAH5+fgQHB2Oz2bBYLJjNZkJCQvDy8sJut1NYWIjZbDaiJRERkctiyFRqQUEBPj4+AHh7e1NYWAicmWK1Wq0MGTIEm83G6tWrKS8vZ/fu3QwaNAgPD49zpl3PWrBgAQsXLjSiVRERkXMYMmI0m81YLBYALBYLvr6+ACQlJeHv78/69euZNm0ac+bMYe3atdx44418/vnnxMTE8Oabb553vLi4ONLT08/5EBERMYIhwRgREUFKSgoAycnJREZGAuDj44O3tzcAQUFBFBYW4uPjUzG6DAwMrBhdioiIOIIhwTh48GDS0tKIjo7G1dWVkpISEhIS6NWrF3a7nVGjRjF9+nTi4uK4++672bFjBzExMSxfvpyHH37YiJZEREQui9NuVCwiIs7rUhmiG/xFREQqUTCKiIhUomAUERGpRMEoIiJSiYJRRESkEgWjiIhIJQpGERGRShSMIiIilVQZjFlZWTXRh4iISK1Q5e4ar776KsePH+eOO+7gzjvvxM/Pryb6EhERcYgqg3H+/Pnk5eXx8ccfM3HiRBo0aMDw4cO56aabaqI/ERGRGnVZ5xh3795Neno6J0+epGXLlqSkpDBhwgSjexMREalxVY4Y77rrLtq1a8fw4cN58cUXMZlMAEyaNMnw5kRERGpalbtrnDp1ioyMDHr27MmqVasYNGhQrTjPqN01RETkav2u3TUmTpxIQUEBAB4eHhopiohIvVZlMBYVFXHLLbcAMHToUIqKigxvSkRExFGqPMdoNptZu3YtkZGR7NixA29v75roS0RExCGqHDHOmjWLbdu2MX36dLZv386sWbNqoi8RERGHqHLEGBgYyKhRo7DZbADs2LGDfv36Gd6YiIiII1QZjOPHj8disZCbm0tZWRlBQUEKRhERqbeqnEo9fvw4//73v+nSpQsfffQRZWVlNdGXiIiIQ1QZjB4eHpSVlVFYWIiXlxfFxcU10ZeIiIhDVBmM999/P2+99RY33HADt99+OyEhITXRl4iIiENUeY6xrKyMsWPHAmh3DRERqfeqHDF++OGHnF01TqEoIiL1XZUjxtOnTxMVFUXLli0BMJlMLF261PDGREREHKHKYFy8eHFN9CEiIlIrVBmMa9asOe9z48ePN6QZERERR6syGJs3bw6A3W4nLS2tYqcNERGR+qjKYBw2bNg5///DH/5gWDMiIiKOVmUwfvTRRxX/zs3N5dSpUwa2IyIi4lhVBuPBgwcr/u3p6cmrr75qaEMiIiKOVOV9jP369SMwMJDx48ezZ88e8vPza6IvqaXKS4qx5u7j9JZPsObuo7zEmCUCVUd1arqW6qjOWVWOGF966SXmzp0LwLhx45gyZQoJCQmGNSS1m+3UEbLffBbs5WByITjmr5z634eUFZ6qthqu5oY0vPFeDi37q+o4cZ2arKU6da9O80dn49m4VbXVqKzKYHR1da24ub9Vq1a4uFQ5yJR6rHjfz2d+MAHs5VgPZdGgxx3V+0vg2xDroSzVcfI6NVlLdepeneJ9PzsuGMPCwnjhhReIjIxkx44dhIaGGtKI1A1erTqCyaXiXZvPtV3waNyy2utYGwTCl6rj7HVqspbq1K063q0iqr3GWSb72YVQL6K8vJz169ezb98+2rRpw8CBAw1r5kqEhYWRnp7u6Dacju1EDqWnj1Fy7CDerSJwa9gYFw+vaq9TXlKM7dQRivf9rDpOXKcma6mOc9W5VIZUGYyrVq1i//79TJo0iTFjxnD33XczdOjQq26muigYHSPvxy8o2PENzWJfdnQrIiJX7VIZUuUJw4SEBCZMmADAa6+9pgtvnJw1JxO3hkGObkNExDBVnmN0cXHBZDJV/Pty2Gw2Jk+eTG5uLuHh4UydOrXia3PnziU5ORk/Pz/mzZtHYmJixXqs+/fvZ9SoUYwbN+5qvhepAcXZGfh3G+ToNkREDFNl0g0fPpx77rmHSZMmcd999xEVFVXlQRMTEwkPDychIQGLxcK2bdsAyMvLY9OmTaxcuZKoqCjWrVvH8OHDiY+PZ/HixQQHBxMbG/u7vykxRrm1CNvRA3g2v87RrYiIGKbKYIyJiWHJkiWEhoZitVrZsGFDlQdNTU2lR48eAPTp04etW7cCZzY6Dg4OxmazYbFYMJvNFc9ZunQpMTEx+Pj4XO33IgazHtqFyc0dD4MukRYRqQ0uOZW6fft2li9fTkpKCkBFQFaloKCgIuC8vb0pLCwEzkyxWq1WhgwZgs1mY/Xq1RXP2bRpE2PHjr3g8RYsWMDChQsv7zsSw1hzMvEMDsXk4uroVkREDHPREeP999/PO++8w+23385nn31G69atL/seRrPZjMViAcBiseDr6wtAUlIS/v7+rF+/nmnTpjFnzhzgTACHhYXh5nbhnI6LiyM9Pf2cD6l5xdkZmkYVkXrvosHYrVs39uzZQ1JSEjt37qy4AOdyREREVIwyk5OTiYyMBMDHxwdvb28AgoKCKkaSmzdvpkuXLlf7PUgNsNvtWLMz8WzWztGtiIgY6qLB+Oc//5lVq1bRu3dvFi9eTGpqKosXLz5nt42LGTx4MGlpaURHR+Pq6kpJSQkJCQn06tULu93OqFGjmD59OnFxccCZHTyCg4Or77uSaleWd4yywlN4acQoIvVclTf4n3XixAnWrVvHmjVrWLt2rdF9VUk3+NesgrTvOJ74Ni2feuOKZg9ERGqj33WD/1kBAQE8/PDDtSIUpeZZszPwbN5OoSgi9Z62ypDLUpydiVczTaOKSP2nYJQq2ctKKTm8W1ekiohTUDBKlUpy92MvK8UzWFuOiUj9p2CUKhVnZ+ARFIKLh7ejWxERMZyCUapkzdH9iyLiPBSMUiVrjla8ERHnoWCUSyorKsB2PAcvjRhFxEkoGOWSrId2YfLwwj2wuaNbERGpEQpGuSRrdgaeza7Tjhoi4jQUjHJJurFfRJyNglEuym63/3pFqoJRRJyHglEuqvTUEcqL8nVFqog4FQWjXFRxdgZu/kG4+V7j6FZERGqMglEu6szGxBotiohzUTDKRVlzMjWNKiJOR8EoF2QvtWE9skc39ouI01EwygVZj+wBux2Ppm0c3YqISI1SMMoFWbMz8GjcGhd3T0e3IiJSoxSMckHFOZl46fyiiDghBaNckK5IFRFnpWCU85QVnqb01BFdkSoiTknBKOcpzsnExcsX94BgR7ciIlLjFIxynjPTqG0xmfTjISLOR3/55DxaOFxEnJmCUc5ht5dj1RWpIuLEFIxyDtvxHMqtFo0YRcRpKRjlHNbsDNyuaYqrTwNHtyIi4hAKRjnHmRv7tT6qiDgvBaOcQzf2i4izUzBKhXKblZLcfQpGEXFqCkapYD2UhcnFFc+mrR3dioiIwygYpYI1JxOPpm0wubo7uhUREYdRMEoFnV8UEVEwSiXF2Rm6sV9EnJ6CUQAozT9BWf5xPHWrhog4OQWjAGemUV18GuDm39jRrYiIOJSCUQAozsnAq9l1mEwmR7ciIuJQCkYBfr3wRtOoIiLGBKPNZuPpp59m1KhRTJ8+/ZyvzZ07l+joaB599FEKCgoAWLx4MSNHjiQmJoYjR44Y0ZJcgr28DOuhLF2RKiKCQcGYmJhIeHg4CQkJWCwWtm3bBkBeXh6bNm1i5cqVREVFsW7dOtLT00lPT2f58uVMnDiR/fv3G9GSXELJ0QPYbVa8mrV1dCsiIg5nSDCmpqbSo0cPAPr06cPWrVsB8PPzIzg4GJvNhsViwWw28/333xMUFMSYMWP44IMP6Ny5sxEtySVYczJxD2yOi5fZ0a2IiDicIcFYUFCAj48PAN7e3hQWFgJnplitVitDhgwhISGBvn37cvr0aQ4cOMAbb7zBtddey6pVq8473oIFCwgLCzvnQ6qPNTtD06giIr8yJBjNZjMWiwUAi8WCr68vAElJSfj7+7N+/XqmTZvGnDlz8Pf354YbbsDFxYXevXuTkZFx3vHi4uIqplzPfkj1Kc7JxEvBKCICGBSMERERpKSkAJCcnExkZCQAPj4+eHt7AxAUFERhYSGdOnViy5YtAOzYsYPWrVsb0ZJcRLnVgu3oQV2RKiLyK0OCcfDgwaSlpREdHY2rqyslJSUkJCTQq1cv7HZ7xdWqcXFxdO7cmTZt2nD//fezYcMGHnjgASNakouwHsrC5O6BR+OWjm5FRKRWMNntdrujm7gaYWFhmlKtBif/t5qirK00e3B61Q8WEaknLpUhusHfyVmzM/DUwuEiIhUUjE7MbrdjzdGKNyIilSkYnVhp3lHKCk/h1UzBKCJyloLRiVmzM3H1DcCtQSNHtyIiUmsoGJ2Yzi+KiJxPwejEdGO/iMj5FIxOyl5WSsnhPbrwRkTkNxSMTqokdx/2slI8g691dCsiIrWKgtFJFWdn4BHUAhcPb0e3IiJSqygYnZQ1J1M7aoiIXICC0UlZs3Vjv4jIhSgYnVBZUT62Ezl46VYNEZHzKBidkDVnFyYPb9wbNXd0KyIitY6C0QlZszPxbNYWk4uro1sREal1FIxOqDgnQzf2i4hchILRyZzZUWOXLrwREbkIBaOTKT15mPKifN2qISJyEQpGJ1OcnYGbfxBuvg0d3YqISK2kYHQyurFfROTSFIxORjf2i4hcmoLRiZSXlmA9slc39ouIXIKC0YmUHN4D2PFo0sbRrYiI1FoKRidizcnEo3FrXNw9Hd2KiEitpWB0IsXZGZpGFRGpgoLRiVhzMvFUMIqIXJKC0UmUFZ6m9FQuns10RaqIyKUoGJ1EcXYGLl6+uAcEO7oVEZFaTcHoJM7c2N8Wk8nk6FZERGo1BaOTOHN+UdOoIiJVUTA6Abu9nOKcXdpqSkTkMigYnYDtWDZ2q0VrpIqIXAYFoxOw5mTidk1TXH38HN2KiEitp2B0AsXZmXjp/KKIyGVRMDoBbTUlInL5FIz1XHlJMSW5+3RFqojIZVIw1nPWw1mYXFzxbNLK0a2IiNQJCsZ6zpqdiUfTazG5uju6FRGROkHBWM9p4XARkSujYKznirMzdGO/iMgVcDPioDabjcmTJ5Obm0t4eDhTp06t+NrcuXNJTk7Gz8+PefPm4evry4gRI3B3PzPV99hjj9GvXz8j2nI6pXnHKcs/oRGjiMgVMGTEmJiYSHh4OAkJCVgsFrZt2wZAXl4emzZtYuXKlURFRbFu3TrKysrw8fEhPj6e+Ph4hWI1suZk4uLTADf/xo5uRUSkzjAkGFNTU+nRowcAffr0YevWrQD4+fkRHByMzWbDYrFgNpvZu3cvhw8fJjY2lueee46ioiIjWnJKxTlnbuzXjhoiIpfPkGAsKCjAx8cHAG9vbwoLC4EzU6xWq5UhQ4aQkJBA3759cXNzY+zYscTHx9OhQwfi4+ONaMkpWbMzdGO/iMgVMiQYzWYzFosFAIvFgq+vLwBJSUn4+/uzfv16pk2bxpw5cwgODmbw4MEA9O3bl127dp13vAULFhAWFnbOh1yavbwM66EsnV8UEblChgRjREQEKSkpACQnJxMZGQmAj48P3t7eAAQFBVFYWMiXX37JvHnzAPjhhx8uGHpxcXGkp6ef8yGXVnL0AHZbCV7BbR3diohInWJIMA4ePJi0tDSio6NxdXWlpKSEhIQEevXqhd1uZ9SoUUyfPp24uDgGDhzIkSNHGD16NN999x2jRo0yoiWnY83OwD2wOS5eZke3IiJSp5jsdrvd0U1cjbCwMI0cLyH3P4sAaHzXkw7uRESk9rlUhugG/3rKmpOBl84viohcMQVjPVRutWA7lq0rUkVEroKCsR6y5uzC5O6BR+OWjm5FRKTOUTDWQ8XZGXgGh2JycXV0KyIidY6CsR6y5mRqGlVE5CopGOsZu92uraZERH4HBWM9U3r6KGWFp/Fq1s7RrYiI1EkKxnrGmpOJq18Abg0aOboVEZE6ScFYzxRr4XARkd9FwVjPWLPPbDUlIiJXR8FYj9jLbJQc3q0Ro4jI76BgrEdKjmbjGRKGZ3Coo1sREamznDYYy0uKsebu4/SWT7Dm7qO8pLjO17GX2fBu0xnbqSOG1RERqe/cHN2Ao9hOHSH7zWfBXg4mF4JHvcjxDe9SVnCy2mq4+l5DowEPcSjhpRqtc/LrFTR/dDaejVtVWw0REWfhtMFYvO/nM2EFYC/HemQPjW4bQ3lRfrXVcPH2w5qT6ZA6xft+VjCKiFwFpw1Gr1YdweRSMZLzaRNpyKLbLp7eDqnj3Sqi2muIiDgDp92ouLykGNupIxTv+xnvVhG4NWyMi4dXNXZYP+uIiNQHl8oQpx0xunh44dm4leHTjfWtjohIfee0V6WKiIhciIJRRESkEgWjiIhIJQpGERGRShSMIiIilSgYRUREKlEwioiIVKJgFBERqUTBKCIiUkmdXvkmLCzM0S2IiEh9Y3dy7dq1Ux3VUZ1aXqcma6mO6mgqVUREpBIFo4iISCUKRhERkUqcPhjHjx+vOqqjOrW8Tk3WUh3VqbMbFYuIiBjB6UeMIiIilTl9MM6cOZONGzcadvyCggLGjRvH6NGjeeqpp7DZbIbUsVgsPPbYY4wYMYLXX3/dkBqVvfXWW/z97383tMaAAQOIjY0lNjaWtLQ0Q2rY7XZefvllYmJiGDNmDIWFhYbUef311yu+l169evHf//7XkDpWq5Vx48YxcuRIpk+fbkgNgMLCwoo6r7zyimF14P9+R/Pz8xkzZgwjRozgjTfeMKwOwIYNGwz7+T5b5/Dhwzz00EOMGjWKv/71r4bVOXLkCLGxsTzwwAN89NFHhtU56+WXX+a9994zrE5+fj433XRTxe/T0aNHq72W0wZjeXk5zz33HOvXrze0zocffsjAgQN57733CA0N5YsvvjCkztq1a7n11ltZsWIFmzZt4tSpU4bUAcjMzCQxMdGw4wMcOXKE66+/nvj4eOLj4+nQoYMhdb766iu8vLxYtmwZI0eOJCcnx5A6Y8eOJT4+nlmzZtG+fXuGDBliSJ2kpCTatm3L8uXLyc3NJSsry5A6q1atokePHixfvhwXFxe+//77aq/x29/R5cuXM3z4cJYvX05ycjK5ubmG1Fm2bJkhYf/bOm+//TaPP/44CQkJWCwWtm3bZkid+Ph4xo0bx4oVK1i2bBnVdfbsQn9Dv/vuO3788cdqOf7F6mRkZHDfffdV/G0ICgqq1npQx1e++T3Ky8u54447CAkJMbTOvffei7u7OwBlZWUV/65uI0eOpKysjJKSEoqKigyrY7PZWLhwIU888QSbN282pAZAeno6WVlZxMTEEB4ezpQpU3Bxqf73cVu2bMHd3Z2HH36Ydu3aMWDAgGqvUdm//vUvnnrqKUO+F4C2bdvyww8/YLfbKSoqwsfHx5A6e/bs4b777gMgIiKC7du3071792qt8dvf0dTUVO655x5MJhM9e/YkNTWVgQMHVnudkJAQ/vrXv/LNN9/87mNfqs4f//hHfH19gTN/Gzw8PAypM2nSJADy8/MBMJlMhtTJz89n1apVxMTEUFxcXC01LlQnIyOD5ORkYmJi6NevH+PGjau2Wmc57YjRzc2Nfv36GV7H19cXT09PfvzxR1JSUoiKijKslsVi4Y477iAgIKDafsl+67XXXiM2NhZvb29Djn/WNddcw/jx41m2bBkAn332mSF1Tp8+zenTp3nnnXewWq189dVXhtQBKC4uJicnh+uvv96wGq6urmzcuJFBgwZRVlZG06ZNDalz3XXX8d133wFnRgnV+YfwrN/+jhYUFFQEvbe3d7VNe/+2Tv/+/Q154/LbOg0bNsTNzY3ExEQsFgvt27c3pI7JZGL37t3cfffddOrUqdpGjL+t849//IMJEyZU+2v32zotW7bk2WefJT4+nu3bt/PTTz9Vaz1w4mCsST/88APTp09n/vz5uLkZN0j38/Nj/fr1tG/fnjVr1hhSY+PGjcyfP58ZM2bwySefGBYk7dq1o2/fvgDcdNNNZGZmGlKnQYMG9OnTB4DevXsbVgfOTNv279/fsOMDvPfeezz66KN8/vnndOzYkXXr1hlS5/7772fv3r3Exsbi5+eHv7+/IXUqM5vNWCwW4MybwLOjrbosMTGR+Ph4/vGPfxhaJzQ0lK+++gqLxVLxhqa6bdmyhb/85S+8/vrrLF26lB07dhhSp2vXrlx//fW4uLjQp08fdu3aVe01FIwG27t3L3/7299YvHgxTZo0MazOO++8U3EC3Gw2V9t0yW+tXr2a+Ph4nn/+eYYMGWLYCPi9995j5cqVAGzdutWwBeM7d+7Mli1bANixYwetWrUypA7A5s2biYyMNOz4AD4+PhWjqsDAQMMuJtq+fTsjRowgPj6eoqIiunXrZkidyiIiIkhJScFut7NlyxY6depkeE0jff/997z77rssXrzY0JD/+9//zs6dO4EzPx9GTeN/+umnxMfHM3bsWB588EEiIiIMqTN79my+/vprwLi/DQpGg7355pvk5+czadIkYmNjDbvY54477mDp0qXExsbyyy+/MHToUEPq1JTo6Gi+/vprYmNjOXnyZLWcS7qQgQMHkp+fT3R0NDk5Odx6662G1AE4ePAgzZo1M+z4ALGxsaxZs4bRo0eTkpLCsGHDDKnTokULZs6cyYgRIwgICKiRnW5iYmJYu3Yt999/P927dzf0jWZNWLRoEadPn+aJJ54gNja22i9aOeu+++5j2rRpjB49GhcXF3r37m1InZoyduxY3n77bWJiYmjRooUhb5B0g7+IiEglGjGKiIhUomAUERGpRMEoIiJSiYJRRESkEgWjiIhIJQpGEQfZvHkzYWFhFfdkwZnVXSIjI1m9evVVH/PGG28kNjaWmJgYHnzwQVJTU6/4OCkpKWRlZXHw4EFiY2OvqheRukrBKOJAbdq0OWe5uy+++ILAwMDfdcy+ffsSHx/PsmXLmDlzJn/+858pKiq6omOsXr2aY8eO/a4+ROoqp11EXKQ2iIyMJC0tjdLSUtzc3Pjyyy8rFhmw2Wy88MILHDt2jNzcXP7whz8wcOBAoqOjef311zl48CBvvPEGb7755kVXM2nevDldu3Zl69atRERE8Pzzz5OXl4e7uzvTp0+nvLycSZMm4e/vT25uLsOHD6dHjx4kJSWRlpbGjBkzyM3N5fHHH+fo0aP079+fp556qiZfIpEap2AUcSCTyUTv3r3ZtGkTnTp1wtXVtWJ5sMOHD3PjjTcydOhQDh06xPjx47n33nt58cUXeeGFF8jPz2fJkiVVLvHVqFEjTp06xZIlS7j11lsZNmwYW7ZsYfbs2TzzzDNkZ2fz1ltv4eHhwT333MPgwYPp27cvw4YNw9/fn8LCQmbPno2Hhwe33HKLglHqPQWjiIMNHjyYlStXcvjwYW677baKRZH9/f1JSUkhKSkJs9lMaWkpAL169WL27Nl07dqVxo0bV3n8nJwc+vfvz0cffcSWLVtYvXo1dru9YkH7jh07VoRxWFgYBw8ePOf5rVu3rvi6Ubu2iNQmOsco4mCdO3cmPT2dDRs2cPPNN1d8fs2aNYSEhDB79mxuv/32iu2CVq9eTYcOHcjIyKhyc9sDBw6QlpZGZGQkbdq0qdgwefr06dx2223AmY2nS0pKKCkpITMzk1atWmEymSrqGbUgvUhtpRGjSC3Qu3dvDh06hJeXV8XnevXqxaRJk/j6669p1KgRpaWlHDhwgH//+9+sWLGCw4cP8/TTT7Ny5cpzNiROSkoiNjYWFxcXXFxcmD17Nu7u7jz++OO88MILvPvuuxQVFfH8888DZ/Zw/OMf/8iJEyd45JFHCAgIoHPnzsyaNYupU6fW+Gsh4mhaRFzEiR08eJApU6YQHx/v6FZEag1NpYqIiFSiEaOIiEglGjGKiIhUomAUERGpRMEoIiJSiYJRRESkEgWjiIhIJQpGERGRSv4/zddTyrBnGLUAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 460.8x345.6 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Part d\n",
    "max_depths = list(range(1, 16))\n",
    "train_scores = []\n",
    "test_scores = []\n",
    "\n",
    "X_train, X_test, y_train, y_test = split_data(X.values, y.values, 0.75)\n",
    "\n",
    "for md in max_depths:\n",
    "    dt = DecisionTree(max_depth=md)\n",
    "    dt.learn(X_train, y_train)\n",
    "    train_scores.append(accuracy(y_train, dt.predict(X_train)))\n",
    "    test_scores.append(accuracy(y_test, dt.predict(X_test)))\n",
    "\n",
    "print('Optimal max depth for Train set:', max_depths[np.argmax(train_scores)])\n",
    "print('Optimal max depth for Test set:', max_depths[np.argmax(test_scores)])\n",
    "print('Maximum accuracy for Train set:', round(max(train_scores), 4))\n",
    "print('Maximum accuracy for Test set:', round(max(test_scores), 4))\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "sns.lineplot(x=max_depths, y=train_scores, label='Train Set', marker='o', ax=ax)\n",
    "sns.lineplot(x=max_depths, y=test_scores, label='Test Set', marker='o', ax=ax)\n",
    "ax.set(\n",
    "    title='Pruning Test',\n",
    "    xlabel='Max Depth',\n",
    "    ylabel='Accuracy',\n",
    "    xticks=max_depths,\n",
    ")\n",
    "fig.savefig('P3_d.png')\n",
    "plt.show()\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.2 64-bit",
   "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.10.2"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "2b324498af64d22b4773901be112d66dec816013b7f64fed368c8550f7daba2d"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}