Jointly clustering rows and columns of binary matrices: algorithms and trade-offs
Jointly clustering rows and columns of binary matrices: algorithms and trade-offs
复制标题
对二元矩阵的行和列进行联合聚类：算法和权衡
DOI：
10.1145/2591971.2592005
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Lei Ying
中科院分区：
文献类型：
--
作者：
Jiaming Xu;Rui Wu;Kai Zhu;B. Hajek;R. Srikant;Lei Ying
在标准聚类问题中，数据点用向量表示，通过将它们堆叠在一起，形成具有行或列聚类结构的数据矩阵。在本文中，我们考虑一类二进制矩阵，出现在许多应用中，表现出行和列集群结构，我们的目标是通过观察只有一小部分的噪声条目，以准确地恢复底层的行和列集群。首先，我们推导出一个下界的最小数目的观察所需的确切的集群恢复。然后，我们研究了三种不同运行时间的算法，并比较了它们成功恢复聚类所需的观测数。我们的分析结果表明，平滑的时间-数据权衡：当越来越多的观测数据可用时，可以逐渐降低计算复杂度。
In standard clustering problems, data points are represented by vectors, and by stacking them together, one forms a data matrix with row or column cluster structure. In this paper, we consider a class of binary matrices, arising in many applications, which exhibit both row and column cluster structure, and our goal is to exactly recover the underlying row and column clusters by observing only a small fraction of noisy entries. We first derive a lower bound on the minimum number of observations needed for exact cluster recovery. Then, we study three algorithms with different running time and compare the number of observations needed by them for successful cluster recovery. Our analytical results show smooth time-data trade offs: one can gradually reduce the computational complexity when increasingly more observations are available.