5. 带约束的概率半监督聚类

在某些聚类任务中，可以以成对约束的形式获得有限的监督，即标记为属于相同或不同簇的实例对。由此产生的问题称为半监督聚类（semi-supervised clustering），这是一个源于传统的无监督学习环境的半监督学习实例。利用约束形式的监督提高聚类质量的算法有多种。这些算法通常利用成对约束来修改聚类目标函数或学习聚类失真度量。本章介绍了一种将隐马尔可夫随机域（HMRFS）作为半监督聚类的概率生成模型的方法，从而为将基于约束的监督纳入基于原型的聚类提供了一个原则性框架。基于HMRF的模型允许使用广泛的聚类失真度量，包括Bregman发散（例如，平方欧几里得距离、Kullback-Leibler发散）和方向距离度量（例如，余弦距离），使其适用于许多领域。该模型引入了HMRF-kmeans算法，该算法将从模型的联合概率中导出的目标函数最小化，并允许统一基于约束和基于距离的半监督聚类方法。此外，在查询驱动框架中选择信息性成对约束的两阶段主动学习算法是从HMRF模型中派生出来的，这有助于提高集群性能，同时用户的监督相对较少。

5.1 简介

本章主要研究带约束的半监督聚类，即当以成对约束的形式提供有限监督时，将一组数据点划分成特定数量的簇的问题。虽然传统上认为聚类是无监督学习的一种形式，因为没有给出类标签，但包含成对约束使其成为半监督学习任务，无监督聚类算法的性能可以使用有限的训练数据得到改善。

成对监督通常作为必须链接和不能链接数据点上的约束提供：必须链接约束表示对中的两个点应放置在同一个簇中，而不能链接约束表示对中的两个点应属于不同的簇。斯特斯。或者，必须链接和不能链接约束有时分别称为等价约束和非等价约束。通常，约束是“软”的，也就是说，违反约束的集群是不可取的，但不是禁止的。

在某些应用中，类标签形式的监督可能不可用，同时很容易获得成对的约束，从而需要利用此类监督的方法。例如，完整的类标签可能在对话中的说话人识别聚类（Bar Hillel等人，2003）或车道搜索的GPS数据聚类（Wagstaff等人，2001）中是未知的。在某些领域，成对约束自然发生，例如，生物学中的相互作用蛋白质（DIP）数据库数据集包含有关过程中共同发生的蛋白质的信息，可以看作是在聚类过程中必须链接的约束。此外，在交互式学习设置中，非领域专家的用户有时可以以“必须链接”的形式提供反馈，并且不能比类标签更容易地链接约束，因为提供约束并不要求用户对数据集中的类别具有重要的先验知识。

提出的半监督聚类方法分为两类，即基于约束和基于距离。基于约束的方法使用提供的监督来指导算法进行避免违反约束的数据分区（Demiriz等人，1999；Wagstaff等人，2001；Basu等人，2002）。在基于距离的方法中，使用了一种使用点之间特定距离函数的现有聚类算法；但是，距离函数是参数化的，并且学习了参数值，将必须链接的点集合在一起，并使不能链接的点进一步分离（Bilenko和Mooney，2003；Cohn等人，2003；Klein等人，2002年；Xing等人，2003年）。

本章描述了一种基于隐马尔可夫随机域（HMRFS）的半监督聚类方法，该方法将基于约束和基于距离的方法结合在一个统一的概率模型中。概率公式导致从观测数据点的联合概率、它们的聚类分配和生成模型参数中导出一个聚类目标函数，该目标函数可以使用期望最大化（em）型聚类算法进行优化。hmrf kmeans，即找到目标函数的局部最小值。HMRF-kmeans可用于使用广泛的畸变（距离）函数（1，即Bregman发散）执行半监督聚类（Banerjee等人，2005b），其中包括各种有用距离，例如kl发散、平方欧几里得距离、i发散和Itakuro-s。A到距离。在许多应用中，例如基于向量空间模型的文本聚类，基于向量间角度余弦的方向距离测量更为合适（Baeza Yates和Ribeiro Neto，1999）。已经开发出聚类算法，利用适合方向数据的畸变测量（Dhillon和Modha，2001；Banerjee等人，2005 a），并且HMRF-kmeans框架自然地扩展了它们。

带有约束的半监督集群的一个实际方面是如何在现实环境中获得最大程度的信息约束，在这种环境中，可以在交互式学习环境中向用户发出有限的查询集（McCallum和Nigam，1998年b）。在这种情况下，应该向用户提出较少的查询，以获得能够显著提高聚类准确性的约束。为此，本文提出了一种新的主动学习方法，通过向表单用户询问“这两个例子在同一类还是不同类中？”，为半监督聚类选择了良好的成对约束条件。“提高了聚类性能。

5.2 半监督聚类的HMRF模型

基于分区原型的集群是正在考虑的底层无监督聚类设置。在这样的设置中，一组数据点被划分成预先指定数量的簇，其中每个簇都有一个代表性的（或“原型”），这样一个定义良好的成本函数（包括点和簇代表之间的失真度量）被最小化。一个众所周知的无监督聚类算法，遵循这个框架是k-均值（Macqueen，1967）。

