# Optimized Weighted Nearest Neighbours Matching Algorithm for Control Group Selection
## 3 Weighted Nearest Neighbours Control Group Selection with Simulated Annealing (WNNSA)  
The Weighted Nearest Neighbours Control Group Selection with Simulated Annealing algorithm proposed in this article is a distance-based method combined with simulated annealing (SA) [33]. The WNNSA method considers each subject as an \(n\)-dimensional data point in an \(n\)-dimensional space where each covariate (\(f_{i},i=1,\ldots,n\)) represents a unique dimension. Thus, control group selection can be interpreted as a distance minimization problem. To select a proper control group, those individuals have to be identified from the candidates that lie close to the individuals of the treated group. Because different covariates contribute differently to whether an individual is selected into the treated group, the closeness of the candidate individuals can not be calculated as a simple distance (e.g., Euclidean distance). For example, if the treated group includes individuals receiving a certain treatment, the application of the treatment may be affected differently by the age of the patient and the severity of the disease. Therefore, the WNNSA method takes the dimensions into account with different weights. The degree of influence is calculated from the regression coefficients of the logistic model fitted to the variable describing group membership. In this logistic regression model, the logit of the probability of belonging to the treated group of the individuals can be estimated as follows:  
\[logit(p)=ln\bigg{(}\frac{p}{1-p}\bigg{)}=b_{0}+b_{1}f_{1}+b_{2}f_{2}+\cdots+b_ {n}f_{n}, \tag{1}\]  
where \(p\) is the probability of belonging to the treated group and \(b_{i}\)-s (\(i=1,2,...,n\)) are the regression coefficients that describe the relative effects of the covariates (\(f_{i},i=1,2,...,n\)). The WNNSA method utilizes the odds ratio (OR) values of the fitted logistic regression model as weighting factors for the dimensions to compute the distances between the individuals. The weights for the features are calculated as:  
\[w_{i}= \begin{cases}exp^{b_{i}}&OR_{i}\geq 1\\ \frac{1}{exp^{b_{i}}}&OR_{i}<1,\end{cases}  \tag{2}\]  
where \(w_{i}\) yields the weight applied for the \(i\)-th dimension in the distance calculation. If \(OR_{i}<1\), then the covariate \(b_{i}\) is negatively correlated to the assignment to the treated group, and if \(OR_{i}\geq 1\), the covariate is positively associated. The calculation of the weights of covariates with an OR value above 1 (positive association) is simple, and it can take any value above one as the weighting factor. In case of negative association, the weight of the covariate should be calculated as the reciprocal of the calculated OR value. This way, the weights of the negatively associated covariates can also take any value from \((1,\infty]\), and it appropriately presents the weight of the covariate. Having the extended calculation of the weighting factors, the distance matrix containing the pairwise distances of the individuals in the treated and candidate groups can be calculated by weighting the dimensions as follows:  
\[dist(\mathbf{X}_{i},\mathbf{X}_{j})=\sum_{l=1}^{n}w_{l}d_{ij}^{(l)}, \tag{3}\]  
where \(d_{ij}^{(l)}\) denotes the normalized dissimilarity value of the \(\mathbf{X}_{i}\in X_{T}\) and \(\mathbf{X}_{j}\in X_{C}\) in the \(l\)-th dimension. Normalization of the distances along the dimensions is required to avoid the effect of the different ranges of the covariates [7]. As mentioned before, the WNNSA method considers control group selection as a distance minimization problem in the \(n\)-dimensional space. Distances between the individuals of the treated and control groups are calculated as weighted distances of the dimensions, and the aim is to match the control subjects to the treated subjects so that the sum of their distances is minimal. It is easy to see that in a simple case, when the neighbour closest to an individual in the treated group is chosen as the pair from the group of possible candidates, then the minimization problem is solved.