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:
