具有聚类结构的向量的随机复杂性

# 包含聚类结构的向量的随机复杂度
来源: https://arxiv.org/html/2609.00084
Daniel Nicorici Olli Yli-Harja 单位: 信号处理研究所, 坦佩雷理工大学 P.O. Box 553, FIN-33101 Tampere, Finland 电子邮件: [email protected], [email protected] Jaakko Astola 单位: 信号处理研究所, 坦佩雷理工大学 P.O. Box 553, FIN-33101 Tampere, Finland 电子邮件: [email protected], [email protected]

最初发表于 *非线性信号与图像处理国际研讨会论文集* *（NSIP 2007）*，罗马尼亚布加勒斯特，2007年9月10-12日，第164-169页。

###### 摘要

本文研究了使用归一化最大似然（NML）模型计算包含聚类结构的编码向量的随机概率（最短码长）问题。这在基于最小描述长度（MDL）原理的数据聚类中具有重要的理论和实践意义，例如用于估计数据的最佳聚类数和最佳聚类结构。基于NML模型直接计算包含聚类结构向量的最短码长，需要相对于向量大小和聚类数的多项式时间。我们通过引入一个用于高效计算NML模型归一化常数的递归公式，证明这是一个可处理的问题。新公式的时间复杂度是线性的，与之前相对于向量大小和聚类数的多项式时间形成对比。

关键词: 最小描述长度，归一化最大似然，随机复杂度，MDL聚类，估计聚类数，寻找聚类结构。

## 1 引言

