为什么是拉普拉斯算子？

光谱聚类的主要思想是：

1. 查找数据的图形表示
2. 将图划分为个高度互连和低内部连接的“集群”$k$

步骤 2. 可以重新表述为找到将图形分成个分量所需的最小“切割”边。$k$

事实证明*最小化割的值等同于最小化拉普拉斯 的函数：$L = D - W$

其中$H \in \mathbb{R}^{n \times k}$$k$个顶点集$A_1,...,A_k$的指示向量。

注意：的定义的情况下，该解决方案通常是 NP-hard 的作为包含个特征向量作为列的矩阵来解决其条目可以采用任何实数值的宽松版本。$H$$H$$k$$L$

这些特征向量跨越由分区指示向量跨越的相同空间，该空间包含我们图的低维嵌入，其中（由于最小化问题的性质）我们的集群现在更容易分离。

拉普拉斯算子的性质

对此的直觉可能是通过认识到拉普拉斯算子在邻接矩阵中没有几个有用的属性来激发的：

• 的最小特征值为λ0，其重数等于图中连通分量的数量。$L$$\lambda_0 = 0$
• 的特征空间由这些分量的指示向量跨越。$\lambda_0$
• $L$是单数
• $L = UU^T$其中是（任意定向）图的关联矩阵（因此是半正定的）$U$$L$

进一步阅读

^{* 请参阅以下文档的第 5 章以获取完整的推导：}

^{...主要技巧是将抽象数据点的表示更改为点。正是由于图拉普拉斯算子的特性，这种表示变化是有用的。我们将在下一节中看到，这种表示的变化增强了数据中的集群属性，因此可以在新的表示中轻松检测到它们。特别是，简单的 k-means 聚类算法在这种新表示中检测聚类没有困难。$x_i [∈ \mathbb{R}^n]$$y_i ∈ \mathbb{R}^k$}

^{-光谱聚类教程(2006)}

^{如需进一步阅读，请参阅提出 he 方法的原始论文：}

^{谱聚类可以追溯到Donath 和 Hoffman (1973)，他们首先建议基于邻接矩阵的特征向量构建图分区。同年，Fiedler (1973) 发现图的二分与图拉普拉斯算子的第二个特征向量密切相关，他建议用这个特征向量来划分一个图。}

^{注意 Fiedler 本人在此之前指出，邻接矩阵（和关联矩阵）之前确实曾用于表征图：}

^{和邻接矩阵的光谱来表征图。$(0, 1)$$(0, 1, —1)$}