# DELER: Distributed Clustering with Local Direction Centrality and Density Measure
## 3 The DEALER Algorithm
### Computation of DCM and \(\rho\) for Local Clustering
#### 3.2.2 Computation of \(\rho\)  
Although clustering methods based on _DCM_ values ensure the identification of sparse clusters, they perform poorly in addressing weak connectivity issues. To maintain the capability of identifying sparse clusters while mitigating weak connectivity problems, a hybrid metric incorporating the \(\rho\)-value is introduced. Unlike traditional density computation methods, the calculation of the \(\rho\)-value in the DEALER algorithm does not require specifying a neighborhood radius. Instead, it directly uses the reciprocal of the Euclidean distance between a data point and its \(k\)-th nearest neighbor, as determined during the _DCM_ computation process, to represent the data point's density. This approach offers two key advantages. First, it does not introduce additional computational overhead, as it merely applies a reciprocal operation to pre-computed data. Second, the reciprocal of the distance to the \(k\)-th nearest neighbor is positively correlated with the density as traditionally defined: the greater the distance to the \(k\)-th neighbor, the smaller the reciprocal, indicating sparser surrounding points and lower density in sparse regions, and vice versa. Moreover, using the reciprocal of the distance to the \(k\)-th nearest neighbor as a density metric inherently normalizes the density, which facilitates subsequent data processing tasks, such as data filtering. The formal definition of density is provided as follows:  
**Definition 3** (\(K\)-Nearest Neighbor Limited Density). : _For any data point \(p_{i}\), if \(p_{ik}\) denotes the \(k\)-th nearest neighbor of \(p_{i}\) in the data space, then the reciprocal of the Euclidean distance between \(p_{i}\) and \(p_{ik}\) is defined as the \(k\)-nearest neighbor limited density \(p_{i}\) of the data point \(p_{i}\)._  
Figure 12 illustrates the density computation process. As shown, for a given data point \(p_{i}\), assuming \(k=5\), five nearest neighbors can be identified, denoted as \(\{q_{1},q_{2},q_{3},q_{4},q_{5}\}\)  
and sorted by distance in ascending order as \(\{q_{1},q_{3},q_{5},q_{4},q_{2}\}\). Based on Figure 12, the formula for calculating the density of \(p_{i}\) is presented in Equation (7):  
\[\rho_{i}=\frac{1}{d(p_{i},p_{ik})} \tag{7}\]  
Here, \(\rho_{i}\) represents the density of the data point \(p_{i}\), \(p_{ik}\) is the \(k\)-th nearest neighbor of \(p_{i}\) in the data space (corresponding to point \(q_{2}\) in the figure), and \(d(p_{i},p_{ik})\) denotes the Euclidean distance between \(p_{i}\) and \(p_{ik}\). Based on the above analysis, to accurately differentiate between boundary points and core points and further enhance clustering accuracy, it is necessary to classify data objects using a combination of two metrics: density (\(\rho\)) and local _DCM_. Within the same cluster, boundary points generally have lower density compared to core points, while their _DCM_ values are higher. Since the core points uniquely determine a cluster, it is essential to ensure all core points are correctly identified. To achieve this, a two-step strategy is employed: first, data objects are filtered based on their _DCM_ values, followed by a secondary filtering based on density values. Specifically, data objects in the dataset are divided into two subsets based on their _DCM_ values: a core point candidate set and a boundary point candidate set. Next, density values are applied to further filter the objects in the core point candidate set. If the density of a data object is smaller than the densities of more than half of its \(k\)-nearest neighbors (KNNs), the object is reclassified as a boundary point. This approach is justified because, for objects in the core point candidate set, their KNN points are relatively evenly distributed. If the density of a data object is exceeded by a certain proportion (\(\gamma_{p}\), typically set to 50%) of its KNN points, the object is likely closer to the cluster boundary.