Skip to content

Instantly share code, notes, and snippets.

@bentrevett

bentrevett/gist:60bedce84237aeadabf9e344ef538e7d

Created February 8, 2024 21:21
Show Gist options
  • Save bentrevett/60bedce84237aeadabf9e344ef538e7d to your computer and use it in GitHub Desktop.
Save bentrevett/60bedce84237aeadabf9e344ef538e7d to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
gistfile1.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"id": "2c2dd28e-ade8-435f-a670-f354958a9b15",
"metadata": {},
"outputs": [],
"source": [
"# Sources\n",
"# https://anderfernandez.com/en/blog/code-decision-tree-python-from-scratch/"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "ff7525de-162f-40ce-bb31-c95af1383ca1",
"metadata": {},
"outputs": [],
"source": [
"import pandas as pd\n",
"import numpy as np\n",
"import itertools\n",
"import matplotlib.pyplot as plt"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "a90b7f7f-f295-49c3-8724-3ee81f49baaf",
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>Gender</th>\n",
" <th>Height</th>\n",
" <th>Weight</th>\n",
" <th>Index</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>Male</td>\n",
" <td>174</td>\n",
" <td>96</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>Male</td>\n",
" <td>189</td>\n",
" <td>87</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>Female</td>\n",
" <td>185</td>\n",
" <td>110</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>Female</td>\n",
" <td>195</td>\n",
" <td>104</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <th>4</th>\n",
" <td>Male</td>\n",
" <td>149</td>\n",
" <td>61</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <th>...</th>\n",
" <td>...</td>\n",
" <td>...</td>\n",
" <td>...</td>\n",
" <td>...</td>\n",
" </tr>\n",
" <tr>\n",
" <th>495</th>\n",
" <td>Female</td>\n",
" <td>150</td>\n",
" <td>153</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <th>496</th>\n",
" <td>Female</td>\n",
" <td>184</td>\n",
" <td>121</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>497</th>\n",
" <td>Female</td>\n",
" <td>141</td>\n",
" <td>136</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <th>498</th>\n",
" <td>Male</td>\n",
" <td>150</td>\n",
" <td>95</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <th>499</th>\n",
" <td>Male</td>\n",
" <td>173</td>\n",
" <td>131</td>\n",
" <td>5</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"<p>500 rows × 4 columns</p>\n",
"</div>"
],
"text/plain": [
" Gender Height Weight Index\n",
"0 Male 174 96 4\n",
"1 Male 189 87 2\n",
"2 Female 185 110 4\n",
"3 Female 195 104 3\n",
"4 Male 149 61 3\n",
".. ... ... ... ...\n",
"495 Female 150 153 5\n",
"496 Female 184 121 4\n",
"497 Female 141 136 5\n",
"498 Male 150 95 5\n",
"499 Male 173 131 5\n",
"\n",
"[500 rows x 4 columns]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"data = pd.read_csv(\"bmi-data.csv\")\n",
"\n",
"data"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "b6824114-10c3-46ef-b9e5-0ad808e08b90",
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>Gender</th>\n",
" <th>Height</th>\n",
" <th>Weight</th>\n",
" <th>Obese</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>Male</td>\n",
" <td>174</td>\n",
" <td>96</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>Male</td>\n",
" <td>189</td>\n",
" <td>87</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>Female</td>\n",
" <td>185</td>\n",
" <td>110</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>Female</td>\n",
" <td>195</td>\n",
" <td>104</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>4</th>\n",
" <td>Male</td>\n",
" <td>149</td>\n",
" <td>61</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>...</th>\n",
" <td>...</td>\n",
" <td>...</td>\n",
" <td>...</td>\n",
" <td>...</td>\n",
" </tr>\n",
" <tr>\n",
" <th>495</th>\n",
" <td>Female</td>\n",
" <td>150</td>\n",
" <td>153</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>496</th>\n",
" <td>Female</td>\n",
" <td>184</td>\n",
" <td>121</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>497</th>\n",
" <td>Female</td>\n",
" <td>141</td>\n",
" <td>136</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>498</th>\n",
" <td>Male</td>\n",
" <td>150</td>\n",
" <td>95</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>499</th>\n",
" <td>Male</td>\n",
" <td>173</td>\n",
" <td>131</td>\n",
" <td>1</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"<p>500 rows × 4 columns</p>\n",
"</div>"
],
"text/plain": [
" Gender Height Weight Obese\n",
"0 Male 174 96 1\n",
"1 Male 189 87 0\n",
"2 Female 185 110 1\n",
"3 Female 195 104 0\n",
"4 Male 149 61 0\n",
".. ... ... ... ...\n",
"495 Female 150 153 1\n",
"496 Female 184 121 1\n",
"497 Female 141 136 1\n",
"498 Male 150 95 1\n",
"499 Male 173 131 1\n",
"\n",
"[500 rows x 4 columns]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"data[\"Obese\"] = (data[\"Index\"] >= 4).astype(\"int\")\n",
"data = data.drop(\"Index\", axis=1)\n",
"\n",
"data"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "9b329465-7e6b-4067-91e3-0f30e82dc3d2",
"metadata": {},
"outputs": [],
"source": [
"# Want to predict if someone is Obese\n",
"# A decision tree tells us different rules, e.g. if weight >= 100kg, then Obese\n",
"# Not all splits are precise, e.g. not everyone who is >= 100kg is Obese\n",
"\n",
"# Decision trees create new branches (splits) that refine predictions\n",
"# Create a node at each split\n",
"# Keep going until we get a node that doesn't split, this is a leaf node\n",
"\n",
"# A decision tree uses a cost function, typically Gini index or entropy\n",
"# Both are based on measuring \"impurity\"\n",
"\n",
"# Impurity = when we make a split, how likely is the target value to be classified incorrectly?\n",
"# If we made the split at 100kg weight, what's the impurity? What about 80kg?"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "89b5373b-e34c-4d54-bf92-1a71e1078f45",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(18, 63)"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"df_100kg = data[(data[\"Weight\"] >= 100) & (data[\"Obese\"] == 0)]\n",
"df_80kg = data[(data[\"Weight\"] >= 80) & (data[\"Obese\"] == 0)]\n",
"\n",
"len(df_100kg), len(df_80kg)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "fb41f186-e638-4fc1-b6f5-9a3cf3b79a7b",
"metadata": {},
"outputs": [],
"source": [
"# Impurity at 100kg is 18 (number of incorrect classifications), and impurity at 80kg is 63\n",
"# 18 is less impure, therefore is a \"better\" split\n",
"# Cost functions in a decision tree seek to find splits that minimize impurity\n",
"\n",
"# Gini index is most widely used cost function in decision trees\n",
"# Calculates the probability a characteristic will be classified incorrectly when randomly selected\n",
"# 0 = pure cut, no impurity\n",
"# 0.5 = divides the data equally (when there is two classes)\n",
"\n",
"# Calculated as: G = 1 - sum^n_{i=1}(P_i)^2\n",
"# P_i is the probability of being that class"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "f0f1b220-9bf2-4d5d-b135-4012602aaed5",
"metadata": {},
"outputs": [],
"source": [
"def gini_index(series):\n",
" assert isinstance(series, pd.Series)\n",
" p = series.value_counts() / len(series)\n",
" gini = 1 - np.sum(p**2)\n",
" return gini"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "2f9a56a7-52d9-4a98-9071-b32a1a4260cb",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.4998"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gini_index(data[\"Gender\"])"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "9d8e86f0-dbbd-412b-8b4d-d74be1827ad8",
"metadata": {},
"outputs": [],
"source": [
"# Impurity of almost 0.5 for gender because we have almost equal amount of male and female\n",
"\n",
"# How do we calculate impurity with Entropy?\n",
"# Entropy measures randomness in data points\n",
"# Defined by: E = - sum^n_{i=1}p_i \\log_2 p_i\n",
"\n",
"# For both Gini index and entropy: higher values are more impure"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "b8216e84-14f4-4204-9360-a69f74a650f5",
"metadata": {},
"outputs": [],
"source": [
"def entropy(series):\n",
" assert isinstance(series, pd.Series)\n",
" p = series.value_counts() / len(series)\n",
" entropy = - np.sum(p * np.log2(p + 1e-10))\n",
" return entropy"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "ea97512a-6b36-4db0-984e-ac149eff68e5",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.9997114414642708"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"entropy(data[\"Gender\"])"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "9d8f1dc1-a2a8-458e-bcb5-119f089d842d",
"metadata": {},
"outputs": [],
"source": [
"# Entropy is between 0 and 1, and reaches maximum when there's an equal amount of each class.\n",
"# The entropy for the Gender split is high, therefore high impurity and a bad split.\n",
"\n",
"# OK. We know how to calculate impurity (to tell if a split is good or not)\n",
"# but how do we decide which splits to do?\n",
"\n",
"# Splits are compared by their impurity\n",
"# For this we use \"Information Gain\"\n",
"\n",
"# IG measures the improvement when performing splits\n",
"# We can do this with entropy\n",
"# Can also with with Gini Index, but if we do then it's not information gain (entropy is related to information)\n",
"\n",
"# IG_classification = E(d) - \\sum |s|/|d| * E(s)\n",
"# IG_regression = E(d) - \\sum |s|/|d| * Var(s)\n",
"\n",
"# d is across all values, s is across values n the split\n",
"\n",
"def get_information_gain(series, mask):\n",
" n_true_split = sum(mask)\n",
" n_false_split = len(mask) - n_true_split\n",
" if n_true_split == 0 or n_false_split == 0:\n",
" return 0\n",
" original_entropy = entropy(series)\n",
" true_split_entropy = entropy(series[mask])\n",
" false_split_entropy = entropy(series[~mask])\n",
" weighted_average_entropy = n_true_split / len(mask) * true_split_entropy + n_false_split / len(mask) * false_split_entropy\n",
" information_gain = original_entropy - weighted_average_entropy\n",
" return information_gain"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "06eafaf1-7150-440a-bcc3-9ca0307b46f7",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.0005506911187600494"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"get_information_gain(data[\"Obese\"], data[\"Gender\"] == \"Male\")"
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "8a5b5d9c-fd48-4324-a51c-d4adc8f8ed62",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[('Blue',),\n",
" ('Red',),\n",
" ('Green',),\n",
" ('Blue', 'Red'),\n",
" ('Blue', 'Green'),\n",
" ('Red', 'Green'),\n",
" ('Blue', 'Red', 'Green')]"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# A high information gain indicates the feature reduces uncertainty in predicting the target variable\n",
"# this makes it a suitable candidate for splitting\n",
"# If the IG = 0, the features providers no additional inforation\n",
"\n",
"# To make our decision tree\n",
"# 1. Calculate information gain for all variables\n",
"# 2. Choose split that generates the highest information gain\n",
"# 3. Repeat until some stopping criterea\n",
"\n",
"# How do we choose where to split with numerical variables? What about with >2 categorical variables?\n",
"\n",
"# For splitting numeric variables:\n",
"# Get all values the variable is taking\n",
"# For each value, calculate IG when filtering all values less than that value\n",
"# If we sort values acending, first split means dropping that entire column\n",
"\n",
"# For categorical variables:\n",
"# Calculate IG for all possible combinations of that variable\n",
"# (exclude the one that includes all options as that would be doing no split)\n",
"# Combinatorial explosion when there's lots of classes so usually set a limit\n",
"\n",
"def get_categorical_options(series):\n",
" assert isinstance(series, pd.Series)\n",
" series = set(series)\n",
" options = []\n",
" for i, _ in enumerate(series):\n",
" subset = itertools.combinations(series, i+1)\n",
" options.extend(subset)\n",
" return options\n",
"\n",
"get_categorical_options(pd.Series([\"Red\", \"Red\", \"Blue\", \"Blue\", \"Green\"]))"
]
},
{
"cell_type": "code",
"execution_count": 156,
"id": "5c9e4114-27a0-4166-a0fe-3f3e2a07ed2f",
"metadata": {},
"outputs": [],
"source": [
"def get_max_information_gain(x_series, y_series):\n",
" is_numeric = x_series.dtype != \"object\"\n",
" if is_numeric:\n",
" split_values = x_series.sort_values().unique()[1:].tolist()\n",
" else:\n",
" split_values = get_categorical_options(x_series)\n",
" results = []\n",
" if not split_values:\n",
" # Handle the case when all values are the same!\n",
" return {\"split_value\": None, \"information_gain\": 0, \"is_numeric\": is_numeric}\n",
" for split_value in split_values:\n",
" mask = x_series < split_value if is_numeric else x_series.isin(split_value)\n",
" split_information_gain = get_information_gain(y_series, mask)\n",
" results.append({\n",
" \"value\": split_value,\n",
" \"information_gain\": split_information_gain,\n",
" })\n",
" results = sorted(results, key=lambda x: x[\"information_gain\"], reverse=True)\n",
" best_split_value = results[0][\"value\"]\n",
" best_information_gain = results[0][\"information_gain\"]\n",
" return {\"split_value\": best_split_value, \"information_gain\": best_information_gain, \"is_numeric\": is_numeric}"
]
},
{
"cell_type": "code",
"execution_count": 157,
"id": "b60045fd-90e2-4978-968f-5352ed62ec73",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'split_value': 103,\n",
" 'information_gain': 0.3824541370911896,\n",
" 'is_numeric': True}"
]
},
"execution_count": 157,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"get_max_information_gain(data[\"Weight\"], data[\"Obese\"])"
]
},
{
"cell_type": "code",
"execution_count": 158,
"id": "8d36f64a-0ac8-4556-a9a1-93b0150dca28",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Text(0, 0.5, 'Information Gain')"
]
},
"execution_count": 158,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAjcAAAGwCAYAAABVdURTAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8g+/7EAAAACXBIWXMAAA9hAAAPYQGoP6dpAABY60lEQVR4nO3deVhUZeM+8Hs2GPZ9X0RxAQRBcQmX1NRMzbXFzNS05ZctmlpvWa/Z8jVts6xM3yyzzbTFytwNdyUXEBQXRARB9kUY9oGZ8/tjZIpCYmTgzAz357q4ijMzeHNU5vY8z3keiSAIAoiIiIgshFTsAERERETGxHJDREREFoXlhoiIiCwKyw0RERFZFJYbIiIisigsN0RERGRRWG6IiIjIosjFDtDetFotcnJy4ODgAIlEInYcIiIiagFBEFBeXg5fX19Ipc1fm+lw5SYnJwcBAQFixyAiIqJbkJWVBX9//2af0+HKjYODAwDdyXF0dBQ5DREREbWESqVCQECA/n28OR2u3DQMRTk6OrLcEBERmZmWTCnhhGIiIiKyKCw3REREZFFYboiIiMiisNwQERGRRWG5ISIiIovCckNEREQWheWGiIiILArLDREREVkUlhsiIiKyKCw3REREZFFELTeHDh3C+PHj4evrC4lEgl9++eVfX3PgwAH06dMH1tbW6Nq1KzZs2NDmOYmIiMh8iFpuKisrERkZidWrV7fo+enp6Rg3bhyGDx+OxMREPPvss3j00Uexe/fuNk5KRERE5kLUjTPHjBmDMWPGtPj5a9euRefOnfHee+8BAEJDQ3HkyBG8//77GD16dFvFJCIzIQgCauu1qKytR3WdBlKJ5MYHIJNKYGcth7Vc2qKN94jIfJnVruBxcXEYOXJko2OjR4/Gs88+e9PX1NbWora2Vv+5SqVqq3hE1E4EQUB6USWSrpUiMbMUiVmlSC+qRKVaA41WaPa1CpkEDkoFHJVyBLrZoZunPbp72aOblwO6eznA3tqsfiwSURPM6m9xXl4evLy8Gh3z8vKCSqVCdXU1bGxs/vGa5cuX47XXXmuviERkZJW19cgorkRKXjnO5aiQnF2G87kqlNfUN/s6K5lu1F0rCDc+dMfrNAJKKtUoqVQjo7gKhy4VNnpdoKstQrwdEOrjiJhgNwzo7MorPURmxqzKza1YvHgxFi5cqP9cpVIhICBAxERE1JR6jRYp+eVIzCpFUlYprhRWIqO4CkUVtU0+30ouRbivI6ICXBAV6IwQbwc4KhWwtZbBzkoOmbRxIdFqBVSq61Feo/u4XqVGelElUvMrkFpQjkv55chX1SKzpAqZJVXYcz4fq2JT0cXdDg/0D8A9ffzhZm/dHqeCiFrJrMqNt7c38vPzGx3Lz8+Ho6Njk1dtAMDa2hrW1vyBRGRqauo0SLh6HX9cKcbx9BKcuVaG6jpNk891tbNCsIcdevo6oaevI3r6OqGrpz2s5C2/J0Iq1Q1HOSgV+mO3dXFr9JySSjUu5qlwMbccZ7PLsOdcHq4UVeLNHRfxzu4UjAn3wWNDuiDC3+nWvmkiahdmVW5iYmKwY8eORsf27t2LmJgYkRIRUUtptQLO5ahwIKUAh1OLkJhVCrVG2+g5DtZy9ApwQlSAM0K8HRHkZodAN1s42Shu8lWNy9XOCgOD3TEw2B2Abkjst6QcfHciE0nXyrA1KQdbk3IwqKsbHr89GLd3c+eQFZEJErXcVFRU4PLly/rP09PTkZiYCFdXVwQGBmLx4sXIzs7GV199BQB44okn8PHHH+M///kP5syZg3379uH777/H9u3bxfoWiKgZlbX1OJBSiNgL+TiUWoiiCnWjx70crRHTxQ0DurihbycXBHvYQyo1nbJgZy3HA/0D8UD/QCRnl+Gzw1fw25lcHL1cjKOXi+HtqISzrQJKhQxKhRQ2ChmUChlsFDJYK2RwtJFjdE9v9A5wZgkiakcSQRCav7WgDR04cADDhw//x/FZs2Zhw4YNePjhh5GRkYEDBw40es2CBQtw/vx5+Pv7Y8mSJXj44Ydb/GuqVCo4OTmhrKwMjo6ORvguiOivCsprcCClELuT83D4chHU9X9enbGzkmFQV3fc3t0Dg7u6o5Obrdm96V+7XoX1RzKw6WQmqtRND6P9XYi3A6YPCMTE3n5wVLbPVSgiS2PI+7eo5UYMLDdExlWlrseR1CIcSyvGsbQiXMqvaPR4kJst7uzpjeE9PBHdycWgeTKmTFVTh0t55aiu06CmTouaOg2q6zSovfHfmjot0osqseNsLmpvFDwbhQwzYzrhyeFd222ojchSsNw0g+WGyHhOZ17Hk98mILesRn9MIgF6+jpiVKg37gr3Rncve7O7OmNMpVVqbEnIxsYTmbhcoCt+zrYKPHNHN8y4rZPFlD2itsZy0wyWG6LWEwQB353Iwqtbz0Gt0cLHSYkRoZ4YGOyOmC5ucLGzEjuiyREEAftTCrB8x0Wk3ig5ga62uL+vPyL8nRHh5wRXnjeim2K5aQbLDVHr1NRp8Mqvyfj+1DUAwOieXnj3vshGt1jTzdVrtPgh/hre23PpH2v4+DnbYFSYF56+oyvcuaYOUSMsN81guSG6dan55VjwfSKSs1WQSoDnR4fgiaFdOvSw062qrK3Hj/HXEH/1OpKzy3ClqFL/mJ2VDI/fHoxHh3SGHbeDIALActMslhsiw2m0AtYfScc7e1KgrtfCxVaBD6f1xpBuHmJHsxiqmjqcTC/BqthUnLlWBgBwt7fGsyO7YVr/wH+suEzU0bDcNIPlhsgwV4sr8fwPZ3AiowQAMKyHB966pxe8HJUiJ7NMgiBg+9lcvLM7BVeLqwAAYT6OeGNST0R3chU5HZF4WG6awXJD1DL1Gi02HMvAe3suobpOAzsrGZbcHYap/QI4DNUO1PVabDx+FSv3XoLqxiahU/r44cUxIfB0YLGkjoflphksN0T/7sy1UizechbnclQAgAGdXfHufZEIcLUVOVnHU1xRi3d2p2DzqSwIAqBUSDE23Af39Q3AgM6uJrWiM1FbYrlpBssNUWOCIKCoQo2s61XIKqnCifQSfHciE1oBcLJR4KWxIbgvOoBvoiJLzCrF0q3nkJRVqj8W6GqL+6L9cX+/AA4TksVjuWkGyw2RjlYrYP3RdHwYm6of9virSVG++O/dYbwl2YQIgoDErFJ8f+oafkvKQUWt7vdNJpVgRIgnHhwQiNu7ebCIkkViuWkGyw0RkF1ajee+T0LclWIAulWFfRyVCHC1RaCrLSZG+WFwN3eRU1JzqtT12Hk2D5tOZuJkxnX98QBXG7w+IRzDQzxFTEdkfCw3zWC5oY5MqxXwS2I2lv56DuW19bC1kuHlcaG4N9of1nKZ2PHoFl3KL8fG45nYknBNfxXu4YFBeHFMCJQK/r6SZWC5aQbLDXUkGUWV+P5UFtKLKpFeVImM4krU1Ok2cewT6IyV90chyN1O5JRkLNVqDd7efRFfHM0AAPTwcsCH03qjh7eDuMGIjIDlphksN9RRXC6owP3/i0NJpbrRcaVCiqeGdcXcYcGQy7hpoyXan1KA539IQlGFGlZyKRaM7I5Hh3SGgr/fZMZYbprBckMdQXZpNe5bcww5ZTUI83HEvdH+6OxuhyB3O/i72PBNrgMoLK/F8z8m4UBKIQCgm6c9/m9SOAZ0cRM5GdGtYblpBssNWbriilrc9784XCmsRLCHHX54YiB3m+6gBEHATwnZeHPHBf0VvHv6+OPlcaH8M0Fmx5D3b/7zjciClNfU4eEvTuJKYSV8nZT4+pEBfBPrwCQSCe6N9se+RUMxrX8gAOCnhGsY/9ERnMspEzkdUdthuSGyAIIgYPe5PNy7Jg5ns8vgZmeFrx8dAF9nG7GjkQlwtrXC8ikR2PLkQHR2t0N2aTXuWXMM28/kih2NqE1wWIrIjGm1Avacz8eHsak4n6vbKsFRKce3j96GCH8nkdORKSqrqsMzm07j0CXdXJx5d3TFsyO7c+E/Mnmcc9MMlhuyFKn55XjuhyQkXdMNL9hZyfDwoCA8OrgLXDgURc2o12jx1q6LWHc4HQAQ08UNL4wJQVSAs7jBiJrBctMMlhsyd1qtgC/jMrBi50XU1mthby3HwwOD8Mjgziw1ZJCf4q9h8c9noa7XrX00MtQLC0d1R5gvfzaS6WG5aQbLDZmz3LJqPP/DGRy5XAQAuL27B965txc3TaRbllVShQ9jU/FTwjVob7wbjAz1wj19/DA8xJMrHJPJYLlpBssNmav4q9fxyJcnUVpVB6VCipfHhuKh2zpBIuFcCWq9tMIKvL/3Erb9ZZKxg1KOseE+mH5bIHr5O4sXjggsN81iuSFzdCClAHO/SUB1nQbhfo5Y9UBvBHvYix2LLFBqfjl+TLiGrYk5yC2rAaDbdfzbRwfgNi4ASCJiuWkGyw2Zm61JOVi4ORH1WgFDu3tgzUN9YGslFzsWWTitVsDx9BJ8cuAyDqcWwdPBGtvnDYGHg7XY0aiD4iJ+RBbi67gMzN90GvVaAeMjfbFuZl8WG2oXUqkEMcFu+N+MaHTztEdBeS2e3XwaGm2H+vcwmSmWGyITpK7XYumvyVjy6zkIAjAzphNWTY2ClZx/Zal92VrJ8cn0PrBRyHD0cjE+2pcqdiSif8WflEQmJq+sBg98Gocv464CABaM7I7XJvTkImskmm5eDlg2ORwAsCo2FUdv3K1HZKpYbohMSFxaMe7+6DASMkvhoJTjs5l9MX9kN94RRaKb0scfD/QLgCAA8zedRkpeudiRiG6K5YbIRGxJuIaHPj+Oogo1Qn0cse2ZwRgZ5iV2LCK9Vyf0RKiPI4oq1Jj8yVHsSubeVGSaWG6ITMBvSTl47ockaLQCJkX5YsvcgejkZid2LKJGlAoZNj46AAOD3VCl1uCJbxKwcu8laDnJmEwMyw2RyHYl5+LZzYnQCsAD/QKw8v4o2FhxVVgyTS52VvhqTn/MGdQZAPBhbCoe/zoemcVVIicj+hPXuSESUeyFfDzxTTzqNAKm9PHDu/dGcuIwmY0f46/hpRt7U0kkwLDuHpg5MAhDu3nwzzEZHRfxawbLDZmK2Av5mPtNAtQaLcZH+uKDqVGQ8Q2BzMzZa2V4Z08KDl0q1B8LdLXF4G7uiApwRlSAM4I97Plnm1qN5aYZLDdkCr6Oy8DSreegFYC7enrjowd7QyHjKDGZr/SiSnzzx1X8cCoLqpr6Ro85WMvxnzEhmHFbJ5HSkSVguWkGyw2JSasVsGLXRXx66AoA4P6+/lg2OYLFhixGtVqDg5cKcDqzFIlZpTibXYYqtQYA8N59kbgn2l/khGSuDHn/5jruRO2kpk6DBZsTsTM5DwDw3J3d8dTwrlzDhiyKjZUMd4X74K5wHwBAvUaLFTsv4rMj6fjPT2fgameF4SGeIqckS8d/LhK1k4Xf64qNlUyKVQ9E4ek7uDgfWT65TIqXxoZicm8/aLQCnvw2AQmZ18WORRaO5YaoHfx+Ph87zuZBLpXgyzn9MTHKT+xIRO1GKpXg7Xt7YWh3D1TXaTBnw0lcLuAKx9R2WG6I2liVuh5Lt54DADwypDNigt1ETkTU/hQyKdY81AeRAc4orarD//s6Hup6rdixyEKx3BC1sVW/pyK7tBp+zjaYP6Kb2HGIRGNrJccXD/eDu70V0gorse7wFbEjkYViuSFqQxdyVfjsSDoA4PWJPWFrxTn81LG52lnhpbGhAICP9qXi2nWubEzGx3JD1Ea0WgEv/XwWGq2Au3p6Y0QoN8EkAoDJvf3Qv7Mrauq0eP2382LHIQvEckPURr49fhWnM0thZyXD0glhYschMhkSiQRvTAyHXCrBnvP52HcxX+xIZGFYboiMTF2vxfIdF7DkV90k4kV39oCPk43IqYhMSw9vB8wZrNt8c+nWc6ip04iciCwJyw2REV0trsR9a4/hfzdWIJ4Z0wmzBgaJG4rIRM0f0Q3ejkpklVRj9f7LYschC8JyQ2Qk28/kYtyHR5B0rQxONgr8b0Y0Xp8Yzg0DiW7CzlqOV8brhmw/3n8ZP5zKEjkRWQqWGyIjOJdThnmbTqOith79g1yxc/4QjO7pLXYsIpM3JtwbM2M6QRCA//x0Bt+z4JAR8L5Uolaq02jxnx/PQKMVMCrMC2um94GcG2EStYhEIsFrE3pCEICv/7iKF346AwC4v2+AyMnInPEnMFErfXroCs7lqOBko8CyyeEsNkQGkkgkeH1iT/0VnBd+OoNvj1+FIAhiRyMzxZ/CRK1wuaAcq35PBQAsHR8GTwelyImIzFPDFZyGgvPyz8mY/MkxHE4tZMkhg7HcEN0ijVbA8z+egVqjxbAeHpjcm5thErVGQ8FZOKo7lAopErNKMePzE5j66R84klqEOg33oqKWkQgdrBKrVCo4OTmhrKwMjo6OYschM/b5kXS8se087K3l2LPgdvg6cy0bImMpKK/BmgNp+PaPTKhvlBo7KxkGdHHDwGA3DOvhia6e9iKnpPZkyPs3yw3RLSiqqMXgt/ahpk6LZZPDMX1AJ7EjEVmk3DLdGjjbzuSitKpOf1wqAd6fGoWJUbxi2lEY8v7Nu6WIbsEPp66hpk6LcD9HTOsXKHYcIovl42SD/5sUgdcnhON8rgrH0orw+4UCnEgvwUtbziLCzwldPHgFhxrjnBsiA2m1Ar47kQkAmHlbEKRcpI+ozUmlEoT7OeHx24Px3WO3YUBnV1SqNXh642lu3UD/wHJDZKAjl4uQWVIFB6Ucd0f6iB2HqMORSSVY9UBvuNpZ4XyuCm/uuCB2JDIxLDdEBvr2+FUAwJTefrC14sgukRi8nZRYeX8kAOCruKvYeTZX5ERkSlhuiAyQr6rB7xcKAAAPchIxkaiG9fDEE0ODAei2bsgqqRI5EZkKlhsiA2w+mQWNVkC/IBf08HYQOw5Rh7fozu7oE+iM8pp6zN90GvVcC4fAckPUYhqtgE03JhI/OIB3SBGZAoVMig+n9YaDtRwJmaVYvT9N7EhkAlhuiFroQEoBcspq4GyrwJhwTiQmMhX+LrZ4Y1I4AODDfalIyLwuciISG8sNUQt9e1x31ea+aH8oFTKR0xDRX03q7YcJkb7QaAUs2JyIitp6sSORiEQvN6tXr0ZQUBCUSiUGDBiAEydONPv8Dz74AD169ICNjQ0CAgKwYMEC1NTUtFNa6qgyi6uwP0U3kXhafw5JEZmiNyaFw8/ZBleLq/D6b+fEjkMiErXcbN68GQsXLsTSpUuRkJCAyMhIjB49GgUFBU0+f+PGjXjxxRexdOlSXLhwAZ9//jk2b96Ml156qZ2TU0fzzp4UCAIwpJs7V0MlMlFONgq8d38kJBLg+1PXsP0Mbw/vqEQtNytXrsRjjz2G2bNnIywsDGvXroWtrS3Wr1/f5POPHTuGQYMG4cEHH0RQUBDuvPNOTJs27V+v9hC1RvzV6/gtKQcSCfDimBCx4xBRM27r4oa5N24Pf+6HJCRnl4mciMQgWrlRq9WIj4/HyJEj/wwjlWLkyJGIi4tr8jUDBw5EfHy8vsxcuXIFO3bswNixY2/669TW1kKlUjX6IGopQRDwxrbzAHRzbXr6OomciIj+zcJR3TGkmzuq6zR45MuTyCvj1IWORrRyU1RUBI1GAy8vr0bHvby8kJeX1+RrHnzwQbz++usYPHgwFAoFgoODMWzYsGaHpZYvXw4nJyf9R0BAgFG/D7JsW5NykJhVClsrGZ67s4fYcYioBeQyKVZP74NunvbIV9XikS9PokrNCcYdiegTig1x4MABvPnmm/jkk0+QkJCALVu2YPv27XjjjTdu+prFixejrKxM/5GVldWOicmc1dRp8PauFADA3KHB8HRUipyIiFrKUanA+of7wc3OCudyVHh2UyK0WkHsWNRORCs37u7ukMlkyM/Pb3Q8Pz8f3t7eTb5myZIlmDFjBh599FFERERg8uTJePPNN7F8+XJotU2vSmltbQ1HR8dGH0Qt8fmRdGSXVsPHSYlHh3QROw4RGSjA1RafzoyGlVyKPefz8d7eFLEjUTsRrdxYWVkhOjoasbGx+mNarRaxsbGIiYlp8jVVVVWQShtHlsl0640IAhs5GU9uWTU+2X8ZAPDCXSGwseK6NkTmKLqTK965txcAYM2BNCRllYobiNqFqMNSCxcuxLp16/Dll1/iwoULmDt3LiorKzF79mwAwMyZM7F48WL988ePH481a9Zg06ZNSE9Px969e7FkyRKMHz9eX3KIWiuzuApT//cHKtUaRPo7YUKkr9iRiKgVJkb5YWKUL7QC8MJPZ6Cu5/5Tlk4u5i8+depUFBYW4pVXXkFeXh6ioqKwa9cu/STjzMzMRldq/vvf/0IikeC///0vsrOz4eHhgfHjx2PZsmVifQtkYS7mqTDj8xMoLK9FoKstPprWB1KpROxYRNRKr9wdhsOpRbiYV461B9Mwb0Q3sSNRG5IIHWw8R6VSwcnJCWVlZZx/Q43EXy3B7C9OQlVTjxBvB3w1pz8nERNZkK1JOZj33WkoZBLsmDcE3bwcxI5EBjDk/dus7pYiaguCIODH+GuY/tlxqGrqEd3JBZsfj2GxIbIw43v5YGSoJ+o0Ap7/8Qw0vHvKYrHcUIeWXlSJ6Z8dx3M/JKGmTouh3T3w9SP94WSrEDsaERmZRCLBG5PC4WAtR2JWKb44mi52JGojLDfUIdVptFi9/zJGf3AIx9KKYS2X4oW7QvDZrL6wtRJ1KhoRtSEfJxssHhsKAFgVm8rdwy0Uyw11OIIgYN53p/HO7hSo67UY0s0dexbcjrnDgqGQ8a8EkaV7oF8AurjbobymHj/FXxM7DrUB/iSnDmfd4SvYmZwHK5kU70+NxFdz+qOTm53YsYionUilEsweFAQA+OJoOlcutkAsN9ShHL9SjLdubKmwZHwYJvf2h0TCW72JOpp7ov3hqJQjo7gK+y4WiB2HjIzlhjqMgvIaPP3daWi0AiZF+eKhAYFiRyIikdhayTHtxs+A9ZxYbHFYbqhDqNdo8czG0ygsr0V3L3u8OSWCV2yIOriZMUGQSSU4llaMC7kqseOQEbHckMUTBAFv7riI4+klsLeWY81D0bwjiojg52yDu8J1GzWvP8KrN5aE5YYsmiAIeHt3iv6y81v39EKwh73IqYjIVMwZ1BkA8GtiDooqakVOQ8bCckMWSxAEvLM7BWsOpAEAXpvQE+N6+YiciohMSXQnF0QFOEOt0eLbPzLFjkNGwnJDFkkQBLy35xI+uVFsXh0fhlkDg8QNRUQmac5g3dWbr/+4ijoNdwy3BCw3ZJFWxabi4/2XAQBLx4fh4RuXnomI/m5MuDfc7a1RVFGLQ5cKxY5DRsByQxZn/8UCfPB7KgDglbvDMJvFhoiaoZBJMT5SN2T9S2KOyGnIGFhuyKIUqGrw3A9JAICHBwbpLzcTETVncm8/AMCec3kor6kTOQ21FssNWQytVsCiH5JQXKlGqI8jXhwTInYkIjITEX5O6OJhh9p6LXafyxc7DrUSyw1ZjM+OXMHh1CIoFVJ8NC0KSoVM7EhEZCYkEgkmRemu3vyamC1yGmotlhuyCGevleGd3bo9o165uye6ejqInIiIzE1DuTl6uQj5qhqR01BrsNyQ2Tufo8KTG+NRpxEwJtwb0/oHiB2JiMxQoJstoju5QCsAvyVxYrE5Y7khs6XVCvjs8BVMWn0UWSXV8HexwYopvbhnFBHdsklRvgCAXzg0ZdZYbsgs5ZXVYOb6E/i/7Reg1mgxMtQLvz41CE62CrGjEZEZG9fLF3KpBMnZKqTml4sdh24Ryw2ZnT3n8nDXqkM4clk3eXjZ5HCsmxkNN3trsaMRkZlztbPCsB4eAHj1xpyx3JDZqKnTYMkvyXj863iUVtUh3M8R254ZgukDOnEoioiMZqL+rqkcaLWCyGnoVsjFDkDUEil55Zj33Wmk3LhM/NiQznh+dAis5OznRGRcI0O9YG8tx7Xr1UjIvI6+Qa5iRyID8Z2BTF5C5nVM+PgIUvLL4W5vjS/n9MfL48JYbIioTdhYyTAqzAsAsP1srshp6Fbw3YFMWrVag0XfJ6G2XouBwW7YOX8Ihnb3EDsWEVm4sRG6vaZ2ns3j0JQZYrkhk/b27otIL6qEt6MSax6KhocDJw0TUdsb0s0d9tZy5KlqcDrruthxyEAsN2Sy/rhSjC+OZgAAVtwTAScb3uZNRO1DqfhzaGrbGQ5NmRuWGzJJlbX1+M+PZwAAD/QLwLAeniInIqKOhkNT5ovlhkzSW7suIrOkCr5OSrw8LlTsOETUAXFoynyx3JDJOZFegq/irgIA3r43Eg5KDkcRUfvj0JT5MnidG41Ggw0bNiA2NhYFBQXQarWNHt+3b5/RwlHH9O1xXbG5L9ofg7u5i5yGiDqysRE++Pl0NnaezcOScWGQSrlgqDkwuNzMnz8fGzZswLhx4xAeHs6VYcmo1PVa7LtQAAB4gLt7E5HI/j40Fd2JC/qZA4PLzaZNm/D9999j7NixbZGHOrhjaUUor62Hh4M1ege4iB2HiDq4hqGpn09nY9uZXJYbM2HwnBsrKyt07dq1LbIQYfe5PADAnWFevPxLRCaBd02ZH4PLzaJFi7Bq1SoIAn+Dybg0WgF7z+cDAO4K9xY5DRGRzl+Hpo6mFYkdh1rA4GGpI0eOYP/+/di5cyd69uwJhaLxnSxbtmwxWjjqWOKvXkdRhRqOSjlu6+ImdhwiIgC6oakpffzwVdxVLN16DjvnD4G1XCZ2LGqGweXG2dkZkydPboss1MHtStYNSY0M9YJCxlUKiMh0LBrVAzvO5uFKYSU+2Z+GBaO6ix2JmmFwufniiy/aIgd1cIIg6OfbjOaQFBGZGCdbBV6dEIanN57GmgNpGB/pg66eDmLHopvgP4/JJJzLUSG7tBpKhRS3d+Ou30RkesZF+OCOEE+oNVq8tCWZk4tNWIuu3PTp0wexsbFwcXFB7969m13bJiEhwWjhqONouGozrLsnbKw4lk1EpkcikeD1iT3xx5VinMgoweZTWZjWP1DsWNSEFpWbiRMnwtraGgAwadKktsxDHVTDfBveJUVEpszfxRaL7uyBN7adx5s7LmBEqCc8HZRix6K/kQgd7J5ulUoFJycnlJWVwdHRUew4BCCtsAIj3jsIuVSC+CWj4GTDvaSIyHRptAImrT6Ks9llePz2LnhpLDf3bQ+GvH9zzg2JbmtiDgBgYFd3FhsiMnkyqQTzRnQDAPwYfw219RqRE9HfGVxuNBoN3n33XfTv3x/e3t5wdXVt9EFkiJMZJVi9/zIAYFKUr8hpiIhaZngPD3g7KlFSqdYPq5PpMLjcvPbaa1i5ciWmTp2KsrIyLFy4EFOmTIFUKsWrr77aBhHJUuWUVmPuN/Go1woY18sHk3v7iR2JiKhF5DIppvbTbe678XimyGno7wwuN99++y3WrVuHRYsWQS6XY9q0afjss8/wyiuv4I8//miLjGSBauo0+H9fx6OoQo1QH0e8c28v7jBPRGblgf4BkEqA4+kluFxQIXYc+guDy01eXh4iIiIAAPb29igrKwMA3H333di+fbtx05FFEgQBi7ecxdnsMrjYKvDpjGjYWhm8niQRkah8nGxwR4gXAOC7E7x6Y0oMLjf+/v7Izc0FAAQHB2PPnj0AgJMnT+pvFydqzhdHM/Dz6WzIpBKsnt4HAa62YkciIrol0wfo1rn5Mf4aauo4sdhUGFxuJk+ejNjYWADAM888gyVLlqBbt26YOXMm5syZY/SAZFlySqvx9u6LAICXx4ZiYLC7yImIiG7d7d094Odsg7LqOuw4myt2HLrB4LGAFStW6P9/6tSpCAwMRFxcHLp164bx48cbNRxZnmU7LqCmTot+QS6YPShI7DhERK0ik0rwQL8AvLf3EjYez8SUPv5iRyLcQrn5u5iYGMTExBgjC1m4uLRibD+TC6kEeHVCT04gJiKLcH+/AHwQm4pTV6/jUn45untxQ02xtbjcaLVanDt3Tj+ZeO3atVCr1frHZTIZ5s6dC6mU6wLSP9VrtHjtt3MAgAcHBKKnr5PIiYiIjMPLUYmRoZ7YfS4f7+5Owf9mRPMfbyJrcbnZtGkT1q5di0OHDgEAnn/+eTg7O0Mu132JoqIiKJVKPPLII22TlMzat8czcTGvHM62Ciwa1UPsOERERvX08G7Yd7EAe87n4/Mj6Xh0SBexI3VoLb7M8sUXX+Cpp55qdOzgwYNIT09Heno63nnnHXzzzTdGD0jmr7iiFu/tSQEALLqzB1zsrERORERkXBH+Tnjl7jAAwPKdF3EivUTkRB1bi8vNxYsX0bdv35s+PnToUCQlJRklFFmWd/dcgqqmHmE+jniwf6DYcYiI2sRDt3XCpChfaLQCntqYgILyGrEjdVgtLjeFhYWNPr9y5QqCgoL0nysUClRWVhotGFmGnNJqfH8qC4BuErFMynFoIrJMEokEb06JQHcvexSW1+LpjadRp9GKHatDanG58fLyQkpKiv5zDw+PRpOHL1y4AG9vb+OmI7O34VgGNFoBMV3c0L8zN1YlIstmayXHmoeiYW8tx4n0Eny077LYkTqkFpebESNGYNmyZU0+JggCli9fjhEjRhgtGJk/VU2dfkO5x2/n5Doi6hiCPeyxbHI4AODruAyo63n1pr21uNy8/PLLSE5OxoABA/DDDz8gKSkJSUlJ+P777zFgwACcO3cOL730UltmJTOz+UQWKmrr0dXTHkO7e4gdh4io3dzdyxeeDta4XlWHfRcLxI7T4bS43AQHB2Pv3r0oLy/H1KlT0adPH/Tp0wcPPPAAKioqsGfPHnTt2rUts5IZqdNosf5oOgDgsSGdIeVcGyLqQGRSCSb39gMA/JRwTeQ0HY9BKxT3798f58+fR2JiIi5dugQA6NatG3r37t0m4ch87Tibi9yyGrjbW2NilJ/YcYiI2t090f7436Er2H+xAMUVtXCz5+bS7eWWtl+IiopCVFSUkaOQpRAEAZ8eugIAmBXTCUqFTORERETtr7uXAyL8nHA2uwxbk3Iwe1BnsSN1GNwrgYwuLq0Y53JUUCqkeOi2TmLHISISzT19ODQlBtHLzerVqxEUFASlUokBAwbgxIkTzT6/tLQUTz31FHx8fGBtbY3u3btjx44d7ZSWWuLTw7qrNvf3DeBqxETUoU2I8oNCJkFytgoX81Rix+kwRC03mzdvxsKFC7F06VIkJCQgMjISo0ePRkFB0zPL1Wo1Ro0ahYyMDPz4449ISUnBunXr4OfHOR2mYufZXBxIKYREAszhJVgi6uBc7awwvIcnAOCneF69aS+ilpuVK1fisccew+zZsxEWFoa1a9fC1tYW69evb/L569evR0lJCX755RcMGjQIQUFBGDp0KCIjI2/6a9TW1kKlUjX6oLaRXVqNF346A0C3rk2Qu53IiYiIxHdPtD8A4OfTOajnisXt4pYmFJeWluLEiRMoKCiAVtv4N2rmzJkt+hpqtRrx8fFYvHix/phUKsXIkSMRFxfX5Gu2bt2KmJgYPPXUU/j111/h4eGBBx98EC+88AJksqYnrS5fvhyvvfZaC78zulX1Gi2e3XQaqpp6RAY447k7ufM3EREADO/hCRdbBYoqanE4tQjDQzzFjmTxDC43v/32G6ZPn46Kigo4OjpCIvlz/RKJRNLiclNUVASNRgMvL69Gx728vHDx4sUmX3PlyhXs27cP06dPx44dO3D58mU8+eSTqKurw9KlS5t8zeLFi7Fw4UL95yqVCgEBAS3KSC330b7LOJlxHfbWcnz4QBQUMtGncxERmQQruRQTo/yw4VgGfky4xnLTDgx+B1q0aBHmzJmDiooKlJaW4vr16/qPkpK23eJdq9XC09MTn376KaKjozF16lS8/PLLWLt27U1fY21tDUdHx0YfZFy6/VNSAQDLJoejkxuHo4iI/ureG0NTv5/PR3lNnchpLJ/B5SY7Oxvz5s2Dra1tq35hd3d3yGQy5OfnNzqen59/0w04fXx80L1790ZDUKGhocjLy4NarW5VHro1lbX1eHbTaWgF4J4+/lywj4ioCT19HRHsYYfaei12n8v/9xdQqxhcbkaPHo1Tp061+he2srJCdHQ0YmNj9ce0Wi1iY2MRExPT5GsGDRqEy5cvN5rnc+nSJfj4+MDKircci2HL6WzklNXA38UGr03sKXYcIiKTJJFI9P/4+zUxW+Q0ls/gOTfjxo3D888/j/PnzyMiIgIKhaLR4xMmTGjx11q4cCFmzZqFvn37on///vjggw9QWVmJ2bNnA9BNTvbz88Py5csBAHPnzsXHH3+M+fPn45lnnkFqairefPNNzJs3z9Bvg4xAEAR8dSwDgO62b3vrW5qfTkTUIUyI9MXKvZdw9HIRCstr4eHA7RjaisHvRo899hgA4PXXX//HYxKJBBqNpsVfa+rUqSgsLMQrr7yCvLw8REVFYdeuXfpJxpmZmZBK/7y4FBAQgN27d2PBggXo1asX/Pz8MH/+fLzwwguGfhtkBH9cKUFqQQVsrWT6Wx2JiKhpQe52iAxwRlJWKbafycHDXAuszUgEQRDEDtGeVCoVnJycUFZWxsnFrTT3m3jsTM7D9AGBWDY5Quw4REQmb/2RdLy+7Tx6Bzrj5ycHiR3HrBjy/s37demW5JZVY8953aS4mTFB4oYhIjITd/fygVQCnM4sRWZxldhxLNYtlZuDBw9i/Pjx6Nq1K7p27YoJEybg8OHDxs5GJmzj8UxotAIGdHZFD28HseMQEZkFT0clBga7AwC2JnFicVsxuNx88803GDlyJGxtbTFv3jzMmzcPNjY2GDFiBDZu3NgWGcnE1NZr8N2JTAC8akNEZKgJUb4AgF8Sc9DBZoa0G4Pn3ISGhuLxxx/HggULGh1fuXIl1q1bhwsXLhg1oLFxzk3r/ZqYjfmbEuHlaI0jL9zB1YiJiAygqqlD3//7Hep6LXbMG4IwX74XtUSbzrm5cuUKxo8f/4/jEyZMQHp6uqFfjszQV3FXAQAP9u/EYkNEZCBHpQJ33Ngp/FcOTbUJg9+ZAgICGi281+D333/nnk0dQPzVEsRfvQ6FTIJpA/j7TUR0Kyb11g1N/ZaYA62WQ1PGZvA6N4sWLcK8efOQmJiIgQMHAgCOHj2KDRs2YNWqVUYPSKajpk6D//x4BgAwKcoPng5KkRMREZmnYT08YW8tR05ZDU5nlSK6k4vYkSyKweVm7ty58Pb2xnvvvYfvv/8egG4ezubNmzFx4kSjByTTsXLvJaQVVsLDwRovjwsVOw4RkdlSKmQYGeqJXxJzsP1MLsuNkd3SevmTJ0/G5MmTjZ2FTNipjBKsO3wFALBiSgScbbmXFxFRa4yN8MEviTnYmZyL/44LhVQqETuSxeBsUPpXVep6PPdDEgQBuDfaHyNCvcSORERk9m7v7gF7azlybwxNkfG0qNy4urqiqKgIAODi4gJXV9ebfpDleXtXCjKKq+DjpMQr48PEjkNEZBGUChlGhOrumtpxNlfkNJalRcNS77//PhwcHPT/L5Hw0llHUFZdh88PX8GGGzt/v3VPLzgqFc2/iIiIWmxshA9+TczBzrO5eHksh6aMpUXlZtasWfr/f/jhh9sqC5kIVU0d1h9Jx+dH0lFeUw8AmBnTCbd39xA5GRGRZRna3QN2VjLklNUg8Vop+gRyYrExGDznRiaToaCg4B/Hi4uLIZPJjBKKxHMqowSDV+zDB7+norymHt297PHJ9D54dXxPsaMREVkc3dCUbh7jjjMcmjIWg8vNzXZrqK2thZUV76Axd6tiU6GqqUdXT3t8/GBv7Jp/O8ZG+PBSKRFRGxnXywcAsDM5j3tNGUmLbwX/8MMPAQASiQSfffYZ7O3t9Y9pNBocOnQIISEhxk9I7aa0So24tGIAwLqZfdHZ3U7kRERElq9haCq7tBqJWaXozaGpVmtxuXn//fcB6K7crF27ttEQlJWVFYKCgrB27VrjJ6R2E3uhAPVaASHeDiw2RETtpGFoamuSbkE/lpvWa3G5adgUc/jw4diyZQtcXHjyLc2uc3kAgNE9vUVOQkTUsYyN8MHWpBzsTM7D4rGhkHEqQKsYPOdm//79LDYWqLK2HocuFQIA7gpnuSEiak/DenjAwVqO7NJqvLTlLDfTbKVb2n7h2rVr2Lp1KzIzM6FWqxs9tnLlSqMEo/Z18FIhauu16ORmixBvB7HjEBF1KEqFDG/d2wtPb0zA5lNZUCqkeHVCT64rd4sMLjexsbGYMGECunTpgosXLyI8PBwZGRkQBAF9+vRpi4zUDnYl64ak7urpzb9MREQiGBvhg3fvi8SiH5LwZdxVKBUyvDgmhD+Tb4HBw1KLFy/Gc889h7Nnz0KpVOKnn35CVlYWhg4divvuu68tMlIbq63XYN9F3dpFHJIiIhLPlD7+WDYpAgDwv0NX8MHvqSInMk8Gl5sLFy5g5syZAAC5XI7q6mrY29vj9ddfx1tvvWX0gNT2jl0uRkVtPbwdlYj0dxY7DhFRh/bggEAsuVu3j9+q2FTEXy0ROZH5Mbjc2NnZ6efZ+Pj4IC0tTf9Yw+aaZF4ahqRG9/TiYn1ERCbgkcGdMSHSFwCw42yeyGnMj8Hl5rbbbsORI0cAAGPHjsWiRYuwbNkyzJkzB7fddpvRA1LbqtdosfdCPgBgNIekiIhMxtgI3c/kvefzuXKxgQyeULxy5UpUVFQAAF577TVUVFRg8+bN6NatG++UMkMnM66jpFINF1sF+ge5ih2HiIhuGNLNA1ZyKTJLqnApvwI9eCdrixlcbrp06aL/fzs7O65KbOZ231i4b1SYF+Qygy/kERFRG7GzlmNwV3fsu1iAvefzWG4M0Kp3s4qKCqhUqkYfZF4aFu4beWNXWiIiMh2jwnQ/m/eezxc5iXkxuNykp6dj3LhxsLOzg5OTE1xcXODi4gJnZ2euXGxmcsuqcaWoElIJcFuwm9hxiIjob0aEekIiAZKulSFfVSN2HLNh8LDUQw89BEEQsH79enh5eXFxITPWsAN4hL8zHJUKkdMQEdHfeTooERXgjNOZpdh7Ph8P3dZJ7EhmweByk5SUhPj4ePTo0aMt8lA7Onaj3AzkVRsiIpM1KsyL5cZABg9L9evXD1lZWW2RhdqRIAj6KzcsN0REpmvUjTmRcWm6BVfp3xl85eazzz7DE088gezsbISHh0OhaDyc0atXL6OFo7aTWVKF7NJqKGQS9O3EW8CJiExVV097BLnZIqO4CocuFWJshI/YkUyeweWmsLAQaWlpmD17tv6YRCKBIAiQSCTQaDRGDUhto2FIqnegC2ysZCKnISKim5FIJBgV5oV1h9Ox93w+y00LGFxu5syZg969e+O7777jhGIzxvk2RETmY1SYN9YdTse+iwWo02ih4LpkzTK43Fy9ehVbt25F165d2yIPtQPdfBvdPmADg91FTkNERP8mupMLXO2sUFKpxqFLhRjBtcmaZXD1u+OOO5CUlNQWWaidpBZUoKhCDaVCiqgAZ7HjEBHRv5BJJbi7l2446rkfkpBWWCFyItNm8JWb8ePHY8GCBTh79iwiIiL+MaF4woQJRgtHbePYZd1Vm35BrrCS89ImEZE5eHFMCJKySpF0rQyz1p/AlicHwtNBKXYskyQRDNxqVCq9+ZuhOUwoVqlUcHJyQllZGRwdHcWOI4rHvzqFPefz8Z+7euDJYRxeJCIyF0UVtbhnzTFcLa5CuJ8jNj0eA3trg69TmCVD3r8N/me7Vqu96YepFxsCNFoBf1xpmEzM+TZERObE3d4aX87uDzc7KyRnqzD3m3jUabRixzI5BpWburo6yOVyJCcnt1UeamPnc1RQ1dTDwVqOcN+OeeWKiMicBbnbYf3D/WCjkOFwahHe33tJ7Egmx6Byo1AoEBgYyCs0ZuzYjbukBnRxhZy3EhIRmaXIAGe8d38kAOCzw+m4WlwpciLTYvC728svv4yXXnoJJSUlbZGH2tjRG+vbxHBIiojIrI0J98aQbu5Qa7RYtv2C2HFMisGzkD7++GNcvnwZvr6+6NSpE+zs7Bo9npCQYLRwZFyqmjr8caPcDO7KckNEZM4kEgleuTsMd606jD3n83EktQiDu/FnO3AL5WbSpEltEIPaw95z+VBrtAj2sEN3L3ux4xARUSt183LAjNs6YcOxDLy+7Rx2zBvCKQe4hXKzdOnStshB7WDbmRwAwN29fLltBhGRhVgwsjt+TczGpfwKfHciEzNigsSOJLpbrnfx8fH45ptv8M033+D06dPGzERtoLRKjcOpusnE4yO56RoRkaVwslVg4Z09AADv7b2E0iq1yInEZ3C5KSgowB133IF+/fph3rx5mDdvHqKjozFixAgUFha2RUYygj3n8lGvFRDi7YCung5ixyEiIiOa1i8AId4OKK2qw0f7LosdR3QGl5tnnnkG5eXlOHfuHEpKSlBSUoLk5GSoVCrMmzevLTKSEfymH5LiVRsiIksjl0nx4pgQAMDmk1moqK0XOZG4DC43u3btwieffILQ0FD9sbCwMKxevRo7d+40ajgyjuKKWhy7cZfU3b18RU5DRERt4fZuHujiboeK2nr8fDpb7DiiuqXtF/6+WSagW+BPq+US0KZo17k8aLQCwv0cEeRu9+8vICIisyOVSvDQbZ0AAF/HZcDArSMtisHl5o477sD8+fORk5OjP5adnY0FCxZgxIgRRg1HxrEtKRcAr9oQEVm6e6L9YaOQ4VJ+BU6kd9zFdg0uNx9//DFUKhWCgoIQHByM4OBgdO7cGSqVCh999FFbZKRWKCivwfF03ZDUuAjOtyEismRONgpM6u0HAPjqj6sipxGPwevcBAQEICEhAb///jsuXrwIAAgNDcXIkSONHo5ab+fZPGgFICrAGQGutmLHISKiNjYzphO+O5GJ3cl5KFDVwNNRKXakdteiKzeurq4oKtKtkTJnzhxUVFRg1KhReOaZZ/DMM8+w2JiwbbxLioioQwn1cUS/IBfUawVsPJEpdhxRtKjcqNVqqFQqAMCXX36JmpqaNg1FxpGQeR0nM65DKgHGsdwQEXUYDasUbzyeiTpNx7vZp0XDUjExMZg0aRKio6MhCALmzZsHGxubJp+7fv16owakWyMIAlbs0A0b3hvtDx+npn+/iIjI8tzV0xvu9tYoKK/FnnP5He4fuC26cvPNN99g7NixqKiogEQiQVlZGa5fv97kB5mG2AsFOJFRAmu5FAtGdRc7DhERtSMruRQP9g8AAHzXAYemWnTlxsvLCytWrAAAdO7cGV9//TXc3NzaNBjdunqNFm/t0l21mTO4M6/aEBF1QHdH+uLDfZeRkHkdWq0AqbTjbJhs8K3g6enpLDYm7qeEa0gtqICzrQJPDA0WOw4REYkg2MMeSoUUVWoN0osrxY7Trgy+FRwAYmNjERsbi4KCgn+sSsw5N+KqVmuwcu8lAMDTw7vCyeafq0kTEZHlk0klCPNxREJmKZKzyxDsYS92pHZj8JWb1157DXfeeSdiY2NRVFTEOTcmZv3RdOSrauHnbIMZMZ3EjkNERCIK93MCACRnl4mcpH0ZfOVm7dq12LBhA2bMmNEWeagVVDV1WHsgDQDw3OjusJbLRE5ERERiCvdtKDcqkZO0L4Ov3KjVagwcONCoIVavXo2goCAolUoMGDAAJ06caNHrNm3aBIlEgkmTJhk1j7nampiD8tp6dPW0x8RIP7HjEBGRyHr6OQIAknPKOtRGmgaXm0cffRQbN240WoDNmzdj4cKFWLp0KRISEhAZGYnRo0ejoKCg2ddlZGTgueeew5AhQ4yWxdxtPpkFAJjWP7BDzYonIqKmdfN0gJVMivKaemSVVIsdp90YPCxVU1ODTz/9FL///jt69eoFhaLxhNWVK1ca9PVWrlyJxx57DLNnzwagG/bavn071q9fjxdffLHJ12g0GkyfPh2vvfYaDh8+jNLS0pt+/draWtTW1uo/b1hp2dIkZ5fhbHYZrGRSTO7NqzZERKRb76aHtwPOZpchOacMgW4dY49Bg6/cnDlzBlFRUZBKpUhOTsbp06f1H4mJiQZ9LbVajfj4+EZ7U0mlUowcORJxcXE3fd3rr78OT09PPPLII//6ayxfvhxOTk76j4CAAIMymouGqzZ39vSCq52VyGmIiMhUhDcMTXWgScUGX7nZv3+/0X7xoqIiaDQaeHl5NTru5eWl33H8744cOYLPP/+8xUVq8eLFWLhwof5zlUplcQWnWq3BL4nZAIAH+gWKnIaIiEyJ7o6pLCTnWObIRVNuaZ0bsZSXl2PGjBlYt24d3N3dW/Qaa2trWFtbt3Eyce04m4vymnoEuNpgYDAXWCQioj813DF1Lls3qVgisfw5mS0uN1OmTGnR87Zs2dLiX9zd3R0ymQz5+fmNjufn58Pb2/sfz09LS0NGRgbGjx+vP9awiKBcLkdKSgqCgzveirwNQ1JT+wZwIjERETXSw9sBMqkExZVq5KlqOsSWPC0uN05OTkb/xa2srBAdHY3Y2Fj97dxarRaxsbF4+umn//H8kJAQnD17ttGx//73vygvL8eqVassbripJdIKK3AiowRSCXBvdMf7/omIqHlKhQzdPO1xMa8cydkqlpu/+uKLL9okwMKFCzFr1iz07dsX/fv3xwcffIDKykr93VMzZ86En58fli9fDqVSifDw8Eavd3Z2BoB/HO8ovr9x1WZ4D094OylFTkNERKYo3M8JF/PKcTa7DKPCvP79BWZO9Dk3U6dORWFhIV555RXk5eUhKioKu3bt0k8yzszMhFRq8E1dHYK6Xosf468BAKb241UbIiJqWrivI36M18276QhELzcA8PTTTzc5DAUABw4caPa1GzZsMH4gM3E4tRDFlWp4OFjjjhBPseMQEZGJ0u8xldMxyg0viZix2Iu6VZzv6ukNuYy/lURE1LRQH0dIJEC+qhYF5TVix2lzfEc0U4IgYN8FXbm5I5RXbYiI6ObsrOXo4m4HADjXAda7YbkxU+dzVchT1cBGIUNMF65tQ0REzWsYmuoI825YbsxUw1WbQV3doVTIRE5DRESmrmExv+RsXrkhE9Uw32YEh6SIiKgFet7YY+osr9yQKSosr0XStVIAuvVtiIiI/k1PH92Vm+zSaqhq6kRO07ZYbszQgZQCCIJup1cu3EdERC3hZKuAz433jJS8cpHTtC2WGzO078aQ1B0hlr/KJBERGU+ItwMA4CLLDZkSdb0Why4VAgBGcOE+IiIyQA9v3bybi7mWPamY5cbMnEgvQaVaA3d7a0T4GX8zUyIislyhProrNxyWIpMSezEfAHBHiAekUonIaYiIyJz08P6z3AiCIHKatsNyY0YEQUDsBc63ISKiW9PF3R4KmQTltfXILq0WO06bYbkxI2mFlcgsqYKVTIrB3dzFjkNERGbGSi5FsIc9AOBiruUOTbHcmJHd5/IAAAO6uMLe2iQ2dCciIjPTcMdUSj7LDZmArYk5AIC7e/mInISIiMxVwx1TFyz4jimWGzNxMU+FlPxyWMmkuKsnyw0REd2akA5wxxTLjZn49cZVm2E9POBkqxA5DRERmauGYakrRZWordeInKZtsNyYAUEQ9ENSE6P8RE5DRETmzNtRCScbBTRaAZcLKsSO0yZYbsxAQuZ1ZJdWw85Kxl3AiYioVSQSiX69G0u9Y4rlxgw0DEmNDveGUiETOQ0REZm7UAu/Y4rlxsTVabTYfiYXAIekiIjIOPR7TFnopGKWGxN39HIRiivVcLOzwqBgN7HjEBGRBWi4Y8pSN9BkuTFxf13bRi7jbxcREbVedy9duSkor0VJpVrkNMbHd0sTVq3W6FclnsAhKSIiMhJ7azkCXW0B6NZRszQsNybsx/gsVKo18HexQZ9AZ7HjEBGRBfnrDuGWhuXGBNXWa/Dq1nNY8us5AMB90QGQSCQipyIiIksSasG3g3P3RRNzpbACz3x3GudydJcJHxvSGXOHBYucioiILE2Iz407pizwdnCWGxMSl1aMR748iSq1Bq52VnjvvkgMD+GifUREZHwNw1KX8sqh1QqQSi1nhIDDUiZkzcE0VKk16N/ZFTvnD2GxISKiNhPkZgdbKxmq6zQWt5gfy40JuXzjD9fzo3vAy1EpchoiIrJkMqkE/YJcAQDH0opFTmNcLDcmorK2HjllNQCArh72IqchIqKOYOCNxWGPXS4SOYlxsdyYiCuFlQAANzsruNhZiZyGiIg6gkFd3QEAx9NLUK/RipzGeFhuTMTlQt2QVLAnr9oQEVH7CPNxhJONAhW19TiTXSZ2HKNhuTERlwsqAADBHJIiIqJ2IpVKENPF8oamWG5MRFqBbliqK6/cEBFROxrUVVdujl62nEnFLDcm4nKh7soNyw0REbWngTfm3cRnXkdNnUbkNMbBcmMC6jRaZBTxyg0REbW/Lu528HZUQl2vRfzV62LHMQqWGxNwtbgK9VoBNgoZfLi+DRERtSOJRKK/Jfyohcy7YbkxAWk3hqSCPe0savlrIiIyDw1DU5aymB/LjQlouFOKi/cREZEYGq7cnLlWClVNnchpWo/lxgSkFXAyMRERicfX2Qad3e2gFYDjV0rEjtNqLDcmQD8sxSs3REQkEkuad8NyIzJBEJBWyDuliIhIXA1bMcRZwLwblhuR5alqUFFbD5lUgk5udmLHISKiDuq2GysVp+SXo7C8VuQ0rcNyI7KGycSd3GxhJedvBxERicPVzgoh3g4AgIRM817vhu+mIkvjnlJERGQiIvycAADJZr6JJsuNyLjtAhERmYoIf125OctyQ63BNW6IiMhUhP/lyo0gCCKnuXUsNyK7zN3AiYjIRIT5OEImlaCoQo08VY3YcW4Zy42IyqrqUFShm5HexYN3ShERkbiUChm63fjH9tlr5js0xXIjoob5Nt6OSjgoFSKnISIiajw0Za5YbkTEbReIiMjUNNwxZc6TilluRJTGO6WIiMjEhOvLjcpsJxWz3IhEEAQk5+hacTDn2xARkYkI83GEVAIUVdQiX2WeKxWz3IhAXa/F8z+ewdHLuv07ege6iJyIiIhIx8ZKhm6eupWKzXVoiuWmnZVUqvHQ58fxY/w1SCXAaxN66i8BEhERmYJwM593w3LTji4XVGDyJ0dxIr0E9tZyrH+4H2YNDBI7FhERUSMRfo4AzPeOKbnYAToKQRDw6JcncbW4Cv4uNlj/cD9093IQOxYREdE/mPs2DLxy004yS6qQUVwFK5kUvzw1iMWGiIhMVpiPE6QSoLC8FvlmuFIxy007adg+PtzPEe721iKnISIiujkbK5l+mRJzXKmY5aadxF/VlZs+vDOKiIjMgDlPKma5aScJV0sBANGdWG6IiMj0RZjxNgwsN+2gorYeF/NUAIA+LDdERGQGzHkbBpMoN6tXr0ZQUBCUSiUGDBiAEydO3PS569atw5AhQ+Di4gIXFxeMHDmy2eebgjNZpdAKgJ+zDbwclWLHISIi+ldhvrqVigvKa1FgZpOKRS83mzdvxsKFC7F06VIkJCQgMjISo0ePRkFBQZPPP3DgAKZNm4b9+/cjLi4OAQEBuPPOO5Gdnd3OyVtOP9+GV22IiMhM2FrJ9ZOKE7NKxQ1jINHLzcqVK/HYY49h9uzZCAsLw9q1a2Fra4v169c3+fxvv/0WTz75JKKiohASEoLPPvsMWq0WsbGx7Zy85RrulOoT6CxuECIiIgPc1sUNALAzOU/kJIYRtdyo1WrEx8dj5MiR+mNSqRQjR45EXFxci75GVVUV6urq4Orq2uTjtbW1UKlUjT7ak1YrICGzFAAnExMRkXmZ3NsPALArOQ8VtfUip2k5UctNUVERNBoNvLy8Gh338vJCXl7LWuILL7wAX1/fRgXpr5YvXw4nJyf9R0BAQKtzG+JKUSXKquugVEgR6uPYrr82ERFRa0QFOKOLux2q6zTYZUZXb0QflmqNFStWYNOmTfj555+hVDY9UXfx4sUoKyvTf2RlZbVrxoQb8216+TtDITPr001ERB2MRCLBlD66qzdbEq6JnKblRH23dXd3h0wmQ35+fqPj+fn58Pb2bva17777LlasWIE9e/agV69eN32etbU1HB0dG320pz/n23BIioiIzM+kG0NTcVeKkV1aLXKalhG13FhZWSE6OrrRZOCGycExMTE3fd3bb7+NN954A7t27ULfvn3bI+ot+3NlYmdxgxAREd0CfxdbDOjsCkEAfjltuncm/5Xo4yQLFy7EunXr8OWXX+LChQuYO3cuKisrMXv2bADAzJkzsXjxYv3z33rrLSxZsgTr169HUFAQ8vLykJeXh4qKCrG+hZsqq65DaoEuF28DJyIic3VPH38AuqEpQRBETvPvRC83U6dOxbvvvotXXnkFUVFRSExMxK5du/STjDMzM5Gbm6t//po1a6BWq3HvvffCx8dH//Huu++K9S3c1OkbQ1Kd3Gy5WSYREZmtMRHesJZLkVZYiTNmsJGmXOwAAPD000/j6aefbvKxAwcONPo8IyOj7QMZif4WcM63ISIiM+agVGB0T29sTcrBloRriAxwFjtSs0S/cmPJGu6U6s0hKSIiMnMNd01tTcqBul4rcprmsdy0EY1W0C9XzSs3RERk7gZ3dYeHgzWuV9Vhf0rTWySZCpabNnIhV4WK2nrYW8vRw9tB7DhEREStIpdJMTHSF4Du6o0pY7lpI3FpxQCAfkEukEklIqchIiJqvQlRunITeyEflSa8HQPLTRuJu6IrNwOD3UVOQkREZBwRfk7o5GaLmjotfr+Q/+8vEAnLTRuo12hxIr0EABAT7CZyGiIiIuOQSCQY30t39ea3pNx/ebZ4WG7aQHKObr6No1LOzTKJiMiijL8x7+bgpQKUVdWJnKZpLDdtoGG+zYAubpxvQ0REFqWHtwO6e9mjTiNg93nT3Cmc5aYNNMy3ienCISkiIrI8fw5NmeZdUyw3Rlan0eJUBufbEBGR5br7xtDUsbRiFFXUipzmn1hujOzMtVJUqTVwsVWghxfXtyEiIsvT2d0OEX5O0GgF7Ew2vaEplhsja5hvExPsBinn2xARkYUaH+kDwDSHplhujOxYGufbEBGR5Rt3Y97NyYwS5JXViJymMZYbI6qt1yD+xmaZnG9DRESWzM/ZBn07uUAQgG1nTOvqDcuNEZ3OLEVtvRYeDtYI9rAXOw4REVGbGhuhG5o6eKlQ5CSNsdwYUcN8m9u6uEEi4XwbIiKybLfdmIKRcPU66jVakdP8ieXGiLi+DRERdSQ9vB3gYC1HpVqDi3nlYsfRY7kxkpo6DRIzSwFwvg0REXUMMqkEfTq5AIB+jTdTwHJjJPFXr0Ot0cLbUYkgN1ux4xAREbWLfkG6cnPyxg01pkAudgBLEeRuhxfHhEAqAefbEBFRh9E3yBWA7sqNIAgm8R7IcmMkfs42eGJosNgxiIiI2lWkvzMUMgnyVbW4dr0aAa7ij15wWIqIiIhumY2VDOF+TgCAU1dNY94Nyw0RERG1Sr8bQ1MnM0xj3g3LDREREbVKXxO7Y4rlhoiIiFol+ka5uZRfgdIqtchpWG6IiIioldzsrdHFww4A9HssionlhoiIiFqtXyfTmXfDckNERESt1jfIdObdsNwQERFRqzXcMXXmWhlq6jSiZmG5ISIiolbr5GYLd3trqDVanM0uEzULyw0RERG1mkQi+XOfKZGHplhuiIiIyCj+3GdK3EnFLDdERERkFP2CXCCRAFXqelFzcONMIiIiMoqevk5IWnonHJUKUXPwyg0REREZhUwqEb3YACw3REREZGFYboiIiMiisNwQERGRRWG5ISIiIovCckNEREQWheWGiIiILArLDREREVkUlhsiIiKyKCw3REREZFFYboiIiMiisNwQERGRRWG5ISIiIovCckNEREQWRS52gPYmCAIAQKVSiZyEiIiIWqrhfbvhfbw5Ha7clJeXAwACAgJETkJERESGKi8vh5OTU7PPkQgtqUAWRKvVIicnBw4ODpBIJGLHaXMqlQoBAQHIysqCo6Oj2HHMGs+l8fBcGgfPo/HwXBpPW51LQRBQXl4OX19fSKXNz6rpcFdupFIp/P39xY7R7hwdHfkX1kh4Lo2H59I4eB6Nh+fSeNriXP7bFZsGnFBMREREFoXlhoiIiCwKy42Fs7a2xtKlS2FtbS12FLPHc2k8PJfGwfNoPDyXxmMK57LDTSgmIiIiy8YrN0RERGRRWG6IiIjIorDcEBERkUVhuSEiIiKLwnJjIbKzs/HQQw/Bzc0NNjY2iIiIwKlTp/SPC4KAV155BT4+PrCxscHIkSORmpoqYmLTpNFosGTJEnTu3Bk2NjYIDg7GG2+80WgvE57Lph06dAjjx4+Hr68vJBIJfvnll0aPt+S8lZSUYPr06XB0dISzszMeeeQRVFRUtON3YRqaO5d1dXV44YUXEBERATs7O/j6+mLmzJnIyclp9DV4Lv/9z+RfPfHEE5BIJPjggw8aHed51GnJubxw4QImTJgAJycn2NnZoV+/fsjMzNQ/XlNTg6eeegpubm6wt7fHPffcg/z8/DbJy3JjAa5fv45BgwZBoVBg586dOH/+PN577z24uLjon/P222/jww8/xNq1a3H8+HHY2dlh9OjRqKmpETG56XnrrbewZs0afPzxx7hw4QLeeustvP322/joo4/0z+G5bFplZSUiIyOxevXqJh9vyXmbPn06zp07h71792Lbtm04dOgQHn/88fb6FkxGc+eyqqoKCQkJWLJkCRISErBlyxakpKRgwoQJjZ7Hc/nvfyYb/Pzzz/jjjz/g6+v7j8d4HnX+7VympaVh8ODBCAkJwYEDB3DmzBksWbIESqVS/5wFCxbgt99+ww8//ICDBw8iJycHU6ZMaZvAApm9F154QRg8ePBNH9dqtYK3t7fwzjvv6I+VlpYK1tbWwnfffdceEc3GuHHjhDlz5jQ6NmXKFGH69OmCIPBcthQA4eeff9Z/3pLzdv78eQGAcPLkSf1zdu7cKUgkEiE7O7vdspuav5/Lppw4cUIAIFy9elUQBJ7LptzsPF67dk3w8/MTkpOThU6dOgnvv/++/jGex6Y1dS6nTp0qPPTQQzd9TWlpqaBQKIQffvhBf+zChQsCACEuLs7oGXnlxgJs3boVffv2xX333QdPT0/07t0b69at0z+enp6OvLw8jBw5Un/MyckJAwYMQFxcnBiRTdbAgQMRGxuLS5cuAQCSkpJw5MgRjBkzBgDP5a1qyXmLi4uDs7Mz+vbtq3/OyJEjIZVKcfz48XbPbE7KysogkUjg7OwMgOeypbRaLWbMmIHnn38ePXv2/MfjPI8to9VqsX37dnTv3h2jR4+Gp6cnBgwY0GjoKj4+HnV1dY1+BoSEhCAwMLBNfnay3FiAK1euYM2aNejWrRt2796NuXPnYt68efjyyy8BAHl5eQAALy+vRq/z8vLSP0Y6L774Ih544AGEhIRAoVCgd+/eePbZZzF9+nQAPJe3qiXnLS8vD56eno0el8vlcHV15bltRk1NDV544QVMmzZNv0khz2XLvPXWW5DL5Zg3b16Tj/M8tkxBQQEqKiqwYsUK3HXXXdizZw8mT56MKVOm4ODBgwB059LKykpfwBu01c/ODrcruCXSarXo27cv3nzzTQBA7969kZycjLVr12LWrFkipzMv33//Pb799lts3LgRPXv2RGJiIp599ln4+vryXJLJqaurw/333w9BELBmzRqx45iV+Ph4rFq1CgkJCZBIJGLHMWtarRYAMHHiRCxYsAAAEBUVhWPHjmHt2rUYOnRou2filRsL4OPjg7CwsEbHQkND9bPUvb29AeAfs9Lz8/P1j5HO888/r796ExERgRkzZmDBggVYvnw5AJ7LW9WS8+bt7Y2CgoJGj9fX16OkpITntgkNxebq1avYu3ev/qoNwHPZEocPH0ZBQQECAwMhl8shl8tx9epVLFq0CEFBQQB4HlvK3d0dcrn8X9+H1Go1SktLGz2nrX52stxYgEGDBiElJaXRsUuXLqFTp04AgM6dO8Pb2xuxsbH6x1UqFY4fP46YmJh2zWrqqqqqIJU2/mshk8n0/zLhubw1LTlvMTExKC0tRXx8vP45+/btg1arxYABA9o9sylrKDapqan4/fff4ebm1uhxnst/N2PGDJw5cwaJiYn6D19fXzz//PPYvXs3AJ7HlrKyskK/fv2afR+Kjo6GQqFo9DMgJSUFmZmZbfOz0+hTlKndnThxQpDL5cKyZcuE1NRU4dtvvxVsbW2Fb775Rv+cFStWCM7OzsKvv/4qnDlzRpg4caLQuXNnobq6WsTkpmfWrFmCn5+fsG3bNiE9PV3YsmWL4O7uLvznP//RP4fnsmnl5eXC6dOnhdOnTwsAhJUrVwqnT5/W38HTkvN21113Cb179xaOHz8uHDlyROjWrZswbdo0sb4l0TR3LtVqtTBhwgTB399fSExMFHJzc/UftbW1+q/Bc/nvfyb/7u93SwkCz2ODfzuXW7ZsERQKhfDpp58KqampwkcffSTIZDLh8OHD+q/xxBNPCIGBgcK+ffuEU6dOCTExMUJMTEyb5GW5sRC//fabEB4eLlhbWwshISHCp59+2uhxrVYrLFmyRPDy8hKsra2FESNGCCkpKSKlNV0qlUqYP3++EBgYKCiVSqFLly7Cyy+/3OhNg+eyafv37xcA/ONj1qxZgiC07LwVFxcL06ZNE+zt7QVHR0dh9uzZQnl5uQjfjbiaO5fp6elNPgZA2L9/v/5r8Fz++5/Jv2uq3PA86rTkXH7++edC165dBaVSKURGRgq//PJLo69RXV0tPPnkk4KLi4tga2srTJ48WcjNzW2TvBJB+MvSq0RERERmjnNuiIiIyKKw3BAREZFFYbkhIiIii8JyQ0RERBaF5YaIiIgsCssNERERWRSWGyIiIrIoLDdERERkUVhuiMjsHThwABKJ5B+b8jXn1VdfRVRUVJtlIiLxsNwQUbtau3YtHBwcUF9frz9WUVEBhUKBYcOGNXpuQ2lJS0tr9msOHDgQubm5cHJyMmrWYcOG4dlnnzXq1ySitsdyQ0Ttavjw4aioqMCpU6f0xw4fPgxvb28cP34cNTU1+uP79+9HYGAggoODm/2aVlZW8Pb2hkQiabPcRGQ+WG6IqF316NEDPj4+OHDggP7YgQMHMHHiRHTu3Bl//PFHo+PDhw+HVqvF8uXL0blzZ9jY2CAyMhI//vhjo+f9fVhq3bp1CAgIgK2tLSZPnoyVK1fC2dn5H3m+/vprBAUFwcnJCQ888ADKy8sBAA8//DAOHjyIVatWQSKRQCKRICMjw9ing4jaAMsNEbW74cOHY//+/frP9+/fj2HDhmHo0KH649XV1Th+/DiGDx+O5cuX46uvvsLatWtx7tw5LFiwAA899BAOHjzY5Nc/evQonnjiCcyfPx+JiYkYNWoUli1b9o/npaWl4ZdffsG2bduwbds2HDx4ECtWrAAArFq1CjExMXjssceQm5uL3NxcBAQEtMHZICJjk4sdgIg6nuHDh+PZZ59FfX09qqurcfr0aQwdOhR1dXVYu3YtACAuLg61tbUYNmwYwsLC8PvvvyMmJgYA0KVLFxw5cgT/+9//MHTo0H98/Y8++ghjxozBc889BwDo3r07jh07hm3btjV6nlarxYYNG+Dg4AAAmDFjBmJjY7Fs2TI4OTnBysoKtra28Pb2bsvTQURGxnJDRO1u2LBhqKysxMmTJ3H9+nV0794dHh4eGDp0KGbPno2amhocOHAAXbp0QUVFBaqqqjBq1KhGX0OtVqN3795Nfv2UlBRMnjy50bH+/fv/o9wEBQXpiw0A+Pj4oKCgwEjfJRGJheWGiNpd165d4e/vj/379+P69ev6qy++vr4ICAjAsWPHsH//ftxxxx2oqKgAAGzfvh1+fn6Nvo61tXWrcigUikafSyQSaLXaVn1NIhIfyw0RiWL48OE4cOAArl+/jueff15//Pbbb8fOnTtx4sQJzJ07F2FhYbC2tkZmZmaTQ1BN6dGjB06ePNno2N8/bwkrKytoNBqDX0dE4mK5ISJRDB8+HE899RTq6uoalZahQ4fi6aefhlqtxvDhw+Hg4IDnnnsOCxYsgFarxeDBg1FWVoajR4/C0dERs2bN+sfXfuaZZ3D77bdj5cqVGD9+PPbt24edO3cafKt4UFAQjh8/joyMDNjb28PV1RVSKe/DIDJ1/FtKRKIYPnw4qqur0bVrV3h5eemPDx06FOXl5fpbxgHgjTfewJIlS7B8+XKEhobirrvuwvbt29G5c+cmv/agQYOwdu1arFy5EpGRkdi1axcWLFgApVJpUMbnnnsOMpkMYWFh8PDwQGZm5q1/w0TUbiSCIAhihyAiamuPPfYYLl68iMOHD4sdhYjaGIeliMgivfvuuxg1ahTs7Oywc+dOfPnll/jkk0/EjkVE7YBXbojIIt1///04cOAAysvL0aVLFzzzzDN44oknxI5FRO2A5YaIiIgsCicUExERkUVhuSEiIiKLwnJDREREFoXlhoiIiCwKyw0RERFZFJYbIiIisigsN0RERGRRWG6IiIjIovx/l/9rJcpBEXMAAAAASUVORK5CYII=",
"text/plain": [
"<Figure size 640x480 with 1 Axes>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"values = data[\"Weight\"].sort_values().unique()[1:]\n",
"igs = [get_information_gain(data[\"Weight\"], data[\"Weight\"] < value) for value in values]\n",
"\n",
"fig, ax = plt.subplots()\n",
"ax.plot(values, igs)\n",
"ax.set_xlabel(\"Weight\")\n",
"ax.set_ylabel(\"Information Gain\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "18037ae6-3a21-4fd6-b2d8-8a7fd089b118",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 159,
"id": "08c32adb-8615-4cda-b2a8-e355ea7af9e9",
"metadata": {},
"outputs": [],
"source": [
"# First row is the value which obtained the best information gain\n",
"# Second row is the information gain value\n",
"\n",
"# We can see the best thing to do in the above (in terms of maximizing information gain) is to split weight at 103\n",
"# This split would generate two DataFrames\n",
"# We would keep applying this recursively and create an entire decision tree\n",
"\n",
"# How do we decide when to stop splitting? Usually three metrics:\n",
"# max_depth: Maximum depth of the tree, if we leave it to None, then it will grow until all leaves are pure\n",
"# min_samples_split: The minimum number of observations in a split to keep creating new nodes\n",
"# min_information_gain: The minimum amount of IG for the tree to keep growing\n",
"\n",
"# Steps:\n",
"# Make sure min_samples_split and max_depth are met\n",
"# Make a split\n",
"# Make sure that min_information_gain is met\n",
"# Save the split and repeat"
]
},
{
"cell_type": "code",
"execution_count": 161,
"id": "bab774ed-4221-47c6-b40d-9d36727dc275",
"metadata": {},
"outputs": [],
"source": [
"def get_best_split(df, y):\n",
" column_max_information_gains = [\n",
" {\"column_name\": column, **get_max_information_gain(df[column], df[y])} for column in df.columns if column != y\n",
" ]\n",
" best_split_info = sorted(column_max_information_gains, key=lambda x: x[\"information_gain\"])[-1]\n",
" return best_split_info\n",
"\n",
"def make_split(df, split_info):\n",
" column_name = split_info[\"column_name\"]\n",
" split_value = split_info[\"split_value\"]\n",
" is_numeric = split_info[\"is_numeric\"]\n",
" assert is_numeric == df[column_name].dtype != \"object\"\n",
" if is_numeric:\n",
" mask = df[column_name] < split_value\n",
" else:\n",
" mask = df[column_name].isin(split_value)\n",
" df_left = df[mask]\n",
" df_right = df[~mask]\n",
" return df_left, df_right"
]
},
{
"cell_type": "code",
"execution_count": 162,
"id": "95c37e9f-4bcf-4952-adf2-7596ca996337",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'column_name': 'Weight',\n",
" 'split_value': 103,\n",
" 'information_gain': 0.3824541370911896,\n",
" 'is_numeric': True}"
]
},
"execution_count": 162,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"split_info = get_best_split(data, \"Obese\")\n",
"\n",
"split_info"
]
},
{
"cell_type": "code",
"execution_count": 163,
"id": "ab56bf34-954c-4945-ba4b-011e02f3df3d",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(500, 229, 271)"
]
},
"execution_count": 163,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"left, right = make_split(data, split_info)\n",
"\n",
"len(data), len(left), len(right)"
]
},
{
"cell_type": "code",
"execution_count": 164,
"id": "b7c5a98d-1e93-4c65-814b-310918998588",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'column_name': 'Height',\n",
" 'split_value': 178,\n",
" 'information_gain': 0.28026630900174687,\n",
" 'is_numeric': True}"
]
},
"execution_count": 164,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"split_info = get_best_split(left, \"Obese\")\n",
"\n",
"split_info"
]
},
{
"cell_type": "code",
"execution_count": 165,
"id": "93f9aa35-eac3-4a21-8cc7-361b01dcd678",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'column_name': 'Weight',\n",
" 'split_value': 116,\n",
" 'information_gain': 0.09289094500737183,\n",
" 'is_numeric': True}"
]
},
"execution_count": 165,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"split_info = get_best_split(right, \"Obese\")\n",
"\n",
"split_info"
]
},
{
"cell_type": "code",
"execution_count": 232,
"id": "2efe3f4d-891c-463b-899c-80597cc15f9d",
"metadata": {},
"outputs": [],
"source": [
"class DecisionNode:\n",
" def __init__(self, column, split_value, is_numeric, left, right, prediction=None):\n",
" self.column = column\n",
" self.split_value = split_value\n",
" self.is_numeric = is_numeric\n",
" self.left = left\n",
" self.right = right\n",
" self.prediction = prediction\n",
"\n",
" def __repr__(self, depth=0, indent=\" \"):\n",
" prefix = depth * indent\n",
" # Representation for leaf node\n",
" if self.is_leaf():\n",
" return f\"{prefix}Leaf(prediction={self.prediction})\"\n",
" description = f\"{prefix}DecisionNode(column={self.column}, split_value={self.split_value}, is_numeric={self.is_numeric})\\n\"\n",
" if self.left:\n",
" description += f\"{prefix}left:\\n{self.left.__repr__(depth + 1, indent)}\\n\"\n",
" if self.right:\n",
" description += f\"{prefix}right:\\n{self.right.__repr__(depth + 1, indent)}\"\n",
" return description\n",
"\n",
" def is_leaf(self):\n",
" return self.left is None and self.right is None\n",
"\n",
"def build_tree(df, y, depth, max_depth, min_samples_split, min_information_gain, is_classification):\n",
"\n",
" print(\"depth:\", depth)\n",
" \n",
" if depth >= max_depth:\n",
" print(\"hit max depth\", depth)\n",
" return create_leaf_node(df, y, is_classification)\n",
"\n",
" if len(df) < min_samples_split:\n",
" print(\"hit min samples\", len(df))\n",
" return create_leaf_node(df, y, is_classification)\n",
"\n",
" print(\"getting best split\", len(df))\n",
" split_info = get_best_split(df, y)\n",
"\n",
" if split_info[\"information_gain\"] < min_information_gain:\n",
" print(\"hit min info gain\", split_info[\"information_gain\"])\n",
" return create_leaf_node(df, y, is_classification)\n",
"\n",
" print(f\"Size before split: {len(df)}\")\n",
" \n",
" print(\"splitting on:\", split_info)\n",
" df_left, df_right = make_split(df, split_info)\n",
"\n",
" print(f\"left size: {len(df_left)}, right size: {len(df_right)}\")\n",
" \n",
" subtree_left = build_tree(df_left, y, depth+1, max_depth, min_samples_split, min_information_gain, is_classification)\n",
" subtree_right = build_tree(df_right, y, depth+1, max_depth, min_samples_split, min_information_gain, is_classification)\n",
"\n",
" return DecisionNode(\n",
" column=split_info[\"column_name\"],\n",
" split_value=split_info[\"split_value\"],\n",
" is_numeric=split_info[\"is_numeric\"],\n",
" left=subtree_left,\n",
" right=subtree_right,\n",
" prediction=None,\n",
" )\n",
"\n",
"def create_leaf_node(df, y, is_classification=True):\n",
" if is_classification:\n",
" prediction = df[y].mode()[0]\n",
" else:\n",
" prediction = df[y].mean()\n",
"\n",
" return DecisionNode(\n",
" column=None,\n",
" split_value=None,\n",
" is_numeric=None,\n",
" left=None,\n",
" right=None,\n",
" prediction=prediction,\n",
" )\n",
"\n",
"def train_decision_tree(df, y, max_depth=10, min_samples_split=2, min_information_gain=0.01, is_classification=True):\n",
" return build_tree(df, y, 0, max_depth, min_samples_split, min_information_gain, is_classification)"
]
},
{
"cell_type": "code",
"execution_count": 233,
"id": "2d65d461-a722-4be1-b949-57490c926f0d",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"depth: 0\n",
"getting best split 500\n",
"Size before split: 500\n",
"splitting on: {'column_name': 'Weight', 'split_value': 103, 'information_gain': 0.3824541370911896, 'is_numeric': True}\n",
"left size: 229, right size: 271\n",
"depth: 1\n",
"getting best split 229\n",
"Size before split: 229\n",
"splitting on: {'column_name': 'Height', 'split_value': 178, 'information_gain': 0.28026630900174687, 'is_numeric': True}\n",
"left size: 138, right size: 91\n",
"depth: 2\n",
"getting best split 138\n",
"Size before split: 138\n",
"splitting on: {'column_name': 'Weight', 'split_value': 66, 'information_gain': 0.3905984031684069, 'is_numeric': True}\n",
"left size: 41, right size: 97\n",
"depth: 3\n",
"getting best split 41\n",
"hit min info gain 2.5849394142282115e-26\n",
"depth: 3\n",
"getting best split 97\n",
"Size before split: 97\n",
"splitting on: {'column_name': 'Height', 'split_value': 151, 'information_gain': 0.16796853890498697, 'is_numeric': True}\n",
"left size: 35, right size: 62\n",
"depth: 4\n",
"getting best split 35\n",
"Size before split: 35\n",
"splitting on: {'column_name': 'Weight', 'split_value': 67, 'information_gain': 0.13003339959432547, 'is_numeric': True}\n",
"left size: 2, right size: 33\n",
"depth: 5\n",
"getting best split 2\n",
"Size before split: 2\n",
"splitting on: {'column_name': 'Height', 'split_value': 149, 'information_gain': 0.9999999998557304, 'is_numeric': True}\n",
"left size: 1, right size: 1\n",
"depth: 6\n",
"hit min samples 1\n",
"depth: 6\n",
"hit min samples 1\n",
"depth: 5\n",
"getting best split 33\n",
"hit min info gain 0.0\n",
"depth: 4\n",
"getting best split 62\n",
"Size before split: 62\n",
"splitting on: {'column_name': 'Weight', 'split_value': 82, 'information_gain': 0.31434467087549045, 'is_numeric': True}\n",
"left size: 26, right size: 36\n",
"depth: 5\n",
"getting best split 26\n",
"Size before split: 26\n",
"splitting on: {'column_name': 'Height', 'split_value': 161, 'information_gain': 0.3216587044834349, 'is_numeric': True}\n",
"left size: 10, right size: 16\n",
"depth: 6\n",
"getting best split 10\n",
"Size before split: 10\n",
"splitting on: {'column_name': 'Weight', 'split_value': 74, 'information_gain': 0.6099865469532797, 'is_numeric': True}\n",
"left size: 4, right size: 6\n",
"depth: 7\n",
"getting best split 4\n",
"hit min info gain 0.0\n",
"depth: 7\n",
"getting best split 6\n",
"Size before split: 6\n",
"splitting on: {'column_name': 'Height', 'split_value': 154, 'information_gain': 0.3166890882188412, 'is_numeric': True}\n",
"left size: 2, right size: 4\n",
"depth: 8\n",
"getting best split 2\n",
"Size before split: 2\n",
"splitting on: {'column_name': 'Weight', 'split_value': 78, 'information_gain': 0.9999999998557304, 'is_numeric': True}\n",
"left size: 1, right size: 1\n",
"depth: 9\n",
"hit min samples 1\n",
"depth: 9\n",
"hit min samples 1\n",
"depth: 8\n",
"getting best split 4\n",
"hit min info gain 0.0\n",
"depth: 6\n",
"getting best split 16\n",
"hit min info gain 0.0\n",
"depth: 5\n",
"getting best split 36\n",
"Size before split: 36\n",
"splitting on: {'column_name': 'Height', 'split_value': 173, 'information_gain': 0.23084979872365263, 'is_numeric': True}\n",
"left size: 27, right size: 9\n",
"depth: 6\n",
"getting best split 27\n",
"hit min info gain 0.06748201253360614\n",
"depth: 6\n",
"getting best split 9\n",
"Size before split: 9\n",
"splitting on: {'column_name': 'Weight', 'split_value': 95, 'information_gain': 0.9910760596939526, 'is_numeric': True}\n",
"left size: 5, right size: 4\n",
"depth: 7\n",
"getting best split 5\n",
"hit min info gain 0.0\n",
"depth: 7\n",
"getting best split 4\n",
"hit min info gain 0.0\n",
"depth: 2\n",
"getting best split 91\n",
"hit min info gain 2.5849394142282115e-26\n",
"depth: 1\n",
"getting best split 271\n",
"hit min info gain 0.09289094500737183\n"
]
}
],
"source": [
"y = \"Obese\"\n",
"max_depth = 10\n",
"min_samples_split = 2\n",
"min_information_gain = 0.1\n",
"is_classification = True\n",
"\n",
"tree = train_decision_tree(data, y, max_depth, min_samples_split, min_information_gain, is_classification=True)"
]
},
{
"cell_type": "code",
"execution_count": 234,
"id": "47d36982-6371-4355-92e3-e4b70a5a97d1",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"DecisionNode(column=Weight, split_value=103, is_numeric=True)\n",
"left:\n",
" DecisionNode(column=Height, split_value=178, is_numeric=True)\n",
" left:\n",
" DecisionNode(column=Weight, split_value=66, is_numeric=True)\n",
" left:\n",
" Leaf(prediction=0)\n",
" right:\n",
" DecisionNode(column=Height, split_value=151, is_numeric=True)\n",
" left:\n",
" DecisionNode(column=Weight, split_value=67, is_numeric=True)\n",
" left:\n",
" DecisionNode(column=Height, split_value=149, is_numeric=True)\n",
" left:\n",
" Leaf(prediction=1)\n",
" right:\n",
" Leaf(prediction=0)\n",
" right:\n",
" Leaf(prediction=1)\n",
" right:\n",
" DecisionNode(column=Weight, split_value=82, is_numeric=True)\n",
" left:\n",
" DecisionNode(column=Height, split_value=161, is_numeric=True)\n",
" left:\n",
" DecisionNode(column=Weight, split_value=74, is_numeric=True)\n",
" left:\n",
" Leaf(prediction=0)\n",
" right:\n",
" DecisionNode(column=Height, split_value=154, is_numeric=True)\n",
" left:\n",
" DecisionNode(column=Weight, split_value=78, is_numeric=True)\n",
" left:\n",
" Leaf(prediction=1)\n",
" right:\n",
" Leaf(prediction=0)\n",
" right:\n",
" Leaf(prediction=1)\n",
" right:\n",
" Leaf(prediction=0)\n",
" right:\n",
" DecisionNode(column=Height, split_value=173, is_numeric=True)\n",
" left:\n",
" Leaf(prediction=1)\n",
" right:\n",
" DecisionNode(column=Weight, split_value=95, is_numeric=True)\n",
" left:\n",
" Leaf(prediction=0)\n",
" right:\n",
" Leaf(prediction=1)\n",
" right:\n",
" Leaf(prediction=0)\n",
"right:\n",
" Leaf(prediction=1)"
]
},
"execution_count": 234,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tree"
]
},
{
"cell_type": "code",
"execution_count": 235,
"id": "fdf0165f-8568-4241-bb2e-2a7f76f85114",
"metadata": {},
"outputs": [],
"source": [
"def _predict(tree, example):\n",
" if tree.is_leaf():\n",
" return tree.prediction\n",
" if tree.is_numeric:\n",
" if example[tree.column] < tree.split_value:\n",
" return _predict(tree.left, example)\n",
" else:\n",
" return _predict(tree.right, example)\n",
" else:\n",
" if example[tree.column] in tree.split_value:\n",
" return _predict(tree.left, example)\n",
" else:\n",
" return _predict(tree.right, example)\n",
"\n",
"def predict(tree, df):\n",
" return df.apply(lambda row: _predict(tree, row), axis=1)"
]
},
{
"cell_type": "code",
"execution_count": 236,
"id": "9216abe0-da28-4218-9edf-1d47aef2455f",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Gender Male\n",
"Height 174\n",
"Weight 96\n",
"Obese 1\n",
"Name: 0, dtype: object"
]
},
"execution_count": 236,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"example = data.iloc[0]\n",
"\n",
"example"
]
},
{
"cell_type": "code",
"execution_count": 237,
"id": "aa2f778c-1610-4d84-84ec-9917feb9b128",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 237,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"_predict(tree, example)"
]
},
{
"cell_type": "code",
"execution_count": 238,
"id": "8550a121-307f-4226-9e4a-b045c34394ee",
"metadata": {},
"outputs": [],
"source": [
"predictions = predict(tree, data)"
]
},
{
"cell_type": "code",
"execution_count": 239,
"id": "b453fabd-5f84-44b9-ac13-7b6f6394c032",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0 1\n",
"1 0\n",
"2 1\n",
"3 1\n",
"4 0\n",
" ..\n",
"495 1\n",
"496 1\n",
"497 1\n",
"498 1\n",
"499 1\n",
"Length: 500, dtype: int64"
]
},
"execution_count": 239,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"predictions"
]
},
{
"cell_type": "code",
"execution_count": 207,
"id": "d2926d7e-ae58-42a0-bb14-e6da06f7840f",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0 True\n",
"1 True\n",
"2 False\n",
"3 False\n",
"4 True\n",
" ... \n",
"495 False\n",
"496 False\n",
"497 False\n",
"498 True\n",
"499 False\n",
"Length: 500, dtype: bool"
]
},
"execution_count": 207,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"predictions == data[\"Obese\"]"
]
},
{
"cell_type": "code",
"execution_count": 240,
"id": "c8b540c3-7f17-42ff-b01a-30f8918d59d3",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"depth: 0\n",
"getting best split 5\n",
"Size before split: 5\n",
"splitting on: {'column_name': 'name', 'split_value': ('d', 'b'), 'information_gain': 0.9709505943103991, 'is_numeric': False}\n",
"left size: 2, right size: 3\n",
"depth: 1\n",
"getting best split 2\n",
"hit min info gain 0.0\n",
"depth: 1\n",
"getting best split 3\n",
"hit min info gain 0\n"
]
}
],
"source": [
"new_tree = train_decision_tree(new_data, \"Obese\")"
]
},
{
"cell_type": "code",
"execution_count": 242,
"id": "379aa34a-566a-4b34-a3fa-108488b7b5ff",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 242,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"_predict(new_tree, new_data.iloc[0])"
]
},
{
"cell_type": "code",
"execution_count": 243,
"id": "981dc982-88de-4f50-bbe9-5e06e9a60a90",
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>name</th>\n",
" <th>Obese</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>a</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>b</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>c</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>d</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>4</th>\n",
" <td>e</td>\n",
" <td>0</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
" name Obese\n",
"0 a 0\n",
"1 b 1\n",
"2 c 0\n",
"3 d 1\n",
"4 e 0"
]
},
"execution_count": 243,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"new_data"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "29b65fc1-5390-44de-91bd-bf7f675cbacd",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.9.12"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment