谱聚类

作者: 魏允臣 | 来源:发表于2019-01-27 01:12 被阅读0次

背景：谱聚类（Spectral Clustering）于 2006 年由 Ulrike von Luxburg 公布在论文 A Tutorial on Spectral Clustering 上。
本质：一种观点认为，谱聚类的本质就是通过拉普拉斯矩阵变换得到其特征向量组成的新矩阵的 K-Means 聚类，而其中的拉普拉斯矩阵变换可以被简单地看作是降维的过程。而谱聚类中的「谱」其实就是矩阵中全部特征向量的总称。

拉普拉斯矩阵

拉普拉斯矩阵（Laplacian Matrix），也称为基尔霍夫矩阵，是无向图的一种矩阵表示形式。对于一个有 $n$ 个顶点的图，其拉普拉斯矩阵定义为： $L_{n \times n} = D - A \tag{1}$ 其中， $D$ 为图的度矩阵， $A$ 为图的邻接矩阵。

度矩阵

对于有边连接的两个点 $v_i$ 和 $v_j$ ， $w_{ij}>0$ ，对于没有边连接的两个点 $v_i$ 和 $v_j$ ， $w_{ij}=0$ 。对于图中的任意一个点 $v_i$ ，它的度 $d_i$ 定义为和它相连的所有边的权重之和，即 $d_i = \sum\limits_{j=1}^{n}w_{ij} \tag{2}$ 度矩阵是一个对角矩阵，主角线上的值由对应的顶点的度组成。
$D = \left( \begin{array}{ccc} d_1 & \ldots & \ldots \\ \ldots & d_2 & \ldots \\ \vdots & \vdots & \ddots \\ \ldots & \ldots & d_n \end{array} \right) \tag{3}$

邻接矩阵

对于一张有 $n$ 个顶点的图 $L_{n \times n}$ ，其邻接矩阵 $A$ 为任意两点之间的权重值 $w_{ij}$ 组成的矩阵： $A=\begin{pmatrix} w_{11} & \cdots & w_{1n}\\ \vdots & & \vdots \\ w_{n1} & \cdots & w_{nn} \end{pmatrix} \tag{4}$ 对于构建邻接矩阵 $A$ ，一般有三种方法，分别是： $\epsilon$ -邻近法，全连接法和 K-近邻法。
第一种方法， $\epsilon$ -邻近法通过设置了一个阈值 $\epsilon$ ，再求解任意两点 $x_{i}$ 和 $x_{j}$ 间的欧式距离 $s_{ij}$ 来度量相似性。然后，根据 $s_{ij}$ 和 $\epsilon$ 的大小关系，定义 $w_{ij}$ 如下： $w_{ij}= \begin{cases} 0& {s_{ij} > \epsilon}\\ \epsilon& {{s_{ij} \leq \epsilon}} \end{cases} \tag{5}$ 第二种方法，全连接法通过选择不同的核函数来定义边权重，常用的有多项式核函数，高斯核函数和 Sigmoid 核函数。例如，当使用高斯核函数 RBF 时， $w_{ij}$ 定义如下： $w_{ij}=s_{ij}=exp(-\frac{||x_i-x_j||_2^2}{2\sigma^2}) \tag{6}$ 除此之外，K-邻近法也可以被用于生成邻接矩阵。当我们令 $x_i$ 对应图中的一个节点 $v_i$ 时，如果 $v_j$ 属于 $v_i$ 的前 $k$ 个最近邻节点集合，则连接 $v_j$ 和 $v_i$ 。
但是，此种方法会产生不对称的有向图。因此，将有向图转换为无向图的方法有两种：
第一，忽略方向性，即如果 $v_j$ 属于 $v_i$ 的前 $k$ 个最近邻节点集，或 $v_i$ 属于 $v_j$ 的前 $k$ 个最近邻节点集，则连接 $v_j$ 和 $v_i$
$w_{ij}=w_{ji}= \begin{cases} 0& {x_i \notin KNN(x_j) \;and \;x_j \notin KNN(x_i)}\\ exp(-\frac{||x_i-x_j||_2^2}{2\sigma^2})& {x_i \in KNN(x_j)\; or\; x_j \in KNN(x_i}) \end{cases} \tag{7}$ 第二是当且仅当 $v_j$ 属于 $v_i$ 的前 $k$ 个最近邻节点集，且 $v_i$ 属于 $v_j$ 的前 $k$ 个最近邻节点集时连接 $v_j$ 和 $v_i$ 。第二种方法体现了相互性。 $w_{ij}=w_{ji}= \begin{cases} 0& {x_i \notin KNN(x_j) \;or\;x_j \notin KNN(x_i)}\\ exp(-\frac{||x_i-x_j||_2^2}{2\sigma^2})& {x_i \in KNN(x_j)\; and \; x_j \in KNN(x_i}) \end{cases} \tag{8}$ 那么，对于 1.1 中的无向图，它对应的邻接矩阵、度矩阵以及拉普拉斯矩阵如下。

