论文阅读“Discovering Multiple Co-Clu

随读摘要：
聚类是一项基本的数据探索任务，旨在发现数据中隐藏的分组结构。 传统的聚类方法通常计算单个分区。 但是，复杂数据中通常存在不同且同样有意义的聚类。 为了解决这个问题，出现了多种聚类方法，其目的是从不同角度探索替代（alternative）聚类。
现有的解决方案主要集中在单向聚类上，也就是说，它们要么对样本、要么对特征进行聚类。但是，对于许多实际任务，探索替代的双向聚类（或共聚）不仅有意义，而且可以捕获样本聚类结构，也可以捕获特征聚类结构，这是有意义且合乎需要的。
为了解决这个有趣且尚未解决的任务，我们引入了一种称为多重共集群（MultiCCs）的方法，可以同时生成多个备用共集群。 MultiCC利用矩阵三因子分解来寻找样本和特征的共聚指标矩阵，并定义行和列冗余量化项，以基于这些指标矩阵在共聚之间加强多样性。 之后，它将矩阵三因子分解和两个非冗余项集成到统一的目标函数中，并给出了用于优化目标函数的替代优化过程。 大量的实验结果表明，MultiCC的性能明显优于现有的多种聚类方法。 此外，MultiCC可以找到有趣的共同集群，而这些比较方法无法做到。

认识multiple co-clustering问题
我们平时关注的clustering，其目的是利用数据（默认单视图）的特征信息或者对象信息得到一致的聚类结果。但是，用户很难确定给定的解决方案是否确实适合当前的问题，尤其是在数据集很大且很复杂的情况下。此外，可能存在许多聚类方案，并且每个聚类解决方案都可以对数据进行有意义的划分，例如，在生物信息学中，可以针对结构或功能对蛋白质进行聚类，并且可以根据基因在不同实验条件下的表达谱对蛋白质进行聚类。
通俗点来说，在这些情况下，希望向用户呈现多个替代集群供选择，并且这些集群应该是高质量的并且彼此不同。而得到这些集群的方法和过程就是multiple clustering。

那么使用co-clustering的方式同时关注数据矩阵的行（行聚类）和列（列聚类）的信息，以获取更加全面的multiple clustering，在这篇文章中被叫做multiple co-clustering。

aims at discovering “blocks” of data with a strong correlation among its elements.

共聚可以发现嵌入在数据矩阵中的局部模式，并且已广泛应用于基因表达数据分析< Biclustering of expression data >，<It is time to apply biclustering: A comprehensive review of biclustering applications in biological and biomedical data >；协同过滤<Co-clustering on manifolds>，<An efficient non-negative matrixfactorization-based approach to collaborative filtering for recommender systems>；推荐系统<Simultaneous co-clustering and learning to address the cold start problem in recommender systems>和许多其他领域。
例如，在基因表达数据分析中，目标是揭示不同样本集之间基因的共表达模式。在进行商业推荐时，目的是向一组潜在客户推荐一套商品。

我们强调，对MultiCC的研究不同于子空间聚类<Subspace clustering by block diagonal representation>，聚类集成<Cluster ensembles: A knowledge reuse framework for combining partitions>，共聚集成<Nonparametric Bayesian co-clustering ensembles>和多视图聚类<Multi-view clustering>。子空间聚类尝试仅找到一个在不同子空间中具有不同集群的聚类，其他三个方法集中于如何得出共识（共）聚类结果，而本文重点在于如何呈现同一数据的多个不同共聚。

模型图对比

compare.png

模型第一部分构造
在论文中，模型的第一部分为基于semi-NMF的三因子分解矩阵。semi-NMF（SNMF），它将传统NMF从非负数据矩阵扩展到混合符号数据矩阵，同时仍保留了强大的聚类可解释性。

SNMF-Obj.png 在矩阵分解中，我们可以通过对索引矩阵进行聚类，完成由软聚类分配到硬聚类的转换。
由于，SNMF只能提供单向群集，发现隐藏在数据中的共同集群结构，作者关注了三因子分解矩阵。通过将矩阵分解为行矩阵和列矩阵分别捕获不同的元素数据块之间的信息。其目标函数如下：
tri SNMF-obj.png

对于给定的数据集表示，通过不断的执行三因子的矩阵分解操作，我们可以获得几个共同聚类结果。

tri-fac.png

模型第二部分构造
第二部分的目的是为了减少不同了了类簇之间的冗余度，以得到更高质量的聚类效果。

冗余度计算.png

（4）式表示索引为h的单个行指标矩阵冗余度度量方式。对于给定的m我们可以分别计算每个冗余度再进行求和，theta_r表示不同h之间的标准化因子，即为（5）式。通过关于trace操作，上述表示可以表示为矩阵运算简化整个过程，

trace opt transformer.png
为了降低两行聚类的不同数量的特征（d）和聚类（kh1和kh2）的影响。
关于列的冗余度计算也是一致。 col .png

统一目标函数

unified obj.png

优化方法：
R^h 和 C^h 都是二进制矩阵，因此很难直接最小化（9）中的统一目标函数。因此，我们将R^h 和 C^h的元素松弛为非负数值。请注意，以上等式在这种松弛条件下仍然成立。
式（9）对于R^h 、S^h和 C^h的变量不是共同凸的，因此很难找到全局最优值。受乘法更新技术的启发，我们引入了一种迭代解决方案，该解决方案可替代性地优化一个变量，同时固定其他变量以进行优化（9）。

---

评价
最近阅读的论文多是关于multiple clustering or co-clustering的。并且作者均使用了基于NMF的矩阵分解技术()与聚类结合，不仅具有很好的可解释性，并且在数学表达形式上也较为优雅。对于论文的构成有很好的效果。基础工作都是基于前人的矩阵分解技术，对于冗余度的考虑则是融入了当前工作的特色（例如：行、列矩阵分别构造冗余度度量，并与基础目标函数统一优化）。感觉是个大趋势。