Cluster-Adaptive Feature Extraction and its Theoretical Foundation with Minkowski Weighted k-Means

Renato Cordeiro de Amorim; Vladimir Makarenkov

cs.LGMar 26, 2026

Cluster-Adaptive Feature Extraction and its Theoretical Foundation with Minkowski Weighted k-Means

Authors: Renato Cordeiro de Amorim, Vladimir Makarenkov

Organizations: School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK. · D´epartement d’informatique, Universit´e du Qu´ebec `a Montr´eal, C.P. 8888 succ. Centre-Ville, Montreal (QC) H3C 3P8 Canada. · Mila - Quebec AI Institute, Montreal, QC, Canada.

Abstract

The Minkowski weighted $k$ -means ( $mwk$ -means) algorithm extends classical $k$ -means by incorporating feature weights and a Minkowski distance. We first 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, and we establish convergence of the algorithm. Building on these theoretical results, we introduce Cluster-Adaptive Feature Extraction (CAFE), a method that uses the $mwk$ -means feature weights to rescale the data prior to unsupervised feature extraction. We prove that this rescaling reverses the within-cluster dispersion ordering, suppressing noisy features and amplifying informative ones. Numerous experiments conducted under controlled within-cluster noise show that CAFE consistently improves the results of traditional feature extraction methods.

Figures & tables

S_{l}\leftarrow\{x_{i}\in X\mid l=\arg\min_{t}d(x_{i},z_{t})\}.

Algorithm 1 Minkowski weighted

k

-means (

mwk

-means)

Figure 1: Sorted feature weights for different values of $p$ . Smaller $p$ yields sparse weight distributions, while larger $p$ produces near-uniform weights, consistent with Proposition 2 .

Figure 2: Values of the normalised objective across data sets and runs for different values of $p$ . The shaded region denotes the theoretical bounds $[0,1]$ established in Theorem 2 . All observed values lie within this interval, confirming that the objective remains within the derived bounds as $p$ varies.

p^{*}=\arg\max_{p}\sum_{q\neq p}\mathrm{ARI}\!\left(\hat{S}^{(p)},\hat{S}^{(q)}\right),

Algorithm 2 Cluster-Adaptive Feature Extraction (CAFE)

Data set	$\sigma$	Auto	UMAP	PCA	CAFE+PCA	NMF	CAFE+NMF	ICA	CAFE+ICA
AustraCC	1	$0.032\pm 0.12$	$0.175\pm 0.21$	$\underline{\mathbf{0.273}}\pm 0.24$	$0.131\pm 0.19$	$\mathbf{0.259}\pm 0.25$	$0.151\pm 0.20$	$\underline{\mathbf{0.273}}\pm 0.24$	$0.218\pm 0.24$
	2	$0.013\pm 0.05$	$0.162\pm 0.21$	$\underline{\mathbf{0.217}}\pm 0.21$	$0.126\pm 0.17$	$\mathbf{0.170}\pm 0.22$	$0.153\pm 0.20$	$\underline{\mathbf{0.217}}\pm 0.21$	$0.183\pm 0.21$
	5	$0.080\pm 0.18$	$0.195\pm 0.21$	$\mathbf{0.321}\pm 0.22$	$0.295\pm 0.26$	$0.195\pm 0.22$	$\mathbf{0.270}\pm 0.25$	$0.321\pm 0.22$	$\underline{\mathbf{0.332}}\pm 0.24$
Balance	1	$0.022\pm 0.02$	$0.038\pm 0.04$	$0.025\pm 0.03$	$\underline{\mathbf{0.061}}\pm 0.04$	$0.024\pm 0.03$	$\underline{\mathbf{0.061}}\pm 0.04$	$0.024\pm 0.02$	$\mathbf{0.049}\pm 0.04$
	2	$0.018\pm 0.02$	$0.031\pm 0.03$	$0.023\pm 0.03$	$\mathbf{0.042}\pm 0.03$	$0.029\pm 0.03$	$\mathbf{0.048}\pm 0.03$	$0.031\pm 0.03$	$\underline{\mathbf{0.056}}\pm 0.05$
	5	$0.021\pm 0.03$	$0.043\pm 0.04$	$0.025\pm 0.03$	$\mathbf{0.064}\pm 0.05$	$0.019\pm 0.03$	$\underline{\mathbf{0.072}}\pm 0.07$	$0.025\pm 0.03$	$\mathbf{0.065}\pm 0.06$

Table 1: Mean ARI

\pm

standard deviation over 20 noisy versions of the data sets for

\eta=20\%

. Bold indicates the best result within each CAFE/baseline pair. Underline indicates the best result in a row.

Data set	$\sigma$	Auto	UMAP	PCA	CAFE+PCA	NMF	CAFE+NMF	ICA	CAFE+ICA
AustraCC	1	$0.064\pm 0.14$	$0.121\pm 0.19$	$0.181\pm 0.21$	$\underline{\mathbf{0.424}}\pm 0.22$	$0.125\pm 0.20$	$\mathbf{0.266}\pm 0.21$	$0.166\pm 0.20$	$\mathbf{0.409}\pm 0.25$
	2	$0.086\pm 0.16$	$0.137\pm 0.20$	$0.199\pm 0.24$	$\underline{\mathbf{0.446}}\pm 0.22$	$0.124\pm 0.21$	$\mathbf{0.218}\pm 0.23$	$0.199\pm 0.24$	$\mathbf{0.400}\pm 0.24$
	5	$0.046\pm 0.12$	$0.126\pm 0.18$	$0.235\pm 0.24$	$\underline{\mathbf{0.492}}\pm 0.27$	$0.074\pm 0.16$	$\mathbf{0.322}\pm 0.31$	$0.235\pm 0.24$	$\mathbf{0.465}\pm 0.28$
Balance	1	$0.029\pm 0.03$	$0.018\pm 0.05$	$0.021\pm 0.03$	$\mathbf{0.075}\pm 0.09$	$0.022\pm 0.03$	$\underline{\mathbf{0.100}}\pm 0.11$	$0.022\pm 0.03$	$\mathbf{0.083}\pm 0.09$
	2	$0.018\pm 0.02$	$0.027\pm 0.04$	$0.028\pm 0.03$	$\mathbf{0.097}\pm 0.11$	$0.019\pm 0.03$	$\mathbf{0.126}\pm 0.13$	$0.023\pm 0.03$	$\underline{\mathbf{0.143}}\pm 0.17$
	5	$0.032\pm 0.03$	$0.013\pm 0.02$	$0.033\pm 0.04$	$\underline{\mathbf{0.245}}\pm 0.32$	$0.021\pm 0.03$	$\mathbf{0.144}\pm 0.20$	$0.016\pm 0.02$	$\mathbf{0.143}\pm 0.21$

Table 2: Mean ARI

\pm

standard deviation over 20 noisy versions of the data sets for

\eta=40\%

. Bold indicates the best result within each CAFE/baseline pair. Underline indicates the best result in a row.

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 345 papers

Jun 6, 2025

Scalable unsupervised feature selection via weight stability

Unsupervised feature selection is critical for improving clustering performance in high-dimensional data, where irrelevant features can obscure meaningful structure. In this work, we propose the Minkowski weighted

k

-means++, a novel initialisation strategy for the Minkowski Weighted

k

-means. Our initialisation selects centroids probabilistically using feature relevance estimates derived from the data itself. Building on this, we propose two new feature selection algorithms, FS-MWK++, which aggregates feature weights across a range of Minkowski exponents identifying stable and informative features, and SFS-MWK++, a scalable variant based on subsampling. We support our approach with a theoretical analysis, demonstrating that, under explicit assumptions on noise features and cluster structure, relevant features are assigned consistently higher weights than noise features across a range of Minkowski exponents. Our software can be found at https://github.com/xzhang4-ops1/FSMWK.

Xudong Zhang, Renato Cordeiro de Amorim

School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK.

Unsupervised Learning Clustering Unsupervised Clustering Feature Selection

Ask PDF

Aug 11, 2025

Shapley-Inspired Feature Weighting in $k$ -means with No Additional Hyperparameters

Clustering algorithms often assume all features contribute equally to the data structure, an assumption that usually fails in high-dimensional or noisy settings. Feature weighting methods can address this, but most require additional parameter tuning. We propose SHARK (Shapley Reweighted

k

-means), a feature-weighted clustering algorithm motivated by the use of Shapley values from cooperative game theory to quantify feature relevance, which requires no additional parameters beyond those in

k

-means. We prove that the

k

-means objective can be decomposed into a sum of per-feature Shapley values, providing an axiomatic foundation for unsupervised feature relevance and reducing Shapley computation from exponential to polynomial time. SHARK iteratively re-weights features by the inverse of their Shapley contribution, emphasising informative dimensions and down-weighting irrelevant ones, and is equivalent to replacing the arithmetic mean of feature dispersions with their harmonic mean. Experiments on synthetic and real-world data sets show that SHARK consistently matches or outperforms existing methods, achieving superior robustness and accuracy, particularly in scenarios where noise may be present. Software: https://github.com/rickfawley/SHARK.

Richard J. Fawley, Renato Cordeiro de Amorim

School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK.

Clustering Unsupervised Clustering

Ask PDF

Jul 16, 2026

Counterfactuals for Feature-Weighted Clustering

Counterfactual explanations provide local, interpretable insight by identifying changes to an input that would alter its assigned outcome. Although well established in supervised learning, their extension to clustering is less direct, since cluster assignments are unlabeled and governed by the geometry of the partition. This paper introduces VoICE, a Voronoi-Induced Counterfactual Explainability framework for feature-weighted

k

-means clustering. Rather than treating cluster change as a crossing of a single pairwise centroid boundary, VoICE formulates counterfactual generation as projection onto the full weighted Voronoi region of a target cluster, incorporating feature weights directly into both the clustering geometry and the counterfactual objective to yield least-cost and parsimonious explanations under actionability constraints. Target regions are further intersected with data-derived bounds and homothetically contracted towards their centroids, limiting extrapolation and boundary sensitivity. VoICE consistently produces valid target-cluster membership, across several benchmark datasets, where the leading pairwise baseline does not.

Richard J. Fawley, Renato Cordeiro de Amorim

School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK.

Counterfactual Explanations Clustering

Ask PDF

Abstract

Clustering

Explore similar work

Scalable unsupervised feature selection via weight stability

Shapley-Inspired Feature Weighting in kkk-means with No Additional Hyperparameters

Counterfactuals for Feature-Weighted Clustering

Shapley-Inspired Feature Weighting in $k$ -means with No Additional Hyperparameters