Model order selection for boolean matrix factorization
Model order selection for boolean matrix factorization
复制标题
布尔矩阵分解的模型阶数选择
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Jilles Vreeken
中科院分区：
文献类型：
--
作者：
Pauli Miettinen;Jilles Vreeken
矩阵因子分解-其中给定的数据矩阵近似于两个或多个因子矩阵的乘积-是强大的数据挖掘工具。在其他任务中，矩阵分解通常用于将全局结构与噪声分离。然而，这需要解决确定细粒度结构停止和噪声开始的“模型阶数选择问题”，即，因子矩阵的合适大小是多少
布尔矩阵分解（BMF）--其中数据、因子和矩阵乘积都是布尔的--近年来受到数据挖掘界越来越多的关注。该技术具有理想的属性，如高的可解释性和自然稀疏性。但迄今为止，还没有一种方法可以为BMF选择正确的模型阶数。
在本文中，我们建议使用最小描述长度（MDL）的原则，这项任务。除了解决问题之外，这种有充分依据的方法还有许多好处，例如，它是自动的，不需要似然函数，是快速的，并且如实验所示，是高度准确的。
我们制定的描述长度函数BMF一般---使其适用于任何BMF算法。我们扩展了现有的算法BMF使用MDL来确定最好的布尔矩阵分解，分析问题的复杂性，并进行了广泛的实验评估，以研究其行为。
Matrix factorizations---where a given data matrix is approximated by a product of two or more factor matrices---are powerful data mining tools. Among other tasks, matrix factorizations are often used to separate global structure from noise. This, however, requires solving the `model order selection problem' of determining where fine-grained structure stops, and noise starts, i.e., what is the proper size of the factor matrices.
Boolean matrix factorization (BMF)---where data, factors, and matrix product are Boolean---has received increased attention from the data mining community in recent years. The technique has desirable properties, such as high interpretability and natural sparsity. But so far no method for selecting the correct model order for BMF has been available.
In this paper we propose to use the Minimum Description Length (MDL) principle for this task. Besides solving the problem, this well-founded approach has numerous benefits, e.g., it is automatic, does not require a likelihood function, is fast, and, as experiments show, is highly accurate.
We formulate the description length function for BMF in general---making it applicable for any BMF algorithm. We extend an existing algorithm for BMF to use MDL to identify the best Boolean matrix factorization, analyze the complexity of the problem, and perform an extensive experimental evaluation to study its behavior.