经典无监督方法

Posted on | In , | Visitors:
Words count in article: 3.7k | Reading time ≈ 17

本文的目的是回顾经典的无监督方法，方便笔者在失忆的时候迅速回忆起来。

目前包含如下内容：

  • PCA
  • K-Means Clustering
  • NMF

  • Spectral Clustering

PCA

可以从两个不同的角度出发，推导出PCA的优化目标。

1.方差最大化

LAMA1 任意矩阵$X \in R^{D \times n}$, 若满足$\sum_{i=1}^n x_i = \boldsymbol 0$, 则 $\frac{1}{n-1} XX^T$ 为 $X$ 的协方差矩阵，$Tr(XX^T)=\Vert X \Vert_F^2$ 为 $X$ 的方差。

把 $X$ 按行向量的形式写，第 $i$ 行用 $(x^i)^T$ 表示:

那么

第 $i$ 个维度的方差$Var(x^i)$满足

$i,j$ 两个维度的协方差$Cov(x^i, x^j)$满足

由此可知，$\frac{1}{n-1}XX^T$ 即为 $X$ 的协方差矩阵。

下面用 $W \in R^{D \times d} $ 描述投影变换， $Y=W^TX$ 表示投影之后的样本空间，很明显 $Y$ 也是中心化的，那么 $\frac{1}{n-1}YY^T$ 也表示投影后的样本的协方差矩阵。

我们希望样本在每一个维度投影后应尽可能多地保留原始空间的信息，同时为了防止信息在投影之后冗余，我们也希望每一个维度之间相互正交。于是有：

2.重构误差最小化

KMeans

NMF

1.SymNMF

Spectral Clustering

矩阵 $A$ 的特征值的全体，称为 $A$ 的谱Spectra，记为 $\lambda(A)$

0.Laplacian Matrix

0.1 Undirected Graph & affinity matrix & degree matrix

一个图 $G$ 由顶点集 $V$ 和边集 $E$ 构成，记为 $G(V,E)$

定义任意两个顶点 $v_i$ 和 $v_j$ 之间的权重 $w_{ij}$ ，无向图中 $w_{ij}=w_{ji}$ ，所有的权重共同构成邻接矩阵 $W$

顶点 $v_i$ 的度 $d_i=\sum\limits_{j=1}^n w_{ij}$ ，所有顶点的度构成的对角阵共同构成度矩阵 $D$

另外，对于任意 $A \in V$ , 我们定义 $|A|$ 表示 $A$ 中元素的个数；定义 $vol(A)=\sum\limits_{i \in A} d_i$ 表示 $A$ 中所有点的总度数

0.2 similarity matrix

一般无法直接获得邻接矩阵，需要人为设计相似度矩阵来近似邻接矩阵。

设计的基本原则是

距离越近的两个样本点之间的相似度越大，距离越远相似度越小。一般大于0。

实际操作中，最常用的是使用高斯核函数来定义权重：

0.3 Laplacian Matrix

它有如下性质：

  1. $L$ 是对称矩阵；

  2. $L$ 的特征值都是实数；

  3. 除了对角线元素非负，其余都非正。

  4. 对于任意向量 $f \in R^n$, 有

  5. $L$ 半正定;

  6. $L\boldsymbol1=\boldsymbol 0, \boldsymbol1^TL\boldsymbol 1=0$;

  7. $L$ 有 $n$ 个非负实特征值，且 $0=\lambda_1\leq \lambda_2 \leq \dots \leq \lambda_n$. ( $L \boldsymbol 1 = \boldsymbol 0$ )

  8. $L$ 的 $0$ 特征值的重数等于图中连通分量的个数，且每个特征向量为对应连通分量的指示向量。

    Proof：

    • 当连通分量个数为$1$; 假设 $0$ 特征值对应的特征向量为 $f$, 即$Lf=0$，所以$f^TLf=0$，又因为$ w_{ij} > 0 $, 所以必有 $f_i = f_j = 1 $。也即0特征值只有一个对应的特征向量，所以$0$特征值重数为$1$。
    • 当连通分量个数为 $k$; 不失一般性，将 $W$ 根据连通性重排成块对角矩阵，同样对于 $L$ 有相应的块对角结构。

对于任意一个对角块 $L_i$, 它也就对应了第 $i$ 个子图 $A_i$ (假设顶点个数为$n_i$)的拉普拉斯矩阵。由于 $A_i$ 是全连通的，其连通分量等于其$0$特征值的重数$1$，对应的特征向量也即是指示向量 $\boldsymbol1$, 其余$n-n_i$维用$0$填充。

0.4 Cut

对于无向图 $G(V,E)$, 我们将它划分成互相不连通的 $k$ 个子图，每个子图的顶点集为：$A_1,A_1,\dots,A_k$, 满足 $A_i \cap A_j = \emptyset, \cup_{i=1}^k A_i=V$

对于任意两个子图的点集 $A，B \in V, A \cap B = \emptyset$, 定义 $A, B$ 之间的权重为

那么对于 $V$ 中互相不连通的 $k$ 个子图，我们定义 $G$ 上的 cut

0.5 形式化Cut

对于第 $t$ 个子图，引入指示向量 $f^t \in R^n$ , 用来指示属于第 $t$ 个子图的顶点:

那么有

于是我们就有了形式化表示两个子图间权重的数学表达式：

于是有