用于统计模型选择和统计推断的MDL原理基于一个简单的思想：捕捉数据中规律性特征的最佳方式是在某个特定的模型类别中构建一个允许对数据和模型本身进行最短描述的模型[1 (https://arxiv.org/html/2609.00084#bib.bib1), 2 (https://arxiv.org/html/2609.00084#bib.bib2), 3 (https://arxiv.org/html/2609.00084#bib.bib3), 4 (https://arxiv.org/html/2609.00084#bib.bib4), 5 (https://arxiv.org/html/2609.00084#bib.bib5)]。该原理选择的模型在观测数据的拟合优度与模型的“复杂度”之间进行权衡[6 (https://arxiv.org/html/2609.00084#bib.bib6)]。此外，MDL方法将模型拟合到数据，无需假设数据是来自一个“真实”随机变量的样本[3 (https://arxiv.org/html/2609.00084#bib.bib3), 5 (https://arxiv.org/html/2609.00084#bib.bib5)]。这消除了其他建模方法中的一个困难，即模型越复杂，对数据的估计就越好[3 (https://arxiv.org/html/2609.00084#bib.bib3), 4 (https://arxiv.org/html/2609.00084#bib.bib4)]。MDL原理[1 (https://arxiv.org/html/2609.00084#bib.bib1), 3 (https://arxiv.org/html/2609.00084#bib.bib3), 5 (https://arxiv.org/html/2609.00084#bib.bib5)]在渐近合理的背景下已被广泛用于统计推断[7 (https://arxiv.org/html/2609.00084#bib.bib7)]。

最近，人们发现了一种基于归一化最大似然模型的更高效的MDL原理形式，该模型通过通用充分统计量分解，将噪声与数据中的可学习信息分离[7 (https://arxiv.org/html/2609.00084#bib.bib7)]。NML模型为比较不同模型类的性能提供了比其他计算码长的方法（例如两部分码[3 (https://arxiv.org/html/2609.00084#bib.bib3), 4 (https://arxiv.org/html/2609.00084#bib.bib4), 7 (https://arxiv.org/html/2609.00084#bib.bib7)]）更好的标准。基于NML模型的随机复杂度，是给定数据在给定模型类中的最短描述长度[8 (https://arxiv.org/html/2609.00084#bib.bib8)]。

我们遵循的情景是，编码器和解码器事先就用于设计编码信息（例如包含聚类结构的向量）代码的特定模型类的NML模型达成一致。信息的最优长度在信息论中是众所周知的，并且可以通过实际的编码方法实现[7 (https://arxiv.org/html/2609.00084#bib.bib7)]。然而，我们的目标是计算编码信息的码长，而不是写出编码信息。我们根据MDL原理选择能给出最小编码信息的模型。

聚类是无监督数据分析领域的核心概念之一。在仅知道观测值而没有其他信息的情况下，基于MDL原理寻找给定数据的聚类结构和聚类数的问题被称为MDL聚类，其目标是将数据划分为若干非层次组的数据项[9 (https://arxiv.org/html/2609.00084#bib.bib9)]。MDL聚类的方法基于这样的思想：一个好的聚类是能够基于NML模型对聚类结构和数据一起进行编码，使得总码长最小化[9 (https://arxiv.org/html/2609.00084#bib.bib9)]。代表不同数据聚类方式的模型根据码长进行比较。通过选择能为数据提供最短码长的最佳模型，同时解决寻找聚类数和聚类结构的问题。

基于NML模型对包含聚类结构的向量（本研究中称为聚类向量）进行高效编码，在MDL聚类框架中至关重要。我们先前的研究[10 (https://arxiv.org/html/2609.00084#bib.bib10)]引入了一种用于编码聚类向量的高效NML模型，以及一种计算其NML码长的多项式时间方法。这已用于我们先前的工作[10 (https://arxiv.org/html/2609.00084#bib.bib10), 11 (https://arxiv.org/html/2609.00084#bib.bib11)]中，用于在微阵列实验的基因表达数据中寻找聚类数和聚类结构。先前引入的多项式时间方法（类似于Kontkanen等人[9 (https://arxiv.org/html/2609.00084#bib.bib9)]）对于大型甚至中等规模的数据集是不可行的。在本研究中，我们的主要目标是利用生成函数的性质[12 (https://arxiv.org/html/2609.00084#bib.bib12)]，推导出一种用于计算编码聚类向量的NML码长的线性时间递归方法。生成函数的性质此前已被用于寻找编码理论中出现的求和式的渐近展开[13 (https://arxiv.org/html/2609.00084#bib.bib13), 14 (https://arxiv.org/html/2609.00084#bib.bib14), 12 (https://arxiv.org/html/2609.00084#bib.bib12)]，以及计算多项式数据情况下的随机复杂度[8 (https://arxiv.org/html/2609.00084#bib.bib8)]。

第2节我们介绍符号并回顾MDL聚类。第3节介绍用于编码聚类向量的NML模型。第4节介绍生成函数的性质，第5节利用生成函数推导出计算编码聚类向量NML码长的新递归公式。最后，第6节给出结论性评述。

## 2 MDL聚类

这里我们介绍Kontkanen等人[9 (https://arxiv.org/html/2609.00084#bib.bib9)]用于数据聚类的MDL聚类方法。考虑一个由n个列向量组成的数据集 **x**^n = (**x**₁, ..., **x**_n)，其中 **x**_i = (x_{i1}, ..., x_{iq})^T，且i = 1, ..., n。数据集 **x**^n 的聚类被定义为将数据划分为互斥子集的划分，这些子集的并集构成数据集。我们用聚类向量 **y**^n = (y₁, ..., y_n)来表示聚类，其中 y_i ∈ {1, ..., m}，且 y_i = k（其中 k ∈ {1, ..., m}）当且仅当 **x**_i 属于簇 k。聚类数记为 m，其中 m = 1, ..., n。

考虑模型 M_m，编码后的数据 **x**^n 与聚类向量 **y**^n 的MDL码长（两部分码）[1 (https://arxiv.org/html/2609.00084#bib.bib1), 9 (https://arxiv.org/html/2609.00084#bib.bib9)]为：

L(**x**^n, **y**^n | M_m) = L(**y**^n | M_m) + L(**x**^n | **y**^n), (1)

其中第一项是编码聚类向量 **y**^n 的成本，最后一项是编码 **x**^n 的成本。如果数据 **x**^n 包含离散值，可以像[9 (https://arxiv.org/html/2609.00084#bib.bib9), 15 (https://arxiv.org/html/2609.00084#bib.bib15)]中那样计算其码长 L(**x**^n | **y**^n)。当数据不包含量化值时，[11 (https://arxiv.org/html/2609.00084#bib.bib11)]中的方法可用于计算 L(**x**^n | **y**^n)。

## 3 用于编码聚类向量的NML模型

在Kontkanen等人[9 (https://arxiv.org/html/2609.00084#bib.bib9)]的方法中，聚类向量 **y**^n 被编码时考虑了所有可能的长度为n的m元序列。我们对用于计算编码聚类向量 **y**^n 码长的NML模型进行了改进，更真实地考虑了聚类向量的数量。这使我们能够使用NML模型更高效地编码聚类向量，并更好地区分不同的模型。

NML方法用于编码聚类向量 **y**^n 时，假设一个简单的参数模型 P(**y**^n; Θ(**y**^n))。聚类向量 **y**^n 通常包含 h_i 个值 i，对于 **y**^n，Θ = {θ₁, ..., θ_q} 的最大似然估计为 \hat{Θ}(**y**^n) = {\hat{θ}_1(**y**^n), ..., \hat{θ}_q(**y**^n)}，其中 \hat{θ}_i(**y**^n) = h_i / n。**y**^n 的概率变为 P(**y**^n; \hat{Θ}(**y**^n)) = ∏_{i=1}^m (h_i / n)^{h_i}。已知NML模型是两个最小最大问题的解，这赋予了它强最优性性质[4 (https://arxiv.org/html/2609.00084#bib.bib4)]。归一化最大似然是

\hat{P}(**y**^n; \hat{Θ}(**y**^n)) = \frac{∏_{i=1}^m \left( \frac{h_i}{n} \right)^{h_i}}{C_n(m)}, (2)

其中

C_n(m) = \sum_{t^n ∈ \mathcal{F}^n_m} P(t^n; \hat{Θ}(t^n)), (3)

是概率 P(**y**^n; \hat{Θ}(**y**^n)) 的归一化常数，\mathcal{F}^n_m 被选择为包含所有恰好具有m个簇且彼此唯一的可能聚类向量序列 t^n。当两个聚类向量描述相同的聚类结构时，即 RAND 指数 = 1，则认为它们不唯一。RAND 指数[16 (https://arxiv.org/html/2609.00084#bib.bib16)]范围在0到1之间，它是替代数据划分（数据聚类）之间一致性的度量。

例如，当 n=4 且 m=2 时，有7个唯一聚类向量的空间 \mathcal{F}^4_2：

(1,2,2,2) (2,1,2,2) (2,2,1,2) (2,2,2,1) (1,1,2,2) (1,2,1,2) (1,2,2,1)

而不是所有14个可能的聚类向量：

(1,1,1,2) (1,1,2,1) (1,1,2,2) (1,2,1,1) (1,2,1,2) (1,2,2,1) (1,2,2,2)
(2,1,1,1) (2,1,1,2) (2,1,2,1) (2,1,2,2) (2,2,1,1) (2,2,1,2) (2,2,2,1)

它们彼此并非都唯一，例如聚类向量 (1,1,1,2) 和 (2,2,2,1) 代表相同的数据聚类方式（前三个样本聚在一起，第四个样本单独聚类），即 RAND 指数 = 1。

可以注意到，在(3)中用于编码具有m个唯一簇的聚类向量 **y**^n 的归一化常数是[10 (https://arxiv.org/html/2609.00084#bib.bib10)]，

C_n(m) = \frac{C_n^*(m)}{m!}, (4)

其中 C_n^*(m) 是NML模型的归一化常数，用于编码长度为n的m元序列，要求m字母表中的每个符号在每个序列中至少出现一次；C_n^*(m) 包含了所有可能的此类m元序列。因此，

C_n^*(m) = \sum_{\begin{subarray}{c} h_1 + \ldots + h_m = n \\ h_1, \ldots, h_m \geq 1 \end{subarray}} \frac{n!}{h_1! \ldots h_m!} \prod_{i=1}^m \left( \frac{h_i}{n} \right)^{h_i}. (5)

计算 C_n^*(m) 的一种高效方法[10 (https://arxiv.org/html/2609.00084#bib.bib10), 12 (https://arxiv.org/html/2609.00084#bib.bib12), 9 (https://arxiv.org/html/2609.00084#bib.bib9)]如下

C_n^*(m) = \sum_{i=1}^{n-1} \frac{n!}{i! (n-i)!} \left( \frac{i}{n} \right)^i \left( \frac{n-i}{n} \right)^{n-i} C_i^*(m-1), (6)

其中 C_0^*(m) = 1 且 C_n^*(1) = 1。C_n(m) 和 C_n^*(m) 的值可以预先计算并制表，以加速计算过程。

基于NML模型，具有m个簇的编码聚类向量 **y**^n 的码长（以比特为单位）是

L(**y**^n | M_m) = - \log_2 \hat{P}(**y**^n; \hat{Θ}(**y**^n)) (7)