# Modeling and Analysis of New Hybrid Clustering Technique for Vehicular Ad Hoc Network
## 3 Clustering Model
### Covering Rough Set Model
#### 3.1.2 Group Implementation
Figure 7: K-Means clustering procedure [21]. (**A**) Initial K-value selection, (**B**) Optimal centroid location selection, (**C**) Cluster centroid updates, (**D**) Final cluster centroid location. ## 4 Problem Formulation and Evaluation Model

### Problem Formulation

The most important problem in data mining is data clustering. The clustering technique can be used in various fields, including ad hoc networks. The clustering technique should distribute the nodes as clusters with high similarity. An efficient clustering model has to verify the following:

1. Maximizing the intra-cluster similarity by minimizing the distances between vehicles in the same cluster. 2. Minimizing inter-cluster similarity by maximizing the distances between vehicle clusters. There are many indices for evaluating cluster efficiency. In this work, we used the most popular indices to evaluate the proposed clustering algorithm and then compared the results with other clustering algorithms in the VANET field. ### Similarity Measurement

A similarity measurement can be defined as the distance between cluster vehicles. While similarity is a value that illustrates the strength of the relationship between two vehicles, dissimilarity deals with the measurement of divergence between two vehicles. The performance of different algorithms depends on how they select an effective distance function for the input dataset. The Root Mean Square Error (RMSE) [26] was used to check the clustering similarity. \[RMSE=\sqrt{\frac{1}{n}\sum_{i,j=1}^{n}\left(d\left(v_{i},v_{j}\right)\right)^{ 2}} \tag{17}\]

where \(x_{i}\) and \(v_{i}\) are two vehicles, and n is the number of vehicles in the cluster. RMSE calculates the square root of the average distance between all vehicles in the existing cluster. A small RMSE represents high cluster similarity. ### Silhouette Coefficient (SC)

The Silhouette Coefficient (SC) represents the fit of objects within a cluster. The quality of a cluster can be measured in the range of \(-1\) to \(1\). A value that is near one (1) indicates that the vehicle belongs to the right cluster. This coefficient involves the two terms of cohesion and separation. Cohesion is the intra-clustering distance, and separation is the distance between cluster centroids. A(x) is the average distance between the sample vehicle and all other vehicles in the same cluster. B(x) is the average distance between the sample vehicle and all other vehicles in its nearest cluster. A value near \(-1\) for a cluster indicates that the vehicles should belong to another cluster. The \(SC\) can be computed as follows [27]:

\[A(x)=\frac{1}{n_{i}-1}\sum_{v_{i}\in C_{i}}d\left(v_{sample},v_{i}\right) \tag{18}\]\[B(x)=min\left\{\frac{1}{n_{j}}\sum_{v_{j}\in C_{j}}d\Big{(}v_{sample},v_{j}\Big{)}\right\} \tag{19}\]

\[SC(i)=\ \frac{B(x)-A(x)}{max\{B(x),A(x)\}} \tag{20}\]

where \(v_{sample}\) is the vehicle sample; \(v_{i}\) is the clustered vehicle; \(d\Big{(}v_{sample},v_{i}\Big{)}\) represents the Euclidean distance between the sample vehicle and all vehicles in the same cluster; and \(d\Big{(}v_{sample},v_{j}\Big{)}\) represents the Euclidean distance between the sample vehicle and all vehicles in the closest cluster. Based on the value of A and B, we can rewrite the Formula (20) as:

\[SC(i)= \begin{cases}1-\frac{A(x)}{B(x)},&A(x)<B(x)\\ 0,&A(x)=B(x)\\ \frac{B(x)}{A(x)}-1,&A(x)>B(x)\end{cases}  \tag{21}\]

### Davies-Bouldin Index

The Davies-Bouldin (DB) index is the measurement of the average similarity between each cluster and the most similar one. A lower DB index value indicates that the clustered vehicles have converged and the divergence of clusters is high. The goal of the DB index is to achieve minimum within-cluster variance and maximum between-cluster separation. It measures the similarity of a cluster (\(R_{ij}\)) according to its variance (\(Si\)) and the separation of a cluster (\(d_{ij}\)) according to the distance between two clusters (\(C_{i}\)_and_\(C_{j}\)).