我们的半监督学习模型考虑一个n 数据点 $X=(x_1,...,x_n)$ 的样本，每一个 $x_i \in R^d$ 为一个 d-维向量，其中 $x_{im}$ 代表它的第 m 个成分。该模型依赖于用于计算点之间距离的畸变测度 $d_A$ ： $R^d \times R^d \rightarrow R$ ，其中 $A$ 是畸变测度参数的集合。监督作为两组成对约束条件提供：must-link 限制 $C_{ML}=\{(x_i,x_j) \}$ 和 cannot-link 限制 $C_{CL}=\{(x_i,x_j) \}$ ，其中 $(x_i,x_j)\in C_{ML}$ 表示 $x_i$ 和 $x_j$ 被标记属于同一个簇，而 $(x_i,x_j)\in C_{CL}$ 表示 $x_i$ 和 $x_j$ 被标记属于不同簇。约束可能伴随着相关的违反成本 $W$ ，其中 $W_{ij}$ 表示违反约束点 $x_i$ 和x_j之间的约束，如果存在这样的约束，也就是， $(x_i,x_j)\in C_{ML}$ 或 $(x_i,x_j)\in C_{CL}$ 。任务是将数据点集 $X$ 划分为 $K$ 个不相交的簇 $(X_1,...,X_K)$ 以便根据给定的失真度量 $d_A$ 最小化点和相应的集群代表之间的总失真，而约束冲突保持最小。

5.2.1 HMRF 模型组件

半监督限制聚类的 HMRF 概率框架由以下组件组成：

a. 一个可观测集 $X=(x_1,...,x_n)$ 对应于给定的数据点 $X$ 。请注意，我们重载了符号，并使用 $X$ 引用给定的数据点集及其相应的随机变量。

b. 一个不可观测（隐藏）集 $Y=(y_1,...,y_n)$ 对应于 $X$ 中数据点的聚类分配。每个隐藏变量 $y_i$ 编码点 $x_i$ 的簇标签，并从聚类索引集合中获取值 $(1,...,K)$ 。

c. 一组不可观测（隐藏）的生成模型参数 $\Theta$ ，由畸变测度参数 $A$ 和代表 $M=(\mu_1,...,\mu_K)$ ： $\Theta = \{A,M \}$ 。

d. 一组可观测的约束变量 $C=(c_{12},c_{13},...,c_{(n-1)n})$ 。每个 $c_{ij}$ 是从集合中取值的三次变量 $(-1,0,1)$ ，其中 $c_{ij}=1$ 表示 $(x_i,x_j)\in C_{ML}$ ， $c_{ij}=-1$ 表示： $(x_i,x_j)\in C_{CL}$ ， $c_{ij}=0$ 对应于不受约束的对 $(x_i,x_j)$ 。

由于约束是完全观察到的，并且所描述的模型并不试图对它们进行生成建模，因此 $X,Y$ 的联合概率是以 $C$ 编码的约束为条件的。

图5.1 显示了一个简单的 $HMRF$ 示例。 $X$ 由五个数据点和相应的变量 $(x_1,...,x_5)$ 组成，具有聚类标签 $Y=(y_1,...,y_5)$ ，每个值 $(1,2,3)$ 表示三个聚类。提供了三个成对约束：两个必须链接约束 $(x_1,x_2)$ 和 $(x_1,x_4)$ ，一个不能链接约束 $(x_2,x_3)$ 。相应的约束变量是 $c_{12}=1,c_{14}=1$ 和 $c_{23}=-1$ ； $C$ 中的所有其他变量都设置为零。任务是将五个点分成三个聚类。图5.1展示了一种可能的聚类配置，它不违反任何约束。必须链接的点 $x_1,x_2$ 和 $x_4$ 属于聚类 $1$ ；不能与 $x_2$ 链接的点 $x_3$ 分配给集群 $2$ ；不涉及任何约束的点 $x_5$ 属于集群 $3$ 。

5.2.2 标签上的马尔科夫随机场

每一个隐藏的随机变量 $y_i\in Y$ 代表 $x_i \in X$ 的簇标签与一组邻居 $N_i$ 相关联。邻居集合定义为 $x_i$ 必须链接或不能链接的所有点： $N_i=\{y_j|(x_i,x_j)\in C_{ML} or (x_i,x_j) \in C_{CL} \}$ 。

图 5.1 一个隐马尔科夫随机场

在隐变量 $Y$ 上定义的结果随机场是一个马尔可夫随机场，其中隐变量上的条件概率分布服从马尔可夫性质。

$\forall i,P(y_i|Y-\{y_i \},\Theta,C)=P(y_i|N_i,\Theta,C)$ （5.1）

因此，给定模型参数和约束集的每一个 $x_i$ 的 $y_i$ 的条件概率，仅取决于必须链接或不能链接到 $x_i$ 的观测变量的簇标签。然后，根据Hammersley-Clifford定理（Hammersley和Clifford，1971），特定标签配置y的先验概率可以表示为吉布斯分布（Geman和Geman，1984），因此

$P(Y|\Theta,C)=\frac{1}{Z} exp(-v(Y))=\frac{1}{Z} \bigg(-\sum_{N_i\in N} v_{N_i}(Y)\bigg)$ （5.2）

其中， $N$ 是所有邻域的集合， $Z$ 是分区函数（规范化项）， $v(Y)$ 是整体标签配置势函数，可以分解为函数 $v_{N_i}(Y)$ 的总和，每个函数表示标签配置 $Y$ 中每个邻域 $N_i$ 的潜力。因为每个邻域的势都是基于 $C$ 中的成对约束（和模型参数 $\Theta$ ），

标签配置可以进一步分解为

$P(Y|\Theta,C)=\frac{1}{Z} \bigg(-\sum_{i,j} v(i,j)\bigg)$ ，（5.3）

其中每个约束势函数 $v(i,j)$ 有以下形式：

$v(i,j)= \begin{cases} w_{ij}f_{ML}(i,j)\quad if \ c_{ij}=1 \ and \ y_i \neq y_j,\\w_{ij}f_{CL}(i,j) \quad if \ c_{ij}= -1 \ and \ y_i = y_j,\\ 0 \quad otherwise . \end{cases}$ （5.4）

惩罚函数 $f_{ML}$ 和 $f_{CL}$ 编码观察 $Y$ 配置的概率降低，其中违反了 $C$ 编码的约束。为此，函数 $f_{ML}$ 惩罚违反必须链接约束，函数 $f_{CL}$ 惩罚违反不能链接约束。通过采用相同的模型参数 $\Theta$ ，选择这些功能与畸变测度相对应，并将在第5.3节中详细描述。总的来说，观察标签分配 $Y$ 的公式导致分配给配置的概率更高，在这些配置中，集群分配不会违反提供的约束。

