Classification/K-Nearest Neighbors/KNN-From-Scratch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# K-Nearest Neighbors from Scratch\n",
    "---\n",
    "### Breast Cancer Wisconsin\n",
    "Citation Request:\n",
    "   This breast cancer databases was obtained from the University of Wisconsin\n",
    "   Hospitals, Madison from Dr. William H. Wolberg.  If you publish results\n",
    "   when using this database, then please include this information in your\n",
    "   acknowledgements.  Also, please cite one or more of:\n",
    "\n",
    "   1. O. L. Mangasarian and W. H. Wolberg: \"Cancer diagnosis via linear \n",
    "      programming\", SIAM News, Volume 23, Number 5, September 1990, pp 1 & 18.\n",
    "\n",
    "   2. William H. Wolberg and O.L. Mangasarian: \"Multisurface method of \n",
    "      pattern separation for medical diagnosis applied to breast cytology\", \n",
    "      Proceedings of the National Academy of Sciences, U.S.A., Volume 87, \n",
    "      December 1990, pp 9193-9196.\n",
    "\n",
    "   3. O. L. Mangasarian, R. Setiono, and W.H. Wolberg: \"Pattern recognition \n",
    "      via linear programming: Theory and application to medical diagnosis\", \n",
    "      in: \"Large-scale numerical optimization\", Thomas F. Coleman and Yuying\n",
    "      Li, editors, SIAM Publications, Philadelphia 1990, pp 22-30.\n",
    "\n",
    "   4. K. P. Bennett & O. L. Mangasarian: \"Robust linear programming \n",
    "      discrimination of two linearly inseparable sets\", Optimization Methods\n",
    "      and Software 1, 1992, 23-34 (Gordon & Breach Science Publishers).\n",
    "\n",
    "1. Title: Wisconsin Breast Cancer Database (January 8, 1991)\n",
    "\n",
    "2. Sources:\n",
    "   -- Dr. WIlliam H. Wolberg (physician)\n",
    "      University of Wisconsin Hospitals\n",
    "      Madison, Wisconsin\n",
    "      USA\n",
    "   -- Donor: Olvi Mangasarian (mangasarian@cs.wisc.edu)\n",
    "      Received by David W. Aha (aha@cs.jhu.edu)\n",
    "   -- Date: 15 July 1992\n",
    "\n",
    "3. Past Usage:\n",
    "\n",
    "   Attributes 2 through 10 have been used to represent instances.\n",
    "   Each instance has one of 2 possible classes: benign or malignant.\n",
    "\n",
    "   1. Wolberg,~W.~H., \\& Mangasarian,~O.~L. (1990). Multisurface method of \n",
    "      pattern separation for medical diagnosis applied to breast cytology. In\n",
    "      {\\it Proceedings of the National Academy of Sciences}, {\\it 87},\n",
    "      9193--9196.\n",
    "      -- Size of data set: only 369 instances (at that point in time)\n",
    "      -- Collected classification results: 1 trial only\n",
    "      -- Two pairs of parallel hyperplanes were found to be consistent with\n",
    "         50% of the data\n",
    "         -- Accuracy on remaining 50% of dataset: 93.5%\n",
    "      -- Three pairs of parallel hyperplanes were found to be consistent with\n",
    "         67% of data\n",
    "         -- Accuracy on remaining 33% of dataset: 95.9%\n",
    "\n",
    "   2. Zhang,~J. (1992). Selecting typical instances in instance-based\n",
    "      learning.  In {\\it Proceedings of the Ninth International Machine\n",
    "      Learning Conference} (pp. 470--479).  Aberdeen, Scotland: Morgan\n",
    "      Kaufmann.\n",
    "      -- Size of data set: only 369 instances (at that point in time)\n",
    "      -- Applied 4 instance-based learning algorithms \n",
    "      -- Collected classification results averaged over 10 trials\n",
    "      -- Best accuracy result: \n",
    "         -- 1-nearest neighbor: 93.7%\n",
    "         -- trained on 200 instances, tested on the other 169\n",
    "      -- Also of interest:\n",
    "         -- Using only typical instances: 92.2% (storing only 23.1 instances)\n",
    "         -- trained on 200 instances, tested on the other 169\n",
    "\n",
    "4. Relevant Information:\n",
    "\n",
    "   Samples arrive periodically as Dr. Wolberg reports his clinical cases.\n",
    "   The database therefore reflects this chronological grouping of the data.\n",
    "   This grouping information appears immediately below, having been removed\n",
    "   from the data itself:\n",
    "\n",
    "     Group 1: 367 instances (January 1989)\n",
    "     Group 2:  70 instances (October 1989)\n",
    "     Group 3:  31 instances (February 1990)\n",
    "     Group 4:  17 instances (April 1990)\n",
    "     Group 5:  48 instances (August 1990)\n",
    "     Group 6:  49 instances (Updated January 1991)\n",
    "     Group 7:  31 instances (June 1991)\n",
    "     Group 8:  86 instances (November 1991)\n",
    "     -----------------------------------------\n",
    "     Total:   699 points (as of the donated datbase on 15 July 1992)\n",
    "\n",
    "   Note that the results summarized above in Past Usage refer to a dataset\n",
    "   of size 369, while Group 1 has only 367 instances.  This is because it\n",
    "   originally contained 369 instances; 2 were removed.  The following\n",
    "   statements summarizes changes to the original Group 1's set of data:\n",
    "\n",
    "   #####  Group 1 : 367 points: 200B 167M (January 1989)\n",
    "   #####  Revised Jan 10, 1991: Replaced zero bare nuclei in 1080185 & 1187805\n",
    "   #####  Revised Nov 22,1991: Removed 765878,4,5,9,7,10,10,10,3,8,1 no record\n",
    "   #####                  : Removed 484201,2,7,8,8,4,3,10,3,4,1 zero epithelial\n",
    "   #####                  : Changed 0 to 1 in field 6 of sample 1219406\n",
    "   #####                  : Changed 0 to 1 in field 8 of following sample:\n",
    "   #####                  : 1182404,2,3,1,1,1,2,0,1,1,1\n",
    "\n",
    "5. Number of Instances: 699 (as of 15 July 1992)\n",
    "\n",
    "6. Number of Attributes: 10 plus the class attribute\n",
    "\n",
    "7. Attribute Information: (class attribute has been moved to last column)\n",
    "\n",
    "   #  Attribute                     Domain\n",
    "   -- -----------------------------------------\n",
    "   1. Sample code number            id number\n",
    "   2. Clump Thickness               1 - 10\n",
    "   3. Uniformity of Cell Size       1 - 10\n",
    "   4. Uniformity of Cell Shape      1 - 10\n",
    "   5. Marginal Adhesion             1 - 10\n",
    "   6. Single Epithelial Cell Size   1 - 10\n",
    "   7. Bare Nuclei                   1 - 10\n",
    "   8. Bland Chromatin               1 - 10\n",
    "   9. Normal Nucleoli               1 - 10\n",
    "  10. Mitoses                       1 - 10\n",
    "  11. Class:                        (2 for benign, 4 for malignant)\n",
    "\n",
    "8. Missing attribute values: 16\n",
    "\n",
    "   There are 16 instances in Groups 1 to 6 that contain a single missing \n",
    "   (i.e., unavailable) attribute value, now denoted by \"?\".  \n",
    "\n",
    "9. Class distribution:\n",
    " \n",
    "   Benign: 458 (65.5%)\n",
    "   Malignant: 241 (34.5%)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from math import sqrt\n",
    "import matplotlib.pyplot as plt\n",
    "import warnings  # To import for useless number for k\n",
    "from matplotlib import style\n",
    "from collections import Counter\n",
    "import random\n",
    "import pandas as pd\n",
    "\n",
    "style.use(\"fivethirtyeight\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Euclidean distance\n",
    "# plot1 = [1, 2]\n",
    "# plot2 = [3, 4]\n",
    "\n",
    "# euclidean_distance = sqrt((plot1[0] - plot2[0])**2 + (plot1[1] - plot2[1])**2)\n",
    "# print(\"Euclidean distance:\", euclidean_distance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Hard coded groups of point.\n",
    "#          class:       features         class:      features\n",
    "dataset = {\"b\": [[1, 2], [2, 3], [3, 1]], \"r\": [[6, 5], [7, 7], [8, 6]]}\n",
    "new_features = [5, 7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def k_nearest_neighbors(data, predict, k = 3):\n",
    "    if len(data) >= k:\n",
    "        warnings.warn(\"K is set to a value less than total voting groups!\")\n",
    "    distances = []\n",
    "    for group in data:\n",
    "        for features in data[group]:\n",
    "            euclidean_distance = np.linalg.norm(np.array(features) - np.array(predict))  # Fast algorithm for calculating Euclidean distance\n",
    "            distances.append([euclidean_distance, group])\n",
    "    votes = [i[1] for i in sorted(distances)[:k]]\n",
    "    vote_result = Counter(votes).most_common(1)[0][0]  # The closest and most common class\n",
    "    confidence = Counter(votes).most_common(1)[0][1] / k\n",
    "    return vote_result, confidence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The data is classified as: 'r' - confidence: 1.0\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZIAAAEJCAYAAAC+I6F6AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAGa9JREFUeJzt3X9sVfXh//HXvb2U21ZJWWmqzCKxttZewUGrMqPGxVAw\nsF7EDC/Y6Py5imYhBkScv3BubIEwI0z5aUTa0hH5YVsN2CwY6Aizdkswd3FeJCUSPmDtVllb7vq9\nP75/IExA7g/evffcA89Hwh/33PfpeZ1W7+ue877nXEdvb29UAABcIKfVAQAA9kaRAACMUCQAACMU\nCQDACEUCADBCkQAAjFAkAAAjFAkAwEhGFkkgELA6ghG755fsvw/ktxb5rZXu/BlZJAAA+6BIAABG\nKBIAgBGKBABghCIBABihSAAARigSAIARigQAYMRldQAAJzmOHNHwpUuV9c9/qvz4cblHjFC4vFz/\nnT9f0dGjrY4HnBdFAlitv185dXVydXTIefSoJOmyb59y7d2rYR98oFBVlU6sXi3l5VmXEziPuEUy\nbtw4ffnll+csr66u1ubNm1MSCrhk9Pcrz+uV65NPzjvEefSosltb5ZwxQ/3bt1MmqRIOy9XcrOxN\nm1TW06OcggINzpmjUE2N5GQWIJa4RbJr1y6Fw+HTj48ePao777xTM2bMSGkw4FKQU1cXs0S+y9XR\noZy6Op3YuDHFqS49ju5u5fp8yvL75QgGNezb5a7duxVesUIDTU2KFhZamjGTxa3ZUaNGqaio6PS/\ntrY2XX755brnnnvSkQ+4aDmOHJGroyOpdVwdHXL83/+lKNElKhJRrs8nV2enHMHgGU85gkG5OjuV\n6/NJkYhFATNfUsdr0WhUGzdu1H333aecnJxUZQIuCcOXLj09J5Io59GjGr50aYoSXZpczc3K8vtj\njsny++VqbU1TIvtJqkh27dqlQ4cO6YEHHkhVHuCSkfXPf17Yep99NsRJLm3ZjY3nHImczREMKru+\nPk2J7CepT21t2LBBEydO1Lhx4+KONb0fPt8HYD2770Om5y8/fvz0p7OSETx+POP3Tcr83/8pZT09\np+dEYjnR02ObfZKG9vdfWloa8/mEi6S7u1sffPCBli1bNiQbjiUQCBitbzW755fsvw92yO8eMeKC\n18v0fbPD7/+UnIKChMfZZZ/S/ftP+NRWY2Ojhg8frnvvvTeVeYBLRvi66y5svfLyIU5yaRucM0dR\ntzvmmKjbrcHa2jQlsp+EiiQajeqdd97RzJkzddllF3IwDuBs/12wQJErrkhqnciVV+q/CxakKNGl\nKVRTo7DHE3NM2ONRaPr0NCWyn4SKZM+ePfriiy/04IMPpjoPcMmIjh6tUFVVUuuEqqoUvfLKFCW6\nRDmdGmhqUqiy8pwjk6jbrVBlpQaamrgoMYaE5kjuuOMO9fb2pjoLcMk5sXq1nHGubD8ldNNNOrFq\nVRpSXXqihYXqb2uTq6VF2Q0NOnHqyvba2pNHIpRITNxrC7BSXp7633vvnHttfVfkyitP3mtr1Spu\nj5JKTqdCXq9CXq+tPiyQCSgSwGp5eTqxcePJu/8uW6aszz5T8NTdf6+//uTdfzmdhQxGkQAZIjp6\ntILLl0uy18dnAU78AQCMUCQAACMUCQDACEUCADBCkQAAjFAkAAAjFAkAwAhFAgAwQpEAAIxQJAAA\nIxQJAMAIRQIAMEKRAACMUCQAACMUCQDACEUCADBCkQAAjFAkAAAjFAkAwAhFAgAwklCRHD16VHV1\ndSopKVFRUZFuueUWtbe3pzobACBR4bBc27Ypd9YsldXVKXfWLLm2b5cikZRv2hVvQG9vr6ZMmaJJ\nkyZp8+bNKigo0KFDh1RYWJjycACA+Bzd3cr1+ZTl98sRDGrYt8tdu3crvGKFBpqaFE3ha3bcInn9\n9dd1xRVXaPXq1aeXjR07NmWBAABJiESU6/PJ1dl5zlOOYFCuzk7l+nzqb2uTnKmZzYj7U99//31V\nVlbqoYce0rXXXqvbbrtNa9asUTQaTUkgAEDiXM3NyvL7Y47J8vvlam1NWYa4RdLV1aX169dr7Nix\n2rJli+rq6rR48WKtXbs2ZaEAAInJbmyUIxiMOcYRDCq7vj5lGRy9vb0xDy0KCws1YcIEffjhh6eX\nvfLKK2ptbdXHH3983vUCgcDQpQQAfK+yujqN+J7TWmc7Xlmpz1etuqBtlJaWxnw+7hxJUVGRrrvu\nujOWlZWV6fDhw0YbjiUQCBitbzW755fsvw/ktxb50yenoCDhcanap7intiZNmqQDBw6csezAgQMq\nLi5OSSAAQOIG58xR1O2OOSbqdmuwtjZlGeIWydy5c9XR0aFly5bp4MGD2r59u9asWaNHH300ZaEA\nAIkJ1dQo7PHEHBP2eBSaPj1lGeIWycSJE9XQ0KBt27bpxz/+sX7961/rueeeo0gAIBM4nRpoalKo\nsvKcI5Oo261QZaUGmppS9tFfKYE5EkmaMmWKpkyZkrIQAIALFy0sVH9bm1wtLcpuaNCJnh7lFBRo\nsLb25JFICktESrBIAAAZzulUyOtVyOtN+4cFuGkjAMAIRQIAMEKRAACMUCQAACMUCQDACEUCADBC\nkQAAjFAkAAAjFAkAwAhFAgAwQpEAAIxQJAAAIxQJAMAIRQIAMEKRAACMUCQAACMUCQDACEUCADBC\nkQAAjFAkAAAjFAkAwAhFAgAwErdIlixZovz8/DP+lZWVpSMbADsJh+Xatk25s2aprK5OubNmybV9\nuxSJWJ0MKeZKZFBpaalaW1tPP87KykpZIAD24+juVq7Ppyy/X45gUMO+Xe7avVvhFSs00NSkaGGh\npRmROgkVicvlUlFRUaqzALCjSES5Pp9cnZ3nPOUIBuXq7FSuz6f+tjbJydn0i1FCf9Wuri6Vl5dr\n/Pjxevjhh9XV1ZXiWADswtXcrCy/P+aYLL9fru+c1cDFJW6RVFVV6Y033tC7776r119/XceOHVN1\ndbX+9a9/pSMfgAyX3dgoRzAYc4wjGFR2fX2aEiHdHL29vdFkVujv79eNN96oefPm6amnnjrvuEAg\nYBwOQOYrq6vTiO85rXW245WV+nzVqjQkwlArLS2N+XxCcyTflZeXp/Lych08eNBow7EEAgGj9a1m\n9/yS/feB/OmTU1CQ8Di77JOdfv/fJ935k575CgaDCgQCTL4DkCQNzpmjqNsdc0zU7dZgbW2aEiHd\n4hbJ888/r/b2dnV1demTTz7Rgw8+qIGBAc2ePTsd+QBkuFBNjcIeT8wxYY9HoenT05QI6Rb31NaR\nI0f06KOPqqenR6NGjVJVVZXa2to0ZsyYdOQDkOmcTg00NZ1xHckpUbdbYY9HA01NfPT3Iha3SN56\n66105ABgY9HCQvW3tcnV0qLshgad6OlRTkGBBmtrTx6JUCIXtaQn2wHgezmdCnm9Cnm9tp+sRnJ4\nmwAAMEKRAACMUCQAACMUCQDACEUCADBCkQAAjFAkAAAjFAkAwAhFAgAwQpEAAIxQJAAAIxQJAMAI\nRQIAMEKRAACMUCQAACMUCQDACEUCADBCkQAAjFAkAAAjFAkAwAhFAgAwQpEAAIwkXSTLly9Xfn6+\nFixYkIo8AACbSapIOjo69Pbbb8vj8aQqDwDAZhIukm+++UaPPfaYVq5cqfz8/FRmAgDYSMJFMm/e\nPHm9Xt1xxx2pzAMAsBlXIoM2bNiggwcPas2aNanOAwCwGUdvb2801oBAIKCpU6dqx44dKi0tlSRN\nmzZNFRUVWrp0acz1AAD2d+q1/3ziFklDQ4OefPJJZWVlnV4WDoflcDjkdDp15MgRDR8+fGjSfisQ\nCMQNnsnsnl+y/z6Q31rkt1a688c9tTVt2jRNmDDhjGVPPvmkSkpK9PTTTys7Oztl4QAAmS9ukeTn\n55/zKa3c3FyNHDlSFRUVKQsGALAHrmwHABhJ6FNbZ3v//feHOgcAwKY4IgEAGKFIAABGKBIAgBGK\nBABghCIBABihSAAARigSAIARigQAYIQiAQAYoUgAAEYoEgCAEYoEAGCEIgEAGKFIAABGKBIAgBGK\nBABghCIBABihSAAARigSAIARigQAYIQiAQAYoUgAAEYoEgCAkbhFsnbtWt16660qLi5WcXGxJk+e\nrJ07d6Yjm62Ew9K2bS7NmpWruroyzZqVq+3bXYpErE4GAKnlijdg9OjRWrx4sUpKShSJRLRp0ybd\nf//9+uijj3TDDTekI2PG6+52yOfLld+fpWDQIWmYJGn3bpdWrAirqWlAhYVRa0MCQIrEPSKZNm2a\nJk+erGuuuUbXXnutXnjhBV122WXq6OhIR76MF4lIPl+uOjtd35bI/wSDDnV2uuTz5XJkAuCildQc\nSTgc1pYtW9Tf36+bb745VZlspbnZJb8/K+YYvz9Lra1xD/4AwJYSenXz+/2qrq5WMBhUXl6e6uvr\n5fF4Up3NFhobs885EjlbMOhQfX22ampCaUoFAOnj6O3tjXvyfnBwUIcPH9bx48f13nvvacOGDWpt\nbVVFRcV51wkEAkMaNFPV1ZWps3NE3HGVlce1atXnaUgEAEOrtLQ05vMJFcnZvF6viouLtXLlygsO\nFksgEIgbPFPMmpWrDz8cFndcdfX/0+bNA2lINDTs9Df4PuS3Fvmtle78F3QdSSQS0eDg4FBnsaU5\ncwbldsfuYrc7qtpafl8ALk5xi+Tll1/W3r17dejQIfn9fi1evFjt7e362c9+lo58Ga+mJiSPJxxz\njMcT1vTpzI8AuDjFnWw/duyYHn/8cX311VcaMWKEPB6P3n33Xd11113pyJfxnE6pqWngrOtITnK7\no/J4Tl5H4uQeAgAuUnGL5M0330xHDlsrLIyqra1fLS0uNTRkq6fnhAoKclRbO6jp00OUCICLGhc3\nDBGnU/J6Q/J6Q7afqAOAZPBeGQBghCIBABihSAAARigSAIARigQAYIQiAQAYoUgAAEYoEgCAEYoE\nAGCEIgEAGKFIAABGKBIAgBGKBABghCIBABihSAAARigSAIARigQAYIQiAQAYoUgAAEYoEgCAEYoE\nAGCEIgEAGHFZHeCUcFhqbnZp06Zs9fSUqaAgR3PmDKqmJiQndQcAGStukSxfvlwtLS06cOCAsrOz\nVVVVpZdeekkVFRVDFqK72yGfL1d+f5aCQYekYZKk3btdWrEirKamARUWRodsewCAoRP3vX57e7se\neeQR7dy5U83NzXK5XJoxY4b+/e9/D0mASETy+XLV2en6tkT+Jxh0qLPTJZ8vV5HIkGwOADDE4h6R\nbN269YzHq1ev1pgxY7Rv3z7dfffdxgGam13y+7NijvH7s9Ta6lJNTch4ewCAoZX07ENfX58ikYjy\n8/OHJEBjY/Y5RyJnCwYdqq/PHpLtAQCGlqO3tzepyYef//zn+uKLL/TRRx8pK+v8RxKBQCChn1dX\nV6bOzhFxx1VWHteqVZ8nnBMAMDRKS0tjPp/Up7aee+457du3Tzt27IhZIols+JSCgpyExyX6M60W\nCARsk/V87L4P5LcW+a2V7vwJn9patGiRtmzZoubmZo0dO3bIAsyZMyi3O/ZBkdsdVW3t4JBtEwAw\ndBIqkoULF54ukbKysiENUFMTkscTjjnG4wlr+nQm2gEgE8Utkvnz56uxsVFr165Vfn6+jh07pmPH\njqmvr29oAjilpqYBVVaGzjkycbujqqwMqalpgIsSASBDxZ0jWbdunSTJ6/WesXzhwoVatGjRkIQo\nLIyqra1fLS0uNTRkq6fnhAoKclRbO6jp07myHQAyWdwi6e3tTUcOOZ2S1xuS1xuy/UQXAFxKeK8P\nADBCkQAAjFAkAAAjFAkAwAhFAgAwQpEAAIxQJAAAIxQJAMAIRQIAMEKRAACMUCQAACMUCQDACEUC\nADBCkQAAjFAkAAAjFAkAwAhFAgAwQpEAAIxQJAAAIxQJAMAIRQIAMEKRAACMuKwOgMwRDkvNzS5t\n2pStnp4yFRTkaM6cQdXUhOTkLQeA80jo5eEvf/mLfD6frr/+euXn56uhoSHVuZBm3d0OVVfn6Ykn\ncvXhh8PU2TlCH344THV1uZo8OU/d3Q6rIwLIUAkVSX9/vyoqKvS73/1OOTk5qc6ENItEJJ8vV52d\nLgWDZxZGMOhQZ6dLPl+uIhGLAgLIaAkVSXV1tV588UV5vV45Ocdx0Wludsnvz4o5xu/PUmsrZ0IB\nnItWgBobs885EjlbMOhQfX12mhIBsJOUvcUMBAKWrm81O+Xv6SmTNCyBcSdstV92yvp9yG8t8v9P\naWlpzOdTViTxNhxLIBAwWt9qdstfUJDYvFdBQY5t9stuf4Ozkd9a5E8Op7agOXMG5XZHY45xu6Oq\nrR1MUyIAdkKRQDU1IXk84ZhjPJ6wpk8PpSkRADtJqEj6+vq0f/9+7d+/X5FIRIcPH9b+/fv15Zdf\npjof0sDplJqaBlRZGTrnyMTtjqqyMqSmpgEuSgTwvRKaI/n73/+un/70p6cfL1myREuWLNHs2bP1\n5ptvpiwc0qewMKq2tn61tLjU0JCtnp4TKijIUW3toKZP58p2AOeXUJHcfvvt6u3tTXUWWMzplLze\nkLzekO0nGwGkD+8zAQBGKBIAgBGKBABgxNHb2xv7AgIAAGLgiAQAYIQiAQAYoUgAAEYoEgCAEYoE\nAGAkY4rE7t8Lv3z5cv3kJz9RcXGxSkpKdN999+kf//iH1bEStnbtWt16660qLi5WcXGxJk+erJ07\nd1od64ItX75c+fn5WrBggdVRErJkyRLl5+ef8a+srMzqWEk5evSo6urqVFJSoqKiIt1yyy1qb2+3\nOlbCxo0bd87fID8/X7NmzbI6WkLC4bBeffVVjR8/XkVFRRo/frxeffVVhUKpv9lqxnx36qnvhZ89\ne7bq6uqsjpO09vZ2PfLII5o4caKi0ah++9vfasaMGfrrX/+qkSNHWh0vrtGjR2vx4sUqKSlRJBLR\npk2bdP/99+ujjz7SDTfcYHW8pHR0dOjtt9+Wx+OxOkpSSktL1draevpxVlbsrz/OJL29vZoyZYom\nTZqkzZs3q6CgQIcOHVJhYaHV0RK2a9cuhcP/uwv20aNHdeedd2rGjBkWpkrca6+9pnXr1unNN99U\nRUWF/H6/5s6dq+zsbD3zzDMp3XbGFEl1dbWqq6slSXPnzrU4TfK2bt16xuPVq1drzJgx2rdvn+6+\n+26LUiVu2rRpZzx+4YUXtH79enV0dNiqSL755hs99thjWrlypX7/+99bHScpLpdLRUVFVse4IK+/\n/rquuOIKrV69+vSysWPHWhfoAowaNeqMxxs3btTll1+ue+65x6JEyfn44481derU0683V199taZO\nnarOzs6UbztjTm1dbPr6+hSJRJSfn291lKSFw2Ft2bJF/f39uvnmm62Ok5R58+bJ6/XqjjvusDpK\n0rq6ulReXq7x48fr4YcfVldXl9WREvb++++rsrJSDz30kK699lrddtttWrNmjaJRe17vHI1GtXHj\nRt13333KyUnsG0StNmnSJLW3t+vzzz+XJH322Wfas2ePJk+enPJtZ8wRycXm2Wef1bhx42z1Quz3\n+1VdXa1gMKi8vDzV19fb6vTQhg0bdPDgQa1Zs8bqKEmrqqrSG2+8odLSUn399ddaunSpqqurtW/f\nPv3gBz+wOl5cXV1dWr9+vebOnat58+bp008/1cKFCyVJjz/+uMXpkrdr1y4dOnRIDzzwgNVREjZv\n3jz19fXplltuUVZWlkKhkObPn69HH3005dumSFLgueee0759+7Rjxw5bnecuLS3Vnj17dPz4cb33\n3nt64okn1NraqoqKCqujxRUIBPTKK69ox44dGjZsmNVxknb2u8abbrpJN954oxobG/XUU09ZlCpx\nkUhEEyZM0EsvvSRJuvHGG3Xw4EGtW7fOlkWyYcMGTZw4UePGjbM6SsK2bt2qpqYmrVu3TuXl5fr0\n00/17LPPasyYMSkvRIpkiC1atEhbt25VS0uL7c4RZ2dn65prrpEk/ehHP9Lf/vY3vfHGG1q5cqXF\nyeL7+OOP1dPTo0mTJp1eFg6HtXfvXr311ls6cuSIhg8fbmHC5OTl5am8vFwHDx60OkpCioqKdN11\n152xrKysTIcPH7Yo0YXr7u7WBx98oGXLllkdJSkvvviinnrqKd17772SJI/Hoy+//FJ/+MMfKBI7\nWbhwobZt26aWlhbbfXTz+0QiEQ0ODlodIyHTpk3ThAkTzlj25JNPqqSkRE8//bSys7MtSnZhgsGg\nAoGAbr/9dqujJGTSpEk6cODAGcsOHDig4uJiixJduMbGRg0fPvz0C7JdDAwMnHMGJCsrS5FIJOXb\nzpgi6evrO/3u67vfCz9y5Ehb/Mc4f/58/elPf1J9fb3y8/N17NgxSSffWV522WUWp4vv5ZdfVnV1\ntX74wx+qr69P7777rtrb27V582aroyXk1Gf+vys3N1cjR460xam5559/XlOnTtVVV111eo5kYGBA\ns2fPtjpaQubOnavq6motW7ZMM2fO1P79+7VmzRq98MILVkdLSjQa1TvvvKOZM2fa4v/b75o6dape\ne+01XX311SovL9f+/fv1xz/+UT6fL+XbzpjbyO/Zs+eM74U/xS7fC3++T2ctXLhQixYtSnOa5D3x\nxBPas2ePvvrqK40YMUIej0e//OUvddddd1kd7YJNmzZNFRUVWrp0qdVR4nr44Ye1d+9e9fT0aNSo\nUaqqqtKvfvUrlZeXWx0tYTt37tQrr7yiAwcO6KqrrtJjjz2mX/ziF3I4HFZHS9ju3btVU1OjP//5\nz6qsrLQ6TlL+85//6De/+Y1aW1v19ddfq6ioSPfee6+eeeYZud3ulG47Y4oEAGBPXEcCADBCkQAA\njFAkAAAjFAkAwAhFAgAwQpEAAIxQJAAAIxQJAMAIRQIAMPL/AfEktpeeefVkAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x18fc104a438>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "result, confidence = k_nearest_neighbors(dataset, new_features)\n",
    "print(\"The data is classified as: '{}' - confidence: {}\".format(result, confidence))\n",
    "for class_color, features in dataset.items():\n",
    "    for point in features:\n",
    "        plt.scatter(point[0], point[1], s=100, color=class_color)\n",
    "plt.scatter(new_features[0], new_features[1], s=200, color=result)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[4.0, 1.0, 1.0, 2.0, 2.0, 1.0, 2.0, 1.0, 1.0, 2.0], [8.0, 7.0, 8.0, 7.0, 5.0, 5.0, 5.0, 10.0, 2.0, 4.0], [1.0, 1.0, 1.0, 1.0, 5.0, 1.0, 3.0, 1.0, 1.0, 2.0]]\n"
     ]
    }
   ],
   "source": [
    "df = pd.read_csv(\"breast-cancer-wisconsin.data\")\n",
    "df.replace(\"?\", -999999, inplace=True)\n",
    "df.drop([\"id\"], 1, inplace=True)\n",
    "full_data = df.astype(float).values.tolist()\n",
    "random.shuffle(full_data)\n",
    "print(full_data[:3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_size = 0.2\n",
    "train_set = {2: [], 4: []}  # Class: (2 for benign, 4 for malignant)\n",
    "test_set = {2: [], 4: []}  # Class: (2 for benign, 4 for malignant)\n",
    "train_data = full_data[:-int(test_size * len(full_data))]  # 80% of the data\n",
    "test_data = full_data[-int(test_size * len(full_data)):]  # 20% of the data\n",
    "\n",
    "for entry in train_data:\n",
    "    train_set[entry[-1]].append(entry[:-1])  # For every class appends the features\n",
    "    \n",
    "for entry in test_data:\n",
    "    test_set[entry[-1]].append(entry[:-1])  # For every class appends the features"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Confidence on incorrect prediction: 1.0\n",
      "Confidence on incorrect prediction: 0.8\n",
      "Confidence on incorrect prediction: 0.6\n",
      "Confidence on incorrect prediction: 0.6\n",
      "Accuracy: 0.9712230215827338\n"
     ]
    }
   ],
   "source": [
    "correct = 0\n",
    "total = 0\n",
    "for group in test_set:\n",
    "    for data in test_set[group]:\n",
    "        vote, confidence = k_nearest_neighbors(train_set, data, k=5)\n",
    "        if group == vote:\n",
    "            correct += 1\n",
    "        else:\n",
    "            print(\"Confidence on incorrect prediction:\", confidence)\n",
    "        total += 1\n",
    "print(\"Accuracy:\", correct / total)"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}