Counterfactuals for Feature-Weighted Clustering

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Counterfactuals for Feature-Weighted Clustering

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Counterfactuals for Feature-Weighted Clustering Richard J. Fawley∗ Renato Cordeiro de Amorim† School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK.

arXiv:2607.14719v1 [cs.LG] 16 Jul 2026

Abstract 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. Software: https://github.com/rickfawley/VoICE. Keywords: Counterfactual explanations; explainable AI; weighted k-means clustering.

Introduction

dicate the minimal changes required for an applicant to change from a rejected to an approved outcome, whereas a parsimonious counterfactual explanation may indicate a minimal increase in income alone.

Explainable Artificial Intelligence (XAI) aims to improve the transparency and interpretability of machine learning models by providing insight into their outputs. Among the various explanation paradigms, counterfactual explanations have emerged as a particularly intuitive and actionable approach. Given a dataset X = {x1 , . . . , xn } with each xi ∈ X described over d features, a counterfactual explanation identifies the minimal modification to an observation xi ∈ X that changes its assigned outcome [1, 2]. This is typically formalised as finding a perturbed instance whose prediction differs from the original while remaining as close as possible under a chosen distance metric. For example, in a loan approval setting, a counterfactual explanation may in-

Explainability methods in XAI are often categorised as either global or local. Global approaches aim to summarise the overall behaviour of a model, whereas local methods focus on explaining individual predictions. Counterfactual explanations belong to the latter category, providing insight into specific outcomes by identifying the minimal changes required to alter a model’s decision. Practical counterfactual explanations are often required to satisfy additional properties, such as actionability, where only certain features may be modified, and plausibility, ensuring that generated explanations lie within realistic, datasupported regions of the feature space. 1

Clustering algorithms aim to group observations in such a way that those within the same cluster (i.e., group) are more similar to one another, according to some selected similarity measure, than those between clusters. However, not all clustering methods produce strict partitions of all available data. For example, some density-based methods allow for noise that is not explicitly allocated to any cluster, fuzzy clustering assigns to each observation a degree of membership between 0 and 1 thereby allowing multiple cluster memberships, and probabilistic mixture models assign each observation a probability distribution over clusters rather than a single hard assignment [3, 4, 5, 6]. Among clustering methods, k-means [7] is one of the most widely used [8, 9], assigning each observation to the cluster whose centre (the centroid) is the nearest. This induces a geometric structure in which cluster membership changes occur when an observation crosses a boundary between clusters. Counterfactual explanations can therefore be interpreted as minimal changes to the feature values required to cross such boundaries. Despite this geometric intuition, generating counterfactual explanations for clustering presents challenges. First, explanations may be highly sensitive near cluster boundaries, where small perturbations can lead to qualitatively different outcomes. Second, controlling the number of features involved in a counterfactual is difficult, limiting interpretability and actionability. Third, counterfactuals can lie in regions of the feature space unsupported by the observed data. These challenges are further amplified in feature-weighted clustering settings as counterfactual approaches provide no mechanism for incorporating feature importance (for details, see Section 2.1). In this paper, we introduce a method for generating counterfactual explanations for feature-weighted k-means, where each feature is assigned an independent non-negative weight. We formulate counterfactual generation as a constrained optimisation problem over the Voronoi cell (the region of space containing all points closer to a given centroid than to any other) of a target cluster, enabling explicit control over both perturbation magnitude and sparsity. Feature weights are incorporated directly into both the geometry and the optimisation objective, providing

a principled mechanism for optimising the construction of parsimonious explanations. To the best of our knowledge, counterfactual explanations have not been studied in the context of feature-weighted kmeans clustering, despite the widespread use of such algorithms. To address instability, a well documented issue in clustering under small perturbations [10, 11], we introduce a robustness-aware mechanism based on homothetic contraction, which scales a bounded target Voronoi region towards its centroid. This contraction yields a compact, empirically bounded subset of the decision region that reduces exposure to boundary-adjacent areas and removes unbounded directions. Restricting counterfactual generation to this contracted region provides explicit geometric control over boundary sensitivity and supports more locally stable explanations [12, 13]. To summarise, this paper makes the following contributions: • To the best of our knowledge, the first mechanism to incorporate feature weights directly into counterfactual explanations for clustering, shaping both the clustering geometry and the counterfactual objective; • An extension of clustering counterfactuals from pairwise source-target boundary projection to full weighted Voronoi-region projection, with counterfactual validity ensured by construction; • A constrained optimisation framework that restricts counterfactual generation to the observed data under actionability constraints, with a homothetic contraction mechanism providing explicit geometric control over robustness; • A parsimonious search procedure based on ranked actionable feature subsets and minimal intervention cardinality.

Background

This section reviews the key concepts and prior work that underpin our proposed method. We begin by discussing feature weighting in clustering and its role 2

in shaping the geometry of cluster assignments. We then examine existing approaches to counterfactual explanations in clustering, highlighting their limitations.