5.2.3 隐马尔科夫随机场（HMRF）中的联合概率

在所描述的HMRF模型中，给定C，X、Y和 $\Theta$ 的联合概率可分解如下：

$P(X,Y,\Theta|C)=P(\Theta|C)P(Y|\Theta,C)P(X|Y,\Theta,C)$ （5.5）

图 5.2 变相关图形板模型

图5.2显示了HMRF中随机变量之间相关性的图形板模型（Buntine，1994年），其中无阴影节点表示隐藏变量，阴影节点是观察变量，定向链接显示变量之间的相关性，而两个变量之间缺少边意味着条件独立。假设的先验概率与 $C$ 无关。观察标签配置 $Y$ 的概率取决于约束 $C$ 和当前生成模型参数 $\Theta$ 。对应于变量 $X$ 的观测数据点是使用基于聚类标签 $Y$ 的模型参数生成的，独立于约束 $C$ 。变量x被假定为相互独立的：每个 $x_i$ 是从条件概率分布 $P(x|y|\Theta)$ 生成的。那么，条件概率 $P(X|Y,\Theta,C)$ 可以写成

$P(X|Y,\Theta,C)=P(X|Y,\Theta)=\prod_{i=1}^n P(x_i|y_i,\Theta)$ （5.6）

其中， $p(\cdot|y_i,\Theta)$ 是第 $y_i$ 群的参数化概率密度函数，由此生成 $x_i$ 。该概率密度与聚类畸变测度 $d_A$ 有关，如下文第5.2.4节所述。

从等式 5.3，5.5 和 5.6 ，最大化HMRF上的联合概率等于最大化

$P(X,Y,\Theta|C)=P(\Theta)\bigg(\frac{1}{Z} exp \Bigg(\sum_{c_{ij}\in C}v(i,j) \Bigg)\bigg)\bigg(\prod_{i=1}^n p(x_i|y_i,\Theta)\bigg)$ （5.7）

方程 5.7 中的联合概率有三个因素。第一个因素描述了模型参数上的概率分布，防止它们收敛到退化值，从而提供正则化。第二个因素是在给定的约束条件下观察特定标签配置的条件概率，有效地为集群分配不违反约束条件的配置分配更高的概率。最后，第三个因素是根据标签和参数生成观测数据点的条件概率：如果在HMRF上进行最大似然（ML）估计，目标是隔离地最大化该项。

总的来说，最大化（5.7）中的联合HMRF概率相当于共同最大化从模型生成数据点的可能性和遵守约束的标签分配的概率，同时规范化模型参数。

5.2.4 基于HMRF的半监督聚类目标函数

公式5.7提出了将约束合并到集群中的一般框架。在框架的特定实例中，条件概率 $p(x|y,\Theta)$ 的选择直接与适合于集群任务的失真度量的选择相关。

当考虑条件概率 $p(x_i|y_i,\Theta)$ -从第 $y_i$ 个簇生成数据点 $x_i$ 的概率时，我们的注意力仅限于指数族的概率密度，其中对应于第 $y_i$ 个簇的期望参数是 $\mu_{y_i}$ ——该簇的点的平均值。规则指数分布和规则布列格曼发散之间的双射（Banerjee等人，2005b），观测数据的条件密度可以表示为

$p(x_i|y_i,\Theta)=\frac{1}{Z_{\Theta}} exp(-d_A(x_i,\mu_h ))$ （5.8）

其中， $d_A(x_i,\mu_{y_i})$ 是 $x_i$ 和 $\mu_{y_i}$ 之间的Brgman散度，对应于指数密度 $p$ ， $Z_{\Theta}$ 是正规化器。不同的聚类模型属于这种指数形式：

a. 如果 $x_i$ 和 $\mu_{y_i}$ 是欧几里得空间中的向量，则 $d_A$ 是由半正定权矩阵 $A(d_A(x_i,\mu_{y_i})=||x_i - \mu_{y_i}||_A^2)$ 所参数的 $L_2$ 范数的平方，则聚类条件概率是由 $A^{-1}$ 编码的协方差的高斯分布（卡恩斯等人，1997）；

b. 如果 $x_i$ 和 $\mu_{y_i}$ 是概率分布， $d_A$ 是KL散度 $(d_A(x_i,\mu_{y_i})=\sum\nolimits_{m=1}^d x_{im}log \frac{x_{im}}{\mu_{y_im}} )$ ，则聚类条件概率是多项式分布（DHyon and Cuin，2003）。

式5.8中的关系成立，即使 $d_A$ 不是布列格曼散度，而是方向距离测度，如余弦距离。例如，如果 $x_i$ 和 $\mu_{y_i}$ 是单位长度的向量，而 $d_A$ 是向量 $(d_A(x_i,\mu_{y_i})=1- \frac{\sum\nolimits_{m=1}^d x_{im}\mu_{y_im} }{||x_i||||\mu_{y_i}||} )$ 的点积的一个减数，那么簇条件概率是具有单位浓度参数的冯 $\cdot$ 米塞斯Fisher（VMF）分布（BANEJEEE等人，2005年A），这实质上是高斯分布的球面模拟。第5.3.3节更详细地讨论了本章研究的特定畸变测量值与其相应的集群条件概率之间的关系。

将式5.8代入5.7，取对数，得到如下聚类目标函数，将其最小化，等于在式5.7中最大化HMRF上的联合概率。

$J_{obj}=\sum_{x_i \in X} d_A(x_i,\mu_{y_i})+\sum_{c_{ij} \in C}v(i,j) - logP(\Theta) +logZ +nlogZ_{\Theta}$ （5.9）

