寻求基于属性集生成最少子组以重构原分组的算法

原始元素-分组映射数据 #

{
    1: [A, B, C],
    2: [A, B, C],
    3: [A, B, C],
    4: [A, B],
    5: [A, B],
    6: [A, B],
    7: [A],
    8: [A],
    9: [A],
    10: [A],
    11: [C, D],
    12: [C, D],
    13: [C, D],
    14: [C, D],
    15: [A, B, D],
    16: [A, B, D],
    17: [A, B, D],
    18: [A, B, D],
}

现有分组构成 #

A consists of [1,2,3,4,5,6,7,8,9,10,15,16,17,18]
B consists of [1,2,3,4,5,6,15,16,17,18]
C consists of [1,2,3,11,12,13,14]
D consists of [11,12,13,14,15,16,17,18]

核心需求 #

找到数量最少的子组（示例如下），用子组重构原有分组：

SG_1 [1,2,3]
SG_2 [4,5,6]
SG_3 [15,16,17,18]
SG_4 [11,12,13,14]
SG_5 [7,8,9,10]

重构后分组示例：

A consists of [SG_1, SG_2, SG_5, SG_3]
B consists of [SG_1, SG_2, SG_3]
C consists of [SG_1, SG_4]
D consists of [SG_4, SG_3]

这个问题本质是二进制矩阵的最小行聚类/最小集合基构建，可关联以下方向：

• 形式概念分析（Formal Concept Analysis, FCA）：子组对应FCA中的"外延"，每个子组内的元素共享完全相同的"内涵"（即所属的分组集合）。通过FCA可直接提取所有等价元素组，这些组就是最小子组集合，因为组内元素的分组归属完全一致，无法再合并。
• 集合等价类划分：将每个原始元素的分组归属视为特征向量，把特征向量完全相同的元素划分为一个子组。这种划分得到的子组数量是理论最小值，任何合并都会导致子组内元素特征向量不一致，无法准确重构原有分组。
• 二元矩阵分解：把原始的元素-分组关联矩阵分解为最少的子矩阵（每个子矩阵的行具有相同列取值），每个子矩阵对应一个子组，属于矩阵分解中的最小块分解问题。

具体操作步骤：

1. 为每个原始元素生成唯一的分组特征标识（比如元素1的标识是ABC，元素11的标识是CD）；
2. 将所有具有相同特征标识的元素归为同一个子组；
3. 用这些子组重新组合成原有分组即可。

内容的提问来源于stack exchange，提问作者Martin S.