Abstract
Microbiome sequencing allows defining clusters of samples with shared composition. However, this paradigm poorly accounts for samples whose composition is a mixture of cluster-characterizing ones, and therefore lie in-between them in cluster space. This paper addresses unsupervised learning of 2-way clusters. It defines a mixture model that allows 2-way cluster assignment and describes a variant of generalized k-means for learning such a model. We demonstrate applicability to microbial 16S rDNA sequencing data from the Human Vaginal Microbiome Project.
Introduction
In microbiome research, identifying distinct microbial communities is crucial for understanding health and disease states. Standard clustering algorithms, such as k-means, are typically used to group similar samples into discrete categories. However, biological reality often presents a spectrum rather than tidy "buckets." A sample may represent a transitional state—a mixture of two distinct microbial communities.
Standard k-means forces these transitional samples into a single cluster. This leads to two primary issues: it misclassifies the sample and creates a "pulling" effect where cluster centers are distorted toward the middle of the data distribution, obscuring the "pure" microbial states. This paper introduces 2-Way k-Means, a modification that models data points as weighted mixtures of two clusters, providing a more accurate representation of transitional states.
Methodology
The proposed 2-Way k-Means model allows a data point $x_i$ to be assigned to a point on a line segment connecting two cluster centers, $c_j$ and $c_{j'}$, rather than just the nearest center.
The Generative Model
The model assumes data is either sampled from a "pure" Gaussian cluster or a weighted average of two Gaussians. This specifically constrains points to exist on linear paths between pairs of clusters, reflecting biological mixing.
The Algorithm
The optimization follows an alternating approach:
- Assignment Step: For each point, the algorithm identifies the best pair of clusters and the optimal weight ($u$) that places the point on the line between them.
- Update Step: Cluster center positions are updated using Ordinary Least Squares (OLS) based on these weighted assignments.
Experimental Setup
The model was evaluated using two primary datasets:
- Simulated Data: 500 points generated from three clusters in 2D space to benchmark accuracy against vanilla k-means.
- Human Vaginal Microbiome Project (HMP): ~1,500 mid-vaginal samples characterized by 16S rDNA sequencing. This dataset is a benchmark for clustering due to well-defined "Community State Types" (CSTs).
Results and Discussion
On simulated data, standard k-means exhibited significant bias. As shown in Figure 1, the estimated cluster centers (triangles) are pulled away from the true centers (stars) due to the presence of intermediate points.
In contrast, the 2-Way k-means algorithm successfully recovered the true centers with high fidelity (Figure 2). Quantitatively, the assignment error rate dropped from 40.6% to 3.8%, and the cluster center precision error ($err_\mu$) decreased from 0.36 to 0.04.
When applied to the HMP dataset, the 2-way model reduced the objective function residual error from 108.0 to 51.0. It revealed that certain "diverse" clusters were actually hubs for samples transitioning between stable states. Specifically, the model identified bacteria like Sneathia and Prevotella as dominant in these transitional samples, offering insights into microbial community shifts.
Conclusion and Future Work
2-Way k-means provides a robust framework for modeling gradients in microbiome data. While effective, the current model assumes spherical clusters and linear transition paths. Future work will explore "k-way" assignments (mixtures of three or more clusters), non-spherical covariance matrices, and non-linear transition paths to better capture the complexity of biological systems.
Summary updated