深入理解：谱聚类及其算法

需积分: 9 87 浏览量更新于2024-07-21 收藏 539KB PDF 举报

"这篇文档是关于谱聚类的教程，由Ulrike von Luxburg撰写，发表在2007年的《统计与计算》期刊上。文章深入探讨了谱聚类的原理、算法及其优缺点，并介绍了不同的图拉普拉斯矩阵及其性质。" 正文: 谱聚类是一种在近年来备受瞩目的现代聚类算法，由于其简洁的实现方式、高效的标准线性代数软件求解能力，以及在很多情况下超越传统如k-means算法的性能，使其成为数据科学领域中的热门工具。然而，对于初次接触的人来说，谱聚类可能显得有些神秘，其工作原理并不直观。本文档的主要目标是为读者提供关于谱聚类的直觉理解。首先，作者介绍了多种类型的图拉普拉斯矩阵，这是谱聚类算法的基础。图拉普拉斯矩阵在数学上表示了图的结构信息，包括节点之间的连接强度和相对关系。它们的基本性质，如对称性和正定性，对于理解和应用谱聚类至关重要。接下来，文档详述了最常见的谱聚类算法。这些算法通常基于图的谱分解，通过解决与图拉普拉斯矩阵相关的特征值问题来发现数据的内在结构。其中，谱聚类的一个关键步骤是将数据转换到特征空间，然后利用这个空间中的信息进行聚类。文档还从不同角度出发，逐步推导了这些算法，帮助读者从多个视角理解其工作机理。这些方法可能包括基于最小割、拉普拉斯正则化或图切割等角度。通过这些推导，读者可以更好地理解为什么谱聚类能有效识别数据集中的自然群组。此外，作者讨论了各种谱聚类算法的优缺点。例如，谱聚类能够处理非凸形状的聚类，但在处理大规模数据集时可能会遇到计算效率问题。同时，与k-means等方法相比，谱聚类通常对初始条件不那么敏感，但可能需要预先指定簇的数量。关键词涵盖了谱聚类的核心概念，包括谱聚类本身和图拉普拉斯矩阵，这些都是理解这一领域所必须掌握的关键术语。这篇教程提供了对谱聚类深入而全面的理解，不仅涵盖了基本理论，还包括了实际应用中的考量因素，是学习和研究谱聚类的宝贵资源。

4. 0 is an eigenvalue of L

with the constant one vector

as eigenvector. 0 is an eigenvalue of

sym

with eigenvector D

1/2

5. L

sym

and L

are positive semi-deﬁnite and have n non-negative real-valued eigenvalues 0 =

≤ . . . ≤ λ

Proof. Part (1) can be proved similarly to Part (1) of Proposition 1.

Part (2) can be seen immediately by multiplying the eigenvalue equation L

sym

w = λw with D

−1/2

from the left and substituting u = D

−1/2

Part (3) follows directly by multiplying the eigenvalue equation L

u = λu with D from the left.

Part (4): The ﬁrst statement is obvious as L

= 0, the second statement follows from (2).

Part (5): The statement about L

sym

follows from (1), and then the statement about L

follows from

(2). 2

As it is the case for the unnormalized graph Laplacian, the multiplicity of the eigenvalue 0 of the

normalized graph Laplacian is related to the numb er of connected components:

Proposition 4 (Number of connected components and spectra of L

sym

and L

) Let G be

an undirected graph with non-negative weights. Then the multiplicity k of the eigenvalue 0 of both L

and L

sym

equals the number of connect ed components A

, . . . , A

in the graph. For L

, the eigenspace

of 0 is spanned by the indicator vectors

of those components. For L

sym

, the eigenspace of 0 is

spanned by the vectors D

1/2

Proof. The proof is analogous to the one of Proposition 2, using Proposition 3. 2

4 Spectral C lust eri ng Algorithms

Now we would like to state the most common spectral clustering algorithms. For references and the

history of spectral clustering we refer to Section 9. We assume that our data consists of n “points”

, . . . , x

which can be arbitrary objects. We measure their pairwise similarities s

= s(x

, x

)

by some similarity function which is symmetric and non-negative, and we denote the corresponding

similarity matrix by S = (s

)

i,j=1...n

Unnormalized spectral clustering

Input: Similarity matrix S ∈

