On the Objective and Feature Weights of Minkowski Weighted k-Means
This provides theoretical insights for researchers using clustering algorithms, but it is incremental as it builds on an existing method without broad new applications.
The paper tackled the lack of theoretical understanding of the Minkowski weighted k-means algorithm by showing its objective can be expressed as a power-mean aggregation, revealing how the Minkowski exponent controls feature usage, and deriving bounds, weight structures, and convergence guarantees.
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.