因此，任务是最小化隐变量 $Y$ 和 $\Theta$ 上的 $J_{obj}$ （注意，给定 $Y$ ，平均值 $M=(\mu_1,...,\mu_K)$ 是唯一确定的）。

5.3 HMRF-KMeans 算法

由于集群分配和生成模型参数在集群设置中是未知的，最小化等式5.9是一个“不完整的数据问题”。这种问题的一种常用解决方法是期望最大化（EM）算法（Dempster等人，1977）。已知k-均值算法（Macqueen，1967）在某些假设下相当于具有硬聚类分配的 $EM$ 算法（Kearns等人，1997；Basu等人，2002；Banerjee等人，2005b）。本节描述了一种k-均值类型的硬分割聚类算法 $HMRF-KMeans$ ，它在等式5.9中找到了半监督聚类目标函数 $J_{obj}$ 的局部最小值。

5.3.1 归一化分量估计

在描述聚类算法的细节之前，重要的是要考虑规范化组件：等式5.9中的 $MRF$ 分区函数 $logZ$ 和失真函数归一化 $logZ_{\Theta}$ 。对于大多数非平凡的依赖结构，分区函数的估计不能以封闭的形式进行，计算时必须采用近似推理方法（Wainwright 和 Jordan，2003）。

畸变归一化 $logZ_{\Theta}$ 的估计取决于在模型使用的畸变测度 $d_A$ 。这一章认为三参数参数化的畸变测度：参数化的平方欧氏距离，参数化余弦距离和参数化 KL 散度。对欧氏距离， $Z_{\Theta}$ 可以在封闭的形式中估计，这种估计是在最小化式 5.9 中的聚类目标函数 $J_{obj}$ 的同时进行的。对其他畸变测度，畸变归一化的估计不能在封闭的形式中进行，而且必须再次使用近似推理（Banerjee等人，2005年）。

由于近似推理方法的计算量非常昂贵，因此可以做出两个简化假设：在聚类过程中，可以将MRF分区函数视为常量，对于不提供近似估计的所有畸变测度，可以将畸变归一化器假定为常量。有了这些假设，等式5.9中的目标函数 $J_{obj}$ 不再精确对应于HMRF上的联合概率。然而，最小化这个简化的目标已经证明在经验上是有效的（Bilenko等人，2004年；Basu等人，2004b）。然而，如果在某些应用中保留底层联合概率模型的语义很重要，那么规范化器 $Z$ 和 $Z_{\Theta}$ 必须通过近似推理方法进行估计。

5.3.2 参数优先级

根据第5.2.1节中 $\Theta$ 的定义，式5.9 中的先前项 $logP(\Theta)$ 和随后的方程可以分解为以下等式：

$logP(\Theta)=log(P(A)P(M))=logP(A) + P_M$ ，

其中畸变参数 $A$ 被假设独立于簇类的中心 $M=(\mu_1,...,\mu_K)$ ，被看作是簇的形心上的一致先验（导致常数项 $P_M$ ）。对不同的畸变测度，可能存在导致优化问题退化解的参数值。例如，对平方欧式距离而言，0 矩阵 $A=0$ 就是一个这样的解。为了避免退化解， $P(A)$ 被用来通过使用一个先验分布正则化参数的值。

如果标准高斯先验分布被用于畸变函数的参数，就会允许这些参数取负值。由于需要将参数值约束为非负值，因此更适合使用瑞利分布（Papulis和Pillai，2001）。假设参数 $a_{ij}\in A$ 独立，基于瑞利分布的先验项为：

$P(A)=\prod_{a_{ij}\in A} \frac{a_{ij}exp\bigg(-\frac{a_{ij}^2}{s^2} \bigg)}{s^2}$ （5.10）

其中 $s$ 是宽度参数。

5.3.3 自适应畸变测度

为一个聚类任务选择一个适当的畸变测度 $d_A$ 通常涉及到特定领域和数据集的属性知识。例如，平方欧几里得距离是最适合分布接近高斯分布的低维数据的，而余弦距离最能捕捉高维空间中向量描述的数据之间的距离，在高维空间中，角度差异很重要，但向量长度不重要。

本章考虑了两个族的畸变测度：Bregman 散度（Banerjee等人，2005b），其中包括参数化的欧几里得距离和 $KL$ 分歧，以及基于方向相似函数的畸变测量，其中包括余弦相似性和皮尔逊相关（Mardia和Jupp，2000）。方向函数的畸变测度被选择为从足够大的常量中减去方向相似性度量，这样得到的值是非负的。对于布列格曼散度和余弦距离，存在有效的k-均值迭代重定位算法，使相应的聚类目标最小化（Banerjee等人，2005a，b），HMRF-k means自然扩展到包含成对监督。

对于许多实际的数据集，现成的畸变测度可能无法在聚类设置中捕获正确的相似性概念。虽然一些无监督的度量，如平方欧几里得距离和皮尔逊距离试图使用数据集的全局平均值和方差来校正失真估计，但如果属性对距离的真正贡献与它们的方差不相关，这些度量可能仍然无法准确地估计距离。存在几种包含自适应畸变测度的半监督聚类方法，包括Jensen-Shannon发散参数化（Cohn等人，2003）和平方欧几里得距离（Bar-Hillel等人，2003；Xing等人，2003）。然而，这些技术仅使用约束来学习畸变测度参数，并从参数学习步骤中排除未标记的数据，以及将参数学习步骤与聚类过程分离。

更进一步，HMRF模型提供了一个集成框架，该框架包括学习畸变测度参数和约束敏感的簇类分配。在 HMRF-KMeans 中，随着聚类的进行，利用未标记的数据和成对的约束，迭代地学习畸变测度的参数。修改参数以减少违反的必须链接约束之间的参数化距离，并增加违反的不能链接约束之间的参数化距离，同时允许违反约束（如果它们伴随更具内聚性的聚类）。

