k-NN_k-Nearest Neighbors Classifier_解説.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# k-NN (k-Nearest Neighbors Classifier; k近傍法)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## k近傍法のアルゴリズム"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### イメージによる理解"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "これ以降では下の用語を使います。\n",
    "\n",
    "::::{grid}\n",
    ":gutter: 2\n",
    "\n",
    ":::{grid-item-card} 教師データ\n",
    "既にクラスがわかっているデータ（教師データ、訓練データ、training dataと呼ばれるもの）\n",
    ":::\n",
    "\n",
    ":::{grid-item-card} テストデータ\n",
    "クラスが未知のデータ、クラスを予測したいデータ\n",
    ":::\n",
    "::::\n",
    "\n",
    "教師データとして与えられるデータは、いくつかの特徴を持っているとします。例えばAさんの身体測定のデータを見てみると、Aさんのデータとして身長、体重の数値が与えられています。これが特徴です。特徴は何次元あってもいいですが、ここでは二次元だと考えます。同じように何かしらの二種類の特徴があるデータがあり、いくつかのデータには、既にクラスが割り当てられている状態だとしましょう。ここで未知のデータがどのクラスに割り当てられるのかを予測するのが __クラス分類タスク__ です。\n",
    "\n",
    "クラス分類タスクを解くために、ここではk-nnを利用します。k-nnでは単純に、テストデータの近い位置にあるデータを$k$個集めて、その中の多数決でテストデータのクラスを決定します。\n",
    "\n",
    "![](figs/knn/2.png)\n",
    "\n",
    ":::{margin}\n",
    "近傍とは「近所」や「ある場所から近いところ」のような意味を持ちます。\n",
    "\n",
    "knnでは最も近い位置にあるデータのクラスをテストデータのクラスとして採用します。イメージ画像では、青クラスと赤クラスに属するデータがあり、テストデータ（黒◯）に最も近いのは青クラスに属するデータです。\n",
    "\n",
    ":::\n",
    "\n",
    "::::{tab-set}\n",
    "\n",
    ":::{tab-item} 近傍1つを探索\n",
    "\n",
    "$k=1$の場合を考えてみましょう。これは __最近傍法__ や1-NNとも呼ばれます。最近傍点に従って，テストデータは青クラスだとします。\n",
    "![](figs/knn/3.png)\n",
    "\n",
    ":::\n",
    ":::{tab-item} 近傍3つを探索\n",
    "\n",
    "$k=3$の場合を考えてみましょう。イメージ画像では近傍の3つのデータは、青１個、赤２個なので、多数決でテストデータを赤クラスに割り当てます。\n",
    "\n",
    "![](figs/knn/4.png)\n",
    "\n",
    ":::\n",
    ":::{tab-item} 近傍5つを探索\n",
    "$k=5$の場合を考えてみましょう。イメージ画像では近傍の5つのデータは、青2個、赤3個なので、多数決でテストデータを赤クラスに割り当てます。\n",
    "\n",
    "![](figs/knn/5.png)\n",
    ":::\n",
    "::::\n",
    "\n",
    "上の三つの例では、kの値を変えることでテストデータの割り当てられるクラスが変わってしまいました。このkの値をk-NNの __ハイパーパラメータ（hyper-parameter）__ と呼びます。ハイパーパラメータは機械学習を行う際に、最終的な結果を大きく左右することがある重要な設定値です。kにどの値を使うかは慎重に考えなければなりません。また、実際にはテストデータが複数ある場合が多いので、この作業をテストデータの数だけ繰り返す必要があることに注意してください。\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### コードベースの理解"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "k-nnにおける処理の流れを簡単にPythonっぽくまとめておきます。初期化ステップ→学習ステップ→予測ステップの順に処理が進んで行きます。\n",
    "\n",
    "```{}python\n",
    "class KNN:\n",
    "    def __init__(self, k:int):\n",
    "        \"初期化ステップ\"\n",
    "        self.k = k # kの値を決めておく\n",
    "\n",
    "    def fit(self,X:教師データの二次元配列,y:教師データのクラスの入った一次元配列):\n",
    "        \"学習ステップ\"\n",
    "        self._X = X # 教師データを保存しておく \n",
    "        self._y = y # 教師ラベルを保存しておく\n",
    "\n",
    "    def predict(self, X:テストデータの二次元配列):\n",
    "        \"予測ステップ\"\n",
    "        pred_y = [] # テストデータの予測ラベルを保存するためのリスト\n",
    "        for x in X:\n",
    "            # xはテストデータから取り出した1つのデータ\n",
    "            1. 教師データをxに近い順にソートする。\n",
    "            2. 近い順にk個の教師データを取り出す。\n",
    "            3. k個の教師データの中で最も多いラベルを見つける。\n",
    "            4. これをxのラベルとする。\n",
    "            pred_y.append(xの予測ラベル)\n",
    "        return pred_y\n",
    "\n",
    "    def score(self,X,y):\n",
    "        pred_y = self.predict(X)\n",
    "        yとpred_yを使って正答率を計算\n",
    "        return 正答率\n",
    "        \n",
    "```\n",
    "\n",
    "上に示したコードと日本語が混ざったものは、scikit-learnの実装に似せたメソッドを用意しています。  \n",
    "scikit-learnで実装された機械学習のクラスは以下のように利用します。\n",
    "1. __init__でハイパーパラメータを設定\n",
    "2. fitで教師データを使ってモデルを訓練\n",
    "3. predictでテストデータに対してクラスラベルを予測\n",
    "\n",
    "k-nnではfitメソッドで教師データセットの保存だけを行っており、これを使って、predictで1~4の流れに沿ってクラスラベルの予測を行っています。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scikit-Learnを使った実験"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "では実際に、scikit-learnを使ってk-nnを試してみましょう。あやめの花のデータセットであるiris datasetを使ってクラス分類を行います。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# このノートで使うパッケージをimportしておきます。\n",
    "import numpy as np\n",
    "import pandas as pd \n",
    "import plotly.express as px \n",
    "\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.preprocessing import StandardScaler\n",
    "from sklearn.neighbors import KNeighborsClassifier"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "実験のために、まずは疑似乱数のシードを固定しておきます。このSEEDの値を決めておくことで、再度同様の実験を行なっても同じ答えになるはずです。  \n",
    "また、データセットの読み込みも行います。ここではiris datasetを利用するので、これを読み込んでtrain_test_splitで教師データとテストデータを分割しておきます。test_sizeは全体に対するテストデータの割合を示します。この値は0.3としますが、値が大きいほど難しい課題設定になる傾向があります。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "SEED = 2023_02_01\n",
    "rng = np.random.default_rng(SEED)\n",
    "np.random.seed(SEED)\n",
    "\n",
    "# デモで使うデータセットを読み込んでおきます。\n",
    "iris_dataset = load_iris()\n",
    "\n",
    "# 教師データとテストデータに分割します。\n",
    "X_train, X_test, y_train, y_test = train_test_split(\n",
    "    iris_dataset.data, iris_dataset.target, # 分割したい配列をここに列挙します。今回はデータとラベルです。\n",
    "    test_size=0.3, # データ全体に対するテストデータの割合を指定します。\n",
    "    #stratify=iris_dataset.target, # クラス毎に偏りが出ないような分割をします。\n",
    "    random_state= SEED, # random_state=None\n",
    "    )"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "iris datasetではあまり必要性がないですが、StandardScalerで正規化しておきます。データを平均0、標準偏差1のガウス分布（標準正規分布）に埋め込む作業です。これによって特徴毎に値のスケールが違う場合でも差異を吸収することができます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "# データを標準化しておきます。（このセルを実行しなくても構いません）\n",
    "scaler = StandardScaler()\n",
    "X_train = scaler.fit_transform(X_train)\n",
    "X_test = scaler.transform(X_test)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "モデルの初期化です。KNeighborsClassifierのコンストラクタ（初期化メソッド）では、ここで示した以外にもいくつかのオプションがあります。調べてみると良いでしょう。また、n_jobsは訓練や推論を並列で行うためのオプションです。並列化しないのであれば指定しなくてもいいのですが、指定する場合はn_jobsの値によって答えが変わるような実装になっている場合があることに注意してください。つまりn_jobs=-1の場合、その環境で最も良い値を指定してくれるはずですが、これは環境依存の値なのでSEEDを固定していても値が変わる場合があるのです。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "# モデルの初期化\n",
    "model = KNeighborsClassifier(\n",
    "    n_neighbors=1, # kの値\n",
    "    n_jobs=1, # 並列計算する数、ここでは1にしているが、計算に時間がかかる場合はCPUのコア数を指定するとよい。\n",
    "    )"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "訓練はscikit-learn準拠モデルではfitメソッドが担います。教師データと教師ラベルを受け取って、学習が終わった自分自身を返します（return self）。もちろんmodel自体のパラメータも更新されています。\n",
    "\n",
    "knnではX_trainとy_trainを推論のためにinstance変数に代入するだけの処理をしていると考えてください。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>#sk-container-id-3 {color: black;background-color: white;}#sk-container-id-3 pre{padding: 0;}#sk-container-id-3 div.sk-toggleable {background-color: white;}#sk-container-id-3 label.sk-toggleable__label {cursor: pointer;display: block;width: 100%;margin-bottom: 0;padding: 0.3em;box-sizing: border-box;text-align: center;}#sk-container-id-3 label.sk-toggleable__label-arrow:before {content: \"▸\";float: left;margin-right: 0.25em;color: #696969;}#sk-container-id-3 label.sk-toggleable__label-arrow:hover:before {color: black;}#sk-container-id-3 div.sk-estimator:hover label.sk-toggleable__label-arrow:before {color: black;}#sk-container-id-3 div.sk-toggleable__content {max-height: 0;max-width: 0;overflow: hidden;text-align: left;background-color: #f0f8ff;}#sk-container-id-3 div.sk-toggleable__content pre {margin: 0.2em;color: black;border-radius: 0.25em;background-color: #f0f8ff;}#sk-container-id-3 input.sk-toggleable__control:checked~div.sk-toggleable__content {max-height: 200px;max-width: 100%;overflow: auto;}#sk-container-id-3 input.sk-toggleable__control:checked~label.sk-toggleable__label-arrow:before {content: \"▾\";}#sk-container-id-3 div.sk-estimator input.sk-toggleable__control:checked~label.sk-toggleable__label {background-color: #d4ebff;}#sk-container-id-3 div.sk-label input.sk-toggleable__control:checked~label.sk-toggleable__label {background-color: #d4ebff;}#sk-container-id-3 input.sk-hidden--visually {border: 0;clip: rect(1px 1px 1px 1px);clip: rect(1px, 1px, 1px, 1px);height: 1px;margin: -1px;overflow: hidden;padding: 0;position: absolute;width: 1px;}#sk-container-id-3 div.sk-estimator {font-family: monospace;background-color: #f0f8ff;border: 1px dotted black;border-radius: 0.25em;box-sizing: border-box;margin-bottom: 0.5em;}#sk-container-id-3 div.sk-estimator:hover {background-color: #d4ebff;}#sk-container-id-3 div.sk-parallel-item::after {content: \"\";width: 100%;border-bottom: 1px solid gray;flex-grow: 1;}#sk-container-id-3 div.sk-label:hover label.sk-toggleable__label {background-color: #d4ebff;}#sk-container-id-3 div.sk-serial::before {content: \"\";position: absolute;border-left: 1px solid gray;box-sizing: border-box;top: 0;bottom: 0;left: 50%;z-index: 0;}#sk-container-id-3 div.sk-serial {display: flex;flex-direction: column;align-items: center;background-color: white;padding-right: 0.2em;padding-left: 0.2em;position: relative;}#sk-container-id-3 div.sk-item {position: relative;z-index: 1;}#sk-container-id-3 div.sk-parallel {display: flex;align-items: stretch;justify-content: center;background-color: white;position: relative;}#sk-container-id-3 div.sk-item::before, #sk-container-id-3 div.sk-parallel-item::before {content: \"\";position: absolute;border-left: 1px solid gray;box-sizing: border-box;top: 0;bottom: 0;left: 50%;z-index: -1;}#sk-container-id-3 div.sk-parallel-item {display: flex;flex-direction: column;z-index: 1;position: relative;background-color: white;}#sk-container-id-3 div.sk-parallel-item:first-child::after {align-self: flex-end;width: 50%;}#sk-container-id-3 div.sk-parallel-item:last-child::after {align-self: flex-start;width: 50%;}#sk-container-id-3 div.sk-parallel-item:only-child::after {width: 0;}#sk-container-id-3 div.sk-dashed-wrapped {border: 1px dashed gray;margin: 0 0.4em 0.5em 0.4em;box-sizing: border-box;padding-bottom: 0.4em;background-color: white;}#sk-container-id-3 div.sk-label label {font-family: monospace;font-weight: bold;display: inline-block;line-height: 1.2em;}#sk-container-id-3 div.sk-label-container {text-align: center;}#sk-container-id-3 div.sk-container {/* jupyter's `normalize.less` sets `[hidden] { display: none; }` but bootstrap.min.css set `[hidden] { display: none !important; }` so we also need the `!important` here to be able to override the default hidden behavior on the sphinx rendered scikit-learn.org. See: https://github.com/scikit-learn/scikit-learn/issues/21755 */display: inline-block !important;position: relative;}#sk-container-id-3 div.sk-text-repr-fallback {display: none;}</style><div id=\"sk-container-id-3\" class=\"sk-top-container\"><div class=\"sk-text-repr-fallback\"><pre>KNeighborsClassifier(n_jobs=1, n_neighbors=1)</pre><b>In a Jupyter environment, please rerun this cell to show the HTML representation or trust the notebook. <br />On GitHub, the HTML representation is unable to render, please try loading this page with nbviewer.org.</b></div><div class=\"sk-container\" hidden><div class=\"sk-item\"><div class=\"sk-estimator sk-toggleable\"><input class=\"sk-toggleable__control sk-hidden--visually\" id=\"sk-estimator-id-3\" type=\"checkbox\" checked><label for=\"sk-estimator-id-3\" class=\"sk-toggleable__label sk-toggleable__label-arrow\">KNeighborsClassifier</label><div class=\"sk-toggleable__content\"><pre>KNeighborsClassifier(n_jobs=1, n_neighbors=1)</pre></div></div></div></div></div>"
      ],
      "text/plain": [
       "KNeighborsClassifier(n_jobs=1, n_neighbors=1)"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# モデルの訓練\n",
    "model.fit(X_train,y_train)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "推論はscikit-learn準拠モデルではpredictメソッドが担います。データのみを受け取って、予測したラベルを返します。ここではテストデータを渡しましたが、訓練データを渡しても同じようにラベルを返します。ただし、通常は汎化誤差を確認したいはずなので、テストデータに対する予測値を見ることが多いと思います。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 0, 0, 2, 1, 2, 0, 1, 0, 2, 2, 2, 1, 2, 2, 0, 0, 0, 0, 1, 0, 1,\n",
       "       1, 2, 2, 1, 2, 2, 2, 1, 1, 2, 0, 2, 2, 1, 1, 0, 2, 2, 2, 1, 0, 0,\n",
       "       0])"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 訓練済みモデルを使ったTest dataのクラス予測\n",
    "model.predict(X_test)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "KNeighborsClassifierのようなクラス分類のためのクラスであれば、正答率を返すようにscoreメソッドが実装されています。これを使ってtraining data accuracyとtest data accuracyを確認しましょう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "教師データの正答率: 1.0\n",
      "テストデータの正答率: 0.9111111111111111\n"
     ]
    }
   ],
   "source": [
    "# 正答率の算出\n",
    "train_acc = model.score(X_train,y_train)\n",
    "test_acc = model.score(X_test,y_test)\n",
    "\n",
    "print(\"教師データの正答率:\", train_acc)\n",
    "print(\"テストデータの正答率:\", test_acc)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "iris datasetは非常にクラス分類しやすいデータです。正答率が高めになっているのもそのためでしょう。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "テストデータの正答率は1に近いほど良いので、kがどの値の時に良い正答率が得られるのかを確認してみましょう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.plotly.v1+json": {
       "config": {
        "plotlyServerURL": "https://plot.ly"
       },
       "data": [
        {
         "hovertemplate": "k=%{x}<br>acc=%{y}<extra></extra>",
         "legendgroup": "",
         "line": {
          "color": "#636efa",
          "dash": "solid"
         },
         "marker": {
          "symbol": "circle"
         },
         "mode": "lines",
         "name": "",
         "orientation": "v",
         "showlegend": false,
         "type": "scatter",
         "x": [
          1,
          2,
          3,
          4,
          5,
          6,
          7,
          8,
          9,
          10,
          11,
          12,
          13,
          14,
          15,
          16,
          17,
          18,
          19,
          20,
          21,
          22,
          23,
          24,
          25,
          26,
          27,
          28,
          29,
          30,
          31,
          32,
          33,
          34,
          35,
          36,
          37,
          38,
          39,
          40,
          41,
          42,
          43,
          44,
          45,
          46,
          47,
          48,
          49,
          50
         ],
         "xaxis": "x",
         "y": [
          0.9622507122507122,
          0.9426638176638178,
          0.9715099715099715,
          0.9426638176638178,
          0.9426638176638178,
          0.9522792022792024,
          0.9811253561253561,
          0.9715099715099715,
          0.9715099715099715,
          0.961894586894587,
          0.9715099715099715,
          0.961894586894587,
          0.9426638176638178,
          0.9430199430199431,
          0.9430199430199431,
          0.9430199430199431,
          0.9426638176638178,
          0.9334045584045585,
          0.9237891737891739,
          0.9141737891737892,
          0.9141737891737892,
          0.9141737891737892,
          0.9141737891737892,
          0.9045584045584046,
          0.9141737891737892,
          0.9045584045584046,
          0.89494301994302,
          0.89494301994302,
          0.89494301994302,
          0.9045584045584046,
          0.9045584045584046,
          0.9045584045584046,
          0.8757122507122508,
          0.8853276353276354,
          0.8853276353276354,
          0.9045584045584045,
          0.89494301994302,
          0.7987891737891738,
          0.8084045584045585,
          0.7799145299145299,
          0.7606837606837606,
          0.7799145299145299,
          0.7702991452991452,
          0.7610398860398861,
          0.7610398860398861,
          0.7432336182336182,
          0.7336182336182335,
          0.7339743589743589,
          0.7435897435897435,
          0.7150997150997151
         ],
         "yaxis": "y"
        }
       ],
       "layout": {
        "height": 400,
        "legend": {
         "tracegroupgap": 0
        },
        "template": {
         "data": {
          "bar": [
           {
            "error_x": {
             "color": "#2a3f5f"
            },
            "error_y": {
             "color": "#2a3f5f"
            },
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "bar"
           }
          ],
          "barpolar": [
           {
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "barpolar"
           }
          ],
          "carpet": [
           {
            "aaxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "baxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "type": "carpet"
           }
          ],
          "choropleth": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "choropleth"
           }
          ],
          "contour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "contour"
           }
          ],
          "contourcarpet": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "contourcarpet"
           }
          ],
          "heatmap": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmap"
           }
          ],
          "heatmapgl": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmapgl"
           }
          ],
          "histogram": [
           {
            "marker": {
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "histogram"
           }
          ],
          "histogram2d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2d"
           }
          ],
          "histogram2dcontour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2dcontour"
           }
          ],
          "mesh3d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "mesh3d"
           }
          ],
          "parcoords": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "parcoords"
           }
          ],
          "pie": [
           {
            "automargin": true,
            "type": "pie"
           }
          ],
          "scatter": [
           {
            "fillpattern": {
             "fillmode": "overlay",
             "size": 10,
             "solidity": 0.2
            },
            "type": "scatter"
           }
          ],
          "scatter3d": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatter3d"
           }
          ],
          "scattercarpet": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattercarpet"
           }
          ],
          "scattergeo": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergeo"
           }
          ],
          "scattergl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergl"
           }
          ],
          "scattermapbox": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattermapbox"
           }
          ],
          "scatterpolar": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolar"
           }
          ],
          "scatterpolargl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolargl"
           }
          ],
          "scatterternary": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterternary"
           }
          ],
          "surface": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "surface"
           }
          ],
          "table": [
           {
            "cells": {
             "fill": {
              "color": "#EBF0F8"
             },
             "line": {
              "color": "white"
             }
            },
            "header": {
             "fill": {
              "color": "#C8D4E3"
             },
             "line": {
              "color": "white"
             }
            },
            "type": "table"
           }
          ]
         },
         "layout": {
          "annotationdefaults": {
           "arrowcolor": "#2a3f5f",
           "arrowhead": 0,
           "arrowwidth": 1
          },
          "autotypenumbers": "strict",
          "coloraxis": {
           "colorbar": {
            "outlinewidth": 0,
            "ticks": ""
           }
          },
          "colorscale": {
           "diverging": [
            [
             0,
             "#8e0152"
            ],
            [
             0.1,
             "#c51b7d"
            ],
            [
             0.2,
             "#de77ae"
            ],
            [
             0.3,
             "#f1b6da"
            ],
            [
             0.4,
             "#fde0ef"
            ],
            [
             0.5,
             "#f7f7f7"
            ],
            [
             0.6,
             "#e6f5d0"
            ],
            [
             0.7,
             "#b8e186"
            ],
            [
             0.8,
             "#7fbc41"
            ],
            [
             0.9,
             "#4d9221"
            ],
            [
             1,
             "#276419"
            ]
           ],
           "sequential": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ],
           "sequentialminus": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ]
          },
          "colorway": [
           "#636efa",
           "#EF553B",
           "#00cc96",
           "#ab63fa",
           "#FFA15A",
           "#19d3f3",
           "#FF6692",
           "#B6E880",
           "#FF97FF",
           "#FECB52"
          ],
          "font": {
           "color": "#2a3f5f"
          },
          "geo": {
           "bgcolor": "white",
           "lakecolor": "white",
           "landcolor": "#E5ECF6",
           "showlakes": true,
           "showland": true,
           "subunitcolor": "white"
          },
          "hoverlabel": {
           "align": "left"
          },
          "hovermode": "closest",
          "mapbox": {
           "style": "light"
          },
          "paper_bgcolor": "white",
          "plot_bgcolor": "#E5ECF6",
          "polar": {
           "angularaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "radialaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "scene": {
           "xaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "yaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "zaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           }
          },
          "shapedefaults": {
           "line": {
            "color": "#2a3f5f"
           }
          },
          "ternary": {
           "aaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "baxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "caxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "title": {
           "x": 0.05
          },
          "xaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          },
          "yaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          }
         }
        },
        "title": {
         "text": "kとacc（正答率）との関係"
        },
        "width": 400,
        "xaxis": {
         "anchor": "y",
         "domain": [
          0,
          1
         ],
         "title": {
          "text": "k"
         }
        },
        "yaxis": {
         "anchor": "x",
         "domain": [
          0,
          1
         ],
         "title": {
          "text": "acc"
         }
        }
       }
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def get_fold(X_train,y_train,n_fold=5, seed=None):\n",
    "    index = np.arange(len(y_train))\n",
    "    if seed is not None:\n",
    "        np.random.seed(seed)\n",
    "    np.random.shuffle(index)\n",
    "    folds = np.array_split(index,n_fold)\n",
    "    for ix in range(n_fold):\n",
    "        fold = folds[ix]\n",
    "        other = np.hstack([folds[j] for j in range(n_fold) if j != ix])\n",
    "        yield {\n",
    "            \"X_val\":X_train[fold],\n",
    "            \"y_val\":y_train[fold],\n",
    "            \"X_train\":X_train[other],\n",
    "            \"y_train\":y_train[other],\n",
    "            }\n",
    "\n",
    "def grid_search(X_train, y_train, test_size=0.3, k=50, n_fold=4, seed=None):\n",
    "    seed = seed if seed is not None else np.random.randint(2**20)\n",
    "    val_acc_list = []\n",
    "    for _k in range(1,k+1):\n",
    "        tmp = []\n",
    "        for data in get_fold(X_train,y_train,n_fold,seed):\n",
    "            knn = KNeighborsClassifier(n_neighbors=_k).fit(data[\"X_train\"],data[\"y_train\"])\n",
    "            val_acc = knn.score(data[\"X_val\"], data[\"y_val\"])\n",
    "            tmp.append(val_acc)\n",
    "        val_acc_list.append(np.mean(tmp))\n",
    "\n",
    "    df = pd.DataFrame()\n",
    "    df[\"k\"] = list(range(1,k+1))\n",
    "    df[\"acc\"] = val_acc_list\n",
    "    \n",
    "\n",
    "    \"\"\"\n",
    "    fig = plt.figure()\n",
    "    ax = fig.add_subplot(111)\n",
    "    ax.plot(df[\"k\"], df[\"acc\"])\n",
    "    ax.set_xlabel('$k$ (n_components)')\n",
    "    ax.set_ylabel('Accuracy')\n",
    "    ax.set_title(\"Elbow plot\")\n",
    "    \"\"\"\n",
    "    return df\n",
    "\n",
    "result_df = grid_search(X_train,y_train,seed=SEED)\n",
    "\n",
    "fig = px.line(\n",
    "        result_df, \n",
    "        x=\"k\", y=\"acc\",\n",
    "        height=400, width=400,\n",
    "        title=\"kとacc（正答率）との関係\")\n",
    "\n",
    "fig.show()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "kとaccの関係を示す上のプロットから、適切なkの値を見ることができます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "k      7.000000\n",
       "acc    0.981125\n",
       "Name: 6, dtype: float64"
      ]
     },
     "execution_count": 115,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_k = int(result_df.iloc[result_df[\"acc\"].argmax()][\"k\"])\n",
    "result_df.iloc[result_df[\"acc\"].argmax()]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最後に、適切なkの値を使ってtest accuracyを求めておきます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9555555555555556"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knn = KNeighborsClassifier(n_neighbors=best_k).fit(X_train,y_train)\n",
    "knn.score(X_test,y_test)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "datasci",
   "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.10.6"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "a79fb6e5a930026e4265f7488905aff41e03ef0de0bdcf381b857b9bad06edd5"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}