aim to modify the contribution of each feature to the clustering objective, typically by incorporating weights into the distance function used to define cluster assignments. Formally, they assign a non-negative weight ωv to each feature v = 1, . . . , d. Each ωv represents the degree of relevance of feature v. In this 2.1 Feature weighting in clustering work, we are concerned with the use of such weights Clustering algorithms partition a dataset X into within counterfactual generation, rather than with k clusters C1 , . . . , Ck based on a similarity or dis- the specific mechanisms by which they are estimated. tance measure. In centroid-based methods such as k-means, each cluster Cj is represented by a centroid 2.2 Counterfactual explanations mj ∈ Rd . Each observation xi ∈ X is assigned to the cluster represented by the centroid that is nearest to Optimisation-based methods have been widely xi . In the case of k-means, specifically, this minimises adopted to generate valid and diverse counterfactual explanations [2, 18]. A prominent example is d k X X X DiCE [19], which formulates counterfactual genera2 (xiv − mjv ) , W = tion as a multi-objective optimisation problem balj=1 xi ∈Cj v=1 ancing proximity to the factual instance with diversity across multiple counterfactuals. Alternative where, approaches generate counterfactuals by moving in1 X xiv . mjv = stances towards representative prototypes or along |Cj | xi ∈Cj rule-based paths, trading optimality for interpretabilThe procedure itself follows three steps: (i) select k ity [20, 21]. While such methods are flexible and observations from X uniformly at random, and copy sometimes model-agnostic, they are primarily develtheir values to m1 , . . . , mk ; (ii) for each observation oped for supervised settings and do not explicitly acxi ∈ X identify its nearest centroid mj and assign xi count for the geometric structure of clustering decito Cj ; (iii) update each centroid to the component- sion regions. There has been limited research exploring counwise mean of the observations in its cluster. These terfactual explanations in clustering settings, often steps are repeated until convergence. Although popular, k-means does have some known in distinct and largely disconnected directions. For drawbacks. For instance, its final clustering strongly instance, counterfactual analysis has been used to depends on the initial centroids (chosen at random), quantify the cost of enforcing fairness constraints in the number of clusters k must be known beforehand, k-means clustering, comparing similarity-based meaand it assumes that all features are equally relevant. sures with counterfactual-based costs of reassigning Here, we are particularly interested in the latter. In individuals between clusters [22]. This line of work many real-world datasets, only a subset of features highlights how counterfactuals can reveal asymmetcontributes meaningfully to the underlying cluster ric impacts across groups and identify features acting structure, and assigning equal importance to all fea- as proxies for sensitive attributes. tures may obscure informative patterns [14, 15]. Also, Counterfactuals for Clustering (CFCLUST) [23] is, even among relevant features there may be differ- to our knowledge, the first formal framework for genent degrees of relevance, which should be taken into erating counterfactual explanations for clustering alaccount. Feature weighting extends clustering algo- gorithms. It considers both k-means clustering and rithms to account for such heterogeneous feature rel- Gaussian mixture models, we focus on the former as evance. our proposed method is grounded in k-means (for deFeature weighting in clustering is a popular re- tails see Section 3). CFCLUST exploits the fact that search area (see [16, 14, 17, 15]). Existing approaches cluster assignments are determined by proximity to 3

3.1

centroids, so that the boundary between two clusters is given by the hyperplane equidistant from the corresponding centroids. Under this geometric formulation, the counterfactual can be obtained by projecting the factual instance onto the separating hyperplane between clusters. This framework proposes valuable practical constraints that are important in real-world settings:

Voronoi regions as target clusters

We model counterfactual generation in a featureweighted k-means scenario as an optimisation problem over the decision region of a target cluster. Here, we are not particularly interested in what exact algorithm is being used as long as it generates a feature weight vector ω = (ω1 , . . . , ωd ), where each of its components, ωv , denotes the weight associated with • Actionability constraints, modelled as binary fea- a feature v and ωv ≥ 0. With this we can define the ture masks that allow certain features to remain weighted squared Euclidean distance d immutable, reflecting attributes that cannot be X Dω (xi , mj ) = ωv (xiv − mjv )2 , changed; v=1

