基于布尔推理的二元双聚类并行化技术比较

《Symmetry》：Comparison of Parallelization Techniques for Boolean Reasoning-Based Binary Biclustering

　　

双聚类是一种二维数据分析范式，旨在识别数据矩阵中行和列的子集，其交集形成满足预定义属性的子矩阵。对于二元数据，双聚类通常定义为仅包含1或仅包含0的子矩阵。在过去的几十年中，已经提出了许多二元双聚类方法。其中，一条独特的研究路线依赖于布尔推理，将双聚类任务转化为寻找数据依赖布尔函数的主蕴含项的问题。从理论角度看，已经证明数据依赖布尔函数的每个主蕴含项对应于原始数据集中的包含–极大双聚类，反之亦然。此处，包含–极大性意味着在不违反双聚类属性的情况下，不能添加额外的行或列。对于离散数据集，相应的布尔函数可以用合取范式（Conjunctive Normal Form, CNF）表示，其中子句包含至多三个变量，将一般双聚类问题简化为3-SAT问题的一个实例。此外，离散数据双聚类的计算复杂度可以简化为二元矩阵分析。在这种情况下，关联的布尔函数由包含至多两个文字的子句组成，产生单调2-CNF公式。本文聚焦于提高计算效率，以获得仅由主蕴含项组成的析取范式（Disjunctive Normal Form, DNF）表示。由于主蕴含项提取是布尔双聚类框架的计算核心，加速这一过程直接增强了基于布尔推理的双聚类方法的可扩展性和实际适用性。

基于布尔推理的二元双聚类并行化技术研究解读

现代数据分析中的许多问题可被表示为矩阵形式，其中行对应对象、列对应属性。传统聚类基于全局相似性对行或列进行划分，但真实系统中对象之间的有意义关联往往只出现在特定的属性子集内，因此全局假设过于严格。双聚类（biclustering）同时分组行和列，能够发现仅存在于局部子矩阵中的一致模式，具有描述上下文相关关系的优势。近年来，研究者发展出基于布尔推理（Boolean reasoning）的双聚类框架，将双聚类任务转化为对数据依赖布尔函数的求解。该框架中的弱定理说明函数蕴含项与双聚类对应，强定理则保证主蕴含项（prime implicant）对应包含–极大双聚类。然而，找到全部主蕴含项需要将布尔函数从合取范式（Conjunctive Normal Form, CNF）转换为析取范式（Disjunctive Normal Form, DNF），该转换计算复杂度极高，成为整个流程的性能瓶颈。因此，本研究旨在通过并行化技术加速CNF到DNF的转换，从而提升布尔推理双聚类的可扩展性和实际适用性。论文发表于《Symmetry》。

研究人员针对上述瓶颈开展了并行化策略的比较研究。由于CNF到DNF转换本质上是子句间的反复乘法与化简，而吸收律可在乘法过程中及时缩减中间结果，他们提出了三种并行化方案：队列方法（queue approach）将待乘子句对分发给多个计算节点，结果放回队列；并行吸收方法（parallel absorption approach）在单个节点内将两个长公式的乘法分解为多个独立任务并行执行，并在合并时应用吸收律；混合方法（mixed approach）根据当前子句长度动态选择上述两种方式。实验采用三个人工二元数据集，它们是由先前研究中的离散数据二值化而来，分别记为#0、#77和#237。每个数据集与每种策略重复运行10次，统计平均计算时间和标准差。

研究结果如下：

其一，理论背景。论文在第2节系统回顾了双聚类的基本概念、经典方法，包括Cheng–Church算法、Bimax、谱方法与概率模型等；阐述了布尔推理的一般范式及其在粗糙集、决策树等领域的应用；并给出了二元数据中双聚类的布尔编码方式。对于任意二元矩阵，将每个零元素对应的行变量与列变量构成一个析取子句，所有子句的合取即为数据依赖布尔函数的CNF。弱定理和强定理保证了主蕴含项与包含–极大双聚类之间的一一对应，为后续计算提供了理论依据。

其二，布尔公式处理的性质。论文在第3节指出，在二元双聚类任务中，输入CNF的子句各自对应矩阵中不同的零元素，因此子句之间不存在集合包含关系，第一种吸收律无法对初始公式进行简化；但在子句乘法过程中，第二种吸收律可反复应用，从而减少中间子句数量。这一观察决定了并行化必须在乘法过程中同时执行化简操作。

其三，并行化的潜力。论文在第4节提出了队列方法和并行吸收方法，并说明了混合模式。通过两个DNF公式相乘的示例，研究人员展示了如何将大规模乘法分解为多个独立的小任务，同时强调合并结果后必须再次应用吸收律，以保证最终DNF仅包含主蕴含项。

其四，人工数据实验。论文在第5节报告了实验结果。数据集#77本身计算非常快，不做比较；对于数据集#0，并行化平均节省约14秒；对于数据集#237，平均计算时间从接近10分钟降至不到1分钟。相对加速程度与实验中使用的16个逻辑处理器数量相符。由于计算具有确定性，所有并行策略得到的最终主蕴含项集合与顺序处理完全一致，验证了并行化的正确性。

论文最后总结了并行化技术对于缓解CNF到DNF转换瓶颈的有效性。结论指出，通过并行化能够显著缩短布尔推理双聚类的总计算时间，并使其适用于更大规模的实际问题。未来工作将把相关软件发布为公开的Java包，核心功能为通用布尔公式处理，同时提供用户界面以直接支持基于布尔推理的双聚类应用。