Best suitable approach to find nearest neighbour to (x, y, z) from list of triplets-CodePudding

I am trying to obtain a triplet from list of triplets that is closest to my required triplet incase if it was not found.

For example:

           # V_s,V_g,V_r 
triplets = [(500, 12, 5), 
           (400, 15, 2.5), 
           (400, 15, 3),
           (450, 12, 3),
           ... ,
           (350, 14, 3)]

The triple that I am looking for is

req_triplet = (450, 15, 2)    #(Vreq_s, Vreq_g, Vreq_r)

How can I achieve this in python, a best suitable strategy to achieve is what I am in need for.

As of now I am thinking to filter the list by finding nearest parameter V_s. From the resulting list filter further by finding nearest to V_g and finally by V_r.

CodePudding user response：

You can compute Euclidean distance with numPy or you can use numpy.linalg.norm.

Try this:

>>> import numpy as np
>>> def dist(x,y):   
...    return np.sqrt(np.sum((x-y)**2))

>>> triplets = [(500, 12, 5), (400, 15, 2.5), (400, 15, 3),(450, 12, 3)(350, 14, 3)]
>>> req_triplet = (450, 15, 2)

>>> arr_dst = [np.linalg.norm(np.array(tr) - np.array(req_triplet)) for tr in triplets]
>>> arr_dst = [dist(np.array(tr), np.array(req_triplet)) for tr in triplets]
>>> arr_dst
[50.17967716117751, 50.002499937503124, 50.00999900019995, 3.1622776601683795, 100.00999950005]

>>> idx = np.argmin(arr_dst)
>>> idx
3

>>> triplets[idx]
(450, 12, 3)

CodePudding user response：

You have to define a metric ||.||, then the triplet T that is close to a fixed one F is the one that minimize ||T - F||. You can use a classic Euclidean distance:

import numpy as np
def dist(u, v):   
    return np.sqrt(np.sum((np.array(u)-np.array(v))**2))

CodePudding user response：

The general strategy would be to Loop through the list, for each element calculate the distance and check if it is the minimum, otherwise keep going on.

In python this would look something like this-

from math import abs
triplets = [(500, 12, 5), 
           (400, 15, 2.5), 
           (400, 15, 3),
           (450, 12, 3),
           ... ,
           (350, 14, 3)]
req_triplet = (450, 15, 2)
def calc_dist(a,b):
    return sum((abs(a[i]-b[i]) for i in range(3))
def find_closest_triple(req_triplet,triplets):
    min_ind = None
    min_dist = -1
    for i,triplet in enumerate(triplets):
        if e == req_triplet:
            return i
        dist = calc_dist(req_triplet,triplet)
        if dist < min_dist:
            min_ind = i
    return min_ind