n×n

, number k of clusters to construct.

• Construct a similarity graph by one of the ways described in Section 2. Let W

be its weighted adjacency matrix.

• Compute the unnormalized Laplacian L.

• Compute the ﬁrst k eigenvectors u

, . . . , u

of L.

• Let U ∈

n×k

be the matrix containing the vectors u

, . . . , u

as columns.

• For i = 1, . . . , n, let y

∈

be the vector corresponding to the i-th row of U.

• Cluster the points (y

)

i=1,...,n

with the k-means algorithm into clusters

, . . . , C

Output: Clusters A

, . . . , A

with A

= {j| y

∈ C

There are two diﬀerent versions of normalized spectral clustering, depending which of the normalized

graph Laplacians is used. We name both algorithms after two popular papers, for more references and

history please see Sec tion 9.

Normalized spectral clustering according to Shi and Malik (2000)

Input: Similarity matrix S ∈

n×n

, number k of clusters to construct.

• Construct a similarity graph by one of the ways described in Section 2. Let W

be its weighted adjacency matrix.

• Compute the unnormalized Laplacian L.

• Compute the ﬁrst k generalized eigenvectors u

, . . . , u

of the generalized eigenprob-

lem Lu = λDu.

• Let U ∈

n×k

be the matrix containing the vectors u

, . . . , u

as columns.

• For i = 1, . . . , n, let y

∈

be the vector corresponding to the i-th row of U.

• Cluster the points (y

)

i=1,...,n

with the k-means algorithm into clusters

, . . . , C

Output: Clusters A

, . . . , A

with A

= {j| y

∈ C

Note that this algorithm uses the generalized eigenvectors of L, which according to Proposition 3

correspond to the eigenvectors of the matrix L

. So in fact, the algorithm works with eigenvectors of

the normalized Laplacian L

, and hence is called normalized spectral clustering. The next algorithm

also uses a normalized Laplacian, but this time the matrix L

sym

instead of L

. As we will see, this

algorithm needs to introduce an additional row normalization step which is not needed in the other

algorithms. The reasons will become clear in Section 7.

Normalized spectral clustering according to Ng, Jordan, and Weiss (2002)

Input: Similarity matrix S ∈

n×n

, number k of clusters to construct.

• Construct a similarity graph by one of the ways described in Section 2. Let W

be its weighted adjacency matrix.

• Compute the normalized Laplacian L

sym

• Compute the ﬁrst k eigenvectors u

, . . . , u

of L

sym

• Let U ∈

n×k

be the matrix containing the vectors u

, . . . , u

as columns.

• Form the matrix T ∈

n×k

from U by normalizing the rows to norm 1,

that is set t

= u

)

1/2

• For i = 1, . . . , n, let y

∈

be the vector corresponding to the i-th row of T .

• Cluster the points (y

)

i=1,...,n

with the k-means algorithm into clusters C

, . . . , C

Output: Clusters A

, . . . , A

with A

= {j| y

∈ C

All three algorithms stated above look rather similar, apart from the fact that they use three diﬀerent

graph Laplacians. In all three algorithms, the main trick is to change the representation of the abstract

data points x

to points y

∈

. It is due to the properties of the graph Laplacians that this change of

representation is useful. We will see in the next sections that this change of representation enhances

the cluster-properties in the data, so that clusters can be trivially detected in the new representation.

In particular, the simple k-means clustering algorithm has no diﬃculties to detect the clusters in this

new representation. Readers not familiar with k-means can read up on this algorithm in numerous

剩余31页未读，继续阅读

qq_33520288

粉丝: 0
资源: 1

深入理解：谱聚类及其算法

QT聚类(Quality Threshold Clustering)

层次聚类hierarchical-clustering

轨迹聚类-trajectory-clustering

spectral clustering谱聚类_spectralclustering_聚类_谱聚类_

GMM聚类.zip_GMM_GMM 聚类_clustering_gmm聚类_聚类

层次聚类 hierarchical clustering

聚类_clustering_

clustering-master.zip_clustering matlab_子空间聚类_稀疏子空间_稀疏聚类_稀疏聚类 ma

spectural_clustering_聚类_谱聚类_谱聚类算法_

Clustering-master.zip_Clustering-master_聚类数据集_聚类算法

最新资源