Wednesday, December 27, 2017

Use K-D Tree to query points - Part 1

We have a group of 2D points, for example, group A, contains 50 data points. We have another point B (or another group of points), that we want to find n points in A that are closest to the point in B. How do we do that? The simplest thinking is that, we can calculate the distances of all the points from A to B and decide which are the closest n points.
But wait a minute, this sounds we need to do a lot of work. For example, if we want to find the 1 closest countries from US, do we need to calculate all the countries in the southern hemisphere? Are there any good ways that we don’t need to calculate all the distances? Yes, there is a way! This is what I want to show this week - K-D tree. I won’t go into details of this algorithm, if you are interested, you can find the intuition here.
I will use a python example to show how easy to use K-D tree to do the job. You can find the code on Qingkai's Github. But you will notice that the distance here is just Euclidean distance, what if we want to use the distance on earth? We will show that in part 2 in the next post. 
from scipy import spatial
import numpy as np
import matplotlib.pyplot as plt

%matplotlib inline

plt.style.use('seaborn-poster')
Let’s first generate 50 x and y points in group A and for simplicity, generate one point in group B. We will calculate the 3 closest data points from A to B.
np.random.seed(100)
A = np.random.random((50,2))*100

B = [50, 50]
We first build the K-D tree using the function in scipy. And query the 3 closest points to B. Note that, the distance here is the Euclid distance.
# we use cKDTree instead of KDTree, since it is a C version, will be faster. 
kdtree = spatial.cKDTree(A)

# it returns the distance and the index of the points, 3 means we want the top 3 cloest points
dist, ix = kdtree.query(B, 3)
plt.plot(A[:, 0], A[:, 1], 'o', label = 'Point in A')
plt.plot(B[0], B[1], 'r*', markersize = 30, label = 'Point B')
plt.plot(A[:, 0][ix], A[:, 1][ix], 'ro', label = '3 cloest Points')
plt.legend(numpoints = 1)
plt.show()
png

Find all points within certain distance

We can also ask the question: ‘what are the points within distance 20 from B’. Here is how we do it:
# let's find all the points within distance 20 from point B
ix_list = kdtree.query_ball_point(B, 20)
plt.plot(A[:, 0], A[:, 1], 'o', label = 'Point in A')
plt.plot(B[0], B[1], 'r*', markersize = 30, label = 'Point B')
plt.plot(A[:, 0][ix_list], A[:, 1][ix_list], 'ro', label = 'Points within 20')
plt.legend(numpoints = 1)
plt.show()
png

Find all pairs within certain distance

If you have another group of points, you can find all the points in one group within distance 10 from another group. I will just use group A to itself, basically, we will find all the pairs of data points that has distance within 10. You can see that for each point, itself is included in the returned index, because the distance is 0.
kdtree.query_ball_tree(kdtree, 10)
[[0, 45],
 [1, 10],
 [2],
 [3],
 [4, 22],
 [5, 8, 9],
 [6],
 [7, 36],
 [5, 8, 23],
 [5, 9, 11, 23],
 [1, 10],
 [9, 11, 23, 38],
 [12, 16, 46],
 [13],
 [14],
 [15],
 [12, 16, 39, 46],
 [17],
 [18],
 [19, 37],
 [20],
 [21, 40],
 [4, 22],
 [8, 9, 11, 23, 38],
 [24],
 [25, 32],
 [26, 30, 44],
 [27, 42],
 [28, 35],
 [29, 39],
 [26, 30, 44],
 [31],
 [25, 32],
 [33],
 [34, 35],
 [28, 34, 35],
 [7, 36],
 [19, 37],
 [11, 23, 38],
 [16, 29, 39],
 [21, 40],
 [41],
 [27, 42],
 [43],
 [26, 30, 44, 48],
 [0, 45],
 [12, 16, 46],
 [47],
 [44, 48, 49],
 [48, 49]]

5 comments:

  1. I absolutely concur with creator sentiment about this subject and I believe that it would be extremely intriguing to makeJogos online
    friv free Games
    play Games friv 2020

    ReplyDelete
  2. Am here to testify what this great spell caster done for me. i never believe in spell casting, until when i was was tempted to try it. i and my wife have been having a lot of problem living together, she will always not make me happy because she have fallen in love with another man outside our relationship, i tried my best to make sure that my wife leave this woman but the more i talk to her the more she makes me fell sad, so my marriage is now leading to divorce because she no longer gives me attention. so with all this pain and agony, i decided to contact this spell caster to see if things can work out between me and my wife again. this spell caster who was a man told me that my wife is really under a great spell that she have been charm by some magic, so he told me that he was going to make all things normal back. he did the spell on my wife and after 5 days my wife changed completely she even apologize with the way she treated me that she was not her self, i really thank this man his name is Dr ose he have bring back my wife back to me i want you all to contact him who are having any problem related to marriage issue and relationship problem he will solve it for you. his email is oseremenspelltemple@gmail.com he is a man and his great. wish you good time.
    He cast spells for different purposes like
    (1) If you want your ex back.
    (2) if you always have bad dream
    (3) You want to be promoted in your office.
    (4) You want women/men to run after you.
    (5) If you want a child.
    (6) You want to be rich.
    (7) You want to tie your husband/wife to be yours forever.
    (8) If you need financial assistance.
    (9) HIV/AIDS CURE
    (10) is the only answer to that your problem of winning the lottery

    Contact him today on oseremenspelltemple@gmail.com or whatsapp him on +2348136482342

    ReplyDelete
  3. Five weeks ago my boyfriend broke up with me. It all started when i went to summer camp i was trying to contact him but it was not going through. So when I came back from camp I saw him with a young lady kissing in his bed room, I was frustrated and it gave me a sleepless night. I thought he will come back to apologies but he didn't come for almost three week i was really hurt but i thank Dr.Azuka for all he did i met Dr.Azuka during my search at the internet i decided to contact him on his email dr.azukasolutionhome@gmail.com he brought my boyfriend back to me just within 48 hours i am really happy. What’s app contact : +44 7520 636249‬

    ReplyDelete
  4. This post is very simple to read and appreciate without leaving any details out. Great work! hosted call center solutions

    ReplyDelete