邻接矩阵为：

对于无向图 G 的切图，我们的目标是将图

from sklearn.cluster import KMeans

plt.scatter(noisy_circles[:,0], noisy_circles[:,1], c=KMeans(n_clusters=2).fit_predict(noisy_circles))

参考上面的谱聚类流程，我们知道首先需要计算由数据生成无向图的邻接矩阵 $A$ ，本次实验使用 K-近邻方法计算无向图中边对应的相似度权重。下面通过 knn_similarity_matrix(data, k) 函数实现：

def knn_similarity_matrix(data, k):
    zero_matrix = np.zeros((len(data), len(data)))
    w = np.zeros((len(data), len(data)))
    
    for i in range(len(data)):
        for j in range(i + 1, len(data)):
            zero_matrix[i][j] = zero_matrix[j][i] = np.linalg.norm(data[i] - data[j]) # 计算欧式距离
    
    for i, vector in enumerate(zero_matrix):
        vector_i  = np.argsort(vector)
        w[i][vector_i[1 : k + 1]] = 1

    w = (np.transpose(w) + w)/2
    
    return w

得到邻接矩阵 $A$ ，就可以计算得到度矩阵 $D$ ，以及对应的拉普拉斯矩阵 $L$ ，进而实现整个谱聚类方法：

def spectral_clustering(data, k, n):  
    
    # 计算近邻矩阵、度矩阵、拉普拉斯矩阵
    A_matrix = knn_similarity_matrix(data, k) 
    D_matrix = np.diag(np.power(np.sum(A_matrix, axis=1), -0.5))  
    L_matrix = np.eye(len(data)) - np.dot(np.dot(D_matrix, A_matrix), D_matrix)  

    # 计算特征值和特征向量
    eigvals, eigvecs = np.linalg.eig(L_matrix)
    
    # 选择前 n 个最小的特征向量
    indices = np.argsort(eigvals)[: n]  
    k_eigenvectors = eigvecs[:, indices]
    k_eigenvectors
    
    # 使用 K-Means 完成聚类
    clusters = KMeans(n_clusters=n).fit_predict(k_eigenvectors)

    return clusters

最后，我们定义参数 k=5, 并将数据集聚为 2 类。

sc_clusters = spectral_clustering(noisy_circles, k=5, n=2)
sc_clusters

Out[6]:
array([0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1,
              0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0,
              1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0,
              0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1,
              1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1,
              0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1,
              0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1,
              1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1,
              1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1,
              1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1,
              1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1,
              1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1,
              1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0,
              0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1], dtype=int32)

根据聚类标签可视化数据集，可以看到谱聚类的效果是非常不错的。

plt.scatter(noisy_circles[:,0], noisy_circles[:,1], c=sc_clusters)

scikit-learn 中的谱聚类

scikit-learn 提供了谱聚类的实现方法，具体为 sklearn.cluster.SpectralClustering()：

