Enhancing Clustering: An Explainable Approach via Filtered Patterns

Motaz Ben Hassine; Saïd Jabbour

cs.AIApr 14, 2026

Enhancing Clustering: An Explainable Approach via Filtered Patterns

Authors: Motaz Ben Hassine, Saïd Jabbour

Organizations: CRIL · CRIL, University of Artois & CNRS, Lens, France

Abstract

Machine learning has become a central research area, with increasing attention devoted to explainable clustering, also known as conceptual clustering, which is a knowledge-driven unsupervised learning paradigm that partitions data into $θ$ disjoint clusters, where each cluster is described by an explicit symbolic representation, typically expressed as a closed pattern or itemset. By providing human-interpretable cluster descriptions, explainable clustering plays an important role in explainable artificial intelligence and knowledge discovery. Recent work improved clustering quality by introducing k-relaxed frequent patterns (k-RFPs), a pattern model that relaxes strict coverage constraints through a generalized kcover definition. This framework integrates constraint-based reasoning, using SAT solvers for pattern generation, with combinatorial optimization, using Integer Linear Programming (ILP) for cluster selection. Despite its effectiveness, this approach suffers from a critical limitation: multiple distinct k-RFPs may induce identical k-covers, leading to redundant symbolic representations that unnecessarily enlarge the search space and increase computational complexity during cluster construction. In this paper, we address this redundancy through a pattern reduction framework. Our contributions are threefold. First, we formally characterize the conditions under which distinct k-RFPs induce identical kcovers, providing theoretical foundations for redundancy detection. Second, we propose an optimization strategy that removes redundant patterns by retaining a single representative pattern for each distinct k-cover. Third, we investigate the interpretability and representativeness of the patterns selected by the ILP model by analyzing their robustness with respect to their induced clusters. Extensive experiments conducted on several real-world datasets demonstrate that the proposed approach significantly reduces the pattern search space, improves computational efficiency, preserves and enhances in some cases the quality of the resulting clusters.

Figures & tables

Transactions	Items
$\tau_{1}$	$a$	$b$	$c$		$e$
$\tau_{2}$					$e$	$f$
$\tau_{3}$	$a$	$b$		$d$				$h$
$\tau_{4}$							$g$	$h$

Table 1: An illustrative dataset

\mathcal{D}

Transactions	Items
$\tau_{1}$	$a$	$b$	$c$	$e$
$\tau_{2}$	$a$	$b$	$c$		$f$
$\tau_{3}$	$a$	$b$	$c$			$g$
$\tau_{4}$	$a$						$h$	$i$
$\tau_{5}$	$a$						$h$	$i$	$j$

Table 2: A representative dataset

\mathcal{D}

Panel of Figure 1 — Figure 1: Conceptual clustering approach: main steps

Panel of Figure 2 — Figure 2: Optimized Conceptual clustering approach: main steps

Dataset	$\|\mathcal{D}\|$	$\|\mathcal{U}\|$	$d$ (%)
Lymph	148	68	40
Mushroom	8124	119	18
Primary-Tumor	336	31	48
Soybean	630	50	32
Tic-tac-toe	958	27	33
Vote	435	48	33

Table 3: Real-world datasets

$\mathcal{D}$	$\alpha$	$\|\mathcal{A}\|$	$\|\mathcal{A}_{f}\|$	$\Delta\;(\%)$
Lymph	$10\%$	3605378	3349874	7.09
	$20\%$	759630	719877	5.23
	$30\%$	202602	190791	5.83
	$40\%$	60470	55449	8.3
Mushroom	$10\%$	128962	118226	8.32
	$20\%$	19712	18176	7.79

Table 4: Comparison of the number of patterns before and after filtering.

$\mathcal{D}$	$\alpha$	CCA- $k$ -RFP-M1			OCCM
$\mathcal{D}$	$\alpha$	$\|\mathcal{A}\|$	F1-score	CPU time	$\|\mathcal{A}_{f}\|$	F1-score	CPU time
Lymph	$37\%$	91888	0.71	49.66	85470	0.71	29.74
Mushroom	$20\%$	19712	0.34	3133.34	18176	0.73	1144.46
Primary-Tumor	$25\%$	45465	0.25	55.88	45250	0.33	55.71
Soybean	$20\%$	11900	0.29	18.29	11664	0.29	16.99
Tic-tac-toe	$10\%$	811	-	-	786	-	-

Table 5: OCCM vs. CCA-

k

-RFP-M1.

$\mathcal{D}$	Pattern size	SVV	ACS
Lymph	$\|\mathcal{I}_{1}\|=4$	48.89	0.84
Lymph	$\|\mathcal{I}_{2}\|=13$	2.22	0.95
Mushroom	$\|\mathcal{I}_{1}\|=5$	146486.32	0.84
Mushroom	$\|\mathcal{I}_{2}\|=8$	27367.52	0.86
Primary-Tumor	$\|\mathcal{I}_{1}\|=2$	12.5	0.53
Primary-Tumor	$\|\mathcal{I}_{2}\|=4$	319.02	0.75

