header

FindKNN : To find k nearest neighbors of P(one m-dimensional test point) from S(n m-dimensional sample points).
Tag:
Edit edit   Starstar

Program Information

Name: FindKNN
Domain: Machine learning
Functionality: To find k nearest neighbors of P(one m-dimensional test point) from S(n m-dimensional sample points).
Input:
     $P=(p_{1},p_{2},\cdots,p_m)$:One m-dimensional test point(Type: Point) $S=(s_{1},s_{2},\cdots,s_n)$ where $s_i=(s_{i_{1}}s_{i_{2}},\cdots,s_{i_m})$:N m-dimensional sample points(Type: Set) k:A positive integer(Type: Integer)
Output:
     $O=(o_{1},o_{2},\cdots,o_k)$ :Indices of the k nearest neighbors(Type: Index)

Reference

               How Effectively Does Metamorphic Testing Alleviate the Oracle Problem? http://dx.doi.org/10.1109/TSE.2013.46

MR Information


MR1


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f = P_s$ $S_f = S_s$ $k_f > k_s$
    Output relation: $O_s \subset O_f$

MR2


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: The coordinates of $P_f$ = The coordinates of $P_s \times x$, where x is a non-zero real number. The coordinates of $S_f$ = The coordinates of $S_s \times x$, where x is a non-zero real number. $k_f = k_s$
    Output relation: $O_f = O_s$

MR3


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f = P_s$ $S_f = S_s \cup \{P\}$ $k_f = k_s + 1$
    Output relation: $O_f = O_s \cup \{n + 1\}$, where n+1 is the index of the added sample.

MR4


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f = P_s$ $S_f$ = Changing the order of $S_s$ $k_f = k_s$
    Output relation: The indices of the selected k nearest neighbors of $O_f$ = Changing the indices of the selected k nearest neighbors of $O_s$ according to changing the order of samples.

MR5


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_{f_{1}},S_{f_{2}},k_f$ ; Follow-up output: $O_{f_{1}},O_{f_{2}}$
    Input relation: $P_f = P_s$ $S_{f_{1}} \cup S_{f_{2}} = S_s$ $k_f = k_s$
    Output relation: $O_s \subset O_{f_{1}} \cup O_{f_{2}}$

MR6


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f = P_s$ Each coordinate for each sample ${s^f}^i_l$ of $S_s$= Each coordinate $2p_l-{s^s}^i_l$ of $S_s$ $k_f = k_s$
    Output relation: $O_f = O_s$

MR7


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f = P_s$ $S_f$ = Adding h<k points whose distance to P are not larger than that of the kth nearest neighbor to $S_s$. $k_f = k_s$
    Output relation: $|O_s \cap O_f| = k – h$

MR8


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f = P_s$ $S_f$ = Adding some points whose distance to P are larger than that of the kth nearest neighbor to $S_s$. $k_f = k_s$
    Output relation: $O_s = O_f$

MR9


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f = P_s$ $S_f$ = Deleting h<k samples from $S_s$. $k_f = k_s$
    Output relation: $|O_s \cap O_f| \ge k – h$

MR10


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f$ = Adding another coordinate to $P_s$, where the value of the added coordinate is a constant. $S_f$ = Adding the same coordinate to $S_s$. $k_f = k_s$
    Output relation: $O_s = O_f$

MR11


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f = P_s$ $S_f$ = Deleting some unselected samples from $S_s$. $k_f = k_s$
    Output relation: $O_s = O_f$

MR12


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f = P_s$ $S_f$ = Deleting some selected samples from $S_s$. $k_f = k_s$
    Output relation: $O_s \cap O_f = O_s \setminus$ {the indices of the deleted samples

MR13


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f = P_s$ $S_f$ = Adding a sample whose distance to P is smaller than the kth nearest neighbor to $S_s$. $k_f = k_s$
    Output relation: $O_f = O_s \setminus \{ok \} \cup \{n+1\} $

MR14


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f$ = Changing the order of coordinates of $P_s$ $S_f$ = Changing the order of coordinates of $S_s$. $k_f = k_s$
    Output relation: $O_f = O_s$

MR15


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: $P_f = P_s$ $S_f = S_s$. $k_f = k_s + 1$
    Output relation: $O_f = (o^f_{1},o^f_{2},\cdots,o^f_k,o^f_{k+1})$ $O_s = (o^f_{1},o^f_{2},\cdots,o^f_k)$ $o^f_{k+1} \notin O$

MR16


    Source input: $P_s,S_s,k_s$ ; Source output: $O_s$
    Follow-up input: $P_f,S_f,k_f$ ; Follow-up output: $O_f$
    Input relation: The coordinates of $P_f$ = The coordinates of $P_s + x$, where x is a non-zero real number. The coordinates of $S_f$ = The coordinates of $S_s + x$, where x is a non-zero real number. $k_f = k_s$
    Output relation: $O_f = O_s$

Related

Insert title here