解决聚类中符号描述冗余问题，提升可解释性与效率
Enhancing Clustering: An Explainable Approach via Filtered Patterns
- 通过分析不同模式产生相同覆盖的条件，识别并消除冗余
- 减少模式搜索空间，计算效率显著提升，部分情况聚类质量更好
- 适合关注可解释聚类与知识发现的研究者
机器学习日益成为研究热点，可解释聚类（又称概念聚类）作为知识驱动的无监督学习范式，将数据划分为θ个互不重叠的簇，每个簇由显式的符号表达描述，通常为闭合模式或项集。通过提供人类可理解的簇描述，可解释聚类在可解释人工智能和知识发现中具有重要作用。近期工作通过引入k-松弛频繁模式（k-RFPs）改进聚类质量，该模式模型通过广义k覆盖定义放宽严格覆盖约束。该框架结合基于约束的推理（使用SAT求解器生成模式）与组合优化（使用整数线性规划ILP选择簇）。然而，该方法存在关键局限：多个不同的k-RFPs可能诱导相同的k覆盖，导致冗余符号表达，不必要的扩大搜索空间并增加聚类构建的计算复杂度。本文提出一种模式精简框架以解决此冗余问题。贡献有三：第一，形式化刻画不同k-RFPs产生相同k覆盖的条件，建立冗余检测的理论基础；第二，提出优化策略，对每个唯一k覆盖仅保留一个代表性模式；第三，通过分析ILP模型选择的模式对其诱导簇的鲁棒性，研究其可解释性与代表性。在多个真实数据集上的大量实验表明，所提方法显著减少模式搜索空间，提升计算效率，并在部分情况下增强聚类质量。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。