重複がないような最近傍の探索

Question

targetの中から、dataの各点の最近傍点を重複なく算出したいのですが、scikitlearnの関数をそのまま使うと、重複が発生します。
重複なく算出する方法はないでしょうか。

import numpy as np
from scipy.spatial import KDTree

target        = np.array([[1,1],[2,2],[3,3]])
data          = np.array([[1.1,1.1],[1.4,1.4],[2.9,2.9]])
kdtree        = KDTree(target)
neighbor_idx  = kdtree.query(data)[1]
print(neighbor_idx)

Comments

[ppaul]

何が重複しているのでしょうか？

Answer 1

重複なくというのをどういったルールで取得するかによりますが
とりあえず見つかったものを除外しながらループ処理していけばできます。
当然、最近傍点が複数存在する場合、target, dataの各点の並び順などにより結果が異なりえます。

import numpy as np
from scipy.spatial import KDTree

target        = np.array([[1,1],[2,2],[3,3]])
data          = np.array([[1.1,1.1],[1.4,1.4],[2.9,2.9]])

ret = []
for d in data:
    kdtree = KDTree(target)
    idx = kdtree.query(d)[1]
    ret.append((d,target[idx]))
    target = np.delete(target, idx, 0)

print(ret) # [(array([1.1, 1.1]), array([1, 1])), (array([1.4, 1.4]), array([2, 2])), (array([2.9, 2.9]), array([3, 3]))]

なお、上記の方法だと、データによっては直観に反した（不自然な）採り方をすることがありえます。

以下のように、複数のdataとtargetの中から最も距離の小さい最近傍点のペアを取り除きつつループしたほうがより自然になるかと思います。

import numpy as np
from scipy.spatial import KDTree

target        = np.array([[1,1],[2,2],[3,3]])
data          = np.array([[1.1,1.1],[1.4,1.4],[2.9,2.9]])

ret = []
while target.shape[0] > 0 and data.shape[0] > 0:
    kdtree = KDTree(target)
    dis, ids = kdtree.query(data)
    dat_i = dis.argmin() # 最も距離の近いペアの位置
    tar_i = ids[dat_i]
    ret.append((data[dat_i], target[tar_i]))
    data = np.delete(data, dat_i, 0)
    target = np.delete(target, tar_i, 0)

print(ret) # [(array([1.1, 1.1]), array([1, 1])), (array([2.9, 2.9]), array([3, 3])), (array([1.4, 1.4]), array([2, 2]))]