NVE: 一种感知可分离性和覆盖度的双聚类内部验证度量

# NVE：一种面向双聚类的可分性与覆盖度感知的内部验证指标
来源：https://arxiv.org/html/2608.29045
作者：I Navin Kumar、James C. Bezdek、Punit Rathore††注：P. Tiwari来自印度科学研究院（班加罗尔）Robert Bosch网络物理系统中心（RBCCPS）（电子邮箱：[email protected]）。I. Navin Kumar在本研究进行时隶属于RBCCPS。目前就职于Cisco India††注：J. C. Bezdek为澳大利亚墨尔本大学访问高级研究员††注：P. Rathore为印度科学研究院（班加罗尔）RBCCPS及基础设施、可持续交通与城市规划中心（CiSTUP）的助理教授。

###### 摘要

双聚类（亦称协同聚类）旨在通过同时对数据矩阵的行列进行分组来发现连贯的子矩阵。这种局部二维结构使得验证比普通聚类更具挑战性——普通聚类的内部指标通常依赖于单一共享特征空间中的紧凑性和分离性。现有流行的双聚类内部度量（如平均平方残差MSR、虚拟误差VE）主要评估双聚类内部的连贯性。尽管这些度量有用，但它们未能直接评估所提取的双聚类是否相互区分，或是否解释了数据矩阵的有意义部分。本文研究归一化虚拟误差（NVE），这是一种通过超双聚类归一化策略扩展VE的内部验证指标。通过将每个双聚类的VE与其合并其他双聚类后获得的VE进行比较，NVE引入了相对可分性和冗余性的概念。我们还研究了覆盖度调整变体NVEcov，它惩罚仅通过选择极小子矩阵来获得低误差的解。通过受控合成基准测试和酵母基因表达数据集，我们验证了NVE和NVEcov是否提供超越标准连贯性指标的信息。结果表明，NVE对冗余且分离性差的双聚类敏感，而NVEcov在低误差双聚类仅覆盖矩阵可忽略部分时改变解的排序。这些发现表明，基于NVE的度量是协同聚类内部验证的有用补充标准，尤其在需要联合考虑连贯性、可分性和覆盖度时。

###### 关键词：

双聚类、协同聚类、内部验证、聚类有效性、虚拟误差、归一化虚拟误差、平均平方残差、双聚类质量、基因表达分析。

## I 引言

双聚类（亦称协同聚类或双模聚类）适用于预期在矩形数据矩阵的两个维度上均出现有意义结构的场景。与在完整特征空间中将对象分配给簇不同，双聚类搜索行在选定列子集上表现出连贯行为的子矩阵。该框架自然适用于基因表达分析、文档-词分析、推荐系统及其他关联数据场景——在这些场景中，一组对象可能仅在有限条件或属性下相似。Cheng和Church基于残差的双聚类模型[1]以及Dhillon的二部图谱协同聚类公式[2]等基础性工作，确立了双聚类/协同聚类作为独立问题（而非普通聚类的直接扩展）的地位。后续综述强调了由此局部二维结构产生的双聚类类型、搜索策略和验证标准的多样性[3,4,5]。

评估问题与标准聚类验证相应地不同。在传统聚类中，许多内部有效性指标围绕单一共享特征空间中的紧凑性和分离性构建。若簇内点彼此接近且与其他簇的点分离良好，则视为优质簇。但对于双聚类，这种几何描述已不足够。双聚类Bk=(Ik,Jk)仅占据由行集Ik和列集Jk诱导的子矩阵；两个双聚类可能重叠、使用不同列子集或表达不同连贯模型。因此，行簇间的全局距离或全局方差分解无法直接衡量所提取子矩阵是否有意义。对双聚类而言，有用的内部验证指标必须提出更具体的问题：所报告的子矩阵是否内部连贯、相互非冗余，且规模足以解释数据矩阵的非平凡部分？

大多数广泛使用的双聚类内部度量仅解决该问题的第一部分。Cheng和Church提出的平均平方残差（MSR）评估双聚类内加性行列模型的拟合度[1]。该指标虽有用，但其解释取决于所假设的连贯模型。特别是，基于残差的评分可能惩罚在基因表达分析等应用中具有结构意义的缩放模式。虚拟误差（VE）通过将标准化行轮廓与代表双聚类平均行为的虚拟模式进行比较来克服此局限性[6]。双聚类质量度量的比较研究表明，此类度量对常数、平移、缩放及组合模式的响应可能大相径庭[7]。因此，内部连贯性并非单一通用属性；它与该度量设计捕捉的模式模型紧密相关。

即使连贯性度量适用，孤立评估每个双聚类仍存在两个重要缺陷。首先，双聚类集合可能包含冗余结构。若两个双聚类具有近乎相同的行为模式，合并它们可能不会显著降低连贯性；由重复模式构成的解不应与包含不同局部结构的解获得同等评价。其次，仅基于连贯性的标准可能偏向极小的子矩阵。小双聚类可能显得极其纯净（有时纯属数值或统计原因），但仅覆盖矩阵的可忽略部分。当参考解可用时，外部验证和基于基准的比较可解决部分问题[8,9]，统计显著性方法在选定的零模型下提供了另一种互补视角[10,11]。然而，许多实际场景需要一种可直接从数据矩阵和提取的双聚类计算的内部准则，无需真实标签或特定应用的注释。

