Glossary

K-Means Clustering

A centroid-based unsupervised learning algorithm that partitions n observations into k clusters, where each observation belongs to the cluster with the nearest mean (centroid), minimizing within-cluster variance.

Get in touch Learn more

Knowledge engineer constructing knowledge base on laptop, document hierarchy visible, casual office setup.

CENTROID-BASED PARTITIONING

What is K-Means Clustering?

K-Means clustering is a foundational unsupervised machine learning algorithm that partitions a patient population into a predefined number (k) of distinct, non-overlapping subgroups by iteratively minimizing the within-cluster sum of squared distances from each data point to its assigned cluster centroid.

The algorithm operates by first initializing k centroids randomly in the feature space. In an iterative expectation-maximization loop, each patient is assigned to the nearest centroid based on a distance metric, typically Euclidean distance. The centroid is then recomputed as the mean of all points assigned to that cluster. This process repeats until centroid positions stabilize and cluster assignments converge, effectively grouping patients with similar molecular or clinical profiles.

In patient stratification, K-Means is widely used to discover molecular subtypes from gene expression or proteomic data. The primary challenge lies in selecting the optimal k, often determined by the elbow method or silhouette score. While computationally efficient and highly interpretable, the algorithm assumes spherical cluster shapes and equal variance, making it sensitive to feature scaling and outliers in high-dimensional biomedical datasets.

ALGORITHM PROPERTIES

Key Characteristics of K-Means

K-Means clustering partitions patient populations into k pre-defined subgroups by iteratively minimizing the within-cluster sum of squares. Understanding its core characteristics is essential for valid clinical stratification.

Centroid-Based Partitioning

K-Means defines each cluster by a centroid—the arithmetic mean of all patients assigned to that group. The algorithm iteratively refines these centroids to minimize the within-cluster variance, also known as inertia. This makes K-Means a hard clustering method, assigning each patient exclusively to the nearest centroid based on a distance metric, typically Euclidean distance.

Predefined Cluster Count (k)

The number of clusters, k, must be specified a priori. This is a critical hyperparameter that directly dictates the granularity of patient stratification. Selecting an inappropriate k can obscure true biological subtypes or create artificial divisions. Common heuristics for determining k include:

Elbow Method: Plotting inertia against k to find the point of diminishing returns.
Silhouette Score: Measuring how similar a patient is to its own cluster versus others.
Gap Statistic: Comparing the total within-cluster variation for different values of k against a null reference distribution.

Spherical Cluster Assumption

K-Means implicitly assumes that clusters are isotropic (spherical) and have similar variance in all directions. The algorithm partitions the feature space using linear hyperplanes, which means it performs poorly when true patient subgroups are elongated, non-convex, or have highly unequal densities. For complex, non-linear disease trajectories, methods like DBSCAN or Gaussian Mixture Models are often more appropriate.

Sensitivity to Initialization

The final clustering result is highly sensitive to the initial placement of centroids. Poor initialization can lead to convergence on a local, suboptimal minimum. The standard mitigation strategy is the K-Means++ initialization algorithm, which spreads initial centroids across the data space probabilistically, improving both the speed and quality of convergence. Multiple random restarts (n_init) are also standard practice to select the run with the lowest inertia.

Feature Scale Dependency

K-Means relies on a distance metric, making it critically sensitive to the scale of input features. A biomarker measured in milligrams (range 0-1000) will dominate a feature measured as a percentage (range 0-1) if data is not normalized. Standardization (z-score normalization) or min-max scaling is a mandatory preprocessing step to ensure each clinical variable contributes equally to the distance calculation and resulting patient clusters.

Computational Efficiency

Lloyd's algorithm, the standard implementation of K-Means, has a time complexity of O(n * k * d * i), where n is the number of patients, k is the number of clusters, d is the number of dimensions, and i is the number of iterations. This linear relationship with the number of patients makes it highly scalable and computationally efficient for large electronic health record datasets, especially when compared to hierarchical clustering methods with quadratic complexity.

ALGORITHM SELECTION GUIDE

K-Means vs. Other Clustering Algorithms

Comparative analysis of centroid-based, density-based, hierarchical, and probabilistic clustering methods for patient stratification tasks.

Feature	K-Means	DBSCAN	Hierarchical	Gaussian Mixture
Cluster shape assumption	Spherical, equal size	Arbitrary shape	Depends on linkage	Elliptical
Predefined cluster count required
Handles noise/outliers
Soft cluster assignment
Scalability (n > 100K)
Deterministic output
Interpretability	High (centroids)	Moderate	High (dendrogram)	Moderate (covariance)
Typical runtime complexity	O(n·k·d·i)	O(n·log n)	O(n²·log n)	O(n·k·d²·i)

