ユークリッド空間内の複数の点の中から、最も近い点を探す短いコード

実務上次の問題を解く必要が発生し、短くて効率のいい書き方を探したのでそのメモです。

n次元ユークリッド空間内に、m個の点が存在し、その座標がm*n行列で与えられる。
新たに1つの点の座標がn次元ベクトルで与えられた時、m個の点のうち最も近い点のインデックスを求める。

結論から言うと次のコードで求まります。
最後の行が今回作成したコードです。(それ以外はサンプルの点を作成しています。)
ここでは、 n=10, m=5です。


import numpy as np
# m個の点の座標を生成
X = (np.random.randn(5, 10) * 20).round(2)
print(X)
"""
[[-25.3   -3.49 -21.3   -1.98  10.99   2.77  -8.37  -9.01  20.05   7.91]
 [ 16.33  -9.    16.55 -10.27   6.56   7.81  16.03 -14.13  10.58 -32.39]
 [ 12.01 -11.79  34.79  -2.94 -12.24   0.71 -35.01 -17.92  20.6   33.73]
 [-11.47  30.95   4.92 -19.94  34.81   2.54 -11.73  21.91  24.16   4.87]
 [ 38.32  22.13  11.5   18.82  -8.29   4.02 -17.15  -5.26 -35.62 -19.43]]
"""
# 新しい点の座標
y = (np.random.randn(10) * 20).round(2)
print(y)
"""
[-23.09 -57.02  28.07  39.45 -22.52  -5.91   9.58  30.66 -11.82  21.5 ]
"""
# 最も近い点のインデックス
print(((X-y)**2).sum(axis=1).argmin())
"""
2
"""

今回は最も近い点を探せればよく、具体的な距離は必要としないので、
ユークリッド距離の定義にある平方根の計算は省略しました。

各点との距離のリストが必要な場合は次のコードで求めることができます。
((X-y)**2).sum(axis=1)**0.5
もしくは線形代数モジュールを使い次のように計算することもできます。
np.linalg.norm(X-y, axis=1)

掲題の問いについても、次のようにかけるのですが、
不要な平方根の計算が入るせいか少しだけ遅かったので、最初の書き方を採用しています。
np.linalg.norm(X-y, axis=1).argmin()

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です