DBSCAN in Domains with Periodic Boundary Conditions

Algorithm

The approach we propose leverages the property of DBSCAN that proximity is defined by a single well-defined radius ϵ. Consequently, the algorithm only needs to search for neighbors across the periodic boundary up to this distance. The method works by periodically extending the domain by a limited distance of ϵ in all periodic directions. This allows the clustering problem to be solved by applying the conventional DBSCAN algorithm – designed for open boundaries – to the extended domain. In the final step, the algorithm identifies and merges cluster labels assigned to different periodic copies of the same data point, ensuring that points in different periodic images are recognized as belonging to the same cluster in the periodic domain.

The algorithm takes as input the data points $\mathcal{S}$ (embedded in a space with dimension D) that need to be labeled, the lower and upper periodic boundaries $x_{min}=\left(x_{min}^{\left(1\right)},\hspace{0.17em}{x}_{min}^{\left(2\right)},\dots ,\hspace{0.17em}{x}_{min}^{\left(D\right)}\right)$ and $x_{max}=\left(x_{max}^{\left(1\right)},\hspace{0.17em}{x}_{max}^{\left(2\right)},\dots ,\hspace{0.17em}{x}_{max}^{\left(D\right)}\right)$ , respectively, and finally the DBSCAN parameters, being the neighborhood ϵ and min_points. The procedure consists of four steps, which are illustrated with an example in Figure 1:

Figure 1

1. Periodic extension. Extend data set $\mathcal{S}$ from [x_min, x_max] to [x_min–ϵ, x_max+ϵ] through periodic extension, saving the padded data points (the periodic copies) into $\mathcal{S}$_pad. For all padded points s_pad ∈ $\mathcal{S}$_pad, save the index of the corresponding point in the original dataset $\mathcal{S}$.

2. DBSCAN. Apply original DBSCAN with neighborhood ϵ and min_points to all data points ${\mathcal{S}}_{\text{all}}=\mathcal{S}\cup {\mathcal{S}}_{\text{pad}}$, yielding labels $\mathcal{L}$_all.

3. Linking equivalent clusters. For each padded point s_pad ∈ $\mathcal{S}$_pad, compare its label l_pad to the label of the corresponding point in the original dataset l_orig. If l_pad ≠ l_orig, save the labels as a linked cluster if that link does not already exist. If one of the labels already exists in another link, extend that link by including the other label.

4. Resolving linked clusters. For all the saved linked clusters, replace the linked labels by a single unique label (e.g. the minimum of the linked labels). This yields the final labels $\mathcal{L}$ corresponding to the clustering of the original data points $\mathcal{S}$ obeying the periodic boundary conditions.

Since this approach employs the conventional DBSCAN algorithm with open boundaries, it is automatically compatible with all optimized implementations of DBSCAN and its underlying neighbor search algorithms. Since the neighborhood distance ϵ is typically small with respect to the domain size, the number of padded points is typically a small fraction of the total number of points N. The impact on the performance of our approach for solving the clustering problem in the periodic domain is thus small with respect to the conventional clustering problem with open boundaries. And crucially, owing to its compatibility, it can be run at the same complexity of $\mathcal{O}$ (N log N) that the optimized neighbor search algorithms for open boundaries are able to achieve.

Implementation

We have implemented the proposed approach for DBSCAN in domains with periodic boundaries in a Python package that is publicly available in the repository at github.com/XanderDW/PBC-DBSCAN. It uses the widely employed and highly optimized Scikit-learn implementation of DBSCAN [14] to ensure broad compatibility. The repository also provides ready-to-use code examples for running the different example cases provided in this work.

Examples with synthetic data

Here we provide examples of the proposed approach for the DBSCAN clustering problem with periodic boundaries using data that is synthetically generated from (multivariate) Gaussian distributions.

Figure 2 depicts the simplest example of periodic clustering in one dimension. It shows that the algorithm successfully connects the purple cluster that traverses the periodic boundary.

Figure 2

In Figure 3 we show an example in two dimensions, distinguishing the cases of doubly periodic Figure 3(a,b) and singly periodic boundary conditions Figure 3(c,d).

Figure 3

Finally, Figure 4 shows an example of periodic clustering in three dimensions, where all three dimensions have periodic boundaries.

Figure 4

Our implementation supports data with an arbitrary number of dimensions and can arbitrarily mix open boundaries and periodic boundaries for every dimension separately.

Example with real data

Real world data can often involve clusters with highly non-Gaussian shapes. DBSCAN is very effective in identifying clusters of these complex shapes. One such example is encountered in turbulent flows, when studying the clustering of light bubbles submerged in a heavier turbulent fluid flow. There, bubbles are found to strongly concentrate in regions of high vorticity, forming filamentary clusters inside the cores of these elongated vortex structures [15, 16]. Such clustering behavior is typically studied computationally in domains with periodic boundary conditions to ensure full homogeneity and to eliminate any effect of confinement, such as boundary layer formation. An example is provided in Figure 5, obtained from a direct numerical simulation of homogeneous isotropic turbulence with Lagrangian bubbles [17]. It shows that the clustering algorithm proposed in this work is able to successfully capture the bubble clusters in accordance with the periodic boundary conditions. Notice how, for instance, the turquoise cluster traverses the top/bottom boundary and the purple cluster crosses four different corners of the domain.

Figure 5

Conclusions

In this work, we have presented a clustering algorithm based on DBSCAN for data embedded in a domain with periodic boundaries. The approach leverages the conventional DBSCAN algorithm designed for open boundaries, ensuring compatibility with existing optimized neighborhood search methods. As a result, it maintains the same runtime complexity of $\mathcal{O}$ (N log N) as conventional optimized DBSCAN algorithms. Our Python implementation of this method is publicly available as a ready-to-use package in the repository at https://github.com/XanderDW/PBC-DBSCAN.

Code repository

Name: GitHub

Persistent identifier: https://github.com/XanderDW/PBC-DBSCAN

Licence: MIT

Date published: 24/01/2025

Language

English