本文研究我们提出的内部验证指标——归一化虚拟误差（NVE）及其覆盖度感知变体——是否提供此类额外的内部验证信息。出发点是认识到VE捕捉了双聚类内部一致性的行为意义形式，但其本身未将双聚类与解决方案其余部分进行比较。因此，我们将VE连贯模型与Lee等人[12]归一化平方残差框架相关的超双聚类归一化思想相结合。对于双聚类Bk，NVE将其VE与其与其他双聚类合并后获得的VE进行比较。若Bk确实独特，则这些合并的超双聚类应连贯性较低；若其冗余，则归一化将暴露其分离性不足。我们进一步考虑覆盖度调整形式NVEcov，它惩罚仅通过解释矩阵极小部分来实现低误差的解。

本文核心问题并非NVE是否应取代所有现有双聚类验证度量。我们探讨的是NVE是否贡献了标准连贯性度量（如MSR和VE）未捕捉的信息。此区分至关重要。有用的验证度量无需普遍最优；它应使解的某一属性可视化，否则该属性可能被隐藏。本例中，相关属性是行为一致性、相对可分性和覆盖度。这些属性相关但不等同，将其视为可互换可能导致关于哪个双聚类解更优的不同结论。

本文主要贡献如下：
- •将NVE表述为一种内部、算法无关的验证准则，将VE从孤立的双聚类连贯性评分扩展为通过超双聚类引入相对可分性的解级度量。
- •引入覆盖度调整变体NVEcov，以减少仅连贯性度量偏向代表性有限的、小而高度同质双聚类的倾向。
- •设计受控合成场景以隔离特定评估失败模式，包括缩放行为、冗余或重叠双聚类、小而纯净 vs. 大而含噪结构、细列退化以及覆盖度“摘樱桃”。
- •在合成基准和酵母基因表达数据集上比较MSR、VE、NVE和NVEcov，检验所提度量在实践中是否改变解排序和模型选择。

总体而言，本文将NVE定位为协同聚类的补充性内部验证度量。其目的是在保持VE所激发的模式敏感性的同时，使可分性和代表性与行为连贯性一同可见。本文余下部分将介绍必要背景、回顾相关双聚类验证工作、定义NVE和NVEcov，并在受控及真实数据实验中评估其行为。

## II 背景

### II-A 双聚类概述

双聚类（部分文献中亦称协同聚类）旨在通过同时选择行和列的子集来识别数据矩阵中的局部结构。设数据矩阵为$\widetilde{D}_{m \times n}$，其中每个元素$\widetilde{d}_{ij}$表示对象$x_i \in X=\{x_1,x_2,...,x_m\}$与特征$y_j \in Y=\{y_1,y_2,...,y_n\}$间的交互。目标是获得$K$个双聚类$\mathcal{O}=\{(O_k,F_k)\}_{k=1}^{K}$，其中$O_k \subseteq X$且$F_k \subseteq Y$定义行列子集，使得对应子矩阵$B_k=\widetilde{D}(O_k,F_k)$表现出高内部连贯性和可解释结构。

因此，每个双聚类$B_k$捕捉了在特征子集上显示连贯行为模式的对象子集。这种局部二维表示将双聚类与常规聚类区分开来——后者在完整特征空间上分组对象或沿单一轴划分。形式上，该过程可视为寻找映射$\Phi:\widetilde{D}_{m \times n} \mapsto \{B_1,B_2,...,B_K\}$，使得双聚类内相似性最大化，同时不同双聚类保持有意义的区分度。由于这种双向结构，双聚类的验证指标必须考虑行列空间间的依赖关系，而非独立评估。

双聚类和协同聚类算法已发展出多个方法学分支，每个分支反映对数据矩阵结构的不同假设。Cheng和Church[1]引入了基于残差的公式，搜索具有低平均平方残差的子矩阵；而Dhillon[2]将协同聚类建模为二部谱图划分。大平均子矩阵（LAS）[13]则采用统计视角，寻找平均信号相对于背景异常大的子矩阵。这些方法代表了对同一宽泛目标——从高维数据中恢复连贯的局部子矩阵——的互补视角：基于残差、图论和统计的观点。本文研究的验证度量是算法无关的，仅需数据矩阵和最终的双聚类集合。

### II-B 双聚类属性

双聚类验证比普通聚类更复杂，因为双聚类由行列子集共同定义。因此，双聚类的质量不能仅凭单一特征空间中的紧凑性来判断。设数据矩阵$A \in \mathbb{R}^{n \times m}$，双聚类$B_k=(I_k,J_k)$的行集$I_k \subseteq \{1,...,n\}$，列集$J_k \subseteq \{1,...,m\}$。有用的验证度量应评估诱导子矩阵是否内部连贯、其模式是否符合预期双聚类模型，以及所恢复的双聚类集合在解层面是否具有信息量。

评估双聚类解时，以下属性相关。首先，双聚类应表现出强内部连贯性，通常通过基于残差或误差的标准（如MSR和VE）衡量[1,6]。其次，该连贯性应对应适当的模式模型。根据应用不同，有意义的双聚类可能是常数、加性、乘性、保序或这些模式的组合[3,7]。第三，双聚类应具有非平凡的规模和覆盖度：极小的子矩阵可能显得高度连贯，却解释了数据矩阵的微小部分。第四，在解层面，所恢复的双聚类不应过度冗余。尽管双聚类中重叠是自然的，但反复发现几乎相同的行列结构会降低可解释性且新增信息甚少。最后，统计显著性以及对噪声或缺失值的鲁棒性也是期望特性，但通常需要额外的零模型、扰动或应用特定假设[11,5]。

本文不尝试同时优化所有这些属性。相反，它们定义了归一化虚拟误差所定位的评估景观。所提出的度量族聚焦于三个可直接从数据矩阵和提取的双聚类计算的内部维度：通过VE实现的行为连贯性、通过超双聚类比较实现的相对区分度，以及通过并集覆盖度实现的代表性。从这个意义上说，NVE和NVEcov