{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "Clustering.ipynb",
"provenance": [],
"collapsed_sections": []
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
},
"language_info": {
"name": "python"
}
},
"cells": [
{
"cell_type": "markdown",
"source": [
"# Introduction \n",
"\n"
],
"metadata": {
"id": "PNmnb8Nf2G1a"
}
},
{
"cell_type": "markdown",
"source": [
"Clustering refers to a very broad set of techniques for finding *subgroups*, or *clusters*, in a data set. When we cluster the observations of a data set, we seek to partition them into distinct groups so that the observations within each group are quite similar to each other.\n",
"\n",
"For instance, suppose that we have a set of $n$ observations, each with $p$ features. The $n$ observations could correspond to tissue samples for patients with breast cancer, and the $p$ features could correspond to measurements collected for eah tissue sample, these could be clinical measurements, such as tumor stage or grade, or they could be gene expression measurements. \n",
"\n",
"We may have a reason to believe that there are a few different *unknown* subtype of breast cancer. \n",
"\n",
" Clustering could be used to find these subgroups. This is an unsupervised problem because we are trying to discover the structure - in this case, distinct clusters - on the basis of a data set. \n",
"\n",
"Both clustering and PCA seek to simplify the data via a small number of summaries, but their mechanisms are different.\n",
"\n",
"- PCA looks to find a low-dimensional representation of the observations that explain a good fracton of the variance. \n",
"\n",
"- Clustering looks to find homogeneous subgroups among the observations."
],
"metadata": {
"id": "bpWDKqsSfv-g"
}
},
{
"cell_type": "markdown",
"source": [
"#K-Means Algorithm\n",
"\n",
"\n",
"\n"
],
"metadata": {
"id": "8UpHPtXk2R1t"
}
},
{
"cell_type": "markdown",
"source": [
"1. Specify number of clusters $K$.\n",
"2. Initialize centtroids by first shuffling the dataset and then randomly selecting $K$ data points for the centroids without replacement.\n",
"3. Keep iterating until there is no change to the centroids i.e assignment of data points to clusters isn't changing\n",
" - Compute the sum of the square distance between data points and all centroids\n",
" - Assign each data point to the closest cluster(centroid).\n",
" - Compute the centroids for the clusters by taking the average of the all data points that belong to each cluster."
],
"metadata": {
"id": "2mVcCYXm4Yxi"
}
},
{
"cell_type": "markdown",
"source": [
"# Implementation"
],
"metadata": {
"id": "InfG7sMa3lO3"
}
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "7sNxr1R2079x",
"outputId": "1673d685-80f2-4207-966f-89977fdfa87f"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Mounted at /content/drive\n"
]
}
],
"source": [
"import random\n",
"from google.colab import drive\n",
"drive.mount('/content/drive')"
]
},
{
"cell_type": "code",
"source": [
"import pandas as pd\n",
"import numpy as np\n",
"import seaborn as sns\n",
"import random\n",
"import matplotlib.pyplot as plt\n",
"\n",
"\n",
"%cd /content/drive/My\\ Drive/colab_notebooks/machine_learning/data/\n",
"df = pd.read_csv(\"clustering.csv\")"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "8SbZHVxU1DDB",
"outputId": "0e2b49e1-94c8-4cf8-aa8c-0c1760bc7897"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"/content/drive/My Drive/colab_notebooks/machine_learning/data\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"df = df[['ApplicantIncome','LoanAmount']]\n",
"\n",
"y1 = df['ApplicantIncome']\n",
"n_bins = 20\n",
"plt.hist(y1, bins=n_bins,edgecolor = \"white\")\n",
"plt.show()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 265
},
"id": "a2tv1u591UEU",
"outputId": "55e359b6-673c-4c1c-e53f-c4916a08476b"
},
"execution_count": null,
"outputs": [
{
"output_type": "display_data",
"data": {
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
],
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAD4CAYAAADiry33AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAP2ElEQVR4nO3db4xldX3H8fenu4tr0bIg080WtLNGouGJQicUojEWqlIwwgNCMEa3FrNJWxutTXSpDxqTPsCm8V/aqBvRbhr/QFELgVRLV0zTJ6tDQQUWyoKgS4AdrKg1oQJ+++D+lo7rLnPn/tmZ+c37ldzcc37nnDvf3z13PnPu755zJ1WFJKlfv7bSBUiSpsugl6TOGfSS1DmDXpI6Z9BLUuc2Hs8fduqpp9bs7Ozx/JGStObddtttj1fVzKjbH9egn52dZX5+/nj+SEla85I8NM72Dt1IUucMeknqnEEvSZ0z6CWpcwa9JHXOoJekzhn0ktQ5g16SOmfQS1LnDHr9iiefemZFt5c0Wcf1KxC0NmzetIHZXTePvP2DV188wWokjcsjeknqnEEvSZ0z6CWpcwa9JHXOoJekzhn0ktQ5g16SOmfQS1LnDHpJ6pxBL0mdGyrok2xJcn2Se5LsT3JeklOS3JLkvnZ/8rSLlSQt37BH9B8DvlpVrwBeCewHdgF7q+oMYG+blyStMksGfZKTgNcC1wBU1c+r6gngEmBPW20PcOm0ipQkjW6YI/rtwALw2SS3J/l0khOBrVX1SFvnUWDrtIqUJI1umKDfCJwNfKKqzgJ+xhHDNFVVQB1t4yQ7k8wnmV9YWBi3XknSMg0T9AeBg1W1r81fzyD4H0uyDaDdHzraxlW1u6rmqmpuZmZmEjVLkpZhyaCvqkeBHyR5eWu6ALgbuBHY0dp2ADdMpUJJ0liG/Q9TfwZ8LskJwAPAOxj8kbguyZXAQ8Dl0ylRkjSOoYK+qu4A5o6y6ILJliNJmjSvjJWkzhn0ktQ5g16SOmfQS1LnDHpJ6pxBL0mdM+glqXMGfaeefOqZlS5B0iox7JWxWmM2b9rA7K6bR9r2wasvnnA1klaSR/SS1DmDXpI6Z9BLUucMeknqnEEvSZ0z6CWpcwa9JHXOoJekzhn0mrhxrsr1il5p8rwyVhPnVbnS6uIRvSR1zqCXpM4Z9JLUOYNekjo31IexSR4Efgo8AzxdVXNJTgGuBWaBB4HLq+pH0ylzfXryqWfYvGnDSpchaY1bzlk3v1dVjy+a3wXsraqrk+xq8++faHXrnGevSJqEcYZuLgH2tOk9wKXjlyNJmrRhg76Af01yW5KdrW1rVT3Sph8Ftk68OknS2IYdunlNVT2c5DeBW5Lcs3hhVVWSOtqG7Q/DToCXvOQlYxUrSVq+oY7oq+rhdn8I+ApwDvBYkm0A7f7QMbbdXVVzVTU3MzMzmaolSUNbMuiTnJjkhYengTcAdwI3AjvaajuAG6ZVpCRpdMMM3WwFvpLk8Pqfr6qvJvkWcF2SK4GHgMunV6YkaVRLBn1VPQC88ijtPwQumEZRkqTJ8cpYSeqcQS9JnTPoJalzBr0kdc6gl6TOGfSS1DmDXpI6Z9BLUucMeknqnEEvSZ0z6CWpcwa9JHXOoJekzhn0ktQ5g16SOmfQS1LnDHpJ6pxBL0mdM+glqXMGvSR1zqCXpM4Z9JLUOYNekjo3dNAn2ZDk9iQ3tfntSfYlOZDk2iQnTK9MSdKolnNE/25g/6L5DwEfqaqXAT8CrpxkYZKkyRgq6JOcDlwMfLrNBzgfuL6tsge4dBoFSpLGM+wR/UeB9wG/aPMvAp6oqqfb/EHgtKNtmGRnkvkk8wsLC2MVK0laviWDPsmbgENVddsoP6CqdlfVXFXNzczMjPIQkqQxbBxinVcDb05yEbAZ+A3gY8CWJBvbUf3pwMPTK1OSNKolj+ir6qqqOr2qZoErgK9X1VuBW4HL2mo7gBumVqUkaWTjnEf/fuC9SQ4wGLO/ZjIlSZImaZihm2dV1TeAb7TpB4BzJl+SJGmSvDJWkjpn0EtS5wx6SeqcQS9JnTPoJalzBr0kdc6gl6TOGfSS1DmDXpI6Z9BLUucMeknqnEEvSZ0z6CWpcwa9VpUnn3pmRbaVerasrymWpm3zpg3M7rp5pG0fvPriCVcj9cEjeknqnEEvSZ0z6CWpcwa9JHXOoJekzhn0ktQ5g16SOmfQS1Lnlgz6JJuTfDPJt5PcleSDrX17kn1JDiS5NskJ0y9XkrRcwxzR/y9wflW9EngVcGGSc4EPAR+pqpcBPwKunF6ZkqRRLRn0NfA/bXZTuxVwPnB9a98DXDqVCiVJYxlqjD7JhiR3AIeAW4D7gSeq6um2ykHgtGNsuzPJfJL5hYWFSdS8pvhFW8ePX4gmHd1QX2pWVc8Ar0qyBfgK8Iphf0BV7QZ2A8zNzdUoRa5lfknX8eNzLR3dss66qaongFuB84AtSQ7/oTgdeHjCtUmSJmCYs25m2pE8SZ4PvB7YzyDwL2ur7QBumFaRkqTRDTN0sw3Yk2QDgz8M11XVTUnuBr6Y5K+B24FrplinJGlESwZ9VX0HOOso7Q8A50yjKEnS5HhlrCR1zqCXpM4Z9JLUOYNekjpn0EtS5wx6SeqcQS9JnTPoJalzBr0kdc6gl6TOGfSS1DmDXpI6Z9BLUucMeknqnEEvSZ0z6CWpcwa9JHXOoJekzhn0ktQ5g16SOmfQS1LnDHpJ6pxBL0mdWzLok7w4ya1J7k5yV5J3t/ZTktyS5L52f/L0y5UkLdcwR/RPA39RVWcC5wJ/muRMYBewt6rOAPa2eUnSKrNk0FfVI1X1n236p8B+4DTgEmBPW20PcOm0ipQkjW5ZY/RJZoGzgH3A1qp6pC16FNh6jG12JplPMr+wsDBGqZKkUQwd9EleAHwJeE9V/WTxsqoqoI62XVXtrqq5qpqbmZkZq1hJ0vINFfRJNjEI+c9V1Zdb82NJtrXl24BD0ylRkjSOYc66CXANsL+qPrxo0Y3Ajja9A7hh8uVJksa1cYh1Xg28Dfhukjta218CVwPXJbkSeAi4fDolSpLGsWTQV9V/ADnG4gsmW44kadK8MlaSOmfQS1LnDHpJ6pxBL0mdM+glqXMGvSR1zqCXpM4Z9JLUOYNekjpn0EtS5wx6SeqcQS9JnTPoJalzBr00piefemZFt5eWMsz30Ut6Dps3bWB2180jb//g1RdPsBrpV3lEL0mdM+glqXMGvSR1zqCXpM4Z9JLUOYNewlMc1TdPr5QY7xRJT4/UaucRvSR1bsmgT/KZJIeS3Lmo7ZQktyS5r92fPN0yJUmjGuaI/h+AC49o2wXsraozgL1tXpK0Ci0Z9FX178B/H9F8CbCnTe8BLp1wXZKkCRl1jH5rVT3Sph8Fth5rxSQ7k8wnmV9YWBjxx0mSRjX2h7FVVUA9x/LdVTVXVXMzMzPj/jhJ0jKNGvSPJdkG0O4PTa4kSdIkjRr0NwI72vQO4IbJlCOtP+NcrOWFXhrGkhdMJfkC8Drg1CQHgb8CrgauS3Il8BBw+TSLlHrmxVqatiWDvqrecoxFF0y4FknSFHhlrCR1zqCXpM4Z9JLUOYNekjpn0EtS5wx6SeqcQS9JnTPopXXKK3LXD/+VoLROeUXu+uERvSR1zqCX1jCHUDQMh26kNczhFw3DI3pJ6pxBvwTfGkta6xy6WcI4b43Bt8eSVp5H9JLUuXUR9A6/SJM17u+Uv5PH17oYuvHMBGmyHNJcW9bFEb0krWdrJuh9qydpJa3l7wZaM0M3Dr9IWklrOYPWzBG9JGk0Br0kdW6soE9yYZJ7kxxIsmtSRUnSsazlsfKVMvIYfZINwN8DrwcOAt9KcmNV3T2p4iTpSOOOla/VcfZxjHNEfw5woKoeqKqfA18ELplMWZKkSUlVjbZhchlwYVW9s82/DfjdqnrXEevtBHa22ZcD9w7x8KcCj49UWB/s//rt/3ruO9j/Y/X/t6tqZtQHnfrplVW1G9i9nG2SzFfV3JRKWvXs//rt/3ruO9j/afV/nKGbh4EXL5o/vbVJklaRcYL+W8AZSbYnOQG4ArhxMmVJkiZl5KGbqno6ybuArwEbgM9U1V0TqmtZQz0dsv/r13ruO9j/qfR/5A9jJUlrg1fGSlLnDHpJ6tyqC/oev1YhyYuT3Jrk7iR3JXl3az8lyS1J7mv3J7f2JPl4ew6+k+TsRY+1o61/X5IdK9WnUSTZkOT2JDe1+e1J9rV+Xts+1CfJ89r8gbZ8dtFjXNXa703yxpXpyfIl2ZLk+iT3JNmf5Lz1sv+T/Hl73d+Z5AtJNve875N8JsmhJHcuapvYvk7yO0m+27b5eJIsWVRVrZobgw917wdeCpwAfBs4c6XrmkC/tgFnt+kXAv8FnAn8DbCrte8CPtSmLwL+BQhwLrCvtZ8CPNDuT27TJ690/5bxPLwX+DxwU5u/DriiTX8S+OM2/SfAJ9v0FcC1bfrM9pp4HrC9vVY2rHS/huz7HuCdbfoEYMt62P/AacD3gOcv2ud/2PO+B14LnA3cuahtYvsa+GZbN23bP1iyppV+Uo54gs4DvrZo/irgqpWuawr9vIHBdwTdC2xrbduAe9v0p4C3LFr/3rb8LcCnFrX/0nqr+cbgOou9wPnATe1F+jiw8ch9z+BMrvPa9Ma2Xo58PSxebzXfgJNa2OWI9u73fwv6H7TA2tj2/Rt73/fA7BFBP5F93Zbds6j9l9Y71m21Dd0cflEcdrC1daO9FT0L2AdsrapH2qJHga1t+ljPw1p+fj4KvA/4RZt/EfBEVT3d5hf35dl+tuU/buuv1f5vBxaAz7ahq08nOZF1sP+r6mHgb4HvA48w2Je3sX72/WGT2tentekj25/Tagv6riV5AfAl4D1V9ZPFy2rw57nLc12TvAk4VFW3rXQtK2Qjg7fyn6iqs4CfMXj7/qxe938bi76EwR+73wJOBC5c0aJW2Ers69UW9N1+rUKSTQxC/nNV9eXW/FiSbW35NuBQaz/W87BWn59XA29O8iCDbzk9H/gYsCXJ4Yv2Fvfl2X625ScBP2Tt9v8gcLCq9rX56xkE/3rY/78PfK+qFqrqKeDLDF4P62XfHzapff1wmz6y/TmttqDv8msV2qfi1wD7q+rDixbdCBz+NH0Hg7H7w+1vb5/Inwv8uL3t+xrwhiQntyOlN7S2Va2qrqqq06tqlsE+/XpVvRW4FbisrXZk/w8/L5e19au1X9HOzNgOnMHgg6lVraoeBX6Q5OWt6QLgbtbH/v8+cG6SX2+/B4f7vi72/SIT2ddt2U+SnNuez7cveqxjW+kPLY7yIcZFDM5KuR/4wErXM6E+vYbBW7XvAHe020UMxh73AvcB/wac0tYPg3/qcj/wXWBu0WP9EXCg3d6x0n0b4bl4Hf9/1s1LGfyyHgD+CXhea9/c5g+05S9dtP0H2vNyL0OcbbBabsCrgPn2GvhnBmdSrIv9D3wQuAe4E/hHBmfOdLvvgS8w+DziKQbv5q6c5L4G5tpzeT/wdxzxIf/Rbn4FgiR1brUN3UiSJsygl6TOGfSS1DmDXpI6Z9BLUucMeknqnEEvSZ37P14RVS/UxfdtAAAAAElFTkSuQmCC\n"
},
"metadata": {
"needs_background": "light"
}
}
]
},
{
"cell_type": "code",
"source": [
"y1 = df['LoanAmount']\n",
"n_bins = 20\n",
"plt.hist(y1, bins=n_bins,edgecolor = \"white\")\n",
"plt.show()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 265
},
"id": "F2vvGjzG1-f3",
"outputId": "2936cf51-9aff-4d5d-811e-a010f62db1a6"
},
"execution_count": null,
"outputs": [
{
"output_type": "display_data",
"data": {
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
],
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXAAAAD4CAYAAAD1jb0+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAO9UlEQVR4nO3dbYxcV33H8e+vaxMXaJuEBNeNo65bIlCKSoJWaSJ4QRMeAkEklSIUhKiruvIbUEOLRB2QKiH1hVErHipRWovQWFUKgQCNlaikqQmqKlWBNQ8hiUljgim2nHhpE6Ct3Nrm3xdzN13Wu57x7szOHPv7kUZ777n3av462v3t2XPvnE1VIUlqz8+MuwBJ0soY4JLUKANckhplgEtSowxwSWrUurV8s4suuqimp6fX8i0lqXn79u37QVVdvLh9TQN8enqa2dnZtXxLSWpeku8t1e4UiiQ1aqAReJKDwI+Bk8CJqppJciFwFzANHATeWlXPjKZMSdJiZzIC/82quqKqZrr9HcDeqroM2NvtS5LWyGqmUG4Ednfbu4GbVl+OJGlQgwZ4Af+QZF+S7V3bxqo60m0/BWxc6sIk25PMJpmdm5tbZbmSpHmDPoXy6qo6nOTFwANJvr3wYFVVkiVXxaqqXcAugJmZGVfOkqQhGWgEXlWHu69HgS8AVwFPJ9kE0H09OqoiJUmn6hvgSV6Q5Ofmt4HXA48Ae4Ct3WlbgXtGVaQk6VSDTKFsBL6QZP78v62qLyb5KvCZJNuA7wFvHV2ZkqTF+gZ4VT0JvGKJ9n8HrhtFUZJG79jxk2xYP7Xm12p41vSj9JImx4b1U0zvuG9F1x7cecOQq9FK+FF6SWqUAS5JjTLAJalRBrgkNcoAl6RGGeCS1CgDXJIaZYBLUqMMcElqlAEuSY0ywKUxO3b85FiuVftcC0UaM9ck0Uo5ApekRhngktQoA1ySGmWAS1KjDHBJapQBLkmNMsAlqVEGuCQ1ygCXpEYZ4JLUKANckhplgEtSowxwSWqUAS5JjTLAJalRBrgkNcoAl6RGGeCS1CgDXJIaZYBLUqMMcElq1MABnmQqydeT3Nvtb0nyUJIDSe5K8rzRlSlJWuxMRuC3AvsX7H8Q+HBVvQR4Btg2zMIkSac3UIAn2QzcAHyi2w9wLXB3d8pu4KZRFChJWtqgI/CPAO8FftLtvwh4tqpOdPuHgEuWujDJ9iSzSWbn5uZWVaykyXDs+MmxXq+edf1OSPJm4GhV7UvymjN9g6raBewCmJmZqTOuUNLE2bB+iukd9634+oM7bxhiNeeuvgEOvAp4S5I3ARuAnwc+CpyfZF03Ct8MHB5dmZKkxfpOoVTVbVW1uaqmgVuAL1XV24EHgZu707YC94ysSknSKVbzHPgfAX+Y5AC9OfHbh1OSJC1vNfPnZ9vc+yBTKM+pqi8DX+62nwSuGn5JkrS81cy/n21z734SU5IaZYBLUqMMcElqlAEuSY0ywCWpUQa4JDXKAJe05s6257HH5YyeA5ekYfBZ7uFwBC5JjTLAJalRBrgkNcoAl6RGGeCS1CgDXJIaZYBLUqMMcElqlAEuSY0ywCWpUQa4JDXKAJekRhngktQoA1ySGmWAS1KjDHBJapQBLkmNMsAlqVEGuCQ1ygCXpEYZ4JLUKANckhplgEtSowxwSWqUAS5Jjeob4Ek2JPlKkm8meTTJB7r2LUkeSnIgyV1Jnjf6ciVJ8wYZgf8PcG1VvQK4Arg+ydXAB4EPV9VLgGeAbaMrU5K0WN8Ar57/7HbXd68CrgXu7tp3AzeNpEJJ0pIGmgNPMpXkG8BR4AHgO8CzVXWiO+UQcMky125PMptkdm5ubhg1S5IYMMCr6mRVXQFsBq4CXjboG1TVrqqaqaqZiy++eIVlSpIWO6OnUKrqWeBB4Brg/CTrukObgcNDrk2SdBqDPIVycZLzu+2fBV4H7KcX5Dd3p20F7hlVkZKkU63rfwqbgN1JpugF/meq6t4kjwGfTvInwNeB20dYpyRpkb4BXlUPA1cu0f4kvflwSdIY+ElMSWqUAS5JjTLAJalRBrgkNcoAl6RGGeCS1CgDXJIaZYBLUqMMcElqlAEuSY0ywCWpUQa4pHPGseMnx3LtqAyyGqEknRU2rJ9iesd9K7r24M4bhlzN6jkCl6RGGeCS1CgDXJIaZYBLUqMMcElqlAEuSY0ywCWpUQa4JDXKAJekRhngktQoA1ySGmWASw2bxAWWtHZczEpq2Nm2OJPOjCNwSWqUAS5JjTLAJalRBrgkNcoAl6RGGeCS1CgDXJIa1TfAk1ya5MEkjyV5NMmtXfuFSR5I8kT39YLRlytJmjfICPwE8J6quhy4GnhnksuBHcDeqroM2NvtS5LWSN8Ar6ojVfW1bvvHwH7gEuBGYHd32m7gplEVKUk61RnNgSeZBq4EHgI2VtWR7tBTwMZlrtmeZDbJ7Nzc3CpK1blgNWt7uC6IzjUDr4WS5IXA54B3V9WPkjx3rKoqSS11XVXtAnYBzMzMLHmONM+1PaTBDTQCT7KeXnjfWVWf75qfTrKpO74JODqaEiVJSxnkKZQAtwP7q+pDCw7tAbZ221uBe4ZfniRpOYNMobwKeAfwrSTf6NreB+wEPpNkG/A94K2jKVGStJS+AV5V/wxkmcPXDbccSZpMx46fZMP6qTW/9nT8hw6SNIBJvMHuR+klqVEGuCQ1ygCXpEYZ4JLUKANckhplgEtSowxwCRfRUpt8DlxiMp/xlfpxBC5JjTLAJalRBri0Ss6Ba1ycA5dWaTXz5+AculbOEbgkNcoAl6RGGeCS1CgDXJIaZYBLUqMMcElqlAEuSY0ywCWpUQa4JDXKAJekRhngktQoA1ySGmWAS1KjDHBJapQBLkmNMsAlqVEGuCQ1ygCXpEYZ4JLUKANckhrVN8CTfDLJ0SSPLGi7MMkDSZ7ovl4w2jIlSYsNMgK/A7h+UdsOYG9VXQbs7fYlSWuob4BX1T8B/7Go+UZgd7e9G7hpyHVJkvpY6Rz4xqo60m0/BWwcUj2SpAGt+iZmVRVQyx1Psj3JbJLZubm51b6dtKxjx0+OuwRpTa1b4XVPJ9lUVUeSbAKOLndiVe0CdgHMzMwsG/TSam1YP8X0jvtWdO3BnTcMuRpp9FY6At8DbO22twL3DKccSdKgBnmM8FPAvwAvTXIoyTZgJ/C6JE8Ar+32JUlrqO8USlW9bZlD1w25Fg3RseMn2bB+as2vHcb1kgaz0jlwTbhxzgc7Fy2tDT9KL0mNMsAlqVEGuE7h89RSG5wD1ylWM4cNzmNLa8URuCQ1ygCXpEYZ4JLUKANckhplgEtSowxwSWqUAS5JjTLAJalRBrgkNcoAl6RGGeCS1CgDvI/VLuzkwlCSRsXFrPpwYSdJk8oRuCQ1ygCXpEYZ4BPM+XNJp+Mc+ATznwNLOh1H4JLUKANckhplgEtSowxwSWqUAS5JjTLAJalRBviI+Sy3pFHxOfAR81luSaPiCFySGmWAS1KjDHBJalQzAb6am4HeSJR0NlrVTcwk1wMfBaaAT1TVzqFUtYTV3gz0RqKks82KR+BJpoCPAW8ELgfeluTyYRUmSTq91UyhXAUcqKonq+p/gU8DNw6nLElSP6mqlV2Y3AxcX1W/1+2/A/iNqnrXovO2A9u73ZcCj6+83JG6CPjBuIsYkLWOhrWOTkv1TmKtv1xVFy9uHPkHeapqF7Br1O+zWklmq2pm3HUMwlpHw1pHp6V6W6p1NVMoh4FLF+xv7tokSWtgNQH+VeCyJFuSPA+4BdgznLIkSf2seAqlqk4keRdwP73HCD9ZVY8OrbK1N/HTPAtY62hY6+i0VG8zta74JqYkabya+SSmJOmnGeCS1KhzLsCTXJrkwSSPJXk0ya1d+4VJHkjyRPf1gnHXOi/JVJKvJ7m329+S5KEkB5Lc1d1EnghJzk9yd5JvJ9mf5JpJ7dskf9B9DzyS5FNJNkxK3yb5ZJKjSR5Z0LZkP6bnz7uaH07yygmo9U+774GHk3whyfkLjt3W1fp4kjesZa3L1bvg2HuSVJKLuv2x9m0/51yAAyeA91TV5cDVwDu7JQB2AHur6jJgb7c/KW4F9i/Y/yDw4ap6CfAMsG0sVS3to8AXq+plwCvo1T1xfZvkEuD3gZmqejm9G/G3MDl9ewdw/aK25frxjcBl3Ws78PE1qnHeHZxa6wPAy6vq14F/BW4D6H7WbgF+rbvmL7plOdbSHZxaL0kuBV4P/NuC5nH37elV1Tn9Au4BXkfvE6KburZNwOPjrq2rZTO9H9ZrgXuB0PuU2Lru+DXA/eOus6vlF4Dv0t0cX9A+cX0LXAJ8H7iQ3tNY9wJvmKS+BaaBR/r1I/BXwNuWOm9ctS469lvAnd32bcBtC47dD1wz7r7t2u6mN+g4CFw0KX17ute5OAJ/TpJp4ErgIWBjVR3pDj0FbBxTWYt9BHgv8JNu/0XAs1V1ots/RC+MJsEWYA74627K5xNJXsAE9m1VHQb+jN5o6wjwQ2Afk9u3sHw/zv8ymjdpdf8u8Pfd9kTWmuRG4HBVfXPRoYmsd945G+BJXgh8Dnh3Vf1o4bHq/aod+/OVSd4MHK2qfeOuZUDrgFcCH6+qK4H/YtF0yQT17QX0Fl/bAvwS8AKW+LN6Uk1KP/aT5P30pi3vHHcty0nyfOB9wB+Pu5YzdU4GeJL19ML7zqr6fNf8dJJN3fFNwNFx1bfAq4C3JDlIb7XHa+nNMZ+fZP5DWJO0hMEh4FBVPdTt300v0Cexb18LfLeq5qrqOPB5ev09qX0Ly/fjRC5rkeR3gDcDb+9+4cBk1vqr9H6Rf7P7WdsMfC3JLzKZ9T7nnAvwJAFuB/ZX1YcWHNoDbO22t9KbGx+rqrqtqjZX1TS9Gz9fqqq3Aw8CN3enTUStAFX1FPD9JC/tmq4DHmMC+5be1MnVSZ7ffU/M1zqRfdtZrh/3AL/dPTFxNfDDBVMtY5HeP3t5L/CWqvrvBYf2ALckOS/JFno3B78yjhrnVdW3qurFVTXd/awdAl7ZfT9PXN/+lHFPwq/1C3g1vT89Hwa+0b3eRG9ueS/wBPCPwIXjrnVR3a8B7u22f4XeN/0B4LPAeeOub0GdVwCzXf/+HXDBpPYt8AHg28AjwN8A501K3wKfojc3f5xeoGxbrh/p3dj+GPAd4Fv0nqwZd60H6M0dz/+M/eWC89/f1fo48MZJ6NtFxw/y/zcxx9q3/V5+lF6SGnXOTaFI0tnCAJekRhngktQoA1ySGmWAS1KjDHBJapQBLkmN+j8n4/oUC5D7FAAAAABJRU5ErkJggg==\n"
},
"metadata": {
"needs_background": "light"
}
}
]
},
{
"cell_type": "code",
"source": [
"def KMeanClustering(arr,K,eps):\n",
"\n",
" # No of clusters are equivalent to \n",
" # Initialize random Centroids \n",
" \n",
" n = len(arr)\n",
" random_centroids = random.sample(range(1, n), K)\n",
" centroid_val = arr[random_centroids,:]\n",
" centroids_lst=[]\n",
" centroids_lst.append(centroid_val)\n",
" clusters_lst = []\n",
" diff = 9999\n",
" j = 0\n",
" while diff > eps:\n",
" \n",
" ###########################################################\n",
" # 1. Code to calculate the Eucledian distance between the centroids \n",
" # and all the other observations.\n",
" # 2. Assigning observations to centroids with least distance.\n",
" ###########################################################\n",
"\n",
" euclidean_centroid_dist = np.sqrt(np.sum(np.square(arr[:,np.newaxis,:] - centroid_val),axis=2))\n",
" assigned_cluster = np.argmin(euclidean_centroid_dist,axis=1).reshape(n,1)\n",
" clusters_lst.append(assigned_cluster)\n",
" ###########################################################\n",
" # 3. Code segment to calculate the new centroids, based on\n",
" # on the assignment in the previous \"assigned cluster\"\n",
" # ASSIGNMENT.\n",
" ###########################################################\n",
"\n",
" centroid_val_old = centroid_val\n",
" centroid_val = np.zeros([K,arr.shape[1]])\n",
"\n",
" for i in range(0,K):\n",
"\n",
" cluster = np.where(assigned_cluster==i)[0]\n",
" cluster_arr = arr[cluster,:]\n",
" centroid_val[i,:] = np.mean(cluster_arr,axis=0)\n",
" \n",
" \n",
" ###########################################################\n",
" # 4. Code segment for the exit condition of the while loop\n",
" # - Calculate the difference between new and the previous \n",
" # centroid, if the difference is below the given eps,\n",
" # end the while and return the clusters and the \n",
" # cluster centroids.\n",
" # - and if not, keep executing the while loop\n",
" ###########################################################\n",
"\n",
" diff = (1/n)*np.sum(np.square(centroid_val_old - centroid_val))\n",
" j+=1\n",
" \n",
" return assigned_cluster,centroid_val,clusters_lst,centroids_lst,j\n"
],
"metadata": {
"id": "yybuH8I_2GIh"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"arr = np.array(df)\n",
"K = 3\n",
"eps = 1e-5\n",
"\n",
"clusters,centroids,clusters_lst,centroids_lst,iter = KMeanClustering(arr,K,eps)\n"
],
"metadata": {
"id": "z3f9Ld8m4GBL"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"print(arr.shape)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "Mn7XdrC8odWQ",
"outputId": "2bfe995c-8d23-46b9-f7e6-e3f22cdea938"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"(381, 2)\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"index0 = np.argwhere(clusters == 0).ravel()\n",
"print(len(index0))\n",
"cluster0 = arr[index0,:]\n",
"print(cluster0.shape)\n",
"index1 = np.argwhere(clusters == 1).ravel()\n",
"cluster1 = arr[index1,:]\n",
"\n",
"index2 = np.argwhere(clusters == 2).ravel()\n",
"cluster2 = arr[index2,:]"
],
"metadata": {
"id": "_91yH86BoELU",
"colab": {
"base_uri": "https://localhost:8080/"
},
"outputId": "0f4d0eef-2652-4287-f7ca-cec871d844a9"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"86\n",
"(86, 2)\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"plt.scatter(cluster0[:,0],cluster0[:,1],color='red',alpha=0.5,label='Cluster-1')\n",
"plt.scatter(cluster1[:,0],cluster1[:,1],color='green',alpha=0.5,label='Cluster-2')\n",
"plt.scatter(cluster2[:,0],cluster2[:,1],color='blue',alpha=0.5,label='Cluster-3')\n",
"plt.title(\"Outcome of K-Mean clustering algorithm\")\n",
"plt.legend()\n",
"plt.grid()\n",
"plt.show()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 281
},
"id": "BG6w6yMBgFCS",
"outputId": "aca316d8-749f-41b6-ec91-bb81ff28733d"
},
"execution_count": null,
"outputs": [
{
"output_type": "display_data",
"data": {
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
],
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAEICAYAAAC55kg0AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nOy9eXQc133n+7m9N5YGQBAbAe67CEOkTIuUJiIhR4lkW5ZsHh2/ZCaJFCnxi23Gz3nRyI5sJXgj2+OZ4ZloPIrkyRsrtmyPFUdDS7JfbNmWAtGxRG0UBYEiSIoiCRILAZC9YOlu9HLfH7+u7upGN9AAARIg6ntOn+6qunXr3qqu+7v3+9uU1hoLFixYsLA4YbvSDbBgwYIFC1cOlhCwYMGChUUMSwhYsGDBwiKGJQQsWLBgYRHDEgIWLFiwsIhhCQELFixYWMSwhICFWYFS6pNKqbNKqRGl1LYr3Z7LBaWUVkqtmwfteFAp9T+vwHXblFLfn6O6b1JKHZvk+KrU/XfMxfUXCywhMAtQSt2jlHpHKTWmlOpXSj2ulKqcxvmnlVK3zGUbLwP2AXu11mVa67dyD+YOlkqp+5VSfUqpLTnljBf7rZz9S5VS40qp03PVgSsFpdR3lFJfvZQ6tNZf11r/yWy1aT5Aa/1rrfVGY/sqeU/mHSwhcIlQSv0l8J+Afw9UADuBlcAvlVKuK9m2y4yVwJFiCiqlvgJ8AdittS50TolSqtm0/W+BU5fWxKsTV+NM+Grs07yF1tr6zPAD+IAR4FM5+8uAQeDe1PZ3gK+ajrcC51K/vwckgXCqrgdS+38LeBkIAGeBe1L7K4AnU/WfAb4C2FLH7gF+A/xt6rz3gRtT+88CA8Ddpna4kRl8N3Ae+BbgLdBXW+paZ1L1PJlqizvVbg2MAicLnK+BdcBXgdPAmgLlVqXKfgX4L6b9bwBfBk6b9i0D/nfqXpwCPm86dj3wSuo+9AGPAq6c9vwZcCJV5u8AVaBNduBB4CQwDLwJLDf3K/W7HfgT03n3AP+a+q1Sz2UACAHvAM3Ap4EYMJ66jz8pom9twNPA91N1/Ulq3/dz7uHdqWc7BHzZdL4X+C7gB44CD5D6Pxbo/39L/X9Cqb7flNOW75u2/yj1H7kAPJR61reY/m+PAL2pzyOA2/xOAF8E+pH3opVJ3pMi+tkG/FPqPg2n7vkG4K9Sz+Es8LtXehy50p8r3oCF/AFuA+KAI8+x7wI/TP3+DgWEQGo7/aKktlem/rS/DziBamBr6tiTwLNAeeolOA7clzp2T6o9f4wMXF9NvRx/l3oBfzdVb1mq/N8CzwFLUvX9BPiPBfp6L/AesAYRcvuB75mOpwfDAudrZOA6AayYpJzxYq9KvaR24BqgC7iFlBBAhNKbwF8DrlS73gduTR3/ILIqc6TqOgp8Iac9PwUqgRXIYHtbgTb9+9QAshEZzK8FqnP7zeRC4NZUeytTdWwGGgr8P6bqWxsiOD6RKuslvxD4f1PHrgWiwObU8W8ALwFVQBPQweRC4A+Q/6AD+EtkkPaY2mJc9xpkgP6tVLv3pdppCIH/ABwEaoEaZJLzsOmdiCOraneq3a1M/p5M1c82IJK69w7k3TmFTCacwJ8Cp670OHKlP1e8AQv5k3o5+gsc+wbwy9Tv3Jd8qj/3XwE/zlOnHZkxXmPa938C7anf9wAnTMc+kHpJ6kz7LgBbkYFoFFhrOnZDoZcCeAH4rGl7Y+oFd6S2ixECIeC/T3FPjRfbAfwq9QJ/I/XimoXADqA759y/Av6hQL1fMN/T1DV+y7T9I+BLBc49Btw5Sb+KEQIfRgT2TlIrN1O53P/HpH1LDW4Hco63MVEINJmOvwb8Xup3WqCktv+ESYRAnj77gWvzXPevSU18Utslqf+rIQROAh81Hb/V9DxbU2U903hPpupnG6l3MLX9cURI2VPb5anzK4vt+9X4sXi3S8MQsFQp5dBax3OONaSOzwTLkRcmF0uRGcwZ074zQKNp+7zpdxhAa527rwyZiZUAbyqljGMKETT5sCzPdR1AHdBTuCtZ+D3g20qpi1rrvwFQSo2Yjl+TU/5JZCC9EbgJWcobWAksU0oFTPvswK9T9W4A/iuwHemnA5ldm9Fv+j2G3Jd8KPQ8iobW+kWl1KPIqmylUmo/cL/WOpSn+KR9S+FsEZct1L9lOedPWpdS6n7gvtR5GqFBl+YpmlWv1npMKXUh53juf2iZaXtQax2ZrC0FMNlzzP3vD2mtE6ZtUuXN93pRwVIMXxpeQZafe8w7lVJlwEeQ2TPIjLvEVKQ+px6ds30WWJvnekPI7Hulad8Kih+Ec+sKA1u01pWpT4XWutBA2JvnunGyX7KpcByZzX9WKfUlAC3WRManO6f8/wY+Bryf59hZZNVSafqUa60/mjr+OEIhrdda+xBOXzEzFHoeuZj0OWutv6m1/iAi7DYgNBPkf/6T9S3fOdNBH0IDGVheqKBS6iaEf/8UUKW1rgSC5L+XWfUqpbwIjWQg33+o17Q9VZ8upc8WCsASApcArXUQ+H+A/66Uuk0p5VRKrUKohXOIMgvgMPBRpdQSpVQ9Qk2YcR7hfQ38ALhFKfUppZRDKVWtlNqamsH8CPiaUqpcKbUS+L8Rxdd0255EuNS/VUrVAiilGpVStxY45YfAXyilVqeE3NeBf8yzAprqukcQQfDvlVK59yG37ChCo+QzfXwNGFZKfVEp5VVK2ZVSzUqpD6WOlyP004hSahPwmem0Mwf/E3hYKbVeCVqUUtV5yh0G9iilSlLmsPcZB5RSH1JK7VBKORFhEUEUnTDx+U/Vt0vFj4C/UkpVKaUagb2TlC1HhP0g4FBK/TWyEsiHp4GPK6VuTFnGtZEtLH4IfEUpVaOUWorQR9P57+beJwuzAEsIXCK01v8ZmWXuQwadV5GZ3G9rraOpYt8D3kY4zV8A/5hTzX9EXo6AUur+1Kz3o4gS7iIyuFybKvvnyCDyPvCvwP8Cnphh87+IKHsPKqVCCAe/sUDZJ1L9OIAo1yKptkwbWuu3ET74b5RSfzZF2Te01hOomJRAvB3Rb5xCVjb/E7FYArgfMSsdRoRd7j2fDv4rMnD+AnnG30YUkbn4W4TXPo8YBvzAdMyXaoefjPXMf0kd+zZwTer5P1NE3y4V/wGZpJxCnvnTyIo2H54Hfo6s4s4gzz0vfZQS8H8OPIWsCkYQKxyj7q8iVl4diKL9UGpfsch6T6ZxnoVJoFIKEgsWLCxSKKU+gyhTd89yvQbXvl5rfWo267Ywe7BWAhYsLDIopRqUUv9GKWVTSm1EVpw/nqW6P56iw0qR1fE7yArYwjyFJQQsWFh8cAH/A6HKXkT8Th6bpbrvJOMMth5ZYVh0wzyGRQdZsGDBwiKGtRKwYMGChUWMeeEstnTpUr1q1aqiyo6OjlJaWjq3DZqnWMx9B6v/Vv8Xb/8L9f3NN98c0lrXXErd80IIrFq1ijfeeKOosu3t7bS2ts5tg+YpFnPfweq/1f/F2/9CfVdKnZlYenqw6CALFixYWMSwhIAFCxYsLGJYQsCCBQsWFjEsIWDBggULixiWELBgwYKFRYx5YR1k4fKiowP274fublixAvbsgZaWWaq7v4P9XfvpDnazomIFzTXNdA52prf3bNpDS/0sXWwWkNve+da+GWMuH/JChnVfJsBaCSwydHTAvn3g90NTk3zv2yf7L7nu/g72vbIPf9hPk6+J40PHeeBXD3DiwgmafE34w372vbKPjv5ZuNgsILe98619M8ZcPuSFDOu+5IW1Elhk2L8fqqrkA5nv/fsvfUK0v2s/VZ4qqrxSae9ILz6Xj57hHtZXr0/v39+1v6jZdu4sfUd8x6U1cIr2Trd98xZz+ZAXMqz7kheWEFhk6O6WSZAZFRWy/1LQ0d/BM13PAFDpqWTT0k0EI0F8bh/BSDBzLU8F3cGpL2bM0qs8VelZ+vnoeTr6O2ZtgO4OduO0OWk/3U4wEqTCU8HG6o1FtW9eY64e8kKHdV/ywqKDFhlWrIBgMHtfMCj7ZwpjwHbb3bhsLsKxMK+cewW7zU4oGqLCk8mFEowEWVEx9cXMs3SbslHlrcJus7O/a//MG5oDl93FgTMHCMfC+Nw+wrEwB84cwGV3zdo1rgjm4iFfDbDuS15YQmCRYc8eoUL9fkgmM7/37Jn63EIwBuzrGq4jmpAkUm67m0gsQmg8RGN5I0mdxB/244/42bNp6ot1B7uzhAeAXdlndZauCqQcLrR/wWAuHvLVAOu+5IUlBBYZWlrg/vuFDj13Tr7vTyXqa2uDe++V7+noyowBu66sjhuX34jX6WU8Po7T7uQ/3/KfWV+9nnOhc1R5q7j/hvuLonNWVKzIopEAEjpR1CqiWEQTUXat3IXX6SUUDeF1etm1cldakC1YFHrIi5j3Bqz7UgCWTmCRYDLLOMNooqoq22ii2PdjRcUK/GE/Vd4q6srqqCurS2/fteUu7uKuabd3z6Y97HtlHyB6hGAkSCKZKGoVUSyMdreuak3v84f9NHgbZu0aVwwtLYt+cMsL675MgLUSWASYyjLObDRhs2V+7y+Sft+zaQ/+iB9/2D9t2qcQWupbuP+G+6nyVqVXEXVldbNqtTMX7bZgYaHBWgksAkxlGTeZ0UQxvjXGgG2Yc7rtbkqcJTzy6iMFHbCKcdJqqW+hpb4lXXZgdIC29rZZc+jKbfeKihXct+2+y28eatzkw4chEIDKSti61XJksnBZYAmBqxjG2PKDH8CyZXDNNVBXJ8fMlnErVsjqwBAOIEYTbnfxNJF5wDZMO2tLa9MOWGZdQD7zz9wy6T6Yym6wbZi07ExgtHvWUaxnqrFMSyTg/fdlKXbxIpSUTI+Ts2BhhrDooKsUZgpo2TIZ1F9+Gc6fl+Nmy7hCRhNaT58mymfaWeWpyjLtnKpMR38Hbe1t3PvsvXz+558nnohT5a1CKZW3vnmH6XimGsu0nh7wemUV4PVCb+/0ODkLFmYISwhcpTBTQJs3y4CuFLz77kTLuEJGE+PjsmIwYyrfmnymnbkOYpOVyQ3lMDA6QOdgJ/0j/QXrm3eYjpKlu1tuajAIHo/s83hk23JksnAZYNFBVynMPH99PdxwAxw9KhPMm2+G++7LZhnyGU0Uookm860xWwqlz8lxEJusTG4oh9rSWgLhAF1DXexeujtvffMO0/FMNW5yRQWEw7IKiEQygmHFigy1tHq12O/Ola7ACq62KDHlSkAp9YRSakAp1Znn2F8qpbRSamlqWymlvqmUek8p1aGUum4uGm1hauQ6RyolY8t08nRP5lvT0ZHfr6AYi5vJyuSuEjYv3cxobJQjA0fwh/387MTPOOk/OWMLHjPV1NbeNjfB4qbjmWrc5MZGEQKBgHwvWyb7m5vhwQfhZz+D0VH5fvDB2Q96ZgVXW7Qohg76DnBb7k6l1HLgdwHz9OYjwPrU59PA45feRAszgXkA7+uD9nYIhWDHjuLf78kcywqNF/lMO3OVuJOVyeckFk/Gs0I5zNSj97JFDZ2OZ6pxk9evhzVrRCewZg1s2CD7f/UrOHlSytrt8n3yJDz22Oy2+VLthC0sWExJB2mtDyilVuU59LfAA8Czpn13Ak9qrTVwUClVqZRq0Fr3zUZjLRQPY2zZvx+efRZ8Pti2TaghA1MFT8zHDgB8/vMwMAC1tbBpU6ZOo75iLG4Klcl1EjvUdwiPw8Ot626liio+UvMR/GH/jCJ9Xraooeabb9y8XP4tt3yhYwcPQnm50ERKybfWsn82YQVXW7RQMl5PUUiEwE+11s2p7TuBD2ut/y+l1Glgu9Z6SCn1U+AbWut/TZV7Afii1vqNPHV+GlktUFdX98GnnnqqqAaPjIxQVlZWVNmrDTPt+5kz4HTKGGJAa4jFYOXK/OeEw2JJZLfLJ5GAaCqaQjQKDofUkUyKHjMWk091dcbAJRwPE4gEGE+M47K7qPRU4nV4p2yv+bzR8VHKXGU47U5cCRcX4heIJ+MArK5aXVR96fsQPIPT5kSZbkQsEWN0fJQSV8m02jgnMOig8XFwueRGnj4tD85mY2TJEsouXpSbrrVo/GcLfX0Qj8uDNWBsN+R4UOdrp3fu75n17k/s+8033/ym1nr7pdQ9bcWwUqoEeBChgmYMrfXfA38PsH37dt3a2lrUee3t7RRb9mqDue/T0eF95jNw6FDG2mfzZnl3q6rg7rvzn9PWNlEp/LOfybfXK+NAIiECZnhY6m1qgt/6LTnvjnuO89zwV6nyVFFRKmEf/MP+adv3t7W3cSx8jGgiSst4C98NfBetNUopNjo2Tqu+tva2LIX0+ZHztJ9tx+f2ceu6W2fcxlmBOXaHoRT2+0WR88474PPRfu+9tD7xhPB6ra3yYGdynXx/nELXz/VTKLbcHMB691vnpO6ZmIiuBVYDb6dWAU3AIaVUPdADLDeVbUrtszCLmI4Or6MDzp6VccPphLEx0Q+8//7kwRMNy0UzolH5bN4s1zx9WsYoEIEwPCyCpqoKHn2yZ0p/gWJgKJHf6nsLm5K/azQR5bqG66ZdX65C+lDfIQC2NWy7pDbOCgpx8kuWwLp1UiaRkO9162YuAAoqc4oMrmbpDq46THsloLV+B6g1tnPooOeAvUqpp4AdQNDSB8w+JgsDAfD440IZay2r+Y0bYfdu6OqSiZvPJ8Yok03c8pmHut1ioHL0qDi1RqMiBEpKYNUqoY2OHoVdu6Cn08GuKfwFioGhRL77mbtJ6iRep5frGq6jrqyOpE5m1dfR38FjbzzGwXMHUSh2Nu3kM9s/k57V54aJMKKI1pdlFCWX5INwKSaWhTj5c+fga1+TektL4SMfmbnp5lTxQ4oJrmbpDq46TCkElFI/BFqBpUqpc8DfaK2/XaD4PwMfBd4DxoA/nqV2TsBiNmku9B4ePgxvvgnvvSe6RIBjx2Tgv+UWYRBAKOVz5ya/xp49Mkk06g4GhULq6RHBYrfL4B+LQU0N4Bqhf3SI4QHFhcPvMep9j++9/T00GoVKf6+sXDkhO9hUcYRa6lu4c9OdlIfKaa1pTe83+wt09Hfw4IsPcvLiScrd5aCh/XQ750Ln+NqHv5YlCIzwFp//+ef5dfevqS2tZdPSTdSX1c/cB+GSQ7FO4pRhDM7t7YX5u2IwGwP4TJxHLMxrTEkHaa1/X2vdoLV2aq2bcgWA1nqV1noo9VtrrT+ntV6rtf5APoXwbGCxmzQXMkMPBMRqx+eTAbqkBMrKhKY5ejS77FTvbD52oLlZVhSVlaKrdDhS9z8Y4/RgP5Ew2J0JuvuHiW38EUOjQwTCAXpDvQTCAQKRAF67N8sss1izzT2b9pBIJgr6H+zv2s/g6CA+t48SZwklrhJ8bh8DowMT6B3jmo3ljTiUg0A4wMtnX+b40PGZRxG95FCslyHhyWxk1rISs1x1WJAew4s1X3Q4LArbw4fh1CnYskXoYUM3V1kpgsDM5dfXS9mBAXlnjbL33Tf19XLZgXvvhbVrxaS9thZeeinl2xSL4o15icU8eDb8mrpdP8Jf0YWKexlPjmOz2UBBk6+JcCKc5t1b6lsmNds0vo0VwrWea6nyVOWN+GnQOxXuTOc9Dg/BSHACvfP4G49zbOiYWC05xP9gLDZG70gv37ztmzNTCl/qLHu6ZqUzQb7lXbF/hsvZTguXFQtSCCxGWrKjQ0w2/X5530pLobNTFL1bt8p7uH+/WPpFIhmLPYdD+P/qapnRX8o7azAB4+NCM9XWim5geDyBw25j1z2/5L36/4TP7WNwKI7NZsNj81DhriCaiLLEuySd0N0YmLuD3TT5sh9mhaeCw32Hed//flak0WA0yJ6t+cNIu+wuBkcH6Qn1UOoqZWnJUuzKjtvhzqJ3nj7yNE8deQqHclDqLKXMVYbdZuemFTcRS8ayQldPFua64M25FJokV+oabtnGYLtjx8RzpsOLztYAbiVmuaqwIIXAYqQl9++XWbjR5/XrYelS2W5ry5T7l3+BI0fkt9stPP6WLfD1rxf/3hYaV4yJ5LFjUrdhJlpWMY5yRDh1aA0VeyoIx8I47A7Q4LQ7icQieJweIvEIdmXn+feeZzwxTlt7Gy67i2AkOCGOUCAaYGXlyqwVgj1mz+vY1dHfQU+oB5fNRTQRJRwLc8p/Cp/bR3Ntc5re6ejv4OFfP4zL5sKu7MR0jKHwEEu9Szncf5iPrP9I3jDXD774IMt9y4kmollCIUtYbHaz55dnaWHtzGbZuTe9uRmeey5bx3D+fMaSxzhnunoIawC3kIMFGUV0MdKS3d2ZqAEG8q1+ysvFt8fhkBm70wn33DM9ATCVFWE0KmPcwIAIolVNXuKJBCdeX83S0M2EoiFcNhclzhJJOB+P4La7uRi+yIXwBULRENc3Xo8/7Kcn1MNJ/8kJXH+lu7LoRPP7u/azpmoNt62/jVUVq1BKYVM2qkuqs5TC+7v2E0vEaPI1kSABWur0R/xcCF9gz6Y9E8JcRxNRTl48yaG+Q1k6i6ePPJ2ty/C52HejoqMqOv38tflu+sMPi7OWWcdgt2frGCxzTQuzgAW5ErgaacnJfHj274e33oLrr4f+/kyYhtzVj7Fa2G7yH/T7hTa6q8g0v7n6FoP6+aM/gk98Qtr1iU+I41jGUbSMBl8DF50Xee/la2n9g340mv7hfgLRAMvKl6W3l5QuSZt4AvjGfBy7cIxzoXNps07DjDM30mihRPMGpWRTNm7feDsASZ3kXOhc1qqhO9hNTUkNkXiE5b7lDI0NEY6FSeokH9/4cVrqW3jk1Uey6KmuoS7K3eWMJ8bTvgQAj77+KNfWXZuty2hYw/41VbS0thV3swvd9KoqMbvq6ZEYQgbs9mypvxh5UQuzjgUpBODqWtUWWtXfcUeGEbj+eqFeXnpJ7PA9nolsQ+6YcP685A/o7ZXtYsxozXWcPy+JaNxu2Ta36/vfFz8mrUUHYUuUcvuuUs4HS6krO0x3sJutDVtprmmmc7CT7mA3wUiQrfVb0wLg/Mh53jn/DnEd565r7hKP3Yhf2jqNRPNGaOpoIkrXUBfBSBCX3cW2hm0TykXjUToHOvE4PKysWEkwEmQsPoZCce+z9/K+/30isQg+j4+uoS7eOf8OHoeHhrJM6IQKTwU9wz3sWrkrq/60rmM6WcUKpX6rqYHBwezyiUS21J9NXnSx2lwv1n6bsCDpoKsNhVb1jz6a+d3QIFSPzwevvpqfbTBbABoDeDCYiUpcjBmtuY6jR0XYKCWzfqMtnZ3wO78j+0MhWQ3ceCOMJAc5pdvTFMnxoeM88KsHOHHhBE2+Jlx2FwfOHOD8iKQ3Ozp0FJuyUVtaO8FjdzqJ5vds2sNJ/0leOv0SY7ExnDYnoWiInlBPlqnpnk17sNvsNNc243F4GBwbZCw+Rn1pPS67iyZfE43ljRzoPsDzJ55nLDaG2+5mLDZGaDyUTmwTjARpLG+cEO00GAmyIuIuzn55qtRvTU3C5Zk5z0Qim/OcLV50sdpcL9Z+58ASAvMA+UI0VFQIG2De73TCrbfCddeJMjh3wmIeE959V2bo/f3yefttGUOmoovNdQQCmZn+pk2ZdnV3S9SCjRtlVbJrlyigO7t72LL7eJpP7x3pxefy0TPcg03Z0jPzQ32HSOokA6MDJEmyaemmTL9NlkMt9S20tbbxxJ1P0NbaNiGwm5Eb4JFXH6F/pB+HzUEsEaPEVULrqlbWVK3J8hEwBMv66vWsXbKWT235FB9e/WG2NWxLt3l99XqqPFWMJ8eJJWIs8y2jprSGEkcJR4eOpnUWez+0N39OhKNF5uScKvWb3Q4PPZTtqFFXNzETUDGhHqbCYtUtLNZ+52DB0kFXEwqt6hsb5du8/+RJEQ733psd3tlY0ZaWiuL21Cn5rqkR89BwWOKQjY5O3hazvkUp+dxww0Q9RD69zOqP/m/Klw/QfvoYwUiQs6GzOJSD7pAM6puXbmbXyl282vMq50LnqC2tZVnZsqywDcV67OZa8Rw8dxCHcrCzaWeabsoNKwFwbcNm4K9NexI89OLDWWXsyk5NaQ07m3ZydOgoI9ER/BE/FyMXuXnVzdy3TTi4EmcJL515KUuX0fKTR6CpNqu+vDx9d7dI9fZ2ualOpwiC3NRvZmVOe/vEG2EM+MaDMAaw6QiCmegWZotGuZJ0jKVTAayVwLxAoVX93r3Z+yMReOUVYQ+M1euDD8KXv5xZ0bpc4jtQWysU0tKlmTD0NpvM7qdCS4usNL77XZntu9352Qaj3BNPyHf92kEOnDlAOBbGpmyMREcYHBskHAtz4sIJXjj1AiPjI3xi0yd44s4n+OZt38Rhd0yahawQcq14SpwlnB89z4+7fkz76XbeHXiX5997nkN9h9IZxJSKAXZAmT52Hv7wQ1l1ux1uEskEL599mXAsTF1ZnVzLU5Vu275X9uG2u7lj4x3sWrmL0VhKuhbrletywYEDIp19Ppn5j43Bb/92/mVeIcwGpTFdT+LZolGuNB0zGx7UVwEsITAPUGhVf9dd2ftjMdi5UwxGjNXr4KCYauauaEdGZOAOh2WCGQ7LdmXlpber0PhkzvjVO9xLQkvUS6UUWmsGRwd5vff19EBaTBayQjCnoewf6ScUDZHQCRKJBEOjQ/z85M8ZGB1gR+OOtFlnRgBktxrsWYKotrSWaCKKQuFxiH+DVpotNVvY37V/ggDKij5aLE+vCmRHK7S/EGaD0piubmG2aJQrTccsRlvzPLDooHmCQtZO5v3f/W4mqrABI9GLGRUVMvPfvFnYhWBQ9i1ZIisBM5WUe818q3OzM1quE2tzsyiKu7vh0NitbLmxniHnvxCIBPA4PLjs4sCVJEmJswSFmhAcbiZhGszJ6ruGuqjyVOGyuRiJjTAUHqLEUUK1t5qG8oapK0NMPA0P4a9t+xp//S9/jT/qJxQJUeGpYFvDNmpLa9P0Uj4v5+5gN7QWab8cjYoyxYjwV1Ehrt/5HuhkmA1KY7o217NFo1xpOuZqtDWfASwhsIDgck3UERjmmyCGJUePysqgpEQsd669Vt6r996T8NKbN4te4eBB+PGPRfdo0M5TOaDmHj9xAp58UlYn69bBkSP1HHl2Gbv/bQ1dni7sygycyhwAACAASURBVA4Kyt3lrKpcxVhsjPHE+KzcC7MJaSASEC9gm52PrPsIB88dpNxVzvD4cLp8ruNZLtpStv2GF/Dp4GkSyQRuh5tgJEjXUBfD0WHWV68HmODDkKXLMEtuQ6o+8ki25DUUQeZEIX7/xCxeU2G2zESLtbnu6JBkFAcPCue4ebMorGdyzfng+n812ZrPEBYdtIBQWTlx9VpTI+/iiRPwm9/ITN/hEMpIKZlYnjsnK4LNm+V3JCLnKSWOqQYFO9XqPPd4T4/Q2b29sn3d6tXg8fPWi6tpLG9kLDZGNB6l2lNNOBZmODrMzqads3IvzFQSCOV04/IbqSuro8JTQSgayhr4xZwzAeSmU9Wp/dkRTddVraM72M3JiydRKALhAK+ce4XmmuYJyWkK6jIm47xni4q4nJSG0Z9ly+RPFgjIn+7EifnfdgsFYa0EFhC83omr169/XY59/vMSZcCc/N2YZLW1CQV08qTY/RvB5SoqRKdgRF+danWee9xIUGPo1urK6ti1cSuvHe1lpW85w+PDuGwuEiRw4GDtkrV8dvtnC/bPHIvHbXej0YwnxtPxenLLGPuNVYHL7qJvuI8LYxc4HTzNKr2KvuE+PA4P/oift/uOpqyDzPE3EmjtBLKVzW+ff5vlvuX4I356R3rZtHQT19RcQ+dgJxuqN1DqLOXAmQNodMYyKJfWmizcbVvb7AVzu1yUhrk/Pp9kKRoYkNnAN785v9tuoSAsIbDAUGj1umaNUMw209rOPICvWCEr+JqazHFjRWAuY0QJPXo0k0jmuusyx48fz+gZ/H4xOV22LFOnJ1HHnTvqaG75A77xm29wyn8Kp93JTStu4qFdDxXk/80mn06bk/bT7QDsWrkrrdj9pPeTPPHKE1nB3fa9so/7b7if+2+4n8feeIwXTr1Atbea29bcRneomxdOvcAta25JD9I6dyFgWgybI5oGI0GqS6qpLqkmFA3RuqqVpE5mRTf9+MaPZ3k5T8BUUnW2qIjLRWmY+1NfLx8jQ9FMr2/RMVcclhC4SjAVvbpnj+gADB1kJCKf6mqheO+9V5LPvPaarPJLS0WRHIlIjuKODlECP/mkTAJ9PrFo7OmReEXmXAUrdv+CB371AD6Xj5UVK+kZ7uHnJ38OUFAQmGfh7acl+TvAsQvHaF3VCsDg6CBVJVWMJ8Y5cOZAOjzE4288zuO3P059WT0fW/+xNEW0pW5LmrsvRvlsVjZXeCQaKmT0CYWimxrtn3CN+cB5zyautv5YACydwFWDqejVlhZRAmstFJDHI85oXV0yk3c6xconEBBlcywm5ZqbZZDfv1+O33CD6CaGh0WHuXu3mJ+aTUh/Evo6PpcPh91Bz3APDpuDEkcJL599OW/WMMg2+QxGgngcnnRSGJCBeDwxTiQeSdvv+9w+tNb88v1f0tHfkVWHgenkDDZz/RurNxKKhghFQ2ys3jhpdNOC17jaOO+rrT8WAEsIXDUoxqb/rrvge9+DT31KBvaBAZnxHz0Kzz8v/koul+gMtmyR5PGDgxkGo7tb0lWa0dQkVJThMNbSAj3DPfjcPobGhnDYHDjtznRI6bQ9fQ5WVKzIGvAj8QiReCRLMLjsLg73H8bj8OB1elFKoZSi2lvN/q79WXUYmE7OYLOyOZaM0bqqld2rdhNLxtI+DFsbthZ/jdkK6zBfcLX1xwJQXKL5J4DbgQGtdXNq338BPg6MAyeBP9ZaB1LH/gq4DzG5+LzW+vk5avtVjXz2+lOhEL1qrmt4WEJKnDsHQ0My4C9ZIuak4bAYfYyNyXkej6z2jVAVRhwilytjHXT4sFDDbW0Z68fG8kYC4UA6jwBANBGl3F0+Ydb89JGn+cZvvsGJoRNEk1GafE1sq9tG50gnAFvrt6Zn4TWlNVzoucAS7xK01lwMX2RwTPIKP9P1DF+56Ss8d/w5ACLxCIf7D9M73EtdWR2H+w6ztWHrpFnCis0olhvd1B/xp0NJFP1Q8jZgkhAKHR2SNm4yJ4/LgcnMX81OI4s0IudCRDErge8At+Xs+yXQrLVuAY4DfwWglLoG+D1gS+qcx5RSOalQLEyFQpaF4fCl1RUKwS9+IcpdI3zE2JgIhvFxsS5KJGRFEA7LJx7PhKpQSsqHQkIXhUKyrVS29ePeD+0lNB5Ca00sESMcCzOeGOdDyz6UNWt++sjTfOH5L3Dy4klKXaWUOEo4GzzLge4DfKD2AxNm4VWeKm5ZcwsKRf9oPwNjAyz1LqXSXYnb7ua5489xx4Y7GE+M88KpFxgdH8Xr9BJPxHnf/z4nLpwoSEcVm/D+Uryci35QueakxrF4fP5Eu8xt74kT8MAD8ueaL220UBSmXAlorQ8opVbl7PuFafMgYES5uhN4SmsdBU4ppd4DrgdemZXWLhIUsiwsJu7PZHU9+6zM7sfGZLD3eETxOzKS4fndbrjlFlEGX7wo+z/wAfE7ePFFUQhHo5myRl6DbOtH+Tt84zff4PiF45S7yrlpxU0sK1/GSf9JlieWc++z9/LiqRcZGx+jxFmC0+7E5XDhtDtx2BxcU3tN2oHLQHtXO5/d/ln2vbKPY0PHqHBXoFBE4hFuXH4jLruLzsFO6srq+Nj6j/H2+bcJx8J4nV7CsTA9wz1cW3dtXiXuZAnvc8vO1Mu56AcF2TfU2HY4Mg4cxrErNdPOba/ZaWTDhvnRRgtFQemJNnMTC4kQ+KlBB+Uc+wnwj1rr7yulHgUOaq2/nzr2beBnWuun85z3aeDTAHV1dR986qmnimrwyMgIZbnE9FWGM2dEUWsOI6M1uN0jVFdPr+/mugYGZAyJxzORi0F0fE6nfLvd4m3scokAGBjInG/kOFFKVgJG4EsQU1OtZf/KlZnrh+NhApEA44lxFIrxxDhuhxu7sksoaZ3EYXOgjMZoySBW5a1iZYWpIjLPPhwPc9p/Go3GYXPgcXhw2p3EEjFGxkdI6iROu5N4Mi51o9BokskkFZ4KYsnYhLrPBM/gtDkz7QBZyZjKmvvisruo9FROCG89YxR66LGY/HY6GfF4KDPCSuTe7HBYZgnj45mH552lthXT3kBA/lzmAFX5/hCXgMXw7hdCob7ffPPNb2qtt+c5pWhckomoUurLQBz4wXTP1Vr/PfD3ANu3b9etZvf5SdDe3k6xZRcq2tomWuL5/bBz5/T7bq7rO9+RscJYCdhs8u1ywerV8s5+73vZEzfz+T/9KZw+LXRRJCKrgERCFMi3354pd/fdBdrS3pYVbuE7J7/D+ZHzOGwOqkuqASRJvc3Bn37wT7m7Nbsi87PPrat/pJ+Xzr6Ez+1LWxX1jfZRW1JLdUl1ekVwbZmkhMytO7c+yISGuLv17iw/horSlC5g2D87VBAUfujGtt9P+86dtB47ln3s7ruz43mYk9zPpdI2t73t7SIIKiszoTCm+kNME4vh3S+Euez7jK2DlFL3IArjf6czy4keYLmpWFNqn4VpoJAl3nQigOara/t2GbyVkhm/wyEDf3m5fD/00OSJaj74QSmbSEhbEgnZ/uAHi7MWzDXhvH7Z9ThsDsYT44zHxwnHwkTiEdZUrZkynHRu6Ia3+t4CkPzFpXX0jfQRjoY5FThF33Af4ViYxvLGgqGqpwoFMWnk0NnAZOaXxrF4PL9p5pWIxpnb3sZGURItW2aZjy4wzGgloJS6DXgA2K21HjMdeg74X0qp/wosA9YDr11yKxcZCnnTX7x4aXUND8OOHWLAYeQxaW6WWXwhQ47cttx2mwgMg3Uw4hM1NBT2+Desbg71HeLIwJF0ovlraq9hdHyU13pfwx/1k0gkqHBX4LA50oNrS31L+vzVwdW0tbelB2ZzUpdwPMzulbsBcTCrLa0laA9yMXyRQDTANUuvYX31+oIWP4bC12wddN+2+9Jlzd7EBqbjgzAlpgqhcP/9cOSImHXlHrsS0Thz27t+PXzyk9nWQVYIiAWBYkxEfwi0AkuVUueAv0GsgdzAL1Mc6kGt9Z9prY8opX4EvIvQRJ/TOhVU3sK0kM+yMDex1FQWhflMTL/8ZVi+XGIMud3y3dycP9DlZG0pFmYaZUfjDg6cOUD76XZ2rdyFx+HBZrOxo2kHPpePzsFObNi4MHYhbclzx4Y7eO74c1R5qthg24A/7GfvP++lf7SfeDJOUidRKMZiY5wLnmM0Ppr2IyhxlrBmyRqurRMKaM+mPezv2s8jrz6S1wR0MoWv2ZvYwHR8EIrCTG/0lfLkzddecyY0CwsCU9JBWuvf11o3aK2dWusmrfW3tdbrtNbLtdZbU58/M5X/mtZ6rdZ6o9b6Z3Pb/MWLYiwKc489/LCElIZM7uLOTslONlfJncw0SkN5A7tX7cbn9vFaz2tUeato9DWytmotvSO9eB1eKr2VeJ1eeoZ7qPJU8ejrj6bPV0oRTUR5d+hdLoxdYGR8hHAsnE4I//K5l+kOSPC5cCxMJBFh09JNVHgqONx3uCgT0EIoOnLoXGAqE1HLk9fCJcDyGJ6HMBK33HuvfOcbkCejgQsd+/WvhcP3ejMpJ8fHM5PIuaCTu4PdROIR2k+382zXs3QNdbG1fivbGrbR1trGeGI87XTlcXgA0ordCk8FPcM9WXqErqEulBZh4LQ58Tq9OOwObMpGpaeSJEmGwkN4nV5uaLqB+rL6dMyfS+H058w/oBgYD9RsImp+SJYnr4VLwKINIHcl81tP1a7cxC4PPiiDtcHdr1kjg/lNN2XOO38e3n1XzLTLyuD667PrraiQOgyMjIjH8IULYu3T359JJj8Znfz00/Doo2IW3tgoeZDzMQAGj//y2ZcZGhuivrQ+baVz4MwBmmubaWtv462+t3i953WGxoY4FzpHqauUclc51SXVBCNBGssbCUaCaRomGAnitDsZjY/isMnf16EcjMZGuabmGqo8Vfg8PrHi8VTMLOZPAcyJf0AxKIbzt6JxWpghFuVK4Ernt54MubP4aBQOHYKXXhKFrMcjYRzefBPeeEPOOX8eXn5ZaOBlyzI5zM+fz9QbDIrwGB6Wwf/sWTEXVUrqfOUVEQRG2Xx08tNPi1NoICCK4EBAtp/O8QIxe9+WOktJJBP0j/YzEh0BIBKL8Pb5t9PJW84EzzAaGyWRTDAaHeVs8CyljlL8ET97P7Q3TcNorXHZXbgdbrwOL9F4FK01kXgEm7LR5Gtia8PWvDP2acX8mW+wEqJbmEMsypXAZM6ZhSZTl2vlkDvp6+qSgVspEQqGRU4kIoJg/XpZASglQmLzZjnvpZdEeNx6a8Zs/EtfEl+Bt94S6tjlEicvj0fOP3pUlMV+vxh25OLRR8Up1DBVNb4ffTR7NfD4G49zbOgY44lx+kb6aChrYHBskGMXj1HmKkMhgd+M5C0rK1ZyMXKRkegISZIkSHBk6Ah/vvrP6RzsJBQJ0R3spsXXwraGbfSEekgmk7ze9zr+iJ+ETlDpqqRzsJNPbvpkwRn7vlf2pVccg2ODOO1OHrrpodl5cHOJPXsyOgFzzO58D8nCwsE8oSMWpRCYrkXdVLl3ZxO5hh7BoDhdulyZMg6HfNxuKdfbKyuAzZszlM6uXfDqqxMtCjdsEN8drWUQN4SGQSXdfHOmbO5/9NgxMSvt7xfBsXSpCIUekydIR38Hv3z/l7htbkZjo4SiIfxhv1jsOLxsrN7IOwPvkNAJzo+cJxgJssS7BJfdxanYKaF/okEGRwf56q+/yo1NN/LBxg8SjASxR+3pzGT7u/YzFh/j3cF3KXGWsKJyBY1ljTx3/Dk2VG/IG+rhjg138PCBhwlFQ2g0triNhw88DMBdW+axVYvB+RcyEbWw8HA5B5UpsCiFwHQt6h5/XAbA8XERFps3Z/Rys/28jEkfyLWMiJ1OZ6ZMPC7fa9aI4ri/X2b3r74q52zaJIP0Jz4hx81oaYE775zY/zNnRNj84Adiivrxj8Pbb2f+o8ePyzkej1wjFhNKqbJSttvaRFi8n7yAXvYBzlf+GrfDTYW7goGxAUbGR6gtreXC2AWi8SgJW4Jnu55FozkdOM1IdIQECYKRYDp0g9aaV869worKFdSV1WGP2dnftZ+21jZa6ltoa29jWfkyeoZ75DwU8UScO566g6ROYlM2VlesZvfq3ezZtIfOwU621GzhyNARkskkoWiIs8Gz7P3ZXmABCIKLFyVm93zDPJnRLijMhI6YIyxKncB0LOo6OuCXv5SZs88nPPrLLwsdMxe+OLmGHtu2idAxmIDxcQn74HSKUrajQ2bioZDsGxsTKujkycIWgrn9f+010SG43Rmu/6tflVhBhm6it1d8CoyMZHa7nNvbKzkJDP3KwFCcwIv3EevbDBpcdhdOmxONZmx8jKHwEA3lDdiUjaHwECPjIwSjQeLEJb4PSRI6QVInARiLjfF6z+sA2JU9S5F7uO8w75x/J51g5mzgLK/1vsbg6CCRWITR6CiHzx/m1bOvsu+VfRzuO0zPiFBJA2MDxJNxyt3ljMfHefjAw0Wbi1owYT4r2OYzurszdtoG5trBrwAWpRCYjkXd/v2SglGpjFmlxyNx9OdKL9fSIjPrJ56Ab30L/uEf4Hd/N6MLWLtWHLvuukvat2aNhGspKZEZus8nDmFmxzGzySlk9//dd8XSp6FBBvzKyoyOwEAwKDGC6urkHoyOyuBfXQ1bt2aERe1SJ9pzkZITf4DT7kybclZ7q/G6vKysWEmTr0kSzTjcJHQCu7LjUJlFqfE7koiQ0Am6LnTRP9JPQieyFLmBaACbsqUTzFyIXMCGjYRO4LQ7KXWX4rK7OHrhKFWeKgLRAIOjg4SiIRzKkQ4yV+4uJ5aMzV4IiMWEKxGy4mrAPFL2L0o6CIq3qOvulkHu4EHZ9nhkVXDx4uXzxWlpgX/6J6FpckNHGPoNm00GaMjk/obJqUdDIKxfnznXQFlZdujqigrZXr1aBI5BQb33Hvzrv4rQSCTA7t2Otg0QveBjQ8VKIvEI/rCfWFIifLrtbi6MXWA4OozL5iKSiJAkidfhJR4TnsuI+gky+0/qJC+dfonty7ZnOWdVuiu5GL5IOBbG4/CkrYQSOpE2H3Xb3QxHh6nwVFDprsQf9jMcHZaBPxEjnoyzxLuEJSVLZi8ExOXGlaRjrkTIiqsBubzvFVT2L8qVwHSwYoUM/DfcIDPgUEgGvFtumR+051QTimImakbsLzO83oylUDIpiudQSMr29QnlFAoJRfT++xJd1GYDe6KM0t5bwRFlcGwQj8PDhxo/xJbaLaysXMm50DkGRgfwODzEkjG01iR1kkQygS31d4zrODZsuO1ulFKUOErwuX247K4she/Whq001zTjdXoJRUN4HB5cdpckkkmKQDEymgUjQbY2bOWhXQ/hcrgYjg7jsDmoLa3FZrPRWNa4MMxFc3Gl6Zh5NKNdUJhHDn6LdiVQLAyBXVUlFjeGwP7sZ2f3OjOdzE01ocidqPX3C83T25s5f+9esfcHoZKMzGEPPCDmqd3dYlW0Z4+EmXjmGSl33XXw+uuiH3A4xP+gvh7K3RXcuOa3uWbL0axUjQB/+Mwf4rA56B3pJZqIolDYsRNLxrBhw26zE0/GsSs7PpePSm8lH179YWpLa9Gh7NwXezbtYd8r+7i27loqPBW8fu51fn321yz1LGUsNsZ4fJy4jnNd/XXpFJCGEHn4wMPEkjGWlCyhsawRh91xeUJAzDautIJxHs1oFxzmiYOfJQSmwFTBHWcDl2ItNlX7zJZQ/f3iFKaUzOwNb+TlyyXvx6lT4kG8di185Sv5PYHvuiubgkok5NyhIREYq1cLfRaLLZ2QGQxgiXsJ7468SzwZT4eJMGbtZa4y4sk4pSWleBweVlSsYNPSTdSX1eMP+3HZXVl15Ub+3LF8B7esuYWfnPgJ7/vfT1sH7Vi+IytY3F1b7mJD9QYef+NxDp47SDASZGfTzuk9tPmCK03HXI4XxMKcwhICRWCuBfalTuYma595onb0aMap7JprxBv55EmxArr1VqnD74c77pAZ/z//c/5ViVmwVFSIxVR9vQiAzdvPc+jUKaLOftraD0+I1KmVpqG0Aa/DSywZw2lzEolF8Dg93LnxznS0z3QCF3Poh/KJCRXyOYb95b/5y6lvGjAaG2XXyl3p2EX7Xtk3N/GA5pKzL8beea51BvNkRmthZrB0AvMAc2ktZqYee3ul3htvFEVwV5fEIBofz+gLEgmJNjoZxWw2Md24UeijUAhqll+g/ehhQgEbO245lzdSZ6W7kqROUuYsI56IE46FxaYfWzoqZ6FgbbOWypHLkCTGwFxz9lPZO19pnYGFeQ9rJTAPMFvh4M0TPrc7k/xlZESUtxcuSL1DQ+KE1tcnXr9Ll2bqOHdO9AGTrUoMwfL44+JjkEiIjqDj1ACVK5Ns+/Ab1K8dAiYma9/asJVSVyk9wz3EkjGiiSh2ZWd5xfKsWXi+GX57V/v0bsgkmPMkMQbmmrOfio650jqDQrAczOYNLCFwGTDV/302dGtmvYLTmUlA09QEv/mNTBLtdqn74kUxCwVp0zXXZOoZHJR4QmYUWpWMjoqy3Gjz/9dxka03n0wJgNS5OQOrWZm7a+UuydUbmcVcvUViOklijIioZiV30W29HJz9ZHTMldYZ5MM8CplgwaKD5hzFrMZnw1rMPOE7dkxm5j6fKIINARCPi4DQWsJENDWJs9eZMxkmwekUM1Az8q1K8pmeVi+xc/hf1mafmzOwXtG4/CYUmyTGHBF1JslorrgJ5ZW+fj5YDmbzCtZKYI5R7Gr8UnVrxoTv/Hnh+kEooXBYPImNsNSlpTLQx+OSn6CvLzvQ3EMPwXPPiUAwr0puuikTH2jFCvGYzm3v1pWreeHwOP6wP61sNUwzzbhicflz2jBZTmFj9v9M1zO47W6ua7gurTuAbIprUlxpE8orff18mI+rk0UMSwjMMWbz/x4OZw/EZlppxQo4cUKseux22ReJyKw/FpOB3+GQGb+xMoD8geY2bMimr266SQSDefV+6pQIFINWAvAk6vid6zRV3qq8A+t8QyFhZM6LDBLI7uWzL3Pj8hupK6ubnu7gSptQXunr58OVyolsIS+KSTT/BHA7MKC1bk7tWwL8I7AKOA18SmvtVxL+8b8BHwXGgHu01ofmpukLA9P9v5szd1VUiNllebkocrdvn0grGbTRnj3wh38oA38yKby/3S6DfCQidZeViZI4mYR16zKGJLmTwtxVyWc+IxRTMCh1eTyykvj5zyV0RE2NtMluh/vvr6elpa3g/Xj6yNM8+vqj9Az30FjeyN4P7WVD9Yb0jNxtd6PRjCfGp8W/F8Pb55Zprmmmc7Bzwjlmy6FKT2U6LMXRoaPUldVNPxlNoWXe5VKOzjcTzvm4OlnEKEYn8B3gtpx9XwJe0FqvB15IbQN8BFif+nwaeHx2mrlwMZ2IpebMXeXlYsP/i1+I+eVbbwmdYzbnzE0zu2SJnBuPy+/SUpn9ezyiHzCseJYtk9l+MboHI4rq6Ki0OxKBgQFRIEejEl5icFBWIHfcMXldTx95mgd+9QCBcICG0gYC4QBfeP4L7P3nvfjDfpw2J+2n23np9Es4bc6i+fdiePvcMseHjvPArx7gxIUTE87pDnanU1FuWrqJSCKCRhMIB2YvwfxiNt2cRyETLBSxEtBaH1BKrcrZfSfQmvr9XaAd+GJq/5Naaw0cVEpVKqUatNZ9s9XghYbprMbNmbtOnxYuPx6XNJJVVTLTPnpUbPzzhX/QWiKBVpp8qgIBEQS33z7RdLQYGFFUT50SOso4124XQVNeLrkH/H4RBBt+q/CM/NHXH02HggCo9FbSN9LHSf9JPrzmw7Sfbsfn9gFw7MIxWle1Shum4N/NM3cgL2+fW6Z3pBefy0fPcA/rq9dnnWO2HKovq+eGpht4q++tdDa0WaG45qvp5uXCfFudLGIoGa+nKCRC4KcmOiigta5M/VaAX2tdqZT6KfANrfW/po69AHxRa/1Gnjo/jawWqKur++BTTz1VVINHRkYoKytLb4fDMtCNjwtlUlkps9OFiM5O4e6TyQyFk8qvQkkJVFWNMDRURmmp0Dogg3FJiczyx8dFaNhsGc/gZFIG/rVr5V6dPy/n2O1yTiKRCQ+di3BYhFE8LnUb4bSTEuofjycTelprCEcS2JecxW6zY1d2EjpBIpmgrqwOr8NL50AnTrsThcpcIx5Ga01dWR2BcACbTRanyWSSSm8lWmtiyRgrK1ZmPftwPEwgEmA8Mc7Y+BilrlKc9kzmHfN5AGeCZ3DanOmENca1jOuYz6ktreX8yPmC/ZgVnDkjD1tl7kVagbNyZd5Tcv/7iw2Luf+F+n7zzTe/qbXefil1X7JiWGutlVJTS5KJ5/098PcA27dv162trUWd197ejlHWbG5sphYX6sqyrU2sdQIBSQ4DMgDb7fCRj0BraztPPtmKxyN91Trj/ev3SyawZctkdRAMyj0xqJ/77pP6c/UTxnZuBjLj3h47Jiv2CxdEYBiWRTabrBDWr5fQ0n4/vB38F679P97Ksr33h/1UOapoa22j7TttBMKB9KALcHTwKA6bgz/94J/SPtROOBYGwOv00lrTmp6R3916d/rZmxW3FaUVPP/e84SiIVpXtVJXVpe5buo8gLb2tiy/gPah9nRbWmtaJ5xzSb4BxWCyh3H33XlPMf/3FyMWc//nsu8z9RM4r5RqAEh9D6T29wDLTeWaUvvmBFebufHevcK3R6My2x4bkxl4VVWGyrnuuonhH0C2KyuF+rn2WqForr1Wtg39Q77wFJEIPPtsJuGMQUkb93bbNlkRlJdLXUqJgtnjkdXIxo0ZPUflthfTXLoBsyXN3g/tJTQeIhAOkEwmCYQDOO1O1latxR/2s7F6I6FoiFA0xMbqjQX599yQD9satgFwqO9QQZv/XL+AZWXLCI2HaCxvzHtOS30Lba1tPHHnE+l0lrOK6SiLLFiYmUmU0AAAIABJREFUQ8xUCDwHGNOVu4FnTfv/SAl2AsG51AfMowxt00Jupi9j4L3rLqFtxsdl1u31io5gZERWB42NEqrh3/070SUePSoDeHu7KJG3bs2vbwO5zltvwfPPiz4BhBr6xS9E8Bw6BD/7mUQV7ejI3Nv6eslc5nIJ7aRUxhpo/fpMiIn774f6tYM8/97zPNv1LO2n2+kf6c+ypLlry118bvvnCEQDHD5/mEA0wF/s+Ase/eijVHmriCVjtK5qpbm2mVd7XuXAmQOUOksn3D+z4hagvqyeXSt3EU1ECzqg5TqpbVi6gc9t/xw9wz38sPOHvH3+be7YcMflM2e1lKMW5gmKMRH9IaIEXqqUOgf8DfAN4EdKqfuAM8CnUsX/GTEPfQ8xEf3jOWhzGgvR3LgYj3mf6EbxeCSuTzyeretoboYnn8x4BQcCMmh/8pMTr3f8eMbG//rrJZfwSy9JuIdf/UpWFV6vzPJ9PhEmjz0mg/7zz2eUwImErFASCRFKa9bA3/2dKYVlfwc9nT2EoiHKXeUMjg7SOdCJ1+nl9vW3py113h54mzs33kkkHuFw/2Eef/Nx3vO/x2e2f4aW+pY01bN75e4J0T0N5Av54HF4+MSmT+QNX23A7BdgXOfaumvZWL2Rw/2H+dILX+KFUy+k2zLnsJSjFuYBplwJaK1/X2vdoLV2aq2btNbf1lpf0Fr/ttZ6vdb6Fq31xVRZrbX+nNZ6rdb6A/kUwrOJhbiinozC6uiQ2bnBucdiopgdHc22+OnshJ07Zd/wsHzv3AkvvDDR6vDhh2XgrqoSy6HWVhnsX3pJfBHKymTGH4/LisBuhxdfzE5eHwhI0DnDJDQeF2uh48dN/eraz5qqNbSuaiWpk/QN92FXdmpLanHZXex7ZR+PvfEYVZ4qookoB3skX+cSzxIO9R1Km2cWE92z2JAPkz6H1HUma4sFC4sBCzp20EJcUU9GYe3fL4rchgaZiScSogfweITqAREUzzwjyeEBduyQgX3dOsmDnCtgYrFMvmEQHcKtt8pg7vHITP/CBRE0hpNZKJSdvL6/X4RBTY3c282bZYXy6KOmfqUomrqyOsrcZayvXs+mpZtI6mR6ID947iAVngq6hrrw2D14nV68Ti/jifH0QJ9L9cDEIHSzEX/IuE7XUBeJRILzo+fpDnVzJniGeCI+rZDSHf0dtLW3ce+z99LW3mYJEAsLCgs+bMRCW1FPRmEdPiyz7J4eGaQbG2VmbiS17+mRmb5h6x8OS4C4G27I7MsVMDU1ImDa27MthkZHpe5IRKggw8RUKck0VlGRSV7f0SErBrNvgc8n7Un3y0TRBCNBfG4fkXgkPaBXeCpQKIKRYPr4yPgIfcN9JHSCw/2HqfJUsbVha1HRPS81/pDR3r7hPgKRAA67Axs2lE3ROdjJWGysqHrMlkpmp7MrERTPgoWZYEGvBBYiClFYzc1CsSQSEioCZHtsDH7nd0TQBQIiPK67TqgZkMH/rbekjp07JwaMLCmR8wwv5EBAVgwOh8zmS0sztv9ay+rg5puz6/H5ROB4PJl9RtL5dL9MFI3P4yMYCRKJR9i8dDNAOoWjPyJpIi+MXeB04DTRRJTG8kaCkSCnAqdormm+ZKqnqOeQau/IeMrhQkNCJ2goa8CGjUA0UFQ9ly05jQULcwRLCFxmFKKwOjtFEGgtA/S6dbI6sNsldg/ITLyiQmbnN94oq4Xxcfncfz989rMTBUxvr5Q16w9uuCHjRLZsmXj+lpSIkGhpkeuZ69myRYSAyyXbgYAIgb17Tf0yUTRV7iq00jTXNlNTWpMeyD+z/TPcf8P9bGvYRu9wL3ZlZ2XFShw2B1ppttRsoXOw87KEmjbaW+YuYzwhS5wmXxN2ZSepk1S6J6ayzIdi6CsLFuYzFjwdtBCRj8J65BExD/X5xPTToG6qqjJlXS7ZX1UlgsBwEjOXyQ1RsXq1HLOZxH0yCUeOyODe0yNCZ/VqmdmvXz8x1MWHPgQf/jD85CdSvrExfyL6XOubQmGav3X7t+gf7scf9ROKhPA6vWxr2EZtaS3dwe7LFmq6pb6F32/+fU5cOEHPcA/BSBCv08u6JetYX71+6gqYXnIaCxbmIywhME9ghII2PHRB9AObN2fKVFbKoA+Fgy/mCpi2Nqm3p0fK2+1CJUWjmdXHrl2ZuvbsKRzc8i+Ly98u7ZhiIM/H/fvD/vTgmc9jdy5gznRmzoFQ7PWM84FJcyhYsDBfYdFB8wTNzRmnL7s9k/3r6NGMM5nXO31rqOZmUR4HAsL9nzwpg3tLi6wEOjulfrNj2eUIbjmZmWehqKDheHh2G8GlWxrNl0xpFizMFNZKYJ6gs1O4ech4C9fWivVObpL36VhDGT4Fvb2ScUwC0Yndf2urWA+ZYwe1tRUX3PJSQ+FPltmrrb0tb1TQQKQ4Ze10can003zIlGbBwkxhCYF5gu5uWQGsW5cJLKm10DRGGIzJMotNVu+6dRJELhjMeCMb1j+5YTbyZUKLRMQ3wbhuc/PETGP79sEd9xyn0/a/ik4OU2jw7A520+TLbkSFp4LxUJHxry1YsFA0LDponmDFCrHWMUJIg/x2u+WY4U08XZrGnGe8okLqjEQy/gS5YTZy85L390uoCbc72ws5Hs92Sku4B3n4f3ReUnKYdBsqVhCMZNu6BiNBXHZXUedbsGCheFhCYJ5gzx6hZkIh8Q0YG5PftbVybP9+WSlMN2Kq2S9h40apMxTKjv5pDrNhLt/XJxZBvb1CUQ0OZryQe3Jiw56LHiF2cRlV3iqOXTiGz+3D5/Zx7MKxadvOF9IXVHqmNtu0vHctWJgeLCEwT9DSAl//OuzeLXb/sZhw9l/7mhwz6CIziomYavZLMOrcvTs7+qeZUjLKR6MSi2h8XExX7XZ4+WVZjdTUiEAwY/BijJpl4mUbjATxODx4HJ70jH46tvOFlK1TJXQpJs2kBQsWsmHpBOYRWlrgW9/Kf2zFCpmNmxEMCk0zlZ5gusrklhYJIf2xj0mimnA4E8H06FGhhQIBWS0YpqrOWA2NO34OyIBvJIcxHKmmazufT1/Q3tU+6TnFpJm0YMFCNqyVwALBnj0iBMzewO+/D2fPzo05pxHobtMm0SGEwyJwjEijDz2Ubar60BdLcDS8O63kMLMNy3vXgoXpw1oJLBC0tAgPb2QZW7FCPHfd7pnnKp/MzNNwXuvpESFgOJotX56hkLI9hjewoT9j8tm6qjVtHdTgbZid5OxToBjv3TlPG3k141Ltgi3MS1hCYAHB683OBXzvvaI4NqPYzGpTJbcxJ66pq8solPfuLfzeX2l7+am8d62In5eAYrIhWViQsOigBYxcc04oPrPaVPmZCyWu6eyc/X7MFqby3rUifl4CrraE3hbSsFYCCxh79shkDArHEiqEfE5h5lWE2cnMQDI5//M3T7YaKeSEZukMisBUfxgLCxaWEFjAyI32uWKFCIBiVudT5Wc2jo+PZ6KaulySyyAfJuPaO/o7eOyNxzh47iAKxc6mnZcvj68JKypWcHzoOL0jvQQjQSo8FXjtXsKJMPc+e6+lI5gMCzGht4WicElCQCn1F8CfABp4B0ks3wA8BVQDbwJ/qLW2/P3nCDPNrGasIoaGxMJncFBSSD70UOb4l78M770neQacTtEJnD0LTz8ttJAheMobT/Pkr94jdvE2apaN0dfyPD8++oesrlxNQ3kDnQOdDI0NYVM2BkcH+YfD/8AP3vkBt669lYd2PXTZBt3mmmaefPtJfC5xZOsb7qNnuIddK3ZZOoKpcCnLTgvzGjPWCSilGoHPA9u11s2AHfg94D8Bf6u1Xgf4AetfMg/R0gJ33CGD+eCgOIBt2SIxgTo65HhjoyiGYzEJPLd7t2w//HDGLPXECfjq35QTPr+cmoYIF/2ag//0bwifW48/8v+3d+7RVVX3vv/MZCfZAUISQCIhhETEB2AIkLZQHDZoaSt1YBVP5fRxQrUDlVbrsRyrdfSUOwZI7WBYPZdWDuPohbZekeZgya2n0KJEzxlFLCikUR4WHyERQsQQEshr78z7x1wrWQl7J/uZ7MfvM0bG3mutueaec6+d9VvzN7/z92vmrVNvceSTI3R5ujh94TStXa2kkopXe9n74V5+/OqPh20xV21TLQsKFpCTmUNrV2tvVrOLnosyRzAU8ZjQWwiIcN1BLiBTKdUNjAJOATcC37CObwXWAM+E+TlCFKitNSuInSP85uY+iWlXl0lK70xIc+RI32pjMBJSldFGV/MEVNEFWlNOkj7aTVftEs5P+d8AKBRn28/SQw+uFBcpKgVPjweFoulC07At5qprqWPauGm9CWN2Ht1JVnpWvzhFMkcwCPGW0FsICKW1Dv1kpX4ArAPagT8BPwDesEYBKKWmAH+0RgoDz10JrATIy8ubt23btoA+s62tjTFjxoTc5nhmqL63t5uVvF1dxn+fk9O30tcXH31k3Dx21FIwkUu7u2HqVBM7yOMxmcdsPv3UbNvRSM+dA4/uoqdHkTmmkw5PO4oUerwuMic0AtDh6TA3faVQKDTmN+dKcZGqUhmdPpqp2VPD7v9QnGo7hafHgyvFdKi1s7V3OysjC6B3e9KYSSF/TrRI5t8+JHf//fV90aJFB7XWZeHUHfJIQCmVC9wKFAPngN8BXwn0fK31ZmAzQFlZmS4vLw/ovOrqagItm2gM1nenjNvpsh1sxL5mzaVzffZ2RYXvOqurzRqC6dPtNsGppouc4yOKSj/k9IU2LrakkzLqPLffZ9w8u07uovFCIwpjbTSaTFcm+Vn5jEobxc3Tb6aivCKs/gdC7zqBtFyy3dmc6DzBvo/3MX/yfK4cfaVZV9DdzOrPxuacQDL/9iG5+x/NvoezTuCLwAda6yatdTewA1gI5CilbONSADT4q0CIHKHIuJ0RQ+1QFM6oor7cwD/5iVk5bJ8zeTJ0t49i3tV5uFMzSe2YgKc9i3k3fsRloy8jPTWdWRNnsbBgIa4UF54eD6PTRjNpzCQ8PR4uG31Z1MNJ2AxcRzB9/HR+/sWfc9WEqyQrmJC0hDMnUAfMV0qNwriDbgIOAHuBOzAKoQpgZ7iNFIYmFBl3IBJTX27gq67qO2f6dLjtNqitHUddXTmL5sOsG45Tm/JWr1y0orCC2qZaRqePpr61nrauNlypLq4vuJ5VZasuuelGM7SDr3UEd3CHn9KCkPiEbAS01vuVUpXAW4AHeBvj3nkZ2KaUWmvtezYSDRUGZ6CMu7ER/vu/jQR0zhyz2ve++8KPMOrvnIFxhO5gDdA/VEPJ5SVMzZlKc0ez3yfuwUI7CEJME6exlcIKG6G1/qnW+hqt9Syt9be11p1a6/e11p/VWl+ptf4HrXVnpBor+GdgMphdu4ymf8IEM/lbXW10/5FOGD8UwYZqkNAOQlxiT6BFI6RvlJHYQXFCTY25ud91l5nQHfjbcvrv33zTKIQKC40RGDXKqHnOnIlsqJfKSiMxnT7dvFZWXlom2PDOEg5aiEviOLaShI2IA+yHjMWLBw/gaLtp6urgrbf68ggDuN39k9aHS2UlPPywMS6TJhmp6MMPm2NO11Ag4Z2dBFs+WCSUtBAV4ji2kowE4gD7IcPlCuwhY6ik9ZFg40ZjAHJyTJtycsz2xo39y/nLF+xPERRs+WCQ9JNC1AgnpO8II0YgDrCzfDkZ7CFjqKT1kaChoW/BmM3YsZcmoB8qvPNAgi0fDKHON0jyemFIhtJbxzDiDooDbOWPk8EeMuyk9b/6FbzxhlkRXF7uWx00EFvgcOiQcfHk5EBpad9v2RY/dHfDhx+aUUBHh3E3paebdQOXtCfIZDOBlA/FrRNKKGlJRCMERDghfUcYMQJxgB3A0eMxDxktLXDihAkJUVpqbvIDJaCDJa134lS1paebJ/msLJO/OCXFbJ84Ac8+az6vrMzkGZgyBfbtM/uUMkZKa5i/qJE11c9E1ece6o05lPmGiCSvj1PpoBAkcRpbSdxBcYD9kOFymZW7nZ3GvVNba27coUpAB6ra3n7bhI4+ftzc3F0uc+zTT43xOX8e3nmnL9n8xIlmFNDVZcpPmNjJ/9vdwfF33VH1uYfq1gllviFstVIcSweF5ECMQJxQUmJUOM89B5dfbgzB2LFG/hmqBHSgqq2ry4wC6uuNe+eTT8xkstdrRiFg9h89akYjLldf2snSUkgbfwrVk87Hb34uqhr/UG/Mocw3FGYX9osyCkGqleJYOigkB+IOikPq6owRCFcCOlDVlp1tJpHBPOF3dJgnfrfbzAE4Pyc720QhzcrqO/9iu5esnA5aGnP66oyCxj8cGWmw8xNDJa8fkjiWDgrJgYwE4pBISUAHqtquucYklZ8wwYSl1trUm5UFo0ebv5YWM+rIzzfH3W7z2t4Oqd7RZIz7hOy8c711RlLjbxNNGelAwlYrxbF0UEgOZCQQwwycT/zc58z+22+HAwfMhK2dDqK11UzY+lKk+ZuXHJgxMCMDpk0zk76nTpn5hsZG4276/Oehrc3MQ+TmmiBy8+bBr3/dl5ls7ux0jn7aSf5n99Oje4J/arbbO4Tyx74xO8vcPefuqKl1gh099EPSMgoxjhiBGMUZy9+eT2xs7Ev9+PjjJs3jq68aF86oUSbOfyD1OFcbD1S1Pf54n8ChpgaeeQb27oWdO80I4MYbYdWqvjKLFzvPH8ddN0ykNqWDupb6kG7OgQaQC+vGPJzEsXRQSA7ECMQozvlEMK+pqX2pH8G4YCZO7PPL19YahdC6dX1lfNVj73cq2ux7lHO+csMGMymcnm4mo22FkNOIXKqK64sgGlK/B5FkllMecr0jSpxKB4XkQOYEYhRfq4RTU/vmE3fsMG6YoRRCQ6029qdgfOYZYzAaGoz8005V+fHH0RW3SAA5QRhexAjEKL7mE73evvlEWyHkdvcdd7vNPqfwZKh5SX8Kxjfe6HNh25/hVAZFS9wStiRTEISgECMQo/gKReL19k38OhVCbW0mhMO775rRQUbG4PU4Q5r4Gylo3XfDt1VIHR19hiFa4pbhVP4IgiBGIGbxld83L6/PtWwHiTtzxhgAW9KZnm6SydgLUn3V4wxB7W+kMH++MRaTJ5u6z50zr/n50Y2LFc0AcoIgXIpMDMcwA+cTq6v7H3v8cZNkpq3NxO8pKjKxfTIy+k8gDzYv6U/BuNoS4+zYARcu9AWTu+oqCX0jCImEGIEYxZe2fyD2zX3JEuPPt+npCdxnP5SCcbhv9pJjWBCGl7CMgFIqB/gPYBaggbuAY8CLQBHwIfB1rXWznyoEHzi1/Wlp8Mc/wm9/C//6r33rBGzS02H3bhP3JzvbrPoNZuVwIAEuhzMIZkJKRAUhhgl3TuBpYJfW+hpgNnAEeAR4RWs9HXjF2haCwFbsdHUZlQ7AuHFmUZgzAGVNjZFwnj9vjMXFi/Daa2YlcSA++0ACXA53EEyRiArC8BKyEVBKZQM3AM8CaK27tNbngFuBrVaxrcDXwm1ksmErdo4cMbLMzEzzp3V/jf6OHXDFFSZhzKhRJsjb2LEm7IPzSb2mxiSnH5ikPpAAl8MdBFMkooIwvChtB58J9kSlSoHNwLuYUcBB4AdAg9Y6xyqjgGZ7e8D5K4GVAHl5efO2bdsW0Oe2tbUxZsyYkNocL5w6ZUI3t7WZG69Sxs8/YUIbXV1j6O6GqVNNFM+0NHPcRmtjDCZONJO5Fy+atQOZmX1hob1eozQ6c8b/+VOnmu3BPsMuE0naPe00tjWSmpJKqkrFq714e7zkjcnD2+FN+Gs/GMnw2x+MZO6/v74vWrTooNa6LJy6w5kTcAFzgfu11vuVUk8zwPWjtdZKKZ9WRmu9GWNEKCsr0+Xl5QF9aHV1NYGWjVdsF8yxY+aGq5TR6P/wh9UcPFhObi5UVJin+ubmvlAQYLa7uoyiJzfXpIlsaTH1fP7z5ubvPMfX+Xb94P8znGUi3n8/AeSS4doPhvQ/efsfzb6HMydQD9Rrrfdb25UYo9ColJoEYL2eCa+JyYet2Jk712T1AqPbt9M42v5+fwvBbLdRbq6ZL8jONm6lI0fMefaK30ByY49E/uySy0tYU76G5259jjXla2SNgCBEkZCNgNb6NHBSKXW1tesmjGuoCrCfESuAnWG1MEkpKTHxe3bsgJtvNu4Xl6v/Qi9/C8FspRD0rfj1eExGsJ07jZooPX3ohWT2ZyxdCocPwwsvmNelS2WdgCAkCuGuE7gfeF4plQ68D3wHY1i2K6XuBj4Cvh7mZyQ1zoVe1dWX3nx9LQQrLOxz2VxzDfzXfxn/f0qKCUJnJ5S35aaD3dBraqCqCmbPhhtuMK6lqiqzaCwYQzBUjoBAzlucupia0zUyMhCECBKWRFRrfUhrXaa1LtFaf01r3ay1Pqu1vklrPV1r/UWt9aeRaqwQGE4XjtbGJQRmchjMRG9WVmAKn0iog+wFYM3tzUEloB94nqfHE5XE9YKQzMiK4RgiUouynKuAf/97c9OfNq0v70B7uxkJOCOQ+iMSKXIHWwA22FP9wPNcKS5y03KHPE8QhMARIxAj+MsAtnSpSRZTV2eyeA1cMewP281jrzlw5iN2u0200UWLhq7H6VqyCTaKaF1LHQVj+1uSQBaAhXqeIAiBI1FEYwRfbhePx6SQtFfrejzBr9YtLDTndnT0RRptaTGjg0AUPpFQB4W6AEwWjglC9BEjECP4iuvf0GBUQbZhcLmC98fffruZDJ41q28EoDX85CeBjyiGUhAN2YYQcwQMPM/T45HcAoIQYcQdFCP4crs0NZmcAU6C9cc75wcyMowLKNi5hnBT5No5ApzqoEAS0A8879rUa1n9WcktIAiRRIxAjOArrr/HYxaLbdtm3Dn/8i9G4z93bnB1RzvPeSAT2iWXl4R087bP2XF0B10tXew4uqPffkEQwkPcQTHCQLdLZydMmmTiBzU1GX++x2P0/s7MYSNNtKOMOmWiaSlpActLBUEIDBkJxBDOJ/Y1a4z75sIFswLY6zVhI8aPN3JPZ+awkcQ5oQ19r5Fqn1MmqtpUwPJSQRACQ4xAjGLr871euPJKYwDsKKDBzgtEk0isIxi0/hGQiYa6ulkQ4hFxB8UodgJ4p8Zf6775gmB0+tHEX6L6SLVvuGWioa5uFoR4RYxADOFM/nL6NLz/PkyebOYDzp0zOv38/OhH8QyGaEcZdcpEtdYBy0tDxel+SlEp5GbmkuvO7Z2QFoREQ9xBMcLAFcN2DoCxY032sHPnjDvoqquGlngOZ07goRLVh12/Qyba3dJNbmZuQPLSUJFVykKyIUYgRvA1wTptmnl95hmzr7ra3GBtfN3swXf4iWAXeAVjSKItQbXlpdXV1VSURymTjUVhdiHN7c29E9Agq5SFxEbcQTGCrxXDg02w+pNm/upXEYj6OczJ5WOJUFc3C0K8IiOBGCHYQG3+pJmvvWaCzjkJOupnlGWfkSBaCp5QVzcHzXD67ARhEMQIxAi+Vgw3N/d3/zjxJ81UypwbVtTPKMs+w8VW8OS6c/speFYviExIiVBXNweMv5CxwfrsBCECiDsoRgg2UJs/aeb8+RGI+hll2We4xL2CJxKZegQhQshIIIYIZoLV38hh9WqzLxy1TrCjknAIxa0T9wqeWB9qCUmFGIE4ZShpZlhRP6Ms+7QJ1a0T9wqeSGTqEYQIEbYRUEqlAgeABq31LUqpYmAbMB44CHxba90V7ucIlxJNaWa0ZZ8QWtrJmtM1NLY18uf3/8z4zPGUXl6K2+WmuaOZu+dEYagSDYZzqCUIQxCJOYEfAEcc208Av9BaXwk0A/LLFnxS11JHtru/LnYwt067p50N+zaQnprOTcU3AfDKB6/Q6e2M2KTwsBCJTD2CECHCGgkopQqArwLrgIeUUgq4EfiGVWQrsAZ4JpzPERKTYN065zrO9Rs5TMqa1Ht+3BgAm+EYaglCACitdegnK1UJrAeygNXACuANaxSAUmoK8Eet9Swf564EVgLk5eXN27ZtW0Cf2dbWxpgxY0JuczyTaH1v97TT2NZIakoqqSoVr/bi7fGSNyaPTFfmJeXPtpylM6UT86xh0FrT3dPN1Oypw9n0ESHRrn+wJHP//fV90aJFB7XWZeHUHfJIQCl1C3BGa31QKVUe7Pla683AZoCysjJdXh5YFdXV1QRaNtFIxL4How564Q8vsD91f7+Rgz0SiHY4iVggnq9/d3c39fX1dNghcUMgOzsbt9sdwVbFD2PGjGH27NmkpaVFvO5w3EELgaVKqSWAGxgLPA3kKKVcWmsPUAA0hN9MIVEJZmFWjjuH5tZmwMwdtHS0xNeEcBJTX19PVlYWRUVF/UZywdDa2kpWVlaEWxb7aK2pr6+nvr6e4uLiiNcf8sSw1vpRrXWB1roIWA68qrX+JrAXuMMqVgHsDLuVQkziDH29Zk30YwtlujJZvWA1uZm51J+vJzczN74mhJOYjo4Oxo8fH7IBSGaUUmRnZ4c1ihqMaKwT+BGwTSm1FngbeDYKnxE3JGqImJGKfBD1kA5C1BADEDrR/O4iEjZCa12ttb7Fev++1vqzWusrtdb/oLXujMRnxCOJHI1TIh8IQmIgsYOiSCLfKIMNfS0IscDp06dZvnw506ZNY968eSxZsoTjx48za9YlAsaA2LJlCx9//HFYbXr99deZO3cuLpeLysrKsOoKBQkbEUUSOUSMRD4QooovP2qYk6Jaa2677TYqKiqwJemHDx+msbEx5Dq3bNnCrFmzyM/PD/gcj8eDy9V36y0sLGTLli1ssFeRDzMyEogisR6NMxyinVtYSGL8+FFTamvDqnbv3r2kpaVx77339u6bPXs2U6ZM6d3esmUL3//+93u3b7nlFqqrq/F6vaxYsYJZs2Zx3XXX8Ytf/ILKykoOHDjAN7/5TUpLS2lvb+fgwYN84QtfYN68eXz5y1/m1KlTAJRRuCGqAAAO10lEQVSXl/Pggw9SVlbG008/3a9dRUVFlJSUkJIyMrdjGQlEkUQOETNcQeaEJMRPVqPUqipYsCDkamtra5k3b15I5x46dIiGhgZqLUN07tw5cnJy2LhxIxs2bKCsrIzu7m7uv/9+du7cyWWXXcaLL77IY489xnPPPQdAV1cXBw4cCLn90UKMQBRJ9BulRD4QooIfP2rKBx+MTHuAK664gvfff5/777+fr371q3zpS1+6pMyxY8eora1l8eLFAHi9XiZNmtR7/M477xy29gaDGIEo47xR2m7Op55KPLloIspghRHCz4RTz0DDECQzZ84ccuLV5XLR09PTu21r83Nzczl8+DC7d+9m06ZNbN++vfcJ30ZrzcyZM9m3b5/PukePHg3AY489xssvvwyYEcZII3MCw0SiykUTtV/CCOJnwsk7MHl2kNx44410dnayefPm3n01NTWcPHmyd7uoqIhDhw7R09PDyZMnefPNNwH45JNP6OnpYdmyZaxdu5a33noLgKysLFpbWwG4+uqraWpq6jUC3d3dvPPOO5e0Y926dRw6dCgmDACIERg2ElUumqj9EkYQP6G2e0KUcdoopXjppZfYs2cP06ZNY+bMmTz66KNcfvnlvWUWLlxIcXExM2bM4IEHHmDu3LkANDQ0UF5eTmlpKd/61rdYv349ACtWrODee++ltLQUr9dLZWUlP/rRj5g9ezalpaX85S9/GbJdf/3rXykoKOB3v/sd99xzDzNnzgyrn8Ei7qBhIlHloonaL2GE8TXhZD1xh0N+fj7bt2+/ZL894auU4vnnn/d5rv3072TZsmUsW7asd7u0tJTXX3/9knLV1dV+2/SZz3yG+vr6oZoeNWQkMEwkqlw0UfslCMmCGIFhIlF19YnaL0FIFsQdNEwkqlw0UfsVMUQ6JcQ4YgSGkUTV1Q/WL19JY4CAE8nENSMValUQgkDcQULUqDldw4Z9G2hub6ZgbAHN7c089upj/PjVH/fbt2HfBmpOJ6CmVKRTQhwgRkCIGjuO7uhNDJ+iUsjNzOXMhTM0XWjqty/XncuOowl4Y5RQq0IcIEZAiBp1LXVku/vfBDs9nXR6+6eYyHZnU9eSgDdGkU7FHLEYSvrJJ59kxowZlJSUcNNNN/HRRx+FVV+wiBEQokZhdiEtHf1vghmuDDJSM/rta+looTA7AW+MIp0KmZrTNaypXsNdO+9iTfWaiLgL7VDS5eXlnDhxgoMHD7J+/fqwQ0kHawQ8Hk+/7Tlz5nDgwAFqamq44447ePjhh0NuTyiIERCixu3X3E5zRzPN7c306B6a25uZOHoil42+rN++5o7m3gnjhMLPyleZFB4cX3NJG/ZtoLYpMUNJL1q0iFGjRgEwf/78YV84JuogIWqUXF7C6gWr+ymB1s1ZB/RXB9095+7EVAdB4krCoohzLgnofa16r4oFVyR2KOlnn32Wm2++OaQ2hkrIRkApNQX4NZAHaGCz1vpppdQ44EWgCPgQ+LrWujn8pgrxiL/E8Al70xfCpq6ljoKx/WORZLuz+eBsYoeS/u1vf8uBAwd47bXXItv4IQjHHeQBfqi1ngHMB76nlJoBPAK8orWeDrxibQuCIASEr7mklo4WCrLCDyV98ODBQcsMFUq6vLycTZs28d3vfveSc+1Q0naE0L/97W/86U9/6j3uDCVdWlpKaWlp77E9e/awbt06qqqqyMjIuKTuaBKyEdBan9Jav2W9bwWOAJOBW4GtVrGtwNfCbaQgCMmDr7mk5o5mlk5PzFDSb7/9Nvfccw9VVVVMnDgxrD6GQkTmBJRSRcAcYD+Qp7U+ZR06jXEX+TpnJbASIC8vb9Aoe07a2toCLptoJHPfQfofz/3Pzs7uvVkORfHoYu6bfR9V71XxwdkPKMgqYPns5Vw77tqA6/DHb37zGx555BHWr1+P2+2msLCQn/3sZ/T09NDa2kpJSQkFBQVcc801XH311cyePZuLFy9y/PhxVq1a1TtK+OlPf0prayt33nknK1euJDMzkz179rB161ZWr17N+fPn8Xg8rFq1isLCQrxeLxcuXPDZ/oceeojW1tbeaKQFBQW8+OKL/cp4vV46Ojqicv2V1jq8CpQaA7wGrNNa71BKndNa5ziON2utc/3XAGVlZTrQ3JvV1dWUl5eH0+S4JZn7DtL/eO7/kSNHuPbaa8Oqo7W1laysrAi1KL5obW2lvr7+ku9QKXVQa10WTt1hjQSUUmnAfwLPa63tJZ+NSqlJWutTSqlJwJlwPiOekFhhgiDEGyHPCSilFPAscERr/aTjUBVQYb2vAHaG3rz4QdIsCoIQj4SjDloIfBu4USl1yPpbAvwMWKyUeg/4orWd8EisMEEQ4pGQ3UFa6/8BlJ/DN4Vab7wiaRYFQYhHJGxEhJBYYYIgxCNiBCKExAoTBCEeESMQISRWmCDEPrEYSnrTpk1cd911lJaWcv311/Puu++GVV+wSAC5CCKxwgQhMviSWxcXh1enHUq6oqKCbdu2AXD48OGwQ0nPmjWL/Pz8gM/xeDy4XH233m984xu9kU2rqqp46KGH2LVrV8htChYZCQiCEFP4k1vX1oZ3u4rVUNJjx47tfX/hwgWM+n74kJGAIAgxhVNuDX2vVVWpLAg9knRMh5L+5S9/yZNPPklXVxevvvpqaB0MERkJCIIQU/hLzVxfP3K3K2co6V27dvV7erdxhpIuLS1l7dq1/RLEDBZK+nvf+x4nTpzgiSeeYO3atVHpgz9kJJCASPgKIZ4pLDQuoFxHxLGWFigo6PF/UgDMnDmTysrKQcsMFUp69+7dbNq0ie3bt/c+4dvYoaTtKKIDcYaSfvnllwF6I4naLF++nPvuuy+4joWJjAQSDAlfIcQ7/uTWS5d6w6o3VkNJv/fee73HXn75ZaZPnx5WP4NFRgIJhj9/6o4dMhoQ4gNbbu0czd59NxQXhzcSUErx0ksv8eCDD/LEE0/gdrspKiriqaee6i2zcOFCiouLmTFjBtdeey1z584FoKGhge985zu9o4T169cDsGLFCu69914yMzPZt28flZWVPPDAA7S0tODxeHjwwQeZOXPmoO3auHEje/bsIS0tjdzcXLZu3Tpo+UgjRiDBkPAVQiLgS24dZioBAPLz89m+ffsl++0JX6UUzz//vM9z7ad/J8uWLevNAwBQWlrK66+/fkm5wfIADFQLDTfiDkowJHyFIAjBIEYgwZDwFYIgBIMYgQRDwlcIsUq4WQyTmWh+dzInkIBI+Aoh1nC73Zw9e5bx48cP+4rYeEdrTUtLC263Oyr1ixEQBCHqFBQUUF9fT1NTU8h1dHR0RO1GGOtcuHCB2bNnR6VuMQKCIESdtLQ0isOMAFddXc2cOXMi1KL4orq6mrS0tKjULXMCgiAISYwYAUEQhCRGjIAgCEISo2JBtqWUagI+CrD4BOCTKDYnlknmvoP0X/qfvP331/epWuvLwqk4JoxAMCilDmity0a6HSNBMvcdpP/S/+TtfzT7Lu4gQRCEJEaMgCAIQhITj0Zg89BFEpZk7jtI/6X/yUvU+h53cwKCIAhC5IjHkYAgCIIQIcQICIIgJDFxYwSUUl9RSh1TSv1dKfXISLcnUiilpiil9iql3lVKvaOU+oG1f5xS6s9Kqfes11xrv1JK/Zv1PdQopeY66qqwyr+nlKoYqT4Fi1IqVSn1tlLqD9Z2sVJqv9XHF5VS6db+DGv779bxIkcdj1r7jymlvjwyPQkepVSOUqpSKXVUKXVEKbUgya79P1u/+1ql1AtKKXciX3+l1HNKqTNKqVrHvohdb6XUPKXU36xz/k0FErJVax3zf0AqcAK4AkgHDgMzRrpdEerbJGCu9T4LOA7MAH4OPGLtfwR4wnq/BPgjoID5wH5r/zjgfes113qfO9L9C/A7eAj4v8AfrO3twHLr/SbgPuv9KmCT9X458KL1fob1m8gAiq3fSupI9yvAvm8Fvmu9TwdykuXaA5OBD4BMx3VfkcjXH7gBmAvUOvZF7HoDb1pllXXuzUO2aaS/lAC/uAXAbsf2o8CjI92uKPV1J7AYOAZMsvZNAo5Z7/8d+EdH+WPW8X8E/t2xv1+5WP0DCoBXgBuBP1g/3k8A18BrD+wGFljvXVY5NfD34CwXy39AtnUTVAP2J8u1nwyctG5mLuv6fznRrz9QNMAIROR6W8eOOvb3K+fvL17cQfaPxabe2pdQWMPbOcB+IE9rfco6dBrIs977+y7i9Tt6CngY6LG2xwPntNYea9vZj94+WsdbrPLx2vdioAn4P5Y77D+UUqNJkmuvtW4ANgB1wCnM9TxI8lx/m0hd78nW+4H7ByVejEDCo5QaA/wn8KDW+rzzmDZmPeG0vEqpW4AzWuuDI92WEcKFcQ08o7WeA1zAuAN6SdRrD2D5vm/FGMN8YDTwlRFt1AgzEtc7XoxAAzDFsV1g7UsIlFJpGAPwvNZ6h7W7USk1yTo+CThj7ff3XcTjd7QQWKqU+hDYhnEJPQ3kKKXshEfOfvT20TqeDZwlPvsO5kmtXmu939quxBiFZLj2AF8EPtBaN2mtu4EdmN9Eslx/m0hd7wbr/cD9gxIvRuCvwHRLNZCOmRSqGuE2RQRr9v5Z4IjW+knHoSrAnvWvwMwV2Pv/yVIOzAdarKHkbuBLSqlc6wnrS9a+mEVr/ajWukBrXYS5pq9qrb8J7AXusIoN7Lv9ndxhldfW/uWWeqQYmI6ZIItptNangZNKqautXTcB75IE196iDpivlBpl/R/Y/U+K6+8gItfbOnZeKTXf+j7/yVGXf0Z6kiSIyZQlGOXMCeCxkW5PBPt1PWb4VwMcsv6WYHydrwDvAXuAcVZ5BfzS+h7+BpQ56roL+Lv1952R7luQ30M5feqgKzD/xH8HfgdkWPvd1vbfreNXOM5/zPpOjhGAIiJW/oBS4IB1/X+PUXskzbUH/hdwFKgFfoNR+CTs9QdewMx/dGNGgndH8noDZdZ3eQLYyADRga8/CRshCIKQxMSLO0gQBEGIAmIEBEEQkhgxAoIgCEmMGAFBEIQkRoyAIAhCEiNGQBAEIYkRIyAIgpDE/H+y39AeL8ogDwAAAABJRU5ErkJggg==\n"
},
"metadata": {
"needs_background": "light"
}
}
]
},
{
"cell_type": "markdown",
"source": [
"# Hierarchical Clustering\n",
"\n",
"1. Begin with $n$ observations and a measure (such as Euclidean distance) of all the ${n \\choose 2} = n(n-1)/2$ pairwise dissimilarities. Treat each observation as its own cluster.\n",
"\n",
"2. For $i = n,n-1,\\ldots, 2$:\n",
"\n",
" (a) Examine all pairwise inter-cluster dissimilarities among the $i$ clusters and identify the pair of clusters that are least dissimilar ( that is, most similar). Fuse these two clusters. The dissimilarity between these two clusters indicates the height in the denogram at which the fusion should be placed. \n",
"\n",
" (b) Compute the new pairwise inter-cluster dissimilarities among the $i-1$ remaining clusters \n",
"\n",
"\n",
"---------------------------------\n",
"\n",
"The above mentioned algorithm is simple enough, but one issue has not been addressed. \n",
"- We have a concept of the dissimilarity between paris of observations, but how do we define the dissimilarity between two clusters if one or both of the clusters contains multiple observations ?\n",
"\n",
"- The concept of dissimilarity between a pair of observations needs to be extended to a pair of *groups of observations*. This extension is achieved by developing the notion of *linkage*, which defines the dissimilarity between two groups of observations. \n",
"\n",
"- The four most common types of linkage - *complete,average,single and centroid*.\n",
"\n",
"For our implementation, we will consider the **Complete Linkage**\n",
"\n",
"**Complete Linkage** : Maximal intercluster dissimilarity. Compute all pairwise dissimilarities between the observations in cluster $A$ and the observations in cluster $B$, and record the largest of these dissimilarities. \n"
],
"metadata": {
"id": "31SiPB9UNXTo"
}
},
{
"cell_type": "markdown",
"source": [
"### Example : Agglomerative Hierarchical Clustering\n",
"\n",
"[Source](https://online.stat.psu.edu/stat555/node/86/)\n",
"\n",
"Clustering starts by computing a distance between every pair of units that you want to cluster. A distance matrix will be symmetric. The table below is an example of a distance matrix. Only the lower triangle is show, because the upper triangle can be filled in my reflection.\n",
"\n",
"\\begin{align}\n",
"\\begin{array}{|c|} \\hline\n",
" & 1 & 2 & 3 & 4 & 5\\\\ \\hline\n",
"1 & 0 & & \\\\\n",
"2 & 9 & 0 \\\\\n",
"3 & 3 & 7 & 0 \\\\ \n",
"4 & 6 & 5 & 9 & 0\\\\\n",
"5 & 11 & 10 & 2 & 8 & 0\\\\ \\hline\n",
"\\end{array}\n",
"\\end{align}\n",
"\n",
"- Now let's start clustering. The smallest distance is between three and five and they get linked up or merged first into a cluster '35'.\n",
"\n",
"- To obtain the new distance matrix, we need to remove the 3 and 5 entries and replace with by entry '35'.\n",
"- Since we are using complete linkage clustering, the distance between '35' and every other item is the maximum of the distance between this item and 3 and this item and 5.\n",
"\n",
" - for example : $d(1,3) = 3, d(1,5)=11 => D(1,\"35\")=11$\n",
" This gives us the distance matrix. The items in with the smallest distance get clustered next.\n",
"\n",
"\\begin{align}\n",
"\\begin{array}{|c|} \\hline\n",
" & 35 & 1 & 2& 4 \\\\ \\hline\n",
"35 & 0 & & \\\\\n",
"1 & 11 & 0 \\\\\n",
"2 & 10 & 9 & 0 \\\\ \n",
"4 & 9 & 6 & 5 & 0\\\\ \\hline\n",
"\\end{array}\n",
"\\end{align}\n",
"\n",
"Similarly\n",
"\n",
"Now, we combine $2 \\text{ & } 4$\n",
"\n",
"\\begin{align}\n",
"\\begin{array}{|c|} \\hline\n",
" & 35 & 24 & 1 \\\\ \\hline\n",
"35 & 0 & & \\\\\n",
"24 & 10 & 0 \\\\\n",
"1 & 11 & 9 & 0 \\\\ \\hline\n",
"\\end{array}\n",
"\\end{align}\n",
"\n",
"Now we combine $'24' \\text{ with } 1$\n",
"\n",
"\\begin{align}\n",
"\\begin{array}{|c|} \\hline\n",
" & 35 & 241 \\\\ \\hline\n",
"35 & 0 & & \\\\\n",
"241 & 11 & 0 \\\\ \\hline\n",
"\\end{array}\n",
"\\end{align}\n",
"\n",
"The above results is summarized below. On this plot, the y-axis shows the distance between the objects at the time they were clustered. This is called the **Clustered Height**. \n",
"\n",
"\n",
"\n"
],
"metadata": {
"id": "EV4cCITlduWp"
}
},
{
"cell_type": "markdown",
"source": [
""
],
"metadata": {
"id": "cpuYVIq_jtnx"
}
},
{
"cell_type": "markdown",
"source": [
"**Determining Clusters**\n",
"\n",
"One of the problems with hierarchical clustering is that there is no objective way to say how many clusters there are. \n",
"If we cut the single linkage tree at the point shown, we would say we have two clusters. \n"
],
"metadata": {
"id": "T09L2-HvjxjY"
}
},
{
"cell_type": "markdown",
"source": [
""
],
"metadata": {
"id": "DABXLpR6Su5o"
}
},
{
"cell_type": "markdown",
"source": [
"However, if we cut the tree lower we might say that there is one cluster and two singletons."
],
"metadata": {
"id": "LnrdewEJS8mr"
}
},
{
"cell_type": "markdown",
"source": [
""
],
"metadata": {
"id": "YhT_LApITJQj"
}
},
{
"cell_type": "markdown",
"source": [
"\n",
"\n"
],
"metadata": {
"id": "x1dITj_HTKaY"
}
},
{
"cell_type": "code",
"source": [
"# to run the code on the data set above and then a little larger data set \n",
"\n",
"class HierarchicalClustering:\n",
"\n",
" def __init__(self,arr):\n",
" self.arr = arr\n",
" self.n = len(self.arr)\n",
" self.stagearr = np.zeros([2,self.n])\n",
" l = int(np.ceil(self.n/2))\n",
" print(\"l\",l)\n",
" self.clusters = np.empty(l,dtype=object)\n",
" self.clusterCounter = 0\n",
" \n",
" #def euclideanDist(self)\n",
" \n",
" def CompleteLinkage(self):\n",
"\n",
" # call the EuclideanDist Function\n",
" # For this example, we are skipping that step\n",
"\n",
"\n",
" self.arr = np.where(self.arr == 0, 100, self.arr)\n",
"\n",
" for k in range(len(self.arr),2,-1):\n",
"\n",
" print(\"k\",k)\n",
" \n",
" \n",
" self.pos = np.where(self.arr == np.min(self.arr))[0]\n",
"\n",
" print(\"self.pos\",self.pos)\n",
"\n",
" # First calling the cluster function, to save the newly groups \n",
" # cluster \n",
" \n",
" self.storeclusters()\n",
"\n",
" self.stagearr = self.arr[self.pos,:]\n",
"\n",
" #2 Delete statement one row and one column\n",
" self.arr[self.pos,:] = 100\n",
" self.arr[:,self.pos] = 100\n",
" print(\"self.arr\",\"\\n\",self.arr)\n",
" #self.arr = np.delete(self.arr,self.pos,axis=1)\n",
" #self.arr = np.delete(self.arr,self.pos,axis=0)\n",
" \n",
" # deleting the present cluster indexes from the stage arr\n",
" print(\"stagearr\",\"\\n\",self.stagearr)\n",
" self.stagearr[:,self.pos] = 100\n",
" \n",
" \n",
" print(\"After placeete\",self.stagearr)\n",
" self.arr[self.pos,:] = self.stagearr\n",
" self.arr[:,self.pos] = self.stagearr.T\n",
" newrow = np.max(self.stagearr,axis=0)\n",
" newrow = newrow.reshape(len(self.stagearr[1]),1)\n",
"\n",
" #self.arr = np.hstack((self.arr, newrow))\n",
"\n",
" newrow = np.append(newrow,100)\n",
" #self.arr = np.vstack((self.arr, newrow.T))\n",
" \n",
"\n",
" print(\"self.arr\")\n",
" print(self.arr)\n",
" \n",
" \n",
" def storeclusters(self):\n",
" \n",
" print(\"we are in clusters \")\n",
" is_looping = True\n",
"\n",
" # When no clusters are created yet.\n",
" if self.clusterCounter == 0:\n",
" self.clusters[0] = self.pos\n",
" is_looping = False\n",
"\n",
" else:\n",
" i = 0\n",
" while i < self.clusterCounter:\n",
" \n",
" for j in range(0,2):\n",
" print(\"j0\",j)\n",
" print(\"i\",i)\n",
" \n",
" if self.clusters[i] is None:\n",
" self.clusters[i] = self.pos\n",
" is_looping = False\n",
" break\n",
" elif any(x in self.pos for x in self.clusters[i]):\n",
" self.clusters[i] = np.append(self.clusters[i],self.pos)\n",
" print(\"elIf\", self.clusters )\n",
" is_looping = False\n",
" break\n",
" else:\n",
" continue\n",
"\n",
" if is_looping is False:\n",
" break \n",
" else:\n",
" i+=1\n",
" \n",
" \n",
" # Case when none of the existing clusters contain any of the \n",
" # 2 new cluster values.\n",
" if is_looping is True:\n",
" self.clusters[self.clusterCounter+1] = self.pos\n",
" \n",
"\n",
" self.clusterCounter +=1\n",
" print(\"Cluster Counter\",self.clusterCounter)\n",
" print(\"Cluster\",self.clusters)\n",
" return self.clusters\n",
"\n"
],
"metadata": {
"id": "88MG6dsijudS"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"f = HierarchicalClustering(x)\n",
"f.CompleteLinkage()\n",
"#f.clusters()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 426
},
"id": "51XYPvwTm-YV",
"outputId": "05e5c49a-0846-42d4-dda6-6b24b3cdd2bc"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"l 13\n",
"k 25\n",
"self.pos [9]\n",
"we are in clusters \n",
"Cluster Counter 1\n",
"Cluster [array([9]) None None None None None None None None None None None None]\n"
]
},
{
"output_type": "error",
"ename": "IndexError",
"evalue": "ignored",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mIndexError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m<ipython-input-33-c130cb51fea9>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0mf\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mHierarchicalClustering\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mf\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mCompleteLinkage\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[0;31m#f.clusters()\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;32m<ipython-input-29-acaeabce0c99>\u001b[0m in \u001b[0;36mCompleteLinkage\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m 40\u001b[0m \u001b[0;31m#2 Delete statement one row and one column\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 41\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0marr\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpos\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m100\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 42\u001b[0;31m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0marr\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpos\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m100\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 43\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"self.arr\"\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\"\\n\"\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0marr\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 44\u001b[0m \u001b[0;31m#self.arr = np.delete(self.arr,self.pos,axis=1)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mIndexError\u001b[0m: index 9 is out of bounds for axis 1 with size 2"
]
}
]
},