学习日记_20241126_聚类方法（谱聚类Spectral Clustering）

前言

提醒：
文章内容为方便作者自己后日复习与查阅而进行的书写与发布，其中引用内容都会使用链接表明出处（如有侵权问题，请及时联系）。
其中内容多为一次书写，缺少检查与订正，如有问题或其他拓展及意见建议，欢迎评论区讨论交流。

---

聚类算法

聚类算法在各种领域中有广泛的应用，主要用于发现数据中的自然分组和模式。以下是一些常见的应用场景以及每种算法的优缺点：

经典应用场景

1. 市场细分：根据消费者的行为和特征，将他们分成不同的群体，以便进行有针对性的营销。

2. 图像分割： 将图像划分为多个区域或对象，以便进行进一步的分析或处理。

3. 社交网络分析：识别社交网络中的社区结构。

4. 文档分类：自动将文档分组到不同的主题或类别中。

5. 异常检测识别数据中的异常点或异常行为。

6. 基因表达分析：在生物信息学中，根据基因表达模式对基因进行聚类。

谱聚类（Spectral Clustering）

谱聚类（Spectral Clustering）是一种基于图论和线性代数的聚类方法，广泛应用于处理复杂的聚类结构。下面是谱聚类的优缺点概述：

优点

1. 能够识别任意形状的聚类：与传统的基于距离的聚类方法（如 K-Means）不同，谱聚类能够处理形状复杂的聚类。它通过构建图和分析其特征向量，可以捕捉到非凸形状的聚类。

2. 利用全局信息：谱聚类通过计算数据点之间的相似性矩阵，从而考虑了数据的全局结构，而不仅仅是局部邻域的信息，能更好地捕捉到数据的内在关系。

3. 降维能力： 谱聚类利用特征值分解可以有效地将高维数据映射到低维空间，这对于高维数据集尤其重要，可以减少噪声和冗余特征的影响。

4. 灵活性强：可以通过选择不同的相似性度量和距离函数，适应不同类型的数据和聚类需求。

缺点

1. 计算复杂度高：谱聚类的计算通常涉及特征值分解或奇异值分解，其计算复杂度为 $O(n^3)$，其中 $n$ 是数据点的数量。因此在大规模数据集上，谱聚类可能会变得非常耗时和资源密集。

2. 对参数敏感：谱聚类的效果可能对参数（如相似性矩阵的构建方式、聚类数目等）非常敏感。选择合适的参数可能需要经验和调试。

3. 对噪声和异常值敏感：谱聚类对噪声和异常值较为敏感，这些点可能会影响相似性矩阵的构建，导致聚类结果不理想。

4. 需要预定义聚类数：与许多聚类算法一样，谱聚类通常需要事先指定要生成的聚类数量，这在实际应用中可能不够灵活。

5. 可解释性差：尽管谱聚类能够产生良好的聚类效果，但其结果的可解释性相对较差，尤其是在高维数据中，难以直观理解聚类的形成原因。

总结

谱聚类是一种强大而灵活的聚类方法，特别适合处理复杂和非线性的数据分布。然而，其高计算复杂度和对参数的敏感性限制了其在某些应用中的实用性。在选择聚类方法时，需要根据实际数据的特点和聚类的需求权衡这些优缺点。

