2018-11-20

作者: hzb_ml | 来源:发表于2018-11-20 00:04 被阅读2次

Co-regularized Spectral Clustering多视图谱聚类算法介绍

假设给出了具有多个视图的数据 $\left\{ \mathbf { x } _{ 1 } ^ { ( v ) } , \mathbf { x }_ { 2 } ^ { ( v ) } , \ldots , \mathbf { x } _ { n } ^ { ( v ) } \right\}$ 。

视图v的相似度矩阵：

$\mathbf { K } ^ { ( v ) }$

视图v的拉普拉斯矩阵：

$\mathcal { L } ( v ) = \mathbf { D } ( v ) ^ { - 1 / 2 } \mathbf { K } ( v ) \mathbf { D } ( v ) ^ { - 1 / 2 }$

单视图聚类算法解决了归一化图拉普拉斯算子 $\mathbf { L } ^ { ( v ) }$ 如下的优化问题：

$\max _ { \mathbf { U } ^ { ( v ) } \in \mathbb { R } ^ { n } \times k } \operatorname { tr } \left( \mathbf { U } ^ { ( v ) ^ { T } } \mathcal { L } ^ { ( v ) } \mathbf { U } ^ { ( v ) } \right) , \quad \text { s.t. } \mathbf { U } ^ { ( v ) ^ { T } } \mathbf { U } ^ { ( v ) } = I$

其中的tr代表求矩阵的迹。

矩阵 $\mathbf { U } ^ { ( v ) }$ 的行是数据点的嵌入，就是说一行对应一个数据，一共有n行，然后用k均值算法进行聚类。

作者的多视图谱聚类框架建立在标准谱聚类基础上，增加了半监督学习中的共正则化框架增加单一视图。

半监督学习中的共正则化基本上是通过使不同数据视图中的学习的假设在未标记数据上一致。

框架成功采用了两个主要假设：(a)每个视图中的真实目标函数应该就未标记数据的标签(兼容性)达成一致;(b)视图在类标签(条件独立性)下是独立的。

兼容性假设允许我们通过进搜索通过仅搜索兼容的函数来缩小可能的目标假设的空间。

作者提出了两种基于共正则化的方法，使得不同视图的聚类假设彼此一致。同时作者构建包含所有数据视图的拉普拉斯算子，同时在拉普拉斯算子的基础上进行了规范化，使得每个拉普拉斯算子得到的聚类结构在每个视图中一致。

第一个共正则化强制一个视图对 $( v , w )$ 的特征向量应该具有高度的成对相似性(使用成对的正则化标准)。第二个共正则化方案是通过将他们规范化为共同的共识(基于中心的共正则化)来强制使视图特定的特征向量看起来相似。

Pairwise Co-regularization成对共正则化

在多视图的情况下，我们希望每个视图的特征向量矩阵是相似的。相当于在强制使所有视图中的谱聚类假设相同。

先讨论双视图情况。

提出以下损失函数作为两个视图之间聚类结果是否一致性的度量。

$D \left( \mathbf { U } ^ { ( v ) } , \mathbf { U } ^ { ( w ) } \right) = \left\| \frac { \mathbf { K } _ { \mathbf { U } ^ { ( v ) } } } { \left\| \mathbf { K } _ { \mathbf { U } ^ { ( v ) } } \right\| _ { F } ^ { 2 } } - \frac { \mathbf { K } _ { \mathbf { U } ^ { ( w ) } } } { \left\| \mathbf { K } _ { \mathbf { U } ^ { ( w ) } } \right\| _ { F } ^ { 2 } } \right\| _ { F } ^ { 2 }$

其中的 $\mathbf { K } _ { \mathbf { U } ( v ) }$ 是 $\mathbf { U } ^ { ( v ) }$ 的相似矩阵。

进行除法的意义在于进行归一化使得两个视图具有可比较性。

然后作者选择了线性核作为相似性的度量方式。

从而得出： $\mathbf { K } _ { \mathbf { U } ^ { ( v ) } } = \mathbf { U } ^ { ( v ) } \mathbf { U } ^ { ( v ) ^ { T } }$

选择线性核的原因：

拉普拉斯谱聚类中使用的相似性度量处理了数据中存在的非线性。
通过使用线性和得到了比较好的优化问题。

因为 $\left\| \mathbf { K } _ { \mathbf { U } ^ { ( v ) } } \right\| _ { F } ^ { 2 } = k$ 对上面的代价函数进行化简最终的到

$D \left( \mathbf { U } ^ { ( v ) } , \mathbf { U } ^ { ( w ) } \right) = - \operatorname { tr } \left( \mathbf { U } ^ { ( v ) } \mathbf { U } ^ { ( v ) ^ { T } } \mathbf { U } ^ { ( w ) } \mathbf { U } ^ { ( w ) ^ { T } } \right)$

