## 3 The Proposed Algorithm
### Merging Period
#### 3.2.1 Methods of Similarity Measurement  
In this section, a similarity metric based on shared nearest neighbors is proposed to iteratively merge subclusters with maximum similarity, where shared nearest neighbors can be obtained based on k-nearest neighbors and reverse k-nearest neighbors. In the proposed merging strategy, the two subclusters to be merged should have sufficiently small shortest distances and more points in the set of shared nearest neighbors. Thus, the shared k-nearest neighbor is born. It evaluates the similarity by counting the number of shared neighbors in the neighborhood between subclusters. In addition, unlike similarity measures that only consider Euclidean distances that must rely on global linearity assumptions, shared k-neighbors focus more on the local neighborhood structure, take into account the relative positions of the samples in their neighborhoods, and are able to capture local structural and contextual information in the samples. This means that they are able to adapt to data distributions of different densities. Based on the above properties, some definitions are given to describe the new similarity metric. * Shared k-nearest neighbor (SKNN): For any two sample points \(x_{i}\) and \(x_{j}\), \(KNN(x_{i})\) and \(KNN(x_{j})\), denote the set of \(K\) nearest neighbor sample points of sample points \(x_{i}\) and \(x_{j}\), respectively. \(RKNN(x_{i})\) refers to a set of data points in a given dataset, where each point in the set considers a query point as one of its k-nearest neighbors. Formally, for a query point \(x_{i}\), its \(RKNN(x_{i})\) set is defined as the collection of points in the dataset that include \(x_{i}\) within their respective sets of k-nearest neighbors. In particular, since \(KNN\) and \(RKNN\) are symmetric neighborhoods and both utilize Euclidean distance to compute the distance between samples, \(RKNN(x_{i})\) can be utilized instead of \(KNN(x_{j})\) to denote the reverse k-nearest neighbors of the sample point \(x_{i}\) as shown in Equation (5), which together form the basis for sharing k-nearest neighbors. \[RKNN(x_{i})=\left\{x_{j}\in\text{ cluster }_{j}\mid x_{i}\in\text{KNN}\big{(}x_{j} \big{)}\right\} \tag{5}\]  
Therefore, the number of shared nearest neighbor points \(SKNN\) defined by \(KNN\) and \(RKNN\) together for any sample point \(x_{i}\) is defined as in Equation (6):  
\[SKNN(x_{i})=KNN(x_{i})\cap RKNN(x_{i}) \tag{6}\]  
where \(KNN(x_{i})\) denotes the set of k-nearest neighbors of the sample point \(x_{i}\) and \(RKNN(x_{i})\) denotes the set of reverse k-nearest neighbors of the sample point \(x_{i}\). * Shared k-nearest neighbors between clusters: The closer two sample points on the structure are and the higher the degree of shared nearest neighbors, the higher their similarity and the higher the probability that they will be merged. As shown in Figure 5, it can be seen that the higher the degree of shared k-nearest neighbors of neighboring subclusters, the more likely they are to be merged into one cluster. According to Equations (5) and (6), the shared k-nearest neighbors of subcluster \(cluster_{i}\) can be defined as in Equation (7):  
\[SKNN(cluster_{i})=KNN(cluster_{i})\cap RKNN(cluster_{i}) \tag{7}\]  
Equation (8) denotes the sum of two neighboring subclusters \(cluster_{i}\) and \(cluster_{j}\) sharing \(k\)-nearest neighbor sample points. \[SNN\big{(}\text{ cluster }_{i}\text{ cluster }_{j}\big{)}=SKNN(\text{ cluster }_{i})+SKNN\big{(}\text{ cluster }_{j}\big{)} \tag{8}\]
* Shared k-nearest neighbor similarity measure: According to the above Equations (7) and (8), the similarity measure \(Sim(cluster_{i},cluster_{j})\) of two neighboring subclusters can be defined as in Equation (9):  
\[Sim(cluster_{i},cluster_{j})=\frac{SNN(cluster_{i},cluster_{j})}{nums_{ cluster_{i}}}*\frac{con_{cluster_{i}}(cluster_{j})}{nums_{cluster_{i}}}* \frac{con_{cluster_{j}}(cluster_{i})}{nums_{cluster_{j}}} \tag{9}\]  
where \(nums_{cluster_{i}}\) denotes the number of subcluster \(cluster_{i}\) data points.