简单实例（函数库实现）

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.cluster import SpectralClustering# 生成模拟数据：两个半月形状的聚类
X, _ = make_moons(n_samples=300, noise=0.1, random_state=42)# 使用谱聚类进行聚类
n_clusters = 2  # 指定要生成的聚类数量
spectral_clustering = SpectralClustering(n_clusters=n_clusters, affinity='nearest_neighbors', random_state=42)
labels = spectral_clustering.fit_predict(X)# 可视化结果
plt.figure(figsize=(8, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=50)
plt.title('Spectral Clustering of Moons Dataset')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

data数据分布与代码运行结果：
数据生成介绍：学习日记_20241115_聚类方法（DBSCAN）
可参考该博客简“简单实例（函数库实现）”部分。
结果：

数学表达

谱聚类（Spectral Clustering）是一种基于图论的聚类方法，它通过将数据点看作图中的节点，并利用图中的谱（即图的拉普拉斯矩阵的特征值和特征向量）来进行聚类。谱聚类在处理复杂数据集时，往往能取得比传统聚类方法更好的效果。

基本步骤

1. 构建相似度图：首先，需要根据数据点之间的相似度构建一个无向加权图 $G=(V,E)$，其中 $V$ 是节点集，表示数据点，$E$ 是边集，边的权重表示数据点之间的相似度。常用的相似度函数有高斯核函数（Gaussian Kernel）：
   $$w_{ij}=\exp \left(-\frac{\Vert x_i-x_j{\Vert }^2}{2{\sigma }^2}\right)$$
   其中 $x_i$ 和 $x_j$ 是数据点，$\sigma$ 是带宽参数。
2. 构建图的拉普拉斯矩阵：图的拉普拉斯矩阵 $L$ 定义为：
   $$L=D-W$$
   度矩阵 $D$：
   $$D=\text{diag}(d_1,d_2,\dots ,d_n)\text{其中}{d}_i=\sum _j{w}_{ij}$$
   相似度矩阵 $W$：
   $$W=[w_{ij}]\text{其中}{w}_{ij}=\exp \left(-\frac{\Vert x_i-x_j{\Vert }^2}{2{\sigma }^2}\right)$$
   其中 $W$ 是权重矩阵，$D$是度矩阵，$D_{ii}$ 是节点 $i$ 的度，即与节点 $i$ 相连的边的权重之和。
   diag()可以将其元素放置在矩阵的主对角线上，其他位置为0，从而构造出一个对角矩阵。
3. 计算拉普拉斯矩阵的特征值和特征向量：对拉普拉斯矩阵 $L$ 进行特征分解，得到特征值和对应的特征向量。谱聚类通常关注最小的 $k$ 个非零特征值对应的特征向量。
   特征分解:
   $$L{u}_i={\lambda }_i{u}_i\text{对于}i=1,2,\dots ,k$$
   其中 ${\lambda }_i$ 是特征值，$u_i$ 是对应的特征向量。
   特征向量矩阵 $U$：
   $$U=[u_1,u_2,\dots ,u_k]$$
4. 构建特征向量矩阵：将这 $k$ 个特征向量组成一个矩阵 $U$，其中每一列是一个特征向量。
5. 聚类：将矩阵 $U$ 的行看作新的数据点，使用传统的聚类算法（如 k-means）对这些新数据点进行聚类。

手动实现

import numpy as np
from scipy.sparse.csgraph import laplacian
from scipy.linalg import eigh
from sklearn.cluster import KMeans
from sklearn.metrics.pairwise import rbf_kerneldef spectral_clustering(X, n_clusters=2, gamma=1.0):"""手动实现谱聚类参数:X: 形状为 (n_samples, n_features) 的 ndarray输入数据。n_clusters: int, 默认=2聚类的数量。gamma: float, 默认=1.0RBF核函数的参数（用于相似度矩阵）。返回:labels: 形状为 (n_samples,) 的 ndarray每个样本的预测标签。"""# 步骤1: 计算相似度矩阵（RBF核）affinity_matrix = rbf_kernel(X, gamma=gamma)# 步骤2: 计算拉普拉斯矩阵（归一化拉普拉斯矩阵）# 计算度矩阵degree_matrix = np.diag(np.sum(affinity_matrix, axis=1))# 计算拉普拉斯矩阵laplacian_matrix = degree_matrix - affinity_matrix# 步骤3: 计算拉普拉斯矩阵的特征值和特征向量# 计算最小的k个特征向量eigenvalues, eigenvectors = eigh(laplacian_matrix, subset_by_index=[0, n_clusters - 1])# 步骤4: 使用特征向量形成矩阵（嵌入）# 特征向量矩阵的行表示样本在新特征空间中的坐标X_embedding = eigenvectors# 步骤5: 在新特征空间中使用K-means对样本进行聚类kmeans = KMeans(n_clusters=n_clusters)labels = kmeans.fit_predict(X_embedding)return labels# 示例用法
if __name__ == "__main__":from sklearn.datasets import make_blobsimport matplotlib.pyplot as plt# 生成合成数据X, y = make_blobs(n_samples=300, centers=3, random_state=42)# 应用谱聚类labels = spectral_clustering(X, n_clusters=3)# 绘制结果plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')plt.title("Spectral Clustering Result")plt.show()

数据与结果为：