然后我们在其中增加各个视图之间的谱聚类目标函数，得到以下的最大化问题：

$\max _ { \mathbf { U } ( w ) \in \mathbb { R } ^ { n } \times k \atop \mathbf { U } ^ { ( w ) } \in \mathbb { R } ^ { n } \times k } \operatorname { tr } \left( \mathbf { U } ^ { ( v ) ^ { T } } \mathcal { L } ^ { ( v ) } \mathbf { U } ^ { ( v ) } \right) + t r \left( \mathbf { U } ^ { ( w ) ^ { T } } \mathcal { L } ^ { ( w ) } \mathbf { U } ^ { ( w ) } \right)+ \lambda \operatorname { tr } \left( \mathbf { U } ^ { ( v ) } \mathbf { U } ^ { ( v ) ^ { T } } \mathbf { U } ^ { ( w ) } \mathbf { U } ^ { ( w ) ^ { T } } \right)$

$\text { s.t. } \mathbf { U } ^ { ( v ) ^ { T } } \mathbf { U } ^ { ( v ) } = I , \mathbf { U } ^ { ( w ) ^ { T } } \mathbf { U } ^ { ( w ) } = I$

然后我们可以通过不断的进行迭代去最大化上面的式子。

例如当给定 $\mathbf { U } ^ { ( w ) }$ 时，上式的优化目标就变成了：

$\max _ { \mathbf { U } ( v ) \in \mathbb { R } ^ { n } \times k } \operatorname { tr } \left\{ \mathbf { U } ^ { ( v ) ^ { T } } \left( \mathcal { L } ^ { ( v ) } + \lambda \mathbf { U } ^ { ( w ) } \mathbf { U } ^ { ( w ) ^ { T } } \right) \mathbf { U } ^ { ( v ) } \right\} , \quad \text { s.t. } \mathbf { U } ^ { ( v ) ^ { T } } \mathbf { U } ^ { ( v ) } = I$

这时候就化简成了普通的单视图的优化目标函数的形式。它的拉普拉斯矩阵为 $\mathcal { L } ^ { ( v ) } + \lambda \mathbf { U } ^ { ( w ) } \mathbf { U } ^ { ( w ) ^ { T } }$ 。

上面的拉普拉斯矩阵是一种自适应(随着每次迭代，拉普拉斯算子会改变)的，结合内核和拉普拉斯算子的方法。

然后我们可以交替最大化使得算法得到最大值。但是同时要注意选择合适的初始化值从而避免陷入局部最大值。迭代开始时，可以选择最具有信息性的视图开始进行迭代。

对固定的 $\lambda$ 和 $n$ ，可以保证算法收敛。实践中通过观察连续迭代之间的目标值的差值来监视是否收敛，当低于某一阈值时，停止迭代。

Extension to Multiple Views扩展到多个视图

我们扩展上一节中提出的共正则化谱聚类。对于m个视图，我们有：

$\max _ { \mathbf { U } ^ { ( 1 ) } , \mathbf { U } ^ { ( 2 ) } , \ldots , \mathbf { U } ^ { ( m ) } \in \mathbb { R } ^ { n \times k } } \sum _ { v = 1 } ^ { m } \operatorname { tr } \left( \mathbf { U } ^ { ( v ) ^ { T } } \mathcal { L } ^ { ( v ) } \mathbf { U } ^ { ( v ) } \right) + \lambda \sum _ { 1 \leq v , w \leq m \atop v \neq w } \operatorname { tr } \left( \mathbf { U } ^ { ( v ) } \mathbf { U } ^ { ( v ) ^ { T } } \mathbf { U } ^ { ( w ) } \mathbf { U } ^ { ( w ) ^ { T } } \right)$

$\text { s.t. } \mathbf { U } ^ { ( v ) ^ { T } } \mathbf { U } ^ { ( v ) } = I , \forall 1 \leq v \leq V$

在这里，对所有的共正则化部分使用了共同的 $\lambda$ 进行平衡。然后优化方法和双视图情况类似。

给定一个视图的 $\mathbf { U } ^ { ( v ) }$ ，优化目标如下所示：

$\max _ { \mathbf { U } ^ { ( v ) } } \operatorname { tr } \left\{ \mathbf { U } ^ { ( v ) ^ { T } } \left( \mathcal { L } ^ { ( v ) } + \lambda \sum _ { 1 \leq w \leq m \atop w \neq v } \mathbf { U } ^ { ( w ) } \mathbf { U } ^ { ( w ) ^ { T } } \right) \mathbf { U } ^ { ( v ) } \right\} , \quad \text { s.t. } \mathbf { U } ^ { ( v ) ^ { T } } \mathbf { U } ^ { ( v ) } = I$

