Pythonで近傍探索した順位を求める方法

複数のデータ点があり、そのコサイン類似度での順位を求めるとします。

python
1# create dataset
2import numpy as np
3d = 3              # dimension
4n = 10             # number of fields
5np.random.seed(0)  # make reproducible
6
7X = np.random.random((n, d)).astype('float32')
8X[:, 0] += np.arange(n) / 1000.
9
10# contents of X
11array([[0.5488135 , 0.71518934, 0.60276335],
12       [0.5458832 , 0.4236548 , 0.6458941 ],
13       [0.4395872 , 0.891773  , 0.96366274],
14       [0.3864415 , 0.79172504, 0.5288949 ],
15       [0.57204455, 0.92559665, 0.07103606],
16       [0.09212931, 0.0202184 , 0.83261985],
17       [0.78415674, 0.87001216, 0.9786183 ],
18       [0.8061586 , 0.46147937, 0.7805292 ],
19       [0.12627442, 0.639921  , 0.14335328],
20       [0.9536689 , 0.5218483 , 0.41466194]], dtype=float32)
21

このとき、scikit-learnのNearest Neighborを使えば、それぞれのデータに近いデータを求めることができるということがわかりました。

python
1from sklearn.neighbors import NearestNeighbors
2# compute nearest neighbors
3distance, indices = NearestNeighbors(n_neighbors=4, metric='cosine').fit(X).kneighbors(X)
4
5# contents of indices
6array([[0, 6, 3, 2],  # 0番目のデータは6番目のデータに一番近く、次いで3, 2番目のデータに近い
7       [1, 7, 6, 0],  # 以下同様
8       [2, 6, 3, 0],
9       [3, 0, 2, 6],
10       [4, 8, 3, 0],
11       [5, 1, 2, 7],
12       [6, 0, 1, 2],
13       [7, 1, 6, 0],
14       [8, 4, 3, 0],
15       [9, 7, 1, 0]])

このとき、逆に6番目のデータは0番目のデータから見て、何番目に近いのかというデータが欲しくなりました。
このような何番目に近いかということを求めるためのアルゴリズムは既に実装されていたりするのでしょうか。

されていなかった場合、それを現実の時間で計算することは可能なのでしょうか。
なお、データ数は最大で500万くらいあり、次元数は100次元くらいを想定しております。

行動規範の内容に同意します

回答1件

ベストアンサー

このとき、逆に6番目のデータは0番目のデータから見て、何番目に近いのかというデータが欲しくなりました。
このような何番目に近いかということを求めるためのアルゴリズムは既に実装されていたりするのでしょうか。

NearestNeighbors にはそのような機能はないと思います。
k近傍探索では、推論時に与えられた点に近い上位 k 個の点を探す必要があります。
素朴に実装すると、全部の点との距離を計算し、ソートして、距離が近い上位 k 個の点を返せばよいのですが、これだとサンプル数が多くなると、計算に時間がかかってしまいます。
そのため、NearestNeighbors では、点の座標を元に kd木または Ball木というデータ構造に格納することで、k 近傍点を探すときに、与えられた点の近くの点に絞って距離計算を行うことで、計算量を削減しています。

そのため、逆にある点は別の点から見て何番目に近いのか知るということはできないです。