基于AOC-posets的关系概念分析中的收敛性问题

# 基于AOC偏序集的关系概念分析收敛性问题  
来源：https://arxiv.org/html/2609.00054  

Xavier Dolques  
Agnès Braud  
地址：斯特拉斯堡大学，ENGEES，CNRS，ICube UMR 7357，法国斯特拉斯堡，F-67000  
Alain Gutierrez  
地址：LIRMM，蒙彼利埃大学，CNRS，蒙彼利埃，法国  
Marianne Huchard  
邮箱：[[email protected]](mailto:[email protected])  
通讯作者：  
通讯作者地址：LIRMM，蒙彼利埃大学，CNRS，蒙彼利埃，法国  
Florence Le Ber  
地址：斯特拉斯堡大学，ENGEES，CNRS，ICube UMR 7357，法国斯特拉斯堡，F-67000  

###### 摘要  
形式概念分析（FCA）是一种用于概念分类构建和规则发现的方法，基于描述对象与属性二元关系的表格。为扩展处理非二元及更复杂数据，提出了关系概念分析（RCA）等方法，用于处理多关系数据。RCA旨在揭示由对象与其他对象组关系所表征的对象群体。底层数据更丰富复杂的特性使RCA能产生比FCA更丰富的结果，但计算与解释的复杂性也随之增加。FCA中最常用的概念分类结构是概念格。但在许多应用中，为规避组合爆炸或聚焦结构中信息最丰富的部分，常采用概念格的子结构（如AOC偏序集）替代完整格。在AOC偏序集中，仅表示引入对象或属性的概念，使其比概念格更小、更易计算和使用。尽管RCA最初基于概念格定义，也可在AOC偏序集上实例化。RCA具有迭代性，基于格的场景下其收敛性有保证，但使用AOC偏序集时此保证失效。本文深入探讨该收敛性丧失问题，阐明其在一般情况下无法保证的原因，识别仍能确保收敛的条件，并讨论如何转换数据集以恢复收敛。我们还提出一种保证收敛的变体流程：关系属性一旦创建即不删除，以此确保收敛，但可能引用最终结构中不存在的概念。  

###### 关键词  
形式概念分析，概念格，关系概念分析，AOC偏序集，收敛性  

## 1 引言  
形式概念分析（FCA）（Ganter and Wille, 1999）在数据分析目标不是预测而是发现和组织可解释、可理解的知识模式时提供了自然框架，符合知识表示的白盒视角（Atzmueller et al., 2024）。基于格论，FCA旨在从对象集及其属性中发现概念结构。它识别形式概念，每个概念由一组对象及其共享属性定义，并将其组织为概念格，使抽象、特化与依赖关系显式化。这与许多主流机器学习方法（包括监督学习、聚类、降维技术和神经模型）形成对比，后者通常聚焦预测精度、数值相似性或紧凑数值表示（Hastie et al., 2009; LeCun et al., 2015）。可解释AI常旨在为预测性黑盒模型提供事后解释（Guidotti et al., 2018），而FCA提供内在可解释的符号表示及数据的综合表示，通过生成显式概念结构、抽象关系和蕴含支持知识发现，供领域专家检查、解释和讨论。FCA已成功用于分析表格数据（二元或多值）（Poelmans et al., 2013a; Poelmans et al., 2013b）。后续提出了多种扩展以处理更复杂数据，如多维数据（Voutsadakis, 2002）、模糊数据（Belohlávek and Vychodil, 2005）和关系数据（Rouane-Hacène et al., 2013; Ferré and Cellier, 2020; Kötters and Eklund, 2020）。关系概念分析（RCA）（Rouane-Hacène et al., 2013）是处理关系数据的扩展之一。该框架中，对象由属性及其相互关系描述。RCA基于FCA的迭代使用，计算多个概念格，并通过抽象对象间关系的链接连接。该结果通过突出对象如何根据这些关系在每个类别中分别分类，补充了基于图模式的分析（Ferré and Cellier, 2020; Kötters and Eklund, 2020）。RCA的另一显著特征是使用了从描述逻辑借鉴的多种缩放算子（Baader et al., 2003）构建概念间链接，这与仅限于存在量词的方法（如Ferré and Cellier (2020); Kötters and Eklund (2020)）不同，能提取更丰富的模式。但由于RCA通过任意距离的对象关系对对象分组，常伴随组合爆炸，且从海量构建概念中难以提取感兴趣的模式。注意其他基于FCA的关系数据方法也存在此问题。RCA中可采用多种策略应对复杂度，包括首次分析后将初始形式对象集拆分为更小集合、引入查询（Azmeh et al., 2011b）、使用频率阈值或特定度量选择感兴趣概念（Stumme et al., 2002; Buzmakov et al., 2014; Kuznetsov and Makhalova, 2018），或使用替代概念结构（即AOC偏序集）替代概念格（Dolques et al., 2013b）。AOC偏序集是格的子序，仅限于引入对象或属性的概念（分别称为对象概念（OC）和属性概念（AC））。它们比概念格更小且计算更高效，同时保留原始信息（Godin and Mili, 1993）。在RCA中使用AOC偏序集源于对特定关系数据集的分析（如环境数据（Dolques et al., 2016; Braud et al., 2022）），我们证明该方法提供了合理数量的概念和相关规则。第二个优势是，在某些应用中，AOC偏序集中的对象概念和属性概念可能是唯一需要的输出。例如软件工程任务中的类模型重构（Miralles et al., 2015）。在此场景下，目标是从泛化关系不完整或缺失的初始类模型中推导出更通用的类。属性概念可指导构建这些泛化类，而对象概念有助于保留初始模型的类。这些实验表明，RCA-AOC在聚焦特定应用最相关模式和限制提取知识量方面具有巨大潜力。然而，为将基于AOC偏序集的RCA过程（RCA-AOC）推广到依赖不同（且可能更复杂）数据模式的其他应用，验证RCA原始特性是否保留至关重要。不幸的是，我们发现使用AOC偏序集可能引入发散问题。关键问题在于理解发散何时及为何发生，并设计消除发散或可靠利用发散结果的方法。本文通过三个涉及最广泛使用的缩放算子（即存在缩放和严格全称缩放）的示例说明过程发散的潜在风险。其中一个示例是基于UML类模型重构任务的现实应用。此外，我们识别了在大多数情况下防止发散的属性，并提出了保证终止、构建真实AOC偏序集并生成某些应用所需概念的变体流程（如本文介绍的UML类模型重构任务）。论文其余部分结构如下：第2节介绍RCA基本定义；第3节详述基于AOC偏序集的RCA过程（RCA-AOC）；第4节展示三个过程发散的示例，包括一个来自真实软件工程应用的案例；第5节讨论确保基于AOC偏序集RCA过程收敛的不同方法，包括对数据和过程本身的约束条件以及过程的收敛变体；第6节介绍AOC偏序集和RCA的现状，包括理论发展、变体和应用；最后，第7节总结论文并展望未来研究方向。  

