k近傍法（K-Nearest Neighbor）の理論

AI技術講座

2024.05.19

こんにちは，デイビッドです．今回は，
パターン認識＞k近傍法（K Nearest Neighbor）についてです．

全体に戻る場合はこちら↓

深層学習の理論学習の全体像

こんにちは，デイビッドです．近頃，JDLAのE資格を取得したこともあり，せっかくなので，学びを残していこうと思います．この記事では，「機械学習・深層学習の理論学習の全体像について」（学習が渋滞している）．です．日頃より知識や概念の理...

Contents

1 k近傍法（K Nearest Neighbor）
2 距離の測定
3 アルゴリズム
- 3.1 メリット
- 3.2 デメリット
4 適用例
5 まとめ

k近傍法（K Nearest Neighbor）

k近傍法（k-nearest neighbors, k-NN）は，パターン認識，データマイニング，機械学習で広く使われるシンプルかつ効果的なアルゴリズム．

未知のデータポイントのクラスを決定するために，最も近いk個の既知のデータポイントを考慮する非パラメトリック手法．
クラスラベルを持つ訓練データセットが与えられたとき，新しいデータポイントのクラスは，その周囲のk個の最も近い訓練データポイントのクラスによって決定

距離の測定

基本的にはユークリッド距離が用いられるが，他の距離尺度を用いることも可能．

アルゴリズム

新しいデータ点を取得
すべての訓練データポイントとの距離を計算
最も近いk個の訓練データポイントを見つける
これらk個のポイントのクラスラベルの多数決によって，新しいデータ点のクラスを決定

メリット

シンプルで直感的: 理解しやすく、実装も簡単
非パラメトリック: モデルが特定の仮定に依存しないため、柔軟性あり
適応性: 様々な問題に適用可能です（分類、回帰、異常検知など）

デメリット

計算量: 大量のデータセットに対して計算コストが高くなりがちです。
メモリ使用量: すべての訓練データを保持する必要があるため、メモリの使用量が多くなります。
次元の呪い: 高次元データに対しては、距離計算が効率的でなくなることがあります。

次元の呪い（The Curse of Dimensionality）とは？

データの次元（特徴量の数）が増えると、データ分析や機械学習における計算やモデルの性能が難しくなる現象

1. 高次元空間の希薄性:　次元が増えると、データポイントが空間全体に分散し、近くのポイントがほとんど存在しなくなる。

2. 距離の測定:　高次元では、ユークリッド距離などの距離尺度が有効に機能しなくなり、全てのデータポイント間の距離がほぼ同じになることがある。

3. 訓練データの必要量:　次元が増えると、モデルの性能を保つために必要なデータポイントの数が指数関数的に増加する。

4. モデルの過適合（オーバーフィッティング）:　高次元データでは、モデルが訓練データのノイズまで学習し、新しいデータに対して一般化能力が低下する。

5. 解決方法:
次元削減（例: PCA, t-SNE）
特徴選択（例: フィルターメソッド、ラッパーメソッド）
正則化（例: L1正則化、L2正則化）

これらの手法を用いることで、次元の呪いに対処し、高次元データの問題を緩和することができます。

適用例

画像認識: 画像のピクセル値を特徴として使用し、k近傍法で画像分類を行うことができます。
推薦システム: ユーザーの過去の行動や好みに基づいて、似たユーザーのアイテムを推薦します。
異常検知: 正常なデータポイントからの距離が大きいデータポイントを異常として検知します。

以下は画像認識の適用例．以下のような画像を識別するのに利用．

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, classification_report, confusion_matrix

# MNISTデータセットのロード
from tensorflow.keras.datasets import mnist

# データセットのロード
(x_train, y_train), (x_test, y_test) = mnist.load_data()

# データを平坦化（1次元に変換）
x_train_flat = x_train.reshape(x_train.shape[0], -1)
x_test_flat = x_test.reshape(x_test.shape[0], -1)

# k-NNモデルの作成とトレーニング
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(x_train_flat, y_train)

# テストデータを用いて予測
y_pred = knn.predict(x_test_flat)

# 精度の評価
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy * 100:.2f}%")

# 詳細な分類レポート
print(classification_report(y_test, y_pred))

# 混同行列
conf_matrix = confusion_matrix(y_test, y_pred)
print("Confusion Matrix:")
print(conf_matrix)

# 予測結果の可視化
def plot_sample(x, y, y_pred, index):
    plt.imshow(x[index], cmap='gray')
    plt.title(f"True: {y[index]}, Pred: {y_pred[index]}")
    plt.axis('off')
    plt.show()

# 任意のサンプルを表示
sample_index = 0
plot_sample(x_test, y_test, y_pred, sample_index)