{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n",
    "\n",
    "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name below.\n",
    "\n",
    "Rename this problem sheet as follows:\n",
    "\n",
    "    ps{number of lab}_{your user name}_problem{number of problem sheet in this lab}\n",
    "    \n",
    "for example\n",
    "    \n",
    "    ps2_blja_problem1\n",
    "\n",
    "Submit your homework within one week until next Monday, 9 a.m."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = \"\"\n",
    "EMAIL = \"\"\n",
    "USERNAME = \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to Data Science\n",
    "## Lab 10: Implementing K-Nearest Neighbors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given is a data sample with the following points:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "a1fd28a0713729e42ad9d34bbdd6a856",
     "grade": false,
     "grade_id": "cell-63aa91cce54c289b",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "K = 5\n",
    "np.random.seed(4)\n",
    "X = np.random.rand(20,2)\n",
    "z = np.random.rand(1,2)\n",
    "plt.plot(X[:,0],X[:,1],'r+');\n",
    "plt.plot(z[:,0], z[:,1], 'bo');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task (1 points)**: Write the function `getKNeighbors` as defined below. It should return the coordinates of `k` nearest neighbors (in the Euclidean distance) of a point `z` among a set of points `X`.\n",
    "Try to use functions provided by `numpy`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "875c3a67b1e5f36e2b0e3d355d30c124",
     "grade": false,
     "grade_id": "cell-fa145e429ed70484",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "def getKNeighbors(X, z, k = 3):\n",
    "    \"\"\"Function to return the coordinates N of \n",
    "    k nearest neighbors of a single point z\n",
    "    among a set of points X.\"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()\n",
    "    return N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "d1ccea937facdef61730d947070136ca",
     "grade": true,
     "grade_id": "cell-581a2ad6775044e4",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "approxEqual = lambda a,b : np.max(np.abs(a - b)) < 1e-7\n",
    "\n",
    "assert approxEqual(getKNeighbors(X,z,1),np.array([[0.40149544, 0.64980511]]))\n",
    "assert approxEqual(getKNeighbors(X,z,3), np.array([[0.40149544, 0.64980511],\n",
    " [0.52440408, 0.63761024],\n",
    " [0.16384224, 0.59733394]]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task (1 point)**: If your code is not already capable of handling $d$-dimensional input go back to its definition and adjust the code as necessary. Make sure that both tests are passed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "4a18f1a83896ed216c692422b47fec3a",
     "grade": true,
     "grade_id": "cell-813d026dac324cfb",
     "locked": true,
     "points": 1,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "np.random.seed(1)\n",
    "X4 = np.random.rand(20,4)\n",
    "z4 = np.random.rand(1,4)\n",
    "\n",
    "assert approxEqual(getKNeighbors(X4,z4,1), np.array([[0.95788953, 0.53316528, 0.69187711, 0.31551563]]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following code is intended to illustrate the K-nearest neighbor algorithm. You have nothing to implement here!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = getKNeighbors(X,z,4)\n",
    "fig, ax = plt.subplots()\n",
    "ax.plot(X[:,0],X[:,1],'r+');\n",
    "ax.plot(z[:,0], z[:,1], 'bo')\n",
    "ax.plot(N[:,0],N[:,1],'k.')\n",
    "\n",
    "D = np.sqrt(np.sum(np.power(N[-1,:]-z,2)))\n",
    "c1= plt.Circle((z[0,0],z[0,1]), D,color='r', alpha=0.3)\n",
    "ax.add_artist(c1);"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}