6
$\begingroup$

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!

$\endgroup$
2
  • 3
    $\begingroup$ I know an algorithm that can do this, but it would be easier if you can provide me a periodic structure that have some sense of clustering, so that I can show you how it works. $\endgroup$
    – Shaun Han
    Jul 14, 2023 at 16:31
  • 1
    $\begingroup$ @ShaunHan, thanks for your answer. I give you a google drive link to two structures and the indices of the water oxygens . (If the algorithm works to distinguish two different structures clustering of extraframework water). drive.google.com/drive/folders/… $\endgroup$
    – Saha_1994
    Jul 14, 2023 at 17:57

1 Answer 1

8
$\begingroup$

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: enter image description here

And a cluster will look something like this: enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .