On the Objective and Feature Weights of Minkowski Weighted k-Means

arXiv cs.LG / 3/30/2026

💬 OpinionSignals & Early TrendsIdeas & Deep AnalysisModels & Research

共有:

Key Points

The paper analyzes Minkowski weighted k-means (mwk-means), extending classical k-means with feature weights and a Minkowski distance, to bridge gaps in its theoretical understanding despite strong empirical performance.
It reformulates the mwk-means objective as a power-mean aggregation of within-cluster dispersions, showing that the Minkowski exponent p governs whether the method behaves more selectively or more uniformly across features.
The authors derive bounds on the objective value and characterize the learned feature-weight structure, proving weights depend on relative dispersion and follow a power-law relationship with dispersion ratios.
The resulting theory provides explicit guarantees on how high-dispersion (less reliable) features are suppressed.
The paper also establishes convergence and offers a unified theoretical interpretation of mwk-means behavior.

Abstract

The Minkowski weighted k-means (mwk-means) algorithm extends classical k-means by incorporating feature weights and a Minkowski distance. Despite its empirical success, its theoretical properties remain insufficiently understood. We show that the mwk-means objective can be expressed as a power-mean aggregation of within-cluster dispersions, with the order determined by the Minkowski exponent p. This formulation reveals how p controls the transition between selective and uniform use of features. Using this representation, we derive bounds for the objective function and characterise the structure of the feature weights, showing that they depend only on relative dispersion and follow a power-law relationship with dispersion ratios. This leads to explicit guarantees on the suppression of high-dispersion features. Finally, we establish convergence of the algorithm and provide a unified theoretical interpretation of its behaviour.