sklearn.cluster.SpectralClustering(n_clusters=8, eigen_solver=None, random_state=None, n_init=10, gamma=1.0, affinity='rbf', n_neighbors=10, eigen_tol=0.0, assign_labels='kmeans', degree=3, coef0=1, kernel_params=None, n_jobs=1)

其主要参数有：

n_clusters：聚类簇数量。
eigen_solver：特征值求解器。
gamma：affinity 使用核函数时的核函数系数。
affinity：邻接矩阵计算方法，可选择核函数、k-近邻以及 $\epsilon$ -邻近法。
n_neighbors：邻接矩阵选择 k-近邻法时的 k 值。
assign_labels：最终聚类方法，默认为 K-Means。
谱聚类在很多时候会被用于图像分割，我们尝试使用谱聚类的 scikit-learn 实现来完成一个有趣的例子。该例子参考自 scikit-learn 官方文档。

首先，我们需要生成一幅示例图像，图像中有几个大小不等的圆，且存在噪点。

"""
1. 生成 100px * 100px 的图像
2. 在图像中添加 4 个圆
3. 添加随机噪声点
"""

l = 100
x, y = np.indices((l, l))

center1 = (28, 24)
center2 = (40, 50)
center3 = (67, 58)
center4 = (24, 70)

radius1, radius2, radius3, radius4 = 16, 14, 15, 14

circle1 = (x - center1[0]) ** 2 + (y - center1[1]) ** 2 < radius1 ** 2
circle2 = (x - center2[0]) ** 2 + (y - center2[1]) ** 2 < radius2 ** 2
circle3 = (x - center3[0]) ** 2 + (y - center3[1]) ** 2 < radius3 ** 2
circle4 = (x - center4[0]) ** 2 + (y - center4[1]) ** 2 < radius4 ** 2

img = circle1 + circle2 + circle3 + circle4
mask = img.astype(bool)
img = img.astype(float)

img += 1 + 0.2 * np.random.randn(*img.shape)

plt.figure(figsize=(5, 5))
plt.imshow(img)

接下来，我们使用谱聚类方法完成图像边缘检测，并得到处理后的图像。

"""
1. 生成 100px * 100px 的图像
2. 在图像中添加 4 个圆
3. 添加随机噪声点
"""

from sklearn.feature_extraction import image
from sklearn.cluster import spectral_clustering

graph = image.img_to_graph(img, mask=mask) # 图像处理为梯度矩阵
graph.data = np.exp(-graph.data / graph.data.std()) # 正则化

labels = spectral_clustering(graph, n_clusters=4)
label_im = -np.ones(mask.shape)
label_im[mask] = labels

plt.figure(figsize=(5, 5))
plt.imshow(label_im)

谱聚类的优势

谱聚类演化于图论，是一种原理简洁且效果不错的聚类方法。相比于 K-Means，谱聚类主要有以下优点。

适用于各类形状的数据分布聚类。
计算速度较快，尤其是在大数据集上明显优于其他算法。
避免了 K-Means 会将少数离群点划为一类的现象。

D. Cai 等（DOI: 10.1109/TKDE.2005.198）曾经在 TDT2 和 Reuters-21578 基准聚类数据集上测试过谱聚类和 K-Means 的聚类准确率表现，结果如下：

	TDT2	TDT2	Reuters-21578	Reuters-21578
k 值	K-Means	谱聚类	K-Means	谱聚类
2	0.989	0.998	0.871	0.923
3	0.974	0.996	0.775	0.816
4	0.959	0.996	0.732	0.793
…	…	…	…	…
9	0.852	0.984	0.553	0.625
10	0.835	0.979	0.545	0.615

可以看出，谱聚类的表现普遍优于 K-Means。
谱聚类也有一些缺点。例如，由于最后使用的 K-Means 聚类，所以要提前指定聚类数量。另外，当使用 K-近邻生成邻接矩阵时还需要指定最近邻样本数量，对参数是比较敏感的。

谱聚类

拉普拉斯矩阵

度矩阵

邻接矩阵

scikit-learn 中的谱聚类

谱聚类的优势

聚类方法选择

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读