Table 6: Pattern size, SVV, and ACS values for each dataset.

Figure 3: Correlation between Shapley Value Variance (SVV) and Average Cluster Stability (ACS).

Figure 4: Influence of Pattern Size on Cluster Stability.

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

Aug 6, 2026

Beyond Feature Importance: A Comparative Analysis of Pattern Detection Methods in Cluster Interpretation

Interpreting clustering outcomes remains a fundamental challenge in data analysis, particularly in domains such as healthcare where meaningful patterns must be extracted from high-dimensional data. While numerous explainability techniques exist, they are primarily designed to assess feature importance or provide local instance-level explanations rather than to identify structured patterns present within clusters. This work presents a comparative evaluation of commonly used post-hoc analysis methods for pattern detection in clustering results. To enable controlled evaluation, we introduce a suite of synthetic datasets in which predefined patterns are systematically injected. Three widely used techniques are evaluated: a Random Forest surrogate model with permutation feature importance, LIME (Local Interpretable Model-agnostic Explanations), and principal component analysis. Results demonstrate that although each method can successfully recover relevant features, none consistently detects all injected pattern types. These findings high- light a critical gap between existing explainability tools and the requirements of pattern-level cluster interpretation, motivating the development of dedicated pattern detection methodologies.

Benjamin Connor, Anna Jurek-Loughrey, Lu Bai +1

School of EEECS Queen’s University Belfast 18 Malone Road, Belfast, BT9 5AF

Clustering Unsupervised Clustering Explainability Evaluation

Ask PDF

May 28, 2026

ExDBSCAN: Explaining DBSCAN with Counterfactual Reasoning -- Additional Material

Clustering is an unsupervised technique for grouping data points by similarity. While explainability methods exist for supervised machine learning, they are not directly applicable to clustering, making it challenging to understand cluster assignments. This interpretability gap is particularly evident in the popular density-based method DBSCAN, which assigns points as inliers (cluster members in dense regions) or outliers (noise points in sparse regions). DBSCAN does not provide insight into why a particular point receives its assignment or whether its assignment is robust to small changes in the data. To address the lack of explainability, we introduce ExDBSCAN, a density-aware, post-hoc explanation method. ExDBSCAN offers actionable counterfactual explanations, with theoretical guarantees for validity. It generates multiple counterfactuals using a density connected weighted graph, adopting a physics-inspired model that repels counterfactual candidates from one another (diversity), while pulling them toward the instance to explain (proximity). Empirical evaluation on 30 tabular datasets comparing against four baselines shows that ExDBSCAN outperforms all baselines while attaining perfect validity and retrieving diverse, proximal counterfactuals.

Pernille Matthews, Lena Krieger, Tommaso Amico +3

LMU Munich, DBS, MCML Munich, Germany

Explainable Artificial Intelligence Counterfactual Explanations Clustering Unsupervised Clustering Density-Based Clustering

Ask PDF

Mar 20, 2026

Explainable cluster analysis: a bagging approach

A major limitation of clustering approaches is their lack of explainability: methods rarely provide insight into which features drive the grouping of similar observations. To address this limitation, we propose an ensemble-based clustering framework that integrates bagging and feature dropout to generate feature importance scores, in analogy with feature importance mechanisms in supervised random forests. By leveraging multiple bootstrap resampling schemes and aggregating the resulting partitions, the method improves stability and robustness of the cluster definition, particularly in small-sample or noisy settings. Feature importance is assessed through an information-theoretic approach: at each step, the mutual information between each feature and the estimated cluster labels is computed and weighted by a measure of clustering validity to emphasize well-formed partitions, before being aggregated into a final score. The method outputs both a consensus partition and a corresponding measure of feature importance, enabling a unified interpretation of clustering structure and variable relevance. Its effectiveness is demonstrated on multiple simulated and real-world datasets.

Federico Maria Quetti, Elena Ballante, Silvia Figini +1

Department of Mathematics, University of Pavia, Pavia, 27100, Italy. · Department of Social and Political Sciences, University of Pavia, Pavia, 27100, Italy. · Department of Economics and Management, University of Pavia, Pavia, 27100, Italy.

Clustering Unsupervised Clustering

Ask PDF

Abstract

Clustering

Explore similar work

Beyond Feature Importance: A Comparative Analysis of Pattern Detection Methods in Cluster Interpretation

ExDBSCAN: Explaining DBSCAN with Counterfactual Reasoning -- Additional Material

Explainable cluster analysis: a bagging approach