Significance and Recovery of Block Structures in Binary Matrices with Noise
Significance and Recovery of Block Structures in Binary Matrices with Noise
复制标题
含噪声二元矩阵中块结构的意义及恢复
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
A. Nobel
中科院分区：
文献类型：
--
作者：
Xing Sun;A. Nobel
频繁项集挖掘是数据挖掘领域的核心问题之一，在数据挖掘研究中占有重要地位。一个等价的形式可以表述如下：给定一个具有二进制元素的矩形数据矩阵，找到每个具有最小列数的Is的子矩阵。本文提出了一个理论分析的几个统计问题时，这个问题的噪声存在。我们开始建立几个结果的极值行为的子矩阵的一个二元矩阵中的随机元素。这些结果提供了简单的显着性界限的输出的迭代算法。然后，我们考虑一个简单的二进制加性噪声模型下的噪声敏感性的TRONIC算法，并表明，即使在小的噪声水平，大块的是只留下对数大小的片段。因此，这样的块不能直接恢复的搜索算法，搜索所有的子矩阵。在积极的一面，我们展示了如何，在噪声的存在下，容错标准可以恢复一个正方形的子矩阵的是对背景的Os，即使当目标子矩阵的大小是非常小的。
Frequent itemset mining (FIM) is one of the core problems in the field of Data Mining and occupies a central place in its literature. One equivalent form of FIM can be stated as follows: given a rectangular data matrix with binary entries, find every submatrix of Is having a minimum number of columns. This paper presents a theoretical analysis of several statistical questions related to this problem when noise is present. We begin by establishing several results concerning the extremal behavior of submatrices of ones in a binary matrix with random entries. These results provide simple significance bounds for the output of FIM algorithms. We then consider the noise sensitivity of FIM algorithms under a simple binary additive noise model, and show that, even at small noise levels, large blocks of Is leave behind fragments of only logarithmic size. Thus such blocks cannot be directly recovered by FIM algorithms, which search for submatrices of all Is. On the positive side, we show how, in the presence of noise, an error-tolerant criterion can recover a square submatrix of Is against a background of Os, even when the size of the target submatrix is very small.