{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# Nearest Neighbours and Sparse Features\n", "\n", "While trying to apply k-nearest neighbours classifier database, we might face a tricky issue. Let's try to find out what it is, why it is happening and how to solve it."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"name": "stderr", "output_type": "stream", "text": ["c:\\python370_x64\\lib\\site-packages\\ipykernel\\parentpoller.py:116: UserWarning: Parent poll failed.  If the frontend dies,\n", "                the kernel may be left running.  Please let us know\n", "                about your system (bitness, Python, etc.) at\n", "                ipython-dev@scipy.org\n", "  ipython-dev@scipy.org\"\"\")\n"]}, {"data": {"text/html": ["<div id=\"my_id_menu_nb\">run previous cell, wait for 2 seconds</div>\n", "<script>\n", "function repeat_indent_string(n){\n", "    var a = \"\" ;\n", "    for ( ; n > 0 ; --n)\n", "        a += \"    \";\n", "    return a;\n", "}\n", "// look up into all sections and builds an automated menu //\n", "var update_menu_string = function(begin, lfirst, llast, sformat, send, keep_item, begin_format, end_format) {\n", "    var anchors = document.getElementsByClassName(\"section\");\n", "    if (anchors.length == 0) {\n", "        anchors = document.getElementsByClassName(\"text_cell_render rendered_html\");\n", "    }\n", "    var i,t;\n", "    var text_menu = begin;\n", "    var text_memo = \"<pre>\\nlength:\" + anchors.length + \"\\n\";\n", "    var ind = \"\";\n", "    var memo_level = 1;\n", "    var href;\n", "    var tags = [];\n", "    var main_item = 0;\n", "    var format_open = 0;\n", "    for (i = 0; i <= llast; i++)\n", "        tags.push(\"h\" + i);\n", "\n", "    for (i = 0; i < anchors.length; i++) {\n", "        text_memo += \"**\" + anchors[i].id + \"--\\n\";\n", "\n", "        var child = null;\n", "        for(t = 0; t < tags.length; t++) {\n", "            var r = anchors[i].getElementsByTagName(tags[t]);\n", "            if (r.length > 0) {\n", "child = r[0];\n", "break;\n", "            }\n", "        }\n", "        if (child == null) {\n", "            text_memo += \"null\\n\";\n", "            continue;\n", "        }\n", "        if (anchors[i].hasAttribute(\"id\")) {\n", "            // when converted in RST\n", "            href = anchors[i].id;\n", "            text_memo += \"#1-\" + href;\n", "            // passer \u00e0 child suivant (le chercher)\n", "        }\n", "        else if (child.hasAttribute(\"id\")) {\n", "            // in a notebook\n", "            href = child.id;\n", "            text_memo += \"#2-\" + href;\n", "        }\n", "        else {\n", "            text_memo += \"#3-\" + \"*\" + \"\\n\";\n", "            continue;\n", "        }\n", "        var title = child.textContent;\n", "        var level = parseInt(child.tagName.substring(1,2));\n", "\n", "        text_memo += \"--\" + level + \"?\" + lfirst + \"--\" + title + \"\\n\";\n", "\n", "        if ((level < lfirst) || (level > llast)) {\n", "            continue ;\n", "        }\n", "        if (title.endsWith('\u00b6')) {\n", "            title = title.substring(0,title.length-1).replace(\"<\", \"&lt;\")\n", "         .replace(\">\", \"&gt;\").replace(\"&\", \"&amp;\");\n", "        }\n", "        if (title.length == 0) {\n", "            continue;\n", "        }\n", "\n", "        while (level < memo_level) {\n", "            text_menu += end_format + \"</ul>\\n\";\n", "            format_open -= 1;\n", "            memo_level -= 1;\n", "        }\n", "        if (level == lfirst) {\n", "            main_item += 1;\n", "        }\n", "        if (keep_item != -1 && main_item != keep_item + 1) {\n", "            // alert(main_item + \" - \" + level + \" - \" + keep_item);\n", "            continue;\n", "        }\n", "        while (level > memo_level) {\n", "            text_menu += \"<ul>\\n\";\n", "            memo_level += 1;\n", "        }\n", "        text_menu += repeat_indent_string(level-2);\n", "        text_menu += begin_format + sformat.replace(\"__HREF__\", href).replace(\"__TITLE__\", title);\n", "        format_open += 1;\n", "    }\n", "    while (1 < memo_level) {\n", "        text_menu += end_format + \"</ul>\\n\";\n", "        memo_level -= 1;\n", "        format_open -= 1;\n", "    }\n", "    text_menu += send;\n", "    //text_menu += \"\\n\" + text_memo;\n", "\n", "    while (format_open > 0) {\n", "        text_menu += end_format;\n", "        format_open -= 1;\n", "    }\n", "    return text_menu;\n", "};\n", "var update_menu = function() {\n", "    var sbegin = \"\";\n", "    var sformat = '<a href=\"#__HREF__\">__TITLE__</a>';\n", "    var send = \"\";\n", "    var begin_format = '<li>';\n", "    var end_format = '</li>';\n", "    var keep_item = -1;\n", "    var text_menu = update_menu_string(sbegin, 2, 4, sformat, send, keep_item,\n", "       begin_format, end_format);\n", "    var menu = document.getElementById(\"my_id_menu_nb\");\n", "    menu.innerHTML=text_menu;\n", "};\n", "window.setTimeout(update_menu,2000);\n", "            </script>"], "text/plain": ["<IPython.core.display.HTML object>"]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Get the data\n", "\n", "We use the package [mnist](https://github.com/datapythonista/mnist)."]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": ["import mnist\n", "train_images = mnist.train_images()\n", "train_labels = mnist.train_labels()\n", "test_images = mnist.test_images()\n", "test_labels = mnist.test_labels()"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"data": {"text/plain": ["((60000, 28, 28), (60000,))"]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["train_images.shape, train_labels.shape"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": ["train_X = train_images.reshape((train_images.shape[0], train_images.shape[1] * train_images.shape[2]))\n", "test_X = test_images.reshape((test_images.shape[0], test_images.shape[1] * test_images.shape[2]))"]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"data": {"text/plain": ["((60000, 784), (60000,))"]}, "execution_count": 6, "metadata": {}, "output_type": "execute_result"}], "source": ["train_X.shape, train_labels.shape"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"data": {"text/plain": ["array([[0, 0, 0, ..., 0, 0, 0],\n", "       [0, 0, 0, ..., 0, 0, 0]], dtype=uint8)"]}, "execution_count": 7, "metadata": {}, "output_type": "execute_result"}], "source": ["train_X[:2]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Train a classifier"]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"data": {"text/plain": ["KNeighborsClassifier(algorithm='kd_tree', leaf_size=30, metric='minkowski',\n", "           metric_params=None, n_jobs=1, n_neighbors=5, p=2,\n", "           weights='uniform')"]}, "execution_count": 8, "metadata": {}, "output_type": "execute_result"}], "source": ["from sklearn.neighbors import KNeighborsClassifier\n", "knn = KNeighborsClassifier(algorithm=\"kd_tree\")\n", "knn"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"data": {"text/plain": ["KNeighborsClassifier(algorithm='kd_tree', leaf_size=30, metric='minkowski',\n", "           metric_params=None, n_jobs=1, n_neighbors=5, p=2,\n", "           weights='uniform')"]}, "execution_count": 9, "metadata": {}, "output_type": "execute_result"}], "source": ["knn.fit(train_X, train_labels)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["The memory consumption is quite huge. The first hill is training, the second one is the beginning of testing."]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAscAAACxCAIAAACncIeMAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAACHnSURBVHhe7Z3/bxzlncfvX7jf7hfUSpVSlR/oLxd+uIYfriD1CtxVCFWiSnVInGSpIKRyKieR6qRCRUksIElbpwQ5FJwvlPgS1IB8ioGATWI7MTGxHcfnOLHjGJw4ziWuiUK4CPXe62d2/Hhmd3Z33s/M7j5+v/RWMjszO5+Z936e5/nMeHfmb/5ampGOn4e0dl8O5uYFomcUdGXLIx0JIewdwHTHSDBhZoZzKlJyO0IIIUSOXO5utQcgDEeGcF58zjKF9xUIBzLMSBg6CyRUFcV3FoLlPBxa0R0TbnmkI+mYSu5Air3K7kCEEEKIiiwXBq2tVlURDkxhrRGfYyiefWP28tzi/0lUUVUUps12MGGwF8WnCxMdHa3FJcV3BfsSf9na3R3MW35HcYXg5bIjKy8NwTrL7wxnR7ZsEy7qsNY3LO/AyhYwXVx5ZX/MCvGJcOdMyMiultsOCBfZcyI+CCGEEE7AEFMcGq1JDFqF4SY+J2B1VWH+rUTlqqIwVC5PrswqNWVNY2LVXHuYx8vlV+GeF5YHK6ysiqlwAyHFt1qLC/tWXLO4ONzyCiubw1R0yysLrenkmfZEsEurCeeHa66aLjMV90EIIYTgwbgSDCurxsjl2fE5wXQwyJpTXUxWNTBV872KcKwL44bT1c804OUKy9utuAX7TfGl9ltWWH3oJdcPKbe1hJnhxLLhdjAsCahmOxVnCiGEEDwYVoKxqqaqIsTUFMtjXjjAlaaav4AY7DnhdPUzDZGXoNIWViZLLS09M0LJ9UMqbi0+015qVRYrs0uumWKmEEIIwYNhpVgsWJNBPRGfE8HUFFjPLAtelqb6qsKatTJVGFKDjWNmMNd+b2EFa0ORl8BeOZy2ZmLSBMBEMNPaSMmZUUquH1JYmngI4XR8woAtLL/E7Oiu2muuTCdPrZ4WQgghSDCsFAuBlUGvOHjF56wCM4tjm1kYzihFDVXF8kyDtSict/JFyMh7i2uE+2xerozA4cor0+Y9yy/Ct1tftAw3UnJm6F1IyfVDihHspat3wMwsObFMEDB8mbydcHZxSTCn5LQQQghBgmHFGhmLQ9DKSBOfU8R+Z3EsTRqhylUVzUHhCDX+CiGEEI1BU1YVK1clVFMIIYQQDUNzX6sQQgghROOgqkIIIYQQblBVIYQQQgg3lK4q/uH3/X/7n+9JkiRJkiRFhCIhKBdilK4q8J5gimPiyo1gKmP8CwTkHoPcY5B7DHKPQe4x5BYroUhQVVEbXuaH3GOQewxyj0HuMcg9BlUVzvAyP+Qeg9xjkHsMco9B7jGoqnCGl/kh9xjkHoPcY5B7DHKPQVWFM7zMD7nHIPcY5B6D3GOQewyqKpzhZX7IPQa5xyD3GOQeg9xjUFXhDC/zQ+4xyD0Guccg9xjkHoOqCmd4mR9yj0HuMcg9BrnHIPcYVFU4w8v8kHsMco9B7jHIPQa5x6Cqwhle5ofcY5B7DHKPQe4xyD0GVRXO8DI/5B6D3GOQewxyj0HuMaiqcIaX+SH3GOQeg9xjkHsMco9BVYUzvMwPuccg9xjkHoPcY5B7DKoqnOFlfsg9BrnHIPcY5B6D3GNIU1Vg5yRJkiRJkmyZIsFUC3F0raI2cgsE5B6D3GOQewxyj0HuMeQWS1WFM7zMD7nHIPcY5B6D3GOQewyqKpzhZX7IPQa5xyD3GOQeg9xjUFXhDC/zQ+4xyD0Guccg9xjkHoOqCmd4mR9yj0HuMcg9BrnHIPcYVFU4w8v8kHsMco9B7jHIPQa5x6Cqwhle5ofcY5B7DHKPQe4xyD0GVRXO8DI/5B6D3GOQewxyj0HuMaiqcIaX+SH3GOQeg9xjkHsMco9BVYUzvMwPuccg9xjkHoPcY5B7DKoqnOFlfsg9BrnHIPcY5B6D3GNQVeEML/ND7jHIPQa5xyD3GOQeg6oKZ3iZH3KPQe4xyD0Guccg9xjSVBXYOUmSJEmSJFumSDDVQhxdq6iN3AIBuccg9xjkHoPcY5B7DLnFUlXhDC/zQ+4xyD0Guccg9xjkHoOqCmd4mR9yj0HuMcg9BrnHIPcYVFU4w8v8kHsMco9B7jHIPQa5x6Cqwhle5ofcY5B7DHKPQe4xyD0GVRXO8DI/5B6D3GOQewxyj0HuMaiqcIaX+SH3GOQeg9xjkHsMco9BVYUzvMwPuccg9xjkHoPcY5B7DKoqnOFlfsg9BrnHIPcY5B6D3GNQVeEML/ND7jHIPQa5xyD3GOQeg6oKZ3iZH3KPQe4xyD0Guccg9xhUVTjDy/yQewxyj0HuMcg9BrnHoKrCGV7mh9xjkHsMco9B7jHIPQZVFc7wMj/kHoPcY5B7DHKPQe4xpKkqsHOSJEmSJEm2TJFgqoU4ulZRG7kFAnKPQe4xyD0Guccg9xhyi6Wqwhle5ofcY5B7DHKPQe4xyD0GVRXO8DI/5B6D3GOQewxyj0HuMaiqcIaX+SH3GOQeg9xjkHsMco9BVYUzvMwPuccg9xjkHoPcY5B7DKoqnOFlfsg9BrnHIPcY5B6D3GNQVeEML/ND7jHIPQa5xyD3GOQeg6oKZ3iZH3KPQe4xyD0Guccg9xhUVTjDy/yQewxyj0HuMcg9BrnHoKrCGV7mh9xjkHsMco9B7jHIPQZVFc7wMj/kHoPcY5B7DHKPQe4xqKpwhpf5IfcY5B6D3GOQewxyj0FVhTO8zA+5xyD3GOQeg9xjkHsMaaoK7JwkSZIkSZItUySYaiGOrlXURm6BgNxjkHsMco9B7jHIPYbcYqmqcIaX+SH3GOQeg9xjkHsMco9BVYUzvMwPuccg9xjkHoPcY5B7DKoqnOFlfsg9BrnHIPcY5B6D3GNQVeEML/ND7jHIPQa5xyD3GOQeg6oKZ3iZH3KPQe4xyD0Guccg9xhUVTjDy/yQe6m5dfvrn+4bxr/B6yxR7jHIPQa5x+Cle6oqnOFlfsi91LQdu3DHr4/g3+B1lij3GOQeg9xj8NI9VRXO8DI/5F46bt3++q4Xj+48NnNP20AwK0uUewxyj0HuMXjpnqoKZ3iZH3IvHb/qntz8wbmhi4v3tw9+PHUtmJsZyj0Guccg9xgaxz2cCP3b/tGzCw72R1WFMxonPxwi91Iw/8VXd7149MrSLVQV+0/Nbdw3HCzIDOUeg9xjkHsMjePe4wfGnuuevHfncf4sSFWFMxonPxwi91LwTNfE1t7pv9z8P1QVqC1QYaDOCJZlg3KPQe4xyD2GBnGvrW/m6UPj6LJmr9+8v31w14nZYEEqVFU4o0Hywy1yr1ZG5pY2tPWjfZqqAv/iDGDzkfPB4mxQ7jHIPQa5x9AI7g1eXHygfRDnP6bXgp58e+ypP48Hi2tHVYUzGiE/nCP3amXjvuH9p+ZM4zRVxbmFG9/e0hMszgblHoPcY5B7DHV3b/6Lr+5pG0AfZbqsUDuOXXhw1+Dil7eD9WohTVWBnZMkKa4DI5e+9/t+FBMR/fOuk68OzERWliRJqqNGLy39U/vgawOzkf7KCPM3tPV3TyxE3pUsUySYaiGOrlXURm6BgNxjyC4Wqv7+6WthvY+WaSYOnb788BtDwUoZoNxjkHsMco+hvu5t6prY2jMV9ldxDc0upvj+pqoKZ9Q3PzLip/uG010EqxUP3Hv3zPwju0+tapPFqgJav63Pya+2SuJl7vkXCMg9BrnHEIn1X8Nzj745EnZQ5ZTi+5uqKpxRx/zICJSod/z6yOMHxoLXWdLs7t26/fU9bQMo7e0GaVcVW3unn+maCNZ2jX+5B/wLBOQeg9xjsGPhDGdDW7/9Dc1k1fT9TVUVzqhXfmTHEwfHfvP+uYdeP/n+2avBrMxodvfajl0wP82yZVcVKPnXbenJ6LEg/uUe8C8QkHsMco8hjLX45W2cAo1dWgp7p2pU/fc3VVU4oy75kR0Y/775/IfHp6+dW7ixfltf1n8HaWr3zP2549+jtqsKCPX+a9wPwcvhWe4Z/AsE5B6D3GMIY23cO9w5HPxOrSYdHr9STWGhqsIZdcmP7DgwcunRP42YcXHX8dms/w7S1O6Z+3Pbzc8oUlX0T1/L6LEgnuWewb9AQO4xyD0GE+uFI+ef6560+6WahHIERYnZYDlUVTgj//zIlIffGDp0+nI4Lmb9d5DmdS+8P3fY8EJFqgpoQ1v/yNxS8E53eJZ7Bv8CAbnHIPcYEOu9iQX05JFOqVY9fWi8rW8m2GgpVFU4I+f8CKayASPlus09SKBwXMz67yDN6154f+644lVF+8DFJw66v+rjU+6F+BcIyD0Gzw5q8OLij/54MrufhkX46PxVnNXMXr8Z6ZRqFc6gHmgfxM4H242hqsIZPrWu8LuH9riY6d9BmtQ9+/7cccWrioweC+JT7oX4FwjIPQZvDgqnZ7/qnrz3leO/7Z128kCvZBDutROzd2/vs++mw2js0tI9bQPlTjJVVTjDp9YV3s0pMi5m93eQxnEPTWXjvuFNXRPV/KnCvj93XPGqAipcPzx2IXi/I3zKvRD/AoG16d4TB8ecXOb0wz10oeu39ZlvYqGLcPJAr3KcXbgB89dt6Xny7bGuM/N2R0Qq4QsWqiqckVsgkGksJCKS3qROZFzM7u8gDeLezPWb9+08gULh5Z6pDW39d714NKG8GLy4iLMN25+ISlYVKPOx2WATjvAm92z8CwTWoHtoJn+/7Vjqh0rYNLt781989dhbozg3C38vFnYR5AO94uwd+vy+V0+gu24fuGi+9VWyO2JU7gsWqiqckVsgkGmsZ5efsWnyJp6IGf0dpBHcQ/XwwK5B+05WqAASyovwik45lWvGj+w+9e6Z+WArLvAm92z8CwTWoHvoTJ7rnkRL4QuLpnZvz8nPMMbv+eQzuyuwuwjmgV4hOC9CB/7tLT0tnaMfTV4NNw45ryrKfcFCVYUzcgsEMo2FjIyX0ray+DtI3d1D20BJUe7OMPHyIn5/7rjKNeP9p+Y27qvw66ya8Cb3bPwLBNage+u395lKnS8smtS9sws3cOAtnaPxb0pGuojD41fu23ki3fc30Sc/9tYoOiiUcfF750DOqwqo5Bcs0lQVcFzyVW8Ozf3jHwaQfwn6YGLhuy8d/WT2L5H3Nq9ePzH7/T8c7z33v5EjjavrzPwvuybu3t53x6+P/Hn0UmRp9frWCx/1X7ge2Q1J8kwfnb/6ndbeMO33D819/5XjPnUdFbXpv9FdHCv3XNC40Kt87/f96Icj2ymnd8bmf3bg9J2tvT949cRLH56PbC0H/e7j6R/98WS4P6ZIMNVCHF2rqI3cAoHsYj1xcKx94GJYiiJpwmlbzv8OUkf39gx9/tDrJ0vecIJUOfcgnE882z0Z7AGNH7kXwb9AYK25t6Nv5her72TPXLFoLvf2Dn1+14tHcRKS0LeU7CKq+f7myNzSpq4JbH9DW//LPVPlLrLaSuiOSEW+YKGqwhm5BQIZxTJ36bbbQEIiuv07SL3cQ4Ns6Ry1j8uhEtw7t3ADPULyY0GwFB3TxioeG+tB7sXxLxBYa+6hgDg8fiWS/KkLi2Zxz9QTLZ2jFQf7hC6i5Pc3UxQTobKrKiJfsFBV4YzcAoGMYpm7dNvpkjwuOvw9SF3cQ/vEmUTkuBwquRnDahhu9iQCXN185LzpmHYcm6l4i1wPci+Of4HAmnIPafyN5z+0cz5UusKi8d2rvp4wSu4iwu9vMsVEqOyqCgi7FH7BQlWFM3ILBDKKZe7SbedKciI6/DtIzu7duv314wfHtvZMRY7IrZLd+2jy6n2vngj2qcjM9ZtPHRpft6Xnue7J8CtXLZ2je05+FqxRCg9yL45/gcCacg9DLFLX5HBcNRUWZli995XjeAuEaZTd0MdT1yAsDdYrgnZkFmEfzJpPHBwz7zXCHCwqd/upFO7VWk8YVRzpD49fQWXGFBOhMq0qoPAOFqoqnJFbIJBFrPAu3bYqJqKrv4Pk6d7opSVk/y7r6yMZqaJ76CzCDnHw4qL5CjdOUCJ/iMXL9dv60FGaNeM0e+6VxL9AYE25h3yO/JAyooqFReQc/bWBWYyyEKaf7Z6E7m8fhLAUA5MtvMUsaukcNWu2D1w07zXCHCzCCmblSJ1Rk3vp6gmjrEd6WznEMl+wgKWBNTFUVdRGboFAFrHCu3TbqpiIOJ9GKW1acjmZRgvhdMGcN5jWC4UjZdbuhWct2I3vvnT0ndMubzNXThXdQwHx1KHxd8/MY69wHpbQBZe8sBHS7LlXEv8CgbXjXvxLWiVVsrAod8E/o3ER24/UGXe29lbssgBTTxh5VlWYL1jAwMCgGKoqaiO3QCCLWCXv6eQkEU2jhXC6YM4bWpZbL4Q2aSoPNGM0YLTShDPy6rFrCBMiPGvBbri9c22CKrqHRoia7JHdp7BXkUVxPdc9+cKR88ERrqbZc68karkMdQ/0/tmrD1X3eMywsChXTITKbQxGF1Gxy4IwM3U9YeRZVQHBEDgTJEEMVRW1kVsg4DyWfZduW3k2YzTgls7CnwCgmiqM5Bqijn2T80D3vnI8/KK1TVPnXjnUchnqHuipQ+M7jl2IJHA5obCo5tsDzdtyyym3QFBusVRVOCO3QMB5LAzAGJUjyQHVpXWhW0moMGqtIeJq3i4DR7d+e1/896hNnXvlUMtlqHsg+xa9rtS8LbeccgsE5RZLVYUzcgsEnMcq1wXUvXXZFQZyL0UNEVdTdxklf3fT1LlXDrVchvoGGqz04L10auqWW1K5BYJyi6Wqwhm5BQJuY+HsH0N1JDOM1LoYZRToJ3tOvTN2Ofjwlmne3EtALZehvoE2Lz9RLJK3vPzrjrzs91RVOCO3QMBtrCdW36XblloXo4wCzV6/uX5b3/wXXwWfXzPnXgJquQz1DRQ+Ucyt/OuOvOz3VFU4I7dAwGGs5B+AqXUxyi7Q4fErD+4aDD7Cps29ZNRyGeoYaOb6zbtePBrJWCfyrzvyst9TVeGM3AIBh7Hid+m2pdbFKNNA9hN9mjT3klHLZahjoPgTxVzJv+7Iy34vTVWBNJK80Q/bB3cem0HCSc2l49PX7t5+rHtiIfKBSlJ9de8rx6t/8LfkmVJWFcEUB5IvmMoY/wIBV7FK3qXblsmSHJRbIMibgxqaXbynbeDW7a+bMfcqopbLUK9Ai+WfKMbLv+7Iy35PVYUzcgsEXMUqeZduW2pdjHIItLVnalPXRDPmXkXUchnqFWhv4hPFSPnXHXnZ76mqcEZugYCrWCXv0m1LrYtRPoHubx98c2gu+ESzRy2XwXv3Kj5RjJF/3ZGX/Z6qCmfkFgg4iVXuLt221LoY5RPo3MKNO1t74zfczAi1XAa/3avyiWKp5V935GW/p6rCGbkFAk5ilbtLty21Lka5BfrJ7k/3Dn0efK4Zo5bL4Ld71T9RLJ38a7le9nuqKpyRWyDgJFY1N+pX62KUW6DXBmbt21dkiloug9/u1fREsRTyr+V62e+pqnBGboEAH+vdM/OP7D4VyYa41LoY5Rlo3eYe+26b2aGWy+C3e1k8UcyWly03Mic75RZLVYUzcgsE+Fgb9w3vPzUXyYa41LoY5Rnol10TL/dMBZ9ulqjlMnjsXkZPFLPlZcuNzMlOucVSVeGM3AIBMlb1t9RV62KUZ6Ch2cX12/uCDzhL1HIZPHYvoyeK2fKy5UbmZKfcYqmqcEZugQAZ65muia2905FUKCm1LkY5B9rQ1j8ytxR8xpmhlsvgsXsZPVHMlq8tNx/lFktVhTNyCwSYWLduf33Xi0er/POnWhejnAOhUkS9GHzMmaGWy+Cre9k9UcyWry03H+UWS1WFM3ILBJhYNd38Tq2LUc6BUCl+e0tP8DFnhloug6/uZfdEMVu+ttx8lFssVRXOyC0QYGJVvJ+mLbUuRvkHeuj1k++fvRp80tmglsvgq3sP7ho8PH4lTMiM5HHLzUG5xUpTVSCNpCbVO2Pzd2/vQ3pJXuqlD8//uOPTyIcuSZnqk9m/3PHrI5FUlNamUlYVwRQHcjGYyhj/AoHUsWq9TY3JkhyUWyDIv4MKA11ZuvXN5z/M9O7darkMXrqX6RPFbHnccnNQbrFUVTgjt0AgXazFL2+v29JT01361boY1SVQS+dopnfvVstl8NK9TJ8oZsvvlpu1coulqsIZuQUC6WJVfO55XGpdjOoS6PD4lUzv3q2Wy+DfQY1eWsr0iWK2/G65WSu3WKoqnNH4fVOKH5SrdTGqV6BM796tlsvg30G9MfhZpk8Us+V9y81UucVSVeGMBu+b0j1OUK2LUb0CZXr3brVcBv8O6rG3RjJ9opgt71tupsotlqoKZzR431Tlgz8iUutiVK9Amd69Wy2XoXkPamRu6eOpa9DmI+ehTV0TD+4ahL7T2pvpE8Vsed9yM1VusVRVOKOR+6b5L75at7kn8tlXI7UuRnUMlN3du9VyGZrroG7d/vqeHQPo8yFk1P3tg9Cz3ZPQyz1Th8evQF1n5iO5l53WQsvNTrnFUlXhjEbum1I/+Eeti1EdA2V39261XIbmOqiNe4c7hytc4FTLZeSle6oqnNGwfVNND/6ISK2LUR0DZXf3brVchiY6qE1dE1t7piJ5FZdaLiMv3VNV4YyG7ZvePTP/yO5TkQ++Sql1MapvoIzu3q2Wy9AsB7XrxOyTb49FMqqk1HIZeeleiqri/ZnrN4MXBOqbGGqKxdyiX62LUX0D7fnks8feGg2SwB1quQxNcVDvTSxU/3sxtVxGXrqX5lrFA7sG+S+CqW9iqD4WPqkNbf2RT716qXUxqm+gjO7enZx7gxcXH35jaFPXhLqIkjT+QeGDQw8/e/1mJJ3KSS2XkZfupakqxi4V0o7sNfzrMioG+njqGjrcJw6O7R36nLzeU/1BPdM1sbV3OvKpVy+1LkZ1D9SSwd27y+Xe4pe3f9U9ee8rxw+dvvxyzxRq2btePJqivEDTwD6jmfywfRA1SjA3S3LrIkDjdEclmf/iq/t2nkAPb2dRstRyGXnpXpqqAm9DJXvvzuPvTSwEc2unwVtXChICoaPcuG/4/vZBdLjtAxdbOkfR4UKpK4wqDwrnqeTNdNW6GNU9UBZ37y6Ze++fvbp+W9/mD87Z0TE4VVlehJWEaRctnaNoJjuPzaBGQaWS6cPSQG5dBGiE7qgc8BklRf/0NftDrCi1XEZeupemqsDOQcenr/3Laydf6plC+jrXqwMzOFNBT9R/4XpkUXNp9NLS0+/+z3dfOvrb3mnjW6iuM/O/ef/cT3Z/+p3W3jtbe3+6bxhmfnT+amQLjF44cu5f3xyOxJXWlL71wkeZNiJs/Mcdn/7g1RMfTCxEQodCqv+ya+Lu7X3I858dOP3O2DzeiFRHwiPtMRNNAA0BzQFrRt77H++M440HRi7ZQaUs9KM/nvzdx9FuSpJqUsqqIixJcBLc0jm668RssKwWkMTB1GoGLy7i7OqR3adwWo+eaN3mHpzBMBdCywVyTjwQukKceD3XPVnxagHO6uxrGBWvG1d5UPe0DdR65hGRyZIclFsgyL+DSgjk/O7ddu7tOfnZ+m191T+vMrx6gW4kvCZR7np7eFBDs4uZXrTIrYsAdeyOkkGfU83vSONSy2XkpXtUVWH05Ntjm4+cDxZXTTzpzZ8J0H1EfrCAfgcz12/v2zv0eYpupS7NGDUBaqNH/zSS4i4R1Vw3ruagUIrBt8jGa5VaF6NGCOT87t0m984u3ECGt3SOVv+1vloVOajNH5xDlZzFNy1y6yJAyVgw890z8+hFH35jCK6i+fMPh6vpoKr/HWlcarmMvHTPQVUB4XT88YNjwRrVYSc9mtAzXRMYRBMeVIHOsaVzdN2WnqcOjdf0RYTcugwTaPHL2/9+aBw1Qeofc4ZKKC+qOajH3hqt/iSynNS6GDVIIKRQ8qWvmkDuvdw77STDkxU/qJouWoTf1cA4/Wz3JEbuYEGM3LoIgFjY+Y+nru3om0FXhn1Dj7p+W98ju09hJw+dvgxXc75GW9PvSONSy2XkpXtuqgpo18DFx/aPVn8twSQ91keFjkZV5e8UcGK049gFjLIo6g+MXDKbSia3LgOB2pb3bcexmchuk4qXFxUPCoUaVma+p2mk1sWoQQLxd+/GKIgRGk0Vo+Cdrb0Y9vjUqqhyB5Vw0aLktz4xTptOBu967cRs/DJAQmuySxMjTGNrEOabp23FT3IwxywypkHhFuDe3z37wf3tg784NI6uLKEyy+caLTqTmn5HGpdaLiMv3XNWVUB7Tn62ce8wTtaDVRNB0u86fhEt/7nuyRQ5jaL+0T+N4O0Vm3qVrSs1Yb+D/uLpQ+PZXRCGwvICscyBo8gwB26OOjwlxWro+iNvTyG1LkYNEqjWu3eHwyESDE0MTR6jYEvnKE6mMQrm9jSphIOyL1qEDdCuJEp+V6N/+tqTb4+t29yzcd8wzknCoTrSRZTcIA7cCNPm8VqYb562ZSyyhTlmEdYxK4dbqNW9TK/RpvgdaVxquYy8dA9NIMiwGDVXFdA7p+fRE4WFBZqBGe1MJwXZNTtaOPkIXbSHik0dgRAUO1BTm0ymZL+TW28LIZY5cFQP5sDNUaPgMEf9jec/JL01Uuti1DiBEu7enVxDxIecxjmozR+cw3l/2ACrHx33n5rDOQmGajRhHD4G4JItmhxuSyqde+Wu0SZ3sKYrSBB6CfLb3FBu+QA1Tu65kpfuIbWCBI2RpqqAkKZIVpO1aAZmtGuha/bUQiAEbaFvEVGx31HrYiT3GFUMFN69u9YaIi5v3MNQjSaMwzc9VUtmlYQt8qDMNVrTuzZIB5tbPkDe5F4oL91DZppBM07KqqJK1eVjQ5eRXGGMzC2Z2t8U/pu6Jkzhb9bHGxP6HS/zw79A0Bp078rSLVPr11pDxLUG3XMoucdI7jHKLdbaqips2RUGDspoQ1u/qf1N4f9yz5Qp/Kvpf73MD/8CQXKPkdxjJPcYyT1GucVau1WFc3mZH3KPkdxjJPcYyT1Gco+Rqgpn8jI/5B4jucdI7jGSe4zkHiNVFc7kZX7IPUZyj5HcYyT3GMk9RqoqnMnL/JB7jOQeI7nHSO4xknuMaq4qwl+NSpIkSZIk2UKREJQLMUpXFUIIIYQQtaKqQgghhBBuUFUhhBBCCDeoqhBCCCGEG1RVCCGEEMINFaqKkY6f/7xjJHhRGaxew9rL4C2t3ZeDF0IIIYRoRAoFwTKJ43xiVXG5u7XS+2lUVQghhBANTjhYFyqDhLogoarAOztGSlx9KGy6o6NQbyBCULsE64RRlye6g7qmWDWES8Pp4N3AWmeZYlBT2GRd2gghhBCiLBicrXE5HMvjlK0qgi1YGypSGPgLW1we8AsLVwoXLDKxCuuszIsutaftmYUXy6uG+1ycIYQQQog6saqSSByZS1cVK+8v8eawDqhmotaZKxTLC12nEEIIIeoJW1XYo3uBVe+PFwQJE+lmrkKVhRBCCFFPMD4Xx+FVFUaMxG9rAmtDReIFQcKEPV0oD4KNYV6JNQsrhC8skg9BCCGEEFmyMoBXGJHzrCqWJ4OLHx3hTDMveFHYb4OJWnxDdB+EEEIIkSPFATkc3UtSqaoQQgghhKgOVRVCCCGEcIOqCiGEEEK4QVWFEEIIIdygqkIIIYQQLvjrX/8f5lPALsL3tfwAAAAASUVORK5CYII=\n", "text/plain": ["<IPython.core.display.Image object>"]}, "execution_count": 10, "metadata": {}, "output_type": "execute_result"}], "source": ["from pyquickhelper.helpgen.utils_sphinx_config import NbImage\n", "NbImage(\"images/train.png\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Predict"]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": ["# do not do it, it takes for ever.\n", "# yest = knn.predict(test_X)"]}, {"cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAscAAAC0CAIAAAD3vRY/AAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAACR1SURBVHhe7Z3tbxVXfsf7L/Rd30SsVIlVIpW+KXnRJS92QWqbzSpKo0obESkSVa3uokhJtam0RFuFRDSACITddRYoTgKBPMBCGogs4SQQ8+DH4IVrjNcYDLaJjSGLHScipCja/s49c4/H83Rn5ntm7r1zvx99BeO5c+d35ztn5nzn3nn4iz8TQgghhNiAqYIQQgghdmCqIIQQQogdmCoIIYQQYofAVFHa+4xhc8cNZ2xeSPWMii7MubQ3ooT7A8jw3pIzoEeaMVUJnA8hhBCSIzc6Nrs7IOmONGacf0wZ9T6F6chkRETX6RCWKirvVMVy7g5d1S1j5lzaG7VMgR8gxafKbkEIIYSQqpSDwebNrlRhOiaTNfxjNJWjbxldHlv5vwrVUoUa1vORAY37Jf+wGti7d3Pllcq7nM/i/3NzR4czrvyOygTOn2VHFv7UONOU32lGe+bsxry01zW9pvwBFuYgw5WJFz6PnsA/YD6cLun5qGHzEcxL7jEeHwghhBArSBdT6Rpdg9Jpqe7GP8ZhcarQ/8agSqpQXWV5cGFU0JBrWAYWjXV38/Jn+S/zydXrzgQLk8qQmYGh8lbXy+qzVaasvGzmvMDC7GTIO+eFF13D0SPdA85HWowZb6ZcNBwy5PeBEEIIwZF+xelWFvWR5dH+Mc6w08nqQ10ZjNsxVT2vwvR1pq4Zjj9SI38uUJ5v1Tm43+R/1f2WBRYveuD0hrC5RYw0A2XD3cXkFYc486k6khBCCMGRbsXpqxKlCoPOFOU+z3RwoVT9BUTjHmOG44/UeP4Uqs1hYTDo1eCRHgKnN1Sdm3+k+1VXslgYHThlipGEEEIIjnQrlbDgGnTyhH+MB50pZDr9mvNnKDFThWvUwpDqUp2Zy0hnrPu9agLXjDx/Cu6JzbBrpAzqAjLgjHTNJHCkl8DpDerVyEUww/4Bjcyh/KeM9n5U95QLw9FDi4cJIYQQEOlWKkFgodOrdF7+MYuQkZW+Tb9oRoQQN1WUR2pcL5lxCydCet5bmcJ8Zv3nQg9sJl4Y1u8p/2He7jrR0swkcKTxzhA4vaFSwf3q4g+gRwYOlHEKmj+j52NGV15xxgQOE0IIISDSrbh6xkoXtNDT+MdUcL+z0pdW6aECU0VjoJaQ/S8hhBBSNzReqlj4VoKZghBCCKknGvi7CkIIIYTUFUwVhBBCCLEDUwUhhBBC7BCQKv7+t91/+auPKIqiKIqiPJKQ4MSFIAJShbzHGcqYkZtfO0PZk1ut4hUS6B4C3UOgewh0D4HuhREdEpgqLFO8QgLdQ6B7CHQPge4h0L0wmCoUbB8IdA+B7iHQPQS6h0D3wmCqULB9INA9BLqHQPcQ6B4C3QuDqULB9oFA9xDoHgLdQ6B7CHQvDKYKBdsHAt1DoHsIdA+B7iHQvTCYKhRsHwh0D4HuIdA9BLqHQPfCYKpQsH0g0D0EuodA9xDoHgLdC4OpQsH2gUD3EOgeAt1DoHsIdC8MpgoF2wcC3UOgewh0D4HuIdC9MJgqFGwfCHQPge4h0D0EuodA98JgqlCwfSDQPQS6h0D3EOgeAt0Lg6lCwfaBQPcQ6B4C3UOgewh0LwymCgXbBwLdQ6B7CHQPge4h0L0w0qQKqU1RFEVRFOWWDgk6LQTC7yosU7xCAt1DoHsIdA+B7iHQvTCYKhRsHwh0D4HuIdA9BLqHQPfCYKpQsH0g0D0EuodA9xDoHgLdC4OpQsH2gUD3EOgeAt1DoHsIdC8MpgoF2wcC3UOgewh0D4HuIdC9MJgqFGwfCHQPge4h0D0EuodA98JgqlCwfSDQPQS6h0D3EOgeAt0Lg6lCwfaBQPcQ6B4C3UOgewh0LwymCgXbBwLdQ6B7CHQPge4h0L0wmCoUbB8IdA+B7iE0p3trDw/NfXPP+QOgOd2zBd0Lg6lCwfaBQPcQ6B5CE7pXmppfsuHE6v3nnb8BmtA9i9C9MJgqFGwfCHQPge4hNKF7r3WN/+LIcMvBwX1nrzuj0tKE7lmE7oXBVKFg+0Cgewh0D6EJ3Xukrf/Y8M2b83eXv9o1PnvHGZuKJnTPInQvjDSpQmpTFEVROWtwev6+l473Xr09MDG3v//6itZuzwQUVVvpkKDTQiD8rsIyxSsk0D0EuofQbO6dGrv98O7+L+/8n9aLHaMvH7/ivJacZnPPLvWzUHfvfbf28JD86/ydFltLxFShqJ/2YQu6h0D3EOgeQnShde0jWzvHTKoQrdzR2z8x57yckGZzzy71s1AvdIz+zZZTrWeuOX+nxdYSMVUo6qd92ILuIdA9BLqHEF3oodae7qu33aliaHp++faudMepzeaeXepkoSRTSrKUViFtwxmVFltLxFShqJP2YRG6h0D3EOgeQkShma++Xbqx0x0ptNp6J39+aMiZKAlN5Z516mGhJE1KmBiYnJNm8PDu/lNjt50XUmFriZgqFPXQPuxC9xDoHgLdQ4gotH/g85aDgyZMuPXEvnNHh24408WmqdyzTj0s1Asdoxs/uazbwIFzU6vfhu5iYmuJmCoU9dA+7EL3EOgeAt1DiCi09vDQ7p4JkyTcmpy9s/zVrpmvvnUmjUdTuWedmi+U/u3DtIGb83eXbTmdtA24sbVETBWKmrcP69A9BLqHQPcQIgp9f1Pn5Vtfm17Eo2PDNx9p63cmjUdTuWed2i6U+7cPoxc7RjfWwTVBTBWK2raPLKB7CHQPge4hhBUqTc2vaO12dyF+PXdkuLVr3HlDDJrHvSyo7UK5f/swktAp0dOZIjm2loipQlHb9pEFdA+B7iHQPYSwQvpG3Z5exKOb83cleVy6FfejNo97WVDDhfL89uHWT9869+HFGWe6hNhaIqYKRQ3bR0bQPQS6h0D3EMIK6Rt1e7oQvwYm5x5q7Yl5oWnzuJcFtVqowN8+jI5cuPH4ngFn0oTYWiKmCkWt2kd20D0EuodA9xACC0lH8r0NJ27O3/V0IYHa1jm2rn3EeWckTeJeRtRqoQJ/+3Br+atd8b+vcmNriZgqFLVqH9lB9xDoHgLdQwgs5LlRd1XFvHVBk7iXETVZqIjfPoy2nbz6y3ix0oOtJWKqUNSkfWQK3UOgewh0DyGwkP9G3dG6fOvrOAesTeJeRuS/UNG/fRhNzt5Zuqkz5q9gbmwtEVOFIv/2kTV0D4HuIdA9hMBC0pd4btRdVdL3rNzZG/2NRZO4lxH5L1TV3z6Mnn5/6PW+Sf2u+NhaojSpQmpTFEVROaj72uxfv/zpwMRcUp28/Kcf/q7n5eOXPTOkGlGHStM/+G23ZxWH6cDA1IPbuzxzyEc6JOi0EAi/q7BM8QoJdA+B7iE0g3sRN+qOIzlsffaDYWdei2kG97Ijz4WK+duHWytau0tT884s4mFriZgqFHm2D2coY+geAt1DoHsI/kIRN+qOqdfOXHukrX/um3vOHCs0g3vZYaXWk2+fl1Wz8fgVyY5hP1dJofi/fRhJm5GW48wiHrbcY6pQ5FareIUEuodA9xCawb3oG3XH1LHhm6t29nnO32wG97IDr9U/MbeitVtWzfqO0ZaDgw/v7pfuddmW056ccag0XfW6D79SPBbElntMFYriNXq6h0D3EOgegqdQnBt1x5T//M3Cu5cpeC0JE5IePKtpaHrekzPue+l4ot8+jNQd3M9cc4rFwJZ7TBWK4jV6uodA9xDoHoKnUJwbdcfX5Owd6ajaKlcHFN69TMFrLd/eFScuDEykiRQiCSjLtpx2isXAlntMFYriNXq6h0D3EOgegqdQzBt1J5I5f7Pw7mUKWOtS+Z4inlUTqNSpQpTosSC23GOqUBSv0dM9BLqHQPcQ3IUS3ag7kfT5m59NfulUyhi2PT9bO8eebx/xrJdAIaniwLmp1W+fd0pWw5Z7TBWK4jV6uodA9xDoHoK70KmEN+pOpGPDN1e0dqe4A2MK2Pb8rNrV9+noF56VEigkVYiWbuyMec6mLfeYKhTFa/R0D4HuIdA9BHehpDfqTqp/OzCY6Gy+1LDteZBuXjp7z+oIE5gqNh6/sr5j1CkciS33mCoUxWv0dA+h4dxbe3jIfzcCD3QPoSaFUtyoO5E+GJxevr3LKZYlbHseXu+bfPr9Ic/qCBOYKi7f+nrZltNxvpSy5R5ThaJ4jZ7uITSWex9enFmy4UTVpxTSPYT8CyU6nE0n6a4Snc2XGrY9D4lOwgVTheipd0uHStNO7XBsucdUoSheo6d7CI3lnhzRfjr6xYrW7uhnVNI9hPwLgTfqjiPprhKdzZcatj03c9/cW7qpM/5JuHiqkP3Dql19TvlwbLnHVKEoXqOnewgN5J65S1LV7oHuIeRfCL9Rd1Xp7irOM9NB2PbcJM2LeKoQyV6i6mNBbLmXJlVIbYqi6kGPvnH21yevyn5H9A+7+vb0X/dMQDWo/vrlTz8ZuaXXbKZ6vn3k339/wVOdyk7/svcPr5y44lkLWWv9sUtr3ivpD3B0aOadgSnRcx/+UfSzQxdW7ugVyc7ks8kvzedMJx0SdFoIhN9VWKZ4hQS6h4DU8vz03n319kOtPc5rPugeQs6FLN6oO0LS2ci/N+fvfm/DiUwvMWXbM6S4B4leTaCk4pINJ6T7FknTenh3v2h9x6hoa+fYseGbov/++PIjbf3OBwVgqlAUr9HTPYRGce+X7SPbTl517zsi7vxP9xByLmT3Rt1hMt1V0gdGJIVtz/DxpS8ee/OsWQVxZCVVxJEU2tY5tq7aed9VYapQFK/R0z2EhnAv8KDncvk2wIFXmdI9hJwLZXGjbr9MdzUwOZfpJaZse4YUp8vkmSrk36feKf3+/JTzcVPBVKEoXqOnewgN4Z4cXMohpnunoLXt5NXAq0zpHkKehVJ8SZ5O7u4q00tM2fYMKZ5rn3OqkIa3cmdv1VM7I2CqUBSv0dM9hIZwL2z3JDuFwKtM6R5CnoUyvVG3W+7uKtNLTNn2NOnWbM6pQjQ0Pf9Qa0/VG+uFwVShKF6jp3sI9e+eHFbKwaXZHXgU2EPQPYQ8C2V9o24jT3eV3SWmbHuadGs2/1QhOjZ8M/WZm0wViuI1erqHUP/uVb2X82Nvnv340hfO1GXoHkKehbK+UbeRp7sK++0Mh21Ps2zL6aHpebfncVSTVCFKfeYmU4WieI2e7iHUuXtxLjv0X2VK9xByK9R9bTbrG3UbeXqRm5ldYsq2J6S+WrhWqUKU7sxNpgpF8Ro93UOoc/dWv33+wLkpz/bvl+dyQbqHkFuhVzrHWjK+UbeRvxfJ6BJTtj1h4/ErL3aMegyPoxqminRnbjJVKIrX6OkeQtVCcjz3rwcGrfwInXSh4j90ynOVafFWk1C8hXry7fNZ36jbyN+LZHSJKduekPqHrRqmClGKMzeZKhTFa/R0D6FqodX7z287eVVS/Kmx286otCRdKP+dryLk/qW8eKtJKNhCSVp9YPPJpFceplZgL5LFJaZse+Ozd5ZtOe2xOqZqmypESc/cZKpQFK/R0z2E6ELrpF8vn8g9OXvn4d39bX2TzgupSLRQSe9k4L7KtHirSSjYQr3QMfqfRzO/paZRYC+SxSWmbHvIzVJrnipEic7cZKpQFK/R0z2EiEKSIZ5+f8i9vcmfz34w7LycnEQLFXbnqwiZTqJ4q0ko0kLpmxnk1oWIwmpZv8SUbQ+5WWo9pApR/DM3mSoUxWv0dA8hrNBHI7cC7+H/2plrstdId9OYRAuV4sZ8In2VafFWk1CYhbp777vl27uGpufrIVVYv8S0ydte/HOhAlUnqSL+mZtpUoW4SVHNpqNDMz/a0XPy8p9k2/Pr9Z7JFa3dHSO3PO+yqF094z9pO+upG0cHBqYe3N7lmRtVV3py/7mXP7nsWXG1Uu/V2/e9dHxwet7zIal0eqVz7Im3/uAxuRHVfnFG9iTRT0vXIUGnhUD4XYVlildIaAb35Ghj1c6+6DvYDEzOpTh/M/5CITdHeu7I8Asdl5wZZQzbXlLcz7GUfbdZa1kropbdS0yLsZo8xK/1+J6BIxdueByOr9yaRJxCB89Prd5f5bQbpgpF8Ro93UPwFLp77zuJFHF69BTnb8ZcqNS30NG6fOvr+zef3No5JvHImWNmsO0lQtaI5EXzw1adpAq7l5gWYDX5iVkr6RnWftVVqhC1HBzcd/a6s3hBMFUoitfo6R6Cp5Bkc0no7u0qWonO34y5UDHvfBWh9oszz7ePLN3YufbwUP/EnDPfDGDbS8SaA2ofbVZTnaQKkcVLTBtrNc19c2/Ne4Pjs3ecv0OIWetQafqpd0sebxOp3lKFJKTlr3ZF+MNUoWisRh8HuofgLmSuI02k+Odvxlko8GwvLbPL2N0zsXJHrxyJ7h/4XA6knBr2YNuLj+SJlsV30qyfVGHxEtMGWk2yzcqWu++z6z9u648+MzFmLQnx4G3N6i1ViD4d/WLVrj5nCX0wVSgaqNHHhO4hmEL+60jjS986pmqwiLNQie58FSbPLmNgcq7l4ODSTZ3PHhmueliWCLa9mEhYlGO+ydk7i9ZL3aQKka1LTBtlNelIoX/rHJqejw4WcWpJapdNzLOKk6oOU4XoxY7Rl49fcZZzMUwVikZp9PGhewi6UNh1pPEV58ymqguF/y6rFbjLkP3da2euLdty+vE9A4dK007J8q0AT43dFu0f+Hzj8SsiOeSSHa5Ijl+joxLbXkzETP89DOoqVdi6xLQhVpM7UmjJ1rFyZ6/sB5wpFhOnlr4HiZlhOtVnqhCt3NEb+FsqU4WiIRp9IugeghSSYxQ5UgEPMkTqXPqucWe+QVRdqBR3vgpU9C7jyIUbT71bkq1bS3KG7A1FLQcH13eMinb3TEgXKNr32XXZ+Ub8dMK2F4e23onAr8HqKlVIlpVDbfyrrPpfTf5IYRx4Yt+5fQOfO9O5iFPr2SPDkto980yquk0VQ9Pzy7d3+XcFTBWK+m/0SSmee5L6H33jrN1b/oXRfW226nWkMSV7pR/v7o84OzLaPdlipYO38mAIi/umfWevrzkw6HxEH8Vre4LdQtKMV7R2B37/VFepQjQwOVf1DIOq1PlqCosUWrKaWg4O+i/sqlpr/8DnVjbeuk0VorbeyZ8fGnIWuAJThaLOG30KiuSeHCqtfvu8HDf/2tIDvSKQXlz2BQ9u74pzHWlMSTqJeOhftHtJLz+JkN190/PtI1s7x5xPuZgitT2D3UKrdvV9OvqFx1KteksVIn2GAXLdUD2vpuhIYfT0+0MbF59GEFFL54mWg4NWjkzqOVWInth37ujQDWfJyzBVKOqq0a89PBTWA8WnGO5JHy9b8vJXu/RFldLoJ2080CsQ8Vxq6X1B+8UZs81YUcQJFhHure8Y3XT8imdWqWV93xT2XIBitD0PFgu9fPzKix2jHjONcutCRPFryXb34939YWcYVKVuV1PMSKEla+3nhxeOywNr2c0TWrk1iXSFpG3ILtp9IxymCkX9NHo5IPi7V89IQweDRQHcO1Salu1TtmTzRbFp9OADvTyMz9559sjw0k2dUkt/XZnFZhx2gkWYe/sGPm9ZfM0hKOsLFfbjTgHanh9bhUpT8yt39gb+9qGVWxciSlRLPvNjb54NPMOgKvW5mhJFCq22nok1Bwb1mQSeWlnkCa3cmkTqQvp6N8cIpgpN/TR6OVyWvk0aOhgsGto92fPK4j/1bsnzk6S70SMP9DJIj7jmvUHZF8jc3Dv6LDbjRH3wqbHbsgeP6HtSKIuFkhUkfaTnbL6GbnuBXLr19YPbu2TXh2vJhhMDk1ErIrcuRJSiVsvBwbBfviLIrUnEL5QiUmjtO3t99X51GZSplV2e0MqtSSCF3EdN0s71QCBMFZapWmj59i690wGDRYO6J8v7H0eGV7R2+6+4E3kavUyzamdfuvM3P7w4I/au3NG777OF2xoaZbQZy07Hf4KF3z3ppMUB/PITjzJaKH9DbdC2F8bvz09JcjowYOfslqrKrQsRpav1fPvIuoSXm+bTJGSj/qfd6uJnOTaTnj7iBCxprukihdbRC2rv8dnkl1nnCa3cmgRSSA6BZK+l98ZpUoU0ESoLfXrli/s3n5RVqyU7sh/t6I1+QFyR9ELHJVn8F4+NGgeq6oPB6R/8tvudgSnPrMJ0dGjmZ4cuPLD55E/azr7eM+mZWw76zamrj75x1vOp3JLVLRunLJfnjfWsXV0T//g/fZ4FKYAGp+fXvFf65zcHwh5U27SSYPHk2+fq56Gmh0rTcoQgG/XOM+OyXT/zvxefeOsPP/xdj/RWsrHLS899+MdXOsf0jkI2Mdmvyt7Vs1CJJG+/76XjUqX94oznpaaV7LUeLF9oyu8qFLnVii70Wtf4LxbfmSD1NxaN5Z6O/M8dGY4+QJeG6xkjinP+ZmlqXo6upIR02Fs7x6oeWAQWsiXPCRZu92SDfHzPQOD3NLgyXahtnWPm+LWx2l4YctS1amefudlApu65lVshEVKrrWdi9f7z+gyDqmS3mvQFYpIb9FbjXyLZ2OWl9R2jLQcHZUch/deSDSdSf0vhVvGaBF5I7weYKhS51YouJAHC36OkCxaN4l6irxAjGn3g+ZtJw4RRppux5wQLt3uyCPg9c8KU9b5JVoHOdo3S9iLQv3q4+54G2rPHF1jr6IUZCV5xdk1mNUkIOBVyz1aRDMt4z2k6Ycx89e0vy1u3+6l7DeRefDVWIR3dnJUUBFOFZSIKycYpIdqzhrRSBIv6dy/FT5LRjd6cv5k6TBhlvRnLRzInWBj3WrvGrdxDM0w57Jsee/PsRyO36r/tRSAH35Ltnnqn5PnarLH27DGF15Jdk+y1pFOIKdkqpdcRtfju2SqSYRkv04giEoasI4kjy1/t8j8cp7Hci6nGKnT51teyop1VFQRThWUiCskm1BJ+JWH8YCHboWxyK3f0mvivjwlk/voowb+hRh9AiMzbnTcsJql7MqukeUKraqOXHZPs41KHCaMcNmNzBwvt3tGhG0/sO+eZxq5yWCjpieUQvyPtXQ1SYHfL9fzq4VZj7dljqm4XSjbesITR1jshY17sGA38tZTuIbJViKlCkVutiEJr3hsMvB7BKDpYyPjX+yZX7erTm9zrPZMm/utjgpbyz4oimUBWolsyJuIAQmTerif25Iz47qXOE1oF24z1CRbiXtV7GFhRPgsla/ZvX1EtRBQn0YKEtT0TkfUneXzPgAx/eHEm4ooh/68ebhWs7Wk1xEK5E4bsf55+fyjiHth0D5GtQrKanI0qCKYKy4QVuhvvuZSBweJQaVoSiRyjy/ZmbgOcXUOUjdyTMx7YfFLvu9e1j+heRHch0lk6HxHOE1oF24z1CRa7esZtPXMkWrm5135xRofRiETrz6bp0BuUO0PoEiYi609y5MINGf7pW+eWv6puOyGTqcc+dY3LG2XTC/vVw62CtT2t4i0U3UNkq5BsYnrzDISpwjJhhT6+9EXMh26bYNE/MSd7RskiT71b8n/JkefWZXqRrZ1juhfRXciK1m5pLVotWJ7QKt5mLJ7cv/lk2PGxXdWVe/5sGpEzIn6hk0Qr73VniDjNTCZ77cy1XxwZljf+1fpPRFVPki1e2xMVb6HoHiJbhWSTdDbdIJgqLBNWKNEDc6UTWrLhxModvfKWsKMrbl2I6B6idIX8OcNIAoeMMdFBZH6hs/7EljCx7SGie4garlB0SGCqsExYoe9v6oz4sTCFuHUhonuI6B4iuoeI7iGyVYipQlHbVNE/MbdyR69nxYDi1oWI7iGie4joHiK6h8hWIaYKRW1TxcbIJyOnE7cuRHQPEd1DRPcQ0T1EtgoxVShqmyrME8UsilsXIrqHiO4honuI6B4iW4WYKhQ1TBXjs3eWbTntWSu4uHUhonuI6B4iuoeI7iGyVYipQlHDVOF/opgVcetCRPcQ0T1EdA8R3UNkq1CaVCFdI2VLK3f01uSR3BRFURRlVylThTOUMdLjOkPZk1stT6G58CeKgdJrNx/lVqt4hUR0DxHdQ0T3ENG9MDFVKGqVKvZHPlEMEbcuRHQPEd1DRPcQ0T1EtgoxVShqlSqqPlEstbh1IaJ7iOgeIrqHiO4hslWIqUJRk1QR84li6cStCxHdQ0T3ENE9RHQPka1CTBWKmqSK+E8USyFuXYjoHiK6h4juIaJ7iGwVYqpQ1CRVJHqiWFJx60JE9xDRPUR0DxHdQ2SrEFOFoiapwvoTxdzi1oWI7iGie4joHiK6h8hWIaYKRf6pIosnirnFrQsR3UNE9xDRPUR0D5GtQkwVivxTRRZPFHOLWxciuoeI7iGie4joHiJbhZgqFPmniiyeKOYWty5EdA8R3UNE9xDRPUS2CjFVKHJOFRk9Ucwtbl2I6B4iuoeI7iGie4hsFWKqUOScKjJ6ophb3LoQ0T1EdA8R3UNE9xDZKsRUocg5VTzS1n9s+KZnTdgVty5EdA8R3UNE9xDRPUS2CqVJFdI1Uqn12eSX9710XNYfRVEURRVJKVOFM5Qx0gE7Q9mTWy0plN0TxdzSazcf5VareIVEdA8R3UNE9xDRvTAxVSjyTBXZPVHMLW5diOgeIrqHiO4honuIbBViqlDkVmtwej67J4q5xa0LEd1DRPcQ0T1EdA+RrUJMFYrcau3pv57dE8Xc4taFiO4honuI6B4iuofIViGmCkVutda8V8ruiWJucetCRPcQ0T1EdA8R3UNkqxBThcJurfHZO6fGbov2D3y+8fgV0drDQ4+09Yvu33wyuyeKucWtCxHdQ0T3ENE9RHQPka1CTBUKvNbde9899FqPmCNatuX0w7v7RS0HB9d3jIp290wcG74par8443Y/O3HrQkT3ENE9RHQPEd1DZKsQU4UCr7V6//mD56c85vrFrQsR3UNE9xDRPUR0D1HDFWKqUIC11rWPbOsc8zgbKG5diOgeIrqHiO4honuIGq4QU4UCqdXWN/n0+0MeW8PErQsR3UNE9xDRPUR0D1HDFWKqUKSu9dHIrURXinLrQkT3ENE9RHQPEd1D1HCFmCoU6WqVpuZ/3NY/OXvH42mEuHUhonuI6B4iuoeI7iFquEJMFYoUtWa++nbVzr6h6XmPodHi1oWI7iGie4joHiK6h6jhCjFVKJLWunvvO4kU3Vdve9ysKm5diOgeIrqHiO4honuIGq5QmlQhfXCT69E3zv7m1FVZBxRFURRFaaVMFc5Qxkjn7QxlT6Ja8a8j9UubnoNyKyQq3kLRPUR0DxHdQ0T3ENkq1HipwtwJW98De2vn2MxX3zqvpSV+qkh0Half3LoQ0T1EdA8R3UNE9xA1XKF6TxXuDLFsy2mpbu6Ere+B/Xz7yNKNnWsPD/VPzOk3piBmqkh6Half3LoQ0T1EdA8R3UNE9xA1XCGbqWJ89o4kAPMkLZEM68dryXj9wC2Zxpm6QmlqXr+kp1zXPqLf+8Dmk54MEXHBxe6eiZU7epdv75JCd+9958w6NnFSRYrrSP3i1oWI7iGie4joHiK6h6jhCqGpwiSJZVtOi1oODponaYlkWD9eS8brB27p7xvcWtHarV/SU27tHNPvTfEgroHJuZaDg0s3dT57ZNgfXyKomirSXUfqF7cuRHQPEd1DRPcQ0T1EDVdIunWn4wwiOFUEJgm8x/Uo9RJOzt557cw1+WCP7xk4VJp2PnfkA8r19yIRWrLhRIrrSP0qXkMUFW+h6B4iuoeI7iGie4hsFZIe0+l0gwhKFf+lnvTdkk2ScAtfwiMXbjz1bskkA/nY+kuRliZ4QHluhUTFWyi6h4juIaJ7iOgeIluFkqeKX33kmUVGYvtARPcQ0T1EdA8R3UNE9xDZKsRUocT2gYjuIaJ7iOgeIrqHiO6FialCie0DEd1DRPcQ0T1EdA8R3QsTU4US2wciuoeI7iGie4joHiK6FyamCiW2D0R0DxHdQ0T3ENE9RHQvTEwVSmwfiOgeIrqHiO4honuI6F6YEqeKJRtOyHsoiqIoiqI8kpDgxIUgAlIFIYQQQkgKmCoIIYQQYgemCkIIIYTYgamCEEIIIXZgqiCEEEKIHaJSRWnvM8/sLTl/VEcmTzB1GXnL5o4bzh+EEEIIqUdUIChTrZ8PTxU3OjbHeD8GUwUhhBBS55jOWiWD6FwQlirknXtLAd8+qFnv3avyhlRwsoszjalaHuhwck0lNZhXzbDzbsE1TZlKUR1sso42hBBCCAlFOmdXv2z68kCCU4UzB9eMKqiOX82x3OGrFxeCi7yka6lpFsZ5X3UPu0eqP8qTms9cGUEIIYSQGrEoSVTrmQNSxcL7A95sckCcgaQjF6jEC35PQQghhNQSNFW4e3fFovf7A0HEQLqRi2CyIIQQQmqJ9M+VfnhRwggi/GxNwTWjCv5AEDHgHlbxwJmZjAuYUk1g/nBRdREIIYQQkhkLHXj1Hjm3VFEedL782GtG6nHOH+pza3TVyhu8n4EQQgghOVLpkE3vHkZkqiCEEEIIiQ1TBSGEEELswFRBCCGEEDswVRBCCCHEBn/+8/8DZX4ZxzL42scAAAAASUVORK5CYII=\n", "text/plain": ["<IPython.core.display.Image object>"]}, "execution_count": 12, "metadata": {}, "output_type": "execute_result"}], "source": ["NbImage(\"images/test.png\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Enigma"]}, {"cell_type": "markdown", "metadata": {}, "source": ["The process almost does not end. We chose a [k-d tree](https://en.wikipedia.org/wiki/K-d_tree) to optimize the neighbours search. Why does it take so much memory and so much time? What would you do to optimize it?"]}, {"cell_type": "code", "execution_count": 12, "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.7.0"}}, "nbformat": 4, "nbformat_minor": 2}