Spectral Clustering 谱聚类
1. 邻接矩阵
无向图 \(G = (V, E)\)，所有顶点之间的权重构成一个 \(n \times n\) 的矩阵：
\[W = \begin{bmatrix} w_{11} & w_{12} & \cdots & w_{1n} \\ w_{21} & w_{22} & \cdots & w_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ w_{n1} & w_{n2} & \cdots & w_{nn} \end{bmatrix} \]邻接矩阵 \(W\) 有 \(w_{ij} = w_{ji}\)
2. 度与度矩阵
传统的节点的度数指的是相连的边的个数，但在谱聚类问题中，有些不一样，公式如下：
\[d_i = \sum_{n}^{j = 1} w_{ij} \]即节点 \(i\) 的度数为所有邻接的边的权值之和。
由此可以得到度矩阵：
\[D = \begin{bmatrix} d_1 & 0 & \cdots & 0 \\ 0 & d_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 \end{bmatrix} \]3. 相似矩阵及衡量方法
图中各个顶点的相似度衡量主要基于距离的度量，也就是说空间两个点的距离越近，则它们越相似，距离越远，则它们越不相似。通过 样本点 之间的距离 \(s_{ij}\) 得到 相似图矩阵 \(S\) ，以此来得到 邻接矩阵 \(W\)。
在向量空间中任意两个向量 \(x_i\)
和 \(x_j\)
的距离为 \(s_{ij} = ||x_i - x_j||^2_2\)
。
以下是三种相似图衡量方法(相似矩阵的计算方法)。
-
\(\epsilon\) — 近邻法
采用欧式距离计算两个顶点的距离，设定一个阈值 \(\epsilon\)，使得：
\[w_{ij} = \begin{cases} 0, & s_{ij} > \epsilon \\ \epsilon, & s_{ij} \le \epsilon \end{cases} \] -
\(k\) 近邻法
取与顶点最近的 \(k\) 个顶点，该顶点与这 \(k\) 个顶点的权重都大于0，但这会导致最后所得的相似矩阵不一定是对称的，因为一个点 \(v_i\) 在另外一个点 \(v_j\) 的 \(k\) 个近邻中，并不能保证 \(v_i\) 也在点 \(v_j\) 的 \(k\) 个近邻中。
有两种方法可以解决不对称的问题：
- 两个顶点 \(v_i\) 与 \(v_j\) 存在其中一个点在另一个点的 \(k\) 近邻中，则令 \(w_{ij} = w_{ji} = \frac{1}{s_{ij}}\)；反之，则令 \(w_{ij} = w_{ji} = 0\) ：
- 两个顶点 \(v_i\) 与 \(v_j\) 只有在同时在对方的 \(k\) 近邻中，则令 \(w_{ij} = w_{ji} = \frac{1}{s_{ij}}\)；反之，则令 \(w_{ij} = w_{ji} = 0\) ：
-
全连接法
将所有的顶点都连接起来。然后通过度量空间中某种对称度量算子来计算顶点之间的相似度。
此处以 高斯核 \(\text{RBF}\) 函数为例（也可以是多项式核函数、 \(\text{sigmoid}\) 函数），计算两个顶点之间的相似度：
\[w_{ij} = w_{ji} = \text{exp}(- \frac{||v_i - v_j||^2_2}{2 \sigma^2}) \]高斯核函数的曲线其实也是一个高斯分布图。高斯核里有运用到euclidean distance(欧几里得距离)，顶点距离也是越远相似度越低，这和高斯核是符合的。另外高斯核的度量都是大于0，这也符合谱聚类中对于相似度量的要求。
还有一点就是，使用的二范数的平方这一度量来衡量相似度，所以这也满足了所求相似矩阵是一个对称矩阵的要求。
4. 拉普拉斯矩阵
4.1 非规范化的图拉普拉斯矩阵
也叫图拉普拉斯矩阵，此处的 \(L\) 是 非规范化的图拉普拉斯矩阵
\[L = D - W \]其中 \(D\) 为度矩阵，\(W\) 为邻接矩阵。
4.2 规范化的图拉普拉斯矩阵
有如下两种规范化图拉普拉斯矩阵：
\[L_{\text{sym}} = D^{- \frac{1}{2}}LD^{- \frac{1}{2}} = I - D^{- \frac{1}{2}}WD^{-\frac{1}{2}} \]\[L_{\text{rw}} = D^{-1}L = I - D^{-1}W \]其中 \(L_{\text{sym}}\) 为 对称矩阵 ，\(\text{sym}\) 为单词symmetric缩写； \(L_{\text{rw}}\) 与随机游走相关，超过了课程考试讨论的范围，不多说了。 主要是我也不会 。
5. 谱聚类的过程
任务是要分成 \(k\) 类，得到簇划分 \(\mathcal C = \{C_1, C_2, \cdots , C_k \}\)。
-
计算样本点之间的距离，得到 相似矩阵 $S ；
-
选择一个衡量方法（一般选择全连接法，即使用 \(\text{RBF}\) 高斯核函数 计算相似度），通过 相似矩阵 \(S\) 得到 邻接矩阵 \(W\) ；
-
根据 邻接矩阵 \(W\) 来计算得到 度矩阵 \(D\) ；
-
通过 \(L = D - W\) 计算得到 拉普拉斯矩阵 \(L\) ；
-
对 拉普拉斯矩阵 \(L\) 进行标准化，即构建 规范化拉普拉斯矩阵 为 \(D^{- \frac{1}{2}}LD^{- \frac{1}{2}}\) （一般采用第一种，当然不进行规范化也是可以的）；
-
对 拉普拉斯矩阵 进行 特征值分解，获取前 \(k\) 小的特征值对应的特征向量，构成特征矩阵 \(Q\)，有 \(Q = [q_1, q_2, \cdots, q_k]\)，其中 \(q_i\) 是大小为 \(1 \times n\) 的列向量，表示选取的第 \(i\) 小的特征向量；
-
对 特征矩阵 \(Q\) 中的所有行 \(r_1, r_2, \cdots, r_n\) 进行 聚类，一般使用 \(\text{K-means}\) 算法进行聚类，得到簇划分 \(\mathcal C = \{C_1, C_2, \cdots , C_k \}\) ；
-
得到原始数据分组 \(\mathcal A = \{A_1, A_2, \cdots , A_k \}\) ，其中 \(A_i = \{v_j | r_j \in C_i\}\) （\(v_j\) 为第 \(j\) 个样本点，\(r_j\) 为第 \(j\) 个样本点对应的所构成的 特征矩阵 \(Q\) 的行特征向量）。
PS：第 5 步可以省去，直接对 拉普拉斯矩阵 \(L\) 进行特征值分解。
6. 谱聚类核心代码
6.1 手写实现
import numpy as np
from sklearn.metrics import pairwise_distances
from sklearn.cluster import KMeans
from sklearn.cluster import SpectralClustering
X, y = ... # 数据
# 相似度矩阵，使用 RBF
def w(x, y, sigma=2.50):
return np.exp(-1.0 * (x - y).T @ (x - y) /(2 * sigma**2)) # 高斯径向基核函数
# 邻接矩阵
W = pairwise_distances(X, metric=w)
# 度矩阵
D = np.diag(W.sum(axis=1))
# 拉普拉斯矩阵
L = D - W
# 拉普拉斯矩阵规范化，不计算也行
L_norm = np.sqrt(np.linalg.inv(D)) @ L @ np.sqrt(np.linalg.inv(D))
# 特征分解
eigenvals, eigvector = np.linalg.eig(L_norm)
# 将特征值按照升序排列
ind = np.argsort(eigenvals)
eig_vec_sorted = eigvector[:,ind] #对应的特征向量也要相应调整顺序
# 取出前k个最小的特征值对应的特征向量，k和要聚类的簇数一样
k = 3
Q = eig_vec_sorted[:, :k] # 特征矩阵
# 对特征矩阵Q进行聚类 训练得到模型
model = KMeans(n_clusters=k)
Q = np.real(Q)
# 用得到的模型进行预测
y_pred = model.fit_predict(Q)
6.2 调用 sklearn 实现
from sklearn.cluster import SpectralClustering
X, y = ... # 数据
# 谱聚类
k = 3
model = SpectralClustering(n_clusters=k)
# 预测
y_pred = model.fit_predict(X)