# Optimized Weighted Nearest Neighbours Matching Algorithm for Control Group Selection
## 3 Weighted Nearest Neighbours Control Group Selection with Simulated Annealing (WNNSA)
### Conflicting Candidates
The first element comes from the treated group while the second one from the set of candidates to be paired as control individuals. ```
Input:\(X_{T}\): the set of the treated group; \(X_{C}\): the set of candidate individuals; \(k\) the size of the reduced environment; \(t_{max}\) the starting temperature Output:\(X_{UT}\) the selected control group; \(M\) the set of the matched pairs. 1 Initialize: \(X_{UT}=\emptyset\)\(M=\emptyset\)\(e_{best}=\infty\)\(t=t_{max}\)
2 Normalize \(X_{T}\) and \(X_{C}\) collectively using feature scaling. Calculate the distance matrix \(\mathbf{D}\) for all pairs of \(\mathbf{X}_{i}\in X_{T}\) and \(\mathbf{X}_{j}\in X_{C}\) by Equation (3). Determine \(NN_{k}(\mathbf{X}_{i},X_{C})\) based on the distance matrix \(\mathbf{D}\) for all \(\mathbf{X}_{i}\in X_{T}\). Determine \(p(\mathbf{X}_{i},\mathbf{X}_{j})\) for each \(\mathbf{X}_{i}\in X_{T}\) and for each \(\mathbf{X}_{j}\in NN_{k}(\mathbf{X}_{i},X_{C})\) by Equation (4). Set: \(X^{(t)}_{unpaired}=X_{T}\)\(X^{(t)}_{UT}=\emptyset\)\(M^{(t)}=\emptyset\). Set \(ActualMattings^{(t)}=\emptyset\) For all \(\mathbf{X}_{i}\in X^{(t)}_{unpaired}\) Select an \(\mathbf{X}_{j}\) pair from \(NN_{k}(\mathbf{X}_{i},X_{C})\) for \(\mathbf{X}_{i}\in X^{(t)}_{unpaired}\) at random with probability \(p(\mathbf{X}_{i},\mathbf{X}_{j})\). Set \(ActualMattings^{(t)}=ActualMattings^{(t)}\cup\{(\mathbf{X}_{i},\mathbf{X}_{j} )\}\). 3 For \(l=1,\dots,|ActualMattings^{(t)}|\) If \(ActualMattings^{(t)}_{l2}\) is selected for only one \(\mathbf{X}_{i}\in X_{T}\)\(X^{(t)}_{unpaired}=X^{(t)}_{unpaired}-\{\mathbf{X}_{i}\}\)\(X^{(t)}_{UT}=X^{(t)}_{UT}\cup\{ActualMattings^{(t)}_{l2}\}\)\(M^{(t)}=M^{(t)}\cup\{ActualMattings^{(t)}_{l}\}\) End if
4 Repeat _Steps 7 to 9_, while \(X^{(t)}_{unpaired}\
eq\emptyset\). 5 Calculate the actual energy \(e^{(t)}\) for the matching \(M^{(t)}\) by Equation (6). 6 If \(e^{(t)}<e_{best}\)\(e^{(t)}\)\(X_{UT}=X^{(t)}_{UT}\)\(M=M^{(t)}\). 7 Set \(t=t-1\). Repeat _Steps 5 to 13_ until \(t=0\). Return \(X_{UT}\) and \(M\). ```  
**Algorithm 1**Weighted Nearest Neighbours Control Group Selection with Simulated Annealing (WNNSA). As Algorithm 1 showed, the WNNSA method uses a reduced environment for selecting the elements of the control group. However, the application of a reduced environment introduces another problem. Below a given value of \(k\), it is guaranteed that the algorithm will not result in a control group with the desired size. This stems from conflicts occurring during the selection process. For example, consider the following situation. Let \(\mathbf{X_{1}}\), \(\mathbf{X_{2}}\), and \(\mathbf{X_{3}}\) be three individuals from the treated group. Let \(\mathbf{X_{4}}\) be the closest and \(\mathbf{X_{5}}\) the second-closest neighbour of \(\mathbf{X_{1}}\) and \(\mathbf{X_{2}}\) individuals among the candidate subjects. Furthermore, let \(\mathbf{X_{5}}\) be the first and \(\mathbf{X_{4}}\) the second nearest neighbour of \(\mathbf{X_{3}}\). Moreover, let \(\mathbf{X_{6}}\) be the third nearest neighbour of \(\mathbf{X_{1}}\), \(\mathbf{X_{2}}\), and \(\mathbf{X_{3}}\). Our aim is to select an equal-sized control group for the treated group. In this case, if we set \(k\) to 2, then the reduced environments for \(\mathbf{X_{1}}\), \(\mathbf{X_{2}}\), and \(\mathbf{X_{3}}\) contain only the individuals \(\mathbf{X_{4}}\) and \(\mathbf{X_{5}}\). So, three individuals cannot be selected from the reduced environments; therefore, 1:1 matching can not be performed. This problem can also be extended to higher \(k\) values. For this reason, a method to determine the minimal \(k\) value is needed. A visual representation of the problem above can be seen in Figure 1.  
The problem of _unsolvable conflict_ described above can be solved mathematically. As mentioned before, \(NN_{k}(\mathbf{X}_{i},Y)\) denotes the \(k\)-closest neighbours of \(\mathbf{X}_{i}\) from the set \(Y\).