Clustering Algorithms with Periodic Boundary Conditions

Question

I've been working on a project that involves the clustering of data with periodic boundary conditions. Like simulation of extra-framework water species. Specifically, I am looking for clustering algorithms that can effectively handle datasets where periodicity plays a significant role.

Upon searching the traditional clustering algorithms like k-means, I gather that they are not designed to account for periodicity inherently. I would love to hear about the clustering algorithms suitable for datasets with periodic boundary conditions from experts and enthusiasts. Are there any other algorithms that you have found to be effective in this context?

Thank you in advance for your valuable input!

Answer 1

First, there is a recent paper in which they proposed a k-means clustering algorithm adapted for periodic boundary conditions. Their Python implementation is available here.

However, the clustering algorithm I would suggest for periodic systems is the k-medoids algorithm. In contrast to the k-means algorithm, k-medoids selects actual data points as centers (i.e. medoids), and relies solely on pairwise distances instead of actual coordinates. The most popular k-medoids algorithm is the PAM algorithm, which has an implementation in PyClustering.

I suggested k-medoids mainly because you mentioned k-means in your question. In some cases, one would want a clustering algorithm that doesn't require a pre-defined number of clusters. Then I would suggest you to look into hierarchical clustering, where you can compare each point with other points only using distance measure. The algorithm actually has a Scipy implementation. Remember you can always get pairwise distance in periodic boundary condition using ASE by atoms.get_distance(a0, a1, mic=True).

Below is an example of the 5-medoids clustering algorithm for your water system using ASE and PyClustering:

from pyclustering.cluster.kmedoids import kmedoids
from ase.io import read, write
from ase.visualize import view
import random

# Read in the structure
atoms = read('str_opt_first.cif')
# Visualize the structure
view(atoms)
# Get the distance matrix in pbc
D = atoms.get_all_distances(mic=True)

# K-medoids clustering (PAM algorithm)
k = 5
# Initialize from a random atom (index). Set seed for reproducibility
medoid_init = random.sample(range(len(atoms)), k)
pam = kmedoids(D, medoid_init, data_type='distance_matrix')
pam.process()
medoids = pam.get_medoids()
clusters = pam.get_clusters()
print(medoids)
print(clusters)

# Visualize one of the clusters
view(atoms[clusters[0]])

Your original structure looks like this:

And a cluster will look something like this: