12. K-ближайших соседей.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 сосед(а,ей): 40 правильных из 75\n",
      "3 сосед(а,ей): 44 правильных из 75\n",
      "5 сосед(а,ей): 41 правильных из 75\n",
      "7 сосед(а,ей): 35 правильных из 75\n",
      "1 7.947421226228712e-06 0.3310009902894413 2.4010264196729895e-05\n",
      "6 0.18647467260473205 0.9677679968196268 0.19268530600055306\n",
      "11 0.315888574043911 1.3334395796543002 0.23689755341281116\n",
      "16 0.7209190490469604 1.6154152410436047 0.4462747600308797\n",
      "21 0.9694045860570238 1.8574960773724116 0.5218878240800003\n",
      "26 1.1698067560262715 2.0632214700056446 0.5669807013122402\n",
      "31 1.2930748713962408 2.257299829279505 0.5728414340991512\n",
      "36 1.5123637311959328 2.437670913316559 0.620413413038717\n",
      "41 1.5514668006745476 2.6039686964057926 0.5958085451703037\n",
      "46 1.6688006850159558 2.756796053135482 0.6053406392242623\n",
      "51 2.0135369208019926 2.902997336534375 0.6936061895274667\n",
      "56 2.1422705294432887 3.0461953095695335 0.7032610557548324\n",
      "61 2.2891825062886793 3.1783717877656223 0.720237486092828\n",
      "66 2.3805561409678484 3.305579571524835 0.7201630121006946\n",
      "71 2.428355816745725 3.4329484139337785 0.7073674066552892\n",
      "76 2.5356413086431617 3.558475062222762 0.7125640237195596\n",
      "81 2.682272988673655 3.669873368578009 0.7308897935388364\n",
      "86 2.8348947533212074 3.779672772114365 0.7500370863415659\n",
      "91 3.015796748953059 3.888554628876585 0.7755572537306314\n",
      "96 2.976216447967502 3.9912782735625743 0.7456800162698157\n"
     ]
    }
   ],
   "source": [
    "# -*- coding: utf-8 -*-\n",
    "\n",
    "# nearest_neighbors.py\n",
    "\n",
    "import sys\n",
    "sys.path.append(\"../code-python3-ru\")\n",
    "\n",
    "from collections import Counter\n",
    "from lib.linear_algebra import distance\n",
    "from lib.statistics import mean\n",
    "import math, random\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def raw_majority_vote(labels):\n",
    "    votes = Counter(labels)\n",
    "    winner, _ = votes.most_common(1)[0]\n",
    "    return winner\n",
    "\n",
    "def majority_vote(labels):\n",
    "    \"\"\"подразумевает, что метки упорядочены от ближайшей\n",
    "    до самой удаленной\"\"\"\n",
    "    vote_counts = Counter(labels)\n",
    "    winner, winner_count = vote_counts.most_common(1)[0]\n",
    "    num_winners = len([count\n",
    "                       for count in vote_counts.values()\n",
    "                       if count == winner_count])\n",
    "\n",
    "    if num_winners == 1:\n",
    "        return winner                     # единственный победитель, поэтому вернуть его\n",
    "    else:\n",
    "        return majority_vote(labels[:-1]) # попытаться снова без самого дальнего\n",
    "\n",
    "\n",
    "def knn_classify(k, labeled_points, new_point):\n",
    "    \"\"\"каждая маркированная точка должна быть представлена\n",
    "    парой (точка, метка)\"\"\"\n",
    "\n",
    "    # упорядочить маркированные точки от ближайшей до самой удаленной\n",
    "    by_distance = sorted(labeled_points,\n",
    "                         key=lambda point_label: distance(point_label[0], new_point))\n",
    "\n",
    "    # найти метки для k ближайших\n",
    "    k_nearest_labels = [label for _, label in by_distance[:k]]\n",
    "\n",
    "    # и дать им проголосовать\n",
    "    return majority_vote(k_nearest_labels)\n",
    "\n",
    "# города\n",
    "# каждая запись - это ([долгота, широта], предпочтительный язык\n",
    "cities = [(-86.75,33.5666666666667,'Python'),(-88.25,30.6833333333333,'Python'),\n",
    "          (-112.016666666667,33.4333333333333,'Java'),(-110.933333333333,32.1166666666667,'Java'),\n",
    "          (-92.2333333333333,34.7333333333333,'R'),(-121.95,37.7,'R'),\n",
    "          (-118.15,33.8166666666667,'Python'),(-118.233333333333,34.05,'Java'),\n",
    "          (-122.316666666667,37.8166666666667,'R'),(-117.6,34.05,'Python'),\n",
    "          (-116.533333333333,33.8166666666667,'Python'),(-121.5,38.5166666666667,'R'),\n",
    "          (-117.166666666667,32.7333333333333,'R'),(-122.383333333333,37.6166666666667,'R'),\n",
    "          (-121.933333333333,37.3666666666667,'R'),(-122.016666666667,36.9833333333333,'Python'),\n",
    "          (-104.716666666667,38.8166666666667,'Python'),(-104.866666666667,39.75,'Python'),\n",
    "          (-72.65,41.7333333333333,'R'),(-75.6,39.6666666666667,'Python'),\n",
    "          (-77.0333333333333,38.85,'Python'),(-80.2666666666667,25.8,'Java'),\n",
    "          (-81.3833333333333,28.55,'Java'),(-82.5333333333333,27.9666666666667,'Java'),\n",
    "          (-84.4333333333333,33.65,'Python'),(-116.216666666667,43.5666666666667,'Python'),\n",
    "          (-87.75,41.7833333333333,'Java'),(-86.2833333333333,39.7333333333333,'Java'),\n",
    "          (-93.65,41.5333333333333,'Java'),(-97.4166666666667,37.65,'Java'),\n",
    "          (-85.7333333333333,38.1833333333333,'Python'),(-90.25,29.9833333333333,'Java'),\n",
    "          (-70.3166666666667,43.65,'R'),(-76.6666666666667,39.1833333333333,'R'),\n",
    "          (-71.0333333333333,42.3666666666667,'R'),(-72.5333333333333,42.2,'R'),\n",
    "          (-83.0166666666667,42.4166666666667,'Python'),(-84.6,42.7833333333333,'Python'),\n",
    "          (-93.2166666666667,44.8833333333333,'Python'),(-90.0833333333333,32.3166666666667,'Java'),\n",
    "          (-94.5833333333333,39.1166666666667,'Java'),(-90.3833333333333,38.75,'Python'),\n",
    "          (-108.533333333333,45.8,'Python'),(-95.9,41.3,'Python'),\n",
    "          (-115.166666666667,36.0833333333333,'Java'),(-71.4333333333333,42.9333333333333,'R'),\n",
    "          (-74.1666666666667,40.7,'R'),(-106.616666666667,35.05,'Python'),\n",
    "          (-78.7333333333333,42.9333333333333,'R'),(-73.9666666666667,40.7833333333333,'R'),\n",
    "          (-80.9333333333333,35.2166666666667,'Python'),(-78.7833333333333,35.8666666666667,'Python'),\n",
    "          (-100.75,46.7666666666667,'Java'),(-84.5166666666667,39.15,'Java'),\n",
    "          (-81.85,41.4,'Java'),(-82.8833333333333,40,'Java'),\n",
    "          (-97.6,35.4,'Python'),(-122.666666666667,45.5333333333333,'Python'),\n",
    "          (-75.25,39.8833333333333,'Python'),(-80.2166666666667,40.5,'Python'),\n",
    "          (-71.4333333333333,41.7333333333333,'R'),(-81.1166666666667,33.95,'R'),\n",
    "          (-96.7333333333333,43.5666666666667,'Python'),(-90,35.05,'R'),\n",
    "          (-86.6833333333333,36.1166666666667,'R'),(-97.7,30.3,'Python'),\n",
    "          (-96.85,32.85,'Java'),(-95.35,29.9666666666667,'Java'),\n",
    "          (-98.4666666666667,29.5333333333333,'Java'),(-111.966666666667,40.7666666666667,'Python'),\n",
    "          (-73.15,44.4666666666667,'R'),(-77.3333333333333,37.5,'Python'),\n",
    "          (-122.3,47.5333333333333,'Python'),(-89.3333333333333,43.1333333333333,'R'),\n",
    "          (-104.816666666667,41.15,'Java')]\n",
    "\n",
    "cities = [([longitude, latitude], language) for longitude, latitude, language in cities]\n",
    "\n",
    "def plot_state_borders(plt, color='0.8'):\n",
    "    pass\n",
    "\n",
    "def plot_cities():\n",
    "\n",
    "    # ключ = язык, значение = пара (долгота, широта)\n",
    "    plots = { \"Java\" : ([], []), \"Python\" : ([], []), \"R\" : ([], []) }\n",
    "\n",
    "    # каждый язык должен иметь разную метку и цвет\n",
    "    markers = { \"Java\" : \"o\", \"Python\" : \"s\", \"R\" : \"^\" }\n",
    "    colors  = { \"Java\" : \"r\", \"Python\" : \"b\", \"R\" : \"g\" }\n",
    "\n",
    "    for (longitude, latitude), language in cities:\n",
    "        plots[language][0].append(longitude)\n",
    "        plots[language][1].append(latitude)\n",
    "\n",
    "    # создать серии разброса для каждого языка\n",
    "    for language, (x, y) in plots.items():\n",
    "        plt.scatter(x, y, color=colors[language], marker=markers[language],\n",
    "                          label=language, zorder=10)\n",
    "\n",
    "    plot_state_borders(plt)    # отрисовать границы штатов\n",
    "\n",
    "    plt.legend(loc=0)          # пусть matplotlib сама выберет расположение легенды\n",
    "    plt.axis([-130,-60,20,55]) # установить оси\n",
    "    plt.title(\"Предпочитаемые языки программирования\")\n",
    "    plt.show()\n",
    "\n",
    "def classify_and_plot_grid(k=1):\n",
    "    plots = { \"Java\" : ([], []), \"Python\" : ([], []), \"R\" : ([], []) }\n",
    "    markers = { \"Java\" : \"o\", \"Python\" : \"s\", \"R\" : \"^\" }\n",
    "    colors  = { \"Java\" : \"r\", \"Python\" : \"b\", \"R\" : \"g\" }\n",
    "\n",
    "    for longitude in range(-130, -60):\n",
    "        for latitude in range(20, 55):\n",
    "            predicted_language = knn_classify(k, cities, [longitude, latitude])\n",
    "            plots[predicted_language][0].append(longitude)\n",
    "            plots[predicted_language][1].append(latitude)\n",
    "\n",
    "    # создать серии разброса для каждого языка\n",
    "    for language, (x, y) in plots.items():\n",
    "        plt.scatter(x, y, color=colors[language], marker=markers[language],\n",
    "                          label=language, zorder=0)\n",
    "\n",
    "    plot_state_borders(plt, color='black')    # отрисовать границы штатов\n",
    "\n",
    "    plt.legend(loc=0)          # пусть matplotlib сама выберет расположение легенды\n",
    "    plt.axis([-130,-60,20,55]) # установить оси\n",
    "    plt.title(\"Языки программирования на основе \" + str(k) + \"-ближайших соседей\")\n",
    "    plt.show()\n",
    "\n",
    "#\n",
    "# Проблема проклятия размерности\n",
    "#\n",
    "\n",
    "def random_point(dim):\n",
    "    return [random.random() for _ in range(dim)]\n",
    "\n",
    "def random_distances(dim, num_pairs):\n",
    "    return [distance(random_point(dim), random_point(dim))\n",
    "            for _ in range(num_pairs)]\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "\n",
    "    # попробовать несколько разных значений k\n",
    "    for k in [1, 3, 5, 7]:\n",
    "        num_correct = 0\n",
    "\n",
    "        for location, actual_language in cities:\n",
    "\n",
    "            other_cities = [other_city\n",
    "                            for other_city in cities\n",
    "                            if other_city != (location, actual_language)]\n",
    "\n",
    "            predicted_language = knn_classify(k, other_cities, location)\n",
    "\n",
    "            if predicted_language == actual_language:\n",
    "                num_correct += 1\n",
    "\n",
    "        print(k, \"сосед(а,ей):\", num_correct, \"правильных из\", len(cities))\n",
    "\n",
    "    dimensions = range(1, 101, 5)\n",
    "\n",
    "    avg_distances = []\n",
    "    min_distances = []\n",
    "\n",
    "    random.seed(0)\n",
    "    for dim in dimensions:\n",
    "        distances = random_distances(dim, 10000)  # 10000 случайных пар\n",
    "        avg_distances.append(mean(distances))     # отследить средние расстояния\n",
    "        min_distances.append(min(distances))      # отследить минимальные расстояния\n",
    "        print(dim, min(distances), mean(distances), min(distances) / mean(distances))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}