KNN_Task4_20b030018 .ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "cPP7BfqFSgyH"
   },
   "source": [
    "# K-Nearest Neighbors Algorithm\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Zd0p7ZUpSgyL"
   },
   "source": [
    "![example 1.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAANwAAADHCAYAAABySz3ZAAAABmJLR0QA/wD/AP+gvaeTAAAAB3RJTUUH2gwWARApxkGQoQAAF9dJREFUeJztnXmcFNW1x7/VPcMMyAwIgqgRZREQgoDgRgiCKy/ufoj6NKLG7bnGLTFq3J9L4hqXGPW5JXF5Ji68uC9oXOKuuKPiSnAX2SIqzNz3x+mWpu2ZqZ6u6nOr+nw/n/4w011T9Zuhbp17zz0LGIZhGMnHwf4OVtbWYRipx0E3B87BpdpaDCP1OPiVgyUOFpqVM4wYcdDVwbychVvi4HfamgwjtTg42sHi3IBzOSvXS1uXkXIc9NDWUG1y1u3LgsGWt3LnaGszUo6DlxyM0dZRTRwcVWTdzMoZ8eNgdO5Gu1dbS7XIWbcvSgy2vJU7V1ujkVIcPOigNfdkH6Gtpxo4OMLBojYGXN7K9dbWaaQMB2NyN5dz0OLgDm1NceOg0cHn7Qy2vJU7X1urkTIczMhZt8In+3BtXXHi4PAOrJtZOSN6HKxfYN3yrxYH/6etLS4cNIQYaPnXUgfXaGvWok5bQAo5H+he9F4GmOxgWACzFDTFzXhgEfBWiGObgXEOugTwbbyyjFTjYGwJ61Zo5aZrazSM1ODg4aK1W/FrkYOh2joNI/E4mSa1Zd0Krdxt2loNI/E4eKQD61bopRuirdfQIdAWkAYcjAOeQRwHroPDm4HnAxgbuzDDO8xLGQ3fArsBrSGOzWDeOcMwjMpxkGlvY7/Iwr04BYLbwH3Y8amDJnD/gFE/rVSkYaSIg4EpwLalPiwacEEvWdczsOPzOoABFYozjNTgIAucDvR0sGoAnxQfkynxcy1lXMPWIoaxnN1ZvkY/qdQBpQac4Q+rAFsBBwBnAIMLPlsVmAvMy73OKvrZ+3KfvwHcUvTZesBPkIDqrpGrrkFy1u1sxAvdBZjm5P9oBcxL6QdrABsA67LiwBkH7A+8C3wALCn47FNgJDCf0t7RrYGeQCPQreizNYE9gbWBQcD6wJzcZz2QRf87nf1lapTdWTGGth74DXBY4UFF+3Av7Q7ucr4ffNsWT8Co8Z3XaAC/BaYCTwMzgQvQnapvAFyHDNYngJOBVxT1eI8Tw/U+sHrRR4uBQYE8HAGzcNWiO7A54r0aDmxa8NkJwLEaotrgGURjL2AT4IuCz3oilvN+ZBprCHsATSXer0f+f3+Rf8PWcNXhLGAa8Bwy9ShkWfXlhGIecCfwUcF7PYDtgNeAu4FRCrq8ImfdzqT0gGsA9nHQJ/+GWbhoCYAfAzsCRxW8f1jpwxPH+8DPkCf35qxo/eqQvaJyvNxpYA/aX4J1AY4HjgSzcFGyI/LkPwN4kXT/bZcC9wD/KnhvIuLcOQ3oryGq2uSsW94z2RYNwH756JM03xTV5h1gZ8TCXUe4uMo0MQOYkPv6ccQDmnb2BFYKcVwdspYr6aW8nlALYtcdgndh1LByVaaADZFpwvGIVTNWpB6xgnmakEyK1JCzbkuBr1lxu6YUdcjfoHfRGi57D7SMC3fJAMguKFNn0lkVuBJYBwnheVNXjrcsLfr+ZGBj4ETgoerLiYWuwJZl/kx9HELSTCPwn9hUvDNsCzwPXK0txPCXHsAkbREpIqBGHCptYU/q0gTA3oi3cZKqknThkBC1PH2AI6ih7ama+UXL5JdI0PCWhKu16BkP1UHvMixJdhmM+KDj4yLHIdEsewH7IlPOVGM1TUrTCHxDx/VJPOXV/rDsfeDLjo91WQiaYZTmvbANEo0zHok/TC1m4YS1kbXFI7nvv9aTEhnzCdVbOwD9uMg7gbtI7AMuPLaGk9Ccx5EUGUOPwsHWFUlLSt0MrNYH3HFIJPemwI3KWozldAV2QsLHUtVpp9YH3P8APwJmawsxVmAesq6bgcw+GnTlREctDrguBV9/xvejIgw/cEhy7maIAysV1NqAOxi4VVuEURaFJRsDEr6uq5UBl0Eauuf3e4xksitwAwmeYtbKgBsKrAZMpkStQCMx/BVZ3z1AqC0P/6iVAfc64v7/SluIUREtwCHInl0is+jTvPHdHclTqrWU/1qguAZnYkirheuBVJYqWd89/SxrRSpsLQnxWopU6EoyiXakJJ1uSIjWKco6jOrQB6np2aejA4142B/xSBq1w8FIKlUiHSlpwKYYtccxwN+0RRhGLVGqGKtXZLUFRMQhyHTibW0hhirWPq0KbA/MwhbNxnJ6IdkGRsQMQ2pkDNUWYnhFX6QK9ERtIWmjN/ZHNUqzEfIw9iqxOOlruCVIgwnDKGYuUmaiEVvbV0zSHxSGkRiGIZ050xqWZqSYpAUvdwH+grQIqrXuNFmkuthQ5KEzEFnDdkc6uDQjMaQLgH8j5eYWIz3c3kP6IMxCple1mOV+MnARoUoHxkfSIjLyvcf2VtZRDXoira82R4ocrYV43t4E3kAK1M5n+cCaj5T3a0AGXvfcqycwABmkQ5GB+hkSb/pQ7vVdD+oUcxKwLtIbwgjJEORmSitDgFORYNwPgD8BP0cGSZSsgdx4VyID92XgHGD9iK/jE3VIZedttIUYuvQCDgL+iSTKnkD19xX7A4cDzwIvAb8CVq+yhmowFjhUW4ShwyDgcqRIzsVI/zQfGI6skd8HbgZG6coxqk0/4A6St95sixHAnxFHxlGEa1mrQT2wD+JouQN/HghGzFwN/FpbRAT0RXp/zwb+i+RUnsoAuyH5ZnciljnpZICp2iJ8ZCxygzZqC6mADDLA5iIPji7tH+4tGSS5dw7i8UvKA6MUAeKl3VlbiG+MA7bQFlEBoxCP43TErZ8GVgGuQrYmNlXWUgnjEA9tUh+ARhEHIK797bWFxMSPkBv2JJIbancDsLW2CKMymoHrkSmLV5HqMdAD8WTOQJxbSSOpD4rIGYtERySNoYhX7zSSFzZXCYciXtdNlHUYneRZkrd22wAJvarVSIYNgXeo2VqgyWUSkg2QJLZENoo30haizGDEmbK3so5yOQmYpi1CixuAXbRFlMFUZOtiuLYQT+gHzASO1BZSBhsh8aRpCa4oi5VIzvpnS+BVYE1tIZ7RE5mlHKQtpAwewjyWXrMR4igYrKzDV/og0SlJ2RaZBGylLcIozRBkD2q0thDP+QGyppukrMMbAni3ERZNCP8jLctgzMMxaNkWmUreDjMnQKaMcK6mx2DA1zFoKkUP4Cmknv2MKl0zyYwEbkcSad/TlaJPHXzVF9z9hEs9z0CmB/EsLo8BTpcvg0fBLSBcGYWV4au1kKiOanAVcCE22MLyMlIZ+0YkFMz36sh9gc+JqYRH3jkxn9CdR4I4LMnaSBJk/iaeR/ieZfNj0NMWhwDLgD9W8Zpp4B5ksJ2JPFh95nrgDODhOE7uS+Wr0UjqitMW0g7rI163A7SFJJQTkc3x7bSFdMAtxLgt5cuAux2p5eErdYhVmwYsVNaSVJYhfdbPRrYNfOUWYAdiirP0ZcD5zmHAA0gRGqPzzAEuQGJNfeUzZNM+lrSdpGwwa7IGUmrASgxEw1XAo8gyYqaylra4Oa4T+2DhLsTvSI1zkfXHV9pCUoJDsgsuoQZDqbQHXHekPuLHyjraYgKy3piuLSRlzES2C36mLaQdeiC5jZGiPeAmAY/hb+nt3/Dd3qARMWcCv0T/HmyLE4kh60F7DTcIKcHmI+OQUnH/1BbSJhcxiFZWAWAZb3MMnysrKoc5SL2XqcS4ZqqAB5BooouiPGn+6VJGGJWLsoLW74FrSlyjaxnniKui1/HIU9hPLmIQLczG8SSOJ8kykXNzgy9GHIyP8HRnI1WefVzLPYY4yiLVVoeE2jgkW7cjssi6K2YyH4KrA1pCHLwa0YcLDc+d98GIzxsdLcwmwxb8IqfxAhz1bEGMmh10Ax53MD6IJkl4NtKc5CdIzUufWAwch2wPfBPVSetgxMfIH9Ij1tNOedkPcV/7zbKqTyEPQ2IMzyM6S3cFsu/l24CDJNwDZTAVacfkG3VIbZLIPVSxcRGDuADHefH1AXDQ1cGXDpyDBRFOLTNIqlPs02Ef0PQQTcXPm3pL4EmSEsKVX8u1MpqjeTHGKx2KOJEAmhArFwWtwF+Rcuo+kppSerOQDAHfuBFZUySDC3D8ns3jvESRdXMxWLl1kYecb2SBT4hw0GlZuAakXW61ctjC0ghMBO7TFlIW8a/lDmK5dcvTBJwf0flfR/wIvpWDb0G2LyLzKWgNuG/ws+HfxsBzSGR7MsgyGMfcuE7voCvSJLK4rVYArOskGicKZgCbRXSuKHkVyVqPBM01nI/RJZPxeSugFC3Mpj7WpokH0nbkfDMSaxoFvg64O6huknNN8QhJ6/gZo3fSQaODz4vWbsWvBRFZuZ5IMV0jBn6Mf40uuiE93HyN7as6Dg53sKiDAeccPBPRJZ+m+v3Na4K7iG7uHxWbAPdqi/AFBw0hrFvUVu4yJCs8tWg9zddAmsn7xDpImJEh7It4kr8O8WpG+pZXyiz8tHC+BtiHZi5VicksizORqlyGHv8B3KQtogSfEFGLZa30nGlIcKhPDEXqyyeLW+lLhmlINax+wBcE3EvAn9ied5XVlcssYJi2iBLkyzZ+VOmJfEyL0OJlJMJkjraQ0NzOwTh+S0A9hU9gx1ICvqGVS9mJ4wi8Lj9YSBYp4hO2Jmm1uBMJsK54yWEDbjmfIrVVIkvFiJXpHEUrpxDQ1M5Ri4Gb2JH9qyUrAj5ANpoXaAuJgwBe7Q4tu5fxM9/CetdWcM0s4oJfVME54mABUscixwujIbth+B9vnQmjn45cVSmmMxR4AheqWvYCYCo78kDMqqLiVaRt1L+0hcRBHdAL3OWIt6kjAmTqcm0F1xwO/AG/UnNKJLsGU6D1rJCl3RuQ36k6Aw7OxYUuptqDgIuRAOEksBjatdqJprC3QMj/wFh6C2jTnZIWN4DQJRwy1WlScTn1tDKJoIzlQCur8XfWYLv4Yi4jZBH+ebAnIg0+Xqv0RBr7cM3AvxWu2x7NJGXNsAqrEoQqPVFIK60MiUVP9CzCPwu3GxH1AtQYcJ/g30aiIymJho0so1xnVwC0eBksXooMMbWK8gGNATcbqbrrEwvxbxpTmmf4lPK7DGWRnLPvcP421GjCP4daAxGlbFmgrrCQFTyUHnMKrbQynXAVzfK8xs58UfTeUw5GRKgsKnwccI1EtAyyASc4krQn2cCxhK+5Mp+AAwvfcNKnbQh+1t30ccDNIKLqBBoDrhdwtcJ1O2IJkt3sP9vwMY6f0/GNuYgsp7MDLxW9fz7ykNnM4Z0zpQn/wv6uQiKRKkZjwH0FbKNw3Y74EP9y9NpmJ24nYAekEcqKHtaAhcA8Ag5iuxXrjjgpI7EeYtG7AmdVR3Ao8iFqvlm4yNAIXv6a+MqTV8Is5Gk/W1tIaHbgIW5mLbqwBTAFWIuAj3HcT5a72K5ki63zWO4gygJbORgc+PF7DwLe1hYRJ/kBV4bHKpLeArOR/3Sfpg5vIJHqd3Xux1t1Mi924VtEc4e6c9bth6y4Xs1buZ/Goq88huBnTuJdRFQ6sQ6WfAV1z0AQYuM3yBDNNHRsBOeImjeBTZd/m5kF7gX4nnevBMHK0PpcXMIi5Hy+v6mcBaY4GBiE6y8RJ8OQmYZPZLHut7EwBnhYW0RcOBifK4VQqkTCMudH4udV+GFpC+kPvKItIo3UIwmG2j3zYsHBEw5a26lLssjBQGWZrwA/UNZQzDiiKR+hykhgC20RJbiHaPufeUEH1i3/WuqkzLsW/ZB1dKrR2vgeDOyldO32mIG0QU4bpdZuxdQB2zoYUAU9pZhEEktcJIQRRFfLMEo2BO7XFhElDibkLNjCnJVr7+Wc3k1/Bf520IkMrXCmOiRroA9+RYZnkRCedaDkHlbicOIMWodwAc8Z4OsApserqiSzkdqgnylcuz2OBi4lXIK216yDn/GLf6QGnrSesTF+FuFtgKp3ma05fkSnN7+NTnIJsKe2iBKMBh7VFpF2AmTztZ+2kBqhC/Ae32+H5QP7ABdHeULNLOd6ZCrhYx3I3pCrjGXEzbbIYLtZW0gJXgX+iWSSJJ4uSNiUjxvNawIvYfmC1eBexFlSE2jeUN8iT5AxihraYg5S8m6qtpCUMw554NpMokqcDRyjLaINBgPP4qcnNS3cCmyuLaINfoifJSgqYiB+Fyi9HlljGNEzEnhMW0Q7XAb8XFtErTEceBJby8XB35CkWV95D1g96pPajdQ+ryHriwO0haSMrZG12z3aQtpgXaRshW9NQyOhHj97guVpRjyWfbSFpIQGYCawlraQdmjEv+JKkdEP6ZTis7XdDbhGW0RKOBE4TltErfMgMFlbRAfcj5/VxpLEaOAFImrfa3SeAxGvkM/0RxIkfctITgpNyNR8nLaQDphAksoldpKVSUahlu2BR0hK4w+/uB44XFtECGbiZzBGzXI+fpYI95n9gdvwP4hgfeBFbRHGinQBHsfPdBIf2QwJ4QvTHlmbi4FDtUVUk7HAatoiQtAHSeHZXluI54wD3kLC5JJAE36mCcXGKcB/a4sIyQDEibKRthBPGYxEa9jfx2NWA+aSlC42Eg/4LrCBthDPWBuJ0vE1MNko4FpgP20RZbAJ8D52c+VZDymZvqO2kDKYCOysLUKLnviZlNoew5GqU7tqC1FmU8Tib9rRgZ7xILYeTxxrIk37jtQWosSuiGVbT1tImWyIeFF937IwStAbeAC4BX+b1kdNA+JOfwFZuyWNXwK7aIvwgT1IZomDDBKg+xb+hzFVyjrA80hYno9NNo0yGIPsdSVtPZdnMuIW/zWyWZ4mAmBfpPaLb+2ljAr4X+AQbREV0BdpdfQK6WkSMgqJtLkb/fZWlZCEyJeqMwA4QVtEBExCBt2fSUYkTSl6AhcijpEkTvULqUf2CUdqCzHiowtwLLKxfxHJSfPpBZyK6P4d0ps96RwB3KAtwqgOzcDxSJb7FcAgXTltsioywD4Ezsl9nwZ6I52E+msL8ZkA2AG/yzCUy0rInt07SDb53uhbjwYk4uJ25IFwKnKDpokAqTlpdMDfSWfqRAZZ412DWJO/IGFR1VrUr4SUq7ssd/2bkaiL+ipdv6ZI0u76D4Cn8LcBSBR0RQbbFCQ86nOkDfJDSDTEHMI1VmyPfkhF4YlIrtpAxOt4L7JhP7/C8xvtkKQBB1L7pA/JSeGplCHIft4kxKO2GhIo/WbutTD3WgAsQvo11CF5XT1z/3ZHNqiHIoPrC8RD9zAykF+m8kGcBC4D7gTu0BSRtAEXUBs3R1tkkXqOQ5HB2AMZUD0QZ0wjsBT4EliMDMIFyDpxVu7fpVVXrc9OwElIbt63yloMI9X0Q6biw7WFJJ1J1Fg6vNEpuiBtpI0KOQcJ/TIMowpkEQ9ereafGe3TTVtAGumDtD1K04a4UTnDECdRUmrjGEZisRKGhlFFbgIO0hZRCzQhYVE2d69tvPZcp2ntswj4GAlPSluGtRGef2sLqCUC4HKkU4tROxyB5O0ZCmTxu4WxES1nIHGhtpQwjJg5A3gMiSU1PCAADsNa3KaVyXjuJKk1AuAPwH3oZ1MbRk0QIPlzLyBbB0ZyaQb20RZhhGOCtgCjItZE2gGfoqzDMFLPWsAHwF7aQozOMQWZZma1hRihyJC8rjxGAc1IRMo9pK8MXFpIUxSUgThTjsUq8PrIaGAmsm4zUoY9Sf0hAI5Gug5N0ZUSD0ltBRUlrQVfj0bWdc8paal1GpFSfhsCnyprMarAJKRH9TlYtrBhVIUm4BKktLoRLxsD/8Ai/Q0s+jxO+iDJwm8C2yhrMTykP3AecqMYldMHqbZmicJGSboDpwEfISkhzbpyEkc3rEUUYC7xsCxGatOPRHobJK0ngxbNwK+AN0h+m2LDEyYjzTWM73MNkh41UFuIkR6mIV1p7kW6tNYqGaQ7jWHEThbYDvi1thAF1gROBt5G+s3Z/qWhxnXAiUgvt7SyE3A2MFhbiGGMRNKA3gCuVNZSCVlgE8RT+zSwuq4cw+iY4mI35wEnIOFkvm2yF8fY7otEhBwHjMG8tJ3G/nB6TEA8nOOBJcDOBZ8NQioIf1xFPVvlNIxCpocDkO0QI0JswPnJyYj3sxcSTL1+wWdDkayGz5Dy7q+zfGDUIVExIBZ1HjC34GcPAEYgJQu+AXYt+GwzZKr4MvAatdkLPHZswPlNFuiLRLjkGY9M8Xojg+pI4JXcZ6sDdyODpQW4Gin9nmdPZFDOAWYjeWeGYRjp5P8BB6S3Szw1L4kAAAAASUVORK5CYII=)In this Jupyter Notebook we will focus on $KNN-Algorithm$. KNN is a data classification algorithm that attempts to determine what group a data point is in by looking at the data points around it.\n",
    "\n",
    "An algorithm, looking at one point on a grid, trying to determine if a point is in group A or B, looks at the states of the points that are near it. The range is arbitrarily determined, but the point is to take a sample of the data. If the majority of the points are in group A, then it is likely that the data point in question will be A rather than B, and vice versa.\n",
    "<br>\n",
    "\n",
    "<img src=\"knn/example 1.png\"  height=\"30%\" width=\"30%\">\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "TyGHDf4NSgyM"
   },
   "source": [
    "# Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {
    "id": "iIEvA0xjSgyN"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from math import *\n",
    "import tqdm\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "rc8ruF56SgyO"
   },
   "source": [
    "# How it works?\n",
    "\n",
    "We have some labeled data set $X-train$, and a new set $X$ that we want to classify based on previous classifications\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "rGbvEXbvSgyO"
   },
   "source": [
    "## Seps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "B-nf9G4ZSgyP"
   },
   "source": [
    "### 1. Calculate distance to all neighbours\n",
    "### 2. Sort neightbours (based on closest distance)\n",
    "### 3. Count possibilities of each class for k nearest neighbours \n",
    "### 4. The class with highest possibilty is Your prediction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "LuWwKdFrSgyP"
   },
   "source": [
    "# 1. Calculate distance to all neighbours\n",
    "\n",
    "Depending on the problem You should use different type of count distance method.\n",
    "<br>\n",
    "For example we can use Euclidean distance. Euclidean distance is the \"ordinary\" straight-line distance between two points in D-Dimensional space\n",
    "\n",
    "#### Definiton\n",
    "$d(p, q) = d(q, p) = \\sqrt{(q_1 - p_1)^2 + (q_2 - p_2)^2 + \\dots + (q_D - p_D)^2} = \\sum_{d=1}^{D} (p_d - q_d)^2$\n",
    "\n",
    "#### Example\n",
    "Distance in $R^2$\n",
    "<img src=\"knn/euklidean_example.png\"  height=\"30%\" width=\"30%\">\n",
    "\n",
    "\n",
    "$p = (4,6)$\n",
    "<br>\n",
    "$q = (1,2)$\n",
    "<br>\n",
    "$d(p, q) = \\sqrt{(1-4)^2 + (2-6)^2} =\\sqrt{9 + 16} = \\sqrt{25} = 5 $\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "vlvNZqiJSgyQ"
   },
   "source": [
    "## Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {
    "id": "EvmQi6nsSgyR"
   },
   "outputs": [],
   "source": [
    "def get_euclidean_distance(A, B): \n",
    "    C = np.zeros([A.shape[0], B.shape[0]])\n",
    "    for i in range(A.shape[0]):\n",
    "        for j in range(B.shape[0]):\n",
    "            C[i][j] = sqrt(np.sum((A[i] - B[j]) ** 2))\n",
    "    return C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "GABzTa_0SgyS"
   },
   "source": [
    "## Example Usage"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "W6b8yBSoSgyS",
    "outputId": "91bd6889-b90d-408f-a5f7-8c6cf618223e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X: 2 Exaples in 3 Dimensional space\n",
      "X_train: 4 Exaples in 3 Dimensional space\n",
      "X:\n",
      "[[ 1  2  3]\n",
      " [-4  5 -6]]\n",
      "X_train:\n",
      "[[ 0  0  0]\n",
      " [ 1  2  3]\n",
      " [ 4  5  6]\n",
      " [-4  4 -6]]\n"
     ]
    }
   ],
   "source": [
    "X = np.array([[1,2,3] , [-4,5,-6]])\n",
    "\n",
    "X_train = np.array([[0,0,0], [1,2,3], [4,5,6], [-4, 4, -6]])\n",
    "\n",
    "print(\"X: {} Exaples in {} Dimensional space\".format(*X.shape))\n",
    "print(\"X_train: {} Exaples in {} Dimensional space\".format(*X_train.shape))\n",
    "\n",
    "print(\"X:\")\n",
    "print(X)\n",
    "\n",
    "print(\"X_train:\")\n",
    "print(X_train)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {
    "id": "kB8IZcDpSgyT",
    "outputId": "0ff10c28-0e46-4f62-d18a-ad235246ad75"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Distance between first example from X and first example form X_train: 3.7416573867739413\n"
     ]
    }
   ],
   "source": [
    "## Initialize the distance matrix using the get_euclidean_matrix\n",
    "distance = get_euclidean_distance(X, X_train)\n",
    "## Print Distance between nth example from X and mth from X_train = distance[n - 1][m - 1]\n",
    "print(\"Distance between first example from X and first example form X_train:\", distance[0][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "vbaJfBihSgyT"
   },
   "source": [
    "# 2. Sort neightbours\n",
    "\n",
    "In order to find best fitting class for our observations we need to find to which classes belong observation neightbours and then to sort classes based on the closest distance\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "b1VLHUj2SgyU"
   },
   "source": [
    "## Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {
    "id": "na0G1o_ASgyU"
   },
   "outputs": [],
   "source": [
    "def get_sorted_train_labels(distance_matrix, y):\n",
    "    arranged_label = np.zeros([distance_matrix.shape[0], distance_matrix.shape[1]])\n",
    "    for i in range(distance_matrix.shape[0]):\n",
    "        row = []\n",
    "        for j in range(distance_matrix.shape[1]):\n",
    "            row.append([distance_matrix[i][j], y[j]])\n",
    "        row.sort()\n",
    "        for j in range(distance_matrix.shape[1]):\n",
    "            arranged_label[i][j] = row[j][1]\n",
    "    return arranged_label\n",
    "\n",
    "    \"\"\"\n",
    "    Function sorts y labels, based on probabilities from distances matrix\n",
    "    Args:\n",
    "        distance_matrix (numpy.ndarray): Distance Matrix, between points from X and X_train, size: N1:N2\n",
    "        y (numpy.ndarray): vector of classes of X points, size: N1\n",
    "\n",
    "    Returns:\n",
    "        numpy.ndarray: labels matrix sorted according to distances to nearest neightours, size N1:N2 \n",
    "\n",
    "    \"\"\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "U0I8eltDSgyV"
   },
   "source": [
    "# 3. Count possibilities of each class for k nearest neighbours \n",
    "\n",
    "In order to find best class for our observation $x$ we need to calculate the probability of belonging to each class. In our case it is quite easy. We need just to count how many from k-nearest-neighbours of observation $x$ belong to each class and then devide it by k \n",
    "<br><br>\n",
    "$p(y=class \\space| x)  = \\frac{\\sum_{1}^{k}(1 \\space if \\space N_i = class, \\space else \\space 0) }{k}$ Where $N_i$ is $i$ nearest neightbour\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "j0ZtOC38SgyV"
   },
   "source": [
    "## Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {
    "id": "y2aaG2GdSgyV"
   },
   "outputs": [],
   "source": [
    "def get_p_y_x_using_knn(y, k):\n",
    "\n",
    "    probabilities_matrix = []\n",
    "    for i in y:\n",
    "        d = {}\n",
    "        for j in range(k):\n",
    "            if i[j] in d.keys():\n",
    "                d[i[j]] += 1/k\n",
    "            else:\n",
    "                d[i[j]] = 1/k\n",
    "        probabilities_matrix.append(d)\n",
    "\n",
    "    return probabilities_matrix\n",
    "\n",
    "    \"\"\"\n",
    "    The function determines the probability distribution p (y | x)\n",
    "    for each of the labels for objects from the X\n",
    "    using the KNN classification learned on the X_train\n",
    "\n",
    "    Args:\n",
    "        y (numpy.ndarray): Sorted matrix of N2 nearest neighbours labels, size N1:N2\n",
    "        k (int): number of nearest neighbours for KNN algorithm\n",
    "\n",
    "    Returns: numpy.ndarray: Matrix of probabilities for N1 points (from set X) of belonging to each class,\n",
    "    size N1:C (where C is number of classes)\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ThEbAnXISgyW"
   },
   "source": [
    "# 4. The class with highest possibilty is Your prediction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "_i7NTtN4SgyW"
   },
   "source": [
    "At the end we combine all previous steps to get prediction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "OzK6rY8mSgyW"
   },
   "source": [
    "## Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {
    "id": "DaYqr_i6SgyW"
   },
   "outputs": [],
   "source": [
    "def predict(X, X_train, y_train, k, distance_function):\n",
    "\n",
    "    predictions = []\n",
    "    distance_matrix = distance_function(X,X_train)\n",
    "    probability = get_p_y_x_using_knn(get_sorted_train_labels(distance_matrix, y_train), k)\n",
    "\n",
    "    for i in probability:\n",
    "        predictions.append(max(zip(i.values(), i.keys()))[1])\n",
    "    \n",
    "    return np.array(predictions)\n",
    "    \n",
    "    \"\"\"\n",
    "    Function returns predictions for new set X based on labels of points from X_train\n",
    "    Args:\n",
    "        X (numpy.ndarray): set of observations (points) that we want to label\n",
    "        X_train (numpy.ndarray): set of lalabeld bservations (points)\n",
    "        y_train (numpy.ndarray): labels for X_train\n",
    "        k (int): number of nearest neighbours for KNN algorithm\n",
    "\n",
    "    Returns:\n",
    "        (numpy.ndarray): label predictions for points from set X\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "i9kzyASWSgyX"
   },
   "source": [
    "# Accuracy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "v8bNPTPZSgyX"
   },
   "source": [
    "To find how good our knn model works we should count accuracy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "dgFCnJ14SgyX"
   },
   "source": [
    "## Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {
    "id": "2ySpyThlSgyX"
   },
   "outputs": [],
   "source": [
    "def count_accuracy(prediction, y_true):\n",
    "\n",
    "    accuracy = np.sum(prediction == y_true) / len(prediction)\n",
    "    return accuracy\n",
    "\n",
    "    \"\"\"\n",
    "    Returns:\n",
    "        float: Predictions accuracy\n",
    "\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "b5g7YFY2SgyX"
   },
   "source": [
    "## Example usage"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {
    "id": "uLqCqmJNSgyY",
    "outputId": "37b92373-4f92-4455-fa01-2069a8f04eae"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0. 2.]\n",
      "True classes:[0 2], accuracy 100.0%\n"
     ]
    }
   ],
   "source": [
    "y_true = np.array([0, 2])\n",
    "\n",
    "prediction = predict(X, X_train, [2, 0, 0, 2], 3, get_euclidean_distance)\n",
    "print(prediction)\n",
    "\n",
    "print(\"True classes:{}, accuracy {}%\".format(y_true, count_accuracy(prediction, y_true)  * 100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "--WUpIcxSgyY"
   },
   "source": [
    "# Find best k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "itkcD0DlSgyY"
   },
   "source": [
    "Best k parameter is that one for which we have highest accuracy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "7GYEUBnnSgyY"
   },
   "source": [
    "## Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {
    "id": "Q6OhNBOoSgyY"
   },
   "outputs": [],
   "source": [
    "def select_knn_model(X_validation, y_validation, X_train, y_train, k_values, distance_function):\n",
    "    \"\"\"\n",
    "    Function returns k parameter that best fit Xval points\n",
    "    Args:\n",
    "        Xval (numpy.ndarray): set of Validation Data, size N1:D\n",
    "        Xtrain (numpy.ndarray): set of Training Data, size N2:D\n",
    "        yval (numpy.ndarray): set of labels for Validation data, size N1:1\n",
    "        ytrain (numpy.ndarray): set of labels for Training Data, size N2:1\n",
    "        k_values (list): list of int values of k parameter that should be checked\n",
    "\n",
    "    Returns:\n",
    "        int: k paprameter that best fit validation set\n",
    "    \"\"\"\n",
    "\n",
    "    accuracies = []\n",
    "\n",
    "    for k in tqdm.notebook.tqdm(k_values):\n",
    "        prediction = predict(X_validation, X_train, y_train, k, distance_function)\n",
    "\n",
    "        accuracy = count_accuracy(prediction, y_validation)\n",
    "        accuracies.append(accuracy)\n",
    "\n",
    "    best_k = k_values[accuracies.index(max(accuracies))]\n",
    "\n",
    "    return best_k, accuracies\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "nGtIjD0WSgyY"
   },
   "source": [
    "# Real World Example - Iris Dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "-o6MHMtKSgyZ"
   },
   "source": [
    "\n",
    "<img src=\"knn/iris_example1.jpeg\"  height=\"60%\" width=\"60%\">\n",
    "\n",
    "\n",
    "This is perhaps the best known database to be found in the pattern recognition literature. The data set contains 3 classes of 50 instances each, where each class refers to a type of iris plant. One class is linearly separable from the other 2; the latter are NOT linearly separable from each other. \n",
    "\n",
    "Each example contains 4 attributes\n",
    "1. sepal length in cm \n",
    "2. sepal width in cm \n",
    "3. petal length in cm \n",
    "4. petal width in cm \n",
    "\n",
    "Predicted attribute: class of iris plant. \n",
    "\n",
    "<img src=\"knn/iris_example2.png\"  height=\"70%\" width=\"70%\">\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "SY8oOngQSgyZ",
    "outputId": "084afbad-b82c-417f-f4b5-9dd4cfcc2a0f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iris: 150 examples in 4 dimensional space\n",
      "First example in dataset :\n",
      " Speal lenght: 5.1cm \n",
      " Speal width: 3.5cm \n",
      " Petal length: 1.4cm \n",
      " Petal width: 0.2cm\n",
      "Avalible classes [0 1 2]\n"
     ]
    }
   ],
   "source": [
    "from sklearn import datasets\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "iris = datasets.load_iris()\n",
    "\n",
    "iris_X = iris.data\n",
    "iris_y = iris.target\n",
    "\n",
    "print(\"Iris: {} examples in {} dimensional space\".format(*iris_X.shape))\n",
    "print(\"First example in dataset :\\n Speal lenght: {}cm \\n Speal width: {}cm \\n Petal length: {}cm \\n Petal width: {}cm\".format(*iris_X[0]))\n",
    "\n",
    "print(\"Avalible classes\", np.unique(iris_y))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "-IlKSX7hSgyZ"
   },
   "source": [
    "## Prepare Data\n",
    "\n",
    "In our data set we have 150 examples (50 examples of each class), we have to divide it into 3 datasets.\n",
    "1. Training data set, 90 examples. It will be used to find  k - nearest neightbours\n",
    "2. Validation data set, 30 examples. It will be used to find best k parameter, the one for which accuracy is highest\n",
    "3. Test data set, 30 examples. It will be used to check how good our model performs\n",
    "\n",
    "Data has to be shuffled (mixed in random order), because originally it is stored 50 examples of class 0, 50 of 1 and 50 of 2.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "RA1Q7kCPSgyZ",
    "outputId": "bc8099c4-6777-4363-c49b-584c3b3812dd"
   },
   "outputs": [],
   "source": [
    "from sklearn.utils import shuffle\n",
    "\n",
    "iris_X, iris_y = shuffle(iris_X, iris_y, random_state=134)\n",
    "\n",
    "\n",
    "test_size = 30\n",
    "validation_size = 30\n",
    "training_size = 90\n",
    "\n",
    "X_test = iris_X[:test_size]\n",
    "X_validation = iris_X[test_size:(test_size + validation_size)]\n",
    "X_train = iris_X[(test_size + validation_size):]\n",
    "y_test = iris_y[:test_size]\n",
    "y_validation = iris_y[test_size:(test_size + validation_size)]\n",
    "y_train = iris_y[(test_size + validation_size):]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "r9xJVLzrSgyZ"
   },
   "source": [
    "## Find best k parameter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {
    "colab": {
     "referenced_widgets": [
      "d75bb342c95b4339b20286ed465e89e8"
     ]
    },
    "id": "hbvZBVNBSgya",
    "outputId": "e5665acc-9a29-4094-e5cf-d4d40c1f623f"
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "0f8ca8c732124b0598d8d364bc02ad02",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "  0%|          | 0/47 [00:00<?, ?it/s]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYgAAAEGCAYAAAB/+QKOAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/MnkTPAAAACXBIWXMAAAsTAAALEwEAmpwYAAAxGklEQVR4nO3de5hbd3ng8e+ruUrjuVhje+LLaGwgIXFDCGCcZCFkEgqEtiQl7CXZdpt0+9TdbemWFnYXtt2kDc3DUy5t2SVt12xTmtIS0pTStLiEYDxNFgJxLtiJExw7IXOzHdujGdszmqv07h/nnLFGlkZHlyNpRu/neeaxdM6Rzk8/z5xX53d5f6KqGGOMMZlC1S6AMcaY2mQBwhhjTFYWIIwxxmRlAcIYY0xWFiCMMcZk1VjtApTLunXrdOvWrdUuRsVNTU3R1tZW7WJUndWDw+rBYfVwXr66ePrpp0+r6vps+1ZNgNi6dStPPfVUtYtRcQMDA/T391e7GFVn9eCwenBYPZyXry5EZDDXPmtiMsYYk5UFCGOMMVlZgDDGGJOVBQhjjDFZWYAwxhiTVWABQkTuE5GTIvJ8jv0iIv9LRI6KyEEReWvavttF5Ij7c3tQZTTGGJNbkHcQXwJuXGb/+4GL3Z9dwJ8CiEgUuAu4CtgJ3CUiawMspzHGmCwCCxCq+hgQX+aQm4H71fF9oEtENgLvAx5V1biqjgOPsnygMQGbXUjy1f1DpFKWGt6YelLNiXKbgeG05yPutlzbLyAiu3DuPujp6WFgYCCQgtayycnJwD/3k8cX+JMDs0wMH+GN0YZAz1WsStTDSmD14LB6OK+UuljRM6lVdTewG2DHjh1ajzMnKzFj9NC+o3DgMNHYJfTv6A30XMWymbMOqweH1cN5pdRFNUcxjQLpV5st7rZc202VDI0lABiOJ6pcEmNMJVUzQDwM/II7mulq4IyqHgceAd4rImvdzun3uttMlQzGp9x/LUAYU08Ca2ISka8A/cA6ERnBGZnUBKCqfwbsAX4KOAokgF9098VF5JPAfvet7lbV5Tq7TcCG49MADFmAMKauBBYgVPW2PPsV+LUc++4D7guiXKYwcwspjp1xAoQ1MRlTX2wmtVnW6MQ0qvD69W2cnpxjanah2kUyxlSIBQizrMExp//h2oud9USsmcmY+mEBwizLa1Z65xvWARYgjKknFiDMsobiCVoaQ7ytz8l2Yv0QxtQPCxBmWYNjCWLRCF2RJtpbG+0Owpg6YgHCLGso7gQIEaGvO8LgmAUIY+qFBQiTk6oyHE8Q644AEItGrInJmDpiAcLkFJ+aY2ouSSzqBIjeaISR8WmSltXVmLpgAcLk5KXW8AJELBphLpnixNmZahbLGFMhFiBMTsMZAaIv2gacT95njFndLECYnLxA0Jt2BwE21NWYemEBwuQ0GE/Q09FCa5OzSNDGrlYaQmJDXY2pExYgTE7eEFdPU0OIzV1hS/ttTJ2wAGFyGo4niLn9Dp5YNGJ3EMbUCQsQJquZ+SQnzs4suYMApz/C+iCMqQ8WIExWI+NOmu9Yd3jJ9lg0QnxqjnMz81UqmTGmUixAmKwyh7h6+txZ1dbMZMzqZwHCZDW0GCAu7IMAG+pqTD2wAGGyGhxLEG5qYN2a5iXbvTkRdgdhzOpnAcJklZ7FNV1nuImuSJMFCGPqgAUIk9VwPLF4t5ApFrW038bUg0ADhIjcKCKHReSoiHw8y/4+EdkrIgdFZEBEtqTt+7SIHBKRF0Xkf0nmV1kTGFVlKJ5Y7JDOZENdjakPgQUIEWkA7gXeD2wHbhOR7RmHfRa4X1WvAO4GPuW+9l8B7wCuAC4H3g5cF1RZzVKnJmeZnk9eMILJE7O038bUhSDvIHYCR1X1FVWdAx4Abs44ZjvwHffxvrT9CrQCzUAL0AS8FmBZTZpcQ1w9fdEICynl2MR0JYtljKmwxgDfezMwnPZ8BLgq45gDwC3A54EPAu0i0q2qT4jIPuA4IMAXVPXFzBOIyC5gF0BPTw8DAwNl/xC1bnJysuyf+3vHFgA4fvR5Bk5c+B0iPpYE4B/3PcH27oaynrtYQdTDSmT14LB6OK+UuggyQPjxMeALInIH8BgwCiRF5A3AZYDXJ/GoiFyrqo+nv1hVdwO7AXbs2KH9/f2VKnfNGBgYoNyf+8C3jyDyEre877rFTK7pXh9P8On9+4j2Xkz/zlhZz12sIOphJbJ6cFg9nFdKXQQZIEaB3rTnW9xti1T1GM4dBCKyBviQqk6IyC8D31fVSXffPwPXAEsChAnGYHyKizpaswYHgE1dYRot7bcxq16QfRD7gYtFZJuINAO3Ag+nHyAi60TEK8MngPvcx0PAdSLSKCJNOB3UFzQxmWAsN8QVoCEkbFlrab+NWe0CCxCqugB8GHgE5+L+oKoeEpG7ReQm97B+4LCIvAT0APe42x8CXgaew+mnOKCq/xhUWc1SmetAZGNDXY1Z/QLtg1DVPcCejG13pj1+CCcYZL4uCfxKkGUz2c3MJ3nt7Cx9eQJELBrhG88dr1CpjDHVYDOpzRKLQ1xzTJLz9HVHmEjMc2ba0n4bs1pZgDBLeB3Py/VBgGV1NaYeWIAwS3gBIl8Tk2V1NWb1swBhlhgcS9DW3EC0rXnZ42IWIIxZ9SxAmCW8Ia75ciO2tzYRbWu2AGHMKmYBwizhZ4irpzcaYcjSfhuzalmAMItSqeXTfGeKRSN2B2HMKmYBwiw6NTnL7ELK9x1EXzTC6MQ0C8lUwCUzxlSDBQizyO8QV08sGiGZUo5NzARZLGNMlViAMIu8/oRC+iDARjIZs1pZgDCLBuMJRGDLWp9NTN0WIIxZzSxAmEXD8QSbOsM0N/r7tejpaKW5IWQBwphVqtoLBlVdKqWMTc1Vuxg0hCTv5LRCqGreuQyZhuIJeqNh38d7ab+Pnpzk1LnZC/Y3hoS1ZfxM52bmmZnP3iF+ZlazliEk0L2mpaDzJFNKPMfvRHNDiM5IU0HvZ8xKVfcBYjwxx9vv+Xa1iwHAPR+8nJ+7qq/k9zl1bpbrPrOPP7/97Vzz+m7frxuKJ7j+jesLOtfWdW18+8XX+PY92ZcM//ytV3LzlZsLes9sXjk1yXv+6DGSKc190L7s/493fWA7v/iObb7P9V8eeJZvHMydqfYvfvHtXP/GDb7fz5iVqu4DRFtLI5/82curXQzu+cYLvHxyqizv9aMTZ0nMJXl2eNx3gEjMLXDq3Cx93W0Fnet//sx2rr80+8Xynm+8wHMjZ8oSIA4dO0sypfzGuy9mXfuFdwRHXnqJiy+55ILtf/zoSxwcOVPQuQ4MT/DWWBcffOuWJdtVlTv/4RDPj5yxAGHqQt0HiNamBv7D1aV/ay/Vnw28XLbU2V6fQCGZVofj04D/Ia6ebeva2LYue1D5qydeLVv/hPc+u971OtpaLvy1HZj5Mf1Z/h+/cfBYQWWYT6Y4NjHNLW/ZnPX34t59R63PxdQN66SuER3hprIHiEIuZN6xfoe4+lHOmdbD8QTr1jRnDQ7lLMOxiWlSmjtQ2uxxU08sQNSIznAjZ6bL01nuzWcYLCBP0uCY07yVL813IXrdi6nqMv0GPg2OLb9Odi6xaIRT52ZJzC34Po/3umx6LUCYOmIBokZ0BnAHcWximnmfaTCG4wnaWxrpKuMInb5ohMRcsiyjxIbiiaKCV8ztU/Ga0Pycx3ld7juIE2dnmJlPFlwWY1YaCxA1olwBQlUZGkvQ3tpISp0g4ceQzzTfhYiVaSLd3EKK42emi2r+KnTdiuF4gubGED3trVn393VHUIVRn/VqzEoWaIAQkRtF5LCIHBWRj2fZ3ycie0XkoIgMiMiWtH0xEfmWiLwoIi+IyNYgy1pt5QoQZ6bnOTe7wDWvc0Yv+b0wFpLm26/Fi3OJKcHz9Qv4KkMB9dC7NkwolD1QluszGbMSBBYgRKQBuBd4P7AduE1Etmcc9lngflW9Argb+FTavvuBz6jqZcBO4GRQZa0FXZFmZuZTzC6U1nThtaFfe/G6Jc+Xk0opw+PTvtN8++Wl7Cj1DmKwhA70tZEm1rQ0MjTmbwjx4NjygdLyT5l6EuQdxE7gqKq+oqpzwAPAzRnHbAe+4z7e5+13A0mjqj4KoKqTqrqq/yI7wk7bf6l3Ed6Fa8fWKM2NIV9DXV87N8PcQqqob+jLaW1q4KKO1pIvpovrZBc4RwNARHyPPFJVhuOJZc+zfk0L4aYGCxCmLgQZIDYDw2nPR9xt6Q4At7iPPwi0i0g3cAkwISJfE5FnReQz7h3JqtXpBoizZQoQfd0ReteGfV3ICs3iWohyDAv1+gU2ZJkgV84yTCSc5rnlAmUhAceYla7aE+U+BnxBRO4AHgNGgSROua4F3gIMAV8F7gD+PP3FIrIL2AXQ09PDwMBAhYpdfoOnnGGY+777JCNr/cfCycnJJZ/7B4dm6WgWnvze/6ONGQ4NTuetl8dHnKB0/MhzDBwr73eGprlZXhhLlvR/8/ThGbpblMce+5ecx2TWwxJTcwyOzfOdffsILdMJ/8qE07x39tjLDAwM5jwuojO8OLTM+apo2XqoI1YP55VSF0EGiFGgN+35FnfbIlU9hnsHISJrgA+p6oSIjAA/VNVX3H1fB64mI0Co6m5gN8COHTu0v78/kA9SCV3DE3zu6e/yuksvp/+yHt+vGxgYIP1z/5+Xvs8bLkrS3/8O9p15nq89M8p111237Oikp791mJAc5ZYb+2lqKG+AOJg8wncffYmr33EtrU3F3QT+wYHHuay3lf7+t+c8JrMe0o20DvLNV5/nsrdezcbO3MkIzx44Bt9/lp9611W88aL2nMc9du4FvvLkUN56rYbl6qGeWD2cV0pdBNnEtB+4WES2iUgzcCvwcPoBIrJORLwyfAK4L+21XSLiZY67AXghwLJWXWcZ+yC8NvRYdxvnZheYSCz/nkPxBJu6wmUPDnC+2WpkvLhhoV6/QCnNX35HHg377Azv644wPZ/k9GT1swAbE6TAAoSqLgAfBh4BXgQeVNVDInK3iNzkHtYPHBaRl4Ae4B73tUmc5qe9IvIcIMAXgyprLShHgPDmC3ht6H6HeAYxxNVzftRPcYkIxxPzTObpF8jHdz2MJVjf3kK4efk7nViJn8mYlSLQPghV3QPsydh2Z9rjh4CHcrz2UeCKIMtXSzpanf+KUgLEqDtfIJYRIAbjCd7c25XzdcPxBO/Z7r9ZqxClzhsoR46oTV1hQpI/eeFgfMrXedKHur6tL1p0uYypdTaTukY0NoRob2ksKUCkj2ACFhf/We7CODm7wOnJubIPcfWsW9NMpLmBIZ+pLjIt5ogqYY5Gc2OITV3hxfkUuQzH/c3W3rI2jAgMjdlsarO6WYCoIaVmdM38th1pbmR9e8uy3979trsXq9RhoV75en2uk51LvjLMLaQ45jOdR7nmdxhT6yxA1JDOcFNJ8yCGxqZoaQyxPm2JzVg0wuAybeVBpPnO5GRALa69fijur18gn1g0suyd1Mh4AlX/9VDKZzJmpbAAUUM6w015Rxwtx0u4l55HyLkw5m4K8S6afdHCZyn71VdC2u/BseKyuGaKdUc4PTnH1Gz2tN/5srhe8H42Wc7UAQsQNaTUhH1D8ekLLqa90QjHzkwzt5A97ffgWIKO1kY6y5jmO1OsO8LMfIpTk7MFv7bUIa6LZcgzkqnQprZYNMJrZ2ct7bdZ1SxA1JBSAoQ3XyCzs7kvunx66qF4wve35mL1FjmSaXYhyfGzM2XpQM8XIIbiCVoKSOfhdZoXsqyrMSuNBYga0hUpPkDEp+aYnF244Buwd/EfzJHNdDieCLR5CQpPue0ZHZ8uqF/ATxlyXdC9LK5+Z0ZbVldTDyxA1JCOcBOzC6mimi0yh7h6lrswJlPK8HhxS3kWYnFYaIEX08Ecn6kYXZFmOlobc6Y/L3SyYLFBz5iVxAJEDSklo2uu0Ugb2ltoaQxlvZCdODvDfFIDHcEE0NLYwMYihoWWewhurDt7x/JiOo8CAlF3WzNtzZb226xuFiBqSCnpNryL6ZaM+QLePIRs35yDTPOdqTcaKbgPYmgsQWtTiPVFpvnOlGuo69jUHFNzyYLqQUSK+kzGrCQWIGqIFyAmiggQg2MJNuSYL5BrSOZwGZtw8unL8e19OV6zT7kypsaibYyMT5NMLR1uW+xcEBvqalY7CxA1ZPEOooi5EE4W1+wXuF73m3PmPITB+BQNIWFjZ2vhhS1QLBrh5LlZpuf896+UO4lgLBphLpnixNmZJduLbcryAkQx8zuMWQksQNSQUpuYcnU293VHmJpLEp9amp56KD7N5q4wjQGk+c7klW143N83blVdnPhXLrkSB3rPCz1XX3eE2YUUJ88VPr/DmJXAAkQN6YoUFyC8+QK5vgGnZ3VNF2Sa71xl8NtmPzY1R6LAfgG/ZcjshxiMJ+jpaCl4QSMb6mpWu7wBQkQ+kLaojwlQe2txAWLEnS+Qq4kp14Wx0JE7pfAWMfJ7Mc01bLcUm7paaQjJBWUoNlCWmsrcmFrn58L/74AjIvJpEbk06ALVs4aQ0N5aeMrvfJ2s2WYyn5uZJz41V7E7iLWRJta0NPoPEAGMsGpsCLE5S9rv5ZrnlrO5yPkdxqwUeQOEqv488BbgZeBLIvKEiOwSkdyL9pqiFZPRdTEldo6LXGtTAz0dLUsujJXI4ppucVhogXcQmcN2S5U58mhmPsmJszNFzSZvaWxgU2fYAoRZtXw1HanqWZyV3x4ANgIfBJ4RkV8PsGx1qTPcVPAw18GxBOGmhiVpvjNlXhiDXgcim74CA8RFHa0F9wvkE+teOhfCa56LdYeLer/eqAUIs3r56YO4SUT+HhgAmoCdqvp+4M3AR4MtXv0pJmGfn/kC3lDX9NeA//TW5eBdnFOp/MNCh8aC6UCPRSPEp+Y4N+PUcamB0uZCmNXMzx3Eh4A/UtU3qepnVPUkgKomgF8KtHR1qJgA4acNPRaNcOLszGKep8GxBF2RJjpag0vznak36n9YaLmHuHoycygN5Wme8/N+p87NkpjLvs6EMSuZnwDxu8CT3hMRCYvIVgBV3RtMsepXoQHCmy+Q7xtwX7eT9ntk3En7Xckhrh6/Ce68foGg7iDg/J2Dn+a5Zd/PHZ213KJMxqxUfgLE3wLpq80k3W15iciNInJYRI6KyMez7O8Tkb0iclBEBkRkS8b+DhEZEZEv+DnfatBZYMrvs3OQmEvmHQ6aeWEs10I8hejzGSC8IBZEChCvSS39DqKUdB6W1dWsZn4CRKOqLk7BdR8353uRiDQA9wLvB7YDt4nI9ozDPgvcr6pXAHcDn8rY/0ngMR9lXDU6w03MFZDy+1TCid35Lvbpk7qSKWVkfLriAWJTV5iQj2Gh3lrPQTQxdbQ20RVpWixDsUNcPRYgzGrmJ0CcEpGbvCcicjNw2sfrdgJHVfUVN6g8ANycccx24Dvu433p+0XkbUAP8C0f51o1Ck23cXLa6fDNd5Fbv6aFcFMDg2MJjk1Ms5AKPs13pubGEBs7wwzlWLzIE3SWWS+7rd/mueUszu/I85mMWYkafRzzn4C/dpt5BBgGfsHH6za7x3pGgKsyjjkA3AJ8HmfobLuIdAPjwOeAnwd+MtcJRGQXsAugp6eHgYEBH8WqbaPHnc7OR//le2xpzx+/RydmEIRXntvPSMPyzSTdLSmePTLEurnjAIwPH2Eg8UrphS5AR2iW5189sez/1fdenKWlAZ5/6nu+m34mJyd9//+3Lszw0miKf/jWPqbnk8zFRxkYOOnrtdlEm1M8e3SEgQE/35uCVUg9rGZWD+eVUhd5A4SqvgxcLSJr3OeTRZ0pu48BXxCRO3CakkZx+jh+FdijqiPLXSBUdTewG2DHjh3a399fxqJVR8ORU/zJgSe55PIr2bktmvf4Lx58hIs6G3nvu6/Pe+ylg08xHE8Q7d0K+5/jAzdcU/aJaPl8c+wg337xJMv9X3158Cm2rU9w/fXv8v2+AwMDy75nuidnfsQzj73CpkuuhH1P8O6r3kz/pRt8nyvT9uGnOXLynO/zB6mQeljNrB7OK6Uu/NxBICI/DfwE0OpdsFX17jwvGwV6055vcbctUtVjOHcQuAHoQ6o6ISLXANeKyK8Ca4BmEZlU1Qs6ulebQpuYTk2nfLehx6IRvnv0NK+OJWgMCRs7i5scVoreaITTk7NMzS7Q1pL9128oPrWYuykIsWiEhZTyg1fGFstU0vt1R/jO4ZOkUkooVJ61K4ypBX4myv0ZTj6mX8dpYvo3QJ+P994PXCwi20SkGbgVeDjjvdelJQL8BHAfgKr+nKrGVHUrzl3G/fUQHKCIAJHw35fQ1x1hej7JM0PjbFkbpqEKF7PF0VQ50n6Xo1/AbxkeP3oaEWfN7FLfb24hxWvnZvIfbMwK4qeT+l+p6i8A46r6e8A1wCX5XqSqC8CHgUeAF4EHVfWQiNyd1undDxwWkZdwOqTvKeIzrCpdYWeAmJ8AMTOfZHxWF4eP5uNdGJ8dGl8cv19p3tDVXBlQT03OMjOfCnSVO2+o67ND42VJ52FZXc1q5aeJyftalBCRTcAYTj6mvFR1D7AnY9udaY8fwsnxtNx7fAn4kp/zrQbtrY2I+AsQI+OFpcvwmlLmk0osWvnmJcg/LDRf4sFy2NgZpjEkzCe1LOdJ/0xXva675Pczplb4uYP4RxHpAj4DPAO8CvxNgGWqa6GQ0N7S6Cuja6FpIra46amhskn60nWGm2hvzZ32ezDgIa7gpFX3mpXKcR6/8zuMWWmWDRBu/8BeVZ1Q1b/D6Xu4NP0uwJSf39nUhV5MW5sauKij1X1NdZqYRGTZBHdD8URZ+gXy8YKq3+a55TQ3htjUZVldzeqzbIBQ1RTObGjv+ayqngm8VHWuM9zERGIu73FD8QStDdDdlndi+yLvwlitOwhw+iGWCxAbO1ppaSxvmu9sZYDyZbO1rK5mNfLTB7FXRD4EfE1V8+dpNiXzm7BvOJ5gfSRUUB6hWDTCkz+O01ulPghwgtS3Dr3Gf/7y0xfs2/9qnNevXxN4GbwAWa6+jlg0wj/88FjWz1RJyXOzvOtdNtzWlIefAPErwG8BCyIygzPUVVW1I9CS1bHOcBMnzuQfMjkUT7A+XNiF4Kev2EiDyOL619Xw7kt7eOyl07x86sI5l9G2Zm66clPgZbjh0g08+eM4l11Unl/j9/3ERfxweCLrZ6qUczMLHD+zwOjEdKCd/KZ++JlJbUuLVlhnuJkz08uvL+DNF+jf7GtRwEXXv3ED17+x+FnD5bBzW5R//o1rq1qGN2xo5//e/vayvd/1l27g+hJmY5fD914+zb//4g8CW0vD1J+8AUJEsuY7UNW6yrJaSd661Kqas/no1DlnvsD6iK/J8KYOeLPPh+IJ3lHlspjVwc/V5b+mPW7FydL6NHBDICUyTsrvZIqZ+RTh5uydtV6HaKFNTGb1uqijlQYbbmvKyE8T0wfSn4tIL/DHQRXILE23kStAeENcN0QKa2Iyq1dDSFgXFpvRbcqmmKvLCHBZuQtizvMCxMR07qGu3nyBdXYHYdJsiITsDsKUjZ8+iP8NeMNbQ8CVODOqTUAW7yASuYe6DscTbHJTRhjjWR8Rnj5lAcKUh58+iKfSHi8AX1HV7wZUHoO/jK7OSJUwMFuhUpmVYH04xJnpOc4k5umMVG8os1kd/ASIh4AZVU2Cs9a0iERU1b6mBKQrkj9ADMYT3PDGDViAMOk2RJw7yqF4gjdFOqtcGrPS+emD2AukT7sNA98OpjgGoCPPHcT0XJJT52bLlibCrB7eoAXrhzDl4CdAtKYvM+o+titTgNpbnJTfuTK6eovt2GQok8kbtGABwpSDnwAxJSJv9Z6IyNuA6eCKZEIhoaM1dz6mSqTENitTuFHobmtmKD5V7aKYVcBPH8RHgL8VkWM4eZguwlmC1ASoM9zERI4A4X077ItGmHi5kqUyK0FsmWy5xhTCz0S5/SJyKfBGd9NhVfW3YLIp2nIZXYfjCdpbGhc7s41JF4tGeGZovNrFMKtA3iYmEfk1oE1Vn1fV54E1IvKrwRetvi0XILxkbIWk+Tb1IxaNcGxihvlkqtpFMSucnz6IX1bVCe+Jqo4DvxxYiQyw/Kpyg2NTiwveGJOpNxohmVKOTVhXoSmNnwDRIGlfVUWkAfC/hJkpipfRNVMqpQyPT1sHtcnJW0bV+iFMqfwEiG8CXxWRd4vIu4GvAP/s581F5EYROSwiR0Xk41n294nIXhE5KCIDIrLF3X6liDwhIofcfXXXKe41MWUu4nfy3CxzCykb4mpy8ubHWIAwpfITIP478B3gP7k/z7F04lxW7p3GvcD7ge3AbSKyPeOwzwL3q+oVwN3Ap9ztCeAXVPUngBuBPxaRLh9lXTU6w03MJ5Xp+eSS7d4fvd1BmFx62ltpbghZVldTsrwBQlVTwA+AV3HWgrgBeNHHe+8EjqrqK6o6BzwA3JxxzHac4AOwz9uvqi+p6hH38THgJLDexzlXjcWMrhkJ+wbHnPHt1gdhcgmFhC3RsN1BmJLlHOYqIpcAt7k/p4GvAqjq9T7fezMwnPZ8BLgq45gDwC3A54EPAu0i0q2qY2nl2InT53HBiH8R2QXsAujp6WFgYMBn0WrfyAlnydG9jz9Bb/v5OP74kTkEOHLgSX4cEiYnJ1fV5y6W1YPDq4c1zPDC0HTd1on9PpxXSl0sNw/iR8DjwM+o6lEAEfnNos6S28eAL4jIHcBjwCiw2KYiIhuBvwJud+9kllDV3cBugB07dmh/f3+Zi1c9TUdPc+8Pf8DFP/Fmrn5d9+L2r594ls1rx/nJG5w4PTAwwGr63MWyenB49bDvzPN87ZlRrrvuurocDm2/D+eVUhfLNTHdAhwH9onIF90O6kJ+00aB3rTnW9xti1T1mKreoqpvAX7b3TYBICIdwDeA31bV7xdw3lUhV8rvwXjC+h9MXr3RCOdmFy5oojSmEDkDhKp+XVVvBS7F6R/4CLBBRP5URN7r4733AxeLyDYRaQZuBR5OP0BE1omIV4ZPAPe525uBv8fpwH6owM+0KuQKEMPxhPU/mLz6utsAG8lkSuOnk3pKVf/GXZt6C/AszsimfK9bAD4MPILTqf2gqh4SkbtF5Cb3sH7gsIi8BPQA97jb/y3wLuAOEfmh+3NlYR9tZfMWe0mfCzE1u8DpyTkb4mryitlcCFMGfpL1LXJnUS+2+/s4fg+wJ2PbnWmPH8JZkCjzdV8GvlxI2VabNc2NhGTpHYSX5tuamEw+zmqDFiBMafzMgzBVEAoJHRn5mLw0333RtmoVy6wQkeZG1q1psbkQpiQWIGpYZ7hpSSfjsE2SMwXos7TfpkQWIGpYZkbXoXiCjtZGW4ze+BKLWoAwpbEAUcMyA8TgWMLWoTa+9UYjHD8zzdyCpf02xbEAUcMyM7oOxxPW/2B864tGSCmMWtpvUyQLEDUs/Q4imVJGxqdtiKvxzbK6mlJZgKhh6Sm/Xzs7w1wyZR3UxrfFuRBugkdjCmUBooZ1hptYSCmJueT5Ia7WB2F8Wr+mhZbGkN1BmKJZgKhhiym/p+dtiKspWCgkNpLJlMQCRA1bzMeUmGconqAhJGzsbK1yqcxK4gQI66Q2xbEAUcPSE/YNxhNs7grT2GD/Zca/3miEobGpC5auNcYPu9rUMG9C3Jlp5w7C+h9Mofq6I0zNJYlPzVW7KGYFsgBRw7w7iLNuH4QNcTWFsqyuphQWIGqYFyBGJ6aJT81ZB7UpmAUIUwoLEDVsTUsjDSHhudEzgDMz1phC9C7OhbAAYQpnAaKGiQgdrY0cHHEChDUxmUK1NjXQ09FidxCmKBYgalxnuInTk7MAlqjPFMXmQphiWYCocV4/RFekiY5WS/NtCtdrAcIUyQJEjeuMNAPW/2CK1xdt48TZGWbmk9UuillhLEDUOO8OwvofTLFi3WHU0n6bIgQaIETkRhE5LCJHReTjWfb3icheETkoIgMisiVt3+0icsT9uT3IctayznAjYDmYTPFiNpLJFCmwACEiDcC9wPuB7cBtIrI947DPAver6hXA3cCn3NdGgbuAq4CdwF0isjaostYy7w7CAoQpVq/NhTBFagzwvXcCR1X1FQAReQC4GXgh7ZjtwG+5j/cBX3cfvw94VFXj7msfBW4EvhJgeWvSYoCwEUymSOvXtBBuamD/q3Eu6Wm/YH9rU4g3b+kiFJIqlM6U6vnRMzSEhMs2dpT9vYMMEJuB4bTnIzh3BOkOALcAnwc+CLSLSHeO127OPIGI7AJ2AfT09DAwMFCusteMMycWaBA4eeQgA8MX3vBNTk6uys9dKKsHR656uCis/NPB4/zTweNZX/fRt7XwpvVBXg4qq55+Hz6zf5rEAtx1TTjr/lLqotq/ER8DviAidwCPAaOA76EWqrob2A2wY8cO7e/vD6CI1XVtSrn1vbmXGh0YGGA1fu5CWT04ctXD9rfO8PKpC1eWm55f4D9+6SkiG19P/zu3VaCElVFPvw93PrmPN2/tor//LVn3l1IXQQaIUaA37fkWd9siVT2GcweBiKwBPqSqEyIyCvRnvHYgwLLWrIaQ2AgmU7INHa1s6LhwLRFVpb2l0ZYlXaEWkilGJ6b5wJs3BvL+QY5i2g9cLCLbRKQZuBV4OP0AEVknIl4ZPgHc5z5+BHiviKx1O6ff624zxpSRiNhEuhXs+JkZkikNbBBLYAFCVReAD+Nc2F8EHlTVQyJyt4jc5B7WDxwWkZeAHuAe97Vx4JM4QWY/cLfXYW2MKa++bgsQK5W3Vn0s2hbI+wfaB6Gqe4A9GdvuTHv8EPBQjtfex/k7CmNMQGLRCHt/dJJUSm0k0wrjBfagRjnaTGpj6lxvNMLcQorXzs1UuyimQEPxBE0NwkVZ+pfKwQKEMXXOW8rWZlqvPMPxBFvWRmgI6M7PAoQxdc5WnVu5BuNTgWZZsABhTJ3b1BUmJBYgVqKhsYQFCGNMcJoaQmzqCluAWGHOJOY5O7NgAcIYEywb6rryDMadyY1BTqS1AGGMcZYltU7qFcUL6H0BJvK0AGGMoTcaYWxqjsnZhWoXxfjkBQi7gzDGBMprxx62ZqYVYzieoLutmTUtwc13tgBhjKHPTdVg/RArx+BYIvB1YixAGGNsWdIVaCge7BBXsABhjAE6I010tDbaHcQKMZ9McWxi2gKEMaYyYjbUdcUYHZ8mpcF2UIMFCGOMqy/aZgFihVgc4moBwhhTCb3RCCPjCZIprXZRTB5Bp/n2WIAwxgBOR/V8Ujlx1tJ+17rheILmhhA97cGk+fZYgDDGAJb2eyUZHEuwJRoOfIEnCxDGGCA97fdUlUti8hmKJwLvfwALEMYY18bOVhpCYh3VNU5VGa7AHAiwAGGMcTU2hNjcFWYoPl3tophlTCTmOTe7EPgQV7AAYYxJ09cdYWjMmphq2aA3gmmlBwgRuVFEDovIURH5eJb9MRHZJyLPishBEfkpd3uTiPyliDwnIi+KyCeCLKcxxtEbtclyte58mu+2wM8VWIAQkQbgXuD9wHbgNhHZnnHY7wAPqupbgFuBP3G3/xugRVXfBLwN+BUR2RpUWY0xjlg0wnhinrMz89UuislheDHNdzjwcwV5B7ETOKqqr6jqHPAAcHPGMQp0uI87gWNp29tEpBEIA3PA2QDLaozB0n6vBINjU6xb00KkObg0354gz7AZGE57PgJclXHM7wLfEpFfB9qAn3S3P4QTTI4DEeA3VTWeeQIR2QXsAujp6WFgYKCMxV8ZJicn6/JzZ7J6cJRaD6fOJgHY89h+Tl0U/AUoKKv59+HgK9N0NeL785VSF9X+DbgN+JKqfk5ErgH+SkQux7n7SAKbgLXA4yLybVV9Jf3Fqrob2A2wY8cO7e/vr2jha8HAwAD1+LkzWT04Sq2HszPz3PW9b9GxcRv9172+fAWrsNX8+/Db3/8OO7dF6e+/0tfxpdRFkE1Mo0Bv2vMt7rZ0vwQ8CKCqTwCtwDrg3wPfVNV5VT0JfBfYEWBZjTFAR2sTXZEm66iuUXMLKY6dma7IEFcINkDsBy4WkW0i0ozTCf1wxjFDwLsBROQynABxyt1+g7u9Dbga+FGAZTXGuGI2kqlmjYwnUK3MEFcIMECo6gLwYeAR4EWc0UqHRORuEbnJPeyjwC+LyAHgK8Adqqo4o5/WiMghnEDzF6p6MKiyGmPOswBRu84Pca1MgAi0D0JV9wB7Mrbdmfb4BeAdWV43iTPU1RhTYbFohG8+f4KFZIrGBptLW0uGKzhJDmwmtTEmQywaYSGlHD9jab9rzVA8QUtjiPVrWipyPgsQxpglvEVorJmp9gyOJeiNRgJP8+2xAGGMWeJ82m8LELWmUmm+PRYgjDFLbOwM02hpv2uOl+a7UkNcwQKEMSZDQ0jYsjZsAaLGjE3NMTWXrFgHNViAMMZkEetus6VHa0ylh7iCBQhjTBaxqN1B1JpKD3EFCxDGmCxi0Qhnpuc5k7C037XCu6PbstYChDGmimwkU+0ZjCfY0N5CuLmhYue0AGGMuUAs6qxWZgGidgzFExXtfwALEMaYLLzVyixA1I5KD3EFCxDGmCzaW5uItjVbgKgRM/NJTpydqWgHNViAMMbk0BuNMBSfqnYxDDAyPl3RNN+eaq8oZ4ypUX3RCN88dIL3/OG/VLsoBZtKJGh7ZuWVO5fpeWcp2Er3QViAMMZk9XNXxUimFEWrXZSCnTw5zYYNa6pdjLK69uL1XL65s6LntABhjMnqqtd1c9XruqtdjKI46zC/rdrFWPGsD8IYY0xWFiCMMcZkZQHCGGNMVhYgjDHGZGUBwhhjTFaBBggRuVFEDovIURH5eJb9MRHZJyLPishBEfmptH1XiMgTInJIRJ4TkdYgy2qMMWapwIa5ikgDcC/wHmAE2C8iD6vqC2mH/Q7woKr+qYhsB/YAW0WkEfgy8B9U9YCIdAOWd9gYYyooyDuIncBRVX1FVeeAB4CbM45RoMN93Akccx+/FzioqgcAVHVMVZMBltUYY0yGICfKbQaG056PAFdlHPO7wLdE5NeBNuAn3e2XACoijwDrgQdU9dOZJxCRXcAu9+mkiBwuX/FXjHXA6WoXogZYPTisHhxWD+flq4u+XDuqPZP6NuBLqvo5EbkG+CsRudwt1zuBtwMJYK+IPK2qe9NfrKq7gd2VLnQtEZGnVHVHtctRbVYPDqsHh9XDeaXURZBNTKNAb9rzLe62dL8EPAigqk8ArTjRbgR4TFVPq2oCp2/irQGW1RhjTIYgA8R+4GIR2SYizcCtwMMZxwwB7wYQkctwAsQp4BHgTSIScTusrwNewBhjTMUE1sSkqgsi8mGci30DcJ+qHhKRu4GnVPVh4KPAF0XkN3E6rO9QVQXGReQPcYKMAntU9RtBlXWFq+smtjRWDw6rB4fVw3lF14U412NjjDFmKZtJbYwxJisLEMYYY7KyALGCiMh9InJSRJ5P2xYVkUdF5Ij779pqlrESRKTXTdHygpuK5Tfc7XVVFyLSKiJPisgBtx5+z92+TUR+4Ka4+ao7SGTVE5EGN23PP7nP664eRORVNzXRD0XkKXdb0X8XFiBWli8BN2Zs+ziwV1UvBva6z1e7BeCjqroduBr4NTdVS73VxSxwg6q+GbgSuFFErgb+APgjVX0DMI4znLwe/AbwYtrzeq2H61X1yrS5D0X/XViAWEFU9TEgnrH5ZuAv3cd/CfxsJctUDap6XFWfcR+fw7kobKbO6kIdk+7TJvdHgRuAh9ztq74eAERkC/DTwP91nwt1WA85FP13YQFi5etR1ePu4xNATzULU2kishV4C/AD6rAu3GaVHwIngUeBl4EJVV1wDxnBCZ6r3R8D/w1Iuc+7qc96UJz0RU+7qYighL+LaqfaMGWkqioidTNuWUTWAH8HfERVzzpfGh31UhduEssrRaQL+Hvg0uqWqPJE5GeAk6r6tIj0V7k41fZOVR0VkQ3AoyLyo/Sdhf5d2B3EyveaiGwEcP89WeXyVISINOEEh79W1a+5m+uyLgBUdQLYB1wDdLkZCCB7ipvV5h3ATSLyKk7W6BuAz1N/9YCqjrr/nsT5wrCTEv4uLECsfA8Dt7uPbwf+oYplqQi3ffnPgRdV9Q/TdtVVXYjIevfOAREJ46y98iJOoPjX7mGrvh5U9ROqukVVt+Kk9PmOqv4cdVYPItImIu3eY5xlE56nhL8Lm0m9gojIV4B+nISGrwF3AV/HSXgYAwaBf6uqmR3Zq4qIvBN4HHiO823O/wOnH6Ju6kJErsDpdGzA+bL3oKreLSKvw/kmHQWeBX5eVWerV9LKcZuYPqaqP1Nv9eB+3r93nzYCf6Oq97gLrhX1d2EBwhhjTFbWxGSMMSYrCxDGGGOysgBhjDEmKwsQxhhjsrIAYYwxJisLEMb4JCJJN0um97NVRL5X4Ht8REQiOfYNiMgO9/E2N/vm+8pRdmOKYcNcjfFJRCZVdY2P4xrTcgBl7nsV2KGqp7PsGwA+hpMvZy/wX92leY2pCsvFZEwJvKDhTtD6JE5a6UtF5C04k5O24Exk+yROkrRNwD4ROa2q12d5y43A/cBvW3Aw1WYBwhj/wm7mVIAfq+oHM/a/FbhcVX8sIh8CjqnqTwOISKeqnhGR38LJ13/BHYTrL4HfUdWHcuw3pmKsD8IY/6bdhViuzBIcAJ5U1R+7j58D3iMifyAi16rqGZ/n+Dbw87n6KYypJAsQxpTPlPdAVV/CuaN4Dvh9EbnT53t8GtgP/G1aJlJjqsIChDEBEJFNQEJVvwx8BidYAJwD2vO8/CPAWeDPJX2RC2MqzAKEMcF4E/Ck22dxF/D77vbdwDdFZF+uF6oztPB2nA7rTwdcTmNysmGuxhhjsrI7CGOMMVlZgDDGGJOVBQhjjDFZWYAwxhiTlQUIY4wxWVmAMMYYk5UFCGOMMVn9f6a6hXZS3edLAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "k_values = [i for i in range(3,50)]\n",
    "\n",
    "best_k, accuracies = select_knn_model(X_validation, y_validation, X_train, y_train, k_values, distance_function=get_euclidean_distance)\n",
    "\n",
    "plt.plot(k_values,accuracies)\n",
    "plt.xlabel(\"First K\")\n",
    "plt.ylabel(\"Accuracy\")\n",
    "plt.grid(True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "BjQBDWJMSgya"
   },
   "source": [
    "## Count accuracy for training set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {
    "id": "_f-J5sSESgya",
    "outputId": "26815b47-6cb0-4ee3-a72c-b6e3a71f023c"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy for first best k =  14 is 93.33 %\n"
     ]
    }
   ],
   "source": [
    "prediction = predict(X_test, X_train, y_train, best_k, get_euclidean_distance)\n",
    "\n",
    "## Calculate Best accuracy using the best k value\n",
    "print(\"Accuracy for first best k = \", best_k, \"is\", round(count_accuracy(prediction,y_test) * 100, 2), \"%\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "72O5eXbCSgyc"
   },
   "source": [
    "# Sources\n",
    "\n",
    "https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm - first visualisation image\n",
    "\n",
    "https://en.wikipedia.org/wiki/Euclidean_distance - euclidean distance visualisation\n",
    "\n",
    "https://rajritvikblog.wordpress.com/2017/06/29/iris-dataset-analysis-python/ - first iris image\n",
    "\n",
    "https://rpubs.com/wjholst/322258 - second iris image\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "Knn.ipynb",
   "provenance": []
  },
  "interpreter": {
   "hash": "fe44fef87f92f48a3a32707d0df204585f471652bc0ce87358a3ce712bc24db0"
  },
  "kernelspec": {
   "display_name": "Python 3.9.7 64-bit",
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}