提出基于整数规划与启发式算法的布尔矩阵分解方法，提升可解释性与计算效率。
Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics
- 采用交替优化结合整数规划求解因子矩阵，保证精度。
- 通过多轮运行筛选最优秩一因子组合，显著降低误差。
- 设计高效C++数据结构，支持大规模数据处理，适合实际应用。
布尔矩阵分解（BMF）将给定的二值输入矩阵近似为两个较小二值因子矩阵的布尔积，利用布尔或与与运算替代标准算术运算，提升结果可解释性并减少近似误差，广泛应用于角色挖掘与计算机视觉。本文首先提出基于交替优化（AO）的BMF算法，每次子问题通过整数规划（IP）求解；随后设计多种策略，从多次运行中选择最优秩一因子子集以进一步优化。为突破IP方法的可扩展性瓶颈，引入新的贪心与局部搜索启发式算法。同时构建了一种新型C++布尔向量与矩阵数据结构，显著优于现有实现，独立具有研究价值，使启发式方法可扩展至大规模数据集。在包含主题建模与图像处理等多类真实数据集上验证了所提方法性能，并与当前最优方法对比，涵盖含缺失数据场景。
原文摘要 · Abstract (English)
Boolean matrix factorization (BMF) approximates a given binary input matrix as the product of two smaller binary factors. Unlike binary matrix factorization based on standard arithmetic, BMF employs the Boolean OR and AND operations for the matrix product, which improves interpretability and reduces the approximation error. It is also used in role mining and computer vision. In this paper, we first propose algorithms for BMF that perform alternating optimization (AO) of the factor matrices, where each subproblem is solved via integer programming (IP). We then design different approaches to further enhance AO-based algorithms by selecting an optimal subset of rank-one factors from multiple runs. To address the scalability limits of IP-based methods, we introduce new greedy and local-search heuristics. We also construct a new C++ data structure for Boolean vectors and matrices that is significantly faster than existing ones and is of independent interest, allowing our heuristics to scale to large datasets. We illustrate the performance of all our proposed methods and compare them with the state of the art on various real datasets, both with and without missing data, including applications in topic modeling and imaging.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。