
{
"cell_type": "code",
"source": [
"import random\n",
"random.seed(2)\n",
"x = np.random.normal(10,5,50).reshape(25,2)\n",
"x[0:25,0] = x[0:25,0]+ 3\n",
"x[0:25,1] = x[0:25,1]-4\n",
"print(x)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "ToWQFpFE6RpK",
"outputId": "338d15d5-dc4d-4bc1-b0a2-de0ff8217202"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[[ 5.34527179 9.4738194 ]\n",
" [12.45726243 9.7374621 ]\n",
" [11.94022622 12.54273861]\n",
" [18.64258696 12.94332958]\n",
" [14.15161936 10.44465552]\n",
" [ 6.60958318 3.50734521]\n",
" [16.57726073 8.24986018]\n",
" [15.59865107 6.19294276]\n",
" [ 4.85377854 9.50420034]\n",
" [13.48193936 -0.30374516]\n",
" [24.95740923 4.15751527]\n",
" [23.04742754 14.06541976]\n",
" [ 8.23589844 13.4393038 ]\n",
" [15.08959773 10.02123544]\n",
" [ 7.55952291 11.11464924]\n",
" [13.06392298 3.96984672]\n",
" [16.07720439 4.52031749]\n",
" [10.04113041 8.9965649 ]\n",
" [12.05649419 6.48268752]\n",
" [17.24744721 15.21122072]\n",
" [14.23036583 9.28744381]\n",
" [ 5.97560551 1.52259464]\n",
" [10.92930899 6.17710445]\n",
" [15.94983823 3.40697168]\n",
" [15.79299311 1.98262685]]\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"import scipy.cluster.hierarchy as sch\n",
"dendrogram = sch.dendrogram(sch.linkage(x, method='ward'))"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 271
},
"id": "rvkctGrj5UzD",
"outputId": "47be6da1-a2cd-4daf-8be2-9f1eeb4ddc8b"
},
"execution_count": null,
"outputs": [
{
"output_type": "display_data",
"data": {
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
],
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXIAAAD+CAYAAAAnIY4eAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAZ4UlEQVR4nO3de5xkZX3n8c9vuEZGcGTGGQaBiTKCIFIDI3el8YKAMXjNhgm3aGhMYAOJlxgTk2w0u2jWSxIT1yawELFBFFEx6oYQO8ZdV3dGOlyz0XXRRZhhsnlt4mx2Ny+TZ/94nnbOFHU5VV3V3afn8369+tV1Tp2nzlPn8j3PeerUqUgpIUlqrhWLXQFJ0vwY5JLUcAa5JDWcQS5JDWeQS1LD7buQM1u9enXasGHDQs5Skhpv27Ztf5NSWtPt+QUN8g0bNrB169aFnKUkNV5EfKfX83atSFLDGeSS1HAGuSQ1nEEuSQ1nkEtSwxnkktRwBrkkNZxBLkkNt6BfCFpqpqZgenqxayE1w5YtMDm52LVQJ3t1i3x6GmZnF7sW0tI3O2ujZynbq1vkAK0WzMwsdi2kpW1iYrFroF726ha5JC0HBrkkNZxBLkkNZ5BLUsMZ5JLUcAa5JDWcQS5JDWeQS1LDGeSS1HAGuSQ1nEEuSQ1nkEtSwxnkktRwBrkkNVzfII+IIyLiSxHxUEQ8GBHXlPG/ERHfi4jZ8nfB+KsrSWpX537kPwDenFL6RkQ8FdgWEXeX5z6QUvq346ueJKmfvkGeUnoceLw8/n5EPAwcPu6KSZLqGaiPPCI2AJuAr5VRV0fEfRFxY0Ss6lJmMiK2RsTWnTt3zquykqQnqx3kEbESuAO4NqX098CHgWcDLXKL/X2dyqWUplJKm1NKm9esWTOCKkuSqmoFeUTsRw7xj6WUPgWQUtqRUvqnlNI/A9cDp4yvmpKkbupctRLADcDDKaX3V8YfVpns1cADo6+eJKmfOletnAlcAtwfEbNl3DuAiyKiBSTgEeDKsdRQktRTnatWvgJEh6c+P/rqSJIG5Tc7JanhDHJJajiDXJIaziCXpIYzyCWp4QxySWo4g1ySGs4gl6SGM8glqeEMcklqOINckhrOIJekhjPIJanhDHJJajiDXJIaziCXpIYzyCWp4QxySWo4g1ySGs4gl6SGM8glqeH2XewKSE01NQXT04tdi4UxO5v/T0wsajUW1JYtMDm52LWoxxa5NKTp6d0Bt9y1WvlvbzE726yDtC1yaR5aLZiZWexaaNSaduZhi1ySGs4gl6SGM8glqeEMcklqOINckhqub5BHxBER8aWIeCgiHoyIa8r4p0fE3RHxzfJ/1firK0lqV6dF/gPgzSml44DTgKsi4jjg7cA9KaWNwD1lWJK0wPoGeUrp8ZTSN8rj7wMPA4cDFwI3l8luBl41rkpKkrobqI88IjYAm4CvAWtTSo+Xp7YDa7uUmYyIrRGxdefOnfOoqiSpk9pBHhErgTuAa1NKf199LqWUgNSpXEppKqW0OaW0ec2aNfOqrCTpyWoFeUTsRw7xj6WUPlVG74iIw8rzhwFPjKeKkqRe6ly1EsANwMMppfdXnvoscFl5fBnwmdFXT5LUT52bZp0JXALcHxFz93p7B3AdcHtEvBH4DvAT46miJKmXvkGeUvoKEF2efsloqyNJGpTf7JSkhjPIJanhDHJJajiDXJIaziCXpIYzyCWp4QxySWo4g1ySGs4gl6SGM8glqeEMcklqOINckhrOIJekhjPIJanhDHJJajiDXJIaziCXpIYzyCWp4QxySWo4g1ySGs4gl6SGM8glqeEMcklqOINckhrOIJekhjPIJanhDHJJajiDXJIarm+QR8SNEfFERDxQGfcbEfG9iJgtfxeMt5qSpG7qtMhvAs7rMP4DKaVW+fv8aKslSaqrb5CnlL4M/O0C1EWSNIT59JFfHRH3la6XVd0miojJiNgaEVt37tw5j9lJkjrZd8hyHwbeBaTy/33AGzpNmFKaAqYANm/enAaZydS2Kabvnx6yiv3Nbv8gABM3XTuW199ywhYmT54cy2tL0pyhgjyltGPucURcD3xuZDWqmL5/mtnts7TWtcbx8rTePp4AB5jdPgtgkEsau6GCPCIOSyk9XgZfDTzQa/r5aK1rMXP5zLhefmwmbppY7CpI2kv0DfKIuBWYAFZHxKPArwMTEdEid608Alw5xjpKknroG+QppYs6jL5hDHWRJA3Bb3ZKUsMZ5JLUcMNefihJjTH12GNM79jRf8JidtfRAEzc+61a029Zu5bJ9euHqtsoGOSSlr3pHTuY3bWL1sqVtaZvXV8vwAFmd+0CMMgladxaK1cys2nTyF934t57R/6agzLItTRMTcH0+L7FOxaz+ZvBTIzvi2Ujt2ULTPolteXGINfSMD0Ns7PQGs+3eMdhptWgAIe8fMEgX4YMci0drRbMzCx2LZaviYnFroHGxMsPJanhDHJJajiDXJIaziCXpIYzyCWp4QxySWo4g1ySGs4gl6SGM8glqeEMcklqOINckhrOIJekhjPIJanhDHJJajiDXJIaziCXpIYzyCWp4QxySWo4g1ySGs4gl6SGM8glqeH6BnlE3BgRT0TEA5VxT4+IuyPim+X/qvFWU5LUTZ0W+U3AeW3j3g7ck1LaCNxThiVJi6BvkKeUvgz8bdvoC4Gby+ObgVeNuF6SpJqG7SNfm1J6vDzeDqztNmFETEbE1ojYunPnziFnJ0nqZt4fdqaUEpB6PD+VUtqcUtq8Zs2a+c5OktRm2CDfERGHAZT/T4yuSpKkQQwb5J8FLiuPLwM+M5rqSJIGVefyw1uBrwLHRMSjEfFG4DrgZRHxTeClZViStAj27TdBSumiLk+9ZMR1kSQNwW92SlLDGeSS1HAGuSQ1nEEuSQ3X98NOSYtgagqmp0f7mrOz+f/ExGhfd8sWmJwc7WtqILbIpaVoenp38I5Kq5X/Rml2dvQHHA3MFrm0VLVaMDOz2LXobdStew3FFrkkNZxBLkkNZ9dKMbVtiun7R9fXN7s9929O3DQxstfccsIWJk/2QyVJe7JFXkzfP/3D8B2F1roWrXWj+2BpdvvsSA80kpYPW+QVrXUtZi6fWexqdDTKlr2k5cUWuSQ1nEEuSQ1nkEtSwxnkktRwBrkkNZxBLkkNZ5BLUsMZ5JLUcAa5JDWcQS5JDWeQS1LDGeSS1HDeNEuSOph67DGmd+zoO93srl0ATNx7b99pt6xdy+T69fOuWztb5JLUwfSOHT8M6V5aK1fSWrmy73Szu3bVOjAMwxa5RmO+v/o+il9499fcNWKtlSuZ2bRpJK9Vp8U+LFvkGo35/ur7fH/h3V9z115sXi3yiHgE+D7wT8APUkqbR1EpNdRi/uq7v+Y+GoOeWQ1zJuWZ08iNomvlnJTS34zgdSQttrkzq7pnR4OeRc0Fv0E+UvaRS9rTOM+sPHMai/kGeQL+JCIS8JGU0lT7BBExCUwCHHnkkfOc3fIwtW1q4B9Snvth6GF+u3PLCVuYPNkWkLRczffDzrNSSicB5wNXRcSL2idIKU2llDanlDavWbNmnrNbHqbvn/5hMNfVWteitW7wDwNnt88OfNCQ1CzzapGnlL5X/j8REXcCpwBfHkXFlrvWuhYzl8+MfT7DtOAlNcvQLfKIOCginjr3GDgXeGBUFZMk1TOfFvla4M6ImHud6ZTSF0dSK0lSbUMHeUrp28CJI6yLJGkIfrNTkhrO68iXgV6XM/a6bNHLEqXlwRb5MtDrcsZuly16WaK0fNgiXyYGvZzRyxKl5cMWuSQ1nEEuSQ1n14q0kOreJnaQ28N6W9i9ni1yaSHV/QGOuj+04Q9qCFvk0sIb5W1ivS2ssEUuSY1nkEtSw9m1IkkjNPXYY0zv2PGk8bO7dgEwce+9HcttWbuWyfXrh5qnQa6la5AfAvZHgLVETO/YweyuXbRWrtxjfPtw1VzIG+RLzLD3PwHvgfJDg/wQsD8CvLi8rHIPrZUrmdm0qfb03VrpdRnkYzJ3/5NO9znp9ZNtcyG/ZIO82w7bbwcddqcc1w8Be7XHaNU96NY94HqgHciSCPJurdemt1yH+Tm3JX8PlG47bK8d1J1y7+BllYtmSQR5t9Zro1uuy9mgO6w7pTRWSyLIwbv3SdKwvI5ckhrOIJekhjPIJanhDHJJargl82GnNBLL9YspC339/kLota56va+l/J4WiUGu5WWYL6Y8/jh0uDcGAH/3d73v+b1QobIcr9/vta66va+l/p4WiUGu5WeY69x37Fj6X/NfjtfvL8f3tAgMcgmG+1aioaIlwg87Janh9qoWuXcklLQc7VUt8rl7unTSWtfqem+X2e2zXQ8AkrTY5tUij4jzgN8B9gH+MKV03UhqNUbL8o6EkvZqQ7fII2If4PeB84HjgIsi4rhRVUySVM98ulZOAb6VUvp2SukfgduAC0dTLUlSXZFSGq5gxOuA81JKP1OGLwFOTSld3TbdJDD3KeExwH8dvrqStFc6KqW0ptuTY79qJaU0BUyNez6StLeaT9fK94AjKsPPLOMkSQtoPkH+X4CNEfGjEbE/8JPAZ0dTLUlSXUN3raSUfhARVwP/gXz54Y0ppQdHVjNJUi1Df9gpSVoa9qpvdkrScmSQS1LDGeR7uYiImtMdNOTrr6s7j8XUhDoudcMuw4UutxwtWpBHxCsj4pohyw60AiPimIg4PSL2K7cWqFPmtIi4pPzff5h6Vl5rLBtcRBwdEZsj4oAhym4ESDU+JImIC4H3RMQzBpzHy4E72fMy1bpla62ntjJHRMT+cwediOi5fUfEWeWLbKSU0nzW0wAHxB8Zdh4Dzmd9dVnUmH5j2ZZWDLrsI+LkiFhRZ1tqK7cO6m2DlTIbIuKQiDhk2HU2jv0xIo6PiLMj4tARvNbg9UspLfgfcC4wC7xsiLKvAH4RWFlz+tcAfwXcA/wR8PPAwX3K/DhwH3Az8Elg44B1PAk4CzhlgDLnA5cOMP2PlTp+CbgVeM4AZV8G7ATeUGPas8vyG2hdVdbxI8DvDFDuOZXH+wy4XTxA/vLZ7cAxZfyKDtOuAFYCDwIPAW+qPldzfqcD5w2yXICXA28FDhygzIuBK4ArBihzHvBV4N8DHwHW9Zn+VcBfAncAHwR+Djio5rzWAf8P+Ciw3wB1PL+sp6MHXH7fIN/j6WPAqprlTi3b8Qsq46JPmZ4Z0eG93Ad8Gvjjfsu7Q/lTgDOBzXXr96TXGGTiUfwBZwA75kIOOAQ4CnhKjbIvAP438C3y1/57hjmwH/Bx4Mwy/Frgt4Hf6raigEPJl1Q+rwzfCLweeEadHZAcsPeSDxq3A1fWKHMA8Bng/wAX1lyGDwObyvAfkC//rLP8zyMH7B8B7+i30ZAPmm8pj9eTDwKnAof0KPPSso6OL+vgT4AX1Vx2/wBMV8b1DHMgyC3++4EJYC3wFuBx4PgyTcdwBt4GvLksi18YYBu+gBx87y077o9X69OlzPmlzESn99CjzAPl/cwAF9Uocw7w1+SGxGbgPcDF3cqU7f0LwHFl+A3k74i8E3hqjWWxCvgi+YB4O7B/jTKnAN8BXtzhuW7raqIsi3OAY8kH7KfNbR89yp0PfLNMfydwQ41l+Jqyrk7t9rpt9fprdufZncBLB9iWXlHm9a/LdviRfvXr+Dp1JxzVH/l+K4+Sb7B1KLlF+fmyEbyuV+XLSjyX3OL9EnAVlTBvX+jkEPkCcPnc8+Qj83uBN3XZsA8BvlzqcjDwbeAuYBp4Nz1aKsAm8pH5xDL8euADNZfLFeQbj/134LI+G+cZc++pDK8htwYOqLHR3QucXMpsp0+LknwGMxfk/4nc+v8ocAtdWkTkltMZ5fHTgN8DfrbPznMQORAmgZuAWyrP9QvzfcqOevjc6wPXkL9p3PVMhXyQ+iDwkvK+3g/8G/LBoduyPwnYCpxeht9NPoN7RmWaaCtzXFmvk2X40LIfnNCjzEHkBsUryvDVwEX0abWRW/yXVIbfRiUcumzvf0ElVIFPkG9PfVG3cm2v8XPkxtgnyrp7IZXWb4fpLwZ+qzxeTw6zSyvPdzqL+pfAOeXxBuAx4APkRszGLstwH/I+dUkZPhj4j8Aneyz3DcBXgLtL2c3dttky/XMr9VpX6vVp8plQvzx7CjmfXlKGjwSeoGajbI/XGrTAKP6AE8kB+Sg5wFaQWwK3Ak/vMP3RwPPLRndoGXcq8GdlA19Zxv1Ih7IvI3/j9IWVlbuFHETdQuV1wDbgPwPvLONeXDbSE3u8rzPY8zT9aODr5BZjt3ntV/5fSA7+k8ktiPeUnelJIVbew8GVx88kB/SaMu7QLvO6gHxjs7nhq8lnHL1a1yeQb3R2G/DTZdyzgH8HvLzPel5R/p9HPmic0Gf69eQuj9XkLq1b+kx/NPks7VDymdfb2p5/W1lnB3Za/sCzgbeXx28mnw38fp95ngKcVh4/nbzj3kU+uP1elzInkwPnZ8qy+NNS37t7lDmo1P0VQIvcRfVx8sH0ji7L4ljymeNRlfGnArdVhp90sCc3am4BLiGfrd4CXEml9dphXpsp+xu59f7W8vhrwD8Dr+yxDCfI3SNHkLtKriMfHG/rMq/nVrb3A8tyeSv5jO+XyI26bmfYv0TlwFbG/QVdDm7kMD27PP41cnZsBvZtm67T9vQrwK+Wx5eT95k1PZbDQeQG7PMq436b3OX3vl7b4ZNea5CJR/lHbqVc3Tbui0CrbdxcX/AMuV+s2oo5jRzmP0kOpY92WOAHluemqJzel3KtHvVbVRbqj1XG3UHlNLoyvtqvOxem+5CPuHdVNsKNncqU4R8Fbi2P3wL8I31CpUy7Lzn87inDPwV8mMpBjdJfXBmeC9hTyoZ6VHV8h3m8ktyi/M3KuOspp+w11/dvAr9Mj9Zu2/SHluV9Sxk+CTi2w3bx58CHyK3iR4Bfrkyzgdwy6nYQXU/uR76CfPD8tbK+ntQd1raO9yE3Pq5i99nT4eRAmehS5kxyC/K/Uc4GyUH2p5RGRocy15JbuV8H3lsZ/3X27GapLouPUrqUynMvAL5WHs8F9T5t7+2Qst3cCLy/Mv5ztAUke34283FgIzlorynv59vk/vlPUukzb3tfJ5bt7leAX6yM/yrw8132/VvZ3VV2TGWaw0q9D+wyr4vJXTJHVsbNNRSO71LmkMrjd5Zt4gVluGdjpG1ZfR44qc+29OvkBu1PlG31Q+SG0vXA02rPq+6E4/4j919vA9ZWxnXtC2b3KfQR5P7Q/wE8v8trryLvdF8gn7pfRj7qre1Tp/PJO/q55KD4BrChw4b9D+zZ6pkLyhVlngeXneizpS6d+oJXAb9bVuhDwK8C/xP4FzWX303kboFt7Hmwm5vXrZVx+1Ye3wDc1ee19wUuJe+kbyx/W4FnD7h+v8JgH2CuLsv/r8hB+8wu28UUuYtjPfDdsuyOJreKttLjQzHyAea7lBYkufvuiC7r+Na28Qe0Dd/A7i6lTtvFKcCrO6y303qUeUpZ9i+tjHsv8Lp++0gZ3kjuFnx92TaO7bEsVlQeX0pu/R9UGddpXlOljt8if351bnnu9sr66rQNvqlsTx+iBBb5DOqne8zr5g51/inyAWxVj2X4LnI+VMP8Nnb3a3eq3/6Vx+8sy/A68oHlGR3q0d5FM5dn69rGz83r45Vx15C32few+wz9M8BhtfeVuhOO64/cMnkDObyOb3uua18wu8PyDOB/tZftMJ/9yTvpbeSdZ1ONuj2N3Ef85+T+yhPbnu/Zr0vuo/8E8IfkQDmuT5nryFcAvLYMn02fT/XL8tuf3NL7Lnu2+nvN64DyfzXwKeCsGsvjJPKHMu9jgJZJpfzttB0Ia5T5Bdq6ZbpsF39cHj+L3EL7A9oOal1e/wjg5Mpw++csvZZh9YD4GvKHhEd1KFM9YFfPlF5bs8xlZd2eUp6/l9Kq67IsPk1poZJb2zvLsui5j1ReY25/PKFtfKd53VUeX0CHD7T7vK8ryPvVtcC/Igf3sf32/TJ8ILlv/i/Z3VJvn1c1mN9Vpr2SfCbwEPksuO8+Uh7PkLvR+m1PB5AbOg9S6TLpV7+26S4mN3pW195PBt0ZR/1HDqIJOrQU6N8XvJ4czoO0DPeh5iVmlTJPpXsfXM9+3bLxPcSep4PtZabL+BXs3kEHu/wotz6ftKPWqN9TyC2BgS6ZGnQdD1luFbkf+flt47ttF4eVcUeRzyK69v0PUsdey5B8sL6KHJTP61HmY22veRk5xGuVYXer8HNtZfrtIxvJDZGuLfEO7/coOjQgesxrdRl3MB0uQezwvqoBexa56+7dbftIv/d1NPlg/dwB5vVq4GfJDatey719H3lOmXfXz8fatocLaOvO7DGv6oFtX/JnKF+nR7dvx9cdxY66EH907gv+XWpe77pAdWzv191IbsEeN0CZVvvGWXPefcOyw7w2kz9pH+jAtsDLtOclnx22i4vJfY1P+uB7TOv4WPKpcdczpw5lnktuTT6rRpnbyvCzyrbR9fK+DsviUnJLtHZf6wDLYW5ef1aG5z6b6bk/Vt7X3OdBzwcOH3AdX0I+e+33fZD2eR1P5YPgmuuqBbyIAVrH89iWnkfuwh24UdW4ux9GxE3kPvFzyf1p9y1ujfYUEavJH5KeWUa9MKW0o2aZ08mtj3NSSo+OuX6nk3eQiXHNayG1bReXp5TuH+O85pbhGeQzyhellLYPWObslNLjNcucWcrU2i4Wch8ZZrm3LYt9qLkNDvO+hplXh/3x7JTSY/3mNYy2+q0Yel6jPsqM648efcFL7Y8O/brjKLOQ9Vuqf4u1XSzUOh6kzEIui/nOayHf196wP461gmN605dT80ObRapfx37dUZdZyPo14W8ht4uFWsfDrqsFXhYDz2sh39fesj82sWsl0hKvdEQcmFL6v+MuM6yFnNdCWejtYqHW8ZBlFmxZDDuvhXxfe8P+2LgglyTtyfuRS1LDGeSS1HAGuSQ1nEEuSQ1nkEtSwxnkktRw/x83htn5LFyP2gAAAABJRU5ErkJggg==\n"
},
"metadata": {
"needs_background": "light"
}
}
]
},
{
"cell_type": "code",
"source": [
"import numpy as np\n",
"g = np.array([[0,9,3,6,11],\n",
" [9,0,7,5,10],\n",
" [3,7,0,9,2],\n",
" [6,5,9,0,8],\n",
" [11,10,2,8,0]])\n"
],
"metadata": {
"id": "LBEd7kFHk-WC"
},
"execution_count": null,
"outputs": []
},
{
"cell_type": "code",
"source": [
"f = [3,5]\n",
"t = [[7,8],[4,5],[6,0]]\n",
"\n",
"any(x in f for x in t[1])\n"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "BV_iy5xEKb4k",
"outputId": "e1ed9a8b-4c15-4d42-a006-ae5d6fbb9d29"
},
"execution_count": null,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"execution_count": 156
}
]
},
{
"cell_type": "code",
"source": [
"import pandas as pd\n",
"import numpy as np\n",
"import seaborn as sns\n",
"import matplotlib.pyplot as plt\n",
"\n",
"\n",
"%cd /content/drive/My\\ Drive/colab_notebooks/machine_learning/data/\n",
"df = pd.read_csv(\"Mall_Customers.csv\")"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "3EU9AawtJFiw",
"outputId": "61991605-1db2-4f77-ec8f-0488340a4116"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"/content/drive/My Drive/colab_notebooks/machine_learning/data\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"df.columns\n",
"df = df.loc[:,['Annual Income (k$)','Spending Score (1-100)']]\n",
"df"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 423
},
"id": "sgTTXhl_hH_5",
"outputId": "5eac8691-05a5-4087-b4db-9edb6e761825"
},
"execution_count": null,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/html": [
"\n",
" <div id=\"df-37c99dde-fe0a-4590-a5c6-3186f2915241\">\n",
" <div class=\"colab-df-container\">\n",
" <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>Annual Income (k$)</th>\n",
" <th>Spending Score (1-100)</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>15</td>\n",
" <td>39</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>15</td>\n",
" <td>81</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>16</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>16</td>\n",
" <td>77</td>\n",
" </tr>\n",
" <tr>\n",
" <th>4</th>\n",
" <td>17</td>\n",
" <td>40</td>\n",
" </tr>\n",
" <tr>\n",
" <th>...</th>\n",
" <td>...</td>\n",
" <td>...</td>\n",
" </tr>\n",
" <tr>\n",
" <th>195</th>\n",
" <td>120</td>\n",
" <td>79</td>\n",
" </tr>\n",
" <tr>\n",
" <th>196</th>\n",
" <td>126</td>\n",
" <td>28</td>\n",
" </tr>\n",
" <tr>\n",
" <th>197</th>\n",
" <td>126</td>\n",
" <td>74</td>\n",
" </tr>\n",
" <tr>\n",
" <th>198</th>\n",
" <td>137</td>\n",
" <td>18</td>\n",
" </tr>\n",
" <tr>\n",
" <th>199</th>\n",
" <td>137</td>\n",
" <td>83</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"<p>200 rows × 2 columns</p>\n",
"</div>\n",
" <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-37c99dde-fe0a-4590-a5c6-3186f2915241')\"\n",
" title=\"Convert this dataframe to an interactive table.\"\n",
" style=\"display:none;\">\n",
" \n",
" <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\"viewBox=\"0 0 24 24\"\n",
" width=\"24px\">\n",
" <path d=\"M0 0h24v24H0V0z\" fill=\"none\"/>\n",
" <path d=\"M18.56 5.44l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94zm-11 1L8.5 8.5l.94-2.06 2.06-.94-2.06-.94L8.5 2.5l-.94 2.06-2.06.94zm10 10l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94z\"/><path d=\"M17.41 7.96l-1.37-1.37c-.4-.4-.92-.59-1.43-.59-.52 0-1.04.2-1.43.59L10.3 9.45l-7.72 7.72c-.78.78-.78 2.05 0 2.83L4 21.41c.39.39.9.59 1.41.59.51 0 1.02-.2 1.41-.59l7.78-7.78 2.81-2.81c.8-.78.8-2.07 0-2.86zM5.41 20L4 18.59l7.72-7.72 1.47 1.35L5.41 20z\"/>\n",
" </svg>\n",
" </button>\n",
" \n",
" <style>\n",
" .colab-df-container {\n",
" display:flex;\n",
" flex-wrap:wrap;\n",
" gap: 12px;\n",
" }\n",
"\n",
" .colab-df-convert {\n",
" background-color: #E8F0FE;\n",
" border: none;\n",
" border-radius: 50%;\n",
" cursor: pointer;\n",
" display: none;\n",
" fill: #1967D2;\n",
" height: 32px;\n",
" padding: 0 0 0 0;\n",
" width: 32px;\n",
" }\n",
"\n",
" .colab-df-convert:hover {\n",
" background-color: #E2EBFA;\n",
" box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
" fill: #174EA6;\n",
" }\n",
"\n",
" [theme=dark] .colab-df-convert {\n",
" background-color: #3B4455;\n",
" fill: #D2E3FC;\n",
" }\n",
"\n",
" [theme=dark] .colab-df-convert:hover {\n",
" background-color: #434B5C;\n",
" box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
" filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
" fill: #FFFFFF;\n",
" }\n",
" </style>\n",
"\n",
" <script>\n",
" const buttonEl =\n",
" document.querySelector('#df-37c99dde-fe0a-4590-a5c6-3186f2915241 button.colab-df-convert');\n",
" buttonEl.style.display =\n",
" google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
"\n",
" async function convertToInteractive(key) {\n",
" const element = document.querySelector('#df-37c99dde-fe0a-4590-a5c6-3186f2915241');\n",
" const dataTable =\n",
" await google.colab.kernel.invokeFunction('convertToInteractive',\n",
" [key], {});\n",
" if (!dataTable) return;\n",
"\n",
" const docLinkHtml = 'Like what you see? Visit the ' +\n",
" '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
" + ' to learn more about interactive tables.';\n",
" element.innerHTML = '';\n",
" dataTable['output_type'] = 'display_data';\n",
" await google.colab.output.renderOutput(dataTable, element);\n",
" const docLink = document.createElement('div');\n",
" docLink.innerHTML = docLinkHtml;\n",
" element.appendChild(docLink);\n",
" }\n",
" </script>\n",
" </div>\n",
" </div>\n",
" "
],
"text/plain": [
" Annual Income (k$) Spending Score (1-100)\n",
"0 15 39\n",
"1 15 81\n",
"2 16 6\n",
"3 16 77\n",
"4 17 40\n",
".. ... ...\n",
"195 120 79\n",
"196 126 28\n",
"197 126 74\n",
"198 137 18\n",
"199 137 83\n",
"\n",
"[200 rows x 2 columns]"
]
},
"metadata": {},
"execution_count": 125
}
]
},
{
"cell_type": "markdown",
"source": [
""
],
"metadata": {
"id": "5q3-dBcjkMno"
}
},
{
"cell_type": "code",
"source": [
"import numpy as np\n",
"\n",
"a = np.array([[1,2,3],[4,6,7],[10,11,12]])\n",
"print(a)\n",
"g = np.square(a - a[:,np.newaxis,:])\n",
"print(g)\n",
"h = np.sum(g,axis=2)\n",
"print(h)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "4W-qM9CrYsFH",
"outputId": "7e8e1465-69fe-41bf-84ea-544a0683bb6c"
},
"execution_count": null,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[[ 1 2 3]\n",
" [ 4 6 7]\n",
" [10 11 12]]\n",
"[[[ 0 0 0]\n",
" [ 9 16 16]\n",
" [81 81 81]]\n",
"\n",
" [[ 9 16 16]\n",
" [ 0 0 0]\n",
" [36 25 25]]\n",
"\n",
" [[81 81 81]\n",
" [36 25 25]\n",
" [ 0 0 0]]]\n",
"[[ 0 41 243]\n",
" [ 41 0 86]\n",
" [243 86 0]]\n"
]
}
]
}
]
}