• Plausibility constraints, modelled as a bound- for any x ∈ X and centroid m . We can then reprei j ary penetration scalar ϵ, move the counterfac- sent the decision region of a cluster C with centroid t tual away from the source–target boundary and m as the Voronoi cell t further into the target side of the pairwise model. (ω) Vt = x ∈ Rd : Dω (x, mt ) ≤ Dω (x, mj ) ∀j ̸= t . Pairwise-boundary counterfactuals for k-means Expanding the inequalities and cancelling rely on the separating hyperplane between a source quadratic terms yields the half-space represenand target centroid. This is sufficient to describe a tation binary transition, but in multi-cluster settings it does ( \ not in general guarantee membership of the intended (ω) Vt = x : (Ω(mj − mt ))⊤ x target Voronoi cell. In this paper, we extend this j̸=t geometric perspective by considering the full Voronoi (1) ) polytope induced by multiple neighbouring centroids, 1 ⊤ ⊤ mj Ωmj − mt Ωmt , ≤ rather than a single pairwise hyperplane, and build 2 on it with additional mechanisms for robustness and interpretability. where, Ω = diag(ω1 , . . . , ωd ). Thus, the target cluster is represented by a convex polyhedral region in feature space, and counterfactual generation can be formulated as an optimisation problem over this re3 Proposed Method gion. The half-space representation in (1) involves k − 1 This section presents our proposed framework, inequalities. However, only those inequalities corVoICE, for generating counterfactual explanations responding to facet-sharing neighbours are required in a clustering setting using a feature-weighted ver(ω) sion of k-means. We begin by introducing weighted to define Vt . Rather than incurring the computaVoronoi regions as target counterfactual sets, fol- tional cost of constructing a complete diagram, the lowed by the construction of bounded feasible tar- Voronoi region of a single centroid mt can be obtained get regions and their robustness refinement via ho- by intersecting the half-spaces defined by pairwise bimothetic contraction. We then formulate counterfac- sectors with respect to a subset of relevant neighbortual generation as a constrained optimisation prob- ing clusters [24]. These neighbours can be efficiently identified using lem over these regions, before introducing parsimonious counterfactual explanations. Finally, we sum- properties of the corresponding Delaunay triangulation (the dual graph of the Voronoi diagram, in which marise our proposed method.

centroids are connected if their Voronoi cells share a boundary) [25, 26], thereby avoiding redundant comparisons with distant centroids that do not influence the cell boundary. As a result, localised Voronoi cell construction offers a computationally efficient alternative, with complexity that depends primarily on the number of effective neighbours rather than k. In the unweighted two-cluster case, with all features actionable, no contraction, and no additional bounded-domain restriction, projection onto the target Voronoi region reduces to projection onto the source–target bisector. Thus, in this special case, the proposed formulation recovers the k-means CFCLUST construction. For k > 2, VoICE extends the pairwise construction to the full target Voronoi region.

3.2

Figure 1: Homothetic contraction of a Voronoi cell. (ω) Green denotes the Voronoi region Vet , while the (ω,α) dashed blue denotes the contracted region Vet . The red points are observations in cluster Ct .

Bounded feasible target regions

(ω)

Ṽt

(ω)

= Vt

Expressing Ax ≤ b in terms of x = mt +α(y−mt ) ∈ (ω) for some y ∈ Ṽt leads to

(ω,α)

Voronoi cells in k-means clustering may be unbounded, as centroids lying on the convex hull of the configuration induce regions that extend infinitely in directions where no competing centroid is closer. As a result, these regions can include parts of the feature space that are not supported by the observed data. To reduce extrapolation beyond the observed feature ranges, we first restrict the target Voronoi cell to a bounded, empirically defined feasible domain. Let F ⊆ Rd denote a feasible region derived from observed data (i.e. feature-wise bounds). We define the bounded target region as

Ṽt

(ω,α)

Ṽt

= {x ∈ Rd : Ax ≤ (1 − α)Amt + αb},

(2)

showing the contraction scales each constraint towards the centroid mt . Figure 1 illustrates this contraction. Smaller values of α yield stronger contraction, increasing the geometric margin from decision boundaries at the cost of excluding boundaryadjacent observations, while larger values retain a greater proportion of the original Voronoi region, with α = 1 recovering the original bounded cell. For each xi ∈ Ct , define the point-wise contraction score

∩ F. (ω)

Notice that F is a polyhedron. Since Vt is also a (ω,α) (ω) αi,t = inf{α ∈ [0, 1] : xi ∈ Vet }. polyhedron by (1), their intersection Ṽt is a polyhedron and admits a half-space representation of the This score records how much of the bounded target form region must be retained in order for observation xi to (ω) d Ṽt = {x ∈ R : Ax ≤ b}. remain inside the contracted region. The cluster-level To improve robustness and reduce sensitivity near full-retention factor is then cluster boundaries, we apply a homothetic contracαt⋆ = max αi,t . tion, i.e., a uniform scaling of the region towards its xi ∈Ct centre (the cluster centroid, mt ), to this bounded region. For α ∈ (0, 1], define Thus, αt⋆ (the smallest contraction factor retaining n o all observed members of Ct ) is determined by the (ω,α) (ω) Ṽt = mt + α(x − mt ) : x ∈ Ṽt . most boundary-adjacent retained member of cluster 5

3.4

Ct , while the distribution of the point-wise scores αi,t provides a diagnostic summary of how centrally or peripherally the assigned observations lie within the bounded target region. These point-wise scores are used later as contraction diagnostics. The empirical interpretation of α depends on the metric used to construct the region. When feature weights are highly concentrated, α may describe compactness in a low-dimensional weighted subspace rather than compactness in the original feature space. We therefore report feature-weight concentration alongside α-based contraction statistics (see Section 5).

Parsimonious counterfactuals

