iSparse kmeans: a two-step clustering approach for big dynamic functional network connectivity data

Mohammad S.e. Sendi, David H. Salat, Robyn L. Miller, Vince D. CalhounbioRxiv 2022 · DOI

TL;DR

This paper introduces "iSparse kmeans," a novel two-step clustering approach designed to efficiently analyze large-scale dynamic functional network connectivity (dFNC) data from fMRI scans. By employing a subsampling strategy, iSparse kmeans significantly reduces computational demands, making complex dFNC analysis accessible without requiring massive computing resources, while still producing comparable results to traditional methods.

What Problem Does This Paper Address?

Analyzing dynamic functional network connectivity (dFNC) from resting-state fMRI (rs-fMRI) is crucial for understanding how brain networks interact over time. A key step in this analysis is clustering these dynamic connectivity patterns to identify recurring "brain states." However, traditional clustering methods, like standard k-means, become computationally prohibitive for the ever-growing size of neuroimaging datasets. Identifying the optimal number of clusters itself requires repeatedly running the algorithm, leading to significant time and computational power demands, especially with large datasets and long scan times. This bottleneck limits the feasibility of dFNC analysis for researchers with limited computational resources.

Methods

The core innovation is the "iSparse kmeans" algorithm, a two-step clustering process:

  • Step 1: Subsampling and Initial Clustering: Instead of using the entire dataset, iSparse kmeans randomly selects a subset of subjects' dFNC data. Standard k-means is then applied to this subsample for a range of cluster numbers (k=2 to L). This step generates multiple sets of cluster centroids at different "model orders" (L).
  • Step 2: Aggregation and Final Clustering: All the cluster centroids generated in Step 1 are aggregated. The "elbow criterion" is then used on this reduced set of centroids to identify the optimal number of clusters (Kopt). Finally, a second standard k-means clustering is performed on the aggregated centroids to determine the final set of dFNC states. This approach effectively summarizes the data and identifies states without processing the entire dataset at once.

Datasets

The study utilized data from the Human Connectome Project (HCP). Specifically, they analyzed rs-fMRI data from 833 young healthy adults. For each participant, four separate rs-fMRI sessions were used (HCP1, HCP2, HCP3, and HCP4) to ensure the reproducibility and robustness of their findings across different scanning sessions.

Key Insights and Ideas

  • Computational Efficiency is Key: The primary insight is that by intelligently subsampling the data, it's possible to achieve high-quality dFNC clustering without the massive computational cost of traditional methods. This democratizes access to advanced neuroimaging analysis.
  • Two-Step Approach Works: The proposed two-step clustering (subsample-then-aggregate) effectively captures the essential information needed for state identification, bypassing the need to process the full dataset repeatedly.
  • Reproducibility Across Sessions: Demonstrating that the iSparse kmeans method yields consistent results across four different sessions from the same participants is a strong indicator of its reliability.

Key Results

  • Similar Brain States: Both iSparse kmeans and conventional kmeans generated highly similar brain dFNC states, with a similarity of over 99% for L > 5.
  • Significant Speedup: iSparse kmeans was found to be 27 times faster than the traditional method in identifying the optimal number of clusters. This speed advantage was observed even when using a very small percentage of the data (as low as 0.12%) in each iteration.
  • Comparable dFNC Features: The dFNC features extracted (occupancy rate and number of transitions) were highly correlated (R > 0.98) between the iSparse kmeans and conventional kmeans methods, indicating that the functional insights are preserved.
  • Improved Cluster Quality: iSparse kmeans demonstrated better cluster quality, as measured by a "distance ratio," compared to standard kmeans across all tested sessions and cluster orders (p < 0.001).

Limitations and Future Work

  • Maximum L Value: The paper acknowledges that the maximum value for L (the range of clusters to test in the first step) is determined empirically. Future work could involve developing an algorithmic approach to set this parameter.
  • Comparison with Other Fast Methods: While iSparse kmeans is shown to be faster and of better quality than standard kmeans, it was not directly compared against other existing "fast" clustering algorithms. Future studies could explore these comparisons.
  • Adaptability to Other Clustering Algorithms: The authors suggest that their iSparse framework is not limited to k-means and could be adapted to other fast clustering approaches, potentially further improving computational speed and performance.

Summary updated

Abstract

Abstract Background Dynamic functional network connectivity (dFNC) estimated from resting-state functional magnetic imaging (rs-fMRI) studies the temporally varying of functional integration between brain networks. In a typical dFNC pipeline, a clustering stage to summarize the connectivity patterns that are transiently but reliably realized over the course of a scanning session. However, identifying the right number of clusters through a conventional clustering criterion computed by running the algorithm repeatedly, over a large range of cluster numbers is time-consuming and requires substantial computational power even for typical dFNC datasets, and the computational demands become prohibitive as datasets become larger and scans longer. Here we developed a new dFNC pipeline, called iterative sparse kmeans or iSparse kmeans, to analyze large dFNC data without having access to huge computational power. Method In iSparse kmeans, we implement two-step clustering. In the first step, we randomly use a sub-sample dFNC data and identify several sets of states at different model orders. In the second step, we aggregate all dFNC states estimated from all iterations in the first step and use this to identify the optimum number of clusters using the elbow criteria. Additionally, we use this new reduced dataset and estimate a final set of states by performing a second kmeans clustering on the aggregated dFNC states from the first k-means clustering. To validate the reproducibility of iSparse kmeans, we analyzed four dFNC datasets from the human connectome project (HCP). Results We found that both conventional kmeans and iSparse kmeans generate similar brain dFNC states while iSparse kmeans is 27 times faster than the traditional method in finding the optimum number of clusters. We show that the results are replicated across four different datasets from HCP. Conclusion We developed a new analytic pipeline which facilitates analysis of large dFNC datasets without having access to a huge computational power source. We validated the reproducibility of the result across multiple datasets.
BibTeX
@misc{sendi2022isparse,
  author = {Mohammad S.E. Sendi and David H. Salat and Robyn L. Miller and Vince D. Calhoun},
  title = {{iSparse kmeans: a two-step clustering approach for big dynamic functional network connectivity data}},
  year = {2022},
  doi = {10.1101/2022.03.13.484193},
  howpublished = {bioRxiv},
}
Figure