## 2 关系概念分析简介  
本节介绍RCA过程及其结果的图形形式。定义通过CNRS Miti’80 2021 Paradise项目（Fokou et al., 2024）的示例说明。  

### 2.1 FCA基础  
RCA是形式概念分析（FCA）（Ganter and Wille, 1999）的关系变体。FCA输入称为形式背景的数据集，由对象（通过属性描述）组成。表1展示了形式背景KPlants，描述古代草药中使用的植物及其有用部分或特征。例如，草本植物当归（angelica）的叶和根可用于草药。FCA的目标是从输入数据集中提取有序概念集。  

表1：植物及其使用部分的形式背景（KPlants）  

###### 定义1（形式背景）  
形式背景是三元组K=(G,M,I)，其中G和M分别为对象和属性的有限集，I是关联关系，即I⊆G×M。  

###### 定义2（推导算子）  
设K=(G,M,I)为形式背景。两个推导算子（均记为(·)′）定义如下：对X⊆G和Y⊆M，  
X′={m∈M | ∀g∈X, (g,m)∈I}  
Y′={g∈G | ∀m∈Y, (g,m)∈I}  
X′是X中所有对象共享的属性集，Y′是拥有Y所有属性的对象集。组合两个算子得到G和M上的闭包算子(·)″。对单个对象o∈G，记{o}′和{o}″。  

###### 定义3（形式概念）  
K=(G,M,I)的形式概念是满足X′=Y且Y′=X的二元对C=(X,Y)（X⊆G，Y⊆M）。X=Extent(C)是概念的外延（概念下的对象集），Y=Intent(C)是内涵（这些对象共享的属性集）。  

###### 定义4（概念特化序与格）  
设C_K为从形式背景K构建的所有概念集。设C₁=(X₁,Y₁)和C₂=(X₂,Y₂)为C_K的两个元素。概念特化序≤ₛ定义为C₁≤ₛC₂当且仅当X₁⊆X₂（等价于Y₂⊆Y₁）。C₁称为C₂的子概念，C₂称为C₁的超概念。配备特化序的概念集(C_K, ≤ₛ)具有格结构，称为与K关联的概念格。图1展示了KPlants上构建的概念格。为减少概念格呈现中的冗余信息，图中仅显示概念引入的对象（或属性）。例如概念C_plants_8（简写为cp₈）引入属性“flowers”和对象“chamomile”。但完整概念定义为Intent(cp₈)={herbaceous, flowers}（herbaceous自上而下继承），Extent(cp₈)={chamomile, borage, garlic}（borage和garlic自下而上继承）。该呈现利用属性属于概念C的内涵时（自上而下）被C的子概念继承的特性，因此仅需在拥有该属性的最高概念中显示属性。同理，对象（自下而上继承）可对称简化。  

图1：KPlants上的概念格。每个概念分三部分表示：标识符（上部）、内涵（中部）和外延（下部）；内涵和外延中分别仅显示引入的属性和对象。文中C_plants_i简写为cpᵢ。  

### 2.2 RCA过程  
关系概念分析（RCA）旨在扩展FCA以处理对象由属性和相互关系描述的多类别数据集...