While the optimisation problem defined in Section 3.3 identifies a feasible counterfactual explanation, practical interpretability often requires explanations that modify as few actionable features as possible. To address this requirement, our proposed framework incorporates ranked feature subsets and searches for the most parsimonious feasible counterfactual. Let Sr denote the set of the r highest-ranked actionable features, ranked in descending order of ωv , with r ≤ |A|. The set Sr represents the subset of actionable features permitted to vary during optimisation, with all remaining features fixed at their factual values. 3.3 Counterfactual optimisation (r) For a given target cluster Ct , let zt denote the Let a be a factual observation assigned to a source solution of the counterfactual optimisation problem cluster Cs , and Ct be a target cluster with t ̸= s. Let when variation is restricted to features in Sr . If A ⊆ {1, . . . , d} denote the set of actionable features. no feasible solution exists for a given r, the correWhen actionability constraints are imposed, features sponding optimisation problem is considered infeaoutside A are held fixed at their factual values. We sible. The proposed framework searches the ranked prefixes sequentially until either a feasible counterfacdenote the corresponding affine subspace by tual is obtained or all actionable prefixes have been EA (a) = {z ∈ Rd : zj = aj ∀j ∈ / A}. exhausted. That is, it starts with S1 , incrementing r until a feasible solution is found or r = |A| has been The optimisation is therefore carried out over the ⋆ tested. When at least one feasible prefix exists, this (ω,αt ) feasible target region, Vet , together with the yields the smallest actionable feature subset capable equality constraints in EA (a). of producing a valid counterfactual. This allows us To ensure uniqueness even when some feature to define the minimal intervention cardinality weights are zero or negligible, we use the regularised weighted objective (r) rt⋆ = min{r ∈ {1, . . . , |A|} | zt is feasible}. Dω,δ (a, z) = Dω (a, z) + δ∥z − a∥22 ,

δ > 0,

If no feasible prefix exists, then no parsimonious where δ is chosen small enough to act only as a nu- counterfactual is returned for the corresponding merical tie-breaker. The counterfactual for a ∈ Cs factual–target pair. with respect to target cluster Ct is then The quantity rt⋆ , when defined, represents the smallest number of ranked actionable features rezt⋆ = arg min Dω,δ (a, z). (3) quired to generate a feasible counterfactual expla⋆ e (ω,αt ) ∩EA (a) z∈V t nation with target cluster Ct . Consequently, lower values of rt⋆ correspond to more parsimonious explaThis incorporates feature weights directly into the optimisation objective while retaining a strictly con- nations, while larger values indicate that the desired cluster transition requires variation across a broader vex projection problem. If the target cluster Ct is not specified in advance, set of actionable features. The associated counterfactual, we solve (3) for each candidate target t ̸= s and select the counterfactual with minimum cost among feasible (r ⋆ ) solutions. zt⋆ = zt t , 6

is referred to as the most parsimonious counterfactual explanation. The minimal intervention cardinality provides a natural measure of explanation complexity and forms the basis of the model-level parsimony metrics introduced in Section 4.5. When the target cluster is clear from context, or when results are aggregated across sampled factual–target pairs, we write this quantity as r⋆ . Aggregated statistics such as the mean and median values of r⋆ are computed over feasible factual–target pairs and quantify the average number of ranked actionable features required to obtain feasible counterfactual explanations across a dataset.

3.5

magnitudes along the same direction, while values close to zero indicate that the minimal counterfactual lies close to a limiting boundary.

3.6

Algorithmic summary

We now summarise the proposed framework through the following algorithms.

Counterfactuals as Voronoi projections. This baseline formulation computes counterfactuals by projecting the factual observation onto the Voronoi cell of a target cluster under Euclidean distance.

Directional counterfactual ranges

The optimisation problems above identify a minimal feasible counterfactual point. However, once such a point has been found, it is also useful to characterise how far one may continue to move in the same coun- Algorithm 1 VoICE (unweighted) terfactual direction while remaining feasible. Let zt⋆ be a feasible counterfactual for factual observation a, Require: Factual observation a, source cluster Cs , centroids {m1 , . . . , mk }, optional target cluster and define the counterfactual direction index t Ensure: Counterfactual z ⋆ dt = zt⋆ − a. 1: if t is specified then For λ ≥ 0, consider the ray 2: T ← {t} 3: else zt (λ) = a + λdt . 4: T ← {1, . . . , k} \ {s} 5: end if By construction, zt (1) = zt⋆ . The admissible direc6: Initialise candidate set Z ← ∅ tional range is 7: for each t ∈ T do (ω,α⋆ t) It (a, dt ) = {λ ≥ 1 : zt (λ) ∈ Vet ∩ EA (a)}. 8: Construct Voronoi cell Vt ⋆ 9: Solve projection zt⋆ = arg minz∈Vt ∥z − a∥2 (ω,αt ) Since Vet ∩EA (a) is convex, this set is an interval 10: Add zt⋆ to Z of the form 11: end for [1, ρt ], 12: return z ⋆ = arg minz∈Z ∥z − a∥2 ⋆ (ω,α ) t whenever zt⋆ ∈ Vet ∩ EA (a). The value ρt is the largest admissible intervention magnitude along the same direction before the path exits the contracted feasible target region or violates the actionability con- Robust weighted counterfactuals. This prostraints. The associated directional tolerance is posed method extends the previous baseline by in-

corporating feature weights, restricting the search to an empirically bounded feasible domain, and improvLarger values of τt indicate that the counterfactual ing robustness through homothetic contraction of the remains feasible over a wider range of intervention target region. τt = ρt − 1.

⋆

(ω,αt ) Vet is compact and convex. The set EA (a) is an (ω,α⋆ t) affine subspace, so Vet ∩ EA (a) is also compact and convex. (ω,α⋆ t) The objective Dω,δ (a, z) is continuous on Vet ∩ ⋆ (ω,α ) t e EA (a). Since Vt ∩ EA (a) is compact and nonempty, a minimiser exists. Furthermore,

Algorithm 2 VoICE: Robust weighted counterfactuals Require: Factual observation a, source cluster Cs , centroids {m1 , . . . , mk }, feature weights ω, regularisation parameter δ > 0, feasible domain F , actionable feature set A, optional target cluster index t Ensure: Counterfactual z ⋆ or failure 1: if t is specified then 2: T ← {t} 3: else 4: T ← {1, . . . , k} \ {s} 5: end if 6: Initialise candidate set Z ← ∅ 7: for each t ∈ T do (ω) 8: Construct the weighted Voronoi cell Vt (ω) (ω) 9: Set Ṽt = Vt ∩ F (ω,α⋆ t) 10: Compute contracted region Ṽt 11: Solve projection zt⋆ = arg

Because ωv ≥ 0 for all v and δ > 0, the matrix Ω + δI is positive definite. Hence Dω,δ (a, z) is strictly convex in z. A strictly convex function has at most one minimiser over a convex set. Therefore the minimiser is unique. A parsimonious extension The proposed framework admits a natural parsimonious extension, which searches for the minimal subset of actionable features required to produce a feasible counterfactual. Starting from the single most important actionable feature, the method incrementally adds features in descending order of importance until a feasible solution is found, terminating in at most |A| steps (see Section 3.4 for details). Feature importance is determined by the non-negative weight, ωv , assigned to each actionable feature.

{Dω,δ (a, z)}.

min

(ω,α⋆ t ) ∩E

z∈Ṽt

Dω,δ (a, z) = (z − a)⊤ (Ω + δI)(z − a).

A (a)

if feasible then Add zt⋆ to Z 14: end if 15: end for 16: if Z = ∅ then 17: return failure 18: else 19: return z ⋆ = arg minzt⋆ ∈Z {Dω,δ (a, zt⋆ )} 20: end if 12: 13:

Experimental Setup

This section describes the experimental methodology we use to evaluate our proposed framework.

We now show that, for a fixed target cluster Ct , 4.1 Comparison with CFCLUST the regularised projection problem solved within AlWe compare VoICE (unweighted), described in Algorithm 2 admits a unique solution. gorithm 1, against CFCLUST (for details, see Sec(ω,α⋆ t) Proposition 1. Let Vet ∩ EA (a) ̸= ∅. Then, tion 2.2), to our knowledge the only existing framework for counterfactual explanations in k-means cluszt⋆ = arg min Dω,δ (a, z) tering. Following the original experiments introduc(ω,α⋆ ) t ∩E (a) e z∈V A t ing CFCLUST [23], we generate counterfactuals for 50 randomly selected factual observations from the admits a unique solution. source cluster, with the target cluster also selected (ω,α⋆ t) Proof. The region Vet is the intersection of at random. The underlying clustering model is unfinitely many closed half-spaces and feature-wise weighted k-means, with ranked feature restrictions bounds, followed by homothetic contraction. Hence, and α-contraction excluded, so that the comparison 8

isolates the geometric difference between the two feasible regions. For each factual observation a assigned to source cluster Cs and each selected target cluster Ct , we generated two counterfactuals under this shared setup, using the same squared Euclidean cost and no plausibility shift. The CFCLUST counterfactual was obtained by projecting a onto the pairwise bisecting hyperplane between the centroids ms and mt , while the VoICE (unweighted) counterfactual was obtained by projecting a onto the full target Voronoi cell Vt . In our experiments, we measure validity. That is, the percentage of counterfactuals lying inside the target Vt . Given VoICE (unweighted) optimises directly over Vt , its validity is guaranteed to be 100% by construction regardless of the number of clusters k. Our comparison therefore quantifies how often the CFCLUST counterfactual fails this same criterion. Where it does, we report repair cost, the squared distance from the invalid counterfactual to the corresponding valid VoICE counterfactual, measuring the extent to which CFCLUST can report an apparently lower-cost counterfactual by stopping outside the true target Voronoi region when k > 2.

4.2

based [15], or adaptive weighting schemes [28]. We evaluate three modes. In Unweighted kmeans, equal feature weights are used for clustering, ranking, and counterfactual optimisation. In Ranked k-means, k-means centroids and equal-weight Voronoi geometry are retained, but SHARK-derived weights rank features for the parsimonious search. In Ranked + weighted SHARK, SHARK weights are used throughout, for clustering, ranking, Voronoi geometry, and the counterfactual objective. Note that Unweighted k-means differs from VoICE (unweighted, Algorithm 1). The former retains the full feasibility bounds, contraction, and optimisation machinery of Algorithm 2, simply with uniform feature weights, whereas the latter omits these mechanisms entirely. Given feature weighting can alter centroid locations, Voronoi geometry, and cluster assignments, the same factual observation may be assigned to different source clusters, and the corresponding target regions may differ, across clustering formulations. Comparisons between clustering formulations should therefore be interpreted as comparisons between complete modelling pipelines, rather than as comparisons of explanation mechanisms applied to the same underlying clustering.

Clustering and weighting modes

The proposed framework operates on clustering structures induced by k-means, with feature weights optionally incorporated to reflect the relative importance of each dimension in the cluster geometry. In our experiments, weights are obtained using Shapley Reweighted k-means (SHARK) [27], which decomposes the k-means objective into per-feature withincluster dispersion contributions and assigns weights inversely related to them, down-weighting noisy or high-variance features. These weights are incorporated into the weighted distance function defined in Section 3. We adopt SHARK because it introduces no additional hyperparameters beyond those required by k-means, preserves the computational complexity of standard k-means, and aligns naturally with the geometric formulation used here. However, our framework is not restricted to SHARK. Any method producing non-negative feature weights may be used, including entropy-based [17], regularisation-

4.3

Feasibility and actionability

Counterfactual generation is constrained to a feasible region encoding plausibility and actionability. In our experiments, F is constructed using feature-wise bounds derived from the observed data, F = [min(X), max(X)], taken componentwise, which keeps counterfactuals within the empirical range of each feature and avoids extrapolation. This construction is simple and computationally efficient; alternatives such as convex hull approximations or neighbourhood-based constraints may be used depending on the application. Actionability is incorporated through binary feature masks defined by the semantic interpretation of each feature, for example holding demographic attributes such as age immutable while allowing financial attributes to vary, formally enforced via the affine constraint EA (a) from Section 3.3. For each 9

dataset we consider both fully actionable and partially constrained masks. For non-interventional datasets, such masks should be interpreted as restrictions on profile-shift explanations rather than claims about real-world recourse. For mixed-type diagnostic datasets, semantic masks are reported descriptively, but categorical and one-hot encoded variables require additional validity constraints beyond the present weighted Euclidean formulation.

4.4

Table 1: Dataset strategy used in the evaluation. Primary datasets are used for the main quantitative comparison, while diagnostic stress-test datasets are retained to analyse feature-weight concentration and mixed-type degeneracy.

Datasets

We evaluate the proposed framework using a twotier dataset strategy, summarised in Table 1 (including illustrative benchmark datasets present in the recent literature [23]). The first tier contains the primary evaluation datasets used for the main quantitative comparison. These datasets were selected because the weighted geometry remains sufficiently well behaved for the resulting counterfactuals, contraction statistics, and feature-ranking behaviour to be interpreted as properties of a meaningful multivariate clustering model. The second tier contains mixed-type diagnostic stress-test datasets. These datasets are retained to characterise failure modes of feature-weighted Euclidean geometry, particularly cases where feature weights collapse onto one or two binary or one-hot encoded indicators. The primary evaluation datasets (see Table 1) are well-understood and have low- to moderatedimensional structure. This enables qualitative analysis of Voronoi geometry, homothetic contraction, and directional counterfactual ranges. Palmer Penguins provides a similarly interpretable morphological dataset with partial cluster overlap. Breast Cancer provides a higher-dimensional numerical benchmark, making it useful for evaluating featurenormalised parsimony. Wholesale Customers provides a behavioural segmentation setting based on six annual-spending variables. Channel and Region were excluded from the clustering matrix, while Region was retained separately as the ground-truth label for external evaluation. The clustering used k = 3, corresponding to the three Region classes. Counterfactuals therefore represent changes in purchasing profiles rather than changes in geographical region or cus-

Degeneracy risk

Evaluation role: Primary Iris [29] 150 Wine [30] 178 Palmer Penguins [31] 342 Breast Cancer [32] 569 Wholesale Cust. [33]a 440

4 13 4 30 6

3 3 3 2 3

Low Low Low Low Moderate

Evaluation role: Diagnostic stress test Diabetes [34] 253,680 20 Obesity [35] 2,111 22 German Credit [36] 1,000 48 Heart Failure [37] 299 12 Student Perf. [38] 649 39

3 7 2 2 5

High High High High High

Dataset

a Channel and region were excluded from the data, while region was retained as the ground-truth label.

Table 2: Clustering-solution diagnostics for the experimental datasets. ARI is reported only where external reference labels are available and is used as an external diagnostic rather than an optimisation criterion. k-means

SHARK

Dataset

ARI

Inertia

ARI

Inertia

Iris Wine Palmer Penguins Breast Cancer Wholesale Customers

0.620 0.897 0.793 0.654 0.028

140.97 1,277.93 379.39 11,595.53 1,608.43

0.886 0.822 0.609 0.718 0.000

15.87 81.15 86.41 341.58 211.09

Diabetes Obesity German Credit Heart Failure Student Performance

0.149 0.101 0.000 -0.004 0.027

4,221,626.00 29,808.39 45,797.93 3,201.12 21,476.45

0.167 0.156 0.047 -0.005 0.036

1.90 × 10−11a 1.00 × 10−11 a 4.70 × 10−11 a 1.10 × 10−11 a 1.85 × 10−11 a

a The near-zero SHARK inertia indicates degeneracy caused by extreme feature-weight concentration, not near-perfect multivariate clustering.

tomer channel. The diagnostic stress-test datasets contain binary, ordinal, or one-hot encoded variables with direct semantic interpretation. Although such datasets are relevant to practical recourse settings, they also expose an important limitation of the present weighted

Euclidean formulation. Under SHARK weighting, several of these datasets exhibit severe feature-weight concentration, causing the effective geometry to collapse onto a single binary feature or a small categorical block. In such cases, near-zero contraction values should not be interpreted as evidence of compact multivariate cluster structure, but rather as a diagnostic indication of feature-weight degeneracy. Accordingly, primary aggregate results are reported on the first tier of datasets, with the diagnostic stress-test results reported separately in Section 5.

4.5

Evaluation metrics

Directional tolerance. We report the directional tolerance τ = ρ −1 (see Section 3.5), which quantifies the range of intervention magnitudes for which the counterfactual direction remains admissible. Contraction diagnostics. For each cluster, we report the full-retention contraction factor αt⋆ (see Section 3.2), together with the minimum, median, and maximum point-wise contraction scores αi,t . The median score helps distinguish clusters whose members are generally boundary-adjacent from clusters with only a small number of boundary-adjacent observations.

We evaluate the proposed framework using metrics designed to assess validity, feasibility, intervention cost, parsimony, directional robustness, and featureweight behaviour.

Feature-weight concentration. Because feature weights determine the weighted Voronoi geometry, we report feature-weight concentration diagnostics, including the maximum feature weight, the effective number of active features, and the dominant feature Validity. A counterfactual is considered valid if it or feature block. These diagnostics are used to idenis assigned to the intended target cluster under the tify cases where the weighted geometry collapses onto clustering function used by the corresponding mode. one or two binary or one-hot encoded indicators. Pd We report the proportion of generated counterfactuFor feature weights normalised so that j=1 ωj = als that satisfy this condition. 1, we define the effective number of active features as 1 Feasibility. We measure feasibility as the propor. deff = Pd 2 tion of sampled factual–target pairs for which a feaj=1 ωj sible counterfactual can be generated under the specThis quantity equals d under uniform normalised feaified actionability and feasibility constraints. ture weights and approaches 1 when the weighted geometry collapses onto a single feature. Distance and cost. We evaluate perturbation magnitude using the weighted squared distance Dω (a, z ⋆ ) between the factual observation a and the External clustering agreement. Where external counterfactual z ⋆ , reflecting intervention cost in the labels are available, we report the Adjusted Rand Index (ARI) as a diagnostic measure of agreement weighted feature space. between the clustering solution and the reference labels. ARI was not used to optimise centroid locaSparsity and parsimony. We evaluate explana- tions, feature weights, or counterfactuals, but it protion parsimony using two complementary measures: vides useful context when interpreting the resulting the number of feature values differing between the cluster structure. factual observation and the counterfactual (with a feature counted as changed when |zj⋆ − aj | > ε for small tolerance ε), and the minimal intervention car- 5 Results and discussion dinality r⋆ (Section 3.4). To compare datasets of different dimensionality, we additionally report the This section analyses the results of our experiments, following the sampling procedure described in Secfeature-normalised cardinality r⋆ /d. 11

Table 3: Validity (Val) of CFCLUST against unweighted, least cost Voronoi-region based counterfactuals. All results use 50 independent k-means iterations. Comparisons are factual–target pairs generated across those iterations. CFCLUST Dataset Iris Wine Palmer Penguins Breast Cancer Wholesale Customers Diabetes Obesity German Credit Heart Failure Student Performance Overall

Comparisons

VoICE

Val (%)

Repair Cost

Val (%)

Repair Cost

15,000 17,800 34,200 28,450 44,000 25,368,000 633,300 50,000 14,950 129,800

72.6 85.9 73.8 100.0 78.8 80.8 71.9 100.0 100.0 68.8

0.776 0.460 0.427 0.000 1.477 0.887 0.463 0.000 0.000 0.521

100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0

0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000

26,335,500

80.6

0.870

100.0

0.000

tion 4, repeated across all clustering modes, actionability masks, and contraction settings.

5.2

VoICE least-cost evaluation

Among invalid counterfactuals, the failureweighted mean repair cost was 0.870, and the mean relative cost underestimation was 15.18%. For Wholesale Customers, the corresponding relative underestimation was 21.86%.

we report both the raw minimal intervention cardinality r⋆ and its feature-normalised version r⋆ /d, where d is the number of features. We do so because raw cardinality can be misleading. For instance, Breast Cancer exhibits the highest mean r⋆

Table 4 summarises the performance of VoICE (Algorithm 2) across the primary evaluation datasets. Nearly all features change under its least-cost optimisation regardless of dataset (99.4–100.0%), since the 5.1 Validity comparison method is not constrained to a small feature subset. Intervention cost varies considerably across datasets, Table 3 compares pairwise bisecting-hyperplane from 0.496 (Breast Cancer) to 7.532 (Wholesale Cuscounterfactuals of CFCLUST with the VoICE untomers). Notably, directional tolerance does not folweighted (see Algorithm 1). VoICE achieves 100.0% low the same ordering as cost. Breast Cancer comvalidity by construction, since it optimises directly bines the lowest intervention cost with the highest over the target Voronoi cell. This experiment tests tolerance, whereas Wholesale Customers combines whether CFCLUST also satisfies this criterion when the highest cost with the lowest mean tolerance. This more than two clusters are present, noting that for indicates that low-cost counterfactuals are not necestwo-cluster solutions the pairwise bisector and the sarily the most robust, so cost and tolerance should target Voronoi cell coincide. be considered jointly rather than relying on either Across 26,335,500 factual–target comparisons over alone. ten datasets, CFCLUST produced 21,221,926 valid counterfactuals and 5,113,574 invalid, corresponding to pooled validity of 80.58% and a failure rate of 5.3 Parsimony evaluation 19.42%. Because Diabetes contributes a substan- Table 5 summarises the performance of VoICE’s tial majority of all comparisons, the macro-averaged most-parsimonious counterfactuals across the privalidity across datasets was also calculated and was mary evaluation datasets. To facilitate compari83.26%. son across datasets with different dimensionalities,

Table 4: VoICE (Algorithm 2) performance on the primary evaluation datasets. All features are set as actionable, and results are averaged across the three modes (Unweighted k-means, Ranked k-means, and Ranked + weighted SHARK). Feasibility was 100.0% across all datasets and modes. Dataset Iris Wine Palmer Penguins Breast Cancer Wholesale Customers

Table 6: Actionability sensitivity for mostparsimonious counterfactuals on the primary evaluation datasets. Entries show feasibility rates under increasingly restrictive random non-actionability masks, averaged across the three modes with contracted target regions.

Changed Cost Mean directional Runtime Dataset features Dω (a, z ⋆ ) tolerance (τ ) (ms) 99.8% 99.4% 100.0% 100.0% 99.4%

1.258 0.528 0.874 0.496 7.532

2.144 1.402 1.927 2.812 1.271

3.1 Iris 8.0 Wine 2.8 Palmer Penguins 9.4 Breast Cancer 3.8 Wholesale Customers

5.4 Table 5: VoICE parsimonious performance on the primary evaluation datasets. All features are set as actionable, results are averaged across the three modes (Unweighted k-means, Ranked k-means, and Ranked + weighted SHARK), and r⋆ is the minimal intervention cardinality. Feasibility was 100.0% across all datasets and modes.

Non-actionable features (%) 0% 25% 50% 75% 100.0 100.0 100.0 100.0 100.0

93.3 100.0 98.7 100.0 94.7

66.7 98.7 72.0 100.0 86.0

24.0 39.3 24.7 88.7 60.0

Contraction-based robustness

Table 7 reports αt⋆ (the smallest contraction factor retaining all observed data points in a target cluster), and the median point-wise contraction score for each dataset under both Unweighted k-means and Ranked + weighted SHARK modes of VoICE (Algorithm 2). Breast Cancer is essentially invariant to mode, with median αt⋆ changing only marginally (0.989 to 0.992), consistent with its insensitivity to Dataset Mean r ⋆ /d Single-feature Mean directional r⋆ feasibility (%) tolerance (τ ) reported in Section 5.2. Iris is the clearest exmode Iris 1.79 0.448 35.3 0.697 ception: SHARK weighting sharply reduces its minWine 3.28 0.252 8.0 0.222 imum αt⋆ (0.851 to 0.305) and its median point-wise Palmer Penguins 1.85 0.462 36.0 0.756 score (0.079 to 0.000), indicating that its target reBreast Cancer 3.88 0.129 5.3 0.099 Wholesale Customers 2.29 0.382 44.0 1.024 gions become substantially more contractible once feature weights concentrate on a small number of features. Wholesale Customers shows the highest median point-wise scores among the primary datasets but its feature-normalised cardinality is the lowest under both modes, with values of 0.274 for unamong all datasets. This indicates that relatively weighted k-means and 0.417 for ranked and weighted few of its available features are required to achieve SHARK. This indicates that its cluster members sit less centrally within their bounded target regions, a feasible cluster transition. consistent with the comparatively large intervention Table 6 reports feasibility of the most-parsimonious costs reported in Table 4. counterfactual as an increasing proportion of features are randomly set non-actionable. Feasibility degrades 5.5 Weight-concentration stress tests at different rates across datasets. Breast Cancer remains highly feasible even at 75% non-actionable Table 8 reports feature-weight concentration and features (88.7%), whereas Iris and Palmer Penguins contraction for the primary and diagnostic stressdrop sharply under the same constraint (24.0% and test datasets. The primary datasets retain multi24.7%). This loosely tracks the feature-normalised feature weighted geometries (deff from 2.53 to 26.21), whereas several diagnostic datasets collapse onto a cardinality r⋆ /d from Table 5. 13

Table 7: Contraction-based robustness for the primary evaluation datasets, where αt⋆ is the smallest contraction factor retaining all observed data points in a target cluster. Min α⋆ t

Median α⋆ t

Max α⋆ t

Median score