Provable Convex Co-clustering of Tensors.
Provable Convex Co-clustering of Tensors.
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yang J
中科院分区：
文献类型：
--
作者：
Chi EC;Gaines BR;Sun WW;Zhou H;Yang J
聚类分析是复杂异构数据模式发现的基本工具。流行的聚类方法主要集中在向量或矩阵变量数据，不适用于一般阶张量，这在现代科学和商业应用中经常出现。此外，由于其非凸公式的性质，现有的张量聚类解决方案的统计保证和计算效率之间存在差距。在这项工作中，我们通过开发一个可证明的张量共聚类凸公式来弥合这一差距。我们的凸共聚类（CoCo）估计享有稳定性保证，其计算和存储成本是多项式的数据的大小。我们进一步建立了一个非渐近误差界的CoCo估计，这揭示了一个令人惊讶的“祝福的维度”的现象，不存在于向量或矩阵变量聚类分析。我们的理论研究结果得到了广泛的模拟研究的支持。最后，我们将CoCo估计应用于一家大型在线公司的广告点击张量数据的聚类分析。我们的聚类结果提供了有意义的商业见解，以提高广告效果。
Cluster analysis is a fundamental tool for pattern discovery of complex heterogeneous data. Prevalent clustering methods mainly focus on vector or matrix-variate data and are not applicable to general-order tensors, which arise frequently in modern scientific and business applications. Moreover, there is a gap between statistical guarantees and computational efficiency for existing tensor clustering solutions due to the nature of their non-convex formulations. In this work, we bridge this gap by developing a provable convex formulation of tensor co-clustering. Our convex co-clustering (CoCo) estimator enjoys stability guarantees and its computational and storage costs are polynomial in the size of the data. We further establish a non-asymptotic error bound for the CoCo estimator, which reveals a surprising “blessing of dimensionality” phenomenon that does not exist in vector or matrix-variate cluster analysis. Our theoretical findings are supported by extensive simulated studies. Finally, we apply the CoCo estimator to the cluster analysis of advertisement click tensor data from a major online company. Our clustering results provide meaningful business insights to improve advertising effectiveness.