# Decoding Urban Intelligence: Clustering and Feature Importance in Smart Cities
## 3 Background
### k-Means  
k-means (see, for example, [17]) is a popular unsupervised learning algorithm used for clustering data into \(k\) distinct, non-overlapping subsets. The goal is to partition a set of \(n\) data points into \(k\) clusters, in which each point belongs to the cluster with the nearest mean, serving as a prototype of the cluster.  
Given a set of observations \(\mathbf{X}=\{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}\}\), where each observation \(\mathbf{x}_{i}\) is a \(d\)-dimensional vector, k-means clustering aims to partition the \(n\) observations into \(k\) clusters \(\mathbf{C}=\{C_{1},C_{2},\ldots,C_{k}\}\) to minimize the within-cluster sum of squares (WCSS):  
\[\operatorname*{arg\,min}_{\mathbf{C}}\sum_{j=1}^{k}\sum_{\mathbf{x}_{i}\in C _{j}}\|\mathbf{x}_{i}-\boldsymbol{\mu}_{j}\|^{2}\]  
where \(\boldsymbol{\mu}_{j}\) is the mean of the points in cluster \(C_{j}\):  
\[\boldsymbol{\mu}_{j}=\frac{1}{|C_{j}|}\sum_{\mathbf{x}_{i}\in C_{j}}\mathbf{x} _{i}\]  
The algorithm proceeds as follows:  
1. Initialize \(k\) cluster centroids randomly.
2. Assign each data point to the nearest centroid, forming \(k\) clusters.
3. Recalculate the centroids of the clusters by computing the mean of the points assigned to each cluster.
4. Repeat steps 2 and 3 until the centroids do not change significantly or a maximum number of iterations is reached.  
k-means aims to find the partition that minimizes the total intra-cluster variance, which is equivalent to minimizing the WCSS. In this sense, the optimal value of \(k\) parameter can be estimated using the silhouette index and the elbow method. This approach is used to determine the optimal number of clusters \(k\) in k-means clustering. It involves running the algorithm for a range of \(k\) values and plotting the WCSS against \(k\). The optimal \(k\) is found at the \"elbow\" point where the rate of decrease in WCSS slows down.  
k-means clustering partitions the data space into regions, with each region corresponding to one of the \(k\) cluster centroids. These regions can be visualized using a geometric concept known as a Voronoi diagram [18]. In a Voronoi diagram, the space is divided into cells based on the distance to a specific set of points, called sites. Each cell contains all the points that are closer to its site than to any other site.  
A Voronoi diagram is a partitioning of a plane into regions based on the distance to a specified set of points. These points are often referred to as sites or generators.  
Given a set of distinct points \(P=\{p_{1},p_{2},\ldots,p_{n}\}\) in the Euclidean plane, the Voronoi diagram is a subdivision of the plane into \(n\) regions, each associated with one point. The region associated with the point \(p_{i}\) consists of all points in the plane that are closer to \(p_{i}\) than to any other point in \(P\).  
Mathematically, the Voronoi cell \(V(p_{i})\) for a site \(p_{i}\) is defined as follows:  
\[V(p_{i})=\{x\in\mathbb{R}^{2}\mid d(x,p_{i})<d(x,p_{j})\text{ for all }j\
eq i\}\]where \(d(x,p)\) denotes the Euclidean distance between points \(x\) and \(p\).  
The Voronoi diagram can be characterized using a set of properties.  
Each Voronoi cell \(V(p_{i})\) is a convex polygon. This follows from the definition since the intersection of half-spaces (regions defined by linear inequalities) results in a convex shape. The edges of the Voronoi cells are portions of the perpendicular bisectors of the line segments joining pairs of sites. For two sites \(p_{i}\) and \(p_{j}\), the perpendicular bisector is given by the following:  
\[B(p_{i},p_{j})=\{x\in\mathbb{R}^{2}\mid d(x,p_{i})=d(x,p_{j})\}\]  
A Voronoi vertex is a point that is equidistant from three or more sites. These vertices are the points of intersection of the perpendicular bisectors of the line segments connecting the sites. To construct a Voronoi diagram, literature offers different algorithmic approaches (see, for example, [PERSON]'s algorithm [PERSON] (1996)).