# DELER: Distributed Clustering with Local Direction Centrality and Density Measure
## 3 The DEALER Algorithm
### Data Partitioning
#### 3.3.2 Data Partition Adjustment
According to the Z-CF algorithm, for a local data point \(p_{i}\) on a sub-node, the algorithm identifies its \(k\)-th nearest neighbor \(kp^{{}^{\prime}}\) within the sub-node and calculates the distance \(d\left(p_{i},kp^{{}^{\prime}}\right)\), which serves as the upper bound for the search range. Next, it computes \(z_{p_{i}^{d(p,q)-}}\) and \(z_{p_{i}^{d(p,q)+}}\) and then determines the \(\min\left(z_{p_{i}^{d(p,q)-}}\right)\) and \(\max\left(z_{p_{i}^{d(p,q)+}}\right)\)\(z\)-values for all local data points on the sub-node. Subsequently, all data points with \(z\)-values within the interval \(\left[\min\left(z_{p_{i}^{d(p,q)-}}\right),\max\left(z_{p_{i}^{d(p,q)+}}\right)\right]\), but not belonging to the local data, are identified as candidate points for replication. These candidate points are copied to the current sub-node to serve as the dataset for finding accurate KNN points. Finally, the Z-CF algorithm is used to compute the precise KNN points for each local data point on the sub-node. The detailed steps of the S-KNN strategy are provided in Algorithm 2. ```
0: Dataset \(P\), KNN value \(k\)
0: KNN sets \(\{KNN_{i}\}\) and distances \(\{D_{i}\}\) for all points in \(P\)
1: Transform all data points \(p_{i}\) in dataset \(P\) into one-dimensional space using Equation (2), obtaining \(z_{p_{i}}\). 2: Sort the data points by their \(z\)-values in ascending order
3: Compute the quantiles \(\frac{1}{\sigma^{2}}\), \(\frac{2}{\sigma^{2}},\ldots,\frac{n-1}{n}\) and assign data points to corresponding sub-nodes \(P_{i}\), where \(i\in\{1,2,\ldots,n\}\). 4:for each sub-node \(P_{i}\)do // Locate initial KNN points
5:for each \(p_{j}\in P_{i}\)do
6: Compute \(z_{p_{i}^{d(p_{j},q)-}}\) and \(z_{p_{i}^{d(p_{j},q)+}}\)
7:endfor
8:\(lz_{p_{i}^{d(p,q)}}=\min\{z_{p_{i}^{d(p_{j},q)-}}|\forall p_{j}\in P_{i}\}\)
9:\(rz_{p_{i}^{d(p,q)}}=max\{z_{p_{i}^{d(p_{j},q)+}}|\forall

### Data Clustering

This section describes the clustering process from the node to the global level after obtaining directional centrality and density data based on the \(z\)-value index. #### 3.4.1 Local Clustering

Once data points have been labeled as either internal points or boundary points, the clustering problem reduces to clustering internal points and assigning boundary points to clusters. The process begins by clustering nearby internal points into initial clusters, followed by assigning boundary points to their nearest clusters based on distance. The detailed process is as follows. First, internal points are clustered by expanding outward from a central internal point, forming initial clusters. For this purpose, we propose the Local Expand (LE) algorithm. Before detailing the algorithm, all internal points are initially stored in a separate set \(CT\). Next, the algorithm selects a random internal point, assigns it a unique and exclusive label and removes it from \(CT\). Subsequently, it checks whether any of its KNN points are boundary points. If no boundary points are found, all unlabeled KNN points are assigned the same label as the selected data point. If boundary points exist, all unlabeled internal points closer than the boundary points are assigned the same label as the selected data point. These newly labeled points are then removed from \(CT\), and their KNN points undergo the same process. This continues until no additional points can be labeled, thereby identifying one initial cluster. The process is repeated by selecting another random point from \(CT\) and following the same steps until \(CT\) becomes empty. At this point, all initial clusters are formed. The detailed procedure for the LE algorithm is presented in Algorithm 3. ```
0: Set of internal points \(CT=\{p_{1},p_{2},\ldots,p_{n1}\}\). 0: Initial clusters \(C_{1},C_{2},\ldots,C_{m}\)
1:\(\mathcal{R}\gets CT\)
2:\(m\gets 0\)
3:while\(\mathcal{R}\
eq\varnothing\)do
4:\(m\gets m+1\)
5:\(\forall p_{i}\in P\)
6:\(C_{m}\leftarrow\{p_{i}\}\)
7:\(C_{m}\gets C_{m}\cup p_{j}\)\(p_{j}\) is among the KNN points of \(p_{i}\), and no KNN points of \(p_{i}\) are boundary points.