然后我们可以通过迭代对它进行不断优化。

Centroid-Based Co-regularization基于中心的共正则化

这里提出的正则化方案是对上面的正则化方案的一种替代。将所有视图的特征向量 $\mathbf { U } ^ { ( v ) }$ 朝向共同的中心 $\mathbf { U } ^ { * }$ (类似一组共同的特征向量)。这样可以减少正则化项的对数(m对)。

目标函数可以写为：

$\max _ { \mathbf { U } ^ { ( 1 ) } , \mathbf { U } ^ { ( 2 ) } , \ldots , \mathbf { U } ^ { ( m ) } , \mathbf { U } ^ { * } \in \mathbb { R } ^ { n \times k } } \sum _ { v = 1 } ^ { m } \operatorname { tr } \left( \mathbf { U } ^ { ( v ) ^ { T } } \mathcal { L } ^ { ( v ) } \mathbf { U } ^ { ( v ) } \right)+ \sum _ { v } \lambda _ { v } t r \left( \mathbf { U } ^ { ( v ) } \mathbf { U } ^ { ( v ) ^ { T } } \mathbf { U } ^ { * } \mathbf { U } ^ { * ^ { T } } \right)$

$\text { s.t. } \mathbf { U } ^ { ( v ) ^ { T } } \mathbf { U } ^ { ( v ) } = I , \forall 1 \leq v \leq V , \quad \mathbf { U } ^ { * ^ { T } } \mathbf { U } ^ { * } = I$

这个目标函数平衡各个谱聚类目标与每个视图特定特征向量 $\mathbf { U } ^ { ( v ) }$ 和共有特征向量 $\mathbf { U } ^ { * }$ 之间的折中。同时与第一种共正则化方法不同的是，我们可以对每一个正则化项设置一个参数来反映它的重要性。

这里的优化方法和上面的还是一样的，通过固定其他特征向量对单个特征向量进行优化。不同的地方在于需要对 $\mathbf { U } ^ { * }$ 进行优化，我们可以固定其他变量，然后对他进行优化。

只有对 $\mathbf { U } ^ { * }$ 进行优化时，和第一种共正则化方法不同，需要优化以下式子：

$\max _ { \mathbf { U } ^ { * } \in \mathbb { R } ^ { n } \times k } \sum _ { y } \lambda _ { v } t r \left( \mathbf { U } ^ { ( v ) } \mathbf { U } ^ { ( v ) ^ { T } } \mathbf { U } ^ { * } \mathbf { U } ^ { * ^ { T } } \right)$

$\text { s.t. } \mathbf { U } ^ { * ^ { T } } \mathbf { U } ^ { * } = I$

然后由矩阵的迹的性质tr(AB)=tr(BA)和tr(mA+nB)=mtr(A)+ntr(B)可以得到：

$\max _ { \mathbf { U } \cdot \in \mathbb { R } ^ { x } \times k } \operatorname { tr } \left\{ \mathbf { U } ^ { * ^ { T } } \left( \sum _ { v } \lambda _ { v } \left( \mathbf { U } ^ { ( v ) } \mathbf { U } ^ { ( v ) ^ { T } } \right) \right) \mathbf { U } ^ { * } \right\} ，\text { s.t. } \quad \mathbf { U } ^ { * ^ { T } } \mathbf { U } ^ { * } = I$

然后就又将这个问题转化成了单视图谱聚类的目标函数形式。对应的拉普拉斯矩阵为： $\sum _ { v } \lambda _ { v } \left( \mathbf { U } ^ { ( v ) } \mathbf { U } ^ { ( v ) ^ { T } } \right)$

使用第二种基于中心的共正则化和第一种共正则化的另一个差别在于这种方法可以直接得到最终的特征向量集合 $\mathbf { U } ^ { * }$ ，然后可以直接对他应用k均值等聚类算法进行聚类。而第一种共正则化方法需要对得出的所有特征向量集合进行拼接等处理步骤。

基于中心的共正则化方法一个缺点是容易受到有噪声的视图的影响，为了解决这个问题，需要仔细的选择每个视图对应的权重 $\lambda$ 。

参考论文：Co-regularized Spectral Clustering，Abhishek Kumar∗，Piyush Rai∗，Hal Daum ́e III.

2018-11-20

Co-regularized Spectral Clustering多视图谱聚类算法介绍

Pairwise Co-regularization成对共正则化

Extension to Multiple Views扩展到多个视图

Centroid-Based Co-regularization基于中心的共正则化

欢迎赞赏

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

大数据，机器学习，人工智能

人工智能/模式识别/机器学习精华专题

机器学习与数据挖掘

机器学习和人工智能入门

机器学习