不失一般性，我们使用行变换将 $F$ 重排列成阶梯型矩阵，为了维持cut值不变，相应的 $L$ 也要按照乘法运算规则重排。重排后目标函数的意义就是对 $L$ 中的 $k$ 个对角块之和，第$i$ 个对角块的size为 $m \times m$, $m$ 为 $f_i\boldsymbol1$ 。

1. MinCut

对于一个聚类问题，我们的目的就是希望将数据集 $X \in R^{d \times n}$ 分割成 $k$ 个子集，每一个子集表示一类数据。根据不同的分割准则，可以引出不同的聚类算法。

  • 通过最小化每一个子集的类内散度，我们可以引出传统的KMeans

  • 下面，我们通过另一种准则：每一个子集之间的权重尽量小，引出Min-cut

前面我们已经知道，cut 就是用来衡量分割后每一个子集间的权重的，于是就很自然的可以用Min-cut的思想来描述这一准则：

然而，该问题存在Trivial Solution。因为约束$F \in Ind$ 只能限制每一个样本仅属于一类，无法保证最终一定出现$k$ 个类别。所以可能出现所有样本都聚在一个集合中的情况，$Tr(F^TLF)=Tr(f^tLf^t)=Tr(\boldsymbol1^TF\boldsymbol1)=0$。

题外话，需要注意的是，虽然有Trivial Solution, 但是在实验中我发现算法并不一定就会跑到这个解上。

为了解决这个问题，直觉上来说，我们需要在上述的约束$F \in Ind$ 之上，再添加上一些约束，保证​在分割后的 $k$ 个集合都能存有顶点。那么一个很直接的操作就是加上区间限制：

这样就能够将每一个类别的样本数目bound在 $[a, b]$, 于是就避免了Trivial的情况出现。

但是这么做，在实操中发现行不通。下面使用Coordinate Descend ，对每一个样本分别求解。

令 $F=[f_1 \ f_2 \ \dots \ f_n]^T$, 则有

回到开始的优化问题

所以 $f_i$ 的更新规则是指示 $k$ 维向量 $F_iL_i$ 中最小的那个元素的位置。$F_i\in R^{k \times n-1}$ 是除了第 $i$ 个样本之外的指示矩阵的转置，$L_i$ 是 $L$ 的第 $i$ 列。使用列变换将 $F_i$ 转换成阶梯型矩阵，$L$ 也相应地变换，得到如下图。

DSC

其中黑线即表示 $L_i$，红点对应需要更新的样本点 $i$。那么 $F_iL_i$ 的结果就是四个值，分别是四个椭圆包裹的黑线值之和。如若把 $L$ 看成样本之间的不相似性，那么这四个值即意味着第 $i$ 个样本与4个类簇的不相似性，结果就是希望样本分配到不相似性最小、也即相似性最大的那个类簇。

但是当某一个对角块很大时，意味着椭圆所包裹的值将越多，其总和也将大概率更小。因为 $L$ 中除了对角元，其余都是负数。负数的值越多，大概率总值就越小。此时当某一样本更新时，那么它大概率会分配进大的对角块。这就形成了一种类似黑洞的现象。虽然有根绳子拉住了样本不掉进去(bound约束)，但是黑洞里的值却很难再逃逸出来。

从上面的分析中，我们点出了一个很关键的东西，就是 $L$ 可以被看成描述样本间不相识性的一种特例。但是作为一种不相似矩阵， $L$ 由于其出对角线外其余元素非正，对于Coordinate Descend不太友好。于是这样我们可以扩展一下，对 $L$ 进行改造或者说寻找更work的不相识矩阵，或者相似矩阵并最大化。

2. RCut

由于MinCut存在Trivial Solution，上面我在MinCut的基础上加上了bound策略，效果并不理想。我们依旧希望样本在划分时，可以考虑到将被划分到的类簇的均衡情况。考虑每一个类簇样本数目均衡，下面引出RCut:

如果按照MinCut中 $f$ 的定义，那么 $|A_t|=(f^t)^Tf^t$; 另外根据 $W(A_t,\bar A_t)=(f^t)^TLf^t$, 我们很容易就能得到

为了方便化简，我们希望$(f^t)^Tf^t=1$, 那么很自然想到的操作就是修改 $f$ 的定义。因为修改$f$ 并不改变指示能力。

如此一来，我们得到

它表示的不再是 $L$ 中 $k$ 个对角块的和，而是加权求和，第 $t$ 个对角块的权重是 $\frac{1}{|A_t|}$。这样在样本更新时，就不再是容易地被划分到大的对角块内，因为大的对角块对应的权重就越小，这样就起到了一部分均衡作用。

但是该问题并不好解决，于是人们就想，把这个离散的问题连续化：

因为连续化之后问题变得相当简单。后续通过KMeans再补救回去。

3. NCut

考虑每一个类簇的度均衡，

$vol(A_t)=\sum\limits_{i \in A_t} d_i$

$f^TDf = \sum\limits_{i=1}^nf_i^2d_i=\sum\limits_{i \in A_t}d_i = vol(A_t)$

同样为了方便化简，我们希望 $(f^t)^TDf^t=1$, 所以有

于是

同样，该问题也不好求解，故连续化成如下求解：

令$F=D^{-1/2}H$ , 那么

令 $\hat{L} = D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}$, 有

$\hat L$ 也叫标准化Laplacian Matrix, $\hat L_{ij}=\frac{L_{ij}}{\sqrt{d_i\times d_j}}$