knn_2d authors solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "da6f9833",
   "metadata": {},
   "source": [
    "# 2_knn_2d\n",
    "Let the user draw points and then use KNN to classify new points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "04918e69",
   "metadata": {},
   "outputs": [],
   "source": [
    "import tkinter as tk\n",
    "\n",
    "# Get the text in an Entry widget and\n",
    "# convert it to an int.\n",
    "\n",
    "def get_int(entry):\n",
    "    return int(entry.get())\n",
    "\n",
    "# Make Label and Entry widgets for a field.\n",
    "# Return the Entry widget.\n",
    "def make_field(parent, label_width, label_text, entry_width, entry_default):\n",
    "    frame = tk.Frame(parent)\n",
    "    frame.pack(side=tk.TOP)\n",
    "\n",
    "    label = tk.Label(frame, text=label_text, width=label_width, anchor=tk.W)\n",
    "    label.pack(side=tk.LEFT)\n",
    "\n",
    "    entry = tk.Entry(frame, width=entry_width, justify='right')\n",
    "    entry.insert(tk.END, entry_default)\n",
    "    entry.pack(side=tk.LEFT)\n",
    "\n",
    "    return entry"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ef952560",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "class DataPoint:\n",
    "    # Create a DataPoint at this spot.\n",
    "    def __init__(self, x, y, name):\n",
    "        self.name = name\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "\n",
    "    # Return the distance between this point and another one.\n",
    "    def distance(self, other):\n",
    "        dx = self.x - other.x\n",
    "        dy = self.y - other.y\n",
    "        return math.sqrt(dx * dx + dy * dy)\n",
    "\n",
    "    # Use K nearest neighbors to set the data point's name.\n",
    "    def knn(self, data_points, k):\n",
    "        # Sort the data points by distance this one.\n",
    "        sorted_data_points = sorted(data_points, key=lambda other: self.distance(other))\n",
    "\n",
    "        # Count the first k votes.\n",
    "        votes = {}\n",
    "        num_votes = 0\n",
    "        for point in sorted_data_points:\n",
    "            # Add 1 to this name's vote count.\n",
    "            if point.name in votes:\n",
    "                votes[point.name] += 1\n",
    "            else:\n",
    "                votes[point.name] = 1\n",
    "\n",
    "            # Count up to k votes.\n",
    "            num_votes += 1\n",
    "            if num_votes >= k: break\n",
    "\n",
    "        # See which name had the most votes.\n",
    "        self.name = max(votes, key=lambda name:votes[name])\n",
    "\n",
    "    # Draw the data point.\n",
    "    def create_oval(self, canvas, bg_color):\n",
    "        radius = 8\n",
    "        canvas.create_oval(\n",
    "            self.x - radius, self.y - radius,\n",
    "            self.x + radius, self.y + radius,\n",
    "            fill=bg_color)\n",
    "        canvas.create_text(self.x, self.y, text=self.name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "47a93e74",
   "metadata": {},
   "outputs": [],
   "source": [
    "import tkinter as tk\n",
    "\n",
    "# The main App class.\n",
    "\n",
    "# Geometry constants.\n",
    "WINDOW_WID = 500\n",
    "WINDOW_HGT = 300\n",
    "MARGIN = 5\n",
    "CANVAS_WID = WINDOW_WID - 200\n",
    "CANVAS_HGT = WINDOW_HGT - 2 * MARGIN\n",
    "\n",
    "class App:\n",
    "    # Create and manage the tkinter interface.\n",
    "    def __init__(self):\n",
    "        self.network = None\n",
    "\n",
    "        # Make the main interface.\n",
    "        self.window = tk.Tk()\n",
    "        self.window.title('knn_2d')\n",
    "        self.window.protocol('WM_DELETE_WINDOW', self.kill_callback)\n",
    "        self.window.geometry(f'{WINDOW_WID}x{WINDOW_HGT}')\n",
    "\n",
    "        # Build the rest of the UI.\n",
    "        self.build_ui()\n",
    "\n",
    "        # Initially we have no data points.\n",
    "        self.data_points = []\n",
    "\n",
    "        # Display the window.\n",
    "        self.window.focus_force()\n",
    "        self.window.mainloop()\n",
    "\n",
    "    # Build the tkinter user interface.\n",
    "    def build_ui(self):\n",
    "        # Make the drawing canvas.\n",
    "        canvas_wid = CANVAS_WID\n",
    "        canvas_hgt = CANVAS_HGT\n",
    "        self.canvas = tk.Canvas(self.window, bg='white',\n",
    "            borderwidth=0, highlightthickness=0, relief=tk.SUNKEN, width=canvas_wid, height=canvas_hgt)\n",
    "        self.canvas.pack(side=tk.LEFT, padx=MARGIN, pady=MARGIN)\n",
    "        self.canvas.bind('<Button-1>', self.click)\n",
    "\n",
    "        # Right frame.\n",
    "        right_frame = tk.Frame(self.window)\n",
    "        right_frame.pack(side=tk.TOP, padx=MARGIN, pady=MARGIN)\n",
    "\n",
    "        # Label and text box for a point's name.\n",
    "        self.cluster_entry = make_field(right_frame, 10, 'Cluster:', 3, 'a')\n",
    "\n",
    "        # Number of neighbors to check.\n",
    "        self.num_neighbors_entry = make_field(right_frame, 10, '# Neighbors:', 3, '5')\n",
    "\n",
    "        # Test data set buttons.\n",
    "        button_frame = tk.Frame(right_frame, pady=MARGIN)\n",
    "        button_frame.pack(side=tk.TOP)\n",
    "        test1_button = tk.Button(button_frame,\n",
    "            text='Dataset 1', width=8, command=self.load_dataset_1)\n",
    "        test1_button.pack(side=tk.LEFT)\n",
    "        test2_button = tk.Button(button_frame,\n",
    "            text='Dataset 2', width=8, command=self.load_dataset_2)\n",
    "        test2_button.pack(side=tk.LEFT, padx=(MARGIN, 0))\n",
    "\n",
    "        # Test data set buttons.\n",
    "        button_frame = tk.Frame(right_frame, pady=MARGIN)\n",
    "        button_frame.pack(side=tk.TOP)\n",
    "        test3_button = tk.Button(button_frame,\n",
    "            text='Dataset 3', width=8, command=self.load_dataset_3)\n",
    "        test3_button.pack(side=tk.LEFT)\n",
    "        test4_button = tk.Button(button_frame,\n",
    "            text='Dataset 4', width=8, command=self.load_dataset_4)\n",
    "        test4_button.pack(side=tk.LEFT, padx=(MARGIN, 0))\n",
    "\n",
    "        # Clear button.\n",
    "        clear_button = tk.Button(right_frame, text='Clear', width=7, command=self.clear)\n",
    "        clear_button.pack(side=tk.TOP, pady=10)\n",
    "\n",
    "    # Clear existing points.\n",
    "    def clear(self):\n",
    "        self.data_points = []\n",
    "        self.canvas.delete('all')\n",
    "\n",
    "    # Save and draw a data point.\n",
    "    def click(self, event):\n",
    "        # Make the basic data point object.\n",
    "        name = self.cluster_entry.get().strip()\n",
    "        self.make_data_point(event.x, event.y, name)\n",
    "\n",
    "    def make_data_point(self, x, y, name):\n",
    "        data_point = DataPoint(x, y, name)\n",
    "\n",
    "        # If it has no name, use KNN to assign one.\n",
    "        if name == '':\n",
    "            # If there are no points defined yet, do nothing.\n",
    "            if len(self.data_points) == 0: return\n",
    "\n",
    "            # See how many neighbors to use.\n",
    "            k = get_int(self.num_neighbors_entry)\n",
    "\n",
    "            # Use KNN to assign a name to the point.\n",
    "            data_point.knn(self.data_points, k)\n",
    "\n",
    "            # Draw with a pink background.\n",
    "            data_point.create_oval(self.canvas, 'pink')\n",
    "        else:\n",
    "            # Draw with a white background.\n",
    "            data_point.create_oval(self.canvas, 'white')\n",
    "\n",
    "            # Save this point to use later as a neighbor.\n",
    "            self.data_points.append(data_point)\n",
    "\n",
    "    def kill_callback(self):\n",
    "        self.window.destroy()\n",
    "\n",
    "    def load_dataset_1(self):\n",
    "        self.clear()\n",
    "        self.data_points = [\n",
    "            DataPoint(62, 80, 'a'),\n",
    "            DataPoint(82, 58, 'a'),\n",
    "            DataPoint(95, 91, 'a'),\n",
    "            DataPoint(111, 54, 'a'),\n",
    "            DataPoint(80, 82, 'a'),\n",
    "            DataPoint(136, 86, 'a'),\n",
    "            DataPoint(121, 108, 'a'),\n",
    "            DataPoint(106, 75, 'a'),\n",
    "            DataPoint(96, 105, 'a'),\n",
    "            DataPoint(67, 124, 'a'),\n",
    "            DataPoint(63, 100, 'a'),\n",
    "            DataPoint(165, 217, 'c'),\n",
    "            DataPoint(166, 198, 'c'),\n",
    "            DataPoint(193, 219, 'c'),\n",
    "            DataPoint(225, 237, 'c'),\n",
    "            DataPoint(207, 248, 'c'),\n",
    "            DataPoint(171, 260, 'c'),\n",
    "            DataPoint(150, 234, 'c'),\n",
    "            DataPoint(184, 240, 'c'),\n",
    "            DataPoint(184, 264, 'c'),\n",
    "            DataPoint(176, 222, 'c'),\n",
    "            DataPoint(194, 199, 'c'),\n",
    "            DataPoint(212, 216, 'c'),\n",
    "            DataPoint(240, 98, 'b'),\n",
    "            DataPoint(215, 101, 'b'),\n",
    "            DataPoint(220, 129, 'b'),\n",
    "            DataPoint(223, 113, 'b'),\n",
    "            DataPoint(242, 122, 'b'),\n",
    "            DataPoint(253, 113, 'b'),\n",
    "            DataPoint(244, 85, 'b'),\n",
    "            DataPoint(219, 72, 'b'),\n",
    "            DataPoint(235, 144, 'b'),\n",
    "            DataPoint(266, 131, 'b'),\n",
    "            DataPoint(259, 92, 'b'),\n",
    "            DataPoint(205, 119, 'b'),\n",
    "        ]\n",
    "        for point in self.data_points:\n",
    "            point.create_oval(self.canvas, 'white')\n",
    "        self.cluster_entry.delete(0, tk.END)\n",
    "        self.cluster_entry.insert(tk.END, '')\n",
    "\n",
    "    def load_dataset_2(self):\n",
    "        self.clear()\n",
    "        self.data_points = [\n",
    "            DataPoint(198, 69, 'a'),\n",
    "            DataPoint(215, 75, 'a'),\n",
    "            DataPoint(213, 99, 'a'),\n",
    "            DataPoint(220, 127, 'a'),\n",
    "            DataPoint(211, 149, 'a'),\n",
    "            DataPoint(63, 192, 'a'),\n",
    "            DataPoint(92, 208, 'a'),\n",
    "            DataPoint(164, 209, 'a'),\n",
    "            DataPoint(91, 68, 'a'),\n",
    "            DataPoint(54, 107, 'a'),\n",
    "            DataPoint(50, 134, 'a'),\n",
    "            DataPoint(136, 59, 'a'),\n",
    "            DataPoint(174, 58, 'a'),\n",
    "            DataPoint(212, 191, 'a'),\n",
    "            DataPoint(202, 170, 'a'),\n",
    "            DataPoint(192, 194, 'a'),\n",
    "            DataPoint(167, 192, 'a'),\n",
    "            DataPoint(143, 192, 'a'),\n",
    "            DataPoint(129, 209, 'a'),\n",
    "            DataPoint(142, 225, 'a'),\n",
    "            DataPoint(101, 228, 'a'),\n",
    "            DataPoint(99, 189, 'a'),\n",
    "            DataPoint(72, 220, 'a'),\n",
    "            DataPoint(45, 181, 'a'),\n",
    "            DataPoint(70, 179, 'a'),\n",
    "            DataPoint(55, 160, 'a'),\n",
    "            DataPoint(36, 160, 'a'),\n",
    "            DataPoint(36, 140, 'a'),\n",
    "            DataPoint(45, 150, 'a'),\n",
    "            DataPoint(42, 113, 'a'),\n",
    "            DataPoint(60, 68, 'a'),\n",
    "            DataPoint(59, 88, 'a'),\n",
    "            DataPoint(99, 56, 'a'),\n",
    "            DataPoint(82, 93, 'a'),\n",
    "            DataPoint(127, 36, 'a'),\n",
    "            DataPoint(151, 53, 'a'),\n",
    "            DataPoint(150, 20, 'a'),\n",
    "            DataPoint(124, 48, 'a'),\n",
    "            DataPoint(200, 48, 'a'),\n",
    "            DataPoint(180, 40, 'a'),\n",
    "            DataPoint(166, 35, 'a'),\n",
    "            DataPoint(224, 96, 'a'),\n",
    "            DataPoint(240, 136, 'a'),\n",
    "            DataPoint(238, 115, 'a'),\n",
    "            DataPoint(230, 114, 'a'),\n",
    "            DataPoint(223, 133, 'a'),\n",
    "            DataPoint(231, 158, 'a'),\n",
    "            DataPoint(216, 177, 'a'),\n",
    "            DataPoint(206, 176, 'a'),\n",
    "            DataPoint(183, 179, 'a'),\n",
    "            DataPoint(195, 212, 'a'),\n",
    "            DataPoint(138, 127, 'b'),\n",
    "            DataPoint(133, 114, 'b'),\n",
    "            DataPoint(155, 114, 'b'),\n",
    "            DataPoint(151, 131, 'b'),\n",
    "            DataPoint(145, 120, 'b'),\n",
    "            DataPoint(142, 142, 'b'),\n",
    "            DataPoint(131, 133, 'b'),\n",
    "            DataPoint(125, 123, 'b'),\n",
    "            DataPoint(124, 144, 'b'),\n",
    "        ]\n",
    "        for point in self.data_points:\n",
    "            point.create_oval(self.canvas, 'white')\n",
    "        self.cluster_entry.delete(0, tk.END)\n",
    "        self.cluster_entry.insert(tk.END, '')\n",
    "\n",
    "    def load_dataset_3(self):\n",
    "        self.clear()\n",
    "        self.data_points = [\n",
    "            DataPoint(100, 87, 'a'),\n",
    "            DataPoint(92, 62, 'a'),\n",
    "            DataPoint(74, 84, 'a'),\n",
    "            DataPoint(123, 75, 'a'),\n",
    "            DataPoint(140, 76, 'a'),\n",
    "            DataPoint(174, 76, 'a'),\n",
    "            DataPoint(202, 77, 'a'),\n",
    "            DataPoint(190, 60, 'a'),\n",
    "            DataPoint(155, 67, 'a'),\n",
    "            DataPoint(189, 83, 'a'),\n",
    "            DataPoint(218, 113, 'a'),\n",
    "            DataPoint(207, 97, 'a'),\n",
    "            DataPoint(233, 85, 'a'),\n",
    "            DataPoint(230, 100, 'a'),\n",
    "            DataPoint(193, 116, 'a'),\n",
    "            DataPoint(187, 128, 'a'),\n",
    "            DataPoint(179, 114, 'a'),\n",
    "            DataPoint(199, 123, 'a'),\n",
    "            DataPoint(173, 142, 'a'),\n",
    "            DataPoint(167, 133, 'a'),\n",
    "            DataPoint(167, 160, 'a'),\n",
    "            DataPoint(156, 161, 'a'),\n",
    "            DataPoint(157, 145, 'a'),\n",
    "            DataPoint(113, 172, 'a'),\n",
    "            DataPoint(135, 153, 'a'),\n",
    "            DataPoint(140, 169, 'a'),\n",
    "            DataPoint(126, 164, 'a'),\n",
    "            DataPoint(90, 188, 'a'),\n",
    "            DataPoint(103, 191, 'a'),\n",
    "            DataPoint(115, 187, 'a'),\n",
    "            DataPoint(129, 195, 'a'),\n",
    "            DataPoint(129, 176, 'a'),\n",
    "            DataPoint(103, 195, 'a'),\n",
    "            DataPoint(86, 221, 'a'),\n",
    "            DataPoint(69, 212, 'a'),\n",
    "            DataPoint(67, 228, 'a'),\n",
    "            DataPoint(83, 238, 'a'),\n",
    "            DataPoint(107, 212, 'a'),\n",
    "            DataPoint(106, 235, 'a'),\n",
    "            DataPoint(139, 259, 'a'),\n",
    "            DataPoint(124, 253, 'a'),\n",
    "            DataPoint(117, 253, 'a'),\n",
    "            DataPoint(125, 240, 'a'),\n",
    "            DataPoint(183, 253, 'a'),\n",
    "            DataPoint(207, 228, 'a'),\n",
    "            DataPoint(207, 231, 'a'),\n",
    "            DataPoint(209, 244, 'a'),\n",
    "            DataPoint(202, 240, 'a'),\n",
    "            DataPoint(199, 256, 'a'),\n",
    "            DataPoint(182, 238, 'a'),\n",
    "            DataPoint(169, 248, 'a'),\n",
    "            DataPoint(147, 241, 'a'),\n",
    "            DataPoint(151, 258, 'a'),\n",
    "            DataPoint(170, 260, 'a'),\n",
    "            DataPoint(95, 76, 'a'),\n",
    "            DataPoint(114, 74, 'a'),\n",
    "            DataPoint(114, 74, 'a'),\n",
    "            DataPoint(114, 74, 'a'),\n",
    "            DataPoint(118, 57, 'a'),\n",
    "            DataPoint(145, 57, 'a'),\n",
    "            DataPoint(64, 130, 'b'),\n",
    "            DataPoint(64, 143, 'b'),\n",
    "            DataPoint(50, 137, 'b'),\n",
    "            DataPoint(51, 123, 'b'),\n",
    "            DataPoint(48, 157, 'b'),\n",
    "            DataPoint(43, 152, 'b'),\n",
    "            DataPoint(59, 152, 'b'),\n",
    "            DataPoint(37, 135, 'b'),\n",
    "            DataPoint(218, 163, 'c'),\n",
    "            DataPoint(220, 169, 'c'),\n",
    "            DataPoint(235, 173, 'c'),\n",
    "            DataPoint(223, 152, 'c'),\n",
    "            DataPoint(248, 152, 'c'),\n",
    "            DataPoint(227, 164, 'c'),\n",
    "            DataPoint(247, 176, 'c'),\n",
    "            DataPoint(239, 155, 'c'),\n",
    "            DataPoint(239, 189, 'c'),\n",
    "            DataPoint(227, 179, 'c'),\n",
    "            DataPoint(211, 180, 'c'),\n",
    "        ]\n",
    "        for point in self.data_points:\n",
    "            point.create_oval(self.canvas, 'white')\n",
    "        self.cluster_entry.delete(0, tk.END)\n",
    "        self.cluster_entry.insert(tk.END, '')\n",
    "\n",
    "    def load_dataset_4(self):\n",
    "        self.clear()\n",
    "        self.data_points = [\n",
    "            DataPoint(139, 31, 'a'),\n",
    "            DataPoint(127, 60, 'a'),\n",
    "            DataPoint(137, 117, 'a'),\n",
    "            DataPoint(137, 160, 'a'),\n",
    "            DataPoint(147, 120, 'a'),\n",
    "            DataPoint(115, 96, 'a'),\n",
    "            DataPoint(141, 90, 'a'),\n",
    "            DataPoint(152, 60, 'a'),\n",
    "            DataPoint(156, 112, 'a'),\n",
    "            DataPoint(123, 74, 'a'),\n",
    "            DataPoint(68, 241, 'b'),\n",
    "            DataPoint(80, 228, 'b'),\n",
    "            DataPoint(115, 249, 'b'),\n",
    "            DataPoint(135, 240, 'b'),\n",
    "            DataPoint(155, 219, 'b'),\n",
    "            DataPoint(169, 242, 'b'),\n",
    "            DataPoint(193, 248, 'b'),\n",
    "            DataPoint(120, 219, 'b'),\n",
    "            DataPoint(155, 255, 'b'),\n",
    "            DataPoint(211, 229, 'b'),\n",
    "            DataPoint(190, 221, 'b'),\n",
    "            DataPoint(245, 232, 'b'),\n",
    "        ]\n",
    "        for point in self.data_points:\n",
    "            point.create_oval(self.canvas, 'white')\n",
    "        self.cluster_entry.delete(0, tk.END)\n",
    "        self.cluster_entry.insert(tk.END, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "68bced29",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.App at 0x2a94edeff70>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "App()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "44849fb6",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}