本节介绍了三个用于 HMRF-KMeans 的畸变函数及其参数化示例：平方欧几里得距离、余弦距离和kl发散。通过参数化，这些函数中的每一个都在半监督的集群设置中变得自适应，允许不同形状的集群。

一旦为给定的领域选择一个畸变测度，函数 $f_{ML}$ 和 $f_{CL}$ ，第5.2.2节中介绍的惩罚必须链接，不能链接违反约束的行为，相应地，必须被定义。这些函数通常遵循与相应畸变测度相同或相似的函数形式，选择如下：

$f_{ML}(i,j) = \varphi (i,j)$ （5.11）

$f_{CL}=\varphi^{max} -\varphi(i,j)$ （5.12）

其中 $\varphi:X \times X \rightarrow R^+$ 是一个惩罚违反限制的非负函数， $\varphi^{max}$ 是数据集中任意一对点上 $\varphi$ 最大值的上界；具体畸变函数的此类界限示例如下所示。选择函数 $\varphi$ 与畸变测度相关，对畸变测度的当前参数值距离较远的点之间违反必须链接约束的行为给予更高的惩罚。相反，对违反的“不能链接”约束的惩罚对于距离较短的点来说更高。使用惩罚函数的这种公式，约束冲突会导致试图修正冲突的失真度量参数发生变化。下节将讨论针对不同聚类畸变测量的 $\varphi$ 函数。

相应的地，（5.4）中的势函数 $v(i,j)$ 变成

$v(i,j)= \begin{cases} w_{ij}\varphi(x_i,x_j)\quad \quad \quad \quad \quad if \ c_{ij}=1 \ and \ y_i \neq y_j,\\w_{ij}(\varphi^{max}-\varphi(x_i,x_j))\quad if \ c_{ij}= -1 \ and \ y_i = y_j,\\ \quad \quad \quad 0 \quad \ \ \ \quad \quad \quad \quad \quad otherwise . \end{cases}$ （5.13）

（5.9）中的半监督聚类的目标函数可以被记为

$J_{obj}=\sum_{x_i\in X} d_A(x_i,\mu(i)) +\sum_{(x_i,x_j)\in C_{ML} \atop s.t. y_i\neq y_j} w_{ij}\varphi(x_i,x_j) \\+ \sum_{(x_i,x_j)\in C_{CL} \atop s.t. y_i = y_j} w_{ij}(\varphi^{max}-\varphi(x_i,x_j))-logP(A) + nlogZ_{\Theta}$ （5.14）

注意，如第5.3.1节所述，MRF分区函数项 $logZ$ 已从目标函数中删除。

5.3.3.1 参数化平方欧几里得距离

平方欧几里得距离使用一个对称正定矩阵 $A$ 参数化如下：

$d_{euc_A}(x_i,x_j)=||x_i-x_j||_A^2=(x_i-x_j)^T A (x_i-x_j)$ （5.15）

参数化的平方欧几里得距离的形式等价于Mahalanobis距离，用一个任意的半正定权矩阵 $A$ 代替协方差逆矩阵，它以前被（Xing et al.，2003）和（Bar Hillel et al.，2003）用于半监督聚类。这种公式也可以看作是每个实例 $x$ 在 $A^{1/2}$ 所跨越的空间上的投影： $x \rightarrow A^{1/2} x$ 。

利用参数化平方欧氏距离作为聚类的自适应畸变测度，将惩罚违反惩罚的 $\varphi$ 函数定义为 $\varphi(x_i,x_j) = d_{euc_A}(x_i,x_j)$ 。无法链接惩罚的上界的一个可能初始化是 $\varphi_{euc_A}^{max} = \sum\nolimits_{(x_i,x_j) \in C_{CL}}d_{euc_A}(x_i,x_j)$ ，它保证惩罚始终为正。利用这些定义以及（5.14），对于具有自适应平方欧几里得距离的半监督聚类，得到以下目标函数：

$J_{euc_A}=\sum_{x_i \in X} d_{euc_A}(x_i,\mu(i))+\sum_{(x_i,x_j)\in C_{ML} \atop s.t. y_i\neq y_j} w_{ij}d_{euc_A}(x_i,x_j) \\ + \sum_{(x_i,x_j)\in C_{CL} \atop s.t. y_i= y_j}w_{ij}(\varphi_{euc_A}^{max}-d_{euc_A}(x_i,x_j))-logP(A) - n log \ det(A) .$ （5.16）

请注意，如第5.3.1节所述， $log \ Z_{\Theta}$ 项可在闭式格式中计算协方差矩阵 $A^{-1}$ 的高斯分布，协方差矩阵a−1是参数化平方欧几里德距离的基本簇条件概率分布。在这种情况下， $log \ det(A)$ 术语（5.16）与 $log \ Z_{\Theta}$ 项相对应。

5.3.3.2 参数化余弦距离

余弦距离可以使用对称正定矩阵 $A$ 参数化，这将导致以下畸变测量：

$d_{cos_A}(x_i,x_j)=1-\frac{x_i^TAx_j}{||x_i||_A||x_j||_A}$ （5.17）

因为对于实数的高维域，计算全矩阵 $A$ 的计算代价很高，所以在这种情况下，考虑对角矩阵，这样 $a=diag(A)$ 是正权重的向量。

利用参数化平方欧氏距离作为聚类的自适应畸变测度，将 $\varphi$ 函数定义为 $\varphi(x_i,x_j)=d_{cos_A}(x_i,x_j)$ 。将该定义与等式5.14结合，将极大值 $\varphi^{max} = 1$ 设为上界 $\varphi(x_i,x_j)$ ，得到了具有自适应余弦距离的半监督聚类的目标函数：

