{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## `np.sort` and `np.argsort`" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import numpy as np" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "x = np.array([2, 1, 4, 3, 5])" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([1, 2, 3, 4, 5])" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.sort(x) # return a sorted version of the array without modifying the input" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([2, 1, 4, 3, 5])" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([1, 2, 3, 4, 5])" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x.sort() # sort the array in-place\n", "x" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`argsort`: returns the *indices* of the sorted elements " ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([1, 0, 3, 2, 4])" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = np.array([2, 1, 4, 3, 5])\n", "i = np.argsort(x)\n", "i" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first element of this result gives the index of the smallest element, the second value gives the index of the second smallest, and so on. These indices can then be used (via fancy indexing) to construct the sorted array if desired:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([1, 2, 3, 4, 5])" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x[i]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Sorting along rows or columns" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[6, 3, 7, 4, 6, 9],\n", " [2, 6, 7, 4, 3, 7],\n", " [7, 2, 5, 4, 1, 7],\n", " [5, 1, 4, 0, 9, 5]])" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "rand = np.random.RandomState(42)\n", "X = rand.randint(0, 10, (4, 6))\n", "X" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[2, 1, 4, 0, 1, 5],\n", " [5, 2, 5, 4, 3, 7],\n", " [6, 3, 7, 4, 6, 7],\n", " [7, 6, 7, 4, 9, 9]])" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# sort each column of X\n", "np.sort(X, axis=0)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[3, 4, 6, 6, 7, 9],\n", " [2, 3, 4, 6, 7, 7],\n", " [1, 2, 4, 5, 7, 7],\n", " [0, 1, 4, 5, 5, 9]])" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# sort each row of X\n", "np.sort(X, axis=1)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Partial Sorts: Partitioning" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Find the *k* smallest values in the array.\n", "\n", "`np.partition`: takes an array and a number *K*; the result is a new array with the smallest *K* values to the left of the partition, and the remaining values to the right, in arbitrary order" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([7, 2, 3, 1, 6, 5, 4])" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = np.array([7, 2, 3, 1, 6, 5, 4])\n", "x " ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([2, 1, 3, 4, 6, 5, 7])" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.partition(x, 3) # the first three values in the resulting array are the three smallest in the array" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([2, 1, 3, 4, 5, 6, 7])" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.partition(x, 4)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[6, 3, 7, 4, 6, 9],\n", " [2, 6, 7, 4, 3, 7],\n", " [7, 2, 5, 4, 1, 7],\n", " [5, 1, 4, 0, 9, 5]])" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "X" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[3, 4, 6, 7, 6, 9],\n", " [2, 3, 4, 7, 6, 7],\n", " [1, 2, 4, 5, 7, 7],\n", " [0, 1, 4, 5, 9, 5]])" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.partition(X, 2, axis=1)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example: k-Nearest Neighbors" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Create a random set of 10 piints on a two-dimensional plane" ] }, { "cell_type": "code", "execution_count": 72, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[2, 0],\n", " [2, 4],\n", " [2, 0],\n", " [4, 9],\n", " [6, 6]])" ] }, "execution_count": 72, "metadata": {}, "output_type": "execute_result" } ], "source": [ "X = rand.randint(10, size=(5, 2))\n", "X" ] }, { "cell_type": "code", "execution_count": 73, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(5, 2)" ] }, "execution_count": 73, "metadata": {}, "output_type": "execute_result" } ], "source": [ "X.shape" ] }, { "cell_type": "code", "execution_count": 74, "metadata": {}, "outputs": [], "source": [ "%matplotlib inline\n", "import matplotlib.pyplot as plt\n", "import seaborn; seaborn.set()" ] }, { "cell_type": "code", "execution_count": 75, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 75, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWwAAAD7CAYAAABOi672AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAU1UlEQVR4nO3df2zU9eHH8df12gIFZFCuFv02wzR+nUHATUFvEhkLtpZSWivZRNG4hmCHiwtTGbLGxRo7frg0a0qTZTOSCZ3ItK0SfjoypbQZlO1rAZlhTLTalpZSKNDS1s+9v3/45b6UH71r6f144/ORmHB9v6/vF2/uXv34uftcXcYYIwBA1IuJdAAAQHAobACwBIUNAJagsAHAEhQ2AFiCwgYAS1DYAGCJ2FAv0N5+Tj7f4N7qnZg4Sm1tZ4c40bUj18BEY65ozCSRa6CiMde1ZoqJcWns2JFXHAt5Yft8ZtCFfeH+0YhcAxONuaIxk0SugYrGXKHKxCkRALAEhQ0Algj5KREgWrS0d2r73gbVHmpWd4+jYfFueSclK316ipLGJkQ6HhAQhY1vhPqjbSqrPCDHMXL+7/zi+R5HH37UqD0Hm7QkZ7KmpCZGOCXQP06J4LrX0t6pssoD6un1+cv6Asdn1NPrU1nlAbW0d0YoIRAcChvXve17G+Q4/b9q7zhGO/Y1hCkRMDgUNq57tYeaLzuyvpTjM6o92BymRMDgUNi47p3vcYZ0HhApFDaue8Pj3UM6D4gUChvXPe+kZLljXP3Occe45L0jOUyJgMGhsHHdS5+eIrc7QGG7XUqblhKmRMDgUNi47iWNTdCSnMmKj4u57EjbHeNSfFyMluRM5uIZRD0unME3wpTURBXmTdeOfQ2qPdis872Ohse55b0jWWnTuNIRdqCw8Y2RNDZBC9Nu08K02+TxjFZr65lIRwIGhFMiAGAJChsALEFhA4AlKGwAsASFDQCWoLABwBIUNgBYgsIGAEtQ2ABgCQobACxBYQOAJYIq7KqqKmVmZiozM1OrVq0KdSYAwBUELOyuri698soreuONN1RVVaW6ujrV1NSEIxsA4CIBC9txHPl8PnV1demrr77SV199pWHDhoUjGwDgIgE/XnXUqFH6+c9/royMDI0YMULTpk3T9773vXBkAwBcxGWMMf1N+Ne//qXly5frtdde0+jRo/Xcc89pypQpWrRoUbgyAgAUxBF2dXW1vF6vEhMTJUm5ubkqLy8PurDb2s7K5+v3Z8JVReuHzJNrYKIxVzRmksg1UNGY61ozxcS4lJg46spjge78ne98RzU1Ners7JQxRrt27dLkyZMHHQYAMDgBj7BnzJihjz/+WLm5uYqLi9PkyZO1ePHicGQDAFwkqN/puHjxYkoaACKMKx0BwBIUNgBYgsIGAEtQ2ABgCQobACxBYQOAJShsALAEhQ0AlqCwAcASFDYAWILCBgBLUNgAYAkKGwAsQWEDgCUobACwBIUNAJagsAHAEhQ2AFiCwgYAS1DYAGAJChsALEFhA4AlKGwAsASFDQCWoLABwBIUNgBYgsIGAEtQ2ABgCQobACxBYQOAJShsALAEhQ0AlqCwAcASFDYAWCI20gEAwHYt7Z3avrdBtYea1d3jaFi8W95JyUqfnqKksQlDtk5Qhb1r1y6Vlpaqq6tL9913nwoKCoYsAADYrP5om8oqD8hxjByfkSSd73H04UeN2nOwSUtyJmtKauKQrBXwlEhDQ4N+/etfq6ysTO+++64+/vhjffDBB0OyOADYrKW9U2WVB9TT6/OX9QWOz6in16eyygNqae8ckvUCFvbOnTs1Z84cJScnKy4uTsXFxZo6deqQLA4ANtu+t0GOY/qd4zhGO/Y1DMl6AQv7s88+k+M4ys/PV3Z2tsrLyzVmzJghWRwAbFZ7qPmyI+tLOT6j2oPNQ7JewHPYjuOorq5Ob7zxhhISEvTTn/5UFRUVys3NDWqBxMRR1xTQ4xl9TfcPFXINTDTmisZMErkGKpK5unucoOad73WGJGfAwh4/fry8Xq/GjRsnSZo9e7bq6+uDLuy2trPyBfgJdDUez2i1tp4Z1H1DiVwDE425ojGTRK6BinSuYfFunQ+itIfHuYPOGRPjuuqBbsBTIrNmzVJ1dbU6OjrkOI52796tSZMmBbUwAFzPvJOS5Y5x9TvHHeOS947kIVkvYGFPnTpVixYt0qOPPqo5c+bopptu0sMPPzwkiwOAzdKnp8jtDlDYbpfSpqUMyXpBvQ97/vz5mj9//pAsCADXi6SxCVqSM/my92FLXx9Zu90uLcmZPGQXz3ClIwBcgympiSrMm64d+xpUe7BZ53sdDY9zy3tHstKmReBKRwDA1SWNTdDCtNu0MO22kL4Qyoc/AYAlKGwAsASFDQCWoLABwBIUNgBYgsIGAEtQ2ABgCQobACxBYQOAJShsALAEhQ0AlqCwAcASFDYAWILCBgBLUNgAYAkKGwAsQWEDgCUobACwBIUNAJagsAHAEhQ2AFiCwgYAS1DYAGAJChsALEFhA4AlKGwAsASFDQCWoLABwBIUNgBYgsIGAEtQ2ABgCQobACwRG+kAl2pp79T2vQ2qPdSs7h5Hw+Ld8k5KVvr0FCWNTYh0PACImKALe9WqVWpvb9fKlStDFqb+aJvKKg/IcYwcn5Ekne9x9OFHjdpzsElLciZrSmpiyNYHgGgW1CmR2tpaVVRUhDRIS3unyioPqKfX5y/rCxyfUU+vT2WVB9TS3hnSHAAQrQIW9qlTp1RcXKz8/PyQBtm+t0GOY/qd4zhGO/Y1hDQHAESrgIX94osvaunSpbrhhhtCGqT2UPNlR9aXcnxGtQebQ5oDAKJVv+ewN23apAkTJsjr9eqdd94Z1AKJiaOCmtfd4wQ173yvI49n9KCyDKVoyHAl5ApeNGaSyDVQ0ZgrVJn6LewtW7aotbVV2dnZOn36tDo7O1VUVKQVK1YEvUBb21n5Ahw5S9KweLfOB1Haw+Pcam09E/T6oeDxjI54hishV/CiMZNEroGKxlzXmikmxnXVA91+C/v111/3//mdd97R3r17B1TWA+GdlKwPP2rs97SIO8Yl7x3JIVkfAKJd1Fw4kz49RW63q985brdLadNSwpQIAKJL0IWdm5sb0vdgJ41N0JKcyYqPi5E7pm9xu2Ncio+L0ZKcyVw8A+AbK6qudJySmqjCvOnasa9BtQebdb7X0fA4t7x3JCttGlc6Avhmi6rClr4+0l6YdpsWpt0WlS8oAECkRM05bABA/yhsALAEhQ0AlqCwAcASFDYAWILCBgBLUNgAYAkKGwAsQWEDgCUobACwBIUNAJagsAHAEhQ2AFiCwgYAS1DYAGAJChsALEFhA4AlKGwAsASFDQCWoLABwBIUNgBYgsIGAEtQ2ABgCQobACxBYQOAJShsALAEhQ0AlqCwAcASFDYAWILCBgBLUNgAYAkKGwAsQWEDgCVig5lUWlqqrVu3SpJmzpypZcuWhTQUAOByAY+wa2pqVF1drYqKClVWVurQoUPauXNnOLIBAC4S8Ajb4/Fo+fLlio+PlySlpqaqsbEx5MEAAH25jDEm2MnHjh3TggUL9Oc//1kTJ04MYSwAwKWCOoctSUeOHNFTTz2lZcuWDais29rOyucL+mdCHx7PaLW2nhnUfUOJXAMTjbmiMZNEroGKxlzXmikmxqXExFFXHgvmG+zfv19PPvmknn32WT300EODDgIAGLyAR9hNTU16+umnVVxcLK/XG45MAIArCFjYr732mrq7u7Vy5Ur/1x555BEtWLAgpMEAAH0FLOyCggIVFBSEIwsAoB9c6QgAlqCwAcASFDYAWILCBgBLUNgAYAkKGwAsQWEDgCUobACwBIUNAJagsAHAEhQ2AFiCwgYAS1DYAGAJChsALEFhA4AlKGwAsASFDQCWoLABwBIUNgBYgsIGAEtQ2ABgCQobACxBYQOAJShsALAEhQ0AlqCwAcASFDYAWILCBgBLUNgAYAkKGwAsQWEDgCUobACwBIUNAJaIjXSASx0+dlIb3j+ixhPn/F+7afxIPTb7Vt0+cVwEkwFAZAV1hP3ee+9pzpw5SktL04YNG0IWpqr6U61583/6lLUkNZ44pzVv/o+qqj8N2doAEO0CFvbx48dVXFys8vJyVVZWauPGjfr3v/895EEOHzsZsJCrqj/V4WMnh3xtALBBwMKuqanRvffeq29961tKSEhQenq6tm3bNuRBNrx/JKh55UHOA4DrTcDCbmlpkcfj8d9OSkrS8ePHhzzIpadBrubLIOcBwPUm4IuOPp9PLpfLf9sY0+d2IImJowaXrB8ez+gh/542ZrgScgUvGjNJ5BqoaMwVqkwBCzs5OVl1dXX+262trUpKSgp6gba2s/L5zODSXUVr65kh/X4D5fGMjniGKyFX8KIxk0SugYrGXNeaKSbGddUD3YCnRL7//e+rtrZWJ0+eVFdXl3bs2KH7779/0GGu5qbxI4Oad3OQ8wDgehOwsG+88UYtXbpUTzzxhHJycjR37lxNmTJlyIM8NvvWoOY9GuQ8ALjeBHXhTFZWlrKyskIa5PaJ45Q945Z+39qXPeMWLp4B8I0VVVc6Zs+4Rf/9X2NU/v6RPu8GuXn8SD3KlY4AvuGiqrClr4+0X150j6TofEEBACKFD38CAEtQ2ABgiZCfEomJCf4im1DcP1TINTDRmCsaM0nkGqhozHUtmfq7r8sYM7RXtQAAQoJTIgBgCQobACxBYQOAJShsALAEhQ0AlqCwAcASFDYAWILCBgBLUNgAYImo+LS+0tJSbd26VZI0c+ZMLVu2rM/44cOH9atf/Urnzp3T3XffrZdeekmxsaGPHihXaWmp3n77bd1www2SpB/96Ed67LHHQp7rd7/7nbZv3y6Xy6X58+frJz/5SZ/xSOxXoEyR2qsLVq1apfb2dq1cubLP1xsbG/X888+rra1Nt9xyi1599VWNHBm+32p0tVwVFRX67W9/q8TEREnSD37wAy1dujTkeR5//HGdPHnS/3gpLCzU1KlT/eM1NTX6zW9+o+7ubmVkZIQlUzC5XnjhBe3fv18jRoyQJP3sZz/TAw88ENJMu3btUmlpqbq6unTfffepoKCgz3hInocmwvbs2WN+/OMfm+7ubtPT02OeeOIJs2PHjj5zMjMzzT//+U9jjDEvvPCC2bBhQ1Tkeuqpp8w//vGPkGe52N///nfzyCOPmN7eXtPV1WVmzZpljh492mdOuPcrmEyR2KsLampqzD333GN++ctfXja2ePFis3nzZmOMMaWlpWb16tVRkauwsNC89957YctijDE+n8/MmDHD9Pb2XnG8q6vLzJw503z++eemt7fX5OXlmb/97W8Rz2WMMXPnzjXHjx8PeZYLPv/8czNjxgzT1NRkenp6zIIFCy7bi1A8DyN+SsTj8Wj58uWKj49XXFycUlNT1djY6B//8ssvdf78ed15552SpNzcXG3bti3iuSTp4MGD+v3vf6+srCwVFhaqu7s75LmmT5+uP/3pT4qNjVVbW5scx1FCQoJ/PBL7FSiTFJm9kqRTp06puLhY+fn5l4319vZq3759Sk9PlxS+x1agXJJ04MABVVRUKCsrS88995xOnz4d8kz/+c9/JEl5eXmaN2+e1q9f32e8vr5e3/72t5WSkqLY2FhlZWWFZb8C5erq6lJjY6NWrFihrKwslZSUyOfzhTTTzp07NWfOHCUnJysuLk7FxcV9jvhD9TyMeGHfeuut/r/UsWPHtHXrVs2cOdM/3tLSIo/H47/t8Xh0/PjxiOc6d+6cbr/9dj3//POqqKhQR0eHysrKQp5LkuLi4lRSUqLMzEx5vV7deOON/rFI7Vd/mSK5Vy+++KKWLl3qPxVzsfb2do0aNcr/v6nh2qtAuS5kWbJkid59911NmDBBhYWFIc/U0dEhr9ertWvXat26dXrzzTe1Z88e//ilj62kpKSw7FegXCdOnNC9996roqIivfXWW6qrq9Nf/vKXkGb67LPP5DiO8vPzlZ2drfLyco0ZM8Y/HqrnYcQL+4IjR44oLy9Py5Yt08SJE/1f9/l8crn+/+MGjTF9bkcq18iRI/WHP/xBqampio2NVV5enj744IOw5XrmmWdUW1urpqYmvfXWW/6vR3K/rpYpUnu1adMmTZgwQV6v94rjV9qbcOxVoFyStHbtWt11111yuVxatGiRdu/eHfJc3/3ud7V69WqNHj1a48aN0/z58/v8O0XqsRUoV0pKitauXaukpCSNGDFCjz/+eMgfX47jqLa2VkVFRdq4caPq6+tVUVHhHw/VXkVFYe/fv19PPvmknn32WT300EN9xpKTk9Xa2uq/feLECSUlJUU8V2NjY5+f4saYsLwQevToUR0+fFiSNGLECKWlpemTTz7xj0divwJlitRebdmyRXv27FF2drZKSkq0a9cuFRUV+cfHjRunM2fOyHEcSVJra2tYHluBcp05c0br1q3z3zbGyO12hzxXXV2damtr+6x78b/TpY+tcO1XoFyffPKJtm/fftXxUBg/fry8Xq/GjRun4cOHa/bs2aqvr/ePh+p5GPHCbmpq0tNPP61XX31VmZmZl43ffPPNGjZsmPbv3y9Jqqqq0v333x/xXMOHD9eaNWvU0NAgY4w2bNgQ8lelJemLL75QQUGBenp61NPTo7/+9a+66667/OOR2K9AmSK1V6+//ro2b96sqqoqPfPMM/rhD3+oFStW+Mfj4uJ09913a8uWLZKkysrKsDy2AuVKSEjQH//4R3300UeSpPXr14dlv86cOaPVq1eru7tbZ8+eVUVFRZ91p06dqk8//dR/OmDz5s1h2a9AuYwxKioq0unTp9Xb26uNGzeGfL9mzZql6upqdXR0yHEc7d69W5MmTfKPh+x5eM0vW16jl19+2dx5551m3rx5/v/Ky8vNokWLTH19vTHGmMOHD5uHH37YpKenm1/84hemu7s7KnJt27bNZGZmmrS0NLN8+fKw5DLGmJKSEpORkWHmzp1rSkpKjDEm4vsVKFOk9uqCt99+2/9ujBUrVpj333/fGGPMF198YRYuXGgyMjJMXl6eOXXqVFTk2rdvn8nJyTEPPvigyc/PNx0dHWHJU1xcbB588EGTlpZm1q1bZ4wxZt68eaa5udkY8/U7W7KyskxaWpp55ZVXjM/ni4pc69evNxkZGeaBBx4wa9asCUumTZs2+R/TL730knEcJ+TPQ37jDABYIuKnRAAAwaGwAcASFDYAWILCBgBLUNgAYAkKGwAsQWEDgCUobACwxP8Crg9i8bnQB6UAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "plt.scatter(X[:, 0], X[:, 1], s=100)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Compute the squared distance between each pair of points" ] }, { "cell_type": "code", "execution_count": 76, "metadata": {}, "outputs": [], "source": [ "dist_sq = np.sum((X[:, np.newaxis, :] - X[np.newaxis, :, :]) ** 2, axis=-1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Break the code above down into its component steps:" ] }, { "cell_type": "code", "execution_count": 77, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(5, 5, 2)" ] }, "execution_count": 77, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# for each pair of points, compute differences in their coordinates\n", "differences = X[:, np.newaxis, :] - X[np.newaxis, :, :]\n", "differences.shape" ] }, { "cell_type": "code", "execution_count": 78, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(5, 5, 2)" ] }, "execution_count": 78, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# square the coordinate differences\n", "sq_differences = differences ** 2\n", "sq_differences.shape" ] }, { "cell_type": "code", "execution_count": 79, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(5, 5)" ] }, "execution_count": 79, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# sum the coordinate differences to get the squared distance\n", "dist_sq = sq_differences.sum(-1)\n", "dist_sq.shape" ] }, { "cell_type": "code", "execution_count": 80, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([0, 0, 0, 0, 0])" ] }, "execution_count": 80, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# double check: whether the diagonal of this matrix is all zero\n", "dist_sq.diagonal()" ] }, { "cell_type": "code", "execution_count": 81, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[ 0, 16, 0, 85, 52],\n", " [16, 0, 16, 29, 20],\n", " [ 0, 16, 0, 85, 52],\n", " [85, 29, 85, 0, 13],\n", " [52, 20, 52, 13, 0]])" ] }, "execution_count": 81, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dist_sq" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Use `np.argsort` to sort along each row\n", "\n", "The leftmost columns will then give the indices of the nearest neighbors" ] }, { "cell_type": "code", "execution_count": 82, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[0, 2, 1, 4, 3],\n", " [1, 0, 2, 4, 3],\n", " [0, 2, 1, 4, 3],\n", " [3, 4, 1, 0, 2],\n", " [4, 3, 1, 0, 2]])" ] }, "execution_count": 82, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nearest = np.argsort(dist_sq, axis=1)\n", "nearest" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first column gives the numbers 0 through 9 in order: this is due to the fact that each point's closest neighbor is itself.\n", "\n", "If we're simply interested in the nearest $k$ neighbors, all we need is to partition each row so that the smallest $k+1$ squared distances come first, with larger distances filling the remaining positions of the array." ] }, { "cell_type": "code", "execution_count": 83, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[2, 0, 1, 4, 3],\n", " [1, 2, 0, 4, 3],\n", " [2, 0, 1, 4, 3],\n", " [3, 4, 1, 0, 2],\n", " [3, 4, 1, 0, 2]])" ] }, "execution_count": 83, "metadata": {}, "output_type": "execute_result" } ], "source": [ "K = 2\n", "nearest_partition = np.argpartition(dist_sq, K + 1, axis=1)\n", "nearest_partition" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Visualization\n", "\n", "Plot the points along with lines representing the connections from each point to its two nearest neighbors" ] }, { "cell_type": "code", "execution_count": 84, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWwAAAD7CAYAAABOi672AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3deVxN+f8H8Ne9rSpEWkjLvTfbYDCWRFOylCQRxjZjH/swWbKFEULMhAljG8bSDxnJHiNbaizZQrYWRbQp7du9n98fw525X0uLbueeej8fD4+H2zl1Xve499XxuedzjoAxxkAIIUTlCbkOQAghpGyosAkhhCeosAkhhCeosAkhhCeosAkhhCeosAkhhCeosAkhhCfUlb2BjIxcyGQVO9XbwEAP6ek5lZzo81Gu8lHFXKqYCaBc5aWKuT43k1AoQL16uh9cpvTClslYhQv73ferIspVPqqYSxUzAZSrvFQxl7Iy0ZAIIYTwBBU2IYTwhNKHRAhRFSkZeQi5loiI+69QWCSFlqYabFqawKmTGYzq6XAdj5BSUWGTGuFuTDo2HYmCVMogfTu+WFAkxaU7Sbhy7yWm9G+NLyUGHKck5NNoSIRUeykZedh0JApFxTJ5Wb8jlTEUFcuw6UgUUjLyOEpISNlQYZNqL+RaIqTST39qL5UynLmeWEWJCKkYKmxS7UXcf6VwZJ2WeB/hBxbgTUqs/GtSGUPEvVdcxCOkzGgMm1R7BUVS+d9fPLyEOyH+kEmLcHnvTNSqY4SmNkNh1rK7wnqEqCI6wibVnramGkqK8nH79HrcOvkL6hqJ0La3B+oYipCflYI7IRtw6tehiL60A3l5NI5NVBcdYZNqr3Gt19j22zzkvklGE+tv0MRmCIRCNTT+wh752Wm4f347kmOv4+mNYxCLTWFnZ4+VK9dCIrHiOjohCqiwSbUlk8mwadOv8F/pDQ3turAZ5A0Ds1YK69Sq3QAd+s2DuqAExnlXcOD/duLChVDY2HwFK6umWLhwCVxcXDl6BoQooiERUi0lJ7/CkCED4O29CI69emNf4Fk0FH8JNaFAYT01oQCaGkJMG9Qey5YuxePHCdi5cx+srJri6dPHGDNmBJo2NcfKlctRUlLC0bMh5B9U2KTa+euvEDg4dMHVqxFYs2Yddu7cC9uvJPAe2wn2bRuhlqYaBAKglqYa7Ns2gvfYTgqTZlxcXBEefgMRETfh4NADWVnZ8PPzhbm5EUaPHo6kpBccPjtSkwkYY0q91FV6ek6Fr1xlaFgbqanZlZzo81Gu8qmqXIWFhVi2bDG2bt2MFi1aYsuW39G8eYvPzpSXlwcfH28EBOxGTs4/l81s2bIVfvppBeztHSotf3lzVSXKVXafm0koFMDAQO/Dyyr8UwlRIU+ePEbv3t2xdetmjBs3ASEh5z9a1uWlo6OD5ctXITY2CRs2bIaZmTnu37+HwYPd0LKlFfz910Mmk1XKtgj5FCpswmuMMezd+wd69bLDy5cvsGfPAaxcuRba2tpK2d7QoSMQGXkPoaFhsLa2QVpaKry9F8HCwhhTp05AenqaUrZLCECFTXgsMzMD48ePwsyZP6B9+064cCECTk7OVbLtVq2+xLFjIXj06BlGjBgJgUCAwMD9+OILCZyde+DWrcgqyUFqFipswkt//x2B7t1tcerUcXh5LUVg4BGYmDSs8hz6+vrw8/NHfPwr+Pj4wtjYBJGR1+Hk5IC2bVvgjz9+p+ESUmmosAmvlJSUYM2alejf3xlqamo4fvwMpk/3gFDI7UtZKBRi/PhJuHv3EY4ePY22bb9CUtILzJnzI0SiRpgz50f5B5aEVBQVNuGN588TMWCAC9asWQl398EIDQ3DV1914DrWezp37oIzZy4gKuoJ3NzcUVJSjD/++B1WVo3h7t4XDx9Gcx2R8BQVNuGFY8eOwMGhK+7di8LGjVuxadM21K5dh+tYn2RsbIxt23bh2bNkzJvnBX39eggLuwQ7O2tYW7dFUNCfXEckPEOFTVRabm4uZs78AePGjYREIkFoaBgGDx7KdaxyUVdXx8yZnnj4MA4BAYfQvHkLxMXFYuLEMZBIGmPp0kUoKiriOibhASpsorKiou7C0dEe+/btxvTpM3Hs2BmIRGKuY32Wnj0dcenSVURGRsHR0Rl5ebnYuHE9LCyMMWLEN3j27BnXEYkKo8ImKocxhi1bNsLZuTuysrIQGBgML6+foKGhwXW0SmNmZoG9ew8gLu4lpk6dAR0dXZw9exqWlpaws7PGuXNnuY5IVBAVNlEpqampGDFiMBYtmg8Hhx64cCECdnbduI6lNNra2liyZBliYp5jy5adsLKywsOH0Rg2bCCaNxfhl1986aJTRK5MhR0cHAwXFxe4uLhg9erVys5Eaqjz58+hWzcbXL58EStXrsHu3fthYFBz7mQ+YMBAPHnyBJcuXYWtrR0yMzOwatVyWFgY4/vvRyM5OZnriIRjpRZ2fn4+VqxYgT179iA4OBg3btxAeHh4VWQjNURRURGWLl2EIUMGoF69ejh9+jzGjZsIgUBQ+jdXQ82bt8Dhw8fx9OlzjB49DhoaGggOPozWrZugVy97/P03vf9qqlILWyqVQiaTIT8/HyUlJSgpKYGWllZVZCM1QGzsU/Tt2wsbN67HyJFjcebMRbRs2ar0b6wB9PT04Ovrh9jYJKxdux6NGpnizp1b6NevN1q3boqtWzfTLMoaptTC1tPTw4wZM+Ds7Ax7e3uYmpriq6++qopspBpjjGH//n3o3v1rxMfH4fff92Lt2nXQ0dHhOprKEQqFGDlyDG7fjsapU+fQvn1HpKQkw8trLiwtTeDhMQ2ZmZlcxyRVgZUiOjqaubm5sbS0NFZYWMh++OEHtm3bttK+jZCPyszMZMOGDWMAmJ2dHUtISOA6Eu+kpqay7777jmlpaTEATCAQsK+//prdunWL62hEiUq9gcH27duRnp6OuXPnAgAuXLiAgIAAbN26tUy/EOgGBlWHD7lu3LiGSZPG48WLRMyZMx8zZsyCmpoap5lUSXlzvbtv5ebNvyI1NQUAYGZmjjlz5mPo0BGc5aoqqpiL0xsYNG/eHOHh4cjLywNjDKGhoWjdunWFw5CaSSqVYt26tXB1dQJjMgQHn8bMmZ6clHV1IhQKMW3aDNy//xSBgcFo1ao1EhMTMH36ZIhEjeDlNQ95eXlcxySVpNTCtrW1hYuLC9zd3dGvXz+UlJRgwoQJVZGNVBMvXrzAoEH94OPjDVdXN4SGhqFTJ2uuY1U79vYOCA29gtu3o9GnT18UFhZg69ZNEItNMWTIAMTEPOU6IvlMdE/HCqBcZXfq1Al4eExFQUEhVq5cg6FDR6jE6XqquK+Ays1VVFSEn3/2xc6dW+UfSlpZNcXChUvg4uLKWa7KpIq56J6OhHfy8/Ph6emBUaOGwdLSEufOXcKwYd+qRFnXFJqampg/3wuPHydg5859sLJqiqdPH2PMmBFo2tQcK1cup1mUPEOFTSpddPQDODl1w65dOzB58g8IDw+HRNKE61g1mouLK8LDbyAi4iYcHHogKysbfn6+MDc3wujRw5GU9ILriKQMqLBJpWGMYceOrXB0tEd6ejr27z+MpUtX0EQrFSKRWOHAgSDExr7AhAlToKWljZMnj6Nt2xZwcOiCixfPcx2RfAIVNqkU6enpGDVqGObPn42uXb/G+fPh6N69J9exyEfo6Ohg+fJViItLwoYNm2FmZo779+9h8GA3tGxpBX//9TSLUgVRYZPPFhZ2CQ4OXXDu3Fl4e/sgIOAQjIyMuI5Fymjo0BGIjLyH0NAwWFvbIC0tFd7ei2BhYYypUycgI+M11xHJW1TYpMKKi4vh4+ONgQNdoaenh9OnQzFp0jTOb4hLKqZVqy9x7FgIHj16hhEjRkIgECAwcD+aNxfBxsYGt25Fch2xxqN3FqmQ+Pg49OvnhHXr1mL48O9w9uwltG7dhutYpBLo6+vDz88f8fGv4OPjCyMjY/z9999wcnJAu3ZfYPfunTRcwhEqbFJuf/55EN272+LJkyfYtm0X/Pz8oaury3UsUsmEQiHGj5+EqKjHuHz5Mtq0aYcXL55j9uwZEIsbwdPTAzk5OVzHrFGosEmZ5eRkY9q0iZg8eTxatPgCoaFhcHNz5zoWqQK2trY4e/YioqKewM3NHcXFxdi1awesrBrD3b0vHj6M5jpijUCFTcrk9u2b6NHjaxw6dACzZs1FcPApmJtbcB2LVDFjY2Ns27YLz54lY948L+jr10NY2CXY2VnD2rotgoL+5DpitUaFTT5JJpPB3389+vTpicLCQgQFncDcuQuhrq7OdTTCIXV1dcyc6YmHD+MQEHAIzZu3QFxcLCZOHAOJpDGWLl2EoqIirmNWO1TY5KOSk19hyJAB8PZeBCenPjh//gpsbLpyHYuomJ49HXHp0lVERkbB0dEZeXm52LhxPSwsjDFixDdITHzGdcRqgwqbfNDZs6fRrZsNrl37G2vXrsfvv+9BvXr1uY5FVJiZmQX27j2AuLiXmDp1BnR0dHH27Gm0b98adnbWOHfuLNcReY8KmygoKCjAwoWeGDHiGxgbN8SZMxcxcuQYumgTKTNtbW0sWbIMMTHP8dtvOyASifHwYTSGDRuI5s1F+OUXX7roVAVRYRO5x48fwdm5B7Zt+w3ffz8Jp0+Holmz5lzHIjzm7j4YV6/exqVLV2Fra4fMzAysWrUcFhYm+P770UhOTuY6Iq9QYRMwxrBnzy706mWHV6+SsHfvAaxY4QttbW2uo5FqonnzFjh8+DiePn2OUaPGQl1dHcHBh9G6dVM4OnbDtWt/cx2RF6iwa7jMzAyMGzcSs2ZNR8eOnXHhQgQcHZ25jkWqKT09PaxZsw5xcUlYs2YdGjVqhNu3b6JvX0d8+WUzbN/+G82i/AQq7Brs77/D4eDQFadPn8CiRd44eDAIxsYmXMciNYBQKMSoUWNx+3Y0Tp06h/btOyI5+RUWLPCEpaUJPDymye+SQ/5FhV0DlZSUwNfXB/3794GGhgZOnDiLH374kS7aRDjRvn1HnDp1Dg8exGDw4KGQyRj27duNZs0s4OrqhHv37nIdUWXQO7SGSUxMQP/+fbB27SoMGjQEoaFhaNeuPdexCIGBQQNs3LgVCQnJWLx4GRo0MMTVqxHo3t0W7du3wv79+7iOyDkq7Brk6NEgODh0xYMH97F583b4+2+Bnl5trmMRokAoFGLatBm4f/8pAgOD0bJlKyQmJmD69MkQiRrBy2se8vLyuI7JCSrsGiA3NxceHtMwfvwoWFlZITQ0DAMHfsN1LEJKZW/vgPPnw3H7djT69OmLwsICbN26CWKxKYYMGYAnT55wHbFKUWFXc1FRd9Crlx0CAvZgxoxZOHbsDCwtRVzHIqRcGjUyxa5dAYiPfwUPD0/UqVMb58+fQ9OmTdGlSwecOnWC64hVggq7mmKMYcuWjXB27oHs7GwcOnQUCxcugYaGBtfRCKkwTU1NzJ/vhcePE7Bz5z40b94cT58+xqhRw9C0qTlWr15erWdRUmFXQ6mpqRg+fBAWLZoPB4ceuHAhAl9/bc91LEIqlYuLK6KjoxEeHolu3bojKysLP//sC3NzI4wZ8y2Skl5wHbHSUWFXM+fPn0O3bjYIC7uElSvXYvfu/TAwMOA6FiFKY2XVBAcPHkFsbBK+/34StLS0ceLEUbRt2wLdu3fF5csXuY5Yaaiwq4mioiLMnj0bQ4YMgIGBAUJCLmDcuAl00SZSY+jo6GDFCl/ExSVhw4bNMDMzx717URg40BUtW1rB338972dRUmFXAzExT9CnT0/8/PPPGD16HEJCLuCLL1pyHYsQzgwdOgKRkfcQGhoGa2sbpKWlwtt7ESwsjDF16gRkZLzmOmKFUGHzGGMM+/fvQ48edkhMfIagoCD4+vqhVq1aXEcjRCW0avUljh0LwaNHzzBixEgIBAIEBu5H8+YiODv3wK1bkVxHLBcqbJ7KynqDSZPGYvr0yWjbth3Onw9H//79uY5FiErS19eHn58/4uNfwcfHF0ZGxoiMvA4nJwe0a/cFdu/eyYvhEipsHrp+/Sq6d7fF0aNHMH/+Ivz55zE0amTKdSxCVJ5QKMT48ZMQFfUYR4+eRps27fDixXPMnj0DYnEjeHp6ICcnh+uYH0WFzSNSqRR+fmvQr19vAMDRo6fh4TEHampqHCcjhH86d+6Cs2cvIirqCdzc3FFcXIxdu3bAyqox3N374uHDaK4jvocKmyeSkl5g0KB+WLlyGdzcBiA0NAwdO1pzHYsQ3jM2Nsa2bbvw7Fky5s3zgr6+PsLCLsHOzhrW1u0QHHyY64hyVNg8cPLkcTg4dMGtWzexYcNmbN68A3Xq1OU6FiHVirq6OmbO9MTDh/EICDiEZs2aIy4uBt9/PxpWVo3h7b0YRUVFnGakwlZh+fn5mDPHA6NHD4e5uSXOnbuEoUNH0LnVhChZz56OuHz5Gq5fv4tevXojNzcX/v7rYGFhjG+/HYLExGcK66dk5GFPyCNM+eUi+s0KxpRfLmJPyCOkZFTuVQXLVNihoaFwd3eHs7Mzli9fXqkByIc9eHAfTk7d8McfOzBlynScOHEWEkkTrmMRUqNYWFhi376DiIt7ialTZ0BHRxdnzpxC+/atYWdnjXPnzuJuTDoW/34Nl+4koaBICgagoEiKS3eSsPj3a7gbk15peUot7MTERCxZsgSbNm3C0aNH8eDBA1y8WH2meqoaxhh27NgKJ6duSE9Px4EDQfjpp+XQ1NTkOhohNZa2tjaWLFmGmJjn+O23HRCJxHj4MBrDhg1En+5tcO/yfhSXFCt8j1TGUFQsw6YjUZV2pF1qYZ89exZ9+vSBiYkJNDQ04OfnhzZt2lTKxomi9PR0jBo1DPPnz4atrR0uXIiAg0MPrmMRQv7D3X0wrl69jUuXrsLqiw4oKsjG4/AAnNowFJHH16AgJ0NhfamU4cz1xErZdqmF/ezZM0ilUkyaNAlubm4ICAhA3br0gVdlu3z5IhwcuiA09C8sW7YS+/YFwtDQkOtYhJAPYIyhbt26aNTGHS27jUNtQ0swJsPLx1fw19YxyMtOla8rlTFE3HtVKdtVL20FqVSKGzduYM+ePdDR0cHkyZMRFBQEd3f3Mm3AwEDvswIaGqrmLawqK1dxcTEWL16M1atXo2nTpjh58gTatWvHea7Kpoq5VDETQLnKS1m5GGNITk7GkydP3vvz9OlThduUCdU0oFfPFAI1NYAxaNXSV/hZBcXSSslZamE3aNAANjY2qF+/PgCgZ8+euHv3bpkLOz09BzIZq1A4Q8PaSE3NrtD3KlNl5YqLi8XkyeNw82Ykvv12FJYtWwVdXd0K/+zqvr8qkypmAihXeX1uLsYY0tPTERsbg9jYp4iLi0FsbCxiY2MQFxeLnJx/f7a6ujosLCwhFktgY2MLkUiCE7dyoaFnjFq1G0Ag/PgENm0NtTLnFAoFHz3QLbWwHRwcMHfuXGRlZUFXVxeXL19Gjx40rvq5Dh06AE/PmRAKhdi+/Q/06zeA60iEVFsZGa/flnLM2zJ+9/dYZGW9ka+npqYGMzNziMUSWFt3hlgsgVgsgUgkgZmZOdTVFStTI+QRLt1JgvQTB6VqQgFsWplUyvMotbDbtGmD8ePHY/jw4SguLkbXrl0xcODAStl4TZSTk425c2chMHA/OnXqjM2bt8PMzJzrWITwXnZ2lkIpvztqjo2NQUbGvx8ECgQCmJmZQyQSY+DAwfJSFoslMDOzKNcZWU6dzHDl3stPF7aaAI4dzT7rub1TamEDwKBBgzBo0KBK2WBNdutWJCZOHIuEhGeYPXseZs70fO83NiHk43JychAXFys/Qk5KSsCDBw8RGxuDtLRUhXVNTRtDLJbA1XWAQilbWFhCS0urUvIY1dPBlP6tselIFKRSplDcakIB1NQEmNK/NYzq6VTK9qgtqoBMJsPGjRuwcqU3jI1NcOTISXTu3IXrWISopPz8fMTFxX5g+CIGycmKZ1s0bNgQlpZiODk5QyT6t5QtLUXQ0amckizNlxIDeI/thDPXExFx7xUKiqXQ1lCDTSsTOHY0q7SyBqiwlS45+RWmTp2IS5fOw9W1P37+eT309etxHYsQThUWFiI+Pu6D48r/e/PcBg0MIRZL4ODQQ2FMWSQSQyRqqBIfhhrV08G3js3wrWMzpX5AS4WtRGfOnMKMGVOQl5eHX375VX7HC0JqguLiYiQkxCuUckzMP8X8/HkiGPt3+KB+/foQiSTo2vVrheELkUhMFzr7DypsJSgoKIC39yJs374FLVu2xpYtv6Np02ZcxyKk0pWUlCAxMUFh2OLdn8TEBEilUvm6devqQywWo2NHawwZMlyhmOl/nWVDhV3JHj9+hAkTxuDBg3uYMGEyvLyWQltbm+tYhFSYVCpFfHw8rl+/896YckLCMxQX/3sNDV1dPYjFErRp0w4DBgx8O65sBbFYAgMDA/of5meiwq4kjDHs2bMLixbNg66uLgICAtGzpxPXsQgpE5lMhpcvkz44pvzsWTwKCwvl6+ro6MDSUowWLVrCxaWfwriykZERlbISUWFXgoyM15g5czpOnDgKe3sH+PtvgbFx5ZwoT0hlYYwhJSX5g+cqx8fHIT8/X76ulpYWRCIxJJIm6NWrN9q0aQlDQ1OIxRKYmDSkUuYIFfZnioi4gsmTxyMlJRlLlizH5MnTIBTSfSEINxhjSEtLe2/o4t1U69zcf28wq6GhAUtLEcRiCeztuyuMKTdqZKrwOlbVqek1DRV2BZWUlGDt2lVYt24tLCwscfLkX2jb9iuuY5Ea4vXr9A8MX/xz7nJ2dpZ8PTU1NZibW7y9/kUX+dCFWCxB48ZmNHGLZ+hfqwLi4+PxzTdDcf36VQwZMhwrV66Bnp5qXsmM8NebN5nvDV+8O2rOzMyUrycUCtG4sTnEYjEGDx7y3lRrDQ0NDp8FqUxU2OUUHHwYs2fPgFQqw+bN2zFw4DdcRyI8lpOTrTCr79+p1k+Rnv7vraUEAgFMTRtDJJLAzW2gQimbm1tU2lRrotqosMsoNzcXCxd6IiBgD6ytrfHrr1thaSniOhbhgby8PHkp/++4ckpKssK6pqamsLQUo08fV4Wp1hYWlqhVqxZHz4CoCirsMoiKuoMJE8YgNjYGP/44G76+PsjMLOA6FlEhBQUFClOt/1vML18mKaxraGgEsViCHj16vTfV2tLShD7cIx9Fhf0JMpkMW7duwvLlP6F+fQP8+ecx2NravR0TpMKuaYqKivDsWfwHx5VfvHiuMNXawMAAIpEEX39t/95U69q163D4LAifUWF/REpKCqZPn4TQ0L/Qu7cL1q3zR/36BlzHIkpWUlKChIRnCkfIMTFPERsbi+fPEyCTyeTr6uvrv73QvY1CKYvFEtStq/+JrRBSMVTYHxAa+hd++GESsrOzsGrVzxgzZjxNFKhGpFIp4uLiPjrVuqSkRL6unl5tSCRWaN++PQYN+kahlOkXOKlqVNj/UVhYiBUrluK33/zRvHkLHDp0FC1afMF1LFIBMpkMSUkvPjrVuqioSL6ujo4uRCIxWrZsDVfX/grnKhsaGtIva6IyqLDfiol5gokTx+Hu3dsYM2Y8fvppBX0qr+IYY3j16uUHx5Tj4+NQUPDv5wza2toQicRo0qQZnJz6KEy1NjY2oVImvFDjC5sxhv3792H+/DnQ0tLEH3/8H5ydXbiORd5ijCE1NVXhCPmfMeUYxMfHIi8vT76upqamfKq1g0NPheGLhg0b0VRrwns1urDfvMnEnDk/4siRw7C1tcPGjVvRsGEjrmPVOIwxvH79Wn7D1P/e0To2NgY5Of8Wq7q6OiwsLCEWS/D113YK5yqbmjaGmpoah8+EEOWqsYV97dpVTJ48DklJL7Bw4RJMm/YjvdmVLDMz4yNTrWPx5o3iVGszM3OIxRJ07NhJ4Vxlc3MLuv4FqbFq3CtfKpVi3bq1WLt2FUxNzXDsWAg6dOjEdaxqIzs76wN3HonH48eP8fr1a/l6AoEAjRubQSSSYMCA/061toK5uQU0NTU5fBaEqKYaVdgvXjzH1KkTEB4eBnf3QfD19aP7xVVAbm4u4uJiP3CucgzS0lIV1m3UyBTNmjWFi4ubwpiyhYUl3YmHkHKqMYV94sQxeHhMRVFRMTZs2IwhQ4bTmQGfkJ+f/9Gp1q9evVRY18jIGBKJFZycnBXGlC0tRdDR0aEP+AipJNW+sPPy8rB48QLs3v072rRphy1bdkAstuI6lkooLCx8b6r1u2JOSnqhMNW6QYMGEIkksLd3eG+qNV1alpCqUa0L+8GD+5g4cQwePXqIqVNnYP78RTVubLS4uBgJCR+6/kUsnj9PVJhqXa9evbcXuu/63lRrGjoihHvVsrAZY/j996346Scv1K2rj4MHj6Bbt+5cx1KakpISPH+eiJs3X+LWrSiFMeXExARIpVL5unXq1IVYLEaHDh0xePBQhVKuV68+h8+CEFKaalfY6enp+PHHKQgJOYWePR2xfv1mGBoach3rs8lkMrx48fyjU62Li4vl6+rq6kEslqBNm3YYMGDg23FlK4jFEhgYGNDYPSE8Va0K+9KlC5g6dQIyMl5j+fJV+P77ybwqJ5lM9smp1oWFhfJ1a9WqBUtLMZo1awFn574QiyVo3/5L1KvXEEZGRrx63oSQsqkWhV1cXIzVq1fg11/9YGXVBAEBh9C69Zdcx/ogxhhSUpLfK+V3U63z8/Pl62ppacHSUgSRSIIePRwVhi9MTBq+d3d2OhuDkOqN94UdFxeLyZPH4ebNSHz33Wh4e6+Erq4up5kYY0hPf3dX66fy2XwxMU8RFxeL3Nwc+boaGhryqdZ2dt0USrlRI1OafUkIkeN1YQcG7sfcubOgpqaGHTt2w9W1f5VuPyPj9QfHlGNjY5GV9Ua+npqaGszNLd6egdFF4fKdjRub0VRrQkiZ8LIpsrOzMHfuLBw6dACdO3fBpk3b0LixmVK2lZX15qNTrTMyMuTrCQQCmJmZQyQSY+DAwfKjZInECmZmFm9vK0YIIRXHu8K+efMGJk4ci8TEBHh6LsCPP87+7CPUnJyc9+5m/e6IOUA2ImMAAA82SURBVC0tTWFdU9PGaNasKVxdB7w31VpLS+uzchBCyKeoXGGnZOQh5FoiIu6/QmGRFFqaarBpaYJeHUxxcN9WrFq1HCYmDXHkyCl07mxT5p+bl5f3wanWMTFPkZKSrLCuiUlDiMUS9O7t8t5U61q1atGHe4QQTpS5sFevXo2MjAysWrVKaWHuxqRj05EoSKUMUtk/06ILiqQIuRKFVV7jkfrsDvr1G4C1a9dBX7/ee99fUFDwyanW/2VoaASxWIIePXopXL5TJBJz/qElIYR8SJkKOyIiAkFBQejWrZvSgqRk5GHTkSgUFcsUvp4ccw23Q36FrKQIX/Wehp+Wz0FaWhquXfv7P8X8z5Xjnj9PVLj+Rf369SESSdC169cKY8oikRi1a9dR2nMhhBBlKLWwMzMz4efnh0mTJuHhw4dKCxJyLRFS6b9lW1JciFsnfkZy7DVoaNdBHSMxHkYcQoe2myGT/TvVum5dfYjFYnTsaI0hQ4YrjCt/6CicEEL4qtTCXrx4MTw8PPDy5cvSVv0sEfdfyYdBAOCvreNQUvjP+coyaTFkJYXQN7FC3Zb2mDLs3RXjrFC/fn2a1UcIqRE+WdiBgYFo2LAhbGxscPjw4QptwMBAr0zrFRZJFR6/K+teE3dBU6euvJQFAmDaNLcKZalMhoaqeUlRylV2qpgJoFzlpYq5lJXpk4V98uRJpKamws3NDW/evEFeXh58fHywYMGCMm8gPT0Hsv8cOX+MlqYaCv6ntAFAS1df4bG2hhrnZ2io6lkilKvsVDETQLnKSxVzfW4moVDw0QPdTxb2zp075X8/fPgwrl27Vq6yLg+blia4dCdJYVjkf6kJBbBpZaKU7RNCiKoTlr5K1XDqZAY1tU+PRaupCeDYUTkzGgkhRNWVubDd3d2Veg62UT0dTOnfGpoaQqgJFYtbTSiApoYQU/q3hlE9HaVlIIQQVaZSMx2/lBjAe2wnnLmeiOC3X6ulqQabViZw7GhGZU0IqdFUqrCBf460v3VshplvH2+cac9pHkIIURUqM4ZNCCHk06iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ6iwCSGEJ9TLspK/vz9OnToFALC3t4enp6dSQxFCCHlfqUfY4eHhCAsLQ1BQEI4cOYL79+/j7NmzVZGNEELIf5R6hG1oaIh58+ZBU1MTACCRSJCUlKT0YIQQQhQJGGOsrCvHx8dj2LBh+L//+z9YWloqMRYgEAgAAOWIRwgh1VqZxrAB4MmTJ5g4cSI8PT3LVdbp6TmQySpeuqmp2RX+XmUxNKxNucpBFXOpYiaAcpWXKub63ExCoQAGBnofXlaWHxAZGYnRo0dj1qxZGDBgQIWDEEIIqbhSj7BfvnyJqVOnws/PDzY2NlWRiRBCyAeUWtg7duxAYWEhVq1aJf/a0KFDMWzYMKUGI4QQoqjUwvby8oKXl1dVZCGEEPIJNNOREEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4ggqbEEJ4Qp3rAP8rOv419v31RP547KpQNGqgixE9m6CFZX0OkxFCCLfKdIR97Ngx9OnTB46Ojti3b5/SwgSHxWHN/ttISstV+HpSWi7W7L+N4LA4pW2bEEJUXamFnZycDD8/PwQEBODIkSM4cOAAnj59WulBouNfl1rIwWFxiI5/XenbJoQQPii1sMPDw9G5c2fo6+tDR0cHTk5OOH36dKUH+e8wyKcElHE9Qgipbkot7JSUFBgaGsofGxkZITk5udKD/O8wyMe8KON6hBBS3ZT6oaNMJoNAIJA/ZowpPC6NgYFehYLp1jP96DJDw9oV+pmVSRUyfAjlKjtVzARQrvJSxVzKylRqYZuYmODGjRvyx6mpqTAyMirzBtLTcyCTsXIHcxiz8aPLUlOzy/3zKpOhYW3OM3wI5So7VcwEUK7yUsVcn5tJKBR89EC31CGRLl26ICIiAq9fv0Z+fj7OnDkDOzu7Cof5mEYNdMu0nmkZ1yOEkOqm1MI2NjaGh4cHRo4cif79+6Nv37748ssvKz3IiJ5NyrTe8DKuRwgh1U2ZJs64urrC1dVVqUFaWNaHm63ok6f2udmKaPIMIaTGUqmZjm62IjRtXBcBfz1ROBvEtIEuhtNMR0JIDadShQ38c6S9bLw1ANX8QIEQQrhCF38ihBCeoMImhBCeUPqQiFBY9kk2yvh+ZaFc5aOKuVQxE0C5yksVc31Opk99r4AxVv5ZLYQQQqocDYkQQghPUGETQghPUGETQghPUGETQghPUGETQghPUGETQghPUGETQghPUGETQghPUGETQghPqMTV+vz9/XHq1CkAgL29PTw9PRWWR0dHY+HChcjNzUWHDh2wdOlSqKsrP3ppufz9/fHnn3+iTp06AIBvvvkGI0aMUHqu9evXIyQkBAKBAIMGDcKYMWMUlnOxv0rLxNW+emf16tXIyMjAqlWrFL6elJSEOXPmID09HSKRCGvXroWubtXd1ehjuYKCgvDzzz/DwMAAANCtWzd4eHgoPc93332H169fy18v3t7eaNOmjXx5eHg4Vq5cicLCQjg7O1dJprLkmj9/PiIjI1GrVi0AwLRp09CrVy+lZgoNDYW/vz/y8/PRtWtXeHl5KSxXyvuQcezKlStsyJAhrLCwkBUVFbGRI0eyM2fOKKzj4uLCbt26xRhjbP78+Wzfvn0qkWvixIns5s2bSs/yX1evXmVDhw5lxcXFLD8/nzk4OLCYmBiFdap6f5UlExf76p3w8HBmbW3N5s6d+96yCRMmsOPHjzPGGPP392e+vr4qkcvb25sdO3asyrIwxphMJmO2trasuLj4g8vz8/OZvb09S0hIYMXFxWzs2LHswoULnOdijLG+ffuy5ORkpWd5JyEhgdna2rKXL1+yoqIiNmzYsPf2hTLeh5wPiRgaGmLevHnQ1NSEhoYGJBIJkpKS5MtfvHiBgoICtG3bFgDg7u6O06dPc54LAO7du4ctW7bA1dUV3t7eKCwsVHquTp06Yffu3VBXV0d6ejqkUil0dHTky7nYX6VlArjZVwCQmZkJPz8/TJo06b1lxcXFuH79OpycnABU3WurtFwAEBUVhaCgILi6umL27Nl48+aN0jPFxsYCAMaOHYt+/fph7969Csvv3r0LCwsLmJmZQV1dHa6urlWyv0rLlZ+fj6SkJCxYsACurq7YsGEDZDKZUjOdPXsWffr0gYmJCTQ0NODn56dwxK+s9yHnhd2kSRP5k4qPj8epU6dgb28vX56SkgJDQ0P5Y0NDQyQnJ3OeKzc3Fy1atMCcOXMQFBSErKwsbNq0Sem5AEBDQwMbNmyAi4sLbGxsYGxsLF/G1f76VCYu99XixYvh4eEhH4r5r4yMDOjp6cn/m1pV+6q0XO+yTJkyBUePHkXDhg3h7e2t9ExZWVmwsbHBxo0bsWvXLuzfvx9XrlyRL//f15aRkVGV7K/ScqWlpaFz587w8fHBwYMHcePGDRw6dEipmZ49ewapVIpJkybBzc0NAQEBqFu3rny5st6HnBf2O0+ePMHYsWPh6ekJS0tL+ddlMhkEgn8vN8gYU3jMVS5dXV1s27YNEokE6urqGDt2LC5evFhluaZPn46IiAi8fPkSBw8elH+dy/31sUxc7avAwEA0bNgQNjY2H1z+oX1TFfuqtFwAsHHjRrRv3x4CgQDjx4/H5cuXlZ6rXbt28PX1Re3atVG/fn0MGjRI4d+Jq9dWabnMzMywceNGGBkZoVatWvjuu++U/vqSSqWIiIiAj48PDhw4gLt37yIoKEi+XFn7SiUKOzIyEqNHj8asWbMwYMAAhWUmJiZITU2VP05LS4ORkRHnuZKSkhR+izPGquSD0JiYGERHRwMAatWqBUdHRzx69Ei+nIv9VVomrvbVyZMnceXKFbi5uWHDhg0IDQ2Fj4+PfHn9+vWRnZ0NqVQKAEhNTa2S11ZpubKzs7Fr1y75Y8YY1NTUlJ7rxo0biIiIUNjuf/+d/ve1VVX7q7Rcjx49QkhIyEeXK0ODBg1gY2OD+vXrQ1tbGz179sTdu3fly5X1PuS8sF++fImpU6di7dq1cHFxeW+5qakptLS0EBkZCQAIDg6GnZ0d57m0tbWxZs0aJCYmgjGGffv2Kf1TaQB4/vw5vLy8UFRUhKKiIpw7dw7t27eXL+dif5WWiat9tXPnThw/fhzBwcGYPn06unfvjgULFsiXa2hooEOHDjh58iQA4MiRI1Xy2iotl46ODrZv3447d+4AAPbu3Vsl+ys7Oxu+vr4oLCxETk4OgoKCFLbbpk0bxMXFyYcDjh8/XiX7q7RcjDH4+PjgzZs3KC4uxoEDB5S+vxwcHBAWFoasrCxIpVJcvnwZLVu2lC9X2vvwsz+2/EzLli1jbdu2Zf369ZP/CQgIYOPHj2d3795ljDEWHR3NBg4cyJycnNjMmTNZYWGhSuQ6ffo0c3FxYY6OjmzevHlVkosxxjZs2MCcnZ1Z37592YYNGxhjjPP9VVomrvbVO3/++af8bIwFCxawv/76izHG2PPnz9m3337LnJ2d2dixY1lmZqZK5Lp+/Trr378/6927N5s0aRLLysqqkjx+fn6sd+/ezNHRke3atYsxxli/fv3Yq1evGGP/nNni6urKHB0d2YoVK5hMJlOJXHv37mXOzs6sV69ebM2aNVWSKTAwUP6aXrp0KZNKpUp/H9IdZwghhCc4HxIhhBBSNlTYhBDCE1TYhBDCE1TYhBDCE1TYhBDCE1TYhBDCE1TYhBDCE1TYhBDCE/8PA33jmbsIwDAAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "plt.scatter(X[:, 0], X[:, 1], s=100)\n", "\n", "# draw lines from each point to its two nearest neighbors\n", "K = 2\n", "\n", "for i in range(X.shape[0]):\n", " for j in nearest_partition[i, :K+1]:\n", " # plot a line from X[i] to X[j]\n", " # use zip magic \n", " plt.plot(*zip(X[j], X[i]), color=\"black\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "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.10" } }, "nbformat": 4, "nbformat_minor": 4 }