k近傍アルゴリズムを書いてみる

https://ja.wikipedia.org/wiki/K%E8%BF%91%E5%82%8D%E6%B3%95#:~:text=k%E8%BF%91%E5%82%8D%E6%B3%95%EF%BC%88%E3%82%B1%E3%82%A4%E3%81%8D%E3%82%93,%E5%AD%A6%E7%BF%92%20%E3%81%AE%E4%B8%80%E7%A8%AE%E3%81%A7%E3%81%82%E3%82%8B%E3%80%82

特徴空間における最も近い訓練例に基づいた分類の手法であり、パターン認識でよく使われる。最近傍探索問題の一つ。 k近傍法は、インスタンスに基づく学習の一種であり、怠惰学習の一種である。

つまり、ある点から見た時にそこから近にいる点を順番にk個選び出すという事か。

import numpy as np

k = 2  # 最も近いポイント2つを選び出す

a = np.array([0,0])
points = [
   np.array([1,1]),
   np.array([1,2]),
   np.array([0,-1]),
   np.array([10,-11]),
]

nearest_list = []
neighbor = None

for p in points:
    # 距離を測る(ここではユークリッド距離を使用)
    distance = np.linalg.norm(a - p)
    if neighbor is None or distance < neighbor:
        neighbor = distance
        if len(nearest_list) > k:
           del nearest_list[k-1:]
        nearest_list.append(
          {
            "point": p,
            "distance": distance,
          }
        )
        nearest_list.sort(key=lambda x: x["distance"])
return nearest_list

この近くにいるk個のデータを最終的に加工し¹、目的に合う数値を得る。

例えば平均を算出する。