$J_{cos_A} = \sum_{x_i \in X} d_{cos_A}(x_i,\mu(i)) + \sum_{(x_i,x_j)\in C_{ML} \atop s.t. y_i \neq y_j}w_{ij}d_{cos_A}(x_i,x_j) \\ + \sum_{(x_i,x_j)\in C_{CL} \atop s.t. y_i = y_j}w_{ij}(1-d_{cos_A}(x_i,x_j))-log \ P(A)$ （5.18）

注意，如第5.3.1节所述，很难以闭合形式计算参数化余弦距离的对数 $log \ Z_{\Theta}$ 项。因此，简化假设在聚类过程中对数 $Z_{\Theta}$ 是常数，规范化项从（5.18）中去掉。

5.3.3.3 参数化 KL 散度

在确定的领域，数据可以描述为概率分布，如，文本文档可以表示成由多项式模型生成的词的概率分布（Pereira 等 1993）。KL 散度是广泛应用于此类数据的距离测度： $d_{KL}(x_i,x_j)=\sum\nolimits_{m=1}^d x_{im}log \ \frac{x_{im}}{x_{jm}}$ ，其中 $x_i$ 和 $x_j$ 是 $d$ 事件上的概率分布： $\sum\nolimits_{m=1}^d x_{im}=\sum\nolimits_{m=1}^d x_{jm} = 1$ 。在先前的研究中，Cohn等人（2003）通过将第 m 分量乘以权重 $\gamma_m = d_{KL}^\prime (x_i,x_j) = \sum\nolimits_{m=1}^d \gamma_mx_{im} \ log \ \frac{x_{im}}{x_{jm}}$ 来参数化kl散度。

在我们的框架中，KL 距离通过一个对角化矩阵 $A$ 来参数化，其中 $a = diag \ (A)$ 是一个正权重的向量。 $A$ 对 $KL$ 的参数化将其转换为 $I$ 散度，该函数也属于Bregman散度类（Banerjee等人，2005b）。 $I$ 散度有这样的形式： $d_I(x_i,x_j)=\sum\nolimits_{m=1}^d x_{im} \ log \ \frac{x_{im}}{x_{jm}} -\sum\nolimits_{m=1}^d (x_{im}-x_{jm})$ ，其中 $x_i$ 和 $x_j$ 不再需要是概率分布可以是任何非负向量。使用以下参数化KL：

$d_{I_A}(x_i,x_j)=\sum_{m=1}^d a_mx_{im} \ log \ \frac{x_{im}}{x_{jm}} -\sum_{m=1}^d a_m(x_{im}-x_{jm})$ ，（5.19）

它可以解释为用 $A$ 的相应分量中包含的权重缩放原始概率分布的每个分量，然后在转换后的分布之间取 $I$ 散度。

对于每个畸变测度，第5.2.4节中描述的集群框架要求定义一个适当的对称约束势函数，因为约束对是无序的。为了满足这一要求，使用从 $x_i$ 和 $x_j$ 到平均矢量 $\frac{x_i+x_j}{2}$ 的加权 $I$ 散度的和。这一参数化的平均值 $I$ 散度 $d_{IM_A}$ 类似于Jensen-Shannon散度（Cover和Thomas，1991），对称的平均值 $KL$ 散度，定义如下：

