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

Scalable unsupervised feature selection via weight stability
Jun 6, 2025Xudong Zhang, Renato Cordeiro de AmorimUnsupervised Learning Clustering
School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK.
Shapley-Inspired Feature Weighting in $k$ -means with No Additional Hyperparameters
Aug 11, 2025Richard J. Fawley, Renato Cordeiro de AmorimClustering Unsupervised Clustering
School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK.
Counterfactuals for Feature-Weighted Clustering
Jul 16, 2026Richard J. Fawley, Renato Cordeiro de AmorimCounterfactual Explanations Clustering
School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK.

Jun 6, 2025J/K move · Enter open · S save

Scalable unsupervised feature selection via weight stability

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

Open paper AskPDF arXiv

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.

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