Regularized K-Means Clustering
Also known as: sparse k-means, penalized k-means, regularized clustering, constrained k-means
Regularized k-means extends standard k-means by adding a penalty term — most commonly an L1 (lasso-type) or L2 constraint — to the objective function. This discourages degenerate cluster solutions and, in the sparse variant introduced by Witten and Tibshirani (2010), simultaneously selects the features that drive cluster separation, making it especially valuable in high-dimensional settings where many features are irrelevant.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use regularized k-means when you suspect that many of your features are irrelevant noise, especially in wide datasets where the number of features is large relative to observations (e.g., genomics, text, sensor arrays). It is also appropriate when you want an automatic feature-selection step integrated with clustering rather than a two-stage pipeline. Do not use it when all features are known to be informative and equally scaled — standard k-means is simpler and equally effective in that case. Avoid it when clusters are non-spherical or of very different densities; density-based methods (DBSCAN, HDBSCAN) or mixture models will fit the geometry better. Requires choosing both K (number of clusters) and lambda (regularization strength), so a validation strategy is essential.
Strengths & limitations
- Performs built-in feature selection, identifying which variables actually drive cluster structure.
- Reduces the effect of irrelevant or noisy features that distort standard k-means distances.
- Produces sparser, more interpretable cluster centroids in high-dimensional data.
- Particularly effective in genomics, text mining, and other settings where p >> n.
- The sparse k-means framework provides a principled, statistically motivated regularization criterion.
- Inherits k-means assumptions: clusters are assumed roughly spherical and similar in size.
- Requires two tuning parameters (K and lambda), increasing the complexity of model selection.
- Computationally heavier than standard k-means due to the alternating weight-update step.
- L1 regularization is not differentiable at zero, making optimization sensitive to numerical precision.
- Feature weights are global across all clusters, so a feature irrelevant for one cluster but relevant for another may be incorrectly suppressed.
Frequently asked
How do I choose the regularization parameter lambda?
Witten and Tibshirani recommend a permutation-based gap statistic: permute the data within each feature to destroy cluster structure, fit regularized k-means on the permuted data, and choose the lambda that maximizes the gap between the observed and permuted objective values. Cross-validation on silhouette or Calinski-Harabasz scores is a practical alternative.
Does regularized k-means guarantee finding the global optimum?
No. Like standard k-means, the alternating optimization converges to a local minimum. Multiple restarts with different initializations are recommended, and k-means++ initialization reduces sensitivity to starting conditions.
What is the difference between regularized k-means and sparse k-means?
Sparse k-means (Witten & Tibshirani, 2010) is the most prominent instance of regularized k-means, using an L1 penalty to shrink feature weights to exactly zero. Other regularized variants use L2 penalties (which shrink but do not zero weights), elastic net combinations, or structured penalties for grouped features.
Should I standardize features before running regularized k-means?
Yes. Without standardization, high-variance features dominate the within-cluster sum of squares, undermining the penalty's ability to select genuinely informative features. Standardizing to zero mean and unit variance before fitting is strongly recommended.
When should I prefer DBSCAN or a Gaussian mixture model over regularized k-means?
Choose DBSCAN or HDBSCAN when clusters are non-spherical, vary in density, or when noise points should be flagged rather than forced into a cluster. Choose a Gaussian mixture model when you want probabilistic cluster membership and soft assignments. Regularized k-means is best when you specifically need built-in feature selection alongside partitional clustering.
Sources
- Witten, D. M., & Tibshirani, R. (2010). A framework for feature selection in clustering. Journal of the American Statistical Association, 105(490), 713–726. DOI: 10.1198/jasa.2010.tm09415 ↗
- K-means clustering. Wikipedia. link ↗
How to cite this page
ScholarGate. (2026, June 3). Regularized K-Means Clustering. ScholarGate. https://scholargate.app/en/machine-learning/regularized-k-means
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- K-meansMachine learning↔ compare
- Regularized Gaussian Mixture ModelMachine learning↔ compare