$d_{IM_A}(x_i,x_j)=\sum_{m=1}^d a_m(x_{im} \ log \ \frac{2x_{im}}{x_{im}+x_{jm}} +x_{jm} \ log \ \frac{2x_{jm}}{x_{im}+x_{jm}}$ （5.20）

利用参数化平方欧氏距离作为聚类的自适应失真测度，将 $\varphi$ 函数定义为 $\varphi(x_i,x_j) = d_{IM_A}(x_i,x_j)$ 。利用该定义以及等式5.14，得到了具有自适应 $KL$ 距离的半监督聚类的以下目标函数： $J_{I_A}=\sum_{x_i \in X} d_{I_A}(x_i,\mu(i))+\sum_{(x_i,x_j \in C_{ML} \atop s.t. \ y_i \neq y_j} w_{ij}d_{IM_A}(x_i,x_j) \\ +\sum_{(x_i,x_j)\in C_{CL} \atop s.t. \ y_i = y_j} w_{ij}(d_{IM_A}^{max} \ - d_{IM_A}(x_i,x_j)) \ - \ log \ P(A).$ （5.21）

上界 $d_{IM_A}^{max}$ 可以初始化为 $d_{IM_A}^{max} =\sum\nolimits_{m=1}^d a_m$ ，这是由于未加权的Jensen-Shannon散度的上界为1（Lin，1991）。

注意，如第5.3.1节所述，很难以闭合形式计算参数化 $KL$ 距离的 $log \ Z_{\Theta}$ 项。因此，与参数化余弦距离情况类似，简化假设 $log \ Z_{\Theta}$ 在聚类过程中是常数，该项从等式5.21中去掉。

5.3.4 EM 框架

如本节之前讨论的， $J_{obj}$ 可以通过 K-Means 型的迭代算法 HMRF-KMeans 最小化。算法概述见算法5.1。HMRF-KMeans 的基本思想是：使用约束条件对聚类进行良好的初始化。然后，在E步骤中，考虑到当前簇的代表性，每个数据点都被重新分配给簇，从而最小化对 $J_{obj}$ 的贡献。在 M 步骤中，簇代表 $M=(\mu_1,...,\mu_K)$ 根据群集分配被重新估计，以最小化当前分配的 $J_{obj}$ 。然后在 $M$ 步中更新聚类畸变测度 $d_A$ ，通过修改畸变测度的参数 $A$ 来降低目标函数。

请注意，这对应于广义 $EM$ 算法（Neal和Hinton，1998；Dempster等人，1977），其中目标函数在 $M$ 步骤中减少但不一定最小化。有效地， $E$ 步骤使集群分配 $Y$ 上的 $J_{obj}$ 最小化， $M$ 步骤（ $A$ ）使集群代表 $M$ 上的 $J_{obj}$ 最小化， $M$ 步骤（ $B$ ）在畸变测度 $d_A$ 的参数 $A$ 上减少 $J_{obj}$ 。重复 $E$ 步和 $M$ 步，直到达到指定的收敛标准。 $E$ 步骤和 $M$ 步骤的具体细节将在以下章节中讨论。

5.3.5 初始化

良好的初始质心对于K均值等分割聚类算法的成功至关重要。在初始化期间，从约束和未标记的数据中推断出良好的质心。为此，使用两阶段初始化过程。

算法 5.1 HMRF-KMeans 算法

input：数据点集 $X=(x_1,...,x_n)$ ，簇的数量 K，限制集 C，限制违反损失 W，畸变测度 D。

output：分离 K-分区 $(X_1,...,X_K)$ ，满足式3.9 目标函数 $J_{obj}$ 是局部最小化的。

Method：

1. 初始化 K 个簇的质心 $M^{(0)}=(\mu_1^{(0)},...,\mu_K^{(0)})$ ，设 $t\leftarrow 0$ 。

2. 重复直到收敛

2a. E-step：给定质心 $M^{(t)}$ 和畸变参数 $A^{(t)}$ ，通过在 X上最小化 $J_{obj}$ 重新分配簇标签 $Y^{(t+1)}=(y_1^{(t+1)},...,y_n^{(t+1)})$ 。

2b. M-step(A)：给定簇标签 $Y^{(t+1)}$ 和畸变参数 $A^{(t+1)}$ ，根据最小化 $J_{obj}$ 重新计算质心 $M^{(t+1)}=(\mu_1^{(t+1)},...,\mu_K^{(t+1)})$ 。

2c. M-step(B)：给定簇标签 $Y^{(t+1)}$ 和质心 $M^{(t+1)}$ ，重新估算畸变测度的参数 $A^{(t+1)}$ 去降低 $J_{obj}$ 。

2d. $t \leftarrow t+1$

邻域推理 首先采用必链接约束的传递闭包，得到由必链接连接的点组成的连接分量。假设存在用于创建 $\lambda$ 邻域的 $\lambda$ 连接组件。这些对应于MRF中隐藏的集群变量上的必须链接的邻居。

簇选择 利用第一阶段产生的 $\lambda$ 邻域集对HMRF均值算法进行初始化。如果 $\lambda=K$ ，则用所有 $\lambda$ 邻域集的形心初始化 $\lambda$ 簇中心。如果 $\lambda < K$ ，则从邻域初始化 $\lambda$ 簇，剩余的 $K - \lambda$ 簇用由 $X$ 的全局质心随机扰动获得的点初始化。如果 $\lambda > K$ ，则将最远第一次遍历的加权变量（Hochbaum和Shmoys，1985）应用于 $\lambda$ 邻域的质心，其中每个质心的权重质心与相应邻域的大小成正比。加权最远优先遍历选择距离较远、规模较大的邻域，并将所选邻域设置为hmrfkmeans的 $K$ 初始簇形心。

总的来说，这两个阶段的初始化过程能够同时考虑未标记和标记的数据，以获得提供良好的数据集初始分区的集群代表。

5.3.6 E 步骤

在 $E$ 步骤中，使用聚类代表的当前估计更新聚类的数据点分配。在一般的无监督K 均值算法中，聚类标签之间没有交互作用，而 $E$ 步是根据聚类畸变测度，将每个点简单地分配给最接近的聚类代表。相比之下，HMRF 模型结合了由隐藏变量上的随机场定义的簇标签之间的交互作用。因此，在任何非平凡的HMRF模型中，计算将数据点分配给聚类代表以找到目标函数的全局最小值（给定集群中心），与其他图形模型（如MRF和信念网络）类似，都是NP-hard 的（Roth，1996）。

在这个框架中，有几种计算集群分配的技术近似于最优解决方案，如，迭代条件模式（ICM）（Besag, 1986; Zhang 等, 2001），信仰传播（Pearl，1988；Segal 等 2003b），及线性规划松弛（Kleinberg 和 Tardos，1999）。ICM是一种贪婪的策略，它按顺序更新每个点的集群分配，保持其他点的分配不变。在许多情况下，它的性能与更昂贵的全局近似技术相当，但计算效率更高；它与Bilenko和Basu（2004）的其他几种方法进行了比较，而在最近的研究中，Lange等人（2005）描述了一种基于平均场近似的替代有效方法。ICM按照随机顺序对所有点执行顺序集群分配。每个点 $x_i$ 被分配到簇代表 $\mu_h$ ，它最小化了点对目标函数 $J_{obj}(x_i,\mu_h)$ 的贡献： $J_{obj}(x_i,\mu_h)=d_A(x_i,\mu_h)+\sum_{(x_i,x_j\in C_{ML}^i \atop s.t. \ y_i \neq y_j} w_{ij}\varphi(x_i,x_j) \\+\sum_{(x_i,x_j \in C_{CL}^i \atop s.t. \ y_i = y_j}w_{ij}(\varphi^{max}-\varphi(x_i,x_j))-log \ P(A),$ （5.22）

其中 $C_{ML}^i$ 和 $C_{CL}^i$ 分别是 $C_{ML}$ 和 $C_{CL}$ 的子集，对应 $x_i$ 出现的约束。每个点的最佳分配将点与其聚类代表（ $J_{obj}$ 的第一项）之间的失真降至最低，同时对由此分配（ $J_{obj}$ 的第二和第三项）导致的约束违反也将受到最低的惩罚。分配完所有点后，随机重新排序，并重复分配过程。这个过程一直进行，直到在两个连续的迭代之间没有任何点改变它的聚类分配。

总的来说，将点分配给聚类包含成对的监督，通过按严重性的比例抑制约束冲突，从而引导算法实现对数据的理想分区。

5.3.7 M 步骤

算法的M步分为质心重估计和畸变测度参数更新两部分。

5.3.7.1 M 步骤A：质心重估计

在 $M$ 步骤的第一部分中，从当前分配给它们的点重新估计簇形心 $M$ ，以减少等式5.9中的目标函数 $J_{obj}$ 。对于Bregman散度和余弦距离，在 $EM$ 算法的 $M$ 步中计算的簇代表性等于该簇中各点的期望值，等于它们的算术平均值（Banerjee等人，2005a，b）。此外，实验证明，对于基于分布的度量（如 $KL$ 发散）的集群，使用确定性退火调度之前平滑集群代表会带来相当大的改进（Dhillon和Guan，2003）。当 $d_{I_A}$ 为畸变测度值时，平滑由正参数 $\alpha$ 控制，每个代表 $\mu_h$ 的簇估计如下：

$\mu_h^{(I_A)}=\frac{1}{1+\alpha} \bigg(\frac{\sum\nolimits_{x_i \in X_h}x_i }{|X_h|} + \frac{\alpha}{n} 1\bigg)$ （5.23）

对于方向测度，每个聚类代表的是投影到单位球体上的算术平均数（Banerjee等人，2005a）。考虑到畸变参数，当 $d_{cos_A}$ 是畸变测度时，质心估计如下：

$\frac{\mu_h^{(cos_A)}}{||\mu_h^{(cos_A)}||_A} =\frac{\sum\nolimits_{x_i\in X_h}x_i }{||\sum\nolimits_{x_i\in X_h}x_i ||_A}$ （5.24）

5.3.7.2 M步骤 B ：畸变参数更新

在 M 步骤的第二部分，对参数化畸变测度的参数进行了更新，以减小目标函数。一般来说，对于具有一般参数先验的参数化 Bregman 散度或方向距离，很难对能够最小化目标函数的畸变测度参数进行封闭式更新。梯度下降为畸变测量参数的学习提供了一种新的途径。

对平方欧几里德距离，在梯度下降过程中，使用以下规则更新全参数矩阵A： $A= A+\eta \frac{\partial{J_{euc_A}}}{\partial A}$ （其中 $\eta$ 为学习率）。根据式（5.16）， $\frac{\partial{J_{euc_A}}}{\partial A}$ 可以表示为：

$\frac{\partial{J_{euc_A}}}{\partial A} = \sum_{x_i\in X} \frac{\partial{d_{euc_A}(x_i,\mu(i))}}{\partial A} + \sum_{(x_i,x_j)\in C_{ML} \atop s.t. \ y_i\neq y_j} w_{ij}\frac{\partial{d_{euc_A}(x_i,x_j)}}{\partial A}\\ + \sum_{(x_i,x_j)\in C_{CL} \atop s.t. y_i=y_j} w_{ij}\bigg[\frac{\partial \varphi_{euc_A}^{max}}{\partial A} -\frac{\partial d_{euc_A}(x_i,x_j)}{\partial A} \bigg] - \frac{\partial log \ P(A)}{\partial A} - n\frac{\partial log \ det(A)}{\partial A}$ （5.25）

参数化平方欧几里德距离的梯度由下式给出

$\frac{\partial d_{euc_A}(x_i,x_j)}{\partial A} = (x_i-x_j)(x_i-x_j)^T$

根据第5.3.3.1节所述，上界 $\varphi_{euc_A}^{max}$ 的导数为 $\frac{\partial \varphi_{euc_A}^{max}}{\partial A} \sum\nolimits_{(x_i,x_j)\in C_{CL}} (x_i-x_j)(x_i-x_j)^T$ 。

当在参数A上使用瑞利先验时，对数先验对每个参数的偏导数 $a_m \in A$ ， $\frac{\partial log \ P(A)}{\partial a_m}$ 由下式给出

$\frac{\partial log \ P(A)}{\partial a_m} = \frac{1}{a_m} - \frac{a_m}{s^2}$ （5.26）

畸变规范化项 $log \ det(A)$ 的梯度如下：

$\frac{\partial log \ det(A)}{\partial A} = 2A^{-1} - diag(A^{-1})$ ( 5.27 )

对于参数化余弦距离和 $KL$ 散度，考虑了对角参数矩阵 $A$ ，其中 $a=diag(A)$ 是正权向量。梯度下降期间，每个权重 $a_m$ 是单独更新的 $a_m = a_m + \eta \frac{\partial J_{obj}}{\partial a_m}$ （ $\eta$ 是学习率）。根据（5.14）， $\frac{\partial J_{obj}}{\partial a_m}$ 可以表示为

$\frac{\partial J_{obj}}{\partial a_m} = \sum_{x_i\in X} \frac{\partial d_A(x_i,\mu(i))}{\partial a_m} + \sum_{(x_i,x_j)\in C_{CL} \atop s.t. y_i \neq y_j} w_{ij}\frac{\partial \varphi(x_i,x_j)}{\partial a_m} \\ +\sum_{(x_i,x_j) \in C_{CL} \atop s.t. y_i = y_j} w_{ij}\bigg[\frac{\partial \varphi^{max}}{\partial a_m} - \frac{\partial \varphi(x_i,x_j)}{\partial a_m} \bigg]- \frac{\partial log \ P(A)}{\partial a_m}$ （5.28）

用对角矩阵 $A$ 参数化的余弦距离和 $KL$ 散度的梯度 $\frac{\partial J_{obj}}{\partial a_m}$ 的计算需要相应的畸变测度和约束势函数的梯度，即

当参数化余弦的上界 $\frac{\partial \varphi^{max}}{\partial a_m}$ 的梯度为0，参数化 $KL$ 发散的上界的梯度为1时，从第5.3.3.2和5.3.3.3节中这些常数的表达式中可以看出。