K-MEANS CLUSTERING

Frequently Asked Questions

Clear, technical answers to the most common questions about centroid-based patient stratification, covering initialization, distance metrics, and validation.

K-Means clustering is a centroid-based unsupervised learning algorithm that partitions a dataset into a predefined number (k) of distinct, non-overlapping subgroups. The algorithm works iteratively: first, it randomly initializes k centroids in the feature space. It then alternates between two steps—assignment, where each data point is assigned to the nearest centroid based on a distance metric (typically Euclidean), and update, where centroids are recalculated as the mean of all points assigned to them. This process repeats until convergence, defined as the point where cluster assignments no longer change or a maximum iteration limit is reached. The objective function minimized is the within-cluster sum of squares (WCSS), also known as inertia, which quantifies the compactness of the resulting clusters.

Enabling Efficiency, Speed & Accuracy

Intelligent Analysis, Decision & Execution

We build AI systems for teams that need search across company data, workflow automation across tools, or AI features inside products and internal software.

Talk to Us

Search across company data

Give teams answers from docs, tickets, runbooks, and product data with sources and permissions.

Useful when people spend too long searching or get different answers from different systems.

Enterprise searchRAGPermissions

Automate internal workflows

Use AI to route work, draft outputs, trigger actions, and keep approvals and logs in place.

Useful when repetitive work moves across multiple tools and teams.

AI agentsWorkflow automationGovernance

Add AI to products and internal tools

Build assistants, guided actions, or decision support into the software your team or customers already use.

Useful when AI needs to be part of the product, not a separate tool.

AI integrationDecision supportModel routing

FOUNDATIONAL CONCEPTS

Related Terms

Master the ecosystem of unsupervised learning and validation techniques that surround centroid-based clustering for robust patient stratification.

Unsupervised Clustering

The foundational machine learning paradigm for grouping patients based on inherent data similarities without predefined labels. Unlike supervised methods, it reveals natural disease subtypes directly from high-dimensional molecular data. Key approaches include centroid-based (K-Means), density-based (DBSCAN), and hierarchical methods, each suited to different data distributions and clinical questions.

Silhouette Score

An internal cluster validation metric measuring how similar a patient is to its own cluster compared to other clusters. Ranges from -1 to 1, where values near 1 indicate well-separated, compact clusters. Essential for determining the optimal k in K-Means by evaluating cohesion and separation simultaneously. A score below 0 suggests patients may be assigned to the wrong cluster.

Gaussian Mixture Models (GMM)

A probabilistic alternative to K-Means that assumes data points are generated from a mixture of finite Gaussian distributions. Unlike hard clustering, GMM provides soft cluster assignments—each patient receives a probability of belonging to each cluster. This captures clinical ambiguity where patients may exhibit characteristics of multiple disease subtypes simultaneously.

Consensus Clustering

A resampling-based methodology that aggregates results from multiple K-Means runs to identify robust and stable patient subgroups. By repeatedly subsampling the data and reclustering, it builds a consensus matrix showing how frequently patients co-cluster. Critical for clinical applications where reproducibility across cohorts determines translational validity.

Dimensionality Reduction

The process of reducing the number of features under consideration before clustering. Techniques like PCA, t-SNE, and UMAP project high-dimensional omics data into 2-3 dimensions for visualization. Essential preprocessing for K-Means because the algorithm suffers from the curse of dimensionality—distance metrics lose meaning in high-dimensional spaces.

Cluster Stability Analysis

A validation framework assessing the robustness of patient clusters by measuring their reproducibility under data perturbation. Methods include bootstrap resampling, noise injection, and feature subsampling. Stable clusters persist across perturbations, while unstable ones indicate overfitting. Essential for regulatory submissions where diagnostic subgroups must demonstrate analytical validity.

About the author

Prasad Kumkar

CEO & MD, Inference Systems

Prasad Kumkar is the CEO & MD of Inference Systems and writes about AI systems architecture, LLM infrastructure, model serving, evaluation, and production deployment. Over 5+ years, he has worked across computer vision models, L5 autonomous vehicle systems, and LLM research, with a focus on taking complex AI ideas into real-world engineering systems.

His work and writing cover AI systems, large language models, AI agents, multimodal systems, autonomous systems, inference optimization, RAG, evaluation, and production AI engineering.

Limited slotsGet a Free AI Consultation

How We Work

Custom AI workflows for your Business

One-fit-all AI don't work for modern businesses. At Inferensys, we aim to understand your business & custom requirements; which we use to define most efficient agentic workflows, the data, and the tools for your business.