# Automatic Clustering for Improved Radio Environment Maps in Distributed Applications
## 5 K-Means Clustering Algorithm  
In this work, we adopt the KMC algorithm to address our clustering prediction problem. Distributed applications, such as smart cities and smart transportation systems, require efficient and scalable technical solutions, which are low in complexity, to address communication challenges [58; 59]. KMC is a clustering method that supports these requirements. As compared to other clustering approaches, such as Monte Carlo and Gillespie algorithms, KMC is an ideal candidate, specifically for unstable wireless environments. For instance, KMC is computationally efficient, as compared to the Monte Carlo and Gillespie algorithms [60]. This is a key concern in wireless environments, due to the large volume of data generated from various communicating entities. Additionally, the Monte Carlo algorithm greatly depends on the quality of the parameters and constraints. In contrast, KMC accounts for errors and uncertainty in clustering results. Based on the advantages of KMC, the model was adopted to perform clustering prediction in pour work. The following describes the approach with KMC. Let \(\mathcal{D}\) be the dataset that contains \(N\) quadri-dimensional normalized observations, i.e., \(\mathcal{D}=\{\mathbf{o}_{n}\mid n=1,\ldots,N\}\), where \(\mathbf{o}_{n}\) is in quadri-dimensional space (\(\mathbf{o}_{n}=\left(\underbrace{x_{n}^{*}}_{o_{1}},\underbrace{y_{n}^{*}}_{o _{2}},\underbrace{r_{n}^{*}}_{o_{1}},\underbrace{d_{n}^{*}}_{o_{n}}\right)\in \mathbb{R}^{4}\) ). \(x_{n}^{*},\ y_{n}^{*},\ r_{n}^{*}\) and \(d_{n}^{*}\) are the normalized values of the x-coordinate, y-coordinate, RSRP and distance to BS, respectively. Here, we apply min-max normalization, and, hence, the normalized values of the x-coordinate, y-coordinate, RSRP, and distance to BS are respectively given by  
\[x_{n}^{*}=\frac{x_{n}-\min(\mathbf{x})}{\max(\mathbf{x})-\min(\mathbf{x})}, \tag{5}\]  
\[y_{n}^{*}=\frac{y_{n}-\min(\mathbf{y})}{\max(\mathbf{y})-\min(\mathbf{y})}, \tag{6}\]  
\[r_{n}^{*}=\frac{r_{n}-\min(\mathbf{r})}{\max(\mathbf{r})-\min(\mathbf{r})}, \tag{7}\]  
\[d_{n}^{*}=\frac{d_{n}-\min(\mathbf{d})}{\max(\mathbf{d})-\min(\mathbf{d})}, \tag{8}\]  
where \(\mathbf{x}=[x_{1},\ldots,x_{n}]\), \(\mathbf{y}=[y_{1},\ldots,y_{n}]\), \(\mathbf{r}=[r_{1},\ldots,r_{n}]\) and \(\mathbf{d}=[d_{1},\ldots,d_{n}]\) are the real x- and y-coordinates, RSRPs, and distances to BS, respectively (before the normalization). For a given \(\mathcal{D}\) and a predefined number of clusters \(U\), the clustering operation aims to divide the \(N\) observations into \(U\) clusters \(C_{u},u=1,\ldots,U\), where the cluster centroid is considered the mean of the collected observations in the cluster. Note that the complexity of KMC is significantly lower in comparison with the complexity of an exhaustive search. The KMC process is summarized in Algorithm 1. The KMC procedure starts by randomly selecting a number of \(U\) observations from the dataset \(\mathcal{D}\), and considering them to be the \(U\) initial set of centroids, denoted by \(\mathbf{c}_{u},u=1,\ldots,U\). In step 2, the Euclidean distance is considered to determine the distance between each observation and the cluster centroids. It is expressed for two observations, \(\mathbf{o}\) and \(\mathbf{o}^{\prime}\) as  
\[d_{\mathbf{o}\mathbf{o}^{\prime}}=\sqrt{\sum_{i=1}^{4}\big{(}o_{i}-o_{i}^{ \prime}\big{)}^{2}}. \tag{9}\]  
The next step consists of assigning each observation \(\mathbf{o}_{n}\) to the cluster having a centroid closest to it. Then, it determines the new centroids of all the \(U\) clusters. In KMC, an iterative process is used to change the positions of the \(U\) cluster centroids until the positions remain unchanged. Given the above description, we explain the complexity of the proposed framework in terms of the number of iterations and the number/size of clusters. The time complexity of the framework is given in Table 3. In the table, \(I\) represents the number of iterations. The number of clusters is represented by \(U\).