0
$\begingroup$

Let $x \in \mathbb{R}^p$ denote a $p$-dimensional data point (a vector). I have two sets $A = \{x_1, \dots, x_n\}$ and $B = \{x_{n+1}, \dots, x_{n+m}\}$, so $|A| = n$, and $|B| = m$. Given $k \in \mathbb{N^*}$, let $d_x^{(A, k)}$ denote the mean Euclidean distance from $x$ to its $k$ nearest points in $A$; and $d_x^{(B, k)}$ denote the mean Euclidean distance from $x$ to its $k$ nearest points in $B$.

I have the following algorithm:

  • $A' = \{ x_i \in A \mid d_{x_i}^{A, k)} > d_{x_i}^{(B, k)} \}$ ... (1)
  • $A = A \setminus A'$ ... (2)
  • $B' = \{ x_i \in B \mid d_{x_i}^{A, k)} < d_{x_i}^{(B, k)}$ ... (3)
  • $B = B \setminus B'$ ... (4)
  • $A = A \cup B'$ ... (5)
  • $B = B \cup A'$ ... (6)
  • Repeat (1), (2), (3), (4), (5) and (6) until: (no element moves from $A$ to $B$ or from $B$ to $A$, that is A' and B' become empty) or (|A| $\leq$ k or |B| $\leq$ k)

Does this algorithm terminate, and if so, is it possible to easily prove it ? Is it also possible to have an upper bound for the number of iterations required to terminate ?

Note: "The $k$ nearest points to $x$ in a set $S$" means: The $k$ points (other than $x$) in $S$, having the smallest Euclidean distance to $x$.

$\endgroup$
3
  • 1
    $\begingroup$ Is the algorithm intended to be asymmetrical, as written? I'd have expected steps (2) and (3) to be reversed, so that the evaluation of A' and B' are acting symmetrically over the full set of n+m vectors. $\endgroup$ Nov 21, 2013 at 1:25
  • $\begingroup$ @HugovanderSanden if steps (2) and (3) are reversed the algorithm do note terminate. For instance in p = 1 dimension with k = 1, if A = {0, 3} and B = {2, 5} then elements of A and B will swap between A and B at each iteration. This is why, it is asymmetrical, as written. $\endgroup$
    – shna
    Nov 21, 2013 at 8:09
  • $\begingroup$ Ok, presumably it needs an extra termination check for |A| <= k after step 2 then; from your example, I also infer that d_x^(A,k) is intended to be defined over the k nearest points in A excluding x itself otherwise we have d_x^(A,1) = 0 whenever x is in A. $\endgroup$ Nov 21, 2013 at 8:27

1 Answer 1

2
$\begingroup$

Counterexample

This algorithm does not terminate. Here is a counterexample, in dimension $p=2$, with $m=n=2$ points in each set, only looking at the $k=1$ nearest neighbours.

$$ A=\left\{ \begin{pmatrix}-2\\0\end{pmatrix}, \begin{pmatrix}0\\1\end{pmatrix} \right\} \qquad B=\left\{ \begin{pmatrix}3\\0\end{pmatrix}, \begin{pmatrix}0\\-1\end{pmatrix} \right\} $$

The two points with $0$ in their first coordinate will change sets in every iteration. After two iterations you are back where you started, so this cannot terminate.

Step by step

Since you doubt my counterexample in a comment below, here is a detailed step-by-step execution of your algo in this case. I'm using the same names for the points as you did:

$$ x_1=\begin{pmatrix}-2\\0\end{pmatrix} \qquad x_2=\begin{pmatrix}0\\1\end{pmatrix} \qquad x_3=\begin{pmatrix}3\\0\end{pmatrix} \qquad x_4=\begin{pmatrix}0\\-1\end{pmatrix} \\ A=\{x_1,x_2\} \qquad B=\{x_3,x_4\} $$

  • $A'=\{x_2\}$ since $d_{x_2}^{(A,1)}=\lVert x_1-x_2\rVert=\sqrt5>2=\lVert x_4-x_2\rVert=d_{x_2}^{(B,1)}$
  • $A=A\setminus A'=\{x_1\}$
  • $B'=\{x_4\}$ since $d_{x_4}^{(A,1)}=\lVert x_1-x_4\rVert=\sqrt5<\sqrt{10}=\lVert x_3-x_4\rVert=d_{x_4}^{(B,1)}$
  • $B=B\setminus B'=\{x_3\}$
  • $A=A\cup B'=\{x_1,x_4\}$
  • $B=B\cup A'=\{x_2,x_3\}$
  • $A'=\{x_4\}$ since $d_{x_4}^{(A,1)}=\lVert x_1-x_4\rVert=\sqrt5>2=\lVert x_2-x_4\rVert=d_{x_4}^{(B,1)}$
  • $A=A\setminus A'=\{x_1\}$
  • $B'=\{x_2\}$ since $d_{x_2}^{(A,1)}=\lVert x_1-x_2\rVert=\sqrt5<\sqrt{10}=\lVert x_3-x_2\rVert=d_{x_2}^{(B,1)}$
  • $B=B\setminus B'=\{x_3\}$
  • $A=A\cup B'=\{x_1,x_2\}$
  • $B=B\cup A'=\{x_3,x_4\}$
$\endgroup$
5
  • $\begingroup$ The problem statement has starts with a vector $x$, which vector does not appear in your answer. $\endgroup$ Nov 20, 2013 at 22:01
  • 2
    $\begingroup$ The vector $x$ also does not appear in the algorithm, and looks to me as a placeholder to explain notation. Gerhard "Ask Me About System Design" Paseman, 2013.11.20 $\endgroup$ Nov 20, 2013 at 22:37
  • $\begingroup$ @MvG for you example, the algorithm that I provide terminates. Let the points: x1=(-2, 0), x2=(0,1), x3=(3,0), x4=(0,-1). At the first step A' = {} because distance(x1, x2) is not higher than distance(x1, x4), and distance(x2, x1) is not higher than distance(x2, x4), see step (1) of my Algorithm. So in step (2) A still the same. Similarly, in step (3) the B' = {x4} because x4 is closer to x1 than to x3, and x3 is not put in B' because distance(x3, x2) is not less than distance(x3, x4). Now at steps (5) and (6) we end up with A = {x1,x2,x4} and B={x3}. Algo stops now subce|B|=1$\leq$k $\endgroup$
    – shna
    Nov 20, 2013 at 22:39
  • $\begingroup$ @shna: I updated my answer to include a detailed step-by-step run. $A'=\{x_1\}$ because the distance(x2,x1) is higher than the distance(x2,x4). $\endgroup$
    – MvG
    Nov 21, 2013 at 8:53
  • $\begingroup$ @MvG Ok, you are right for that version of the algorithm. What about the case where instead of identifying $ALL x_i \in A'$ (Step 1), I immediately move $x_i$ from A to B as soon as I detect that $d^{(A,k)}_{x_i}>d^{(B,k)}_{x_i}$ (and vice versa) ? that is we do not need A' and B', we directly move a point from A to B as soon as we detect it (and from B to A as soon as we detect it). Will we have the same problem ? I just tested that on your example and it terminates. $\endgroup$
    – shna
    Nov 21, 2013 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.